(index<- ) ./libstd/trie.rs
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.
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 //! An ordered map and set for integer keys implemented as a radix trie
12
13 use prelude::*;
14 use uint;
15 use util::{swap, replace};
16 use vec;
17
18 // FIXME: #5244: need to manually update the TrieNode constructor
19 static SHIFT: uint = 4;
20 static SIZE: uint = 1 << SHIFT;
21 static MASK: uint = SIZE - 1;
22
23 enum Child<T> {
24 Internal(~TrieNode<T>),
25 External(uint, T),
26 Nothing
27 }
28
29 #[allow(missing_doc)]
30 pub struct TrieMap<T> {
31 priv root: TrieNode<T>,
32 priv length: uint
33 }
34
35 impl<T> Container for TrieMap<T> {
36 /// Return the number of elements in the map
37 #[inline]
38 fn len(&self) -> uint { self.length }
39 }
40
41 impl<T> Mutable for TrieMap<T> {
42 /// Clear the map, removing all values.
43 #[inline]
44 fn clear(&mut self) {
45 self.root = TrieNode::new();
46 self.length = 0;
47 }
48 }
49
50 impl<T> Map<uint, T> for TrieMap<T> {
51 /// Return a reference to the value corresponding to the key
52 #[inline]
53 fn find<'a>(&'a self, key: &uint) -> Option<&'a T> {
54 let mut node: &'a TrieNode<T> = &self.root;
55 let mut idx = 0;
56 loop {
57 match node.children[chunk(*key, idx)] {
58 Internal(ref x) => node = &**x,
59 External(stored, ref value) => {
60 if stored == *key {
61 return Some(value)
62 } else {
63 return None
64 }
65 }
66 Nothing => return None
67 }
68 idx += 1;
69 }
70 }
71 }
72
73 impl<T> MutableMap<uint, T> for TrieMap<T> {
74 /// Return a mutable reference to the value corresponding to the key
75 #[inline]
76 fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
77 find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
78 }
79
80 /// Insert a key-value pair from the map. If the key already had a value
81 /// present in the map, that value is returned. Otherwise None is returned.
82 fn swap(&mut self, key: uint, value: T) -> Option<T> {
83 let ret = insert(&mut self.root.count,
84 &mut self.root.children[chunk(key, 0)],
85 key, value, 1);
86 if ret.is_none() { self.length += 1 }
87 ret
88 }
89
90 /// Removes a key from the map, returning the value at the key if the key
91 /// was previously in the map.
92 fn pop(&mut self, key: &uint) -> Option<T> {
93 let ret = remove(&mut self.root.count,
94 &mut self.root.children[chunk(*key, 0)],
95 *key, 1);
96 if ret.is_some() { self.length -= 1 }
97 ret
98 }
99 }
100
101 impl<T> TrieMap<T> {
102 /// Create an empty TrieMap
103 #[inline]
104 pub fn new() -> TrieMap<T> {
105 TrieMap{root: TrieNode::new(), length: 0}
106 }
107
108 /// Visit all key-value pairs in reverse order
109 #[inline]
110 pub fn each_reverse<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
111 self.root.each_reverse(f)
112 }
113
114 /// Visit all key-value pairs in order
115 #[inline]
116 pub fn each<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
117 self.root.each(f)
118 }
119
120 /// Visit all keys in order
121 #[inline]
122 pub fn each_key(&self, f: &fn(&uint) -> bool) -> bool {
123 self.each(|k, _| f(k))
124 }
125
126 /// Visit all values in order
127 #[inline]
128 pub fn each_value<'a>(&'a self, f: &fn(&'a T) -> bool) -> bool {
129 self.each(|_, v| f(v))
130 }
131
132 /// Iterate over the map and mutate the contained values
133 #[inline]
134 pub fn mutate_values(&mut self, f: &fn(&uint, &mut T) -> bool) -> bool {
135 self.root.mutate_values(f)
136 }
137
138 /// Visit all keys in reverse order
139 #[inline]
140 pub fn each_key_reverse(&self, f: &fn(&uint) -> bool) -> bool {
141 self.each_reverse(|k, _| f(k))
142 }
143
144 /// Visit all values in reverse order
145 #[inline]
146 pub fn each_value_reverse(&self, f: &fn(&T) -> bool) -> bool {
147 self.each_reverse(|_, v| f(v))
148 }
149
150 /// Get an iterator over the key-value pairs in the map
151 pub fn iter<'a>(&'a self) -> TrieMapIterator<'a, T> {
152 TrieMapIterator {
153 stack: ~[self.root.children.iter()],
154 remaining_min: self.length,
155 remaining_max: self.length
156 }
157 }
158
159 // If `upper` is true then returns upper_bound else returns lower_bound.
160 #[inline]
161 fn bound_iter<'a>(&'a self, key: uint, upper: bool) -> TrieMapIterator<'a, T> {
162 let mut node: &'a TrieNode<T> = &self.root;
163 let mut idx = 0;
164 let mut it = TrieMapIterator {
165 stack: ~[],
166 remaining_min: 0,
167 remaining_max: self.length
168 };
169 loop {
170 let children = &node.children;
171 let child_id = chunk(key, idx);
172 match children[child_id] {
173 Internal(ref n) => {
174 node = &**n;
175 it.stack.push(children.slice_from(child_id + 1).iter());
176 }
177 External(stored, _) => {
178 if stored < key || (upper && stored == key) {
179 it.stack.push(children.slice_from(child_id + 1).iter());
180 } else {
181 it.stack.push(children.slice_from(child_id).iter());
182 }
183 return it;
184 }
185 Nothing => {
186 it.stack.push(children.slice_from(child_id + 1).iter());
187 return it
188 }
189 }
190 idx += 1;
191 }
192 }
193
194 /// Get an iterator pointing to the first key-value pair whose key is not less than `key`.
195 /// If all keys in the map are less than `key` an empty iterator is returned.
196 pub fn lower_bound_iter<'a>(&'a self, key: uint) -> TrieMapIterator<'a, T> {
197 self.bound_iter(key, false)
198 }
199
200 /// Get an iterator pointing to the first key-value pair whose key is greater than `key`.
201 /// If all keys in the map are not greater than `key` an empty iterator is returned.
202 pub fn upper_bound_iter<'a>(&'a self, key: uint) -> TrieMapIterator<'a, T> {
203 self.bound_iter(key, true)
204 }
205 }
206
207 impl<T> FromIterator<(uint, T)> for TrieMap<T> {
208 fn from_iterator<Iter: Iterator<(uint, T)>>(iter: &mut Iter) -> TrieMap<T> {
209 let mut map = TrieMap::new();
210 map.extend(iter);
211 map
212 }
213 }
214
215 impl<T> Extendable<(uint, T)> for TrieMap<T> {
216 fn extend<Iter: Iterator<(uint, T)>>(&mut self, iter: &mut Iter) {
217 for (k, v) in *iter {
218 self.insert(k, v);
219 }
220 }
221 }
222
223 #[allow(missing_doc)]
224 pub struct TrieSet {
225 priv map: TrieMap<()>
226 }
227
228 impl Container for TrieSet {
229 /// Return the number of elements in the set
230 #[inline]
231 fn len(&self) -> uint { self.map.len() }
232 }
233
234 impl Mutable for TrieSet {
235 /// Clear the set, removing all values.
236 #[inline]
237 fn clear(&mut self) { self.map.clear() }
238 }
239
240 impl TrieSet {
241 /// Create an empty TrieSet
242 #[inline]
243 pub fn new() -> TrieSet {
244 TrieSet{map: TrieMap::new()}
245 }
246
247 /// Return true if the set contains a value
248 #[inline]
249 pub fn contains(&self, value: &uint) -> bool {
250 self.map.contains_key(value)
251 }
252
253 /// Add a value to the set. Return true if the value was not already
254 /// present in the set.
255 #[inline]
256 pub fn insert(&mut self, value: uint) -> bool {
257 self.map.insert(value, ())
258 }
259
260 /// Remove a value from the set. Return true if the value was
261 /// present in the set.
262 #[inline]
263 pub fn remove(&mut self, value: &uint) -> bool {
264 self.map.remove(value)
265 }
266
267 /// Visit all values in order
268 #[inline]
269 pub fn each(&self, f: &fn(&uint) -> bool) -> bool { self.map.each_key(f) }
270
271 /// Visit all values in reverse order
272 #[inline]
273 pub fn each_reverse(&self, f: &fn(&uint) -> bool) -> bool {
274 self.map.each_key_reverse(f)
275 }
276
277 /// Get an iterator over the values in the set
278 #[inline]
279 pub fn iter<'a>(&'a self) -> TrieSetIterator<'a> {
280 TrieSetIterator{iter: self.map.iter()}
281 }
282
283 /// Get an iterator pointing to the first value that is not less than `val`.
284 /// If all values in the set are less than `val` an empty iterator is returned.
285 pub fn lower_bound_iter<'a>(&'a self, val: uint) -> TrieSetIterator<'a> {
286 TrieSetIterator{iter: self.map.lower_bound_iter(val)}
287 }
288
289 /// Get an iterator pointing to the first value that key is greater than `val`.
290 /// If all values in the set are not greater than `val` an empty iterator is returned.
291 pub fn upper_bound_iter<'a>(&'a self, val: uint) -> TrieSetIterator<'a> {
292 TrieSetIterator{iter: self.map.upper_bound_iter(val)}
293 }
294 }
295
296 impl FromIterator<uint> for TrieSet {
297 fn from_iterator<Iter: Iterator<uint>>(iter: &mut Iter) -> TrieSet {
298 let mut set = TrieSet::new();
299 set.extend(iter);
300 set
301 }
302 }
303
304 impl Extendable<uint> for TrieSet {
305 fn extend<Iter: Iterator<uint>>(&mut self, iter: &mut Iter) {
306 for elem in *iter {
307 self.insert(elem);
308 }
309 }
310 }
311
312 struct TrieNode<T> {
313 count: uint,
314 children: [Child<T>, ..SIZE]
315 }
316
317 impl<T> TrieNode<T> {
318 #[inline]
319 fn new() -> TrieNode<T> {
320 // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit
321 // copyability
322 TrieNode{count: 0,
323 children: [Nothing, Nothing, Nothing, Nothing,
324 Nothing, Nothing, Nothing, Nothing,
325 Nothing, Nothing, Nothing, Nothing,
326 Nothing, Nothing, Nothing, Nothing]}
327 }
328 }
329
330 impl<T> TrieNode<T> {
331 fn each<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
332 for elt in self.children.iter() {
333 match *elt {
334 Internal(ref x) => if !x.each(|i,t| f(i,t)) { return false },
335 External(k, ref v) => if !f(&k, v) { return false },
336 Nothing => ()
337 }
338 }
339 true
340 }
341
342 fn each_reverse<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
343 for elt in self.children.rev_iter() {
344 match *elt {
345 Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false },
346 External(k, ref v) => if !f(&k, v) { return false },
347 Nothing => ()
348 }
349 }
350 true
351 }
352
353 fn mutate_values<'a>(&'a mut self, f: &fn(&uint, &mut T) -> bool) -> bool {
354 for child in self.children.mut_iter() {
355 match *child {
356 Internal(ref mut x) => if !x.mutate_values(|i,t| f(i,t)) {
357 return false
358 },
359 External(k, ref mut v) => if !f(&k, v) { return false },
360 Nothing => ()
361 }
362 }
363 true
364 }
365 }
366
367 // if this was done via a trait, the key could be generic
368 #[inline]
369 fn chunk(n: uint, idx: uint) -> uint {
370 let sh = uint::bits - (SHIFT * (idx + 1));
371 (n >> sh) & MASK
372 }
373
374 fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
375 match *child {
376 External(_, ref mut value) => Some(value),
377 Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
378 Nothing => None
379 }
380 }
381
382 fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
383 idx: uint) -> Option<T> {
384 let mut tmp = Nothing;
385 let ret;
386 swap(&mut tmp, child);
387
388 *child = match tmp {
389 External(stored_key, stored_value) => {
390 if stored_key == key {
391 ret = Some(stored_value);
392 External(stored_key, value)
393 } else {
394 // conflict - split the node
395 let mut new = ~TrieNode::new();
396 insert(&mut new.count,
397 &mut new.children[chunk(stored_key, idx)],
398 stored_key, stored_value, idx + 1);
399 ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
400 key, value, idx + 1);
401 Internal(new)
402 }
403 }
404 Internal(x) => {
405 let mut x = x;
406 ret = insert(&mut x.count, &mut x.children[chunk(key, idx)], key,
407 value, idx + 1);
408 Internal(x)
409 }
410 Nothing => {
411 *count += 1;
412 ret = None;
413 External(key, value)
414 }
415 };
416 return ret;
417 }
418
419 fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
420 idx: uint) -> Option<T> {
421 let (ret, this) = match *child {
422 External(stored, _) if stored == key => {
423 match replace(child, Nothing) {
424 External(_, value) => (Some(value), true),
425 _ => fail2!()
426 }
427 }
428 External(*) => (None, false),
429 Internal(ref mut x) => {
430 let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
431 key, idx + 1);
432 (ret, x.count == 0)
433 }
434 Nothing => (None, false)
435 };
436
437 if this {
438 *child = Nothing;
439 *count -= 1;
440 }
441 return ret;
442 }
443
444 /// Forward iterator over a map
445 pub struct TrieMapIterator<'self, T> {
446 priv stack: ~[vec::VecIterator<'self, Child<T>>],
447 priv remaining_min: uint,
448 priv remaining_max: uint
449 }
450
451 impl<'self, T> Iterator<(uint, &'self T)> for TrieMapIterator<'self, T> {
452 fn next(&mut self) -> Option<(uint, &'self T)> {
453 while !self.stack.is_empty() {
454 match self.stack[self.stack.len() - 1].next() {
455 None => {
456 self.stack.pop();
457 }
458 Some(ref child) => {
459 match **child {
460 Internal(ref node) => {
461 self.stack.push(node.children.iter());
462 }
463 External(key, ref value) => {
464 self.remaining_max -= 1;
465 if self.remaining_min > 0 {
466 self.remaining_min -= 1;
467 }
468 return Some((key, value));
469 }
470 Nothing => {}
471 }
472 }
473 }
474 }
475 return None;
476 }
477
478 #[inline]
479 fn size_hint(&self) -> (uint, Option<uint>) {
480 (self.remaining_min, Some(self.remaining_max))
481 }
482 }
483
484 /// Forward iterator over a set
485 pub struct TrieSetIterator<'self> {
486 priv iter: TrieMapIterator<'self, ()>
487 }
488
489 impl<'self> Iterator<uint> for TrieSetIterator<'self> {
490 fn next(&mut self) -> Option<uint> {
491 do self.iter.next().map |(key, _)| { key }
492 }
493
494 fn size_hint(&self) -> (uint, Option<uint>) {
495 self.iter.size_hint()
496 }
497 }
498
499 #[cfg(test)]
500 pub fn check_integrity<T>(trie: &TrieNode<T>) {
501 assert!(trie.count != 0);
502
503 let mut sum = 0;
504
505 for x in trie.children.iter() {
506 match *x {
507 Nothing => (),
508 Internal(ref y) => {
509 check_integrity(&**y);
510 sum += 1
511 }
512 External(_, _) => { sum += 1 }
513 }
514 }
515
516 assert_eq!(sum, trie.count);
517 }
518
519 #[cfg(test)]
520 mod test_map {
521 use super::*;
522 use prelude::*;
523 use iter::range_step;
524 use uint;
525
526 #[test]
527 fn test_find_mut() {
528 let mut m = TrieMap::new();
529 assert!(m.insert(1, 12));
530 assert!(m.insert(2, 8));
531 assert!(m.insert(5, 14));
532 let new = 100;
533 match m.find_mut(&5) {
534 None => fail2!(), Some(x) => *x = new
535 }
536 assert_eq!(m.find(&5), Some(&new));
537 }
538
539 #[test]
540 fn test_step() {
541 let mut trie = TrieMap::new();
542 let n = 300u;
543
544 for x in range_step(1u, n, 2) {
545 assert!(trie.insert(x, x + 1));
546 assert!(trie.contains_key(&x));
547 check_integrity(&trie.root);
548 }
549
550 for x in range_step(0u, n, 2) {
551 assert!(!trie.contains_key(&x));
552 assert!(trie.insert(x, x + 1));
553 check_integrity(&trie.root);
554 }
555
556 for x in range(0u, n) {
557 assert!(trie.contains_key(&x));
558 assert!(!trie.insert(x, x + 1));
559 check_integrity(&trie.root);
560 }
561
562 for x in range_step(1u, n, 2) {
563 assert!(trie.remove(&x));
564 assert!(!trie.contains_key(&x));
565 check_integrity(&trie.root);
566 }
567
568 for x in range_step(0u, n, 2) {
569 assert!(trie.contains_key(&x));
570 assert!(!trie.insert(x, x + 1));
571 check_integrity(&trie.root);
572 }
573 }
574
575 #[test]
576 fn test_each() {
577 let mut m = TrieMap::new();
578
579 assert!(m.insert(3, 6));
580 assert!(m.insert(0, 0));
581 assert!(m.insert(4, 8));
582 assert!(m.insert(2, 4));
583 assert!(m.insert(1, 2));
584
585 let mut n = 0;
586 do m.each |k, v| {
587 assert_eq!(*k, n);
588 assert_eq!(*v, n * 2);
589 n += 1;
590 true
591 };
592 }
593
594 #[test]
595 fn test_each_break() {
596 let mut m = TrieMap::new();
597
598 for x in range(uint::max_value - 10000, uint::max_value).invert() {
599 m.insert(x, x / 2);
600 }
601
602 let mut n = uint::max_value - 10000;
603 do m.each |k, v| {
604 if n == uint::max_value - 5000 { false } else {
605 assert!(n < uint::max_value - 5000);
606
607 assert_eq!(*k, n);
608 assert_eq!(*v, n / 2);
609 n += 1;
610 true
611 }
612 };
613 }
614
615 #[test]
616 fn test_each_reverse() {
617 let mut m = TrieMap::new();
618
619 assert!(m.insert(3, 6));
620 assert!(m.insert(0, 0));
621 assert!(m.insert(4, 8));
622 assert!(m.insert(2, 4));
623 assert!(m.insert(1, 2));
624
625 let mut n = 4;
626 do m.each_reverse |k, v| {
627 assert_eq!(*k, n);
628 assert_eq!(*v, n * 2);
629 n -= 1;
630 true
631 };
632 }
633
634 #[test]
635 fn test_each_reverse_break() {
636 let mut m = TrieMap::new();
637
638 for x in range(uint::max_value - 10000, uint::max_value).invert() {
639 m.insert(x, x / 2);
640 }
641
642 let mut n = uint::max_value - 1;
643 do m.each_reverse |k, v| {
644 if n == uint::max_value - 5000 { false } else {
645 assert!(n > uint::max_value - 5000);
646
647 assert_eq!(*k, n);
648 assert_eq!(*v, n / 2);
649 n -= 1;
650 true
651 }
652 };
653 }
654
655 #[test]
656 fn test_swap() {
657 let mut m = TrieMap::new();
658 assert_eq!(m.swap(1, 2), None);
659 assert_eq!(m.swap(1, 3), Some(2));
660 assert_eq!(m.swap(1, 4), Some(3));
661 }
662
663 #[test]
664 fn test_pop() {
665 let mut m = TrieMap::new();
666 m.insert(1, 2);
667 assert_eq!(m.pop(&1), Some(2));
668 assert_eq!(m.pop(&1), None);
669 }
670
671 #[test]
672 fn test_from_iter() {
673 let xs = ~[(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
674
675 let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
676
677 for &(k, v) in xs.iter() {
678 assert_eq!(map.find(&k), Some(&v));
679 }
680 }
681
682 #[test]
683 fn test_iteration() {
684 let empty_map : TrieMap<uint> = TrieMap::new();
685 assert_eq!(empty_map.iter().next(), None);
686
687 let first = uint::max_value - 10000;
688 let last = uint::max_value;
689
690 let mut map = TrieMap::new();
691 for x in range(first, last).invert() {
692 map.insert(x, x / 2);
693 }
694
695 let mut i = 0;
696 for (k, &v) in map.iter() {
697 assert_eq!(k, first + i);
698 assert_eq!(v, k / 2);
699 i += 1;
700 }
701 assert_eq!(i, last - first);
702 }
703
704 #[test]
705 fn test_bound_iter() {
706 let empty_map : TrieMap<uint> = TrieMap::new();
707 assert_eq!(empty_map.lower_bound_iter(0).next(), None);
708 assert_eq!(empty_map.upper_bound_iter(0).next(), None);
709
710 let last = 999u;
711 let step = 3u;
712 let value = 42u;
713
714 let mut map : TrieMap<uint> = TrieMap::new();
715 for x in range_step(0u, last, step) {
716 assert!(x % step == 0);
717 map.insert(x, value);
718 }
719
720 for i in range(0u, last - step) {
721 let mut lb = map.lower_bound_iter(i);
722 let mut ub = map.upper_bound_iter(i);
723 let next_key = i - i % step + step;
724 let next_pair = (next_key, &value);
725 if (i % step == 0) {
726 assert_eq!(lb.next(), Some((i, &value)));
727 } else {
728 assert_eq!(lb.next(), Some(next_pair));
729 }
730 assert_eq!(ub.next(), Some(next_pair));
731 }
732
733 let mut lb = map.lower_bound_iter(last - step);
734 assert_eq!(lb.next(), Some((last - step, &value)));
735 let mut ub = map.upper_bound_iter(last - step);
736 assert_eq!(ub.next(), None);
737
738 for i in range(last - step + 1, last) {
739 let mut lb = map.lower_bound_iter(i);
740 assert_eq!(lb.next(), None);
741 let mut ub = map.upper_bound_iter(i);
742 assert_eq!(ub.next(), None);
743 }
744 }
745 }
746
747 #[cfg(test)]
748 mod test_set {
749 use super::*;
750 use prelude::*;
751 use uint;
752
753 #[test]
754 fn test_sane_chunk() {
755 let x = 1;
756 let y = 1 << (uint::bits - 1);
757
758 let mut trie = TrieSet::new();
759
760 assert!(trie.insert(x));
761 assert!(trie.insert(y));
762
763 assert_eq!(trie.len(), 2);
764
765 let expected = [x, y];
766
767 let mut i = 0;
768
769 do trie.each |x| {
770 assert_eq!(expected[i], *x);
771 i += 1;
772 true
773 };
774 }
775
776 #[test]
777 fn test_from_iter() {
778 let xs = ~[9u, 8, 7, 6, 5, 4, 3, 2, 1];
779
780 let set: TrieSet = xs.iter().map(|&x| x).collect();
781
782 for x in xs.iter() {
783 assert!(set.contains(x));
784 }
785 }
786 }
libstd/trie.rs:418:1-418:1 -fn- definition:
fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
references:-93: let ret = remove(&mut self.root.count,
430: let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
libstd/trie.rs:22:1-22:1 -enum- definition:
enum Child<T> {
references:-314: children: [Child<T>, ..SIZE]
446: priv stack: ~[vec::VecIterator<'self, Child<T>>],
374: fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
382: fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
419: fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
libstd/trie.rs:29:22-29:22 -struct- definition:
#[allow(missing_doc)]
pub struct TrieMap<T> {
references:-215: impl<T> Extendable<(uint, T)> for TrieMap<T> {
101: impl<T> TrieMap<T> {
225: priv map: TrieMap<()>
105: TrieMap{root: TrieNode::new(), length: 0}
41: impl<T> Mutable for TrieMap<T> {
208: fn from_iterator<Iter: Iterator<(uint, T)>>(iter: &mut Iter) -> TrieMap<T> {
35: impl<T> Container for TrieMap<T> {
50: impl<T> Map<uint, T> for TrieMap<T> {
104: pub fn new() -> TrieMap<T> {
73: impl<T> MutableMap<uint, T> for TrieMap<T> {
207: impl<T> FromIterator<(uint, T)> for TrieMap<T> {
libstd/trie.rs:368:10-368:10 -fn- definition:
#[inline]
fn chunk(n: uint, idx: uint) -> uint {
references:-77: find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
377: Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
406: ret = insert(&mut x.count, &mut x.children[chunk(key, idx)], key,
397: &mut new.children[chunk(stored_key, idx)],
399: ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
94: &mut self.root.children[chunk(*key, 0)],
171: let child_id = chunk(key, idx);
57: match node.children[chunk(*key, idx)] {
84: &mut self.root.children[chunk(key, 0)],
430: let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
libstd/trie.rs:484:32-484:32 -struct- definition:
/// Forward iterator over a set
pub struct TrieSetIterator<'self> {
references:-286: TrieSetIterator{iter: self.map.lower_bound_iter(val)}
279: pub fn iter<'a>(&'a self) -> TrieSetIterator<'a> {
291: pub fn upper_bound_iter<'a>(&'a self, val: uint) -> TrieSetIterator<'a> {
489: impl<'self> Iterator<uint> for TrieSetIterator<'self> {
285: pub fn lower_bound_iter<'a>(&'a self, val: uint) -> TrieSetIterator<'a> {
292: TrieSetIterator{iter: self.map.upper_bound_iter(val)}
280: TrieSetIterator{iter: self.map.iter()}
libstd/trie.rs:381:1-381:1 -fn- definition:
fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
references:-406: ret = insert(&mut x.count, &mut x.children[chunk(key, idx)], key,
83: let ret = insert(&mut self.root.count,
396: insert(&mut new.count,
399: ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
libstd/trie.rs:373:1-373:1 -fn- definition:
fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> {
references:-377: Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
77: find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
libstd/trie.rs:444:32-444:32 -struct- definition:
/// Forward iterator over a map
pub struct TrieMapIterator<'self, T> {
references:-196: pub fn lower_bound_iter<'a>(&'a self, key: uint) -> TrieMapIterator<'a, T> {
152: TrieMapIterator {
161: fn bound_iter<'a>(&'a self, key: uint, upper: bool) -> TrieMapIterator<'a, T> {
151: pub fn iter<'a>(&'a self) -> TrieMapIterator<'a, T> {
202: pub fn upper_bound_iter<'a>(&'a self, key: uint) -> TrieMapIterator<'a, T> {
451: impl<'self, T> Iterator<(uint, &'self T)> for TrieMapIterator<'self, T> {
164: let mut it = TrieMapIterator {
486: priv iter: TrieMapIterator<'self, ()>
libstd/trie.rs:311:1-311:1 -struct- definition:
struct TrieNode<T> {
references:-330: impl<T> TrieNode<T> {
54: let mut node: &'a TrieNode<T> = &self.root;
317: impl<T> TrieNode<T> {
24: Internal(~TrieNode<T>),
31: priv root: TrieNode<T>,
162: let mut node: &'a TrieNode<T> = &self.root;
322: TrieNode{count: 0,
319: fn new() -> TrieNode<T> {
libstd/trie.rs:223:22-223:22 -struct- definition:
#[allow(missing_doc)]
pub struct TrieSet {
references:-304: impl Extendable<uint> for TrieSet {
243: pub fn new() -> TrieSet {
297: fn from_iterator<Iter: Iterator<uint>>(iter: &mut Iter) -> TrieSet {
228: impl Container for TrieSet {
234: impl Mutable for TrieSet {
296: impl FromIterator<uint> for TrieSet {
240: impl TrieSet {
244: TrieSet{map: TrieMap::new()}