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