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::Borrow;
  14 use clone::Clone;
  15 use cmp::{Eq, PartialEq};
  16 use core::marker::Sized;
  17 use default::Default;
  18 use fmt::Debug;
  19 use fmt;
  20 use hash::Hash;
  21 use iter::{Iterator, IntoIterator, ExactSizeIterator, FromIterator, Map, Chain, Extend};
  22 use ops::{BitOr, BitAnd, BitXor, Sub};
  23 use option::Option::{Some, None, self};
  24
  25 use super::map::{self, HashMap, Keys, INITIAL_CAPACITY, RandomState};
  26 use super::state::HashState;
  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. This can
  38 /// frequently be achieved by using `#[derive(Eq, Hash)]`. If you implement
  39 /// these yourself, it is important that the following property holds:
  40 ///
  41 /// ```text
  42 /// k1 == k2 -> hash(k1) == hash(k2)
  43 /// ```
  44 ///
  45 /// In other words, if two keys are equal, their hashes must be equal.
  46 ///
  47 ///
  48 /// It is a logic error for an item to be modified in such a way that the
  49 /// item's hash, as determined by the `Hash` trait, or its equality, as
  50 /// determined by the `Eq` trait, changes while it is in the set. This is
  51 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or
  52 /// unsafe code.
  53 ///
  54 /// # Examples
  55 ///
  56 /// ```
  57 /// use std::collections::HashSet;
  58 /// // Type inference lets us omit an explicit type signature (which
  59 /// // would be `HashSet<&str>` in this example).
  60 /// let mut books = HashSet::new();
  61 ///
  62 /// // Add some books.
  63 /// books.insert("A Dance With Dragons");
  64 /// books.insert("To Kill a Mockingbird");
  65 /// books.insert("The Odyssey");
  66 /// books.insert("The Great Gatsby");
  67 ///
  68 /// // Check for a specific one.
  69 /// if !books.contains(&("The Winds of Winter")) {
  70 ///     println!("We have {} books, but The Winds of Winter ain't one.",
  71 ///              books.len());
  72 /// }
  73 ///
  74 /// // Remove a book.
  75 /// books.remove(&"The Odyssey");
  76 ///
  77 /// // Iterate over everything.
  78 /// for book in books.iter() {
  79 ///     println!("{}", *book);
  80 /// }
  81 /// ```
  82 ///
  83 /// The easiest way to use `HashSet` with a custom type is to derive
  84 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
  85 /// future be implied by `Eq`.
  86 ///
  87 /// ```
  88 /// use std::collections::HashSet;
  89 /// #[derive(Hash, Eq, PartialEq, Debug)]
  90 /// struct Viking<'a> {
  91 ///     name: &'a str,
  92 ///     power: usize,
  93 /// }
  94 ///
  95 /// let mut vikings = HashSet::new();
  96 ///
  97 /// vikings.insert(Viking { name: "Einar", power: 9 });
  98 /// vikings.insert(Viking { name: "Einar", power: 9 });
  99 /// vikings.insert(Viking { name: "Olaf", power: 4 });
 100 /// vikings.insert(Viking { name: "Harald", power: 8 });
 101 ///
 102 /// // Use derived implementation to print the vikings.
 103 /// for x in vikings.iter() {
 104 ///     println!("{:?}", x);
 105 /// }
 106 /// ```
 107 #[derive(Clone)]
 108 #[stable(feature = "rust1", since = "1.0.0")]
 109 pub struct HashSet<T, S = RandomState> {
 110     map: HashMap<T, (), S>
 111 }
 112
 113 impl<T: Hash + Eq> HashSet<T, RandomState> {
 114     /// Creates an empty HashSet.
 115     ///
 116     /// # Examples
 117     ///
 118     /// ```
 119     /// use std::collections::HashSet;
 120     /// let mut set: HashSet<i32> = HashSet::new();
 121     /// ```
 122     #[inline]
 123     #[stable(feature = "rust1", since = "1.0.0")]
 124     pub fn new() -> HashSet<T, RandomState> {
 125         HashSet::with_capacity(INITIAL_CAPACITY)
 126     }
 127
 128     /// Creates an empty HashSet with space for at least `n` elements in
 129     /// the hash table.
 130     ///
 131     /// # Examples
 132     ///
 133     /// ```
 134     /// use std::collections::HashSet;
 135     /// let mut set: HashSet<i32> = HashSet::with_capacity(10);
 136     /// ```
 137     #[inline]
 138     #[stable(feature = "rust1", since = "1.0.0")]
 139     pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> {
 140         HashSet { map: HashMap::with_capacity(capacity) }
 141     }
 142 }
 143
 144 impl<T, S> HashSet<T, S>
 145     where T: Eq + Hash, S: HashState
 146 {
 147     /// Creates a new empty hash set which will use the given hasher to hash
 148     /// keys.
 149     ///
 150     /// The hash set is also created with the default initial capacity.
 151     ///
 152     /// # Examples
 153     ///
 154     /// ```
 155     /// # #![feature(std_misc)]
 156     /// use std::collections::HashSet;
 157     /// use std::collections::hash_map::RandomState;
 158     ///
 159     /// let s = RandomState::new();
 160     /// let mut set = HashSet::with_hash_state(s);
 161     /// set.insert(2);
 162     /// ```
 163     #[inline]
 164     #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
 165     pub fn with_hash_state(hash_state: S) -> HashSet<T, S> {
 166         HashSet::with_capacity_and_hash_state(INITIAL_CAPACITY, hash_state)
 167     }
 168
 169     /// Creates an empty HashSet with space for at least `capacity`
 170     /// elements in the hash table, using `hasher` to hash the keys.
 171     ///
 172     /// Warning: `hasher` is normally randomly generated, and
 173     /// is designed to allow `HashSet`s to be resistant to attacks that
 174     /// cause many collisions and very poor performance. Setting it
 175     /// manually using this function can expose a DoS attack vector.
 176     ///
 177     /// # Examples
 178     ///
 179     /// ```
 180     /// # #![feature(std_misc)]
 181     /// use std::collections::HashSet;
 182     /// use std::collections::hash_map::RandomState;
 183     ///
 184     /// let s = RandomState::new();
 185     /// let mut set = HashSet::with_capacity_and_hash_state(10, s);
 186     /// set.insert(1);
 187     /// ```
 188     #[inline]
 189     #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
 190     pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S)
 191                                         -> HashSet<T, S> {
 192         HashSet {
 193             map: HashMap::with_capacity_and_hash_state(capacity, hash_state),
 194         }
 195     }
 196
 197     /// Returns the number of elements the set can hold without reallocating.
 198     ///
 199     /// # Examples
 200     ///
 201     /// ```
 202     /// use std::collections::HashSet;
 203     /// let set: HashSet<i32> = HashSet::with_capacity(100);
 204     /// assert!(set.capacity() >= 100);
 205     /// ```
 206     #[inline]
 207     #[stable(feature = "rust1", since = "1.0.0")]
 208     pub fn capacity(&self) -> usize {
 209         self.map.capacity()
 210     }
 211
 212     /// Reserves capacity for at least `additional` more elements to be inserted
 213     /// in the `HashSet`. The collection may reserve more space to avoid
 214     /// frequent reallocations.
 215     ///
 216     /// # Panics
 217     ///
 218     /// Panics if the new allocation size overflows `usize`.
 219     ///
 220     /// # Examples
 221     ///
 222     /// ```
 223     /// use std::collections::HashSet;
 224     /// let mut set: HashSet<i32> = HashSet::new();
 225     /// set.reserve(10);
 226     /// ```
 227     #[stable(feature = "rust1", since = "1.0.0")]
 228     pub fn reserve(&mut self, additional: usize) {
 229         self.map.reserve(additional)
 230     }
 231
 232     /// Shrinks the capacity of the set as much as possible. It will drop
 233     /// down as much as possible while maintaining the internal rules
 234     /// and possibly leaving some space in accordance with the resize policy.
 235     ///
 236     /// # Examples
 237     ///
 238     /// ```
 239     /// use std::collections::HashSet;
 240     ///
 241     /// let mut set = HashSet::with_capacity(100);
 242     /// set.insert(1);
 243     /// set.insert(2);
 244     /// assert!(set.capacity() >= 100);
 245     /// set.shrink_to_fit();
 246     /// assert!(set.capacity() >= 2);
 247     /// ```
 248     #[stable(feature = "rust1", since = "1.0.0")]
 249     pub fn shrink_to_fit(&mut self) {
 250         self.map.shrink_to_fit()
 251     }
 252
 253     /// An iterator visiting all elements in arbitrary order.
 254     /// Iterator element type is &'a T.
 255     ///
 256     /// # Examples
 257     ///
 258     /// ```
 259     /// use std::collections::HashSet;
 260     /// let mut set = HashSet::new();
 261     /// set.insert("a");
 262     /// set.insert("b");
 263     ///
 264     /// // Will print in an arbitrary order.
 265     /// for x in set.iter() {
 266     ///     println!("{}", x);
 267     /// }
 268     /// ```
 269     #[stable(feature = "rust1", since = "1.0.0")]
 270     pub fn iter(&self) -> Iter<T> {
 271         Iter { iter: self.map.keys() }
 272     }
 273
 274     /// Visit the values representing the difference.
 275     ///
 276     /// # Examples
 277     ///
 278     /// ```
 279     /// use std::collections::HashSet;
 280     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 281     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 282     ///
 283     /// // Can be seen as `a - b`.
 284     /// for x in a.difference(&b) {
 285     ///     println!("{}", x); // Print 1
 286     /// }
 287     ///
 288     /// let diff: HashSet<_> = a.difference(&b).cloned().collect();
 289     /// assert_eq!(diff, [1].iter().cloned().collect());
 290     ///
 291     /// // Note that difference is not symmetric,
 292     /// // and `b - a` means something else:
 293     /// let diff: HashSet<_> = b.difference(&a).cloned().collect();
 294     /// assert_eq!(diff, [4].iter().cloned().collect());
 295     /// ```
 296     #[stable(feature = "rust1", since = "1.0.0")]
 297     pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
 298         Difference {
 299             iter: self.iter(),
 300             other: other,
 301         }
 302     }
 303
 304     /// Visit the values representing the symmetric difference.
 305     ///
 306     /// # Examples
 307     ///
 308     /// ```
 309     /// use std::collections::HashSet;
 310     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 311     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 312     ///
 313     /// // Print 1, 4 in arbitrary order.
 314     /// for x in a.symmetric_difference(&b) {
 315     ///     println!("{}", x);
 316     /// }
 317     ///
 318     /// let diff1: HashSet<_> = a.symmetric_difference(&b).cloned().collect();
 319     /// let diff2: HashSet<_> = b.symmetric_difference(&a).cloned().collect();
 320     ///
 321     /// assert_eq!(diff1, diff2);
 322     /// assert_eq!(diff1, [1, 4].iter().cloned().collect());
 323     /// ```
 324     #[stable(feature = "rust1", since = "1.0.0")]
 325     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>)
 326         -> SymmetricDifference<'a, T, S> {
 327         SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
 328     }
 329
 330     /// Visit the values representing the intersection.
 331     ///
 332     /// # Examples
 333     ///
 334     /// ```
 335     /// use std::collections::HashSet;
 336     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 337     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 338     ///
 339     /// // Print 2, 3 in arbitrary order.
 340     /// for x in a.intersection(&b) {
 341     ///     println!("{}", x);
 342     /// }
 343     ///
 344     /// let diff: HashSet<_> = a.intersection(&b).cloned().collect();
 345     /// assert_eq!(diff, [2, 3].iter().cloned().collect());
 346     /// ```
 347     #[stable(feature = "rust1", since = "1.0.0")]
 348     pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
 349         Intersection {
 350             iter: self.iter(),
 351             other: other,
 352         }
 353     }
 354
 355     /// Visit the values representing the union.
 356     ///
 357     /// # Examples
 358     ///
 359     /// ```
 360     /// use std::collections::HashSet;
 361     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 362     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 363     ///
 364     /// // Print 1, 2, 3, 4 in arbitrary order.
 365     /// for x in a.union(&b) {
 366     ///     println!("{}", x);
 367     /// }
 368     ///
 369     /// let diff: HashSet<_> = a.union(&b).cloned().collect();
 370     /// assert_eq!(diff, [1, 2, 3, 4].iter().cloned().collect());
 371     /// ```
 372     #[stable(feature = "rust1", since = "1.0.0")]
 373     pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
 374         Union { iter: self.iter().chain(other.difference(self)) }
 375     }
 376
 377     /// Returns the number of elements in the set.
 378     ///
 379     /// # Examples
 380     ///
 381     /// ```
 382     /// use std::collections::HashSet;
 383     ///
 384     /// let mut v = HashSet::new();
 385     /// assert_eq!(v.len(), 0);
 386     /// v.insert(1);
 387     /// assert_eq!(v.len(), 1);
 388     /// ```
 389     #[stable(feature = "rust1", since = "1.0.0")]
 390     pub fn len(&self) -> usize { self.map.len() }
 391
 392     /// Returns true if the set contains no elements.
 393     ///
 394     /// # Examples
 395     ///
 396     /// ```
 397     /// use std::collections::HashSet;
 398     ///
 399     /// let mut v = HashSet::new();
 400     /// assert!(v.is_empty());
 401     /// v.insert(1);
 402     /// assert!(!v.is_empty());
 403     /// ```
 404     #[stable(feature = "rust1", since = "1.0.0")]
 405     pub fn is_empty(&self) -> bool { self.map.is_empty() }
 406
 407     /// Clears the set, returning all elements in an iterator.
 408     #[inline]
 409     #[unstable(feature = "std_misc",
 410                reason = "matches collection reform specification, waiting for dust to settle")]
 411     pub fn drain(&mut self) -> Drain<T> {
 412         fn first<A, B>((a, _): (A, B)) -> A { a }
 413         let first: fn((T, ())) -> T = first; // coerce to fn pointer
 414
 415         Drain { iter: self.map.drain().map(first) }
 416     }
 417
 418     /// Clears the set, removing all values.
 419     ///
 420     /// # Examples
 421     ///
 422     /// ```
 423     /// use std::collections::HashSet;
 424     ///
 425     /// let mut v = HashSet::new();
 426     /// v.insert(1);
 427     /// v.clear();
 428     /// assert!(v.is_empty());
 429     /// ```
 430     #[stable(feature = "rust1", since = "1.0.0")]
 431     pub fn clear(&mut self) { self.map.clear() }
 432
 433     /// Returns `true` if the set contains a value.
 434     ///
 435     /// The value may be any borrowed form of the set's value type, but
 436     /// `Hash` and `Eq` on the borrowed form *must* match those for
 437     /// the value type.
 438     ///
 439     /// # Examples
 440     ///
 441     /// ```
 442     /// use std::collections::HashSet;
 443     ///
 444     /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 445     /// assert_eq!(set.contains(&1), true);
 446     /// assert_eq!(set.contains(&4), false);
 447     /// ```
 448     #[stable(feature = "rust1", since = "1.0.0")]
 449     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
 450         where T: Borrow<Q>, Q: Hash + Eq
 451     {
 452         self.map.contains_key(value)
 453     }
 454
 455     /// Returns `true` if the set has no elements in common with `other`.
 456     /// This is equivalent to checking for an empty intersection.
 457     ///
 458     /// # Examples
 459     ///
 460     /// ```
 461     /// use std::collections::HashSet;
 462     ///
 463     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 464     /// let mut b = HashSet::new();
 465     ///
 466     /// assert_eq!(a.is_disjoint(&b), true);
 467     /// b.insert(4);
 468     /// assert_eq!(a.is_disjoint(&b), true);
 469     /// b.insert(1);
 470     /// assert_eq!(a.is_disjoint(&b), false);
 471     /// ```
 472     #[stable(feature = "rust1", since = "1.0.0")]
 473     pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
 474         self.iter().all(|v| !other.contains(v))
 475     }
 476
 477     /// Returns `true` if the set is a subset of another.
 478     ///
 479     /// # Examples
 480     ///
 481     /// ```
 482     /// use std::collections::HashSet;
 483     ///
 484     /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 485     /// let mut set = HashSet::new();
 486     ///
 487     /// assert_eq!(set.is_subset(&sup), true);
 488     /// set.insert(2);
 489     /// assert_eq!(set.is_subset(&sup), true);
 490     /// set.insert(4);
 491     /// assert_eq!(set.is_subset(&sup), false);
 492     /// ```
 493     #[stable(feature = "rust1", since = "1.0.0")]
 494     pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
 495         self.iter().all(|v| other.contains(v))
 496     }
 497
 498     /// Returns `true` if the set is a superset of another.
 499     ///
 500     /// # Examples
 501     ///
 502     /// ```
 503     /// use std::collections::HashSet;
 504     ///
 505     /// let sub: HashSet<_> = [1, 2].iter().cloned().collect();
 506     /// let mut set = HashSet::new();
 507     ///
 508     /// assert_eq!(set.is_superset(&sub), false);
 509     ///
 510     /// set.insert(0);
 511     /// set.insert(1);
 512     /// assert_eq!(set.is_superset(&sub), false);
 513     ///
 514     /// set.insert(2);
 515     /// assert_eq!(set.is_superset(&sub), true);
 516     /// ```
 517     #[inline]
 518     #[stable(feature = "rust1", since = "1.0.0")]
 519     pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
 520         other.is_subset(self)
 521     }
 522
 523     /// Adds a value to the set. Returns `true` if the value was not already
 524     /// present in the set.
 525     ///
 526     /// # Examples
 527     ///
 528     /// ```
 529     /// use std::collections::HashSet;
 530     ///
 531     /// let mut set = HashSet::new();
 532     ///
 533     /// assert_eq!(set.insert(2), true);
 534     /// assert_eq!(set.insert(2), false);
 535     /// assert_eq!(set.len(), 1);
 536     /// ```
 537     #[stable(feature = "rust1", since = "1.0.0")]
 538     pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 539
 540     /// Removes a value from the set. Returns `true` if the value was
 541     /// present in the set.
 542     ///
 543     /// The value may be any borrowed form of the set's value type, but
 544     /// `Hash` and `Eq` on the borrowed form *must* match those for
 545     /// the value type.
 546     ///
 547     /// # Examples
 548     ///
 549     /// ```
 550     /// use std::collections::HashSet;
 551     ///
 552     /// let mut set = HashSet::new();
 553     ///
 554     /// set.insert(2);
 555     /// assert_eq!(set.remove(&2), true);
 556     /// assert_eq!(set.remove(&2), false);
 557     /// ```
 558     #[stable(feature = "rust1", since = "1.0.0")]
 559     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
 560         where T: Borrow<Q>, Q: Hash + Eq
 561     {
 562         self.map.remove(value).is_some()
 563     }
 564 }
 565
 566 #[stable(feature = "rust1", since = "1.0.0")]
 567 impl<T, S> PartialEq for HashSet<T, S>
 568     where T: Eq + Hash, S: HashState
 569 {
 570     fn eq(&self, other: &HashSet<T, S>) -> bool {
 571         if self.len() != other.len() { return false; }
 572
 573         self.iter().all(|key| other.contains(key))
 574     }
 575 }
 576
 577 #[stable(feature = "rust1", since = "1.0.0")]
 578 impl<T, S> Eq for HashSet<T, S>
 579     where T: Eq + Hash, S: HashState
 580 {}
 581
 582 #[stable(feature = "rust1", since = "1.0.0")]
 583 impl<T, S> fmt::Debug for HashSet<T, S>
 584     where T: Eq + Hash + fmt::Debug,
 585           S: HashState
 586 {
 587     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 588         self.iter().fold(f.debug_set(), |b, e| b.entry(e)).finish()
 589     }
 590 }
 591
 592 #[stable(feature = "rust1", since = "1.0.0")]
 593 impl<T, S> FromIterator<T> for HashSet<T, S>
 594     where T: Eq + Hash,
 595           S: HashState + Default,
 596 {
 597     fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> HashSet<T, S> {
 598         let iter = iterable.into_iter();
 599         let lower = iter.size_hint().0;
 600         let mut set = HashSet::with_capacity_and_hash_state(lower, Default::default());
 601         set.extend(iter);
 602         set
 603     }
 604 }
 605
 606 #[stable(feature = "rust1", since = "1.0.0")]
 607 impl<T, S> Extend<T> for HashSet<T, S>
 608     where T: Eq + Hash,
 609           S: HashState,
 610 {
 611     fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
 612         for k in iter {
 613             self.insert(k);
 614         }
 615     }
 616 }
 617
 618 #[stable(feature = "rust1", since = "1.0.0")]
 619 impl<T, S> Default for HashSet<T, S>
 620     where T: Eq + Hash,
 621           S: HashState + Default,
 622 {
 623     #[stable(feature = "rust1", since = "1.0.0")]
 624     fn default() -> HashSet<T, S> {
 625         HashSet::with_hash_state(Default::default())
 626     }
 627 }
 628
 629 #[stable(feature = "rust1", since = "1.0.0")]
 630 impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S>
 631     where T: Eq + Hash + Clone,
 632           S: HashState + Default,
 633 {
 634     type Output = HashSet<T, S>;
 635
 636     /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
 637     ///
 638     /// # Examples
 639     ///
 640     /// ```
 641     /// use std::collections::HashSet;
 642     ///
 643     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 644     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
 645     ///
 646     /// let set = &a | &b;
 647     ///
 648     /// let mut i = 0;
 649     /// let expected = [1, 2, 3, 4, 5];
 650     /// for x in set.iter() {
 651     ///     assert!(expected.contains(x));
 652     ///     i += 1;
 653     /// }
 654     /// assert_eq!(i, expected.len());
 655     /// ```
 656     fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 657         self.union(rhs).cloned().collect()
 658     }
 659 }
 660
 661 #[stable(feature = "rust1", since = "1.0.0")]
 662 impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S>
 663     where T: Eq + Hash + Clone,
 664           S: HashState + Default,
 665 {
 666     type Output = HashSet<T, S>;
 667
 668     /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
 669     ///
 670     /// # Examples
 671     ///
 672     /// ```
 673     /// use std::collections::HashSet;
 674     ///
 675     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 676     /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect();
 677     ///
 678     /// let set = &a & &b;
 679     ///
 680     /// let mut i = 0;
 681     /// let expected = [2, 3];
 682     /// for x in set.iter() {
 683     ///     assert!(expected.contains(x));
 684     ///     i += 1;
 685     /// }
 686     /// assert_eq!(i, expected.len());
 687     /// ```
 688     fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 689         self.intersection(rhs).cloned().collect()
 690     }
 691 }
 692
 693 #[stable(feature = "rust1", since = "1.0.0")]
 694 impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S>
 695     where T: Eq + Hash + Clone,
 696           S: HashState + Default,
 697 {
 698     type Output = HashSet<T, S>;
 699
 700     /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
 701     ///
 702     /// # Examples
 703     ///
 704     /// ```
 705     /// use std::collections::HashSet;
 706     ///
 707     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 708     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
 709     ///
 710     /// let set = &a ^ &b;
 711     ///
 712     /// let mut i = 0;
 713     /// let expected = [1, 2, 4, 5];
 714     /// for x in set.iter() {
 715     ///     assert!(expected.contains(x));
 716     ///     i += 1;
 717     /// }
 718     /// assert_eq!(i, expected.len());
 719     /// ```
 720     fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 721         self.symmetric_difference(rhs).cloned().collect()
 722     }
 723 }
 724
 725 #[stable(feature = "rust1", since = "1.0.0")]
 726 impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S>
 727     where T: Eq + Hash + Clone,
 728           S: HashState + Default,
 729 {
 730     type Output = HashSet<T, S>;
 731
 732     /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
 733     ///
 734     /// # Examples
 735     ///
 736     /// ```
 737     /// use std::collections::HashSet;
 738     ///
 739     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 740     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
 741     ///
 742     /// let set = &a - &b;
 743     ///
 744     /// let mut i = 0;
 745     /// let expected = [1, 2];
 746     /// for x in set.iter() {
 747     ///     assert!(expected.contains(x));
 748     ///     i += 1;
 749     /// }
 750     /// assert_eq!(i, expected.len());
 751     /// ```
 752     fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 753         self.difference(rhs).cloned().collect()
 754     }
 755 }
 756
 757 /// HashSet iterator
 758 #[stable(feature = "rust1", since = "1.0.0")]
 759 pub struct Iter<'a, K: 'a> {
 760     iter: Keys<'a, K, ()>
 761 }
 762
 763 /// HashSet move iterator
 764 #[stable(feature = "rust1", since = "1.0.0")]
 765 pub struct IntoIter<K> {
 766     iter: Map<map::IntoIter<K, ()>, fn((K, ())) -> K>
 767 }
 768
 769 /// HashSet drain iterator
 770 #[stable(feature = "rust1", since = "1.0.0")]
 771 pub struct Drain<'a, K: 'a> {
 772     iter: Map<map::Drain<'a, K, ()>, fn((K, ())) -> K>,
 773 }
 774
 775 /// Intersection iterator
 776 #[stable(feature = "rust1", since = "1.0.0")]
 777 pub struct Intersection<'a, T: 'a, S: 'a> {
 778     // iterator of the first set
 779     iter: Iter<'a, T>,
 780     // the second set
 781     other: &'a HashSet<T, S>,
 782 }
 783
 784 /// Difference iterator
 785 #[stable(feature = "rust1", since = "1.0.0")]
 786 pub struct Difference<'a, T: 'a, S: 'a> {
 787     // iterator of the first set
 788     iter: Iter<'a, T>,
 789     // the second set
 790     other: &'a HashSet<T, S>,
 791 }
 792
 793 /// Symmetric difference iterator.
 794 #[stable(feature = "rust1", since = "1.0.0")]
 795 pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
 796     iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>
 797 }
 798
 799 /// Set union iterator.
 800 #[stable(feature = "rust1", since = "1.0.0")]
 801 pub struct Union<'a, T: 'a, S: 'a> {
 802     iter: Chain<Iter<'a, T>, Difference<'a, T, S>>
 803 }
 804
 805 #[stable(feature = "rust1", since = "1.0.0")]
 806 impl<'a, T, S> IntoIterator for &'a HashSet<T, S>
 807     where T: Eq + Hash, S: HashState
 808 {
 809     type Item = &'a T;
 810     type IntoIter = Iter<'a, T>;
 811
 812     fn into_iter(self) -> Iter<'a, T> {
 813         self.iter()
 814     }
 815 }
 816
 817 #[stable(feature = "rust1", since = "1.0.0")]
 818 impl<T, S> IntoIterator for HashSet<T, S>
 819     where T: Eq + Hash,
 820           S: HashState
 821 {
 822     type Item = T;
 823     type IntoIter = IntoIter<T>;
 824
 825     /// Creates a consuming iterator, that is, one that moves each value out
 826     /// of the set in arbitrary order. The set cannot be used after calling
 827     /// this.
 828     ///
 829     /// # Examples
 830     ///
 831     /// ```
 832     /// use std::collections::HashSet;
 833     /// let mut set = HashSet::new();
 834     /// set.insert("a".to_string());
 835     /// set.insert("b".to_string());
 836     ///
 837     /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
 838     /// let v: Vec<String> = set.into_iter().collect();
 839     ///
 840     /// // Will print in an arbitrary order.
 841     /// for x in v.iter() {
 842     ///     println!("{}", x);
 843     /// }
 844     /// ```
 845     fn into_iter(self) -> IntoIter<T> {
 846         fn first<A, B>((a, _): (A, B)) -> A { a }
 847         let first: fn((T, ())) -> T = first;
 848
 849         IntoIter { iter: self.map.into_iter().map(first) }
 850     }
 851 }
 852
 853 impl<'a, K> Clone for Iter<'a, K> {
 854     fn clone(&self) -> Iter<'a, K> { Iter { iter: self.iter.clone() } }
 855 }
 856 #[stable(feature = "rust1", since = "1.0.0")]
 857 impl<'a, K> Iterator for Iter<'a, K> {
 858     type Item = &'a K;
 859
 860     fn next(&mut self) -> Option<&'a K> { self.iter.next() }
 861     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 862 }
 863 #[stable(feature = "rust1", since = "1.0.0")]
 864 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
 865     fn len(&self) -> usize { self.iter.len() }
 866 }
 867
 868 #[stable(feature = "rust1", since = "1.0.0")]
 869 impl<K> Iterator for IntoIter<K> {
 870     type Item = K;
 871
 872     fn next(&mut self) -> Option<K> { self.iter.next() }
 873     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 874 }
 875 #[stable(feature = "rust1", since = "1.0.0")]
 876 impl<K> ExactSizeIterator for IntoIter<K> {
 877     fn len(&self) -> usize { self.iter.len() }
 878 }
 879
 880 #[stable(feature = "rust1", since = "1.0.0")]
 881 impl<'a, K> Iterator for Drain<'a, K> {
 882     type Item = K;
 883
 884     fn next(&mut self) -> Option<K> { self.iter.next() }
 885     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 886 }
 887 #[stable(feature = "rust1", since = "1.0.0")]
 888 impl<'a, K> ExactSizeIterator for Drain<'a, K> {
 889     fn len(&self) -> usize { self.iter.len() }
 890 }
 891
 892 impl<'a, T, S> Clone for Intersection<'a, T, S> {
 893     fn clone(&self) -> Intersection<'a, T, S> {
 894         Intersection { iter: self.iter.clone(), ..*self }
 895     }
 896 }
 897
 898 #[stable(feature = "rust1", since = "1.0.0")]
 899 impl<'a, T, S> Iterator for Intersection<'a, T, S>
 900     where T: Eq + Hash, S: HashState
 901 {
 902     type Item = &'a T;
 903
 904     fn next(&mut self) -> Option<&'a T> {
 905         loop {
 906             match self.iter.next() {
 907                 None => return None,
 908                 Some(elt) => if self.other.contains(elt) {
 909                     return Some(elt)
 910                 },
 911             }
 912         }
 913     }
 914
 915     fn size_hint(&self) -> (usize, Option<usize>) {
 916         let (_, upper) = self.iter.size_hint();
 917         (0, upper)
 918     }
 919 }
 920
 921 impl<'a, T, S> Clone for Difference<'a, T, S> {
 922     fn clone(&self) -> Difference<'a, T, S> {
 923         Difference { iter: self.iter.clone(), ..*self }
 924     }
 925 }
 926
 927 #[stable(feature = "rust1", since = "1.0.0")]
 928 impl<'a, T, S> Iterator for Difference<'a, T, S>
 929     where T: Eq + Hash, S: HashState
 930 {
 931     type Item = &'a T;
 932
 933     fn next(&mut self) -> Option<&'a T> {
 934         loop {
 935             match self.iter.next() {
 936                 None => return None,
 937                 Some(elt) => if !self.other.contains(elt) {
 938                     return Some(elt)
 939                 },
 940             }
 941         }
 942     }
 943
 944     fn size_hint(&self) -> (usize, Option<usize>) {
 945         let (_, upper) = self.iter.size_hint();
 946         (0, upper)
 947     }
 948 }
 949
 950 impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
 951     fn clone(&self) -> SymmetricDifference<'a, T, S> {
 952         SymmetricDifference { iter: self.iter.clone() }
 953     }
 954 }
 955
 956 #[stable(feature = "rust1", since = "1.0.0")]
 957 impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
 958     where T: Eq + Hash, S: HashState
 959 {
 960     type Item = &'a T;
 961
 962     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 963     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 964 }
 965
 966 impl<'a, T, S> Clone for Union<'a, T, S> {
 967     fn clone(&self) -> Union<'a, T, S> { Union { iter: self.iter.clone() } }
 968 }
 969
 970 #[stable(feature = "rust1", since = "1.0.0")]
 971 impl<'a, T, S> Iterator for Union<'a, T, S>
 972     where T: Eq + Hash, S: HashState
 973 {
 974     type Item = &'a T;
 975
 976     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 977     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 978 }
 979
 980 #[cfg(test)]
 981 mod test_set {
 982     use prelude::v1::*;
 983
 984     use super::HashSet;
 985
 986     #[test]
 987     fn test_disjoint() {
 988         let mut xs = HashSet::new();
 989         let mut ys = HashSet::new();
 990         assert!(xs.is_disjoint(&ys));
 991         assert!(ys.is_disjoint(&xs));
 992         assert!(xs.insert(5));
 993         assert!(ys.insert(11));
 994         assert!(xs.is_disjoint(&ys));
 995         assert!(ys.is_disjoint(&xs));
 996         assert!(xs.insert(7));
 997         assert!(xs.insert(19));
 998         assert!(xs.insert(4));
 999         assert!(ys.insert(2));
1000         assert!(ys.insert(-11));
1001         assert!(xs.is_disjoint(&ys));
1002         assert!(ys.is_disjoint(&xs));
1003         assert!(ys.insert(7));
1004         assert!(!xs.is_disjoint(&ys));
1005         assert!(!ys.is_disjoint(&xs));
1006     }
1007
1008     #[test]
1009     fn test_subset_and_superset() {
1010         let mut a = HashSet::new();
1011         assert!(a.insert(0));
1012         assert!(a.insert(5));
1013         assert!(a.insert(11));
1014         assert!(a.insert(7));
1015
1016         let mut b = HashSet::new();
1017         assert!(b.insert(0));
1018         assert!(b.insert(7));
1019         assert!(b.insert(19));
1020         assert!(b.insert(250));
1021         assert!(b.insert(11));
1022         assert!(b.insert(200));
1023
1024         assert!(!a.is_subset(&b));
1025         assert!(!a.is_superset(&b));
1026         assert!(!b.is_subset(&a));
1027         assert!(!b.is_superset(&a));
1028
1029         assert!(b.insert(5));
1030
1031         assert!(a.is_subset(&b));
1032         assert!(!a.is_superset(&b));
1033         assert!(!b.is_subset(&a));
1034         assert!(b.is_superset(&a));
1035     }
1036
1037     #[test]
1038     fn test_iterate() {
1039         let mut a = HashSet::new();
1040         for i in 0..32 {
1041             assert!(a.insert(i));
1042         }
1043         let mut observed: u32 = 0;
1044         for k in &a {
1045             observed |= 1 << *k;
1046         }
1047         assert_eq!(observed, 0xFFFF_FFFF);
1048     }
1049
1050     #[test]
1051     fn test_intersection() {
1052         let mut a = HashSet::new();
1053         let mut b = HashSet::new();
1054
1055         assert!(a.insert(11));
1056         assert!(a.insert(1));
1057         assert!(a.insert(3));
1058         assert!(a.insert(77));
1059         assert!(a.insert(103));
1060         assert!(a.insert(5));
1061         assert!(a.insert(-5));
1062
1063         assert!(b.insert(2));
1064         assert!(b.insert(11));
1065         assert!(b.insert(77));
1066         assert!(b.insert(-9));
1067         assert!(b.insert(-42));
1068         assert!(b.insert(5));
1069         assert!(b.insert(3));
1070
1071         let mut i = 0;
1072         let expected = [3, 5, 11, 77];
1073         for x in a.intersection(&b) {
1074             assert!(expected.contains(x));
1075             i += 1
1076         }
1077         assert_eq!(i, expected.len());
1078     }
1079
1080     #[test]
1081     fn test_difference() {
1082         let mut a = HashSet::new();
1083         let mut b = HashSet::new();
1084
1085         assert!(a.insert(1));
1086         assert!(a.insert(3));
1087         assert!(a.insert(5));
1088         assert!(a.insert(9));
1089         assert!(a.insert(11));
1090
1091         assert!(b.insert(3));
1092         assert!(b.insert(9));
1093
1094         let mut i = 0;
1095         let expected = [1, 5, 11];
1096         for x in a.difference(&b) {
1097             assert!(expected.contains(x));
1098             i += 1
1099         }
1100         assert_eq!(i, expected.len());
1101     }
1102
1103     #[test]
1104     fn test_symmetric_difference() {
1105         let mut a = HashSet::new();
1106         let mut b = HashSet::new();
1107
1108         assert!(a.insert(1));
1109         assert!(a.insert(3));
1110         assert!(a.insert(5));
1111         assert!(a.insert(9));
1112         assert!(a.insert(11));
1113
1114         assert!(b.insert(-2));
1115         assert!(b.insert(3));
1116         assert!(b.insert(9));
1117         assert!(b.insert(14));
1118         assert!(b.insert(22));
1119
1120         let mut i = 0;
1121         let expected = [-2, 1, 5, 11, 14, 22];
1122         for x in a.symmetric_difference(&b) {
1123             assert!(expected.contains(x));
1124             i += 1
1125         }
1126         assert_eq!(i, expected.len());
1127     }
1128
1129     #[test]
1130     fn test_union() {
1131         let mut a = HashSet::new();
1132         let mut b = HashSet::new();
1133
1134         assert!(a.insert(1));
1135         assert!(a.insert(3));
1136         assert!(a.insert(5));
1137         assert!(a.insert(9));
1138         assert!(a.insert(11));
1139         assert!(a.insert(16));
1140         assert!(a.insert(19));
1141         assert!(a.insert(24));
1142
1143         assert!(b.insert(-2));
1144         assert!(b.insert(1));
1145         assert!(b.insert(5));
1146         assert!(b.insert(9));
1147         assert!(b.insert(13));
1148         assert!(b.insert(19));
1149
1150         let mut i = 0;
1151         let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1152         for x in a.union(&b) {
1153             assert!(expected.contains(x));
1154             i += 1
1155         }
1156         assert_eq!(i, expected.len());
1157     }
1158
1159     #[test]
1160     fn test_from_iter() {
1161         let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
1162
1163         let set: HashSet<_> = xs.iter().cloned().collect();
1164
1165         for x in &xs {
1166             assert!(set.contains(x));
1167         }
1168     }
1169
1170     #[test]
1171     fn test_move_iter() {
1172         let hs = {
1173             let mut hs = HashSet::new();
1174
1175             hs.insert('a');
1176             hs.insert('b');
1177
1178             hs
1179         };
1180
1181         let v = hs.into_iter().collect::<Vec<char>>();
1182         assert!(v == ['a', 'b'] || v == ['b', 'a']);
1183     }
1184
1185     #[test]
1186     fn test_eq() {
1187         // These constants once happened to expose a bug in insert().
1188         // I'm keeping them around to prevent a regression.
1189         let mut s1 = HashSet::new();
1190
1191         s1.insert(1);
1192         s1.insert(2);
1193         s1.insert(3);
1194
1195         let mut s2 = HashSet::new();
1196
1197         s2.insert(1);
1198         s2.insert(2);
1199
1200         assert!(s1 != s2);
1201
1202         s2.insert(3);
1203
1204         assert_eq!(s1, s2);
1205     }
1206
1207     #[test]
1208     fn test_show() {
1209         let mut set = HashSet::new();
1210         let empty = HashSet::<i32>::new();
1211
1212         set.insert(1);
1213         set.insert(2);
1214
1215         let set_str = format!("{:?}", set);
1216
1217         assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
1218         assert_eq!(format!("{:?}", empty), "{}");
1219     }
1220
1221     #[test]
1222     fn test_trivial_drain() {
1223         let mut s = HashSet::<i32>::new();
1224         for _ in s.drain() {}
1225         assert!(s.is_empty());
1226         drop(s);
1227
1228         let mut s = HashSet::<i32>::new();
1229         drop(s.drain());
1230         assert!(s.is_empty());
1231     }
1232
1233     #[test]
1234     fn test_drain() {
1235         let mut s: HashSet<_> = (1..100).collect();
1236
1237         // try this a bunch of times to make sure we don't screw up internal state.
1238         for _ in 0..20 {
1239             assert_eq!(s.len(), 99);
1240
1241             {
1242                 let mut last_i = 0;
1243                 let mut d = s.drain();
1244                 for (i, x) in d.by_ref().take(50).enumerate() {
1245                     last_i = i;
1246                     assert!(x != 0);
1247                 }
1248                 assert_eq!(last_i, 49);
1249             }
1250
1251             for _ in &s { panic!("s should be empty!"); }
1252
1253             // reset to try again.
1254             s.extend(1..100);
1255         }
1256     }
1257 }