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 clone::Clone;
  15 use cmp::{Eq, Equiv, PartialEq};
  16 use core::kinds::Sized;
  17 use default::Default;
  18 use fmt::Show;
  19 use fmt;
  20 use hash::{Hash, Hasher, RandomSipHasher};
  21 use iter::{Iterator, IteratorExt, IteratorCloneExt, FromIterator, Map, Chain, Extend};
  22 use ops::{BitOr, BitAnd, BitXor, Sub};
  23 use option::Option::{Some, None, mod};
  24 use result::Result::{Ok, Err};
  25
  26 use super::map::{mod, HashMap, Keys, INITIAL_CAPACITY};
  27
  28 // Future Optimization (FIXME!)
  29 // =============================
  30 //
  31 // Iteration over zero sized values is a noop. There is no need
  32 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
  33 // to get rid of it properly.
  34
  35 /// An implementation of a hash set using the underlying representation of a
  36 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
  37 /// requires that the elements implement the `Eq` and `Hash` traits.
  38 ///
  39 /// # Example
  40 ///
  41 /// ```
  42 /// use std::collections::HashSet;
  43 /// // Type inference lets us omit an explicit type signature (which
  44 /// // would be `HashSet<&str>` in this example).
  45 /// let mut books = HashSet::new();
  46 ///
  47 /// // Add some books.
  48 /// books.insert("A Dance With Dragons");
  49 /// books.insert("To Kill a Mockingbird");
  50 /// books.insert("The Odyssey");
  51 /// books.insert("The Great Gatsby");
  52 ///
  53 /// // Check for a specific one.
  54 /// if !books.contains(&("The Winds of Winter")) {
  55 ///     println!("We have {} books, but The Winds of Winter ain't one.",
  56 ///              books.len());
  57 /// }
  58 ///
  59 /// // Remove a book.
  60 /// books.remove(&"The Odyssey");
  61 ///
  62 /// // Iterate over everything.
  63 /// for book in books.iter() {
  64 ///     println!("{}", *book);
  65 /// }
  66 /// ```
  67 ///
  68 /// The easiest way to use `HashSet` with a custom type is to derive
  69 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
  70 /// future be implied by `Eq`.
  71 ///
  72 /// ```
  73 /// use std::collections::HashSet;
  74 /// #[deriving(Hash, Eq, PartialEq, Show)]
  75 /// struct Viking<'a> {
  76 ///     name: &'a str,
  77 ///     power: uint,
  78 /// }
  79 ///
  80 /// let mut vikings = HashSet::new();
  81 ///
  82 /// vikings.insert(Viking { name: "Einar", power: 9u });
  83 /// vikings.insert(Viking { name: "Einar", power: 9u });
  84 /// vikings.insert(Viking { name: "Olaf", power: 4u });
  85 /// vikings.insert(Viking { name: "Harald", power: 8u });
  86 ///
  87 /// // Use derived implementation to print the vikings.
  88 /// for x in vikings.iter() {
  89 ///     println!("{}", x);
  90 /// }
  91 /// ```
  92 #[deriving(Clone)]
  93 pub struct HashSet<T, H = RandomSipHasher> {
  94     map: HashMap<T, (), H>
  95 }
  96
  97 impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
  98     /// Create an empty HashSet.
  99     ///
 100     /// # Example
 101     ///
 102     /// ```
 103     /// use std::collections::HashSet;
 104     /// let mut set: HashSet<int> = HashSet::new();
 105     /// ```
 106     #[inline]
 107     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 108     pub fn new() -> HashSet<T, RandomSipHasher> {
 109         HashSet::with_capacity(INITIAL_CAPACITY)
 110     }
 111
 112     /// Create an empty HashSet with space for at least `n` elements in
 113     /// the hash table.
 114     ///
 115     /// # Example
 116     ///
 117     /// ```
 118     /// use std::collections::HashSet;
 119     /// let mut set: HashSet<int> = HashSet::with_capacity(10);
 120     /// ```
 121     #[inline]
 122     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 123     pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
 124         HashSet { map: HashMap::with_capacity(capacity) }
 125     }
 126 }
 127
 128 impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
 129     /// Creates a new empty hash set which will use the given hasher to hash
 130     /// keys.
 131     ///
 132     /// The hash set is also created with the default initial capacity.
 133     ///
 134     /// # Example
 135     ///
 136     /// ```
 137     /// use std::collections::HashSet;
 138     /// use std::hash::sip::SipHasher;
 139     ///
 140     /// let h = SipHasher::new();
 141     /// let mut set = HashSet::with_hasher(h);
 142     /// set.insert(2u);
 143     /// ```
 144     #[inline]
 145     pub fn with_hasher(hasher: H) -> HashSet<T, H> {
 146         HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
 147     }
 148
 149     /// Create an empty HashSet with space for at least `capacity`
 150     /// elements in the hash table, using `hasher` to hash the keys.
 151     ///
 152     /// Warning: `hasher` is normally randomly generated, and
 153     /// is designed to allow `HashSet`s to be resistant to attacks that
 154     /// cause many collisions and very poor performance. Setting it
 155     /// manually using this function can expose a DoS attack vector.
 156     ///
 157     /// # Example
 158     ///
 159     /// ```
 160     /// use std::collections::HashSet;
 161     /// use std::hash::sip::SipHasher;
 162     ///
 163     /// let h = SipHasher::new();
 164     /// let mut set = HashSet::with_capacity_and_hasher(10u, h);
 165     /// set.insert(1i);
 166     /// ```
 167     #[inline]
 168     pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
 169         HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
 170     }
 171
 172     /// Returns the number of elements the set can hold without reallocating.
 173     ///
 174     /// # Example
 175     ///
 176     /// ```
 177     /// use std::collections::HashSet;
 178     /// let set: HashSet<int> = HashSet::with_capacity(100);
 179     /// assert!(set.capacity() >= 100);
 180     /// ```
 181     #[inline]
 182     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 183     pub fn capacity(&self) -> uint {
 184         self.map.capacity()
 185     }
 186
 187     /// Reserves capacity for at least `additional` more elements to be inserted
 188     /// in the `HashSet`. The collection may reserve more space to avoid
 189     /// frequent reallocations.
 190     ///
 191     /// # Panics
 192     ///
 193     /// Panics if the new allocation size overflows `uint`.
 194     ///
 195     /// # Example
 196     ///
 197     /// ```
 198     /// use std::collections::HashSet;
 199     /// let mut set: HashSet<int> = HashSet::new();
 200     /// set.reserve(10);
 201     /// ```
 202     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 203     pub fn reserve(&mut self, additional: uint) {
 204         self.map.reserve(additional)
 205     }
 206
 207     /// Shrinks the capacity of the set as much as possible. It will drop
 208     /// down as much as possible while maintaining the internal rules
 209     /// and possibly leaving some space in accordance with the resize policy.
 210     ///
 211     /// # Example
 212     ///
 213     /// ```
 214     /// use std::collections::HashSet;
 215     ///
 216     /// let mut set: HashSet<int> = HashSet::with_capacity(100);
 217     /// set.insert(1);
 218     /// set.insert(2);
 219     /// assert!(set.capacity() >= 100);
 220     /// set.shrink_to_fit();
 221     /// assert!(set.capacity() >= 2);
 222     /// ```
 223     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 224     pub fn shrink_to_fit(&mut self) {
 225         self.map.shrink_to_fit()
 226     }
 227
 228     /// Deprecated: use `contains` and `BorrowFrom`.
 229     #[deprecated = "use contains and BorrowFrom"]
 230     #[allow(deprecated)]
 231     pub fn contains_equiv<Sized? Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
 232       self.map.contains_key_equiv(value)
 233     }
 234
 235     /// An iterator visiting all elements in arbitrary order.
 236     /// Iterator element type is &'a T.
 237     ///
 238     /// # Example
 239     ///
 240     /// ```
 241     /// use std::collections::HashSet;
 242     /// let mut set = HashSet::new();
 243     /// set.insert("a");
 244     /// set.insert("b");
 245     ///
 246     /// // Will print in an arbitrary order.
 247     /// for x in set.iter() {
 248     ///     println!("{}", x);
 249     /// }
 250     /// ```
 251     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 252     pub fn iter<'a>(&'a self) -> Iter<'a, T> {
 253         Iter { iter: self.map.keys() }
 254     }
 255
 256     /// Creates a consuming iterator, that is, one that moves each value out
 257     /// of the set in arbitrary order. The set cannot be used after calling
 258     /// this.
 259     ///
 260     /// # Example
 261     ///
 262     /// ```
 263     /// use std::collections::HashSet;
 264     /// let mut set = HashSet::new();
 265     /// set.insert("a".to_string());
 266     /// set.insert("b".to_string());
 267     ///
 268     /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
 269     /// let v: Vec<String> = set.into_iter().collect();
 270     ///
 271     /// // Will print in an arbitrary order.
 272     /// for x in v.iter() {
 273     ///     println!("{}", x);
 274     /// }
 275     /// ```
 276     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 277     pub fn into_iter(self) -> IntoIter<T> {
 278         fn first<A, B>((a, _): (A, B)) -> A { a }
 279         let first: fn((T, ())) -> T = first;
 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, returning all elements in an iterator.
 418     #[inline]
 419     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 420     pub fn drain(&mut self) -> Drain<T> {
 421         fn first<A, B>((a, _): (A, B)) -> A { a }
 422         let first: fn((T, ())) -> T = first; // coerce to fn pointer
 423
 424         Drain { iter: self.map.drain().map(first) }
 425     }
 426
 427     /// Clears the set, removing all values.
 428     ///
 429     /// # Example
 430     ///
 431     /// ```
 432     /// use std::collections::HashSet;
 433     ///
 434     /// let mut v = HashSet::new();
 435     /// v.insert(1u);
 436     /// v.clear();
 437     /// assert!(v.is_empty());
 438     /// ```
 439     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 440     pub fn clear(&mut self) { self.map.clear() }
 441
 442     /// Returns `true` if the set contains a value.
 443     ///
 444     /// The value may be any borrowed form of the set's value type, but
 445     /// `Hash` and `Eq` on the borrowed form *must* match those for
 446     /// the value type.
 447     ///
 448     /// # Example
 449     ///
 450     /// ```
 451     /// use std::collections::HashSet;
 452     ///
 453     /// let set: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
 454     /// assert_eq!(set.contains(&1), true);
 455     /// assert_eq!(set.contains(&4), false);
 456     /// ```
 457     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 458     pub fn contains<Sized? Q>(&self, value: &Q) -> bool
 459         where Q: BorrowFrom<T> + Hash<S> + Eq
 460     {
 461         self.map.contains_key(value)
 462     }
 463
 464     /// Returns `true` if the set has no elements in common with `other`.
 465     /// This is equivalent to checking for an empty intersection.
 466     ///
 467     /// # Example
 468     ///
 469     /// ```
 470     /// use std::collections::HashSet;
 471     ///
 472     /// let a: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
 473     /// let mut b: HashSet<uint> = HashSet::new();
 474     ///
 475     /// assert_eq!(a.is_disjoint(&b), true);
 476     /// b.insert(4);
 477     /// assert_eq!(a.is_disjoint(&b), true);
 478     /// b.insert(1);
 479     /// assert_eq!(a.is_disjoint(&b), false);
 480     /// ```
 481     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 482     pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
 483         self.iter().all(|v| !other.contains(v))
 484     }
 485
 486     /// Returns `true` if the set is a subset of another.
 487     ///
 488     /// # Example
 489     ///
 490     /// ```
 491     /// use std::collections::HashSet;
 492     ///
 493     /// let sup: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
 494     /// let mut set: HashSet<uint> = HashSet::new();
 495     ///
 496     /// assert_eq!(set.is_subset(&sup), true);
 497     /// set.insert(2);
 498     /// assert_eq!(set.is_subset(&sup), true);
 499     /// set.insert(4);
 500     /// assert_eq!(set.is_subset(&sup), false);
 501     /// ```
 502     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 503     pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
 504         self.iter().all(|v| other.contains(v))
 505     }
 506
 507     /// Returns `true` if the set is a superset of another.
 508     ///
 509     /// # Example
 510     ///
 511     /// ```
 512     /// use std::collections::HashSet;
 513     ///
 514     /// let sub: HashSet<uint> = [1, 2].iter().map(|&x| x).collect();
 515     /// let mut set: HashSet<uint> = HashSet::new();
 516     ///
 517     /// assert_eq!(set.is_superset(&sub), false);
 518     ///
 519     /// set.insert(0);
 520     /// set.insert(1);
 521     /// assert_eq!(set.is_superset(&sub), false);
 522     ///
 523     /// set.insert(2);
 524     /// assert_eq!(set.is_superset(&sub), true);
 525     /// ```
 526     #[inline]
 527     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 528     pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
 529         other.is_subset(self)
 530     }
 531
 532     /// Adds a value to the set. Returns `true` if the value was not already
 533     /// present in the set.
 534     ///
 535     /// # Example
 536     ///
 537     /// ```
 538     /// use std::collections::HashSet;
 539     ///
 540     /// let mut set = HashSet::new();
 541     ///
 542     /// assert_eq!(set.insert(2u), true);
 543     /// assert_eq!(set.insert(2), false);
 544     /// assert_eq!(set.len(), 1);
 545     /// ```
 546     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 547     pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 548
 549     /// Removes a value from the set. Returns `true` if the value was
 550     /// present in the set.
 551     ///
 552     /// The value may be any borrowed form of the set's value type, but
 553     /// `Hash` and `Eq` on the borrowed form *must* match those for
 554     /// the value type.
 555     ///
 556     /// # Example
 557     ///
 558     /// ```
 559     /// use std::collections::HashSet;
 560     ///
 561     /// let mut set = HashSet::new();
 562     ///
 563     /// set.insert(2u);
 564     /// assert_eq!(set.remove(&2), true);
 565     /// assert_eq!(set.remove(&2), false);
 566     /// ```
 567     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 568     pub fn remove<Sized? Q>(&mut self, value: &Q) -> bool
 569         where Q: BorrowFrom<T> + Hash<S> + Eq
 570     {
 571         self.map.remove(value).is_some()
 572     }
 573 }
 574
 575 impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
 576     fn eq(&self, other: &HashSet<T, H>) -> bool {
 577         if self.len() != other.len() { return false; }
 578
 579         self.iter().all(|key| other.contains(key))
 580     }
 581 }
 582
 583 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
 584
 585 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
 586     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 587         try!(write!(f, "{{"));
 588
 589         for (i, x) in self.iter().enumerate() {
 590             if i != 0 { try!(write!(f, ", ")); }
 591             try!(write!(f, "{}", *x));
 592         }
 593
 594         write!(f, "}}")
 595     }
 596 }
 597
 598 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
 599     fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
 600         let lower = iter.size_hint().0;
 601         let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
 602         set.extend(iter);
 603         set
 604     }
 605 }
 606
 607 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extend<T> for HashSet<T, H> {
 608     fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
 609         for k in iter {
 610             self.insert(k);
 611         }
 612     }
 613 }
 614
 615 #[stable]
 616 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
 617     #[stable]
 618     fn default() -> HashSet<T, H> {
 619         HashSet::with_hasher(Default::default())
 620     }
 621 }
 622
 623 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 624 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 625 BitOr<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
 626     /// Returns the union of `self` and `rhs` as a new `HashSet<T, H>`.
 627     ///
 628     /// # Examples
 629     ///
 630     /// ```
 631     /// use std::collections::HashSet;
 632     ///
 633     /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
 634     /// let b: HashSet<int> = vec![3, 4, 5].into_iter().collect();
 635     ///
 636     /// let set: HashSet<int> = &a | &b;
 637     ///
 638     /// let mut i = 0;
 639     /// let expected = [1, 2, 3, 4, 5];
 640     /// for x in set.iter() {
 641     ///     assert!(expected.contains(x));
 642     ///     i += 1;
 643     /// }
 644     /// assert_eq!(i, expected.len());
 645     /// ```
 646     fn bitor(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
 647         self.union(rhs).cloned().collect()
 648     }
 649 }
 650
 651 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 652 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 653 BitAnd<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
 654     /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, H>`.
 655     ///
 656     /// # Examples
 657     ///
 658     /// ```
 659     /// use std::collections::HashSet;
 660     ///
 661     /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
 662     /// let b: HashSet<int> = vec![2, 3, 4].into_iter().collect();
 663     ///
 664     /// let set: HashSet<int> = &a & &b;
 665     ///
 666     /// let mut i = 0;
 667     /// let expected = [2, 3];
 668     /// for x in set.iter() {
 669     ///     assert!(expected.contains(x));
 670     ///     i += 1;
 671     /// }
 672     /// assert_eq!(i, expected.len());
 673     /// ```
 674     fn bitand(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
 675         self.intersection(rhs).cloned().collect()
 676     }
 677 }
 678
 679 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 680 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 681 BitXor<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
 682     /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, H>`.
 683     ///
 684     /// # Examples
 685     ///
 686     /// ```
 687     /// use std::collections::HashSet;
 688     ///
 689     /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
 690     /// let b: HashSet<int> = vec![3, 4, 5].into_iter().collect();
 691     ///
 692     /// let set: HashSet<int> = &a ^ &b;
 693     ///
 694     /// let mut i = 0;
 695     /// let expected = [1, 2, 4, 5];
 696     /// for x in set.iter() {
 697     ///     assert!(expected.contains(x));
 698     ///     i += 1;
 699     /// }
 700     /// assert_eq!(i, expected.len());
 701     /// ```
 702     fn bitxor(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
 703         self.symmetric_difference(rhs).cloned().collect()
 704     }
 705 }
 706
 707 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 708 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 709 Sub<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
 710     /// Returns the difference of `self` and `rhs` as a new `HashSet<T, H>`.
 711     ///
 712     /// # Examples
 713     ///
 714     /// ```
 715     /// use std::collections::HashSet;
 716     ///
 717     /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
 718     /// let b: HashSet<int> = vec![3, 4, 5].into_iter().collect();
 719     ///
 720     /// let set: HashSet<int> = &a - &b;
 721     ///
 722     /// let mut i = 0;
 723     /// let expected = [1, 2];
 724     /// for x in set.iter() {
 725     ///     assert!(expected.contains(x));
 726     ///     i += 1;
 727     /// }
 728     /// assert_eq!(i, expected.len());
 729     /// ```
 730     fn sub(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
 731         self.difference(rhs).cloned().collect()
 732     }
 733 }
 734
 735 /// HashSet iterator
 736 pub struct Iter<'a, K: 'a> {
 737     iter: Keys<'a, K, ()>
 738 }
 739
 740 /// HashSet move iterator
 741 pub struct IntoIter<K> {
 742     iter: Map<(K, ()), K, map::IntoIter<K, ()>, fn((K, ())) -> K>
 743 }
 744
 745 /// HashSet drain iterator
 746 pub struct Drain<'a, K: 'a> {
 747     iter: Map<(K, ()), K, map::Drain<'a, K, ()>, fn((K, ())) -> K>,
 748 }
 749
 750 /// Intersection iterator
 751 pub struct Intersection<'a, T: 'a, H: 'a> {
 752     // iterator of the first set
 753     iter: Iter<'a, T>,
 754     // the second set
 755     other: &'a HashSet<T, H>,
 756 }
 757
 758 /// Difference iterator
 759 pub struct Difference<'a, T: 'a, H: 'a> {
 760     // iterator of the first set
 761     iter: Iter<'a, T>,
 762     // the second set
 763     other: &'a HashSet<T, H>,
 764 }
 765
 766 /// Symmetric difference iterator.
 767 pub struct SymmetricDifference<'a, T: 'a, H: 'a> {
 768     iter: Chain<Difference<'a, T, H>, Difference<'a, T, H>>
 769 }
 770
 771 /// Set union iterator.
 772 pub struct Union<'a, T: 'a, H: 'a> {
 773     iter: Chain<Iter<'a, T>, Difference<'a, T, H>>
 774 }
 775
 776 impl<'a, K> Iterator<&'a K> for Iter<'a, K> {
 777     fn next(&mut self) -> Option<&'a K> { self.iter.next() }
 778     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 779 }
 780
 781 impl<K> Iterator<K> for IntoIter<K> {
 782     fn next(&mut self) -> Option<K> { self.iter.next() }
 783     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 784 }
 785
 786 impl<'a, K: 'a> Iterator<K> for Drain<'a, K> {
 787     fn next(&mut self) -> Option<K> { self.iter.next() }
 788     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 789 }
 790
 791 impl<'a, T, S, H> Iterator<&'a T> for Intersection<'a, T, H>
 792     where T: Eq + Hash<S>, H: Hasher<S>
 793 {
 794     fn next(&mut self) -> Option<&'a T> {
 795         loop {
 796             match self.iter.next() {
 797                 None => return None,
 798                 Some(elt) => if self.other.contains(elt) {
 799                     return Some(elt)
 800                 },
 801             }
 802         }
 803     }
 804
 805     fn size_hint(&self) -> (uint, Option<uint>) {
 806         let (_, upper) = self.iter.size_hint();
 807         (0, upper)
 808     }
 809 }
 810
 811 impl<'a, T, S, H> Iterator<&'a T> for Difference<'a, T, H>
 812     where T: Eq + Hash<S>, H: Hasher<S>
 813 {
 814     fn next(&mut self) -> Option<&'a T> {
 815         loop {
 816             match self.iter.next() {
 817                 None => return None,
 818                 Some(elt) => if !self.other.contains(elt) {
 819                     return Some(elt)
 820                 },
 821             }
 822         }
 823     }
 824
 825     fn size_hint(&self) -> (uint, Option<uint>) {
 826         let (_, upper) = self.iter.size_hint();
 827         (0, upper)
 828     }
 829 }
 830
 831 impl<'a, T, S, H> Iterator<&'a T> for SymmetricDifference<'a, T, H>
 832     where T: Eq + Hash<S>, H: Hasher<S>
 833 {
 834     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 835     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 836 }
 837
 838 impl<'a, T, S, H> Iterator<&'a T> for Union<'a, T, H>
 839     where T: Eq + Hash<S>, H: Hasher<S>
 840 {
 841     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 842     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 843 }
 844
 845 #[cfg(test)]
 846 mod test_set {
 847     use prelude::*;
 848
 849     use super::HashSet;
 850
 851     #[test]
 852     fn test_disjoint() {
 853         let mut xs = HashSet::new();
 854         let mut ys = HashSet::new();
 855         assert!(xs.is_disjoint(&ys));
 856         assert!(ys.is_disjoint(&xs));
 857         assert!(xs.insert(5i));
 858         assert!(ys.insert(11i));
 859         assert!(xs.is_disjoint(&ys));
 860         assert!(ys.is_disjoint(&xs));
 861         assert!(xs.insert(7));
 862         assert!(xs.insert(19));
 863         assert!(xs.insert(4));
 864         assert!(ys.insert(2));
 865         assert!(ys.insert(-11));
 866         assert!(xs.is_disjoint(&ys));
 867         assert!(ys.is_disjoint(&xs));
 868         assert!(ys.insert(7));
 869         assert!(!xs.is_disjoint(&ys));
 870         assert!(!ys.is_disjoint(&xs));
 871     }
 872
 873     #[test]
 874     fn test_subset_and_superset() {
 875         let mut a = HashSet::new();
 876         assert!(a.insert(0i));
 877         assert!(a.insert(5));
 878         assert!(a.insert(11));
 879         assert!(a.insert(7));
 880
 881         let mut b = HashSet::new();
 882         assert!(b.insert(0i));
 883         assert!(b.insert(7));
 884         assert!(b.insert(19));
 885         assert!(b.insert(250));
 886         assert!(b.insert(11));
 887         assert!(b.insert(200));
 888
 889         assert!(!a.is_subset(&b));
 890         assert!(!a.is_superset(&b));
 891         assert!(!b.is_subset(&a));
 892         assert!(!b.is_superset(&a));
 893
 894         assert!(b.insert(5));
 895
 896         assert!(a.is_subset(&b));
 897         assert!(!a.is_superset(&b));
 898         assert!(!b.is_subset(&a));
 899         assert!(b.is_superset(&a));
 900     }
 901
 902     #[test]
 903     fn test_iterate() {
 904         let mut a = HashSet::new();
 905         for i in range(0u, 32) {
 906             assert!(a.insert(i));
 907         }
 908         let mut observed: u32 = 0;
 909         for k in a.iter() {
 910             observed |= 1 << *k;
 911         }
 912         assert_eq!(observed, 0xFFFF_FFFF);
 913     }
 914
 915     #[test]
 916     fn test_intersection() {
 917         let mut a = HashSet::new();
 918         let mut b = HashSet::new();
 919
 920         assert!(a.insert(11i));
 921         assert!(a.insert(1));
 922         assert!(a.insert(3));
 923         assert!(a.insert(77));
 924         assert!(a.insert(103));
 925         assert!(a.insert(5));
 926         assert!(a.insert(-5));
 927
 928         assert!(b.insert(2i));
 929         assert!(b.insert(11));
 930         assert!(b.insert(77));
 931         assert!(b.insert(-9));
 932         assert!(b.insert(-42));
 933         assert!(b.insert(5));
 934         assert!(b.insert(3));
 935
 936         let mut i = 0;
 937         let expected = [3, 5, 11, 77];
 938         for x in a.intersection(&b) {
 939             assert!(expected.contains(x));
 940             i += 1
 941         }
 942         assert_eq!(i, expected.len());
 943     }
 944
 945     #[test]
 946     fn test_difference() {
 947         let mut a = HashSet::new();
 948         let mut b = HashSet::new();
 949
 950         assert!(a.insert(1i));
 951         assert!(a.insert(3));
 952         assert!(a.insert(5));
 953         assert!(a.insert(9));
 954         assert!(a.insert(11));
 955
 956         assert!(b.insert(3i));
 957         assert!(b.insert(9));
 958
 959         let mut i = 0;
 960         let expected = [1, 5, 11];
 961         for x in a.difference(&b) {
 962             assert!(expected.contains(x));
 963             i += 1
 964         }
 965         assert_eq!(i, expected.len());
 966     }
 967
 968     #[test]
 969     fn test_symmetric_difference() {
 970         let mut a = HashSet::new();
 971         let mut b = HashSet::new();
 972
 973         assert!(a.insert(1i));
 974         assert!(a.insert(3));
 975         assert!(a.insert(5));
 976         assert!(a.insert(9));
 977         assert!(a.insert(11));
 978
 979         assert!(b.insert(-2i));
 980         assert!(b.insert(3));
 981         assert!(b.insert(9));
 982         assert!(b.insert(14));
 983         assert!(b.insert(22));
 984
 985         let mut i = 0;
 986         let expected = [-2, 1, 5, 11, 14, 22];
 987         for x in a.symmetric_difference(&b) {
 988             assert!(expected.contains(x));
 989             i += 1
 990         }
 991         assert_eq!(i, expected.len());
 992     }
 993
 994     #[test]
 995     fn test_union() {
 996         let mut a = HashSet::new();
 997         let mut b = HashSet::new();
 998
 999         assert!(a.insert(1i));
1000         assert!(a.insert(3));
1001         assert!(a.insert(5));
1002         assert!(a.insert(9));
1003         assert!(a.insert(11));
1004         assert!(a.insert(16));
1005         assert!(a.insert(19));
1006         assert!(a.insert(24));
1007
1008         assert!(b.insert(-2i));
1009         assert!(b.insert(1));
1010         assert!(b.insert(5));
1011         assert!(b.insert(9));
1012         assert!(b.insert(13));
1013         assert!(b.insert(19));
1014
1015         let mut i = 0;
1016         let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1017         for x in a.union(&b) {
1018             assert!(expected.contains(x));
1019             i += 1
1020         }
1021         assert_eq!(i, expected.len());
1022     }
1023
1024     #[test]
1025     fn test_from_iter() {
1026         let xs = [1i, 2, 3, 4, 5, 6, 7, 8, 9];
1027
1028         let set: HashSet<int> = xs.iter().map(|&x| x).collect();
1029
1030         for x in xs.iter() {
1031             assert!(set.contains(x));
1032         }
1033     }
1034
1035     #[test]
1036     fn test_move_iter() {
1037         let hs = {
1038             let mut hs = HashSet::new();
1039
1040             hs.insert('a');
1041             hs.insert('b');
1042
1043             hs
1044         };
1045
1046         let v = hs.into_iter().collect::<Vec<char>>();
1047         assert!(['a', 'b'] == v || ['b', 'a'] == v);
1048     }
1049
1050     #[test]
1051     fn test_eq() {
1052         // These constants once happened to expose a bug in insert().
1053         // I'm keeping them around to prevent a regression.
1054         let mut s1 = HashSet::new();
1055
1056         s1.insert(1i);
1057         s1.insert(2);
1058         s1.insert(3);
1059
1060         let mut s2 = HashSet::new();
1061
1062         s2.insert(1i);
1063         s2.insert(2);
1064
1065         assert!(s1 != s2);
1066
1067         s2.insert(3);
1068
1069         assert_eq!(s1, s2);
1070     }
1071
1072     #[test]
1073     fn test_show() {
1074         let mut set: HashSet<int> = HashSet::new();
1075         let empty: HashSet<int> = HashSet::new();
1076
1077         set.insert(1i);
1078         set.insert(2);
1079
1080         let set_str = format!("{}", set);
1081
1082         assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
1083         assert_eq!(format!("{}", empty), "{}");
1084     }
1085
1086     #[test]
1087     fn test_trivial_drain() {
1088         let mut s = HashSet::<int>::new();
1089         for _ in s.drain() {}
1090         assert!(s.is_empty());
1091         drop(s);
1092
1093         let mut s = HashSet::<int>::new();
1094         drop(s.drain());
1095         assert!(s.is_empty());
1096     }
1097
1098     #[test]
1099     fn test_drain() {
1100         let mut s: HashSet<int> = range(1, 100).collect();
1101
1102         // try this a bunch of times to make sure we don't screw up internal state.
1103         for _ in range(0i, 20) {
1104             assert_eq!(s.len(), 99);
1105
1106             {
1107                 let mut last_i = 0;
1108                 let mut d = s.drain();
1109                 for (i, x) in d.by_ref().take(50).enumerate() {
1110                     last_i = i;
1111                     assert!(x != 0);
1112                 }
1113                 assert_eq!(last_i, 49);
1114             }
1115
1116             for _ in s.iter() { panic!("s should be empty!"); }
1117
1118             // reset to try again.
1119             s.extend(range(1, 100));
1120         }
1121     }
1122 }