src/liballoc/collections/btree/map.rs

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