src/libcollections/trie/set.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // FIXME(conventions): implement bounded iterators
  12 // FIXME(conventions): replace each_reverse by making iter DoubleEnded
  13 // FIXME(conventions): implement iter_mut and into_iter
  14
  15 use core::prelude::*;
  16
  17 use core::default::Default;
  18 use core::fmt;
  19 use core::fmt::Show;
  20 use core::iter::Peekable;
  21 use std::hash::Hash;
  22
  23 use trie_map::{TrieMap, Entries};
  24
  25 /// A set implemented as a radix trie.
  26 ///
  27 /// # Example
  28 ///
  29 /// ```
  30 /// use std::collections::TrieSet;
  31 ///
  32 /// let mut set = TrieSet::new();
  33 /// set.insert(6);
  34 /// set.insert(28);
  35 /// set.insert(6);
  36 ///
  37 /// assert_eq!(set.len(), 2);
  38 ///
  39 /// if !set.contains(&3) {
  40 ///     println!("3 is not in the set");
  41 /// }
  42 ///
  43 /// // Print contents in order
  44 /// for x in set.iter() {
  45 ///     println!("{}", x);
  46 /// }
  47 ///
  48 /// set.remove(&6);
  49 /// assert_eq!(set.len(), 1);
  50 ///
  51 /// set.clear();
  52 /// assert!(set.is_empty());
  53 /// ```
  54 #[deriving(Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
  55 pub struct TrieSet {
  56     map: TrieMap<()>
  57 }
  58
  59 impl Show for TrieSet {
  60     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  61         try!(write!(f, "{{"));
  62
  63         for (i, x) in self.iter().enumerate() {
  64             if i != 0 { try!(write!(f, ", ")); }
  65             try!(write!(f, "{}", x));
  66         }
  67
  68         write!(f, "}}")
  69     }
  70 }
  71
  72 impl Default for TrieSet {
  73     #[inline]
  74     fn default() -> TrieSet { TrieSet::new() }
  75 }
  76
  77 impl TrieSet {
  78     /// Creates an empty TrieSet.
  79     ///
  80     /// # Example
  81     ///
  82     /// ```
  83     /// use std::collections::TrieSet;
  84     /// let mut set = TrieSet::new();
  85     /// ```
  86     #[inline]
  87     #[unstable = "matches collection reform specification, waiting for dust to settle"]
  88     pub fn new() -> TrieSet {
  89         TrieSet{map: TrieMap::new()}
  90     }
  91
  92     /// Visits all values in reverse order. Aborts traversal when `f` returns `false`.
  93     /// Returns `true` if `f` returns `true` for all elements.
  94     ///
  95     /// # Example
  96     ///
  97     /// ```
  98     /// use std::collections::TrieSet;
  99     ///
 100     /// let set: TrieSet = [1, 2, 3, 4, 5].iter().map(|&x| x).collect();
 101     ///
 102     /// let mut vec = Vec::new();
 103     /// assert_eq!(true, set.each_reverse(|&x| { vec.push(x); true }));
 104     /// assert_eq!(vec, vec![5, 4, 3, 2, 1]);
 105     ///
 106     /// // Stop when we reach 3
 107     /// let mut vec = Vec::new();
 108     /// assert_eq!(false, set.each_reverse(|&x| { vec.push(x); x != 3 }));
 109     /// assert_eq!(vec, vec![5, 4, 3]);
 110     /// ```
 111     #[inline]
 112     pub fn each_reverse(&self, f: |&uint| -> bool) -> bool {
 113         self.map.each_reverse(|k, _| f(k))
 114     }
 115
 116     /// Gets an iterator over the values in the set, in sorted order.
 117     ///
 118     /// # Example
 119     ///
 120     /// ```
 121     /// use std::collections::TrieSet;
 122     ///
 123     /// let mut set = TrieSet::new();
 124     /// set.insert(3);
 125     /// set.insert(2);
 126     /// set.insert(1);
 127     /// set.insert(2);
 128     ///
 129     /// // Print 1, 2, 3
 130     /// for x in set.iter() {
 131     ///     println!("{}", x);
 132     /// }
 133     /// ```
 134     #[inline]
 135     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 136     pub fn iter<'a>(&'a self) -> SetItems<'a> {
 137         SetItems{iter: self.map.iter()}
 138     }
 139
 140     /// Gets an iterator pointing to the first value that is not less than `val`.
 141     /// If all values in the set are less than `val` an empty iterator is returned.
 142     ///
 143     /// # Example
 144     ///
 145     /// ```
 146     /// use std::collections::TrieSet;
 147     ///
 148     /// let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect();
 149     /// assert_eq!(set.lower_bound(4).next(), Some(4));
 150     /// assert_eq!(set.lower_bound(5).next(), Some(6));
 151     /// assert_eq!(set.lower_bound(10).next(), None);
 152     /// ```
 153     pub fn lower_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
 154         SetItems{iter: self.map.lower_bound(val)}
 155     }
 156
 157     /// Gets an iterator pointing to the first value that key is greater than `val`.
 158     /// If all values in the set are less than or equal to `val` an empty iterator is returned.
 159     ///
 160     /// # Example
 161     ///
 162     /// ```
 163     /// use std::collections::TrieSet;
 164     ///
 165     /// let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect();
 166     /// assert_eq!(set.upper_bound(4).next(), Some(6));
 167     /// assert_eq!(set.upper_bound(5).next(), Some(6));
 168     /// assert_eq!(set.upper_bound(10).next(), None);
 169     /// ```
 170     pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> {
 171         SetItems{iter: self.map.upper_bound(val)}
 172     }
 173
 174     /// Visits the values representing the difference, in ascending order.
 175     ///
 176     /// # Example
 177     ///
 178     /// ```
 179     /// use std::collections::TrieSet;
 180     ///
 181     /// let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 182     /// let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect();
 183     ///
 184     /// // Can be seen as `a - b`.
 185     /// for x in a.difference(&b) {
 186     ///     println!("{}", x); // Print 1 then 2
 187     /// }
 188     ///
 189     /// let diff1: TrieSet = a.difference(&b).collect();
 190     /// assert_eq!(diff1, [1, 2].iter().map(|&x| x).collect());
 191     ///
 192     /// // Note that difference is not symmetric,
 193     /// // and `b - a` means something else:
 194     /// let diff2: TrieSet = b.difference(&a).collect();
 195     /// assert_eq!(diff2, [4, 5].iter().map(|&x| x).collect());
 196     /// ```
 197     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 198     pub fn difference<'a>(&'a self, other: &'a TrieSet) -> DifferenceItems<'a> {
 199         DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
 200     }
 201
 202     /// Visits the values representing the symmetric difference, in ascending order.
 203     ///
 204     /// # Example
 205     ///
 206     /// ```
 207     /// use std::collections::TrieSet;
 208     ///
 209     /// let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 210     /// let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect();
 211     ///
 212     /// // Print 1, 2, 4, 5 in ascending order.
 213     /// for x in a.symmetric_difference(&b) {
 214     ///     println!("{}", x);
 215     /// }
 216     ///
 217     /// let diff1: TrieSet = a.symmetric_difference(&b).collect();
 218     /// let diff2: TrieSet = b.symmetric_difference(&a).collect();
 219     ///
 220     /// assert_eq!(diff1, diff2);
 221     /// assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect());
 222     /// ```
 223     #[unstable = "matches collection reform specification, waiting for dust to settle."]
 224     pub fn symmetric_difference<'a>(&'a self, other: &'a TrieSet) -> SymDifferenceItems<'a> {
 225         SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
 226     }
 227
 228     /// Visits the values representing the intersection, in ascending order.
 229     ///
 230     /// # Example
 231     ///
 232     /// ```
 233     /// use std::collections::TrieSet;
 234     ///
 235     /// let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 236     /// let b: TrieSet = [2, 3, 4].iter().map(|&x| x).collect();
 237     ///
 238     /// // Print 2, 3 in ascending order.
 239     /// for x in a.intersection(&b) {
 240     ///     println!("{}", x);
 241     /// }
 242     ///
 243     /// let diff: TrieSet = a.intersection(&b).collect();
 244     /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect());
 245     /// ```
 246     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 247     pub fn intersection<'a>(&'a self, other: &'a TrieSet) -> IntersectionItems<'a> {
 248         IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()}
 249     }
 250
 251     /// Visits the values representing the union, in ascending order.
 252     ///
 253     /// # Example
 254     ///
 255     /// ```
 256     /// use std::collections::TrieSet;
 257     ///
 258     /// let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 259     /// let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect();
 260     ///
 261     /// // Print 1, 2, 3, 4, 5 in ascending order.
 262     /// for x in a.union(&b) {
 263     ///     println!("{}", x);
 264     /// }
 265     ///
 266     /// let diff: TrieSet = a.union(&b).collect();
 267     /// assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect());
 268     /// ```
 269     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 270     pub fn union<'a>(&'a self, other: &'a TrieSet) -> UnionItems<'a> {
 271         UnionItems{a: self.iter().peekable(), b: other.iter().peekable()}
 272     }
 273
 274     /// Return the number of elements in the set
 275     ///
 276     /// # Example
 277     ///
 278     /// ```
 279     /// use std::collections::TrieSet;
 280     ///
 281     /// let mut v = TrieSet::new();
 282     /// assert_eq!(v.len(), 0);
 283     /// v.insert(1);
 284     /// assert_eq!(v.len(), 1);
 285     /// ```
 286     #[inline]
 287     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 288     pub fn len(&self) -> uint { self.map.len() }
 289
 290     /// Returns true if the set contains no elements
 291     ///
 292     /// # Example
 293     ///
 294     /// ```
 295     /// use std::collections::TrieSet;
 296     ///
 297     /// let mut v = TrieSet::new();
 298     /// assert!(v.is_empty());
 299     /// v.insert(1);
 300     /// assert!(!v.is_empty());
 301     /// ```
 302     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 303     pub fn is_empty(&self) -> bool { self.len() == 0 }
 304
 305     /// Clears the set, removing all values.
 306     ///
 307     /// # Example
 308     ///
 309     /// ```
 310     /// use std::collections::TrieSet;
 311     ///
 312     /// let mut v = TrieSet::new();
 313     /// v.insert(1);
 314     /// v.clear();
 315     /// assert!(v.is_empty());
 316     /// ```
 317     #[inline]
 318     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 319     pub fn clear(&mut self) { self.map.clear() }
 320
 321     /// Returns `true` if the set contains a value.
 322     ///
 323     /// # Example
 324     ///
 325     /// ```
 326     /// use std::collections::TrieSet;
 327     ///
 328     /// let set: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 329     /// assert_eq!(set.contains(&1), true);
 330     /// assert_eq!(set.contains(&4), false);
 331     /// ```
 332     #[inline]
 333     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 334     pub fn contains(&self, value: &uint) -> bool {
 335         self.map.contains_key(value)
 336     }
 337
 338     /// Returns `true` if the set has no elements in common with `other`.
 339     /// This is equivalent to checking for an empty intersection.
 340     ///
 341     /// # Example
 342     ///
 343     /// ```
 344     /// use std::collections::TrieSet;
 345     ///
 346     /// let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 347     /// let mut b: TrieSet = TrieSet::new();
 348     ///
 349     /// assert_eq!(a.is_disjoint(&b), true);
 350     /// b.insert(4);
 351     /// assert_eq!(a.is_disjoint(&b), true);
 352     /// b.insert(1);
 353     /// assert_eq!(a.is_disjoint(&b), false);
 354     /// ```
 355     #[inline]
 356     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 357     pub fn is_disjoint(&self, other: &TrieSet) -> bool {
 358         self.iter().all(|v| !other.contains(&v))
 359     }
 360
 361     /// Returns `true` if the set is a subset of another.
 362     ///
 363     /// # Example
 364     ///
 365     /// ```
 366     /// use std::collections::TrieSet;
 367     ///
 368     /// let sup: TrieSet = [1, 2, 3].iter().map(|&x| x).collect();
 369     /// let mut set: TrieSet = TrieSet::new();
 370     ///
 371     /// assert_eq!(set.is_subset(&sup), true);
 372     /// set.insert(2);
 373     /// assert_eq!(set.is_subset(&sup), true);
 374     /// set.insert(4);
 375     /// assert_eq!(set.is_subset(&sup), false);
 376     /// ```
 377     #[inline]
 378     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 379     pub fn is_subset(&self, other: &TrieSet) -> bool {
 380         self.iter().all(|v| other.contains(&v))
 381     }
 382
 383     /// Returns `true` if the set is a superset of another.
 384     ///
 385     /// # Example
 386     ///
 387     /// ```
 388     /// use std::collections::TrieSet;
 389     ///
 390     /// let sub: TrieSet = [1, 2].iter().map(|&x| x).collect();
 391     /// let mut set: TrieSet = TrieSet::new();
 392     ///
 393     /// assert_eq!(set.is_superset(&sub), false);
 394     ///
 395     /// set.insert(0);
 396     /// set.insert(1);
 397     /// assert_eq!(set.is_superset(&sub), false);
 398     ///
 399     /// set.insert(2);
 400     /// assert_eq!(set.is_superset(&sub), true);
 401     /// ```
 402     #[inline]
 403     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 404     pub fn is_superset(&self, other: &TrieSet) -> bool {
 405         other.is_subset(self)
 406     }
 407
 408     /// Adds a value to the set. Returns `true` if the value was not already
 409     /// present in the set.
 410     ///
 411     /// # Example
 412     ///
 413     /// ```
 414     /// use std::collections::TrieSet;
 415     ///
 416     /// let mut set = TrieSet::new();
 417     ///
 418     /// assert_eq!(set.insert(2), true);
 419     /// assert_eq!(set.insert(2), false);
 420     /// assert_eq!(set.len(), 1);
 421     /// ```
 422     #[inline]
 423     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 424     pub fn insert(&mut self, value: uint) -> bool {
 425         self.map.insert(value, ()).is_none()
 426     }
 427
 428     /// Removes a value from the set. Returns `true` if the value was
 429     /// present in the set.
 430     ///
 431     /// # Example
 432     ///
 433     /// ```
 434     /// use std::collections::TrieSet;
 435     ///
 436     /// let mut set = TrieSet::new();
 437     ///
 438     /// set.insert(2);
 439     /// assert_eq!(set.remove(&2), true);
 440     /// assert_eq!(set.remove(&2), false);
 441     /// ```
 442     #[inline]
 443     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 444     pub fn remove(&mut self, value: &uint) -> bool {
 445         self.map.remove(value).is_some()
 446     }
 447 }
 448
 449 impl FromIterator<uint> for TrieSet {
 450     fn from_iter<Iter: Iterator<uint>>(iter: Iter) -> TrieSet {
 451         let mut set = TrieSet::new();
 452         set.extend(iter);
 453         set
 454     }
 455 }
 456
 457 impl Extend<uint> for TrieSet {
 458     fn extend<Iter: Iterator<uint>>(&mut self, mut iter: Iter) {
 459         for elem in iter {
 460             self.insert(elem);
 461         }
 462     }
 463 }
 464
 465 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 466 impl BitOr<TrieSet, TrieSet> for TrieSet {
 467     /// Returns the union of `self` and `rhs` as a new `TrieSet`.
 468     ///
 469     /// # Example
 470     ///
 471     /// ```
 472     /// use std::collections::TrieSet;
 473     ///
 474     /// let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 475     /// let b: TrieSet = vec![3, 4, 5].into_iter().collect();
 476     ///
 477     /// let set: TrieSet = a | b;
 478     /// let v: Vec<uint> = set.iter().collect();
 479     /// assert_eq!(v, vec![1u, 2, 3, 4, 5]);
 480     /// ```
 481     fn bitor(&self, rhs: &TrieSet) -> TrieSet {
 482         self.union(rhs).collect()
 483     }
 484 }
 485
 486 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 487 impl BitAnd<TrieSet, TrieSet> for TrieSet {
 488     /// Returns the intersection of `self` and `rhs` as a new `TrieSet`.
 489     ///
 490     /// # Example
 491     ///
 492     /// ```
 493     /// use std::collections::TrieSet;
 494     ///
 495     /// let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 496     /// let b: TrieSet = vec![2, 3, 4].into_iter().collect();
 497     ///
 498     /// let set: TrieSet = a & b;
 499     /// let v: Vec<uint> = set.iter().collect();
 500     /// assert_eq!(v, vec![2u, 3]);
 501     /// ```
 502     fn bitand(&self, rhs: &TrieSet) -> TrieSet {
 503         self.intersection(rhs).collect()
 504     }
 505 }
 506
 507 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 508 impl BitXor<TrieSet, TrieSet> for TrieSet {
 509     /// Returns the symmetric difference of `self` and `rhs` as a new `TrieSet`.
 510     ///
 511     /// # Example
 512     ///
 513     /// ```
 514     /// use std::collections::TrieSet;
 515     ///
 516     /// let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 517     /// let b: TrieSet = vec![3, 4, 5].into_iter().collect();
 518     ///
 519     /// let set: TrieSet = a ^ b;
 520     /// let v: Vec<uint> = set.iter().collect();
 521     /// assert_eq!(v, vec![1u, 2, 4, 5]);
 522     /// ```
 523     fn bitxor(&self, rhs: &TrieSet) -> TrieSet {
 524         self.symmetric_difference(rhs).collect()
 525     }
 526 }
 527
 528 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 529 impl Sub<TrieSet, TrieSet> for TrieSet {
 530     /// Returns the difference of `self` and `rhs` as a new `TrieSet`.
 531     ///
 532     /// # Example
 533     ///
 534     /// ```
 535     /// use std::collections::TrieSet;
 536     ///
 537     /// let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 538     /// let b: TrieSet = vec![3, 4, 5].into_iter().collect();
 539     ///
 540     /// let set: TrieSet = a - b;
 541     /// let v: Vec<uint> = set.iter().collect();
 542     /// assert_eq!(v, vec![1u, 2]);
 543     /// ```
 544     fn sub(&self, rhs: &TrieSet) -> TrieSet {
 545         self.difference(rhs).collect()
 546     }
 547 }
 548
 549 /// A forward iterator over a set.
 550 pub struct SetItems<'a> {
 551     iter: Entries<'a, ()>
 552 }
 553
 554 /// An iterator producing elements in the set difference (in-order).
 555 pub struct DifferenceItems<'a> {
 556     a: Peekable<uint, SetItems<'a>>,
 557     b: Peekable<uint, SetItems<'a>>,
 558 }
 559
 560 /// An iterator producing elements in the set symmetric difference (in-order).
 561 pub struct SymDifferenceItems<'a> {
 562     a: Peekable<uint, SetItems<'a>>,
 563     b: Peekable<uint, SetItems<'a>>,
 564 }
 565
 566 /// An iterator producing elements in the set intersection (in-order).
 567 pub struct IntersectionItems<'a> {
 568     a: Peekable<uint, SetItems<'a>>,
 569     b: Peekable<uint, SetItems<'a>>,
 570 }
 571
 572 /// An iterator producing elements in the set union (in-order).
 573 pub struct UnionItems<'a> {
 574     a: Peekable<uint, SetItems<'a>>,
 575     b: Peekable<uint, SetItems<'a>>,
 576 }
 577
 578 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
 579 fn cmp_opt(x: Option<&uint>, y: Option<&uint>, short: Ordering, long: Ordering) -> Ordering {
 580     match (x, y) {
 581         (None    , _       ) => short,
 582         (_       , None    ) => long,
 583         (Some(x1), Some(y1)) => x1.cmp(y1),
 584     }
 585 }
 586
 587 impl<'a> Iterator<uint> for SetItems<'a> {
 588     fn next(&mut self) -> Option<uint> {
 589         self.iter.next().map(|(key, _)| key)
 590     }
 591
 592     fn size_hint(&self) -> (uint, Option<uint>) {
 593         self.iter.size_hint()
 594     }
 595 }
 596
 597 impl<'a> Iterator<uint> for DifferenceItems<'a> {
 598     fn next(&mut self) -> Option<uint> {
 599         loop {
 600             match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
 601                 Less    => return self.a.next(),
 602                 Equal   => { self.a.next(); self.b.next(); }
 603                 Greater => { self.b.next(); }
 604             }
 605         }
 606     }
 607 }
 608
 609 impl<'a> Iterator<uint> for SymDifferenceItems<'a> {
 610     fn next(&mut self) -> Option<uint> {
 611         loop {
 612             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 613                 Less => return self.a.next(),
 614                 Equal => { self.a.next(); self.b.next(); }
 615                 Greater => return self.b.next(),
 616             }
 617         }
 618     }
 619 }
 620
 621 impl<'a> Iterator<uint> for IntersectionItems<'a> {
 622     fn next(&mut self) -> Option<uint> {
 623         loop {
 624             let o_cmp = match (self.a.peek(), self.b.peek()) {
 625                 (None    , _       ) => None,
 626                 (_       , None    ) => None,
 627                 (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
 628             };
 629             match o_cmp {
 630                 None          => return None,
 631                 Some(Less)    => { self.a.next(); }
 632                 Some(Equal)   => { self.b.next(); return self.a.next() }
 633                 Some(Greater) => { self.b.next(); }
 634             }
 635         }
 636     }
 637 }
 638
 639 impl<'a> Iterator<uint> for UnionItems<'a> {
 640     fn next(&mut self) -> Option<uint> {
 641         loop {
 642             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 643                 Less    => return self.a.next(),
 644                 Equal   => { self.b.next(); return self.a.next() }
 645                 Greater => return self.b.next(),
 646             }
 647         }
 648     }
 649 }
 650
 651 #[cfg(test)]
 652 mod test {
 653     use std::prelude::*;
 654     use std::uint;
 655     use vec::Vec;
 656
 657     use super::TrieSet;
 658
 659     #[test]
 660     fn test_sane_chunk() {
 661         let x = 1;
 662         let y = 1 << (uint::BITS - 1);
 663
 664         let mut trie = TrieSet::new();
 665
 666         assert!(trie.insert(x));
 667         assert!(trie.insert(y));
 668
 669         assert_eq!(trie.len(), 2);
 670
 671         let expected = [x, y];
 672
 673         for (i, x) in trie.iter().enumerate() {
 674             assert_eq!(expected[i], x);
 675         }
 676     }
 677
 678     #[test]
 679     fn test_from_iter() {
 680         let xs = vec![9u, 8, 7, 6, 5, 4, 3, 2, 1];
 681
 682         let set: TrieSet = xs.iter().map(|&x| x).collect();
 683
 684         for x in xs.iter() {
 685             assert!(set.contains(x));
 686         }
 687     }
 688
 689     #[test]
 690     fn test_show() {
 691         let mut set = TrieSet::new();
 692         let empty = TrieSet::new();
 693
 694         set.insert(1);
 695         set.insert(2);
 696
 697         let set_str = format!("{}", set);
 698
 699         assert!(set_str == "{1, 2}".to_string());
 700         assert_eq!(format!("{}", empty), "{}".to_string());
 701     }
 702
 703     #[test]
 704     fn test_clone() {
 705         let mut a = TrieSet::new();
 706
 707         a.insert(1);
 708         a.insert(2);
 709         a.insert(3);
 710
 711         assert!(a.clone() == a);
 712     }
 713
 714     #[test]
 715     fn test_lt() {
 716         let mut a = TrieSet::new();
 717         let mut b = TrieSet::new();
 718
 719         assert!(!(a < b) && !(b < a));
 720         assert!(b.insert(2u));
 721         assert!(a < b);
 722         assert!(a.insert(3u));
 723         assert!(!(a < b) && b < a);
 724         assert!(b.insert(1));
 725         assert!(b < a);
 726         assert!(a.insert(0));
 727         assert!(a < b);
 728         assert!(a.insert(6));
 729         assert!(a < b && !(b < a));
 730     }
 731
 732     #[test]
 733     fn test_ord() {
 734         let mut a = TrieSet::new();
 735         let mut b = TrieSet::new();
 736
 737         assert!(a <= b && a >= b);
 738         assert!(a.insert(1u));
 739         assert!(a > b && a >= b);
 740         assert!(b < a && b <= a);
 741         assert!(b.insert(2u));
 742         assert!(b > a && b >= a);
 743         assert!(a < b && a <= b);
 744     }
 745
 746     fn check(a: &[uint],
 747              b: &[uint],
 748              expected: &[uint],
 749              f: |&TrieSet, &TrieSet, f: |uint| -> bool| -> bool) {
 750         let mut set_a = TrieSet::new();
 751         let mut set_b = TrieSet::new();
 752
 753         for x in a.iter() { assert!(set_a.insert(*x)) }
 754         for y in b.iter() { assert!(set_b.insert(*y)) }
 755
 756         let mut i = 0;
 757         f(&set_a, &set_b, |x| {
 758             assert_eq!(x, expected[i]);
 759             i += 1;
 760             true
 761         });
 762         assert_eq!(i, expected.len());
 763     }
 764
 765     #[test]
 766     fn test_intersection() {
 767         fn check_intersection(a: &[uint], b: &[uint], expected: &[uint]) {
 768             check(a, b, expected, |x, y, f| x.intersection(y).all(f))
 769         }
 770
 771         check_intersection(&[], &[], &[]);
 772         check_intersection(&[1, 2, 3], &[], &[]);
 773         check_intersection(&[], &[1, 2, 3], &[]);
 774         check_intersection(&[2], &[1, 2, 3], &[2]);
 775         check_intersection(&[1, 2, 3], &[2], &[2]);
 776         check_intersection(&[11, 1, 3, 77, 103, 5],
 777                            &[2, 11, 77, 5, 3],
 778                            &[3, 5, 11, 77]);
 779     }
 780
 781     #[test]
 782     fn test_difference() {
 783         fn check_difference(a: &[uint], b: &[uint], expected: &[uint]) {
 784             check(a, b, expected, |x, y, f| x.difference(y).all(f))
 785         }
 786
 787         check_difference(&[], &[], &[]);
 788         check_difference(&[1, 12], &[], &[1, 12]);
 789         check_difference(&[], &[1, 2, 3, 9], &[]);
 790         check_difference(&[1, 3, 5, 9, 11],
 791                          &[3, 9],
 792                          &[1, 5, 11]);
 793         check_difference(&[11, 22, 33, 40, 42],
 794                          &[14, 23, 34, 38, 39, 50],
 795                          &[11, 22, 33, 40, 42]);
 796     }
 797
 798     #[test]
 799     fn test_symmetric_difference() {
 800         fn check_symmetric_difference(a: &[uint], b: &[uint], expected: &[uint]) {
 801             check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
 802         }
 803
 804         check_symmetric_difference(&[], &[], &[]);
 805         check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
 806         check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
 807         check_symmetric_difference(&[1, 3, 5, 9, 11],
 808                                    &[3, 9, 14, 22],
 809                                    &[1, 5, 11, 14, 22]);
 810     }
 811
 812     #[test]
 813     fn test_union() {
 814         fn check_union(a: &[uint], b: &[uint], expected: &[uint]) {
 815             check(a, b, expected, |x, y, f| x.union(y).all(f))
 816         }
 817
 818         check_union(&[], &[], &[]);
 819         check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
 820         check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
 821         check_union(&[1, 3, 5, 9, 11, 16, 19, 24],
 822                     &[1, 5, 9, 13, 19],
 823                     &[1, 3, 5, 9, 11, 13, 16, 19, 24]);
 824     }
 825
 826     #[test]
 827     fn test_bit_or() {
 828         let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 829         let b: TrieSet = vec![3, 4, 5].into_iter().collect();
 830
 831         let set: TrieSet = a | b;
 832         let v: Vec<uint> = set.iter().collect();
 833         assert_eq!(v, vec![1u, 2, 3, 4, 5]);
 834     }
 835
 836     #[test]
 837     fn test_bit_and() {
 838         let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 839         let b: TrieSet = vec![2, 3, 4].into_iter().collect();
 840
 841         let set: TrieSet = a & b;
 842         let v: Vec<uint> = set.iter().collect();
 843         assert_eq!(v, vec![2u, 3]);
 844     }
 845
 846     #[test]
 847     fn test_bit_xor() {
 848         let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 849         let b: TrieSet = vec![3, 4, 5].into_iter().collect();
 850
 851         let set: TrieSet = a ^ b;
 852         let v: Vec<uint> = set.iter().collect();
 853         assert_eq!(v, vec![1u, 2, 4, 5]);
 854     }
 855
 856     #[test]
 857     fn test_sub() {
 858         let a: TrieSet = vec![1, 2, 3].into_iter().collect();
 859         let b: TrieSet = vec![3, 4, 5].into_iter().collect();
 860
 861         let set: TrieSet = a - b;
 862         let v: Vec<uint> = set.iter().collect();
 863         assert_eq!(v, vec![1u, 2]);
 864     }
 865 }