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