diff options
Diffstat (limited to 'libcollections')
| -rw-r--r-- | libcollections/btree/map.rs | 198 | ||||
| -rw-r--r-- | libcollections/btree/node.rs | 294 | ||||
| -rw-r--r-- | libcollections/btree/set.rs | 41 | ||||
| -rw-r--r-- | libcollections/fmt.rs | 48 | ||||
| -rw-r--r-- | libcollections/lib.rs | 1 | ||||
| -rw-r--r-- | libcollections/slice.rs | 18 | ||||
| -rw-r--r-- | libcollections/str.rs | 269 | ||||
| -rw-r--r-- | libcollections/string.rs | 2 | ||||
| -rw-r--r-- | libcollections/vec.rs | 2 |
9 files changed, 497 insertions, 376 deletions
diff --git a/libcollections/btree/map.rs b/libcollections/btree/map.rs index 20ef273..29f3e4b 100644 --- a/libcollections/btree/map.rs +++ b/libcollections/btree/map.rs @@ -286,7 +286,7 @@ pub struct Values<'a, K: 'a, V: 'a> { } /// A mutable iterator over a BTreeMap's values. -#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")] +#[stable(feature = "map_values_mut", since = "1.10.0")] pub struct ValuesMut<'a, K: 'a, V: 'a> { inner: IterMut<'a, K, V>, } @@ -842,13 +842,13 @@ impl<K: Ord, V> BTreeMap<K, V> { // Check if right-most child is underfull. let mut last_edge = internal.last_edge(); let right_child_len = last_edge.reborrow().descend().len(); - if right_child_len < node::CAPACITY / 2 { + if right_child_len < node::MIN_LEN { // We need to steal. let mut last_kv = match last_edge.left_kv() { Ok(left) => left, Err(_) => unreachable!(), }; - last_kv.bulk_steal_left(node::CAPACITY/2 - right_child_len); + last_kv.bulk_steal_left(node::MIN_LEN - right_child_len); last_edge = last_kv.right_edge(); } @@ -856,6 +856,174 @@ impl<K: Ord, V> BTreeMap<K, V> { cur_node = last_edge.descend(); } } + + /// Splits the collection into two at the given key. Returns everything after the given key, + /// including the key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_split_off)] + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(17, "d"); + /// a.insert(41, "e"); + /// + /// let b = a.split_off(&3); + /// + /// assert_eq!(a.len(), 2); + /// assert_eq!(b.len(), 3); + /// + /// assert_eq!(a[&1], "a"); + /// assert_eq!(a[&2], "b"); + /// + /// assert_eq!(b[&3], "c"); + /// assert_eq!(b[&17], "d"); + /// assert_eq!(b[&41], "e"); + /// ``` + #[unstable(feature = "btree_split_off", + reason = "recently added as part of collections reform 2", + issue = "19986")] + pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where K: Borrow<Q> { + if self.is_empty() { + return Self::new(); + } + + let total_num = self.len(); + + let mut right = Self::new(); + for _ in 0..(self.root.as_ref().height()) { + right.root.push_level(); + } + + { + let mut left_node = self.root.as_mut(); + let mut right_node = right.root.as_mut(); + + loop { + let mut split_edge = match search::search_node(left_node, key) { + // key is going to the right tree + Found(handle) => handle.left_edge(), + GoDown(handle) => handle + }; + + split_edge.move_suffix(&mut right_node); + + match (split_edge.force(), right_node.force()) { + (Internal(edge), Internal(node)) => { + left_node = edge.descend(); + right_node = node.first_edge().descend(); + } + (Leaf(_), Leaf(_)) => { break; }, + _ => { unreachable!(); } + } + } + } + + self.fix_right_border(); + right.fix_left_border(); + + if self.root.as_ref().height() < right.root.as_ref().height() { + self.recalc_length(); + right.length = total_num - self.len(); + } else { + right.recalc_length(); + self.length = total_num - right.len(); + } + + right + } + + /// Calculates the number of elements if it is incorrect. + fn recalc_length(&mut self) { + fn dfs<K, V>(node: NodeRef<marker::Immut, K, V, marker::LeafOrInternal>) -> usize { + let mut res = node.len(); + + if let Internal(node) = node.force() { + let mut edge = node.first_edge(); + loop { + res += dfs(edge.reborrow().descend()); + match edge.right_kv() { + Ok(right_kv) => { edge = right_kv.right_edge(); }, + Err(_) => { break; } + } + } + } + + res + } + + self.length = dfs(self.root.as_ref()); + } + + /// Removes empty levels on the top. + fn fix_top(&mut self) { + loop { + { + let node = self.root.as_ref(); + if node.height() == 0 || node.len() > 0 { + break; + } + } + self.root.pop_level(); + } + } + + fn fix_right_border(&mut self) { + self.fix_top(); + + { + let mut cur_node = self.root.as_mut(); + + while let Internal(node) = cur_node.force() { + let mut last_kv = node.last_kv(); + + if last_kv.can_merge() { + cur_node = last_kv.merge().descend(); + } else { + let right_len = last_kv.reborrow().right_edge().descend().len(); + // `MINLEN + 1` to avoid readjust if merge happens on the next level. + if right_len < node::MIN_LEN + 1 { + last_kv.bulk_steal_left(node::MIN_LEN + 1 - right_len); + } + cur_node = last_kv.right_edge().descend(); + } + } + } + + self.fix_top(); + } + + /// The symmetric clone of `fix_right_border`. + fn fix_left_border(&mut self) { + self.fix_top(); + + { + let mut cur_node = self.root.as_mut(); + + while let Internal(node) = cur_node.force() { + let mut first_kv = node.first_kv(); + + if first_kv.can_merge() { + cur_node = first_kv.merge().descend(); + } else { + let left_len = first_kv.reborrow().left_edge().descend().len(); + if left_len < node::MIN_LEN + 1 { + first_kv.bulk_steal_right(node::MIN_LEN + 1 - left_len); + } + cur_node = first_kv.left_edge().descend(); + } + } + } + + self.fix_top(); + } } impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> { @@ -1144,7 +1312,7 @@ impl<'a, K, V> Iterator for Range<'a, K, V> { } } -#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")] +#[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { type Item = &'a mut V; @@ -1157,14 +1325,14 @@ impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { } } -#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")] +#[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> { fn next_back(&mut self) -> Option<&'a mut V> { self.inner.next_back().map(|(_, v)| v) } } -#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")] +#[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> { fn len(&self) -> usize { self.inner.len() @@ -1575,7 +1743,6 @@ impl<K, V> BTreeMap<K, V> { /// Basic usage: /// /// ``` - /// # #![feature(map_values_mut)] /// use std::collections::BTreeMap; /// /// let mut a = BTreeMap::new(); @@ -1590,8 +1757,8 @@ impl<K, V> BTreeMap<K, V> { /// assert_eq!(values, [String::from("hello!"), /// String::from("goodbye!")]); /// ``` - #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")] - pub fn values_mut<'a>(&'a mut self) -> ValuesMut<'a, K, V> { + #[stable(feature = "map_values_mut", since = "1.10.0")] + pub fn values_mut(&mut self) -> ValuesMut<K, V> { ValuesMut { inner: self.iter_mut() } } @@ -1654,12 +1821,21 @@ impl<'a, K: Ord, V> Entry<'a, K, V> { Vacant(entry) => entry.insert(default()), } } + + /// Returns a reference to this entry's key. + #[stable(feature = "map_entry_keys", since = "1.10.0")] + pub fn key(&self) -> &K { + match *self { + Occupied(ref entry) => entry.key(), + Vacant(ref entry) => entry.key(), + } + } } impl<'a, K: Ord, V> VacantEntry<'a, K, V> { /// Gets a reference to the key that would be used when inserting a value /// through the VacantEntry. - #[unstable(feature = "map_entry_keys", issue = "32281")] + #[stable(feature = "map_entry_keys", since = "1.10.0")] pub fn key(&self) -> &K { &self.key } @@ -1709,7 +1885,7 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> { impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { /// Gets a reference to the key in the entry. - #[unstable(feature = "map_entry_keys", issue = "32281")] + #[stable(feature = "map_entry_keys", since = "1.10.0")] pub fn key(&self) -> &K { self.handle.reborrow().into_kv().0 } diff --git a/libcollections/btree/node.rs b/libcollections/btree/node.rs index ca1cf6b..e9bc291 100644 --- a/libcollections/btree/node.rs +++ b/libcollections/btree/node.rs @@ -51,6 +51,7 @@ use core::slice; use boxed::Box; const B: usize = 6; +pub const MIN_LEN: usize = B - 1; pub const CAPACITY: usize = 2 * B - 1; /// The underlying representation of leaf nodes. Note that it is often unsafe to actually store @@ -413,6 +414,19 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { let len = self.len(); Handle::new_edge(self, len) } + + /// Note that `self` must be nonempty. + pub fn first_kv(self) -> Handle<Self, marker::KV> { + debug_assert!(self.len() > 0); + Handle::new_kv(self, 0) + } + + /// Note that `self` must be nonempty. + pub fn last_kv(self) -> Handle<Self, marker::KV> { + let len = self.len(); + debug_assert!(len > 0); + Handle::new_kv(self, len - 1) + } } impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> { @@ -602,6 +616,17 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { } } + fn correct_childrens_parent_links(&mut self, first: usize, after_last: usize) { + for i in first..after_last { + Handle::new_edge(unsafe { self.reborrow_mut() }, i).correct_parent_link(); + } + } + + fn correct_all_childrens_parent_links(&mut self) { + let len = self.len(); + self.correct_childrens_parent_links(0, len + 1); + } + /// Adds a key/value pair and an edge to go to the left of that pair to /// the beginning of the node. pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) { @@ -623,11 +648,8 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { self.as_leaf_mut().len += 1; - for i in 0..self.len()+1 { - Handle::new_edge(self.reborrow_mut(), i).correct_parent_link(); - } + self.correct_all_childrens_parent_links(); } - } } @@ -696,6 +718,13 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { (key, val, edge) } } + + fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) { + ( + self.keys_mut().as_mut_ptr(), + self.vals_mut().as_mut_ptr() + ) + } } impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { @@ -1275,105 +1304,155 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: } /// This does stealing similar to `steal_left` but steals multiple elements at once. - pub fn bulk_steal_left(&mut self, n: usize) { + pub fn bulk_steal_left(&mut self, count: usize) { unsafe { - // Get raw pointers to left child's keys, values and edges. - let (left_len, left_k, left_v, left_e) = { - let mut left = self.reborrow_mut().left_edge().descend(); - - (left.len(), - left.keys_mut().as_mut_ptr(), - left.vals_mut().as_mut_ptr(), - match left.force() { - ForceResult::Leaf(_) => None, - ForceResult::Internal(mut i) => Some(i.as_internal_mut().edges.as_mut_ptr()), - }) - }; - - // Get raw pointers to right child's keys, values and edges. - let (right_len, right_k, right_v, right_e) = { - let mut right = self.reborrow_mut().right_edge().descend(); - - (right.len(), - right.keys_mut().as_mut_ptr(), - right.vals_mut().as_mut_ptr(), - match right.force() { - ForceResult::Leaf(_) => None, - ForceResult::Internal(mut i) => Some(i.as_internal_mut().edges.as_mut_ptr()), - }) - }; - - // Get raw pointers to parent's key and value. - let (parent_k, parent_v) = { - let kv = self.reborrow_mut().into_kv_mut(); - (kv.0 as *mut K, kv.1 as *mut V) - }; + let mut left_node = ptr::read(self).left_edge().descend(); + let left_len = left_node.len(); + let mut right_node = ptr::read(self).right_edge().descend(); + let right_len = right_node.len(); // Make sure that we may steal safely. - debug_assert!(right_len + n <= CAPACITY); - debug_assert!(left_len >= n); - - // Make room for stolen elements in right child. - ptr::copy(right_k, - right_k.offset(n as isize), - right_len); - ptr::copy(right_v, - right_v.offset(n as isize), - right_len); - if let Some(edges) = right_e { - ptr::copy(edges, - edges.offset(n as isize), - right_len+1); + debug_assert!(right_len + count <= CAPACITY); + debug_assert!(left_len >= count); + + let new_left_len = left_len - count; + + // Move data. + { + let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); + let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); + let parent_kv = { + let kv = self.reborrow_mut().into_kv_mut(); + (kv.0 as *mut K, kv.1 as *mut V) + }; + + // Make room for stolen elements in the right child. + ptr::copy(right_kv.0, + right_kv.0.offset(count as isize), + right_len); + ptr::copy(right_kv.1, + right_kv.1.offset(count as isize), + right_len); + + // Move elements from the left child to the right one. + move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1); + + // Move parent's key/value pair to the right child. + move_kv(parent_kv, 0, right_kv, count - 1, 1); + + // Move the left-most stolen pair to the parent. + move_kv(left_kv, new_left_len, parent_kv, 0, 1); } - // Move elements from the left child to the right one. - let left_ind = (left_len - n) as isize; - ptr::copy_nonoverlapping(left_k.offset(left_ind + 1), - right_k, - n - 1); - ptr::copy_nonoverlapping(left_v.offset(left_ind + 1), - right_v, - n - 1); - match (left_e, right_e) { - (Some(left), Some(right)) => { - ptr::copy_nonoverlapping(left.offset(left_ind + 1), - right, - n); + left_node.reborrow_mut().as_leaf_mut().len -= count as u16; + right_node.reborrow_mut().as_leaf_mut().len += count as u16; + + match (left_node.force(), right_node.force()) { + (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { + // Make room for stolen edges. + let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); + ptr::copy(right_edges, + right_edges.offset(count as isize), + right_len + 1); + right.correct_childrens_parent_links(count, count + right_len + 1); + + move_edges(left, new_left_len + 1, right, 0, count); }, - (Some(_), None) => unreachable!(), - (None, Some(_)) => unreachable!(), - (None, None) => {}, + (ForceResult::Leaf(_), ForceResult::Leaf(_)) => { } + _ => { unreachable!(); } } + } + } - // Copy parent key/value pair to right child. - ptr::copy_nonoverlapping(parent_k, - right_k.offset(n as isize - 1), - 1); - ptr::copy_nonoverlapping(parent_v, - right_v.offset(n as isize - 1), - 1); - // Copy left-most stolen pair to parent. - ptr::copy_nonoverlapping(left_k.offset(left_ind), - parent_k, - 1); - ptr::copy_nonoverlapping(left_v.offset(left_ind), - parent_v, - 1); - - // Fix lengths of left and right child and parent pointers in children of the right - // child. - self.reborrow_mut().left_edge().descend().as_leaf_mut().len -= n as u16; - let mut right = self.reborrow_mut().right_edge().descend(); - right.as_leaf_mut().len += n as u16; - if let ForceResult::Internal(mut node) = right.force() { - for i in 0..(right_len+n+1) { - Handle::new_edge(node.reborrow_mut(), i as usize).correct_parent_link(); - } + /// The symmetric clone of `bulk_steal_left`. + pub fn bulk_steal_right(&mut self, count: usize) { + unsafe { + let mut left_node = ptr::read(self).left_edge().descend(); + let left_len = left_node.len(); + let mut right_node = ptr::read(self).right_edge().descend(); + let right_len = right_node.len(); + + // Make sure that we may steal safely. + debug_assert!(left_len + count <= CAPACITY); + debug_assert!(right_len >= count); + + let new_right_len = right_len - count; + + // Move data. + { + let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); + let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); + let parent_kv = { + let kv = self.reborrow_mut().into_kv_mut(); + (kv.0 as *mut K, kv.1 as *mut V) + }; + + // Move parent's key/value pair to the left child. + move_kv(parent_kv, 0, left_kv, left_len, 1); + + // Move elements from the right child to the left one. + move_kv(right_kv, 0, left_kv, left_len + 1, count - 1); + + // Move the right-most stolen pair to the parent. + move_kv(right_kv, count - 1, parent_kv, 0, 1); + + // Fix right indexing + ptr::copy(right_kv.0.offset(count as isize), + right_kv.0, + new_right_len); + ptr::copy(right_kv.1.offset(count as isize), + right_kv.1, + new_right_len); + } + + left_node.reborrow_mut().as_leaf_mut().len += count as u16; + right_node.reborrow_mut().as_leaf_mut().len -= count as u16; + + match (left_node.force(), right_node.force()) { + (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { + move_edges(right.reborrow_mut(), 0, left, left_len + 1, count); + + // Fix right indexing. + let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); + ptr::copy(right_edges.offset(count as isize), + right_edges, + new_right_len + 1); + right.correct_childrens_parent_links(0, new_right_len + 1); + }, + (ForceResult::Leaf(_), ForceResult::Leaf(_)) => { } + _ => { unreachable!(); } } } } } +unsafe fn move_kv<K, V>( + source: (*mut K, *mut V), source_offset: usize, + dest: (*mut K, *mut V), dest_offset: usize, + count: usize) +{ + ptr::copy_nonoverlapping(source.0.offset(source_offset as isize), + dest.0.offset(dest_offset as isize), + count); + ptr::copy_nonoverlapping(source.1.offset(source_offset as isize), + dest.1.offset(dest_offset as isize), + count); +} + +// Source and destination must have the same height. +unsafe fn move_edges<K, V>( + mut source: NodeRef<marker::Mut, K, V, marker::Internal>, source_offset: usize, + mut dest: NodeRef<marker::Mut, K, V, marker::Internal>, dest_offset: usize, + count: usize) +{ + let source_ptr = source.as_internal_mut().edges.as_mut_ptr(); + let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr(); + ptr::copy_nonoverlapping(source_ptr.offset(source_offset as isize), + dest_ptr.offset(dest_offset as isize), + count); + dest.correct_childrens_parent_links(dest_offset, dest_offset + count); +} + impl<BorrowType, K, V, HandleType> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> { @@ -1397,6 +1476,41 @@ impl<BorrowType, K, V, HandleType> } } +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> { + /// Move the suffix after `self` from one node to another one. `right` must be empty. + /// The first edge of `right` remains unchanged. + pub fn move_suffix(&mut self, + right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>) { + unsafe { + let left_new_len = self.idx; + let mut left_node = self.reborrow_mut().into_node(); + + let right_new_len = left_node.len() - left_new_len; + let mut right_node = right.reborrow_mut(); + + debug_assert!(right_node.len() == 0); + debug_assert!(left_node.height == right_node.height); + + let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); + let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); + + + move_kv(left_kv, left_new_len, right_kv, 0, right_new_len); + + left_node.reborrow_mut().as_leaf_mut().len = left_new_len as u16; + right_node.reborrow_mut().as_leaf_mut().len = right_new_len as u16; + + match (left_node.force(), right_node.force()) { + (ForceResult::Internal(left), ForceResult::Internal(right)) => { + move_edges(left, left_new_len + 1, right, 1, right_new_len); + }, + (ForceResult::Leaf(_), ForceResult::Leaf(_)) => { } + _ => { unreachable!(); } + } + } + } +} + pub enum ForceResult<Leaf, Internal> { Leaf(Leaf), Internal(Internal) diff --git a/libcollections/btree/set.rs b/libcollections/btree/set.rs index 5419d7a..765595b 100644 --- a/libcollections/btree/set.rs +++ b/libcollections/btree/set.rs @@ -477,9 +477,9 @@ impl<T: Ord> BTreeSet<T> { /// Adds a value to the set. /// - /// If the set did not have a value present, `true` is returned. + /// If the set did not have this value present, `true` is returned. /// - /// If the set did have this key present, `false` is returned, and the + /// If the set did have this value present, `false` is returned, and the /// entry is not updated. See the [module-level documentation] for more. /// /// [module-level documentation]: index.html#insert-and-complex-keys @@ -580,6 +580,43 @@ impl<T: Ord> BTreeSet<T> { pub fn append(&mut self, other: &mut Self) { self.map.append(&mut other.map); } + + /// Splits the collection into two at the given key. Returns everything after the given key, + /// including the key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_split_off)] + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(17, "d"); + /// a.insert(41, "e"); + /// + /// let b = a.split_off(&3); + /// + /// assert_eq!(a.len(), 2); + /// assert_eq!(b.len(), 3); + /// + /// assert_eq!(a[&1], "a"); + /// assert_eq!(a[&2], "b"); + /// + /// assert_eq!(b[&3], "c"); + /// assert_eq!(b[&17], "d"); + /// assert_eq!(b[&41], "e"); + /// ``` + #[unstable(feature = "btree_split_off", + reason = "recently added as part of collections reform 2", + issue = "19986")] + pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where T: Borrow<Q> { + BTreeSet { map: self.map.split_off(key) } + } } #[stable(feature = "rust1", since = "1.0.0")] diff --git a/libcollections/fmt.rs b/libcollections/fmt.rs index 710a30f..6f77d79 100644 --- a/libcollections/fmt.rs +++ b/libcollections/fmt.rs @@ -8,19 +8,16 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -//! Utilities for formatting and printing strings +//! Utilities for formatting and printing `String`s //! //! This module contains the runtime support for the `format!` syntax extension. //! This macro is implemented in the compiler to emit calls to this module in -//! order to format arguments at runtime into strings and streams. +//! order to format arguments at runtime into strings. //! //! # Usage //! //! The `format!` macro is intended to be familiar to those coming from C's -//! printf/fprintf functions or Python's `str.format` function. In its current -//! revision, the `format!` macro returns a `String` type which is the result of -//! the formatting. In the future it will also be able to pass in a stream to -//! format arguments directly while performing minimal allocations. +//! printf/fprintf functions or Python's `str.format` function. //! //! Some examples of the `format!` extension are: //! @@ -81,7 +78,7 @@ //! //! ``` //! format!("{argument}", argument = "test"); // => "test" -//! format!("{name} {}", 1, name = 2); // => "2 1" +//! format!("{name} {}", 1, name = 2); // => "2 1" //! format!("{a} {c} {b}", a="a", b='b', c=3); // => "a 3 b" //! ``` //! @@ -104,8 +101,8 @@ //! octal. //! //! There are various parameters which do require a particular type, however. -//! Namely, the `{:.*}` syntax, which sets the number of numbers after the -//! decimal in floating-point types: +//! An example is the `{:.*}` syntax, which sets the number of decimal places +//! in floating-point types: //! //! ``` //! let formatted_number = format!("{:.*}", 2, 1.234567); @@ -292,15 +289,13 @@ //! use std::fmt; //! use std::io::{self, Write}; //! -//! fmt::format(format_args!("this returns {}", "String")); -//! //! let mut some_writer = io::stdout(); //! write!(&mut some_writer, "{}", format_args!("print with a {}", "macro")); //! //! fn my_fmt_fn(args: fmt::Arguments) { //! write!(&mut io::stdout(), "{}", args); //! } -//! my_fmt_fn(format_args!("or a {} too", "function")); +//! my_fmt_fn(format_args!(", or a {} too", "function")); //! ``` //! //! The result of the `format_args!` macro is a value of type `fmt::Arguments`. @@ -316,7 +311,7 @@ //! # Syntax //! //! The syntax for the formatting language used is drawn from other languages, -//! so it should not be too alien. Arguments are formatted with python-like +//! so it should not be too alien. Arguments are formatted with Python-like //! syntax, meaning that arguments are surrounded by `{}` instead of the C-like //! `%`. The actual grammar for the formatting syntax is: //! @@ -333,7 +328,7 @@ //! precision := count | '*' //! type := identifier | '' //! count := parameter | integer -//! parameter := integer '$' +//! parameter := argument '$' //! ``` //! //! # Formatting Parameters @@ -403,11 +398,12 @@ //! println!("Hello {:5}!", "x"); //! println!("Hello {:1$}!", "x", 5); //! println!("Hello {1:0$}!", 5, "x"); +//! println!("Hello {:width$}!", "x", width = 5); //! ``` //! //! Referring to an argument with the dollar syntax does not affect the "next -//! argument" counter, so it's usually a good idea to refer to all arguments by -//! their position explicitly. +//! argument" counter, so it's usually a good idea to refer to arguments by +//! position, or use named arguments. //! //! ## Precision //! @@ -426,7 +422,7 @@ //! //! the integer `N` itself is the precision. //! -//! 2. An integer followed by dollar sign `.N$`: +//! 2. An integer or name followed by dollar sign `.N$`: //! //! use format *argument* `N` (which must be a `usize`) as the precision. //! @@ -456,6 +452,10 @@ //! // Hello {next arg (x)} is {arg 2 (0.01) with precision //! // specified in its predecessor (5)} //! println!("Hello {} is {2:.*}", "x", 5, 0.01); +//! +//! // Hello {next arg (x)} is {arg "number" (0.01) with precision specified +//! // in arg "prec" (5)} +//! println!("Hello {} is {number:.prec$}", "x", prec = 5, number = 0.01); //! ``` //! //! All print the same thing: @@ -516,12 +516,24 @@ use string; /// /// # Examples /// +/// Basic usage: +/// /// ``` /// use std::fmt; /// /// let s = fmt::format(format_args!("Hello, {}!", "world")); -/// assert_eq!(s, "Hello, world!".to_string()); +/// assert_eq!(s, "Hello, world!"); +/// ``` +/// +/// Please note that using [`format!`][format!] might be preferrable. +/// Example: +/// /// ``` +/// let s = format!("Hello, {}!", "world"); +/// assert_eq!(s, "Hello, world!"); +/// ``` +/// +/// [format!]: ../macro.format!.html #[stable(feature = "rust1", since = "1.0.0")] pub fn format(args: Arguments) -> string::String { let mut output = string::String::new(); diff --git a/libcollections/lib.rs b/libcollections/lib.rs index 34e4a42..6ab66fc 100644 --- a/libcollections/lib.rs +++ b/libcollections/lib.rs @@ -27,7 +27,6 @@ test(no_crate_inject, attr(allow(unused_variables), deny(warnings))))] #![cfg_attr(test, allow(deprecated))] // rand -#![cfg_attr(not(test), feature(slice_binary_search_by_key))] // impl [T] #![cfg_attr(not(stage0), deny(warnings))] #![feature(alloc)] diff --git a/libcollections/slice.rs b/libcollections/slice.rs index 588ad7a..cef8a33 100644 --- a/libcollections/slice.rs +++ b/libcollections/slice.rs @@ -419,8 +419,8 @@ impl<T> [T] { /// /// ```rust /// let v = &[1, 2, 3, 4, 5]; - /// for win in v.chunks(2) { - /// println!("{:?}", win); + /// for chunk in v.chunks(2) { + /// println!("{:?}", chunk); /// } /// ``` #[stable(feature = "rust1", since = "1.0.0")] @@ -759,7 +759,6 @@ impl<T> [T] { /// fourth could match any position in `[1,4]`. /// /// ```rust - /// #![feature(slice_binary_search_by_key)] /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1), /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13), /// (1, 21), (2, 34), (4, 55)]; @@ -770,7 +769,7 @@ impl<T> [T] { /// let r = s.binary_search_by_key(&1, |&(a,b)| b); /// assert!(match r { Ok(1...4) => true, _ => false, }); /// ``` - #[unstable(feature = "slice_binary_search_by_key", reason = "recently added", issue = "33018")] + #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")] #[inline] pub fn binary_search_by_key<B, F>(&self, b: &B, f: F) -> Result<usize, usize> where F: FnMut(&T) -> B, @@ -779,11 +778,10 @@ impl<T> [T] { core_slice::SliceExt::binary_search_by_key(self, b, f) } - /// Sorts the slice, in place. - /// /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`. /// - /// This is a stable sort. + /// This sort is stable and `O(n log n)` worst-case but allocates + /// approximately `2 * n` where `n` is the length of `self`. /// /// # Examples /// @@ -804,11 +802,9 @@ impl<T> [T] { /// Sorts the slice, in place, using `key` to extract a key by which to /// order the sort by. /// - /// This sort is `O(n log n)` worst-case and stable, but allocates + /// This sort is stable and `O(n log n)` worst-case but allocates /// approximately `2 * n`, where `n` is the length of `self`. /// - /// This is a stable sort. - /// /// # Examples /// /// ```rust @@ -828,7 +824,7 @@ impl<T> [T] { /// Sorts the slice, in place, using `compare` to compare /// elements. /// - /// This sort is `O(n log n)` worst-case and stable, but allocates + /// This sort is stable and `O(n log n)` worst-case but allocates /// approximately `2 * n`, where `n` is the length of `self`. /// /// # Examples diff --git a/libcollections/str.rs b/libcollections/str.rs index 2059943..d7c11f3 100644 --- a/libcollections/str.rs +++ b/libcollections/str.rs @@ -112,11 +112,6 @@ impl<S: Borrow<str>> SliceConcatExt<str> for [S] { } } -/// Deprecated, renamed to EncodeUtf16 -#[unstable(feature = "str_utf16", issue = "27714")] -#[rustc_deprecated(since = "1.8.0", reason = "renamed to EncodeUtf16")] -pub type Utf16Units<'a> = EncodeUtf16<'a>; - /// External iterator for a string's UTF-16 code units. /// /// For use with the `std::iter` module. @@ -352,230 +347,6 @@ impl str { core_str::StrExt::slice_mut_unchecked(self, begin, end) } - /// Given a byte position, returns the next `char` and its index. - /// - /// # Panics - /// - /// If `i` is greater than or equal to the length of the string. - /// If `i` is not the index of the beginning of a valid UTF-8 sequence. - /// - /// # Examples - /// - /// This example manually iterates through the code points of a string; - /// this should normally be - /// done by `.chars()` or `.char_indices()`. - /// - /// ``` - /// #![feature(str_char)] - /// #![allow(deprecated)] - /// - /// use std::str::CharRange; - /// - /// let s = "中华Việt Nam"; - /// let mut i = 0; - /// while i < s.len() { - /// let CharRange {ch, next} = s.char_range_at(i); - /// println!("{}: {}", i, ch); - /// i = next; - /// } - /// ``` - /// - /// This outputs: - /// - /// ```text - /// 0: 中 - /// 3: 华 - /// 6: V - /// 7: i - /// 8: e - /// 9: - /// 11: - /// 13: t - /// 14: - /// 15: N - /// 16: a - /// 17: m - /// ``` - #[unstable(feature = "str_char", - reason = "often replaced by char_indices, this method may \ - be removed in favor of just char_at() or eventually \ - removed altogether", - issue = "27754")] - #[inline] - #[rustc_deprecated(reason = "use slicing plus chars() plus len_utf8", - since = "1.9.0")] - #[allow(deprecated)] - pub fn char_range_at(&self, start: usize) -> CharRange { - core_str::StrExt::char_range_at(self, start) - } - - /// Given a byte position, returns the previous `char` and its position. - /// - /// Note that Unicode has many features, such as combining marks, ligatures, - /// and direction marks, that need to be taken into account to correctly reverse a string. - /// - /// Returns 0 for next index if called on start index 0. - /// - /// # Panics - /// - /// If `i` is greater than the length of the string. - /// If `i` is not an index following a valid UTF-8 sequence. - /// - /// # Examples - /// - /// This example manually iterates through the code points of a string; - /// this should normally be - /// done by `.chars().rev()` or `.char_indices()`. - /// - /// ``` - /// #![feature(str_char)] - /// #![allow(deprecated)] - /// - /// use std::str::CharRange; - /// - /// let s = "中华Việt Nam"; - /// let mut i = s.len(); - /// while i > 0 { - /// let CharRange {ch, next} = s.char_range_at_reverse(i); - /// println!("{}: {}", i, ch); - /// i = next; - /// } - /// ``` - /// - /// This outputs: - /// - /// ```text - /// 18: m - /// 17: a - /// 16: N - /// 15: - /// 14: t - /// 13: - /// 11: - /// 9: e - /// 8: i - /// 7: V - /// 6: 华 - /// 3: 中 - /// ``` - #[unstable(feature = "str_char", - reason = "often replaced by char_indices, this method may \ - be removed in favor of just char_at_reverse() or \ - eventually removed altogether", - issue = "27754")] - #[inline] - #[rustc_deprecated(reason = "use slicing plus chars().rev() plus len_utf8", - since = "1.9.0")] - #[allow(deprecated)] - pub fn char_range_at_reverse(&self, start: usize) -> CharRange { - core_str::StrExt::char_range_at_reverse(self, start) - } - - /// Given a byte position, returns the `char` at that position. - /// - /// # Panics - /// - /// If `i` is greater than or equal to the length of the string. - /// If `i` is not the index of the beginning of a valid UTF-8 sequence. - /// - /// # Examples - /// - /// ``` - /// #![feature(str_char)] - /// #![allow(deprecated)] - /// - /// let s = "abπc"; - /// assert_eq!(s.char_at(1), 'b'); - /// assert_eq!(s.char_at(2), 'π'); - /// assert_eq!(s.char_at(4), 'c'); - /// ``` - #[unstable(feature = "str_char", - reason = "frequently replaced by the chars() iterator, this \ - method may be removed or possibly renamed in the \ - future; it is normally replaced by chars/char_indices \ - iterators or by getting the first char from a \ - subslice", - issue = "27754")] - #[inline] - #[allow(deprecated)] - #[rustc_deprecated(reason = "use slicing plus chars()", - since = "1.9.0")] - pub fn char_at(&self, i: usize) -> char { - core_str::StrExt::char_at(self, i) - } - - /// Given a byte position, returns the `char` at that position, counting - /// from the end. - /// - /// # Panics - /// - /// If `i` is greater than the length of the string. - /// If `i` is not an index following a valid UTF-8 sequence. - /// - /// # Examples - /// - /// ``` - /// #![feature(str_char)] - /// #![allow(deprecated)] - /// - /// let s = "abπc"; - /// assert_eq!(s.char_at_reverse(1), 'a'); - /// assert_eq!(s.char_at_reverse(2), 'b'); - /// assert_eq!(s.char_at_reverse(3), 'π'); - /// ``` - #[unstable(feature = "str_char", - reason = "see char_at for more details, but reverse semantics \ - are also somewhat unclear, especially with which \ - cases generate panics", - issue = "27754")] - #[inline] - #[rustc_deprecated(reason = "use slicing plus chars().rev()", - since = "1.9.0")] - #[allow(deprecated)] - pub fn char_at_reverse(&self, i: usize) -> char { - core_str::StrExt::char_at_reverse(self, i) - } - - /// Retrieves the first `char` from a `&str` and returns it. - /// - /// Note that a single Unicode character (grapheme cluster) - /// can be composed of multiple `char`s. - /// - /// This does not allocate a new string; instead, it returns a slice that - /// points one code point beyond the code point that was shifted. - /// - /// `None` is returned if the slice is empty. - /// - /// # Examples - /// - /// ``` - /// #![feature(str_char)] - /// #![allow(deprecated)] - /// - /// let s = "Łódź"; // \u{141}o\u{301}dz\u{301} - /// let (c, s1) = s.slice_shift_char().unwrap(); - /// - /// assert_eq!(c, 'Ł'); - /// assert_eq!(s1, "ódź"); - /// - /// let (c, s2) = s1.slice_shift_char().unwrap(); - /// - /// assert_eq!(c, 'o'); - /// assert_eq!(s2, "\u{301}dz\u{301}"); - /// ``` - #[unstable(feature = "str_char", - reason = "awaiting conventions about shifting and slices and \ - may not be warranted with the existence of the chars \ - and/or char_indices iterators", - issue = "27754")] - #[inline] - #[rustc_deprecated(reason = "use chars() plus Chars::as_str", - since = "1.9.0")] - #[allow(deprecated)] - pub fn slice_shift_char(&self) -> Option<(char, &str)> { - core_str::StrExt::slice_shift_char(self) - } - /// Divide one string slice into two at an index. /// /// The argument, `mid`, should be a byte offset from the start of the @@ -868,16 +639,6 @@ impl str { } /// Returns an iterator of `u16` over the string encoded as UTF-16. - #[unstable(feature = "str_utf16", - reason = "this functionality may only be provided by libunicode", - issue = "27714")] - #[rustc_deprecated(since = "1.8.0", reason = "renamed to encode_utf16")] - #[allow(deprecated)] - pub fn utf16_units(&self) -> Utf16Units { - Utf16Units { encoder: Utf16Encoder::new(self[..].chars()) } - } - - /// Returns an iterator of `u16` over the string encoded as UTF-16. #[stable(feature = "encode_utf16", since = "1.8.0")] pub fn encode_utf16(&self) -> EncodeUtf16 { EncodeUtf16 { encoder: Utf16Encoder::new(self[..].chars()) } @@ -1097,8 +858,34 @@ impl str { /// assert_eq!(d, &["", "", "", "", "a", "", "b", "c"]); /// ``` /// - /// This can lead to possibly surprising behavior when whitespace is used - /// as the separator. This code is correct: + /// Contiguous separators are separated by the empty string. + /// + /// ``` + /// let x = "(///)".to_string(); + /// let d: Vec<_> = x.split('/').collect();; + /// + /// assert_eq!(d, &["(", "", "", ")"]); + /// ``` + /// + /// Separators at the start or end of a string are neighbored + /// by empty strings. + /// + /// ``` + /// let d: Vec<_> = "010".split("0").collect(); + /// assert_eq!(d, &["", "1", ""]); + /// ``` + /// + /// When the empty string is used as a separator, it separates + /// every character in the string, along with the beginning + /// and end of the string. + /// + /// ``` + /// let f: Vec<_> = "rust".split("").collect(); + /// assert_eq!(f, &["", "r", "u", "s", "t", ""]); + /// ``` + /// + /// Contiguous separators can lead to possibly surprising behavior + /// when whitespace is used as the separator. This code is correct: /// /// ``` /// let x = " a b c".to_string(); diff --git a/libcollections/string.rs b/libcollections/string.rs index 306fad2..eedf4c2 100644 --- a/libcollections/string.rs +++ b/libcollections/string.rs @@ -184,7 +184,7 @@ use boxed::Box; /// let len = story.len(); /// let capacity = story.capacity(); /// -/// // story has thirteen bytes +/// // story has nineteen bytes /// assert_eq!(19, len); /// /// // Now that we have our parts, we throw the story away. diff --git a/libcollections/vec.rs b/libcollections/vec.rs index 58d4a4e..bd1bf6e 100644 --- a/libcollections/vec.rs +++ b/libcollections/vec.rs @@ -966,7 +966,7 @@ impl<T: Clone> Vec<T> { } } - /// Appends all elements in a slice to the `Vec`. + /// Clones and appends all elements in a slice to the `Vec`. /// /// Iterates over the slice `other`, clones each element, and then appends /// it to this `Vec`. The `other` vector is traversed in-order. |