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