1 // Copyright 2013 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.
13 use alloc::boxed::Box;
15 use core::borrow::BorrowFrom;
16 use core::default::Default;
20 use core::mem::{replace, swap};
22 use std::hash::{Writer, Hash};
26 // FIXME(conventions): implement bounded iterators
27 // FIXME(conventions): replace rev_iter(_mut) by making iter(_mut) DoubleEnded
29 /// This is implemented as an AA tree, which is a simplified variation of
30 /// a red-black tree where red (horizontal) nodes can only be added
31 /// as a right child. The time complexity is the same, and re-balancing
32 /// operations are more frequent but also cheaper.
37 /// use std::collections::TreeMap;
39 /// let mut map = TreeMap::new();
41 /// map.insert(2i, "bar");
42 /// map.insert(1i, "foo");
43 /// map.insert(3i, "quux");
45 /// // In ascending order by keys
46 /// for (key, value) in map.iter() {
47 /// println!("{}: {}", key, value);
51 /// for key in map.keys() {
52 /// println!("{}", key);
55 /// // Prints `foo`, `bar`, `quux`
56 /// for key in map.values() {
57 /// println!("{}", key);
61 /// assert_eq!(map.len(), 2);
63 /// if !map.contains_key(&1) {
64 /// println!("1 is no more");
67 /// for key in range(0, 4) {
68 /// match map.get(&key) {
69 /// Some(val) => println!("{} has a value: {}", key, val),
70 /// None => println!("{} not in map", key),
75 /// assert!(map.is_empty());
78 /// The easiest way to use `TreeMap` with a custom type as keys is to implement `Ord`.
79 /// We must also implement `PartialEq`, `Eq` and `PartialOrd`.
82 /// use std::collections::TreeMap;
84 /// // We need `Eq` and `PartialEq`, these can be derived.
85 /// #[deriving(Eq, PartialEq)]
86 /// struct Troll<'a> {
91 /// // Implement `Ord` and sort trolls by level.
92 /// impl<'a> Ord for Troll<'a> {
93 /// fn cmp(&self, other: &Troll) -> Ordering {
94 /// // If we swap `self` and `other`, we get descending ordering.
95 /// self.level.cmp(&other.level)
99 /// // `PartialOrd` needs to be implemented as well.
100 /// impl<'a> PartialOrd for Troll<'a> {
101 /// fn partial_cmp(&self, other: &Troll) -> Option<Ordering> {
102 /// Some(self.cmp(other))
106 /// // Use a map to store trolls, sorted by level, and track a list of
108 /// let mut trolls = TreeMap::new();
110 /// trolls.insert(Troll { name: "Orgarr", level: 2 },
111 /// vec!["King Karl"]);
112 /// trolls.insert(Troll { name: "Blargarr", level: 3 },
114 /// trolls.insert(Troll { name: "Kron the Smelly One", level: 4 },
115 /// vec!["Omar the Brave", "Peter: Slayer of Trolls"]);
116 /// trolls.insert(Troll { name: "Wartilda", level: 1 },
119 /// println!("You are facing {} trolls!", trolls.len());
121 /// // Print the trolls, ordered by level with smallest level first
122 /// for (troll, heroes) in trolls.iter() {
123 /// let what = if heroes.len() == 1u { "hero" }
124 /// else { "heroes" };
126 /// println!("level {}: '{}' has slain {} {}",
127 /// troll.level, troll.name, heroes.len(), what);
130 /// // Kill all trolls
132 /// assert_eq!(trolls.len(), 0);
135 // Future improvements:
137 // range search - O(log n) retrieval of an iterator from some key
139 // (possibly) implement the overloads Python does for sets:
142 // * symmetric difference: ^
144 // These would be convenient since the methods work like `each`
147 pub struct TreeMap<K, V> {
148 root: Option<Box<TreeNode<K, V>>>,
152 impl<K: PartialEq + Ord, V: PartialEq> PartialEq for TreeMap<K, V> {
153 fn eq(&self, other: &TreeMap<K, V>) -> bool {
154 self.len() == other.len() &&
155 self.iter().zip(other.iter()).all(|(a, b)| a == b)
159 impl<K: Eq + Ord, V: Eq> Eq for TreeMap<K, V> {}
161 impl<K: Ord, V: PartialOrd> PartialOrd for TreeMap<K, V> {
163 fn partial_cmp(&self, other: &TreeMap<K, V>) -> Option<Ordering> {
164 iter::order::partial_cmp(self.iter(), other.iter())
168 impl<K: Ord, V: Ord> Ord for TreeMap<K, V> {
170 fn cmp(&self, other: &TreeMap<K, V>) -> Ordering {
171 iter::order::cmp(self.iter(), other.iter())
175 impl<K: Ord + Show, V: Show> Show for TreeMap<K, V> {
176 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
177 try!(write!(f, "{{"));
179 for (i, (k, v)) in self.iter().enumerate() {
180 if i != 0 { try!(write!(f, ", ")); }
181 try!(write!(f, "{}: {}", *k, *v));
188 impl<K: Ord, V> Default for TreeMap<K,V> {
190 fn default() -> TreeMap<K, V> { TreeMap::new() }
193 impl<K: Ord, Sized? Q, V> Index<Q, V> for TreeMap<K, V> where Q: BorrowFrom<K> + Ord {
195 fn index<'a>(&'a self, i: &Q) -> &'a V {
196 self.get(i).expect("no entry found for key")
200 impl<K: Ord, Sized? Q, V> IndexMut<Q, V> for TreeMap<K, V> where Q: BorrowFrom<K> + Ord {
202 fn index_mut<'a>(&'a mut self, i: &Q) -> &'a mut V {
203 self.get_mut(i).expect("no entry found for key")
207 impl<K: Ord, V> TreeMap<K, V> {
208 /// Creates an empty `TreeMap`.
213 /// use std::collections::TreeMap;
214 /// let mut map: TreeMap<&str, int> = TreeMap::new();
216 #[unstable = "matches collection reform specification, waiting for dust to settle"]
217 pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
219 /// Gets a lazy iterator over the keys in the map, in ascending order.
224 /// use std::collections::TreeMap;
225 /// let mut map = TreeMap::new();
226 /// map.insert("a", 1i);
227 /// map.insert("c", 3i);
228 /// map.insert("b", 2i);
230 /// // Print "a", "b", "c" in order.
231 /// for x in map.keys() {
232 /// println!("{}", x);
235 #[unstable = "matches collection reform specification, waiting for dust to settle"]
236 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
237 self.iter().map(|(k, _v)| k)
240 /// Gets a lazy iterator over the values in the map, in ascending order
241 /// with respect to the corresponding keys.
246 /// use std::collections::TreeMap;
247 /// let mut map = TreeMap::new();
248 /// map.insert("a", 1i);
249 /// map.insert("c", 3i);
250 /// map.insert("b", 2i);
252 /// // Print 1, 2, 3 ordered by keys.
253 /// for x in map.values() {
254 /// println!("{}", x);
257 #[unstable = "matches collection reform specification, waiting for dust to settle"]
258 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
259 self.iter().map(|(_k, v)| v)
262 /// Gets a lazy iterator over the key-value pairs in the map, in ascending order.
267 /// use std::collections::TreeMap;
268 /// let mut map = TreeMap::new();
269 /// map.insert("a", 1i);
270 /// map.insert("c", 3i);
271 /// map.insert("b", 2i);
273 /// // Print contents in ascending order
274 /// for (key, value) in map.iter() {
275 /// println!("{}: {}", key, value);
278 #[unstable = "matches collection reform specification, waiting for dust to settle"]
279 pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
282 node: deref(&self.root),
283 remaining_min: self.length,
284 remaining_max: self.length
288 /// Gets a lazy reverse iterator over the key-value pairs in the map, in descending order.
293 /// use std::collections::TreeMap;
294 /// let mut map = TreeMap::new();
295 /// map.insert("a", 1i);
296 /// map.insert("c", 3i);
297 /// map.insert("b", 2i);
299 /// // Print contents in descending order
300 /// for (key, value) in map.rev_iter() {
301 /// println!("{}: {}", key, value);
304 pub fn rev_iter<'a>(&'a self) -> RevEntries<'a, K, V> {
305 RevEntries{iter: self.iter()}
308 /// Gets a lazy forward iterator over the key-value pairs in the
309 /// map, with the values being mutable.
314 /// use std::collections::TreeMap;
315 /// let mut map = TreeMap::new();
316 /// map.insert("a", 1i);
317 /// map.insert("c", 3i);
318 /// map.insert("b", 2i);
320 /// // Add 10 until we find "b"
321 /// for (key, value) in map.iter_mut() {
323 /// if key == &"b" { break }
326 /// assert_eq!(map.get(&"a"), Some(&11));
327 /// assert_eq!(map.get(&"b"), Some(&12));
328 /// assert_eq!(map.get(&"c"), Some(&3));
330 #[unstable = "matches collection reform specification, waiting for dust to settle"]
331 pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, K, V> {
334 node: deref_mut(&mut self.root),
335 remaining_min: self.length,
336 remaining_max: self.length
340 /// Gets a lazy reverse iterator over the key-value pairs in the
341 /// map, with the values being mutable.
346 /// use std::collections::TreeMap;
347 /// let mut map = TreeMap::new();
348 /// map.insert("a", 1i);
349 /// map.insert("c", 3i);
350 /// map.insert("b", 2i);
352 /// // Add 10 until we find "b"
353 /// for (key, value) in map.rev_iter_mut() {
355 /// if key == &"b" { break }
358 /// assert_eq!(map.get(&"a"), Some(&1));
359 /// assert_eq!(map.get(&"b"), Some(&12));
360 /// assert_eq!(map.get(&"c"), Some(&13));
362 pub fn rev_iter_mut<'a>(&'a mut self) -> RevMutEntries<'a, K, V> {
363 RevMutEntries{iter: self.iter_mut()}
366 /// Gets a lazy iterator that consumes the treemap.
371 /// use std::collections::TreeMap;
372 /// let mut map = TreeMap::new();
373 /// map.insert("a", 1i);
374 /// map.insert("c", 3i);
375 /// map.insert("b", 2i);
377 /// // Not possible with a regular `.iter()`
378 /// let vec: Vec<(&str, int)> = map.into_iter().collect();
379 /// assert_eq!(vec, vec![("a", 1), ("b", 2), ("c", 3)]);
381 #[unstable = "matches collection reform specification, waiting for dust to settle"]
382 pub fn into_iter(self) -> MoveEntries<K, V> {
383 let TreeMap { root, length } = self;
384 let stk = match root {
386 Some(box tn) => vec!(tn)
394 /// Return the number of elements in the map.
399 /// use std::collections::TreeMap;
401 /// let mut a = TreeMap::new();
402 /// assert_eq!(a.len(), 0);
403 /// a.insert(1u, "a");
404 /// assert_eq!(a.len(), 1);
406 #[unstable = "matches collection reform specification, waiting for dust to settle"]
407 pub fn len(&self) -> uint { self.length }
409 /// Return true if the map contains no elements.
414 /// use std::collections::TreeMap;
416 /// let mut a = TreeMap::new();
417 /// assert!(a.is_empty());
418 /// a.insert(1u, "a");
419 /// assert!(!a.is_empty());
421 #[unstable = "matches collection reform specification, waiting for dust to settle"]
423 pub fn is_empty(&self) -> bool { self.len() == 0 }
425 /// Clears the map, removing all values.
430 /// use std::collections::TreeMap;
432 /// let mut a = TreeMap::new();
433 /// a.insert(1u, "a");
435 /// assert!(a.is_empty());
437 #[unstable = "matches collection reform specification, waiting for dust to settle"]
438 pub fn clear(&mut self) {
443 /// Deprecated: Renamed to `get`.
444 #[deprecated = "Renamed to `get`"]
445 pub fn find(&self, key: &K) -> Option<&V> {
449 /// Returns a reference to the value corresponding to the key.
451 /// The key may be any borrowed form of the map's key type, but the ordering
452 /// on the borrowed form *must* match the ordering on the key type.
457 /// use std::collections::TreeMap;
459 /// let mut map = TreeMap::new();
460 /// map.insert(1u, "a");
461 /// assert_eq!(map.get(&1), Some(&"a"));
462 /// assert_eq!(map.get(&2), None);
465 #[unstable = "matches collection reform specification, waiting for dust to settle"]
466 pub fn get<Sized? Q>(&self, key: &Q) -> Option<&V>
467 where Q: BorrowFrom<K> + Ord
469 tree_find_with(&self.root, |k2| key.cmp(BorrowFrom::borrow_from(k2)))
472 /// Returns true if the map contains a value for the specified key.
474 /// The key may be any borrowed form of the map's key type, but the ordering
475 /// on the borrowed form *must* match the ordering on the key type.
480 /// use std::collections::TreeMap;
482 /// let mut map = TreeMap::new();
483 /// map.insert(1u, "a");
484 /// assert_eq!(map.contains_key(&1), true);
485 /// assert_eq!(map.contains_key(&2), false);
488 #[unstable = "matches collection reform specification, waiting for dust to settle"]
489 pub fn contains_key<Sized? Q>(&self, key: &Q) -> bool
490 where Q: BorrowFrom<K> + Ord
492 self.get(key).is_some()
495 /// Deprecated: Renamed to `get_mut`.
496 #[deprecated = "Renamed to `get_mut`"]
497 pub fn find_mut(&mut self, key: &K) -> Option<&mut V> {
501 /// Returns a mutable reference to the value corresponding to the key.
503 /// The key may be any borrowed form of the map's key type, but the ordering
504 /// on the borrowed form *must* match the ordering on the key type.
509 /// use std::collections::TreeMap;
511 /// let mut map = TreeMap::new();
512 /// map.insert(1u, "a");
513 /// match map.get_mut(&1) {
514 /// Some(x) => *x = "b",
517 /// assert_eq!(map[1], "b");
520 #[unstable = "matches collection reform specification, waiting for dust to settle"]
521 pub fn get_mut<Sized? Q>(&mut self, key: &Q) -> Option<&mut V>
522 where Q: BorrowFrom<K> + Ord
524 tree_find_with_mut(&mut self.root, |x| key.cmp(BorrowFrom::borrow_from(x)))
527 /// Deprecated: Renamed to `insert`.
528 #[deprecated = "Renamed to `insert`"]
529 pub fn swap(&mut self, key: K, value: V) -> Option<V> {
530 self.insert(key, value)
533 /// Inserts a key-value pair from the map. If the key already had a value
534 /// present in the map, that value is returned. Otherwise, `None` is returned.
539 /// use std::collections::TreeMap;
541 /// let mut map = TreeMap::new();
542 /// assert_eq!(map.insert(37u, "a"), None);
543 /// assert_eq!(map.is_empty(), false);
545 /// map.insert(37, "b");
546 /// assert_eq!(map.insert(37, "c"), Some("b"));
547 /// assert_eq!(map[37], "c");
549 #[unstable = "matches collection reform specification, waiting for dust to settle"]
550 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
551 let ret = insert(&mut self.root, key, value);
552 if ret.is_none() { self.length += 1 }
556 /// Deprecated: Renamed to `remove`.
557 #[deprecated = "Renamed to `remove`"]
558 pub fn pop(&mut self, key: &K) -> Option<V> {
562 /// Removes a key from the map, returning the value at the key if the key
563 /// was previously in the map.
565 /// The key may be any borrowed form of the map's key type, but the ordering
566 /// on the borrowed form *must* match the ordering on the key type.
571 /// use std::collections::TreeMap;
573 /// let mut map = TreeMap::new();
574 /// map.insert(1u, "a");
575 /// assert_eq!(map.remove(&1), Some("a"));
576 /// assert_eq!(map.remove(&1), None);
578 #[unstable = "matches collection reform specification, waiting for dust to settle"]
579 pub fn remove<Sized? Q>(&mut self, key: &Q) -> Option<V>
580 where Q: BorrowFrom<K> + Ord
582 let ret = remove(&mut self.root, key);
583 if ret.is_some() { self.length -= 1 }
588 impl<K, V> TreeMap<K, V> {
589 /// Returns the value for which `f(key)` returns `Equal`. `f` is invoked
590 /// with current key and guides tree navigation. That means `f` should
591 /// be aware of natural ordering of the tree.
596 /// use collections::tree_map::TreeMap;
598 /// fn get_headers() -> TreeMap<String, String> {
599 /// let mut result = TreeMap::new();
600 /// result.insert("Content-Type".to_string(), "application/xml".to_string());
601 /// result.insert("User-Agent".to_string(), "Curl-Rust/0.1".to_string());
605 /// let headers = get_headers();
606 /// let ua_key = "User-Agent";
607 /// let ua = headers.find_with(|k| {
608 /// ua_key.cmp(k.as_slice())
611 /// assert_eq!((*ua.unwrap()).as_slice(), "Curl-Rust/0.1");
614 #[experimental = "likely to be renamed, may be removed"]
615 pub fn find_with(&self, f:|&K| -> Ordering) -> Option<&V> {
616 tree_find_with(&self.root, f)
619 /// Returns the value for which `f(key)` returns `Equal`. `f` is invoked
620 /// with current key and guides tree navigation. That means `f` should
621 /// be aware of natural ordering of the tree.
626 /// let mut t = collections::tree_map::TreeMap::new();
627 /// t.insert("Content-Type", "application/xml");
628 /// t.insert("User-Agent", "Curl-Rust/0.1");
630 /// let new_ua = "Safari/156.0";
631 /// match t.find_with_mut(|&k| "User-Agent".cmp(k)) {
632 /// Some(x) => *x = new_ua,
633 /// None => panic!(),
636 /// assert_eq!(t.get(&"User-Agent"), Some(&new_ua));
639 #[experimental = "likely to be renamed, may be removed"]
640 pub fn find_with_mut<'a>(&'a mut self, f:|&K| -> Ordering) -> Option<&'a mut V> {
641 tree_find_with_mut(&mut self.root, f)
647 macro_rules! bound_setup {
648 // initialiser of the iterator to manipulate
649 ($iter:expr, $k:expr,
650 // whether we are looking for the lower or upper bound.
651 $is_lower_bound:expr) => {
653 let mut iter = $iter;
655 if !iter.node.is_null() {
656 let node_k = unsafe {&(*iter.node).key};
657 match $k.cmp(node_k) {
658 Less => iter.traverse_left(),
659 Greater => iter.traverse_right(),
662 iter.traverse_complete();
665 iter.traverse_right()
670 iter.traverse_complete();
679 impl<K: Ord, V> TreeMap<K, V> {
680 /// Gets a lazy iterator that should be initialized using
681 /// `traverse_left`/`traverse_right`/`traverse_complete`.
682 fn iter_for_traversal<'a>(&'a self) -> Entries<'a, K, V> {
685 node: deref(&self.root),
687 remaining_max: self.length
691 /// Returns a lazy iterator to the first key-value pair whose key is not less than `k`
692 /// If all keys in map are less than `k` an empty iterator is returned.
697 /// use std::collections::TreeMap;
699 /// let mut map = TreeMap::new();
700 /// map.insert(2i, "a");
701 /// map.insert(4, "b");
702 /// map.insert(6, "c");
703 /// map.insert(8, "d");
705 /// assert_eq!(map.lower_bound(&4).next(), Some((&4, &"b")));
706 /// assert_eq!(map.lower_bound(&5).next(), Some((&6, &"c")));
707 /// assert_eq!(map.lower_bound(&10).next(), None);
709 pub fn lower_bound<'a>(&'a self, k: &K) -> Entries<'a, K, V> {
710 bound_setup!(self.iter_for_traversal(), k, true)
713 /// Returns a lazy iterator to the first key-value pair whose key is greater than `k`
714 /// If all keys in map are less than or equal to `k` an empty iterator is returned.
719 /// use std::collections::TreeMap;
721 /// let mut map = TreeMap::new();
722 /// map.insert(2i, "a");
723 /// map.insert(4, "b");
724 /// map.insert(6, "c");
725 /// map.insert(8, "d");
727 /// assert_eq!(map.upper_bound(&4).next(), Some((&6, &"c")));
728 /// assert_eq!(map.upper_bound(&5).next(), Some((&6, &"c")));
729 /// assert_eq!(map.upper_bound(&10).next(), None);
731 pub fn upper_bound<'a>(&'a self, k: &K) -> Entries<'a, K, V> {
732 bound_setup!(self.iter_for_traversal(), k, false)
735 /// Gets a lazy iterator that should be initialized using
736 /// `traverse_left`/`traverse_right`/`traverse_complete`.
737 fn iter_mut_for_traversal<'a>(&'a mut self) -> MutEntries<'a, K, V> {
740 node: deref_mut(&mut self.root),
742 remaining_max: self.length
746 /// Returns a lazy value iterator to the first key-value pair (with
747 /// the value being mutable) whose key is not less than `k`.
749 /// If all keys in map are less than `k` an empty iterator is
755 /// use std::collections::TreeMap;
757 /// let mut map = TreeMap::new();
758 /// map.insert(2i, "a");
759 /// map.insert(4, "b");
760 /// map.insert(6, "c");
761 /// map.insert(8, "d");
763 /// assert_eq!(map.lower_bound_mut(&4).next(), Some((&4, &mut "b")));
764 /// assert_eq!(map.lower_bound_mut(&5).next(), Some((&6, &mut "c")));
765 /// assert_eq!(map.lower_bound_mut(&10).next(), None);
767 /// for (key, value) in map.lower_bound_mut(&4) {
768 /// *value = "changed";
771 /// assert_eq!(map.get(&2), Some(&"a"));
772 /// assert_eq!(map.get(&4), Some(&"changed"));
773 /// assert_eq!(map.get(&6), Some(&"changed"));
774 /// assert_eq!(map.get(&8), Some(&"changed"));
776 pub fn lower_bound_mut<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
777 bound_setup!(self.iter_mut_for_traversal(), k, true)
780 /// Returns a lazy iterator to the first key-value pair (with the
781 /// value being mutable) whose key is greater than `k`.
783 /// If all keys in map are less than or equal to `k` an empty iterator
789 /// use std::collections::TreeMap;
791 /// let mut map = TreeMap::new();
792 /// map.insert(2i, "a");
793 /// map.insert(4, "b");
794 /// map.insert(6, "c");
795 /// map.insert(8, "d");
797 /// assert_eq!(map.upper_bound_mut(&4).next(), Some((&6, &mut "c")));
798 /// assert_eq!(map.upper_bound_mut(&5).next(), Some((&6, &mut "c")));
799 /// assert_eq!(map.upper_bound_mut(&10).next(), None);
801 /// for (key, value) in map.upper_bound_mut(&4) {
802 /// *value = "changed";
805 /// assert_eq!(map.get(&2), Some(&"a"));
806 /// assert_eq!(map.get(&4), Some(&"b"));
807 /// assert_eq!(map.get(&6), Some(&"changed"));
808 /// assert_eq!(map.get(&8), Some(&"changed"));
810 pub fn upper_bound_mut<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
811 bound_setup!(self.iter_mut_for_traversal(), k, false)
815 /// Lazy forward iterator over a map
816 pub struct Entries<'a, K:'a, V:'a> {
817 stack: Vec<&'a TreeNode<K, V>>,
818 // See the comment on MutEntries; this is just to allow
819 // code-sharing (for this immutable-values iterator it *could* very
820 // well be Option<&'a TreeNode<K,V>>).
821 node: *const TreeNode<K, V>,
826 /// Lazy backward iterator over a map
827 pub struct RevEntries<'a, K:'a, V:'a> {
828 iter: Entries<'a, K, V>,
831 /// Lazy forward iterator over a map that allows for the mutation of
833 pub struct MutEntries<'a, K:'a, V:'a> {
834 stack: Vec<&'a mut TreeNode<K, V>>,
835 // Unfortunately, we require some unsafe-ness to get around the
836 // fact that we would be storing a reference *into* one of the
837 // nodes in the stack.
839 // As far as the compiler knows, this would let us invalidate the
840 // reference by assigning a new value to this node's position in
841 // its parent, which would cause this current one to be
842 // deallocated so this reference would be invalid. (i.e. the
843 // compilers complaints are 100% correct.)
845 // However, as far as you humans reading this code know (or are
846 // about to know, if you haven't read far enough down yet), we are
847 // only reading from the TreeNode.{left,right} fields. the only
848 // thing that is ever mutated is the .value field (although any
849 // actual mutation that happens is done externally, by the
850 // iterator consumer). So, don't be so concerned, rustc, we've got
853 // (This field can legitimately be null.)
854 node: *mut TreeNode<K, V>,
859 /// Lazy backward iterator over a map
860 pub struct RevMutEntries<'a, K:'a, V:'a> {
861 iter: MutEntries<'a, K, V>,
864 /// TreeMap keys iterator.
865 pub type Keys<'a, K, V> =
866 iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
868 /// TreeMap values iterator.
869 pub type Values<'a, K, V> =
870 iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
873 // FIXME #5846 we want to be able to choose between &x and &mut x
874 // (with many different `x`) below, so we need to optionally pass mut
875 // as a tt, but the only thing we can do with a `tt` is pass them to
876 // other macros, so this takes the `& <mutability> <operand>` token
877 // sequence and forces their evaluation as an expression.
878 macro_rules! addr { ($e:expr) => { $e }}
879 // putting an optional mut into type signatures
880 macro_rules! item { ($i:item) => { $i }}
882 macro_rules! define_iterator {
886 // the function to go from &m Option<Box<TreeNode>> to *m TreeNode
887 deref = $deref:ident,
889 // see comment on `addr!`, this is just an optional `mut`, but
890 // there's no support for 0-or-1 repeats.
891 addr_mut = $($addr_mut:tt)*
893 // private methods on the forward iterator (item!() for the
894 // addr_mut in the next_ return value)
895 item!(impl<'a, K, V> $name<'a, K, V> {
897 fn next_(&mut self, forward: bool) -> Option<(&'a K, &'a $($addr_mut)* V)> {
898 while !self.stack.is_empty() || !self.node.is_null() {
899 if !self.node.is_null() {
900 let node = unsafe {addr!(& $($addr_mut)* *self.node)};
902 let next_node = if forward {
903 addr!(& $($addr_mut)* node.left)
905 addr!(& $($addr_mut)* node.right)
907 self.node = $deref(next_node);
909 self.stack.push(node);
911 let node = self.stack.pop().unwrap();
912 let next_node = if forward {
913 addr!(& $($addr_mut)* node.right)
915 addr!(& $($addr_mut)* node.left)
917 self.node = $deref(next_node);
918 self.remaining_max -= 1;
919 if self.remaining_min > 0 {
920 self.remaining_min -= 1;
922 return Some((&node.key, addr!(& $($addr_mut)* node.value)));
928 /// traverse_left, traverse_right and traverse_complete are
929 /// used to initialize Entries/MutEntries
930 /// pointing to element inside tree structure.
932 /// They should be used in following manner:
933 /// - create iterator using TreeMap::[mut_]iter_for_traversal
934 /// - find required node using `traverse_left`/`traverse_right`
935 /// (current node is `Entries::node` field)
936 /// - complete initialization with `traverse_complete`
938 /// After this, iteration will start from `self.node`. If
939 /// `self.node` is None iteration will start from last
940 /// node from which we traversed left.
942 fn traverse_left(&mut self) {
943 let node = unsafe {addr!(& $($addr_mut)* *self.node)};
944 self.node = $deref(addr!(& $($addr_mut)* node.left));
945 self.stack.push(node);
949 fn traverse_right(&mut self) {
950 let node = unsafe {addr!(& $($addr_mut)* *self.node)};
951 self.node = $deref(addr!(& $($addr_mut)* node.right));
955 fn traverse_complete(&mut self) {
956 if !self.node.is_null() {
958 self.stack.push(addr!(& $($addr_mut)* *self.node));
960 self.node = ptr::RawPtr::null();
965 // the forward Iterator impl.
966 item!(impl<'a, K, V> Iterator<(&'a K, &'a $($addr_mut)* V)> for $name<'a, K, V> {
967 /// Advances the iterator to the next node (in order) and return a
968 /// tuple with a reference to the key and value. If there are no
969 /// more nodes, return `None`.
970 fn next(&mut self) -> Option<(&'a K, &'a $($addr_mut)* V)> {
975 fn size_hint(&self) -> (uint, Option<uint>) {
976 (self.remaining_min, Some(self.remaining_max))
980 // the reverse Iterator impl.
981 item!(impl<'a, K, V> Iterator<(&'a K, &'a $($addr_mut)* V)> for $rev_name<'a, K, V> {
982 fn next(&mut self) -> Option<(&'a K, &'a $($addr_mut)* V)> {
983 self.iter.next_(false)
987 fn size_hint(&self) -> (uint, Option<uint>) {
988 self.iter.size_hint()
992 } // end of define_iterator
999 // immutable, so no mut
1010 fn deref<'a, K, V>(node: &'a Option<Box<TreeNode<K, V>>>) -> *const TreeNode<K, V> {
1013 let n: &TreeNode<K, V> = &**n;
1014 n as *const TreeNode<K, V>
1020 fn deref_mut<K, V>(x: &mut Option<Box<TreeNode<K, V>>>)
1021 -> *mut TreeNode<K, V> {
1023 Some(ref mut n) => {
1024 let n: &mut TreeNode<K, V> = &mut **n;
1025 n as *mut TreeNode<K, V>
1027 None => ptr::null_mut()
1031 /// Lazy forward iterator over a map that consumes the map while iterating
1032 pub struct MoveEntries<K, V> {
1033 stack: Vec<TreeNode<K, V>>,
1037 impl<K, V> Iterator<(K, V)> for MoveEntries<K,V> {
1039 fn next(&mut self) -> Option<(K, V)> {
1040 while !self.stack.is_empty() {
1047 } = self.stack.pop().unwrap();
1059 self.stack.push(left);
1063 Some(box right) => self.stack.push(right),
1066 self.remaining -= 1;
1067 return Some((key, value))
1075 fn size_hint(&self) -> (uint, Option<uint>) {
1076 (self.remaining, Some(self.remaining))
1083 // Nodes keep track of their level in the tree, starting at 1 in the
1084 // leaves and with a red child sharing the level of the parent.
1086 struct TreeNode<K, V> {
1089 left: Option<Box<TreeNode<K, V>>>,
1090 right: Option<Box<TreeNode<K, V>>>,
1094 impl<K: Ord, V> TreeNode<K, V> {
1095 /// Creates a new tree node.
1097 pub fn new(key: K, value: V) -> TreeNode<K, V> {
1098 TreeNode{key: key, value: value, left: None, right: None, level: 1}
1102 // Remove left horizontal link by rotating right
1103 fn skew<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
1104 if node.left.as_ref().map_or(false, |x| x.level == node.level) {
1105 let mut save = node.left.take().unwrap();
1106 swap(&mut node.left, &mut save.right); // save.right now None
1107 swap(node, &mut save);
1108 node.right = Some(save);
1112 // Remove dual horizontal link by rotating left and increasing level of
1114 fn split<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
1115 if node.right.as_ref().map_or(false,
1116 |x| x.right.as_ref().map_or(false, |y| y.level == node.level)) {
1117 let mut save = node.right.take().unwrap();
1118 swap(&mut node.right, &mut save.left); // save.left now None
1120 swap(node, &mut save);
1121 node.left = Some(save);
1125 // Next 2 functions have the same convention: comparator gets
1126 // at input current key and returns search_key cmp cur_key
1127 // (i.e. search_key.cmp(&cur_key))
1128 fn tree_find_with<'r, K, V>(node: &'r Option<Box<TreeNode<K, V>>>,
1129 f: |&K| -> Ordering) -> Option<&'r V> {
1130 let mut current: &'r Option<Box<TreeNode<K, V>>> = node;
1135 Less => current = &r.left,
1136 Greater => current = &r.right,
1137 Equal => return Some(&r.value)
1145 // See comments above tree_find_with
1146 fn tree_find_with_mut<'r, K, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
1147 f: |&K| -> Ordering) -> Option<&'r mut V> {
1149 let mut current = node;
1151 let temp = current; // hack to appease borrowck
1153 Some(ref mut r) => {
1155 Less => current = &mut r.left,
1156 Greater => current = &mut r.right,
1157 Equal => return Some(&mut r.value)
1165 fn insert<K: Ord, V>(node: &mut Option<Box<TreeNode<K, V>>>,
1166 key: K, value: V) -> Option<V> {
1168 Some(ref mut save) => {
1169 match key.cmp(&save.key) {
1171 let inserted = insert(&mut save.left, key, value);
1177 let inserted = insert(&mut save.right, key, value);
1184 Some(replace(&mut save.value, value))
1189 *node = Some(box TreeNode::new(key, value));
1195 fn remove<K, Sized? Q, V>(node: &mut Option<Box<TreeNode<K, V>>>, key: &Q) -> Option<V>
1196 where K: Ord, Q: BorrowFrom<K> + Ord
1198 fn heir_swap<K: Ord, V>(node: &mut Box<TreeNode<K, V>>,
1199 child: &mut Option<Box<TreeNode<K, V>>>) {
1200 // *could* be done without recursion, but it won't borrow check
1201 for x in child.iter_mut() {
1202 if x.right.is_some() {
1203 heir_swap(node, &mut x.right);
1205 swap(&mut node.key, &mut x.key);
1206 swap(&mut node.value, &mut x.value);
1213 return None; // bottom of tree
1215 Some(ref mut save) => {
1216 let (ret, rebalance) = match key.cmp(BorrowFrom::borrow_from(&save.key)) {
1217 Less => (remove(&mut save.left, key), true),
1218 Greater => (remove(&mut save.right, key), true),
1220 if save.left.is_some() {
1221 if save.right.is_some() {
1222 let mut left = save.left.take().unwrap();
1223 if left.right.is_some() {
1224 heir_swap(save, &mut left.right);
1226 swap(&mut save.key, &mut left.key);
1227 swap(&mut save.value, &mut left.value);
1229 save.left = Some(left);
1230 (remove(&mut save.left, key), true)
1232 let new = save.left.take().unwrap();
1233 let box TreeNode{value, ..} = replace(save, new);
1234 *save = save.left.take().unwrap();
1237 } else if save.right.is_some() {
1238 let new = save.right.take().unwrap();
1239 let box TreeNode{value, ..} = replace(save, new);
1248 let left_level = save.left.as_ref().map_or(0, |x| x.level);
1249 let right_level = save.right.as_ref().map_or(0, |x| x.level);
1251 // re-balance, if necessary
1252 if left_level < save.level - 1 || right_level < save.level - 1 {
1255 if right_level > save.level {
1256 let save_level = save.level;
1257 for x in save.right.iter_mut() { x.level = save_level }
1262 for right in save.right.iter_mut() {
1264 for x in right.right.iter_mut() { skew(x) }
1268 for x in save.right.iter_mut() { split(x) }
1275 return match node.take() {
1276 Some(box TreeNode{value, ..}) => Some(value), None => panic!()
1280 impl<K: Ord, V> FromIterator<(K, V)> for TreeMap<K, V> {
1281 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> TreeMap<K, V> {
1282 let mut map = TreeMap::new();
1288 impl<K: Ord, V> Extend<(K, V)> for TreeMap<K, V> {
1290 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1291 for (k, v) in iter {
1297 impl<S: Writer, K: Ord + Hash<S>, V: Hash<S>> Hash<S> for TreeMap<K, V> {
1298 fn hash(&self, state: &mut S) {
1299 for elt in self.iter() {
1308 use std::prelude::*;
1312 use super::{TreeMap, TreeNode};
1316 let m: TreeMap<int,int> = TreeMap::new();
1317 assert!(m.get(&5) == None);
1321 fn find_not_found() {
1322 let mut m = TreeMap::new();
1323 assert!(m.insert(1i, 2i).is_none());
1324 assert!(m.insert(5i, 3i).is_none());
1325 assert!(m.insert(9i, 3i).is_none());
1326 assert_eq!(m.get(&2), None);
1330 fn find_with_empty() {
1331 let m: TreeMap<&'static str,int> = TreeMap::new();
1332 assert!(m.find_with(|&k| "test".cmp(k)) == None);
1336 fn find_with_not_found() {
1337 let mut m = TreeMap::new();
1338 assert!(m.insert("test1", 2i).is_none());
1339 assert!(m.insert("test2", 3i).is_none());
1340 assert!(m.insert("test3", 3i).is_none());
1341 assert_eq!(m.find_with(|&k| "test4".cmp(k)), None);
1345 fn find_with_found() {
1346 let mut m = TreeMap::new();
1347 assert!(m.insert("test1", 2i).is_none());
1348 assert!(m.insert("test2", 3i).is_none());
1349 assert!(m.insert("test3", 4i).is_none());
1350 assert_eq!(m.find_with(|&k| "test2".cmp(k)), Some(&3i));
1354 fn test_find_mut() {
1355 let mut m = TreeMap::new();
1356 assert!(m.insert(1i, 12i).is_none());
1357 assert!(m.insert(2, 8).is_none());
1358 assert!(m.insert(5, 14).is_none());
1360 match m.get_mut(&5) {
1361 None => panic!(), Some(x) => *x = new
1363 assert_eq!(m.get(&5), Some(&new));
1367 fn test_find_with_mut() {
1368 let mut m = TreeMap::new();
1369 assert!(m.insert("t1", 12i).is_none());
1370 assert!(m.insert("t2", 8).is_none());
1371 assert!(m.insert("t5", 14).is_none());
1374 match m.find_with_mut(|&k| "t5".cmp(k)) {
1375 None => panic!(), Some(x) => *x = new
1377 assert_eq!(m.find_with(|&k| "t5".cmp(k)), Some(&new));
1381 fn insert_replace() {
1382 let mut m = TreeMap::new();
1383 assert!(m.insert(5i, 2i).is_none());
1384 assert!(m.insert(2, 9).is_none());
1385 assert!(!m.insert(2, 11).is_none());
1386 assert_eq!(m.get(&2).unwrap(), &11);
1391 let mut m = TreeMap::new();
1393 assert!(m.insert(5i, 11i).is_none());
1394 assert!(m.insert(12, -3).is_none());
1395 assert!(m.insert(19, 2).is_none());
1397 assert!(m.get(&5).is_none());
1398 assert!(m.get(&12).is_none());
1399 assert!(m.get(&19).is_none());
1400 assert!(m.is_empty());
1405 let mut m = TreeMap::new();
1407 let k1 = "foo".as_bytes();
1408 let k2 = "bar".as_bytes();
1409 let v1 = "baz".as_bytes();
1410 let v2 = "foobar".as_bytes();
1412 m.insert(k1.clone(), v1.clone());
1413 m.insert(k2.clone(), v2.clone());
1415 assert_eq!(m.get(&k2), Some(&v2));
1416 assert_eq!(m.get(&k1), Some(&v1));
1419 fn check_equal<K: PartialEq + Ord, V: PartialEq>(ctrl: &[(K, V)],
1420 map: &TreeMap<K, V>) {
1421 assert_eq!(ctrl.is_empty(), map.is_empty());
1422 for x in ctrl.iter() {
1423 let &(ref k, ref v) = x;
1424 assert!(map.get(k).unwrap() == v)
1426 for (map_k, map_v) in map.iter() {
1427 let mut found = false;
1428 for x in ctrl.iter() {
1429 let &(ref ctrl_k, ref ctrl_v) = x;
1430 if *map_k == *ctrl_k {
1431 assert!(*map_v == *ctrl_v);
1440 fn check_left<K: Ord, V>(node: &Option<Box<TreeNode<K, V>>>,
1441 parent: &Box<TreeNode<K, V>>) {
1444 assert_eq!(r.key.cmp(&parent.key), Less);
1445 assert!(r.level == parent.level - 1); // left is black
1446 check_left(&r.left, r);
1447 check_right(&r.right, r, false);
1449 None => assert!(parent.level == 1) // parent is leaf
1453 fn check_right<K: Ord, V>(node: &Option<Box<TreeNode<K, V>>>,
1454 parent: &Box<TreeNode<K, V>>,
1458 assert_eq!(r.key.cmp(&parent.key), Greater);
1459 let red = r.level == parent.level;
1460 if parent_red { assert!(!red) } // no dual horizontal links
1461 // Right red or black
1462 assert!(red || r.level == parent.level - 1);
1463 check_left(&r.left, r);
1464 check_right(&r.right, r, red);
1466 None => assert!(parent.level == 1) // parent is leaf
1470 fn check_structure<K: Ord, V>(map: &TreeMap<K, V>) {
1473 check_left(&r.left, r);
1474 check_right(&r.right, r, false);
1481 fn test_rand_int() {
1482 let mut map: TreeMap<int,int> = TreeMap::new();
1483 let mut ctrl = vec![];
1485 check_equal(ctrl.as_slice(), &map);
1486 assert!(map.get(&5).is_none());
1488 let seed: &[_] = &[42];
1489 let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
1491 for _ in range(0u, 3) {
1492 for _ in range(0u, 90) {
1495 if !ctrl.iter().any(|x| x == &(k, v)) {
1496 assert!(map.insert(k, v).is_none());
1498 check_structure(&map);
1499 check_equal(ctrl.as_slice(), &map);
1503 for _ in range(0u, 30) {
1504 let r = rng.gen_range(0, ctrl.len());
1505 let (key, _) = ctrl.remove(r).unwrap();
1506 assert!(map.remove(&key).is_some());
1507 check_structure(&map);
1508 check_equal(ctrl.as_slice(), &map);
1515 let mut m = TreeMap::new();
1516 assert!(m.insert(3i, 6i).is_none());
1517 assert_eq!(m.len(), 1);
1518 assert!(m.insert(0, 0).is_none());
1519 assert_eq!(m.len(), 2);
1520 assert!(m.insert(4, 8).is_none());
1521 assert_eq!(m.len(), 3);
1522 assert!(m.remove(&3).is_some());
1523 assert_eq!(m.len(), 2);
1524 assert!(!m.remove(&5).is_some());
1525 assert_eq!(m.len(), 2);
1526 assert!(m.insert(2, 4).is_none());
1527 assert_eq!(m.len(), 3);
1528 assert!(m.insert(1, 2).is_none());
1529 assert_eq!(m.len(), 4);
1533 fn test_iterator() {
1534 let mut m = TreeMap::new();
1536 assert!(m.insert(3i, 6i).is_none());
1537 assert!(m.insert(0, 0).is_none());
1538 assert!(m.insert(4, 8).is_none());
1539 assert!(m.insert(2, 4).is_none());
1540 assert!(m.insert(1, 2).is_none());
1543 for (k, v) in m.iter() {
1545 assert_eq!(*v, n * 2);
1552 fn test_interval_iteration() {
1553 let mut m = TreeMap::new();
1554 for i in range(1i, 100i) {
1555 assert!(m.insert(i * 2, i * 4).is_none());
1558 for i in range(1i, 198i) {
1559 let mut lb_it = m.lower_bound(&i);
1560 let (&k, &v) = lb_it.next().unwrap();
1563 assert_eq!(lb * 2, v);
1565 let mut ub_it = m.upper_bound(&i);
1566 let (&k, &v) = ub_it.next().unwrap();
1567 let ub = i + 2 - i % 2;
1569 assert_eq!(ub * 2, v);
1571 let mut end_it = m.lower_bound(&199);
1572 assert_eq!(end_it.next(), None);
1576 fn test_rev_iter() {
1577 let mut m = TreeMap::new();
1579 assert!(m.insert(3i, 6i).is_none());
1580 assert!(m.insert(0, 0).is_none());
1581 assert!(m.insert(4, 8).is_none());
1582 assert!(m.insert(2, 4).is_none());
1583 assert!(m.insert(1, 2).is_none());
1586 for (k, v) in m.rev_iter() {
1588 assert_eq!(*v, n * 2);
1594 fn test_mut_iter() {
1595 let mut m = TreeMap::new();
1596 for i in range(0u, 10) {
1597 assert!(m.insert(i, 100 * i).is_none());
1600 for (i, (&k, v)) in m.iter_mut().enumerate() {
1601 *v += k * 10 + i; // 000 + 00 + 0, 100 + 10 + 1, ...
1604 for (&k, &v) in m.iter() {
1605 assert_eq!(v, 111 * k);
1609 fn test_mut_rev_iter() {
1610 let mut m = TreeMap::new();
1611 for i in range(0u, 10) {
1612 assert!(m.insert(i, 100 * i).is_none());
1615 for (i, (&k, v)) in m.rev_iter_mut().enumerate() {
1616 *v += k * 10 + (9 - i); // 900 + 90 + (9 - 0), 800 + 80 + (9 - 1), ...
1619 for (&k, &v) in m.iter() {
1620 assert_eq!(v, 111 * k);
1625 fn test_mut_interval_iter() {
1626 let mut m_lower = TreeMap::new();
1627 let mut m_upper = TreeMap::new();
1628 for i in range(1i, 100i) {
1629 assert!(m_lower.insert(i * 2, i * 4).is_none());
1630 assert!(m_upper.insert(i * 2, i * 4).is_none());
1633 for i in range(1i, 199) {
1634 let mut lb_it = m_lower.lower_bound_mut(&i);
1635 let (&k, v) = lb_it.next().unwrap();
1640 for i in range(0i, 198) {
1641 let mut ub_it = m_upper.upper_bound_mut(&i);
1642 let (&k, v) = ub_it.next().unwrap();
1643 let ub = i + 2 - i % 2;
1648 assert!(m_lower.lower_bound_mut(&199).next().is_none());
1650 assert!(m_upper.upper_bound_mut(&198).next().is_none());
1652 assert!(m_lower.iter().all(|(_, &x)| x == 0));
1653 assert!(m_upper.iter().all(|(_, &x)| x == 0));
1658 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1659 let map = vec.into_iter().collect::<TreeMap<int, char>>();
1660 let keys = map.keys().map(|&k| k).collect::<Vec<int>>();
1661 assert_eq!(keys.len(), 3);
1662 assert!(keys.contains(&1));
1663 assert!(keys.contains(&2));
1664 assert!(keys.contains(&3));
1669 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1670 let map = vec.into_iter().collect::<TreeMap<int, char>>();
1671 let values = map.values().map(|&v| v).collect::<Vec<char>>();
1672 assert_eq!(values.len(), 3);
1673 assert!(values.contains(&'a'));
1674 assert!(values.contains(&'b'));
1675 assert!(values.contains(&'c'));
1680 let mut a = TreeMap::new();
1681 let mut b = TreeMap::new();
1684 assert!(a.insert(0i, 5i).is_none());
1686 assert!(b.insert(0, 4).is_none());
1688 assert!(a.insert(5, 19).is_none());
1690 assert!(!b.insert(0, 5).is_none());
1692 assert!(b.insert(5, 19).is_none());
1698 let mut a = TreeMap::new();
1699 let mut b = TreeMap::new();
1701 assert!(!(a < b) && !(b < a));
1702 assert!(b.insert(0i, 5i).is_none());
1704 assert!(a.insert(0, 7).is_none());
1705 assert!(!(a < b) && b < a);
1706 assert!(b.insert(-2, 0).is_none());
1708 assert!(a.insert(-5, 2).is_none());
1710 assert!(a.insert(6, 2).is_none());
1711 assert!(a < b && !(b < a));
1716 let mut a = TreeMap::new();
1717 let mut b = TreeMap::new();
1719 assert!(a <= b && a >= b);
1720 assert!(a.insert(1i, 1i).is_none());
1721 assert!(a > b && a >= b);
1722 assert!(b < a && b <= a);
1723 assert!(b.insert(2, 2).is_none());
1724 assert!(b > a && b >= a);
1725 assert!(a < b && a <= b);
1730 let mut map: TreeMap<int, int> = TreeMap::new();
1731 let empty: TreeMap<int, int> = TreeMap::new();
1736 let map_str = format!("{}", map);
1738 assert!(map_str == "{1: 2, 3: 4}".to_string());
1739 assert_eq!(format!("{}", empty), "{}".to_string());
1743 fn test_lazy_iterator() {
1744 let mut m = TreeMap::new();
1745 let (x1, y1) = (2i, 5i);
1746 let (x2, y2) = (9, 12);
1747 let (x3, y3) = (20, -3);
1748 let (x4, y4) = (29, 5);
1749 let (x5, y5) = (103, 3);
1751 assert!(m.insert(x1, y1).is_none());
1752 assert!(m.insert(x2, y2).is_none());
1753 assert!(m.insert(x3, y3).is_none());
1754 assert!(m.insert(x4, y4).is_none());
1755 assert!(m.insert(x5, y5).is_none());
1758 let mut a = m.iter();
1760 assert_eq!(a.next().unwrap(), (&x1, &y1));
1761 assert_eq!(a.next().unwrap(), (&x2, &y2));
1762 assert_eq!(a.next().unwrap(), (&x3, &y3));
1763 assert_eq!(a.next().unwrap(), (&x4, &y4));
1764 assert_eq!(a.next().unwrap(), (&x5, &y5));
1766 assert!(a.next().is_none());
1768 let mut b = m.iter();
1770 let expected = [(&x1, &y1), (&x2, &y2), (&x3, &y3), (&x4, &y4),
1775 assert_eq!(expected[i], x);
1784 assert_eq!(expected[i], x);
1790 fn test_from_iter() {
1791 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1793 let map: TreeMap<int, int> = xs.iter().map(|&x| x).collect();
1795 for &(k, v) in xs.iter() {
1796 assert_eq!(map.get(&k), Some(&v));
1802 let mut map: TreeMap<int, int> = TreeMap::new();
1808 assert_eq!(map[2], 1);
1813 fn test_index_nonexistent() {
1814 let mut map: TreeMap<int, int> = TreeMap::new();
1825 let mut m = TreeMap::new();
1826 assert_eq!(m.insert(1u, 2i), None);
1827 assert_eq!(m.insert(1u, 3i), Some(2));
1828 assert_eq!(m.insert(1u, 4i), Some(3));
1833 let mut m = TreeMap::new();
1835 assert_eq!(m.remove(&1), Some(2));
1836 assert_eq!(m.remove(&1), None);
1842 use std::prelude::*;
1843 use std::rand::{weak_rng, Rng};
1844 use test::{Bencher, black_box};
1847 use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1850 pub fn insert_rand_100(b: &mut Bencher) {
1851 let mut m : TreeMap<uint,uint> = TreeMap::new();
1852 insert_rand_n(100, &mut m, b,
1853 |m, i| { m.insert(i, 1); },
1854 |m, i| { m.remove(&i); });
1858 pub fn insert_rand_10_000(b: &mut Bencher) {
1859 let mut m : TreeMap<uint,uint> = TreeMap::new();
1860 insert_rand_n(10_000, &mut m, b,
1861 |m, i| { m.insert(i, 1); },
1862 |m, i| { m.remove(&i); });
1867 pub fn insert_seq_100(b: &mut Bencher) {
1868 let mut m : TreeMap<uint,uint> = TreeMap::new();
1869 insert_seq_n(100, &mut m, b,
1870 |m, i| { m.insert(i, 1); },
1871 |m, i| { m.remove(&i); });
1875 pub fn insert_seq_10_000(b: &mut Bencher) {
1876 let mut m : TreeMap<uint,uint> = TreeMap::new();
1877 insert_seq_n(10_000, &mut m, b,
1878 |m, i| { m.insert(i, 1); },
1879 |m, i| { m.remove(&i); });
1884 pub fn find_rand_100(b: &mut Bencher) {
1885 let mut m : TreeMap<uint,uint> = TreeMap::new();
1886 find_rand_n(100, &mut m, b,
1887 |m, i| { m.insert(i, 1); },
1888 |m, i| { m.get(&i); });
1892 pub fn find_rand_10_000(b: &mut Bencher) {
1893 let mut m : TreeMap<uint,uint> = TreeMap::new();
1894 find_rand_n(10_000, &mut m, b,
1895 |m, i| { m.insert(i, 1); },
1896 |m, i| { m.get(&i); });
1901 pub fn find_seq_100(b: &mut Bencher) {
1902 let mut m : TreeMap<uint,uint> = TreeMap::new();
1903 find_seq_n(100, &mut m, b,
1904 |m, i| { m.insert(i, 1); },
1905 |m, i| { m.get(&i); });
1909 pub fn find_seq_10_000(b: &mut Bencher) {
1910 let mut m : TreeMap<uint,uint> = TreeMap::new();
1911 find_seq_n(10_000, &mut m, b,
1912 |m, i| { m.insert(i, 1); },
1913 |m, i| { m.get(&i); });
1916 fn bench_iter(b: &mut Bencher, size: uint) {
1917 let mut map = TreeMap::<uint, uint>::new();
1918 let mut rng = weak_rng();
1920 for _ in range(0, size) {
1921 map.insert(rng.gen(), rng.gen());
1925 for entry in map.iter() {
1932 pub fn iter_20(b: &mut Bencher) {
1937 pub fn iter_1000(b: &mut Bencher) {
1938 bench_iter(b, 1000);
1942 pub fn iter_100000(b: &mut Bencher) {
1943 bench_iter(b, 100000);