src/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 //! Ordered containers with integer keys, implemented as radix tries (`TrieSet` and `TrieMap` types)
  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: |&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: |&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: |&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: |&'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: |&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: |&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: |&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<'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<'a>(&'a self, key: uint) -> TrieMapIterator<'a, T> {
 197         self.bound(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<'a>(&'a self, key: uint) -> TrieMapIterator<'a, T> {
 203         self.bound(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: |&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: |&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<'a>(&'a self, val: uint) -> TrieSetIterator<'a> {
 286         TrieSetIterator{iter: self.map.lower_bound(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<'a>(&'a self, val: uint) -> TrieSetIterator<'a> {
 292         TrieSetIterator{iter: self.map.upper_bound(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: |&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: |&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: |&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(stored, ref mut value) if stored == key => Some(value),
 377         External(..) => None,
 378         Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
 379         Nothing => None
 380     }
 381 }
 382
 383 fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
 384              idx: uint) -> Option<T> {
 385     let mut tmp = Nothing;
 386     let ret;
 387     swap(&mut tmp, child);
 388
 389     *child = match tmp {
 390       External(stored_key, stored_value) => {
 391           if stored_key == key {
 392               ret = Some(stored_value);
 393               External(stored_key, value)
 394           } else {
 395               // conflict - split the node
 396               let mut new = ~TrieNode::new();
 397               insert(&mut new.count,
 398                      &mut new.children[chunk(stored_key, idx)],
 399                      stored_key, stored_value, idx + 1);
 400               ret = insert(&mut new.count, &mut new.children[chunk(key, idx)],
 401                            key, value, idx + 1);
 402               Internal(new)
 403           }
 404       }
 405       Internal(x) => {
 406         let mut x = x;
 407         ret = insert(&mut x.count, &mut x.children[chunk(key, idx)], key,
 408                      value, idx + 1);
 409         Internal(x)
 410       }
 411       Nothing => {
 412         *count += 1;
 413         ret = None;
 414         External(key, value)
 415       }
 416     };
 417     return ret;
 418 }
 419
 420 fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
 421              idx: uint) -> Option<T> {
 422     let (ret, this) = match *child {
 423       External(stored, _) if stored == key => {
 424         match replace(child, Nothing) {
 425             External(_, value) => (Some(value), true),
 426             _ => fail!()
 427         }
 428       }
 429       External(..) => (None, false),
 430       Internal(ref mut x) => {
 431           let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
 432                            key, idx + 1);
 433           (ret, x.count == 0)
 434       }
 435       Nothing => (None, false)
 436     };
 437
 438     if this {
 439         *child = Nothing;
 440         *count -= 1;
 441     }
 442     return ret;
 443 }
 444
 445 /// Forward iterator over a map
 446 pub struct TrieMapIterator<'a, T> {
 447     priv stack: ~[vec::VecIterator<'a, Child<T>>],
 448     priv remaining_min: uint,
 449     priv remaining_max: uint
 450 }
 451
 452 impl<'a, T> Iterator<(uint, &'a T)> for TrieMapIterator<'a, T> {
 453     fn next(&mut self) -> Option<(uint, &'a T)> {
 454         while !self.stack.is_empty() {
 455             match self.stack[self.stack.len() - 1].next() {
 456                 None => {
 457                     self.stack.pop();
 458                 }
 459                 Some(ref child) => {
 460                     match **child {
 461                         Internal(ref node) => {
 462                             self.stack.push(node.children.iter());
 463                         }
 464                         External(key, ref value) => {
 465                             self.remaining_max -= 1;
 466                             if self.remaining_min > 0 {
 467                                 self.remaining_min -= 1;
 468                             }
 469                             return Some((key, value));
 470                         }
 471                         Nothing => {}
 472                     }
 473                 }
 474             }
 475         }
 476         return None;
 477     }
 478
 479     #[inline]
 480     fn size_hint(&self) -> (uint, Option<uint>) {
 481         (self.remaining_min, Some(self.remaining_max))
 482     }
 483 }
 484
 485 /// Forward iterator over a set
 486 pub struct TrieSetIterator<'a> {
 487     priv iter: TrieMapIterator<'a, ()>
 488 }
 489
 490 impl<'a> Iterator<uint> for TrieSetIterator<'a> {
 491     fn next(&mut self) -> Option<uint> {
 492         self.iter.next().map(|(key, _)| key)
 493     }
 494
 495     fn size_hint(&self) -> (uint, Option<uint>) {
 496         self.iter.size_hint()
 497     }
 498 }
 499
 500 #[cfg(test)]
 501 pub fn check_integrity<T>(trie: &TrieNode<T>) {
 502     assert!(trie.count != 0);
 503
 504     let mut sum = 0;
 505
 506     for x in trie.children.iter() {
 507         match *x {
 508           Nothing => (),
 509           Internal(ref y) => {
 510               check_integrity(&**y);
 511               sum += 1
 512           }
 513           External(_, _) => { sum += 1 }
 514         }
 515     }
 516
 517     assert_eq!(sum, trie.count);
 518 }
 519
 520 #[cfg(test)]
 521 mod test_map {
 522     use super::*;
 523     use prelude::*;
 524     use iter::range_step;
 525     use uint;
 526
 527     #[test]
 528     fn test_find_mut() {
 529         let mut m = TrieMap::new();
 530         assert!(m.insert(1, 12));
 531         assert!(m.insert(2, 8));
 532         assert!(m.insert(5, 14));
 533         let new = 100;
 534         match m.find_mut(&5) {
 535             None => fail!(), Some(x) => *x = new
 536         }
 537         assert_eq!(m.find(&5), Some(&new));
 538     }
 539
 540     #[test]
 541     fn test_find_mut_missing() {
 542         let mut m = TrieMap::new();
 543         assert!(m.find_mut(&0).is_none());
 544         assert!(m.insert(1, 12));
 545         assert!(m.find_mut(&0).is_none());
 546         assert!(m.insert(2, 8));
 547         assert!(m.find_mut(&0).is_none());
 548     }
 549
 550     #[test]
 551     fn test_step() {
 552         let mut trie = TrieMap::new();
 553         let n = 300u;
 554
 555         for x in range_step(1u, n, 2) {
 556             assert!(trie.insert(x, x + 1));
 557             assert!(trie.contains_key(&x));
 558             check_integrity(&trie.root);
 559         }
 560
 561         for x in range_step(0u, n, 2) {
 562             assert!(!trie.contains_key(&x));
 563             assert!(trie.insert(x, x + 1));
 564             check_integrity(&trie.root);
 565         }
 566
 567         for x in range(0u, n) {
 568             assert!(trie.contains_key(&x));
 569             assert!(!trie.insert(x, x + 1));
 570             check_integrity(&trie.root);
 571         }
 572
 573         for x in range_step(1u, n, 2) {
 574             assert!(trie.remove(&x));
 575             assert!(!trie.contains_key(&x));
 576             check_integrity(&trie.root);
 577         }
 578
 579         for x in range_step(0u, n, 2) {
 580             assert!(trie.contains_key(&x));
 581             assert!(!trie.insert(x, x + 1));
 582             check_integrity(&trie.root);
 583         }
 584     }
 585
 586     #[test]
 587     fn test_each() {
 588         let mut m = TrieMap::new();
 589
 590         assert!(m.insert(3, 6));
 591         assert!(m.insert(0, 0));
 592         assert!(m.insert(4, 8));
 593         assert!(m.insert(2, 4));
 594         assert!(m.insert(1, 2));
 595
 596         let mut n = 0;
 597         m.each(|k, v| {
 598             assert_eq!(*k, n);
 599             assert_eq!(*v, n * 2);
 600             n += 1;
 601             true
 602         });
 603     }
 604
 605     #[test]
 606     fn test_each_break() {
 607         let mut m = TrieMap::new();
 608
 609         for x in range(uint::max_value - 10000, uint::max_value).invert() {
 610             m.insert(x, x / 2);
 611         }
 612
 613         let mut n = uint::max_value - 10000;
 614         m.each(|k, v| {
 615             if n == uint::max_value - 5000 { false } else {
 616                 assert!(n < uint::max_value - 5000);
 617
 618                 assert_eq!(*k, n);
 619                 assert_eq!(*v, n / 2);
 620                 n += 1;
 621                 true
 622             }
 623         });
 624     }
 625
 626     #[test]
 627     fn test_each_reverse() {
 628         let mut m = TrieMap::new();
 629
 630         assert!(m.insert(3, 6));
 631         assert!(m.insert(0, 0));
 632         assert!(m.insert(4, 8));
 633         assert!(m.insert(2, 4));
 634         assert!(m.insert(1, 2));
 635
 636         let mut n = 4;
 637         m.each_reverse(|k, v| {
 638             assert_eq!(*k, n);
 639             assert_eq!(*v, n * 2);
 640             n -= 1;
 641             true
 642         });
 643     }
 644
 645     #[test]
 646     fn test_each_reverse_break() {
 647         let mut m = TrieMap::new();
 648
 649         for x in range(uint::max_value - 10000, uint::max_value).invert() {
 650             m.insert(x, x / 2);
 651         }
 652
 653         let mut n = uint::max_value - 1;
 654         m.each_reverse(|k, v| {
 655             if n == uint::max_value - 5000 { false } else {
 656                 assert!(n > uint::max_value - 5000);
 657
 658                 assert_eq!(*k, n);
 659                 assert_eq!(*v, n / 2);
 660                 n -= 1;
 661                 true
 662             }
 663         });
 664     }
 665
 666     #[test]
 667     fn test_swap() {
 668         let mut m = TrieMap::new();
 669         assert_eq!(m.swap(1, 2), None);
 670         assert_eq!(m.swap(1, 3), Some(2));
 671         assert_eq!(m.swap(1, 4), Some(3));
 672     }
 673
 674     #[test]
 675     fn test_pop() {
 676         let mut m = TrieMap::new();
 677         m.insert(1, 2);
 678         assert_eq!(m.pop(&1), Some(2));
 679         assert_eq!(m.pop(&1), None);
 680     }
 681
 682     #[test]
 683     fn test_from_iter() {
 684         let xs = ~[(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 685
 686         let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
 687
 688         for &(k, v) in xs.iter() {
 689             assert_eq!(map.find(&k), Some(&v));
 690         }
 691     }
 692
 693     #[test]
 694     fn test_iteration() {
 695         let empty_map : TrieMap<uint> = TrieMap::new();
 696         assert_eq!(empty_map.iter().next(), None);
 697
 698         let first = uint::max_value - 10000;
 699         let last = uint::max_value;
 700
 701         let mut map = TrieMap::new();
 702         for x in range(first, last).invert() {
 703             map.insert(x, x / 2);
 704         }
 705
 706         let mut i = 0;
 707         for (k, &v) in map.iter() {
 708             assert_eq!(k, first + i);
 709             assert_eq!(v, k / 2);
 710             i += 1;
 711         }
 712         assert_eq!(i, last - first);
 713     }
 714
 715     #[test]
 716     fn test_bound() {
 717         let empty_map : TrieMap<uint> = TrieMap::new();
 718         assert_eq!(empty_map.lower_bound(0).next(), None);
 719         assert_eq!(empty_map.upper_bound(0).next(), None);
 720
 721         let last = 999u;
 722         let step = 3u;
 723         let value = 42u;
 724
 725         let mut map : TrieMap<uint> = TrieMap::new();
 726         for x in range_step(0u, last, step) {
 727             assert!(x % step == 0);
 728             map.insert(x, value);
 729         }
 730
 731         for i in range(0u, last - step) {
 732             let mut lb = map.lower_bound(i);
 733             let mut ub = map.upper_bound(i);
 734             let next_key = i - i % step + step;
 735             let next_pair = (next_key, &value);
 736             if (i % step == 0) {
 737                 assert_eq!(lb.next(), Some((i, &value)));
 738             } else {
 739                 assert_eq!(lb.next(), Some(next_pair));
 740             }
 741             assert_eq!(ub.next(), Some(next_pair));
 742         }
 743
 744         let mut lb = map.lower_bound(last - step);
 745         assert_eq!(lb.next(), Some((last - step, &value)));
 746         let mut ub = map.upper_bound(last - step);
 747         assert_eq!(ub.next(), None);
 748
 749         for i in range(last - step + 1, last) {
 750             let mut lb = map.lower_bound(i);
 751             assert_eq!(lb.next(), None);
 752             let mut ub = map.upper_bound(i);
 753             assert_eq!(ub.next(), None);
 754         }
 755     }
 756 }
 757
 758 #[cfg(test)]
 759 mod test_set {
 760     use super::*;
 761     use prelude::*;
 762     use uint;
 763
 764     #[test]
 765     fn test_sane_chunk() {
 766         let x = 1;
 767         let y = 1 << (uint::bits - 1);
 768
 769         let mut trie = TrieSet::new();
 770
 771         assert!(trie.insert(x));
 772         assert!(trie.insert(y));
 773
 774         assert_eq!(trie.len(), 2);
 775
 776         let expected = [x, y];
 777
 778         let mut i = 0;
 779
 780         trie.each(|x| {
 781             assert_eq!(expected[i], *x);
 782             i += 1;
 783             true
 784         });
 785     }
 786
 787     #[test]
 788     fn test_from_iter() {
 789         let xs = ~[9u, 8, 7, 6, 5, 4, 3, 2, 1];
 790
 791         let set: TrieSet = xs.iter().map(|&x| x).collect();
 792
 793         for x in xs.iter() {
 794             assert!(set.contains(x));
 795         }
 796     }
 797 }