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, IntoIterator};
  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)) {};
 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 impl<K, V> IntoIterator for BTreeMap<K, V> {
 482     type Iter = IntoIter<K, V>;
 483
 484     fn into_iter(self) -> IntoIter<K, V> {
 485         self.into_iter()
 486     }
 487 }
 488
 489 impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
 490     type Iter = Iter<'a, K, V>;
 491
 492     fn into_iter(self) -> Iter<'a, K, V> {
 493         self.iter()
 494     }
 495 }
 496
 497 impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
 498     type Iter = IterMut<'a, K, V>;
 499
 500     fn into_iter(mut self) -> IterMut<'a, K, V> {
 501         self.iter_mut()
 502     }
 503 }
 504
 505 /// A helper enum useful for deciding whether to continue a loop since we can't
 506 /// return from a closure
 507 enum Continuation<A, B> {
 508     Continue(A),
 509     Finished(B)
 510 }
 511
 512 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
 513 /// to nodes. By using this module much better safety guarantees can be made, and more search
 514 /// boilerplate gets cut out.
 515 mod stack {
 516     use core::prelude::*;
 517     use core::marker;
 518     use core::mem;
 519     use core::ops::{Deref, DerefMut};
 520     use super::BTreeMap;
 521     use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
 522     use super::super::node::handle;
 523     use vec::Vec;
 524
 525     /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
 526     /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
 527     /// with the exact requested lifetime can be used. This is in contrast to normal references,
 528     /// where `&'static` can be used in any function expecting any lifetime reference.
 529     pub struct IdRef<'id, T: 'id> {
 530         inner: &'id mut T,
 531         marker: marker::InvariantLifetime<'id>
 532     }
 533
 534     impl<'id, T> Deref for IdRef<'id, T> {
 535         type Target = T;
 536
 537         fn deref(&self) -> &T {
 538             &*self.inner
 539         }
 540     }
 541
 542     impl<'id, T> DerefMut for IdRef<'id, T> {
 543         fn deref_mut(&mut self) -> &mut T {
 544             &mut *self.inner
 545         }
 546     }
 547
 548     type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
 549     type Stack<K, V> = Vec<StackItem<K, V>>;
 550
 551     /// A `PartialSearchStack` handles the construction of a search stack.
 552     pub struct PartialSearchStack<'a, K:'a, V:'a> {
 553         map: &'a mut BTreeMap<K, V>,
 554         stack: Stack<K, V>,
 555         next: *mut Node<K, V>,
 556     }
 557
 558     /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
 559     /// methods depending on the type of what the path points to for removing an element, inserting
 560     /// a new element, and manipulating to element at the top of the stack.
 561     pub struct SearchStack<'a, K:'a, V:'a, Type, NodeType> {
 562         map: &'a mut BTreeMap<K, V>,
 563         stack: Stack<K, V>,
 564         top: node::Handle<*mut Node<K, V>, Type, NodeType>,
 565     }
 566
 567     /// A `PartialSearchStack` that doesn't hold a a reference to the next node, and is just
 568     /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
 569     /// for more details.
 570     pub struct Pusher<'id, 'a, K:'a, V:'a> {
 571         map: &'a mut BTreeMap<K, V>,
 572         stack: Stack<K, V>,
 573         marker: marker::InvariantLifetime<'id>
 574     }
 575
 576     impl<'a, K, V> PartialSearchStack<'a, K, V> {
 577         /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
 578         /// root of the tree.
 579         pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
 580             let depth = map.depth;
 581
 582             PartialSearchStack {
 583                 next: &mut map.root as *mut _,
 584                 map: map,
 585                 stack: Vec::with_capacity(depth),
 586             }
 587         }
 588
 589         /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
 590         /// to interact with, search, and finally push the `Node` onto the stack. The passed in
 591         /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
 592         /// ensures that only `Handle`s from the correct `Node` can be pushed.
 593         ///
 594         /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
 595         /// handles with the same `'id`. The closure could only get references with that lifetime
 596         /// through its arguments or through some other `IdRef` that it has lying around. However,
 597         /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
 598         /// parameter, it would need to have precisely the correct lifetime, which would mean that
 599         /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
 600         /// specific lifetime instead of the one that `with` chooses to give it.
 601         ///
 602         /// See also Haskell's `ST` monad, which uses a similar trick.
 603         pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
 604                                           IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
 605             let pusher = Pusher {
 606                 map: self.map,
 607                 stack: self.stack,
 608                 marker: marker::InvariantLifetime
 609             };
 610             let node = IdRef {
 611                 inner: unsafe { &mut *self.next },
 612                 marker: marker::InvariantLifetime
 613             };
 614
 615             closure(pusher, node)
 616         }
 617     }
 618
 619     impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
 620         /// Pushes the requested child of the stack's current top on top of the stack. If the child
 621         /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
 622         /// yielded.
 623         pub fn push(mut self, mut edge: node::Handle<IdRef<'id, Node<K, V>>,
 624                                                      handle::Edge,
 625                                                      handle::Internal>)
 626                     -> PartialSearchStack<'a, K, V> {
 627             self.stack.push(edge.as_raw());
 628             PartialSearchStack {
 629                 map: self.map,
 630                 stack: self.stack,
 631                 next: edge.edge_mut() as *mut _,
 632             }
 633         }
 634
 635         /// Converts the PartialSearchStack into a SearchStack.
 636         pub fn seal<Type, NodeType>
 637                    (self, mut handle: node::Handle<IdRef<'id, Node<K, V>>, Type, NodeType>)
 638                     -> SearchStack<'a, K, V, Type, NodeType> {
 639             SearchStack {
 640                 map: self.map,
 641                 stack: self.stack,
 642                 top: handle.as_raw(),
 643             }
 644         }
 645     }
 646
 647     impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
 648         /// Gets a reference to the value the stack points to.
 649         pub fn peek(&self) -> &V {
 650             unsafe { self.top.from_raw().into_kv().1 }
 651         }
 652
 653         /// Gets a mutable reference to the value the stack points to.
 654         pub fn peek_mut(&mut self) -> &mut V {
 655             unsafe { self.top.from_raw_mut().into_kv_mut().1 }
 656         }
 657
 658         /// Converts the stack into a mutable reference to the value it points to, with a lifetime
 659         /// tied to the original tree.
 660         pub fn into_top(mut self) -> &'a mut V {
 661             unsafe {
 662                 mem::copy_mut_lifetime(
 663                     self.map,
 664                     self.top.from_raw_mut().val_mut()
 665                 )
 666             }
 667         }
 668     }
 669
 670     impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
 671         /// Removes the key and value in the top element of the stack, then handles underflows as
 672         /// described in BTree's pop function.
 673         fn remove_leaf(mut self) -> V {
 674             self.map.length -= 1;
 675
 676             // Remove the key-value pair from the leaf that this search stack points to.
 677             // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
 678             // to avoid ownership issues.
 679             let (value, mut underflow) = unsafe {
 680                 let (_, value) = self.top.from_raw_mut().remove_as_leaf();
 681                 let underflow = self.top.from_raw().node().is_underfull();
 682                 (value, underflow)
 683             };
 684
 685             loop {
 686                 match self.stack.pop() {
 687                     None => {
 688                         // We've reached the root, so no matter what, we're done. We manually
 689                         // access the root via the tree itself to avoid creating any dangling
 690                         // pointers.
 691                         if self.map.root.len() == 0 && !self.map.root.is_leaf() {
 692                             // We've emptied out the root, so make its only child the new root.
 693                             // If it's a leaf, we just let it become empty.
 694                             self.map.depth -= 1;
 695                             self.map.root.hoist_lone_child();
 696                         }
 697                         return value;
 698                     }
 699                     Some(mut handle) => {
 700                         if underflow {
 701                             // Underflow! Handle it!
 702                             unsafe {
 703                                 handle.from_raw_mut().handle_underflow();
 704                                 underflow = handle.from_raw().node().is_underfull();
 705                             }
 706                         } else {
 707                             // All done!
 708                             return value;
 709                         }
 710                     }
 711                 }
 712             }
 713         }
 714     }
 715
 716     impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
 717         /// Removes the key and value in the top element of the stack, then handles underflows as
 718         /// described in BTree's pop function.
 719         pub fn remove(self) -> V {
 720             // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
 721             // in a BTree. Note that this may put the tree in an inconsistent state (further
 722             // described in into_leaf's comments), but this is immediately fixed by the
 723             // removing the value we want to remove
 724             self.into_leaf().remove_leaf()
 725         }
 726
 727         /// Subroutine for removal. Takes a search stack for a key that might terminate at an
 728         /// internal node, and mutates the tree and search stack to *make* it a search stack
 729         /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
 730         /// leaves the tree in an inconsistent state that must be repaired by the caller by
 731         /// removing the entry in question. Specifically the key-value pair and its successor will
 732         /// become swapped.
 733         fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
 734             unsafe {
 735                 let mut top_raw = self.top;
 736                 let mut top = top_raw.from_raw_mut();
 737
 738                 let key_ptr = top.key_mut() as *mut _;
 739                 let val_ptr = top.val_mut() as *mut _;
 740
 741                 // Try to go into the right subtree of the found key to find its successor
 742                 match top.force() {
 743                     Leaf(mut leaf_handle) => {
 744                         // We're a proper leaf stack, nothing to do
 745                         return SearchStack {
 746                             map: self.map,
 747                             stack: self.stack,
 748                             top: leaf_handle.as_raw()
 749                         }
 750                     }
 751                     Internal(mut internal_handle) => {
 752                         let mut right_handle = internal_handle.right_edge();
 753
 754                         //We're not a proper leaf stack, let's get to work.
 755                         self.stack.push(right_handle.as_raw());
 756
 757                         let mut temp_node = right_handle.edge_mut();
 758                         loop {
 759                             // Walk into the smallest subtree of this node
 760                             let node = temp_node;
 761
 762                             match node.kv_handle(0).force() {
 763                                 Leaf(mut handle) => {
 764                                     // This node is a leaf, do the swap and return
 765                                     mem::swap(handle.key_mut(), &mut *key_ptr);
 766                                     mem::swap(handle.val_mut(), &mut *val_ptr);
 767                                     return SearchStack {
 768                                         map: self.map,
 769                                         stack: self.stack,
 770                                         top: handle.as_raw()
 771                                     }
 772                                 },
 773                                 Internal(kv_handle) => {
 774                                     // This node is internal, go deeper
 775                                     let mut handle = kv_handle.into_left_edge();
 776                                     self.stack.push(handle.as_raw());
 777                                     temp_node = handle.into_edge_mut();
 778                                 }
 779                             }
 780                         }
 781                     }
 782                 }
 783             }
 784         }
 785     }
 786
 787     impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
 788         /// Inserts the key and value into the top element in the stack, and if that node has to
 789         /// split recursively inserts the split contents into the next element stack until
 790         /// splits stop.
 791         ///
 792         /// Assumes that the stack represents a search path from the root to a leaf.
 793         ///
 794         /// An &mut V is returned to the inserted value, for callers that want a reference to this.
 795         pub fn insert(mut self, key: K, val: V) -> &'a mut V {
 796             unsafe {
 797                 self.map.length += 1;
 798
 799                 // Insert the key and value into the leaf at the top of the stack
 800                 let (mut insertion, inserted_ptr) = self.top.from_raw_mut()
 801                                                         .insert_as_leaf(key, val);
 802
 803                 loop {
 804                     match insertion {
 805                         Fit => {
 806                             // The last insertion went off without a hitch, no splits! We can stop
 807                             // inserting now.
 808                             return &mut *inserted_ptr;
 809                         }
 810                         Split(key, val, right) => match self.stack.pop() {
 811                             // The last insertion triggered a split, so get the next element on the
 812                             // stack to recursively insert the split node into.
 813                             None => {
 814                                 // The stack was empty; we've split the root, and need to make a
 815                                 // a new one. This is done in-place because we can't move the
 816                                 // root out of a reference to the tree.
 817                                 Node::make_internal_root(&mut self.map.root, self.map.b,
 818                                                          key, val, right);
 819
 820                                 self.map.depth += 1;
 821                                 return &mut *inserted_ptr;
 822                             }
 823                             Some(mut handle) => {
 824                                 // The stack wasn't empty, do the insertion and recurse
 825                                 insertion = handle.from_raw_mut()
 826                                                   .insert_as_internal(key, val, right);
 827                                 continue;
 828                             }
 829                         }
 830                     }
 831                 }
 832             }
 833         }
 834     }
 835 }
 836
 837 #[stable(feature = "rust1", since = "1.0.0")]
 838 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
 839     fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
 840         let mut map = BTreeMap::new();
 841         map.extend(iter);
 842         map
 843     }
 844 }
 845
 846 #[stable(feature = "rust1", since = "1.0.0")]
 847 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
 848     #[inline]
 849     fn extend<T: Iterator<Item=(K, V)>>(&mut self, mut iter: T) {
 850         for (k, v) in iter {
 851             self.insert(k, v);
 852         }
 853     }
 854 }
 855
 856 #[stable(feature = "rust1", since = "1.0.0")]
 857 impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
 858     fn hash(&self, state: &mut S) {
 859         for elt in self {
 860             elt.hash(state);
 861         }
 862     }
 863 }
 864
 865 #[stable(feature = "rust1", since = "1.0.0")]
 866 impl<K: Ord, V> Default for BTreeMap<K, V> {
 867     #[stable(feature = "rust1", since = "1.0.0")]
 868     fn default() -> BTreeMap<K, V> {
 869         BTreeMap::new()
 870     }
 871 }
 872
 873 #[stable(feature = "rust1", since = "1.0.0")]
 874 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
 875     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
 876         self.len() == other.len() &&
 877             self.iter().zip(other.iter()).all(|(a, b)| a == b)
 878     }
 879 }
 880
 881 #[stable(feature = "rust1", since = "1.0.0")]
 882 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
 883
 884 #[stable(feature = "rust1", since = "1.0.0")]
 885 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
 886     #[inline]
 887     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
 888         iter::order::partial_cmp(self.iter(), other.iter())
 889     }
 890 }
 891
 892 #[stable(feature = "rust1", since = "1.0.0")]
 893 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
 894     #[inline]
 895     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
 896         iter::order::cmp(self.iter(), other.iter())
 897     }
 898 }
 899
 900 #[stable(feature = "rust1", since = "1.0.0")]
 901 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
 902     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 903         try!(write!(f, "BTreeMap {{"));
 904
 905         for (i, (k, v)) in self.iter().enumerate() {
 906             if i != 0 { try!(write!(f, ", ")); }
 907             try!(write!(f, "{:?}: {:?}", *k, *v));
 908         }
 909
 910         write!(f, "}}")
 911     }
 912 }
 913
 914 #[stable(feature = "rust1", since = "1.0.0")]
 915 impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V>
 916     where Q: BorrowFrom<K> + Ord
 917 {
 918     type Output = V;
 919
 920     fn index(&self, key: &Q) -> &V {
 921         self.get(key).expect("no entry found for key")
 922     }
 923 }
 924
 925 #[stable(feature = "rust1", since = "1.0.0")]
 926 impl<K: Ord, Q: ?Sized, V> IndexMut<Q> for BTreeMap<K, V>
 927     where Q: BorrowFrom<K> + Ord
 928 {
 929     type Output = V;
 930
 931     fn index_mut(&mut self, key: &Q) -> &mut V {
 932         self.get_mut(key).expect("no entry found for key")
 933     }
 934 }
 935
 936 /// Genericises over how to get the correct type of iterator from the correct type
 937 /// of Node ownership.
 938 trait Traverse<N> {
 939     fn traverse(node: N) -> Self;
 940 }
 941
 942 impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
 943     fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
 944         node.iter()
 945     }
 946 }
 947
 948 impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
 949     fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
 950         node.iter_mut()
 951     }
 952 }
 953
 954 impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
 955     fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
 956         node.into_iter()
 957     }
 958 }
 959
 960 /// Represents an operation to perform inside the following iterator methods.
 961 /// This is necessary to use in `next` because we want to modify `self.traversals` inside
 962 /// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
 963 /// what we want to do, and do it after the match.
 964 enum StackOp<T> {
 965     Push(T),
 966     Pop,
 967 }
 968 impl<K, V, E, T> Iterator for AbsIter<T> where
 969     T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
 970 {
 971     type Item = (K, V);
 972
 973     // Our iterator represents a queue of all ancestors of elements we have
 974     // yet to yield, from smallest to largest.  Note that the design of these
 975     // iterators permits an *arbitrary* initial pair of min and max, making
 976     // these arbitrary sub-range iterators.
 977     fn next(&mut self) -> Option<(K, V)> {
 978         loop {
 979             // We want the smallest element, so try to get the back of the queue
 980             let op = match self.traversals.back_mut() {
 981                 None => return None,
 982                 // The queue wasn't empty, so continue along the node in its head
 983                 Some(iter) => match iter.next() {
 984                     // The head is empty, so Pop it off and continue the process
 985                     None => Pop,
 986                     // The head yielded an edge, so make that the new head
 987                     Some(Edge(next)) => Push(Traverse::traverse(next)),
 988                     // The head yielded an entry, so yield that
 989                     Some(Elem(kv)) => {
 990                         self.size -= 1;
 991                         return Some(kv)
 992                     }
 993                 }
 994             };
 995
 996             // Handle any operation as necessary, without a conflicting borrow of the queue
 997             match op {
 998                 Push(item) => { self.traversals.push_back(item); },
 999                 Pop => { self.traversals.pop_back(); },
1000             }
1001         }
1002     }
1003
1004     fn size_hint(&self) -> (uint, Option<uint>) {
1005         (self.size, Some(self.size))
1006     }
1007 }
1008
1009 impl<K, V, E, T> DoubleEndedIterator for AbsIter<T> where
1010     T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
1011 {
1012     // next_back is totally symmetric to next
1013     #[inline]
1014     fn next_back(&mut self) -> Option<(K, V)> {
1015         loop {
1016             let op = match self.traversals.front_mut() {
1017                 None => return None,
1018                 Some(iter) => match iter.next_back() {
1019                     None => Pop,
1020                     Some(Edge(next)) => Push(Traverse::traverse(next)),
1021                     Some(Elem(kv)) => {
1022                         self.size -= 1;
1023                         return Some(kv)
1024                     }
1025                 }
1026             };
1027
1028             match op {
1029                 Push(item) => { self.traversals.push_front(item); },
1030                 Pop => { self.traversals.pop_front(); }
1031             }
1032         }
1033     }
1034 }
1035
1036 #[stable(feature = "rust1", since = "1.0.0")]
1037 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1038     type Item = (&'a K, &'a V);
1039
1040     fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1041     fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1042 }
1043 #[stable(feature = "rust1", since = "1.0.0")]
1044 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1045     fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
1046 }
1047 #[stable(feature = "rust1", since = "1.0.0")]
1048 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1049
1050 #[stable(feature = "rust1", since = "1.0.0")]
1051 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1052     type Item = (&'a K, &'a mut V);
1053
1054     fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1055     fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1056 }
1057 #[stable(feature = "rust1", since = "1.0.0")]
1058 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1059     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
1060 }
1061 #[stable(feature = "rust1", since = "1.0.0")]
1062 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1063
1064 #[stable(feature = "rust1", since = "1.0.0")]
1065 impl<K, V> Iterator for IntoIter<K, V> {
1066     type Item = (K, V);
1067
1068     fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1069     fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1070 }
1071 #[stable(feature = "rust1", since = "1.0.0")]
1072 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1073     fn next_back(&mut self) -> Option<(K, V)> { self.inner.next_back() }
1074 }
1075 #[stable(feature = "rust1", since = "1.0.0")]
1076 impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
1077
1078 #[stable(feature = "rust1", since = "1.0.0")]
1079 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1080     type Item = &'a K;
1081
1082     fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1083     fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1084 }
1085 #[stable(feature = "rust1", since = "1.0.0")]
1086 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1087     fn next_back(&mut self) -> Option<(&'a K)> { self.inner.next_back() }
1088 }
1089 #[stable(feature = "rust1", since = "1.0.0")]
1090 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
1091
1092
1093 #[stable(feature = "rust1", since = "1.0.0")]
1094 impl<'a, K, V> Iterator for Values<'a, K, V> {
1095     type Item = &'a V;
1096
1097     fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1098     fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1099 }
1100 #[stable(feature = "rust1", since = "1.0.0")]
1101 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1102     fn next_back(&mut self) -> Option<(&'a V)> { self.inner.next_back() }
1103 }
1104 #[stable(feature = "rust1", since = "1.0.0")]
1105 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
1106
1107 impl<'a, K, V> Iterator for Range<'a, K, V> {
1108     type Item = (&'a K, &'a V);
1109
1110     fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1111 }
1112 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1113     fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
1114 }
1115
1116 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1117     type Item = (&'a K, &'a mut V);
1118
1119     fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1120 }
1121 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1122     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
1123 }
1124
1125 impl<'a, K: Ord, V> Entry<'a, K, V> {
1126     #[unstable(feature = "collections",
1127                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1128     /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1129     pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> {
1130         match self {
1131             Occupied(entry) => Ok(entry.into_mut()),
1132             Vacant(entry) => Err(entry),
1133         }
1134     }
1135 }
1136
1137 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1138     /// Sets the value of the entry with the VacantEntry's key,
1139     /// and returns a mutable reference to it.
1140     #[unstable(feature = "collections",
1141                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1142     pub fn insert(self, value: V) -> &'a mut V {
1143         self.stack.insert(self.key, value)
1144     }
1145 }
1146
1147 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1148     /// Gets a reference to the value in the entry.
1149     #[unstable(feature = "collections",
1150                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1151     pub fn get(&self) -> &V {
1152         self.stack.peek()
1153     }
1154
1155     /// Gets a mutable reference to the value in the entry.
1156     #[unstable(feature = "collections",
1157                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1158     pub fn get_mut(&mut self) -> &mut V {
1159         self.stack.peek_mut()
1160     }
1161
1162     /// Converts the entry into a mutable reference to its value.
1163     #[unstable(feature = "collections",
1164                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1165     pub fn into_mut(self) -> &'a mut V {
1166         self.stack.into_top()
1167     }
1168
1169     /// Sets the value of the entry with the OccupiedEntry's key,
1170     /// and returns the entry's old value.
1171     #[unstable(feature = "collections",
1172                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1173     pub fn insert(&mut self, mut value: V) -> V {
1174         mem::swap(self.stack.peek_mut(), &mut value);
1175         value
1176     }
1177
1178     /// Takes the value of the entry out of the map, and returns it.
1179     #[unstable(feature = "collections",
1180                reason = "matches collection reform v2 specification, waiting for dust to settle")]
1181     pub fn remove(self) -> V {
1182         self.stack.remove()
1183     }
1184 }
1185
1186 impl<K, V> BTreeMap<K, V> {
1187     /// Gets an iterator over the entries of the map.
1188     ///
1189     /// # Example
1190     ///
1191     /// ```
1192     /// use std::collections::BTreeMap;
1193     ///
1194     /// let mut map = BTreeMap::new();
1195     /// map.insert(1u, "a");
1196     /// map.insert(2u, "b");
1197     /// map.insert(3u, "c");
1198     ///
1199     /// for (key, value) in map.iter() {
1200     ///     println!("{}: {}", key, value);
1201     /// }
1202     ///
1203     /// let (first_key, first_value) = map.iter().next().unwrap();
1204     /// assert_eq!((*first_key, *first_value), (1u, "a"));
1205     /// ```
1206     #[stable(feature = "rust1", since = "1.0.0")]
1207     pub fn iter(&self) -> Iter<K, V> {
1208         let len = self.len();
1209         // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
1210         let mut lca = RingBuf::new();
1211         lca.push_back(Traverse::traverse(&self.root));
1212         Iter {
1213             inner: AbsIter {
1214                 traversals: lca,
1215                 size: len,
1216             }
1217         }
1218     }
1219
1220     /// Gets a mutable iterator over the entries of the map.
1221     ///
1222     /// # Examples
1223     ///
1224     /// ```
1225     /// use std::collections::BTreeMap;
1226     ///
1227     /// let mut map = BTreeMap::new();
1228     /// map.insert("a", 1u);
1229     /// map.insert("b", 2u);
1230     /// map.insert("c", 3u);
1231     ///
1232     /// // add 10 to the value if the key isn't "a"
1233     /// for (key, value) in map.iter_mut() {
1234     ///     if key != &"a" {
1235     ///         *value += 10;
1236     ///     }
1237     /// }
1238     /// ```
1239     #[stable(feature = "rust1", since = "1.0.0")]
1240     pub fn iter_mut(&mut self) -> IterMut<K, V> {
1241         let len = self.len();
1242         let mut lca = RingBuf::new();
1243         lca.push_back(Traverse::traverse(&mut self.root));
1244         IterMut {
1245             inner: AbsIter {
1246                 traversals: lca,
1247                 size: len,
1248             }
1249         }
1250     }
1251
1252     /// Gets an owning iterator over the entries of the map.
1253     ///
1254     /// # Examples
1255     ///
1256     /// ```
1257     /// use std::collections::BTreeMap;
1258     ///
1259     /// let mut map = BTreeMap::new();
1260     /// map.insert(1u, "a");
1261     /// map.insert(2u, "b");
1262     /// map.insert(3u, "c");
1263     ///
1264     /// for (key, value) in map.into_iter() {
1265     ///     println!("{}: {}", key, value);
1266     /// }
1267     /// ```
1268     #[stable(feature = "rust1", since = "1.0.0")]
1269     pub fn into_iter(self) -> IntoIter<K, V> {
1270         let len = self.len();
1271         let mut lca = RingBuf::new();
1272         lca.push_back(Traverse::traverse(self.root));
1273         IntoIter {
1274             inner: AbsIter {
1275                 traversals: lca,
1276                 size: len,
1277             }
1278         }
1279     }
1280
1281     /// Gets an iterator over the keys of the map.
1282     ///
1283     /// # Examples
1284     ///
1285     /// ```
1286     /// use std::collections::BTreeMap;
1287     ///
1288     /// let mut a = BTreeMap::new();
1289     /// a.insert(1u, "a");
1290     /// a.insert(2u, "b");
1291     ///
1292     /// let keys: Vec<uint> = a.keys().cloned().collect();
1293     /// assert_eq!(keys, vec![1u,2,]);
1294     /// ```
1295     #[stable(feature = "rust1", since = "1.0.0")]
1296     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1297         fn first<A, B>((a, _): (A, B)) -> A { a }
1298         let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
1299
1300         Keys { inner: self.iter().map(first) }
1301     }
1302
1303     /// Gets an iterator over the values of the map.
1304     ///
1305     /// # Examples
1306     ///
1307     /// ```
1308     /// use std::collections::BTreeMap;
1309     ///
1310     /// let mut a = BTreeMap::new();
1311     /// a.insert(1u, "a");
1312     /// a.insert(2u, "b");
1313     ///
1314     /// let values: Vec<&str> = a.values().cloned().collect();
1315     /// assert_eq!(values, vec!["a","b"]);
1316     /// ```
1317     #[stable(feature = "rust1", since = "1.0.0")]
1318     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1319         fn second<A, B>((_, b): (A, B)) -> B { b }
1320         let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
1321
1322         Values { inner: self.iter().map(second) }
1323     }
1324
1325     /// Return the number of elements in the map.
1326     ///
1327     /// # Examples
1328     ///
1329     /// ```
1330     /// use std::collections::BTreeMap;
1331     ///
1332     /// let mut a = BTreeMap::new();
1333     /// assert_eq!(a.len(), 0);
1334     /// a.insert(1u, "a");
1335     /// assert_eq!(a.len(), 1);
1336     /// ```
1337     #[stable(feature = "rust1", since = "1.0.0")]
1338     pub fn len(&self) -> uint { self.length }
1339
1340     /// Return true if the map contains no elements.
1341     ///
1342     /// # Examples
1343     ///
1344     /// ```
1345     /// use std::collections::BTreeMap;
1346     ///
1347     /// let mut a = BTreeMap::new();
1348     /// assert!(a.is_empty());
1349     /// a.insert(1u, "a");
1350     /// assert!(!a.is_empty());
1351     /// ```
1352     #[stable(feature = "rust1", since = "1.0.0")]
1353     pub fn is_empty(&self) -> bool { self.len() == 0 }
1354 }
1355
1356 macro_rules! range_impl {
1357     ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident,
1358                                        $edges:ident, [$($mutability:ident)*]) => (
1359         {
1360             // A deque that encodes two search paths containing (left-to-right):
1361             // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
1362             // and a series of truncated-from-the-right iterators.
1363             let mut traversals = RingBuf::new();
1364             let (root, min, max) = ($root, $min, $max);
1365
1366             let mut leftmost = None;
1367             let mut rightmost = None;
1368
1369             match (&min, &max) {
1370                 (&Unbounded, &Unbounded) => {
1371                     traversals.push_back(Traverse::traverse(root))
1372                 }
1373                 (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => {
1374                     rightmost = Some(root);
1375                 }
1376                 (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => {
1377                     leftmost = Some(root);
1378                 }
1379                   (&Included(min_key), &Included(max_key))
1380                 | (&Included(min_key), &Excluded(max_key))
1381                 | (&Excluded(min_key), &Included(max_key))
1382                 | (&Excluded(min_key), &Excluded(max_key)) => {
1383                     // lca represents the Lowest Common Ancestor, above which we never
1384                     // walk, since everything else is outside the range to iterate.
1385                     //       ___________________
1386                     //      |__0_|_80_|_85_|_90_|  (root)
1387                     //      |    |    |    |    |
1388                     //           |
1389                     //           v
1390                     //  ___________________
1391                     // |__5_|_15_|_30_|_73_|
1392                     // |    |    |    |    |
1393                     //                |
1394                     //                v
1395                     //       ___________________
1396                     //      |_33_|_58_|_63_|_68_|  lca for the range [41, 65]
1397                     //      |    |\___|___/|    |  iterator at traversals[2]
1398                     //           |         |
1399                     //           |         v
1400                     //           v         rightmost
1401                     //           leftmost
1402                     let mut is_leaf = root.is_leaf();
1403                     let mut lca = root.$as_slices_internal();
1404                     loop {
1405                         let slice = lca.slice_from(min_key).slice_to(max_key);
1406                         if let [ref $($mutability)* edge] = slice.edges {
1407                             // Follow the only edge that leads the node that covers the range.
1408                             is_leaf = edge.is_leaf();
1409                             lca = edge.$as_slices_internal();
1410                         } else {
1411                             let mut iter = slice.$iter();
1412                             if is_leaf {
1413                                 leftmost = None;
1414                                 rightmost = None;
1415                             } else {
1416                                 // Only change the state of nodes with edges.
1417                                 leftmost = iter.next_edge_item();
1418                                 rightmost = iter.next_edge_item_back();
1419                             }
1420                             traversals.push_back(iter);
1421                             break;
1422                         }
1423                     }
1424                 }
1425             }
1426             // Keep narrowing the range by going down.
1427             //               ___________________
1428             //              |_38_|_43_|_48_|_53_|
1429             //              |    |____|____|____/ iterator at traversals[1]
1430             //                   |
1431             //                   v
1432             //  ___________________
1433             // |_39_|_40_|_41_|_42_|  (leaf, the last leftmost)
1434             //           \_________|  iterator at traversals[0]
1435             match min {
1436                 Included(key) | Excluded(key) =>
1437                     while let Some(left) = leftmost {
1438                         let is_leaf = left.is_leaf();
1439                         let mut iter = left.$as_slices_internal().slice_from(key).$iter();
1440                         leftmost = if is_leaf {
1441                             None
1442                         } else {
1443                             // Only change the state of nodes with edges.
1444                             iter.next_edge_item()
1445                         };
1446                         traversals.push_back(iter);
1447                     },
1448                 _ => {}
1449             }
1450             // If the leftmost iterator starts with an element, then it was an exact match.
1451             if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) {
1452                 // Drop this excluded element. `next_kv_item` has no effect when
1453                 // the next item is an edge.
1454                 leftmost_iter.next_kv_item();
1455             }
1456
1457             // The code for the right side is similar.
1458             match max {
1459                 Included(key) | Excluded(key) =>
1460                     while let Some(right) = rightmost {
1461                         let is_leaf = right.is_leaf();
1462                         let mut iter = right.$as_slices_internal().slice_to(key).$iter();
1463                         rightmost = if is_leaf {
1464                             None
1465                         } else {
1466                             iter.next_edge_item_back()
1467                         };
1468                         traversals.push_front(iter);
1469                     },
1470                 _ => {}
1471             }
1472             if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) {
1473                 rightmost_iter.next_kv_item_back();
1474             }
1475
1476             $Range {
1477                 inner: AbsIter {
1478                     traversals: traversals,
1479                     size: 0, // unused
1480                 }
1481             }
1482         }
1483     )
1484 }
1485
1486 impl<K: Ord, V> BTreeMap<K, V> {
1487     /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
1488     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1489     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1490     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1491     ///
1492     /// # Examples
1493     ///
1494     /// ```
1495     /// use std::collections::BTreeMap;
1496     /// use std::collections::Bound::{Included, Unbounded};
1497     ///
1498     /// let mut map = BTreeMap::new();
1499     /// map.insert(3u, "a");
1500     /// map.insert(5u, "b");
1501     /// map.insert(8u, "c");
1502     /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
1503     ///     println!("{}: {}", key, value);
1504     /// }
1505     /// assert_eq!(Some((&5u, &"b")), map.range(Included(&4), Unbounded).next());
1506     /// ```
1507     #[unstable(feature = "collections",
1508                reason = "matches collection reform specification, waiting for dust to settle")]
1509     pub fn range<'a>(&'a self, min: Bound<&K>, max: Bound<&K>) -> Range<'a, K, V> {
1510         range_impl!(&self.root, min, max, as_slices_internal, iter, Range, edges, [])
1511     }
1512
1513     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
1514     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1515     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1516     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1517     ///
1518     /// # Examples
1519     ///
1520     /// ```
1521     /// use std::collections::BTreeMap;
1522     /// use std::collections::Bound::{Included, Excluded};
1523     ///
1524     /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
1525     ///                                                                       .map(|&s| (s, 0))
1526     ///                                                                       .collect();
1527     /// for (_, balance) in map.range_mut(Included(&"B"), Excluded(&"Cheryl")) {
1528     ///     *balance += 100;
1529     /// }
1530     /// for (name, balance) in map.iter() {
1531     ///     println!("{} => {}", name, balance);
1532     /// }
1533     /// ```
1534     #[unstable(feature = "collections",
1535                reason = "matches collection reform specification, waiting for dust to settle")]
1536     pub fn range_mut<'a>(&'a mut self, min: Bound<&K>, max: Bound<&K>) -> RangeMut<'a, K, V> {
1537         range_impl!(&mut self.root, min, max, as_slices_internal_mut, iter_mut, RangeMut,
1538                                                                       edges_mut, [mut])
1539     }
1540
1541     /// Gets the given key's corresponding entry in the map for in-place manipulation.
1542     ///
1543     /// # Examples
1544     ///
1545     /// ```
1546     /// use std::collections::BTreeMap;
1547     /// use std::collections::btree_map::Entry;
1548     ///
1549     /// let mut count: BTreeMap<&str, uint> = BTreeMap::new();
1550     ///
1551     /// // count the number of occurrences of letters in the vec
1552     /// for x in vec!["a","b","a","c","a","b"].iter() {
1553     ///     match count.entry(*x) {
1554     ///         Entry::Vacant(view) => {
1555     ///             view.insert(1);
1556     ///         },
1557     ///         Entry::Occupied(mut view) => {
1558     ///             let v = view.get_mut();
1559     ///             *v += 1;
1560     ///         },
1561     ///     }
1562     /// }
1563     ///
1564     /// assert_eq!(count["a"], 3u);
1565     /// ```
1566     /// The key must have the same ordering before or after `.to_owned()` is called.
1567     #[unstable(feature = "collections",
1568                reason = "precise API still under development")]
1569     pub fn entry<'a>(&'a mut self, mut key: K) -> Entry<'a, K, V> {
1570         // same basic logic of `swap` and `pop`, blended together
1571         let mut stack = stack::PartialSearchStack::new(self);
1572         loop {
1573             let result = stack.with(move |pusher, node| {
1574                 return match Node::search(node, &key) {
1575                     Found(handle) => {
1576                         // Perfect match
1577                         Finished(Occupied(OccupiedEntry {
1578                             stack: pusher.seal(handle)
1579                         }))
1580                     },
1581                     GoDown(handle) => {
1582                         match handle.force() {
1583                             Leaf(leaf_handle) => {
1584                                 Finished(Vacant(VacantEntry {
1585                                     stack: pusher.seal(leaf_handle),
1586                                     key: key,
1587                                 }))
1588                             },
1589                             Internal(internal_handle) => {
1590                                 Continue((
1591                                     pusher.push(internal_handle),
1592                                     key
1593                                 ))
1594                             }
1595                         }
1596                     }
1597                 }
1598             });
1599             match result {
1600                 Finished(finished) => return finished,
1601                 Continue((new_stack, renewed_key)) => {
1602                     stack = new_stack;
1603                     key = renewed_key;
1604                 }
1605             }
1606         }
1607     }
1608 }
1609
1610
1611
1612
1613
1614 #[cfg(test)]
1615 mod test {
1616     use prelude::*;
1617     use std::iter::range_inclusive;
1618
1619     use super::{BTreeMap, Occupied, Vacant};
1620     use Bound::{self, Included, Excluded, Unbounded};
1621
1622     #[test]
1623     fn test_basic_large() {
1624         let mut map = BTreeMap::new();
1625         let size = 10000u;
1626         assert_eq!(map.len(), 0);
1627
1628         for i in 0..size {
1629             assert_eq!(map.insert(i, 10*i), None);
1630             assert_eq!(map.len(), i + 1);
1631         }
1632
1633         for i in 0..size {
1634             assert_eq!(map.get(&i).unwrap(), &(i*10));
1635         }
1636
1637         for i in size..size*2 {
1638             assert_eq!(map.get(&i), None);
1639         }
1640
1641         for i in 0..size {
1642             assert_eq!(map.insert(i, 100*i), Some(10*i));
1643             assert_eq!(map.len(), size);
1644         }
1645
1646         for i in 0..size {
1647             assert_eq!(map.get(&i).unwrap(), &(i*100));
1648         }
1649
1650         for i in 0..size/2 {
1651             assert_eq!(map.remove(&(i*2)), Some(i*200));
1652             assert_eq!(map.len(), size - i - 1);
1653         }
1654
1655         for i in 0..size/2 {
1656             assert_eq!(map.get(&(2*i)), None);
1657             assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
1658         }
1659
1660         for i in 0..size/2 {
1661             assert_eq!(map.remove(&(2*i)), None);
1662             assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
1663             assert_eq!(map.len(), size/2 - i - 1);
1664         }
1665     }
1666
1667     #[test]
1668     fn test_basic_small() {
1669         let mut map = BTreeMap::new();
1670         assert_eq!(map.remove(&1), None);
1671         assert_eq!(map.get(&1), None);
1672         assert_eq!(map.insert(1u, 1u), None);
1673         assert_eq!(map.get(&1), Some(&1));
1674         assert_eq!(map.insert(1, 2), Some(1));
1675         assert_eq!(map.get(&1), Some(&2));
1676         assert_eq!(map.insert(2, 4), None);
1677         assert_eq!(map.get(&2), Some(&4));
1678         assert_eq!(map.remove(&1), Some(2));
1679         assert_eq!(map.remove(&2), Some(4));
1680         assert_eq!(map.remove(&1), None);
1681     }
1682
1683     #[test]
1684     fn test_iter() {
1685         let size = 10000u;
1686
1687         // Forwards
1688         let mut map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1689
1690         fn test<T>(size: uint, mut iter: T) where T: Iterator<Item=(uint, uint)> {
1691             for i in 0..size {
1692                 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1693                 assert_eq!(iter.next().unwrap(), (i, i));
1694             }
1695             assert_eq!(iter.size_hint(), (0, Some(0)));
1696             assert_eq!(iter.next(), None);
1697         }
1698         test(size, map.iter().map(|(&k, &v)| (k, v)));
1699         test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
1700         test(size, map.into_iter());
1701     }
1702
1703     #[test]
1704     fn test_iter_rev() {
1705         let size = 10000u;
1706
1707         // Forwards
1708         let mut map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1709
1710         fn test<T>(size: uint, mut iter: T) where T: Iterator<Item=(uint, uint)> {
1711             for i in 0..size {
1712                 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1713                 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
1714             }
1715             assert_eq!(iter.size_hint(), (0, Some(0)));
1716             assert_eq!(iter.next(), None);
1717         }
1718         test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
1719         test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
1720         test(size, map.into_iter().rev());
1721     }
1722
1723     #[test]
1724     fn test_iter_mixed() {
1725         let size = 10000u;
1726
1727         // Forwards
1728         let mut map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1729
1730         fn test<T>(size: uint, mut iter: T)
1731                 where T: Iterator<Item=(uint, uint)> + DoubleEndedIterator {
1732             for i in 0..size / 4 {
1733                 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
1734                 assert_eq!(iter.next().unwrap(), (i, i));
1735                 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
1736             }
1737             for i in size / 4..size * 3 / 4 {
1738                 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
1739                 assert_eq!(iter.next().unwrap(), (i, i));
1740             }
1741             assert_eq!(iter.size_hint(), (0, Some(0)));
1742             assert_eq!(iter.next(), None);
1743         }
1744         test(size, map.iter().map(|(&k, &v)| (k, v)));
1745         test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
1746         test(size, map.into_iter());
1747     }
1748
1749     #[test]
1750     fn test_range_small() {
1751         let size = 5u;
1752
1753         // Forwards
1754         let map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1755
1756         let mut j = 0u;
1757         for ((&k, &v), i) in map.range(Included(&2), Unbounded).zip(2u..size) {
1758             assert_eq!(k, i);
1759             assert_eq!(v, i);
1760             j += 1;
1761         }
1762         assert_eq!(j, size - 2);
1763     }
1764
1765     #[test]
1766     fn test_range_1000() {
1767         let size = 1000u;
1768         let map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1769
1770         fn test(map: &BTreeMap<uint, uint>, size: uint, min: Bound<&uint>, max: Bound<&uint>) {
1771             let mut kvs = map.range(min, max).map(|(&k, &v)| (k, v));
1772             let mut pairs = (0..size).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         test(&map, size, Included(&0), Excluded(&size));
1781         test(&map, size, Unbounded, Excluded(&size));
1782         test(&map, size, Included(&0), Included(&(size - 1)));
1783         test(&map, size, Unbounded, Included(&(size - 1)));
1784         test(&map, size, Included(&0), Unbounded);
1785         test(&map, size, Unbounded, Unbounded);
1786     }
1787
1788     #[test]
1789     fn test_range() {
1790         let size = 200u;
1791         let map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1792
1793         for i in 0..size {
1794             for j in i..size {
1795                 let mut kvs = map.range(Included(&i), Included(&j)).map(|(&k, &v)| (k, v));
1796                 let mut pairs = range_inclusive(i, j).map(|i| (i, i));
1797
1798                 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
1799                     assert_eq!(kv, pair);
1800                 }
1801                 assert_eq!(kvs.next(), None);
1802                 assert_eq!(pairs.next(), None);
1803             }
1804         }
1805     }
1806
1807     #[test]
1808     fn test_entry(){
1809         let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1810
1811         let mut map: BTreeMap<int, int> = xs.iter().map(|&x| x).collect();
1812
1813         // Existing key (insert)
1814         match map.entry(1) {
1815             Vacant(_) => unreachable!(),
1816             Occupied(mut view) => {
1817                 assert_eq!(view.get(), &10);
1818                 assert_eq!(view.insert(100), 10);
1819             }
1820         }
1821         assert_eq!(map.get(&1).unwrap(), &100);
1822         assert_eq!(map.len(), 6);
1823
1824
1825         // Existing key (update)
1826         match map.entry(2) {
1827             Vacant(_) => unreachable!(),
1828             Occupied(mut view) => {
1829                 let v = view.get_mut();
1830                 *v *= 10;
1831             }
1832         }
1833         assert_eq!(map.get(&2).unwrap(), &200);
1834         assert_eq!(map.len(), 6);
1835
1836         // Existing key (take)
1837         match map.entry(3) {
1838             Vacant(_) => unreachable!(),
1839             Occupied(view) => {
1840                 assert_eq!(view.remove(), 30);
1841             }
1842         }
1843         assert_eq!(map.get(&3), None);
1844         assert_eq!(map.len(), 5);
1845
1846
1847         // Inexistent key (insert)
1848         match map.entry(10) {
1849             Occupied(_) => unreachable!(),
1850             Vacant(view) => {
1851                 assert_eq!(*view.insert(1000), 1000);
1852             }
1853         }
1854         assert_eq!(map.get(&10).unwrap(), &1000);
1855         assert_eq!(map.len(), 6);
1856     }
1857 }
1858
1859
1860
1861
1862
1863
1864 #[cfg(test)]
1865 mod bench {
1866     use prelude::*;
1867     use std::rand::{weak_rng, Rng};
1868     use test::{Bencher, black_box};
1869
1870     use super::BTreeMap;
1871     use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1872
1873     #[bench]
1874     pub fn insert_rand_100(b: &mut Bencher) {
1875         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1876         insert_rand_n(100, &mut m, b,
1877                       |m, i| { m.insert(i, 1); },
1878                       |m, i| { m.remove(&i); });
1879     }
1880
1881     #[bench]
1882     pub fn insert_rand_10_000(b: &mut Bencher) {
1883         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1884         insert_rand_n(10_000, &mut m, b,
1885                       |m, i| { m.insert(i, 1); },
1886                       |m, i| { m.remove(&i); });
1887     }
1888
1889     // Insert seq
1890     #[bench]
1891     pub fn insert_seq_100(b: &mut Bencher) {
1892         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1893         insert_seq_n(100, &mut m, b,
1894                      |m, i| { m.insert(i, 1); },
1895                      |m, i| { m.remove(&i); });
1896     }
1897
1898     #[bench]
1899     pub fn insert_seq_10_000(b: &mut Bencher) {
1900         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1901         insert_seq_n(10_000, &mut m, b,
1902                      |m, i| { m.insert(i, 1); },
1903                      |m, i| { m.remove(&i); });
1904     }
1905
1906     // Find rand
1907     #[bench]
1908     pub fn find_rand_100(b: &mut Bencher) {
1909         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1910         find_rand_n(100, &mut m, b,
1911                     |m, i| { m.insert(i, 1); },
1912                     |m, i| { m.get(&i); });
1913     }
1914
1915     #[bench]
1916     pub fn find_rand_10_000(b: &mut Bencher) {
1917         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1918         find_rand_n(10_000, &mut m, b,
1919                     |m, i| { m.insert(i, 1); },
1920                     |m, i| { m.get(&i); });
1921     }
1922
1923     // Find seq
1924     #[bench]
1925     pub fn find_seq_100(b: &mut Bencher) {
1926         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1927         find_seq_n(100, &mut m, b,
1928                    |m, i| { m.insert(i, 1); },
1929                    |m, i| { m.get(&i); });
1930     }
1931
1932     #[bench]
1933     pub fn find_seq_10_000(b: &mut Bencher) {
1934         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1935         find_seq_n(10_000, &mut m, b,
1936                    |m, i| { m.insert(i, 1); },
1937                    |m, i| { m.get(&i); });
1938     }
1939
1940     fn bench_iter(b: &mut Bencher, size: uint) {
1941         let mut map = BTreeMap::<uint, uint>::new();
1942         let mut rng = weak_rng();
1943
1944         for _ in 0..size {
1945             map.insert(rng.gen(), rng.gen());
1946         }
1947
1948         b.iter(|| {
1949             for entry in &map {
1950                 black_box(entry);
1951             }
1952         });
1953     }
1954
1955     #[bench]
1956     pub fn iter_20(b: &mut Bencher) {
1957         bench_iter(b, 20);
1958     }
1959
1960     #[bench]
1961     pub fn iter_1000(b: &mut Bencher) {
1962         bench_iter(b, 1000);
1963     }
1964
1965     #[bench]
1966     pub fn iter_100000(b: &mut Bencher) {
1967         bench_iter(b, 100000);
1968     }
1969 }