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/).
20 use core::cmp::Ordering;
22 use core::hash::{Hash, Hasher};
23 use core::iter::{Map, FromIterator};
25 use core::{fmt, mem, usize};
26 use Bound::{self, Included, Excluded, Unbounded};
29 use vec_deque::VecDeque;
31 use self::Continuation::{Continue, Finished};
33 use super::node::ForceResult::{Leaf, Internal};
34 use super::node::TraversalItem::{self, Elem, Edge};
35 use super::node::{Traversal, MutTraversal, MoveTraversal};
36 use super::node::{self, Node, Found, GoDown};
38 /// A map based on a B-Tree.
40 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
41 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
42 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
43 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
44 /// is done is *very* inefficient for modern computer architectures. In particular, every element
45 /// is stored in its own individually heap-allocated node. This means that every single insertion
46 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
47 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
50 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
51 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
52 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
53 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
54 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
55 /// the node using binary search. As a compromise, one could also perform a linear search
56 /// that initially only checks every i<sup>th</sup> element for some choice of i.
58 /// Currently, our implementation simply performs naive linear search. This provides excellent
59 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
60 /// would like to further explore choosing the optimal search strategy based on the choice of B,
61 /// and possibly other factors. Using linear search, searching for a random element is expected
62 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
63 /// however, performance is excellent.
65 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
66 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
67 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
69 #[stable(feature = "rust1", since = "1.0.0")]
70 pub struct BTreeMap<K, V> {
77 /// An abstract base over-which all other BTree iterators are built.
80 traversals: VecDeque<T>,
84 /// An iterator over a BTreeMap's entries.
85 #[stable(feature = "rust1", since = "1.0.0")]
86 pub struct Iter<'a, K: 'a, V: 'a> {
87 inner: AbsIter<Traversal<'a, K, V>>,
90 /// A mutable iterator over a BTreeMap's entries.
91 #[stable(feature = "rust1", since = "1.0.0")]
92 pub struct IterMut<'a, K: 'a, V: 'a> {
93 inner: AbsIter<MutTraversal<'a, K, V>>,
96 /// An owning iterator over a BTreeMap's entries.
97 #[stable(feature = "rust1", since = "1.0.0")]
98 pub struct IntoIter<K, V> {
99 inner: AbsIter<MoveTraversal<K, V>>,
102 /// An iterator over a BTreeMap's keys.
103 #[stable(feature = "rust1", since = "1.0.0")]
104 pub struct Keys<'a, K: 'a, V: 'a> {
105 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>,
108 /// An iterator over a BTreeMap's values.
109 #[stable(feature = "rust1", since = "1.0.0")]
110 pub struct Values<'a, K: 'a, V: 'a> {
111 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>,
114 /// An iterator over a sub-range of BTreeMap's entries.
115 pub struct Range<'a, K: 'a, V: 'a> {
116 inner: AbsIter<Traversal<'a, K, V>>,
119 /// A mutable iterator over a sub-range of BTreeMap's entries.
120 pub struct RangeMut<'a, K: 'a, V: 'a> {
121 inner: AbsIter<MutTraversal<'a, K, V>>,
124 /// A view into a single entry in a map, which may either be vacant or occupied.
125 #[stable(feature = "rust1", since = "1.0.0")]
126 pub enum Entry<'a, K: 'a, V: 'a> {
128 #[stable(feature = "rust1", since = "1.0.0")]
129 Vacant(VacantEntry<'a, K, V>),
131 /// An occupied Entry
132 #[stable(feature = "rust1", since = "1.0.0")]
133 Occupied(OccupiedEntry<'a, K, V>),
137 #[stable(feature = "rust1", since = "1.0.0")]
138 pub struct VacantEntry<'a, K: 'a, V: 'a> {
140 stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>,
143 /// An occupied Entry.
144 #[stable(feature = "rust1", since = "1.0.0")]
145 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
146 stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>,
149 impl<K: Ord, V> BTreeMap<K, V> {
150 /// Makes a new empty BTreeMap with a reasonable choice for B.
151 #[stable(feature = "rust1", since = "1.0.0")]
153 pub fn new() -> BTreeMap<K, V> {
154 // FIXME(Gankro): Tune this as a function of size_of<K/V>?
158 /// Makes a new empty BTreeMap with the given B.
160 /// B cannot be less than 2.
161 #[unstable(feature = "btree_b",
162 reason = "probably want this to be on the type, eventually",
164 #[deprecated(since = "1.4.0", reason = "niche API")]
165 pub fn with_b(b: usize) -> BTreeMap<K, V> {
166 assert!(b > 1, "B must be greater than 1");
170 root: Node::make_leaf_root(b),
175 /// Clears the map, removing all values.
180 /// use std::collections::BTreeMap;
182 /// let mut a = BTreeMap::new();
183 /// a.insert(1, "a");
185 /// assert!(a.is_empty());
187 #[stable(feature = "rust1", since = "1.0.0")]
189 pub fn clear(&mut self) {
191 // avoid recursive destructors by manually traversing the tree
192 for _ in mem::replace(self, BTreeMap::with_b(b)) {}
195 // Searching in a B-Tree is pretty straightforward.
197 // Start at the root. Try to find the key in the current node. If we find it, return it.
198 // If it's not in there, follow the edge *before* the smallest key larger than
199 // the search key. If no such key exists (they're *all* smaller), then just take the last
200 // edge in the node. If we're in a leaf and we don't find our key, then it's not
203 /// Returns a reference to the value corresponding to the key.
205 /// The key may be any borrowed form of the map's key type, but the ordering
206 /// on the borrowed form *must* match the ordering on the key type.
211 /// use std::collections::BTreeMap;
213 /// let mut map = BTreeMap::new();
214 /// map.insert(1, "a");
215 /// assert_eq!(map.get(&1), Some(&"a"));
216 /// assert_eq!(map.get(&2), None);
218 #[stable(feature = "rust1", since = "1.0.0")]
219 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
223 let mut cur_node = &self.root;
225 match Node::search(cur_node, key) {
226 Found(handle) => return Some(handle.into_kv().1),
228 match handle.force() {
229 Leaf(_) => return None,
230 Internal(internal_handle) => {
231 cur_node = internal_handle.into_edge();
240 /// Returns true if the map contains a value for the specified key.
242 /// The key may be any borrowed form of the map's key type, but the ordering
243 /// on the borrowed form *must* match the ordering on the key type.
248 /// use std::collections::BTreeMap;
250 /// let mut map = BTreeMap::new();
251 /// map.insert(1, "a");
252 /// assert_eq!(map.contains_key(&1), true);
253 /// assert_eq!(map.contains_key(&2), false);
255 #[stable(feature = "rust1", since = "1.0.0")]
256 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
260 self.get(key).is_some()
263 /// Returns a mutable reference to the value corresponding to the key.
265 /// The key may be any borrowed form of the map's key type, but the ordering
266 /// on the borrowed form *must* match the ordering on the key type.
271 /// use std::collections::BTreeMap;
273 /// let mut map = BTreeMap::new();
274 /// map.insert(1, "a");
275 /// if let Some(x) = map.get_mut(&1) {
278 /// assert_eq!(map[&1], "b");
280 // See `get` for implementation notes, this is basically a copy-paste with mut's added
281 #[stable(feature = "rust1", since = "1.0.0")]
282 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
286 // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
287 let mut temp_node = &mut self.root;
289 let cur_node = temp_node;
290 match Node::search(cur_node, key) {
291 Found(handle) => return Some(handle.into_kv_mut().1),
293 match handle.force() {
294 Leaf(_) => return None,
295 Internal(internal_handle) => {
296 temp_node = internal_handle.into_edge_mut();
305 // Insertion in a B-Tree is a bit complicated.
307 // First we do the same kind of search described in `find`. But we need to maintain a stack of
308 // all the nodes/edges in our search path. If we find a match for the key we're trying to
309 // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
310 // we attempt to insert our key-value pair at the same location we would want to follow another
313 // If the node has room, then this is done in the obvious way by shifting elements. However,
314 // if the node itself is full, we split node into two, and give its median key-value
315 // pair to its parent to insert the new node with. Of course, the parent may also be
316 // full, and insertion can propagate until we reach the root. If we reach the root, and
317 // it is *also* full, then we split the root and place the two nodes under a newly made root.
319 // Note that we subtly deviate from Open Data Structures in our implementation of split.
320 // ODS describes inserting into the node *regardless* of its capacity, and then
321 // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
322 // Instead, we split beforehand, and then insert the key-value pair into the appropriate
323 // result node. This has two consequences:
325 // 1) While ODS produces a left node of size B-1, and a right node of size B,
326 // we may potentially reverse this. However, this shouldn't effect the analysis.
328 // 2) While ODS may potentially return the pair we *just* inserted after
329 // the split, we will never do this. Again, this shouldn't effect the analysis.
331 /// Inserts a key-value pair into the map.
333 /// If the map did not have this key present, `None` is returned.
335 /// If the map did have this key present, the key is not updated, the
336 /// value is updated and the old value is returned.
337 /// See the [module-level documentation] for more.
339 /// [module-level documentation]: index.html#insert-and-complex-keys
344 /// use std::collections::BTreeMap;
346 /// let mut map = BTreeMap::new();
347 /// assert_eq!(map.insert(37, "a"), None);
348 /// assert_eq!(map.is_empty(), false);
350 /// map.insert(37, "b");
351 /// assert_eq!(map.insert(37, "c"), Some("b"));
352 /// assert_eq!(map[&37], "c");
354 #[stable(feature = "rust1", since = "1.0.0")]
355 pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
356 // This is a stack of rawptrs to nodes paired with indices, respectively
357 // representing the nodes and edges of our search path. We have to store rawptrs
358 // because as far as Rust is concerned, we can mutate aliased data with such a
359 // stack. It is of course correct, but what it doesn't know is that we will only
360 // be popping and using these ptrs one at a time in child-to-parent order. The alternative
361 // to doing this is to take the Nodes from their parents. This actually makes
362 // borrowck *really* happy and everything is pretty smooth. However, this creates
363 // *tons* of pointless writes, and requires us to always walk all the way back to
364 // the root after an insertion, even if we only needed to change a leaf. Therefore,
365 // we accept this potential unsafety and complexity in the name of performance.
367 // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
368 // by the stack module. All it can do is immutably read nodes, and ask the search stack
369 // to proceed down some edge by index. This makes the search logic we'll be reusing in a
370 // few different methods much neater, and of course drastically improves safety.
371 let mut stack = stack::PartialSearchStack::new(self);
374 let result = stack.with(move |pusher, node| {
375 // Same basic logic as found in `find`, but with PartialSearchStack mediating the
376 // actual nodes for us
377 match Node::search(node, &key) {
378 Found(mut handle) => {
379 // Perfect match, swap the values and return the old one
380 mem::swap(handle.val_mut(), &mut value);
381 Finished(Some(value))
384 // We need to keep searching, try to get the search stack
385 // to go down further
386 match handle.force() {
387 Leaf(leaf_handle) => {
388 // We've reached a leaf, perform the insertion here
389 pusher.seal(leaf_handle).insert(key, value);
392 Internal(internal_handle) => {
393 // We've found the subtree to insert this key/value pair in,
395 Continue((pusher.push(internal_handle), key, value))
402 Finished(ret) => return ret,
403 Continue((new_stack, renewed_key, renewed_val)) => {
412 // Deletion is the most complicated operation for a B-Tree.
414 // First we do the same kind of search described in
415 // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
416 // If we don't find the key, then we just return `None` and do nothing. If we do find the
417 // key, we perform two operations: remove the item, and then possibly handle underflow.
419 // # removing the item
420 // If the node is a leaf, we just remove the item, and shift
421 // any items after it back to fill the hole.
423 // If the node is an internal node, we *swap* the item with the smallest item in
424 // in its right subtree (which must reside in a leaf), and then revert to the leaf
427 // # handling underflow
428 // After removing an item, there may be too few items in the node. We want nodes
429 // to be mostly full for efficiency, although we make an exception for the root, which
430 // may have as few as one item. If this is the case, we may first try to steal
431 // an item from our left or right neighbour.
433 // To steal from the left (right) neighbour,
434 // we take the largest (smallest) item and child from it. We then swap the taken item
435 // with the item in their mutual parent that separates them, and then insert the
436 // parent's item and the taken child into the first (last) index of the underflowed node.
438 // However, stealing has the possibility of underflowing our neighbour. If this is the
439 // case, we instead *merge* with our neighbour. This of course reduces the number of
440 // children in the parent. Therefore, we also steal the item that separates the now
441 // merged nodes, and insert it into the merged node.
443 // Merging may cause the parent to underflow. If this is the case, then we must repeat
444 // the underflow handling process on the parent. If merging merges the last two children
445 // of the root, then we replace the root with the merged node.
447 /// Removes a key from the map, returning the value at the key if the key
448 /// was previously in the map.
450 /// The key may be any borrowed form of the map's key type, but the ordering
451 /// on the borrowed form *must* match the ordering on the key type.
456 /// use std::collections::BTreeMap;
458 /// let mut map = BTreeMap::new();
459 /// map.insert(1, "a");
460 /// assert_eq!(map.remove(&1), Some("a"));
461 /// assert_eq!(map.remove(&1), None);
463 #[stable(feature = "rust1", since = "1.0.0")]
464 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
468 // See `swap` for a more thorough description of the stuff going on in here
469 let mut stack = stack::PartialSearchStack::new(self);
471 let result = stack.with(move |pusher, node| {
472 match Node::search(node, key) {
474 // Perfect match. Terminate the stack here, and remove the entry
475 Finished(Some(pusher.seal(handle).remove()))
478 // We need to keep searching, try to go down the next edge
479 match handle.force() {
480 // We're at a leaf; the key isn't in here
481 Leaf(_) => Finished(None),
482 Internal(internal_handle) => Continue(pusher.push(internal_handle)),
488 Finished(ret) => return ret.map(|(_, v)| v),
489 Continue(new_stack) => stack = new_stack,
495 #[stable(feature = "rust1", since = "1.0.0")]
496 impl<K, V> IntoIterator for BTreeMap<K, V> {
498 type IntoIter = IntoIter<K, V>;
500 /// Gets an owning iterator over the entries of the map.
505 /// use std::collections::BTreeMap;
507 /// let mut map = BTreeMap::new();
508 /// map.insert(1, "a");
509 /// map.insert(2, "b");
510 /// map.insert(3, "c");
512 /// for (key, value) in map.into_iter() {
513 /// println!("{}: {}", key, value);
516 fn into_iter(self) -> IntoIter<K, V> {
517 let len = self.len();
518 let mut lca = VecDeque::new();
519 lca.push_back(Traverse::traverse(self.root));
529 #[stable(feature = "rust1", since = "1.0.0")]
530 impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
531 type Item = (&'a K, &'a V);
532 type IntoIter = Iter<'a, K, V>;
534 fn into_iter(self) -> Iter<'a, K, V> {
539 #[stable(feature = "rust1", since = "1.0.0")]
540 impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
541 type Item = (&'a K, &'a mut V);
542 type IntoIter = IterMut<'a, K, V>;
544 fn into_iter(mut self) -> IterMut<'a, K, V> {
549 /// A helper enum useful for deciding whether to continue a loop since we can't
550 /// return from a closure
551 enum Continuation<A, B> {
556 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
557 /// to nodes. By using this module much better safety guarantees can be made, and more search
558 /// boilerplate gets cut out.
562 use core::ops::{Deref, DerefMut};
564 use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
565 use super::super::node::handle;
568 struct InvariantLifetime<'id>(marker::PhantomData<::core::cell::Cell<&'id ()>>);
570 impl<'id> InvariantLifetime<'id> {
571 fn new() -> InvariantLifetime<'id> {
572 InvariantLifetime(marker::PhantomData)
576 /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
577 /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
578 /// with the exact requested lifetime can be used. This is in contrast to normal references,
579 /// where `&'static` can be used in any function expecting any lifetime reference.
580 pub struct IdRef<'id, T: 'id> {
582 _marker: InvariantLifetime<'id>,
585 impl<'id, T> Deref for IdRef<'id, T> {
588 fn deref(&self) -> &T {
593 impl<'id, T> DerefMut for IdRef<'id, T> {
594 fn deref_mut(&mut self) -> &mut T {
599 type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
600 type Stack<K, V> = Vec<StackItem<K, V>>;
602 /// A `PartialSearchStack` handles the construction of a search stack.
603 pub struct PartialSearchStack<'a, K: 'a, V: 'a> {
604 map: &'a mut BTreeMap<K, V>,
606 next: *mut Node<K, V>,
609 /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
610 /// methods depending on the type of what the path points to for removing an element, inserting
611 /// a new element, and manipulating to element at the top of the stack.
612 pub struct SearchStack<'a, K: 'a, V: 'a, Type, NodeType> {
613 map: &'a mut BTreeMap<K, V>,
615 top: node::Handle<*mut Node<K, V>, Type, NodeType>,
618 /// A `PartialSearchStack` that doesn't hold a reference to the next node, and is just
619 /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
620 /// for more details.
621 pub struct Pusher<'id, 'a, K: 'a, V: 'a> {
622 map: &'a mut BTreeMap<K, V>,
624 _marker: InvariantLifetime<'id>,
627 impl<'a, K, V> PartialSearchStack<'a, K, V> {
628 /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
629 /// root of the tree.
630 pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
631 let depth = map.depth;
634 next: &mut map.root as *mut _,
636 stack: Vec::with_capacity(depth),
640 /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
641 /// to interact with, search, and finally push the `Node` onto the stack. The passed in
642 /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
643 /// ensures that only `Handle`s from the correct `Node` can be pushed.
645 /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
646 /// handles with the same `'id`. The closure could only get references with that lifetime
647 /// through its arguments or through some other `IdRef` that it has lying around. However,
648 /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
649 /// parameter, it would need to have precisely the correct lifetime, which would mean that
650 /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
651 /// specific lifetime instead of the one that `with` chooses to give it.
653 /// See also Haskell's `ST` monad, which uses a similar trick.
654 pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
655 IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
656 let pusher = Pusher {
659 _marker: InvariantLifetime::new(),
662 inner: unsafe { &mut *self.next },
663 _marker: InvariantLifetime::new(),
666 closure(pusher, node)
670 impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
671 /// Pushes the requested child of the stack's current top on top of the stack. If the child
672 /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
674 pub fn push(mut self,
675 mut edge: node::Handle<IdRef<'id, Node<K, V>>, handle::Edge, handle::Internal>)
676 -> PartialSearchStack<'a, K, V> {
677 self.stack.push(edge.as_raw());
681 next: edge.edge_mut() as *mut _,
685 /// Converts the PartialSearchStack into a SearchStack.
686 pub fn seal<Type, NodeType>(self,
687 mut handle: node::Handle<IdRef<'id, Node<K, V>>,
690 -> SearchStack<'a, K, V, Type, NodeType> {
694 top: handle.as_raw(),
699 impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
700 /// Gets a reference to the value the stack points to.
701 pub fn peek(&self) -> &V {
702 unsafe { self.top.from_raw().into_kv().1 }
705 /// Gets a mutable reference to the value the stack points to.
706 pub fn peek_mut(&mut self) -> &mut V {
707 unsafe { self.top.from_raw_mut().into_kv_mut().1 }
710 /// Converts the stack into a mutable reference to the value it points to, with a lifetime
711 /// tied to the original tree.
712 pub fn into_top(mut self) -> &'a mut V {
713 unsafe { &mut *(self.top.from_raw_mut().val_mut() as *mut V) }
717 impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
718 /// Removes the key and value in the top element of the stack, then handles underflows as
719 /// described in BTree's pop function.
720 fn remove_leaf(mut self) -> (K, V) {
721 self.map.length -= 1;
723 // Remove the key-value pair from the leaf that this search stack points to.
724 // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
725 // to avoid ownership issues.
726 let (key_val, mut underflow) = unsafe {
727 let key_val = self.top.from_raw_mut().remove_as_leaf();
728 let underflow = self.top.from_raw().node().is_underfull();
733 match self.stack.pop() {
735 // We've reached the root, so no matter what, we're done. We manually
736 // access the root via the tree itself to avoid creating any dangling
738 if self.map.root.is_empty() && !self.map.root.is_leaf() {
739 // We've emptied out the root, so make its only child the new root.
740 // If it's a leaf, we just let it become empty.
742 self.map.root.hoist_lone_child();
746 Some(mut handle) => {
748 // Underflow! Handle it!
750 handle.from_raw_mut().handle_underflow();
751 underflow = handle.from_raw().node().is_underfull();
763 impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
764 /// Removes the key and value in the top element of the stack, then handles underflows as
765 /// described in BTree's pop function.
766 pub fn remove(self) -> (K, V) {
767 // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
768 // in a BTree. Note that this may put the tree in an inconsistent state (further
769 // described in into_leaf's comments), but this is immediately fixed by the
770 // removing the value we want to remove
771 self.into_leaf().remove_leaf()
774 /// Subroutine for removal. Takes a search stack for a key that might terminate at an
775 /// internal node, and mutates the tree and search stack to *make* it a search stack
776 /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
777 /// leaves the tree in an inconsistent state that must be repaired by the caller by
778 /// removing the entry in question. Specifically the key-value pair and its successor will
780 fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
782 let mut top_raw = self.top;
783 let mut top = top_raw.from_raw_mut();
785 let key_ptr = top.key_mut() as *mut _;
786 let val_ptr = top.val_mut() as *mut _;
788 // Try to go into the right subtree of the found key to find its successor
790 Leaf(mut leaf_handle) => {
791 // We're a proper leaf stack, nothing to do
795 top: leaf_handle.as_raw(),
798 Internal(mut internal_handle) => {
799 let mut right_handle = internal_handle.right_edge();
801 // We're not a proper leaf stack, let's get to work.
802 self.stack.push(right_handle.as_raw());
804 let mut temp_node = right_handle.edge_mut();
806 // Walk into the smallest subtree of this node
807 let node = temp_node;
809 match node.kv_handle(0).force() {
810 Leaf(mut handle) => {
811 // This node is a leaf, do the swap and return
812 mem::swap(handle.key_mut(), &mut *key_ptr);
813 mem::swap(handle.val_mut(), &mut *val_ptr);
817 top: handle.as_raw(),
820 Internal(kv_handle) => {
821 // This node is internal, go deeper
822 let mut handle = kv_handle.into_left_edge();
823 self.stack.push(handle.as_raw());
824 temp_node = handle.into_edge_mut();
834 impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
835 /// Inserts the key and value into the top element in the stack, and if that node has to
836 /// split recursively inserts the split contents into the next element stack until
839 /// Assumes that the stack represents a search path from the root to a leaf.
841 /// An &mut V is returned to the inserted value, for callers that want a reference to this.
842 pub fn insert(mut self, key: K, val: V) -> &'a mut V {
844 self.map.length += 1;
846 // Insert the key and value into the leaf at the top of the stack
847 let (mut insertion, inserted_ptr) = self.top
849 .insert_as_leaf(key, val);
854 // The last insertion went off without a hitch, no splits! We can stop
856 return &mut *inserted_ptr;
858 Split(key, val, right) => {
859 match self.stack.pop() {
860 // The last insertion triggered a split, so get the next element on
861 // the stack to recursively insert the split node into.
863 // The stack was empty; we've split the root, and need to make a
864 // a new one. This is done in-place because we can't move the
865 // root out of a reference to the tree.
866 Node::make_internal_root(&mut self.map.root,
873 return &mut *inserted_ptr;
875 Some(mut handle) => {
876 // The stack wasn't empty, do the insertion and recurse
877 insertion = handle.from_raw_mut()
878 .insert_as_internal(key, val, right);
890 #[stable(feature = "rust1", since = "1.0.0")]
891 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
892 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
893 let mut map = BTreeMap::new();
899 #[stable(feature = "rust1", since = "1.0.0")]
900 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
902 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
909 #[stable(feature = "extend_ref", since = "1.2.0")]
910 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
911 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
912 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
916 #[stable(feature = "rust1", since = "1.0.0")]
917 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
918 fn hash<H: Hasher>(&self, state: &mut H) {
925 #[stable(feature = "rust1", since = "1.0.0")]
926 impl<K: Ord, V> Default for BTreeMap<K, V> {
927 fn default() -> BTreeMap<K, V> {
932 #[stable(feature = "rust1", since = "1.0.0")]
933 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
934 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
935 self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
939 #[stable(feature = "rust1", since = "1.0.0")]
940 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
942 #[stable(feature = "rust1", since = "1.0.0")]
943 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
945 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
946 self.iter().partial_cmp(other.iter())
950 #[stable(feature = "rust1", since = "1.0.0")]
951 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
953 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
954 self.iter().cmp(other.iter())
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
960 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
961 f.debug_map().entries(self.iter()).finish()
965 #[stable(feature = "rust1", since = "1.0.0")]
966 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
973 fn index(&self, key: &Q) -> &V {
974 self.get(key).expect("no entry found for key")
978 /// Genericizes over how to get the correct type of iterator from the correct type
979 /// of Node ownership.
981 fn traverse(node: N) -> Self;
984 impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
985 fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
990 impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
991 fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
996 impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
997 fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
1002 /// Represents an operation to perform inside the following iterator methods.
1003 /// This is necessary to use in `next` because we want to modify `self.traversals` inside
1004 /// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
1005 /// what we want to do, and do it after the match.
1010 impl<K, V, E, T> Iterator for AbsIter<T>
1011 where T: DoubleEndedIterator<Item = TraversalItem<K, V, E>> + Traverse<E>
1015 // Our iterator represents a queue of all ancestors of elements we have
1016 // yet to yield, from smallest to largest. Note that the design of these
1017 // iterators permits an *arbitrary* initial pair of min and max, making
1018 // these arbitrary sub-range iterators.
1019 fn next(&mut self) -> Option<(K, V)> {
1021 // We want the smallest element, so try to get the back of the queue
1022 let op = match self.traversals.back_mut() {
1023 None => return None,
1024 // The queue wasn't empty, so continue along the node in its head
1027 // The head is empty, so Pop it off and continue the process
1029 // The head yielded an edge, so make that the new head
1030 Some(Edge(next)) => Push(Traverse::traverse(next)),
1031 // The head yielded an entry, so yield that
1040 // Handle any operation as necessary, without a conflicting borrow of the queue
1043 self.traversals.push_back(item);
1046 self.traversals.pop_back();
1052 fn size_hint(&self) -> (usize, Option<usize>) {
1053 (self.size, Some(self.size))
1057 impl<K, V, E, T> DoubleEndedIterator for AbsIter<T>
1058 where T: DoubleEndedIterator<Item = TraversalItem<K, V, E>> + Traverse<E>
1060 // next_back is totally symmetric to next
1062 fn next_back(&mut self) -> Option<(K, V)> {
1064 let op = match self.traversals.front_mut() {
1065 None => return None,
1067 match iter.next_back() {
1069 Some(Edge(next)) => Push(Traverse::traverse(next)),
1080 self.traversals.push_front(item);
1083 self.traversals.pop_front();
1090 impl<'a, K, V> Clone for Iter<'a, K, V> {
1091 fn clone(&self) -> Iter<'a, K, V> {
1092 Iter { inner: self.inner.clone() }
1095 #[stable(feature = "rust1", since = "1.0.0")]
1096 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1097 type Item = (&'a K, &'a V);
1099 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1102 fn size_hint(&self) -> (usize, Option<usize>) {
1103 self.inner.size_hint()
1106 #[stable(feature = "rust1", since = "1.0.0")]
1107 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1108 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1109 self.inner.next_back()
1112 #[stable(feature = "rust1", since = "1.0.0")]
1113 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1115 #[stable(feature = "rust1", since = "1.0.0")]
1116 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1117 type Item = (&'a K, &'a mut V);
1119 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1122 fn size_hint(&self) -> (usize, Option<usize>) {
1123 self.inner.size_hint()
1126 #[stable(feature = "rust1", since = "1.0.0")]
1127 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1128 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1129 self.inner.next_back()
1132 #[stable(feature = "rust1", since = "1.0.0")]
1133 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1135 #[stable(feature = "rust1", since = "1.0.0")]
1136 impl<K, V> Iterator for IntoIter<K, V> {
1139 fn next(&mut self) -> Option<(K, V)> {
1142 fn size_hint(&self) -> (usize, Option<usize>) {
1143 self.inner.size_hint()
1146 #[stable(feature = "rust1", since = "1.0.0")]
1147 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1148 fn next_back(&mut self) -> Option<(K, V)> {
1149 self.inner.next_back()
1152 #[stable(feature = "rust1", since = "1.0.0")]
1153 impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
1155 impl<'a, K, V> Clone for Keys<'a, K, V> {
1156 fn clone(&self) -> Keys<'a, K, V> {
1157 Keys { inner: self.inner.clone() }
1160 #[stable(feature = "rust1", since = "1.0.0")]
1161 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1164 fn next(&mut self) -> Option<(&'a K)> {
1167 fn size_hint(&self) -> (usize, Option<usize>) {
1168 self.inner.size_hint()
1171 #[stable(feature = "rust1", since = "1.0.0")]
1172 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1173 fn next_back(&mut self) -> Option<(&'a K)> {
1174 self.inner.next_back()
1177 #[stable(feature = "rust1", since = "1.0.0")]
1178 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
1181 impl<'a, K, V> Clone for Values<'a, K, V> {
1182 fn clone(&self) -> Values<'a, K, V> {
1183 Values { inner: self.inner.clone() }
1186 #[stable(feature = "rust1", since = "1.0.0")]
1187 impl<'a, K, V> Iterator for Values<'a, K, V> {
1190 fn next(&mut self) -> Option<(&'a V)> {
1193 fn size_hint(&self) -> (usize, Option<usize>) {
1194 self.inner.size_hint()
1197 #[stable(feature = "rust1", since = "1.0.0")]
1198 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1199 fn next_back(&mut self) -> Option<(&'a V)> {
1200 self.inner.next_back()
1203 #[stable(feature = "rust1", since = "1.0.0")]
1204 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
1206 impl<'a, K, V> Clone for Range<'a, K, V> {
1207 fn clone(&self) -> Range<'a, K, V> {
1208 Range { inner: self.inner.clone() }
1211 impl<'a, K, V> Iterator for Range<'a, K, V> {
1212 type Item = (&'a K, &'a V);
1214 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1218 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1219 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1220 self.inner.next_back()
1224 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1225 type Item = (&'a K, &'a mut V);
1227 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1231 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1232 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1233 self.inner.next_back()
1237 impl<'a, K: Ord, V> Entry<'a, K, V> {
1238 #[stable(feature = "rust1", since = "1.0.0")]
1239 /// Ensures a value is in the entry by inserting the default if empty, and returns
1240 /// a mutable reference to the value in the entry.
1241 pub fn or_insert(self, default: V) -> &'a mut V {
1243 Occupied(entry) => entry.into_mut(),
1244 Vacant(entry) => entry.insert(default),
1248 #[stable(feature = "rust1", since = "1.0.0")]
1249 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1250 /// and returns a mutable reference to the value in the entry.
1251 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1253 Occupied(entry) => entry.into_mut(),
1254 Vacant(entry) => entry.insert(default()),
1259 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1260 /// Sets the value of the entry with the VacantEntry's key,
1261 /// and returns a mutable reference to it.
1262 #[stable(feature = "rust1", since = "1.0.0")]
1263 pub fn insert(self, value: V) -> &'a mut V {
1264 self.stack.insert(self.key, value)
1268 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1269 /// Gets a reference to the value in the entry.
1270 #[stable(feature = "rust1", since = "1.0.0")]
1271 pub fn get(&self) -> &V {
1275 /// Gets a mutable reference to the value in the entry.
1276 #[stable(feature = "rust1", since = "1.0.0")]
1277 pub fn get_mut(&mut self) -> &mut V {
1278 self.stack.peek_mut()
1281 /// Converts the entry into a mutable reference to its value.
1282 #[stable(feature = "rust1", since = "1.0.0")]
1283 pub fn into_mut(self) -> &'a mut V {
1284 self.stack.into_top()
1287 /// Sets the value of the entry with the OccupiedEntry's key,
1288 /// and returns the entry's old value.
1289 #[stable(feature = "rust1", since = "1.0.0")]
1290 pub fn insert(&mut self, mut value: V) -> V {
1291 mem::swap(self.stack.peek_mut(), &mut value);
1295 /// Takes the value of the entry out of the map, and returns it.
1296 #[stable(feature = "rust1", since = "1.0.0")]
1297 pub fn remove(self) -> V {
1298 self.stack.remove().1
1302 impl<K, V> BTreeMap<K, V> {
1303 /// Gets an iterator over the entries of the map.
1308 /// use std::collections::BTreeMap;
1310 /// let mut map = BTreeMap::new();
1311 /// map.insert(1, "a");
1312 /// map.insert(2, "b");
1313 /// map.insert(3, "c");
1315 /// for (key, value) in map.iter() {
1316 /// println!("{}: {}", key, value);
1319 /// let (first_key, first_value) = map.iter().next().unwrap();
1320 /// assert_eq!((*first_key, *first_value), (1, "a"));
1322 #[stable(feature = "rust1", since = "1.0.0")]
1323 pub fn iter(&self) -> Iter<K, V> {
1324 let len = self.len();
1325 // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
1326 let mut lca = VecDeque::new();
1327 lca.push_back(Traverse::traverse(&self.root));
1336 /// Gets a mutable iterator over the entries of the map.
1341 /// use std::collections::BTreeMap;
1343 /// let mut map = BTreeMap::new();
1344 /// map.insert("a", 1);
1345 /// map.insert("b", 2);
1346 /// map.insert("c", 3);
1348 /// // add 10 to the value if the key isn't "a"
1349 /// for (key, value) in map.iter_mut() {
1350 /// if key != &"a" {
1355 #[stable(feature = "rust1", since = "1.0.0")]
1356 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1357 let len = self.len();
1358 let mut lca = VecDeque::new();
1359 lca.push_back(Traverse::traverse(&mut self.root));
1368 /// Gets an iterator over the keys of the map.
1373 /// use std::collections::BTreeMap;
1375 /// let mut a = BTreeMap::new();
1376 /// a.insert(1, "a");
1377 /// a.insert(2, "b");
1379 /// let keys: Vec<_> = a.keys().cloned().collect();
1380 /// assert_eq!(keys, [1, 2]);
1382 #[stable(feature = "rust1", since = "1.0.0")]
1383 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1384 fn first<A, B>((a, _): (A, B)) -> A {
1387 let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
1389 Keys { inner: self.iter().map(first) }
1392 /// Gets an iterator over the values of the map.
1397 /// use std::collections::BTreeMap;
1399 /// let mut a = BTreeMap::new();
1400 /// a.insert(1, "a");
1401 /// a.insert(2, "b");
1403 /// let values: Vec<&str> = a.values().cloned().collect();
1404 /// assert_eq!(values, ["a", "b"]);
1406 #[stable(feature = "rust1", since = "1.0.0")]
1407 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1408 fn second<A, B>((_, b): (A, B)) -> B {
1411 let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
1413 Values { inner: self.iter().map(second) }
1416 /// Returns the number of elements in the map.
1421 /// use std::collections::BTreeMap;
1423 /// let mut a = BTreeMap::new();
1424 /// assert_eq!(a.len(), 0);
1425 /// a.insert(1, "a");
1426 /// assert_eq!(a.len(), 1);
1428 #[stable(feature = "rust1", since = "1.0.0")]
1429 pub fn len(&self) -> usize {
1433 /// Returns true if the map contains no elements.
1438 /// use std::collections::BTreeMap;
1440 /// let mut a = BTreeMap::new();
1441 /// assert!(a.is_empty());
1442 /// a.insert(1, "a");
1443 /// assert!(!a.is_empty());
1445 #[stable(feature = "rust1", since = "1.0.0")]
1446 pub fn is_empty(&self) -> bool {
1451 macro_rules! range_impl {
1452 ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident,
1453 $edges:ident, [$($mutability:ident)*]) => (
1455 // A deque that encodes two search paths containing (left-to-right):
1456 // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
1457 // and a series of truncated-from-the-right iterators.
1458 let mut traversals = VecDeque::new();
1459 let (root, min, max) = ($root, $min, $max);
1461 let mut leftmost = None;
1462 let mut rightmost = None;
1464 match (&min, &max) {
1465 (&Unbounded, &Unbounded) => {
1466 traversals.push_back(Traverse::traverse(root))
1468 (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => {
1469 rightmost = Some(root);
1471 (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => {
1472 leftmost = Some(root);
1474 (&Included(min_key), &Included(max_key))
1475 | (&Included(min_key), &Excluded(max_key))
1476 | (&Excluded(min_key), &Included(max_key))
1477 | (&Excluded(min_key), &Excluded(max_key)) => {
1478 // lca represents the Lowest Common Ancestor, above which we never
1479 // walk, since everything else is outside the range to iterate.
1480 // ___________________
1481 // |__0_|_80_|_85_|_90_| (root)
1485 // ___________________
1486 // |__5_|_15_|_30_|_73_|
1490 // ___________________
1491 // |_33_|_58_|_63_|_68_| lca for the range [41, 65]
1492 // | |\___|___/| | iterator at traversals[2]
1497 let mut is_leaf = root.is_leaf();
1498 let mut lca = root.$as_slices_internal();
1500 let slice = lca.slice_from(min_key).slice_to(max_key);
1501 if let [ref $($mutability)* edge] = slice.edges {
1502 // Follow the only edge that leads the node that covers the range.
1503 is_leaf = edge.is_leaf();
1504 lca = edge.$as_slices_internal();
1506 let mut iter = slice.$iter();
1511 // Only change the state of nodes with edges.
1512 leftmost = iter.next_edge_item();
1513 rightmost = iter.next_edge_item_back();
1515 traversals.push_back(iter);
1521 // Keep narrowing the range by going down.
1522 // ___________________
1523 // |_38_|_43_|_48_|_53_|
1524 // | |____|____|____/ iterator at traversals[1]
1527 // ___________________
1528 // |_39_|_40_|_41_|_42_| (leaf, the last leftmost)
1529 // \_________| iterator at traversals[0]
1531 Included(key) | Excluded(key) =>
1532 while let Some(left) = leftmost {
1533 let is_leaf = left.is_leaf();
1534 let mut iter = left.$as_slices_internal().slice_from(key).$iter();
1535 leftmost = if is_leaf {
1538 // Only change the state of nodes with edges.
1539 iter.next_edge_item()
1541 traversals.push_back(iter);
1545 // If the leftmost iterator starts with an element, then it was an exact match.
1546 if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) {
1547 // Drop this excluded element. `next_kv_item` has no effect when
1548 // the next item is an edge.
1549 leftmost_iter.next_kv_item();
1552 // The code for the right side is similar.
1554 Included(key) | Excluded(key) =>
1555 while let Some(right) = rightmost {
1556 let is_leaf = right.is_leaf();
1557 let mut iter = right.$as_slices_internal().slice_to(key).$iter();
1558 rightmost = if is_leaf {
1561 iter.next_edge_item_back()
1563 traversals.push_front(iter);
1567 if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) {
1568 rightmost_iter.next_kv_item_back();
1573 traversals: traversals,
1574 size: usize::MAX, // unused
1581 impl<K: Ord, V> BTreeMap<K, V> {
1582 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
1583 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1584 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1585 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1590 /// #![feature(btree_range, collections_bound)]
1592 /// use std::collections::BTreeMap;
1593 /// use std::collections::Bound::{Included, Unbounded};
1595 /// let mut map = BTreeMap::new();
1596 /// map.insert(3, "a");
1597 /// map.insert(5, "b");
1598 /// map.insert(8, "c");
1599 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
1600 /// println!("{}: {}", key, value);
1602 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
1604 #[unstable(feature = "btree_range",
1605 reason = "matches collection reform specification, waiting for dust to settle",
1607 pub fn range<Min: ?Sized + Ord = K, Max: ?Sized + Ord = K>(&self,
1611 where K: Borrow<Min> + Borrow<Max>
1613 range_impl!(&self.root,
1623 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
1624 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1625 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1626 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1631 /// #![feature(btree_range, collections_bound)]
1633 /// use std::collections::BTreeMap;
1634 /// use std::collections::Bound::{Included, Excluded};
1636 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
1637 /// .map(|&s| (s, 0))
1639 /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
1640 /// *balance += 100;
1642 /// for (name, balance) in &map {
1643 /// println!("{} => {}", name, balance);
1646 #[unstable(feature = "btree_range",
1647 reason = "matches collection reform specification, waiting for dust to settle",
1649 pub fn range_mut<Min: ?Sized + Ord = K, Max: ?Sized + Ord = K>(&mut self,
1653 where K: Borrow<Min> + Borrow<Max>
1655 range_impl!(&mut self.root,
1658 as_slices_internal_mut,
1665 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1670 /// use std::collections::BTreeMap;
1672 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1674 /// // count the number of occurrences of letters in the vec
1675 /// for x in vec!["a","b","a","c","a","b"] {
1676 /// *count.entry(x).or_insert(0) += 1;
1679 /// assert_eq!(count["a"], 3);
1681 #[stable(feature = "rust1", since = "1.0.0")]
1682 pub fn entry(&mut self, mut key: K) -> Entry<K, V> {
1683 // same basic logic of `swap` and `pop`, blended together
1684 let mut stack = stack::PartialSearchStack::new(self);
1686 let result = stack.with(move |pusher, node| {
1687 match Node::search(node, &key) {
1690 Finished(Occupied(OccupiedEntry { stack: pusher.seal(handle) }))
1693 match handle.force() {
1694 Leaf(leaf_handle) => {
1695 Finished(Vacant(VacantEntry {
1696 stack: pusher.seal(leaf_handle),
1700 Internal(internal_handle) => {
1701 Continue((pusher.push(internal_handle), key))
1708 Finished(finished) => return finished,
1709 Continue((new_stack, renewed_key)) => {
1718 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
1719 where K: Borrow<Q> + Ord,
1724 fn get(&self, key: &Q) -> Option<&K> {
1725 let mut cur_node = &self.root;
1727 match Node::search(cur_node, key) {
1728 Found(handle) => return Some(handle.into_kv().0),
1730 match handle.force() {
1731 Leaf(_) => return None,
1732 Internal(internal_handle) => {
1733 cur_node = internal_handle.into_edge();
1742 fn take(&mut self, key: &Q) -> Option<K> {
1743 // See `remove` for an explanation of this.
1745 let mut stack = stack::PartialSearchStack::new(self);
1747 let result = stack.with(move |pusher, node| {
1748 match Node::search(node, key) {
1750 // Perfect match. Terminate the stack here, and remove the entry
1751 Finished(Some(pusher.seal(handle).remove()))
1754 // We need to keep searching, try to go down the next edge
1755 match handle.force() {
1756 // We're at a leaf; the key isn't in here
1757 Leaf(_) => Finished(None),
1758 Internal(internal_handle) => Continue(pusher.push(internal_handle)),
1764 Finished(ret) => return ret.map(|(k, _)| k),
1765 Continue(new_stack) => stack = new_stack,
1770 fn replace(&mut self, mut key: K) -> Option<K> {
1771 // See `insert` for an explanation of this.
1773 let mut stack = stack::PartialSearchStack::new(self);
1776 let result = stack.with(move |pusher, node| {
1777 match Node::search::<K, _>(node, &key) {
1778 Found(mut handle) => {
1779 mem::swap(handle.key_mut(), &mut key);
1783 match handle.force() {
1784 Leaf(leaf_handle) => {
1785 pusher.seal(leaf_handle).insert(key, ());
1788 Internal(internal_handle) => {
1789 Continue((pusher.push(internal_handle), key, ()))
1796 Finished(ret) => return ret,
1797 Continue((new_stack, renewed_key, _)) => {