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