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