Merge branch 'libcore_nofp'HEADmaster

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.