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 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             _ => fail!()
 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 => 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 = 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 }