libcollections

5 files changed, 3878 insertions, 0 deletions

diff --git a/libcollections/btree/map.rs b/libcollections/btree/map.rs
new file mode 100644
index 0000000..de40568
--- /dev/null
+++ b/libcollections/btree/map.rs
@@ -0,0 +1,1721 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use core::cmp::Ordering;
+use core::fmt::Debug;
+use core::hash::{Hash, Hasher};
+use core::iter::FromIterator;
+use core::marker::PhantomData;
+use core::ops::Index;
+use core::{fmt, intrinsics, mem, ptr};
+
+use borrow::Borrow;
+use Bound::{self, Included, Excluded, Unbounded};
+
+use super::node::{self, NodeRef, Handle, marker};
+use super::search;
+
+use super::node::InsertResult::*;
+use super::node::ForceResult::*;
+use super::search::SearchResult::*;
+use self::UnderflowResult::*;
+use self::Entry::*;
+
+/// A map based on a B-Tree.
+///
+/// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
+/// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
+/// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
+/// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
+/// is done is *very* inefficient for modern computer architectures. In particular, every element
+/// is stored in its own individually heap-allocated node. This means that every single insertion
+/// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
+/// are both notably expensive things to do in practice, we are forced to at very least reconsider
+/// the BST strategy.
+///
+/// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
+/// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
+/// searches. However, this does mean that searches will have to do *more* comparisons on average.
+/// The precise number of comparisons depends on the node search strategy used. For optimal cache
+/// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
+/// the node using binary search. As a compromise, one could also perform a linear search
+/// that initially only checks every i<sup>th</sup> element for some choice of i.
+///
+/// Currently, our implementation simply performs naive linear search. This provides excellent
+/// performance on *small* nodes of elements which are cheap to compare. However in the future we
+/// would like to further explore choosing the optimal search strategy based on the choice of B,
+/// and possibly other factors. Using linear search, searching for a random element is expected
+/// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
+/// however, performance is excellent.
+///
+/// It is a logic error for a key to be modified in such a way that the key's ordering relative to
+/// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
+/// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::BTreeMap;
+///
+/// // type inference lets us omit an explicit type signature (which
+/// // would be `BTreeMap<&str, &str>` in this example).
+/// let mut movie_reviews = BTreeMap::new();
+///
+/// // review some books.
+/// movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
+/// movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
+/// movie_reviews.insert("The Godfather",      "Very enjoyable.");
+/// movie_reviews.insert("The Blues Brothers", "Eye lyked it alot.");
+///
+/// // check for a specific one.
+/// if !movie_reviews.contains_key("Les Misérables") {
+///     println!("We've got {} reviews, but Les Misérables ain't one.",
+///              movie_reviews.len());
+/// }
+///
+/// // oops, this review has a lot of spelling mistakes, let's delete it.
+/// movie_reviews.remove("The Blues Brothers");
+///
+/// // look up the values associated with some keys.
+/// let to_find = ["Up!", "Office Space"];
+/// for book in &to_find {
+///     match movie_reviews.get(book) {
+///        Some(review) => println!("{}: {}", book, review),
+///        None => println!("{} is unreviewed.", book)
+///     }
+/// }
+///
+/// // iterate over everything.
+/// for (movie, review) in &movie_reviews {
+///     println!("{}: \"{}\"", movie, review);
+/// }
+/// ```
+///
+/// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
+/// for more complex methods of getting, setting, updating and removing keys and
+/// their values:
+///
+/// ```
+/// use std::collections::BTreeMap;
+///
+/// // type inference lets us omit an explicit type signature (which
+/// // would be `BTreeMap<&str, u8>` in this example).
+/// let mut player_stats = BTreeMap::new();
+///
+/// fn random_stat_buff() -> u8 {
+///     // could actually return some random value here - let's just return
+///     // some fixed value for now
+///     42
+/// }
+///
+/// // insert a key only if it doesn't already exist
+/// player_stats.entry("health").or_insert(100);
+///
+/// // insert a key using a function that provides a new value only if it
+/// // doesn't already exist
+/// player_stats.entry("defence").or_insert_with(random_stat_buff);
+///
+/// // update a key, guarding against the key possibly not being set
+/// let stat = player_stats.entry("attack").or_insert(100);
+/// *stat += random_stat_buff();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct BTreeMap<K, V> {
+    root: node::Root<K, V>,
+    length: usize
+}
+
+impl<K, V> Drop for BTreeMap<K, V> {
+    #[unsafe_destructor_blind_to_params]
+    fn drop(&mut self) {
+        unsafe {
+            for _ in ptr::read(self).into_iter() { }
+        }
+    }
+}
+
+impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
+    fn clone(&self) -> BTreeMap<K, V> {
+        fn clone_subtree<K: Clone, V: Clone>(
+                node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
+                -> BTreeMap<K, V> {
+
+            match node.force() {
+                Leaf(leaf) => {
+                    let mut out_tree = BTreeMap {
+                        root: node::Root::new_leaf(),
+                        length: 0
+                    };
+
+                    {
+                        let mut out_node = match out_tree.root.as_mut().force() {
+                            Leaf(leaf) => leaf,
+                            Internal(_) => unreachable!()
+                        };
+
+                        let mut in_edge = leaf.first_edge();
+                        while let Ok(kv) = in_edge.right_kv() {
+                            let (k, v) = kv.into_kv();
+                            in_edge = kv.right_edge();
+
+                            out_node.push(k.clone(), v.clone());
+                            out_tree.length += 1;
+                        }
+                    }
+
+                    out_tree
+                },
+                Internal(internal) => {
+                    let mut out_tree = clone_subtree(internal.first_edge().descend());
+
+                    {
+                        let mut out_node = out_tree.root.push_level();
+                        let mut in_edge = internal.first_edge();
+                        while let Ok(kv) = in_edge.right_kv() {
+                            let (k, v) = kv.into_kv();
+                            in_edge = kv.right_edge();
+
+                            let k = (*k).clone();
+                            let v = (*v).clone();
+                            let subtree = clone_subtree(in_edge.descend());
+
+                            // We can't destructure subtree directly
+                            // because BTreeMap implements Drop
+                            let (subroot, sublength) = unsafe {
+                                let root = ptr::read(&subtree.root);
+                                let length = subtree.length;
+                                mem::forget(subtree);
+                                (root, length)
+                            };
+
+                            out_node.push(k, v, subroot);
+                            out_tree.length += 1 + sublength;
+                        }
+                    }
+
+                    out_tree
+                }
+            }
+        }
+
+        clone_subtree(self.root.as_ref())
+    }
+}
+
+impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
+    where K: Borrow<Q> + Ord,
+          Q: Ord
+{
+    type Key = K;
+
+    fn get(&self, key: &Q) -> Option<&K> {
+        match search::search_tree(self.root.as_ref(), key) {
+            Found(handle) => Some(handle.into_kv().0),
+            GoDown(_) => None
+        }
+    }
+
+    fn take(&mut self, key: &Q) -> Option<K> {
+        match search::search_tree(self.root.as_mut(), key) {
+            Found(handle) => {
+                Some(OccupiedEntry {
+                    handle: handle,
+                    length: &mut self.length,
+                    _marker: PhantomData,
+                }.remove_kv().0)
+            },
+            GoDown(_) => None
+        }
+    }
+
+    fn replace(&mut self, key: K) -> Option<K> {
+        match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
+            Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
+            GoDown(handle) => {
+                VacantEntry {
+                    key: key,
+                    handle: handle,
+                    length: &mut self.length,
+                    _marker: PhantomData,
+                }.insert(());
+                None
+            }
+        }
+    }
+}
+
+/// An iterator over a BTreeMap's entries.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Iter<'a, K: 'a, V: 'a> {
+    range: Range<'a, K, V>,
+    length: usize
+}
+
+/// A mutable iterator over a BTreeMap's entries.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct IterMut<'a, K: 'a, V: 'a> {
+    range: RangeMut<'a, K, V>,
+    length: usize
+}
+
+/// An owning iterator over a BTreeMap's entries.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct IntoIter<K, V> {
+    front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
+    back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
+    length: usize
+}
+
+/// An iterator over a BTreeMap's keys.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Keys<'a, K: 'a, V: 'a> {
+    inner: Iter<'a, K, V>,
+}
+
+/// An iterator over a BTreeMap's values.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Values<'a, K: 'a, V: 'a> {
+    inner: Iter<'a, K, V>,
+}
+
+/// A mutable iterator over a BTreeMap's values.
+#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+pub struct ValuesMut<'a, K: 'a, V: 'a> {
+    inner: IterMut<'a, K, V>,
+}
+
+/// An iterator over a sub-range of BTreeMap's entries.
+pub struct Range<'a, K: 'a, V: 'a> {
+    front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
+}
+
+/// A mutable iterator over a sub-range of BTreeMap's entries.
+pub struct RangeMut<'a, K: 'a, V: 'a> {
+    front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+
+    // Be invariant in `K` and `V`
+    _marker: PhantomData<&'a mut (K, V)>,
+}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub enum Entry<'a, K: 'a, V: 'a> {
+    /// A vacant Entry
+    #[stable(feature = "rust1", since = "1.0.0")]
+    Vacant(
+        #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
+    ),
+
+    /// An occupied Entry
+    #[stable(feature = "rust1", since = "1.0.0")]
+    Occupied(
+        #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
+    ),
+}
+
+/// A vacant Entry.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct VacantEntry<'a, K: 'a, V: 'a> {
+    key: K,
+    handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    length: &'a mut usize,
+
+    // Be invariant in `K` and `V`
+    _marker: PhantomData<&'a mut (K, V)>,
+}
+
+/// An occupied Entry.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
+    handle: Handle<NodeRef<
+        marker::Mut<'a>,
+        K, V,
+        marker::LeafOrInternal
+    >, marker::KV>,
+
+    length: &'a mut usize,
+
+    // Be invariant in `K` and `V`
+    _marker: PhantomData<&'a mut (K, V)>,
+}
+
+impl<K: Ord, V> BTreeMap<K, V> {
+    /// Makes a new empty BTreeMap with a reasonable choice for B.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    ///
+    /// // entries can now be inserted into the empty map
+    /// map.insert(1, "a");
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn new() -> BTreeMap<K, V> {
+        BTreeMap {
+            root: node::Root::new_leaf(),
+            length: 0
+        }
+    }
+
+    /// Clears the map, removing all values.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// a.insert(1, "a");
+    /// a.clear();
+    /// assert!(a.is_empty());
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn clear(&mut self) {
+        // FIXME(gereeter) .clear() allocates
+        *self = BTreeMap::new();
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
+        match search::search_tree(self.root.as_ref(), key) {
+            Found(handle) => Some(handle.into_kv().1),
+            GoDown(_) => None
+        }
+    }
+
+    /// Returns true if the map contains a value for the specified key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.contains_key(&1), true);
+    /// assert_eq!(map.contains_key(&2), false);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
+        self.get(key).is_some()
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(1, "a");
+    /// if let Some(x) = map.get_mut(&1) {
+    ///     *x = "b";
+    /// }
+    /// assert_eq!(map[&1], "b");
+    /// ```
+    // See `get` for implementation notes, this is basically a copy-paste with mut's added
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
+        match search::search_tree(self.root.as_mut(), key) {
+            Found(handle) => Some(handle.into_kv_mut().1),
+            GoDown(_) => None
+        }
+    }
+
+    /// Inserts a key-value pair into the map.
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical. See the [module-level
+    /// documentation] for more.
+    ///
+    /// [module-level documentation]: index.html#insert-and-complex-keys
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// assert_eq!(map.insert(37, "a"), None);
+    /// assert_eq!(map.is_empty(), false);
+    ///
+    /// map.insert(37, "b");
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
+    /// assert_eq!(map[&37], "c");
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
+        match self.entry(key) {
+            Occupied(mut entry) => Some(entry.insert(value)),
+            Vacant(entry) => {
+                entry.insert(value);
+                None
+            }
+        }
+    }
+
+    /// Removes a key from the map, returning the value at the key if the key
+    /// was previously in the map.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
+        match search::search_tree(self.root.as_mut(), key) {
+            Found(handle) => {
+                Some(OccupiedEntry {
+                    handle: handle,
+                    length: &mut self.length,
+                    _marker: PhantomData,
+                }.remove())
+            },
+            GoDown(_) => None
+        }
+    }
+
+    /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
+    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
+    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
+    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(btree_range, collections_bound)]
+    ///
+    /// use std::collections::BTreeMap;
+    /// use std::collections::Bound::{Included, Unbounded};
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(3, "a");
+    /// map.insert(5, "b");
+    /// map.insert(8, "c");
+    /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
+    ///     println!("{}: {}", key, value);
+    /// }
+    /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
+    /// ```
+    #[unstable(feature = "btree_range",
+               reason = "matches collection reform specification, waiting for dust to settle",
+               issue = "27787")]
+    pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
+                                                       min: Bound<&Min>,
+                                                       max: Bound<&Max>)
+                                                       -> Range<K, V>
+        where K: Borrow<Min> + Borrow<Max>,
+    {
+        let front = match min {
+            Included(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => first_leaf_edge(self.root.as_ref())
+        };
+
+        let back = match max {
+            Included(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => last_leaf_edge(self.root.as_ref())
+        };
+
+        Range {
+            front: front,
+            back: back
+        }
+    }
+
+    /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
+    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
+    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
+    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(btree_range, collections_bound)]
+    ///
+    /// use std::collections::BTreeMap;
+    /// use std::collections::Bound::{Included, Excluded};
+    ///
+    /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
+    ///                                                                       .map(|&s| (s, 0))
+    ///                                                                       .collect();
+    /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
+    ///     *balance += 100;
+    /// }
+    /// for (name, balance) in &map {
+    ///     println!("{} => {}", name, balance);
+    /// }
+    /// ```
+    #[unstable(feature = "btree_range",
+               reason = "matches collection reform specification, waiting for dust to settle",
+               issue = "27787")]
+    pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
+                                                           min: Bound<&Min>,
+                                                           max: Bound<&Max>)
+                                                           -> RangeMut<K, V>
+        where K: Borrow<Min> + Borrow<Max>,
+    {
+        let root1 = self.root.as_mut();
+        let root2 = unsafe { ptr::read(&root1) };
+
+        let front = match min {
+            Included(key) => match search::search_tree(root1, key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(root1, key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => first_leaf_edge(root1)
+        };
+
+        let back = match max {
+            Included(key) => match search::search_tree(root2, key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(root2, key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => last_leaf_edge(root2)
+        };
+
+        RangeMut {
+            front: front,
+            back: back,
+            _marker: PhantomData
+        }
+    }
+
+    /// Gets the given key's corresponding entry in the map for in-place manipulation.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
+    ///
+    /// // count the number of occurrences of letters in the vec
+    /// for x in vec!["a","b","a","c","a","b"] {
+    ///     *count.entry(x).or_insert(0) += 1;
+    /// }
+    ///
+    /// assert_eq!(count["a"], 3);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn entry(&mut self, key: K) -> Entry<K, V> {
+        match search::search_tree(self.root.as_mut(), &key) {
+            Found(handle) => Occupied(OccupiedEntry {
+                handle: handle,
+                length: &mut self.length,
+                _marker: PhantomData,
+            }),
+            GoDown(handle) => Vacant(VacantEntry {
+                key: key,
+                handle: handle,
+                length: &mut self.length,
+                _marker: PhantomData,
+            })
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
+    type Item = (&'a K, &'a V);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Iter<'a, K, V> {
+        self.iter()
+    }
+}
+
+impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn next(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_unchecked()) }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.length, Some(self.length))
+    }
+}
+
+impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_back_unchecked()) }
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
+    fn len(&self) -> usize { self.length }
+}
+
+impl<'a, K, V> Clone for Iter<'a, K, V> {
+    fn clone(&self) -> Iter<'a, K, V> {
+        Iter {
+            range: self.range.clone(),
+            length: self.length
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
+    type Item = (&'a K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> IterMut<'a, K, V> {
+        self.iter_mut()
+    }
+}
+
+impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
+
+    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_unchecked()) }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.length, Some(self.length))
+    }
+}
+
+impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_back_unchecked()) }
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
+    fn len(&self) -> usize { self.length }
+}
+
+impl<K, V> IntoIterator for BTreeMap<K, V> {
+    type Item = (K, V);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> IntoIter<K, V> {
+        let root1 = unsafe { ptr::read(&self.root).into_ref() };
+        let root2 = unsafe { ptr::read(&self.root).into_ref() };
+        let len = self.length;
+        mem::forget(self);
+
+        IntoIter {
+            front: first_leaf_edge(root1),
+            back: last_leaf_edge(root2),
+            length: len
+        }
+    }
+}
+
+impl<K, V> Drop for IntoIter<K, V> {
+    fn drop(&mut self) {
+        for _ in &mut *self { }
+        unsafe {
+            let leaf_node = ptr::read(&self.front).into_node();
+            if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
+                let mut cur_node = first_parent.into_node();
+                while let Some(parent) = cur_node.deallocate_and_ascend() {
+                    cur_node = parent.into_node()
+                }
+            }
+        }
+    }
+}
+
+impl<K, V> Iterator for IntoIter<K, V> {
+    type Item = (K, V);
+
+    fn next(&mut self) -> Option<(K, V)> {
+        if self.length == 0 {
+            return None;
+        } else {
+            self.length -= 1;
+        }
+
+        let handle = unsafe { ptr::read(&self.front) };
+
+        let mut cur_handle = match handle.right_kv() {
+            Ok(kv) => {
+                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                self.front = kv.right_edge();
+                return Some((k, v));
+            },
+            Err(last_edge) => unsafe {
+                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+            }
+        };
+
+        loop {
+            match cur_handle.right_kv() {
+                Ok(kv) => {
+                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                    self.front = first_leaf_edge(kv.right_edge().descend());
+                    return Some((k, v));
+                },
+                Err(last_edge) => unsafe {
+                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
+                }
+            }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.length, Some(self.length))
+    }
+}
+
+impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
+    fn next_back(&mut self) -> Option<(K, V)> {
+        if self.length == 0 {
+            return None;
+        } else {
+            self.length -= 1;
+        }
+
+        let handle = unsafe { ptr::read(&self.back) };
+
+        let mut cur_handle = match handle.left_kv() {
+            Ok(kv) => {
+                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                self.back = kv.left_edge();
+                return Some((k, v));
+            },
+            Err(last_edge) => unsafe {
+                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+            }
+        };
+
+        loop {
+            match cur_handle.left_kv() {
+                Ok(kv) => {
+                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                    self.back = last_leaf_edge(kv.left_edge().descend());
+                    return Some((k, v));
+                },
+                Err(last_edge) => unsafe {
+                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
+                }
+            }
+        }
+    }
+}
+
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+    fn len(&self) -> usize { self.length }
+}
+
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+    type Item = &'a K;
+
+    fn next(&mut self) -> Option<&'a K> {
+        self.inner.next().map(|(k, _)| k)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
+    fn next_back(&mut self) -> Option<&'a K> {
+        self.inner.next_back().map(|(k, _)| k)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> Clone for Keys<'a, K, V> {
+    fn clone(&self) -> Keys<'a, K, V> {
+        Keys {
+            inner: self.inner.clone()
+        }
+    }
+}
+
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+    type Item = &'a V;
+
+    fn next(&mut self) -> Option<&'a V> {
+        self.inner.next().map(|(_, v)| v)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
+    fn next_back(&mut self) -> Option<&'a V> {
+        self.inner.next_back().map(|(_, v)| v)
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> Clone for Values<'a, K, V> {
+    fn clone(&self) -> Values<'a, K, V> {
+        Values {
+            inner: self.inner.clone()
+        }
+    }
+}
+
+impl<'a, K, V> Iterator for Range<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn next(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some(self.next_unchecked()) }
+        }
+    }
+}
+
+#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
+    type Item = &'a mut V;
+
+    fn next(&mut self) -> Option<&'a mut V> {
+        self.inner.next().map(|(_, v)| v)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+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")]
+impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
+}
+
+impl<'a, K, V> Range<'a, K, V> {
+    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+        let handle = self.front;
+
+        let mut cur_handle = match handle.right_kv() {
+            Ok(kv) => {
+                let ret = kv.into_kv();
+                self.front = kv.right_edge();
+                return ret;
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
+
+        loop {
+            match cur_handle.right_kv() {
+                Ok(kv) => {
+                    let ret = kv.into_kv();
+                    self.front = first_leaf_edge(kv.right_edge().descend());
+                    return ret;
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
+                }
+            }
+        }
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some(self.next_back_unchecked()) }
+        }
+    }
+}
+
+impl<'a, K, V> Range<'a, K, V> {
+    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
+        let handle = self.back;
+
+        let mut cur_handle = match handle.left_kv() {
+            Ok(kv) => {
+                let ret = kv.into_kv();
+                self.back = kv.left_edge();
+                return ret;
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
+
+        loop {
+            match cur_handle.left_kv() {
+                Ok(kv) => {
+                    let ret = kv.into_kv();
+                    self.back = last_leaf_edge(kv.left_edge().descend());
+                    return ret;
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
+                }
+            }
+        }
+    }
+}
+
+impl<'a, K, V> Clone for Range<'a, K, V> {
+    fn clone(&self) -> Range<'a, K, V> {
+        Range {
+            front: self.front,
+            back: self.back
+        }
+    }
+}
+
+impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
+
+    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some (self.next_unchecked()) }
+        }
+    }
+}
+
+impl<'a, K, V> RangeMut<'a, K, V> {
+    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
+        let handle = ptr::read(&self.front);
+
+        let mut cur_handle = match handle.right_kv() {
+            Ok(kv) => {
+                let (k, v) = ptr::read(&kv).into_kv_mut();
+                self.front = kv.right_edge();
+                return (k, v);
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
+
+        loop {
+            match cur_handle.right_kv() {
+                Ok(kv) => {
+                    let (k, v) = ptr::read(&kv).into_kv_mut();
+                    self.front = first_leaf_edge(kv.right_edge().descend());
+                    return (k, v);
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
+                }
+            }
+        }
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some(self.next_back_unchecked()) }
+        }
+    }
+}
+
+impl<'a, K, V> RangeMut<'a, K, V> {
+    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
+        let handle = ptr::read(&self.back);
+
+        let mut cur_handle = match handle.left_kv() {
+            Ok(kv) => {
+                let (k, v) = ptr::read(&kv).into_kv_mut();
+                self.back = kv.left_edge();
+                return (k, v);
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
+
+        loop {
+            match cur_handle.left_kv() {
+                Ok(kv) => {
+                    let (k, v) = ptr::read(&kv).into_kv_mut();
+                    self.back = last_leaf_edge(kv.left_edge().descend());
+                    return (k, v);
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
+                }
+            }
+        }
+    }
+}
+
+impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
+    fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
+        let mut map = BTreeMap::new();
+        map.extend(iter);
+        map
+    }
+}
+
+impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
+    #[inline]
+    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
+        for (k, v) in iter {
+            self.insert(k, v);
+        }
+    }
+}
+
+impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
+    fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
+        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
+    }
+}
+
+impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        for elt in self {
+            elt.hash(state);
+        }
+    }
+}
+
+impl<K: Ord, V> Default for BTreeMap<K, V> {
+    fn default() -> BTreeMap<K, V> {
+        BTreeMap::new()
+    }
+}
+
+impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
+    fn eq(&self, other: &BTreeMap<K, V>) -> bool {
+        self.len() == other.len() &&
+            self.iter().zip(other).all(|(a, b)| a == b)
+    }
+}
+
+impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
+
+impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
+    #[inline]
+    fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
+        self.iter().partial_cmp(other.iter())
+    }
+}
+
+impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
+    #[inline]
+    fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
+        self.iter().cmp(other.iter())
+    }
+}
+
+impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_map().entries(self.iter()).finish()
+    }
+}
+
+impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
+    where K: Borrow<Q>, Q: Ord
+{
+    type Output = V;
+
+    #[inline]
+    fn index(&self, key: &Q) -> &V {
+        self.get(key).expect("no entry found for key")
+    }
+}
+
+fn first_leaf_edge<BorrowType, K, V>(
+        mut node: NodeRef<BorrowType,
+                          K, V,
+                          marker::LeafOrInternal>
+        ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+    loop {
+        match node.force() {
+            Leaf(leaf) => return leaf.first_edge(),
+            Internal(internal) => {
+                node = internal.first_edge().descend();
+            }
+        }
+    }
+}
+
+fn last_leaf_edge<BorrowType, K, V>(
+        mut node: NodeRef<BorrowType,
+                          K, V,
+                          marker::LeafOrInternal>
+        ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+    loop {
+        match node.force() {
+            Leaf(leaf) => return leaf.last_edge(),
+            Internal(internal) => {
+                node = internal.last_edge().descend();
+            }
+        }
+    }
+}
+
+#[inline(always)]
+unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
+    val.unwrap_or_else(|| {
+        if cfg!(debug_assertions) {
+            panic!("'unchecked' unwrap on None in BTreeMap");
+        } else {
+            intrinsics::unreachable();
+        }
+    })
+}
+
+impl<K, V> BTreeMap<K, V> {
+    /// Gets an iterator over the entries of the map, sorted by key.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert(3, "c");
+    /// map.insert(2, "b");
+    /// map.insert(1, "a");
+    ///
+    /// for (key, value) in map.iter() {
+    ///     println!("{}: {}", key, value);
+    /// }
+    ///
+    /// let (first_key, first_value) = map.iter().next().unwrap();
+    /// assert_eq!((*first_key, *first_value), (1, "a"));
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn iter(&self) -> Iter<K, V> {
+        Iter {
+            range: Range {
+                front: first_leaf_edge(self.root.as_ref()),
+                back: last_leaf_edge(self.root.as_ref())
+            },
+            length: self.length
+        }
+    }
+
+    /// Gets a mutable iterator over the entries of the map, sorted by key.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut map = BTreeMap::new();
+    /// map.insert("a", 1);
+    /// map.insert("b", 2);
+    /// map.insert("c", 3);
+    ///
+    /// // add 10 to the value if the key isn't "a"
+    /// for (key, value) in map.iter_mut() {
+    ///     if key != &"a" {
+    ///         *value += 10;
+    ///     }
+    /// }
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        let root1 = self.root.as_mut();
+        let root2 = unsafe { ptr::read(&root1) };
+        IterMut {
+            range: RangeMut {
+                front: first_leaf_edge(root1),
+                back: last_leaf_edge(root2),
+                _marker: PhantomData,
+            },
+            length: self.length
+        }
+    }
+
+    /// Gets an iterator over the keys of the map, in sorted order.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// a.insert(2, "b");
+    /// a.insert(1, "a");
+    ///
+    /// let keys: Vec<_> = a.keys().cloned().collect();
+    /// assert_eq!(keys, [1, 2]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
+        Keys { inner: self.iter() }
+    }
+
+    /// Gets an iterator over the values of the map, in order by key.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// a.insert(1, "hello");
+    /// a.insert(2, "goodbye");
+    ///
+    /// let values: Vec<&str> = a.values().cloned().collect();
+    /// assert_eq!(values, ["hello", "goodbye"]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn values<'a>(&'a self) -> Values<'a, K, V> {
+        Values { inner: self.iter() }
+    }
+
+    /// Gets a mutable iterator over the values of the map, in order by key.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// # #![feature(map_values_mut)]
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// a.insert(1, String::from("hello"));
+    /// a.insert(2, String::from("goodbye"));
+    ///
+    /// for value in a.values_mut() {
+    ///     value.push_str("!");
+    /// }
+    ///
+    /// let values: Vec<String> = a.values().cloned().collect();
+    /// 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> {
+        ValuesMut { inner: self.iter_mut() }
+    }
+
+    /// Returns the number of elements in the map.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// assert_eq!(a.len(), 0);
+    /// a.insert(1, "a");
+    /// assert_eq!(a.len(), 1);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn len(&self) -> usize {
+        self.length
+    }
+
+    /// Returns true if the map contains no elements.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut a = BTreeMap::new();
+    /// assert!(a.is_empty());
+    /// a.insert(1, "a");
+    /// assert!(!a.is_empty());
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+}
+
+impl<'a, K: Ord, V> Entry<'a, K, V> {
+    /// Ensures a value is in the entry by inserting the default if empty, and returns
+    /// a mutable reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn or_insert(self, default: V) -> &'a mut V {
+        match self {
+            Occupied(entry) => entry.into_mut(),
+            Vacant(entry) => entry.insert(default),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting the result of the default function if empty,
+    /// and returns a mutable reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+        match self {
+            Occupied(entry) => entry.into_mut(),
+            Vacant(entry) => entry.insert(default()),
+        }
+    }
+}
+
+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")]
+    pub fn key(&self) -> &K {
+        &self.key
+    }
+
+    /// Sets the value of the entry with the VacantEntry's key,
+    /// and returns a mutable reference to it.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn insert(self, value: V) -> &'a mut V {
+        *self.length += 1;
+
+        let out_ptr;
+
+        let mut ins_k;
+        let mut ins_v;
+        let mut ins_edge;
+
+        let mut cur_parent = match self.handle.insert(self.key, value) {
+            (Fit(handle), _) => return handle.into_kv_mut().1,
+            (Split(left, k, v, right), ptr) => {
+                ins_k = k;
+                ins_v = v;
+                ins_edge = right;
+                out_ptr = ptr;
+                left.ascend().map_err(|n| n.into_root_mut())
+            }
+        };
+
+        loop {
+            match cur_parent {
+                Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
+                    Fit(_) => return unsafe { &mut *out_ptr },
+                    Split(left, k, v, right) => {
+                        ins_k = k;
+                        ins_v = v;
+                        ins_edge = right;
+                        cur_parent = left.ascend().map_err(|n| n.into_root_mut());
+                    }
+                },
+                Err(root) => {
+                    root.push_level().push(ins_k, ins_v, ins_edge);
+                    return unsafe { &mut *out_ptr };
+                }
+            }
+        }
+    }
+}
+
+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")]
+    pub fn key(&self) -> &K {
+        self.handle.reborrow().into_kv().0
+    }
+
+    /// Gets a reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn get(&self) -> &V {
+        self.handle.reborrow().into_kv().1
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn get_mut(&mut self) -> &mut V {
+        self.handle.kv_mut().1
+    }
+
+    /// Converts the entry into a mutable reference to its value.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn into_mut(self) -> &'a mut V {
+        self.handle.into_kv_mut().1
+    }
+
+    /// Sets the value of the entry with the OccupiedEntry's key,
+    /// and returns the entry's old value.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn insert(&mut self, value: V) -> V {
+        mem::replace(self.get_mut(), value)
+    }
+
+    /// Takes the value of the entry out of the map, and returns it.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn remove(self) -> V {
+        self.remove_kv().1
+    }
+
+    fn remove_kv(self) -> (K, V) {
+        *self.length -= 1;
+
+        let (small_leaf, old_key, old_val) = match self.handle.force() {
+            Leaf(leaf) => {
+                let (hole, old_key, old_val) = leaf.remove();
+                (hole.into_node(), old_key, old_val)
+            },
+            Internal(mut internal) => {
+                let key_loc = internal.kv_mut().0 as *mut K;
+                let val_loc = internal.kv_mut().1 as *mut V;
+
+                let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
+                let to_remove = unsafe { unwrap_unchecked(to_remove) };
+
+                let (hole, key, val) = to_remove.remove();
+
+                let old_key = unsafe {
+                    mem::replace(&mut *key_loc, key)
+                };
+                let old_val = unsafe {
+                    mem::replace(&mut *val_loc, val)
+                };
+
+                (hole.into_node(), old_key, old_val)
+            }
+        };
+
+        // Handle underflow
+        let mut cur_node = small_leaf.forget_type();
+        while cur_node.len() < node::CAPACITY / 2 {
+            match handle_underfull_node(cur_node) {
+                AtRoot => break,
+                EmptyParent(_) => unreachable!(),
+                Merged(parent) => if parent.len() == 0 {
+                    // We must be at the root
+                    parent.into_root_mut().pop_level();
+                    break;
+                } else {
+                    cur_node = parent.forget_type();
+                },
+                Stole(_) => break
+            }
+        }
+
+        (old_key, old_val)
+    }
+}
+
+enum UnderflowResult<'a, K, V> {
+    AtRoot,
+    EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
+    Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
+    Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
+}
+
+fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
+                                                 K, V,
+                                                 marker::LeafOrInternal>)
+                                                 -> UnderflowResult<'a, K, V> {
+    let parent = if let Ok(parent) = node.ascend() {
+        parent
+    } else {
+        return AtRoot;
+    };
+
+    let (is_left, mut handle) = match parent.left_kv() {
+        Ok(left) => (true, left),
+        Err(parent) => match parent.right_kv() {
+            Ok(right) => (false, right),
+            Err(parent) => {
+                return EmptyParent(parent.into_node());
+            }
+        }
+    };
+
+    if handle.can_merge() {
+        return Merged(handle.merge().into_node());
+    } else {
+        unsafe {
+            let (k, v, edge) = if is_left {
+                handle.reborrow_mut().left_edge().descend().pop()
+            } else {
+                handle.reborrow_mut().right_edge().descend().pop_front()
+            };
+
+            let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
+            let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
+
+            // FIXME: reuse cur_node?
+            if is_left {
+                match handle.reborrow_mut().right_edge().descend().force() {
+                    Leaf(mut leaf) => leaf.push_front(k, v),
+                    Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
+                }
+            } else {
+                match handle.reborrow_mut().left_edge().descend().force() {
+                    Leaf(mut leaf) => leaf.push(k, v),
+                    Internal(mut internal) => internal.push(k, v, edge.unwrap())
+                }
+            }
+        }
+
+        return Stole(handle.into_node());
+    }
+}
diff --git a/libcollections/btree/mod.rs b/libcollections/btree/mod.rs
new file mode 100644
index 0000000..087c9f2
--- /dev/null
+++ b/libcollections/btree/mod.rs
@@ -0,0 +1,23 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+mod node;
+mod search;
+pub mod map;
+pub mod set;
+
+#[doc(hidden)]
+trait Recover<Q: ?Sized> {
+    type Key;
+
+    fn get(&self, key: &Q) -> Option<&Self::Key>;
+    fn take(&mut self, key: &Q) -> Option<Self::Key>;
+    fn replace(&mut self, key: Self::Key) -> Option<Self::Key>;
+}
diff --git a/libcollections/btree/node.rs b/libcollections/btree/node.rs
new file mode 100644
index 0000000..8ae23a6
--- /dev/null
+++ b/libcollections/btree/node.rs
@@ -0,0 +1,1132 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// This is an attempt at an implementation following the ideal
+//
+// ```
+// struct BTreeMap<K, V> {
+//     height: usize,
+//     root: Option<Box<Node<K, V, height>>>
+// }
+//
+// struct Node<K, V, height: usize> {
+//     keys: [K; 2 * B - 1],
+//     vals: [V; 2 * B - 1],
+//     edges: if height > 0 {
+//         [Box<Node<K, V, height - 1>>; 2 * B]
+//     } else { () },
+//     parent: *const Node<K, V, height + 1>,
+//     parent_idx: u16,
+//     len: u16,
+// }
+// ```
+//
+// Since Rust doesn't actually have dependent types and polymorphic recursion,
+// we make do with lots of unsafety.
+
+use alloc::heap;
+use core::marker::PhantomData;
+use core::mem;
+use core::nonzero::NonZero;
+use core::ptr::{self, Unique};
+use core::slice;
+
+use boxed::Box;
+
+const B: usize = 6;
+pub const CAPACITY: usize = 2 * B - 1;
+
+struct LeafNode<K, V> {
+    keys: [K; CAPACITY],
+    vals: [V; CAPACITY],
+    parent: *const InternalNode<K, V>,
+    parent_idx: u16,
+    len: u16,
+}
+
+impl<K, V> LeafNode<K, V> {
+    unsafe fn new() -> Self {
+        LeafNode {
+            keys: mem::uninitialized(),
+            vals: mem::uninitialized(),
+            parent: ptr::null(),
+            parent_idx: mem::uninitialized(),
+            len: 0
+        }
+    }
+}
+
+// We use repr(C) so that a pointer to an internal node can be
+// directly used as a pointer to a leaf node
+#[repr(C)]
+struct InternalNode<K, V> {
+    data: LeafNode<K, V>,
+    edges: [BoxedNode<K, V>; 2 * B],
+}
+
+impl<K, V> InternalNode<K, V> {
+    unsafe fn new() -> Self {
+        InternalNode {
+            data: LeafNode::new(),
+            edges: mem::uninitialized()
+        }
+    }
+}
+
+struct BoxedNode<K, V> {
+    ptr: Unique<LeafNode<K, V>> // we don't know if this points to a leaf node or an internal node
+}
+
+impl<K, V> BoxedNode<K, V> {
+    fn from_leaf(node: Box<LeafNode<K, V>>) -> Self {
+        unsafe {
+            BoxedNode { ptr: Unique::new(Box::into_raw(node)) }
+        }
+    }
+
+    fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
+        unsafe {
+            BoxedNode { ptr: Unique::new(Box::into_raw(node) as *mut LeafNode<K, V>) }
+        }
+    }
+
+    unsafe fn from_ptr(ptr: NonZero<*const LeafNode<K, V>>) -> Self {
+        BoxedNode { ptr: Unique::new(*ptr as *mut LeafNode<K, V>) }
+    }
+
+    fn as_ptr(&self) -> NonZero<*const LeafNode<K, V>> {
+        unsafe {
+            NonZero::new(*self.ptr as *const LeafNode<K, V>)
+        }
+    }
+}
+
+/// An owned tree. Note that despite being owned, this does not have a destructor,
+/// and must be cleaned up manually.
+pub struct Root<K, V> {
+    node: BoxedNode<K, V>,
+    height: usize
+}
+
+unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> { }
+unsafe impl<K: Send, V: Send> Send for Root<K, V> { }
+
+impl<K, V> Root<K, V> {
+    pub fn new_leaf() -> Self {
+        Root {
+            node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })),
+            height: 0
+        }
+    }
+
+    pub fn as_ref(&self)
+            -> NodeRef<marker::Immut, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: self as *const _ as *mut _,
+            _marker: PhantomData,
+        }
+    }
+
+    pub fn as_mut(&mut self)
+            -> NodeRef<marker::Mut, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: self as *mut _,
+            _marker: PhantomData,
+        }
+    }
+
+    pub fn into_ref(self)
+            -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: ptr::null_mut(), // FIXME: Is there anything better to do here?
+            _marker: PhantomData,
+        }
+    }
+
+    /// Add a new internal node with a single edge, pointing to the previous root, and make that
+    /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
+    pub fn push_level(&mut self)
+            -> NodeRef<marker::Mut, K, V, marker::Internal> {
+        let mut new_node = Box::new(unsafe { InternalNode::new() });
+        new_node.edges[0] = unsafe { BoxedNode::from_ptr(self.node.as_ptr()) };
+
+        self.node = BoxedNode::from_internal(new_node);
+        self.height += 1;
+
+        let mut ret = NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: self as *mut _,
+            _marker: PhantomData
+        };
+
+        unsafe {
+            ret.reborrow_mut().first_edge().correct_parent_link();
+        }
+
+        ret
+    }
+
+    /// Remove the root node, using its first child as the new root. This cannot be called when
+    /// the tree consists only of a leaf node. As it is intended only to be called when the root
+    /// has only one edge, no cleanup is done on any of the other children are elements of the root.
+    /// This decreases the height by 1 and is the opposite of `push_level`.
+    pub fn pop_level(&mut self) {
+        debug_assert!(self.height > 0);
+
+        let top = *self.node.ptr as *mut u8;
+
+        self.node = unsafe {
+            BoxedNode::from_ptr(self.as_mut()
+                                    .cast_unchecked::<marker::Internal>()
+                                    .first_edge()
+                                    .descend()
+                                    .node)
+        };
+        self.height -= 1;
+        self.as_mut().as_leaf_mut().parent = ptr::null();
+
+        unsafe {
+            heap::deallocate(
+                top,
+                mem::size_of::<InternalNode<K, V>>(),
+                mem::align_of::<InternalNode<K, V>>()
+            );
+        }
+    }
+}
+
+// N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType`
+// is `Mut`. This is technically wrong, but cannot result in any unsafety due to
+// internal use of `NodeRef` because we stay completely generic over `K` and `V`.
+// However, whenever a public type wraps `NodeRef`, make sure that it has the
+// correct variance.
+/// A reference to a node.
+///
+/// This type has a number of paramaters that controls how it acts:
+/// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`.
+///    When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`,
+///    when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
+///    and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`.
+/// - `K` and `V`: These control what types of things are stored in the nodes.
+/// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
+///   `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
+///   `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
+///   `NodeRef` could be pointing to either type of node.
+pub struct NodeRef<BorrowType, K, V, Type> {
+    height: usize,
+    node: NonZero<*const LeafNode<K, V>>,
+    root: *const Root<K, V>,
+    _marker: PhantomData<(BorrowType, Type)>
+}
+
+impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> { }
+impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync
+    for NodeRef<BorrowType, K, V, Type> { }
+
+unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send
+   for NodeRef<marker::Immut<'a>, K, V, Type> { }
+unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send
+   for NodeRef<marker::Mut<'a>, K, V, Type> { }
+unsafe impl<K: Send, V: Send, Type> Send
+   for NodeRef<marker::Owned, K, V, Type> { }
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
+    fn as_internal(&self) -> &InternalNode<K, V> {
+        unsafe {
+            &*(*self.node as *const InternalNode<K, V>)
+        }
+    }
+}
+
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
+    fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
+        unsafe {
+            &mut *(*self.node as *mut InternalNode<K, V>)
+        }
+    }
+}
+
+
+impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
+    pub fn len(&self) -> usize {
+        self.as_leaf().len as usize
+    }
+
+    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
+        }
+    }
+
+    fn reborrow<'a>(&'a self) -> NodeRef<marker::Immut<'a>, K, V, Type> {
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
+        }
+    }
+
+    fn as_leaf(&self) -> &LeafNode<K, V> {
+        unsafe {
+            &**self.node
+        }
+    }
+
+    pub fn keys(&self) -> &[K] {
+        self.reborrow().into_slices().0
+    }
+
+    pub fn vals(&self) -> &[V] {
+        self.reborrow().into_slices().1
+    }
+
+    pub fn ascend(self) -> Result<
+        Handle<
+            NodeRef<
+                BorrowType,
+                K, V,
+                marker::Internal
+            >,
+            marker::Edge
+        >,
+        Self
+    > {
+        if self.as_leaf().parent.is_null() {
+            Err(self)
+        } else {
+            Ok(Handle {
+                node: NodeRef {
+                    height: self.height + 1,
+                    node: unsafe {
+                        NonZero::new(self.as_leaf().parent as *mut LeafNode<K, V>)
+                    },
+                    root: self.root,
+                    _marker: PhantomData
+                },
+                idx: self.as_leaf().parent_idx as usize,
+                _marker: PhantomData
+            })
+        }
+    }
+
+    pub fn first_edge(self) -> Handle<Self, marker::Edge> {
+        Handle::new_edge(self, 0)
+    }
+
+    pub fn last_edge(self) -> Handle<Self, marker::Edge> {
+        let len = self.len();
+        Handle::new_edge(self, len)
+    }
+}
+
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
+    pub unsafe fn deallocate_and_ascend(self) -> Option<
+        Handle<
+            NodeRef<
+                marker::Owned,
+                K, V,
+                marker::Internal
+            >,
+            marker::Edge
+        >
+    > {
+        let ptr = self.as_leaf() as *const LeafNode<K, V> as *const u8 as *mut u8;
+        let ret = self.ascend().ok();
+        heap::deallocate(ptr, mem::size_of::<LeafNode<K, V>>(), mem::align_of::<LeafNode<K, V>>());
+        ret
+    }
+}
+
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
+    pub unsafe fn deallocate_and_ascend(self) -> Option<
+        Handle<
+            NodeRef<
+                marker::Owned,
+                K, V,
+                marker::Internal
+            >,
+            marker::Edge
+        >
+    > {
+        let ptr = self.as_internal() as *const InternalNode<K, V> as *const u8 as *mut u8;
+        let ret = self.ascend().ok();
+        heap::deallocate(
+            ptr,
+            mem::size_of::<InternalNode<K, V>>(),
+            mem::align_of::<InternalNode<K, V>>()
+        );
+        ret
+    }
+}
+
+impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+    unsafe fn cast_unchecked<NewType>(&mut self)
+            -> NodeRef<marker::Mut, K, V, NewType> {
+
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
+        }
+    }
+
+    unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut, K, V, Type> {
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
+        }
+    }
+
+    fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
+        unsafe {
+            &mut *(*self.node as *mut LeafNode<K, V>)
+        }
+    }
+
+    pub fn keys_mut(&mut self) -> &mut [K] {
+        unsafe { self.reborrow_mut().into_slices_mut().0 }
+    }
+
+    pub fn vals_mut(&mut self) -> &mut [V] {
+        unsafe { self.reborrow_mut().into_slices_mut().1 }
+    }
+}
+
+impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
+    pub fn into_slices(self) -> (&'a [K], &'a [V]) {
+        unsafe {
+            (
+                slice::from_raw_parts(
+                    self.as_leaf().keys.as_ptr(),
+                    self.len()
+                ),
+                slice::from_raw_parts(
+                    self.as_leaf().vals.as_ptr(),
+                    self.len()
+                )
+            )
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+    pub fn into_root_mut(self) -> &'a mut Root<K, V> {
+        unsafe {
+            &mut *(self.root as *mut Root<K, V>)
+        }
+    }
+
+    pub fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
+        unsafe {
+            (
+                slice::from_raw_parts_mut(
+                    &mut self.as_leaf_mut().keys as *mut [K] as *mut K,
+                    self.len()
+                ),
+                slice::from_raw_parts_mut(
+                    &mut self.as_leaf_mut().vals as *mut [V] as *mut V,
+                    self.len()
+                )
+            )
+        }
+    }
+}
+
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
+    pub fn push(&mut self, key: K, val: V) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() < CAPACITY);
+
+        let idx = self.len();
+
+        unsafe {
+            ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
+            ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
+        }
+
+        self.as_leaf_mut().len += 1;
+    }
+
+    pub fn push_front(&mut self, key: K, val: V) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() < CAPACITY);
+
+        unsafe {
+            slice_insert(self.keys_mut(), 0, key);
+            slice_insert(self.vals_mut(), 0, val);
+        }
+
+        self.as_leaf_mut().len += 1;
+    }
+}
+
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
+    pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(edge.height == self.height - 1);
+        debug_assert!(self.len() < CAPACITY);
+
+        let idx = self.len();
+
+        unsafe {
+            ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
+            ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
+            ptr::write(self.as_internal_mut().edges.get_unchecked_mut(idx + 1), edge.node);
+
+            self.as_leaf_mut().len += 1;
+
+            Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
+        }
+    }
+
+    pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(edge.height == self.height - 1);
+        debug_assert!(self.len() < CAPACITY);
+
+        unsafe {
+            slice_insert(self.keys_mut(), 0, key);
+            slice_insert(self.vals_mut(), 0, val);
+            slice_insert(
+                slice::from_raw_parts_mut(
+                    self.as_internal_mut().edges.as_mut_ptr(),
+                    self.len()+1
+                ),
+                0,
+                edge.node
+            );
+
+            self.as_leaf_mut().len += 1;
+
+            for i in 0..self.len()+1 {
+                Handle::new_edge(self.reborrow_mut(), i).correct_parent_link();
+            }
+        }
+
+    }
+}
+
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
+    pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() > 0);
+
+        let idx = self.len() - 1;
+
+        unsafe {
+            let key = ptr::read(self.keys().get_unchecked(idx));
+            let val = ptr::read(self.vals().get_unchecked(idx));
+            let edge = match self.reborrow_mut().force() {
+                ForceResult::Leaf(_) => None,
+                ForceResult::Internal(internal) => {
+                    let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1));
+                    let mut new_root = Root { node: edge, height: internal.height - 1 };
+                    new_root.as_mut().as_leaf_mut().parent = ptr::null();
+                    Some(new_root)
+                }
+            };
+
+            self.as_leaf_mut().len -= 1;
+            (key, val, edge)
+        }
+    }
+
+    pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() > 0);
+
+        let old_len = self.len();
+
+        unsafe {
+            let key = slice_remove(self.keys_mut(), 0);
+            let val = slice_remove(self.vals_mut(), 0);
+            let edge = match self.reborrow_mut().force() {
+                ForceResult::Leaf(_) => None,
+                ForceResult::Internal(mut internal) => {
+                    let edge = slice_remove(
+                        slice::from_raw_parts_mut(
+                            internal.as_internal_mut().edges.as_mut_ptr(),
+                            old_len+1
+                        ),
+                        0
+                    );
+
+                    let mut new_root = Root { node: edge, height: internal.height - 1 };
+                    new_root.as_mut().as_leaf_mut().parent = ptr::null();
+
+                    for i in 0..old_len {
+                        Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
+                    }
+
+                    Some(new_root)
+                }
+            };
+
+            self.as_leaf_mut().len -= 1;
+
+            (key, val, edge)
+        }
+    }
+}
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+    pub fn force(self) -> ForceResult<
+        NodeRef<BorrowType, K, V, marker::Leaf>,
+        NodeRef<BorrowType, K, V, marker::Internal>
+    > {
+        if self.height == 0 {
+            ForceResult::Leaf(NodeRef {
+                height: self.height,
+                node: self.node,
+                root: self.root,
+                _marker: PhantomData
+            })
+        } else {
+            ForceResult::Internal(NodeRef {
+                height: self.height,
+                node: self.node,
+                root: self.root,
+                _marker: PhantomData
+            })
+        }
+    }
+}
+
+pub struct Handle<Node, Type> {
+    node: Node,
+    idx: usize,
+    _marker: PhantomData<Type>
+}
+
+impl<Node: Copy, Type> Copy for Handle<Node, Type> { }
+impl<Node: Copy, Type> Clone for Handle<Node, Type> {
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+impl<Node, Type> Handle<Node, Type> {
+    pub fn into_node(self) -> Node {
+        self.node
+    }
+}
+
+impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
+    pub fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
+        // Necessary for correctness, but in a private module
+        debug_assert!(idx < node.len());
+
+        Handle {
+            node: node,
+            idx: idx,
+            _marker: PhantomData
+        }
+    }
+
+    pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+        Handle::new_edge(self.node, self.idx)
+    }
+
+    pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+        Handle::new_edge(self.node, self.idx + 1)
+    }
+}
+
+impl<BorrowType, K, V, NodeType, HandleType> PartialEq
+        for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
+
+    fn eq(&self, other: &Self) -> bool {
+        self.node.node == other.node.node && self.idx == other.idx
+    }
+}
+
+impl<BorrowType, K, V, NodeType, HandleType>
+        Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
+
+    pub fn reborrow(&self)
+            -> Handle<NodeRef<marker::Immut, K, V, NodeType>, HandleType> {
+
+        // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
+        Handle {
+            node: self.node.reborrow(),
+            idx: self.idx,
+            _marker: PhantomData
+        }
+    }
+}
+
+impl<'a, K, V, NodeType, HandleType>
+        Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
+
+    pub unsafe fn reborrow_mut(&mut self)
+            -> Handle<NodeRef<marker::Mut, K, V, NodeType>, HandleType> {
+
+        // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
+        Handle {
+            node: self.node.reborrow_mut(),
+            idx: self.idx,
+            _marker: PhantomData
+        }
+    }
+}
+
+impl<BorrowType, K, V, NodeType>
+        Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+
+    pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
+        // Necessary for correctness, but in a private module
+        debug_assert!(idx <= node.len());
+
+        Handle {
+            node: node,
+            idx: idx,
+            _marker: PhantomData
+        }
+    }
+
+    pub fn left_kv(self)
+            -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
+
+        if self.idx > 0 {
+            Ok(Handle::new_kv(self.node, self.idx - 1))
+        } else {
+            Err(self)
+        }
+    }
+
+    pub fn right_kv(self)
+            -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
+
+        if self.idx < self.node.len() {
+            Ok(Handle::new_kv(self.node, self.idx))
+        } else {
+            Err(self)
+        }
+    }
+}
+
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    fn insert_fit(&mut self, key: K, val: V) -> *mut V {
+        // Necessary for correctness, but in a private module
+        debug_assert!(self.node.len() < CAPACITY);
+
+        unsafe {
+            slice_insert(self.node.keys_mut(), self.idx, key);
+            slice_insert(self.node.vals_mut(), self.idx, val);
+
+            self.node.as_leaf_mut().len += 1;
+
+            self.node.vals_mut().get_unchecked_mut(self.idx)
+        }
+    }
+
+    pub fn insert(mut self, key: K, val: V)
+            -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
+
+        if self.node.len() < CAPACITY {
+            let ptr = self.insert_fit(key, val);
+            (InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr)
+        } else {
+            let middle = Handle::new_kv(self.node, B);
+            let (mut left, k, v, mut right) = middle.split();
+            let ptr = if self.idx <= B {
+                unsafe {
+                    Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val)
+                }
+            } else {
+                unsafe {
+                    Handle::new_edge(
+                        right.as_mut().cast_unchecked::<marker::Leaf>(),
+                        self.idx - (B + 1)
+                    ).insert_fit(key, val)
+                }
+            };
+            (InsertResult::Split(left, k, v, right), ptr)
+        }
+    }
+}
+
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+    fn correct_parent_link(mut self) {
+        let idx = self.idx as u16;
+        let ptr = self.node.as_internal_mut() as *mut _;
+        let mut child = self.descend();
+        child.as_leaf_mut().parent = ptr;
+        child.as_leaf_mut().parent_idx = idx;
+    }
+
+    unsafe fn cast_unchecked<NewType>(&mut self)
+            -> Handle<NodeRef<marker::Mut, K, V, NewType>, marker::Edge> {
+
+        Handle::new_edge(self.node.cast_unchecked(), self.idx)
+    }
+
+    fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
+        // Necessary for correctness, but in an internal module
+        debug_assert!(self.node.len() < CAPACITY);
+        debug_assert!(edge.height == self.node.height - 1);
+
+        unsafe {
+            self.cast_unchecked::<marker::Leaf>().insert_fit(key, val);
+
+            slice_insert(
+                slice::from_raw_parts_mut(
+                    self.node.as_internal_mut().edges.as_mut_ptr(),
+                    self.node.len()
+                ),
+                self.idx + 1,
+                edge.node
+            );
+
+            for i in (self.idx+1)..(self.node.len()+1) {
+                Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
+            }
+        }
+    }
+
+    pub fn insert(mut self, key: K, val: V, edge: Root<K, V>)
+            -> InsertResult<'a, K, V, marker::Internal> {
+
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(edge.height == self.node.height - 1);
+
+        if self.node.len() < CAPACITY {
+            self.insert_fit(key, val, edge);
+            InsertResult::Fit(Handle::new_kv(self.node, self.idx))
+        } else {
+            let middle = Handle::new_kv(self.node, B);
+            let (mut left, k, v, mut right) = middle.split();
+            if self.idx <= B {
+                unsafe {
+                    Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge);
+                }
+            } else {
+                unsafe {
+                    Handle::new_edge(
+                        right.as_mut().cast_unchecked::<marker::Internal>(),
+                        self.idx - (B + 1)
+                    ).insert_fit(key, val, edge);
+                }
+            }
+            InsertResult::Split(left, k, v, right)
+        }
+    }
+}
+
+impl<BorrowType, K, V>
+        Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
+
+    pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.node.height - 1,
+            node: unsafe { self.node.as_internal().edges.get_unchecked(self.idx).as_ptr() },
+            root: self.node.root,
+            _marker: PhantomData
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a, NodeType>
+        Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
+
+    pub fn into_kv(self) -> (&'a K, &'a V) {
+        let (keys, vals) = self.node.into_slices();
+        unsafe {
+            (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx))
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a, NodeType>
+        Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
+
+    pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
+        let (mut keys, mut vals) = self.node.into_slices_mut();
+        unsafe {
+            (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+        }
+    }
+}
+
+impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
+    pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
+        unsafe {
+            let (mut keys, mut vals) = self.node.reborrow_mut().into_slices_mut();
+            (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+        }
+    }
+}
+
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
+    pub fn split(mut self)
+            -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
+        unsafe {
+            let mut new_node = Box::new(LeafNode::new());
+
+            let k = ptr::read(self.node.keys().get_unchecked(self.idx));
+            let v = ptr::read(self.node.vals().get_unchecked(self.idx));
+
+            let new_len = self.node.len() - self.idx - 1;
+
+            ptr::copy_nonoverlapping(
+                self.node.keys().as_ptr().offset(self.idx as isize + 1),
+                new_node.keys.as_mut_ptr(),
+                new_len
+            );
+            ptr::copy_nonoverlapping(
+                self.node.vals().as_ptr().offset(self.idx as isize + 1),
+                new_node.vals.as_mut_ptr(),
+                new_len
+            );
+
+            self.node.as_leaf_mut().len = self.idx as u16;
+            new_node.len = new_len as u16;
+
+            (
+                self.node,
+                k, v,
+                Root {
+                    node: BoxedNode::from_leaf(new_node),
+                    height: 0
+                }
+            )
+        }
+    }
+
+    pub fn remove(mut self)
+            -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
+        unsafe {
+            let k = slice_remove(self.node.keys_mut(), self.idx);
+            let v = slice_remove(self.node.vals_mut(), self.idx);
+            self.node.as_leaf_mut().len -= 1;
+            (self.left_edge(), k, v)
+        }
+    }
+}
+
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
+    pub fn split(mut self)
+            -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
+        unsafe {
+            let mut new_node = Box::new(InternalNode::new());
+
+            let k = ptr::read(self.node.keys().get_unchecked(self.idx));
+            let v = ptr::read(self.node.vals().get_unchecked(self.idx));
+
+            let height = self.node.height;
+            let new_len = self.node.len() - self.idx - 1;
+
+            ptr::copy_nonoverlapping(
+                self.node.keys().as_ptr().offset(self.idx as isize + 1),
+                new_node.data.keys.as_mut_ptr(),
+                new_len
+            );
+            ptr::copy_nonoverlapping(
+                self.node.vals().as_ptr().offset(self.idx as isize + 1),
+                new_node.data.vals.as_mut_ptr(),
+                new_len
+            );
+            ptr::copy_nonoverlapping(
+                self.node.as_internal().edges.as_ptr().offset(self.idx as isize + 1),
+                new_node.edges.as_mut_ptr(),
+                new_len + 1
+            );
+
+            self.node.as_leaf_mut().len = self.idx as u16;
+            new_node.data.len = new_len as u16;
+
+            let mut new_root = Root {
+                node: BoxedNode::from_internal(new_node),
+                height: height
+            };
+
+            for i in 0..(new_len+1) {
+                Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link();
+            }
+
+            (
+                self.node,
+                k, v,
+                new_root
+            )
+        }
+    }
+
+    pub fn can_merge(&self) -> bool {
+        (
+            self.reborrow()
+                .left_edge()
+                .descend()
+                .len()
+          + self.reborrow()
+                .right_edge()
+                .descend()
+                .len()
+          + 1
+        ) <= CAPACITY
+    }
+
+    pub fn merge(mut self)
+            -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+        let self1 = unsafe { ptr::read(&self) };
+        let self2 = unsafe { ptr::read(&self) };
+        let mut left_node = self1.left_edge().descend();
+        let left_len = left_node.len();
+        let mut right_node = self2.right_edge().descend();
+        let right_len = right_node.len();
+
+        // necessary for correctness, but in a private module
+        debug_assert!(left_len + right_len + 1 <= CAPACITY);
+
+        unsafe {
+            ptr::write(left_node.keys_mut().get_unchecked_mut(left_len),
+                       slice_remove(self.node.keys_mut(), self.idx));
+            ptr::copy_nonoverlapping(
+                right_node.keys().as_ptr(),
+                left_node.keys_mut().as_mut_ptr().offset(left_len as isize + 1),
+                right_len
+            );
+            ptr::write(left_node.vals_mut().get_unchecked_mut(left_len),
+                       slice_remove(self.node.vals_mut(), self.idx));
+            ptr::copy_nonoverlapping(
+                right_node.vals().as_ptr(),
+                left_node.vals_mut().as_mut_ptr().offset(left_len as isize + 1),
+                right_len
+            );
+
+            slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
+            for i in self.idx+1..self.node.len() {
+                Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
+            }
+            self.node.as_leaf_mut().len -= 1;
+
+            left_node.as_leaf_mut().len += right_len as u16 + 1;
+
+            if self.node.height > 1 {
+                ptr::copy_nonoverlapping(
+                    right_node.cast_unchecked().as_internal().edges.as_ptr(),
+                    left_node.cast_unchecked()
+                             .as_internal_mut()
+                             .edges
+                             .as_mut_ptr()
+                             .offset(left_len as isize + 1),
+                    right_len + 1
+                );
+
+                for i in left_len+1..left_len+right_len+2 {
+                    Handle::new_edge(
+                        left_node.cast_unchecked().reborrow_mut(),
+                        i
+                    ).correct_parent_link();
+                }
+
+                heap::deallocate(
+                    *right_node.node as *mut u8,
+                    mem::size_of::<InternalNode<K, V>>(),
+                    mem::align_of::<InternalNode<K, V>>()
+                );
+            } else {
+                heap::deallocate(
+                    *right_node.node as *mut u8,
+                    mem::size_of::<LeafNode<K, V>>(),
+                    mem::align_of::<LeafNode<K, V>>()
+                );
+            }
+
+            Handle::new_edge(self.node, self.idx)
+        }
+    }
+}
+
+impl<BorrowType, K, V, HandleType>
+        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> {
+
+    pub fn force(self) -> ForceResult<
+        Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
+        Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>
+    > {
+        match self.node.force() {
+            ForceResult::Leaf(node) => ForceResult::Leaf(Handle {
+                node: node,
+                idx: self.idx,
+                _marker: PhantomData
+            }),
+            ForceResult::Internal(node) => ForceResult::Internal(Handle {
+                node: node,
+                idx: self.idx,
+                _marker: PhantomData
+            })
+        }
+    }
+}
+
+pub enum ForceResult<Leaf, Internal> {
+    Leaf(Leaf),
+    Internal(Internal)
+}
+
+pub enum InsertResult<'a, K, V, Type> {
+    Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
+    Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>)
+}
+
+pub mod marker {
+    use core::marker::PhantomData;
+
+    pub enum Leaf { }
+    pub enum Internal { }
+    pub enum LeafOrInternal { }
+
+    pub enum Owned { }
+    pub struct Immut<'a>(PhantomData<&'a ()>);
+    pub struct Mut<'a>(PhantomData<&'a mut ()>);
+
+    pub enum KV { }
+    pub enum Edge { }
+}
+
+unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
+    ptr::copy(
+        slice.as_ptr().offset(idx as isize),
+        slice.as_mut_ptr().offset(idx as isize + 1),
+        slice.len() - idx
+    );
+    ptr::write(slice.get_unchecked_mut(idx), val);
+}
+
+unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
+    let ret = ptr::read(slice.get_unchecked(idx));
+    ptr::copy(
+        slice.as_ptr().offset(idx as isize + 1),
+        slice.as_mut_ptr().offset(idx as isize),
+        slice.len() - idx - 1
+    );
+    ret
+}
diff --git a/libcollections/btree/search.rs b/libcollections/btree/search.rs
new file mode 100644
index 0000000..c94b570
--- /dev/null
+++ b/libcollections/btree/search.rs
@@ -0,0 +1,76 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use core::cmp::Ordering;
+
+use borrow::Borrow;
+
+use super::node::{Handle, NodeRef, marker};
+
+use super::node::ForceResult::*;
+use self::SearchResult::*;
+
+pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
+    Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>),
+    GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>)
+}
+
+pub fn search_tree<BorrowType, K, V, Q: ?Sized>(
+    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+    key: &Q
+) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf>
+        where Q: Ord, K: Borrow<Q> {
+
+    loop {
+        match search_node(node, key) {
+            Found(handle) => return Found(handle),
+            GoDown(handle) => match handle.force() {
+                Leaf(leaf) => return GoDown(leaf),
+                Internal(internal) => {
+                    node = internal.descend();
+                    continue;
+                }
+            }
+        }
+    }
+}
+
+pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>(
+    node: NodeRef<BorrowType, K, V, Type>,
+    key: &Q
+) -> SearchResult<BorrowType, K, V, Type, Type>
+        where Q: Ord, K: Borrow<Q> {
+
+    match search_linear(&node, key) {
+        (idx, true) => Found(
+            Handle::new_kv(node, idx)
+        ),
+        (idx, false) => SearchResult::GoDown(
+            Handle::new_edge(node, idx)
+        )
+    }
+}
+
+fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
+    node: &NodeRef<BorrowType, K, V, Type>,
+    key: &Q
+) -> (usize, bool)
+        where Q: Ord, K: Borrow<Q> {
+
+    for (i, k) in node.keys().iter().enumerate() {
+        match key.cmp(k.borrow()) {
+            Ordering::Greater => {},
+            Ordering::Equal => return (i, true),
+            Ordering::Less => return (i, false)
+        }
+    }
+    (node.keys().len(), false)
+}
+
diff --git a/libcollections/btree/set.rs b/libcollections/btree/set.rs
new file mode 100644
index 0000000..23e0af8
--- /dev/null
+++ b/libcollections/btree/set.rs
@@ -0,0 +1,926 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface
+// to TreeMap
+
+use core::cmp::Ordering::{self, Less, Greater, Equal};
+use core::cmp::{min, max};
+use core::fmt::Debug;
+use core::fmt;
+use core::iter::{Peekable, FromIterator};
+use core::ops::{BitOr, BitAnd, BitXor, Sub};
+
+use borrow::Borrow;
+use btree_map::{BTreeMap, Keys};
+use super::Recover;
+use Bound;
+
+// FIXME(conventions): implement bounded iterators
+
+/// A set based on a B-Tree.
+///
+/// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
+/// benefits and drawbacks.
+///
+/// It is a logic error for an item to be modified in such a way that the item's ordering relative
+/// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
+/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
+///
+/// [`BTreeMap`]: struct.BTreeMap.html
+/// [`Ord`]: ../../std/cmp/trait.Ord.html
+/// [`Cell`]: ../../std/cell/struct.Cell.html
+/// [`RefCell`]: ../../std/cell/struct.RefCell.html
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::BTreeSet;
+///
+/// // Type inference lets us omit an explicit type signature (which
+/// // would be `BTreeSet<&str>` in this example).
+/// let mut books = BTreeSet::new();
+///
+/// // Add some books.
+/// books.insert("A Dance With Dragons");
+/// books.insert("To Kill a Mockingbird");
+/// books.insert("The Odyssey");
+/// books.insert("The Great Gatsby");
+///
+/// // Check for a specific one.
+/// if !books.contains("The Winds of Winter") {
+///     println!("We have {} books, but The Winds of Winter ain't one.",
+///              books.len());
+/// }
+///
+/// // Remove a book.
+/// books.remove("The Odyssey");
+///
+/// // Iterate over everything.
+/// for book in &books {
+///     println!("{}", book);
+/// }
+/// ```
+#[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct BTreeSet<T> {
+    map: BTreeMap<T, ()>,
+}
+
+/// An iterator over a BTreeSet's items.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Iter<'a, T: 'a> {
+    iter: Keys<'a, T, ()>,
+}
+
+/// An owning iterator over a BTreeSet's items.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct IntoIter<T> {
+    iter: ::btree_map::IntoIter<T, ()>,
+}
+
+/// An iterator over a sub-range of BTreeSet's items.
+pub struct Range<'a, T: 'a> {
+    iter: ::btree_map::Range<'a, T, ()>,
+}
+
+/// A lazy iterator producing elements in the set difference (in-order).
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Difference<'a, T: 'a> {
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
+}
+
+/// A lazy iterator producing elements in the set symmetric difference (in-order).
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct SymmetricDifference<'a, T: 'a> {
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
+}
+
+/// A lazy iterator producing elements in the set intersection (in-order).
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Intersection<'a, T: 'a> {
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
+}
+
+/// A lazy iterator producing elements in the set union (in-order).
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Union<'a, T: 'a> {
+    a: Peekable<Iter<'a, T>>,
+    b: Peekable<Iter<'a, T>>,
+}
+
+impl<T: Ord> BTreeSet<T> {
+    /// Makes a new BTreeSet with a reasonable choice of B.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![allow(unused_mut)]
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut set: BTreeSet<i32> = BTreeSet::new();
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn new() -> BTreeSet<T> {
+        BTreeSet { map: BTreeMap::new() }
+    }
+}
+
+impl<T> BTreeSet<T> {
+    /// Gets an iterator over the BTreeSet's contents.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
+    ///
+    /// for x in set.iter() {
+    ///     println!("{}", x);
+    /// }
+    ///
+    /// let v: Vec<_> = set.iter().cloned().collect();
+    /// assert_eq!(v, [1, 2, 3, 4]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn iter(&self) -> Iter<T> {
+        Iter { iter: self.map.keys() }
+    }
+}
+
+impl<T: Ord> BTreeSet<T> {
+    /// Constructs a double-ended iterator over a sub-range of elements in the set, starting
+    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
+    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
+    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(btree_range, collections_bound)]
+    ///
+    /// use std::collections::BTreeSet;
+    /// use std::collections::Bound::{Included, Unbounded};
+    ///
+    /// let mut set = BTreeSet::new();
+    /// set.insert(3);
+    /// set.insert(5);
+    /// set.insert(8);
+    /// for &elem in set.range(Included(&4), Included(&8)) {
+    ///     println!("{}", elem);
+    /// }
+    /// assert_eq!(Some(&5), set.range(Included(&4), Unbounded).next());
+    /// ```
+    #[unstable(feature = "btree_range",
+               reason = "matches collection reform specification, waiting for dust to settle",
+               issue = "27787")]
+    pub fn range<'a, Min: ?Sized + Ord, Max: ?Sized + Ord>(&'a self,
+                                                           min: Bound<&Min>,
+                                                           max: Bound<&Max>)
+                                                           -> Range<'a, T>
+        where T: Borrow<Min> + Borrow<Max>
+    {
+        Range { iter: self.map.range(min, max) }
+    }
+}
+
+impl<T: Ord> BTreeSet<T> {
+    /// Visits the values representing the difference, in ascending order.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut a = BTreeSet::new();
+    /// a.insert(1);
+    /// a.insert(2);
+    ///
+    /// let mut b = BTreeSet::new();
+    /// b.insert(2);
+    /// b.insert(3);
+    ///
+    /// let diff: Vec<_> = a.difference(&b).cloned().collect();
+    /// assert_eq!(diff, [1]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> {
+        Difference {
+            a: self.iter().peekable(),
+            b: other.iter().peekable(),
+        }
+    }
+
+    /// Visits the values representing the symmetric difference, in ascending order.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut a = BTreeSet::new();
+    /// a.insert(1);
+    /// a.insert(2);
+    ///
+    /// let mut b = BTreeSet::new();
+    /// b.insert(2);
+    /// b.insert(3);
+    ///
+    /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
+    /// assert_eq!(sym_diff, [1, 3]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn symmetric_difference<'a>(&'a self,
+                                    other: &'a BTreeSet<T>)
+                                    -> SymmetricDifference<'a, T> {
+        SymmetricDifference {
+            a: self.iter().peekable(),
+            b: other.iter().peekable(),
+        }
+    }
+
+    /// Visits the values representing the intersection, in ascending order.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut a = BTreeSet::new();
+    /// a.insert(1);
+    /// a.insert(2);
+    ///
+    /// let mut b = BTreeSet::new();
+    /// b.insert(2);
+    /// b.insert(3);
+    ///
+    /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
+    /// assert_eq!(intersection, [2]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> {
+        Intersection {
+            a: self.iter().peekable(),
+            b: other.iter().peekable(),
+        }
+    }
+
+    /// Visits the values representing the union, in ascending order.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut a = BTreeSet::new();
+    /// a.insert(1);
+    ///
+    /// let mut b = BTreeSet::new();
+    /// b.insert(2);
+    ///
+    /// let union: Vec<_> = a.union(&b).cloned().collect();
+    /// assert_eq!(union, [1, 2]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T> {
+        Union {
+            a: self.iter().peekable(),
+            b: other.iter().peekable(),
+        }
+    }
+
+    /// Returns the number of elements in the set.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut v = BTreeSet::new();
+    /// assert_eq!(v.len(), 0);
+    /// v.insert(1);
+    /// assert_eq!(v.len(), 1);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn len(&self) -> usize {
+        self.map.len()
+    }
+
+    /// Returns true if the set contains no elements.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut v = BTreeSet::new();
+    /// assert!(v.is_empty());
+    /// v.insert(1);
+    /// assert!(!v.is_empty());
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Clears the set, removing all values.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut v = BTreeSet::new();
+    /// v.insert(1);
+    /// v.clear();
+    /// assert!(v.is_empty());
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn clear(&mut self) {
+        self.map.clear()
+    }
+
+    /// Returns `true` if the set contains a value.
+    ///
+    /// The value may be any borrowed form of the set's value type,
+    /// but the ordering on the borrowed form *must* match the
+    /// ordering on the value type.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
+    /// assert_eq!(set.contains(&1), true);
+    /// assert_eq!(set.contains(&4), false);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
+        where T: Borrow<Q>,
+              Q: Ord
+    {
+        self.map.contains_key(value)
+    }
+
+    /// Returns a reference to the value in the set, if any, that is equal to the given value.
+    ///
+    /// The value may be any borrowed form of the set's value type,
+    /// but the ordering on the borrowed form *must* match the
+    /// ordering on the value type.
+    #[unstable(feature = "set_recovery", issue = "28050")]
+    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
+        where T: Borrow<Q>,
+              Q: Ord
+    {
+        Recover::get(&self.map, value)
+    }
+
+    /// Returns `true` if the set has no elements in common with `other`.
+    /// This is equivalent to checking for an empty intersection.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
+    /// let mut b = BTreeSet::new();
+    ///
+    /// assert_eq!(a.is_disjoint(&b), true);
+    /// b.insert(4);
+    /// assert_eq!(a.is_disjoint(&b), true);
+    /// b.insert(1);
+    /// assert_eq!(a.is_disjoint(&b), false);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool {
+        self.intersection(other).next().is_none()
+    }
+
+    /// Returns `true` if the set is a subset of another.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
+    /// let mut set = BTreeSet::new();
+    ///
+    /// assert_eq!(set.is_subset(&sup), true);
+    /// set.insert(2);
+    /// assert_eq!(set.is_subset(&sup), true);
+    /// set.insert(4);
+    /// assert_eq!(set.is_subset(&sup), false);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn is_subset(&self, other: &BTreeSet<T>) -> bool {
+        // Stolen from TreeMap
+        let mut x = self.iter();
+        let mut y = other.iter();
+        let mut a = x.next();
+        let mut b = y.next();
+        while a.is_some() {
+            if b.is_none() {
+                return false;
+            }
+
+            let a1 = a.unwrap();
+            let b1 = b.unwrap();
+
+            match b1.cmp(a1) {
+                Less => (),
+                Greater => return false,
+                Equal => a = x.next(),
+            }
+
+            b = y.next();
+        }
+        true
+    }
+
+    /// Returns `true` if the set is a superset of another.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect();
+    /// let mut set = BTreeSet::new();
+    ///
+    /// assert_eq!(set.is_superset(&sub), false);
+    ///
+    /// set.insert(0);
+    /// set.insert(1);
+    /// assert_eq!(set.is_superset(&sub), false);
+    ///
+    /// set.insert(2);
+    /// assert_eq!(set.is_superset(&sub), true);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn is_superset(&self, other: &BTreeSet<T>) -> bool {
+        other.is_subset(self)
+    }
+
+    /// Adds a value to the set.
+    ///
+    /// If the set did not have a value present, `true` is returned.
+    ///
+    /// If the set did have this key 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
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut set = BTreeSet::new();
+    ///
+    /// assert_eq!(set.insert(2), true);
+    /// assert_eq!(set.insert(2), false);
+    /// assert_eq!(set.len(), 1);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn insert(&mut self, value: T) -> bool {
+        self.map.insert(value, ()).is_none()
+    }
+
+    /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
+    /// one. Returns the replaced value.
+    #[unstable(feature = "set_recovery", issue = "28050")]
+    pub fn replace(&mut self, value: T) -> Option<T> {
+        Recover::replace(&mut self.map, value)
+    }
+
+    /// Removes a value from the set. Returns `true` if the value was
+    /// present in the set.
+    ///
+    /// The value may be any borrowed form of the set's value type,
+    /// but the ordering on the borrowed form *must* match the
+    /// ordering on the value type.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let mut set = BTreeSet::new();
+    ///
+    /// set.insert(2);
+    /// assert_eq!(set.remove(&2), true);
+    /// assert_eq!(set.remove(&2), false);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
+        where T: Borrow<Q>,
+              Q: Ord
+    {
+        self.map.remove(value).is_some()
+    }
+
+    /// Removes and returns the value in the set, if any, that is equal to the given one.
+    ///
+    /// The value may be any borrowed form of the set's value type,
+    /// but the ordering on the borrowed form *must* match the
+    /// ordering on the value type.
+    #[unstable(feature = "set_recovery", issue = "28050")]
+    pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
+        where T: Borrow<Q>,
+              Q: Ord
+    {
+        Recover::take(&mut self.map, value)
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Ord> FromIterator<T> for BTreeSet<T> {
+    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
+        let mut set = BTreeSet::new();
+        set.extend(iter);
+        set
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T> IntoIterator for BTreeSet<T> {
+    type Item = T;
+    type IntoIter = IntoIter<T>;
+
+    /// Gets an iterator for moving out the BtreeSet's contents.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
+    ///
+    /// let v: Vec<_> = set.into_iter().collect();
+    /// assert_eq!(v, [1, 2, 3, 4]);
+    /// ```
+    fn into_iter(self) -> IntoIter<T> {
+        IntoIter { iter: self.map.into_iter() }
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T> IntoIterator for &'a BTreeSet<T> {
+    type Item = &'a T;
+    type IntoIter = Iter<'a, T>;
+
+    fn into_iter(self) -> Iter<'a, T> {
+        self.iter()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Ord> Extend<T> for BTreeSet<T> {
+    #[inline]
+    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
+        for elem in iter {
+            self.insert(elem);
+        }
+    }
+}
+
+#[stable(feature = "extend_ref", since = "1.2.0")]
+impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> {
+    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
+        self.extend(iter.into_iter().cloned());
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Ord> Default for BTreeSet<T> {
+    fn default() -> BTreeSet<T> {
+        BTreeSet::new()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, 'b, T: Ord + Clone> Sub<&'b BTreeSet<T>> for &'a BTreeSet<T> {
+    type Output = BTreeSet<T>;
+
+    /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
+    /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
+    ///
+    /// let result = &a - &b;
+    /// let result_vec: Vec<_> = result.into_iter().collect();
+    /// assert_eq!(result_vec, [1, 2]);
+    /// ```
+    fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
+        self.difference(rhs).cloned().collect()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, 'b, T: Ord + Clone> BitXor<&'b BTreeSet<T>> for &'a BTreeSet<T> {
+    type Output = BTreeSet<T>;
+
+    /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
+    /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
+    ///
+    /// let result = &a ^ &b;
+    /// let result_vec: Vec<_> = result.into_iter().collect();
+    /// assert_eq!(result_vec, [1, 4]);
+    /// ```
+    fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
+        self.symmetric_difference(rhs).cloned().collect()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, 'b, T: Ord + Clone> BitAnd<&'b BTreeSet<T>> for &'a BTreeSet<T> {
+    type Output = BTreeSet<T>;
+
+    /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
+    /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
+    ///
+    /// let result = &a & &b;
+    /// let result_vec: Vec<_> = result.into_iter().collect();
+    /// assert_eq!(result_vec, [2, 3]);
+    /// ```
+    fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
+        self.intersection(rhs).cloned().collect()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, 'b, T: Ord + Clone> BitOr<&'b BTreeSet<T>> for &'a BTreeSet<T> {
+    type Output = BTreeSet<T>;
+
+    /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
+    /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
+    ///
+    /// let result = &a | &b;
+    /// let result_vec: Vec<_> = result.into_iter().collect();
+    /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
+    /// ```
+    fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
+        self.union(rhs).cloned().collect()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Debug> Debug for BTreeSet<T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_set().entries(self.iter()).finish()
+    }
+}
+
+impl<'a, T> Clone for Iter<'a, T> {
+    fn clone(&self) -> Iter<'a, T> {
+        Iter { iter: self.iter.clone() }
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T> Iterator for Iter<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<&'a T> {
+        self.iter.next()
+    }
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
+    fn next_back(&mut self) -> Option<&'a T> {
+        self.iter.next_back()
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T> ExactSizeIterator for Iter<'a, T> {
+    fn len(&self) -> usize { self.iter.len() }
+}
+
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T> Iterator for IntoIter<T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        self.iter.next().map(|(k, _)| k)
+    }
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T> DoubleEndedIterator for IntoIter<T> {
+    fn next_back(&mut self) -> Option<T> {
+        self.iter.next_back().map(|(k, _)| k)
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T> ExactSizeIterator for IntoIter<T> {
+    fn len(&self) -> usize { self.iter.len() }
+}
+
+
+impl<'a, T> Clone for Range<'a, T> {
+    fn clone(&self) -> Range<'a, T> {
+        Range { iter: self.iter.clone() }
+    }
+}
+impl<'a, T> Iterator for Range<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<&'a T> {
+        self.iter.next().map(|(k, _)| k)
+    }
+}
+impl<'a, T> DoubleEndedIterator for Range<'a, T> {
+    fn next_back(&mut self) -> Option<&'a T> {
+        self.iter.next_back().map(|(k, _)| k)
+    }
+}
+
+/// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
+fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering {
+    match (x, y) {
+        (None, _) => short,
+        (_, None) => long,
+        (Some(x1), Some(y1)) => x1.cmp(y1),
+    }
+}
+
+impl<'a, T> Clone for Difference<'a, T> {
+    fn clone(&self) -> Difference<'a, T> {
+        Difference {
+            a: self.a.clone(),
+            b: self.b.clone(),
+        }
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T: Ord> Iterator for Difference<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<&'a T> {
+        loop {
+            match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
+                Less => return self.a.next(),
+                Equal => {
+                    self.a.next();
+                    self.b.next();
+                }
+                Greater => {
+                    self.b.next();
+                }
+            }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let a_len = self.a.len();
+        let b_len = self.b.len();
+        (a_len.saturating_sub(b_len), Some(a_len))
+    }
+}
+
+impl<'a, T> Clone for SymmetricDifference<'a, T> {
+    fn clone(&self) -> SymmetricDifference<'a, T> {
+        SymmetricDifference {
+            a: self.a.clone(),
+            b: self.b.clone(),
+        }
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<&'a T> {
+        loop {
+            match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
+                Less => return self.a.next(),
+                Equal => {
+                    self.a.next();
+                    self.b.next();
+                }
+                Greater => return self.b.next(),
+            }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.a.len() + self.b.len()))
+    }
+}
+
+impl<'a, T> Clone for Intersection<'a, T> {
+    fn clone(&self) -> Intersection<'a, T> {
+        Intersection {
+            a: self.a.clone(),
+            b: self.b.clone(),
+        }
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T: Ord> Iterator for Intersection<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<&'a T> {
+        loop {
+            let o_cmp = match (self.a.peek(), self.b.peek()) {
+                (None, _) => None,
+                (_, None) => None,
+                (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
+            };
+            match o_cmp {
+                None => return None,
+                Some(Less) => {
+                    self.a.next();
+                }
+                Some(Equal) => {
+                    self.b.next();
+                    return self.a.next();
+                }
+                Some(Greater) => {
+                    self.b.next();
+                }
+            }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(min(self.a.len(), self.b.len())))
+    }
+}
+
+impl<'a, T> Clone for Union<'a, T> {
+    fn clone(&self) -> Union<'a, T> {
+        Union {
+            a: self.a.clone(),
+            b: self.b.clone(),
+        }
+    }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T: Ord> Iterator for Union<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<&'a T> {
+        loop {
+            match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
+                Less => return self.a.next(),
+                Equal => {
+                    self.b.next();
+                    return self.a.next();
+                }
+                Greater => return self.b.next(),
+            }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let a_len = self.a.len();
+        let b_len = self.b.len();
+        (max(a_len, b_len), Some(a_len + b_len))
+    }
+}