vendor/hashbrown-0.5.0/src/set.rs

   1 use crate::CollectionAllocErr;
   2 use core::borrow::Borrow;
   3 use core::fmt;
   4 use core::hash::{BuildHasher, Hash};
   5 use core::iter::{Chain, FromIterator, FusedIterator};
   6 use core::ops::{BitAnd, BitOr, BitXor, Sub};
   7
   8 use super::map::{self, DefaultHashBuilder, HashMap, Keys};
   9
  10 // Future Optimization (FIXME!)
  11 // =============================
  12 //
  13 // Iteration over zero sized values is a noop. There is no need
  14 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
  15 // to get rid of it properly.
  16
  17 /// A hash set implemented as a `HashMap` where the value is `()`.
  18 ///
  19 /// As with the [`HashMap`] type, a `HashSet` requires that the elements
  20 /// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by
  21 /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
  22 /// it is important that the following property holds:
  23 ///
  24 /// ```text
  25 /// k1 == k2 -> hash(k1) == hash(k2)
  26 /// ```
  27 ///
  28 /// In other words, if two keys are equal, their hashes must be equal.
  29 ///
  30 ///
  31 /// It is a logic error for an item to be modified in such a way that the
  32 /// item's hash, as determined by the [`Hash`] trait, or its equality, as
  33 /// determined by the [`Eq`] trait, changes while it is in the set. This is
  34 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or
  35 /// unsafe code.
  36 ///
  37 /// It is also a logic error for the [`Hash`] implementation of a key to panic.
  38 /// This is generally only possible if the trait is implemented manually. If a
  39 /// panic does occur then the contents of the `HashSet` may become corrupted and
  40 /// some items may be dropped from the table.
  41 ///
  42 /// # Examples
  43 ///
  44 /// ```
  45 /// use hashbrown::HashSet;
  46 /// // Type inference lets us omit an explicit type signature (which
  47 /// // would be `HashSet<String>` in this example).
  48 /// let mut books = HashSet::new();
  49 ///
  50 /// // Add some books.
  51 /// books.insert("A Dance With Dragons".to_string());
  52 /// books.insert("To Kill a Mockingbird".to_string());
  53 /// books.insert("The Odyssey".to_string());
  54 /// books.insert("The Great Gatsby".to_string());
  55 ///
  56 /// // Check for a specific one.
  57 /// if !books.contains("The Winds of Winter") {
  58 ///     println!("We have {} books, but The Winds of Winter ain't one.",
  59 ///              books.len());
  60 /// }
  61 ///
  62 /// // Remove a book.
  63 /// books.remove("The Odyssey");
  64 ///
  65 /// // Iterate over everything.
  66 /// for book in &books {
  67 ///     println!("{}", book);
  68 /// }
  69 /// ```
  70 ///
  71 /// The easiest way to use `HashSet` with a custom type is to derive
  72 /// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the
  73 /// future be implied by [`Eq`].
  74 ///
  75 /// ```
  76 /// use hashbrown::HashSet;
  77 /// #[derive(Hash, Eq, PartialEq, Debug)]
  78 /// struct Viking {
  79 ///     name: String,
  80 ///     power: usize,
  81 /// }
  82 ///
  83 /// let mut vikings = HashSet::new();
  84 ///
  85 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
  86 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
  87 /// vikings.insert(Viking { name: "Olaf".to_string(), power: 4 });
  88 /// vikings.insert(Viking { name: "Harald".to_string(), power: 8 });
  89 ///
  90 /// // Use derived implementation to print the vikings.
  91 /// for x in &vikings {
  92 ///     println!("{:?}", x);
  93 /// }
  94 /// ```
  95 ///
  96 /// A `HashSet` with fixed list of elements can be initialized from an array:
  97 ///
  98 /// ```
  99 /// use hashbrown::HashSet;
 100 ///
 101 /// fn main() {
 102 ///     let viking_names: HashSet<&'static str> =
 103 ///         [ "Einar", "Olaf", "Harald" ].iter().cloned().collect();
 104 ///     // use the values stored in the set
 105 /// }
 106 /// ```
 107 ///
 108 /// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html
 109 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
 110 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
 111 /// [`HashMap`]: struct.HashMap.html
 112 /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
 113 /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
 114 #[derive(Clone)]
 115 pub struct HashSet<T, S = DefaultHashBuilder> {
 116     pub(crate) map: HashMap<T, (), S>,
 117 }
 118
 119 impl<T: Hash + Eq> HashSet<T, DefaultHashBuilder> {
 120     /// Creates an empty `HashSet`.
 121     ///
 122     /// The hash set is initially created with a capacity of 0, so it will not allocate until it
 123     /// is first inserted into.
 124     ///
 125     /// # Examples
 126     ///
 127     /// ```
 128     /// use hashbrown::HashSet;
 129     /// let set: HashSet<i32> = HashSet::new();
 130     /// ```
 131     #[inline]
 132     pub fn new() -> Self {
 133         Self {
 134             map: HashMap::new(),
 135         }
 136     }
 137
 138     /// Creates an empty `HashSet` with the specified capacity.
 139     ///
 140     /// The hash set will be able to hold at least `capacity` elements without
 141     /// reallocating. If `capacity` is 0, the hash set will not allocate.
 142     ///
 143     /// # Examples
 144     ///
 145     /// ```
 146     /// use hashbrown::HashSet;
 147     /// let set: HashSet<i32> = HashSet::with_capacity(10);
 148     /// assert!(set.capacity() >= 10);
 149     /// ```
 150     #[inline]
 151     pub fn with_capacity(capacity: usize) -> Self {
 152         Self {
 153             map: HashMap::with_capacity(capacity),
 154         }
 155     }
 156 }
 157
 158 impl<T, S> HashSet<T, S> {
 159     /// Returns the number of elements the set can hold without reallocating.
 160     ///
 161     /// # Examples
 162     ///
 163     /// ```
 164     /// use hashbrown::HashSet;
 165     /// let set: HashSet<i32> = HashSet::with_capacity(100);
 166     /// assert!(set.capacity() >= 100);
 167     /// ```
 168     #[inline]
 169     pub fn capacity(&self) -> usize {
 170         self.map.capacity()
 171     }
 172
 173     /// An iterator visiting all elements in arbitrary order.
 174     /// The iterator element type is `&'a T`.
 175     ///
 176     /// # Examples
 177     ///
 178     /// ```
 179     /// use hashbrown::HashSet;
 180     /// let mut set = HashSet::new();
 181     /// set.insert("a");
 182     /// set.insert("b");
 183     ///
 184     /// // Will print in an arbitrary order.
 185     /// for x in set.iter() {
 186     ///     println!("{}", x);
 187     /// }
 188     /// ```
 189     #[inline]
 190     pub fn iter(&self) -> Iter<'_, T> {
 191         Iter {
 192             iter: self.map.keys(),
 193         }
 194     }
 195
 196     /// Returns the number of elements in the set.
 197     ///
 198     /// # Examples
 199     ///
 200     /// ```
 201     /// use hashbrown::HashSet;
 202     ///
 203     /// let mut v = HashSet::new();
 204     /// assert_eq!(v.len(), 0);
 205     /// v.insert(1);
 206     /// assert_eq!(v.len(), 1);
 207     /// ```
 208     #[inline]
 209     pub fn len(&self) -> usize {
 210         self.map.len()
 211     }
 212
 213     /// Returns `true` if the set contains no elements.
 214     ///
 215     /// # Examples
 216     ///
 217     /// ```
 218     /// use hashbrown::HashSet;
 219     ///
 220     /// let mut v = HashSet::new();
 221     /// assert!(v.is_empty());
 222     /// v.insert(1);
 223     /// assert!(!v.is_empty());
 224     /// ```
 225     #[inline]
 226     pub fn is_empty(&self) -> bool {
 227         self.map.is_empty()
 228     }
 229
 230     /// Clears the set, returning all elements in an iterator.
 231     ///
 232     /// # Examples
 233     ///
 234     /// ```
 235     /// use hashbrown::HashSet;
 236     ///
 237     /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 238     /// assert!(!set.is_empty());
 239     ///
 240     /// // print 1, 2, 3 in an arbitrary order
 241     /// for i in set.drain() {
 242     ///     println!("{}", i);
 243     /// }
 244     ///
 245     /// assert!(set.is_empty());
 246     /// ```
 247     #[inline]
 248     pub fn drain(&mut self) -> Drain<'_, T> {
 249         Drain {
 250             iter: self.map.drain(),
 251         }
 252     }
 253
 254     /// Clears the set, removing all values.
 255     ///
 256     /// # Examples
 257     ///
 258     /// ```
 259     /// use hashbrown::HashSet;
 260     ///
 261     /// let mut v = HashSet::new();
 262     /// v.insert(1);
 263     /// v.clear();
 264     /// assert!(v.is_empty());
 265     /// ```
 266     #[inline]
 267     pub fn clear(&mut self) {
 268         self.map.clear()
 269     }
 270 }
 271
 272 impl<T, S> HashSet<T, S>
 273 where
 274     T: Eq + Hash,
 275     S: BuildHasher,
 276 {
 277     /// Creates a new empty hash set which will use the given hasher to hash
 278     /// keys.
 279     ///
 280     /// The hash set is also created with the default initial capacity.
 281     ///
 282     /// Warning: `hasher` is normally randomly generated, and
 283     /// is designed to allow `HashSet`s to be resistant to attacks that
 284     /// cause many collisions and very poor performance. Setting it
 285     /// manually using this function can expose a DoS attack vector.
 286     ///
 287     /// # Examples
 288     ///
 289     /// ```
 290     /// use hashbrown::HashSet;
 291     /// use hashbrown::hash_map::DefaultHashBuilder;
 292     ///
 293     /// let s = DefaultHashBuilder::default();
 294     /// let mut set = HashSet::with_hasher(s);
 295     /// set.insert(2);
 296     /// ```
 297     #[inline]
 298     pub fn with_hasher(hasher: S) -> Self {
 299         Self {
 300             map: HashMap::with_hasher(hasher),
 301         }
 302     }
 303
 304     /// Creates an empty `HashSet` with the specified capacity, using
 305     /// `hasher` to hash the keys.
 306     ///
 307     /// The hash set will be able to hold at least `capacity` elements without
 308     /// reallocating. If `capacity` is 0, the hash set will not allocate.
 309     ///
 310     /// Warning: `hasher` is normally randomly generated, and
 311     /// is designed to allow `HashSet`s to be resistant to attacks that
 312     /// cause many collisions and very poor performance. Setting it
 313     /// manually using this function can expose a DoS attack vector.
 314     ///
 315     /// # Examples
 316     ///
 317     /// ```
 318     /// use hashbrown::HashSet;
 319     /// use hashbrown::hash_map::DefaultHashBuilder;
 320     ///
 321     /// let s = DefaultHashBuilder::default();
 322     /// let mut set = HashSet::with_capacity_and_hasher(10, s);
 323     /// set.insert(1);
 324     /// ```
 325     #[inline]
 326     pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
 327         Self {
 328             map: HashMap::with_capacity_and_hasher(capacity, hasher),
 329         }
 330     }
 331
 332     /// Returns a reference to the set's [`BuildHasher`].
 333     ///
 334     /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
 335     ///
 336     /// # Examples
 337     ///
 338     /// ```
 339     /// use hashbrown::HashSet;
 340     /// use hashbrown::hash_map::DefaultHashBuilder;
 341     ///
 342     /// let hasher = DefaultHashBuilder::default();
 343     /// let set: HashSet<i32> = HashSet::with_hasher(hasher);
 344     /// let hasher: &DefaultHashBuilder = set.hasher();
 345     /// ```
 346     #[inline]
 347     pub fn hasher(&self) -> &S {
 348         self.map.hasher()
 349     }
 350
 351     /// Reserves capacity for at least `additional` more elements to be inserted
 352     /// in the `HashSet`. The collection may reserve more space to avoid
 353     /// frequent reallocations.
 354     ///
 355     /// # Panics
 356     ///
 357     /// Panics if the new allocation size overflows `usize`.
 358     ///
 359     /// # Examples
 360     ///
 361     /// ```
 362     /// use hashbrown::HashSet;
 363     /// let mut set: HashSet<i32> = HashSet::new();
 364     /// set.reserve(10);
 365     /// assert!(set.capacity() >= 10);
 366     /// ```
 367     #[inline]
 368     pub fn reserve(&mut self, additional: usize) {
 369         self.map.reserve(additional)
 370     }
 371
 372     /// Tries to reserve capacity for at least `additional` more elements to be inserted
 373     /// in the given `HashSet<K,V>`. The collection may reserve more space to avoid
 374     /// frequent reallocations.
 375     ///
 376     /// # Errors
 377     ///
 378     /// If the capacity overflows, or the allocator reports a failure, then an error
 379     /// is returned.
 380     ///
 381     /// # Examples
 382     ///
 383     /// ```
 384     /// use hashbrown::HashSet;
 385     /// let mut set: HashSet<i32> = HashSet::new();
 386     /// set.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
 387     /// ```
 388     #[inline]
 389     pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
 390         self.map.try_reserve(additional)
 391     }
 392
 393     /// Shrinks the capacity of the set as much as possible. It will drop
 394     /// down as much as possible while maintaining the internal rules
 395     /// and possibly leaving some space in accordance with the resize policy.
 396     ///
 397     /// # Examples
 398     ///
 399     /// ```
 400     /// use hashbrown::HashSet;
 401     ///
 402     /// let mut set = HashSet::with_capacity(100);
 403     /// set.insert(1);
 404     /// set.insert(2);
 405     /// assert!(set.capacity() >= 100);
 406     /// set.shrink_to_fit();
 407     /// assert!(set.capacity() >= 2);
 408     /// ```
 409     #[inline]
 410     pub fn shrink_to_fit(&mut self) {
 411         self.map.shrink_to_fit()
 412     }
 413
 414     /// Shrinks the capacity of the set with a lower limit. It will drop
 415     /// down no lower than the supplied limit while maintaining the internal rules
 416     /// and possibly leaving some space in accordance with the resize policy.
 417     ///
 418     /// Panics if the current capacity is smaller than the supplied
 419     /// minimum capacity.
 420     ///
 421     /// # Examples
 422     ///
 423     /// ```
 424     /// use hashbrown::HashSet;
 425     ///
 426     /// let mut set = HashSet::with_capacity(100);
 427     /// set.insert(1);
 428     /// set.insert(2);
 429     /// assert!(set.capacity() >= 100);
 430     /// set.shrink_to(10);
 431     /// assert!(set.capacity() >= 10);
 432     /// set.shrink_to(0);
 433     /// assert!(set.capacity() >= 2);
 434     /// ```
 435     #[inline]
 436     pub fn shrink_to(&mut self, min_capacity: usize) {
 437         self.map.shrink_to(min_capacity)
 438     }
 439
 440     /// Visits the values representing the difference,
 441     /// i.e., the values that are in `self` but not in `other`.
 442     ///
 443     /// # Examples
 444     ///
 445     /// ```
 446     /// use hashbrown::HashSet;
 447     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 448     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 449     ///
 450     /// // Can be seen as `a - b`.
 451     /// for x in a.difference(&b) {
 452     ///     println!("{}", x); // Print 1
 453     /// }
 454     ///
 455     /// let diff: HashSet<_> = a.difference(&b).collect();
 456     /// assert_eq!(diff, [1].iter().collect());
 457     ///
 458     /// // Note that difference is not symmetric,
 459     /// // and `b - a` means something else:
 460     /// let diff: HashSet<_> = b.difference(&a).collect();
 461     /// assert_eq!(diff, [4].iter().collect());
 462     /// ```
 463     #[inline]
 464     pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S> {
 465         Difference {
 466             iter: self.iter(),
 467             other,
 468         }
 469     }
 470
 471     /// Visits the values representing the symmetric difference,
 472     /// i.e., the values that are in `self` or in `other` but not in both.
 473     ///
 474     /// # Examples
 475     ///
 476     /// ```
 477     /// use hashbrown::HashSet;
 478     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 479     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 480     ///
 481     /// // Print 1, 4 in arbitrary order.
 482     /// for x in a.symmetric_difference(&b) {
 483     ///     println!("{}", x);
 484     /// }
 485     ///
 486     /// let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
 487     /// let diff2: HashSet<_> = b.symmetric_difference(&a).collect();
 488     ///
 489     /// assert_eq!(diff1, diff2);
 490     /// assert_eq!(diff1, [1, 4].iter().collect());
 491     /// ```
 492     #[inline]
 493     pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S> {
 494         SymmetricDifference {
 495             iter: self.difference(other).chain(other.difference(self)),
 496         }
 497     }
 498
 499     /// Visits the values representing the intersection,
 500     /// i.e., the values that are both in `self` and `other`.
 501     ///
 502     /// # Examples
 503     ///
 504     /// ```
 505     /// use hashbrown::HashSet;
 506     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 507     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 508     ///
 509     /// // Print 2, 3 in arbitrary order.
 510     /// for x in a.intersection(&b) {
 511     ///     println!("{}", x);
 512     /// }
 513     ///
 514     /// let intersection: HashSet<_> = a.intersection(&b).collect();
 515     /// assert_eq!(intersection, [2, 3].iter().collect());
 516     /// ```
 517     #[inline]
 518     pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S> {
 519         Intersection {
 520             iter: self.iter(),
 521             other,
 522         }
 523     }
 524
 525     /// Visits the values representing the union,
 526     /// i.e., all the values in `self` or `other`, without duplicates.
 527     ///
 528     /// # Examples
 529     ///
 530     /// ```
 531     /// use hashbrown::HashSet;
 532     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 533     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
 534     ///
 535     /// // Print 1, 2, 3, 4 in arbitrary order.
 536     /// for x in a.union(&b) {
 537     ///     println!("{}", x);
 538     /// }
 539     ///
 540     /// let union: HashSet<_> = a.union(&b).collect();
 541     /// assert_eq!(union, [1, 2, 3, 4].iter().collect());
 542     /// ```
 543     #[inline]
 544     pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S> {
 545         Union {
 546             iter: self.iter().chain(other.difference(self)),
 547         }
 548     }
 549
 550     /// Returns `true` if the set contains a value.
 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     /// # Examples
 557     ///
 558     /// ```
 559     /// use hashbrown::HashSet;
 560     ///
 561     /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 562     /// assert_eq!(set.contains(&1), true);
 563     /// assert_eq!(set.contains(&4), false);
 564     /// ```
 565     ///
 566     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
 567     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
 568     #[inline]
 569     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
 570     where
 571         T: Borrow<Q>,
 572         Q: Hash + Eq,
 573     {
 574         self.map.contains_key(value)
 575     }
 576
 577     /// Returns a reference to the value in the set, if any, that is equal to the given value.
 578     ///
 579     /// The value may be any borrowed form of the set's value type, but
 580     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 581     /// the value type.
 582     ///
 583     /// # Examples
 584     ///
 585     /// ```
 586     /// use hashbrown::HashSet;
 587     ///
 588     /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 589     /// assert_eq!(set.get(&2), Some(&2));
 590     /// assert_eq!(set.get(&4), None);
 591     /// ```
 592     ///
 593     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
 594     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
 595     #[inline]
 596     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
 597     where
 598         T: Borrow<Q>,
 599         Q: Hash + Eq,
 600     {
 601         self.map.get_key_value(value).map(|(k, _)| k)
 602     }
 603
 604     /// Returns `true` if `self` has no elements in common with `other`.
 605     /// This is equivalent to checking for an empty intersection.
 606     ///
 607     /// # Examples
 608     ///
 609     /// ```
 610     /// use hashbrown::HashSet;
 611     ///
 612     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 613     /// let mut b = HashSet::new();
 614     ///
 615     /// assert_eq!(a.is_disjoint(&b), true);
 616     /// b.insert(4);
 617     /// assert_eq!(a.is_disjoint(&b), true);
 618     /// b.insert(1);
 619     /// assert_eq!(a.is_disjoint(&b), false);
 620     /// ```
 621     pub fn is_disjoint(&self, other: &Self) -> bool {
 622         self.iter().all(|v| !other.contains(v))
 623     }
 624
 625     /// Returns `true` if the set is a subset of another,
 626     /// i.e., `other` contains at least all the values in `self`.
 627     ///
 628     /// # Examples
 629     ///
 630     /// ```
 631     /// use hashbrown::HashSet;
 632     ///
 633     /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 634     /// let mut set = HashSet::new();
 635     ///
 636     /// assert_eq!(set.is_subset(&sup), true);
 637     /// set.insert(2);
 638     /// assert_eq!(set.is_subset(&sup), true);
 639     /// set.insert(4);
 640     /// assert_eq!(set.is_subset(&sup), false);
 641     /// ```
 642     pub fn is_subset(&self, other: &Self) -> bool {
 643         if self.len() <= other.len() {
 644             self.iter().all(|v| other.contains(v))
 645         } else {
 646             false
 647         }
 648     }
 649
 650     /// Returns `true` if the set is a superset of another,
 651     /// i.e., `self` contains at least all the values in `other`.
 652     ///
 653     /// # Examples
 654     ///
 655     /// ```
 656     /// use hashbrown::HashSet;
 657     ///
 658     /// let sub: HashSet<_> = [1, 2].iter().cloned().collect();
 659     /// let mut set = HashSet::new();
 660     ///
 661     /// assert_eq!(set.is_superset(&sub), false);
 662     ///
 663     /// set.insert(0);
 664     /// set.insert(1);
 665     /// assert_eq!(set.is_superset(&sub), false);
 666     ///
 667     /// set.insert(2);
 668     /// assert_eq!(set.is_superset(&sub), true);
 669     /// ```
 670     #[inline]
 671     pub fn is_superset(&self, other: &Self) -> bool {
 672         other.is_subset(self)
 673     }
 674
 675     /// Adds a value to the set.
 676     ///
 677     /// If the set did not have this value present, `true` is returned.
 678     ///
 679     /// If the set did have this value present, `false` is returned.
 680     ///
 681     /// # Examples
 682     ///
 683     /// ```
 684     /// use hashbrown::HashSet;
 685     ///
 686     /// let mut set = HashSet::new();
 687     ///
 688     /// assert_eq!(set.insert(2), true);
 689     /// assert_eq!(set.insert(2), false);
 690     /// assert_eq!(set.len(), 1);
 691     /// ```
 692     #[inline]
 693     pub fn insert(&mut self, value: T) -> bool {
 694         self.map.insert(value, ()).is_none()
 695     }
 696
 697     /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
 698     /// one. Returns the replaced value.
 699     ///
 700     /// # Examples
 701     ///
 702     /// ```
 703     /// use hashbrown::HashSet;
 704     ///
 705     /// let mut set = HashSet::new();
 706     /// set.insert(Vec::<i32>::new());
 707     ///
 708     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
 709     /// set.replace(Vec::with_capacity(10));
 710     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
 711     /// ```
 712     #[inline]
 713     pub fn replace(&mut self, value: T) -> Option<T> {
 714         match self.map.entry(value) {
 715             map::Entry::Occupied(occupied) => Some(occupied.replace_key()),
 716             map::Entry::Vacant(vacant) => {
 717                 vacant.insert(());
 718                 None
 719             }
 720         }
 721     }
 722
 723     /// Removes a value from the set. Returns whether the value was
 724     /// present in the set.
 725     ///
 726     /// The value may be any borrowed form of the set's value type, but
 727     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 728     /// the value type.
 729     ///
 730     /// # Examples
 731     ///
 732     /// ```
 733     /// use hashbrown::HashSet;
 734     ///
 735     /// let mut set = HashSet::new();
 736     ///
 737     /// set.insert(2);
 738     /// assert_eq!(set.remove(&2), true);
 739     /// assert_eq!(set.remove(&2), false);
 740     /// ```
 741     ///
 742     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
 743     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
 744     #[inline]
 745     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
 746     where
 747         T: Borrow<Q>,
 748         Q: Hash + Eq,
 749     {
 750         self.map.remove(value).is_some()
 751     }
 752
 753     /// Removes and returns the value in the set, if any, that is equal to the given one.
 754     ///
 755     /// The value may be any borrowed form of the set's value type, but
 756     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 757     /// the value type.
 758     ///
 759     /// # Examples
 760     ///
 761     /// ```
 762     /// use hashbrown::HashSet;
 763     ///
 764     /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
 765     /// assert_eq!(set.take(&2), Some(2));
 766     /// assert_eq!(set.take(&2), None);
 767     /// ```
 768     ///
 769     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
 770     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
 771     #[inline]
 772     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
 773     where
 774         T: Borrow<Q>,
 775         Q: Hash + Eq,
 776     {
 777         self.map.remove_entry(value).map(|(k, _)| k)
 778     }
 779
 780     /// Retains only the elements specified by the predicate.
 781     ///
 782     /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
 783     ///
 784     /// # Examples
 785     ///
 786     /// ```
 787     /// use hashbrown::HashSet;
 788     ///
 789     /// let xs = [1,2,3,4,5,6];
 790     /// let mut set: HashSet<i32> = xs.iter().cloned().collect();
 791     /// set.retain(|&k| k % 2 == 0);
 792     /// assert_eq!(set.len(), 3);
 793     /// ```
 794     pub fn retain<F>(&mut self, mut f: F)
 795     where
 796         F: FnMut(&T) -> bool,
 797     {
 798         self.map.retain(|k, _| f(k));
 799     }
 800 }
 801
 802 impl<T, S> PartialEq for HashSet<T, S>
 803 where
 804     T: Eq + Hash,
 805     S: BuildHasher,
 806 {
 807     fn eq(&self, other: &Self) -> bool {
 808         if self.len() != other.len() {
 809             return false;
 810         }
 811
 812         self.iter().all(|key| other.contains(key))
 813     }
 814 }
 815
 816 impl<T, S> Eq for HashSet<T, S>
 817 where
 818     T: Eq + Hash,
 819     S: BuildHasher,
 820 {
 821 }
 822
 823 impl<T, S> fmt::Debug for HashSet<T, S>
 824 where
 825     T: Eq + Hash + fmt::Debug,
 826     S: BuildHasher,
 827 {
 828     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 829         f.debug_set().entries(self.iter()).finish()
 830     }
 831 }
 832
 833 impl<T, S> FromIterator<T> for HashSet<T, S>
 834 where
 835     T: Eq + Hash,
 836     S: BuildHasher + Default,
 837 {
 838     #[inline]
 839     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
 840         let mut set = Self::with_hasher(Default::default());
 841         set.extend(iter);
 842         set
 843     }
 844 }
 845
 846 impl<T, S> Extend<T> for HashSet<T, S>
 847 where
 848     T: Eq + Hash,
 849     S: BuildHasher,
 850 {
 851     #[inline]
 852     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
 853         self.map.extend(iter.into_iter().map(|k| (k, ())));
 854     }
 855 }
 856
 857 impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
 858 where
 859     T: 'a + Eq + Hash + Copy,
 860     S: BuildHasher,
 861 {
 862     #[inline]
 863     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
 864         self.extend(iter.into_iter().cloned());
 865     }
 866 }
 867
 868 impl<T, S> Default for HashSet<T, S>
 869 where
 870     T: Eq + Hash,
 871     S: BuildHasher + Default,
 872 {
 873     /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
 874     #[inline]
 875     fn default() -> Self {
 876         Self {
 877             map: HashMap::default(),
 878         }
 879     }
 880 }
 881
 882 impl<T, S> BitOr<&HashSet<T, S>> for &HashSet<T, S>
 883 where
 884     T: Eq + Hash + Clone,
 885     S: BuildHasher + Default,
 886 {
 887     type Output = HashSet<T, S>;
 888
 889     /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
 890     ///
 891     /// # Examples
 892     ///
 893     /// ```
 894     /// use hashbrown::HashSet;
 895     ///
 896     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 897     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
 898     ///
 899     /// let set = &a | &b;
 900     ///
 901     /// let mut i = 0;
 902     /// let expected = [1, 2, 3, 4, 5];
 903     /// for x in &set {
 904     ///     assert!(expected.contains(x));
 905     ///     i += 1;
 906     /// }
 907     /// assert_eq!(i, expected.len());
 908     /// ```
 909     fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 910         self.union(rhs).cloned().collect()
 911     }
 912 }
 913
 914 impl<T, S> BitAnd<&HashSet<T, S>> for &HashSet<T, S>
 915 where
 916     T: Eq + Hash + Clone,
 917     S: BuildHasher + Default,
 918 {
 919     type Output = HashSet<T, S>;
 920
 921     /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
 922     ///
 923     /// # Examples
 924     ///
 925     /// ```
 926     /// use hashbrown::HashSet;
 927     ///
 928     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 929     /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect();
 930     ///
 931     /// let set = &a & &b;
 932     ///
 933     /// let mut i = 0;
 934     /// let expected = [2, 3];
 935     /// for x in &set {
 936     ///     assert!(expected.contains(x));
 937     ///     i += 1;
 938     /// }
 939     /// assert_eq!(i, expected.len());
 940     /// ```
 941     fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 942         self.intersection(rhs).cloned().collect()
 943     }
 944 }
 945
 946 impl<T, S> BitXor<&HashSet<T, S>> for &HashSet<T, S>
 947 where
 948     T: Eq + Hash + Clone,
 949     S: BuildHasher + Default,
 950 {
 951     type Output = HashSet<T, S>;
 952
 953     /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
 954     ///
 955     /// # Examples
 956     ///
 957     /// ```
 958     /// use hashbrown::HashSet;
 959     ///
 960     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 961     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
 962     ///
 963     /// let set = &a ^ &b;
 964     ///
 965     /// let mut i = 0;
 966     /// let expected = [1, 2, 4, 5];
 967     /// for x in &set {
 968     ///     assert!(expected.contains(x));
 969     ///     i += 1;
 970     /// }
 971     /// assert_eq!(i, expected.len());
 972     /// ```
 973     fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
 974         self.symmetric_difference(rhs).cloned().collect()
 975     }
 976 }
 977
 978 impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
 979 where
 980     T: Eq + Hash + Clone,
 981     S: BuildHasher + Default,
 982 {
 983     type Output = HashSet<T, S>;
 984
 985     /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
 986     ///
 987     /// # Examples
 988     ///
 989     /// ```
 990     /// use hashbrown::HashSet;
 991     ///
 992     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
 993     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
 994     ///
 995     /// let set = &a - &b;
 996     ///
 997     /// let mut i = 0;
 998     /// let expected = [1, 2];
 999     /// for x in &set {
1000     ///     assert!(expected.contains(x));
1001     ///     i += 1;
1002     /// }
1003     /// assert_eq!(i, expected.len());
1004     /// ```
1005     fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1006         self.difference(rhs).cloned().collect()
1007     }
1008 }
1009
1010 /// An iterator over the items of a `HashSet`.
1011 ///
1012 /// This `struct` is created by the [`iter`] method on [`HashSet`].
1013 /// See its documentation for more.
1014 ///
1015 /// [`HashSet`]: struct.HashSet.html
1016 /// [`iter`]: struct.HashSet.html#method.iter
1017 pub struct Iter<'a, K> {
1018     iter: Keys<'a, K, ()>,
1019 }
1020
1021 /// An owning iterator over the items of a `HashSet`.
1022 ///
1023 /// This `struct` is created by the [`into_iter`] method on [`HashSet`][`HashSet`]
1024 /// (provided by the `IntoIterator` trait). See its documentation for more.
1025 ///
1026 /// [`HashSet`]: struct.HashSet.html
1027 /// [`into_iter`]: struct.HashSet.html#method.into_iter
1028 pub struct IntoIter<K> {
1029     iter: map::IntoIter<K, ()>,
1030 }
1031
1032 /// A draining iterator over the items of a `HashSet`.
1033 ///
1034 /// This `struct` is created by the [`drain`] method on [`HashSet`].
1035 /// See its documentation for more.
1036 ///
1037 /// [`HashSet`]: struct.HashSet.html
1038 /// [`drain`]: struct.HashSet.html#method.drain
1039 pub struct Drain<'a, K> {
1040     iter: map::Drain<'a, K, ()>,
1041 }
1042
1043 /// A lazy iterator producing elements in the intersection of `HashSet`s.
1044 ///
1045 /// This `struct` is created by the [`intersection`] method on [`HashSet`].
1046 /// See its documentation for more.
1047 ///
1048 /// [`HashSet`]: struct.HashSet.html
1049 /// [`intersection`]: struct.HashSet.html#method.intersection
1050 pub struct Intersection<'a, T, S> {
1051     // iterator of the first set
1052     iter: Iter<'a, T>,
1053     // the second set
1054     other: &'a HashSet<T, S>,
1055 }
1056
1057 /// A lazy iterator producing elements in the difference of `HashSet`s.
1058 ///
1059 /// This `struct` is created by the [`difference`] method on [`HashSet`].
1060 /// See its documentation for more.
1061 ///
1062 /// [`HashSet`]: struct.HashSet.html
1063 /// [`difference`]: struct.HashSet.html#method.difference
1064 pub struct Difference<'a, T, S> {
1065     // iterator of the first set
1066     iter: Iter<'a, T>,
1067     // the second set
1068     other: &'a HashSet<T, S>,
1069 }
1070
1071 /// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
1072 ///
1073 /// This `struct` is created by the [`symmetric_difference`] method on
1074 /// [`HashSet`]. See its documentation for more.
1075 ///
1076 /// [`HashSet`]: struct.HashSet.html
1077 /// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference
1078 pub struct SymmetricDifference<'a, T, S> {
1079     iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
1080 }
1081
1082 /// A lazy iterator producing elements in the union of `HashSet`s.
1083 ///
1084 /// This `struct` is created by the [`union`] method on [`HashSet`].
1085 /// See its documentation for more.
1086 ///
1087 /// [`HashSet`]: struct.HashSet.html
1088 /// [`union`]: struct.HashSet.html#method.union
1089 pub struct Union<'a, T, S> {
1090     iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
1091 }
1092
1093 impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
1094     type Item = &'a T;
1095     type IntoIter = Iter<'a, T>;
1096
1097     #[inline]
1098     fn into_iter(self) -> Iter<'a, T> {
1099         self.iter()
1100     }
1101 }
1102
1103 impl<T, S> IntoIterator for HashSet<T, S> {
1104     type Item = T;
1105     type IntoIter = IntoIter<T>;
1106
1107     /// Creates a consuming iterator, that is, one that moves each value out
1108     /// of the set in arbitrary order. The set cannot be used after calling
1109     /// this.
1110     ///
1111     /// # Examples
1112     ///
1113     /// ```
1114     /// use hashbrown::HashSet;
1115     /// let mut set = HashSet::new();
1116     /// set.insert("a".to_string());
1117     /// set.insert("b".to_string());
1118     ///
1119     /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1120     /// let v: Vec<String> = set.into_iter().collect();
1121     ///
1122     /// // Will print in an arbitrary order.
1123     /// for x in &v {
1124     ///     println!("{}", x);
1125     /// }
1126     /// ```
1127     #[inline]
1128     fn into_iter(self) -> IntoIter<T> {
1129         IntoIter {
1130             iter: self.map.into_iter(),
1131         }
1132     }
1133 }
1134
1135 impl<K> Clone for Iter<'_, K> {
1136     #[inline]
1137     fn clone(&self) -> Self {
1138         Iter {
1139             iter: self.iter.clone(),
1140         }
1141     }
1142 }
1143 impl<'a, K> Iterator for Iter<'a, K> {
1144     type Item = &'a K;
1145
1146     #[inline]
1147     fn next(&mut self) -> Option<&'a K> {
1148         self.iter.next()
1149     }
1150     #[inline]
1151     fn size_hint(&self) -> (usize, Option<usize>) {
1152         self.iter.size_hint()
1153     }
1154 }
1155 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
1156     #[inline]
1157     fn len(&self) -> usize {
1158         self.iter.len()
1159     }
1160 }
1161 impl<K> FusedIterator for Iter<'_, K> {}
1162
1163 impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
1164     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1165         f.debug_list().entries(self.clone()).finish()
1166     }
1167 }
1168
1169 impl<K> Iterator for IntoIter<K> {
1170     type Item = K;
1171
1172     #[inline]
1173     fn next(&mut self) -> Option<K> {
1174         self.iter.next().map(|(k, _)| k)
1175     }
1176     #[inline]
1177     fn size_hint(&self) -> (usize, Option<usize>) {
1178         self.iter.size_hint()
1179     }
1180 }
1181 impl<K> ExactSizeIterator for IntoIter<K> {
1182     #[inline]
1183     fn len(&self) -> usize {
1184         self.iter.len()
1185     }
1186 }
1187 impl<K> FusedIterator for IntoIter<K> {}
1188
1189 impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
1190     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1191         let entries_iter = self.iter.iter().map(|(k, _)| k);
1192         f.debug_list().entries(entries_iter).finish()
1193     }
1194 }
1195
1196 impl<K> Iterator for Drain<'_, K> {
1197     type Item = K;
1198
1199     #[inline]
1200     fn next(&mut self) -> Option<K> {
1201         self.iter.next().map(|(k, _)| k)
1202     }
1203     #[inline]
1204     fn size_hint(&self) -> (usize, Option<usize>) {
1205         self.iter.size_hint()
1206     }
1207 }
1208 impl<K> ExactSizeIterator for Drain<'_, K> {
1209     #[inline]
1210     fn len(&self) -> usize {
1211         self.iter.len()
1212     }
1213 }
1214 impl<K> FusedIterator for Drain<'_, K> {}
1215
1216 impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
1217     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1218         let entries_iter = self.iter.iter().map(|(k, _)| k);
1219         f.debug_list().entries(entries_iter).finish()
1220     }
1221 }
1222
1223 impl<T, S> Clone for Intersection<'_, T, S> {
1224     #[inline]
1225     fn clone(&self) -> Self {
1226         Intersection {
1227             iter: self.iter.clone(),
1228             ..*self
1229         }
1230     }
1231 }
1232
1233 impl<'a, T, S> Iterator for Intersection<'a, T, S>
1234 where
1235     T: Eq + Hash,
1236     S: BuildHasher,
1237 {
1238     type Item = &'a T;
1239
1240     #[inline]
1241     fn next(&mut self) -> Option<&'a T> {
1242         loop {
1243             let elt = self.iter.next()?;
1244             if self.other.contains(elt) {
1245                 return Some(elt);
1246             }
1247         }
1248     }
1249
1250     #[inline]
1251     fn size_hint(&self) -> (usize, Option<usize>) {
1252         let (_, upper) = self.iter.size_hint();
1253         (0, upper)
1254     }
1255 }
1256
1257 impl<T, S> fmt::Debug for Intersection<'_, T, S>
1258 where
1259     T: fmt::Debug + Eq + Hash,
1260     S: BuildHasher,
1261 {
1262     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1263         f.debug_list().entries(self.clone()).finish()
1264     }
1265 }
1266
1267 impl<T, S> FusedIterator for Intersection<'_, T, S>
1268 where
1269     T: Eq + Hash,
1270     S: BuildHasher,
1271 {
1272 }
1273
1274 impl<T, S> Clone for Difference<'_, T, S> {
1275     #[inline]
1276     fn clone(&self) -> Self {
1277         Difference {
1278             iter: self.iter.clone(),
1279             ..*self
1280         }
1281     }
1282 }
1283
1284 impl<'a, T, S> Iterator for Difference<'a, T, S>
1285 where
1286     T: Eq + Hash,
1287     S: BuildHasher,
1288 {
1289     type Item = &'a T;
1290
1291     #[inline]
1292     fn next(&mut self) -> Option<&'a T> {
1293         loop {
1294             let elt = self.iter.next()?;
1295             if !self.other.contains(elt) {
1296                 return Some(elt);
1297             }
1298         }
1299     }
1300
1301     #[inline]
1302     fn size_hint(&self) -> (usize, Option<usize>) {
1303         let (_, upper) = self.iter.size_hint();
1304         (0, upper)
1305     }
1306 }
1307
1308 impl<T, S> FusedIterator for Difference<'_, T, S>
1309 where
1310     T: Eq + Hash,
1311     S: BuildHasher,
1312 {
1313 }
1314
1315 impl<T, S> fmt::Debug for Difference<'_, T, S>
1316 where
1317     T: fmt::Debug + Eq + Hash,
1318     S: BuildHasher,
1319 {
1320     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1321         f.debug_list().entries(self.clone()).finish()
1322     }
1323 }
1324
1325 impl<T, S> Clone for SymmetricDifference<'_, T, S> {
1326     #[inline]
1327     fn clone(&self) -> Self {
1328         SymmetricDifference {
1329             iter: self.iter.clone(),
1330         }
1331     }
1332 }
1333
1334 impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
1335 where
1336     T: Eq + Hash,
1337     S: BuildHasher,
1338 {
1339     type Item = &'a T;
1340
1341     #[inline]
1342     fn next(&mut self) -> Option<&'a T> {
1343         self.iter.next()
1344     }
1345     #[inline]
1346     fn size_hint(&self) -> (usize, Option<usize>) {
1347         self.iter.size_hint()
1348     }
1349 }
1350
1351 impl<T, S> FusedIterator for SymmetricDifference<'_, T, S>
1352 where
1353     T: Eq + Hash,
1354     S: BuildHasher,
1355 {
1356 }
1357
1358 impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
1359 where
1360     T: fmt::Debug + Eq + Hash,
1361     S: BuildHasher,
1362 {
1363     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1364         f.debug_list().entries(self.clone()).finish()
1365     }
1366 }
1367
1368 impl<T, S> Clone for Union<'_, T, S> {
1369     #[inline]
1370     fn clone(&self) -> Self {
1371         Union {
1372             iter: self.iter.clone(),
1373         }
1374     }
1375 }
1376
1377 impl<T, S> FusedIterator for Union<'_, T, S>
1378 where
1379     T: Eq + Hash,
1380     S: BuildHasher,
1381 {
1382 }
1383
1384 impl<T, S> fmt::Debug for Union<'_, T, S>
1385 where
1386     T: fmt::Debug + Eq + Hash,
1387     S: BuildHasher,
1388 {
1389     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1390         f.debug_list().entries(self.clone()).finish()
1391     }
1392 }
1393
1394 impl<'a, T, S> Iterator for Union<'a, T, S>
1395 where
1396     T: Eq + Hash,
1397     S: BuildHasher,
1398 {
1399     type Item = &'a T;
1400
1401     #[inline]
1402     fn next(&mut self) -> Option<&'a T> {
1403         self.iter.next()
1404     }
1405     #[inline]
1406     fn size_hint(&self) -> (usize, Option<usize>) {
1407         self.iter.size_hint()
1408     }
1409 }
1410
1411 #[allow(dead_code)]
1412 fn assert_covariance() {
1413     fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
1414         v
1415     }
1416     fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
1417         v
1418     }
1419     fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
1420         v
1421     }
1422     fn difference<'a, 'new>(
1423         v: Difference<'a, &'static str, DefaultHashBuilder>,
1424     ) -> Difference<'a, &'new str, DefaultHashBuilder> {
1425         v
1426     }
1427     fn symmetric_difference<'a, 'new>(
1428         v: SymmetricDifference<'a, &'static str, DefaultHashBuilder>,
1429     ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder> {
1430         v
1431     }
1432     fn intersection<'a, 'new>(
1433         v: Intersection<'a, &'static str, DefaultHashBuilder>,
1434     ) -> Intersection<'a, &'new str, DefaultHashBuilder> {
1435         v
1436     }
1437     fn union<'a, 'new>(
1438         v: Union<'a, &'static str, DefaultHashBuilder>,
1439     ) -> Union<'a, &'new str, DefaultHashBuilder> {
1440         v
1441     }
1442     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1443         d
1444     }
1445 }
1446
1447 #[cfg(test)]
1448 mod test_set {
1449     use super::super::map::DefaultHashBuilder;
1450     use super::HashSet;
1451     use std::vec::Vec;
1452
1453     #[test]
1454     fn test_zero_capacities() {
1455         type HS = HashSet<i32>;
1456
1457         let s = HS::new();
1458         assert_eq!(s.capacity(), 0);
1459
1460         let s = HS::default();
1461         assert_eq!(s.capacity(), 0);
1462
1463         let s = HS::with_hasher(DefaultHashBuilder::default());
1464         assert_eq!(s.capacity(), 0);
1465
1466         let s = HS::with_capacity(0);
1467         assert_eq!(s.capacity(), 0);
1468
1469         let s = HS::with_capacity_and_hasher(0, DefaultHashBuilder::default());
1470         assert_eq!(s.capacity(), 0);
1471
1472         let mut s = HS::new();
1473         s.insert(1);
1474         s.insert(2);
1475         s.remove(&1);
1476         s.remove(&2);
1477         s.shrink_to_fit();
1478         assert_eq!(s.capacity(), 0);
1479
1480         let mut s = HS::new();
1481         s.reserve(0);
1482         assert_eq!(s.capacity(), 0);
1483     }
1484
1485     #[test]
1486     fn test_disjoint() {
1487         let mut xs = HashSet::new();
1488         let mut ys = HashSet::new();
1489         assert!(xs.is_disjoint(&ys));
1490         assert!(ys.is_disjoint(&xs));
1491         assert!(xs.insert(5));
1492         assert!(ys.insert(11));
1493         assert!(xs.is_disjoint(&ys));
1494         assert!(ys.is_disjoint(&xs));
1495         assert!(xs.insert(7));
1496         assert!(xs.insert(19));
1497         assert!(xs.insert(4));
1498         assert!(ys.insert(2));
1499         assert!(ys.insert(-11));
1500         assert!(xs.is_disjoint(&ys));
1501         assert!(ys.is_disjoint(&xs));
1502         assert!(ys.insert(7));
1503         assert!(!xs.is_disjoint(&ys));
1504         assert!(!ys.is_disjoint(&xs));
1505     }
1506
1507     #[test]
1508     fn test_subset_and_superset() {
1509         let mut a = HashSet::new();
1510         assert!(a.insert(0));
1511         assert!(a.insert(5));
1512         assert!(a.insert(11));
1513         assert!(a.insert(7));
1514
1515         let mut b = HashSet::new();
1516         assert!(b.insert(0));
1517         assert!(b.insert(7));
1518         assert!(b.insert(19));
1519         assert!(b.insert(250));
1520         assert!(b.insert(11));
1521         assert!(b.insert(200));
1522
1523         assert!(!a.is_subset(&b));
1524         assert!(!a.is_superset(&b));
1525         assert!(!b.is_subset(&a));
1526         assert!(!b.is_superset(&a));
1527
1528         assert!(b.insert(5));
1529
1530         assert!(a.is_subset(&b));
1531         assert!(!a.is_superset(&b));
1532         assert!(!b.is_subset(&a));
1533         assert!(b.is_superset(&a));
1534     }
1535
1536     #[test]
1537     fn test_iterate() {
1538         let mut a = HashSet::new();
1539         for i in 0..32 {
1540             assert!(a.insert(i));
1541         }
1542         let mut observed: u32 = 0;
1543         for k in &a {
1544             observed |= 1 << *k;
1545         }
1546         assert_eq!(observed, 0xFFFF_FFFF);
1547     }
1548
1549     #[test]
1550     fn test_intersection() {
1551         let mut a = HashSet::new();
1552         let mut b = HashSet::new();
1553
1554         assert!(a.insert(11));
1555         assert!(a.insert(1));
1556         assert!(a.insert(3));
1557         assert!(a.insert(77));
1558         assert!(a.insert(103));
1559         assert!(a.insert(5));
1560         assert!(a.insert(-5));
1561
1562         assert!(b.insert(2));
1563         assert!(b.insert(11));
1564         assert!(b.insert(77));
1565         assert!(b.insert(-9));
1566         assert!(b.insert(-42));
1567         assert!(b.insert(5));
1568         assert!(b.insert(3));
1569
1570         let mut i = 0;
1571         let expected = [3, 5, 11, 77];
1572         for x in a.intersection(&b) {
1573             assert!(expected.contains(x));
1574             i += 1
1575         }
1576         assert_eq!(i, expected.len());
1577     }
1578
1579     #[test]
1580     fn test_difference() {
1581         let mut a = HashSet::new();
1582         let mut b = HashSet::new();
1583
1584         assert!(a.insert(1));
1585         assert!(a.insert(3));
1586         assert!(a.insert(5));
1587         assert!(a.insert(9));
1588         assert!(a.insert(11));
1589
1590         assert!(b.insert(3));
1591         assert!(b.insert(9));
1592
1593         let mut i = 0;
1594         let expected = [1, 5, 11];
1595         for x in a.difference(&b) {
1596             assert!(expected.contains(x));
1597             i += 1
1598         }
1599         assert_eq!(i, expected.len());
1600     }
1601
1602     #[test]
1603     fn test_symmetric_difference() {
1604         let mut a = HashSet::new();
1605         let mut b = HashSet::new();
1606
1607         assert!(a.insert(1));
1608         assert!(a.insert(3));
1609         assert!(a.insert(5));
1610         assert!(a.insert(9));
1611         assert!(a.insert(11));
1612
1613         assert!(b.insert(-2));
1614         assert!(b.insert(3));
1615         assert!(b.insert(9));
1616         assert!(b.insert(14));
1617         assert!(b.insert(22));
1618
1619         let mut i = 0;
1620         let expected = [-2, 1, 5, 11, 14, 22];
1621         for x in a.symmetric_difference(&b) {
1622             assert!(expected.contains(x));
1623             i += 1
1624         }
1625         assert_eq!(i, expected.len());
1626     }
1627
1628     #[test]
1629     fn test_union() {
1630         let mut a = HashSet::new();
1631         let mut b = HashSet::new();
1632
1633         assert!(a.insert(1));
1634         assert!(a.insert(3));
1635         assert!(a.insert(5));
1636         assert!(a.insert(9));
1637         assert!(a.insert(11));
1638         assert!(a.insert(16));
1639         assert!(a.insert(19));
1640         assert!(a.insert(24));
1641
1642         assert!(b.insert(-2));
1643         assert!(b.insert(1));
1644         assert!(b.insert(5));
1645         assert!(b.insert(9));
1646         assert!(b.insert(13));
1647         assert!(b.insert(19));
1648
1649         let mut i = 0;
1650         let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1651         for x in a.union(&b) {
1652             assert!(expected.contains(x));
1653             i += 1
1654         }
1655         assert_eq!(i, expected.len());
1656     }
1657
1658     #[test]
1659     fn test_from_iter() {
1660         let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
1661
1662         let set: HashSet<_> = xs.iter().cloned().collect();
1663
1664         for x in &xs {
1665             assert!(set.contains(x));
1666         }
1667     }
1668
1669     #[test]
1670     fn test_move_iter() {
1671         let hs = {
1672             let mut hs = HashSet::new();
1673
1674             hs.insert('a');
1675             hs.insert('b');
1676
1677             hs
1678         };
1679
1680         let v = hs.into_iter().collect::<Vec<char>>();
1681         assert!(v == ['a', 'b'] || v == ['b', 'a']);
1682     }
1683
1684     #[test]
1685     fn test_eq() {
1686         // These constants once happened to expose a bug in insert().
1687         // I'm keeping them around to prevent a regression.
1688         let mut s1 = HashSet::new();
1689
1690         s1.insert(1);
1691         s1.insert(2);
1692         s1.insert(3);
1693
1694         let mut s2 = HashSet::new();
1695
1696         s2.insert(1);
1697         s2.insert(2);
1698
1699         assert!(s1 != s2);
1700
1701         s2.insert(3);
1702
1703         assert_eq!(s1, s2);
1704     }
1705
1706     #[test]
1707     fn test_show() {
1708         let mut set = HashSet::new();
1709         let empty = HashSet::<i32>::new();
1710
1711         set.insert(1);
1712         set.insert(2);
1713
1714         let set_str = format!("{:?}", set);
1715
1716         assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
1717         assert_eq!(format!("{:?}", empty), "{}");
1718     }
1719
1720     #[test]
1721     fn test_trivial_drain() {
1722         let mut s = HashSet::<i32>::new();
1723         for _ in s.drain() {}
1724         assert!(s.is_empty());
1725         drop(s);
1726
1727         let mut s = HashSet::<i32>::new();
1728         drop(s.drain());
1729         assert!(s.is_empty());
1730     }
1731
1732     #[test]
1733     fn test_drain() {
1734         let mut s: HashSet<_> = (1..100).collect();
1735
1736         // try this a bunch of times to make sure we don't screw up internal state.
1737         for _ in 0..20 {
1738             assert_eq!(s.len(), 99);
1739
1740             {
1741                 let mut last_i = 0;
1742                 let mut d = s.drain();
1743                 for (i, x) in d.by_ref().take(50).enumerate() {
1744                     last_i = i;
1745                     assert!(x != 0);
1746                 }
1747                 assert_eq!(last_i, 49);
1748             }
1749
1750             for _ in &s {
1751                 panic!("s should be empty!");
1752             }
1753
1754             // reset to try again.
1755             s.extend(1..100);
1756         }
1757     }
1758
1759     #[test]
1760     fn test_replace() {
1761         use core::hash;
1762
1763         #[derive(Debug)]
1764         struct Foo(&'static str, i32);
1765
1766         impl PartialEq for Foo {
1767             fn eq(&self, other: &Self) -> bool {
1768                 self.0 == other.0
1769             }
1770         }
1771
1772         impl Eq for Foo {}
1773
1774         impl hash::Hash for Foo {
1775             fn hash<H: hash::Hasher>(&self, h: &mut H) {
1776                 self.0.hash(h);
1777             }
1778         }
1779
1780         let mut s = HashSet::new();
1781         assert_eq!(s.replace(Foo("a", 1)), None);
1782         assert_eq!(s.len(), 1);
1783         assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
1784         assert_eq!(s.len(), 1);
1785
1786         let mut it = s.iter();
1787         assert_eq!(it.next(), Some(&Foo("a", 2)));
1788         assert_eq!(it.next(), None);
1789     }
1790
1791     #[test]
1792     fn test_extend_ref() {
1793         let mut a = HashSet::new();
1794         a.insert(1);
1795
1796         a.extend(&[2, 3, 4]);
1797
1798         assert_eq!(a.len(), 4);
1799         assert!(a.contains(&1));
1800         assert!(a.contains(&2));
1801         assert!(a.contains(&3));
1802         assert!(a.contains(&4));
1803
1804         let mut b = HashSet::new();
1805         b.insert(5);
1806         b.insert(6);
1807
1808         a.extend(&b);
1809
1810         assert_eq!(a.len(), 6);
1811         assert!(a.contains(&1));
1812         assert!(a.contains(&2));
1813         assert!(a.contains(&3));
1814         assert!(a.contains(&4));
1815         assert!(a.contains(&5));
1816         assert!(a.contains(&6));
1817     }
1818
1819     #[test]
1820     fn test_retain() {
1821         let xs = [1, 2, 3, 4, 5, 6];
1822         let mut set: HashSet<i32> = xs.iter().cloned().collect();
1823         set.retain(|&k| k % 2 == 0);
1824         assert_eq!(set.len(), 3);
1825         assert!(set.contains(&2));
1826         assert!(set.contains(&4));
1827         assert!(set.contains(&6));
1828     }
1829 }