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.
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.
11 use core
::cmp
::Ordering
;
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}
;
18 use core
::ops
::RangeBounds
;
19 use core
::{fmt, intrinsics, mem, ptr}
;
23 use super::node
::{self, Handle, NodeRef, marker}
;
26 use super::node
::InsertResult
::*;
27 use super::node
::ForceResult
::*;
28 use super::search
::SearchResult
::*;
29 use self::UnderflowResult
::*;
32 /// A map based on a B-Tree.
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
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.
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.
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.
63 /// [`Ord`]: ../../std/cmp/trait.Ord.html
64 /// [`Cell`]: ../../std/cell/struct.Cell.html
65 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
70 /// use std::collections::BTreeMap;
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();
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 alot.");
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());
88 /// // oops, this review has a lot of spelling mistakes, let's delete it.
89 /// movie_reviews.remove("The Blues Brothers");
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)
100 /// // iterate over everything.
101 /// for (movie, review) in &movie_reviews {
102 /// println!("{}: \"{}\"", movie, review);
106 /// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
107 /// for more complex methods of getting, setting, updating and removing keys and
111 /// use std::collections::BTreeMap;
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();
117 /// fn random_stat_buff() -> u8 {
118 /// // could actually return some random value here - let's just return
119 /// // some fixed value for now
123 /// // insert a key only if it doesn't already exist
124 /// player_stats.entry("health").or_insert(100);
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);
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();
134 #[stable(feature = "rust1", since = "1.0.0")]
135 pub struct BTreeMap
<K
, V
> {
136 root
: node
::Root
<K
, V
>,
140 #[stable(feature = "btree_drop", since = "1.7.0")]
141 unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> {
144 drop(ptr
::read(self).into_iter());
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
<K
: Clone
, V
: Clone
>(node
: node
::NodeRef
<marker
::Immut
,
155 marker
::LeafOrInternal
>)
160 let mut out_tree
= BTreeMap
{
161 root
: node
::Root
::new_leaf(),
166 let mut out_node
= match out_tree
.root
.as_mut().force() {
168 Internal(_
) => unreachable
!(),
171 let mut in_edge
= leaf
.first_edge();
172 while let Ok(kv
) = in_edge
.right_kv() {
173 let (k
, v
) = kv
.into_kv();
174 in_edge
= kv
.right_edge();
176 out_node
.push(k
.clone(), v
.clone());
177 out_tree
.length
+= 1;
183 Internal(internal
) => {
184 let mut out_tree
= clone_subtree(internal
.first_edge().descend());
187 let mut out_node
= out_tree
.root
.push_level();
188 let mut in_edge
= internal
.first_edge();
189 while let Ok(kv
) = in_edge
.right_kv() {
190 let (k
, v
) = kv
.into_kv();
191 in_edge
= kv
.right_edge();
193 let k
= (*k
).clone();
194 let v
= (*v
).clone();
195 let subtree
= clone_subtree(in_edge
.descend());
197 // We can't destructure subtree directly
198 // because BTreeMap implements Drop
199 let (subroot
, sublength
) = unsafe {
200 let root
= ptr
::read(&subtree
.root
);
201 let length
= subtree
.length
;
202 mem
::forget(subtree
);
206 out_node
.push(k
, v
, subroot
);
207 out_tree
.length
+= 1 + sublength
;
216 clone_subtree(self.root
.as_ref())
220 impl<K
, Q
: ?Sized
> super::Recover
<Q
> for BTreeMap
<K
, ()>
221 where K
: Borrow
<Q
> + Ord
,
226 fn get(&self, key
: &Q
) -> Option
<&K
> {
227 match search
::search_tree(self.root
.as_ref(), key
) {
228 Found(handle
) => Some(handle
.into_kv().0),
233 fn take(&mut self, key
: &Q
) -> Option
<K
> {
234 match search
::search_tree(self.root
.as_mut(), key
) {
238 length
: &mut self.length
,
239 _marker
: PhantomData
,
248 fn replace(&mut self, key
: K
) -> Option
<K
> {
249 self.ensure_root_is_owned();
250 match search
::search_tree
::<marker
::Mut
, K
, (), K
>(self.root
.as_mut(), &key
) {
251 Found(handle
) => Some(mem
::replace(handle
.into_kv_mut().0, key
)),
256 length
: &mut self.length
,
257 _marker
: PhantomData
,
266 /// An iterator over the entries of a `BTreeMap`.
268 /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
269 /// documentation for more.
271 /// [`iter`]: struct.BTreeMap.html#method.iter
272 /// [`BTreeMap`]: struct.BTreeMap.html
273 #[stable(feature = "rust1", since = "1.0.0")]
274 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
275 range
: Range
<'a
, K
, V
>,
279 #[stable(feature = "collection_debug", since = "1.17.0")]
280 impl<'a
, K
: 'a
+ fmt
::Debug
, V
: 'a
+ fmt
::Debug
> fmt
::Debug
for Iter
<'a
, K
, V
> {
281 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
282 f
.debug_list().entries(self.clone()).finish()
286 /// A mutable iterator over the entries of a `BTreeMap`.
288 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
289 /// documentation for more.
291 /// [`iter_mut`]: struct.BTreeMap.html#method.iter_mut
292 /// [`BTreeMap`]: struct.BTreeMap.html
293 #[stable(feature = "rust1", since = "1.0.0")]
295 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
296 range
: RangeMut
<'a
, K
, V
>,
300 /// An owning iterator over the entries of a `BTreeMap`.
302 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`][`BTreeMap`]
303 /// (provided by the `IntoIterator` trait). See its documentation for more.
305 /// [`into_iter`]: struct.BTreeMap.html#method.into_iter
306 /// [`BTreeMap`]: struct.BTreeMap.html
307 #[stable(feature = "rust1", since = "1.0.0")]
308 pub struct IntoIter
<K
, V
> {
309 front
: Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
310 back
: Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
314 #[stable(feature = "collection_debug", since = "1.17.0")]
315 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for IntoIter
<K
, V
> {
316 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
318 front
: self.front
.reborrow(),
319 back
: self.back
.reborrow(),
321 f
.debug_list().entries(range
).finish()
325 /// An iterator over the keys of a `BTreeMap`.
327 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
328 /// documentation for more.
330 /// [`keys`]: struct.BTreeMap.html#method.keys
331 /// [`BTreeMap`]: struct.BTreeMap.html
332 #[stable(feature = "rust1", since = "1.0.0")]
333 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
334 inner
: Iter
<'a
, K
, V
>,
337 #[stable(feature = "collection_debug", since = "1.17.0")]
338 impl<'a
, K
: 'a
+ fmt
::Debug
, V
: 'a
> fmt
::Debug
for Keys
<'a
, K
, V
> {
339 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
340 f
.debug_list().entries(self.clone()).finish()
344 /// An iterator over the values of a `BTreeMap`.
346 /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
347 /// documentation for more.
349 /// [`values`]: struct.BTreeMap.html#method.values
350 /// [`BTreeMap`]: struct.BTreeMap.html
351 #[stable(feature = "rust1", since = "1.0.0")]
352 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
353 inner
: Iter
<'a
, K
, V
>,
356 #[stable(feature = "collection_debug", since = "1.17.0")]
357 impl<'a
, K
: 'a
, V
: 'a
+ fmt
::Debug
> fmt
::Debug
for Values
<'a
, K
, V
> {
358 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
359 f
.debug_list().entries(self.clone()).finish()
363 /// A mutable iterator over the values of a `BTreeMap`.
365 /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
366 /// documentation for more.
368 /// [`values_mut`]: struct.BTreeMap.html#method.values_mut
369 /// [`BTreeMap`]: struct.BTreeMap.html
370 #[stable(feature = "map_values_mut", since = "1.10.0")]
372 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
373 inner
: IterMut
<'a
, K
, V
>,
376 /// An iterator over a sub-range of entries in a `BTreeMap`.
378 /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
379 /// documentation for more.
381 /// [`range`]: struct.BTreeMap.html#method.range
382 /// [`BTreeMap`]: struct.BTreeMap.html
383 #[stable(feature = "btree_range", since = "1.17.0")]
384 pub struct Range
<'a
, K
: 'a
, V
: 'a
> {
385 front
: Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
386 back
: Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
389 #[stable(feature = "collection_debug", since = "1.17.0")]
390 impl<'a
, K
: 'a
+ fmt
::Debug
, V
: 'a
+ fmt
::Debug
> fmt
::Debug
for Range
<'a
, K
, V
> {
391 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
392 f
.debug_list().entries(self.clone()).finish()
396 /// A mutable iterator over a sub-range of entries in a `BTreeMap`.
398 /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
399 /// documentation for more.
401 /// [`range_mut`]: struct.BTreeMap.html#method.range_mut
402 /// [`BTreeMap`]: struct.BTreeMap.html
403 #[stable(feature = "btree_range", since = "1.17.0")]
404 pub struct RangeMut
<'a
, K
: 'a
, V
: 'a
> {
405 front
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
406 back
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
408 // Be invariant in `K` and `V`
409 _marker
: PhantomData
<&'a
mut (K
, V
)>,
412 #[stable(feature = "collection_debug", since = "1.17.0")]
413 impl<'a
, K
: 'a
+ fmt
::Debug
, V
: 'a
+ fmt
::Debug
> fmt
::Debug
for RangeMut
<'a
, K
, V
> {
414 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
416 front
: self.front
.reborrow(),
417 back
: self.back
.reborrow(),
419 f
.debug_list().entries(range
).finish()
423 /// A view into a single entry in a map, which may either be vacant or occupied.
425 /// This `enum` is constructed from the [`entry`] method on [`BTreeMap`].
427 /// [`BTreeMap`]: struct.BTreeMap.html
428 /// [`entry`]: struct.BTreeMap.html#method.entry
429 #[stable(feature = "rust1", since = "1.0.0")]
430 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
432 #[stable(feature = "rust1", since = "1.0.0")]
433 Vacant(#[stable(feature = "rust1", since = "1.0.0")]
434 VacantEntry
<'a
, K
, V
>),
436 /// An occupied entry.
437 #[stable(feature = "rust1", since = "1.0.0")]
438 Occupied(#[stable(feature = "rust1", since = "1.0.0")]
439 OccupiedEntry
<'a
, K
, V
>),
442 #[stable(feature= "debug_btree_map", since = "1.12.0")]
443 impl<'a
, K
: 'a
+ Debug
+ Ord
, V
: 'a
+ Debug
> Debug
for Entry
<'a
, K
, V
> {
444 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
446 Vacant(ref v
) => f
.debug_tuple("Entry")
449 Occupied(ref o
) => f
.debug_tuple("Entry")
456 /// A view into a vacant entry in a `BTreeMap`.
457 /// It is part of the [`Entry`] enum.
459 /// [`Entry`]: enum.Entry.html
460 #[stable(feature = "rust1", since = "1.0.0")]
461 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
463 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
464 length
: &'a
mut usize,
466 // Be invariant in `K` and `V`
467 _marker
: PhantomData
<&'a
mut (K
, V
)>,
470 #[stable(feature= "debug_btree_map", since = "1.12.0")]
471 impl<'a
, K
: 'a
+ Debug
+ Ord
, V
: 'a
> Debug
for VacantEntry
<'a
, K
, V
> {
472 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
473 f
.debug_tuple("VacantEntry")
479 /// A view into an occupied entry in a `BTreeMap`.
480 /// It is part of the [`Entry`] enum.
482 /// [`Entry`]: enum.Entry.html
483 #[stable(feature = "rust1", since = "1.0.0")]
484 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
485 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::LeafOrInternal
>, marker
::KV
>,
487 length
: &'a
mut usize,
489 // Be invariant in `K` and `V`
490 _marker
: PhantomData
<&'a
mut (K
, V
)>,
493 #[stable(feature= "debug_btree_map", since = "1.12.0")]
494 impl<'a
, K
: 'a
+ Debug
+ Ord
, V
: 'a
+ Debug
> Debug
for OccupiedEntry
<'a
, K
, V
> {
495 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
496 f
.debug_struct("OccupiedEntry")
497 .field("key", self.key())
498 .field("value", self.get())
503 // An iterator for merging two sorted sequences into one
504 struct MergeIter
<K
, V
, I
: Iterator
<Item
= (K
, V
)>> {
509 impl<K
: Ord
, V
> BTreeMap
<K
, V
> {
510 /// Makes a new empty BTreeMap with a reasonable choice for B.
517 /// use std::collections::BTreeMap;
519 /// let mut map = BTreeMap::new();
521 /// // entries can now be inserted into the empty map
522 /// map.insert(1, "a");
524 #[stable(feature = "rust1", since = "1.0.0")]
525 pub fn new() -> BTreeMap
<K
, V
> {
527 root
: node
::Root
::shared_empty_root(),
532 /// Clears the map, removing all values.
539 /// use std::collections::BTreeMap;
541 /// let mut a = BTreeMap::new();
542 /// a.insert(1, "a");
544 /// assert!(a.is_empty());
546 #[stable(feature = "rust1", since = "1.0.0")]
547 pub fn clear(&mut self) {
548 *self = BTreeMap
::new();
551 /// Returns a reference to the value corresponding to the key.
553 /// The key may be any borrowed form of the map's key type, but the ordering
554 /// on the borrowed form *must* match the ordering on the key type.
561 /// use std::collections::BTreeMap;
563 /// let mut map = BTreeMap::new();
564 /// map.insert(1, "a");
565 /// assert_eq!(map.get(&1), Some(&"a"));
566 /// assert_eq!(map.get(&2), None);
568 #[stable(feature = "rust1", since = "1.0.0")]
569 pub fn get
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<&V
>
573 match search
::search_tree(self.root
.as_ref(), key
) {
574 Found(handle
) => Some(handle
.into_kv().1),
579 /// Returns the key-value pair corresponding to the supplied key.
581 /// The supplied key may be any borrowed form of the map's key type, but the ordering
582 /// on the borrowed form *must* match the ordering on the key type.
587 /// #![feature(map_get_key_value)]
588 /// use std::collections::BTreeMap;
590 /// let mut map = BTreeMap::new();
591 /// map.insert(1, "a");
592 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
593 /// assert_eq!(map.get_key_value(&2), None);
595 #[unstable(feature = "map_get_key_value", issue = "49347")]
596 pub fn get_key_value
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<(&K
, &V
)>
600 match search
::search_tree(self.root
.as_ref(), k
) {
601 Found(handle
) => Some(handle
.into_kv()),
606 /// Returns `true` if the map contains a value for the specified key.
608 /// The key may be any borrowed form of the map's key type, but the ordering
609 /// on the borrowed form *must* match the ordering on the key type.
616 /// use std::collections::BTreeMap;
618 /// let mut map = BTreeMap::new();
619 /// map.insert(1, "a");
620 /// assert_eq!(map.contains_key(&1), true);
621 /// assert_eq!(map.contains_key(&2), false);
623 #[stable(feature = "rust1", since = "1.0.0")]
624 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
628 self.get(key
).is_some()
631 /// Returns a mutable reference to the value corresponding to the key.
633 /// The key may be any borrowed form of the map's key type, but the ordering
634 /// on the borrowed form *must* match the ordering on the key type.
641 /// use std::collections::BTreeMap;
643 /// let mut map = BTreeMap::new();
644 /// map.insert(1, "a");
645 /// if let Some(x) = map.get_mut(&1) {
648 /// assert_eq!(map[&1], "b");
650 // See `get` for implementation notes, this is basically a copy-paste with mut's added
651 #[stable(feature = "rust1", since = "1.0.0")]
652 pub fn get_mut
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<&mut V
>
656 match search
::search_tree(self.root
.as_mut(), key
) {
657 Found(handle
) => Some(handle
.into_kv_mut().1),
662 /// Inserts a key-value pair into the map.
664 /// If the map did not have this key present, `None` is returned.
666 /// If the map did have this key present, the value is updated, and the old
667 /// value is returned. The key is not updated, though; this matters for
668 /// types that can be `==` without being identical. See the [module-level
669 /// documentation] for more.
671 /// [module-level documentation]: index.html#insert-and-complex-keys
678 /// use std::collections::BTreeMap;
680 /// let mut map = BTreeMap::new();
681 /// assert_eq!(map.insert(37, "a"), None);
682 /// assert_eq!(map.is_empty(), false);
684 /// map.insert(37, "b");
685 /// assert_eq!(map.insert(37, "c"), Some("b"));
686 /// assert_eq!(map[&37], "c");
688 #[stable(feature = "rust1", since = "1.0.0")]
689 pub fn insert(&mut self, key
: K
, value
: V
) -> Option
<V
> {
690 match self.entry(key
) {
691 Occupied(mut entry
) => Some(entry
.insert(value
)),
699 /// Removes a key from the map, returning the value at the key if the key
700 /// was previously in the map.
702 /// The key may be any borrowed form of the map's key type, but the ordering
703 /// on the borrowed form *must* match the ordering on the key type.
710 /// use std::collections::BTreeMap;
712 /// let mut map = BTreeMap::new();
713 /// map.insert(1, "a");
714 /// assert_eq!(map.remove(&1), Some("a"));
715 /// assert_eq!(map.remove(&1), None);
717 #[stable(feature = "rust1", since = "1.0.0")]
718 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
>
722 match search
::search_tree(self.root
.as_mut(), key
) {
726 length
: &mut self.length
,
727 _marker
: PhantomData
,
735 /// Moves all elements from `other` into `Self`, leaving `other` empty.
740 /// use std::collections::BTreeMap;
742 /// let mut a = BTreeMap::new();
743 /// a.insert(1, "a");
744 /// a.insert(2, "b");
745 /// a.insert(3, "c");
747 /// let mut b = BTreeMap::new();
748 /// b.insert(3, "d");
749 /// b.insert(4, "e");
750 /// b.insert(5, "f");
752 /// a.append(&mut b);
754 /// assert_eq!(a.len(), 5);
755 /// assert_eq!(b.len(), 0);
757 /// assert_eq!(a[&1], "a");
758 /// assert_eq!(a[&2], "b");
759 /// assert_eq!(a[&3], "d");
760 /// assert_eq!(a[&4], "e");
761 /// assert_eq!(a[&5], "f");
763 #[stable(feature = "btree_append", since = "1.11.0")]
764 pub fn append(&mut self, other
: &mut Self) {
765 // Do we have to append anything at all?
766 if other
.len() == 0 {
770 // We can just swap `self` and `other` if `self` is empty.
772 mem
::swap(self, other
);
776 // First, we merge `self` and `other` into a sorted sequence in linear time.
777 let self_iter
= mem
::replace(self, BTreeMap
::new()).into_iter();
778 let other_iter
= mem
::replace(other
, BTreeMap
::new()).into_iter();
779 let iter
= MergeIter
{
780 left
: self_iter
.peekable(),
781 right
: other_iter
.peekable(),
784 // Second, we build a tree from the sorted sequence in linear time.
785 self.from_sorted_iter(iter
);
786 self.fix_right_edge();
789 /// Constructs a double-ended iterator over a sub-range of elements in the map.
790 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
791 /// yield elements from min (inclusive) to max (exclusive).
792 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
793 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
794 /// range from 4 to 10.
798 /// Panics if range `start > end`.
799 /// Panics if range `start == end` and both bounds are `Excluded`.
806 /// use std::collections::BTreeMap;
807 /// use std::ops::Bound::Included;
809 /// let mut map = BTreeMap::new();
810 /// map.insert(3, "a");
811 /// map.insert(5, "b");
812 /// map.insert(8, "c");
813 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
814 /// println!("{}: {}", key, value);
816 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
818 #[stable(feature = "btree_range", since = "1.17.0")]
819 pub fn range
<T
: ?Sized
, R
>(&self, range
: R
) -> Range
<K
, V
>
820 where T
: Ord
, K
: Borrow
<T
>, R
: RangeBounds
<T
>
822 let root1
= self.root
.as_ref();
823 let root2
= self.root
.as_ref();
824 let (f
, b
) = range_search(root1
, root2
, range
);
826 Range { front: f, back: b}
829 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
830 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
831 /// yield elements from min (inclusive) to max (exclusive).
832 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
833 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
834 /// range from 4 to 10.
838 /// Panics if range `start > end`.
839 /// Panics if range `start == end` and both bounds are `Excluded`.
846 /// use std::collections::BTreeMap;
848 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
849 /// .map(|&s| (s, 0))
851 /// for (_, balance) in map.range_mut("B".."Cheryl") {
854 /// for (name, balance) in &map {
855 /// println!("{} => {}", name, balance);
858 #[stable(feature = "btree_range", since = "1.17.0")]
859 pub fn range_mut
<T
: ?Sized
, R
>(&mut self, range
: R
) -> RangeMut
<K
, V
>
860 where T
: Ord
, K
: Borrow
<T
>, R
: RangeBounds
<T
>
862 let root1
= self.root
.as_mut();
863 let root2
= unsafe { ptr::read(&root1) }
;
864 let (f
, b
) = range_search(root1
, root2
, range
);
869 _marker
: PhantomData
,
873 /// Gets the given key's corresponding entry in the map for in-place manipulation.
880 /// use std::collections::BTreeMap;
882 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
884 /// // count the number of occurrences of letters in the vec
885 /// for x in vec!["a","b","a","c","a","b"] {
886 /// *count.entry(x).or_insert(0) += 1;
889 /// assert_eq!(count["a"], 3);
891 #[stable(feature = "rust1", since = "1.0.0")]
892 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
893 // FIXME(@porglezomp) Avoid allocating if we don't insert
894 self.ensure_root_is_owned();
895 match search
::search_tree(self.root
.as_mut(), &key
) {
897 Occupied(OccupiedEntry
{
899 length
: &mut self.length
,
900 _marker
: PhantomData
,
907 length
: &mut self.length
,
908 _marker
: PhantomData
,
914 fn from_sorted_iter
<I
: Iterator
<Item
= (K
, V
)>>(&mut self, iter
: I
) {
915 self.ensure_root_is_owned();
916 let mut cur_node
= last_leaf_edge(self.root
.as_mut()).into_node();
917 // Iterate through all key-value pairs, pushing them into nodes at the right level.
918 for (key
, value
) in iter
{
919 // Try to push key-value pair into the current leaf node.
920 if cur_node
.len() < node
::CAPACITY
{
921 cur_node
.push(key
, value
);
923 // No space left, go up and push there.
925 let mut test_node
= cur_node
.forget_type();
927 match test_node
.ascend() {
929 let parent
= parent
.into_node();
930 if parent
.len() < node
::CAPACITY
{
931 // Found a node with space left, push here.
936 test_node
= parent
.forget_type();
940 // We are at the top, create a new root node and push there.
941 open_node
= node
.into_root_mut().push_level();
947 // Push key-value pair and new right subtree.
948 let tree_height
= open_node
.height() - 1;
949 let mut right_tree
= node
::Root
::new_leaf();
950 for _
in 0..tree_height
{
951 right_tree
.push_level();
953 open_node
.push(key
, value
, right_tree
);
955 // Go down to the right-most leaf again.
956 cur_node
= last_leaf_edge(open_node
.forget_type()).into_node();
963 fn fix_right_edge(&mut self) {
964 // Handle underfull nodes, start from the top.
965 let mut cur_node
= self.root
.as_mut();
966 while let Internal(internal
) = cur_node
.force() {
967 // Check if right-most child is underfull.
968 let mut last_edge
= internal
.last_edge();
969 let right_child_len
= last_edge
.reborrow().descend().len();
970 if right_child_len
< node
::MIN_LEN
{
972 let mut last_kv
= match last_edge
.left_kv() {
974 Err(_
) => unreachable
!(),
976 last_kv
.bulk_steal_left(node
::MIN_LEN
- right_child_len
);
977 last_edge
= last_kv
.right_edge();
981 cur_node
= last_edge
.descend();
985 /// Splits the collection into two at the given key. Returns everything after the given key,
986 /// including the key.
993 /// use std::collections::BTreeMap;
995 /// let mut a = BTreeMap::new();
996 /// a.insert(1, "a");
997 /// a.insert(2, "b");
998 /// a.insert(3, "c");
999 /// a.insert(17, "d");
1000 /// a.insert(41, "e");
1002 /// let b = a.split_off(&3);
1004 /// assert_eq!(a.len(), 2);
1005 /// assert_eq!(b.len(), 3);
1007 /// assert_eq!(a[&1], "a");
1008 /// assert_eq!(a[&2], "b");
1010 /// assert_eq!(b[&3], "c");
1011 /// assert_eq!(b[&17], "d");
1012 /// assert_eq!(b[&41], "e");
1014 #[stable(feature = "btree_split_off", since = "1.11.0")]
1015 pub fn split_off
<Q
: ?Sized
+ Ord
>(&mut self, key
: &Q
) -> Self
1018 if self.is_empty() {
1022 let total_num
= self.len();
1024 let mut right
= Self::new();
1025 right
.root
= node
::Root
::new_leaf();
1026 for _
in 0..(self.root
.as_ref().height()) {
1027 right
.root
.push_level();
1031 let mut left_node
= self.root
.as_mut();
1032 let mut right_node
= right
.root
.as_mut();
1035 let mut split_edge
= match search
::search_node(left_node
, key
) {
1036 // key is going to the right tree
1037 Found(handle
) => handle
.left_edge(),
1038 GoDown(handle
) => handle
,
1041 split_edge
.move_suffix(&mut right_node
);
1043 match (split_edge
.force(), right_node
.force()) {
1044 (Internal(edge
), Internal(node
)) => {
1045 left_node
= edge
.descend();
1046 right_node
= node
.first_edge().descend();
1048 (Leaf(_
), Leaf(_
)) => {
1058 self.fix_right_border();
1059 right
.fix_left_border();
1061 if self.root
.as_ref().height() < right
.root
.as_ref().height() {
1062 self.recalc_length();
1063 right
.length
= total_num
- self.len();
1065 right
.recalc_length();
1066 self.length
= total_num
- right
.len();
1072 /// Calculates the number of elements if it is incorrect.
1073 fn recalc_length(&mut self) {
1074 fn dfs
<K
, V
>(node
: NodeRef
<marker
::Immut
, K
, V
, marker
::LeafOrInternal
>) -> usize {
1075 let mut res
= node
.len();
1077 if let Internal(node
) = node
.force() {
1078 let mut edge
= node
.first_edge();
1080 res
+= dfs(edge
.reborrow().descend());
1081 match edge
.right_kv() {
1083 edge
= right_kv
.right_edge();
1095 self.length
= dfs(self.root
.as_ref());
1098 /// Removes empty levels on the top.
1099 fn fix_top(&mut self) {
1102 let node
= self.root
.as_ref();
1103 if node
.height() == 0 || node
.len() > 0 {
1107 self.root
.pop_level();
1111 fn fix_right_border(&mut self) {
1115 let mut cur_node
= self.root
.as_mut();
1117 while let Internal(node
) = cur_node
.force() {
1118 let mut last_kv
= node
.last_kv();
1120 if last_kv
.can_merge() {
1121 cur_node
= last_kv
.merge().descend();
1123 let right_len
= last_kv
.reborrow().right_edge().descend().len();
1124 // `MINLEN + 1` to avoid readjust if merge happens on the next level.
1125 if right_len
< node
::MIN_LEN
+ 1 {
1126 last_kv
.bulk_steal_left(node
::MIN_LEN
+ 1 - right_len
);
1128 cur_node
= last_kv
.right_edge().descend();
1136 /// The symmetric clone of `fix_right_border`.
1137 fn fix_left_border(&mut self) {
1141 let mut cur_node
= self.root
.as_mut();
1143 while let Internal(node
) = cur_node
.force() {
1144 let mut first_kv
= node
.first_kv();
1146 if first_kv
.can_merge() {
1147 cur_node
= first_kv
.merge().descend();
1149 let left_len
= first_kv
.reborrow().left_edge().descend().len();
1150 if left_len
< node
::MIN_LEN
+ 1 {
1151 first_kv
.bulk_steal_right(node
::MIN_LEN
+ 1 - left_len
);
1153 cur_node
= first_kv
.left_edge().descend();
1161 /// If the root node is the shared root node, allocate our own node.
1162 fn ensure_root_is_owned(&mut self) {
1163 if self.root
.is_shared_root() {
1164 self.root
= node
::Root
::new_leaf();
1169 #[stable(feature = "rust1", since = "1.0.0")]
1170 impl<'a
, K
: 'a
, V
: 'a
> IntoIterator
for &'a BTreeMap
<K
, V
> {
1171 type Item
= (&'a K
, &'a V
);
1172 type IntoIter
= Iter
<'a
, K
, V
>;
1174 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1179 #[stable(feature = "rust1", since = "1.0.0")]
1180 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for Iter
<'a
, K
, V
> {
1181 type Item
= (&'a K
, &'a V
);
1183 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1184 if self.length
== 0 {
1188 unsafe { Some(self.range.next_unchecked()) }
1192 fn size_hint(&self) -> (usize, Option
<usize>) {
1193 (self.length
, Some(self.length
))
1197 #[stable(feature = "fused", since = "1.26.0")]
1198 impl<'a
, K
, V
> FusedIterator
for Iter
<'a
, K
, V
> {}
1200 #[stable(feature = "rust1", since = "1.0.0")]
1201 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
1202 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1203 if self.length
== 0 {
1207 unsafe { Some(self.range.next_back_unchecked()) }
1212 #[stable(feature = "rust1", since = "1.0.0")]
1213 impl<'a
, K
: 'a
, V
: 'a
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1214 fn len(&self) -> usize {
1219 #[stable(feature = "rust1", since = "1.0.0")]
1220 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1221 fn clone(&self) -> Iter
<'a
, K
, V
> {
1223 range
: self.range
.clone(),
1224 length
: self.length
,
1229 #[stable(feature = "rust1", since = "1.0.0")]
1230 impl<'a
, K
: 'a
, V
: 'a
> IntoIterator
for &'a
mut BTreeMap
<K
, V
> {
1231 type Item
= (&'a K
, &'a
mut V
);
1232 type IntoIter
= IterMut
<'a
, K
, V
>;
1234 fn into_iter(self) -> IterMut
<'a
, K
, V
> {
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for IterMut
<'a
, K
, V
> {
1241 type Item
= (&'a K
, &'a
mut V
);
1243 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1244 if self.length
== 0 {
1248 unsafe { Some(self.range.next_unchecked()) }
1252 fn size_hint(&self) -> (usize, Option
<usize>) {
1253 (self.length
, Some(self.length
))
1257 #[stable(feature = "rust1", since = "1.0.0")]
1258 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
1259 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1260 if self.length
== 0 {
1264 unsafe { Some(self.range.next_back_unchecked()) }
1269 #[stable(feature = "rust1", since = "1.0.0")]
1270 impl<'a
, K
: 'a
, V
: 'a
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1271 fn len(&self) -> usize {
1276 #[stable(feature = "fused", since = "1.26.0")]
1277 impl<'a
, K
, V
> FusedIterator
for IterMut
<'a
, K
, V
> {}
1279 #[stable(feature = "rust1", since = "1.0.0")]
1280 impl<K
, V
> IntoIterator
for BTreeMap
<K
, V
> {
1282 type IntoIter
= IntoIter
<K
, V
>;
1284 fn into_iter(self) -> IntoIter
<K
, V
> {
1285 let root1
= unsafe { ptr::read(&self.root).into_ref() }
;
1286 let root2
= unsafe { ptr::read(&self.root).into_ref() }
;
1287 let len
= self.length
;
1291 front
: first_leaf_edge(root1
),
1292 back
: last_leaf_edge(root2
),
1298 #[stable(feature = "btree_drop", since = "1.7.0")]
1299 impl<K
, V
> Drop
for IntoIter
<K
, V
> {
1300 fn drop(&mut self) {
1301 self.for_each(drop
);
1303 let leaf_node
= ptr
::read(&self.front
).into_node();
1304 if leaf_node
.is_shared_root() {
1308 if let Some(first_parent
) = leaf_node
.deallocate_and_ascend() {
1309 let mut cur_node
= first_parent
.into_node();
1310 while let Some(parent
) = cur_node
.deallocate_and_ascend() {
1311 cur_node
= parent
.into_node()
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1322 fn next(&mut self) -> Option
<(K
, V
)> {
1323 if self.length
== 0 {
1329 let handle
= unsafe { ptr::read(&self.front) }
;
1331 let mut cur_handle
= match handle
.right_kv() {
1333 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1334 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1335 self.front
= kv
.right_edge();
1336 return Some((k
, v
));
1338 Err(last_edge
) => unsafe {
1339 unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend())
1344 match cur_handle
.right_kv() {
1346 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1347 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1348 self.front
= first_leaf_edge(kv
.right_edge().descend());
1349 return Some((k
, v
));
1351 Err(last_edge
) => unsafe {
1352 cur_handle
= unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend());
1358 fn size_hint(&self) -> (usize, Option
<usize>) {
1359 (self.length
, Some(self.length
))
1363 #[stable(feature = "rust1", since = "1.0.0")]
1364 impl<K
, V
> DoubleEndedIterator
for IntoIter
<K
, V
> {
1365 fn next_back(&mut self) -> Option
<(K
, V
)> {
1366 if self.length
== 0 {
1372 let handle
= unsafe { ptr::read(&self.back) }
;
1374 let mut cur_handle
= match handle
.left_kv() {
1376 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1377 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1378 self.back
= kv
.left_edge();
1379 return Some((k
, v
));
1381 Err(last_edge
) => unsafe {
1382 unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend())
1387 match cur_handle
.left_kv() {
1389 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1390 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1391 self.back
= last_leaf_edge(kv
.left_edge().descend());
1392 return Some((k
, v
));
1394 Err(last_edge
) => unsafe {
1395 cur_handle
= unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend());
1402 #[stable(feature = "rust1", since = "1.0.0")]
1403 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1404 fn len(&self) -> usize {
1409 #[stable(feature = "fused", since = "1.26.0")]
1410 impl<K
, V
> FusedIterator
for IntoIter
<K
, V
> {}
1412 #[stable(feature = "rust1", since = "1.0.0")]
1413 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1416 fn next(&mut self) -> Option
<&'a K
> {
1417 self.inner
.next().map(|(k
, _
)| k
)
1420 fn size_hint(&self) -> (usize, Option
<usize>) {
1421 self.inner
.size_hint()
1425 #[stable(feature = "rust1", since = "1.0.0")]
1426 impl<'a
, K
, V
> DoubleEndedIterator
for Keys
<'a
, K
, V
> {
1427 fn next_back(&mut self) -> Option
<&'a K
> {
1428 self.inner
.next_back().map(|(k
, _
)| k
)
1432 #[stable(feature = "rust1", since = "1.0.0")]
1433 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1434 fn len(&self) -> usize {
1439 #[stable(feature = "fused", since = "1.26.0")]
1440 impl<'a
, K
, V
> FusedIterator
for Keys
<'a
, K
, V
> {}
1442 #[stable(feature = "rust1", since = "1.0.0")]
1443 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1444 fn clone(&self) -> Keys
<'a
, K
, V
> {
1445 Keys { inner: self.inner.clone() }
1449 #[stable(feature = "rust1", since = "1.0.0")]
1450 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1453 fn next(&mut self) -> Option
<&'a V
> {
1454 self.inner
.next().map(|(_
, v
)| v
)
1457 fn size_hint(&self) -> (usize, Option
<usize>) {
1458 self.inner
.size_hint()
1462 #[stable(feature = "rust1", since = "1.0.0")]
1463 impl<'a
, K
, V
> DoubleEndedIterator
for Values
<'a
, K
, V
> {
1464 fn next_back(&mut self) -> Option
<&'a V
> {
1465 self.inner
.next_back().map(|(_
, v
)| v
)
1469 #[stable(feature = "rust1", since = "1.0.0")]
1470 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1471 fn len(&self) -> usize {
1476 #[stable(feature = "fused", since = "1.26.0")]
1477 impl<'a
, K
, V
> FusedIterator
for Values
<'a
, K
, V
> {}
1479 #[stable(feature = "rust1", since = "1.0.0")]
1480 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1481 fn clone(&self) -> Values
<'a
, K
, V
> {
1482 Values { inner: self.inner.clone() }
1486 #[stable(feature = "btree_range", since = "1.17.0")]
1487 impl<'a
, K
, V
> Iterator
for Range
<'a
, K
, V
> {
1488 type Item
= (&'a K
, &'a V
);
1490 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1491 if self.front
== self.back
{
1494 unsafe { Some(self.next_unchecked()) }
1499 #[stable(feature = "map_values_mut", since = "1.10.0")]
1500 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1501 type Item
= &'a
mut V
;
1503 fn next(&mut self) -> Option
<&'a
mut V
> {
1504 self.inner
.next().map(|(_
, v
)| v
)
1507 fn size_hint(&self) -> (usize, Option
<usize>) {
1508 self.inner
.size_hint()
1512 #[stable(feature = "map_values_mut", since = "1.10.0")]
1513 impl<'a
, K
, V
> DoubleEndedIterator
for ValuesMut
<'a
, K
, V
> {
1514 fn next_back(&mut self) -> Option
<&'a
mut V
> {
1515 self.inner
.next_back().map(|(_
, v
)| v
)
1519 #[stable(feature = "map_values_mut", since = "1.10.0")]
1520 impl<'a
, K
, V
> ExactSizeIterator
for ValuesMut
<'a
, K
, V
> {
1521 fn len(&self) -> usize {
1526 #[stable(feature = "fused", since = "1.26.0")]
1527 impl<'a
, K
, V
> FusedIterator
for ValuesMut
<'a
, K
, V
> {}
1530 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1531 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a V
) {
1532 let handle
= self.front
;
1534 let mut cur_handle
= match handle
.right_kv() {
1536 let ret
= kv
.into_kv();
1537 self.front
= kv
.right_edge();
1541 let next_level
= last_edge
.into_node().ascend().ok();
1542 unwrap_unchecked(next_level
)
1547 match cur_handle
.right_kv() {
1549 let ret
= kv
.into_kv();
1550 self.front
= first_leaf_edge(kv
.right_edge().descend());
1554 let next_level
= last_edge
.into_node().ascend().ok();
1555 cur_handle
= unwrap_unchecked(next_level
);
1562 #[stable(feature = "btree_range", since = "1.17.0")]
1563 impl<'a
, K
, V
> DoubleEndedIterator
for Range
<'a
, K
, V
> {
1564 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1565 if self.front
== self.back
{
1568 unsafe { Some(self.next_back_unchecked()) }
1573 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1574 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a V
) {
1575 let handle
= self.back
;
1577 let mut cur_handle
= match handle
.left_kv() {
1579 let ret
= kv
.into_kv();
1580 self.back
= kv
.left_edge();
1584 let next_level
= last_edge
.into_node().ascend().ok();
1585 unwrap_unchecked(next_level
)
1590 match cur_handle
.left_kv() {
1592 let ret
= kv
.into_kv();
1593 self.back
= last_leaf_edge(kv
.left_edge().descend());
1597 let next_level
= last_edge
.into_node().ascend().ok();
1598 cur_handle
= unwrap_unchecked(next_level
);
1605 #[stable(feature = "fused", since = "1.26.0")]
1606 impl<'a
, K
, V
> FusedIterator
for Range
<'a
, K
, V
> {}
1608 #[stable(feature = "btree_range", since = "1.17.0")]
1609 impl<'a
, K
, V
> Clone
for Range
<'a
, K
, V
> {
1610 fn clone(&self) -> Range
<'a
, K
, V
> {
1618 #[stable(feature = "btree_range", since = "1.17.0")]
1619 impl<'a
, K
, V
> Iterator
for RangeMut
<'a
, K
, V
> {
1620 type Item
= (&'a K
, &'a
mut V
);
1622 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1623 if self.front
== self.back
{
1626 unsafe { Some(self.next_unchecked()) }
1631 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1632 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1633 let handle
= ptr
::read(&self.front
);
1635 let mut cur_handle
= match handle
.right_kv() {
1637 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1638 self.front
= kv
.right_edge();
1642 let next_level
= last_edge
.into_node().ascend().ok();
1643 unwrap_unchecked(next_level
)
1648 match cur_handle
.right_kv() {
1650 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1651 self.front
= first_leaf_edge(kv
.right_edge().descend());
1655 let next_level
= last_edge
.into_node().ascend().ok();
1656 cur_handle
= unwrap_unchecked(next_level
);
1663 #[stable(feature = "btree_range", since = "1.17.0")]
1664 impl<'a
, K
, V
> DoubleEndedIterator
for RangeMut
<'a
, K
, V
> {
1665 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1666 if self.front
== self.back
{
1669 unsafe { Some(self.next_back_unchecked()) }
1674 #[stable(feature = "fused", since = "1.26.0")]
1675 impl<'a
, K
, V
> FusedIterator
for RangeMut
<'a
, K
, V
> {}
1677 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1678 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1679 let handle
= ptr
::read(&self.back
);
1681 let mut cur_handle
= match handle
.left_kv() {
1683 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1684 self.back
= kv
.left_edge();
1688 let next_level
= last_edge
.into_node().ascend().ok();
1689 unwrap_unchecked(next_level
)
1694 match cur_handle
.left_kv() {
1696 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1697 self.back
= last_leaf_edge(kv
.left_edge().descend());
1701 let next_level
= last_edge
.into_node().ascend().ok();
1702 cur_handle
= unwrap_unchecked(next_level
);
1709 #[stable(feature = "rust1", since = "1.0.0")]
1710 impl<K
: Ord
, V
> FromIterator
<(K
, V
)> for BTreeMap
<K
, V
> {
1711 fn from_iter
<T
: IntoIterator
<Item
= (K
, V
)>>(iter
: T
) -> BTreeMap
<K
, V
> {
1712 let mut map
= BTreeMap
::new();
1718 #[stable(feature = "rust1", since = "1.0.0")]
1719 impl<K
: Ord
, V
> Extend
<(K
, V
)> for BTreeMap
<K
, V
> {
1721 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
1722 for (k
, v
) in iter
{
1728 #[stable(feature = "extend_ref", since = "1.2.0")]
1729 impl<'a
, K
: Ord
+ Copy
, V
: Copy
> Extend
<(&'a K
, &'a V
)> for BTreeMap
<K
, V
> {
1730 fn extend
<I
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: I
) {
1731 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
1735 #[stable(feature = "rust1", since = "1.0.0")]
1736 impl<K
: Hash
, V
: Hash
> Hash
for BTreeMap
<K
, V
> {
1737 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
1744 #[stable(feature = "rust1", since = "1.0.0")]
1745 impl<K
: Ord
, V
> Default
for BTreeMap
<K
, V
> {
1746 /// Creates an empty `BTreeMap<K, V>`.
1747 fn default() -> BTreeMap
<K
, V
> {
1752 #[stable(feature = "rust1", since = "1.0.0")]
1753 impl<K
: PartialEq
, V
: PartialEq
> PartialEq
for BTreeMap
<K
, V
> {
1754 fn eq(&self, other
: &BTreeMap
<K
, V
>) -> bool
{
1755 self.len() == other
.len() && self.iter().zip(other
).all(|(a
, b
)| a
== b
)
1759 #[stable(feature = "rust1", since = "1.0.0")]
1760 impl<K
: Eq
, V
: Eq
> Eq
for BTreeMap
<K
, V
> {}
1762 #[stable(feature = "rust1", since = "1.0.0")]
1763 impl<K
: PartialOrd
, V
: PartialOrd
> PartialOrd
for BTreeMap
<K
, V
> {
1765 fn partial_cmp(&self, other
: &BTreeMap
<K
, V
>) -> Option
<Ordering
> {
1766 self.iter().partial_cmp(other
.iter())
1770 #[stable(feature = "rust1", since = "1.0.0")]
1771 impl<K
: Ord
, V
: Ord
> Ord
for BTreeMap
<K
, V
> {
1773 fn cmp(&self, other
: &BTreeMap
<K
, V
>) -> Ordering
{
1774 self.iter().cmp(other
.iter())
1778 #[stable(feature = "rust1", since = "1.0.0")]
1779 impl<K
: Debug
, V
: Debug
> Debug
for BTreeMap
<K
, V
> {
1780 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1781 f
.debug_map().entries(self.iter()).finish()
1785 #[stable(feature = "rust1", since = "1.0.0")]
1786 impl<'a
, K
: Ord
, Q
: ?Sized
, V
> Index
<&'a Q
> for BTreeMap
<K
, V
>
1792 /// Returns a reference to the value corresponding to the supplied key.
1796 /// Panics if the key is not present in the `BTreeMap`.
1798 fn index(&self, key
: &Q
) -> &V
{
1799 self.get(key
).expect("no entry found for key")
1803 fn first_leaf_edge
<BorrowType
, K
, V
>
1804 (mut node
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>)
1805 -> Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
> {
1807 match node
.force() {
1808 Leaf(leaf
) => return leaf
.first_edge(),
1809 Internal(internal
) => {
1810 node
= internal
.first_edge().descend();
1816 fn last_leaf_edge
<BorrowType
, K
, V
>
1817 (mut node
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>)
1818 -> Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
> {
1820 match node
.force() {
1821 Leaf(leaf
) => return leaf
.last_edge(),
1822 Internal(internal
) => {
1823 node
= internal
.last_edge().descend();
1829 fn range_search
<BorrowType
, K
, V
, Q
: ?Sized
, R
: RangeBounds
<Q
>>(
1830 root1
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>,
1831 root2
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>,
1833 )-> (Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
1834 Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
>)
1835 where Q
: Ord
, K
: Borrow
<Q
>
1837 match (range
.start_bound(), range
.end_bound()) {
1838 (Excluded(s
), Excluded(e
)) if s
==e
=>
1839 panic
!("range start and end are equal and excluded in BTreeMap"),
1840 (Included(s
), Included(e
)) |
1841 (Included(s
), Excluded(e
)) |
1842 (Excluded(s
), Included(e
)) |
1843 (Excluded(s
), Excluded(e
)) if s
>e
=>
1844 panic
!("range start is greater than range end in BTreeMap"),
1848 let mut min_node
= root1
;
1849 let mut max_node
= root2
;
1850 let mut min_found
= false;
1851 let mut max_found
= false;
1852 let mut diverged
= false;
1855 let min_edge
= match (min_found
, range
.start_bound()) {
1856 (false, Included(key
)) => match search
::search_linear(&min_node
, key
) {
1857 (i
, true) => { min_found = true; i }
,
1860 (false, Excluded(key
)) => match search
::search_linear(&min_node
, key
) {
1861 (i
, true) => { min_found = true; i+1 }
,
1864 (_
, Unbounded
) => 0,
1865 (true, Included(_
)) => min_node
.keys().len(),
1866 (true, Excluded(_
)) => 0,
1869 let max_edge
= match (max_found
, range
.end_bound()) {
1870 (false, Included(key
)) => match search
::search_linear(&max_node
, key
) {
1871 (i
, true) => { max_found = true; i+1 }
,
1874 (false, Excluded(key
)) => match search
::search_linear(&max_node
, key
) {
1875 (i
, true) => { max_found = true; i }
,
1878 (_
, Unbounded
) => max_node
.keys().len(),
1879 (true, Included(_
)) => 0,
1880 (true, Excluded(_
)) => max_node
.keys().len(),
1884 if max_edge
< min_edge { panic!("Ord is ill-defined in BTreeMap range") }
1885 if min_edge
!= max_edge { diverged = true; }
1888 let front
= Handle
::new_edge(min_node
, min_edge
);
1889 let back
= Handle
::new_edge(max_node
, max_edge
);
1890 match (front
.force(), back
.force()) {
1891 (Leaf(f
), Leaf(b
)) => {
1894 (Internal(min_int
), Internal(max_int
)) => {
1895 min_node
= min_int
.descend();
1896 max_node
= max_int
.descend();
1898 _
=> unreachable
!("BTreeMap has different depths"),
1904 unsafe fn unwrap_unchecked
<T
>(val
: Option
<T
>) -> T
{
1905 val
.unwrap_or_else(|| {
1906 if cfg
!(debug_assertions
) {
1907 panic
!("'unchecked' unwrap on None in BTreeMap");
1909 intrinsics
::unreachable();
1914 impl<K
, V
> BTreeMap
<K
, V
> {
1915 /// Gets an iterator over the entries of the map, sorted by key.
1922 /// use std::collections::BTreeMap;
1924 /// let mut map = BTreeMap::new();
1925 /// map.insert(3, "c");
1926 /// map.insert(2, "b");
1927 /// map.insert(1, "a");
1929 /// for (key, value) in map.iter() {
1930 /// println!("{}: {}", key, value);
1933 /// let (first_key, first_value) = map.iter().next().unwrap();
1934 /// assert_eq!((*first_key, *first_value), (1, "a"));
1936 #[stable(feature = "rust1", since = "1.0.0")]
1937 pub fn iter(&self) -> Iter
<K
, V
> {
1940 front
: first_leaf_edge(self.root
.as_ref()),
1941 back
: last_leaf_edge(self.root
.as_ref()),
1943 length
: self.length
,
1947 /// Gets a mutable iterator over the entries of the map, sorted by key.
1954 /// use std::collections::BTreeMap;
1956 /// let mut map = BTreeMap::new();
1957 /// map.insert("a", 1);
1958 /// map.insert("b", 2);
1959 /// map.insert("c", 3);
1961 /// // add 10 to the value if the key isn't "a"
1962 /// for (key, value) in map.iter_mut() {
1963 /// if key != &"a" {
1968 #[stable(feature = "rust1", since = "1.0.0")]
1969 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
1970 let root1
= self.root
.as_mut();
1971 let root2
= unsafe { ptr::read(&root1) }
;
1974 front
: first_leaf_edge(root1
),
1975 back
: last_leaf_edge(root2
),
1976 _marker
: PhantomData
,
1978 length
: self.length
,
1982 /// Gets an iterator over the keys of the map, in sorted order.
1989 /// use std::collections::BTreeMap;
1991 /// let mut a = BTreeMap::new();
1992 /// a.insert(2, "b");
1993 /// a.insert(1, "a");
1995 /// let keys: Vec<_> = a.keys().cloned().collect();
1996 /// assert_eq!(keys, [1, 2]);
1998 #[stable(feature = "rust1", since = "1.0.0")]
1999 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
2000 Keys { inner: self.iter() }
2003 /// Gets an iterator over the values of the map, in order by key.
2010 /// use std::collections::BTreeMap;
2012 /// let mut a = BTreeMap::new();
2013 /// a.insert(1, "hello");
2014 /// a.insert(2, "goodbye");
2016 /// let values: Vec<&str> = a.values().cloned().collect();
2017 /// assert_eq!(values, ["hello", "goodbye"]);
2019 #[stable(feature = "rust1", since = "1.0.0")]
2020 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
2021 Values { inner: self.iter() }
2024 /// Gets a mutable iterator over the values of the map, in order by key.
2031 /// use std::collections::BTreeMap;
2033 /// let mut a = BTreeMap::new();
2034 /// a.insert(1, String::from("hello"));
2035 /// a.insert(2, String::from("goodbye"));
2037 /// for value in a.values_mut() {
2038 /// value.push_str("!");
2041 /// let values: Vec<String> = a.values().cloned().collect();
2042 /// assert_eq!(values, [String::from("hello!"),
2043 /// String::from("goodbye!")]);
2045 #[stable(feature = "map_values_mut", since = "1.10.0")]
2046 pub fn values_mut(&mut self) -> ValuesMut
<K
, V
> {
2047 ValuesMut { inner: self.iter_mut() }
2050 /// Returns the number of elements in the map.
2057 /// use std::collections::BTreeMap;
2059 /// let mut a = BTreeMap::new();
2060 /// assert_eq!(a.len(), 0);
2061 /// a.insert(1, "a");
2062 /// assert_eq!(a.len(), 1);
2064 #[stable(feature = "rust1", since = "1.0.0")]
2065 pub fn len(&self) -> usize {
2069 /// Returns `true` if the map contains no elements.
2076 /// use std::collections::BTreeMap;
2078 /// let mut a = BTreeMap::new();
2079 /// assert!(a.is_empty());
2080 /// a.insert(1, "a");
2081 /// assert!(!a.is_empty());
2083 #[stable(feature = "rust1", since = "1.0.0")]
2084 pub fn is_empty(&self) -> bool
{
2089 impl<'a
, K
: Ord
, V
> Entry
<'a
, K
, V
> {
2090 /// Ensures a value is in the entry by inserting the default if empty, and returns
2091 /// a mutable reference to the value in the entry.
2096 /// use std::collections::BTreeMap;
2098 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2099 /// map.entry("poneyland").or_insert(12);
2101 /// assert_eq!(map["poneyland"], 12);
2103 #[stable(feature = "rust1", since = "1.0.0")]
2104 pub fn or_insert(self, default: V
) -> &'a
mut V
{
2106 Occupied(entry
) => entry
.into_mut(),
2107 Vacant(entry
) => entry
.insert(default),
2111 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2112 /// and returns a mutable reference to the value in the entry.
2117 /// use std::collections::BTreeMap;
2119 /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
2120 /// let s = "hoho".to_string();
2122 /// map.entry("poneyland").or_insert_with(|| s);
2124 /// assert_eq!(map["poneyland"], "hoho".to_string());
2126 #[stable(feature = "rust1", since = "1.0.0")]
2127 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
2129 Occupied(entry
) => entry
.into_mut(),
2130 Vacant(entry
) => entry
.insert(default()),
2134 /// Returns a reference to this entry's key.
2139 /// use std::collections::BTreeMap;
2141 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2142 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2144 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2145 pub fn key(&self) -> &K
{
2147 Occupied(ref entry
) => entry
.key(),
2148 Vacant(ref entry
) => entry
.key(),
2152 /// Provides in-place mutable access to an occupied entry before any
2153 /// potential inserts into the map.
2158 /// use std::collections::BTreeMap;
2160 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2162 /// map.entry("poneyland")
2163 /// .and_modify(|e| { *e += 1 })
2165 /// assert_eq!(map["poneyland"], 42);
2167 /// map.entry("poneyland")
2168 /// .and_modify(|e| { *e += 1 })
2170 /// assert_eq!(map["poneyland"], 43);
2172 #[stable(feature = "entry_and_modify", since = "1.26.0")]
2173 pub fn and_modify
<F
>(self, f
: F
) -> Self
2174 where F
: FnOnce(&mut V
)
2177 Occupied(mut entry
) => {
2181 Vacant(entry
) => Vacant(entry
),
2186 impl<'a
, K
: Ord
, V
: Default
> Entry
<'a
, K
, V
> {
2187 #[stable(feature = "entry_or_default", since = "1.28.0")]
2188 /// Ensures a value is in the entry by inserting the default value if empty,
2189 /// and returns a mutable reference to the value in the entry.
2195 /// use std::collections::BTreeMap;
2197 /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
2198 /// map.entry("poneyland").or_default();
2200 /// assert_eq!(map["poneyland"], None);
2203 pub fn or_default(self) -> &'a
mut V
{
2205 Occupied(entry
) => entry
.into_mut(),
2206 Vacant(entry
) => entry
.insert(Default
::default()),
2212 impl<'a
, K
: Ord
, V
> VacantEntry
<'a
, K
, V
> {
2213 /// Gets a reference to the key that would be used when inserting a value
2214 /// through the VacantEntry.
2219 /// use std::collections::BTreeMap;
2221 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2222 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2224 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2225 pub fn key(&self) -> &K
{
2229 /// Take ownership of the key.
2234 /// use std::collections::BTreeMap;
2235 /// use std::collections::btree_map::Entry;
2237 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2239 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2243 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2244 pub fn into_key(self) -> K
{
2248 /// Sets the value of the entry with the `VacantEntry`'s key,
2249 /// and returns a mutable reference to it.
2254 /// use std::collections::BTreeMap;
2256 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
2258 /// // count the number of occurrences of letters in the vec
2259 /// for x in vec!["a","b","a","c","a","b"] {
2260 /// *count.entry(x).or_insert(0) += 1;
2263 /// assert_eq!(count["a"], 3);
2265 #[stable(feature = "rust1", since = "1.0.0")]
2266 pub fn insert(self, value
: V
) -> &'a
mut V
{
2275 let mut cur_parent
= match self.handle
.insert(self.key
, value
) {
2276 (Fit(handle
), _
) => return handle
.into_kv_mut().1,
2277 (Split(left
, k
, v
, right
), ptr
) => {
2282 left
.ascend().map_err(|n
| n
.into_root_mut())
2289 match parent
.insert(ins_k
, ins_v
, ins_edge
) {
2290 Fit(_
) => return unsafe { &mut *out_ptr }
,
2291 Split(left
, k
, v
, right
) => {
2295 cur_parent
= left
.ascend().map_err(|n
| n
.into_root_mut());
2300 root
.push_level().push(ins_k
, ins_v
, ins_edge
);
2301 return unsafe { &mut *out_ptr }
;
2308 impl<'a
, K
: Ord
, V
> OccupiedEntry
<'a
, K
, V
> {
2309 /// Gets a reference to the key in the entry.
2314 /// use std::collections::BTreeMap;
2316 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2317 /// map.entry("poneyland").or_insert(12);
2318 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2320 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2321 pub fn key(&self) -> &K
{
2322 self.handle
.reborrow().into_kv().0
2325 /// Take ownership of the key and value from the map.
2330 /// use std::collections::BTreeMap;
2331 /// use std::collections::btree_map::Entry;
2333 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2334 /// map.entry("poneyland").or_insert(12);
2336 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2337 /// // We delete the entry from the map.
2338 /// o.remove_entry();
2341 /// // If now try to get the value, it will panic:
2342 /// // println!("{}", map["poneyland"]);
2344 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2345 pub fn remove_entry(self) -> (K
, V
) {
2349 /// Gets a reference to the value in the entry.
2354 /// use std::collections::BTreeMap;
2355 /// use std::collections::btree_map::Entry;
2357 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2358 /// map.entry("poneyland").or_insert(12);
2360 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2361 /// assert_eq!(o.get(), &12);
2364 #[stable(feature = "rust1", since = "1.0.0")]
2365 pub fn get(&self) -> &V
{
2366 self.handle
.reborrow().into_kv().1
2369 /// Gets a mutable reference to the value in the entry.
2371 /// If you need a reference to the `OccupiedEntry` which may outlive the
2372 /// destruction of the `Entry` value, see [`into_mut`].
2374 /// [`into_mut`]: #method.into_mut
2379 /// use std::collections::BTreeMap;
2380 /// use std::collections::btree_map::Entry;
2382 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2383 /// map.entry("poneyland").or_insert(12);
2385 /// assert_eq!(map["poneyland"], 12);
2386 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2387 /// *o.get_mut() += 10;
2388 /// assert_eq!(*o.get(), 22);
2390 /// // We can use the same Entry multiple times.
2391 /// *o.get_mut() += 2;
2393 /// assert_eq!(map["poneyland"], 24);
2395 #[stable(feature = "rust1", since = "1.0.0")]
2396 pub fn get_mut(&mut self) -> &mut V
{
2397 self.handle
.kv_mut().1
2400 /// Converts the entry into a mutable reference to its value.
2402 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2404 /// [`get_mut`]: #method.get_mut
2409 /// use std::collections::BTreeMap;
2410 /// use std::collections::btree_map::Entry;
2412 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2413 /// map.entry("poneyland").or_insert(12);
2415 /// assert_eq!(map["poneyland"], 12);
2416 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2417 /// *o.into_mut() += 10;
2419 /// assert_eq!(map["poneyland"], 22);
2421 #[stable(feature = "rust1", since = "1.0.0")]
2422 pub fn into_mut(self) -> &'a
mut V
{
2423 self.handle
.into_kv_mut().1
2426 /// Sets the value of the entry with the `OccupiedEntry`'s key,
2427 /// and returns the entry's old value.
2432 /// use std::collections::BTreeMap;
2433 /// use std::collections::btree_map::Entry;
2435 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2436 /// map.entry("poneyland").or_insert(12);
2438 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2439 /// assert_eq!(o.insert(15), 12);
2441 /// assert_eq!(map["poneyland"], 15);
2443 #[stable(feature = "rust1", since = "1.0.0")]
2444 pub fn insert(&mut self, value
: V
) -> V
{
2445 mem
::replace(self.get_mut(), value
)
2448 /// Takes the value of the entry out of the map, and returns it.
2453 /// use std::collections::BTreeMap;
2454 /// use std::collections::btree_map::Entry;
2456 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2457 /// map.entry("poneyland").or_insert(12);
2459 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2460 /// assert_eq!(o.remove(), 12);
2462 /// // If we try to get "poneyland"'s value, it'll panic:
2463 /// // println!("{}", map["poneyland"]);
2465 #[stable(feature = "rust1", since = "1.0.0")]
2466 pub fn remove(self) -> V
{
2470 fn remove_kv(self) -> (K
, V
) {
2473 let (small_leaf
, old_key
, old_val
) = match self.handle
.force() {
2475 let (hole
, old_key
, old_val
) = leaf
.remove();
2476 (hole
.into_node(), old_key
, old_val
)
2478 Internal(mut internal
) => {
2479 let key_loc
= internal
.kv_mut().0 as *mut K
;
2480 let val_loc
= internal
.kv_mut().1 as *mut V
;
2482 let to_remove
= first_leaf_edge(internal
.right_edge().descend()).right_kv().ok();
2483 let to_remove
= unsafe { unwrap_unchecked(to_remove) }
;
2485 let (hole
, key
, val
) = to_remove
.remove();
2487 let old_key
= unsafe { mem::replace(&mut *key_loc, key) }
;
2488 let old_val
= unsafe { mem::replace(&mut *val_loc, val) }
;
2490 (hole
.into_node(), old_key
, old_val
)
2495 let mut cur_node
= small_leaf
.forget_type();
2496 while cur_node
.len() < node
::CAPACITY
/ 2 {
2497 match handle_underfull_node(cur_node
) {
2499 EmptyParent(_
) => unreachable
!(),
2501 if parent
.len() == 0 {
2502 // We must be at the root
2503 parent
.into_root_mut().pop_level();
2506 cur_node
= parent
.forget_type();
2517 enum UnderflowResult
<'a
, K
, V
> {
2519 EmptyParent(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
2520 Merged(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
2521 Stole(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
2524 fn handle_underfull_node
<'a
, K
, V
>(node
: NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::LeafOrInternal
>)
2525 -> UnderflowResult
<'a
, K
, V
> {
2526 let parent
= if let Ok(parent
) = node
.ascend() {
2532 let (is_left
, mut handle
) = match parent
.left_kv() {
2533 Ok(left
) => (true, left
),
2535 match parent
.right_kv() {
2536 Ok(right
) => (false, right
),
2538 return EmptyParent(parent
.into_node());
2544 if handle
.can_merge() {
2545 Merged(handle
.merge().into_node())
2548 handle
.steal_left();
2550 handle
.steal_right();
2552 Stole(handle
.into_node())
2556 impl<K
: Ord
, V
, I
: Iterator
<Item
= (K
, V
)>> Iterator
for MergeIter
<K
, V
, I
> {
2559 fn next(&mut self) -> Option
<(K
, V
)> {
2560 let res
= match (self.left
.peek(), self.right
.peek()) {
2561 (Some(&(ref left_key
, _
)), Some(&(ref right_key
, _
))) => left_key
.cmp(right_key
),
2562 (Some(_
), None
) => Ordering
::Less
,
2563 (None
, Some(_
)) => Ordering
::Greater
,
2564 (None
, None
) => return None
,
2567 // Check which elements comes first and only advance the corresponding iterator.
2568 // If two keys are equal, take the value from `right`.
2570 Ordering
::Less
=> self.left
.next(),
2571 Ordering
::Greater
=> self.right
.next(),
2572 Ordering
::Equal
=> {