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 integer keys, implemented as radix tries (`TrieSet` and `TrieMap` types)
15 use alloc::owned::Box;
16 use core::default::Default;
17 use core::mem::zeroed;
21 use {Collection, Mutable, Map, MutableMap, Set, MutableSet};
22 use slice::{Items, MutItems};
25 // FIXME: #5244: need to manually update the TrieNode constructor
26 static SHIFT: uint = 4;
27 static SIZE: uint = 1 << SHIFT;
28 static MASK: uint = SIZE - 1;
29 static NUM_CHUNKS: uint = uint::BITS / SHIFT;
32 Internal(Box<TrieNode<T>>),
38 pub struct TrieMap<T> {
43 impl<T> Collection for TrieMap<T> {
44 /// Return the number of elements in the map
46 fn len(&self) -> uint { self.length }
49 impl<T> Mutable for TrieMap<T> {
50 /// Clear the map, removing all values.
53 self.root = TrieNode::new();
58 impl<T> Map<uint, T> for TrieMap<T> {
59 /// Return a reference to the value corresponding to the key
61 fn find<'a>(&'a self, key: &uint) -> Option<&'a T> {
62 let mut node: &'a TrieNode<T> = &self.root;
65 match node.children[chunk(*key, idx)] {
66 Internal(ref x) => node = &**x,
67 External(stored, ref value) => {
74 Nothing => return None
81 impl<T> MutableMap<uint, T> for TrieMap<T> {
82 /// Return a mutable reference to the value corresponding to the key
84 fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
85 find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
88 /// Insert a key-value pair from the map. If the key already had a value
89 /// present in the map, that value is returned. Otherwise None is returned.
90 fn swap(&mut self, key: uint, value: T) -> Option<T> {
91 let ret = insert(&mut self.root.count,
92 &mut self.root.children[chunk(key, 0)],
94 if ret.is_none() { self.length += 1 }
98 /// Removes a key from the map, returning the value at the key if the key
99 /// was previously in the map.
100 fn pop(&mut self, key: &uint) -> Option<T> {
101 let ret = remove(&mut self.root.count,
102 &mut self.root.children[chunk(*key, 0)],
104 if ret.is_some() { self.length -= 1 }
109 impl<T> Default for TrieMap<T> {
111 fn default() -> TrieMap<T> { TrieMap::new() }
115 /// Create an empty TrieMap
117 pub fn new() -> TrieMap<T> {
118 TrieMap{root: TrieNode::new(), length: 0}
121 /// Visit all key-value pairs in reverse order
123 pub fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
124 self.root.each_reverse(f)
127 /// Get an iterator over the key-value pairs in the map
128 pub fn iter<'a>(&'a self) -> Entries<'a, T> {
129 let mut iter = unsafe {Entries::new()};
130 iter.stack[0] = self.root.children.iter();
132 iter.remaining_min = self.length;
133 iter.remaining_max = self.length;
138 /// Get an iterator over the key-value pairs in the map, with the
139 /// ability to mutate the values.
140 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, T> {
141 let mut iter = unsafe {MutEntries::new()};
142 iter.stack[0] = self.root.children.mut_iter();
144 iter.remaining_min = self.length;
145 iter.remaining_max = self.length;
151 // FIXME #5846 we want to be able to choose between &x and &mut x
152 // (with many different `x`) below, so we need to optionally pass mut
153 // as a tt, but the only thing we can do with a `tt` is pass them to
154 // other macros, so this takes the `& <mutability> <operand>` token
155 // sequence and forces their evaluation as an expression. (see also
157 macro_rules! addr { ($e:expr) => { $e } }
160 ($iterator_name:ident,
161 // the current treemap
163 // the key to look for
165 // are we looking at the upper bound?
166 is_upper = $upper:expr,
168 // method names for slicing/iterating.
169 slice_from = $slice_from:ident,
172 // see the comment on `addr!`, this is just an optional mut, but
173 // there's no 0-or-1 repeats yet.
174 mutability = $($mut_:tt)*) => {
177 // We need an unsafe pointer here because we are borrowing
178 // mutable references to the internals of each of these
179 // mutable nodes, while still using the outer node.
181 // However, we're allowed to flaunt rustc like this because we
182 // never actually modify the "shape" of the nodes. The only
183 // place that mutation is can actually occur is of the actual
184 // values of the TrieMap (as the return value of the
185 // iterator), i.e. we can never cause a deallocation of any
186 // TrieNodes so the raw pointer is always valid.
189 // We like sharing code so much that even a little unsafe won't
192 let mut node = addr!(& $($mut_)* this.root as * $($mut_)* TrieNode<T>);
196 let mut it = unsafe {$iterator_name::new()};
197 // everything else is zero'd, as we want.
198 it.remaining_max = this.length;
200 // this addr is necessary for the `Internal` pattern.
202 let children = unsafe {addr!(& $($mut_)* (*node).children)};
203 // it.length is the current depth in the iterator and the
204 // current depth through the `uint` key we've traversed.
205 let child_id = chunk(key, it.length);
206 let (slice_idx, ret) = match children[child_id] {
207 Internal(ref $($mut_)* n) => {
208 node = addr!(& $($mut_)* **n as * $($mut_)* TrieNode<T>);
209 (child_id + 1, false)
211 External(stored, _) => {
212 (if stored < key || ($upper && stored == key) {
222 // push to the stack.
223 it.stack[it.length] = children.$slice_from(slice_idx).$iter();
232 // If `upper` is true then returns upper_bound else returns lower_bound.
234 fn bound<'a>(&'a self, key: uint, upper: bool) -> Entries<'a, T> {
235 bound!(Entries, self = self,
236 key = key, is_upper = upper,
237 slice_from = slice_from, iter = iter,
241 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
242 /// If all keys in the map are less than `key` an empty iterator is returned.
243 pub fn lower_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
244 self.bound(key, false)
247 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
248 /// If all keys in the map are not greater than `key` an empty iterator is returned.
249 pub fn upper_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
250 self.bound(key, true)
252 // If `upper` is true then returns upper_bound else returns lower_bound.
254 fn mut_bound<'a>(&'a mut self, key: uint, upper: bool) -> MutEntries<'a, T> {
255 bound!(MutEntries, self = self,
256 key = key, is_upper = upper,
257 slice_from = mut_slice_from, iter = mut_iter,
261 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
262 /// If all keys in the map are less than `key` an empty iterator is returned.
263 pub fn mut_lower_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
264 self.mut_bound(key, false)
267 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
268 /// If all keys in the map are not greater than `key` an empty iterator is returned.
269 pub fn mut_upper_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
270 self.mut_bound(key, true)
274 impl<T> FromIterator<(uint, T)> for TrieMap<T> {
275 fn from_iter<Iter: Iterator<(uint, T)>>(iter: Iter) -> TrieMap<T> {
276 let mut map = TrieMap::new();
282 impl<T> Extendable<(uint, T)> for TrieMap<T> {
283 fn extend<Iter: Iterator<(uint, T)>>(&mut self, mut iter: Iter) {
290 #[allow(missing_doc)]
295 impl Collection for TrieSet {
296 /// Return the number of elements in the set
298 fn len(&self) -> uint { self.map.len() }
301 impl Mutable for TrieSet {
302 /// Clear the set, removing all values.
304 fn clear(&mut self) { self.map.clear() }
307 impl Set<uint> for TrieSet {
309 fn contains(&self, value: &uint) -> bool {
310 self.map.contains_key(value)
314 fn is_disjoint(&self, other: &TrieSet) -> bool {
315 self.iter().all(|v| !other.contains(&v))
319 fn is_subset(&self, other: &TrieSet) -> bool {
320 self.iter().all(|v| other.contains(&v))
324 fn is_superset(&self, other: &TrieSet) -> bool {
325 other.is_subset(self)
329 impl MutableSet<uint> for TrieSet {
331 fn insert(&mut self, value: uint) -> bool {
332 self.map.insert(value, ())
336 fn remove(&mut self, value: &uint) -> bool {
337 self.map.remove(value)
341 impl Default for TrieSet {
343 fn default() -> TrieSet { TrieSet::new() }
347 /// Create an empty TrieSet
349 pub fn new() -> TrieSet {
350 TrieSet{map: TrieMap::new()}
353 /// Visit all values in reverse order
355 pub fn each_reverse(&self, f: |&uint| -> bool) -> bool {
356 self.map.each_reverse(|k, _| f(k))
359 /// Get an iterator over the values in the set
361 pub fn iter<'a>(&'a self) -> SetItems<'a> {
362 SetItems{iter: self.map.iter()}
365 /// Get an iterator pointing to the first value that is not less than `val`.
366 /// If all values in the set are less than `val` an empty iterator is returned.
367 pub fn lower_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
368 SetItems{iter: self.map.lower_bound(val)}
371 /// Get an iterator pointing to the first value that key is greater than `val`.
372 /// If all values in the set are not greater than `val` an empty iterator is returned.
373 pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
374 SetItems{iter: self.map.upper_bound(val)}
378 impl FromIterator<uint> for TrieSet {
379 fn from_iter<Iter: Iterator<uint>>(iter: Iter) -> TrieSet {
380 let mut set = TrieSet::new();
386 impl Extendable<uint> for TrieSet {
387 fn extend<Iter: Iterator<uint>>(&mut self, mut iter: Iter) {
396 children: [Child<T>, ..SIZE]
399 impl<T> TrieNode<T> {
401 fn new() -> TrieNode<T> {
402 // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit
405 children: [Nothing, Nothing, Nothing, Nothing,
406 Nothing, Nothing, Nothing, Nothing,
407 Nothing, Nothing, Nothing, Nothing,
408 Nothing, Nothing, Nothing, Nothing]}
412 impl<T> TrieNode<T> {
413 fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
414 for elt in self.children.iter().rev() {
416 Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false },
417 External(k, ref v) => if !f(&k, v) { return false },
425 // if this was done via a trait, the key could be generic
427 fn chunk(n: uint, idx: uint) -> uint {
428 let sh = uint::BITS - (SHIFT * (idx + 1));
432 fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
434 External(stored, ref mut value) if stored == key => Some(value),
435 External(..) => None,
436 Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
441 fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
442 idx: uint) -> Option<T> {
443 // we branch twice to avoid having to do the `replace` when we
444 // don't need to; this is much faster, especially for keys that
445 // have long shared prefixes.
449 *child = External(key, value);
452 Internal(ref mut x) => {
453 return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
455 External(stored_key, ref mut stored_value) if stored_key == key => {
456 // swap in the new value and return the old.
457 return Some(mem::replace(stored_value, value));
462 // conflict, an external node with differing keys: we have to
463 // split the node, so we need the old value by value; hence we
464 // have to move out of `child`.
465 match mem::replace(child, Nothing) {
466 External(stored_key, stored_value) => {
467 let mut new = box TrieNode::new();
468 insert(&mut new.count,
469 &mut new.children[chunk(stored_key, idx)],
470 stored_key, stored_value, idx + 1);
471 let ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
472 key, value, idx + 1);
473 *child = Internal(new);
476 _ => fail!("unreachable code"),
480 fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
481 idx: uint) -> Option<T> {
482 let (ret, this) = match *child {
483 External(stored, _) if stored == key => {
484 match mem::replace(child, Nothing) {
485 External(_, value) => (Some(value), true),
489 External(..) => (None, false),
490 Internal(ref mut x) => {
491 let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
495 Nothing => (None, false)
505 /// Forward iterator over a map
506 pub struct Entries<'a, T> {
507 stack: [slice::Items<'a, Child<T>>, .. NUM_CHUNKS],
513 /// Forward iterator over the key-value pairs of a map, with the
514 /// values being mutable.
515 pub struct MutEntries<'a, T> {
516 stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
522 // FIXME #5846: see `addr!` above.
523 macro_rules! item { ($i:item) => {$i}}
525 macro_rules! iterator_impl {
528 mutability = $($mut_:tt)*) => {
529 impl<'a, T> $name<'a, T> {
530 // Create new zero'd iterator. We have a thin gilding of safety by
531 // using init rather than uninit, so that the worst that can happen
532 // from failing to initialise correctly after calling these is a
534 #[cfg(target_word_size="32")]
535 unsafe fn new() -> $name<'a, T> {
540 // ick :( ... at least the compiler will tell us if we screwed up.
541 stack: [zeroed(), zeroed(), zeroed(), zeroed(), zeroed(),
542 zeroed(), zeroed(), zeroed()]
546 #[cfg(target_word_size="64")]
547 unsafe fn new() -> $name<'a, T> {
552 stack: [zeroed(), zeroed(), zeroed(), zeroed(),
553 zeroed(), zeroed(), zeroed(), zeroed(),
554 zeroed(), zeroed(), zeroed(), zeroed(),
555 zeroed(), zeroed(), zeroed(), zeroed()]
560 item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> {
561 // you might wonder why we're not even trying to act within the
562 // rules, and are just manipulating raw pointers like there's no
563 // such thing as invalid pointers and memory unsafety. The
564 // reason is performance, without doing this we can get the
565 // bench_iter_large microbenchmark down to about 30000 ns/iter
566 // (using .unsafe_ref to index self.stack directly, 38000
567 // ns/iter with [] checked indexing), but this smashes that down
570 // Fortunately, it's still safe...
572 // We have an invariant that every Internal node
573 // corresponds to one push to self.stack, and one pop,
574 // nested appropriately. self.stack has enough storage
575 // to store the maximum depth of Internal nodes in the
576 // trie (8 on 32-bit platforms, 16 on 64-bit).
577 fn next(&mut self) -> Option<(uint, &'a $($mut_)* T)> {
578 let start_ptr = self.stack.as_mut_ptr();
581 // write_ptr is the next place to write to the stack.
582 // invariant: start_ptr <= write_ptr < end of the
584 let mut write_ptr = start_ptr.offset(self.length as int);
585 while write_ptr != start_ptr {
586 // indexing back one is safe, since write_ptr >
588 match (*write_ptr.offset(-1)).next() {
589 // exhausted this iterator (i.e. finished this
590 // Internal node), so pop from the stack.
592 // don't bother clearing the memory, because the
593 // next time we use it we'll've written to it
595 None => write_ptr = write_ptr.offset(-1),
598 Internal(ref $($mut_)* node) => {
599 // going down a level, so push
600 // to the stack (this is the
601 // write referenced above)
602 *write_ptr = node.children.$iter();
603 write_ptr = write_ptr.offset(1);
605 External(key, ref $($mut_)* value) => {
606 self.remaining_max -= 1;
607 if self.remaining_min > 0 {
608 self.remaining_min -= 1;
610 // store the new length of the
611 // stack, based on our current
613 self.length = (write_ptr as uint
614 - start_ptr as uint) /
615 mem::size_of_val(&*write_ptr);
617 return Some((key, value));
629 fn size_hint(&self) -> (uint, Option<uint>) {
630 (self.remaining_min, Some(self.remaining_max))
636 iterator_impl! { Entries, iter = iter, mutability = }
637 iterator_impl! { MutEntries, iter = mut_iter, mutability = mut }
639 /// Forward iterator over a set
640 pub struct SetItems<'a> {
641 iter: Entries<'a, ()>
644 impl<'a> Iterator<uint> for SetItems<'a> {
645 fn next(&mut self) -> Option<uint> {
646 self.iter.next().map(|(key, _)| key)
649 fn size_hint(&self) -> (uint, Option<uint>) {
650 self.iter.size_hint()
657 use std::iter::range_step;
660 use {MutableMap, Map};
661 use super::{TrieMap, TrieNode, Internal, External, Nothing};
663 fn check_integrity<T>(trie: &TrieNode<T>) {
664 assert!(trie.count != 0);
668 for x in trie.children.iter() {
672 check_integrity(&**y);
675 External(_, _) => { sum += 1 }
679 assert_eq!(sum, trie.count);
684 let mut m = TrieMap::new();
685 assert!(m.insert(1u, 12i));
686 assert!(m.insert(2u, 8i));
687 assert!(m.insert(5u, 14i));
689 match m.find_mut(&5) {
690 None => fail!(), Some(x) => *x = new
692 assert_eq!(m.find(&5), Some(&new));
696 fn test_find_mut_missing() {
697 let mut m = TrieMap::new();
698 assert!(m.find_mut(&0).is_none());
699 assert!(m.insert(1u, 12i));
700 assert!(m.find_mut(&0).is_none());
701 assert!(m.insert(2, 8));
702 assert!(m.find_mut(&0).is_none());
707 let mut trie = TrieMap::new();
710 for x in range_step(1u, n, 2) {
711 assert!(trie.insert(x, x + 1));
712 assert!(trie.contains_key(&x));
713 check_integrity(&trie.root);
716 for x in range_step(0u, n, 2) {
717 assert!(!trie.contains_key(&x));
718 assert!(trie.insert(x, x + 1));
719 check_integrity(&trie.root);
722 for x in range(0u, n) {
723 assert!(trie.contains_key(&x));
724 assert!(!trie.insert(x, x + 1));
725 check_integrity(&trie.root);
728 for x in range_step(1u, n, 2) {
729 assert!(trie.remove(&x));
730 assert!(!trie.contains_key(&x));
731 check_integrity(&trie.root);
734 for x in range_step(0u, n, 2) {
735 assert!(trie.contains_key(&x));
736 assert!(!trie.insert(x, x + 1));
737 check_integrity(&trie.root);
742 fn test_each_reverse() {
743 let mut m = TrieMap::new();
745 assert!(m.insert(3, 6));
746 assert!(m.insert(0, 0));
747 assert!(m.insert(4, 8));
748 assert!(m.insert(2, 4));
749 assert!(m.insert(1, 2));
752 m.each_reverse(|k, v| {
754 assert_eq!(*v, n * 2);
761 fn test_each_reverse_break() {
762 let mut m = TrieMap::new();
764 for x in range(uint::MAX - 10000, uint::MAX).rev() {
768 let mut n = uint::MAX - 1;
769 m.each_reverse(|k, v| {
770 if n == uint::MAX - 5000 { false } else {
771 assert!(n > uint::MAX - 5000);
774 assert_eq!(*v, n / 2);
783 let mut m = TrieMap::new();
784 assert_eq!(m.swap(1u, 2i), None);
785 assert_eq!(m.swap(1u, 3i), Some(2));
786 assert_eq!(m.swap(1u, 4i), Some(3));
791 let mut m = TrieMap::new();
793 assert_eq!(m.pop(&1), Some(2));
794 assert_eq!(m.pop(&1), None);
798 fn test_from_iter() {
799 let xs = vec![(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
801 let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
803 for &(k, v) in xs.iter() {
804 assert_eq!(map.find(&k), Some(&v));
809 fn test_iteration() {
810 let empty_map : TrieMap<uint> = TrieMap::new();
811 assert_eq!(empty_map.iter().next(), None);
813 let first = uint::MAX - 10000;
814 let last = uint::MAX;
816 let mut map = TrieMap::new();
817 for x in range(first, last).rev() {
818 map.insert(x, x / 2);
822 for (k, &v) in map.iter() {
823 assert_eq!(k, first + i);
824 assert_eq!(v, k / 2);
827 assert_eq!(i, last - first);
832 let mut empty_map : TrieMap<uint> = TrieMap::new();
833 assert!(empty_map.mut_iter().next().is_none());
835 let first = uint::MAX - 10000;
836 let last = uint::MAX;
838 let mut map = TrieMap::new();
839 for x in range(first, last).rev() {
840 map.insert(x, x / 2);
844 for (k, v) in map.mut_iter() {
845 assert_eq!(k, first + i);
849 assert_eq!(i, last - first);
851 assert!(map.iter().all(|(_, &v)| v == 0));
856 let empty_map : TrieMap<uint> = TrieMap::new();
857 assert_eq!(empty_map.lower_bound(0).next(), None);
858 assert_eq!(empty_map.upper_bound(0).next(), None);
864 let mut map : TrieMap<uint> = TrieMap::new();
865 for x in range_step(0u, last, step) {
866 assert!(x % step == 0);
867 map.insert(x, value);
870 for i in range(0u, last - step) {
871 let mut lb = map.lower_bound(i);
872 let mut ub = map.upper_bound(i);
873 let next_key = i - i % step + step;
874 let next_pair = (next_key, &value);
876 assert_eq!(lb.next(), Some((i, &value)));
878 assert_eq!(lb.next(), Some(next_pair));
880 assert_eq!(ub.next(), Some(next_pair));
883 let mut lb = map.lower_bound(last - step);
884 assert_eq!(lb.next(), Some((last - step, &value)));
885 let mut ub = map.upper_bound(last - step);
886 assert_eq!(ub.next(), None);
888 for i in range(last - step + 1, last) {
889 let mut lb = map.lower_bound(i);
890 assert_eq!(lb.next(), None);
891 let mut ub = map.upper_bound(i);
892 assert_eq!(ub.next(), None);
897 fn test_mut_bound() {
898 let empty_map : TrieMap<uint> = TrieMap::new();
899 assert_eq!(empty_map.lower_bound(0).next(), None);
900 assert_eq!(empty_map.upper_bound(0).next(), None);
902 let mut m_lower = TrieMap::new();
903 let mut m_upper = TrieMap::new();
904 for i in range(0u, 100) {
905 m_lower.insert(2 * i, 4 * i);
906 m_upper.insert(2 * i, 4 * i);
909 for i in range(0u, 199) {
910 let mut lb_it = m_lower.mut_lower_bound(i);
911 let (k, v) = lb_it.next().unwrap();
917 for i in range(0u, 198) {
918 let mut ub_it = m_upper.mut_upper_bound(i);
919 let (k, v) = ub_it.next().unwrap();
920 let ub = i + 2 - i % 2;
925 assert!(m_lower.mut_lower_bound(199).next().is_none());
926 assert!(m_upper.mut_upper_bound(198).next().is_none());
928 assert!(m_lower.iter().all(|(_, &x)| x == 0));
929 assert!(m_upper.iter().all(|(_, &x)| x == 0));
936 use std::rand::{weak_rng, Rng};
943 fn bench_iter_small(b: &mut Bencher) {
944 let mut m = TrieMap::<uint>::new();
945 let mut rng = weak_rng();
946 for _ in range(0u, 20) {
947 m.insert(rng.gen(), rng.gen());
950 b.iter(|| for _ in m.iter() {})
954 fn bench_iter_large(b: &mut Bencher) {
955 let mut m = TrieMap::<uint>::new();
956 let mut rng = weak_rng();
957 for _ in range(0u, 1000) {
958 m.insert(rng.gen(), rng.gen());
961 b.iter(|| for _ in m.iter() {})
965 fn bench_lower_bound(b: &mut Bencher) {
966 let mut m = TrieMap::<uint>::new();
967 let mut rng = weak_rng();
968 for _ in range(0u, 1000) {
969 m.insert(rng.gen(), rng.gen());
973 for _ in range(0u, 10) {
974 m.lower_bound(rng.gen());
980 fn bench_upper_bound(b: &mut Bencher) {
981 let mut m = TrieMap::<uint>::new();
982 let mut rng = weak_rng();
983 for _ in range(0u, 1000) {
984 m.insert(rng.gen(), rng.gen());
988 for _ in range(0u, 10) {
989 m.upper_bound(rng.gen());
995 fn bench_insert_large(b: &mut Bencher) {
996 let mut m = TrieMap::<[uint, .. 10]>::new();
997 let mut rng = weak_rng();
1000 for _ in range(0u, 1000) {
1001 m.insert(rng.gen(), [1, .. 10]);
1006 fn bench_insert_large_low_bits(b: &mut Bencher) {
1007 let mut m = TrieMap::<[uint, .. 10]>::new();
1008 let mut rng = weak_rng();
1011 for _ in range(0u, 1000) {
1012 // only have the last few bits set.
1013 m.insert(rng.gen::<uint>() & 0xff_ff, [1, .. 10]);
1019 fn bench_insert_small(b: &mut Bencher) {
1020 let mut m = TrieMap::<()>::new();
1021 let mut rng = weak_rng();
1024 for _ in range(0u, 1000) {
1025 m.insert(rng.gen(), ());
1030 fn bench_insert_small_low_bits(b: &mut Bencher) {
1031 let mut m = TrieMap::<()>::new();
1032 let mut rng = weak_rng();
1035 for _ in range(0u, 1000) {
1036 // only have the last few bits set.
1037 m.insert(rng.gen::<uint>() & 0xff_ff, ());
1045 use std::prelude::*;
1048 use {MutableSet, Set};
1052 fn test_sane_chunk() {
1054 let y = 1 << (uint::BITS - 1);
1056 let mut trie = TrieSet::new();
1058 assert!(trie.insert(x));
1059 assert!(trie.insert(y));
1061 assert_eq!(trie.len(), 2);
1063 let expected = [x, y];
1065 for (i, x) in trie.iter().enumerate() {
1066 assert_eq!(expected[i], x);
1071 fn test_from_iter() {
1072 let xs = vec![9u, 8, 7, 6, 5, 4, 3, 2, 1];
1074 let set: TrieSet = xs.iter().map(|&x| x).collect();
1076 for x in xs.iter() {
1077 assert!(set.contains(x));