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;
  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, Included, Excluded, Unbounded};
  21
  22 use super::node::{self, NodeRef, Handle, 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 books.
  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 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
 145     fn clone(&self) -> BTreeMap<K, V> {
 146         fn clone_subtree<K: Clone, V: Clone>(
 147                 node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
 148                 -> BTreeMap<K, V> {
 149
 150             match node.force() {
 151                 Leaf(leaf) => {
 152                     let mut out_tree = BTreeMap {
 153                         root: node::Root::new_leaf(),
 154                         length: 0
 155                     };
 156
 157                     {
 158                         let mut out_node = match out_tree.root.as_mut().force() {
 159                             Leaf(leaf) => leaf,
 160                             Internal(_) => unreachable!()
 161                         };
 162
 163                         let mut in_edge = leaf.first_edge();
 164                         while let Ok(kv) = in_edge.right_kv() {
 165                             let (k, v) = kv.into_kv();
 166                             in_edge = kv.right_edge();
 167
 168                             out_node.push(k.clone(), v.clone());
 169                             out_tree.length += 1;
 170                         }
 171                     }
 172
 173                     out_tree
 174                 },
 175                 Internal(internal) => {
 176                     let mut out_tree = clone_subtree(internal.first_edge().descend());
 177
 178                     {
 179                         let mut out_node = out_tree.root.push_level();
 180                         let mut in_edge = internal.first_edge();
 181                         while let Ok(kv) = in_edge.right_kv() {
 182                             let (k, v) = kv.into_kv();
 183                             in_edge = kv.right_edge();
 184
 185                             let k = (*k).clone();
 186                             let v = (*v).clone();
 187                             let subtree = clone_subtree(in_edge.descend());
 188
 189                             // We can't destructure subtree directly
 190                             // because BTreeMap implements Drop
 191                             let (subroot, sublength) = unsafe {
 192                                 let root = ptr::read(&subtree.root);
 193                                 let length = subtree.length;
 194                                 mem::forget(subtree);
 195                                 (root, length)
 196                             };
 197
 198                             out_node.push(k, v, subroot);
 199                             out_tree.length += 1 + sublength;
 200                         }
 201                     }
 202
 203                     out_tree
 204                 }
 205             }
 206         }
 207
 208         clone_subtree(self.root.as_ref())
 209     }
 210 }
 211
 212 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 213     where K: Borrow<Q> + Ord,
 214           Q: Ord
 215 {
 216     type Key = K;
 217
 218     fn get(&self, key: &Q) -> Option<&K> {
 219         match search::search_tree(self.root.as_ref(), key) {
 220             Found(handle) => Some(handle.into_kv().0),
 221             GoDown(_) => None
 222         }
 223     }
 224
 225     fn take(&mut self, key: &Q) -> Option<K> {
 226         match search::search_tree(self.root.as_mut(), key) {
 227             Found(handle) => {
 228                 Some(OccupiedEntry {
 229                     handle: handle,
 230                     length: &mut self.length,
 231                     _marker: PhantomData,
 232                 }.remove_kv().0)
 233             },
 234             GoDown(_) => None
 235         }
 236     }
 237
 238     fn replace(&mut self, key: K) -> Option<K> {
 239         match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
 240             Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
 241             GoDown(handle) => {
 242                 VacantEntry {
 243                     key: key,
 244                     handle: handle,
 245                     length: &mut self.length,
 246                     _marker: PhantomData,
 247                 }.insert(());
 248                 None
 249             }
 250         }
 251     }
 252 }
 253
 254 /// An iterator over a BTreeMap's entries.
 255 #[stable(feature = "rust1", since = "1.0.0")]
 256 pub struct Iter<'a, K: 'a, V: 'a> {
 257     range: Range<'a, K, V>,
 258     length: usize
 259 }
 260
 261 /// A mutable iterator over a BTreeMap's entries.
 262 #[stable(feature = "rust1", since = "1.0.0")]
 263 pub struct IterMut<'a, K: 'a, V: 'a> {
 264     range: RangeMut<'a, K, V>,
 265     length: usize
 266 }
 267
 268 /// An owning iterator over a BTreeMap's entries.
 269 #[stable(feature = "rust1", since = "1.0.0")]
 270 pub struct IntoIter<K, V> {
 271     front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 272     back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 273     length: usize
 274 }
 275
 276 /// An iterator over a BTreeMap's keys.
 277 #[stable(feature = "rust1", since = "1.0.0")]
 278 pub struct Keys<'a, K: 'a, V: 'a> {
 279     inner: Iter<'a, K, V>,
 280 }
 281
 282 /// An iterator over a BTreeMap's values.
 283 #[stable(feature = "rust1", since = "1.0.0")]
 284 pub struct Values<'a, K: 'a, V: 'a> {
 285     inner: Iter<'a, K, V>,
 286 }
 287
 288 /// A mutable iterator over a BTreeMap's values.
 289 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
 290 pub struct ValuesMut<'a, K: 'a, V: 'a> {
 291     inner: IterMut<'a, K, V>,
 292 }
 293
 294 /// An iterator over a sub-range of BTreeMap's entries.
 295 pub struct Range<'a, K: 'a, V: 'a> {
 296     front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 297     back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
 298 }
 299
 300 /// A mutable iterator over a sub-range of BTreeMap's entries.
 301 pub struct RangeMut<'a, K: 'a, V: 'a> {
 302     front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 303     back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 304
 305     // Be invariant in `K` and `V`
 306     _marker: PhantomData<&'a mut (K, V)>,
 307 }
 308
 309 /// A view into a single entry in a map, which may either be vacant or occupied.
 310 #[stable(feature = "rust1", since = "1.0.0")]
 311 pub enum Entry<'a, K: 'a, V: 'a> {
 312     /// A vacant Entry
 313     #[stable(feature = "rust1", since = "1.0.0")]
 314     Vacant(
 315         #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
 316     ),
 317
 318     /// An occupied Entry
 319     #[stable(feature = "rust1", since = "1.0.0")]
 320     Occupied(
 321         #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
 322     ),
 323 }
 324
 325 /// A vacant Entry.
 326 #[stable(feature = "rust1", since = "1.0.0")]
 327 pub struct VacantEntry<'a, K: 'a, V: 'a> {
 328     key: K,
 329     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 330     length: &'a mut usize,
 331
 332     // Be invariant in `K` and `V`
 333     _marker: PhantomData<&'a mut (K, V)>,
 334 }
 335
 336 /// An occupied Entry.
 337 #[stable(feature = "rust1", since = "1.0.0")]
 338 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
 339     handle: Handle<NodeRef<
 340         marker::Mut<'a>,
 341         K, V,
 342         marker::LeafOrInternal
 343     >, 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 impl<K: Ord, V> BTreeMap<K, V> {
 352     /// Makes a new empty BTreeMap with a reasonable choice for B.
 353     ///
 354     /// # Examples
 355     ///
 356     /// Basic usage:
 357     ///
 358     /// ```
 359     /// use std::collections::BTreeMap;
 360     ///
 361     /// let mut map = BTreeMap::new();
 362     ///
 363     /// // entries can now be inserted into the empty map
 364     /// map.insert(1, "a");
 365     /// ```
 366     #[stable(feature = "rust1", since = "1.0.0")]
 367     pub fn new() -> BTreeMap<K, V> {
 368         BTreeMap {
 369             root: node::Root::new_leaf(),
 370             length: 0
 371         }
 372     }
 373
 374     /// Clears the map, removing all values.
 375     ///
 376     /// # Examples
 377     ///
 378     /// Basic usage:
 379     ///
 380     /// ```
 381     /// use std::collections::BTreeMap;
 382     ///
 383     /// let mut a = BTreeMap::new();
 384     /// a.insert(1, "a");
 385     /// a.clear();
 386     /// assert!(a.is_empty());
 387     /// ```
 388     #[stable(feature = "rust1", since = "1.0.0")]
 389     pub fn clear(&mut self) {
 390         // FIXME(gereeter) .clear() allocates
 391         *self = BTreeMap::new();
 392     }
 393
 394     /// Returns a reference to the value corresponding to the key.
 395     ///
 396     /// The key may be any borrowed form of the map's key type, but the ordering
 397     /// on the borrowed form *must* match the ordering on the key type.
 398     ///
 399     /// # Examples
 400     ///
 401     /// Basic usage:
 402     ///
 403     /// ```
 404     /// use std::collections::BTreeMap;
 405     ///
 406     /// let mut map = BTreeMap::new();
 407     /// map.insert(1, "a");
 408     /// assert_eq!(map.get(&1), Some(&"a"));
 409     /// assert_eq!(map.get(&2), None);
 410     /// ```
 411     #[stable(feature = "rust1", since = "1.0.0")]
 412     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
 413         match search::search_tree(self.root.as_ref(), key) {
 414             Found(handle) => Some(handle.into_kv().1),
 415             GoDown(_) => None
 416         }
 417     }
 418
 419     /// Returns true if the map contains a value for the specified key.
 420     ///
 421     /// The key may be any borrowed form of the map's key type, but the ordering
 422     /// on the borrowed form *must* match the ordering on the key type.
 423     ///
 424     /// # Examples
 425     ///
 426     /// Basic usage:
 427     ///
 428     /// ```
 429     /// use std::collections::BTreeMap;
 430     ///
 431     /// let mut map = BTreeMap::new();
 432     /// map.insert(1, "a");
 433     /// assert_eq!(map.contains_key(&1), true);
 434     /// assert_eq!(map.contains_key(&2), false);
 435     /// ```
 436     #[stable(feature = "rust1", since = "1.0.0")]
 437     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
 438         self.get(key).is_some()
 439     }
 440
 441     /// Returns a mutable reference to the value corresponding to the key.
 442     ///
 443     /// The key may be any borrowed form of the map's key type, but the ordering
 444     /// on the borrowed form *must* match the ordering on the key type.
 445     ///
 446     /// # Examples
 447     ///
 448     /// Basic usage:
 449     ///
 450     /// ```
 451     /// use std::collections::BTreeMap;
 452     ///
 453     /// let mut map = BTreeMap::new();
 454     /// map.insert(1, "a");
 455     /// if let Some(x) = map.get_mut(&1) {
 456     ///     *x = "b";
 457     /// }
 458     /// assert_eq!(map[&1], "b");
 459     /// ```
 460     // See `get` for implementation notes, this is basically a copy-paste with mut's added
 461     #[stable(feature = "rust1", since = "1.0.0")]
 462     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
 463         match search::search_tree(self.root.as_mut(), key) {
 464             Found(handle) => Some(handle.into_kv_mut().1),
 465             GoDown(_) => None
 466         }
 467     }
 468
 469     /// Inserts a key-value pair into the map.
 470     ///
 471     /// If the map did not have this key present, `None` is returned.
 472     ///
 473     /// If the map did have this key present, the value is updated, and the old
 474     /// value is returned. The key is not updated, though; this matters for
 475     /// types that can be `==` without being identical. See the [module-level
 476     /// documentation] for more.
 477     ///
 478     /// [module-level documentation]: index.html#insert-and-complex-keys
 479     ///
 480     /// # Examples
 481     ///
 482     /// Basic usage:
 483     ///
 484     /// ```
 485     /// use std::collections::BTreeMap;
 486     ///
 487     /// let mut map = BTreeMap::new();
 488     /// assert_eq!(map.insert(37, "a"), None);
 489     /// assert_eq!(map.is_empty(), false);
 490     ///
 491     /// map.insert(37, "b");
 492     /// assert_eq!(map.insert(37, "c"), Some("b"));
 493     /// assert_eq!(map[&37], "c");
 494     /// ```
 495     #[stable(feature = "rust1", since = "1.0.0")]
 496     pub fn insert(&mut self, key: K, value: V) -> Option<V> {
 497         match self.entry(key) {
 498             Occupied(mut entry) => Some(entry.insert(value)),
 499             Vacant(entry) => {
 500                 entry.insert(value);
 501                 None
 502             }
 503         }
 504     }
 505
 506     /// Removes a key from the map, returning the value at the key if the key
 507     /// was previously in the map.
 508     ///
 509     /// The key may be any borrowed form of the map's key type, but the ordering
 510     /// on the borrowed form *must* match the ordering on the key type.
 511     ///
 512     /// # Examples
 513     ///
 514     /// Basic usage:
 515     ///
 516     /// ```
 517     /// use std::collections::BTreeMap;
 518     ///
 519     /// let mut map = BTreeMap::new();
 520     /// map.insert(1, "a");
 521     /// assert_eq!(map.remove(&1), Some("a"));
 522     /// assert_eq!(map.remove(&1), None);
 523     /// ```
 524     #[stable(feature = "rust1", since = "1.0.0")]
 525     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
 526         match search::search_tree(self.root.as_mut(), key) {
 527             Found(handle) => {
 528                 Some(OccupiedEntry {
 529                     handle: handle,
 530                     length: &mut self.length,
 531                     _marker: PhantomData,
 532                 }.remove())
 533             },
 534             GoDown(_) => None
 535         }
 536     }
 537
 538     /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
 539     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
 540     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
 541     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
 542     ///
 543     /// # Examples
 544     ///
 545     /// Basic usage:
 546     ///
 547     /// ```
 548     /// #![feature(btree_range, collections_bound)]
 549     ///
 550     /// use std::collections::BTreeMap;
 551     /// use std::collections::Bound::{Included, Unbounded};
 552     ///
 553     /// let mut map = BTreeMap::new();
 554     /// map.insert(3, "a");
 555     /// map.insert(5, "b");
 556     /// map.insert(8, "c");
 557     /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
 558     ///     println!("{}: {}", key, value);
 559     /// }
 560     /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
 561     /// ```
 562     #[unstable(feature = "btree_range",
 563                reason = "matches collection reform specification, waiting for dust to settle",
 564                issue = "27787")]
 565     pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
 566                                                        min: Bound<&Min>,
 567                                                        max: Bound<&Max>)
 568                                                        -> Range<K, V>
 569         where K: Borrow<Min> + Borrow<Max>,
 570     {
 571         let front = match min {
 572             Included(key) => match search::search_tree(self.root.as_ref(), key) {
 573                 Found(kv_handle) => match kv_handle.left_edge().force() {
 574                     Leaf(bottom) => bottom,
 575                     Internal(internal) => last_leaf_edge(internal.descend())
 576                 },
 577                 GoDown(bottom) => bottom
 578             },
 579             Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
 580                 Found(kv_handle) => match kv_handle.right_edge().force() {
 581                     Leaf(bottom) => bottom,
 582                     Internal(internal) => first_leaf_edge(internal.descend())
 583                 },
 584                 GoDown(bottom) => bottom
 585             },
 586             Unbounded => first_leaf_edge(self.root.as_ref())
 587         };
 588
 589         let back = match max {
 590             Included(key) => match search::search_tree(self.root.as_ref(), key) {
 591                 Found(kv_handle) => match kv_handle.right_edge().force() {
 592                     Leaf(bottom) => bottom,
 593                     Internal(internal) => first_leaf_edge(internal.descend())
 594                 },
 595                 GoDown(bottom) => bottom
 596             },
 597             Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
 598                 Found(kv_handle) => match kv_handle.left_edge().force() {
 599                     Leaf(bottom) => bottom,
 600                     Internal(internal) => last_leaf_edge(internal.descend())
 601                 },
 602                 GoDown(bottom) => bottom
 603             },
 604             Unbounded => last_leaf_edge(self.root.as_ref())
 605         };
 606
 607         Range {
 608             front: front,
 609             back: back
 610         }
 611     }
 612
 613     /// Constructs a mutable 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, Excluded};
 627     ///
 628     /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
 629     ///                                                                       .map(|&s| (s, 0))
 630     ///                                                                       .collect();
 631     /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
 632     ///     *balance += 100;
 633     /// }
 634     /// for (name, balance) in &map {
 635     ///     println!("{} => {}", name, balance);
 636     /// }
 637     /// ```
 638     #[unstable(feature = "btree_range",
 639                reason = "matches collection reform specification, waiting for dust to settle",
 640                issue = "27787")]
 641     pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
 642                                                            min: Bound<&Min>,
 643                                                            max: Bound<&Max>)
 644                                                            -> RangeMut<K, V>
 645         where K: Borrow<Min> + Borrow<Max>,
 646     {
 647         let root1 = self.root.as_mut();
 648         let root2 = unsafe { ptr::read(&root1) };
 649
 650         let front = match min {
 651             Included(key) => match search::search_tree(root1, key) {
 652                 Found(kv_handle) => match kv_handle.left_edge().force() {
 653                     Leaf(bottom) => bottom,
 654                     Internal(internal) => last_leaf_edge(internal.descend())
 655                 },
 656                 GoDown(bottom) => bottom
 657             },
 658             Excluded(key) => match search::search_tree(root1, key) {
 659                 Found(kv_handle) => match kv_handle.right_edge().force() {
 660                     Leaf(bottom) => bottom,
 661                     Internal(internal) => first_leaf_edge(internal.descend())
 662                 },
 663                 GoDown(bottom) => bottom
 664             },
 665             Unbounded => first_leaf_edge(root1)
 666         };
 667
 668         let back = match max {
 669             Included(key) => match search::search_tree(root2, key) {
 670                 Found(kv_handle) => match kv_handle.right_edge().force() {
 671                     Leaf(bottom) => bottom,
 672                     Internal(internal) => first_leaf_edge(internal.descend())
 673                 },
 674                 GoDown(bottom) => bottom
 675             },
 676             Excluded(key) => match search::search_tree(root2, key) {
 677                 Found(kv_handle) => match kv_handle.left_edge().force() {
 678                     Leaf(bottom) => bottom,
 679                     Internal(internal) => last_leaf_edge(internal.descend())
 680                 },
 681                 GoDown(bottom) => bottom
 682             },
 683             Unbounded => last_leaf_edge(root2)
 684         };
 685
 686         RangeMut {
 687             front: front,
 688             back: back,
 689             _marker: PhantomData
 690         }
 691     }
 692
 693     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 694     ///
 695     /// # Examples
 696     ///
 697     /// Basic usage:
 698     ///
 699     /// ```
 700     /// use std::collections::BTreeMap;
 701     ///
 702     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
 703     ///
 704     /// // count the number of occurrences of letters in the vec
 705     /// for x in vec!["a","b","a","c","a","b"] {
 706     ///     *count.entry(x).or_insert(0) += 1;
 707     /// }
 708     ///
 709     /// assert_eq!(count["a"], 3);
 710     /// ```
 711     #[stable(feature = "rust1", since = "1.0.0")]
 712     pub fn entry(&mut self, key: K) -> Entry<K, V> {
 713         match search::search_tree(self.root.as_mut(), &key) {
 714             Found(handle) => Occupied(OccupiedEntry {
 715                 handle: handle,
 716                 length: &mut self.length,
 717                 _marker: PhantomData,
 718             }),
 719             GoDown(handle) => Vacant(VacantEntry {
 720                 key: key,
 721                 handle: handle,
 722                 length: &mut self.length,
 723                 _marker: PhantomData,
 724             })
 725         }
 726     }
 727 }
 728
 729 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
 730     type Item = (&'a K, &'a V);
 731     type IntoIter = Iter<'a, K, V>;
 732
 733     fn into_iter(self) -> Iter<'a, K, V> {
 734         self.iter()
 735     }
 736 }
 737
 738 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
 739     type Item = (&'a K, &'a V);
 740
 741     fn next(&mut self) -> Option<(&'a K, &'a V)> {
 742         if self.length == 0 {
 743             None
 744         } else {
 745             self.length -= 1;
 746             unsafe { Some(self.range.next_unchecked()) }
 747         }
 748     }
 749
 750     fn size_hint(&self) -> (usize, Option<usize>) {
 751         (self.length, Some(self.length))
 752     }
 753 }
 754
 755 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
 756     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
 757         if self.length == 0 {
 758             None
 759         } else {
 760             self.length -= 1;
 761             unsafe { Some(self.range.next_back_unchecked()) }
 762         }
 763     }
 764 }
 765
 766 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
 767     fn len(&self) -> usize { self.length }
 768 }
 769
 770 impl<'a, K, V> Clone for Iter<'a, K, V> {
 771     fn clone(&self) -> Iter<'a, K, V> {
 772         Iter {
 773             range: self.range.clone(),
 774             length: self.length
 775         }
 776     }
 777 }
 778
 779 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
 780     type Item = (&'a K, &'a mut V);
 781     type IntoIter = IterMut<'a, K, V>;
 782
 783     fn into_iter(self) -> IterMut<'a, K, V> {
 784         self.iter_mut()
 785     }
 786 }
 787
 788 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
 789     type Item = (&'a K, &'a mut V);
 790
 791     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
 792         if self.length == 0 {
 793             None
 794         } else {
 795             self.length -= 1;
 796             unsafe { Some(self.range.next_unchecked()) }
 797         }
 798     }
 799
 800     fn size_hint(&self) -> (usize, Option<usize>) {
 801         (self.length, Some(self.length))
 802     }
 803 }
 804
 805 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
 806     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
 807         if self.length == 0 {
 808             None
 809         } else {
 810             self.length -= 1;
 811             unsafe { Some(self.range.next_back_unchecked()) }
 812         }
 813     }
 814 }
 815
 816 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
 817     fn len(&self) -> usize { self.length }
 818 }
 819
 820 impl<K, V> IntoIterator for BTreeMap<K, V> {
 821     type Item = (K, V);
 822     type IntoIter = IntoIter<K, V>;
 823
 824     fn into_iter(self) -> IntoIter<K, V> {
 825         let root1 = unsafe { ptr::read(&self.root).into_ref() };
 826         let root2 = unsafe { ptr::read(&self.root).into_ref() };
 827         let len = self.length;
 828         mem::forget(self);
 829
 830         IntoIter {
 831             front: first_leaf_edge(root1),
 832             back: last_leaf_edge(root2),
 833             length: len
 834         }
 835     }
 836 }
 837
 838 impl<K, V> Drop for IntoIter<K, V> {
 839     fn drop(&mut self) {
 840         for _ in &mut *self { }
 841         unsafe {
 842             let leaf_node = ptr::read(&self.front).into_node();
 843             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
 844                 let mut cur_node = first_parent.into_node();
 845                 while let Some(parent) = cur_node.deallocate_and_ascend() {
 846                     cur_node = parent.into_node()
 847                 }
 848             }
 849         }
 850     }
 851 }
 852
 853 impl<K, V> Iterator for IntoIter<K, V> {
 854     type Item = (K, V);
 855
 856     fn next(&mut self) -> Option<(K, V)> {
 857         if self.length == 0 {
 858             return None;
 859         } else {
 860             self.length -= 1;
 861         }
 862
 863         let handle = unsafe { ptr::read(&self.front) };
 864
 865         let mut cur_handle = match handle.right_kv() {
 866             Ok(kv) => {
 867                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 868                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 869                 self.front = kv.right_edge();
 870                 return Some((k, v));
 871             },
 872             Err(last_edge) => unsafe {
 873                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
 874             }
 875         };
 876
 877         loop {
 878             match cur_handle.right_kv() {
 879                 Ok(kv) => {
 880                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 881                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 882                     self.front = first_leaf_edge(kv.right_edge().descend());
 883                     return Some((k, v));
 884                 },
 885                 Err(last_edge) => unsafe {
 886                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
 887                 }
 888             }
 889         }
 890     }
 891
 892     fn size_hint(&self) -> (usize, Option<usize>) {
 893         (self.length, Some(self.length))
 894     }
 895 }
 896
 897 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
 898     fn next_back(&mut self) -> Option<(K, V)> {
 899         if self.length == 0 {
 900             return None;
 901         } else {
 902             self.length -= 1;
 903         }
 904
 905         let handle = unsafe { ptr::read(&self.back) };
 906
 907         let mut cur_handle = match handle.left_kv() {
 908             Ok(kv) => {
 909                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 910                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 911                 self.back = kv.left_edge();
 912                 return Some((k, v));
 913             },
 914             Err(last_edge) => unsafe {
 915                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
 916             }
 917         };
 918
 919         loop {
 920             match cur_handle.left_kv() {
 921                 Ok(kv) => {
 922                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 923                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 924                     self.back = last_leaf_edge(kv.left_edge().descend());
 925                     return Some((k, v));
 926                 },
 927                 Err(last_edge) => unsafe {
 928                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
 929                 }
 930             }
 931         }
 932     }
 933 }
 934
 935 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
 936     fn len(&self) -> usize { self.length }
 937 }
 938
 939 impl<'a, K, V> Iterator for Keys<'a, K, V> {
 940     type Item = &'a K;
 941
 942     fn next(&mut self) -> Option<&'a K> {
 943         self.inner.next().map(|(k, _)| k)
 944     }
 945
 946     fn size_hint(&self) -> (usize, Option<usize>) {
 947         self.inner.size_hint()
 948     }
 949 }
 950
 951 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
 952     fn next_back(&mut self) -> Option<&'a K> {
 953         self.inner.next_back().map(|(k, _)| k)
 954     }
 955 }
 956
 957 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
 958     fn len(&self) -> usize {
 959         self.inner.len()
 960     }
 961 }
 962
 963 impl<'a, K, V> Clone for Keys<'a, K, V> {
 964     fn clone(&self) -> Keys<'a, K, V> {
 965         Keys {
 966             inner: self.inner.clone()
 967         }
 968     }
 969 }
 970
 971 impl<'a, K, V> Iterator for Values<'a, K, V> {
 972     type Item = &'a V;
 973
 974     fn next(&mut self) -> Option<&'a V> {
 975         self.inner.next().map(|(_, v)| v)
 976     }
 977
 978     fn size_hint(&self) -> (usize, Option<usize>) {
 979         self.inner.size_hint()
 980     }
 981 }
 982
 983 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
 984     fn next_back(&mut self) -> Option<&'a V> {
 985         self.inner.next_back().map(|(_, v)| v)
 986     }
 987 }
 988
 989 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
 990     fn len(&self) -> usize {
 991         self.inner.len()
 992     }
 993 }
 994
 995 impl<'a, K, V> Clone for Values<'a, K, V> {
 996     fn clone(&self) -> Values<'a, K, V> {
 997         Values {
 998             inner: self.inner.clone()
 999         }
1000     }
1001 }
1002
1003 impl<'a, K, V> Iterator for Range<'a, K, V> {
1004     type Item = (&'a K, &'a V);
1005
1006     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1007         if self.front == self.back {
1008             None
1009         } else {
1010             unsafe { Some(self.next_unchecked()) }
1011         }
1012     }
1013 }
1014
1015 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1016 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1017     type Item = &'a mut V;
1018
1019     fn next(&mut self) -> Option<&'a mut V> {
1020         self.inner.next().map(|(_, v)| v)
1021     }
1022
1023     fn size_hint(&self) -> (usize, Option<usize>) {
1024         self.inner.size_hint()
1025     }
1026 }
1027
1028 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1029 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1030     fn next_back(&mut self) -> Option<&'a mut V> {
1031         self.inner.next_back().map(|(_, v)| v)
1032     }
1033 }
1034
1035 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1036 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
1037     fn len(&self) -> usize {
1038         self.inner.len()
1039     }
1040 }
1041
1042 impl<'a, K, V> Range<'a, K, V> {
1043     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
1044         let handle = self.front;
1045
1046         let mut cur_handle = match handle.right_kv() {
1047             Ok(kv) => {
1048                 let ret = kv.into_kv();
1049                 self.front = kv.right_edge();
1050                 return ret;
1051             },
1052             Err(last_edge) => {
1053                 let next_level = last_edge.into_node().ascend().ok();
1054                 unwrap_unchecked(next_level)
1055             }
1056         };
1057
1058         loop {
1059             match cur_handle.right_kv() {
1060                 Ok(kv) => {
1061                     let ret = kv.into_kv();
1062                     self.front = first_leaf_edge(kv.right_edge().descend());
1063                     return ret;
1064                 },
1065                 Err(last_edge) => {
1066                     let next_level = last_edge.into_node().ascend().ok();
1067                     cur_handle = unwrap_unchecked(next_level);
1068                 }
1069             }
1070         }
1071     }
1072 }
1073
1074 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1075     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1076         if self.front == self.back {
1077             None
1078         } else {
1079             unsafe { Some(self.next_back_unchecked()) }
1080         }
1081     }
1082 }
1083
1084 impl<'a, K, V> Range<'a, K, V> {
1085     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
1086         let handle = self.back;
1087
1088         let mut cur_handle = match handle.left_kv() {
1089             Ok(kv) => {
1090                 let ret = kv.into_kv();
1091                 self.back = kv.left_edge();
1092                 return ret;
1093             },
1094             Err(last_edge) => {
1095                 let next_level = last_edge.into_node().ascend().ok();
1096                 unwrap_unchecked(next_level)
1097             }
1098         };
1099
1100         loop {
1101             match cur_handle.left_kv() {
1102                 Ok(kv) => {
1103                     let ret = kv.into_kv();
1104                     self.back = last_leaf_edge(kv.left_edge().descend());
1105                     return ret;
1106                 },
1107                 Err(last_edge) => {
1108                     let next_level = last_edge.into_node().ascend().ok();
1109                     cur_handle = unwrap_unchecked(next_level);
1110                 }
1111             }
1112         }
1113     }
1114 }
1115
1116 impl<'a, K, V> Clone for Range<'a, K, V> {
1117     fn clone(&self) -> Range<'a, K, V> {
1118         Range {
1119             front: self.front,
1120             back: self.back
1121         }
1122     }
1123 }
1124
1125 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1126     type Item = (&'a K, &'a mut V);
1127
1128     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1129         if self.front == self.back {
1130             None
1131         } else {
1132             unsafe { Some (self.next_unchecked()) }
1133         }
1134     }
1135 }
1136
1137 impl<'a, K, V> RangeMut<'a, K, V> {
1138     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1139         let handle = ptr::read(&self.front);
1140
1141         let mut cur_handle = match handle.right_kv() {
1142             Ok(kv) => {
1143                 let (k, v) = ptr::read(&kv).into_kv_mut();
1144                 self.front = kv.right_edge();
1145                 return (k, v);
1146             },
1147             Err(last_edge) => {
1148                 let next_level = last_edge.into_node().ascend().ok();
1149                 unwrap_unchecked(next_level)
1150             }
1151         };
1152
1153         loop {
1154             match cur_handle.right_kv() {
1155                 Ok(kv) => {
1156                     let (k, v) = ptr::read(&kv).into_kv_mut();
1157                     self.front = first_leaf_edge(kv.right_edge().descend());
1158                     return (k, v);
1159                 },
1160                 Err(last_edge) => {
1161                     let next_level = last_edge.into_node().ascend().ok();
1162                     cur_handle = unwrap_unchecked(next_level);
1163                 }
1164             }
1165         }
1166     }
1167 }
1168
1169 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1170     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1171         if self.front == self.back {
1172             None
1173         } else {
1174             unsafe { Some(self.next_back_unchecked()) }
1175         }
1176     }
1177 }
1178
1179 impl<'a, K, V> RangeMut<'a, K, V> {
1180     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1181         let handle = ptr::read(&self.back);
1182
1183         let mut cur_handle = match handle.left_kv() {
1184             Ok(kv) => {
1185                 let (k, v) = ptr::read(&kv).into_kv_mut();
1186                 self.back = kv.left_edge();
1187                 return (k, v);
1188             },
1189             Err(last_edge) => {
1190                 let next_level = last_edge.into_node().ascend().ok();
1191                 unwrap_unchecked(next_level)
1192             }
1193         };
1194
1195         loop {
1196             match cur_handle.left_kv() {
1197                 Ok(kv) => {
1198                     let (k, v) = ptr::read(&kv).into_kv_mut();
1199                     self.back = last_leaf_edge(kv.left_edge().descend());
1200                     return (k, v);
1201                 },
1202                 Err(last_edge) => {
1203                     let next_level = last_edge.into_node().ascend().ok();
1204                     cur_handle = unwrap_unchecked(next_level);
1205                 }
1206             }
1207         }
1208     }
1209 }
1210
1211 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1212     fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
1213         let mut map = BTreeMap::new();
1214         map.extend(iter);
1215         map
1216     }
1217 }
1218
1219 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1220     #[inline]
1221     fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1222         for (k, v) in iter {
1223             self.insert(k, v);
1224         }
1225     }
1226 }
1227
1228 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1229     fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
1230         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1231     }
1232 }
1233
1234 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1235     fn hash<H: Hasher>(&self, state: &mut H) {
1236         for elt in self {
1237             elt.hash(state);
1238         }
1239     }
1240 }
1241
1242 impl<K: Ord, V> Default for BTreeMap<K, V> {
1243     fn default() -> BTreeMap<K, V> {
1244         BTreeMap::new()
1245     }
1246 }
1247
1248 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1249     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1250         self.len() == other.len() &&
1251             self.iter().zip(other).all(|(a, b)| a == b)
1252     }
1253 }
1254
1255 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1256
1257 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1258     #[inline]
1259     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1260         self.iter().partial_cmp(other.iter())
1261     }
1262 }
1263
1264 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1265     #[inline]
1266     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1267         self.iter().cmp(other.iter())
1268     }
1269 }
1270
1271 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1272     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1273         f.debug_map().entries(self.iter()).finish()
1274     }
1275 }
1276
1277 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1278     where K: Borrow<Q>, Q: Ord
1279 {
1280     type Output = V;
1281
1282     #[inline]
1283     fn index(&self, key: &Q) -> &V {
1284         self.get(key).expect("no entry found for key")
1285     }
1286 }
1287
1288 fn first_leaf_edge<BorrowType, K, V>(
1289         mut node: NodeRef<BorrowType,
1290                           K, V,
1291                           marker::LeafOrInternal>
1292         ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1293     loop {
1294         match node.force() {
1295             Leaf(leaf) => return leaf.first_edge(),
1296             Internal(internal) => {
1297                 node = internal.first_edge().descend();
1298             }
1299         }
1300     }
1301 }
1302
1303 fn last_leaf_edge<BorrowType, K, V>(
1304         mut node: NodeRef<BorrowType,
1305                           K, V,
1306                           marker::LeafOrInternal>
1307         ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1308     loop {
1309         match node.force() {
1310             Leaf(leaf) => return leaf.last_edge(),
1311             Internal(internal) => {
1312                 node = internal.last_edge().descend();
1313             }
1314         }
1315     }
1316 }
1317
1318 #[inline(always)]
1319 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1320     val.unwrap_or_else(|| {
1321         if cfg!(debug_assertions) {
1322             panic!("'unchecked' unwrap on None in BTreeMap");
1323         } else {
1324             intrinsics::unreachable();
1325         }
1326     })
1327 }
1328
1329 impl<K, V> BTreeMap<K, V> {
1330     /// Gets an iterator over the entries of the map, sorted by key.
1331     ///
1332     /// # Examples
1333     ///
1334     /// Basic usage:
1335     ///
1336     /// ```
1337     /// use std::collections::BTreeMap;
1338     ///
1339     /// let mut map = BTreeMap::new();
1340     /// map.insert(3, "c");
1341     /// map.insert(2, "b");
1342     /// map.insert(1, "a");
1343     ///
1344     /// for (key, value) in map.iter() {
1345     ///     println!("{}: {}", key, value);
1346     /// }
1347     ///
1348     /// let (first_key, first_value) = map.iter().next().unwrap();
1349     /// assert_eq!((*first_key, *first_value), (1, "a"));
1350     /// ```
1351     #[stable(feature = "rust1", since = "1.0.0")]
1352     pub fn iter(&self) -> Iter<K, V> {
1353         Iter {
1354             range: Range {
1355                 front: first_leaf_edge(self.root.as_ref()),
1356                 back: last_leaf_edge(self.root.as_ref())
1357             },
1358             length: self.length
1359         }
1360     }
1361
1362     /// Gets a mutable iterator over the entries of the map, sorted by key.
1363     ///
1364     /// # Examples
1365     ///
1366     /// Basic usage:
1367     ///
1368     /// ```
1369     /// use std::collections::BTreeMap;
1370     ///
1371     /// let mut map = BTreeMap::new();
1372     /// map.insert("a", 1);
1373     /// map.insert("b", 2);
1374     /// map.insert("c", 3);
1375     ///
1376     /// // add 10 to the value if the key isn't "a"
1377     /// for (key, value) in map.iter_mut() {
1378     ///     if key != &"a" {
1379     ///         *value += 10;
1380     ///     }
1381     /// }
1382     /// ```
1383     #[stable(feature = "rust1", since = "1.0.0")]
1384     pub fn iter_mut(&mut self) -> IterMut<K, V> {
1385         let root1 = self.root.as_mut();
1386         let root2 = unsafe { ptr::read(&root1) };
1387         IterMut {
1388             range: RangeMut {
1389                 front: first_leaf_edge(root1),
1390                 back: last_leaf_edge(root2),
1391                 _marker: PhantomData,
1392             },
1393             length: self.length
1394         }
1395     }
1396
1397     /// Gets an iterator over the keys of the map, in sorted order.
1398     ///
1399     /// # Examples
1400     ///
1401     /// Basic usage:
1402     ///
1403     /// ```
1404     /// use std::collections::BTreeMap;
1405     ///
1406     /// let mut a = BTreeMap::new();
1407     /// a.insert(2, "b");
1408     /// a.insert(1, "a");
1409     ///
1410     /// let keys: Vec<_> = a.keys().cloned().collect();
1411     /// assert_eq!(keys, [1, 2]);
1412     /// ```
1413     #[stable(feature = "rust1", since = "1.0.0")]
1414     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1415         Keys { inner: self.iter() }
1416     }
1417
1418     /// Gets an iterator over the values of the map, in order by key.
1419     ///
1420     /// # Examples
1421     ///
1422     /// Basic usage:
1423     ///
1424     /// ```
1425     /// use std::collections::BTreeMap;
1426     ///
1427     /// let mut a = BTreeMap::new();
1428     /// a.insert(1, "hello");
1429     /// a.insert(2, "goodbye");
1430     ///
1431     /// let values: Vec<&str> = a.values().cloned().collect();
1432     /// assert_eq!(values, ["hello", "goodbye"]);
1433     /// ```
1434     #[stable(feature = "rust1", since = "1.0.0")]
1435     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1436         Values { inner: self.iter() }
1437     }
1438
1439     /// Gets a mutable iterator over the values of the map, in order by key.
1440     ///
1441     /// # Examples
1442     ///
1443     /// Basic usage:
1444     ///
1445     /// ```
1446     /// # #![feature(map_values_mut)]
1447     /// use std::collections::BTreeMap;
1448     ///
1449     /// let mut a = BTreeMap::new();
1450     /// a.insert(1, String::from("hello"));
1451     /// a.insert(2, String::from("goodbye"));
1452     ///
1453     /// for value in a.values_mut() {
1454     ///     value.push_str("!");
1455     /// }
1456     ///
1457     /// let values: Vec<String> = a.values().cloned().collect();
1458     /// assert_eq!(values, [String::from("hello!"),
1459     ///                     String::from("goodbye!")]);
1460     /// ```
1461     #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1462     pub fn values_mut<'a>(&'a mut self) -> ValuesMut<'a, K, V> {
1463         ValuesMut { inner: self.iter_mut() }
1464     }
1465
1466     /// Returns the number of elements in the map.
1467     ///
1468     /// # Examples
1469     ///
1470     /// Basic usage:
1471     ///
1472     /// ```
1473     /// use std::collections::BTreeMap;
1474     ///
1475     /// let mut a = BTreeMap::new();
1476     /// assert_eq!(a.len(), 0);
1477     /// a.insert(1, "a");
1478     /// assert_eq!(a.len(), 1);
1479     /// ```
1480     #[stable(feature = "rust1", since = "1.0.0")]
1481     pub fn len(&self) -> usize {
1482         self.length
1483     }
1484
1485     /// Returns true if the map contains no elements.
1486     ///
1487     /// # Examples
1488     ///
1489     /// Basic usage:
1490     ///
1491     /// ```
1492     /// use std::collections::BTreeMap;
1493     ///
1494     /// let mut a = BTreeMap::new();
1495     /// assert!(a.is_empty());
1496     /// a.insert(1, "a");
1497     /// assert!(!a.is_empty());
1498     /// ```
1499     #[stable(feature = "rust1", since = "1.0.0")]
1500     pub fn is_empty(&self) -> bool {
1501         self.len() == 0
1502     }
1503 }
1504
1505 impl<'a, K: Ord, V> Entry<'a, K, V> {
1506     /// Ensures a value is in the entry by inserting the default if empty, and returns
1507     /// a mutable reference to the value in the entry.
1508     #[stable(feature = "rust1", since = "1.0.0")]
1509     pub fn or_insert(self, default: V) -> &'a mut V {
1510         match self {
1511             Occupied(entry) => entry.into_mut(),
1512             Vacant(entry) => entry.insert(default),
1513         }
1514     }
1515
1516     /// Ensures a value is in the entry by inserting the result of the default function if empty,
1517     /// and returns a mutable reference to the value in the entry.
1518     #[stable(feature = "rust1", since = "1.0.0")]
1519     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1520         match self {
1521             Occupied(entry) => entry.into_mut(),
1522             Vacant(entry) => entry.insert(default()),
1523         }
1524     }
1525 }
1526
1527 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1528     /// Gets a reference to the key that would be used when inserting a value
1529     /// through the VacantEntry.
1530     #[unstable(feature = "map_entry_keys", issue = "32281")]
1531     pub fn key(&self) -> &K {
1532         &self.key
1533     }
1534
1535     /// Sets the value of the entry with the VacantEntry's key,
1536     /// and returns a mutable reference to it.
1537     #[stable(feature = "rust1", since = "1.0.0")]
1538     pub fn insert(self, value: V) -> &'a mut V {
1539         *self.length += 1;
1540
1541         let out_ptr;
1542
1543         let mut ins_k;
1544         let mut ins_v;
1545         let mut ins_edge;
1546
1547         let mut cur_parent = match self.handle.insert(self.key, value) {
1548             (Fit(handle), _) => return handle.into_kv_mut().1,
1549             (Split(left, k, v, right), ptr) => {
1550                 ins_k = k;
1551                 ins_v = v;
1552                 ins_edge = right;
1553                 out_ptr = ptr;
1554                 left.ascend().map_err(|n| n.into_root_mut())
1555             }
1556         };
1557
1558         loop {
1559             match cur_parent {
1560                 Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
1561                     Fit(_) => return unsafe { &mut *out_ptr },
1562                     Split(left, k, v, right) => {
1563                         ins_k = k;
1564                         ins_v = v;
1565                         ins_edge = right;
1566                         cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1567                     }
1568                 },
1569                 Err(root) => {
1570                     root.push_level().push(ins_k, ins_v, ins_edge);
1571                     return unsafe { &mut *out_ptr };
1572                 }
1573             }
1574         }
1575     }
1576 }
1577
1578 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1579     /// Gets a reference to the key in the entry.
1580     #[unstable(feature = "map_entry_keys", issue = "32281")]
1581     pub fn key(&self) -> &K {
1582         self.handle.reborrow().into_kv().0
1583     }
1584
1585     /// Gets a reference to the value in the entry.
1586     #[stable(feature = "rust1", since = "1.0.0")]
1587     pub fn get(&self) -> &V {
1588         self.handle.reborrow().into_kv().1
1589     }
1590
1591     /// Gets a mutable reference to the value in the entry.
1592     #[stable(feature = "rust1", since = "1.0.0")]
1593     pub fn get_mut(&mut self) -> &mut V {
1594         self.handle.kv_mut().1
1595     }
1596
1597     /// Converts the entry into a mutable reference to its value.
1598     #[stable(feature = "rust1", since = "1.0.0")]
1599     pub fn into_mut(self) -> &'a mut V {
1600         self.handle.into_kv_mut().1
1601     }
1602
1603     /// Sets the value of the entry with the OccupiedEntry's key,
1604     /// and returns the entry's old value.
1605     #[stable(feature = "rust1", since = "1.0.0")]
1606     pub fn insert(&mut self, value: V) -> V {
1607         mem::replace(self.get_mut(), value)
1608     }
1609
1610     /// Takes the value of the entry out of the map, and returns it.
1611     #[stable(feature = "rust1", since = "1.0.0")]
1612     pub fn remove(self) -> V {
1613         self.remove_kv().1
1614     }
1615
1616     fn remove_kv(self) -> (K, V) {
1617         *self.length -= 1;
1618
1619         let (small_leaf, old_key, old_val) = match self.handle.force() {
1620             Leaf(leaf) => {
1621                 let (hole, old_key, old_val) = leaf.remove();
1622                 (hole.into_node(), old_key, old_val)
1623             },
1624             Internal(mut internal) => {
1625                 let key_loc = internal.kv_mut().0 as *mut K;
1626                 let val_loc = internal.kv_mut().1 as *mut V;
1627
1628                 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1629                 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1630
1631                 let (hole, key, val) = to_remove.remove();
1632
1633                 let old_key = unsafe {
1634                     mem::replace(&mut *key_loc, key)
1635                 };
1636                 let old_val = unsafe {
1637                     mem::replace(&mut *val_loc, val)
1638                 };
1639
1640                 (hole.into_node(), old_key, old_val)
1641             }
1642         };
1643
1644         // Handle underflow
1645         let mut cur_node = small_leaf.forget_type();
1646         while cur_node.len() < node::CAPACITY / 2 {
1647             match handle_underfull_node(cur_node) {
1648                 AtRoot => break,
1649                 EmptyParent(_) => unreachable!(),
1650                 Merged(parent) => if parent.len() == 0 {
1651                     // We must be at the root
1652                     parent.into_root_mut().pop_level();
1653                     break;
1654                 } else {
1655                     cur_node = parent.forget_type();
1656                 },
1657                 Stole(_) => break
1658             }
1659         }
1660
1661         (old_key, old_val)
1662     }
1663 }
1664
1665 enum UnderflowResult<'a, K, V> {
1666     AtRoot,
1667     EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1668     Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1669     Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
1670 }
1671
1672 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
1673                                                  K, V,
1674                                                  marker::LeafOrInternal>)
1675                                                  -> UnderflowResult<'a, K, V> {
1676     let parent = if let Ok(parent) = node.ascend() {
1677         parent
1678     } else {
1679         return AtRoot;
1680     };
1681
1682     let (is_left, mut handle) = match parent.left_kv() {
1683         Ok(left) => (true, left),
1684         Err(parent) => match parent.right_kv() {
1685             Ok(right) => (false, right),
1686             Err(parent) => {
1687                 return EmptyParent(parent.into_node());
1688             }
1689         }
1690     };
1691
1692     if handle.can_merge() {
1693         return Merged(handle.merge().into_node());
1694     } else {
1695         unsafe {
1696             let (k, v, edge) = if is_left {
1697                 handle.reborrow_mut().left_edge().descend().pop()
1698             } else {
1699                 handle.reborrow_mut().right_edge().descend().pop_front()
1700             };
1701
1702             let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
1703             let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
1704
1705             // FIXME: reuse cur_node?
1706             if is_left {
1707                 match handle.reborrow_mut().right_edge().descend().force() {
1708                     Leaf(mut leaf) => leaf.push_front(k, v),
1709                     Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
1710                 }
1711             } else {
1712                 match handle.reborrow_mut().left_edge().descend().force() {
1713                     Leaf(mut leaf) => leaf.push(k, v),
1714                     Internal(mut internal) => internal.push(k, v, edge.unwrap())
1715                 }
1716             }
1717         }
1718
1719         return Stole(handle.into_node());
1720     }
1721 }