src/libcollections/btree/map.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // This implementation is largely based on the high-level description and analysis of B-Trees
  12 // found in *Open Data Structures* (ODS). Although our implementation does not use any of
  13 // the source found in ODS, if one wishes to review the high-level design of this structure, it
  14 // can be freely downloaded at http://opendatastructures.org/. Its contents are as of this
  15 // writing (August 2014) freely licensed under the following Creative Commons Attribution
  16 // License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/).
  17
  18 use self::Entry::*;
  19
  20 use core::cmp::Ordering;
  21 use core::fmt::Debug;
  22 use core::hash::{Hash, Hasher};
  23 use core::iter::{Map, FromIterator};
  24 use core::ops::Index;
  25 use core::{fmt, mem, usize};
  26 use Bound::{self, Included, Excluded, Unbounded};
  27
  28 use borrow::Borrow;
  29 use vec_deque::VecDeque;
  30
  31 use self::Continuation::{Continue, Finished};
  32 use self::StackOp::*;
  33 use super::node::ForceResult::{Leaf, Internal};
  34 use super::node::TraversalItem::{self, Elem, Edge};
  35 use super::node::{Traversal, MutTraversal, MoveTraversal};
  36 use super::node::{self, Node, Found, GoDown};
  37
  38 /// A map based on a B-Tree.
  39 ///
  40 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
  41 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
  42 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
  43 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
  44 /// is done is *very* inefficient for modern computer architectures. In particular, every element
  45 /// is stored in its own individually heap-allocated node. This means that every single insertion
  46 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
  47 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
  48 /// the BST strategy.
  49 ///
  50 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
  51 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
  52 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
  53 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
  54 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
  55 /// the node using binary search. As a compromise, one could also perform a linear search
  56 /// that initially only checks every i<sup>th</sup> element for some choice of i.
  57 ///
  58 /// Currently, our implementation simply performs naive linear search. This provides excellent
  59 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
  60 /// would like to further explore choosing the optimal search strategy based on the choice of B,
  61 /// and possibly other factors. Using linear search, searching for a random element is expected
  62 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
  63 /// however, performance is excellent.
  64 ///
  65 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
  66 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
  67 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
  68 #[derive(Clone)]
  69 #[stable(feature = "rust1", since = "1.0.0")]
  70 pub struct BTreeMap<K, V> {
  71     root: Node<K, V>,
  72     length: usize,
  73     depth: usize,
  74     b: usize,
  75 }
  76
  77 /// An abstract base over-which all other BTree iterators are built.
  78 #[derive(Clone)]
  79 struct AbsIter<T> {
  80     traversals: VecDeque<T>,
  81     size: usize,
  82 }
  83
  84 /// An iterator over a BTreeMap's entries.
  85 #[stable(feature = "rust1", since = "1.0.0")]
  86 pub struct Iter<'a, K: 'a, V: 'a> {
  87     inner: AbsIter<Traversal<'a, K, V>>,
  88 }
  89
  90 /// A mutable iterator over a BTreeMap's entries.
  91 #[stable(feature = "rust1", since = "1.0.0")]
  92 pub struct IterMut<'a, K: 'a, V: 'a> {
  93     inner: AbsIter<MutTraversal<'a, K, V>>,
  94 }
  95
  96 /// An owning iterator over a BTreeMap's entries.
  97 #[stable(feature = "rust1", since = "1.0.0")]
  98 pub struct IntoIter<K, V> {
  99     inner: AbsIter<MoveTraversal<K, V>>,
 100 }
 101
 102 /// An iterator over a BTreeMap's keys.
 103 #[stable(feature = "rust1", since = "1.0.0")]
 104 pub struct Keys<'a, K: 'a, V: 'a> {
 105     inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>,
 106 }
 107
 108 /// An iterator over a BTreeMap's values.
 109 #[stable(feature = "rust1", since = "1.0.0")]
 110 pub struct Values<'a, K: 'a, V: 'a> {
 111     inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>,
 112 }
 113
 114 /// An iterator over a sub-range of BTreeMap's entries.
 115 pub struct Range<'a, K: 'a, V: 'a> {
 116     inner: AbsIter<Traversal<'a, K, V>>,
 117 }
 118
 119 /// A mutable iterator over a sub-range of BTreeMap's entries.
 120 pub struct RangeMut<'a, K: 'a, V: 'a> {
 121     inner: AbsIter<MutTraversal<'a, K, V>>,
 122 }
 123
 124 /// A view into a single entry in a map, which may either be vacant or occupied.
 125 #[stable(feature = "rust1", since = "1.0.0")]
 126 pub enum Entry<'a, K: 'a, V: 'a> {
 127     /// A vacant Entry
 128     #[stable(feature = "rust1", since = "1.0.0")]
 129     Vacant(VacantEntry<'a, K, V>),
 130
 131     /// An occupied Entry
 132     #[stable(feature = "rust1", since = "1.0.0")]
 133     Occupied(OccupiedEntry<'a, K, V>),
 134 }
 135
 136 /// A vacant Entry.
 137 #[stable(feature = "rust1", since = "1.0.0")]
 138 pub struct VacantEntry<'a, K: 'a, V: 'a> {
 139     key: K,
 140     stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>,
 141 }
 142
 143 /// An occupied Entry.
 144 #[stable(feature = "rust1", since = "1.0.0")]
 145 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
 146     stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>,
 147 }
 148
 149 impl<K: Ord, V> BTreeMap<K, V> {
 150     /// Makes a new empty BTreeMap with a reasonable choice for B.
 151     #[stable(feature = "rust1", since = "1.0.0")]
 152     #[allow(deprecated)]
 153     pub fn new() -> BTreeMap<K, V> {
 154         BTreeMap {
 155             length: 0,
 156             depth: 1,
 157             root: Node::make_leaf_root(6),
 158             // FIXME(Gankro): Tune this as a function of size_of<K/V>?
 159             b: 6,
 160         }
 161
 162     }
 163
 164     /// Clears the map, removing all values.
 165     ///
 166     /// # Examples
 167     ///
 168     /// ```
 169     /// use std::collections::BTreeMap;
 170     ///
 171     /// let mut a = BTreeMap::new();
 172     /// a.insert(1, "a");
 173     /// a.clear();
 174     /// assert!(a.is_empty());
 175     /// ```
 176     #[stable(feature = "rust1", since = "1.0.0")]
 177     pub fn clear(&mut self) {
 178         // avoid recursive destructors by manually traversing the tree
 179         for _ in mem::replace(self, BTreeMap::new()) {}
 180     }
 181
 182     // Searching in a B-Tree is pretty straightforward.
 183     //
 184     // Start at the root. Try to find the key in the current node. If we find it, return it.
 185     // If it's not in there, follow the edge *before* the smallest key larger than
 186     // the search key. If no such key exists (they're *all* smaller), then just take the last
 187     // edge in the node. If we're in a leaf and we don't find our key, then it's not
 188     // in the tree.
 189
 190     /// Returns a reference to the value corresponding to the key.
 191     ///
 192     /// The key may be any borrowed form of the map's key type, but the ordering
 193     /// on the borrowed form *must* match the ordering on the key type.
 194     ///
 195     /// # Examples
 196     ///
 197     /// ```
 198     /// use std::collections::BTreeMap;
 199     ///
 200     /// let mut map = BTreeMap::new();
 201     /// map.insert(1, "a");
 202     /// assert_eq!(map.get(&1), Some(&"a"));
 203     /// assert_eq!(map.get(&2), None);
 204     /// ```
 205     #[stable(feature = "rust1", since = "1.0.0")]
 206     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
 207         where K: Borrow<Q>,
 208               Q: Ord
 209     {
 210         let mut cur_node = &self.root;
 211         loop {
 212             match Node::search(cur_node, key) {
 213                 Found(handle) => return Some(handle.into_kv().1),
 214                 GoDown(handle) => {
 215                     match handle.force() {
 216                         Leaf(_) => return None,
 217                         Internal(internal_handle) => {
 218                             cur_node = internal_handle.into_edge();
 219                             continue;
 220                         }
 221                     }
 222                 }
 223             }
 224         }
 225     }
 226
 227     /// Returns true if the map contains a value for the specified key.
 228     ///
 229     /// The key may be any borrowed form of the map's key type, but the ordering
 230     /// on the borrowed form *must* match the ordering on the key type.
 231     ///
 232     /// # Examples
 233     ///
 234     /// ```
 235     /// use std::collections::BTreeMap;
 236     ///
 237     /// let mut map = BTreeMap::new();
 238     /// map.insert(1, "a");
 239     /// assert_eq!(map.contains_key(&1), true);
 240     /// assert_eq!(map.contains_key(&2), false);
 241     /// ```
 242     #[stable(feature = "rust1", since = "1.0.0")]
 243     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
 244         where K: Borrow<Q>,
 245               Q: Ord
 246     {
 247         self.get(key).is_some()
 248     }
 249
 250     /// Returns a mutable reference to the value corresponding to the key.
 251     ///
 252     /// The key may be any borrowed form of the map's key type, but the ordering
 253     /// on the borrowed form *must* match the ordering on the key type.
 254     ///
 255     /// # Examples
 256     ///
 257     /// ```
 258     /// use std::collections::BTreeMap;
 259     ///
 260     /// let mut map = BTreeMap::new();
 261     /// map.insert(1, "a");
 262     /// if let Some(x) = map.get_mut(&1) {
 263     ///     *x = "b";
 264     /// }
 265     /// assert_eq!(map[&1], "b");
 266     /// ```
 267     // See `get` for implementation notes, this is basically a copy-paste with mut's added
 268     #[stable(feature = "rust1", since = "1.0.0")]
 269     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
 270         where K: Borrow<Q>,
 271               Q: Ord
 272     {
 273         // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
 274         let mut temp_node = &mut self.root;
 275         loop {
 276             let cur_node = temp_node;
 277             match Node::search(cur_node, key) {
 278                 Found(handle) => return Some(handle.into_kv_mut().1),
 279                 GoDown(handle) => {
 280                     match handle.force() {
 281                         Leaf(_) => return None,
 282                         Internal(internal_handle) => {
 283                             temp_node = internal_handle.into_edge_mut();
 284                             continue;
 285                         }
 286                     }
 287                 }
 288             }
 289         }
 290     }
 291
 292     // Insertion in a B-Tree is a bit complicated.
 293     //
 294     // First we do the same kind of search described in `find`. But we need to maintain a stack of
 295     // all the nodes/edges in our search path. If we find a match for the key we're trying to
 296     // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
 297     // we attempt to insert our key-value pair at the same location we would want to follow another
 298     // edge.
 299     //
 300     // If the node has room, then this is done in the obvious way by shifting elements. However,
 301     // if the node itself is full, we split node into two, and give its median key-value
 302     // pair to its parent to insert the new node with. Of course, the parent may also be
 303     // full, and insertion can propagate until we reach the root. If we reach the root, and
 304     // it is *also* full, then we split the root and place the two nodes under a newly made root.
 305     //
 306     // Note that we subtly deviate from Open Data Structures in our implementation of split.
 307     // ODS describes inserting into the node *regardless* of its capacity, and then
 308     // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
 309     // Instead, we split beforehand, and then insert the key-value pair into the appropriate
 310     // result node. This has two consequences:
 311     //
 312     // 1) While ODS produces a left node of size B-1, and a right node of size B,
 313     // we may potentially reverse this. However, this shouldn't effect the analysis.
 314     //
 315     // 2) While ODS may potentially return the pair we *just* inserted after
 316     // the split, we will never do this. Again, this shouldn't effect the analysis.
 317
 318     /// Inserts a key-value pair into the map.
 319     ///
 320     /// If the map did not have this key present, `None` is returned.
 321     ///
 322     /// If the map did have this key present, the key is not updated, the
 323     /// value is updated and the old value is returned.
 324     /// See the [module-level documentation] for more.
 325     ///
 326     /// [module-level documentation]: index.html#insert-and-complex-keys
 327     ///
 328     /// # Examples
 329     ///
 330     /// ```
 331     /// use std::collections::BTreeMap;
 332     ///
 333     /// let mut map = BTreeMap::new();
 334     /// assert_eq!(map.insert(37, "a"), None);
 335     /// assert_eq!(map.is_empty(), false);
 336     ///
 337     /// map.insert(37, "b");
 338     /// assert_eq!(map.insert(37, "c"), Some("b"));
 339     /// assert_eq!(map[&37], "c");
 340     /// ```
 341     #[stable(feature = "rust1", since = "1.0.0")]
 342     pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
 343         // This is a stack of rawptrs to nodes paired with indices, respectively
 344         // representing the nodes and edges of our search path. We have to store rawptrs
 345         // because as far as Rust is concerned, we can mutate aliased data with such a
 346         // stack. It is of course correct, but what it doesn't know is that we will only
 347         // be popping and using these ptrs one at a time in child-to-parent order. The alternative
 348         // to doing this is to take the Nodes from their parents. This actually makes
 349         // borrowck *really* happy and everything is pretty smooth. However, this creates
 350         // *tons* of pointless writes, and requires us to always walk all the way back to
 351         // the root after an insertion, even if we only needed to change a leaf. Therefore,
 352         // we accept this potential unsafety and complexity in the name of performance.
 353         //
 354         // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
 355         // by the stack module. All it can do is immutably read nodes, and ask the search stack
 356         // to proceed down some edge by index. This makes the search logic we'll be reusing in a
 357         // few different methods much neater, and of course drastically improves safety.
 358         let mut stack = stack::PartialSearchStack::new(self);
 359
 360         loop {
 361             let result = stack.with(move |pusher, node| {
 362                 // Same basic logic as found in `find`, but with PartialSearchStack mediating the
 363                 // actual nodes for us
 364                 match Node::search(node, &key) {
 365                     Found(mut handle) => {
 366                         // Perfect match, swap the values and return the old one
 367                         mem::swap(handle.val_mut(), &mut value);
 368                         Finished(Some(value))
 369                     }
 370                     GoDown(handle) => {
 371                         // We need to keep searching, try to get the search stack
 372                         // to go down further
 373                         match handle.force() {
 374                             Leaf(leaf_handle) => {
 375                                 // We've reached a leaf, perform the insertion here
 376                                 pusher.seal(leaf_handle).insert(key, value);
 377                                 Finished(None)
 378                             }
 379                             Internal(internal_handle) => {
 380                                 // We've found the subtree to insert this key/value pair in,
 381                                 // keep searching
 382                                 Continue((pusher.push(internal_handle), key, value))
 383                             }
 384                         }
 385                     }
 386                 }
 387             });
 388             match result {
 389                 Finished(ret) => return ret,
 390                 Continue((new_stack, renewed_key, renewed_val)) => {
 391                     stack = new_stack;
 392                     key = renewed_key;
 393                     value = renewed_val;
 394                 }
 395             }
 396         }
 397     }
 398
 399     // Deletion is the most complicated operation for a B-Tree.
 400     //
 401     // First we do the same kind of search described in
 402     // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
 403     // If we don't find the key, then we just return `None` and do nothing. If we do find the
 404     // key, we perform two operations: remove the item, and then possibly handle underflow.
 405     //
 406     // # removing the item
 407     //      If the node is a leaf, we just remove the item, and shift
 408     //      any items after it back to fill the hole.
 409     //
 410     //      If the node is an internal node, we *swap* the item with the smallest item in
 411     //      in its right subtree (which must reside in a leaf), and then revert to the leaf
 412     //      case
 413     //
 414     // # handling underflow
 415     //      After removing an item, there may be too few items in the node. We want nodes
 416     //      to be mostly full for efficiency, although we make an exception for the root, which
 417     //      may have as few as one item. If this is the case, we may first try to steal
 418     //      an item from our left or right neighbour.
 419     //
 420     //      To steal from the left (right) neighbour,
 421     //      we take the largest (smallest) item and child from it. We then swap the taken item
 422     //      with the item in their mutual parent that separates them, and then insert the
 423     //      parent's item and the taken child into the first (last) index of the underflowed node.
 424     //
 425     //      However, stealing has the possibility of underflowing our neighbour. If this is the
 426     //      case, we instead *merge* with our neighbour. This of course reduces the number of
 427     //      children in the parent. Therefore, we also steal the item that separates the now
 428     //      merged nodes, and insert it into the merged node.
 429     //
 430     //      Merging may cause the parent to underflow. If this is the case, then we must repeat
 431     //      the underflow handling process on the parent. If merging merges the last two children
 432     //      of the root, then we replace the root with the merged node.
 433
 434     /// Removes a key from the map, returning the value at the key if the key
 435     /// was previously in the map.
 436     ///
 437     /// The key may be any borrowed form of the map's key type, but the ordering
 438     /// on the borrowed form *must* match the ordering on the key type.
 439     ///
 440     /// # Examples
 441     ///
 442     /// ```
 443     /// use std::collections::BTreeMap;
 444     ///
 445     /// let mut map = BTreeMap::new();
 446     /// map.insert(1, "a");
 447     /// assert_eq!(map.remove(&1), Some("a"));
 448     /// assert_eq!(map.remove(&1), None);
 449     /// ```
 450     #[stable(feature = "rust1", since = "1.0.0")]
 451     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
 452         where K: Borrow<Q>,
 453               Q: Ord
 454     {
 455         // See `swap` for a more thorough description of the stuff going on in here
 456         let mut stack = stack::PartialSearchStack::new(self);
 457         loop {
 458             let result = stack.with(move |pusher, node| {
 459                 match Node::search(node, key) {
 460                     Found(handle) => {
 461                         // Perfect match. Terminate the stack here, and remove the entry
 462                         Finished(Some(pusher.seal(handle).remove()))
 463                     }
 464                     GoDown(handle) => {
 465                         // We need to keep searching, try to go down the next edge
 466                         match handle.force() {
 467                             // We're at a leaf; the key isn't in here
 468                             Leaf(_) => Finished(None),
 469                             Internal(internal_handle) => Continue(pusher.push(internal_handle)),
 470                         }
 471                     }
 472                 }
 473             });
 474             match result {
 475                 Finished(ret) => return ret.map(|(_, v)| v),
 476                 Continue(new_stack) => stack = new_stack,
 477             }
 478         }
 479     }
 480 }
 481
 482 #[stable(feature = "rust1", since = "1.0.0")]
 483 impl<K, V> IntoIterator for BTreeMap<K, V> {
 484     type Item = (K, V);
 485     type IntoIter = IntoIter<K, V>;
 486
 487     /// Gets an owning iterator over the entries of the map.
 488     ///
 489     /// # Examples
 490     ///
 491     /// ```
 492     /// use std::collections::BTreeMap;
 493     ///
 494     /// let mut map = BTreeMap::new();
 495     /// map.insert(1, "a");
 496     /// map.insert(2, "b");
 497     /// map.insert(3, "c");
 498     ///
 499     /// for (key, value) in map.into_iter() {
 500     ///     println!("{}: {}", key, value);
 501     /// }
 502     /// ```
 503     fn into_iter(self) -> IntoIter<K, V> {
 504         let len = self.len();
 505         let mut lca = VecDeque::new();
 506         lca.push_back(Traverse::traverse(self.root));
 507         IntoIter {
 508             inner: AbsIter {
 509                 traversals: lca,
 510                 size: len,
 511             },
 512         }
 513     }
 514 }
 515
 516 #[stable(feature = "rust1", since = "1.0.0")]
 517 impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
 518     type Item = (&'a K, &'a V);
 519     type IntoIter = Iter<'a, K, V>;
 520
 521     fn into_iter(self) -> Iter<'a, K, V> {
 522         self.iter()
 523     }
 524 }
 525
 526 #[stable(feature = "rust1", since = "1.0.0")]
 527 impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
 528     type Item = (&'a K, &'a mut V);
 529     type IntoIter = IterMut<'a, K, V>;
 530
 531     fn into_iter(mut self) -> IterMut<'a, K, V> {
 532         self.iter_mut()
 533     }
 534 }
 535
 536 /// A helper enum useful for deciding whether to continue a loop since we can't
 537 /// return from a closure
 538 enum Continuation<A, B> {
 539     Continue(A),
 540     Finished(B),
 541 }
 542
 543 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
 544 /// to nodes. By using this module much better safety guarantees can be made, and more search
 545 /// boilerplate gets cut out.
 546 mod stack {
 547     use core::marker;
 548     use core::mem;
 549     use core::ops::{Deref, DerefMut};
 550     use super::BTreeMap;
 551     use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
 552     use super::super::node::handle;
 553     use vec::Vec;
 554
 555     struct InvariantLifetime<'id>(marker::PhantomData<::core::cell::Cell<&'id ()>>);
 556
 557     impl<'id> InvariantLifetime<'id> {
 558         fn new() -> InvariantLifetime<'id> {
 559             InvariantLifetime(marker::PhantomData)
 560         }
 561     }
 562
 563     /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
 564     /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
 565     /// with the exact requested lifetime can be used. This is in contrast to normal references,
 566     /// where `&'static` can be used in any function expecting any lifetime reference.
 567     pub struct IdRef<'id, T: 'id> {
 568         inner: &'id mut T,
 569         _marker: InvariantLifetime<'id>,
 570     }
 571
 572     impl<'id, T> Deref for IdRef<'id, T> {
 573         type Target = T;
 574
 575         fn deref(&self) -> &T {
 576             &*self.inner
 577         }
 578     }
 579
 580     impl<'id, T> DerefMut for IdRef<'id, T> {
 581         fn deref_mut(&mut self) -> &mut T {
 582             &mut *self.inner
 583         }
 584     }
 585
 586     type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
 587     type Stack<K, V> = Vec<StackItem<K, V>>;
 588
 589     /// A `PartialSearchStack` handles the construction of a search stack.
 590     pub struct PartialSearchStack<'a, K: 'a, V: 'a> {
 591         map: &'a mut BTreeMap<K, V>,
 592         stack: Stack<K, V>,
 593         next: *mut Node<K, V>,
 594     }
 595
 596     /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
 597     /// methods depending on the type of what the path points to for removing an element, inserting
 598     /// a new element, and manipulating to element at the top of the stack.
 599     pub struct SearchStack<'a, K: 'a, V: 'a, Type, NodeType> {
 600         map: &'a mut BTreeMap<K, V>,
 601         stack: Stack<K, V>,
 602         top: node::Handle<*mut Node<K, V>, Type, NodeType>,
 603     }
 604
 605     /// A `PartialSearchStack` that doesn't hold a reference to the next node, and is just
 606     /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
 607     /// for more details.
 608     pub struct Pusher<'id, 'a, K: 'a, V: 'a> {
 609         map: &'a mut BTreeMap<K, V>,
 610         stack: Stack<K, V>,
 611         _marker: InvariantLifetime<'id>,
 612     }
 613
 614     impl<'a, K, V> PartialSearchStack<'a, K, V> {
 615         /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
 616         /// root of the tree.
 617         pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
 618             let depth = map.depth;
 619
 620             PartialSearchStack {
 621                 next: &mut map.root as *mut _,
 622                 map: map,
 623                 stack: Vec::with_capacity(depth),
 624             }
 625         }
 626
 627         /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
 628         /// to interact with, search, and finally push the `Node` onto the stack. The passed in
 629         /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
 630         /// ensures that only `Handle`s from the correct `Node` can be pushed.
 631         ///
 632         /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
 633         /// handles with the same `'id`. The closure could only get references with that lifetime
 634         /// through its arguments or through some other `IdRef` that it has lying around. However,
 635         /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
 636         /// parameter, it would need to have precisely the correct lifetime, which would mean that
 637         /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
 638         /// specific lifetime instead of the one that `with` chooses to give it.
 639         ///
 640         /// See also Haskell's `ST` monad, which uses a similar trick.
 641         pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
 642                                           IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
 643             let pusher = Pusher {
 644                 map: self.map,
 645                 stack: self.stack,
 646                 _marker: InvariantLifetime::new(),
 647             };
 648             let node = IdRef {
 649                 inner: unsafe { &mut *self.next },
 650                 _marker: InvariantLifetime::new(),
 651             };
 652
 653             closure(pusher, node)
 654         }
 655     }
 656
 657     impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
 658         /// Pushes the requested child of the stack's current top on top of the stack. If the child
 659         /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
 660         /// yielded.
 661         pub fn push(mut self,
 662                     mut edge: node::Handle<IdRef<'id, Node<K, V>>, handle::Edge, handle::Internal>)
 663                     -> PartialSearchStack<'a, K, V> {
 664             self.stack.push(edge.as_raw());
 665             PartialSearchStack {
 666                 map: self.map,
 667                 stack: self.stack,
 668                 next: edge.edge_mut() as *mut _,
 669             }
 670         }
 671
 672         /// Converts the PartialSearchStack into a SearchStack.
 673         pub fn seal<Type, NodeType>(self,
 674                                     mut handle: node::Handle<IdRef<'id, Node<K, V>>,
 675                                                              Type,
 676                                                              NodeType>)
 677                                     -> SearchStack<'a, K, V, Type, NodeType> {
 678             SearchStack {
 679                 map: self.map,
 680                 stack: self.stack,
 681                 top: handle.as_raw(),
 682             }
 683         }
 684     }
 685
 686     impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
 687         /// Gets a reference to the value the stack points to.
 688         pub fn peek(&self) -> &V {
 689             unsafe { self.top.from_raw().into_kv().1 }
 690         }
 691
 692         /// Gets a mutable reference to the value the stack points to.
 693         pub fn peek_mut(&mut self) -> &mut V {
 694             unsafe { self.top.from_raw_mut().into_kv_mut().1 }
 695         }
 696
 697         /// Converts the stack into a mutable reference to the value it points to, with a lifetime
 698         /// tied to the original tree.
 699         pub fn into_top(mut self) -> &'a mut V {
 700             unsafe { &mut *(self.top.from_raw_mut().val_mut() as *mut V) }
 701         }
 702     }
 703
 704     impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
 705         /// Removes the key and value in the top element of the stack, then handles underflows as
 706         /// described in BTree's pop function.
 707         fn remove_leaf(mut self) -> (K, V) {
 708             self.map.length -= 1;
 709
 710             // Remove the key-value pair from the leaf that this search stack points to.
 711             // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
 712             // to avoid ownership issues.
 713             let (key_val, mut underflow) = unsafe {
 714                 let key_val = self.top.from_raw_mut().remove_as_leaf();
 715                 let underflow = self.top.from_raw().node().is_underfull();
 716                 (key_val, underflow)
 717             };
 718
 719             loop {
 720                 match self.stack.pop() {
 721                     None => {
 722                         // We've reached the root, so no matter what, we're done. We manually
 723                         // access the root via the tree itself to avoid creating any dangling
 724                         // pointers.
 725                         if self.map.root.is_empty() && !self.map.root.is_leaf() {
 726                             // We've emptied out the root, so make its only child the new root.
 727                             // If it's a leaf, we just let it become empty.
 728                             self.map.depth -= 1;
 729                             self.map.root.hoist_lone_child();
 730                         }
 731                         return key_val;
 732                     }
 733                     Some(mut handle) => {
 734                         if underflow {
 735                             // Underflow! Handle it!
 736                             unsafe {
 737                                 handle.from_raw_mut().handle_underflow();
 738                                 underflow = handle.from_raw().node().is_underfull();
 739                             }
 740                         } else {
 741                             // All done!
 742                             return key_val;
 743                         }
 744                     }
 745                 }
 746             }
 747         }
 748     }
 749
 750     impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
 751         /// Removes the key and value in the top element of the stack, then handles underflows as
 752         /// described in BTree's pop function.
 753         pub fn remove(self) -> (K, V) {
 754             // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
 755             // in a BTree. Note that this may put the tree in an inconsistent state (further
 756             // described in into_leaf's comments), but this is immediately fixed by the
 757             // removing the value we want to remove
 758             self.into_leaf().remove_leaf()
 759         }
 760
 761         /// Subroutine for removal. Takes a search stack for a key that might terminate at an
 762         /// internal node, and mutates the tree and search stack to *make* it a search stack
 763         /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
 764         /// leaves the tree in an inconsistent state that must be repaired by the caller by
 765         /// removing the entry in question. Specifically the key-value pair and its successor will
 766         /// become swapped.
 767         fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
 768             unsafe {
 769                 let mut top_raw = self.top;
 770                 let mut top = top_raw.from_raw_mut();
 771
 772                 let key_ptr = top.key_mut() as *mut _;
 773                 let val_ptr = top.val_mut() as *mut _;
 774
 775                 // Try to go into the right subtree of the found key to find its successor
 776                 match top.force() {
 777                     Leaf(mut leaf_handle) => {
 778                         // We're a proper leaf stack, nothing to do
 779                         return SearchStack {
 780                             map: self.map,
 781                             stack: self.stack,
 782                             top: leaf_handle.as_raw(),
 783                         };
 784                     }
 785                     Internal(mut internal_handle) => {
 786                         let mut right_handle = internal_handle.right_edge();
 787
 788                         // We're not a proper leaf stack, let's get to work.
 789                         self.stack.push(right_handle.as_raw());
 790
 791                         let mut temp_node = right_handle.edge_mut();
 792                         loop {
 793                             // Walk into the smallest subtree of this node
 794                             let node = temp_node;
 795
 796                             match node.kv_handle(0).force() {
 797                                 Leaf(mut handle) => {
 798                                     // This node is a leaf, do the swap and return
 799                                     mem::swap(handle.key_mut(), &mut *key_ptr);
 800                                     mem::swap(handle.val_mut(), &mut *val_ptr);
 801                                     return SearchStack {
 802                                         map: self.map,
 803                                         stack: self.stack,
 804                                         top: handle.as_raw(),
 805                                     };
 806                                 }
 807                                 Internal(kv_handle) => {
 808                                     // This node is internal, go deeper
 809                                     let mut handle = kv_handle.into_left_edge();
 810                                     self.stack.push(handle.as_raw());
 811                                     temp_node = handle.into_edge_mut();
 812                                 }
 813                             }
 814                         }
 815                     }
 816                 }
 817             }
 818         }
 819     }
 820
 821     impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
 822         /// Inserts the key and value into the top element in the stack, and if that node has to
 823         /// split recursively inserts the split contents into the next element stack until
 824         /// splits stop.
 825         ///
 826         /// Assumes that the stack represents a search path from the root to a leaf.
 827         ///
 828         /// An &mut V is returned to the inserted value, for callers that want a reference to this.
 829         pub fn insert(mut self, key: K, val: V) -> &'a mut V {
 830             unsafe {
 831                 self.map.length += 1;
 832
 833                 // Insert the key and value into the leaf at the top of the stack
 834                 let (mut insertion, inserted_ptr) = self.top
 835                                                         .from_raw_mut()
 836                                                         .insert_as_leaf(key, val);
 837
 838                 loop {
 839                     match insertion {
 840                         Fit => {
 841                             // The last insertion went off without a hitch, no splits! We can stop
 842                             // inserting now.
 843                             return &mut *inserted_ptr;
 844                         }
 845                         Split(key, val, right) => {
 846                             match self.stack.pop() {
 847                                 // The last insertion triggered a split, so get the next element on
 848                                 // the stack to recursively insert the split node into.
 849                                 None => {
 850                                     // The stack was empty; we've split the root, and need to make a
 851                                     // a new one. This is done in-place because we can't move the
 852                                     // root out of a reference to the tree.
 853                                     Node::make_internal_root(&mut self.map.root,
 854                                                              self.map.b,
 855                                                              key,
 856                                                              val,
 857                                                              right);
 858
 859                                     self.map.depth += 1;
 860                                     return &mut *inserted_ptr;
 861                                 }
 862                                 Some(mut handle) => {
 863                                     // The stack wasn't empty, do the insertion and recurse
 864                                     insertion = handle.from_raw_mut()
 865                                                       .insert_as_internal(key, val, right);
 866                                     continue;
 867                                 }
 868                             }
 869                         }
 870                     }
 871                 }
 872             }
 873         }
 874     }
 875 }
 876
 877 #[stable(feature = "rust1", since = "1.0.0")]
 878 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
 879     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
 880         let mut map = BTreeMap::new();
 881         map.extend(iter);
 882         map
 883     }
 884 }
 885
 886 #[stable(feature = "rust1", since = "1.0.0")]
 887 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
 888     #[inline]
 889     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
 890         for (k, v) in iter {
 891             self.insert(k, v);
 892         }
 893     }
 894 }
 895
 896 #[stable(feature = "extend_ref", since = "1.2.0")]
 897 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
 898     fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
 899         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
 900     }
 901 }
 902
 903 #[stable(feature = "rust1", since = "1.0.0")]
 904 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
 905     fn hash<H: Hasher>(&self, state: &mut H) {
 906         for elt in self {
 907             elt.hash(state);
 908         }
 909     }
 910 }
 911
 912 #[stable(feature = "rust1", since = "1.0.0")]
 913 impl<K: Ord, V> Default for BTreeMap<K, V> {
 914     fn default() -> BTreeMap<K, V> {
 915         BTreeMap::new()
 916     }
 917 }
 918
 919 #[stable(feature = "rust1", since = "1.0.0")]
 920 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
 921     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
 922         self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
 923     }
 924 }
 925
 926 #[stable(feature = "rust1", since = "1.0.0")]
 927 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
 928
 929 #[stable(feature = "rust1", since = "1.0.0")]
 930 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
 931     #[inline]
 932     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
 933         self.iter().partial_cmp(other.iter())
 934     }
 935 }
 936
 937 #[stable(feature = "rust1", since = "1.0.0")]
 938 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
 939     #[inline]
 940     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
 941         self.iter().cmp(other.iter())
 942     }
 943 }
 944
 945 #[stable(feature = "rust1", since = "1.0.0")]
 946 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
 947     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 948         f.debug_map().entries(self.iter()).finish()
 949     }
 950 }
 951
 952 #[stable(feature = "rust1", since = "1.0.0")]
 953 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
 954     where K: Borrow<Q>,
 955           Q: Ord
 956 {
 957     type Output = V;
 958
 959     #[inline]
 960     fn index(&self, key: &Q) -> &V {
 961         self.get(key).expect("no entry found for key")
 962     }
 963 }
 964
 965 /// Genericizes over how to get the correct type of iterator from the correct type
 966 /// of Node ownership.
 967 trait Traverse<N> {
 968     fn traverse(node: N) -> Self;
 969 }
 970
 971 impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
 972     fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
 973         node.iter()
 974     }
 975 }
 976
 977 impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
 978     fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
 979         node.iter_mut()
 980     }
 981 }
 982
 983 impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
 984     fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
 985         node.into_iter()
 986     }
 987 }
 988
 989 /// Represents an operation to perform inside the following iterator methods.
 990 /// This is necessary to use in `next` because we want to modify `self.traversals` inside
 991 /// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
 992 /// what we want to do, and do it after the match.
 993 enum StackOp<T> {
 994     Push(T),
 995     Pop,
 996 }
 997 impl<K, V, E, T> Iterator for AbsIter<T>
 998     where T: DoubleEndedIterator<Item = TraversalItem<K, V, E>> + Traverse<E>
 999 {
1000     type Item = (K, V);
1001
1002     // Our iterator represents a queue of all ancestors of elements we have
1003     // yet to yield, from smallest to largest.  Note that the design of these
1004     // iterators permits an *arbitrary* initial pair of min and max, making
1005     // these arbitrary sub-range iterators.
1006     fn next(&mut self) -> Option<(K, V)> {
1007         loop {
1008             // We want the smallest element, so try to get the back of the queue
1009             let op = match self.traversals.back_mut() {
1010                 None => return None,
1011                 // The queue wasn't empty, so continue along the node in its head
1012                 Some(iter) => {
1013                     match iter.next() {
1014                         // The head is empty, so Pop it off and continue the process
1015                         None => Pop,
1016                         // The head yielded an edge, so make that the new head
1017                         Some(Edge(next)) => Push(Traverse::traverse(next)),
1018                         // The head yielded an entry, so yield that
1019                         Some(Elem(kv)) => {
1020                             self.size -= 1;
1021                             return Some(kv);
1022                         }
1023                     }
1024                 }
1025             };
1026
1027             // Handle any operation as necessary, without a conflicting borrow of the queue
1028             match op {
1029                 Push(item) => {
1030                     self.traversals.push_back(item);
1031                 }
1032                 Pop => {
1033                     self.traversals.pop_back();
1034                 }
1035             }
1036         }
1037     }
1038
1039     fn size_hint(&self) -> (usize, Option<usize>) {
1040         (self.size, Some(self.size))
1041     }
1042 }
1043
1044 impl<K, V, E, T> DoubleEndedIterator for AbsIter<T>
1045     where T: DoubleEndedIterator<Item = TraversalItem<K, V, E>> + Traverse<E>
1046 {
1047     // next_back is totally symmetric to next
1048     #[inline]
1049     fn next_back(&mut self) -> Option<(K, V)> {
1050         loop {
1051             let op = match self.traversals.front_mut() {
1052                 None => return None,
1053                 Some(iter) => {
1054                     match iter.next_back() {
1055                         None => Pop,
1056                         Some(Edge(next)) => Push(Traverse::traverse(next)),
1057                         Some(Elem(kv)) => {
1058                             self.size -= 1;
1059                             return Some(kv);
1060                         }
1061                     }
1062                 }
1063             };
1064
1065             match op {
1066                 Push(item) => {
1067                     self.traversals.push_front(item);
1068                 }
1069                 Pop => {
1070                     self.traversals.pop_front();
1071                 }
1072             }
1073         }
1074     }
1075 }
1076
1077 impl<'a, K, V> Clone for Iter<'a, K, V> {
1078     fn clone(&self) -> Iter<'a, K, V> {
1079         Iter { inner: self.inner.clone() }
1080     }
1081 }
1082 #[stable(feature = "rust1", since = "1.0.0")]
1083 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1084     type Item = (&'a K, &'a V);
1085
1086     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1087         self.inner.next()
1088     }
1089     fn size_hint(&self) -> (usize, Option<usize>) {
1090         self.inner.size_hint()
1091     }
1092 }
1093 #[stable(feature = "rust1", since = "1.0.0")]
1094 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1095     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1096         self.inner.next_back()
1097     }
1098 }
1099 #[stable(feature = "rust1", since = "1.0.0")]
1100 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1101
1102 #[stable(feature = "rust1", since = "1.0.0")]
1103 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1104     type Item = (&'a K, &'a mut V);
1105
1106     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1107         self.inner.next()
1108     }
1109     fn size_hint(&self) -> (usize, Option<usize>) {
1110         self.inner.size_hint()
1111     }
1112 }
1113 #[stable(feature = "rust1", since = "1.0.0")]
1114 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1115     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1116         self.inner.next_back()
1117     }
1118 }
1119 #[stable(feature = "rust1", since = "1.0.0")]
1120 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1121
1122 #[stable(feature = "rust1", since = "1.0.0")]
1123 impl<K, V> Iterator for IntoIter<K, V> {
1124     type Item = (K, V);
1125
1126     fn next(&mut self) -> Option<(K, V)> {
1127         self.inner.next()
1128     }
1129     fn size_hint(&self) -> (usize, Option<usize>) {
1130         self.inner.size_hint()
1131     }
1132 }
1133 #[stable(feature = "rust1", since = "1.0.0")]
1134 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1135     fn next_back(&mut self) -> Option<(K, V)> {
1136         self.inner.next_back()
1137     }
1138 }
1139 #[stable(feature = "rust1", since = "1.0.0")]
1140 impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
1141
1142 impl<'a, K, V> Clone for Keys<'a, K, V> {
1143     fn clone(&self) -> Keys<'a, K, V> {
1144         Keys { inner: self.inner.clone() }
1145     }
1146 }
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1149     type Item = &'a K;
1150
1151     fn next(&mut self) -> Option<(&'a K)> {
1152         self.inner.next()
1153     }
1154     fn size_hint(&self) -> (usize, Option<usize>) {
1155         self.inner.size_hint()
1156     }
1157 }
1158 #[stable(feature = "rust1", since = "1.0.0")]
1159 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1160     fn next_back(&mut self) -> Option<(&'a K)> {
1161         self.inner.next_back()
1162     }
1163 }
1164 #[stable(feature = "rust1", since = "1.0.0")]
1165 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
1166
1167
1168 impl<'a, K, V> Clone for Values<'a, K, V> {
1169     fn clone(&self) -> Values<'a, K, V> {
1170         Values { inner: self.inner.clone() }
1171     }
1172 }
1173 #[stable(feature = "rust1", since = "1.0.0")]
1174 impl<'a, K, V> Iterator for Values<'a, K, V> {
1175     type Item = &'a V;
1176
1177     fn next(&mut self) -> Option<(&'a V)> {
1178         self.inner.next()
1179     }
1180     fn size_hint(&self) -> (usize, Option<usize>) {
1181         self.inner.size_hint()
1182     }
1183 }
1184 #[stable(feature = "rust1", since = "1.0.0")]
1185 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1186     fn next_back(&mut self) -> Option<(&'a V)> {
1187         self.inner.next_back()
1188     }
1189 }
1190 #[stable(feature = "rust1", since = "1.0.0")]
1191 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
1192
1193 impl<'a, K, V> Clone for Range<'a, K, V> {
1194     fn clone(&self) -> Range<'a, K, V> {
1195         Range { inner: self.inner.clone() }
1196     }
1197 }
1198 impl<'a, K, V> Iterator for Range<'a, K, V> {
1199     type Item = (&'a K, &'a V);
1200
1201     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1202         self.inner.next()
1203     }
1204 }
1205 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1206     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1207         self.inner.next_back()
1208     }
1209 }
1210
1211 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1212     type Item = (&'a K, &'a mut V);
1213
1214     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1215         self.inner.next()
1216     }
1217 }
1218 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1219     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1220         self.inner.next_back()
1221     }
1222 }
1223
1224 impl<'a, K: Ord, V> Entry<'a, K, V> {
1225     #[stable(feature = "rust1", since = "1.0.0")]
1226     /// Ensures a value is in the entry by inserting the default if empty, and returns
1227     /// a mutable reference to the value in the entry.
1228     pub fn or_insert(self, default: V) -> &'a mut V {
1229         match self {
1230             Occupied(entry) => entry.into_mut(),
1231             Vacant(entry) => entry.insert(default),
1232         }
1233     }
1234
1235     #[stable(feature = "rust1", since = "1.0.0")]
1236     /// Ensures a value is in the entry by inserting the result of the default function if empty,
1237     /// and returns a mutable reference to the value in the entry.
1238     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1239         match self {
1240             Occupied(entry) => entry.into_mut(),
1241             Vacant(entry) => entry.insert(default()),
1242         }
1243     }
1244 }
1245
1246 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1247     /// Sets the value of the entry with the VacantEntry's key,
1248     /// and returns a mutable reference to it.
1249     #[stable(feature = "rust1", since = "1.0.0")]
1250     pub fn insert(self, value: V) -> &'a mut V {
1251         self.stack.insert(self.key, value)
1252     }
1253 }
1254
1255 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1256     /// Gets a reference to the value in the entry.
1257     #[stable(feature = "rust1", since = "1.0.0")]
1258     pub fn get(&self) -> &V {
1259         self.stack.peek()
1260     }
1261
1262     /// Gets a mutable reference to the value in the entry.
1263     #[stable(feature = "rust1", since = "1.0.0")]
1264     pub fn get_mut(&mut self) -> &mut V {
1265         self.stack.peek_mut()
1266     }
1267
1268     /// Converts the entry into a mutable reference to its value.
1269     #[stable(feature = "rust1", since = "1.0.0")]
1270     pub fn into_mut(self) -> &'a mut V {
1271         self.stack.into_top()
1272     }
1273
1274     /// Sets the value of the entry with the OccupiedEntry's key,
1275     /// and returns the entry's old value.
1276     #[stable(feature = "rust1", since = "1.0.0")]
1277     pub fn insert(&mut self, mut value: V) -> V {
1278         mem::swap(self.stack.peek_mut(), &mut value);
1279         value
1280     }
1281
1282     /// Takes the value of the entry out of the map, and returns it.
1283     #[stable(feature = "rust1", since = "1.0.0")]
1284     pub fn remove(self) -> V {
1285         self.stack.remove().1
1286     }
1287 }
1288
1289 impl<K, V> BTreeMap<K, V> {
1290     /// Gets an iterator over the entries of the map.
1291     ///
1292     /// # Examples
1293     ///
1294     /// ```
1295     /// use std::collections::BTreeMap;
1296     ///
1297     /// let mut map = BTreeMap::new();
1298     /// map.insert(1, "a");
1299     /// map.insert(2, "b");
1300     /// map.insert(3, "c");
1301     ///
1302     /// for (key, value) in map.iter() {
1303     ///     println!("{}: {}", key, value);
1304     /// }
1305     ///
1306     /// let (first_key, first_value) = map.iter().next().unwrap();
1307     /// assert_eq!((*first_key, *first_value), (1, "a"));
1308     /// ```
1309     #[stable(feature = "rust1", since = "1.0.0")]
1310     pub fn iter(&self) -> Iter<K, V> {
1311         let len = self.len();
1312         // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
1313         let mut lca = VecDeque::new();
1314         lca.push_back(Traverse::traverse(&self.root));
1315         Iter {
1316             inner: AbsIter {
1317                 traversals: lca,
1318                 size: len,
1319             },
1320         }
1321     }
1322
1323     /// Gets a mutable iterator over the entries of the map.
1324     ///
1325     /// # Examples
1326     ///
1327     /// ```
1328     /// use std::collections::BTreeMap;
1329     ///
1330     /// let mut map = BTreeMap::new();
1331     /// map.insert("a", 1);
1332     /// map.insert("b", 2);
1333     /// map.insert("c", 3);
1334     ///
1335     /// // add 10 to the value if the key isn't "a"
1336     /// for (key, value) in map.iter_mut() {
1337     ///     if key != &"a" {
1338     ///         *value += 10;
1339     ///     }
1340     /// }
1341     /// ```
1342     #[stable(feature = "rust1", since = "1.0.0")]
1343     pub fn iter_mut(&mut self) -> IterMut<K, V> {
1344         let len = self.len();
1345         let mut lca = VecDeque::new();
1346         lca.push_back(Traverse::traverse(&mut self.root));
1347         IterMut {
1348             inner: AbsIter {
1349                 traversals: lca,
1350                 size: len,
1351             },
1352         }
1353     }
1354
1355     /// Gets an iterator over the keys of the map.
1356     ///
1357     /// # Examples
1358     ///
1359     /// ```
1360     /// use std::collections::BTreeMap;
1361     ///
1362     /// let mut a = BTreeMap::new();
1363     /// a.insert(1, "a");
1364     /// a.insert(2, "b");
1365     ///
1366     /// let keys: Vec<_> = a.keys().cloned().collect();
1367     /// assert_eq!(keys, [1, 2]);
1368     /// ```
1369     #[stable(feature = "rust1", since = "1.0.0")]
1370     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1371         fn first<A, B>((a, _): (A, B)) -> A {
1372             a
1373         }
1374         let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
1375
1376         Keys { inner: self.iter().map(first) }
1377     }
1378
1379     /// Gets an iterator over the values of the map.
1380     ///
1381     /// # Examples
1382     ///
1383     /// ```
1384     /// use std::collections::BTreeMap;
1385     ///
1386     /// let mut a = BTreeMap::new();
1387     /// a.insert(1, "a");
1388     /// a.insert(2, "b");
1389     ///
1390     /// let values: Vec<&str> = a.values().cloned().collect();
1391     /// assert_eq!(values, ["a", "b"]);
1392     /// ```
1393     #[stable(feature = "rust1", since = "1.0.0")]
1394     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1395         fn second<A, B>((_, b): (A, B)) -> B {
1396             b
1397         }
1398         let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
1399
1400         Values { inner: self.iter().map(second) }
1401     }
1402
1403     /// Returns the number of elements in the map.
1404     ///
1405     /// # Examples
1406     ///
1407     /// ```
1408     /// use std::collections::BTreeMap;
1409     ///
1410     /// let mut a = BTreeMap::new();
1411     /// assert_eq!(a.len(), 0);
1412     /// a.insert(1, "a");
1413     /// assert_eq!(a.len(), 1);
1414     /// ```
1415     #[stable(feature = "rust1", since = "1.0.0")]
1416     pub fn len(&self) -> usize {
1417         self.length
1418     }
1419
1420     /// Returns true if the map contains no elements.
1421     ///
1422     /// # Examples
1423     ///
1424     /// ```
1425     /// use std::collections::BTreeMap;
1426     ///
1427     /// let mut a = BTreeMap::new();
1428     /// assert!(a.is_empty());
1429     /// a.insert(1, "a");
1430     /// assert!(!a.is_empty());
1431     /// ```
1432     #[stable(feature = "rust1", since = "1.0.0")]
1433     pub fn is_empty(&self) -> bool {
1434         self.len() == 0
1435     }
1436 }
1437
1438 macro_rules! range_impl {
1439     ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident,
1440                                        $edges:ident, [$($mutability:ident)*]) => (
1441         {
1442             // A deque that encodes two search paths containing (left-to-right):
1443             // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
1444             // and a series of truncated-from-the-right iterators.
1445             let mut traversals = VecDeque::new();
1446             let (root, min, max) = ($root, $min, $max);
1447
1448             let mut leftmost = None;
1449             let mut rightmost = None;
1450
1451             match (&min, &max) {
1452                 (&Unbounded, &Unbounded) => {
1453                     traversals.push_back(Traverse::traverse(root))
1454                 }
1455                 (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => {
1456                     rightmost = Some(root);
1457                 }
1458                 (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => {
1459                     leftmost = Some(root);
1460                 }
1461                   (&Included(min_key), &Included(max_key))
1462                 | (&Included(min_key), &Excluded(max_key))
1463                 | (&Excluded(min_key), &Included(max_key))
1464                 | (&Excluded(min_key), &Excluded(max_key)) => {
1465                     // lca represents the Lowest Common Ancestor, above which we never
1466                     // walk, since everything else is outside the range to iterate.
1467                     //       ___________________
1468                     //      |__0_|_80_|_85_|_90_|  (root)
1469                     //      |    |    |    |    |
1470                     //           |
1471                     //           v
1472                     //  ___________________
1473                     // |__5_|_15_|_30_|_73_|
1474                     // |    |    |    |    |
1475                     //                |
1476                     //                v
1477                     //       ___________________
1478                     //      |_33_|_58_|_63_|_68_|  lca for the range [41, 65]
1479                     //      |    |\___|___/|    |  iterator at traversals[2]
1480                     //           |         |
1481                     //           |         v
1482                     //           v         rightmost
1483                     //           leftmost
1484                     let mut is_leaf = root.is_leaf();
1485                     let mut lca = root.$as_slices_internal();
1486                     loop {
1487                         let slice = lca.slice_from(min_key).slice_to(max_key);
1488                         if let [ref $($mutability)* edge] = slice.edges {
1489                             // Follow the only edge that leads the node that covers the range.
1490                             is_leaf = edge.is_leaf();
1491                             lca = edge.$as_slices_internal();
1492                         } else {
1493                             let mut iter = slice.$iter();
1494                             if is_leaf {
1495                                 leftmost = None;
1496                                 rightmost = None;
1497                             } else {
1498                                 // Only change the state of nodes with edges.
1499                                 leftmost = iter.next_edge_item();
1500                                 rightmost = iter.next_edge_item_back();
1501                             }
1502                             traversals.push_back(iter);
1503                             break;
1504                         }
1505                     }
1506                 }
1507             }
1508             // Keep narrowing the range by going down.
1509             //               ___________________
1510             //              |_38_|_43_|_48_|_53_|
1511             //              |    |____|____|____/ iterator at traversals[1]
1512             //                   |
1513             //                   v
1514             //  ___________________
1515             // |_39_|_40_|_41_|_42_|  (leaf, the last leftmost)
1516             //           \_________|  iterator at traversals[0]
1517             match min {
1518                 Included(key) | Excluded(key) =>
1519                     while let Some(left) = leftmost {
1520                         let is_leaf = left.is_leaf();
1521                         let mut iter = left.$as_slices_internal().slice_from(key).$iter();
1522                         leftmost = if is_leaf {
1523                             None
1524                         } else {
1525                             // Only change the state of nodes with edges.
1526                             iter.next_edge_item()
1527                         };
1528                         traversals.push_back(iter);
1529                     },
1530                 _ => {}
1531             }
1532             // If the leftmost iterator starts with an element, then it was an exact match.
1533             if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) {
1534                 // Drop this excluded element. `next_kv_item` has no effect when
1535                 // the next item is an edge.
1536                 leftmost_iter.next_kv_item();
1537             }
1538
1539             // The code for the right side is similar.
1540             match max {
1541                 Included(key) | Excluded(key) =>
1542                     while let Some(right) = rightmost {
1543                         let is_leaf = right.is_leaf();
1544                         let mut iter = right.$as_slices_internal().slice_to(key).$iter();
1545                         rightmost = if is_leaf {
1546                             None
1547                         } else {
1548                             iter.next_edge_item_back()
1549                         };
1550                         traversals.push_front(iter);
1551                     },
1552                 _ => {}
1553             }
1554             if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) {
1555                 rightmost_iter.next_kv_item_back();
1556             }
1557
1558             $Range {
1559                 inner: AbsIter {
1560                     traversals: traversals,
1561                     size: usize::MAX, // unused
1562                 }
1563             }
1564         }
1565     )
1566 }
1567
1568 impl<K: Ord, V> BTreeMap<K, V> {
1569     /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
1570     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1571     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1572     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1573     ///
1574     /// # Examples
1575     ///
1576     /// ```
1577     /// #![feature(btree_range, collections_bound)]
1578     ///
1579     /// use std::collections::BTreeMap;
1580     /// use std::collections::Bound::{Included, Unbounded};
1581     ///
1582     /// let mut map = BTreeMap::new();
1583     /// map.insert(3, "a");
1584     /// map.insert(5, "b");
1585     /// map.insert(8, "c");
1586     /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
1587     ///     println!("{}: {}", key, value);
1588     /// }
1589     /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
1590     /// ```
1591     #[unstable(feature = "btree_range",
1592                reason = "matches collection reform specification, waiting for dust to settle",
1593                issue = "27787")]
1594     pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
1595                                                        min: Bound<&Min>,
1596                                                        max: Bound<&Max>)
1597                                                        -> Range<K, V>
1598         where K: Borrow<Min> + Borrow<Max>
1599     {
1600         range_impl!(&self.root,
1601                     min,
1602                     max,
1603                     as_slices_internal,
1604                     iter,
1605                     Range,
1606                     edges,
1607                     [])
1608     }
1609
1610     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
1611     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1612     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1613     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1614     ///
1615     /// # Examples
1616     ///
1617     /// ```
1618     /// #![feature(btree_range, collections_bound)]
1619     ///
1620     /// use std::collections::BTreeMap;
1621     /// use std::collections::Bound::{Included, Excluded};
1622     ///
1623     /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
1624     ///                                                                       .map(|&s| (s, 0))
1625     ///                                                                       .collect();
1626     /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
1627     ///     *balance += 100;
1628     /// }
1629     /// for (name, balance) in &map {
1630     ///     println!("{} => {}", name, balance);
1631     /// }
1632     /// ```
1633     #[unstable(feature = "btree_range",
1634                reason = "matches collection reform specification, waiting for dust to settle",
1635                issue = "27787")]
1636     pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
1637                                                            min: Bound<&Min>,
1638                                                            max: Bound<&Max>)
1639                                                            -> RangeMut<K, V>
1640         where K: Borrow<Min> + Borrow<Max>
1641     {
1642         range_impl!(&mut self.root,
1643                     min,
1644                     max,
1645                     as_slices_internal_mut,
1646                     iter_mut,
1647                     RangeMut,
1648                     edges_mut,
1649                     [mut])
1650     }
1651
1652     /// Gets the given key's corresponding entry in the map for in-place manipulation.
1653     ///
1654     /// # Examples
1655     ///
1656     /// ```
1657     /// use std::collections::BTreeMap;
1658     ///
1659     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1660     ///
1661     /// // count the number of occurrences of letters in the vec
1662     /// for x in vec!["a","b","a","c","a","b"] {
1663     ///     *count.entry(x).or_insert(0) += 1;
1664     /// }
1665     ///
1666     /// assert_eq!(count["a"], 3);
1667     /// ```
1668     #[stable(feature = "rust1", since = "1.0.0")]
1669     pub fn entry(&mut self, mut key: K) -> Entry<K, V> {
1670         // same basic logic of `swap` and `pop`, blended together
1671         let mut stack = stack::PartialSearchStack::new(self);
1672         loop {
1673             let result = stack.with(move |pusher, node| {
1674                 match Node::search(node, &key) {
1675                     Found(handle) => {
1676                         // Perfect match
1677                         Finished(Occupied(OccupiedEntry { stack: pusher.seal(handle) }))
1678                     }
1679                     GoDown(handle) => {
1680                         match handle.force() {
1681                             Leaf(leaf_handle) => {
1682                                 Finished(Vacant(VacantEntry {
1683                                     stack: pusher.seal(leaf_handle),
1684                                     key: key,
1685                                 }))
1686                             }
1687                             Internal(internal_handle) => {
1688                                 Continue((pusher.push(internal_handle), key))
1689                             }
1690                         }
1691                     }
1692                 }
1693             });
1694             match result {
1695                 Finished(finished) => return finished,
1696                 Continue((new_stack, renewed_key)) => {
1697                     stack = new_stack;
1698                     key = renewed_key;
1699                 }
1700             }
1701         }
1702     }
1703 }
1704
1705 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
1706     where K: Borrow<Q> + Ord,
1707           Q: Ord
1708 {
1709     type Key = K;
1710
1711     fn get(&self, key: &Q) -> Option<&K> {
1712         let mut cur_node = &self.root;
1713         loop {
1714             match Node::search(cur_node, key) {
1715                 Found(handle) => return Some(handle.into_kv().0),
1716                 GoDown(handle) => {
1717                     match handle.force() {
1718                         Leaf(_) => return None,
1719                         Internal(internal_handle) => {
1720                             cur_node = internal_handle.into_edge();
1721                             continue;
1722                         }
1723                     }
1724                 }
1725             }
1726         }
1727     }
1728
1729     fn take(&mut self, key: &Q) -> Option<K> {
1730         // See `remove` for an explanation of this.
1731
1732         let mut stack = stack::PartialSearchStack::new(self);
1733         loop {
1734             let result = stack.with(move |pusher, node| {
1735                 match Node::search(node, key) {
1736                     Found(handle) => {
1737                         // Perfect match. Terminate the stack here, and remove the entry
1738                         Finished(Some(pusher.seal(handle).remove()))
1739                     }
1740                     GoDown(handle) => {
1741                         // We need to keep searching, try to go down the next edge
1742                         match handle.force() {
1743                             // We're at a leaf; the key isn't in here
1744                             Leaf(_) => Finished(None),
1745                             Internal(internal_handle) => Continue(pusher.push(internal_handle)),
1746                         }
1747                     }
1748                 }
1749             });
1750             match result {
1751                 Finished(ret) => return ret.map(|(k, _)| k),
1752                 Continue(new_stack) => stack = new_stack,
1753             }
1754         }
1755     }
1756
1757     fn replace(&mut self, mut key: K) -> Option<K> {
1758         // See `insert` for an explanation of this.
1759
1760         let mut stack = stack::PartialSearchStack::new(self);
1761
1762         loop {
1763             let result = stack.with(move |pusher, node| {
1764                 match Node::search::<K, _>(node, &key) {
1765                     Found(mut handle) => {
1766                         mem::swap(handle.key_mut(), &mut key);
1767                         Finished(Some(key))
1768                     }
1769                     GoDown(handle) => {
1770                         match handle.force() {
1771                             Leaf(leaf_handle) => {
1772                                 pusher.seal(leaf_handle).insert(key, ());
1773                                 Finished(None)
1774                             }
1775                             Internal(internal_handle) => {
1776                                 Continue((pusher.push(internal_handle), key, ()))
1777                             }
1778                         }
1779                     }
1780                 }
1781             });
1782             match result {
1783                 Finished(ret) => return ret,
1784                 Continue((new_stack, renewed_key, _)) => {
1785                     stack = new_stack;
1786                     key = renewed_key;
1787                 }
1788             }
1789         }
1790     }
1791 }