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.
4 //
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.
10
11 //! Ordered containers with integer keys, implemented as radix tries (`TrieSet` and `TrieMap` types)
12
13 use std::mem::init;
14 use std::mem;
15 use std::slice::{Items, MutItems};
16 use std::slice;
17 use std::uint;
18
19 // FIXME: #5244: need to manually update the TrieNode constructor
20 static SHIFT: uint = 4;
21 static SIZE: uint = 1 << SHIFT;
22 static MASK: uint = SIZE - 1;
23 static NUM_CHUNKS: uint = uint::BITS / SHIFT;
24
25 enum Child<T> {
26 Internal(Box<TrieNode<T>>),
27 External(uint, T),
28 Nothing
29 }
30
31 #[allow(missing_doc)]
32 pub struct TrieMap<T> {
33 root: TrieNode<T>,
34 length: uint
35 }
36
37 impl<T> Container for TrieMap<T> {
38 /// Return the number of elements in the map
39 #[inline]
40 fn len(&self) -> uint { self.length }
41 }
42
43 impl<T> Mutable for TrieMap<T> {
44 /// Clear the map, removing all values.
45 #[inline]
46 fn clear(&mut self) {
47 self.root = TrieNode::new();
48 self.length = 0;
49 }
50 }
51
52 impl<T> Map<uint, T> for TrieMap<T> {
53 /// Return a reference to the value corresponding to the key
54 #[inline]
55 fn find<'a>(&'a self, key: &uint) -> Option<&'a T> {
56 let mut node: &'a TrieNode<T> = &self.root;
57 let mut idx = 0;
58 loop {
59 match node.children[chunk(*key, idx)] {
60 Internal(ref x) => node = &**x,
61 External(stored, ref value) => {
62 if stored == *key {
63 return Some(value)
64 } else {
65 return None
66 }
67 }
68 Nothing => return None
69 }
70 idx += 1;
71 }
72 }
73 }
74
75 impl<T> MutableMap<uint, T> for TrieMap<T> {
76 /// Return a mutable reference to the value corresponding to the key
77 #[inline]
78 fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
79 find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
80 }
81
82 /// Insert a key-value pair from the map. If the key already had a value
83 /// present in the map, that value is returned. Otherwise None is returned.
84 fn swap(&mut self, key: uint, value: T) -> Option<T> {
85 let ret = insert(&mut self.root.count,
86 &mut self.root.children[chunk(key, 0)],
87 key, value, 1);
88 if ret.is_none() { self.length += 1 }
89 ret
90 }
91
92 /// Removes a key from the map, returning the value at the key if the key
93 /// was previously in the map.
94 fn pop(&mut self, key: &uint) -> Option<T> {
95 let ret = remove(&mut self.root.count,
96 &mut self.root.children[chunk(*key, 0)],
97 *key, 1);
98 if ret.is_some() { self.length -= 1 }
99 ret
100 }
101 }
102
103 impl<T> TrieMap<T> {
104 /// Create an empty TrieMap
105 #[inline]
106 pub fn new() -> TrieMap<T> {
107 TrieMap{root: TrieNode::new(), length: 0}
108 }
109
110 /// Visit all key-value pairs in reverse order
111 #[inline]
112 pub fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
113 self.root.each_reverse(f)
114 }
115
116 /// Get an iterator over the key-value pairs in the map
117 pub fn iter<'a>(&'a self) -> Entries<'a, T> {
118 let mut iter = unsafe {Entries::new()};
119 iter.stack[0] = self.root.children.iter();
120 iter.length = 1;
121 iter.remaining_min = self.length;
122 iter.remaining_max = self.length;
123
124 iter
125 }
126
127 /// Get an iterator over the key-value pairs in the map, with the
128 /// ability to mutate the values.
129 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, T> {
130 let mut iter = unsafe {MutEntries::new()};
131 iter.stack[0] = self.root.children.mut_iter();
132 iter.length = 1;
133 iter.remaining_min = self.length;
134 iter.remaining_max = self.length;
135
136 iter
137 }
138 }
139
140 // FIXME #5846 we want to be able to choose between &x and &mut x
141 // (with many different `x`) below, so we need to optionally pass mut
142 // as a tt, but the only thing we can do with a `tt` is pass them to
143 // other macros, so this takes the `& <mutability> <operand>` token
144 // sequence and forces their evaluation as an expression. (see also
145 // `item!` below.)
146 macro_rules! addr { ($e:expr) => { $e } }
147
148 macro_rules! bound {
149 ($iterator_name:ident,
150 // the current treemap
151 self = $this:expr,
152 // the key to look for
153 key = $key:expr,
154 // are we looking at the upper bound?
155 is_upper = $upper:expr,
156
157 // method names for slicing/iterating.
158 slice_from = $slice_from:ident,
159 iter = $iter:ident,
160
161 // see the comment on `addr!`, this is just an optional mut, but
162 // there's no 0-or-1 repeats yet.
163 mutability = $($mut_:tt)*) => {
164 {
165 // # For `mut`
166 // We need an unsafe pointer here because we are borrowing
167 // mutable references to the internals of each of these
168 // mutable nodes, while still using the outer node.
169 //
170 // However, we're allowed to flaunt rustc like this because we
171 // never actually modify the "shape" of the nodes. The only
172 // place that mutation is can actually occur is of the actual
173 // values of the TrieMap (as the return value of the
174 // iterator), i.e. we can never cause a deallocation of any
175 // TrieNodes so the raw pointer is always valid.
176 //
177 // # For non-`mut`
178 // We like sharing code so much that even a little unsafe won't
179 // stop us.
180 let this = $this;
181 let mut node = addr!(& $($mut_)* this.root as * $($mut_)* TrieNode<T>);
182
183 let key = $key;
184
185 let mut it = unsafe {$iterator_name::new()};
186 // everything else is zero'd, as we want.
187 it.remaining_max = this.length;
188
189 // this addr is necessary for the `Internal` pattern.
190 addr!(loop {
191 let children = unsafe {addr!(& $($mut_)* (*node).children)};
192 // it.length is the current depth in the iterator and the
193 // current depth through the `uint` key we've traversed.
194 let child_id = chunk(key, it.length);
195 let (slice_idx, ret) = match children[child_id] {
196 Internal(ref $($mut_)* n) => {
197 node = addr!(& $($mut_)* **n as * $($mut_)* TrieNode<T>);
198 (child_id + 1, false)
199 }
200 External(stored, _) => {
201 (if stored < key || ($upper && stored == key) {
202 child_id + 1
203 } else {
204 child_id
205 }, true)
206 }
207 Nothing => {
208 (child_id + 1, true)
209 }
210 };
211 // push to the stack.
212 it.stack[it.length] = children.$slice_from(slice_idx).$iter();
213 it.length += 1;
214 if ret { return it }
215 })
216 }
217 }
218 }
219
220 impl<T> TrieMap<T> {
221 // If `upper` is true then returns upper_bound else returns lower_bound.
222 #[inline]
223 fn bound<'a>(&'a self, key: uint, upper: bool) -> Entries<'a, T> {
224 bound!(Entries, self = self,
225 key = key, is_upper = upper,
226 slice_from = slice_from, iter = iter,
227 mutability = )
228 }
229
230 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
231 /// If all keys in the map are less than `key` an empty iterator is returned.
232 pub fn lower_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
233 self.bound(key, false)
234 }
235
236 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
237 /// If all keys in the map are not greater than `key` an empty iterator is returned.
238 pub fn upper_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
239 self.bound(key, true)
240 }
241 // If `upper` is true then returns upper_bound else returns lower_bound.
242 #[inline]
243 fn mut_bound<'a>(&'a mut self, key: uint, upper: bool) -> MutEntries<'a, T> {
244 bound!(MutEntries, self = self,
245 key = key, is_upper = upper,
246 slice_from = mut_slice_from, iter = mut_iter,
247 mutability = mut)
248 }
249
250 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
251 /// If all keys in the map are less than `key` an empty iterator is returned.
252 pub fn mut_lower_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
253 self.mut_bound(key, false)
254 }
255
256 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
257 /// If all keys in the map are not greater than `key` an empty iterator is returned.
258 pub fn mut_upper_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
259 self.mut_bound(key, true)
260 }
261 }
262
263 impl<T> FromIterator<(uint, T)> for TrieMap<T> {
264 fn from_iter<Iter: Iterator<(uint, T)>>(iter: Iter) -> TrieMap<T> {
265 let mut map = TrieMap::new();
266 map.extend(iter);
267 map
268 }
269 }
270
271 impl<T> Extendable<(uint, T)> for TrieMap<T> {
272 fn extend<Iter: Iterator<(uint, T)>>(&mut self, mut iter: Iter) {
273 for (k, v) in iter {
274 self.insert(k, v);
275 }
276 }
277 }
278
279 #[allow(missing_doc)]
280 pub struct TrieSet {
281 map: TrieMap<()>
282 }
283
284 impl Container for TrieSet {
285 /// Return the number of elements in the set
286 #[inline]
287 fn len(&self) -> uint { self.map.len() }
288 }
289
290 impl Mutable for TrieSet {
291 /// Clear the set, removing all values.
292 #[inline]
293 fn clear(&mut self) { self.map.clear() }
294 }
295
296 impl Set<uint> for TrieSet {
297 #[inline]
298 fn contains(&self, value: &uint) -> bool {
299 self.map.contains_key(value)
300 }
301
302 #[inline]
303 fn is_disjoint(&self, other: &TrieSet) -> bool {
304 self.iter().all(|v| !other.contains(&v))
305 }
306
307 #[inline]
308 fn is_subset(&self, other: &TrieSet) -> bool {
309 self.iter().all(|v| other.contains(&v))
310 }
311
312 #[inline]
313 fn is_superset(&self, other: &TrieSet) -> bool {
314 other.is_subset(self)
315 }
316 }
317
318 impl MutableSet<uint> for TrieSet {
319 #[inline]
320 fn insert(&mut self, value: uint) -> bool {
321 self.map.insert(value, ())
322 }
323
324 #[inline]
325 fn remove(&mut self, value: &uint) -> bool {
326 self.map.remove(value)
327 }
328 }
329
330 impl TrieSet {
331 /// Create an empty TrieSet
332 #[inline]
333 pub fn new() -> TrieSet {
334 TrieSet{map: TrieMap::new()}
335 }
336
337 /// Visit all values in reverse order
338 #[inline]
339 pub fn each_reverse(&self, f: |&uint| -> bool) -> bool {
340 self.map.each_reverse(|k, _| f(k))
341 }
342
343 /// Get an iterator over the values in the set
344 #[inline]
345 pub fn iter<'a>(&'a self) -> SetItems<'a> {
346 SetItems{iter: self.map.iter()}
347 }
348
349 /// Get an iterator pointing to the first value that is not less than `val`.
350 /// If all values in the set are less than `val` an empty iterator is returned.
351 pub fn lower_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
352 SetItems{iter: self.map.lower_bound(val)}
353 }
354
355 /// Get an iterator pointing to the first value that key is greater than `val`.
356 /// If all values in the set are not greater than `val` an empty iterator is returned.
357 pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
358 SetItems{iter: self.map.upper_bound(val)}
359 }
360 }
361
362 impl FromIterator<uint> for TrieSet {
363 fn from_iter<Iter: Iterator<uint>>(iter: Iter) -> TrieSet {
364 let mut set = TrieSet::new();
365 set.extend(iter);
366 set
367 }
368 }
369
370 impl Extendable<uint> for TrieSet {
371 fn extend<Iter: Iterator<uint>>(&mut self, mut iter: Iter) {
372 for elem in iter {
373 self.insert(elem);
374 }
375 }
376 }
377
378 struct TrieNode<T> {
379 count: uint,
380 children: [Child<T>, ..SIZE]
381 }
382
383 impl<T> TrieNode<T> {
384 #[inline]
385 fn new() -> TrieNode<T> {
386 // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit
387 // copyability
388 TrieNode{count: 0,
389 children: [Nothing, Nothing, Nothing, Nothing,
390 Nothing, Nothing, Nothing, Nothing,
391 Nothing, Nothing, Nothing, Nothing,
392 Nothing, Nothing, Nothing, Nothing]}
393 }
394 }
395
396 impl<T> TrieNode<T> {
397 fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
398 for elt in self.children.iter().rev() {
399 match *elt {
400 Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false },
401 External(k, ref v) => if !f(&k, v) { return false },
402 Nothing => ()
403 }
404 }
405 true
406 }
407 }
408
409 // if this was done via a trait, the key could be generic
410 #[inline]
411 fn chunk(n: uint, idx: uint) -> uint {
412 let sh = uint::BITS - (SHIFT * (idx + 1));
413 (n >> sh) & MASK
414 }
415
416 fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
417 match *child {
418 External(stored, ref mut value) if stored == key => Some(value),
419 External(..) => None,
420 Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
421 Nothing => None
422 }
423 }
424
425 fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
426 idx: uint) -> Option<T> {
427 // we branch twice to avoid having to do the `replace` when we
428 // don't need to; this is much faster, especially for keys that
429 // have long shared prefixes.
430 match *child {
431 Nothing => {
432 *count += 1;
433 *child = External(key, value);
434 return None;
435 }
436 Internal(ref mut x) => {
437 return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
438 }
439 External(stored_key, ref mut stored_value) if stored_key == key => {
440 // swap in the new value and return the old.
441 return Some(mem::replace(stored_value, value));
442 }
443 _ => {}
444 }
445
446 // conflict, an external node with differing keys: we have to
447 // split the node, so we need the old value by value; hence we
448 // have to move out of `child`.
449 match mem::replace(child, Nothing) {
450 External(stored_key, stored_value) => {
451 let mut new = box TrieNode::new();
452 insert(&mut new.count,
453 &mut new.children[chunk(stored_key, idx)],
454 stored_key, stored_value, idx + 1);
455 let ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
456 key, value, idx + 1);
457 *child = Internal(new);
458 return ret;
459 }
460 _ => unreachable!()
461 }
462 }
463
464 fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
465 idx: uint) -> Option<T> {
466 let (ret, this) = match *child {
467 External(stored, _) if stored == key => {
468 match mem::replace(child, Nothing) {
469 External(_, value) => (Some(value), true),
470 _ => fail!()
471 }
472 }
473 External(..) => (None, false),
474 Internal(ref mut x) => {
475 let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
476 key, idx + 1);
477 (ret, x.count == 0)
478 }
479 Nothing => (None, false)
480 };
481
482 if this {
483 *child = Nothing;
484 *count -= 1;
485 }
486 return ret;
487 }
488
489 /// Forward iterator over a map
490 pub struct Entries<'a, T> {
491 stack: [slice::Items<'a, Child<T>>, .. NUM_CHUNKS],
492 length: uint,
493 remaining_min: uint,
494 remaining_max: uint
495 }
496
497 /// Forward iterator over the key-value pairs of a map, with the
498 /// values being mutable.
499 pub struct MutEntries<'a, T> {
500 stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
501 length: uint,
502 remaining_min: uint,
503 remaining_max: uint
504 }
505
506 // FIXME #5846: see `addr!` above.
507 macro_rules! item { ($i:item) => {$i}}
508
509 macro_rules! iterator_impl {
510 ($name:ident,
511 iter = $iter:ident,
512 mutability = $($mut_:tt)*) => {
513 impl<'a, T> $name<'a, T> {
514 // Create new zero'd iterator. We have a thin gilding of safety by
515 // using init rather than uninit, so that the worst that can happen
516 // from failing to initialise correctly after calling these is a
517 // segfault.
518 #[cfg(target_word_size="32")]
519 unsafe fn new() -> $name<'a, T> {
520 $name {
521 remaining_min: 0,
522 remaining_max: 0,
523 length: 0,
524 // ick :( ... at least the compiler will tell us if we screwed up.
525 stack: [init(), init(), init(), init(), init(), init(), init(), init()]
526 }
527 }
528
529 #[cfg(target_word_size="64")]
530 unsafe fn new() -> $name<'a, T> {
531 $name {
532 remaining_min: 0,
533 remaining_max: 0,
534 length: 0,
535 stack: [init(), init(), init(), init(), init(), init(), init(), init(),
536 init(), init(), init(), init(), init(), init(), init(), init()]
537 }
538 }
539 }
540
541 item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> {
542 // you might wonder why we're not even trying to act within the
543 // rules, and are just manipulating raw pointers like there's no
544 // such thing as invalid pointers and memory unsafety. The
545 // reason is performance, without doing this we can get the
546 // bench_iter_large microbenchmark down to about 30000 ns/iter
547 // (using .unsafe_ref to index self.stack directly, 38000
548 // ns/iter with [] checked indexing), but this smashes that down
549 // to 13500 ns/iter.
550 //
551 // Fortunately, it's still safe...
552 //
553 // We have an invariant that every Internal node
554 // corresponds to one push to self.stack, and one pop,
555 // nested appropriately. self.stack has enough storage
556 // to store the maximum depth of Internal nodes in the
557 // trie (8 on 32-bit platforms, 16 on 64-bit).
558 fn next(&mut self) -> Option<(uint, &'a $($mut_)* T)> {
559 let start_ptr = self.stack.as_mut_ptr();
560
561 unsafe {
562 // write_ptr is the next place to write to the stack.
563 // invariant: start_ptr <= write_ptr < end of the
564 // vector.
565 let mut write_ptr = start_ptr.offset(self.length as int);
566 while write_ptr != start_ptr {
567 // indexing back one is safe, since write_ptr >
568 // start_ptr now.
569 match (*write_ptr.offset(-1)).next() {
570 // exhausted this iterator (i.e. finished this
571 // Internal node), so pop from the stack.
572 //
573 // don't bother clearing the memory, because the
574 // next time we use it we'll've written to it
575 // first.
576 None => write_ptr = write_ptr.offset(-1),
577 Some(child) => {
578 addr!(match *child {
579 Internal(ref $($mut_)* node) => {
580 // going down a level, so push
581 // to the stack (this is the
582 // write referenced above)
583 *write_ptr = node.children.$iter();
584 write_ptr = write_ptr.offset(1);
585 }
586 External(key, ref $($mut_)* value) => {
587 self.remaining_max -= 1;
588 if self.remaining_min > 0 {
589 self.remaining_min -= 1;
590 }
591 // store the new length of the
592 // stack, based on our current
593 // position.
594 self.length = (write_ptr as uint
595 - start_ptr as uint) /
596 mem::size_of_val(&*write_ptr);
597
598 return Some((key, value));
599 }
600 Nothing => {}
601 })
602 }
603 }
604 }
605 }
606 return None;
607 }
608
609 #[inline]
610 fn size_hint(&self) -> (uint, Option<uint>) {
611 (self.remaining_min, Some(self.remaining_max))
612 }
613 })
614 }
615 }
616
617 iterator_impl! { Entries, iter = iter, mutability = }
618 iterator_impl! { MutEntries, iter = mut_iter, mutability = mut }
619
620 /// Forward iterator over a set
621 pub struct SetItems<'a> {
622 iter: Entries<'a, ()>
623 }
624
625 impl<'a> Iterator<uint> for SetItems<'a> {
626 fn next(&mut self) -> Option<uint> {
627 self.iter.next().map(|(key, _)| key)
628 }
629
630 fn size_hint(&self) -> (uint, Option<uint>) {
631 self.iter.size_hint()
632 }
633 }
634
635 #[cfg(test)]
636 mod test_map {
637 use super::{TrieMap, TrieNode, Internal, External};
638 use std::iter::range_step;
639 use std::uint;
640
641 fn check_integrity<T>(trie: &TrieNode<T>) {
642 assert!(trie.count != 0);
643
644 let mut sum = 0;
645
646 for x in trie.children.iter() {
647 match *x {
648 Nothing => (),
649 Internal(ref y) => {
650 check_integrity(&**y);
651 sum += 1
652 }
653 External(_, _) => { sum += 1 }
654 }
655 }
656
657 assert_eq!(sum, trie.count);
658 }
659
660 #[test]
661 fn test_find_mut() {
662 let mut m = TrieMap::new();
663 assert!(m.insert(1, 12));
664 assert!(m.insert(2, 8));
665 assert!(m.insert(5, 14));
666 let new = 100;
667 match m.find_mut(&5) {
668 None => fail!(), Some(x) => *x = new
669 }
670 assert_eq!(m.find(&5), Some(&new));
671 }
672
673 #[test]
674 fn test_find_mut_missing() {
675 let mut m = TrieMap::new();
676 assert!(m.find_mut(&0).is_none());
677 assert!(m.insert(1, 12));
678 assert!(m.find_mut(&0).is_none());
679 assert!(m.insert(2, 8));
680 assert!(m.find_mut(&0).is_none());
681 }
682
683 #[test]
684 fn test_step() {
685 let mut trie = TrieMap::new();
686 let n = 300u;
687
688 for x in range_step(1u, n, 2) {
689 assert!(trie.insert(x, x + 1));
690 assert!(trie.contains_key(&x));
691 check_integrity(&trie.root);
692 }
693
694 for x in range_step(0u, n, 2) {
695 assert!(!trie.contains_key(&x));
696 assert!(trie.insert(x, x + 1));
697 check_integrity(&trie.root);
698 }
699
700 for x in range(0u, n) {
701 assert!(trie.contains_key(&x));
702 assert!(!trie.insert(x, x + 1));
703 check_integrity(&trie.root);
704 }
705
706 for x in range_step(1u, n, 2) {
707 assert!(trie.remove(&x));
708 assert!(!trie.contains_key(&x));
709 check_integrity(&trie.root);
710 }
711
712 for x in range_step(0u, n, 2) {
713 assert!(trie.contains_key(&x));
714 assert!(!trie.insert(x, x + 1));
715 check_integrity(&trie.root);
716 }
717 }
718
719 #[test]
720 fn test_each_reverse() {
721 let mut m = TrieMap::new();
722
723 assert!(m.insert(3, 6));
724 assert!(m.insert(0, 0));
725 assert!(m.insert(4, 8));
726 assert!(m.insert(2, 4));
727 assert!(m.insert(1, 2));
728
729 let mut n = 4;
730 m.each_reverse(|k, v| {
731 assert_eq!(*k, n);
732 assert_eq!(*v, n * 2);
733 n -= 1;
734 true
735 });
736 }
737
738 #[test]
739 fn test_each_reverse_break() {
740 let mut m = TrieMap::new();
741
742 for x in range(uint::MAX - 10000, uint::MAX).rev() {
743 m.insert(x, x / 2);
744 }
745
746 let mut n = uint::MAX - 1;
747 m.each_reverse(|k, v| {
748 if n == uint::MAX - 5000 { false } else {
749 assert!(n > uint::MAX - 5000);
750
751 assert_eq!(*k, n);
752 assert_eq!(*v, n / 2);
753 n -= 1;
754 true
755 }
756 });
757 }
758
759 #[test]
760 fn test_swap() {
761 let mut m = TrieMap::new();
762 assert_eq!(m.swap(1, 2), None);
763 assert_eq!(m.swap(1, 3), Some(2));
764 assert_eq!(m.swap(1, 4), Some(3));
765 }
766
767 #[test]
768 fn test_pop() {
769 let mut m = TrieMap::new();
770 m.insert(1, 2);
771 assert_eq!(m.pop(&1), Some(2));
772 assert_eq!(m.pop(&1), None);
773 }
774
775 #[test]
776 fn test_from_iter() {
777 let xs = vec![(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
778
779 let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
780
781 for &(k, v) in xs.iter() {
782 assert_eq!(map.find(&k), Some(&v));
783 }
784 }
785
786 #[test]
787 fn test_iteration() {
788 let empty_map : TrieMap<uint> = TrieMap::new();
789 assert_eq!(empty_map.iter().next(), None);
790
791 let first = uint::MAX - 10000;
792 let last = uint::MAX;
793
794 let mut map = TrieMap::new();
795 for x in range(first, last).rev() {
796 map.insert(x, x / 2);
797 }
798
799 let mut i = 0;
800 for (k, &v) in map.iter() {
801 assert_eq!(k, first + i);
802 assert_eq!(v, k / 2);
803 i += 1;
804 }
805 assert_eq!(i, last - first);
806 }
807
808 #[test]
809 fn test_mut_iter() {
810 let mut empty_map : TrieMap<uint> = TrieMap::new();
811 assert!(empty_map.mut_iter().next().is_none());
812
813 let first = uint::MAX - 10000;
814 let last = uint::MAX;
815
816 let mut map = TrieMap::new();
817 for x in range(first, last).rev() {
818 map.insert(x, x / 2);
819 }
820
821 let mut i = 0;
822 for (k, v) in map.mut_iter() {
823 assert_eq!(k, first + i);
824 *v -= k / 2;
825 i += 1;
826 }
827 assert_eq!(i, last - first);
828
829 assert!(map.iter().all(|(_, &v)| v == 0));
830 }
831
832 #[test]
833 fn test_bound() {
834 let empty_map : TrieMap<uint> = TrieMap::new();
835 assert_eq!(empty_map.lower_bound(0).next(), None);
836 assert_eq!(empty_map.upper_bound(0).next(), None);
837
838 let last = 999u;
839 let step = 3u;
840 let value = 42u;
841
842 let mut map : TrieMap<uint> = TrieMap::new();
843 for x in range_step(0u, last, step) {
844 assert!(x % step == 0);
845 map.insert(x, value);
846 }
847
848 for i in range(0u, last - step) {
849 let mut lb = map.lower_bound(i);
850 let mut ub = map.upper_bound(i);
851 let next_key = i - i % step + step;
852 let next_pair = (next_key, &value);
853 if i % step == 0 {
854 assert_eq!(lb.next(), Some((i, &value)));
855 } else {
856 assert_eq!(lb.next(), Some(next_pair));
857 }
858 assert_eq!(ub.next(), Some(next_pair));
859 }
860
861 let mut lb = map.lower_bound(last - step);
862 assert_eq!(lb.next(), Some((last - step, &value)));
863 let mut ub = map.upper_bound(last - step);
864 assert_eq!(ub.next(), None);
865
866 for i in range(last - step + 1, last) {
867 let mut lb = map.lower_bound(i);
868 assert_eq!(lb.next(), None);
869 let mut ub = map.upper_bound(i);
870 assert_eq!(ub.next(), None);
871 }
872 }
873
874 #[test]
875 fn test_mut_bound() {
876 let empty_map : TrieMap<uint> = TrieMap::new();
877 assert_eq!(empty_map.lower_bound(0).next(), None);
878 assert_eq!(empty_map.upper_bound(0).next(), None);
879
880 let mut m_lower = TrieMap::new();
881 let mut m_upper = TrieMap::new();
882 for i in range(0u, 100) {
883 m_lower.insert(2 * i, 4 * i);
884 m_upper.insert(2 * i, 4 * i);
885 }
886
887 for i in range(0u, 199) {
888 let mut lb_it = m_lower.mut_lower_bound(i);
889 let (k, v) = lb_it.next().unwrap();
890 let lb = i + i % 2;
891 assert_eq!(lb, k);
892 *v -= k;
893 }
894
895 for i in range(0u, 198) {
896 let mut ub_it = m_upper.mut_upper_bound(i);
897 let (k, v) = ub_it.next().unwrap();
898 let ub = i + 2 - i % 2;
899 assert_eq!(ub, k);
900 *v -= k;
901 }
902
903 assert!(m_lower.mut_lower_bound(199).next().is_none());
904 assert!(m_upper.mut_upper_bound(198).next().is_none());
905
906 assert!(m_lower.iter().all(|(_, &x)| x == 0));
907 assert!(m_upper.iter().all(|(_, &x)| x == 0));
908 }
909 }
910
911 #[cfg(test)]
912 mod bench_map {
913 extern crate test;
914 use super::TrieMap;
915 use rand::{weak_rng, Rng};
916 use self::test::Bencher;
917
918 #[bench]
919 fn bench_iter_small(b: &mut Bencher) {
920 let mut m = TrieMap::<uint>::new();
921 let mut rng = weak_rng();
922 for _ in range(0, 20) {
923 m.insert(rng.gen(), rng.gen());
924 }
925
926 b.iter(|| for _ in m.iter() {})
927 }
928
929 #[bench]
930 fn bench_iter_large(b: &mut Bencher) {
931 let mut m = TrieMap::<uint>::new();
932 let mut rng = weak_rng();
933 for _ in range(0, 1000) {
934 m.insert(rng.gen(), rng.gen());
935 }
936
937 b.iter(|| for _ in m.iter() {})
938 }
939
940 #[bench]
941 fn bench_lower_bound(b: &mut Bencher) {
942 let mut m = TrieMap::<uint>::new();
943 let mut rng = weak_rng();
944 for _ in range(0, 1000) {
945 m.insert(rng.gen(), rng.gen());
946 }
947
948 b.iter(|| {
949 for _ in range(0, 10) {
950 m.lower_bound(rng.gen());
951 }
952 });
953 }
954
955 #[bench]
956 fn bench_upper_bound(b: &mut Bencher) {
957 let mut m = TrieMap::<uint>::new();
958 let mut rng = weak_rng();
959 for _ in range(0, 1000) {
960 m.insert(rng.gen(), rng.gen());
961 }
962
963 b.iter(|| {
964 for _ in range(0, 10) {
965 m.upper_bound(rng.gen());
966 }
967 });
968 }
969
970 #[bench]
971 fn bench_insert_large(b: &mut Bencher) {
972 let mut m = TrieMap::<[uint, .. 10]>::new();
973 let mut rng = weak_rng();
974
975 b.iter(|| {
976 for _ in range(0, 1000) {
977 m.insert(rng.gen(), [1, .. 10]);
978 }
979 })
980 }
981 #[bench]
982 fn bench_insert_large_low_bits(b: &mut Bencher) {
983 let mut m = TrieMap::<[uint, .. 10]>::new();
984 let mut rng = weak_rng();
985
986 b.iter(|| {
987 for _ in range(0, 1000) {
988 // only have the last few bits set.
989 m.insert(rng.gen::<uint>() & 0xff_ff, [1, .. 10]);
990 }
991 })
992 }
993
994 #[bench]
995 fn bench_insert_small(b: &mut Bencher) {
996 let mut m = TrieMap::<()>::new();
997 let mut rng = weak_rng();
998
999 b.iter(|| {
1000 for _ in range(0, 1000) {
1001 m.insert(rng.gen(), ());
1002 }
1003 })
1004 }
1005 #[bench]
1006 fn bench_insert_small_low_bits(b: &mut Bencher) {
1007 let mut m = TrieMap::<()>::new();
1008 let mut rng = weak_rng();
1009
1010 b.iter(|| {
1011 for _ in range(0, 1000) {
1012 // only have the last few bits set.
1013 m.insert(rng.gen::<uint>() & 0xff_ff, ());
1014 }
1015 })
1016 }
1017 }
1018
1019 #[cfg(test)]
1020 mod test_set {
1021 use super::TrieSet;
1022 use std::uint;
1023
1024 #[test]
1025 fn test_sane_chunk() {
1026 let x = 1;
1027 let y = 1 << (uint::BITS - 1);
1028
1029 let mut trie = TrieSet::new();
1030
1031 assert!(trie.insert(x));
1032 assert!(trie.insert(y));
1033
1034 assert_eq!(trie.len(), 2);
1035
1036 let expected = [x, y];
1037
1038 for (i, x) in trie.iter().enumerate() {
1039 assert_eq!(expected[i], x);
1040 }
1041 }
1042
1043 #[test]
1044 fn test_from_iter() {
1045 let xs = vec![9u, 8, 7, 6, 5, 4, 3, 2, 1];
1046
1047 let set: TrieSet = xs.iter().map(|&x| x).collect();
1048
1049 for x in xs.iter() {
1050 assert!(set.contains(x));
1051 }
1052 }
1053 }
libcollections/trie.rs:498:26-498:26 -struct- definition:
/// values being mutable.
pub struct MutEntries<'a, T> {
stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
references:- 8530: unsafe fn new() -> $name<'a, T> {
531: $name {
532: remaining_min: 0,
--
541: item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> {
542: // you might wonder why we're not even trying to act within the
libcollections/trie.rs:463:1-463:1 -fn- definition:
fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
idx: uint) -> Option<T> {
let (ret, this) = match *child {
references:- 294: fn pop(&mut self, key: &uint) -> Option<T> {
95: let ret = remove(&mut self.root.count,
96: &mut self.root.children[chunk(*key, 0)],
--
474: Internal(ref mut x) => {
475: let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
476: key, idx + 1);
libcollections/trie.rs:620:32-620:32 -struct- definition:
/// Forward iterator over a set
pub struct SetItems<'a> {
iter: Entries<'a, ()>
references:- 7357: pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
358: SetItems{iter: self.map.upper_bound(val)}
359: }
--
625: impl<'a> Iterator<uint> for SetItems<'a> {
626: fn next(&mut self) -> Option<uint> {
libcollections/trie.rs:31:22-31:22 -struct- definition:
pub struct TrieMap<T> {
root: TrieNode<T>,
length: uint
references:- 12106: pub fn new() -> TrieMap<T> {
107: TrieMap{root: TrieNode::new(), length: 0}
108: }
--
271: impl<T> Extendable<(uint, T)> for TrieMap<T> {
272: fn extend<Iter: Iterator<(uint, T)>>(&mut self, mut iter: Iter) {
--
280: pub struct TrieSet {
281: map: TrieMap<()>
282: }
libcollections/trie.rs:410:10-410:10 -fn- definition:
fn chunk(n: uint, idx: uint) -> uint {
let sh = uint::BITS - (SHIFT * (idx + 1));
(n >> sh) & MASK
references:- 11436: Internal(ref mut x) => {
437: return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
438: }
--
452: insert(&mut new.count,
453: &mut new.children[chunk(stored_key, idx)],
454: stored_key, stored_value, idx + 1);
455: let ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
456: key, value, idx + 1);
--
474: Internal(ref mut x) => {
475: let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
476: key, idx + 1);
libcollections/trie.rs:24:1-24:1 -enum- definition:
enum Child<T> {
Internal(Box<TrieNode<T>>),
External(uint, T),
references:- 6499: pub struct MutEntries<'a, T> {
500: stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
501: length: uint,
libcollections/trie.rs:415:1-415:1 -fn- definition:
fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
match *child {
External(stored, ref mut value) if stored == key => Some(value),
references:- 278: fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
79: find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
80: }
--
419: External(..) => None,
420: Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
421: Nothing => None
libcollections/trie.rs:424:1-424:1 -fn- definition:
fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
idx: uint) -> Option<T> {
// we branch twice to avoid having to do the `replace` when we
references:- 484: fn swap(&mut self, key: uint, value: T) -> Option<T> {
85: let ret = insert(&mut self.root.count,
86: &mut self.root.children[chunk(key, 0)],
--
454: stored_key, stored_value, idx + 1);
455: let ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
456: key, value, idx + 1);
libcollections/trie.rs:489:32-489:32 -struct- definition:
/// Forward iterator over a map
pub struct Entries<'a, T> {
stack: [slice::Items<'a, Child<T>>, .. NUM_CHUNKS],
references:- 9530: unsafe fn new() -> $name<'a, T> {
531: $name {
532: remaining_min: 0,
--
541: item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> {
542: // you might wonder why we're not even trying to act within the
--
621: pub struct SetItems<'a> {
622: iter: Entries<'a, ()>
623: }
libcollections/trie.rs:377:1-377:1 -struct- definition:
struct TrieNode<T> {
count: uint,
children: [Child<T>, ..SIZE]
references:- 11387: // copyability
388: TrieNode{count: 0,
389: children: [Nothing, Nothing, Nothing, Nothing,
--
396: impl<T> TrieNode<T> {
397: fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
libcollections/trie.rs:279:22-279:22 -struct- definition:
pub struct TrieSet {
map: TrieMap<()>
}
references:- 13302: #[inline]
303: fn is_disjoint(&self, other: &TrieSet) -> bool {
304: self.iter().all(|v| !other.contains(&v))
--
318: impl MutableSet<uint> for TrieSet {
319: #[inline]
--
362: impl FromIterator<uint> for TrieSet {
363: fn from_iter<Iter: Iterator<uint>>(iter: Iter) -> TrieSet {
364: let mut set = TrieSet::new();
--
370: impl Extendable<uint> for TrieSet {
371: fn extend<Iter: Iterator<uint>>(&mut self, mut iter: Iter) {