1 // Copyright 2014 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 // This implementation is largely based on the high-level description and analysis of B-Trees
12 // found in *Open Data Structures* (ODS). Although our implementation does not use any of
13 // the source found in ODS, if one wishes to review the high-level design of this structure, it
14 // can be freely downloaded at http://opendatastructures.org/. Its contents are as of this
15 // writing (August 2014) freely licensed under the following Creative Commons Attribution
16 // License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/).
22 use core
::cmp
::Ordering
;
24 use core
::hash
::{Hash, Hasher}
;
25 use core
::iter
::{Map, FromIterator}
;
27 use core
::{iter, fmt, mem, usize}
;
28 use Bound
::{self, Included, Excluded, Unbounded}
;
31 use vec_deque
::VecDeque
;
33 use self::Continuation
::{Continue, Finished}
;
35 use super::node
::ForceResult
::{Leaf, Internal}
;
36 use super::node
::TraversalItem
::{self, Elem, Edge}
;
37 use super::node
::{Traversal, MutTraversal, MoveTraversal}
;
38 use super::node
::{self, Node, Found, GoDown}
;
40 /// A map based on a B-Tree.
42 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
43 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
44 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
45 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
46 /// is done is *very* inefficient for modern computer architectures. In particular, every element
47 /// is stored in its own individually heap-allocated node. This means that every single insertion
48 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
49 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
52 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
53 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
54 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
55 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
56 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
57 /// the node using binary search. As a compromise, one could also perform a linear search
58 /// that initially only checks every i<sup>th</sup> element for some choice of i.
60 /// Currently, our implementation simply performs naive linear search. This provides excellent
61 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
62 /// would like to further explore choosing the optimal search strategy based on the choice of B,
63 /// and possibly other factors. Using linear search, searching for a random element is expected
64 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
65 /// however, performance is excellent.
67 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
68 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
69 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
71 #[stable(feature = "rust1", since = "1.0.0")]
72 pub struct BTreeMap
<K
, V
> {
79 /// An abstract base over-which all other BTree iterators are built.
82 traversals
: VecDeque
<T
>,
86 /// An iterator over a BTreeMap's entries.
87 #[stable(feature = "rust1", since = "1.0.0")]
88 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
89 inner
: AbsIter
<Traversal
<'a
, K
, V
>>
92 /// A mutable iterator over a BTreeMap's entries.
93 #[stable(feature = "rust1", since = "1.0.0")]
94 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
95 inner
: AbsIter
<MutTraversal
<'a
, K
, V
>>
98 /// An owning iterator over a BTreeMap's entries.
99 #[stable(feature = "rust1", since = "1.0.0")]
100 pub struct IntoIter
<K
, V
> {
101 inner
: AbsIter
<MoveTraversal
<K
, V
>>
104 /// An iterator over a BTreeMap's keys.
105 #[stable(feature = "rust1", since = "1.0.0")]
106 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
107 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a K
>
110 /// An iterator over a BTreeMap's values.
111 #[stable(feature = "rust1", since = "1.0.0")]
112 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
113 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a V
>
116 /// An iterator over a sub-range of BTreeMap's entries.
117 pub struct Range
<'a
, K
: 'a
, V
: 'a
> {
118 inner
: AbsIter
<Traversal
<'a
, K
, V
>>
121 /// A mutable iterator over a sub-range of BTreeMap's entries.
122 pub struct RangeMut
<'a
, K
: 'a
, V
: 'a
> {
123 inner
: AbsIter
<MutTraversal
<'a
, K
, V
>>
126 /// A view into a single entry in a map, which may either be vacant or occupied.
127 #[stable(feature = "rust1", since = "1.0.0")]
128 pub enum Entry
<'a
, K
:'a
, V
:'a
> {
130 #[stable(feature = "rust1", since = "1.0.0")]
131 Vacant(VacantEntry
<'a
, K
, V
>),
133 /// An occupied Entry
134 #[stable(feature = "rust1", since = "1.0.0")]
135 Occupied(OccupiedEntry
<'a
, K
, V
>),
139 #[stable(feature = "rust1", since = "1.0.0")]
140 pub struct VacantEntry
<'a
, K
:'a
, V
:'a
> {
142 stack
: stack
::SearchStack
<'a
, K
, V
, node
::handle
::Edge
, node
::handle
::Leaf
>,
145 /// An occupied Entry.
146 #[stable(feature = "rust1", since = "1.0.0")]
147 pub struct OccupiedEntry
<'a
, K
:'a
, V
:'a
> {
148 stack
: stack
::SearchStack
<'a
, K
, V
, node
::handle
::KV
, node
::handle
::LeafOrInternal
>,
151 impl<K
: Ord
, V
> BTreeMap
<K
, V
> {
152 /// Makes a new empty BTreeMap with a reasonable choice for B.
153 #[stable(feature = "rust1", since = "1.0.0")]
154 pub fn new() -> BTreeMap
<K
, V
> {
155 //FIXME(Gankro): Tune this as a function of size_of<K/V>?
159 /// Makes a new empty BTreeMap with the given B.
161 /// B cannot be less than 2.
162 pub fn with_b(b
: usize) -> BTreeMap
<K
, V
> {
163 assert
!(b
> 1, "B must be greater than 1");
167 root
: Node
::make_leaf_root(b
),
172 /// Clears the map, removing all values.
177 /// use std::collections::BTreeMap;
179 /// let mut a = BTreeMap::new();
180 /// a.insert(1, "a");
182 /// assert!(a.is_empty());
184 #[stable(feature = "rust1", since = "1.0.0")]
185 pub fn clear(&mut self) {
187 // avoid recursive destructors by manually traversing the tree
188 for _
in mem
::replace(self, BTreeMap
::with_b(b
)) {}
;
191 // Searching in a B-Tree is pretty straightforward.
193 // Start at the root. Try to find the key in the current node. If we find it, return it.
194 // If it's not in there, follow the edge *before* the smallest key larger than
195 // the search key. If no such key exists (they're *all* smaller), then just take the last
196 // edge in the node. If we're in a leaf and we don't find our key, then it's not
199 /// Returns a reference to the value corresponding to the key.
201 /// The key may be any borrowed form of the map's key type, but the ordering
202 /// on the borrowed form *must* match the ordering on the key type.
207 /// use std::collections::BTreeMap;
209 /// let mut map = BTreeMap::new();
210 /// map.insert(1, "a");
211 /// assert_eq!(map.get(&1), Some(&"a"));
212 /// assert_eq!(map.get(&2), None);
214 #[stable(feature = "rust1", since = "1.0.0")]
215 pub fn get
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<&V
> where K
: Borrow
<Q
>, Q
: Ord
{
216 let mut cur_node
= &self.root
;
218 match Node
::search(cur_node
, key
) {
219 Found(handle
) => return Some(handle
.into_kv().1),
220 GoDown(handle
) => match handle
.force() {
221 Leaf(_
) => return None
,
222 Internal(internal_handle
) => {
223 cur_node
= internal_handle
.into_edge();
231 /// Returns true if the map contains a value for the specified key.
233 /// The key may be any borrowed form of the map's key type, but the ordering
234 /// on the borrowed form *must* match the ordering on the key type.
239 /// use std::collections::BTreeMap;
241 /// let mut map = BTreeMap::new();
242 /// map.insert(1, "a");
243 /// assert_eq!(map.contains_key(&1), true);
244 /// assert_eq!(map.contains_key(&2), false);
246 #[stable(feature = "rust1", since = "1.0.0")]
247 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
where K
: Borrow
<Q
>, Q
: Ord
{
248 self.get(key
).is_some()
251 /// Returns a mutable reference to the value corresponding to the key.
253 /// The key may be any borrowed form of the map's key type, but the ordering
254 /// on the borrowed form *must* match the ordering on the key type.
259 /// use std::collections::BTreeMap;
261 /// let mut map = BTreeMap::new();
262 /// map.insert(1, "a");
263 /// if let Some(x) = map.get_mut(&1) {
266 /// assert_eq!(map[&1], "b");
268 // See `get` for implementation notes, this is basically a copy-paste with mut's added
269 #[stable(feature = "rust1", since = "1.0.0")]
270 pub fn get_mut
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<&mut V
> where K
: Borrow
<Q
>, Q
: Ord
{
271 // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
272 let mut temp_node
= &mut self.root
;
274 let cur_node
= temp_node
;
275 match Node
::search(cur_node
, key
) {
276 Found(handle
) => return Some(handle
.into_kv_mut().1),
277 GoDown(handle
) => match handle
.force() {
278 Leaf(_
) => return None
,
279 Internal(internal_handle
) => {
280 temp_node
= internal_handle
.into_edge_mut();
288 // Insertion in a B-Tree is a bit complicated.
290 // First we do the same kind of search described in `find`. But we need to maintain a stack of
291 // all the nodes/edges in our search path. If we find a match for the key we're trying to
292 // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
293 // we attempt to insert our key-value pair at the same location we would want to follow another
296 // If the node has room, then this is done in the obvious way by shifting elements. However,
297 // if the node itself is full, we split node into two, and give its median key-value
298 // pair to its parent to insert the new node with. Of course, the parent may also be
299 // full, and insertion can propagate until we reach the root. If we reach the root, and
300 // it is *also* full, then we split the root and place the two nodes under a newly made root.
302 // Note that we subtly deviate from Open Data Structures in our implementation of split.
303 // ODS describes inserting into the node *regardless* of its capacity, and then
304 // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
305 // Instead, we split beforehand, and then insert the key-value pair into the appropriate
306 // result node. This has two consequences:
308 // 1) While ODS produces a left node of size B-1, and a right node of size B,
309 // we may potentially reverse this. However, this shouldn't effect the analysis.
311 // 2) While ODS may potentially return the pair we *just* inserted after
312 // the split, we will never do this. Again, this shouldn't effect the analysis.
314 /// Inserts a key-value pair into the map. If the key already had a value
315 /// present in the map, that value is returned. Otherwise, `None` is returned.
320 /// use std::collections::BTreeMap;
322 /// let mut map = BTreeMap::new();
323 /// assert_eq!(map.insert(37, "a"), None);
324 /// assert_eq!(map.is_empty(), false);
326 /// map.insert(37, "b");
327 /// assert_eq!(map.insert(37, "c"), Some("b"));
328 /// assert_eq!(map[&37], "c");
330 #[stable(feature = "rust1", since = "1.0.0")]
331 pub fn insert(&mut self, mut key
: K
, mut value
: V
) -> Option
<V
> {
332 // This is a stack of rawptrs to nodes paired with indices, respectively
333 // representing the nodes and edges of our search path. We have to store rawptrs
334 // because as far as Rust is concerned, we can mutate aliased data with such a
335 // stack. It is of course correct, but what it doesn't know is that we will only
336 // be popping and using these ptrs one at a time in child-to-parent order. The alternative
337 // to doing this is to take the Nodes from their parents. This actually makes
338 // borrowck *really* happy and everything is pretty smooth. However, this creates
339 // *tons* of pointless writes, and requires us to always walk all the way back to
340 // the root after an insertion, even if we only needed to change a leaf. Therefore,
341 // we accept this potential unsafety and complexity in the name of performance.
343 // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
344 // by the stack module. All it can do is immutably read nodes, and ask the search stack
345 // to proceed down some edge by index. This makes the search logic we'll be reusing in a
346 // few different methods much neater, and of course drastically improves safety.
347 let mut stack
= stack
::PartialSearchStack
::new(self);
350 let result
= stack
.with(move |pusher
, node
| {
351 // Same basic logic as found in `find`, but with PartialSearchStack mediating the
352 // actual nodes for us
353 match Node
::search(node
, &key
) {
354 Found(mut handle
) => {
355 // Perfect match, swap the values and return the old one
356 mem
::swap(handle
.val_mut(), &mut value
);
357 Finished(Some(value
))
360 // We need to keep searching, try to get the search stack
361 // to go down further
362 match handle
.force() {
363 Leaf(leaf_handle
) => {
364 // We've reached a leaf, perform the insertion here
365 pusher
.seal(leaf_handle
).insert(key
, value
);
368 Internal(internal_handle
) => {
369 // We've found the subtree to insert this key/value pair in,
371 Continue((pusher
.push(internal_handle
), key
, value
))
378 Finished(ret
) => return ret
,
379 Continue((new_stack
, renewed_key
, renewed_val
)) => {
388 // Deletion is the most complicated operation for a B-Tree.
390 // First we do the same kind of search described in
391 // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
392 // If we don't find the key, then we just return `None` and do nothing. If we do find the
393 // key, we perform two operations: remove the item, and then possibly handle underflow.
395 // # removing the item
396 // If the node is a leaf, we just remove the item, and shift
397 // any items after it back to fill the hole.
399 // If the node is an internal node, we *swap* the item with the smallest item in
400 // in its right subtree (which must reside in a leaf), and then revert to the leaf
403 // # handling underflow
404 // After removing an item, there may be too few items in the node. We want nodes
405 // to be mostly full for efficiency, although we make an exception for the root, which
406 // may have as few as one item. If this is the case, we may first try to steal
407 // an item from our left or right neighbour.
409 // To steal from the left (right) neighbour,
410 // we take the largest (smallest) item and child from it. We then swap the taken item
411 // with the item in their mutual parent that separates them, and then insert the
412 // parent's item and the taken child into the first (last) index of the underflowed node.
414 // However, stealing has the possibility of underflowing our neighbour. If this is the
415 // case, we instead *merge* with our neighbour. This of course reduces the number of
416 // children in the parent. Therefore, we also steal the item that separates the now
417 // merged nodes, and insert it into the merged node.
419 // Merging may cause the parent to underflow. If this is the case, then we must repeat
420 // the underflow handling process on the parent. If merging merges the last two children
421 // of the root, then we replace the root with the merged node.
423 /// Removes a key from the map, returning the value at the key if the key
424 /// was previously in the map.
426 /// The key may be any borrowed form of the map's key type, but the ordering
427 /// on the borrowed form *must* match the ordering on the key type.
432 /// use std::collections::BTreeMap;
434 /// let mut map = BTreeMap::new();
435 /// map.insert(1, "a");
436 /// assert_eq!(map.remove(&1), Some("a"));
437 /// assert_eq!(map.remove(&1), None);
439 #[stable(feature = "rust1", since = "1.0.0")]
440 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
> where K
: Borrow
<Q
>, Q
: Ord
{
441 // See `swap` for a more thorough description of the stuff going on in here
442 let mut stack
= stack
::PartialSearchStack
::new(self);
444 let result
= stack
.with(move |pusher
, node
| {
445 match Node
::search(node
, key
) {
447 // Perfect match. Terminate the stack here, and remove the entry
448 Finished(Some(pusher
.seal(handle
).remove()))
451 // We need to keep searching, try to go down the next edge
452 match handle
.force() {
453 // We're at a leaf; the key isn't in here
454 Leaf(_
) => Finished(None
),
455 Internal(internal_handle
) => Continue(pusher
.push(internal_handle
))
461 Finished(ret
) => return ret
,
462 Continue(new_stack
) => stack
= new_stack
468 #[stable(feature = "rust1", since = "1.0.0")]
469 impl<K
, V
> IntoIterator
for BTreeMap
<K
, V
> {
471 type IntoIter
= IntoIter
<K
, V
>;
473 /// Gets an owning iterator over the entries of the map.
478 /// use std::collections::BTreeMap;
480 /// let mut map = BTreeMap::new();
481 /// map.insert(1, "a");
482 /// map.insert(2, "b");
483 /// map.insert(3, "c");
485 /// for (key, value) in map.into_iter() {
486 /// println!("{}: {}", key, value);
489 fn into_iter(self) -> IntoIter
<K
, V
> {
490 let len
= self.len();
491 let mut lca
= VecDeque
::new();
492 lca
.push_back(Traverse
::traverse(self.root
));
502 #[stable(feature = "rust1", since = "1.0.0")]
503 impl<'a
, K
, V
> IntoIterator
for &'a BTreeMap
<K
, V
> {
504 type Item
= (&'a K
, &'a V
);
505 type IntoIter
= Iter
<'a
, K
, V
>;
507 fn into_iter(self) -> Iter
<'a
, K
, V
> {
512 #[stable(feature = "rust1", since = "1.0.0")]
513 impl<'a
, K
, V
> IntoIterator
for &'a
mut BTreeMap
<K
, V
> {
514 type Item
= (&'a K
, &'a
mut V
);
515 type IntoIter
= IterMut
<'a
, K
, V
>;
517 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
522 /// A helper enum useful for deciding whether to continue a loop since we can't
523 /// return from a closure
524 enum Continuation
<A
, B
> {
529 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
530 /// to nodes. By using this module much better safety guarantees can be made, and more search
531 /// boilerplate gets cut out.
533 use core
::prelude
::*;
536 use core
::ops
::{Deref, DerefMut}
;
538 use super::super::node
::{self, Node, Fit, Split, Internal, Leaf}
;
539 use super::super::node
::handle
;
542 struct InvariantLifetime
<'id
>(
543 marker
::PhantomData
<::core
::cell
::Cell
<&'
id ()>>);
545 impl<'id
> InvariantLifetime
<'id
> {
546 fn new() -> InvariantLifetime
<'id
> {
547 InvariantLifetime(marker
::PhantomData
)
551 /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
552 /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
553 /// with the exact requested lifetime can be used. This is in contrast to normal references,
554 /// where `&'static` can be used in any function expecting any lifetime reference.
555 pub struct IdRef
<'id
, T
: 'id
> {
557 _marker
: InvariantLifetime
<'id
>,
560 impl<'id
, T
> Deref
for IdRef
<'id
, T
> {
563 fn deref(&self) -> &T
{
568 impl<'id
, T
> DerefMut
for IdRef
<'id
, T
> {
569 fn deref_mut(&mut self) -> &mut T
{
574 type StackItem
<K
, V
> = node
::Handle
<*mut Node
<K
, V
>, handle
::Edge
, handle
::Internal
>;
575 type Stack
<K
, V
> = Vec
<StackItem
<K
, V
>>;
577 /// A `PartialSearchStack` handles the construction of a search stack.
578 pub struct PartialSearchStack
<'a
, K
:'a
, V
:'a
> {
579 map
: &'a
mut BTreeMap
<K
, V
>,
581 next
: *mut Node
<K
, V
>,
584 /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
585 /// methods depending on the type of what the path points to for removing an element, inserting
586 /// a new element, and manipulating to element at the top of the stack.
587 pub struct SearchStack
<'a
, K
:'a
, V
:'a
, Type
, NodeType
> {
588 map
: &'a
mut BTreeMap
<K
, V
>,
590 top
: node
::Handle
<*mut Node
<K
, V
>, Type
, NodeType
>,
593 /// A `PartialSearchStack` that doesn't hold a a reference to the next node, and is just
594 /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
595 /// for more details.
596 pub struct Pusher
<'id
, 'a
, K
:'a
, V
:'a
> {
597 map
: &'a
mut BTreeMap
<K
, V
>,
599 _marker
: InvariantLifetime
<'id
>,
602 impl<'a
, K
, V
> PartialSearchStack
<'a
, K
, V
> {
603 /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
604 /// root of the tree.
605 pub fn new(map
: &'a
mut BTreeMap
<K
, V
>) -> PartialSearchStack
<'a
, K
, V
> {
606 let depth
= map
.depth
;
609 next
: &mut map
.root
as *mut _
,
611 stack
: Vec
::with_capacity(depth
),
615 /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
616 /// to interact with, search, and finally push the `Node` onto the stack. The passed in
617 /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
618 /// ensures that only `Handle`s from the correct `Node` can be pushed.
620 /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
621 /// handles with the same `'id`. The closure could only get references with that lifetime
622 /// through its arguments or through some other `IdRef` that it has lying around. However,
623 /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
624 /// parameter, it would need to have precisely the correct lifetime, which would mean that
625 /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
626 /// specific lifetime instead of the one that `with` chooses to give it.
628 /// See also Haskell's `ST` monad, which uses a similar trick.
629 pub fn with
<T
, F
: for<'id
> FnOnce(Pusher
<'id
, 'a
, K
, V
>,
630 IdRef
<'id
, Node
<K
, V
>>) -> T
>(self, closure
: F
) -> T
{
631 let pusher
= Pusher
{
634 _marker
: InvariantLifetime
::new(),
637 inner
: unsafe { &mut *self.next }
,
638 _marker
: InvariantLifetime
::new(),
641 closure(pusher
, node
)
645 impl<'id
, 'a
, K
, V
> Pusher
<'id
, 'a
, K
, V
> {
646 /// Pushes the requested child of the stack's current top on top of the stack. If the child
647 /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
649 pub fn push(mut self, mut edge
: node
::Handle
<IdRef
<'id
, Node
<K
, V
>>,
652 -> PartialSearchStack
<'a
, K
, V
> {
653 self.stack
.push(edge
.as_raw());
657 next
: edge
.edge_mut() as *mut _
,
661 /// Converts the PartialSearchStack into a SearchStack.
662 pub fn seal
<Type
, NodeType
>
663 (self, mut handle
: node
::Handle
<IdRef
<'id
, Node
<K
, V
>>, Type
, NodeType
>)
664 -> SearchStack
<'a
, K
, V
, Type
, NodeType
> {
668 top
: handle
.as_raw(),
673 impl<'a
, K
, V
, NodeType
> SearchStack
<'a
, K
, V
, handle
::KV
, NodeType
> {
674 /// Gets a reference to the value the stack points to.
675 pub fn peek(&self) -> &V
{
676 unsafe { self.top.from_raw().into_kv().1 }
679 /// Gets a mutable reference to the value the stack points to.
680 pub fn peek_mut(&mut self) -> &mut V
{
681 unsafe { self.top.from_raw_mut().into_kv_mut().1 }
684 /// Converts the stack into a mutable reference to the value it points to, with a lifetime
685 /// tied to the original tree.
686 pub fn into_top(mut self) -> &'a
mut V
{
688 &mut *(self.top
.from_raw_mut().val_mut() as *mut V
)
693 impl<'a
, K
, V
> SearchStack
<'a
, K
, V
, handle
::KV
, handle
::Leaf
> {
694 /// Removes the key and value in the top element of the stack, then handles underflows as
695 /// described in BTree's pop function.
696 fn remove_leaf(mut self) -> V
{
697 self.map
.length
-= 1;
699 // Remove the key-value pair from the leaf that this search stack points to.
700 // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
701 // to avoid ownership issues.
702 let (value
, mut underflow
) = unsafe {
703 let (_
, value
) = self.top
.from_raw_mut().remove_as_leaf();
704 let underflow
= self.top
.from_raw().node().is_underfull();
709 match self.stack
.pop() {
711 // We've reached the root, so no matter what, we're done. We manually
712 // access the root via the tree itself to avoid creating any dangling
714 if self.map
.root
.is_empty() && !self.map
.root
.is_leaf() {
715 // We've emptied out the root, so make its only child the new root.
716 // If it's a leaf, we just let it become empty.
718 self.map
.root
.hoist_lone_child();
722 Some(mut handle
) => {
724 // Underflow! Handle it!
726 handle
.from_raw_mut().handle_underflow();
727 underflow
= handle
.from_raw().node().is_underfull();
739 impl<'a
, K
, V
> SearchStack
<'a
, K
, V
, handle
::KV
, handle
::LeafOrInternal
> {
740 /// Removes the key and value in the top element of the stack, then handles underflows as
741 /// described in BTree's pop function.
742 pub fn remove(self) -> V
{
743 // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
744 // in a BTree. Note that this may put the tree in an inconsistent state (further
745 // described in into_leaf's comments), but this is immediately fixed by the
746 // removing the value we want to remove
747 self.into_leaf().remove_leaf()
750 /// Subroutine for removal. Takes a search stack for a key that might terminate at an
751 /// internal node, and mutates the tree and search stack to *make* it a search stack
752 /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
753 /// leaves the tree in an inconsistent state that must be repaired by the caller by
754 /// removing the entry in question. Specifically the key-value pair and its successor will
756 fn into_leaf(mut self) -> SearchStack
<'a
, K
, V
, handle
::KV
, handle
::Leaf
> {
758 let mut top_raw
= self.top
;
759 let mut top
= top_raw
.from_raw_mut();
761 let key_ptr
= top
.key_mut() as *mut _
;
762 let val_ptr
= top
.val_mut() as *mut _
;
764 // Try to go into the right subtree of the found key to find its successor
766 Leaf(mut leaf_handle
) => {
767 // We're a proper leaf stack, nothing to do
771 top
: leaf_handle
.as_raw()
774 Internal(mut internal_handle
) => {
775 let mut right_handle
= internal_handle
.right_edge();
777 //We're not a proper leaf stack, let's get to work.
778 self.stack
.push(right_handle
.as_raw());
780 let mut temp_node
= right_handle
.edge_mut();
782 // Walk into the smallest subtree of this node
783 let node
= temp_node
;
785 match node
.kv_handle(0).force() {
786 Leaf(mut handle
) => {
787 // This node is a leaf, do the swap and return
788 mem
::swap(handle
.key_mut(), &mut *key_ptr
);
789 mem
::swap(handle
.val_mut(), &mut *val_ptr
);
796 Internal(kv_handle
) => {
797 // This node is internal, go deeper
798 let mut handle
= kv_handle
.into_left_edge();
799 self.stack
.push(handle
.as_raw());
800 temp_node
= handle
.into_edge_mut();
810 impl<'a
, K
, V
> SearchStack
<'a
, K
, V
, handle
::Edge
, handle
::Leaf
> {
811 /// Inserts the key and value into the top element in the stack, and if that node has to
812 /// split recursively inserts the split contents into the next element stack until
815 /// Assumes that the stack represents a search path from the root to a leaf.
817 /// An &mut V is returned to the inserted value, for callers that want a reference to this.
818 pub fn insert(mut self, key
: K
, val
: V
) -> &'a
mut V
{
820 self.map
.length
+= 1;
822 // Insert the key and value into the leaf at the top of the stack
823 let (mut insertion
, inserted_ptr
) = self.top
.from_raw_mut()
824 .insert_as_leaf(key
, val
);
829 // The last insertion went off without a hitch, no splits! We can stop
831 return &mut *inserted_ptr
;
833 Split(key
, val
, right
) => match self.stack
.pop() {
834 // The last insertion triggered a split, so get the next element on the
835 // stack to recursively insert the split node into.
837 // The stack was empty; we've split the root, and need to make a
838 // a new one. This is done in-place because we can't move the
839 // root out of a reference to the tree.
840 Node
::make_internal_root(&mut self.map
.root
, self.map
.b
,
844 return &mut *inserted_ptr
;
846 Some(mut handle
) => {
847 // The stack wasn't empty, do the insertion and recurse
848 insertion
= handle
.from_raw_mut()
849 .insert_as_internal(key
, val
, right
);
860 #[stable(feature = "rust1", since = "1.0.0")]
861 impl<K
: Ord
, V
> FromIterator
<(K
, V
)> for BTreeMap
<K
, V
> {
862 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iter
: T
) -> BTreeMap
<K
, V
> {
863 let mut map
= BTreeMap
::new();
869 #[stable(feature = "rust1", since = "1.0.0")]
870 impl<K
: Ord
, V
> Extend
<(K
, V
)> for BTreeMap
<K
, V
> {
872 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
879 #[stable(feature = "extend_ref", since = "1.2.0")]
880 impl<'a
, K
: Ord
+ Copy
, V
: Copy
> Extend
<(&'a K
, &'a V
)> for BTreeMap
<K
, V
> {
881 fn extend
<I
: IntoIterator
<Item
=(&'a K
, &'a V
)>>(&mut self, iter
: I
) {
882 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
886 #[stable(feature = "rust1", since = "1.0.0")]
887 impl<K
: Hash
, V
: Hash
> Hash
for BTreeMap
<K
, V
> {
888 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
895 #[stable(feature = "rust1", since = "1.0.0")]
896 impl<K
: Ord
, V
> Default
for BTreeMap
<K
, V
> {
897 #[stable(feature = "rust1", since = "1.0.0")]
898 fn default() -> BTreeMap
<K
, V
> {
903 #[stable(feature = "rust1", since = "1.0.0")]
904 impl<K
: PartialEq
, V
: PartialEq
> PartialEq
for BTreeMap
<K
, V
> {
905 fn eq(&self, other
: &BTreeMap
<K
, V
>) -> bool
{
906 self.len() == other
.len() &&
907 self.iter().zip(other
).all(|(a
, b
)| a
== b
)
911 #[stable(feature = "rust1", since = "1.0.0")]
912 impl<K
: Eq
, V
: Eq
> Eq
for BTreeMap
<K
, V
> {}
914 #[stable(feature = "rust1", since = "1.0.0")]
915 impl<K
: PartialOrd
, V
: PartialOrd
> PartialOrd
for BTreeMap
<K
, V
> {
917 fn partial_cmp(&self, other
: &BTreeMap
<K
, V
>) -> Option
<Ordering
> {
918 iter
::order
::partial_cmp(self.iter(), other
.iter())
922 #[stable(feature = "rust1", since = "1.0.0")]
923 impl<K
: Ord
, V
: Ord
> Ord
for BTreeMap
<K
, V
> {
925 fn cmp(&self, other
: &BTreeMap
<K
, V
>) -> Ordering
{
926 iter
::order
::cmp(self.iter(), other
.iter())
930 #[stable(feature = "rust1", since = "1.0.0")]
931 impl<K
: Debug
, V
: Debug
> Debug
for BTreeMap
<K
, V
> {
932 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
933 f
.debug_map().entries(self.iter()).finish()
937 #[stable(feature = "rust1", since = "1.0.0")]
938 impl<'a
, K
: Ord
, Q
: ?Sized
, V
> Index
<&'a Q
> for BTreeMap
<K
, V
>
939 where K
: Borrow
<Q
>, Q
: Ord
944 fn index(&self, key
: &Q
) -> &V
{
945 self.get(key
).expect("no entry found for key")
949 /// Genericises over how to get the correct type of iterator from the correct type
950 /// of Node ownership.
952 fn traverse(node
: N
) -> Self;
955 impl<'a
, K
, V
> Traverse
<&'a Node
<K
, V
>> for Traversal
<'a
, K
, V
> {
956 fn traverse(node
: &'a Node
<K
, V
>) -> Traversal
<'a
, K
, V
> {
961 impl<'a
, K
, V
> Traverse
<&'a
mut Node
<K
, V
>> for MutTraversal
<'a
, K
, V
> {
962 fn traverse(node
: &'a
mut Node
<K
, V
>) -> MutTraversal
<'a
, K
, V
> {
967 impl<K
, V
> Traverse
<Node
<K
, V
>> for MoveTraversal
<K
, V
> {
968 fn traverse(node
: Node
<K
, V
>) -> MoveTraversal
<K
, V
> {
973 /// Represents an operation to perform inside the following iterator methods.
974 /// This is necessary to use in `next` because we want to modify `self.traversals` inside
975 /// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
976 /// what we want to do, and do it after the match.
981 impl<K
, V
, E
, T
> Iterator
for AbsIter
<T
> where
982 T
: DoubleEndedIterator
<Item
=TraversalItem
<K
, V
, E
>> + Traverse
<E
>,
986 // Our iterator represents a queue of all ancestors of elements we have
987 // yet to yield, from smallest to largest. Note that the design of these
988 // iterators permits an *arbitrary* initial pair of min and max, making
989 // these arbitrary sub-range iterators.
990 fn next(&mut self) -> Option
<(K
, V
)> {
992 // We want the smallest element, so try to get the back of the queue
993 let op
= match self.traversals
.back_mut() {
995 // The queue wasn't empty, so continue along the node in its head
996 Some(iter
) => match iter
.next() {
997 // The head is empty, so Pop it off and continue the process
999 // The head yielded an edge, so make that the new head
1000 Some(Edge(next
)) => Push(Traverse
::traverse(next
)),
1001 // The head yielded an entry, so yield that
1009 // Handle any operation as necessary, without a conflicting borrow of the queue
1011 Push(item
) => { self.traversals.push_back(item); }
,
1012 Pop
=> { self.traversals.pop_back(); }
,
1017 fn size_hint(&self) -> (usize, Option
<usize>) {
1018 (self.size
, Some(self.size
))
1022 impl<K
, V
, E
, T
> DoubleEndedIterator
for AbsIter
<T
> where
1023 T
: DoubleEndedIterator
<Item
=TraversalItem
<K
, V
, E
>> + Traverse
<E
>,
1025 // next_back is totally symmetric to next
1027 fn next_back(&mut self) -> Option
<(K
, V
)> {
1029 let op
= match self.traversals
.front_mut() {
1030 None
=> return None
,
1031 Some(iter
) => match iter
.next_back() {
1033 Some(Edge(next
)) => Push(Traverse
::traverse(next
)),
1042 Push(item
) => { self.traversals.push_front(item); }
,
1043 Pop
=> { self.traversals.pop_front(); }
1049 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1050 fn clone(&self) -> Iter
<'a
, K
, V
> { Iter { inner: self.inner.clone() }
}
1052 #[stable(feature = "rust1", since = "1.0.0")]
1053 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1054 type Item
= (&'a K
, &'a V
);
1056 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> { self.inner.next() }
1057 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1059 #[stable(feature = "rust1", since = "1.0.0")]
1060 impl<'a
, K
, V
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
1061 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> { self.inner.next_back() }
1063 #[stable(feature = "rust1", since = "1.0.0")]
1064 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {}
1066 #[stable(feature = "rust1", since = "1.0.0")]
1067 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1068 type Item
= (&'a K
, &'a
mut V
);
1070 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> { self.inner.next() }
1071 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1073 #[stable(feature = "rust1", since = "1.0.0")]
1074 impl<'a
, K
, V
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
1075 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> { self.inner.next_back() }
1077 #[stable(feature = "rust1", since = "1.0.0")]
1078 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {}
1080 #[stable(feature = "rust1", since = "1.0.0")]
1081 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1084 fn next(&mut self) -> Option
<(K
, V
)> { self.inner.next() }
1085 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1087 #[stable(feature = "rust1", since = "1.0.0")]
1088 impl<K
, V
> DoubleEndedIterator
for IntoIter
<K
, V
> {
1089 fn next_back(&mut self) -> Option
<(K
, V
)> { self.inner.next_back() }
1091 #[stable(feature = "rust1", since = "1.0.0")]
1092 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {}
1094 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1095 fn clone(&self) -> Keys
<'a
, K
, V
> { Keys { inner: self.inner.clone() }
}
1097 #[stable(feature = "rust1", since = "1.0.0")]
1098 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1101 fn next(&mut self) -> Option
<(&'a K
)> { self.inner.next() }
1102 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1104 #[stable(feature = "rust1", since = "1.0.0")]
1105 impl<'a
, K
, V
> DoubleEndedIterator
for Keys
<'a
, K
, V
> {
1106 fn next_back(&mut self) -> Option
<(&'a K
)> { self.inner.next_back() }
1108 #[stable(feature = "rust1", since = "1.0.0")]
1109 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {}
1112 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1113 fn clone(&self) -> Values
<'a
, K
, V
> { Values { inner: self.inner.clone() }
}
1115 #[stable(feature = "rust1", since = "1.0.0")]
1116 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1119 fn next(&mut self) -> Option
<(&'a V
)> { self.inner.next() }
1120 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1122 #[stable(feature = "rust1", since = "1.0.0")]
1123 impl<'a
, K
, V
> DoubleEndedIterator
for Values
<'a
, K
, V
> {
1124 fn next_back(&mut self) -> Option
<(&'a V
)> { self.inner.next_back() }
1126 #[stable(feature = "rust1", since = "1.0.0")]
1127 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {}
1129 impl<'a
, K
, V
> Clone
for Range
<'a
, K
, V
> {
1130 fn clone(&self) -> Range
<'a
, K
, V
> { Range { inner: self.inner.clone() }
}
1132 impl<'a
, K
, V
> Iterator
for Range
<'a
, K
, V
> {
1133 type Item
= (&'a K
, &'a V
);
1135 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> { self.inner.next() }
1137 impl<'a
, K
, V
> DoubleEndedIterator
for Range
<'a
, K
, V
> {
1138 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> { self.inner.next_back() }
1141 impl<'a
, K
, V
> Iterator
for RangeMut
<'a
, K
, V
> {
1142 type Item
= (&'a K
, &'a
mut V
);
1144 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> { self.inner.next() }
1146 impl<'a
, K
, V
> DoubleEndedIterator
for RangeMut
<'a
, K
, V
> {
1147 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> { self.inner.next_back() }
1150 impl<'a
, K
: Ord
, V
> Entry
<'a
, K
, V
> {
1151 #[unstable(feature = "entry",
1152 reason
= "will soon be replaced by or_insert")]
1153 #[deprecated(since = "1.0",
1154 reason
= "replaced with more ergonomic `or_insert` and `or_insert_with`")]
1155 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1156 pub fn get(self) -> Result
<&'a
mut V
, VacantEntry
<'a
, K
, V
>> {
1158 Occupied(entry
) => Ok(entry
.into_mut()),
1159 Vacant(entry
) => Err(entry
),
1163 #[stable(feature = "rust1", since = "1.0.0")]
1164 /// Ensures a value is in the entry by inserting the default if empty, and returns
1165 /// a mutable reference to the value in the entry.
1166 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1168 Occupied(entry
) => entry
.into_mut(),
1169 Vacant(entry
) => entry
.insert(default),
1173 #[stable(feature = "rust1", since = "1.0.0")]
1174 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1175 /// and returns a mutable reference to the value in the entry.
1176 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1178 Occupied(entry
) => entry
.into_mut(),
1179 Vacant(entry
) => entry
.insert(default()),
1184 impl<'a
, K
: Ord
, V
> VacantEntry
<'a
, K
, V
> {
1185 /// Sets the value of the entry with the VacantEntry's key,
1186 /// and returns a mutable reference to it.
1187 #[stable(feature = "rust1", since = "1.0.0")]
1188 pub fn insert(self, value
: V
) -> &'a
mut V
{
1189 self.stack
.insert(self.key
, value
)
1193 impl<'a
, K
: Ord
, V
> OccupiedEntry
<'a
, K
, V
> {
1194 /// Gets a reference to the value in the entry.
1195 #[stable(feature = "rust1", since = "1.0.0")]
1196 pub fn get(&self) -> &V
{
1200 /// Gets a mutable reference to the value in the entry.
1201 #[stable(feature = "rust1", since = "1.0.0")]
1202 pub fn get_mut(&mut self) -> &mut V
{
1203 self.stack
.peek_mut()
1206 /// Converts the entry into a mutable reference to its value.
1207 #[stable(feature = "rust1", since = "1.0.0")]
1208 pub fn into_mut(self) -> &'a
mut V
{
1209 self.stack
.into_top()
1212 /// Sets the value of the entry with the OccupiedEntry's key,
1213 /// and returns the entry's old value.
1214 #[stable(feature = "rust1", since = "1.0.0")]
1215 pub fn insert(&mut self, mut value
: V
) -> V
{
1216 mem
::swap(self.stack
.peek_mut(), &mut value
);
1220 /// Takes the value of the entry out of the map, and returns it.
1221 #[stable(feature = "rust1", since = "1.0.0")]
1222 pub fn remove(self) -> V
{
1227 impl<K
, V
> BTreeMap
<K
, V
> {
1228 /// Gets an iterator over the entries of the map.
1233 /// use std::collections::BTreeMap;
1235 /// let mut map = BTreeMap::new();
1236 /// map.insert(1, "a");
1237 /// map.insert(2, "b");
1238 /// map.insert(3, "c");
1240 /// for (key, value) in map.iter() {
1241 /// println!("{}: {}", key, value);
1244 /// let (first_key, first_value) = map.iter().next().unwrap();
1245 /// assert_eq!((*first_key, *first_value), (1, "a"));
1247 #[stable(feature = "rust1", since = "1.0.0")]
1248 pub fn iter(&self) -> Iter
<K
, V
> {
1249 let len
= self.len();
1250 // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
1251 let mut lca
= VecDeque
::new();
1252 lca
.push_back(Traverse
::traverse(&self.root
));
1261 /// Gets a mutable iterator over the entries of the map.
1266 /// use std::collections::BTreeMap;
1268 /// let mut map = BTreeMap::new();
1269 /// map.insert("a", 1);
1270 /// map.insert("b", 2);
1271 /// map.insert("c", 3);
1273 /// // add 10 to the value if the key isn't "a"
1274 /// for (key, value) in map.iter_mut() {
1275 /// if key != &"a" {
1280 #[stable(feature = "rust1", since = "1.0.0")]
1281 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
1282 let len
= self.len();
1283 let mut lca
= VecDeque
::new();
1284 lca
.push_back(Traverse
::traverse(&mut self.root
));
1293 /// Gets an iterator over the keys of the map.
1298 /// use std::collections::BTreeMap;
1300 /// let mut a = BTreeMap::new();
1301 /// a.insert(1, "a");
1302 /// a.insert(2, "b");
1304 /// let keys: Vec<_> = a.keys().cloned().collect();
1305 /// assert_eq!(keys, [1, 2]);
1307 #[stable(feature = "rust1", since = "1.0.0")]
1308 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
1309 fn first
<A
, B
>((a
, _
): (A
, B
)) -> A { a }
1310 let first
: fn((&'a K
, &'a V
)) -> &'a K
= first
; // coerce to fn pointer
1312 Keys { inner: self.iter().map(first) }
1315 /// Gets an iterator over the values of the map.
1320 /// use std::collections::BTreeMap;
1322 /// let mut a = BTreeMap::new();
1323 /// a.insert(1, "a");
1324 /// a.insert(2, "b");
1326 /// let values: Vec<&str> = a.values().cloned().collect();
1327 /// assert_eq!(values, ["a", "b"]);
1329 #[stable(feature = "rust1", since = "1.0.0")]
1330 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
1331 fn second
<A
, B
>((_
, b
): (A
, B
)) -> B { b }
1332 let second
: fn((&'a K
, &'a V
)) -> &'a V
= second
; // coerce to fn pointer
1334 Values { inner: self.iter().map(second) }
1337 /// Returns the number of elements in the map.
1342 /// use std::collections::BTreeMap;
1344 /// let mut a = BTreeMap::new();
1345 /// assert_eq!(a.len(), 0);
1346 /// a.insert(1, "a");
1347 /// assert_eq!(a.len(), 1);
1349 #[stable(feature = "rust1", since = "1.0.0")]
1350 pub fn len(&self) -> usize { self.length }
1352 /// Returns true if the map contains no elements.
1357 /// use std::collections::BTreeMap;
1359 /// let mut a = BTreeMap::new();
1360 /// assert!(a.is_empty());
1361 /// a.insert(1, "a");
1362 /// assert!(!a.is_empty());
1364 #[stable(feature = "rust1", since = "1.0.0")]
1365 pub fn is_empty(&self) -> bool { self.len() == 0 }
1368 macro_rules
! range_impl
{
1369 ($root
:expr
, $min
:expr
, $max
:expr
, $as_slices_internal
:ident
, $iter
:ident
, $Range
:ident
,
1370 $edges
:ident
, [$
($mutability
:ident
)*]) => (
1372 // A deque that encodes two search paths containing (left-to-right):
1373 // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
1374 // and a series of truncated-from-the-right iterators.
1375 let mut traversals
= VecDeque
::new();
1376 let (root
, min
, max
) = ($root
, $min
, $max
);
1378 let mut leftmost
= None
;
1379 let mut rightmost
= None
;
1381 match (&min
, &max
) {
1382 (&Unbounded
, &Unbounded
) => {
1383 traversals
.push_back(Traverse
::traverse(root
))
1385 (&Unbounded
, &Included(_
)) | (&Unbounded
, &Excluded(_
)) => {
1386 rightmost
= Some(root
);
1388 (&Included(_
), &Unbounded
) | (&Excluded(_
), &Unbounded
) => {
1389 leftmost
= Some(root
);
1391 (&Included(min_key
), &Included(max_key
))
1392 | (&Included(min_key
), &Excluded(max_key
))
1393 | (&Excluded(min_key
), &Included(max_key
))
1394 | (&Excluded(min_key
), &Excluded(max_key
)) => {
1395 // lca represents the Lowest Common Ancestor, above which we never
1396 // walk, since everything else is outside the range to iterate.
1397 // ___________________
1398 // |__0_|_80_|_85_|_90_| (root)
1402 // ___________________
1403 // |__5_|_15_|_30_|_73_|
1407 // ___________________
1408 // |_33_|_58_|_63_|_68_| lca for the range [41, 65]
1409 // | |\___|___/| | iterator at traversals[2]
1414 let mut is_leaf
= root
.is_leaf();
1415 let mut lca
= root
.$
as_slices_internal();
1417 let slice
= lca
.slice_from(min_key
).slice_to(max_key
);
1418 if let [ref $
($mutability
)* edge
] = slice
.edges
{
1419 // Follow the only edge that leads the node that covers the range.
1420 is_leaf
= edge
.is_leaf();
1421 lca
= edge
.$
as_slices_internal();
1423 let mut iter
= slice
.$
iter();
1428 // Only change the state of nodes with edges.
1429 leftmost
= iter
.next_edge_item();
1430 rightmost
= iter
.next_edge_item_back();
1432 traversals
.push_back(iter
);
1438 // Keep narrowing the range by going down.
1439 // ___________________
1440 // |_38_|_43_|_48_|_53_|
1441 // | |____|____|____/ iterator at traversals[1]
1444 // ___________________
1445 // |_39_|_40_|_41_|_42_| (leaf, the last leftmost)
1446 // \_________| iterator at traversals[0]
1448 Included(key
) | Excluded(key
) =>
1449 while let Some(left
) = leftmost
{
1450 let is_leaf
= left
.is_leaf();
1451 let mut iter
= left
.$
as_slices_internal().slice_from(key
).$
iter();
1452 leftmost
= if is_leaf
{
1455 // Only change the state of nodes with edges.
1456 iter
.next_edge_item()
1458 traversals
.push_back(iter
);
1462 // If the leftmost iterator starts with an element, then it was an exact match.
1463 if let (Excluded(_
), Some(leftmost_iter
)) = (min
, traversals
.back_mut()) {
1464 // Drop this excluded element. `next_kv_item` has no effect when
1465 // the next item is an edge.
1466 leftmost_iter
.next_kv_item();
1469 // The code for the right side is similar.
1471 Included(key
) | Excluded(key
) =>
1472 while let Some(right
) = rightmost
{
1473 let is_leaf
= right
.is_leaf();
1474 let mut iter
= right
.$
as_slices_internal().slice_to(key
).$
iter();
1475 rightmost
= if is_leaf
{
1478 iter
.next_edge_item_back()
1480 traversals
.push_front(iter
);
1484 if let (Excluded(_
), Some(rightmost_iter
)) = (max
, traversals
.front_mut()) {
1485 rightmost_iter
.next_kv_item_back();
1490 traversals
: traversals
,
1491 size
: usize::MAX
, // unused
1498 impl<K
: Ord
, V
> BTreeMap
<K
, V
> {
1499 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
1500 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1501 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1502 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1507 /// # #![feature(btree_range, collections_bound)]
1508 /// use std::collections::BTreeMap;
1509 /// use std::collections::Bound::{Included, Unbounded};
1511 /// let mut map = BTreeMap::new();
1512 /// map.insert(3, "a");
1513 /// map.insert(5, "b");
1514 /// map.insert(8, "c");
1515 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
1516 /// println!("{}: {}", key, value);
1518 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
1520 #[unstable(feature = "btree_range",
1521 reason
= "matches collection reform specification, waiting for dust to settle")]
1522 pub fn range
<'a
>(&'a
self, min
: Bound
<&K
>, max
: Bound
<&K
>) -> Range
<'a
, K
, V
> {
1523 range_impl
!(&self.root
, min
, max
, as_slices_internal
, iter
, Range
, edges
, [])
1526 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
1527 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1528 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1529 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1534 /// # #![feature(btree_range, collections_bound)]
1535 /// use std::collections::BTreeMap;
1536 /// use std::collections::Bound::{Included, Excluded};
1538 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
1539 /// .map(|&s| (s, 0))
1541 /// for (_, balance) in map.range_mut(Included(&"B"), Excluded(&"Cheryl")) {
1542 /// *balance += 100;
1544 /// for (name, balance) in &map {
1545 /// println!("{} => {}", name, balance);
1548 #[unstable(feature = "btree_range",
1549 reason
= "matches collection reform specification, waiting for dust to settle")]
1550 pub fn range_mut
<'a
>(&'a
mut self, min
: Bound
<&K
>, max
: Bound
<&K
>) -> RangeMut
<'a
, K
, V
> {
1551 range_impl
!(&mut self.root
, min
, max
, as_slices_internal_mut
, iter_mut
, RangeMut
,
1555 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1560 /// use std::collections::BTreeMap;
1562 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1564 /// // count the number of occurrences of letters in the vec
1565 /// for x in vec!["a","b","a","c","a","b"] {
1566 /// *count.entry(x).or_insert(0) += 1;
1569 /// assert_eq!(count["a"], 3);
1571 #[stable(feature = "rust1", since = "1.0.0")]
1572 pub fn entry(&mut self, mut key
: K
) -> Entry
<K
, V
> {
1573 // same basic logic of `swap` and `pop`, blended together
1574 let mut stack
= stack
::PartialSearchStack
::new(self);
1576 let result
= stack
.with(move |pusher
, node
| {
1577 match Node
::search(node
, &key
) {
1580 Finished(Occupied(OccupiedEntry
{
1581 stack
: pusher
.seal(handle
)
1585 match handle
.force() {
1586 Leaf(leaf_handle
) => {
1587 Finished(Vacant(VacantEntry
{
1588 stack
: pusher
.seal(leaf_handle
),
1592 Internal(internal_handle
) => {
1594 pusher
.push(internal_handle
),
1603 Finished(finished
) => return finished
,
1604 Continue((new_stack
, renewed_key
)) => {