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