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