src/libstd/collections/hash/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 // ignore-lexer-test FIXME #15883
  12
  13 use borrow::BorrowFrom;
  14 use cmp::{Eq, Equiv, PartialEq};
  15 use core::kinds::Sized;
  16 use default::Default;
  17 use fmt::Show;
  18 use fmt;
  19 use hash::{Hash, Hasher, RandomSipHasher};
  20 use iter::{Iterator, IteratorExt, FromIterator, Map, Chain, Extend};
  21 use option::Option::{Some, None, mod};
  22 use result::Result::{Ok, Err};
  23
  24 use super::map::{HashMap, MoveEntries, Keys, INITIAL_CAPACITY};
  25
  26 // FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
  27
  28
  29 // Future Optimization (FIXME!)
  30 // =============================
  31 //
  32 // Iteration over zero sized values is a noop. There is no need
  33 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
  34 // to get rid of it properly.
  35
  36 /// An implementation of a hash set using the underlying representation of a
  37 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
  38 /// requires that the elements implement the `Eq` and `Hash` traits.
  39 ///
  40 /// # Example
  41 ///
  42 /// ```
  43 /// use std::collections::HashSet;
  44 /// // Type inference lets us omit an explicit type signature (which
  45 /// // would be `HashSet<&str>` in this example).
  46 /// let mut books = HashSet::new();
  47 ///
  48 /// // Add some books.
  49 /// books.insert("A Dance With Dragons");
  50 /// books.insert("To Kill a Mockingbird");
  51 /// books.insert("The Odyssey");
  52 /// books.insert("The Great Gatsby");
  53 ///
  54 /// // Check for a specific one.
  55 /// if !books.contains(&("The Winds of Winter")) {
  56 ///     println!("We have {} books, but The Winds of Winter ain't one.",
  57 ///              books.len());
  58 /// }
  59 ///
  60 /// // Remove a book.
  61 /// books.remove(&"The Odyssey");
  62 ///
  63 /// // Iterate over everything.
  64 /// for book in books.iter() {
  65 ///     println!("{}", *book);
  66 /// }
  67 /// ```
  68 ///
  69 /// The easiest way to use `HashSet` with a custom type is to derive
  70 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
  71 /// future be implied by `Eq`.
  72 ///
  73 /// ```
  74 /// use std::collections::HashSet;
  75 /// #[deriving(Hash, Eq, PartialEq, Show)]
  76 /// struct Viking<'a> {
  77 ///     name: &'a str,
  78 ///     power: uint,
  79 /// }
  80 ///
  81 /// let mut vikings = HashSet::new();
  82 ///
  83 /// vikings.insert(Viking { name: "Einar", power: 9u });
  84 /// vikings.insert(Viking { name: "Einar", power: 9u });
  85 /// vikings.insert(Viking { name: "Olaf", power: 4u });
  86 /// vikings.insert(Viking { name: "Harald", power: 8u });
  87 ///
  88 /// // Use derived implementation to print the vikings.
  89 /// for x in vikings.iter() {
  90 ///     println!("{}", x);
  91 /// }
  92 /// ```
  93 #[deriving(Clone)]
  94 pub struct HashSet<T, H = RandomSipHasher> {
  95     map: HashMap<T, (), H>
  96 }
  97
  98 impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
  99     /// Create an empty HashSet.
 100     ///
 101     /// # Example
 102     ///
 103     /// ```
 104     /// use std::collections::HashSet;
 105     /// let mut set: HashSet<int> = HashSet::new();
 106     /// ```
 107     #[inline]
 108     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 109     pub fn new() -> HashSet<T, RandomSipHasher> {
 110         HashSet::with_capacity(INITIAL_CAPACITY)
 111     }
 112
 113     /// Create an empty HashSet with space for at least `n` elements in
 114     /// the hash table.
 115     ///
 116     /// # Example
 117     ///
 118     /// ```
 119     /// use std::collections::HashSet;
 120     /// let mut set: HashSet<int> = HashSet::with_capacity(10);
 121     /// ```
 122     #[inline]
 123     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 124     pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
 125         HashSet { map: HashMap::with_capacity(capacity) }
 126     }
 127 }
 128
 129 impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
 130     /// Creates a new empty hash set which will use the given hasher to hash
 131     /// keys.
 132     ///
 133     /// The hash set is also created with the default initial capacity.
 134     ///
 135     /// # Example
 136     ///
 137     /// ```
 138     /// use std::collections::HashSet;
 139     /// use std::hash::sip::SipHasher;
 140     ///
 141     /// let h = SipHasher::new();
 142     /// let mut set = HashSet::with_hasher(h);
 143     /// set.insert(2u);
 144     /// ```
 145     #[inline]
 146     pub fn with_hasher(hasher: H) -> HashSet<T, H> {
 147         HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
 148     }
 149
 150     /// Create an empty HashSet with space for at least `capacity`
 151     /// elements in the hash table, using `hasher` to hash the keys.
 152     ///
 153     /// Warning: `hasher` is normally randomly generated, and
 154     /// is designed to allow `HashSet`s to be resistant to attacks that
 155     /// cause many collisions and very poor performance. Setting it
 156     /// manually using this function can expose a DoS attack vector.
 157     ///
 158     /// # Example
 159     ///
 160     /// ```
 161     /// use std::collections::HashSet;
 162     /// use std::hash::sip::SipHasher;
 163     ///
 164     /// let h = SipHasher::new();
 165     /// let mut set = HashSet::with_capacity_and_hasher(10u, h);
 166     /// set.insert(1i);
 167     /// ```
 168     #[inline]
 169     pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
 170         HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
 171     }
 172
 173     /// Returns the number of elements the set can hold without reallocating.
 174     ///
 175     /// # Example
 176     ///
 177     /// ```
 178     /// use std::collections::HashSet;
 179     /// let set: HashSet<int> = HashSet::with_capacity(100);
 180     /// assert!(set.capacity() >= 100);
 181     /// ```
 182     #[inline]
 183     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 184     pub fn capacity(&self) -> uint {
 185         self.map.capacity()
 186     }
 187
 188     /// Reserves capacity for at least `additional` more elements to be inserted
 189     /// in the `HashSet`. The collection may reserve more space to avoid
 190     /// frequent reallocations.
 191     ///
 192     /// # Panics
 193     ///
 194     /// Panics if the new allocation size overflows `uint`.
 195     ///
 196     /// # Example
 197     ///
 198     /// ```
 199     /// use std::collections::HashSet;
 200     /// let mut set: HashSet<int> = HashSet::new();
 201     /// set.reserve(10);
 202     /// ```
 203     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 204     pub fn reserve(&mut self, additional: uint) {
 205         self.map.reserve(additional)
 206     }
 207
 208     /// Shrinks the capacity of the set as much as possible. It will drop
 209     /// down as much as possible while maintaining the internal rules
 210     /// and possibly leaving some space in accordance with the resize policy.
 211     ///
 212     /// # Example
 213     ///
 214     /// ```
 215     /// use std::collections::HashSet;
 216     ///
 217     /// let mut set: HashSet<int> = HashSet::with_capacity(100);
 218     /// set.insert(1);
 219     /// set.insert(2);
 220     /// assert!(set.capacity() >= 100);
 221     /// set.shrink_to_fit();
 222     /// assert!(set.capacity() >= 2);
 223     /// ```
 224     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 225     pub fn shrink_to_fit(&mut self) {
 226         self.map.shrink_to_fit()
 227     }
 228
 229     /// Deprecated: use `contains` and `BorrowFrom`.
 230     #[deprecated = "use contains and BorrowFrom"]
 231     #[allow(deprecated)]
 232     pub fn contains_equiv<Sized? Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
 233       self.map.contains_key_equiv(value)
 234     }
 235
 236     /// An iterator visiting all elements in arbitrary order.
 237     /// Iterator element type is &'a T.
 238     ///
 239     /// # Example
 240     ///
 241     /// ```
 242     /// use std::collections::HashSet;
 243     /// let mut set = HashSet::new();
 244     /// set.insert("a");
 245     /// set.insert("b");
 246     ///
 247     /// // Will print in an arbitrary order.
 248     /// for x in set.iter() {
 249     ///     println!("{}", x);
 250     /// }
 251     /// ```
 252     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 253     pub fn iter<'a>(&'a self) -> Iter<'a, T> {
 254         Iter { iter: self.map.keys() }
 255     }
 256
 257     /// Creates a consuming iterator, that is, one that moves each value out
 258     /// of the set in arbitrary order. The set cannot be used after calling
 259     /// this.
 260     ///
 261     /// # Example
 262     ///
 263     /// ```
 264     /// use std::collections::HashSet;
 265     /// let mut set = HashSet::new();
 266     /// set.insert("a".to_string());
 267     /// set.insert("b".to_string());
 268     ///
 269     /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
 270     /// let v: Vec<String> = set.into_iter().collect();
 271     ///
 272     /// // Will print in an arbitrary order.
 273     /// for x in v.iter() {
 274     ///     println!("{}", x);
 275     /// }
 276     /// ```
 277     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 278     pub fn into_iter(self) -> IntoIter<T> {
 279         fn first<A, B>((a, _): (A, B)) -> A { a }
 280
 281         IntoIter { iter: self.map.into_iter().map(first) }
 282     }
 283
 284     /// Visit the values representing the difference.
 285     ///
 286     /// # Example
 287     ///
 288     /// ```
 289     /// use std::collections::HashSet;
 290     /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 291     /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
 292     ///
 293     /// // Can be seen as `a - b`.
 294     /// for x in a.difference(&b) {
 295     ///     println!("{}", x); // Print 1
 296     /// }
 297     ///
 298     /// let diff: HashSet<int> = a.difference(&b).map(|&x| x).collect();
 299     /// assert_eq!(diff, [1i].iter().map(|&x| x).collect());
 300     ///
 301     /// // Note that difference is not symmetric,
 302     /// // and `b - a` means something else:
 303     /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect();
 304     /// assert_eq!(diff, [4i].iter().map(|&x| x).collect());
 305     /// ```
 306     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 307     pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> Difference<'a, T, H> {
 308         Difference {
 309             iter: self.iter(),
 310             other: other,
 311         }
 312     }
 313
 314     /// Visit the values representing the symmetric difference.
 315     ///
 316     /// # Example
 317     ///
 318     /// ```
 319     /// use std::collections::HashSet;
 320     /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 321     /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
 322     ///
 323     /// // Print 1, 4 in arbitrary order.
 324     /// for x in a.symmetric_difference(&b) {
 325     ///     println!("{}", x);
 326     /// }
 327     ///
 328     /// let diff1: HashSet<int> = a.symmetric_difference(&b).map(|&x| x).collect();
 329     /// let diff2: HashSet<int> = b.symmetric_difference(&a).map(|&x| x).collect();
 330     ///
 331     /// assert_eq!(diff1, diff2);
 332     /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect());
 333     /// ```
 334     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 335     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
 336         -> SymmetricDifference<'a, T, H> {
 337         SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
 338     }
 339
 340     /// Visit the values representing the intersection.
 341     ///
 342     /// # Example
 343     ///
 344     /// ```
 345     /// use std::collections::HashSet;
 346     /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 347     /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
 348     ///
 349     /// // Print 2, 3 in arbitrary order.
 350     /// for x in a.intersection(&b) {
 351     ///     println!("{}", x);
 352     /// }
 353     ///
 354     /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect();
 355     /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect());
 356     /// ```
 357     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 358     pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>) -> Intersection<'a, T, H> {
 359         Intersection {
 360             iter: self.iter(),
 361             other: other,
 362         }
 363     }
 364
 365     /// Visit the values representing the union.
 366     ///
 367     /// # Example
 368     ///
 369     /// ```
 370     /// use std::collections::HashSet;
 371     /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 372     /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
 373     ///
 374     /// // Print 1, 2, 3, 4 in arbitrary order.
 375     /// for x in a.union(&b) {
 376     ///     println!("{}", x);
 377     /// }
 378     ///
 379     /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect();
 380     /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
 381     /// ```
 382     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 383     pub fn union<'a>(&'a self, other: &'a HashSet<T, H>) -> Union<'a, T, H> {
 384         Union { iter: self.iter().chain(other.difference(self)) }
 385     }
 386
 387     /// Return the number of elements in the set
 388     ///
 389     /// # Example
 390     ///
 391     /// ```
 392     /// use std::collections::HashSet;
 393     ///
 394     /// let mut v = HashSet::new();
 395     /// assert_eq!(v.len(), 0);
 396     /// v.insert(1u);
 397     /// assert_eq!(v.len(), 1);
 398     /// ```
 399     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 400     pub fn len(&self) -> uint { self.map.len() }
 401
 402     /// Returns true if the set contains no elements
 403     ///
 404     /// # Example
 405     ///
 406     /// ```
 407     /// use std::collections::HashSet;
 408     ///
 409     /// let mut v = HashSet::new();
 410     /// assert!(v.is_empty());
 411     /// v.insert(1u);
 412     /// assert!(!v.is_empty());
 413     /// ```
 414     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 415     pub fn is_empty(&self) -> bool { self.map.len() == 0 }
 416
 417     /// Clears the set, removing all values.
 418     ///
 419     /// # Example
 420     ///
 421     /// ```
 422     /// use std::collections::HashSet;
 423     ///
 424     /// let mut v = HashSet::new();
 425     /// v.insert(1u);
 426     /// v.clear();
 427     /// assert!(v.is_empty());
 428     /// ```
 429     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 430     pub fn clear(&mut self) { self.map.clear() }
 431
 432     /// Returns `true` if the set contains a value.
 433     ///
 434     /// The value may be any borrowed form of the set's value type, but
 435     /// `Hash` and `Eq` on the borrowed form *must* match those for
 436     /// the value type.
 437     ///
 438     /// # Example
 439     ///
 440     /// ```
 441     /// use std::collections::HashSet;
 442     ///
 443     /// let set: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
 444     /// assert_eq!(set.contains(&1), true);
 445     /// assert_eq!(set.contains(&4), false);
 446     /// ```
 447     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 448     pub fn contains<Sized? Q>(&self, value: &Q) -> bool
 449         where Q: BorrowFrom<T> + Hash<S> + Eq
 450     {
 451         self.map.contains_key(value)
 452     }
 453
 454     /// Returns `true` if the set has no elements in common with `other`.
 455     /// This is equivalent to checking for an empty intersection.
 456     ///
 457     /// # Example
 458     ///
 459     /// ```
 460     /// use std::collections::HashSet;
 461     ///
 462     /// let a: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
 463     /// let mut b: HashSet<uint> = HashSet::new();
 464     ///
 465     /// assert_eq!(a.is_disjoint(&b), true);
 466     /// b.insert(4);
 467     /// assert_eq!(a.is_disjoint(&b), true);
 468     /// b.insert(1);
 469     /// assert_eq!(a.is_disjoint(&b), false);
 470     /// ```
 471     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 472     pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
 473         self.iter().all(|v| !other.contains(v))
 474     }
 475
 476     /// Returns `true` if the set is a subset of another.
 477     ///
 478     /// # Example
 479     ///
 480     /// ```
 481     /// use std::collections::HashSet;
 482     ///
 483     /// let sup: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
 484     /// let mut set: HashSet<uint> = HashSet::new();
 485     ///
 486     /// assert_eq!(set.is_subset(&sup), true);
 487     /// set.insert(2);
 488     /// assert_eq!(set.is_subset(&sup), true);
 489     /// set.insert(4);
 490     /// assert_eq!(set.is_subset(&sup), false);
 491     /// ```
 492     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 493     pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
 494         self.iter().all(|v| other.contains(v))
 495     }
 496
 497     /// Returns `true` if the set is a superset of another.
 498     ///
 499     /// # Example
 500     ///
 501     /// ```
 502     /// use std::collections::HashSet;
 503     ///
 504     /// let sub: HashSet<uint> = [1, 2].iter().map(|&x| x).collect();
 505     /// let mut set: HashSet<uint> = HashSet::new();
 506     ///
 507     /// assert_eq!(set.is_superset(&sub), false);
 508     ///
 509     /// set.insert(0);
 510     /// set.insert(1);
 511     /// assert_eq!(set.is_superset(&sub), false);
 512     ///
 513     /// set.insert(2);
 514     /// assert_eq!(set.is_superset(&sub), true);
 515     /// ```
 516     #[inline]
 517     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 518     pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
 519         other.is_subset(self)
 520     }
 521
 522     /// Adds a value to the set. Returns `true` if the value was not already
 523     /// present in the set.
 524     ///
 525     /// # Example
 526     ///
 527     /// ```
 528     /// use std::collections::HashSet;
 529     ///
 530     /// let mut set = HashSet::new();
 531     ///
 532     /// assert_eq!(set.insert(2u), true);
 533     /// assert_eq!(set.insert(2), false);
 534     /// assert_eq!(set.len(), 1);
 535     /// ```
 536     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 537     pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 538
 539     /// Removes a value from the set. Returns `true` if the value was
 540     /// present in the set.
 541     ///
 542     /// The value may be any borrowed form of the set's value type, but
 543     /// `Hash` and `Eq` on the borrowed form *must* match those for
 544     /// the value type.
 545     ///
 546     /// # Example
 547     ///
 548     /// ```
 549     /// use std::collections::HashSet;
 550     ///
 551     /// let mut set = HashSet::new();
 552     ///
 553     /// set.insert(2u);
 554     /// assert_eq!(set.remove(&2), true);
 555     /// assert_eq!(set.remove(&2), false);
 556     /// ```
 557     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 558     pub fn remove<Sized? Q>(&mut self, value: &Q) -> bool
 559         where Q: BorrowFrom<T> + Hash<S> + Eq
 560     {
 561         self.map.remove(value).is_some()
 562     }
 563 }
 564
 565 impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
 566     fn eq(&self, other: &HashSet<T, H>) -> bool {
 567         if self.len() != other.len() { return false; }
 568
 569         self.iter().all(|key| other.contains(key))
 570     }
 571 }
 572
 573 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
 574
 575 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
 576     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 577         try!(write!(f, "{{"));
 578
 579         for (i, x) in self.iter().enumerate() {
 580             if i != 0 { try!(write!(f, ", ")); }
 581             try!(write!(f, "{}", *x));
 582         }
 583
 584         write!(f, "}}")
 585     }
 586 }
 587
 588 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
 589     fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
 590         let lower = iter.size_hint().0;
 591         let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
 592         set.extend(iter);
 593         set
 594     }
 595 }
 596
 597 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extend<T> for HashSet<T, H> {
 598     fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
 599         for k in iter {
 600             self.insert(k);
 601         }
 602     }
 603 }
 604
 605 #[stable]
 606 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
 607     #[stable]
 608     fn default() -> HashSet<T, H> {
 609         HashSet::with_hasher(Default::default())
 610     }
 611 }
 612
 613 /// HashSet iterator
 614 pub struct Iter<'a, K: 'a> {
 615     iter: Keys<'a, K, ()>
 616 }
 617
 618 /// HashSet move iterator
 619 pub struct IntoIter<K> {
 620     iter: Map<(K, ()), K, MoveEntries<K, ()>, fn((K, ())) -> K>
 621 }
 622
 623 /// Intersection iterator
 624 pub struct Intersection<'a, T: 'a, H: 'a> {
 625     // iterator of the first set
 626     iter: Iter<'a, T>,
 627     // the second set
 628     other: &'a HashSet<T, H>,
 629 }
 630
 631 /// Difference iterator
 632 pub struct Difference<'a, T: 'a, H: 'a> {
 633     // iterator of the first set
 634     iter: Iter<'a, T>,
 635     // the second set
 636     other: &'a HashSet<T, H>,
 637 }
 638
 639 /// Symmetric difference iterator.
 640 pub struct SymmetricDifference<'a, T: 'a, H: 'a> {
 641     iter: Chain<Difference<'a, T, H>, Difference<'a, T, H>>
 642 }
 643
 644 /// Set union iterator.
 645 pub struct Union<'a, T: 'a, H: 'a> {
 646     iter: Chain<Iter<'a, T>, Difference<'a, T, H>>
 647 }
 648
 649 impl<'a, K> Iterator<&'a K> for Iter<'a, K> {
 650     fn next(&mut self) -> Option<&'a K> { self.iter.next() }
 651     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 652 }
 653
 654 impl<K> Iterator<K> for IntoIter<K> {
 655     fn next(&mut self) -> Option<K> { self.iter.next() }
 656     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 657 }
 658
 659 impl<'a, T, S, H> Iterator<&'a T> for Intersection<'a, T, H>
 660     where T: Eq + Hash<S>, H: Hasher<S>
 661 {
 662     fn next(&mut self) -> Option<&'a T> {
 663         loop {
 664             match self.iter.next() {
 665                 None => return None,
 666                 Some(elt) => if self.other.contains(elt) {
 667                     return Some(elt)
 668                 },
 669             }
 670         }
 671     }
 672
 673     fn size_hint(&self) -> (uint, Option<uint>) {
 674         let (_, upper) = self.iter.size_hint();
 675         (0, upper)
 676     }
 677 }
 678
 679 impl<'a, T, S, H> Iterator<&'a T> for Difference<'a, T, H>
 680     where T: Eq + Hash<S>, H: Hasher<S>
 681 {
 682     fn next(&mut self) -> Option<&'a T> {
 683         loop {
 684             match self.iter.next() {
 685                 None => return None,
 686                 Some(elt) => if !self.other.contains(elt) {
 687                     return Some(elt)
 688                 },
 689             }
 690         }
 691     }
 692
 693     fn size_hint(&self) -> (uint, Option<uint>) {
 694         let (_, upper) = self.iter.size_hint();
 695         (0, upper)
 696     }
 697 }
 698
 699 impl<'a, T, S, H> Iterator<&'a T> for SymmetricDifference<'a, T, H>
 700     where T: Eq + Hash<S>, H: Hasher<S>
 701 {
 702     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 703     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 704 }
 705
 706 impl<'a, T, S, H> Iterator<&'a T> for Union<'a, T, H>
 707     where T: Eq + Hash<S>, H: Hasher<S>
 708 {
 709     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 710     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 711 }
 712
 713 #[cfg(test)]
 714 mod test_set {
 715     use prelude::*;
 716
 717     use super::HashSet;
 718     use slice::PartialEqSliceExt;
 719
 720     #[test]
 721     fn test_disjoint() {
 722         let mut xs = HashSet::new();
 723         let mut ys = HashSet::new();
 724         assert!(xs.is_disjoint(&ys));
 725         assert!(ys.is_disjoint(&xs));
 726         assert!(xs.insert(5i));
 727         assert!(ys.insert(11i));
 728         assert!(xs.is_disjoint(&ys));
 729         assert!(ys.is_disjoint(&xs));
 730         assert!(xs.insert(7));
 731         assert!(xs.insert(19));
 732         assert!(xs.insert(4));
 733         assert!(ys.insert(2));
 734         assert!(ys.insert(-11));
 735         assert!(xs.is_disjoint(&ys));
 736         assert!(ys.is_disjoint(&xs));
 737         assert!(ys.insert(7));
 738         assert!(!xs.is_disjoint(&ys));
 739         assert!(!ys.is_disjoint(&xs));
 740     }
 741
 742     #[test]
 743     fn test_subset_and_superset() {
 744         let mut a = HashSet::new();
 745         assert!(a.insert(0i));
 746         assert!(a.insert(5));
 747         assert!(a.insert(11));
 748         assert!(a.insert(7));
 749
 750         let mut b = HashSet::new();
 751         assert!(b.insert(0i));
 752         assert!(b.insert(7));
 753         assert!(b.insert(19));
 754         assert!(b.insert(250));
 755         assert!(b.insert(11));
 756         assert!(b.insert(200));
 757
 758         assert!(!a.is_subset(&b));
 759         assert!(!a.is_superset(&b));
 760         assert!(!b.is_subset(&a));
 761         assert!(!b.is_superset(&a));
 762
 763         assert!(b.insert(5));
 764
 765         assert!(a.is_subset(&b));
 766         assert!(!a.is_superset(&b));
 767         assert!(!b.is_subset(&a));
 768         assert!(b.is_superset(&a));
 769     }
 770
 771     #[test]
 772     fn test_iterate() {
 773         let mut a = HashSet::new();
 774         for i in range(0u, 32) {
 775             assert!(a.insert(i));
 776         }
 777         let mut observed: u32 = 0;
 778         for k in a.iter() {
 779             observed |= 1 << *k;
 780         }
 781         assert_eq!(observed, 0xFFFF_FFFF);
 782     }
 783
 784     #[test]
 785     fn test_intersection() {
 786         let mut a = HashSet::new();
 787         let mut b = HashSet::new();
 788
 789         assert!(a.insert(11i));
 790         assert!(a.insert(1));
 791         assert!(a.insert(3));
 792         assert!(a.insert(77));
 793         assert!(a.insert(103));
 794         assert!(a.insert(5));
 795         assert!(a.insert(-5));
 796
 797         assert!(b.insert(2i));
 798         assert!(b.insert(11));
 799         assert!(b.insert(77));
 800         assert!(b.insert(-9));
 801         assert!(b.insert(-42));
 802         assert!(b.insert(5));
 803         assert!(b.insert(3));
 804
 805         let mut i = 0;
 806         let expected = [3, 5, 11, 77];
 807         for x in a.intersection(&b) {
 808             assert!(expected.contains(x));
 809             i += 1
 810         }
 811         assert_eq!(i, expected.len());
 812     }
 813
 814     #[test]
 815     fn test_difference() {
 816         let mut a = HashSet::new();
 817         let mut b = HashSet::new();
 818
 819         assert!(a.insert(1i));
 820         assert!(a.insert(3));
 821         assert!(a.insert(5));
 822         assert!(a.insert(9));
 823         assert!(a.insert(11));
 824
 825         assert!(b.insert(3i));
 826         assert!(b.insert(9));
 827
 828         let mut i = 0;
 829         let expected = [1, 5, 11];
 830         for x in a.difference(&b) {
 831             assert!(expected.contains(x));
 832             i += 1
 833         }
 834         assert_eq!(i, expected.len());
 835     }
 836
 837     #[test]
 838     fn test_symmetric_difference() {
 839         let mut a = HashSet::new();
 840         let mut b = HashSet::new();
 841
 842         assert!(a.insert(1i));
 843         assert!(a.insert(3));
 844         assert!(a.insert(5));
 845         assert!(a.insert(9));
 846         assert!(a.insert(11));
 847
 848         assert!(b.insert(-2i));
 849         assert!(b.insert(3));
 850         assert!(b.insert(9));
 851         assert!(b.insert(14));
 852         assert!(b.insert(22));
 853
 854         let mut i = 0;
 855         let expected = [-2, 1, 5, 11, 14, 22];
 856         for x in a.symmetric_difference(&b) {
 857             assert!(expected.contains(x));
 858             i += 1
 859         }
 860         assert_eq!(i, expected.len());
 861     }
 862
 863     #[test]
 864     fn test_union() {
 865         let mut a = HashSet::new();
 866         let mut b = HashSet::new();
 867
 868         assert!(a.insert(1i));
 869         assert!(a.insert(3));
 870         assert!(a.insert(5));
 871         assert!(a.insert(9));
 872         assert!(a.insert(11));
 873         assert!(a.insert(16));
 874         assert!(a.insert(19));
 875         assert!(a.insert(24));
 876
 877         assert!(b.insert(-2i));
 878         assert!(b.insert(1));
 879         assert!(b.insert(5));
 880         assert!(b.insert(9));
 881         assert!(b.insert(13));
 882         assert!(b.insert(19));
 883
 884         let mut i = 0;
 885         let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
 886         for x in a.union(&b) {
 887             assert!(expected.contains(x));
 888             i += 1
 889         }
 890         assert_eq!(i, expected.len());
 891     }
 892
 893     #[test]
 894     fn test_from_iter() {
 895         let xs = [1i, 2, 3, 4, 5, 6, 7, 8, 9];
 896
 897         let set: HashSet<int> = xs.iter().map(|&x| x).collect();
 898
 899         for x in xs.iter() {
 900             assert!(set.contains(x));
 901         }
 902     }
 903
 904     #[test]
 905     fn test_move_iter() {
 906         let hs = {
 907             let mut hs = HashSet::new();
 908
 909             hs.insert('a');
 910             hs.insert('b');
 911
 912             hs
 913         };
 914
 915         let v = hs.into_iter().collect::<Vec<char>>();
 916         assert!(['a', 'b'] == v || ['b', 'a'] == v);
 917     }
 918
 919     #[test]
 920     fn test_eq() {
 921         // These constants once happened to expose a bug in insert().
 922         // I'm keeping them around to prevent a regression.
 923         let mut s1 = HashSet::new();
 924
 925         s1.insert(1i);
 926         s1.insert(2);
 927         s1.insert(3);
 928
 929         let mut s2 = HashSet::new();
 930
 931         s2.insert(1i);
 932         s2.insert(2);
 933
 934         assert!(s1 != s2);
 935
 936         s2.insert(3);
 937
 938         assert_eq!(s1, s2);
 939     }
 940
 941     #[test]
 942     fn test_show() {
 943         let mut set: HashSet<int> = HashSet::new();
 944         let empty: HashSet<int> = HashSet::new();
 945
 946         set.insert(1i);
 947         set.insert(2);
 948
 949         let set_str = format!("{}", set);
 950
 951         assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
 952         assert_eq!(format!("{}", empty), "{}");
 953     }
 954 }