src/libcollections/btree/map.rs

   1 // Copyright 2015 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 use core::cmp::Ordering;
  12 use core::fmt::Debug;
  13 use core::hash::{Hash, Hasher};
  14 use core::iter::{FromIterator, Peekable};
  15 use core::marker::PhantomData;
  16 use core::ops::Index;
  17 use core::{fmt, intrinsics, mem, ptr};
  18
  19 use borrow::Borrow;
  20 use Bound::{self, Excluded, Included, Unbounded};
  21
  22 use super::node::{self, Handle, NodeRef, marker};
  23 use super::search;
  24
  25 use super::node::InsertResult::*;
  26 use super::node::ForceResult::*;
  27 use super::search::SearchResult::*;
  28 use self::UnderflowResult::*;
  29 use self::Entry::*;
  30
  31 /// A map based on a B-Tree.
  32 ///
  33 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
  34 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
  35 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
  36 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
  37 /// is done is *very* inefficient for modern computer architectures. In particular, every element
  38 /// is stored in its own individually heap-allocated node. This means that every single insertion
  39 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
  40 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
  41 /// the BST strategy.
  42 ///
  43 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
  44 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
  45 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
  46 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
  47 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
  48 /// the node using binary search. As a compromise, one could also perform a linear search
  49 /// that initially only checks every i<sup>th</sup> element for some choice of i.
  50 ///
  51 /// Currently, our implementation simply performs naive linear search. This provides excellent
  52 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
  53 /// would like to further explore choosing the optimal search strategy based on the choice of B,
  54 /// and possibly other factors. Using linear search, searching for a random element is expected
  55 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
  56 /// however, performance is excellent.
  57 ///
  58 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
  59 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
  60 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
  61 ///
  62 /// # Examples
  63 ///
  64 /// ```
  65 /// use std::collections::BTreeMap;
  66 ///
  67 /// // type inference lets us omit an explicit type signature (which
  68 /// // would be `BTreeMap<&str, &str>` in this example).
  69 /// let mut movie_reviews = BTreeMap::new();
  70 ///
  71 /// // review some movies.
  72 /// movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
  73 /// movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
  74 /// movie_reviews.insert("The Godfather",      "Very enjoyable.");
  75 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it alot.");
  76 ///
  77 /// // check for a specific one.
  78 /// if !movie_reviews.contains_key("Les Misérables") {
  79 ///     println!("We've got {} reviews, but Les Misérables ain't one.",
  80 ///              movie_reviews.len());
  81 /// }
  82 ///
  83 /// // oops, this review has a lot of spelling mistakes, let's delete it.
  84 /// movie_reviews.remove("The Blues Brothers");
  85 ///
  86 /// // look up the values associated with some keys.
  87 /// let to_find = ["Up!", "Office Space"];
  88 /// for book in &to_find {
  89 ///     match movie_reviews.get(book) {
  90 ///        Some(review) => println!("{}: {}", book, review),
  91 ///        None => println!("{} is unreviewed.", book)
  92 ///     }
  93 /// }
  94 ///
  95 /// // iterate over everything.
  96 /// for (movie, review) in &movie_reviews {
  97 ///     println!("{}: \"{}\"", movie, review);
  98 /// }
  99 /// ```
 100 ///
 101 /// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
 102 /// for more complex methods of getting, setting, updating and removing keys and
 103 /// their values:
 104 ///
 105 /// ```
 106 /// use std::collections::BTreeMap;
 107 ///
 108 /// // type inference lets us omit an explicit type signature (which
 109 /// // would be `BTreeMap<&str, u8>` in this example).
 110 /// let mut player_stats = BTreeMap::new();
 111 ///
 112 /// fn random_stat_buff() -> u8 {
 113 ///     // could actually return some random value here - let's just return
 114 ///     // some fixed value for now
 115 ///     42
 116 /// }
 117 ///
 118 /// // insert a key only if it doesn't already exist
 119 /// player_stats.entry("health").or_insert(100);
 120 ///
 121 /// // insert a key using a function that provides a new value only if it
 122 /// // doesn't already exist
 123 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
 124 ///
 125 /// // update a key, guarding against the key possibly not being set
 126 /// let stat = player_stats.entry("attack").or_insert(100);
 127 /// *stat += random_stat_buff();
 128 /// ```
 129 #[stable(feature = "rust1", since = "1.0.0")]
 130 pub struct BTreeMap<K, V> {
 131     root: node::Root<K, V>,
 132     length: usize,
 133 }
 134
 135 impl<K, V> Drop for BTreeMap<K, V> {
 136     #[unsafe_destructor_blind_to_params]
 137     fn drop(&mut self) {
 138         unsafe {
 139             for _ in ptr::read(self).into_iter() {
 140             }
 141         }
 142     }
 143 }
 144
 145 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
 146     fn clone(&self) -> BTreeMap<K, V> {
 147         fn clone_subtree<K: Clone, V: Clone>(node: node::NodeRef<marker::Immut,
 148                                                                  K,
 149                                                                  V,
 150                                                                  marker::LeafOrInternal>)
 151                                              -> BTreeMap<K, V> {
 152
 153             match node.force() {
 154                 Leaf(leaf) => {
 155                     let mut out_tree = BTreeMap {
 156                         root: node::Root::new_leaf(),
 157                         length: 0,
 158                     };
 159
 160                     {
 161                         let mut out_node = match out_tree.root.as_mut().force() {
 162                             Leaf(leaf) => leaf,
 163                             Internal(_) => unreachable!(),
 164                         };
 165
 166                         let mut in_edge = leaf.first_edge();
 167                         while let Ok(kv) = in_edge.right_kv() {
 168                             let (k, v) = kv.into_kv();
 169                             in_edge = kv.right_edge();
 170
 171                             out_node.push(k.clone(), v.clone());
 172                             out_tree.length += 1;
 173                         }
 174                     }
 175
 176                     out_tree
 177                 }
 178                 Internal(internal) => {
 179                     let mut out_tree = clone_subtree(internal.first_edge().descend());
 180
 181                     {
 182                         let mut out_node = out_tree.root.push_level();
 183                         let mut in_edge = internal.first_edge();
 184                         while let Ok(kv) = in_edge.right_kv() {
 185                             let (k, v) = kv.into_kv();
 186                             in_edge = kv.right_edge();
 187
 188                             let k = (*k).clone();
 189                             let v = (*v).clone();
 190                             let subtree = clone_subtree(in_edge.descend());
 191
 192                             // We can't destructure subtree directly
 193                             // because BTreeMap implements Drop
 194                             let (subroot, sublength) = unsafe {
 195                                 let root = ptr::read(&subtree.root);
 196                                 let length = subtree.length;
 197                                 mem::forget(subtree);
 198                                 (root, length)
 199                             };
 200
 201                             out_node.push(k, v, subroot);
 202                             out_tree.length += 1 + sublength;
 203                         }
 204                     }
 205
 206                     out_tree
 207                 }
 208             }
 209         }
 210
 211         clone_subtree(self.root.as_ref())
 212     }
 213 }
 214
 215 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 216     where K: Borrow<Q> + Ord,
 217           Q: Ord
 218 {
 219     type Key = K;
 220
 221     fn get(&self, key: &Q) -> Option<&K> {
 222         match search::search_tree(self.root.as_ref(), key) {
 223             Found(handle) => Some(handle.into_kv().0),
 224             GoDown(_) => None,
 225         }
 226     }
 227
 228     fn take(&mut self, key: &Q) -> Option<K> {
 229         match search::search_tree(self.root.as_mut(), key) {
 230             Found(handle) => {
 231                 Some(OccupiedEntry {
 232                          handle: handle,
 233                          length: &mut self.length,
 234                          _marker: PhantomData,
 235                      }
 236                      .remove_kv()
 237                      .0)
 238             }
 239             GoDown(_) => None,
 240         }
 241     }
 242
 243     fn replace(&mut self, key: K) -> Option<K> {
 244         match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
 245             Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
 246             GoDown(handle) => {
 247                 VacantEntry {
 248                     key: key,
 249                     handle: handle,
 250                     length: &mut self.length,
 251                     _marker: PhantomData,
 252                 }
 253                 .insert(());
 254                 None
 255             }
 256         }
 257     }
 258 }
 259
 260 /// An iterator over a BTreeMap's entries.
 261 #[stable(feature = "rust1", since = "1.0.0")]
 262 pub struct Iter<'a, K: 'a, V: 'a> {
 263     range: Range<'a, K, V>,
 264     length: usize,
 265 }
 266
 267 /// A mutable iterator over a BTreeMap's entries.
 268 #[stable(feature = "rust1", since = "1.0.0")]
 269 pub struct IterMut<'a, K: 'a, V: 'a> {
 270     range: RangeMut<'a, K, V>,
 271     length: usize,
 272 }
 273
 274 /// An owning iterator over a BTreeMap's entries.
 275 #[stable(feature = "rust1", since = "1.0.0")]
 276 pub struct IntoIter<K, V> {
 277     front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 278     back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 279     length: usize,
 280 }
 281
 282 /// An iterator over a BTreeMap's keys.
 283 #[stable(feature = "rust1", since = "1.0.0")]
 284 pub struct Keys<'a, K: 'a, V: 'a> {
 285     inner: Iter<'a, K, V>,
 286 }
 287
 288 /// An iterator over a BTreeMap's values.
 289 #[stable(feature = "rust1", since = "1.0.0")]
 290 pub struct Values<'a, K: 'a, V: 'a> {
 291     inner: Iter<'a, K, V>,
 292 }
 293
 294 /// A mutable iterator over a BTreeMap's values.
 295 #[stable(feature = "map_values_mut", since = "1.10.0")]
 296 pub struct ValuesMut<'a, K: 'a, V: 'a> {
 297     inner: IterMut<'a, K, V>,
 298 }
 299
 300 /// An iterator over a sub-range of BTreeMap's entries.
 301 pub struct Range<'a, K: 'a, V: 'a> {
 302     front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 303     back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 304 }
 305
 306 /// A mutable iterator over a sub-range of BTreeMap's entries.
 307 pub struct RangeMut<'a, K: 'a, V: 'a> {
 308     front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 309     back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 310
 311     // Be invariant in `K` and `V`
 312     _marker: PhantomData<&'a mut (K, V)>,
 313 }
 314
 315 /// A view into a single entry in a map, which may either be vacant or occupied.
 316 #[stable(feature = "rust1", since = "1.0.0")]
 317 pub enum Entry<'a, K: 'a, V: 'a> {
 318     /// A vacant Entry
 319     #[stable(feature = "rust1", since = "1.0.0")]
 320     Vacant(#[stable(feature = "rust1", since = "1.0.0")]
 321            VacantEntry<'a, K, V>),
 322
 323     /// An occupied Entry
 324     #[stable(feature = "rust1", since = "1.0.0")]
 325     Occupied(#[stable(feature = "rust1", since = "1.0.0")]
 326              OccupiedEntry<'a, K, V>),
 327 }
 328
 329 /// A vacant Entry.
 330 #[stable(feature = "rust1", since = "1.0.0")]
 331 pub struct VacantEntry<'a, K: 'a, V: 'a> {
 332     key: K,
 333     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 334     length: &'a mut usize,
 335
 336     // Be invariant in `K` and `V`
 337     _marker: PhantomData<&'a mut (K, V)>,
 338 }
 339
 340 /// An occupied Entry.
 341 #[stable(feature = "rust1", since = "1.0.0")]
 342 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
 343     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
 344
 345     length: &'a mut usize,
 346
 347     // Be invariant in `K` and `V`
 348     _marker: PhantomData<&'a mut (K, V)>,
 349 }
 350
 351 // An iterator for merging two sorted sequences into one
 352 struct MergeIter<K, V, I: Iterator<Item = (K, V)>> {
 353     left: Peekable<I>,
 354     right: Peekable<I>,
 355 }
 356
 357 impl<K: Ord, V> BTreeMap<K, V> {
 358     /// Makes a new empty BTreeMap with a reasonable choice for B.
 359     ///
 360     /// # Examples
 361     ///
 362     /// Basic usage:
 363     ///
 364     /// ```
 365     /// use std::collections::BTreeMap;
 366     ///
 367     /// let mut map = BTreeMap::new();
 368     ///
 369     /// // entries can now be inserted into the empty map
 370     /// map.insert(1, "a");
 371     /// ```
 372     #[stable(feature = "rust1", since = "1.0.0")]
 373     pub fn new() -> BTreeMap<K, V> {
 374         BTreeMap {
 375             root: node::Root::new_leaf(),
 376             length: 0,
 377         }
 378     }
 379
 380     /// Clears the map, removing all values.
 381     ///
 382     /// # Examples
 383     ///
 384     /// Basic usage:
 385     ///
 386     /// ```
 387     /// use std::collections::BTreeMap;
 388     ///
 389     /// let mut a = BTreeMap::new();
 390     /// a.insert(1, "a");
 391     /// a.clear();
 392     /// assert!(a.is_empty());
 393     /// ```
 394     #[stable(feature = "rust1", since = "1.0.0")]
 395     pub fn clear(&mut self) {
 396         // FIXME(gereeter) .clear() allocates
 397         *self = BTreeMap::new();
 398     }
 399
 400     /// Returns a reference to the value corresponding to the key.
 401     ///
 402     /// The key may be any borrowed form of the map's key type, but the ordering
 403     /// on the borrowed form *must* match the ordering on the key type.
 404     ///
 405     /// # Examples
 406     ///
 407     /// Basic usage:
 408     ///
 409     /// ```
 410     /// use std::collections::BTreeMap;
 411     ///
 412     /// let mut map = BTreeMap::new();
 413     /// map.insert(1, "a");
 414     /// assert_eq!(map.get(&1), Some(&"a"));
 415     /// assert_eq!(map.get(&2), None);
 416     /// ```
 417     #[stable(feature = "rust1", since = "1.0.0")]
 418     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
 419         where K: Borrow<Q>,
 420               Q: Ord
 421     {
 422         match search::search_tree(self.root.as_ref(), key) {
 423             Found(handle) => Some(handle.into_kv().1),
 424             GoDown(_) => None,
 425         }
 426     }
 427
 428     /// Returns true if the map contains a value for the specified key.
 429     ///
 430     /// The key may be any borrowed form of the map's key type, but the ordering
 431     /// on the borrowed form *must* match the ordering on the key type.
 432     ///
 433     /// # Examples
 434     ///
 435     /// Basic usage:
 436     ///
 437     /// ```
 438     /// use std::collections::BTreeMap;
 439     ///
 440     /// let mut map = BTreeMap::new();
 441     /// map.insert(1, "a");
 442     /// assert_eq!(map.contains_key(&1), true);
 443     /// assert_eq!(map.contains_key(&2), false);
 444     /// ```
 445     #[stable(feature = "rust1", since = "1.0.0")]
 446     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
 447         where K: Borrow<Q>,
 448               Q: Ord
 449     {
 450         self.get(key).is_some()
 451     }
 452
 453     /// Returns a mutable reference to the value corresponding to the key.
 454     ///
 455     /// The key may be any borrowed form of the map's key type, but the ordering
 456     /// on the borrowed form *must* match the ordering on the key type.
 457     ///
 458     /// # Examples
 459     ///
 460     /// Basic usage:
 461     ///
 462     /// ```
 463     /// use std::collections::BTreeMap;
 464     ///
 465     /// let mut map = BTreeMap::new();
 466     /// map.insert(1, "a");
 467     /// if let Some(x) = map.get_mut(&1) {
 468     ///     *x = "b";
 469     /// }
 470     /// assert_eq!(map[&1], "b");
 471     /// ```
 472     // See `get` for implementation notes, this is basically a copy-paste with mut's added
 473     #[stable(feature = "rust1", since = "1.0.0")]
 474     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
 475         where K: Borrow<Q>,
 476               Q: Ord
 477     {
 478         match search::search_tree(self.root.as_mut(), key) {
 479             Found(handle) => Some(handle.into_kv_mut().1),
 480             GoDown(_) => None,
 481         }
 482     }
 483
 484     /// Inserts a key-value pair into the map.
 485     ///
 486     /// If the map did not have this key present, `None` is returned.
 487     ///
 488     /// If the map did have this key present, the value is updated, and the old
 489     /// value is returned. The key is not updated, though; this matters for
 490     /// types that can be `==` without being identical. See the [module-level
 491     /// documentation] for more.
 492     ///
 493     /// [module-level documentation]: index.html#insert-and-complex-keys
 494     ///
 495     /// # Examples
 496     ///
 497     /// Basic usage:
 498     ///
 499     /// ```
 500     /// use std::collections::BTreeMap;
 501     ///
 502     /// let mut map = BTreeMap::new();
 503     /// assert_eq!(map.insert(37, "a"), None);
 504     /// assert_eq!(map.is_empty(), false);
 505     ///
 506     /// map.insert(37, "b");
 507     /// assert_eq!(map.insert(37, "c"), Some("b"));
 508     /// assert_eq!(map[&37], "c");
 509     /// ```
 510     #[stable(feature = "rust1", since = "1.0.0")]
 511     pub fn insert(&mut self, key: K, value: V) -> Option<V> {
 512         match self.entry(key) {
 513             Occupied(mut entry) => Some(entry.insert(value)),
 514             Vacant(entry) => {
 515                 entry.insert(value);
 516                 None
 517             }
 518         }
 519     }
 520
 521     /// Removes a key from the map, returning the value at the key if the key
 522     /// was previously in the map.
 523     ///
 524     /// The key may be any borrowed form of the map's key type, but the ordering
 525     /// on the borrowed form *must* match the ordering on the key type.
 526     ///
 527     /// # Examples
 528     ///
 529     /// Basic usage:
 530     ///
 531     /// ```
 532     /// use std::collections::BTreeMap;
 533     ///
 534     /// let mut map = BTreeMap::new();
 535     /// map.insert(1, "a");
 536     /// assert_eq!(map.remove(&1), Some("a"));
 537     /// assert_eq!(map.remove(&1), None);
 538     /// ```
 539     #[stable(feature = "rust1", since = "1.0.0")]
 540     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
 541         where K: Borrow<Q>,
 542               Q: Ord
 543     {
 544         match search::search_tree(self.root.as_mut(), key) {
 545             Found(handle) => {
 546                 Some(OccupiedEntry {
 547                          handle: handle,
 548                          length: &mut self.length,
 549                          _marker: PhantomData,
 550                      }
 551                      .remove())
 552             }
 553             GoDown(_) => None,
 554         }
 555     }
 556
 557     /// Moves all elements from `other` into `Self`, leaving `other` empty.
 558     ///
 559     /// # Examples
 560     ///
 561     /// ```
 562     /// #![feature(btree_append)]
 563     /// use std::collections::BTreeMap;
 564     ///
 565     /// let mut a = BTreeMap::new();
 566     /// a.insert(1, "a");
 567     /// a.insert(2, "b");
 568     /// a.insert(3, "c");
 569     ///
 570     /// let mut b = BTreeMap::new();
 571     /// b.insert(3, "d");
 572     /// b.insert(4, "e");
 573     /// b.insert(5, "f");
 574     ///
 575     /// a.append(&mut b);
 576     ///
 577     /// assert_eq!(a.len(), 5);
 578     /// assert_eq!(b.len(), 0);
 579     ///
 580     /// assert_eq!(a[&1], "a");
 581     /// assert_eq!(a[&2], "b");
 582     /// assert_eq!(a[&3], "d");
 583     /// assert_eq!(a[&4], "e");
 584     /// assert_eq!(a[&5], "f");
 585     /// ```
 586     #[unstable(feature = "btree_append", reason = "recently added as part of collections reform 2",
 587                issue = "19986")]
 588     pub fn append(&mut self, other: &mut Self) {
 589         // Do we have to append anything at all?
 590         if other.len() == 0 {
 591             return;
 592         }
 593
 594         // We can just swap `self` and `other` if `self` is empty.
 595         if self.len() == 0 {
 596             mem::swap(self, other);
 597             return;
 598         }
 599
 600         // First, we merge `self` and `other` into a sorted sequence in linear time.
 601         let self_iter = mem::replace(self, BTreeMap::new()).into_iter();
 602         let other_iter = mem::replace(other, BTreeMap::new()).into_iter();
 603         let iter = MergeIter {
 604             left: self_iter.peekable(),
 605             right: other_iter.peekable(),
 606         };
 607
 608         // Second, we build a tree from the sorted sequence in linear time.
 609         self.from_sorted_iter(iter);
 610         self.fix_right_edge();
 611     }
 612
 613     /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
 614     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
 615     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
 616     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
 617     ///
 618     /// # Examples
 619     ///
 620     /// Basic usage:
 621     ///
 622     /// ```
 623     /// #![feature(btree_range, collections_bound)]
 624     ///
 625     /// use std::collections::BTreeMap;
 626     /// use std::collections::Bound::{Included, Unbounded};
 627     ///
 628     /// let mut map = BTreeMap::new();
 629     /// map.insert(3, "a");
 630     /// map.insert(5, "b");
 631     /// map.insert(8, "c");
 632     /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
 633     ///     println!("{}: {}", key, value);
 634     /// }
 635     /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
 636     /// ```
 637     #[unstable(feature = "btree_range",
 638                reason = "matches collection reform specification, waiting for dust to settle",
 639                issue = "27787")]
 640     pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
 641                                                        min: Bound<&Min>,
 642                                                        max: Bound<&Max>)
 643                                                        -> Range<K, V>
 644         where K: Borrow<Min> + Borrow<Max>
 645     {
 646         let front = match min {
 647             Included(key) => {
 648                 match search::search_tree(self.root.as_ref(), key) {
 649                     Found(kv_handle) => {
 650                         match kv_handle.left_edge().force() {
 651                             Leaf(bottom) => bottom,
 652                             Internal(internal) => last_leaf_edge(internal.descend()),
 653                         }
 654                     }
 655                     GoDown(bottom) => bottom,
 656                 }
 657             }
 658             Excluded(key) => {
 659                 match search::search_tree(self.root.as_ref(), key) {
 660                     Found(kv_handle) => {
 661                         match kv_handle.right_edge().force() {
 662                             Leaf(bottom) => bottom,
 663                             Internal(internal) => first_leaf_edge(internal.descend()),
 664                         }
 665                     }
 666                     GoDown(bottom) => bottom,
 667                 }
 668             }
 669             Unbounded => first_leaf_edge(self.root.as_ref()),
 670         };
 671
 672         let back = match max {
 673             Included(key) => {
 674                 match search::search_tree(self.root.as_ref(), key) {
 675                     Found(kv_handle) => {
 676                         match kv_handle.right_edge().force() {
 677                             Leaf(bottom) => bottom,
 678                             Internal(internal) => first_leaf_edge(internal.descend()),
 679                         }
 680                     }
 681                     GoDown(bottom) => bottom,
 682                 }
 683             }
 684             Excluded(key) => {
 685                 match search::search_tree(self.root.as_ref(), key) {
 686                     Found(kv_handle) => {
 687                         match kv_handle.left_edge().force() {
 688                             Leaf(bottom) => bottom,
 689                             Internal(internal) => last_leaf_edge(internal.descend()),
 690                         }
 691                     }
 692                     GoDown(bottom) => bottom,
 693                 }
 694             }
 695             Unbounded => last_leaf_edge(self.root.as_ref()),
 696         };
 697
 698         Range {
 699             front: front,
 700             back: back,
 701         }
 702     }
 703
 704     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
 705     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
 706     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
 707     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
 708     ///
 709     /// # Examples
 710     ///
 711     /// Basic usage:
 712     ///
 713     /// ```
 714     /// #![feature(btree_range, collections_bound)]
 715     ///
 716     /// use std::collections::BTreeMap;
 717     /// use std::collections::Bound::{Included, Excluded};
 718     ///
 719     /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
 720     ///                                                                       .map(|&s| (s, 0))
 721     ///                                                                       .collect();
 722     /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
 723     ///     *balance += 100;
 724     /// }
 725     /// for (name, balance) in &map {
 726     ///     println!("{} => {}", name, balance);
 727     /// }
 728     /// ```
 729     #[unstable(feature = "btree_range",
 730                reason = "matches collection reform specification, waiting for dust to settle",
 731                issue = "27787")]
 732     pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
 733                                                            min: Bound<&Min>,
 734                                                            max: Bound<&Max>)
 735                                                            -> RangeMut<K, V>
 736         where K: Borrow<Min> + Borrow<Max>
 737     {
 738         let root1 = self.root.as_mut();
 739         let root2 = unsafe { ptr::read(&root1) };
 740
 741         let front = match min {
 742             Included(key) => {
 743                 match search::search_tree(root1, key) {
 744                     Found(kv_handle) => {
 745                         match kv_handle.left_edge().force() {
 746                             Leaf(bottom) => bottom,
 747                             Internal(internal) => last_leaf_edge(internal.descend()),
 748                         }
 749                     }
 750                     GoDown(bottom) => bottom,
 751                 }
 752             }
 753             Excluded(key) => {
 754                 match search::search_tree(root1, key) {
 755                     Found(kv_handle) => {
 756                         match kv_handle.right_edge().force() {
 757                             Leaf(bottom) => bottom,
 758                             Internal(internal) => first_leaf_edge(internal.descend()),
 759                         }
 760                     }
 761                     GoDown(bottom) => bottom,
 762                 }
 763             }
 764             Unbounded => first_leaf_edge(root1),
 765         };
 766
 767         let back = match max {
 768             Included(key) => {
 769                 match search::search_tree(root2, key) {
 770                     Found(kv_handle) => {
 771                         match kv_handle.right_edge().force() {
 772                             Leaf(bottom) => bottom,
 773                             Internal(internal) => first_leaf_edge(internal.descend()),
 774                         }
 775                     }
 776                     GoDown(bottom) => bottom,
 777                 }
 778             }
 779             Excluded(key) => {
 780                 match search::search_tree(root2, key) {
 781                     Found(kv_handle) => {
 782                         match kv_handle.left_edge().force() {
 783                             Leaf(bottom) => bottom,
 784                             Internal(internal) => last_leaf_edge(internal.descend()),
 785                         }
 786                     }
 787                     GoDown(bottom) => bottom,
 788                 }
 789             }
 790             Unbounded => last_leaf_edge(root2),
 791         };
 792
 793         RangeMut {
 794             front: front,
 795             back: back,
 796             _marker: PhantomData,
 797         }
 798     }
 799
 800     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 801     ///
 802     /// # Examples
 803     ///
 804     /// Basic usage:
 805     ///
 806     /// ```
 807     /// use std::collections::BTreeMap;
 808     ///
 809     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
 810     ///
 811     /// // count the number of occurrences of letters in the vec
 812     /// for x in vec!["a","b","a","c","a","b"] {
 813     ///     *count.entry(x).or_insert(0) += 1;
 814     /// }
 815     ///
 816     /// assert_eq!(count["a"], 3);
 817     /// ```
 818     #[stable(feature = "rust1", since = "1.0.0")]
 819     pub fn entry(&mut self, key: K) -> Entry<K, V> {
 820         match search::search_tree(self.root.as_mut(), &key) {
 821             Found(handle) => {
 822                 Occupied(OccupiedEntry {
 823                     handle: handle,
 824                     length: &mut self.length,
 825                     _marker: PhantomData,
 826                 })
 827             }
 828             GoDown(handle) => {
 829                 Vacant(VacantEntry {
 830                     key: key,
 831                     handle: handle,
 832                     length: &mut self.length,
 833                     _marker: PhantomData,
 834                 })
 835             }
 836         }
 837     }
 838
 839     fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) {
 840         let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node();
 841         // Iterate through all key-value pairs, pushing them into nodes at the right level.
 842         for (key, value) in iter {
 843             // Try to push key-value pair into the current leaf node.
 844             if cur_node.len() < node::CAPACITY {
 845                 cur_node.push(key, value);
 846             } else {
 847                 // No space left, go up and push there.
 848                 let mut open_node;
 849                 let mut test_node = cur_node.forget_type();
 850                 loop {
 851                     match test_node.ascend() {
 852                         Ok(parent) => {
 853                             let parent = parent.into_node();
 854                             if parent.len() < node::CAPACITY {
 855                                 // Found a node with space left, push here.
 856                                 open_node = parent;
 857                                 break;
 858                             } else {
 859                                 // Go up again.
 860                                 test_node = parent.forget_type();
 861                             }
 862                         }
 863                         Err(node) => {
 864                             // We are at the top, create a new root node and push there.
 865                             open_node = node.into_root_mut().push_level();
 866                             break;
 867                         }
 868                     }
 869                 }
 870
 871                 // Push key-value pair and new right subtree.
 872                 let tree_height = open_node.height() - 1;
 873                 let mut right_tree = node::Root::new_leaf();
 874                 for _ in 0..tree_height {
 875                     right_tree.push_level();
 876                 }
 877                 open_node.push(key, value, right_tree);
 878
 879                 // Go down to the right-most leaf again.
 880                 cur_node = last_leaf_edge(open_node.forget_type()).into_node();
 881             }
 882
 883             self.length += 1;
 884         }
 885     }
 886
 887     fn fix_right_edge(&mut self) {
 888         // Handle underfull nodes, start from the top.
 889         let mut cur_node = self.root.as_mut();
 890         while let Internal(internal) = cur_node.force() {
 891             // Check if right-most child is underfull.
 892             let mut last_edge = internal.last_edge();
 893             let right_child_len = last_edge.reborrow().descend().len();
 894             if right_child_len < node::MIN_LEN {
 895                 // We need to steal.
 896                 let mut last_kv = match last_edge.left_kv() {
 897                     Ok(left) => left,
 898                     Err(_) => unreachable!(),
 899                 };
 900                 last_kv.bulk_steal_left(node::MIN_LEN - right_child_len);
 901                 last_edge = last_kv.right_edge();
 902             }
 903
 904             // Go further down.
 905             cur_node = last_edge.descend();
 906         }
 907     }
 908
 909     /// Splits the collection into two at the given key. Returns everything after the given key,
 910     /// including the key.
 911     ///
 912     /// # Examples
 913     ///
 914     /// Basic usage:
 915     ///
 916     /// ```
 917     /// #![feature(btree_split_off)]
 918     /// use std::collections::BTreeMap;
 919     ///
 920     /// let mut a = BTreeMap::new();
 921     /// a.insert(1, "a");
 922     /// a.insert(2, "b");
 923     /// a.insert(3, "c");
 924     /// a.insert(17, "d");
 925     /// a.insert(41, "e");
 926     ///
 927     /// let b = a.split_off(&3);
 928     ///
 929     /// assert_eq!(a.len(), 2);
 930     /// assert_eq!(b.len(), 3);
 931     ///
 932     /// assert_eq!(a[&1], "a");
 933     /// assert_eq!(a[&2], "b");
 934     ///
 935     /// assert_eq!(b[&3], "c");
 936     /// assert_eq!(b[&17], "d");
 937     /// assert_eq!(b[&41], "e");
 938     /// ```
 939     #[unstable(feature = "btree_split_off",
 940                reason = "recently added as part of collections reform 2",
 941                issue = "19986")]
 942     pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
 943         where K: Borrow<Q>
 944     {
 945         if self.is_empty() {
 946             return Self::new();
 947         }
 948
 949         let total_num = self.len();
 950
 951         let mut right = Self::new();
 952         for _ in 0..(self.root.as_ref().height()) {
 953             right.root.push_level();
 954         }
 955
 956         {
 957             let mut left_node = self.root.as_mut();
 958             let mut right_node = right.root.as_mut();
 959
 960             loop {
 961                 let mut split_edge = match search::search_node(left_node, key) {
 962                     // key is going to the right tree
 963                     Found(handle) => handle.left_edge(),
 964                     GoDown(handle) => handle,
 965                 };
 966
 967                 split_edge.move_suffix(&mut right_node);
 968
 969                 match (split_edge.force(), right_node.force()) {
 970                     (Internal(edge), Internal(node)) => {
 971                         left_node = edge.descend();
 972                         right_node = node.first_edge().descend();
 973                     }
 974                     (Leaf(_), Leaf(_)) => {
 975                         break;
 976                     }
 977                     _ => {
 978                         unreachable!();
 979                     }
 980                 }
 981             }
 982         }
 983
 984         self.fix_right_border();
 985         right.fix_left_border();
 986
 987         if self.root.as_ref().height() < right.root.as_ref().height() {
 988             self.recalc_length();
 989             right.length = total_num - self.len();
 990         } else {
 991             right.recalc_length();
 992             self.length = total_num - right.len();
 993         }
 994
 995         right
 996     }
 997
 998     /// Calculates the number of elements if it is incorrect.
 999     fn recalc_length(&mut self) {
1000         fn dfs<K, V>(node: NodeRef<marker::Immut, K, V, marker::LeafOrInternal>) -> usize {
1001             let mut res = node.len();
1002
1003             if let Internal(node) = node.force() {
1004                 let mut edge = node.first_edge();
1005                 loop {
1006                     res += dfs(edge.reborrow().descend());
1007                     match edge.right_kv() {
1008                         Ok(right_kv) => {
1009                             edge = right_kv.right_edge();
1010                         }
1011                         Err(_) => {
1012                             break;
1013                         }
1014                     }
1015                 }
1016             }
1017
1018             res
1019         }
1020
1021         self.length = dfs(self.root.as_ref());
1022     }
1023
1024     /// Removes empty levels on the top.
1025     fn fix_top(&mut self) {
1026         loop {
1027             {
1028                 let node = self.root.as_ref();
1029                 if node.height() == 0 || node.len() > 0 {
1030                     break;
1031                 }
1032             }
1033             self.root.pop_level();
1034         }
1035     }
1036
1037     fn fix_right_border(&mut self) {
1038         self.fix_top();
1039
1040         {
1041             let mut cur_node = self.root.as_mut();
1042
1043             while let Internal(node) = cur_node.force() {
1044                 let mut last_kv = node.last_kv();
1045
1046                 if last_kv.can_merge() {
1047                     cur_node = last_kv.merge().descend();
1048                 } else {
1049                     let right_len = last_kv.reborrow().right_edge().descend().len();
1050                     // `MINLEN + 1` to avoid readjust if merge happens on the next level.
1051                     if right_len < node::MIN_LEN + 1 {
1052                         last_kv.bulk_steal_left(node::MIN_LEN + 1 - right_len);
1053                     }
1054                     cur_node = last_kv.right_edge().descend();
1055                 }
1056             }
1057         }
1058
1059         self.fix_top();
1060     }
1061
1062     /// The symmetric clone of `fix_right_border`.
1063     fn fix_left_border(&mut self) {
1064         self.fix_top();
1065
1066         {
1067             let mut cur_node = self.root.as_mut();
1068
1069             while let Internal(node) = cur_node.force() {
1070                 let mut first_kv = node.first_kv();
1071
1072                 if first_kv.can_merge() {
1073                     cur_node = first_kv.merge().descend();
1074                 } else {
1075                     let left_len = first_kv.reborrow().left_edge().descend().len();
1076                     if left_len < node::MIN_LEN + 1 {
1077                         first_kv.bulk_steal_right(node::MIN_LEN + 1 - left_len);
1078                     }
1079                     cur_node = first_kv.left_edge().descend();
1080                 }
1081             }
1082         }
1083
1084         self.fix_top();
1085     }
1086 }
1087
1088 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
1089     type Item = (&'a K, &'a V);
1090     type IntoIter = Iter<'a, K, V>;
1091
1092     fn into_iter(self) -> Iter<'a, K, V> {
1093         self.iter()
1094     }
1095 }
1096
1097 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
1098     type Item = (&'a K, &'a V);
1099
1100     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1101         if self.length == 0 {
1102             None
1103         } else {
1104             self.length -= 1;
1105             unsafe { Some(self.range.next_unchecked()) }
1106         }
1107     }
1108
1109     fn size_hint(&self) -> (usize, Option<usize>) {
1110         (self.length, Some(self.length))
1111     }
1112 }
1113
1114 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
1115     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1116         if self.length == 0 {
1117             None
1118         } else {
1119             self.length -= 1;
1120             unsafe { Some(self.range.next_back_unchecked()) }
1121         }
1122     }
1123 }
1124
1125 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
1126     fn len(&self) -> usize {
1127         self.length
1128     }
1129 }
1130
1131 impl<'a, K, V> Clone for Iter<'a, K, V> {
1132     fn clone(&self) -> Iter<'a, K, V> {
1133         Iter {
1134             range: self.range.clone(),
1135             length: self.length,
1136         }
1137     }
1138 }
1139
1140 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
1141     type Item = (&'a K, &'a mut V);
1142     type IntoIter = IterMut<'a, K, V>;
1143
1144     fn into_iter(self) -> IterMut<'a, K, V> {
1145         self.iter_mut()
1146     }
1147 }
1148
1149 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
1150     type Item = (&'a K, &'a mut V);
1151
1152     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1153         if self.length == 0 {
1154             None
1155         } else {
1156             self.length -= 1;
1157             unsafe { Some(self.range.next_unchecked()) }
1158         }
1159     }
1160
1161     fn size_hint(&self) -> (usize, Option<usize>) {
1162         (self.length, Some(self.length))
1163     }
1164 }
1165
1166 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
1167     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1168         if self.length == 0 {
1169             None
1170         } else {
1171             self.length -= 1;
1172             unsafe { Some(self.range.next_back_unchecked()) }
1173         }
1174     }
1175 }
1176
1177 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
1178     fn len(&self) -> usize {
1179         self.length
1180     }
1181 }
1182
1183 impl<K, V> IntoIterator for BTreeMap<K, V> {
1184     type Item = (K, V);
1185     type IntoIter = IntoIter<K, V>;
1186
1187     fn into_iter(self) -> IntoIter<K, V> {
1188         let root1 = unsafe { ptr::read(&self.root).into_ref() };
1189         let root2 = unsafe { ptr::read(&self.root).into_ref() };
1190         let len = self.length;
1191         mem::forget(self);
1192
1193         IntoIter {
1194             front: first_leaf_edge(root1),
1195             back: last_leaf_edge(root2),
1196             length: len,
1197         }
1198     }
1199 }
1200
1201 impl<K, V> Drop for IntoIter<K, V> {
1202     fn drop(&mut self) {
1203         for _ in &mut *self {
1204         }
1205         unsafe {
1206             let leaf_node = ptr::read(&self.front).into_node();
1207             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
1208                 let mut cur_node = first_parent.into_node();
1209                 while let Some(parent) = cur_node.deallocate_and_ascend() {
1210                     cur_node = parent.into_node()
1211                 }
1212             }
1213         }
1214     }
1215 }
1216
1217 impl<K, V> Iterator for IntoIter<K, V> {
1218     type Item = (K, V);
1219
1220     fn next(&mut self) -> Option<(K, V)> {
1221         if self.length == 0 {
1222             return None;
1223         } else {
1224             self.length -= 1;
1225         }
1226
1227         let handle = unsafe { ptr::read(&self.front) };
1228
1229         let mut cur_handle = match handle.right_kv() {
1230             Ok(kv) => {
1231                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1232                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1233                 self.front = kv.right_edge();
1234                 return Some((k, v));
1235             }
1236             Err(last_edge) => unsafe {
1237                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
1238             },
1239         };
1240
1241         loop {
1242             match cur_handle.right_kv() {
1243                 Ok(kv) => {
1244                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1245                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1246                     self.front = first_leaf_edge(kv.right_edge().descend());
1247                     return Some((k, v));
1248                 }
1249                 Err(last_edge) => unsafe {
1250                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
1251                 },
1252             }
1253         }
1254     }
1255
1256     fn size_hint(&self) -> (usize, Option<usize>) {
1257         (self.length, Some(self.length))
1258     }
1259 }
1260
1261 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1262     fn next_back(&mut self) -> Option<(K, V)> {
1263         if self.length == 0 {
1264             return None;
1265         } else {
1266             self.length -= 1;
1267         }
1268
1269         let handle = unsafe { ptr::read(&self.back) };
1270
1271         let mut cur_handle = match handle.left_kv() {
1272             Ok(kv) => {
1273                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1274                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1275                 self.back = kv.left_edge();
1276                 return Some((k, v));
1277             }
1278             Err(last_edge) => unsafe {
1279                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
1280             },
1281         };
1282
1283         loop {
1284             match cur_handle.left_kv() {
1285                 Ok(kv) => {
1286                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1287                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1288                     self.back = last_leaf_edge(kv.left_edge().descend());
1289                     return Some((k, v));
1290                 }
1291                 Err(last_edge) => unsafe {
1292                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
1293                 },
1294             }
1295         }
1296     }
1297 }
1298
1299 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1300     fn len(&self) -> usize {
1301         self.length
1302     }
1303 }
1304
1305 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1306     type Item = &'a K;
1307
1308     fn next(&mut self) -> Option<&'a K> {
1309         self.inner.next().map(|(k, _)| k)
1310     }
1311
1312     fn size_hint(&self) -> (usize, Option<usize>) {
1313         self.inner.size_hint()
1314     }
1315 }
1316
1317 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1318     fn next_back(&mut self) -> Option<&'a K> {
1319         self.inner.next_back().map(|(k, _)| k)
1320     }
1321 }
1322
1323 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1324     fn len(&self) -> usize {
1325         self.inner.len()
1326     }
1327 }
1328
1329 impl<'a, K, V> Clone for Keys<'a, K, V> {
1330     fn clone(&self) -> Keys<'a, K, V> {
1331         Keys { inner: self.inner.clone() }
1332     }
1333 }
1334
1335 impl<'a, K, V> Iterator for Values<'a, K, V> {
1336     type Item = &'a V;
1337
1338     fn next(&mut self) -> Option<&'a V> {
1339         self.inner.next().map(|(_, v)| v)
1340     }
1341
1342     fn size_hint(&self) -> (usize, Option<usize>) {
1343         self.inner.size_hint()
1344     }
1345 }
1346
1347 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1348     fn next_back(&mut self) -> Option<&'a V> {
1349         self.inner.next_back().map(|(_, v)| v)
1350     }
1351 }
1352
1353 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1354     fn len(&self) -> usize {
1355         self.inner.len()
1356     }
1357 }
1358
1359 impl<'a, K, V> Clone for Values<'a, K, V> {
1360     fn clone(&self) -> Values<'a, K, V> {
1361         Values { inner: self.inner.clone() }
1362     }
1363 }
1364
1365 impl<'a, K, V> Iterator for Range<'a, K, V> {
1366     type Item = (&'a K, &'a V);
1367
1368     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1369         if self.front == self.back {
1370             None
1371         } else {
1372             unsafe { Some(self.next_unchecked()) }
1373         }
1374     }
1375 }
1376
1377 #[stable(feature = "map_values_mut", since = "1.10.0")]
1378 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1379     type Item = &'a mut V;
1380
1381     fn next(&mut self) -> Option<&'a mut V> {
1382         self.inner.next().map(|(_, v)| v)
1383     }
1384
1385     fn size_hint(&self) -> (usize, Option<usize>) {
1386         self.inner.size_hint()
1387     }
1388 }
1389
1390 #[stable(feature = "map_values_mut", since = "1.10.0")]
1391 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1392     fn next_back(&mut self) -> Option<&'a mut V> {
1393         self.inner.next_back().map(|(_, v)| v)
1394     }
1395 }
1396
1397 #[stable(feature = "map_values_mut", since = "1.10.0")]
1398 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
1399     fn len(&self) -> usize {
1400         self.inner.len()
1401     }
1402 }
1403
1404 impl<'a, K, V> Range<'a, K, V> {
1405     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
1406         let handle = self.front;
1407
1408         let mut cur_handle = match handle.right_kv() {
1409             Ok(kv) => {
1410                 let ret = kv.into_kv();
1411                 self.front = kv.right_edge();
1412                 return ret;
1413             }
1414             Err(last_edge) => {
1415                 let next_level = last_edge.into_node().ascend().ok();
1416                 unwrap_unchecked(next_level)
1417             }
1418         };
1419
1420         loop {
1421             match cur_handle.right_kv() {
1422                 Ok(kv) => {
1423                     let ret = kv.into_kv();
1424                     self.front = first_leaf_edge(kv.right_edge().descend());
1425                     return ret;
1426                 }
1427                 Err(last_edge) => {
1428                     let next_level = last_edge.into_node().ascend().ok();
1429                     cur_handle = unwrap_unchecked(next_level);
1430                 }
1431             }
1432         }
1433     }
1434 }
1435
1436 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1437     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1438         if self.front == self.back {
1439             None
1440         } else {
1441             unsafe { Some(self.next_back_unchecked()) }
1442         }
1443     }
1444 }
1445
1446 impl<'a, K, V> Range<'a, K, V> {
1447     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
1448         let handle = self.back;
1449
1450         let mut cur_handle = match handle.left_kv() {
1451             Ok(kv) => {
1452                 let ret = kv.into_kv();
1453                 self.back = kv.left_edge();
1454                 return ret;
1455             }
1456             Err(last_edge) => {
1457                 let next_level = last_edge.into_node().ascend().ok();
1458                 unwrap_unchecked(next_level)
1459             }
1460         };
1461
1462         loop {
1463             match cur_handle.left_kv() {
1464                 Ok(kv) => {
1465                     let ret = kv.into_kv();
1466                     self.back = last_leaf_edge(kv.left_edge().descend());
1467                     return ret;
1468                 }
1469                 Err(last_edge) => {
1470                     let next_level = last_edge.into_node().ascend().ok();
1471                     cur_handle = unwrap_unchecked(next_level);
1472                 }
1473             }
1474         }
1475     }
1476 }
1477
1478 impl<'a, K, V> Clone for Range<'a, K, V> {
1479     fn clone(&self) -> Range<'a, K, V> {
1480         Range {
1481             front: self.front,
1482             back: self.back,
1483         }
1484     }
1485 }
1486
1487 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1488     type Item = (&'a K, &'a mut V);
1489
1490     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1491         if self.front == self.back {
1492             None
1493         } else {
1494             unsafe { Some(self.next_unchecked()) }
1495         }
1496     }
1497 }
1498
1499 impl<'a, K, V> RangeMut<'a, K, V> {
1500     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1501         let handle = ptr::read(&self.front);
1502
1503         let mut cur_handle = match handle.right_kv() {
1504             Ok(kv) => {
1505                 let (k, v) = ptr::read(&kv).into_kv_mut();
1506                 self.front = kv.right_edge();
1507                 return (k, v);
1508             }
1509             Err(last_edge) => {
1510                 let next_level = last_edge.into_node().ascend().ok();
1511                 unwrap_unchecked(next_level)
1512             }
1513         };
1514
1515         loop {
1516             match cur_handle.right_kv() {
1517                 Ok(kv) => {
1518                     let (k, v) = ptr::read(&kv).into_kv_mut();
1519                     self.front = first_leaf_edge(kv.right_edge().descend());
1520                     return (k, v);
1521                 }
1522                 Err(last_edge) => {
1523                     let next_level = last_edge.into_node().ascend().ok();
1524                     cur_handle = unwrap_unchecked(next_level);
1525                 }
1526             }
1527         }
1528     }
1529 }
1530
1531 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1532     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1533         if self.front == self.back {
1534             None
1535         } else {
1536             unsafe { Some(self.next_back_unchecked()) }
1537         }
1538     }
1539 }
1540
1541 impl<'a, K, V> RangeMut<'a, K, V> {
1542     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1543         let handle = ptr::read(&self.back);
1544
1545         let mut cur_handle = match handle.left_kv() {
1546             Ok(kv) => {
1547                 let (k, v) = ptr::read(&kv).into_kv_mut();
1548                 self.back = kv.left_edge();
1549                 return (k, v);
1550             }
1551             Err(last_edge) => {
1552                 let next_level = last_edge.into_node().ascend().ok();
1553                 unwrap_unchecked(next_level)
1554             }
1555         };
1556
1557         loop {
1558             match cur_handle.left_kv() {
1559                 Ok(kv) => {
1560                     let (k, v) = ptr::read(&kv).into_kv_mut();
1561                     self.back = last_leaf_edge(kv.left_edge().descend());
1562                     return (k, v);
1563                 }
1564                 Err(last_edge) => {
1565                     let next_level = last_edge.into_node().ascend().ok();
1566                     cur_handle = unwrap_unchecked(next_level);
1567                 }
1568             }
1569         }
1570     }
1571 }
1572
1573 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1574     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
1575         let mut map = BTreeMap::new();
1576         map.extend(iter);
1577         map
1578     }
1579 }
1580
1581 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1582     #[inline]
1583     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
1584         for (k, v) in iter {
1585             self.insert(k, v);
1586         }
1587     }
1588 }
1589
1590 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1591     fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
1592         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1593     }
1594 }
1595
1596 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1597     fn hash<H: Hasher>(&self, state: &mut H) {
1598         for elt in self {
1599             elt.hash(state);
1600         }
1601     }
1602 }
1603
1604 impl<K: Ord, V> Default for BTreeMap<K, V> {
1605     fn default() -> BTreeMap<K, V> {
1606         BTreeMap::new()
1607     }
1608 }
1609
1610 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1611     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1612         self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
1613     }
1614 }
1615
1616 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1617
1618 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1619     #[inline]
1620     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1621         self.iter().partial_cmp(other.iter())
1622     }
1623 }
1624
1625 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1626     #[inline]
1627     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1628         self.iter().cmp(other.iter())
1629     }
1630 }
1631
1632 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1633     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1634         f.debug_map().entries(self.iter()).finish()
1635     }
1636 }
1637
1638 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1639     where K: Borrow<Q>,
1640           Q: Ord
1641 {
1642     type Output = V;
1643
1644     #[inline]
1645     fn index(&self, key: &Q) -> &V {
1646         self.get(key).expect("no entry found for key")
1647     }
1648 }
1649
1650 fn first_leaf_edge<BorrowType, K, V>
1651     (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
1652      -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1653     loop {
1654         match node.force() {
1655             Leaf(leaf) => return leaf.first_edge(),
1656             Internal(internal) => {
1657                 node = internal.first_edge().descend();
1658             }
1659         }
1660     }
1661 }
1662
1663 fn last_leaf_edge<BorrowType, K, V>
1664     (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
1665      -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1666     loop {
1667         match node.force() {
1668             Leaf(leaf) => return leaf.last_edge(),
1669             Internal(internal) => {
1670                 node = internal.last_edge().descend();
1671             }
1672         }
1673     }
1674 }
1675
1676 #[inline(always)]
1677 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1678     val.unwrap_or_else(|| {
1679         if cfg!(debug_assertions) {
1680             panic!("'unchecked' unwrap on None in BTreeMap");
1681         } else {
1682             intrinsics::unreachable();
1683         }
1684     })
1685 }
1686
1687 impl<K, V> BTreeMap<K, V> {
1688     /// Gets an iterator over the entries of the map, sorted by key.
1689     ///
1690     /// # Examples
1691     ///
1692     /// Basic usage:
1693     ///
1694     /// ```
1695     /// use std::collections::BTreeMap;
1696     ///
1697     /// let mut map = BTreeMap::new();
1698     /// map.insert(3, "c");
1699     /// map.insert(2, "b");
1700     /// map.insert(1, "a");
1701     ///
1702     /// for (key, value) in map.iter() {
1703     ///     println!("{}: {}", key, value);
1704     /// }
1705     ///
1706     /// let (first_key, first_value) = map.iter().next().unwrap();
1707     /// assert_eq!((*first_key, *first_value), (1, "a"));
1708     /// ```
1709     #[stable(feature = "rust1", since = "1.0.0")]
1710     pub fn iter(&self) -> Iter<K, V> {
1711         Iter {
1712             range: Range {
1713                 front: first_leaf_edge(self.root.as_ref()),
1714                 back: last_leaf_edge(self.root.as_ref()),
1715             },
1716             length: self.length,
1717         }
1718     }
1719
1720     /// Gets a mutable iterator over the entries of the map, sorted by key.
1721     ///
1722     /// # Examples
1723     ///
1724     /// Basic usage:
1725     ///
1726     /// ```
1727     /// use std::collections::BTreeMap;
1728     ///
1729     /// let mut map = BTreeMap::new();
1730     /// map.insert("a", 1);
1731     /// map.insert("b", 2);
1732     /// map.insert("c", 3);
1733     ///
1734     /// // add 10 to the value if the key isn't "a"
1735     /// for (key, value) in map.iter_mut() {
1736     ///     if key != &"a" {
1737     ///         *value += 10;
1738     ///     }
1739     /// }
1740     /// ```
1741     #[stable(feature = "rust1", since = "1.0.0")]
1742     pub fn iter_mut(&mut self) -> IterMut<K, V> {
1743         let root1 = self.root.as_mut();
1744         let root2 = unsafe { ptr::read(&root1) };
1745         IterMut {
1746             range: RangeMut {
1747                 front: first_leaf_edge(root1),
1748                 back: last_leaf_edge(root2),
1749                 _marker: PhantomData,
1750             },
1751             length: self.length,
1752         }
1753     }
1754
1755     /// Gets an iterator over the keys of the map, in sorted order.
1756     ///
1757     /// # Examples
1758     ///
1759     /// Basic usage:
1760     ///
1761     /// ```
1762     /// use std::collections::BTreeMap;
1763     ///
1764     /// let mut a = BTreeMap::new();
1765     /// a.insert(2, "b");
1766     /// a.insert(1, "a");
1767     ///
1768     /// let keys: Vec<_> = a.keys().cloned().collect();
1769     /// assert_eq!(keys, [1, 2]);
1770     /// ```
1771     #[stable(feature = "rust1", since = "1.0.0")]
1772     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1773         Keys { inner: self.iter() }
1774     }
1775
1776     /// Gets an iterator over the values of the map, in order by key.
1777     ///
1778     /// # Examples
1779     ///
1780     /// Basic usage:
1781     ///
1782     /// ```
1783     /// use std::collections::BTreeMap;
1784     ///
1785     /// let mut a = BTreeMap::new();
1786     /// a.insert(1, "hello");
1787     /// a.insert(2, "goodbye");
1788     ///
1789     /// let values: Vec<&str> = a.values().cloned().collect();
1790     /// assert_eq!(values, ["hello", "goodbye"]);
1791     /// ```
1792     #[stable(feature = "rust1", since = "1.0.0")]
1793     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1794         Values { inner: self.iter() }
1795     }
1796
1797     /// Gets a mutable iterator over the values of the map, in order by key.
1798     ///
1799     /// # Examples
1800     ///
1801     /// Basic usage:
1802     ///
1803     /// ```
1804     /// use std::collections::BTreeMap;
1805     ///
1806     /// let mut a = BTreeMap::new();
1807     /// a.insert(1, String::from("hello"));
1808     /// a.insert(2, String::from("goodbye"));
1809     ///
1810     /// for value in a.values_mut() {
1811     ///     value.push_str("!");
1812     /// }
1813     ///
1814     /// let values: Vec<String> = a.values().cloned().collect();
1815     /// assert_eq!(values, [String::from("hello!"),
1816     ///                     String::from("goodbye!")]);
1817     /// ```
1818     #[stable(feature = "map_values_mut", since = "1.10.0")]
1819     pub fn values_mut(&mut self) -> ValuesMut<K, V> {
1820         ValuesMut { inner: self.iter_mut() }
1821     }
1822
1823     /// Returns the number of elements in the map.
1824     ///
1825     /// # Examples
1826     ///
1827     /// Basic usage:
1828     ///
1829     /// ```
1830     /// use std::collections::BTreeMap;
1831     ///
1832     /// let mut a = BTreeMap::new();
1833     /// assert_eq!(a.len(), 0);
1834     /// a.insert(1, "a");
1835     /// assert_eq!(a.len(), 1);
1836     /// ```
1837     #[stable(feature = "rust1", since = "1.0.0")]
1838     pub fn len(&self) -> usize {
1839         self.length
1840     }
1841
1842     /// Returns true if the map contains no elements.
1843     ///
1844     /// # Examples
1845     ///
1846     /// Basic usage:
1847     ///
1848     /// ```
1849     /// use std::collections::BTreeMap;
1850     ///
1851     /// let mut a = BTreeMap::new();
1852     /// assert!(a.is_empty());
1853     /// a.insert(1, "a");
1854     /// assert!(!a.is_empty());
1855     /// ```
1856     #[stable(feature = "rust1", since = "1.0.0")]
1857     pub fn is_empty(&self) -> bool {
1858         self.len() == 0
1859     }
1860 }
1861
1862 impl<'a, K: Ord, V> Entry<'a, K, V> {
1863     /// Ensures a value is in the entry by inserting the default if empty, and returns
1864     /// a mutable reference to the value in the entry.
1865     #[stable(feature = "rust1", since = "1.0.0")]
1866     pub fn or_insert(self, default: V) -> &'a mut V {
1867         match self {
1868             Occupied(entry) => entry.into_mut(),
1869             Vacant(entry) => entry.insert(default),
1870         }
1871     }
1872
1873     /// Ensures a value is in the entry by inserting the result of the default function if empty,
1874     /// and returns a mutable reference to the value in the entry.
1875     #[stable(feature = "rust1", since = "1.0.0")]
1876     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1877         match self {
1878             Occupied(entry) => entry.into_mut(),
1879             Vacant(entry) => entry.insert(default()),
1880         }
1881     }
1882
1883     /// Returns a reference to this entry's key.
1884     #[stable(feature = "map_entry_keys", since = "1.10.0")]
1885     pub fn key(&self) -> &K {
1886         match *self {
1887             Occupied(ref entry) => entry.key(),
1888             Vacant(ref entry) => entry.key(),
1889         }
1890     }
1891 }
1892
1893 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1894     /// Gets a reference to the key that would be used when inserting a value
1895     /// through the VacantEntry.
1896     #[stable(feature = "map_entry_keys", since = "1.10.0")]
1897     pub fn key(&self) -> &K {
1898         &self.key
1899     }
1900
1901     /// Sets the value of the entry with the VacantEntry's key,
1902     /// and returns a mutable reference to it.
1903     #[stable(feature = "rust1", since = "1.0.0")]
1904     pub fn insert(self, value: V) -> &'a mut V {
1905         *self.length += 1;
1906
1907         let out_ptr;
1908
1909         let mut ins_k;
1910         let mut ins_v;
1911         let mut ins_edge;
1912
1913         let mut cur_parent = match self.handle.insert(self.key, value) {
1914             (Fit(handle), _) => return handle.into_kv_mut().1,
1915             (Split(left, k, v, right), ptr) => {
1916                 ins_k = k;
1917                 ins_v = v;
1918                 ins_edge = right;
1919                 out_ptr = ptr;
1920                 left.ascend().map_err(|n| n.into_root_mut())
1921             }
1922         };
1923
1924         loop {
1925             match cur_parent {
1926                 Ok(parent) => {
1927                     match parent.insert(ins_k, ins_v, ins_edge) {
1928                         Fit(_) => return unsafe { &mut *out_ptr },
1929                         Split(left, k, v, right) => {
1930                             ins_k = k;
1931                             ins_v = v;
1932                             ins_edge = right;
1933                             cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1934                         }
1935                     }
1936                 }
1937                 Err(root) => {
1938                     root.push_level().push(ins_k, ins_v, ins_edge);
1939                     return unsafe { &mut *out_ptr };
1940                 }
1941             }
1942         }
1943     }
1944 }
1945
1946 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1947     /// Gets a reference to the key in the entry.
1948     #[stable(feature = "map_entry_keys", since = "1.10.0")]
1949     pub fn key(&self) -> &K {
1950         self.handle.reborrow().into_kv().0
1951     }
1952
1953     /// Gets a reference to the value in the entry.
1954     #[stable(feature = "rust1", since = "1.0.0")]
1955     pub fn get(&self) -> &V {
1956         self.handle.reborrow().into_kv().1
1957     }
1958
1959     /// Gets a mutable reference to the value in the entry.
1960     #[stable(feature = "rust1", since = "1.0.0")]
1961     pub fn get_mut(&mut self) -> &mut V {
1962         self.handle.kv_mut().1
1963     }
1964
1965     /// Converts the entry into a mutable reference to its value.
1966     #[stable(feature = "rust1", since = "1.0.0")]
1967     pub fn into_mut(self) -> &'a mut V {
1968         self.handle.into_kv_mut().1
1969     }
1970
1971     /// Sets the value of the entry with the OccupiedEntry's key,
1972     /// and returns the entry's old value.
1973     #[stable(feature = "rust1", since = "1.0.0")]
1974     pub fn insert(&mut self, value: V) -> V {
1975         mem::replace(self.get_mut(), value)
1976     }
1977
1978     /// Takes the value of the entry out of the map, and returns it.
1979     #[stable(feature = "rust1", since = "1.0.0")]
1980     pub fn remove(self) -> V {
1981         self.remove_kv().1
1982     }
1983
1984     fn remove_kv(self) -> (K, V) {
1985         *self.length -= 1;
1986
1987         let (small_leaf, old_key, old_val) = match self.handle.force() {
1988             Leaf(leaf) => {
1989                 let (hole, old_key, old_val) = leaf.remove();
1990                 (hole.into_node(), old_key, old_val)
1991             }
1992             Internal(mut internal) => {
1993                 let key_loc = internal.kv_mut().0 as *mut K;
1994                 let val_loc = internal.kv_mut().1 as *mut V;
1995
1996                 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1997                 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1998
1999                 let (hole, key, val) = to_remove.remove();
2000
2001                 let old_key = unsafe { mem::replace(&mut *key_loc, key) };
2002                 let old_val = unsafe { mem::replace(&mut *val_loc, val) };
2003
2004                 (hole.into_node(), old_key, old_val)
2005             }
2006         };
2007
2008         // Handle underflow
2009         let mut cur_node = small_leaf.forget_type();
2010         while cur_node.len() < node::CAPACITY / 2 {
2011             match handle_underfull_node(cur_node) {
2012                 AtRoot => break,
2013                 EmptyParent(_) => unreachable!(),
2014                 Merged(parent) => {
2015                     if parent.len() == 0 {
2016                         // We must be at the root
2017                         parent.into_root_mut().pop_level();
2018                         break;
2019                     } else {
2020                         cur_node = parent.forget_type();
2021                     }
2022                 }
2023                 Stole(_) => break,
2024             }
2025         }
2026
2027         (old_key, old_val)
2028     }
2029 }
2030
2031 enum UnderflowResult<'a, K, V> {
2032     AtRoot,
2033     EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2034     Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2035     Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2036 }
2037
2038 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>)
2039                                    -> UnderflowResult<'a, K, V> {
2040     let parent = if let Ok(parent) = node.ascend() {
2041         parent
2042     } else {
2043         return AtRoot;
2044     };
2045
2046     let (is_left, mut handle) = match parent.left_kv() {
2047         Ok(left) => (true, left),
2048         Err(parent) => {
2049             match parent.right_kv() {
2050                 Ok(right) => (false, right),
2051                 Err(parent) => {
2052                     return EmptyParent(parent.into_node());
2053                 }
2054             }
2055         }
2056     };
2057
2058     if handle.can_merge() {
2059         Merged(handle.merge().into_node())
2060     } else {
2061         if is_left {
2062             handle.steal_left();
2063         } else {
2064             handle.steal_right();
2065         }
2066         Stole(handle.into_node())
2067     }
2068 }
2069
2070 impl<K: Ord, V, I: Iterator<Item = (K, V)>> Iterator for MergeIter<K, V, I> {
2071     type Item = (K, V);
2072
2073     fn next(&mut self) -> Option<(K, V)> {
2074         let res = match (self.left.peek(), self.right.peek()) {
2075             (Some(&(ref left_key, _)), Some(&(ref right_key, _))) => left_key.cmp(right_key),
2076             (Some(_), None) => Ordering::Less,
2077             (None, Some(_)) => Ordering::Greater,
2078             (None, None) => return None,
2079         };
2080
2081         // Check which elements comes first and only advance the corresponding iterator.
2082         // If two keys are equal, take the value from `right`.
2083         match res {
2084             Ordering::Less => self.left.next(),
2085             Ordering::Greater => self.right.next(),
2086             Ordering::Equal => {
2087                 self.left.next();
2088                 self.right.next()
2089             }
2090         }
2091     }
2092 }