src/libcollections/btree/map.rs

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