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