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/).
18 pub use self::Entry::*;
22 use core::borrow::BorrowFrom;
23 use core::cmp::Ordering;
24 use core::default::Default;
26 use core::hash::{Hash, Hasher};
27 use core::iter::{Map, FromIterator, IntoIterator};
28 use core::ops::{Index, IndexMut};
29 use core::{iter, fmt, mem};
30 use Bound::{self, Included, Excluded, Unbounded};
32 use ring_buf::RingBuf;
34 use self::Continuation::{Continue, Finished};
36 use super::node::ForceResult::{Leaf, Internal};
37 use super::node::TraversalItem::{self, Elem, Edge};
38 use super::node::{Traversal, MutTraversal, MoveTraversal};
39 use super::node::{self, Node, Found, GoDown};
41 /// A map based on a B-Tree.
43 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
44 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
45 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
46 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
47 /// is done is *very* inefficient for modern computer architectures. In particular, every element
48 /// is stored in its own individually heap-allocated node. This means that every single insertion
49 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
50 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
53 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
54 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
55 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
56 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
57 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
58 /// the node using binary search. As a compromise, one could also perform a linear search
59 /// that initially only checks every i<sup>th</sup> element for some choice of i.
61 /// Currently, our implementation simply performs naive linear search. This provides excellent
62 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
63 /// would like to further explore choosing the optimal search strategy based on the choice of B,
64 /// and possibly other factors. Using linear search, searching for a random element is expected
65 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
66 /// however, performance is excellent. `BTreeMap` is able to readily outperform `TreeMap` under
67 /// many workloads, and is competitive where it doesn't. BTreeMap also generally *scales* better
68 /// than TreeMap, making it more appropriate for large datasets.
70 /// However, `TreeMap` may still be more appropriate to use in many contexts. If elements are very
71 /// large or expensive to compare, `TreeMap` may be more appropriate. It won't allocate any
72 /// more space than is needed, and will perform the minimal number of comparisons necessary.
73 /// `TreeMap` also provides much better performance stability guarantees. Generally, very few
74 /// changes need to be made to update a BST, and two updates are expected to take about the same
75 /// amount of time on roughly equal sized BSTs. However a B-Tree's performance is much more
76 /// amortized. If a node is overfull, it must be split into two nodes. If a node is underfull, it
77 /// may be merged with another. Both of these operations are relatively expensive to perform, and
78 /// it's possible to force one to occur at every single level of the tree in a single insertion or
79 /// deletion. In fact, a malicious or otherwise unlucky sequence of insertions and deletions can
80 /// force this degenerate behaviour to occur on every operation. While the total amount of work
81 /// done on each operation isn't *catastrophic*, and *is* still bounded by O(B log<sub>B</sub>n),
82 /// it is certainly much slower when it does.
84 #[stable(feature = "rust1", since = "1.0.0")]
85 pub struct BTreeMap<K, V> {
92 /// An abstract base over-which all other BTree iterators are built.
94 traversals: RingBuf<T>,
98 /// An iterator over a BTreeMap's entries.
99 #[stable(feature = "rust1", since = "1.0.0")]
100 pub struct Iter<'a, K: 'a, V: 'a> {
101 inner: AbsIter<Traversal<'a, K, V>>
104 /// A mutable iterator over a BTreeMap's entries.
105 #[stable(feature = "rust1", since = "1.0.0")]
106 pub struct IterMut<'a, K: 'a, V: 'a> {
107 inner: AbsIter<MutTraversal<'a, K, V>>
110 /// An owning iterator over a BTreeMap's entries.
111 #[stable(feature = "rust1", since = "1.0.0")]
112 pub struct IntoIter<K, V> {
113 inner: AbsIter<MoveTraversal<K, V>>
116 /// An iterator over a BTreeMap's keys.
117 #[stable(feature = "rust1", since = "1.0.0")]
118 pub struct Keys<'a, K: 'a, V: 'a> {
119 inner: Map<(&'a K, &'a V), &'a K, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
122 /// An iterator over a BTreeMap's values.
123 #[stable(feature = "rust1", since = "1.0.0")]
124 pub struct Values<'a, K: 'a, V: 'a> {
125 inner: Map<(&'a K, &'a V), &'a V, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
128 /// An iterator over a sub-range of BTreeMap's entries.
129 pub struct Range<'a, K: 'a, V: 'a> {
130 inner: AbsIter<Traversal<'a, K, V>>
133 /// A mutable iterator over a sub-range of BTreeMap's entries.
134 pub struct RangeMut<'a, K: 'a, V: 'a> {
135 inner: AbsIter<MutTraversal<'a, K, V>>
138 /// A view into a single entry in a map, which may either be vacant or occupied.
139 #[unstable(feature = "collections",
140 reason = "precise API still under development")]
141 pub enum Entry<'a, K:'a, V:'a> {
143 Vacant(VacantEntry<'a, K, V>),
144 /// An occupied Entry
145 Occupied(OccupiedEntry<'a, K, V>),
149 #[unstable(feature = "collections",
150 reason = "precise API still under development")]
151 pub struct VacantEntry<'a, K:'a, V:'a> {
153 stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>,
156 /// An occupied Entry.
157 #[unstable(feature = "collections",
158 reason = "precise API still under development")]
159 pub struct OccupiedEntry<'a, K:'a, V:'a> {
160 stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>,
163 impl<K: Ord, V> BTreeMap<K, V> {
164 /// Makes a new empty BTreeMap with a reasonable choice for B.
165 #[stable(feature = "rust1", since = "1.0.0")]
166 pub fn new() -> BTreeMap<K, V> {
167 //FIXME(Gankro): Tune this as a function of size_of<K/V>?
171 /// Makes a new empty BTreeMap with the given B.
173 /// B cannot be less than 2.
174 pub fn with_b(b: uint) -> BTreeMap<K, V> {
175 assert!(b > 1, "B must be greater than 1");
179 root: Node::make_leaf_root(b),
184 /// Clears the map, removing all values.
189 /// use std::collections::BTreeMap;
191 /// let mut a = BTreeMap::new();
192 /// a.insert(1u, "a");
194 /// assert!(a.is_empty());
196 #[stable(feature = "rust1", since = "1.0.0")]
197 pub fn clear(&mut self) {
199 // avoid recursive destructors by manually traversing the tree
200 for _ in mem::replace(self, BTreeMap::with_b(b)).into_iter() {};
203 // Searching in a B-Tree is pretty straightforward.
205 // Start at the root. Try to find the key in the current node. If we find it, return it.
206 // If it's not in there, follow the edge *before* the smallest key larger than
207 // the search key. If no such key exists (they're *all* smaller), then just take the last
208 // edge in the node. If we're in a leaf and we don't find our key, then it's not
211 /// Returns a reference to the value corresponding to the key.
213 /// The key may be any borrowed form of the map's key type, but the ordering
214 /// on the borrowed form *must* match the ordering on the key type.
219 /// use std::collections::BTreeMap;
221 /// let mut map = BTreeMap::new();
222 /// map.insert(1u, "a");
223 /// assert_eq!(map.get(&1), Some(&"a"));
224 /// assert_eq!(map.get(&2), None);
226 #[stable(feature = "rust1", since = "1.0.0")]
227 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: BorrowFrom<K> + Ord {
228 let mut cur_node = &self.root;
230 match Node::search(cur_node, key) {
231 Found(handle) => return Some(handle.into_kv().1),
232 GoDown(handle) => match handle.force() {
233 Leaf(_) => return None,
234 Internal(internal_handle) => {
235 cur_node = internal_handle.into_edge();
243 /// Returns true if the map contains a value for the specified key.
245 /// The key may be any borrowed form of the map's key type, but the ordering
246 /// on the borrowed form *must* match the ordering on the key type.
251 /// use std::collections::BTreeMap;
253 /// let mut map = BTreeMap::new();
254 /// map.insert(1u, "a");
255 /// assert_eq!(map.contains_key(&1), true);
256 /// assert_eq!(map.contains_key(&2), false);
258 #[stable(feature = "rust1", since = "1.0.0")]
259 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: BorrowFrom<K> + Ord {
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(1u, "a");
275 /// match map.get_mut(&1) {
276 /// Some(x) => *x = "b",
279 /// assert_eq!(map[1], "b");
281 // See `get` for implementation notes, this is basically a copy-paste with mut's added
282 #[stable(feature = "rust1", since = "1.0.0")]
283 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: BorrowFrom<K> + Ord {
284 // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
285 let mut temp_node = &mut self.root;
287 let cur_node = temp_node;
288 match Node::search(cur_node, key) {
289 Found(handle) => return Some(handle.into_kv_mut().1),
290 GoDown(handle) => match handle.force() {
291 Leaf(_) => return None,
292 Internal(internal_handle) => {
293 temp_node = internal_handle.into_edge_mut();
301 // Insertion in a B-Tree is a bit complicated.
303 // First we do the same kind of search described in `find`. But we need to maintain a stack of
304 // all the nodes/edges in our search path. If we find a match for the key we're trying to
305 // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
306 // we attempt to insert our key-value pair at the same location we would want to follow another
309 // If the node has room, then this is done in the obvious way by shifting elements. However,
310 // if the node itself is full, we split node into two, and give its median key-value
311 // pair to its parent to insert the new node with. Of course, the parent may also be
312 // full, and insertion can propagate until we reach the root. If we reach the root, and
313 // it is *also* full, then we split the root and place the two nodes under a newly made root.
315 // Note that we subtly deviate from Open Data Structures in our implementation of split.
316 // ODS describes inserting into the node *regardless* of its capacity, and then
317 // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
318 // Instead, we split beforehand, and then insert the key-value pair into the appropriate
319 // result node. This has two consequences:
321 // 1) While ODS produces a left node of size B-1, and a right node of size B,
322 // we may potentially reverse this. However, this shouldn't effect the analysis.
324 // 2) While ODS may potentially return the pair we *just* inserted after
325 // the split, we will never do this. Again, this shouldn't effect the analysis.
327 /// Inserts a key-value pair from the map. If the key already had a value
328 /// present in the map, that value is returned. Otherwise, `None` is returned.
333 /// use std::collections::BTreeMap;
335 /// let mut map = BTreeMap::new();
336 /// assert_eq!(map.insert(37u, "a"), None);
337 /// assert_eq!(map.is_empty(), false);
339 /// map.insert(37, "b");
340 /// assert_eq!(map.insert(37, "c"), Some("b"));
341 /// assert_eq!(map[37], "c");
343 #[stable(feature = "rust1", since = "1.0.0")]
344 pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
345 // This is a stack of rawptrs to nodes paired with indices, respectively
346 // representing the nodes and edges of our search path. We have to store rawptrs
347 // because as far as Rust is concerned, we can mutate aliased data with such a
348 // stack. It is of course correct, but what it doesn't know is that we will only
349 // be popping and using these ptrs one at a time in child-to-parent order. The alternative
350 // to doing this is to take the Nodes from their parents. This actually makes
351 // borrowck *really* happy and everything is pretty smooth. However, this creates
352 // *tons* of pointless writes, and requires us to always walk all the way back to
353 // the root after an insertion, even if we only needed to change a leaf. Therefore,
354 // we accept this potential unsafety and complexity in the name of performance.
356 // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
357 // by the stack module. All it can do is immutably read nodes, and ask the search stack
358 // to proceed down some edge by index. This makes the search logic we'll be reusing in a
359 // few different methods much neater, and of course drastically improves safety.
360 let mut stack = stack::PartialSearchStack::new(self);
363 let result = stack.with(move |pusher, node| {
364 // Same basic logic as found in `find`, but with PartialSearchStack mediating the
365 // actual nodes for us
366 return match Node::search(node, &key) {
367 Found(mut handle) => {
368 // Perfect match, swap the values and return the old one
369 mem::swap(handle.val_mut(), &mut value);
370 Finished(Some(value))
373 // We need to keep searching, try to get the search stack
374 // to go down further
375 match handle.force() {
376 Leaf(leaf_handle) => {
377 // We've reached a leaf, perform the insertion here
378 pusher.seal(leaf_handle).insert(key, value);
381 Internal(internal_handle) => {
382 // We've found the subtree to insert this key/value pair in,
384 Continue((pusher.push(internal_handle), key, value))
391 Finished(ret) => { return ret; },
392 Continue((new_stack, renewed_key, renewed_val)) => {
401 // Deletion is the most complicated operation for a B-Tree.
403 // First we do the same kind of search described in
404 // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
405 // If we don't find the key, then we just return `None` and do nothing. If we do find the
406 // key, we perform two operations: remove the item, and then possibly handle underflow.
408 // # removing the item
409 // If the node is a leaf, we just remove the item, and shift
410 // any items after it back to fill the hole.
412 // If the node is an internal node, we *swap* the item with the smallest item in
413 // in its right subtree (which must reside in a leaf), and then revert to the leaf
416 // # handling underflow
417 // After removing an item, there may be too few items in the node. We want nodes
418 // to be mostly full for efficiency, although we make an exception for the root, which
419 // may have as few as one item. If this is the case, we may first try to steal
420 // an item from our left or right neighbour.
422 // To steal from the left (right) neighbour,
423 // we take the largest (smallest) item and child from it. We then swap the taken item
424 // with the item in their mutual parent that separates them, and then insert the
425 // parent's item and the taken child into the first (last) index of the underflowed node.
427 // However, stealing has the possibility of underflowing our neighbour. If this is the
428 // case, we instead *merge* with our neighbour. This of course reduces the number of
429 // children in the parent. Therefore, we also steal the item that separates the now
430 // merged nodes, and insert it into the merged node.
432 // Merging may cause the parent to underflow. If this is the case, then we must repeat
433 // the underflow handling process on the parent. If merging merges the last two children
434 // of the root, then we replace the root with the merged node.
436 /// Removes a key from the map, returning the value at the key if the key
437 /// was previously in the map.
439 /// The key may be any borrowed form of the map's key type, but the ordering
440 /// on the borrowed form *must* match the ordering on the key type.
445 /// use std::collections::BTreeMap;
447 /// let mut map = BTreeMap::new();
448 /// map.insert(1u, "a");
449 /// assert_eq!(map.remove(&1), Some("a"));
450 /// assert_eq!(map.remove(&1), None);
452 #[stable(feature = "rust1", since = "1.0.0")]
453 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: BorrowFrom<K> + Ord {
454 // See `swap` for a more thorough description of the stuff going on in here
455 let mut stack = stack::PartialSearchStack::new(self);
457 let result = stack.with(move |pusher, node| {
458 return match Node::search(node, key) {
460 // Perfect match. Terminate the stack here, and remove the entry
461 Finished(Some(pusher.seal(handle).remove()))
464 // We need to keep searching, try to go down the next edge
465 match handle.force() {
466 // We're at a leaf; the key isn't in here
467 Leaf(_) => Finished(None),
468 Internal(internal_handle) => Continue(pusher.push(internal_handle))
474 Finished(ret) => return ret,
475 Continue(new_stack) => stack = new_stack
481 impl<K, V> IntoIterator for BTreeMap<K, V> {
482 type Iter = IntoIter<K, V>;
484 fn into_iter(self) -> IntoIter<K, V> {
489 impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
490 type Iter = Iter<'a, K, V>;
492 fn into_iter(self) -> Iter<'a, K, V> {
497 impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
498 type Iter = IterMut<'a, K, V>;
500 fn into_iter(mut self) -> IterMut<'a, K, V> {
505 /// A helper enum useful for deciding whether to continue a loop since we can't
506 /// return from a closure
507 enum Continuation<A, B> {
512 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
513 /// to nodes. By using this module much better safety guarantees can be made, and more search
514 /// boilerplate gets cut out.
516 use core::prelude::*;
519 use core::ops::{Deref, DerefMut};
521 use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
522 use super::super::node::handle;
525 /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
526 /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
527 /// with the exact requested lifetime can be used. This is in contrast to normal references,
528 /// where `&'static` can be used in any function expecting any lifetime reference.
529 pub struct IdRef<'id, T: 'id> {
531 marker: marker::InvariantLifetime<'id>
534 impl<'id, T> Deref for IdRef<'id, T> {
537 fn deref(&self) -> &T {
542 impl<'id, T> DerefMut for IdRef<'id, T> {
543 fn deref_mut(&mut self) -> &mut T {
548 type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
549 type Stack<K, V> = Vec<StackItem<K, V>>;
551 /// A `PartialSearchStack` handles the construction of a search stack.
552 pub struct PartialSearchStack<'a, K:'a, V:'a> {
553 map: &'a mut BTreeMap<K, V>,
555 next: *mut Node<K, V>,
558 /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
559 /// methods depending on the type of what the path points to for removing an element, inserting
560 /// a new element, and manipulating to element at the top of the stack.
561 pub struct SearchStack<'a, K:'a, V:'a, Type, NodeType> {
562 map: &'a mut BTreeMap<K, V>,
564 top: node::Handle<*mut Node<K, V>, Type, NodeType>,
567 /// A `PartialSearchStack` that doesn't hold a a reference to the next node, and is just
568 /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
569 /// for more details.
570 pub struct Pusher<'id, 'a, K:'a, V:'a> {
571 map: &'a mut BTreeMap<K, V>,
573 marker: marker::InvariantLifetime<'id>
576 impl<'a, K, V> PartialSearchStack<'a, K, V> {
577 /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
578 /// root of the tree.
579 pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
580 let depth = map.depth;
583 next: &mut map.root as *mut _,
585 stack: Vec::with_capacity(depth),
589 /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
590 /// to interact with, search, and finally push the `Node` onto the stack. The passed in
591 /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
592 /// ensures that only `Handle`s from the correct `Node` can be pushed.
594 /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
595 /// handles with the same `'id`. The closure could only get references with that lifetime
596 /// through its arguments or through some other `IdRef` that it has lying around. However,
597 /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
598 /// parameter, it would need to have precisely the correct lifetime, which would mean that
599 /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
600 /// specific lifetime instead of the one that `with` chooses to give it.
602 /// See also Haskell's `ST` monad, which uses a similar trick.
603 pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
604 IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
605 let pusher = Pusher {
608 marker: marker::InvariantLifetime
611 inner: unsafe { &mut *self.next },
612 marker: marker::InvariantLifetime
615 closure(pusher, node)
619 impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
620 /// Pushes the requested child of the stack's current top on top of the stack. If the child
621 /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
623 pub fn push(mut self, mut edge: node::Handle<IdRef<'id, Node<K, V>>,
626 -> PartialSearchStack<'a, K, V> {
627 self.stack.push(edge.as_raw());
631 next: edge.edge_mut() as *mut _,
635 /// Converts the PartialSearchStack into a SearchStack.
636 pub fn seal<Type, NodeType>
637 (self, mut handle: node::Handle<IdRef<'id, Node<K, V>>, Type, NodeType>)
638 -> SearchStack<'a, K, V, Type, NodeType> {
642 top: handle.as_raw(),
647 impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
648 /// Gets a reference to the value the stack points to.
649 pub fn peek(&self) -> &V {
650 unsafe { self.top.from_raw().into_kv().1 }
653 /// Gets a mutable reference to the value the stack points to.
654 pub fn peek_mut(&mut self) -> &mut V {
655 unsafe { self.top.from_raw_mut().into_kv_mut().1 }
658 /// Converts the stack into a mutable reference to the value it points to, with a lifetime
659 /// tied to the original tree.
660 pub fn into_top(mut self) -> &'a mut V {
662 mem::copy_mut_lifetime(
664 self.top.from_raw_mut().val_mut()
670 impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
671 /// Removes the key and value in the top element of the stack, then handles underflows as
672 /// described in BTree's pop function.
673 fn remove_leaf(mut self) -> V {
674 self.map.length -= 1;
676 // Remove the key-value pair from the leaf that this search stack points to.
677 // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
678 // to avoid ownership issues.
679 let (value, mut underflow) = unsafe {
680 let (_, value) = self.top.from_raw_mut().remove_as_leaf();
681 let underflow = self.top.from_raw().node().is_underfull();
686 match self.stack.pop() {
688 // We've reached the root, so no matter what, we're done. We manually
689 // access the root via the tree itself to avoid creating any dangling
691 if self.map.root.len() == 0 && !self.map.root.is_leaf() {
692 // We've emptied out the root, so make its only child the new root.
693 // If it's a leaf, we just let it become empty.
695 self.map.root.hoist_lone_child();
699 Some(mut handle) => {
701 // Underflow! Handle it!
703 handle.from_raw_mut().handle_underflow();
704 underflow = handle.from_raw().node().is_underfull();
716 impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
717 /// Removes the key and value in the top element of the stack, then handles underflows as
718 /// described in BTree's pop function.
719 pub fn remove(self) -> V {
720 // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
721 // in a BTree. Note that this may put the tree in an inconsistent state (further
722 // described in into_leaf's comments), but this is immediately fixed by the
723 // removing the value we want to remove
724 self.into_leaf().remove_leaf()
727 /// Subroutine for removal. Takes a search stack for a key that might terminate at an
728 /// internal node, and mutates the tree and search stack to *make* it a search stack
729 /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
730 /// leaves the tree in an inconsistent state that must be repaired by the caller by
731 /// removing the entry in question. Specifically the key-value pair and its successor will
733 fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
735 let mut top_raw = self.top;
736 let mut top = top_raw.from_raw_mut();
738 let key_ptr = top.key_mut() as *mut _;
739 let val_ptr = top.val_mut() as *mut _;
741 // Try to go into the right subtree of the found key to find its successor
743 Leaf(mut leaf_handle) => {
744 // We're a proper leaf stack, nothing to do
748 top: leaf_handle.as_raw()
751 Internal(mut internal_handle) => {
752 let mut right_handle = internal_handle.right_edge();
754 //We're not a proper leaf stack, let's get to work.
755 self.stack.push(right_handle.as_raw());
757 let mut temp_node = right_handle.edge_mut();
759 // Walk into the smallest subtree of this node
760 let node = temp_node;
762 match node.kv_handle(0).force() {
763 Leaf(mut handle) => {
764 // This node is a leaf, do the swap and return
765 mem::swap(handle.key_mut(), &mut *key_ptr);
766 mem::swap(handle.val_mut(), &mut *val_ptr);
773 Internal(kv_handle) => {
774 // This node is internal, go deeper
775 let mut handle = kv_handle.into_left_edge();
776 self.stack.push(handle.as_raw());
777 temp_node = handle.into_edge_mut();
787 impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
788 /// Inserts the key and value into the top element in the stack, and if that node has to
789 /// split recursively inserts the split contents into the next element stack until
792 /// Assumes that the stack represents a search path from the root to a leaf.
794 /// An &mut V is returned to the inserted value, for callers that want a reference to this.
795 pub fn insert(mut self, key: K, val: V) -> &'a mut V {
797 self.map.length += 1;
799 // Insert the key and value into the leaf at the top of the stack
800 let (mut insertion, inserted_ptr) = self.top.from_raw_mut()
801 .insert_as_leaf(key, val);
806 // The last insertion went off without a hitch, no splits! We can stop
808 return &mut *inserted_ptr;
810 Split(key, val, right) => match self.stack.pop() {
811 // The last insertion triggered a split, so get the next element on the
812 // stack to recursively insert the split node into.
814 // The stack was empty; we've split the root, and need to make a
815 // a new one. This is done in-place because we can't move the
816 // root out of a reference to the tree.
817 Node::make_internal_root(&mut self.map.root, self.map.b,
821 return &mut *inserted_ptr;
823 Some(mut handle) => {
824 // The stack wasn't empty, do the insertion and recurse
825 insertion = handle.from_raw_mut()
826 .insert_as_internal(key, val, right);
837 #[stable(feature = "rust1", since = "1.0.0")]
838 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
839 fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
840 let mut map = BTreeMap::new();
846 #[stable(feature = "rust1", since = "1.0.0")]
847 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
849 fn extend<T: Iterator<Item=(K, V)>>(&mut self, mut iter: T) {
856 #[stable(feature = "rust1", since = "1.0.0")]
857 impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
858 fn hash(&self, state: &mut S) {
859 for elt in self.iter() {
865 #[stable(feature = "rust1", since = "1.0.0")]
866 impl<K: Ord, V> Default for BTreeMap<K, V> {
867 #[stable(feature = "rust1", since = "1.0.0")]
868 fn default() -> BTreeMap<K, V> {
873 #[stable(feature = "rust1", since = "1.0.0")]
874 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
875 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
876 self.len() == other.len() &&
877 self.iter().zip(other.iter()).all(|(a, b)| a == b)
881 #[stable(feature = "rust1", since = "1.0.0")]
882 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
884 #[stable(feature = "rust1", since = "1.0.0")]
885 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
887 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
888 iter::order::partial_cmp(self.iter(), other.iter())
892 #[stable(feature = "rust1", since = "1.0.0")]
893 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
895 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
896 iter::order::cmp(self.iter(), other.iter())
900 #[stable(feature = "rust1", since = "1.0.0")]
901 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
902 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
903 try!(write!(f, "BTreeMap {{"));
905 for (i, (k, v)) in self.iter().enumerate() {
906 if i != 0 { try!(write!(f, ", ")); }
907 try!(write!(f, "{:?}: {:?}", *k, *v));
914 #[stable(feature = "rust1", since = "1.0.0")]
915 impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V>
916 where Q: BorrowFrom<K> + Ord
920 fn index(&self, key: &Q) -> &V {
921 self.get(key).expect("no entry found for key")
925 #[stable(feature = "rust1", since = "1.0.0")]
926 impl<K: Ord, Q: ?Sized, V> IndexMut<Q> for BTreeMap<K, V>
927 where Q: BorrowFrom<K> + Ord
931 fn index_mut(&mut self, key: &Q) -> &mut V {
932 self.get_mut(key).expect("no entry found for key")
936 /// Genericises over how to get the correct type of iterator from the correct type
937 /// of Node ownership.
939 fn traverse(node: N) -> Self;
942 impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
943 fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
948 impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
949 fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
954 impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
955 fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
960 /// Represents an operation to perform inside the following iterator methods.
961 /// This is necessary to use in `next` because we want to modify `self.traversals` inside
962 /// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
963 /// what we want to do, and do it after the match.
968 impl<K, V, E, T> Iterator for AbsIter<T> where
969 T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
973 // Our iterator represents a queue of all ancestors of elements we have
974 // yet to yield, from smallest to largest. Note that the design of these
975 // iterators permits an *arbitrary* initial pair of min and max, making
976 // these arbitrary sub-range iterators.
977 fn next(&mut self) -> Option<(K, V)> {
979 // We want the smallest element, so try to get the back of the queue
980 let op = match self.traversals.back_mut() {
982 // The queue wasn't empty, so continue along the node in its head
983 Some(iter) => match iter.next() {
984 // The head is empty, so Pop it off and continue the process
986 // The head yielded an edge, so make that the new head
987 Some(Edge(next)) => Push(Traverse::traverse(next)),
988 // The head yielded an entry, so yield that
996 // Handle any operation as necessary, without a conflicting borrow of the queue
998 Push(item) => { self.traversals.push_back(item); },
999 Pop => { self.traversals.pop_back(); },
1004 fn size_hint(&self) -> (uint, Option<uint>) {
1005 (self.size, Some(self.size))
1009 impl<K, V, E, T> DoubleEndedIterator for AbsIter<T> where
1010 T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
1012 // next_back is totally symmetric to next
1014 fn next_back(&mut self) -> Option<(K, V)> {
1016 let op = match self.traversals.front_mut() {
1017 None => return None,
1018 Some(iter) => match iter.next_back() {
1020 Some(Edge(next)) => Push(Traverse::traverse(next)),
1029 Push(item) => { self.traversals.push_front(item); },
1030 Pop => { self.traversals.pop_front(); }
1036 #[stable(feature = "rust1", since = "1.0.0")]
1037 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1038 type Item = (&'a K, &'a V);
1040 fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1041 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1043 #[stable(feature = "rust1", since = "1.0.0")]
1044 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1045 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
1047 #[stable(feature = "rust1", since = "1.0.0")]
1048 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1050 #[stable(feature = "rust1", since = "1.0.0")]
1051 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1052 type Item = (&'a K, &'a mut V);
1054 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1055 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1057 #[stable(feature = "rust1", since = "1.0.0")]
1058 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1059 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
1061 #[stable(feature = "rust1", since = "1.0.0")]
1062 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1064 #[stable(feature = "rust1", since = "1.0.0")]
1065 impl<K, V> Iterator for IntoIter<K, V> {
1068 fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1069 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1071 #[stable(feature = "rust1", since = "1.0.0")]
1072 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1073 fn next_back(&mut self) -> Option<(K, V)> { self.inner.next_back() }
1075 #[stable(feature = "rust1", since = "1.0.0")]
1076 impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
1078 #[stable(feature = "rust1", since = "1.0.0")]
1079 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1082 fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1083 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1085 #[stable(feature = "rust1", since = "1.0.0")]
1086 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1087 fn next_back(&mut self) -> Option<(&'a K)> { self.inner.next_back() }
1089 #[stable(feature = "rust1", since = "1.0.0")]
1090 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
1093 #[stable(feature = "rust1", since = "1.0.0")]
1094 impl<'a, K, V> Iterator for Values<'a, K, V> {
1097 fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1098 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1100 #[stable(feature = "rust1", since = "1.0.0")]
1101 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1102 fn next_back(&mut self) -> Option<(&'a V)> { self.inner.next_back() }
1104 #[stable(feature = "rust1", since = "1.0.0")]
1105 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
1107 impl<'a, K, V> Iterator for Range<'a, K, V> {
1108 type Item = (&'a K, &'a V);
1110 fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1112 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1113 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
1116 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1117 type Item = (&'a K, &'a mut V);
1119 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1121 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1122 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
1125 impl<'a, K: Ord, V> Entry<'a, K, V> {
1126 #[unstable(feature = "collections",
1127 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1128 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1129 pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> {
1131 Occupied(entry) => Ok(entry.into_mut()),
1132 Vacant(entry) => Err(entry),
1137 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1138 /// Sets the value of the entry with the VacantEntry's key,
1139 /// and returns a mutable reference to it.
1140 #[unstable(feature = "collections",
1141 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1142 pub fn insert(self, value: V) -> &'a mut V {
1143 self.stack.insert(self.key, value)
1147 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1148 /// Gets a reference to the value in the entry.
1149 #[unstable(feature = "collections",
1150 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1151 pub fn get(&self) -> &V {
1155 /// Gets a mutable reference to the value in the entry.
1156 #[unstable(feature = "collections",
1157 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1158 pub fn get_mut(&mut self) -> &mut V {
1159 self.stack.peek_mut()
1162 /// Converts the entry into a mutable reference to its value.
1163 #[unstable(feature = "collections",
1164 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1165 pub fn into_mut(self) -> &'a mut V {
1166 self.stack.into_top()
1169 /// Sets the value of the entry with the OccupiedEntry's key,
1170 /// and returns the entry's old value.
1171 #[unstable(feature = "collections",
1172 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1173 pub fn insert(&mut self, mut value: V) -> V {
1174 mem::swap(self.stack.peek_mut(), &mut value);
1178 /// Takes the value of the entry out of the map, and returns it.
1179 #[unstable(feature = "collections",
1180 reason = "matches collection reform v2 specification, waiting for dust to settle")]
1181 pub fn remove(self) -> V {
1186 impl<K, V> BTreeMap<K, V> {
1187 /// Gets an iterator over the entries of the map.
1192 /// use std::collections::BTreeMap;
1194 /// let mut map = BTreeMap::new();
1195 /// map.insert(1u, "a");
1196 /// map.insert(2u, "b");
1197 /// map.insert(3u, "c");
1199 /// for (key, value) in map.iter() {
1200 /// println!("{}: {}", key, value);
1203 /// let (first_key, first_value) = map.iter().next().unwrap();
1204 /// assert_eq!((*first_key, *first_value), (1u, "a"));
1206 #[stable(feature = "rust1", since = "1.0.0")]
1207 pub fn iter(&self) -> Iter<K, V> {
1208 let len = self.len();
1209 // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
1210 let mut lca = RingBuf::new();
1211 lca.push_back(Traverse::traverse(&self.root));
1220 /// Gets a mutable iterator over the entries of the map.
1225 /// use std::collections::BTreeMap;
1227 /// let mut map = BTreeMap::new();
1228 /// map.insert("a", 1u);
1229 /// map.insert("b", 2u);
1230 /// map.insert("c", 3u);
1232 /// // add 10 to the value if the key isn't "a"
1233 /// for (key, value) in map.iter_mut() {
1234 /// if key != &"a" {
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1241 let len = self.len();
1242 let mut lca = RingBuf::new();
1243 lca.push_back(Traverse::traverse(&mut self.root));
1252 /// Gets an owning iterator over the entries of the map.
1257 /// use std::collections::BTreeMap;
1259 /// let mut map = BTreeMap::new();
1260 /// map.insert(1u, "a");
1261 /// map.insert(2u, "b");
1262 /// map.insert(3u, "c");
1264 /// for (key, value) in map.into_iter() {
1265 /// println!("{}: {}", key, value);
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 pub fn into_iter(self) -> IntoIter<K, V> {
1270 let len = self.len();
1271 let mut lca = RingBuf::new();
1272 lca.push_back(Traverse::traverse(self.root));
1281 /// Gets an iterator over the keys of the map.
1286 /// use std::collections::BTreeMap;
1288 /// let mut a = BTreeMap::new();
1289 /// a.insert(1u, "a");
1290 /// a.insert(2u, "b");
1292 /// let keys: Vec<uint> = a.keys().cloned().collect();
1293 /// assert_eq!(keys, vec![1u,2,]);
1295 #[stable(feature = "rust1", since = "1.0.0")]
1296 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1297 fn first<A, B>((a, _): (A, B)) -> A { a }
1298 let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
1300 Keys { inner: self.iter().map(first) }
1303 /// Gets an iterator over the values of the map.
1308 /// use std::collections::BTreeMap;
1310 /// let mut a = BTreeMap::new();
1311 /// a.insert(1u, "a");
1312 /// a.insert(2u, "b");
1314 /// let values: Vec<&str> = a.values().cloned().collect();
1315 /// assert_eq!(values, vec!["a","b"]);
1317 #[stable(feature = "rust1", since = "1.0.0")]
1318 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1319 fn second<A, B>((_, b): (A, B)) -> B { b }
1320 let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
1322 Values { inner: self.iter().map(second) }
1325 /// Return the number of elements in the map.
1330 /// use std::collections::BTreeMap;
1332 /// let mut a = BTreeMap::new();
1333 /// assert_eq!(a.len(), 0);
1334 /// a.insert(1u, "a");
1335 /// assert_eq!(a.len(), 1);
1337 #[stable(feature = "rust1", since = "1.0.0")]
1338 pub fn len(&self) -> uint { self.length }
1340 /// Return true if the map contains no elements.
1345 /// use std::collections::BTreeMap;
1347 /// let mut a = BTreeMap::new();
1348 /// assert!(a.is_empty());
1349 /// a.insert(1u, "a");
1350 /// assert!(!a.is_empty());
1352 #[stable(feature = "rust1", since = "1.0.0")]
1353 pub fn is_empty(&self) -> bool { self.len() == 0 }
1356 macro_rules! range_impl {
1357 ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident,
1358 $edges:ident, [$($mutability:ident)*]) => (
1360 // A deque that encodes two search paths containing (left-to-right):
1361 // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
1362 // and a series of truncated-from-the-right iterators.
1363 let mut traversals = RingBuf::new();
1364 let (root, min, max) = ($root, $min, $max);
1366 let mut leftmost = None;
1367 let mut rightmost = None;
1369 match (&min, &max) {
1370 (&Unbounded, &Unbounded) => {
1371 traversals.push_back(Traverse::traverse(root))
1373 (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => {
1374 rightmost = Some(root);
1376 (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => {
1377 leftmost = Some(root);
1379 (&Included(min_key), &Included(max_key))
1380 | (&Included(min_key), &Excluded(max_key))
1381 | (&Excluded(min_key), &Included(max_key))
1382 | (&Excluded(min_key), &Excluded(max_key)) => {
1383 // lca represents the Lowest Common Ancestor, above which we never
1384 // walk, since everything else is outside the range to iterate.
1385 // ___________________
1386 // |__0_|_80_|_85_|_90_| (root)
1390 // ___________________
1391 // |__5_|_15_|_30_|_73_|
1395 // ___________________
1396 // |_33_|_58_|_63_|_68_| lca for the range [41, 65]
1397 // | |\___|___/| | iterator at traversals[2]
1402 let mut is_leaf = root.is_leaf();
1403 let mut lca = root.$as_slices_internal();
1405 let slice = lca.slice_from(min_key).slice_to(max_key);
1406 if let [ref $($mutability)* edge] = slice.edges {
1407 // Follow the only edge that leads the node that covers the range.
1408 is_leaf = edge.is_leaf();
1409 lca = edge.$as_slices_internal();
1411 let mut iter = slice.$iter();
1416 // Only change the state of nodes with edges.
1417 leftmost = iter.next_edge_item();
1418 rightmost = iter.next_edge_item_back();
1420 traversals.push_back(iter);
1426 // Keep narrowing the range by going down.
1427 // ___________________
1428 // |_38_|_43_|_48_|_53_|
1429 // | |____|____|____/ iterator at traversals[1]
1432 // ___________________
1433 // |_39_|_40_|_41_|_42_| (leaf, the last leftmost)
1434 // \_________| iterator at traversals[0]
1436 Included(key) | Excluded(key) =>
1437 while let Some(left) = leftmost {
1438 let is_leaf = left.is_leaf();
1439 let mut iter = left.$as_slices_internal().slice_from(key).$iter();
1440 leftmost = if is_leaf {
1443 // Only change the state of nodes with edges.
1444 iter.next_edge_item()
1446 traversals.push_back(iter);
1450 // If the leftmost iterator starts with an element, then it was an exact match.
1451 if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) {
1452 // Drop this excluded element. `next_kv_item` has no effect when
1453 // the next item is an edge.
1454 leftmost_iter.next_kv_item();
1457 // The code for the right side is similar.
1459 Included(key) | Excluded(key) =>
1460 while let Some(right) = rightmost {
1461 let is_leaf = right.is_leaf();
1462 let mut iter = right.$as_slices_internal().slice_to(key).$iter();
1463 rightmost = if is_leaf {
1466 iter.next_edge_item_back()
1468 traversals.push_front(iter);
1472 if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) {
1473 rightmost_iter.next_kv_item_back();
1478 traversals: traversals,
1486 impl<K: Ord, V> BTreeMap<K, V> {
1487 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
1488 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1489 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1490 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1495 /// use std::collections::BTreeMap;
1496 /// use std::collections::Bound::{Included, Unbounded};
1498 /// let mut map = BTreeMap::new();
1499 /// map.insert(3u, "a");
1500 /// map.insert(5u, "b");
1501 /// map.insert(8u, "c");
1502 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
1503 /// println!("{}: {}", key, value);
1505 /// assert_eq!(Some((&5u, &"b")), map.range(Included(&4), Unbounded).next());
1507 #[unstable(feature = "collections",
1508 reason = "matches collection reform specification, waiting for dust to settle")]
1509 pub fn range<'a>(&'a self, min: Bound<&K>, max: Bound<&K>) -> Range<'a, K, V> {
1510 range_impl!(&self.root, min, max, as_slices_internal, iter, Range, edges, [])
1513 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
1514 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
1515 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
1516 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
1521 /// use std::collections::BTreeMap;
1522 /// use std::collections::Bound::{Included, Excluded};
1524 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
1525 /// .map(|&s| (s, 0))
1527 /// for (_, balance) in map.range_mut(Included(&"B"), Excluded(&"Cheryl")) {
1528 /// *balance += 100;
1530 /// for (name, balance) in map.iter() {
1531 /// println!("{} => {}", name, balance);
1534 #[unstable(feature = "collections",
1535 reason = "matches collection reform specification, waiting for dust to settle")]
1536 pub fn range_mut<'a>(&'a mut self, min: Bound<&K>, max: Bound<&K>) -> RangeMut<'a, K, V> {
1537 range_impl!(&mut self.root, min, max, as_slices_internal_mut, iter_mut, RangeMut,
1541 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1546 /// use std::collections::BTreeMap;
1547 /// use std::collections::btree_map::Entry;
1549 /// let mut count: BTreeMap<&str, uint> = BTreeMap::new();
1551 /// // count the number of occurrences of letters in the vec
1552 /// for x in vec!["a","b","a","c","a","b"].iter() {
1553 /// match count.entry(*x) {
1554 /// Entry::Vacant(view) => {
1557 /// Entry::Occupied(mut view) => {
1558 /// let v = view.get_mut();
1564 /// assert_eq!(count["a"], 3u);
1566 /// The key must have the same ordering before or after `.to_owned()` is called.
1567 #[unstable(feature = "collections",
1568 reason = "precise API still under development")]
1569 pub fn entry<'a>(&'a mut self, mut key: K) -> Entry<'a, K, V> {
1570 // same basic logic of `swap` and `pop`, blended together
1571 let mut stack = stack::PartialSearchStack::new(self);
1573 let result = stack.with(move |pusher, node| {
1574 return match Node::search(node, &key) {
1577 Finished(Occupied(OccupiedEntry {
1578 stack: pusher.seal(handle)
1582 match handle.force() {
1583 Leaf(leaf_handle) => {
1584 Finished(Vacant(VacantEntry {
1585 stack: pusher.seal(leaf_handle),
1589 Internal(internal_handle) => {
1591 pusher.push(internal_handle),
1600 Finished(finished) => return finished,
1601 Continue((new_stack, renewed_key)) => {
1617 use std::iter::range_inclusive;
1619 use super::{BTreeMap, Occupied, Vacant};
1620 use Bound::{self, Included, Excluded, Unbounded};
1623 fn test_basic_large() {
1624 let mut map = BTreeMap::new();
1626 assert_eq!(map.len(), 0);
1629 assert_eq!(map.insert(i, 10*i), None);
1630 assert_eq!(map.len(), i + 1);
1634 assert_eq!(map.get(&i).unwrap(), &(i*10));
1637 for i in size..size*2 {
1638 assert_eq!(map.get(&i), None);
1642 assert_eq!(map.insert(i, 100*i), Some(10*i));
1643 assert_eq!(map.len(), size);
1647 assert_eq!(map.get(&i).unwrap(), &(i*100));
1650 for i in 0..size/2 {
1651 assert_eq!(map.remove(&(i*2)), Some(i*200));
1652 assert_eq!(map.len(), size - i - 1);
1655 for i in 0..size/2 {
1656 assert_eq!(map.get(&(2*i)), None);
1657 assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
1660 for i in 0..size/2 {
1661 assert_eq!(map.remove(&(2*i)), None);
1662 assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
1663 assert_eq!(map.len(), size/2 - i - 1);
1668 fn test_basic_small() {
1669 let mut map = BTreeMap::new();
1670 assert_eq!(map.remove(&1), None);
1671 assert_eq!(map.get(&1), None);
1672 assert_eq!(map.insert(1u, 1u), None);
1673 assert_eq!(map.get(&1), Some(&1));
1674 assert_eq!(map.insert(1, 2), Some(1));
1675 assert_eq!(map.get(&1), Some(&2));
1676 assert_eq!(map.insert(2, 4), None);
1677 assert_eq!(map.get(&2), Some(&4));
1678 assert_eq!(map.remove(&1), Some(2));
1679 assert_eq!(map.remove(&2), Some(4));
1680 assert_eq!(map.remove(&1), None);
1688 let mut map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1690 fn test<T>(size: uint, mut iter: T) where T: Iterator<Item=(uint, uint)> {
1692 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1693 assert_eq!(iter.next().unwrap(), (i, i));
1695 assert_eq!(iter.size_hint(), (0, Some(0)));
1696 assert_eq!(iter.next(), None);
1698 test(size, map.iter().map(|(&k, &v)| (k, v)));
1699 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
1700 test(size, map.into_iter());
1704 fn test_iter_rev() {
1708 let mut map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1710 fn test<T>(size: uint, mut iter: T) where T: Iterator<Item=(uint, uint)> {
1712 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1713 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
1715 assert_eq!(iter.size_hint(), (0, Some(0)));
1716 assert_eq!(iter.next(), None);
1718 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
1719 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
1720 test(size, map.into_iter().rev());
1724 fn test_iter_mixed() {
1728 let mut map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1730 fn test<T>(size: uint, mut iter: T)
1731 where T: Iterator<Item=(uint, uint)> + DoubleEndedIterator {
1732 for i in 0..size / 4 {
1733 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
1734 assert_eq!(iter.next().unwrap(), (i, i));
1735 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
1737 for i in size / 4..size * 3 / 4 {
1738 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
1739 assert_eq!(iter.next().unwrap(), (i, i));
1741 assert_eq!(iter.size_hint(), (0, Some(0)));
1742 assert_eq!(iter.next(), None);
1744 test(size, map.iter().map(|(&k, &v)| (k, v)));
1745 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
1746 test(size, map.into_iter());
1750 fn test_range_small() {
1754 let map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1757 for ((&k, &v), i) in map.range(Included(&2), Unbounded).zip(2u..size) {
1762 assert_eq!(j, size - 2);
1766 fn test_range_1000() {
1768 let map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1770 fn test(map: &BTreeMap<uint, uint>, size: uint, min: Bound<&uint>, max: Bound<&uint>) {
1771 let mut kvs = map.range(min, max).map(|(&k, &v)| (k, v));
1772 let mut pairs = (0..size).map(|i| (i, i));
1774 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
1775 assert_eq!(kv, pair);
1777 assert_eq!(kvs.next(), None);
1778 assert_eq!(pairs.next(), None);
1780 test(&map, size, Included(&0), Excluded(&size));
1781 test(&map, size, Unbounded, Excluded(&size));
1782 test(&map, size, Included(&0), Included(&(size - 1)));
1783 test(&map, size, Unbounded, Included(&(size - 1)));
1784 test(&map, size, Included(&0), Unbounded);
1785 test(&map, size, Unbounded, Unbounded);
1791 let map: BTreeMap<uint, uint> = (0..size).map(|i| (i, i)).collect();
1795 let mut kvs = map.range(Included(&i), Included(&j)).map(|(&k, &v)| (k, v));
1796 let mut pairs = range_inclusive(i, j).map(|i| (i, i));
1798 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
1799 assert_eq!(kv, pair);
1801 assert_eq!(kvs.next(), None);
1802 assert_eq!(pairs.next(), None);
1809 let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1811 let mut map: BTreeMap<int, int> = xs.iter().map(|&x| x).collect();
1813 // Existing key (insert)
1814 match map.entry(1) {
1815 Vacant(_) => unreachable!(),
1816 Occupied(mut view) => {
1817 assert_eq!(view.get(), &10);
1818 assert_eq!(view.insert(100), 10);
1821 assert_eq!(map.get(&1).unwrap(), &100);
1822 assert_eq!(map.len(), 6);
1825 // Existing key (update)
1826 match map.entry(2) {
1827 Vacant(_) => unreachable!(),
1828 Occupied(mut view) => {
1829 let v = view.get_mut();
1833 assert_eq!(map.get(&2).unwrap(), &200);
1834 assert_eq!(map.len(), 6);
1836 // Existing key (take)
1837 match map.entry(3) {
1838 Vacant(_) => unreachable!(),
1840 assert_eq!(view.remove(), 30);
1843 assert_eq!(map.get(&3), None);
1844 assert_eq!(map.len(), 5);
1847 // Inexistent key (insert)
1848 match map.entry(10) {
1849 Occupied(_) => unreachable!(),
1851 assert_eq!(*view.insert(1000), 1000);
1854 assert_eq!(map.get(&10).unwrap(), &1000);
1855 assert_eq!(map.len(), 6);
1867 use std::rand::{weak_rng, Rng};
1868 use test::{Bencher, black_box};
1870 use super::BTreeMap;
1871 use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1874 pub fn insert_rand_100(b: &mut Bencher) {
1875 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1876 insert_rand_n(100, &mut m, b,
1877 |m, i| { m.insert(i, 1); },
1878 |m, i| { m.remove(&i); });
1882 pub fn insert_rand_10_000(b: &mut Bencher) {
1883 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1884 insert_rand_n(10_000, &mut m, b,
1885 |m, i| { m.insert(i, 1); },
1886 |m, i| { m.remove(&i); });
1891 pub fn insert_seq_100(b: &mut Bencher) {
1892 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1893 insert_seq_n(100, &mut m, b,
1894 |m, i| { m.insert(i, 1); },
1895 |m, i| { m.remove(&i); });
1899 pub fn insert_seq_10_000(b: &mut Bencher) {
1900 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1901 insert_seq_n(10_000, &mut m, b,
1902 |m, i| { m.insert(i, 1); },
1903 |m, i| { m.remove(&i); });
1908 pub fn find_rand_100(b: &mut Bencher) {
1909 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1910 find_rand_n(100, &mut m, b,
1911 |m, i| { m.insert(i, 1); },
1912 |m, i| { m.get(&i); });
1916 pub fn find_rand_10_000(b: &mut Bencher) {
1917 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1918 find_rand_n(10_000, &mut m, b,
1919 |m, i| { m.insert(i, 1); },
1920 |m, i| { m.get(&i); });
1925 pub fn find_seq_100(b: &mut Bencher) {
1926 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1927 find_seq_n(100, &mut m, b,
1928 |m, i| { m.insert(i, 1); },
1929 |m, i| { m.get(&i); });
1933 pub fn find_seq_10_000(b: &mut Bencher) {
1934 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1935 find_seq_n(10_000, &mut m, b,
1936 |m, i| { m.insert(i, 1); },
1937 |m, i| { m.get(&i); });
1940 fn bench_iter(b: &mut Bencher, size: uint) {
1941 let mut map = BTreeMap::<uint, uint>::new();
1942 let mut rng = weak_rng();
1945 map.insert(rng.gen(), rng.gen());
1949 for entry in map.iter() {
1956 pub fn iter_20(b: &mut Bencher) {
1961 pub fn iter_1000(b: &mut Bencher) {
1962 bench_iter(b, 1000);
1966 pub fn iter_100000(b: &mut Bencher) {
1967 bench_iter(b, 100000);