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