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::*;
24 use core::borrow::BorrowFrom;
25 use std::hash::{Writer, Hash};
26 use core::default::Default;
27 use core::{iter, fmt, mem};
30 use ring_buf::RingBuf;
32 // FIXME(conventions): implement bounded iterators
34 /// A map based on a B-Tree.
36 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
37 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
38 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
39 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
40 /// is done is *very* inefficient for modern computer architectures. In particular, every element
41 /// is stored in its own individually heap-allocated node. This means that every single insertion
42 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
43 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
46 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
47 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
48 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
49 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
50 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
51 /// the node using binary search. As a compromise, one could also perform a linear search
52 /// that initially only checks every i<sup>th</sup> element for some choice of i.
54 /// Currently, our implementation simply performs naive linear search. This provides excellent
55 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
56 /// would like to further explore choosing the optimal search strategy based on the choice of B,
57 /// and possibly other factors. Using linear search, searching for a random element is expected
58 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
59 /// however, performance is excellent. `BTreeMap` is able to readily outperform `TreeMap` under
60 /// many workloads, and is competitive where it doesn't. BTreeMap also generally *scales* better
61 /// than TreeMap, making it more appropriate for large datasets.
63 /// However, `TreeMap` may still be more appropriate to use in many contexts. If elements are very
64 /// large or expensive to compare, `TreeMap` may be more appropriate. It won't allocate any
65 /// more space than is needed, and will perform the minimal number of comparisons necessary.
66 /// `TreeMap` also provides much better performance stability guarantees. Generally, very few
67 /// changes need to be made to update a BST, and two updates are expected to take about the same
68 /// amount of time on roughly equal sized BSTs. However a B-Tree's performance is much more
69 /// amortized. If a node is overfull, it must be split into two nodes. If a node is underfull, it
70 /// may be merged with another. Both of these operations are relatively expensive to perform, and
71 /// it's possible to force one to occur at every single level of the tree in a single insertion or
72 /// deletion. In fact, a malicious or otherwise unlucky sequence of insertions and deletions can
73 /// force this degenerate behaviour to occur on every operation. While the total amount of work
74 /// done on each operation isn't *catastrophic*, and *is* still bounded by O(B log<sub>B</sub>n),
75 /// it is certainly much slower when it does.
77 pub struct BTreeMap<K, V> {
84 /// An abstract base over-which all other BTree iterators are built.
85 struct AbsEntries<T> {
92 /// An iterator over a BTreeMap's entries.
93 pub struct Entries<'a, K: 'a, V: 'a> {
94 inner: AbsEntries<Traversal<'a, K, V>>
97 /// A mutable iterator over a BTreeMap's entries.
98 pub struct MutEntries<'a, K: 'a, V: 'a> {
99 inner: AbsEntries<MutTraversal<'a, K, V>>
102 /// An owning iterator over a BTreeMap's entries.
103 pub struct MoveEntries<K, V> {
104 inner: AbsEntries<MoveTraversal<K, V>>
107 /// An iterator over a BTreeMap's keys.
108 pub type Keys<'a, K, V> = iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
110 /// An iterator over a BTreeMap's values.
111 pub type Values<'a, K, V> = iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
113 /// A view into a single entry in a map, which may either be vacant or occupied.
114 pub enum Entry<'a, K:'a, V:'a> {
116 Vacant(VacantEntry<'a, K, V>),
117 /// An occupied Entry
118 Occupied(OccupiedEntry<'a, K, V>),
122 pub struct VacantEntry<'a, K:'a, V:'a> {
124 stack: stack::SearchStack<'a, K, V>,
127 /// An occupied Entry.
128 pub struct OccupiedEntry<'a, K:'a, V:'a> {
129 stack: stack::SearchStack<'a, K, V>,
132 impl<K: Ord, V> BTreeMap<K, V> {
133 /// Makes a new empty BTreeMap with a reasonable choice for B.
134 #[unstable = "matches collection reform specification, waiting for dust to settle"]
135 pub fn new() -> BTreeMap<K, V> {
136 //FIXME(Gankro): Tune this as a function of size_of<K/V>?
140 /// Makes a new empty BTreeMap with the given B.
142 /// B cannot be less than 2.
143 pub fn with_b(b: uint) -> BTreeMap<K, V> {
144 assert!(b > 1, "B must be greater than 1");
148 root: Node::make_leaf_root(b),
153 /// Clears the map, removing all values.
158 /// use std::collections::BTreeMap;
160 /// let mut a = BTreeMap::new();
161 /// a.insert(1u, "a");
163 /// assert!(a.is_empty());
165 #[unstable = "matches collection reform specification, waiting for dust to settle"]
166 pub fn clear(&mut self) {
168 // avoid recursive destructors by manually traversing the tree
169 for _ in mem::replace(self, BTreeMap::with_b(b)).into_iter() {};
172 /// Deprecated: renamed to `get`.
173 #[deprecated = "renamed to `get`"]
174 pub fn find(&self, key: &K) -> Option<&V> {
178 // Searching in a B-Tree is pretty straightforward.
180 // Start at the root. Try to find the key in the current node. If we find it, return it.
181 // If it's not in there, follow the edge *before* the smallest key larger than
182 // the search key. If no such key exists (they're *all* smaller), then just take the last
183 // edge in the node. If we're in a leaf and we don't find our key, then it's not
186 /// Returns a reference to the value corresponding to the key.
188 /// The key may be any borrowed form of the map's key type, but the ordering
189 /// on the borrowed form *must* match the ordering on the key type.
194 /// use std::collections::BTreeMap;
196 /// let mut map = BTreeMap::new();
197 /// map.insert(1u, "a");
198 /// assert_eq!(map.get(&1), Some(&"a"));
199 /// assert_eq!(map.get(&2), None);
201 #[unstable = "matches collection reform specification, waiting for dust to settle"]
202 pub fn get<Sized? Q>(&self, key: &Q) -> Option<&V> where Q: BorrowFrom<K> + Ord {
203 let mut cur_node = &self.root;
205 match cur_node.search(key) {
206 Found(i) => return cur_node.val(i),
207 GoDown(i) => match cur_node.edge(i) {
210 cur_node = next_node;
218 /// Returns true if the map contains a value for the specified key.
220 /// The key may be any borrowed form of the map's key type, but the ordering
221 /// on the borrowed form *must* match the ordering on the key type.
226 /// use std::collections::BTreeMap;
228 /// let mut map = BTreeMap::new();
229 /// map.insert(1u, "a");
230 /// assert_eq!(map.contains_key(&1), true);
231 /// assert_eq!(map.contains_key(&2), false);
233 #[unstable = "matches collection reform specification, waiting for dust to settle"]
234 pub fn contains_key<Sized? Q>(&self, key: &Q) -> bool where Q: BorrowFrom<K> + Ord {
235 self.get(key).is_some()
238 /// Deprecated: renamed to `get_mut`.
239 #[deprecated = "renamed to `get_mut`"]
240 pub fn find_mut(&mut self, key: &K) -> Option<&mut V> {
244 /// Returns a mutable reference to the value corresponding to the key.
246 /// The key may be any borrowed form of the map's key type, but the ordering
247 /// on the borrowed form *must* match the ordering on the key type.
252 /// use std::collections::BTreeMap;
254 /// let mut map = BTreeMap::new();
255 /// map.insert(1u, "a");
256 /// match map.get_mut(&1) {
257 /// Some(x) => *x = "b",
260 /// assert_eq!(map[1], "b");
262 // See `get` for implementation notes, this is basically a copy-paste with mut's added
263 #[unstable = "matches collection reform specification, waiting for dust to settle"]
264 pub fn get_mut<Sized? Q>(&mut self, key: &Q) -> Option<&mut V> where Q: BorrowFrom<K> + Ord {
265 // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
266 let mut temp_node = &mut self.root;
268 let cur_node = temp_node;
269 match cur_node.search(key) {
270 Found(i) => return cur_node.val_mut(i),
271 GoDown(i) => match cur_node.edge_mut(i) {
274 temp_node = next_node;
282 /// Deprecated: renamed to `insert`.
283 #[deprecated = "renamed to `insert`"]
284 pub fn swap(&mut self, key: K, value: V) -> Option<V> {
285 self.insert(key, value)
288 // Insertion in a B-Tree is a bit complicated.
290 // First we do the same kind of search described in `find`. But we need to maintain a stack of
291 // all the nodes/edges in our search path. If we find a match for the key we're trying to
292 // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
293 // we attempt to insert our key-value pair at the same location we would want to follow another
296 // If the node has room, then this is done in the obvious way by shifting elements. However,
297 // if the node itself is full, we split node into two, and give its median key-value
298 // pair to its parent to insert the new node with. Of course, the parent may also be
299 // full, and insertion can propagate until we reach the root. If we reach the root, and
300 // it is *also* full, then we split the root and place the two nodes under a newly made root.
302 // Note that we subtly deviate from Open Data Structures in our implementation of split.
303 // ODS describes inserting into the node *regardless* of its capacity, and then
304 // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
305 // Instead, we split beforehand, and then insert the key-value pair into the appropriate
306 // result node. This has two consequences:
308 // 1) While ODS produces a left node of size B-1, and a right node of size B,
309 // we may potentially reverse this. However, this shouldn't effect the analysis.
311 // 2) While ODS may potentially return the pair we *just* inserted after
312 // the split, we will never do this. Again, this shouldn't effect the analysis.
314 /// Inserts a key-value pair from the map. If the key already had a value
315 /// present in the map, that value is returned. Otherwise, `None` is returned.
320 /// use std::collections::BTreeMap;
322 /// let mut map = BTreeMap::new();
323 /// assert_eq!(map.insert(37u, "a"), None);
324 /// assert_eq!(map.is_empty(), false);
326 /// map.insert(37, "b");
327 /// assert_eq!(map.insert(37, "c"), Some("b"));
328 /// assert_eq!(map[37], "c");
330 #[unstable = "matches collection reform specification, waiting for dust to settle"]
331 pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
332 // This is a stack of rawptrs to nodes paired with indices, respectively
333 // representing the nodes and edges of our search path. We have to store rawptrs
334 // because as far as Rust is concerned, we can mutate aliased data with such a
335 // stack. It is of course correct, but what it doesn't know is that we will only
336 // be popping and using these ptrs one at a time in child-to-parent order. The alternative
337 // to doing this is to take the Nodes from their parents. This actually makes
338 // borrowck *really* happy and everything is pretty smooth. However, this creates
339 // *tons* of pointless writes, and requires us to always walk all the way back to
340 // the root after an insertion, even if we only needed to change a leaf. Therefore,
341 // we accept this potential unsafety and complexity in the name of performance.
343 // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
344 // by the stack module. All it can do is immutably read nodes, and ask the search stack
345 // to proceed down some edge by index. This makes the search logic we'll be reusing in a
346 // few different methods much neater, and of course drastically improves safety.
347 let mut stack = stack::PartialSearchStack::new(self);
350 // Same basic logic as found in `find`, but with PartialSearchStack mediating the
351 // actual nodes for us
352 match stack.next().search(&key) {
354 // Perfect match, swap the values and return the old one
355 let next = stack.into_next();
356 mem::swap(next.unsafe_val_mut(i), &mut value);
360 // We need to keep searching, try to get the search stack
361 // to go down further
362 stack = match stack.push(i) {
363 stack::Done(new_stack) => {
364 // We've reached a leaf, perform the insertion here
365 new_stack.insert(key, value);
368 stack::Grew(new_stack) => {
369 // We've found the subtree to insert this key/value pair in,
379 // Deletion is the most complicated operation for a B-Tree.
381 // First we do the same kind of search described in
382 // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
383 // If we don't find the key, then we just return `None` and do nothing. If we do find the
384 // key, we perform two operations: remove the item, and then possibly handle underflow.
386 // # removing the item
387 // If the node is a leaf, we just remove the item, and shift
388 // any items after it back to fill the hole.
390 // If the node is an internal node, we *swap* the item with the smallest item in
391 // in its right subtree (which must reside in a leaf), and then revert to the leaf
394 // # handling underflow
395 // After removing an item, there may be too few items in the node. We want nodes
396 // to be mostly full for efficiency, although we make an exception for the root, which
397 // may have as few as one item. If this is the case, we may first try to steal
398 // an item from our left or right neighbour.
400 // To steal from the left (right) neighbour,
401 // we take the largest (smallest) item and child from it. We then swap the taken item
402 // with the item in their mutual parent that separates them, and then insert the
403 // parent's item and the taken child into the first (last) index of the underflowed node.
405 // However, stealing has the possibility of underflowing our neighbour. If this is the
406 // case, we instead *merge* with our neighbour. This of course reduces the number of
407 // children in the parent. Therefore, we also steal the item that separates the now
408 // merged nodes, and insert it into the merged node.
410 // Merging may cause the parent to underflow. If this is the case, then we must repeat
411 // the underflow handling process on the parent. If merging merges the last two children
412 // of the root, then we replace the root with the merged node.
414 /// Deprecated: renamed to `remove`.
415 #[deprecated = "renamed to `remove`"]
416 pub fn pop(&mut self, key: &K) -> Option<V> {
420 /// Removes a key from the map, returning the value at the key if the key
421 /// was previously in the map.
423 /// The key may be any borrowed form of the map's key type, but the ordering
424 /// on the borrowed form *must* match the ordering on the key type.
429 /// use std::collections::BTreeMap;
431 /// let mut map = BTreeMap::new();
432 /// map.insert(1u, "a");
433 /// assert_eq!(map.remove(&1), Some("a"));
434 /// assert_eq!(map.remove(&1), None);
436 #[unstable = "matches collection reform specification, waiting for dust to settle"]
437 pub fn remove<Sized? Q>(&mut self, key: &Q) -> Option<V> where Q: BorrowFrom<K> + Ord {
438 // See `swap` for a more thorough description of the stuff going on in here
439 let mut stack = stack::PartialSearchStack::new(self);
441 match stack.next().search(key) {
443 // Perfect match. Terminate the stack here, and remove the entry
444 return Some(stack.seal(i).remove());
447 // We need to keep searching, try to go down the next edge
448 stack = match stack.push(i) {
449 stack::Done(_) => return None, // We're at a leaf; the key isn't in here
450 stack::Grew(new_stack) => {
460 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
461 /// to nodes. By using this module much better safety guarantees can be made, and more search
462 /// boilerplate gets cut out.
464 pub use self::PushResult::*;
465 use core::prelude::*;
467 use super::super::node::*;
470 type StackItem<K, V> = (*mut Node<K, V>, uint);
471 type Stack<K, V> = Vec<StackItem<K, V>>;
473 /// A PartialSearchStack handles the construction of a search stack.
474 pub struct PartialSearchStack<'a, K:'a, V:'a> {
475 map: &'a mut BTreeMap<K, V>,
477 next: *mut Node<K, V>,
480 /// A SearchStack represents a full path to an element of interest. It provides methods
481 /// for manipulating the element at the top of its stack.
482 pub struct SearchStack<'a, K:'a, V:'a> {
483 map: &'a mut BTreeMap<K, V>,
485 top: StackItem<K, V>,
488 /// The result of asking a PartialSearchStack to push another node onto itself. Either it
489 /// Grew, in which case it's still Partial, or it found its last node was actually a leaf, in
490 /// which case it seals itself and yields a complete SearchStack.
491 pub enum PushResult<'a, K:'a, V:'a> {
492 Grew(PartialSearchStack<'a, K, V>),
493 Done(SearchStack<'a, K, V>),
496 impl<'a, K, V> PartialSearchStack<'a, K, V> {
497 /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
498 /// root of the tree.
499 pub fn new<'a>(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
500 let depth = map.depth;
503 next: &mut map.root as *mut _,
505 stack: Vec::with_capacity(depth),
509 /// Pushes the requested child of the stack's current top on top of the stack. If the child
510 /// exists, then a new PartialSearchStack is yielded. Otherwise, a full SearchStack is
512 pub fn push(self, edge: uint) -> PushResult<'a, K, V> {
514 let mut stack = self.stack;
515 let next_ptr = self.next;
516 let next_node = unsafe {
519 let to_insert = (next_ptr, edge);
520 match next_node.edge_mut(edge) {
521 None => Done(SearchStack {
527 stack.push(to_insert);
528 Grew(PartialSearchStack {
531 next: node as *mut _,
537 /// Converts the stack into a mutable reference to its top.
538 pub fn into_next(self) -> &'a mut Node<K, V> {
544 /// Gets the top of the stack.
545 pub fn next(&self) -> &Node<K, V> {
551 /// Converts the PartialSearchStack into a SearchStack.
552 pub fn seal(self, index: uint) -> SearchStack<'a, K, V> {
556 top: (self.next as *mut _, index),
561 impl<'a, K, V> SearchStack<'a, K, V> {
562 /// Gets a reference to the value the stack points to.
563 pub fn peek(&self) -> &V {
564 let (node_ptr, index) = self.top;
566 (*node_ptr).val(index).unwrap()
570 /// Gets a mutable reference to the value the stack points to.
571 pub fn peek_mut(&mut self) -> &mut V {
572 let (node_ptr, index) = self.top;
574 (*node_ptr).val_mut(index).unwrap()
578 /// Converts the stack into a mutable reference to the value it points to, with a lifetime
579 /// tied to the original tree.
580 pub fn into_top(self) -> &'a mut V {
581 let (node_ptr, index) = self.top;
583 (*node_ptr).val_mut(index).unwrap()
587 /// Inserts the key and value into the top element in the stack, and if that node has to
588 /// split recursively inserts the split contents into the next element stack until
591 /// Assumes that the stack represents a search path from the root to a leaf.
593 /// An &mut V is returned to the inserted value, for callers that want a reference to this.
594 pub fn insert(self, key: K, val: V) -> &'a mut V {
599 let mut stack = self.stack;
600 // Insert the key and value into the leaf at the top of the stack
601 let (node, index) = self.top;
602 let (mut insertion, inserted_ptr) = {
603 (*node).insert_as_leaf(index, key, val)
609 // The last insertion went off without a hitch, no splits! We can stop
611 return &mut *inserted_ptr;
613 Split(key, val, right) => match stack.pop() {
614 // The last insertion triggered a split, so get the next element on the
615 // stack to recursively insert the split node into.
617 // The stack was empty; we've split the root, and need to make a
618 // a new one. This is done in-place because we can't move the
619 // root out of a reference to the tree.
620 Node::make_internal_root(&mut map.root, map.b, key, val, right);
623 return &mut *inserted_ptr;
625 Some((node, index)) => {
626 // The stack wasn't empty, do the insertion and recurse
627 insertion = (*node).insert_as_internal(index, key, val, right);
636 /// Removes the key and value in the top element of the stack, then handles underflows as
637 /// described in BTree's pop function.
638 pub fn remove(mut self) -> V {
639 // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
640 // in a BTree. Note that this may put the tree in an inconsistent state (further
641 // described in leafify's comments), but this is immediately fixed by the
642 // removing the value we want to remove
648 let mut stack = self.stack;
650 // Remove the key-value pair from the leaf that this search stack points to.
651 // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
652 // to avoid ownership issues.
653 let (value, mut underflow) = unsafe {
654 let (leaf_ptr, index) = self.top;
655 let leaf = &mut *leaf_ptr;
656 let (_key, value) = leaf.remove_as_leaf(index);
657 let underflow = leaf.is_underfull();
664 // We've reached the root, so no matter what, we're done. We manually
665 // access the root via the tree itself to avoid creating any dangling
667 if map.root.len() == 0 && !map.root.is_leaf() {
668 // We've emptied out the root, so make its only child the new root.
669 // If it's a leaf, we just let it become empty.
671 map.root = map.root.pop_edge().unwrap();
675 Some((parent_ptr, index)) => {
677 // Underflow! Handle it!
679 let parent = &mut *parent_ptr;
680 parent.handle_underflow(index);
681 underflow = parent.is_underfull();
692 /// Subroutine for removal. Takes a search stack for a key that might terminate at an
693 /// internal node, and mutates the tree and search stack to *make* it a search stack
694 /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
695 /// leaves the tree in an inconsistent state that must be repaired by the caller by
696 /// removing the entry in question. Specifically the key-value pair and its successor will
698 fn leafify(&mut self) {
700 let (node_ptr, index) = self.top;
701 // First, get ptrs to the found key-value pair
702 let node = &mut *node_ptr;
703 let (key_ptr, val_ptr) = {
704 (node.unsafe_key_mut(index) as *mut _,
705 node.unsafe_val_mut(index) as *mut _)
708 // Try to go into the right subtree of the found key to find its successor
709 match node.edge_mut(index + 1) {
711 // We're a proper leaf stack, nothing to do
713 Some(mut temp_node) => {
714 //We're not a proper leaf stack, let's get to work.
715 self.stack.push((node_ptr, index + 1));
717 // Walk into the smallest subtree of this node
718 let node = temp_node;
719 let node_ptr = node as *mut _;
722 // This node is a leaf, do the swap and return
723 self.top = (node_ptr, 0);
724 node.unsafe_swap(0, &mut *key_ptr, &mut *val_ptr);
727 // This node is internal, go deeper
728 self.stack.push((node_ptr, 0));
729 temp_node = node.unsafe_edge_mut(0);
739 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
740 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> BTreeMap<K, V> {
741 let mut map = BTreeMap::new();
747 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
749 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
756 impl<S: Writer, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
757 fn hash(&self, state: &mut S) {
758 for elt in self.iter() {
764 impl<K: Ord, V> Default for BTreeMap<K, V> {
765 fn default() -> BTreeMap<K, V> {
770 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
771 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
772 self.len() == other.len() &&
773 self.iter().zip(other.iter()).all(|(a, b)| a == b)
777 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
779 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
781 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
782 iter::order::partial_cmp(self.iter(), other.iter())
786 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
788 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
789 iter::order::cmp(self.iter(), other.iter())
793 impl<K: Show, V: Show> Show for BTreeMap<K, V> {
794 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
795 try!(write!(f, "{{"));
797 for (i, (k, v)) in self.iter().enumerate() {
798 if i != 0 { try!(write!(f, ", ")); }
799 try!(write!(f, "{}: {}", *k, *v));
806 impl<K: Ord, Sized? Q, V> Index<Q, V> for BTreeMap<K, V>
807 where Q: BorrowFrom<K> + Ord
809 fn index(&self, key: &Q) -> &V {
810 self.get(key).expect("no entry found for key")
814 impl<K: Ord, Sized? Q, V> IndexMut<Q, V> for BTreeMap<K, V>
815 where Q: BorrowFrom<K> + Ord
817 fn index_mut(&mut self, key: &Q) -> &mut V {
818 self.get_mut(key).expect("no entry found for key")
822 /// Genericises over how to get the correct type of iterator from the correct type
823 /// of Node ownership.
825 fn traverse(node: N) -> Self;
828 impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
829 fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
834 impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
835 fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
840 impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
841 fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
846 /// Represents an operation to perform inside the following iterator methods.
847 /// This is necessary to use in `next` because we want to modify self.left inside
848 /// a match that borrows it. Similarly, in `next_back` for self.right. Instead, we use this
849 /// enum to note what we want to do, and do it after the match.
855 impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>>
856 Iterator<(K, V)> for AbsEntries<T> {
857 // This function is pretty long, but only because there's a lot of cases to consider.
858 // Our iterator represents two search paths, left and right, to the smallest and largest
859 // elements we have yet to yield. lca represents the least common ancestor of these two paths,
860 // above-which we never walk, since everything outside it has already been consumed (or was
861 // never in the range to iterate).
863 // Note that the design of these iterators permits an *arbitrary* initial pair of min and max,
864 // making these arbitrary sub-range iterators. However the logic to construct these paths
865 // efficiently is fairly involved, so this is a FIXME. The sub-range iterators also wouldn't be
866 // able to accurately predict size, so those iterators can't implement ExactSizeIterator.
867 fn next(&mut self) -> Option<(K, V)> {
869 // We want the smallest element, so try to get the top of the left stack
870 let op = match self.left.back_mut() {
871 // The left stack is empty, so try to get the next element of the two paths
872 // LCAs (the left search path is currently a subpath of the right one)
873 None => match self.lca.next() {
874 // The lca has been exhausted, walk further down the right path
875 None => match self.right.pop_front() {
876 // The right path is exhausted, so we're done
878 // The right path had something, make that the new LCA
879 // and restart the whole process
885 // The lca yielded an edge, make that the new head of the left path
886 Some(Edge(next)) => Push(Traverse::traverse(next)),
887 // The lca yielded an entry, so yield that
888 Some(Elem(k, v)) => {
893 // The left stack wasn't empty, so continue along the node in its head
894 Some(iter) => match iter.next() {
895 // The head of the left path is empty, so Pop it off and restart the process
897 // The head of the left path yielded an edge, so make that the new head
899 Some(Edge(next)) => Push(Traverse::traverse(next)),
900 // The head of the left path yielded entry, so yield that
901 Some(Elem(k, v)) => {
908 // Handle any operation on the left stack as necessary
910 Push(item) => { self.left.push_back(item); },
911 Pop => { self.left.pop_back(); },
916 fn size_hint(&self) -> (uint, Option<uint>) {
917 (self.size, Some(self.size))
921 impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>>
922 DoubleEndedIterator<(K, V)> for AbsEntries<T> {
923 // next_back is totally symmetric to next
924 fn next_back(&mut self) -> Option<(K, V)> {
926 let op = match self.right.back_mut() {
927 None => match self.lca.next_back() {
928 None => match self.left.pop_front() {
935 Some(Edge(next)) => Push(Traverse::traverse(next)),
936 Some(Elem(k, v)) => {
941 Some(iter) => match iter.next_back() {
943 Some(Edge(next)) => Push(Traverse::traverse(next)),
944 Some(Elem(k, v)) => {
952 Push(item) => { self.right.push_back(item); },
953 Pop => { self.right.pop_back(); }
959 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
960 fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
961 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
963 impl<'a, K, V> DoubleEndedIterator<(&'a K, &'a V)> for Entries<'a, K, V> {
964 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
966 impl<'a, K, V> ExactSizeIterator<(&'a K, &'a V)> for Entries<'a, K, V> {}
969 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
970 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
971 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
973 impl<'a, K, V> DoubleEndedIterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
974 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
976 impl<'a, K, V> ExactSizeIterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {}
979 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
980 fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
981 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
983 impl<K, V> DoubleEndedIterator<(K, V)> for MoveEntries<K, V> {
984 fn next_back(&mut self) -> Option<(K, V)> { self.inner.next_back() }
986 impl<K, V> ExactSizeIterator<(K, V)> for MoveEntries<K, V> {}
990 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
991 /// Sets the value of the entry with the VacantEntry's key,
992 /// and returns a mutable reference to it.
993 pub fn set(self, value: V) -> &'a mut V {
994 self.stack.insert(self.key, value)
998 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
999 /// Gets a reference to the value in the entry.
1000 pub fn get(&self) -> &V {
1004 /// Gets a mutable reference to the value in the entry.
1005 pub fn get_mut(&mut self) -> &mut V {
1006 self.stack.peek_mut()
1009 /// Converts the entry into a mutable reference to its value.
1010 pub fn into_mut(self) -> &'a mut V {
1011 self.stack.into_top()
1014 /// Sets the value of the entry with the OccupiedEntry's key,
1015 /// and returns the entry's old value.
1016 pub fn set(&mut self, mut value: V) -> V {
1017 mem::swap(self.stack.peek_mut(), &mut value);
1021 /// Takes the value of the entry out of the map, and returns it.
1022 pub fn take(self) -> V {
1027 impl<K, V> BTreeMap<K, V> {
1028 /// Gets an iterator over the entries of the map.
1029 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1030 pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
1031 let len = self.len();
1034 lca: Traverse::traverse(&self.root),
1035 left: RingBuf::new(),
1036 right: RingBuf::new(),
1042 /// Gets a mutable iterator over the entries of the map.
1043 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1044 pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, K, V> {
1045 let len = self.len();
1048 lca: Traverse::traverse(&mut self.root),
1049 left: RingBuf::new(),
1050 right: RingBuf::new(),
1056 /// Gets an owning iterator over the entries of the map.
1057 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1058 pub fn into_iter(self) -> MoveEntries<K, V> {
1059 let len = self.len();
1062 lca: Traverse::traverse(self.root),
1063 left: RingBuf::new(),
1064 right: RingBuf::new(),
1070 /// Gets an iterator over the keys of the map.
1071 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1072 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1073 self.iter().map(|(k, _)| k)
1076 /// Gets an iterator over the values of the map.
1077 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1078 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1079 self.iter().map(|(_, v)| v)
1082 /// Return the number of elements in the map.
1087 /// use std::collections::BTreeMap;
1089 /// let mut a = BTreeMap::new();
1090 /// assert_eq!(a.len(), 0);
1091 /// a.insert(1u, "a");
1092 /// assert_eq!(a.len(), 1);
1094 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1095 pub fn len(&self) -> uint { self.length }
1097 /// Return true if the map contains no elements.
1102 /// use std::collections::BTreeMap;
1104 /// let mut a = BTreeMap::new();
1105 /// assert!(a.is_empty());
1106 /// a.insert(1u, "a");
1107 /// assert!(!a.is_empty());
1109 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1110 pub fn is_empty(&self) -> bool { self.len() == 0 }
1113 impl<K: Ord, V> BTreeMap<K, V> {
1114 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1115 pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V> {
1116 // same basic logic of `swap` and `pop`, blended together
1117 let mut stack = stack::PartialSearchStack::new(self);
1119 match stack.next().search(&key) {
1122 return Occupied(OccupiedEntry {
1123 stack: stack.seal(i)
1127 stack = match stack.push(i) {
1128 stack::Done(new_stack) => {
1129 // Not in the tree, but we've found where it goes
1130 return Vacant(VacantEntry {
1135 stack::Grew(new_stack) => {
1136 // We've found the subtree this key must go in
1152 use std::prelude::*;
1154 use super::{BTreeMap, Occupied, Vacant};
1157 fn test_basic_large() {
1158 let mut map = BTreeMap::new();
1160 assert_eq!(map.len(), 0);
1162 for i in range(0, size) {
1163 assert_eq!(map.insert(i, 10*i), None);
1164 assert_eq!(map.len(), i + 1);
1167 for i in range(0, size) {
1168 assert_eq!(map.get(&i).unwrap(), &(i*10));
1171 for i in range(size, size*2) {
1172 assert_eq!(map.get(&i), None);
1175 for i in range(0, size) {
1176 assert_eq!(map.insert(i, 100*i), Some(10*i));
1177 assert_eq!(map.len(), size);
1180 for i in range(0, size) {
1181 assert_eq!(map.get(&i).unwrap(), &(i*100));
1184 for i in range(0, size/2) {
1185 assert_eq!(map.remove(&(i*2)), Some(i*200));
1186 assert_eq!(map.len(), size - i - 1);
1189 for i in range(0, size/2) {
1190 assert_eq!(map.get(&(2*i)), None);
1191 assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
1194 for i in range(0, size/2) {
1195 assert_eq!(map.remove(&(2*i)), None);
1196 assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
1197 assert_eq!(map.len(), size/2 - i - 1);
1202 fn test_basic_small() {
1203 let mut map = BTreeMap::new();
1204 assert_eq!(map.remove(&1), None);
1205 assert_eq!(map.get(&1), None);
1206 assert_eq!(map.insert(1u, 1u), None);
1207 assert_eq!(map.get(&1), Some(&1));
1208 assert_eq!(map.insert(1, 2), Some(1));
1209 assert_eq!(map.get(&1), Some(&2));
1210 assert_eq!(map.insert(2, 4), None);
1211 assert_eq!(map.get(&2), Some(&4));
1212 assert_eq!(map.remove(&1), Some(2));
1213 assert_eq!(map.remove(&2), Some(4));
1214 assert_eq!(map.remove(&1), None);
1222 let mut map: BTreeMap<uint, uint> = Vec::from_fn(size, |i| (i, i)).into_iter().collect();
1225 let mut iter = map.iter();
1226 for i in range(0, size) {
1227 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1228 assert_eq!(iter.next().unwrap(), (&i, &i));
1230 assert_eq!(iter.size_hint(), (0, Some(0)));
1231 assert_eq!(iter.next(), None);
1235 let mut iter = map.iter_mut();
1236 for i in range(0, size) {
1237 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1238 assert_eq!(iter.next().unwrap(), (&i, &mut (i + 0)));
1240 assert_eq!(iter.size_hint(), (0, Some(0)));
1241 assert_eq!(iter.next(), None);
1245 let mut iter = map.into_iter();
1246 for i in range(0, size) {
1247 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1248 assert_eq!(iter.next().unwrap(), (i, i));
1250 assert_eq!(iter.size_hint(), (0, Some(0)));
1251 assert_eq!(iter.next(), None);
1257 fn test_iter_rev() {
1261 let mut map: BTreeMap<uint, uint> = Vec::from_fn(size, |i| (i, i)).into_iter().collect();
1264 let mut iter = map.iter().rev();
1265 for i in range(0, size) {
1266 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1267 assert_eq!(iter.next().unwrap(), (&(size - i - 1), &(size - i - 1)));
1269 assert_eq!(iter.size_hint(), (0, Some(0)));
1270 assert_eq!(iter.next(), None);
1274 let mut iter = map.iter_mut().rev();
1275 for i in range(0, size) {
1276 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1277 assert_eq!(iter.next().unwrap(), (&(size - i - 1), &mut(size - i - 1)));
1279 assert_eq!(iter.size_hint(), (0, Some(0)));
1280 assert_eq!(iter.next(), None);
1284 let mut iter = map.into_iter().rev();
1285 for i in range(0, size) {
1286 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1287 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
1289 assert_eq!(iter.size_hint(), (0, Some(0)));
1290 assert_eq!(iter.next(), None);
1297 let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1299 let mut map: BTreeMap<int, int> = xs.iter().map(|&x| x).collect();
1301 // Existing key (insert)
1302 match map.entry(1) {
1303 Vacant(_) => unreachable!(),
1304 Occupied(mut view) => {
1305 assert_eq!(view.get(), &10);
1306 assert_eq!(view.set(100), 10);
1309 assert_eq!(map.get(&1).unwrap(), &100);
1310 assert_eq!(map.len(), 6);
1313 // Existing key (update)
1314 match map.entry(2) {
1315 Vacant(_) => unreachable!(),
1316 Occupied(mut view) => {
1317 let v = view.get_mut();
1321 assert_eq!(map.get(&2).unwrap(), &200);
1322 assert_eq!(map.len(), 6);
1324 // Existing key (take)
1325 match map.entry(3) {
1326 Vacant(_) => unreachable!(),
1328 assert_eq!(view.take(), 30);
1331 assert_eq!(map.get(&3), None);
1332 assert_eq!(map.len(), 5);
1335 // Inexistent key (insert)
1336 match map.entry(10) {
1337 Occupied(_) => unreachable!(),
1339 assert_eq!(*view.set(1000), 1000);
1342 assert_eq!(map.get(&10).unwrap(), &1000);
1343 assert_eq!(map.len(), 6);
1354 use std::prelude::*;
1355 use std::rand::{weak_rng, Rng};
1356 use test::{Bencher, black_box};
1358 use super::BTreeMap;
1359 use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1362 pub fn insert_rand_100(b: &mut Bencher) {
1363 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1364 insert_rand_n(100, &mut m, b,
1365 |m, i| { m.insert(i, 1); },
1366 |m, i| { m.remove(&i); });
1370 pub fn insert_rand_10_000(b: &mut Bencher) {
1371 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1372 insert_rand_n(10_000, &mut m, b,
1373 |m, i| { m.insert(i, 1); },
1374 |m, i| { m.remove(&i); });
1379 pub fn insert_seq_100(b: &mut Bencher) {
1380 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1381 insert_seq_n(100, &mut m, b,
1382 |m, i| { m.insert(i, 1); },
1383 |m, i| { m.remove(&i); });
1387 pub fn insert_seq_10_000(b: &mut Bencher) {
1388 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1389 insert_seq_n(10_000, &mut m, b,
1390 |m, i| { m.insert(i, 1); },
1391 |m, i| { m.remove(&i); });
1396 pub fn find_rand_100(b: &mut Bencher) {
1397 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1398 find_rand_n(100, &mut m, b,
1399 |m, i| { m.insert(i, 1); },
1400 |m, i| { m.get(&i); });
1404 pub fn find_rand_10_000(b: &mut Bencher) {
1405 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1406 find_rand_n(10_000, &mut m, b,
1407 |m, i| { m.insert(i, 1); },
1408 |m, i| { m.get(&i); });
1413 pub fn find_seq_100(b: &mut Bencher) {
1414 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1415 find_seq_n(100, &mut m, b,
1416 |m, i| { m.insert(i, 1); },
1417 |m, i| { m.get(&i); });
1421 pub fn find_seq_10_000(b: &mut Bencher) {
1422 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1423 find_seq_n(10_000, &mut m, b,
1424 |m, i| { m.insert(i, 1); },
1425 |m, i| { m.get(&i); });
1428 fn bench_iter(b: &mut Bencher, size: uint) {
1429 let mut map = BTreeMap::<uint, uint>::new();
1430 let mut rng = weak_rng();
1432 for _ in range(0, size) {
1433 map.insert(rng.gen(), rng.gen());
1437 for entry in map.iter() {
1444 pub fn iter_20(b: &mut Bencher) {
1449 pub fn iter_1000(b: &mut Bencher) {
1450 bench_iter(b, 1000);
1454 pub fn iter_100000(b: &mut Bencher) {
1455 bench_iter(b, 100000);