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