1 // Copyright 2013-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 //! Ordered containers with unsigned integer keys,
12 //! implemented as radix tries (`TrieSet` and `TrieMap` types).
16 use alloc::boxed::Box;
17 use core::default::Default;
20 use core::mem::zeroed;
24 use std::hash::{Writer, Hash};
26 use {Collection, Mutable, Map, MutableMap, Set, MutableSet};
27 use slice::{Items, MutItems};
30 // FIXME: #5244: need to manually update the TrieNode constructor
31 static SHIFT: uint = 4;
32 static SIZE: uint = 1 << SHIFT;
33 static MASK: uint = SIZE - 1;
34 static NUM_CHUNKS: uint = uint::BITS / SHIFT;
38 Internal(Box<TrieNode<T>>),
43 /// A map implemented as a radix trie.
48 /// use std::collections::TrieMap;
50 /// let mut map = TrieMap::new();
51 /// map.insert(27, "Olaf");
52 /// map.insert(1, "Edgar");
53 /// map.insert(13, "Ruth");
54 /// map.insert(1, "Martin");
56 /// assert_eq!(map.len(), 3);
57 /// assert_eq!(map.find(&1), Some(&"Martin"));
59 /// if !map.contains_key(&90) {
60 /// println!("Nobody is keyed 90");
64 /// match map.find_mut(&1) {
65 /// Some(value) => *value = "Olga",
70 /// assert_eq!(map.len(), 2);
72 /// // Print the key value pairs, ordered by key.
73 /// for (key, value) in map.iter() {
74 /// // Prints `1: Olga` then `27: Olaf`
75 /// println!("{}: {}", key, value);
79 /// assert!(map.is_empty());
82 pub struct TrieMap<T> {
87 impl<T: PartialEq> PartialEq for TrieMap<T> {
88 fn eq(&self, other: &TrieMap<T>) -> bool {
89 self.len() == other.len() &&
90 self.iter().zip(other.iter()).all(|(a, b)| a == b)
94 impl<T: Eq> Eq for TrieMap<T> {}
96 impl<T: PartialOrd> PartialOrd for TrieMap<T> {
98 fn partial_cmp(&self, other: &TrieMap<T>) -> Option<Ordering> {
99 iter::order::partial_cmp(self.iter(), other.iter())
103 impl<T: Ord> Ord for TrieMap<T> {
105 fn cmp(&self, other: &TrieMap<T>) -> Ordering {
106 iter::order::cmp(self.iter(), other.iter())
110 impl<T: Show> Show for TrieMap<T> {
111 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
112 try!(write!(f, "{{"));
114 for (i, (k, v)) in self.iter().enumerate() {
115 if i != 0 { try!(write!(f, ", ")); }
116 try!(write!(f, "{}: {}", k, *v));
123 impl<T> Collection for TrieMap<T> {
124 /// Return the number of elements in the map.
126 fn len(&self) -> uint { self.length }
129 impl<T> Mutable for TrieMap<T> {
130 /// Clear the map, removing all values.
132 fn clear(&mut self) {
133 self.root = TrieNode::new();
138 impl<T> Map<uint, T> for TrieMap<T> {
139 /// Return a reference to the value corresponding to the key.
141 fn find<'a>(&'a self, key: &uint) -> Option<&'a T> {
142 let mut node: &'a TrieNode<T> = &self.root;
145 match node.children[chunk(*key, idx)] {
146 Internal(ref x) => node = &**x,
147 External(stored, ref value) => {
154 Nothing => return None
161 impl<T> MutableMap<uint, T> for TrieMap<T> {
162 /// Return a mutable reference to the value corresponding to the key.
164 fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
165 find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
168 /// Insert a key-value pair from the map. If the key already had a value
169 /// present in the map, that value is returned. Otherwise None is returned.
170 fn swap(&mut self, key: uint, value: T) -> Option<T> {
171 let ret = insert(&mut self.root.count,
172 &mut self.root.children[chunk(key, 0)],
174 if ret.is_none() { self.length += 1 }
178 /// Removes a key from the map, returning the value at the key if the key
179 /// was previously in the map.
180 fn pop(&mut self, key: &uint) -> Option<T> {
181 let ret = remove(&mut self.root.count,
182 &mut self.root.children[chunk(*key, 0)],
184 if ret.is_some() { self.length -= 1 }
189 impl<T> Default for TrieMap<T> {
191 fn default() -> TrieMap<T> { TrieMap::new() }
195 /// Create an empty TrieMap.
200 /// use std::collections::TrieMap;
201 /// let mut map: TrieMap<&str> = TrieMap::new();
204 pub fn new() -> TrieMap<T> {
205 TrieMap{root: TrieNode::new(), length: 0}
208 /// Visit all key-value pairs in reverse order. Abort traversal when f returns false.
209 /// Return true if f returns true for all elements.
214 /// use std::collections::TrieMap;
215 /// let map: TrieMap<&str> = [(1, "a"), (2, "b"), (3, "c")].iter().map(|&x| x).collect();
217 /// let mut vec = Vec::new();
218 /// assert_eq!(true, map.each_reverse(|&key, &value| { vec.push((key, value)); true }));
219 /// assert_eq!(vec, vec![(3, "c"), (2, "b"), (1, "a")]);
221 /// // Stop when we reach 2
222 /// let mut vec = Vec::new();
223 /// assert_eq!(false, map.each_reverse(|&key, &value| { vec.push(value); key != 2 }));
224 /// assert_eq!(vec, vec!["c", "b"]);
227 pub fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
228 self.root.each_reverse(f)
231 /// Get an iterator visiting all keys in ascending order by the keys.
232 /// Iterator element type is `uint`.
233 pub fn keys<'r>(&'r self) -> Keys<'r, T> {
234 self.iter().map(|(k, _v)| k)
237 /// Get an iterator visiting all values in ascending order by the keys.
238 /// Iterator element type is `&'r T`.
239 pub fn values<'r>(&'r self) -> Values<'r, T> {
240 self.iter().map(|(_k, v)| v)
243 /// Get an iterator over the key-value pairs in the map, ordered by keys.
248 /// use std::collections::TrieMap;
249 /// let map: TrieMap<&str> = [(3, "c"), (1, "a"), (2, "b")].iter().map(|&x| x).collect();
251 /// for (key, value) in map.iter() {
252 /// println!("{}: {}", key, value);
255 pub fn iter<'a>(&'a self) -> Entries<'a, T> {
256 let mut iter = unsafe {Entries::new()};
257 iter.stack[0] = self.root.children.iter();
259 iter.remaining_min = self.length;
260 iter.remaining_max = self.length;
265 /// Get an iterator over the key-value pairs in the map, with the
266 /// ability to mutate the values.
271 /// use std::collections::TrieMap;
272 /// let mut map: TrieMap<int> = [(1, 2), (2, 4), (3, 6)].iter().map(|&x| x).collect();
274 /// for (key, value) in map.mut_iter() {
275 /// *value = -(key as int);
278 /// assert_eq!(map.find(&1), Some(&-1));
279 /// assert_eq!(map.find(&2), Some(&-2));
280 /// assert_eq!(map.find(&3), Some(&-3));
282 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, T> {
283 let mut iter = unsafe {MutEntries::new()};
284 iter.stack[0] = self.root.children.mut_iter();
286 iter.remaining_min = self.length;
287 iter.remaining_max = self.length;
293 // FIXME #5846 we want to be able to choose between &x and &mut x
294 // (with many different `x`) below, so we need to optionally pass mut
295 // as a tt, but the only thing we can do with a `tt` is pass them to
296 // other macros, so this takes the `& <mutability> <operand>` token
297 // sequence and forces their evaluation as an expression. (see also
299 macro_rules! addr { ($e:expr) => { $e } }
302 ($iterator_name:ident,
303 // the current treemap
305 // the key to look for
307 // are we looking at the upper bound?
308 is_upper = $upper:expr,
310 // method names for slicing/iterating.
311 slice_from = $slice_from:ident,
314 // see the comment on `addr!`, this is just an optional mut, but
315 // there's no 0-or-1 repeats yet.
316 mutability = $($mut_:tt)*) => {
319 // We need an unsafe pointer here because we are borrowing
320 // mutable references to the internals of each of these
321 // mutable nodes, while still using the outer node.
323 // However, we're allowed to flaunt rustc like this because we
324 // never actually modify the "shape" of the nodes. The only
325 // place that mutation is can actually occur is of the actual
326 // values of the TrieMap (as the return value of the
327 // iterator), i.e. we can never cause a deallocation of any
328 // TrieNodes so the raw pointer is always valid.
331 // We like sharing code so much that even a little unsafe won't
334 let mut node = unsafe {
335 mem::transmute::<_, uint>(&this.root) as *mut TrieNode<T>
340 let mut it = unsafe {$iterator_name::new()};
341 // everything else is zero'd, as we want.
342 it.remaining_max = this.length;
344 // this addr is necessary for the `Internal` pattern.
346 let children = unsafe {addr!(& $($mut_)* (*node).children)};
347 // it.length is the current depth in the iterator and the
348 // current depth through the `uint` key we've traversed.
349 let child_id = chunk(key, it.length);
350 let (slice_idx, ret) = match children[child_id] {
351 Internal(ref $($mut_)* n) => {
353 mem::transmute::<_, uint>(&**n)
356 (child_id + 1, false)
358 External(stored, _) => {
359 (if stored < key || ($upper && stored == key) {
369 // push to the stack.
370 it.stack[it.length] = children.$slice_from(slice_idx).$iter();
379 // If `upper` is true then returns upper_bound else returns lower_bound.
381 fn bound<'a>(&'a self, key: uint, upper: bool) -> Entries<'a, T> {
382 bound!(Entries, self = self,
383 key = key, is_upper = upper,
384 slice_from = slice_from, iter = iter,
388 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
389 /// If all keys in the map are less than `key` an empty iterator is returned.
394 /// use std::collections::TrieMap;
395 /// let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
397 /// assert_eq!(map.lower_bound(4).next(), Some((4, &"b")));
398 /// assert_eq!(map.lower_bound(5).next(), Some((6, &"c")));
399 /// assert_eq!(map.lower_bound(10).next(), None);
401 pub fn lower_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
402 self.bound(key, false)
405 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
406 /// If all keys in the map are not greater than `key` an empty iterator is returned.
411 /// use std::collections::TrieMap;
412 /// let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
414 /// assert_eq!(map.upper_bound(4).next(), Some((6, &"c")));
415 /// assert_eq!(map.upper_bound(5).next(), Some((6, &"c")));
416 /// assert_eq!(map.upper_bound(10).next(), None);
418 pub fn upper_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
419 self.bound(key, true)
421 // If `upper` is true then returns upper_bound else returns lower_bound.
423 fn mut_bound<'a>(&'a mut self, key: uint, upper: bool) -> MutEntries<'a, T> {
424 bound!(MutEntries, self = self,
425 key = key, is_upper = upper,
426 slice_from = mut_slice_from, iter = mut_iter,
430 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
431 /// If all keys in the map are less than `key` an empty iterator is returned.
436 /// use std::collections::TrieMap;
437 /// let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
439 /// assert_eq!(map.mut_lower_bound(4).next(), Some((4, &mut "b")));
440 /// assert_eq!(map.mut_lower_bound(5).next(), Some((6, &mut "c")));
441 /// assert_eq!(map.mut_lower_bound(10).next(), None);
443 /// for (key, value) in map.mut_lower_bound(4) {
444 /// *value = "changed";
447 /// assert_eq!(map.find(&2), Some(&"a"));
448 /// assert_eq!(map.find(&4), Some(&"changed"));
449 /// assert_eq!(map.find(&6), Some(&"changed"));
451 pub fn mut_lower_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
452 self.mut_bound(key, false)
455 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
456 /// If all keys in the map are not greater than `key` an empty iterator is returned.
461 /// use std::collections::TrieMap;
462 /// let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
464 /// assert_eq!(map.mut_upper_bound(4).next(), Some((6, &mut "c")));
465 /// assert_eq!(map.mut_upper_bound(5).next(), Some((6, &mut "c")));
466 /// assert_eq!(map.mut_upper_bound(10).next(), None);
468 /// for (key, value) in map.mut_upper_bound(4) {
469 /// *value = "changed";
472 /// assert_eq!(map.find(&2), Some(&"a"));
473 /// assert_eq!(map.find(&4), Some(&"b"));
474 /// assert_eq!(map.find(&6), Some(&"changed"));
476 pub fn mut_upper_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
477 self.mut_bound(key, true)
481 impl<T> FromIterator<(uint, T)> for TrieMap<T> {
482 fn from_iter<Iter: Iterator<(uint, T)>>(iter: Iter) -> TrieMap<T> {
483 let mut map = TrieMap::new();
489 impl<T> Extendable<(uint, T)> for TrieMap<T> {
490 fn extend<Iter: Iterator<(uint, T)>>(&mut self, mut iter: Iter) {
497 impl<S: Writer, T: Hash<S>> Hash<S> for TrieMap<T> {
498 fn hash(&self, state: &mut S) {
499 for elt in self.iter() {
505 /// A set implemented as a radix trie.
510 /// use std::collections::TrieSet;
512 /// let mut set = TrieSet::new();
517 /// assert_eq!(set.len(), 2);
519 /// if !set.contains(&3) {
520 /// println!("3 is not in the set");
523 /// // Print contents in order
524 /// for x in set.iter() {
525 /// println!("{}", x);
529 /// assert_eq!(set.len(), 1);
532 /// assert!(set.is_empty());
534 #[deriving(Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
539 impl Show for TrieSet {
540 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
541 try!(write!(f, "{{"));
543 for (i, x) in self.iter().enumerate() {
544 if i != 0 { try!(write!(f, ", ")); }
545 try!(write!(f, "{}", x));
552 impl Collection for TrieSet {
553 /// Return the number of elements in the set.
555 fn len(&self) -> uint { self.map.len() }
558 impl Mutable for TrieSet {
559 /// Clear the set, removing all values.
561 fn clear(&mut self) { self.map.clear() }
564 impl Set<uint> for TrieSet {
566 fn contains(&self, value: &uint) -> bool {
567 self.map.contains_key(value)
571 fn is_disjoint(&self, other: &TrieSet) -> bool {
572 self.iter().all(|v| !other.contains(&v))
576 fn is_subset(&self, other: &TrieSet) -> bool {
577 self.iter().all(|v| other.contains(&v))
581 fn is_superset(&self, other: &TrieSet) -> bool {
582 other.is_subset(self)
586 impl MutableSet<uint> for TrieSet {
588 fn insert(&mut self, value: uint) -> bool {
589 self.map.insert(value, ())
593 fn remove(&mut self, value: &uint) -> bool {
594 self.map.remove(value)
598 impl Default for TrieSet {
600 fn default() -> TrieSet { TrieSet::new() }
604 /// Create an empty TrieSet.
609 /// use std::collections::TrieSet;
610 /// let mut set = TrieSet::new();
613 pub fn new() -> TrieSet {
614 TrieSet{map: TrieMap::new()}
617 /// Visit all values in reverse order. Abort traversal when `f` returns false.
618 /// Return `true` if `f` returns `true` for all elements.
623 /// use std::collections::TrieSet;
625 /// let set: TrieSet = [1, 2, 3, 4, 5].iter().map(|&x| x).collect();
627 /// let mut vec = Vec::new();
628 /// assert_eq!(true, set.each_reverse(|&x| { vec.push(x); true }));
629 /// assert_eq!(vec, vec![5, 4, 3, 2, 1]);
631 /// // Stop when we reach 3
632 /// let mut vec = Vec::new();
633 /// assert_eq!(false, set.each_reverse(|&x| { vec.push(x); x != 3 }));
634 /// assert_eq!(vec, vec![5, 4, 3]);
637 pub fn each_reverse(&self, f: |&uint| -> bool) -> bool {
638 self.map.each_reverse(|k, _| f(k))
641 /// Get an iterator over the values in the set, in sorted order.
646 /// use std::collections::TrieSet;
648 /// let mut set = TrieSet::new();
655 /// for x in set.iter() {
656 /// println!("{}", x);
660 pub fn iter<'a>(&'a self) -> SetItems<'a> {
661 SetItems{iter: self.map.iter()}
664 /// Get an iterator pointing to the first value that is not less than `val`.
665 /// If all values in the set are less than `val` an empty iterator is returned.
670 /// use std::collections::TrieSet;
672 /// let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect();
673 /// assert_eq!(set.lower_bound(4).next(), Some(4));
674 /// assert_eq!(set.lower_bound(5).next(), Some(6));
675 /// assert_eq!(set.lower_bound(10).next(), None);
677 pub fn lower_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
678 SetItems{iter: self.map.lower_bound(val)}
681 /// Get an iterator pointing to the first value that key is greater than `val`.
682 /// If all values in the set are less than or equal to `val` an empty iterator is returned.
687 /// use std::collections::TrieSet;
689 /// let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect();
690 /// assert_eq!(set.upper_bound(4).next(), Some(6));
691 /// assert_eq!(set.upper_bound(5).next(), Some(6));
692 /// assert_eq!(set.upper_bound(10).next(), None);
694 pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
695 SetItems{iter: self.map.upper_bound(val)}
699 impl FromIterator<uint> for TrieSet {
700 fn from_iter<Iter: Iterator<uint>>(iter: Iter) -> TrieSet {
701 let mut set = TrieSet::new();
707 impl Extendable<uint> for TrieSet {
708 fn extend<Iter: Iterator<uint>>(&mut self, mut iter: Iter) {
717 children: [Child<T>, ..SIZE]
720 impl<T:Clone> Clone for TrieNode<T> {
722 fn clone(&self) -> TrieNode<T> {
723 let ch = &self.children;
726 children: [ch[0].clone(), ch[1].clone(), ch[2].clone(), ch[3].clone(),
727 ch[4].clone(), ch[5].clone(), ch[6].clone(), ch[7].clone(),
728 ch[8].clone(), ch[9].clone(), ch[10].clone(), ch[11].clone(),
729 ch[12].clone(), ch[13].clone(), ch[14].clone(), ch[15].clone()]}
733 impl<T> TrieNode<T> {
735 fn new() -> TrieNode<T> {
736 // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit
739 children: [Nothing, Nothing, Nothing, Nothing,
740 Nothing, Nothing, Nothing, Nothing,
741 Nothing, Nothing, Nothing, Nothing,
742 Nothing, Nothing, Nothing, Nothing]}
746 impl<T> TrieNode<T> {
747 fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
748 for elt in self.children.iter().rev() {
750 Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false },
751 External(k, ref v) => if !f(&k, v) { return false },
759 // if this was done via a trait, the key could be generic
761 fn chunk(n: uint, idx: uint) -> uint {
762 let sh = uint::BITS - (SHIFT * (idx + 1));
766 fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
768 External(stored, ref mut value) if stored == key => Some(value),
769 External(..) => None,
770 Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
775 fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
776 idx: uint) -> Option<T> {
777 // we branch twice to avoid having to do the `replace` when we
778 // don't need to; this is much faster, especially for keys that
779 // have long shared prefixes.
783 *child = External(key, value);
786 Internal(ref mut x) => {
787 return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
789 External(stored_key, ref mut stored_value) if stored_key == key => {
790 // swap in the new value and return the old.
791 return Some(mem::replace(stored_value, value));
796 // conflict, an external node with differing keys: we have to
797 // split the node, so we need the old value by value; hence we
798 // have to move out of `child`.
799 match mem::replace(child, Nothing) {
800 External(stored_key, stored_value) => {
801 let mut new = box TrieNode::new();
802 insert(&mut new.count,
803 &mut new.children[chunk(stored_key, idx)],
804 stored_key, stored_value, idx + 1);
805 let ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
806 key, value, idx + 1);
807 *child = Internal(new);
810 _ => fail!("unreachable code"),
814 fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
815 idx: uint) -> Option<T> {
816 let (ret, this) = match *child {
817 External(stored, _) if stored == key => {
818 match mem::replace(child, Nothing) {
819 External(_, value) => (Some(value), true),
823 External(..) => (None, false),
824 Internal(ref mut x) => {
825 let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
829 Nothing => (None, false)
839 /// Forward iterator over a map.
840 pub struct Entries<'a, T> {
841 stack: [slice::Items<'a, Child<T>>, .. NUM_CHUNKS],
847 /// Forward iterator over the key-value pairs of a map, with the
848 /// values being mutable.
849 pub struct MutEntries<'a, T> {
850 stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
856 /// Forward iterator over the keys of a map
857 pub type Keys<'a, T> =
858 iter::Map<'static, (uint, &'a T), uint, Entries<'a, T>>;
860 /// Forward iterator over the values of a map
861 pub type Values<'a, T> =
862 iter::Map<'static, (uint, &'a T), &'a T, Entries<'a, T>>;
864 // FIXME #5846: see `addr!` above.
865 macro_rules! item { ($i:item) => {$i}}
867 macro_rules! iterator_impl {
870 mutability = $($mut_:tt)*) => {
871 impl<'a, T> $name<'a, T> {
872 // Create new zero'd iterator. We have a thin gilding of safety by
873 // using init rather than uninit, so that the worst that can happen
874 // from failing to initialise correctly after calling these is a
876 #[cfg(target_word_size="32")]
877 unsafe fn new() -> $name<'a, T> {
882 // ick :( ... at least the compiler will tell us if we screwed up.
883 stack: [zeroed(), zeroed(), zeroed(), zeroed(), zeroed(),
884 zeroed(), zeroed(), zeroed()]
888 #[cfg(target_word_size="64")]
889 unsafe fn new() -> $name<'a, T> {
894 stack: [zeroed(), zeroed(), zeroed(), zeroed(),
895 zeroed(), zeroed(), zeroed(), zeroed(),
896 zeroed(), zeroed(), zeroed(), zeroed(),
897 zeroed(), zeroed(), zeroed(), zeroed()]
902 item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> {
903 // you might wonder why we're not even trying to act within the
904 // rules, and are just manipulating raw pointers like there's no
905 // such thing as invalid pointers and memory unsafety. The
906 // reason is performance, without doing this we can get the
907 // bench_iter_large microbenchmark down to about 30000 ns/iter
908 // (using .unsafe_ref to index self.stack directly, 38000
909 // ns/iter with [] checked indexing), but this smashes that down
912 // Fortunately, it's still safe...
914 // We have an invariant that every Internal node
915 // corresponds to one push to self.stack, and one pop,
916 // nested appropriately. self.stack has enough storage
917 // to store the maximum depth of Internal nodes in the
918 // trie (8 on 32-bit platforms, 16 on 64-bit).
919 fn next(&mut self) -> Option<(uint, &'a $($mut_)* T)> {
920 let start_ptr = self.stack.as_mut_ptr();
923 // write_ptr is the next place to write to the stack.
924 // invariant: start_ptr <= write_ptr < end of the
926 let mut write_ptr = start_ptr.offset(self.length as int);
927 while write_ptr != start_ptr {
928 // indexing back one is safe, since write_ptr >
930 match (*write_ptr.offset(-1)).next() {
931 // exhausted this iterator (i.e. finished this
932 // Internal node), so pop from the stack.
934 // don't bother clearing the memory, because the
935 // next time we use it we'll've written to it
937 None => write_ptr = write_ptr.offset(-1),
940 Internal(ref $($mut_)* node) => {
941 // going down a level, so push
942 // to the stack (this is the
943 // write referenced above)
944 *write_ptr = node.children.$iter();
945 write_ptr = write_ptr.offset(1);
947 External(key, ref $($mut_)* value) => {
948 self.remaining_max -= 1;
949 if self.remaining_min > 0 {
950 self.remaining_min -= 1;
952 // store the new length of the
953 // stack, based on our current
955 self.length = (write_ptr as uint
956 - start_ptr as uint) /
957 mem::size_of_val(&*write_ptr);
959 return Some((key, value));
971 fn size_hint(&self) -> (uint, Option<uint>) {
972 (self.remaining_min, Some(self.remaining_max))
978 iterator_impl! { Entries, iter = iter, mutability = }
979 iterator_impl! { MutEntries, iter = mut_iter, mutability = mut }
981 /// Forward iterator over a set.
982 pub struct SetItems<'a> {
983 iter: Entries<'a, ()>
986 impl<'a> Iterator<uint> for SetItems<'a> {
987 fn next(&mut self) -> Option<uint> {
988 self.iter.next().map(|(key, _)| key)
991 fn size_hint(&self) -> (uint, Option<uint>) {
992 self.iter.size_hint()
999 use std::iter::range_step;
1003 use {MutableMap, Map, MutableSeq};
1004 use super::{TrieMap, TrieNode, Internal, External, Nothing};
1006 fn check_integrity<T>(trie: &TrieNode<T>) {
1007 assert!(trie.count != 0);
1011 for x in trie.children.iter() {
1014 Internal(ref y) => {
1015 check_integrity(&**y);
1018 External(_, _) => { sum += 1 }
1022 assert_eq!(sum, trie.count);
1026 fn test_find_mut() {
1027 let mut m = TrieMap::new();
1028 assert!(m.insert(1u, 12i));
1029 assert!(m.insert(2u, 8i));
1030 assert!(m.insert(5u, 14i));
1032 match m.find_mut(&5) {
1033 None => fail!(), Some(x) => *x = new
1035 assert_eq!(m.find(&5), Some(&new));
1039 fn test_find_mut_missing() {
1040 let mut m = TrieMap::new();
1041 assert!(m.find_mut(&0).is_none());
1042 assert!(m.insert(1u, 12i));
1043 assert!(m.find_mut(&0).is_none());
1044 assert!(m.insert(2, 8));
1045 assert!(m.find_mut(&0).is_none());
1050 let mut trie = TrieMap::new();
1053 for x in range_step(1u, n, 2) {
1054 assert!(trie.insert(x, x + 1));
1055 assert!(trie.contains_key(&x));
1056 check_integrity(&trie.root);
1059 for x in range_step(0u, n, 2) {
1060 assert!(!trie.contains_key(&x));
1061 assert!(trie.insert(x, x + 1));
1062 check_integrity(&trie.root);
1065 for x in range(0u, n) {
1066 assert!(trie.contains_key(&x));
1067 assert!(!trie.insert(x, x + 1));
1068 check_integrity(&trie.root);
1071 for x in range_step(1u, n, 2) {
1072 assert!(trie.remove(&x));
1073 assert!(!trie.contains_key(&x));
1074 check_integrity(&trie.root);
1077 for x in range_step(0u, n, 2) {
1078 assert!(trie.contains_key(&x));
1079 assert!(!trie.insert(x, x + 1));
1080 check_integrity(&trie.root);
1085 fn test_each_reverse() {
1086 let mut m = TrieMap::new();
1088 assert!(m.insert(3, 6));
1089 assert!(m.insert(0, 0));
1090 assert!(m.insert(4, 8));
1091 assert!(m.insert(2, 4));
1092 assert!(m.insert(1, 2));
1095 m.each_reverse(|k, v| {
1097 assert_eq!(*v, n * 2);
1104 fn test_each_reverse_break() {
1105 let mut m = TrieMap::new();
1107 for x in range(uint::MAX - 10000, uint::MAX).rev() {
1111 let mut n = uint::MAX - 1;
1112 m.each_reverse(|k, v| {
1113 if n == uint::MAX - 5000 { false } else {
1114 assert!(n > uint::MAX - 5000);
1117 assert_eq!(*v, n / 2);
1126 let mut m = TrieMap::new();
1127 assert_eq!(m.swap(1u, 2i), None);
1128 assert_eq!(m.swap(1u, 3i), Some(2));
1129 assert_eq!(m.swap(1u, 4i), Some(3));
1134 let mut m = TrieMap::new();
1136 assert_eq!(m.pop(&1), Some(2));
1137 assert_eq!(m.pop(&1), None);
1141 fn test_from_iter() {
1142 let xs = vec![(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1144 let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
1146 for &(k, v) in xs.iter() {
1147 assert_eq!(map.find(&k), Some(&v));
1153 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1154 let map = vec.move_iter().collect::<TrieMap<char>>();
1155 let keys = map.keys().collect::<Vec<uint>>();
1156 assert_eq!(keys.len(), 3);
1157 assert!(keys.contains(&1));
1158 assert!(keys.contains(&2));
1159 assert!(keys.contains(&3));
1164 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1165 let map = vec.move_iter().collect::<TrieMap<char>>();
1166 let values = map.values().map(|&v| v).collect::<Vec<char>>();
1167 assert_eq!(values.len(), 3);
1168 assert!(values.contains(&'a'));
1169 assert!(values.contains(&'b'));
1170 assert!(values.contains(&'c'));
1174 fn test_iteration() {
1175 let empty_map : TrieMap<uint> = TrieMap::new();
1176 assert_eq!(empty_map.iter().next(), None);
1178 let first = uint::MAX - 10000;
1179 let last = uint::MAX;
1181 let mut map = TrieMap::new();
1182 for x in range(first, last).rev() {
1183 map.insert(x, x / 2);
1187 for (k, &v) in map.iter() {
1188 assert_eq!(k, first + i);
1189 assert_eq!(v, k / 2);
1192 assert_eq!(i, last - first);
1196 fn test_mut_iter() {
1197 let mut empty_map : TrieMap<uint> = TrieMap::new();
1198 assert!(empty_map.mut_iter().next().is_none());
1200 let first = uint::MAX - 10000;
1201 let last = uint::MAX;
1203 let mut map = TrieMap::new();
1204 for x in range(first, last).rev() {
1205 map.insert(x, x / 2);
1209 for (k, v) in map.mut_iter() {
1210 assert_eq!(k, first + i);
1214 assert_eq!(i, last - first);
1216 assert!(map.iter().all(|(_, &v)| v == 0));
1221 let empty_map : TrieMap<uint> = TrieMap::new();
1222 assert_eq!(empty_map.lower_bound(0).next(), None);
1223 assert_eq!(empty_map.upper_bound(0).next(), None);
1229 let mut map : TrieMap<uint> = TrieMap::new();
1230 for x in range_step(0u, last, step) {
1231 assert!(x % step == 0);
1232 map.insert(x, value);
1235 for i in range(0u, last - step) {
1236 let mut lb = map.lower_bound(i);
1237 let mut ub = map.upper_bound(i);
1238 let next_key = i - i % step + step;
1239 let next_pair = (next_key, &value);
1241 assert_eq!(lb.next(), Some((i, &value)));
1243 assert_eq!(lb.next(), Some(next_pair));
1245 assert_eq!(ub.next(), Some(next_pair));
1248 let mut lb = map.lower_bound(last - step);
1249 assert_eq!(lb.next(), Some((last - step, &value)));
1250 let mut ub = map.upper_bound(last - step);
1251 assert_eq!(ub.next(), None);
1253 for i in range(last - step + 1, last) {
1254 let mut lb = map.lower_bound(i);
1255 assert_eq!(lb.next(), None);
1256 let mut ub = map.upper_bound(i);
1257 assert_eq!(ub.next(), None);
1262 fn test_mut_bound() {
1263 let empty_map : TrieMap<uint> = TrieMap::new();
1264 assert_eq!(empty_map.lower_bound(0).next(), None);
1265 assert_eq!(empty_map.upper_bound(0).next(), None);
1267 let mut m_lower = TrieMap::new();
1268 let mut m_upper = TrieMap::new();
1269 for i in range(0u, 100) {
1270 m_lower.insert(2 * i, 4 * i);
1271 m_upper.insert(2 * i, 4 * i);
1274 for i in range(0u, 199) {
1275 let mut lb_it = m_lower.mut_lower_bound(i);
1276 let (k, v) = lb_it.next().unwrap();
1282 for i in range(0u, 198) {
1283 let mut ub_it = m_upper.mut_upper_bound(i);
1284 let (k, v) = ub_it.next().unwrap();
1285 let ub = i + 2 - i % 2;
1290 assert!(m_lower.mut_lower_bound(199).next().is_none());
1291 assert!(m_upper.mut_upper_bound(198).next().is_none());
1293 assert!(m_lower.iter().all(|(_, &x)| x == 0));
1294 assert!(m_upper.iter().all(|(_, &x)| x == 0));
1299 let mut a = TrieMap::new();
1305 assert!(a.clone() == a);
1310 let mut a = TrieMap::new();
1311 let mut b = TrieMap::new();
1314 assert!(a.insert(0, 5i));
1316 assert!(b.insert(0, 4i));
1318 assert!(a.insert(5, 19));
1320 assert!(!b.insert(0, 5));
1322 assert!(b.insert(5, 19));
1328 let mut a = TrieMap::new();
1329 let mut b = TrieMap::new();
1331 assert!(!(a < b) && !(b < a));
1332 assert!(b.insert(2u, 5i));
1334 assert!(a.insert(2, 7));
1335 assert!(!(a < b) && b < a);
1336 assert!(b.insert(1, 0));
1338 assert!(a.insert(0, 6));
1340 assert!(a.insert(6, 2));
1341 assert!(a < b && !(b < a));
1346 let mut a = TrieMap::new();
1347 let mut b = TrieMap::new();
1349 assert!(a <= b && a >= b);
1350 assert!(a.insert(1u, 1i));
1351 assert!(a > b && a >= b);
1352 assert!(b < a && b <= a);
1353 assert!(b.insert(2, 2));
1354 assert!(b > a && b >= a);
1355 assert!(a < b && a <= b);
1360 let mut x = TrieMap::new();
1361 let mut y = TrieMap::new();
1363 assert!(hash::hash(&x) == hash::hash(&y));
1372 assert!(hash::hash(&x) == hash::hash(&y));
1377 let mut map = TrieMap::new();
1378 let empty: TrieMap<uint> = TrieMap::new();
1383 let map_str = format!("{}", map);
1385 assert!(map_str == "{1: a, 2: b}".to_string());
1386 assert_eq!(format!("{}", empty), "{}".to_string());
1392 use std::prelude::*;
1393 use std::rand::{weak_rng, Rng};
1400 fn bench_iter_small(b: &mut Bencher) {
1401 let mut m = TrieMap::<uint>::new();
1402 let mut rng = weak_rng();
1403 for _ in range(0u, 20) {
1404 m.insert(rng.gen(), rng.gen());
1407 b.iter(|| for _ in m.iter() {})
1411 fn bench_iter_large(b: &mut Bencher) {
1412 let mut m = TrieMap::<uint>::new();
1413 let mut rng = weak_rng();
1414 for _ in range(0u, 1000) {
1415 m.insert(rng.gen(), rng.gen());
1418 b.iter(|| for _ in m.iter() {})
1422 fn bench_lower_bound(b: &mut Bencher) {
1423 let mut m = TrieMap::<uint>::new();
1424 let mut rng = weak_rng();
1425 for _ in range(0u, 1000) {
1426 m.insert(rng.gen(), rng.gen());
1430 for _ in range(0u, 10) {
1431 m.lower_bound(rng.gen());
1437 fn bench_upper_bound(b: &mut Bencher) {
1438 let mut m = TrieMap::<uint>::new();
1439 let mut rng = weak_rng();
1440 for _ in range(0u, 1000) {
1441 m.insert(rng.gen(), rng.gen());
1445 for _ in range(0u, 10) {
1446 m.upper_bound(rng.gen());
1452 fn bench_insert_large(b: &mut Bencher) {
1453 let mut m = TrieMap::<[uint, .. 10]>::new();
1454 let mut rng = weak_rng();
1457 for _ in range(0u, 1000) {
1458 m.insert(rng.gen(), [1, .. 10]);
1463 fn bench_insert_large_low_bits(b: &mut Bencher) {
1464 let mut m = TrieMap::<[uint, .. 10]>::new();
1465 let mut rng = weak_rng();
1468 for _ in range(0u, 1000) {
1469 // only have the last few bits set.
1470 m.insert(rng.gen::<uint>() & 0xff_ff, [1, .. 10]);
1476 fn bench_insert_small(b: &mut Bencher) {
1477 let mut m = TrieMap::<()>::new();
1478 let mut rng = weak_rng();
1481 for _ in range(0u, 1000) {
1482 m.insert(rng.gen(), ());
1487 fn bench_insert_small_low_bits(b: &mut Bencher) {
1488 let mut m = TrieMap::<()>::new();
1489 let mut rng = weak_rng();
1492 for _ in range(0u, 1000) {
1493 // only have the last few bits set.
1494 m.insert(rng.gen::<uint>() & 0xff_ff, ());
1502 use std::prelude::*;
1505 use {MutableSet, Set, MutableSeq};
1509 fn test_sane_chunk() {
1511 let y = 1 << (uint::BITS - 1);
1513 let mut trie = TrieSet::new();
1515 assert!(trie.insert(x));
1516 assert!(trie.insert(y));
1518 assert_eq!(trie.len(), 2);
1520 let expected = [x, y];
1522 for (i, x) in trie.iter().enumerate() {
1523 assert_eq!(expected[i], x);
1528 fn test_from_iter() {
1529 let xs = vec![9u, 8, 7, 6, 5, 4, 3, 2, 1];
1531 let set: TrieSet = xs.iter().map(|&x| x).collect();
1533 for x in xs.iter() {
1534 assert!(set.contains(x));
1540 let mut set = TrieSet::new();
1541 let empty = TrieSet::new();
1546 let set_str = format!("{}", set);
1548 assert!(set_str == "{1, 2}".to_string());
1549 assert_eq!(format!("{}", empty), "{}".to_string());
1554 let mut a = TrieSet::new();
1560 assert!(a.clone() == a);
1565 let mut a = TrieSet::new();
1566 let mut b = TrieSet::new();
1568 assert!(!(a < b) && !(b < a));
1569 assert!(b.insert(2u));
1571 assert!(a.insert(3u));
1572 assert!(!(a < b) && b < a);
1573 assert!(b.insert(1));
1575 assert!(a.insert(0));
1577 assert!(a.insert(6));
1578 assert!(a < b && !(b < a));
1583 let mut a = TrieSet::new();
1584 let mut b = TrieSet::new();
1586 assert!(a <= b && a >= b);
1587 assert!(a.insert(1u));
1588 assert!(a > b && a >= b);
1589 assert!(b < a && b <= a);
1590 assert!(b.insert(2u));
1591 assert!(b > a && b >= a);
1592 assert!(a < b && a <= b);