1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // ignore-lexer-test FIXME #15883
13 use borrow::BorrowFrom;
15 use cmp::{Eq, PartialEq};
16 use core::marker::Sized;
20 use hash::{self, Hash};
22 Iterator, IntoIterator, ExactSizeIterator, IteratorExt, FromIterator, Map, Chain, Extend,
24 use ops::{BitOr, BitAnd, BitXor, Sub};
25 use option::Option::{Some, None, self};
27 use super::map::{self, HashMap, Keys, INITIAL_CAPACITY, RandomState, Hasher};
28 use super::state::HashState;
30 // Future Optimization (FIXME!)
31 // =============================
33 // Iteration over zero sized values is a noop. There is no need
34 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
35 // to get rid of it properly.
37 /// An implementation of a hash set using the underlying representation of a
38 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
39 /// requires that the elements implement the `Eq` and `Hash` traits.
44 /// use std::collections::HashSet;
45 /// // Type inference lets us omit an explicit type signature (which
46 /// // would be `HashSet<&str>` in this example).
47 /// let mut books = HashSet::new();
49 /// // Add some books.
50 /// books.insert("A Dance With Dragons");
51 /// books.insert("To Kill a Mockingbird");
52 /// books.insert("The Odyssey");
53 /// books.insert("The Great Gatsby");
55 /// // Check for a specific one.
56 /// if !books.contains(&("The Winds of Winter")) {
57 /// println!("We have {} books, but The Winds of Winter ain't one.",
62 /// books.remove(&"The Odyssey");
64 /// // Iterate over everything.
65 /// for book in books.iter() {
66 /// println!("{}", *book);
70 /// The easiest way to use `HashSet` with a custom type is to derive
71 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
72 /// future be implied by `Eq`.
75 /// use std::collections::HashSet;
76 /// #[derive(Hash, Eq, PartialEq, Debug)]
77 /// struct Viking<'a> {
82 /// let mut vikings = HashSet::new();
84 /// vikings.insert(Viking { name: "Einar", power: 9u });
85 /// vikings.insert(Viking { name: "Einar", power: 9u });
86 /// vikings.insert(Viking { name: "Olaf", power: 4u });
87 /// vikings.insert(Viking { name: "Harald", power: 8u });
89 /// // Use derived implementation to print the vikings.
90 /// for x in vikings.iter() {
91 /// println!("{:?}", x);
95 #[stable(feature = "rust1", since = "1.0.0")]
96 pub struct HashSet<T, S = RandomState> {
97 map: HashMap<T, (), S>
100 impl<T: Hash<Hasher> + Eq> HashSet<T, RandomState> {
101 /// Create an empty HashSet.
106 /// use std::collections::HashSet;
107 /// let mut set: HashSet<int> = HashSet::new();
110 #[stable(feature = "rust1", since = "1.0.0")]
111 pub fn new() -> HashSet<T, RandomState> {
112 HashSet::with_capacity(INITIAL_CAPACITY)
115 /// Create an empty HashSet with space for at least `n` elements in
121 /// use std::collections::HashSet;
122 /// let mut set: HashSet<int> = HashSet::with_capacity(10);
125 #[stable(feature = "rust1", since = "1.0.0")]
126 pub fn with_capacity(capacity: uint) -> HashSet<T, RandomState> {
127 HashSet { map: HashMap::with_capacity(capacity) }
131 impl<T, S, H> HashSet<T, S>
132 where T: Eq + Hash<H>,
133 S: HashState<Hasher=H>,
134 H: hash::Hasher<Output=u64>
136 /// Creates a new empty hash set which will use the given hasher to hash
139 /// The hash set is also created with the default initial capacity.
144 /// use std::collections::HashSet;
145 /// use std::collections::hash_map::RandomState;
147 /// let s = RandomState::new();
148 /// let mut set = HashSet::with_hash_state(s);
152 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
153 pub fn with_hash_state(hash_state: S) -> HashSet<T, S> {
154 HashSet::with_capacity_and_hash_state(INITIAL_CAPACITY, hash_state)
157 /// Create an empty HashSet with space for at least `capacity`
158 /// elements in the hash table, using `hasher` to hash the keys.
160 /// Warning: `hasher` is normally randomly generated, and
161 /// is designed to allow `HashSet`s to be resistant to attacks that
162 /// cause many collisions and very poor performance. Setting it
163 /// manually using this function can expose a DoS attack vector.
168 /// use std::collections::HashSet;
169 /// use std::collections::hash_map::RandomState;
171 /// let s = RandomState::new();
172 /// let mut set = HashSet::with_capacity_and_hash_state(10u, s);
176 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
177 pub fn with_capacity_and_hash_state(capacity: uint, hash_state: S)
180 map: HashMap::with_capacity_and_hash_state(capacity, hash_state),
184 /// Returns the number of elements the set can hold without reallocating.
189 /// use std::collections::HashSet;
190 /// let set: HashSet<int> = HashSet::with_capacity(100);
191 /// assert!(set.capacity() >= 100);
194 #[stable(feature = "rust1", since = "1.0.0")]
195 pub fn capacity(&self) -> uint {
199 /// Reserves capacity for at least `additional` more elements to be inserted
200 /// in the `HashSet`. The collection may reserve more space to avoid
201 /// frequent reallocations.
205 /// Panics if the new allocation size overflows `uint`.
210 /// use std::collections::HashSet;
211 /// let mut set: HashSet<int> = HashSet::new();
214 #[stable(feature = "rust1", since = "1.0.0")]
215 pub fn reserve(&mut self, additional: uint) {
216 self.map.reserve(additional)
219 /// Shrinks the capacity of the set as much as possible. It will drop
220 /// down as much as possible while maintaining the internal rules
221 /// and possibly leaving some space in accordance with the resize policy.
226 /// use std::collections::HashSet;
228 /// let mut set: HashSet<int> = HashSet::with_capacity(100);
231 /// assert!(set.capacity() >= 100);
232 /// set.shrink_to_fit();
233 /// assert!(set.capacity() >= 2);
235 #[stable(feature = "rust1", since = "1.0.0")]
236 pub fn shrink_to_fit(&mut self) {
237 self.map.shrink_to_fit()
240 /// An iterator visiting all elements in arbitrary order.
241 /// Iterator element type is &'a T.
246 /// use std::collections::HashSet;
247 /// let mut set = HashSet::new();
251 /// // Will print in an arbitrary order.
252 /// for x in set.iter() {
253 /// println!("{}", x);
256 #[stable(feature = "rust1", since = "1.0.0")]
257 pub fn iter(&self) -> Iter<T> {
258 Iter { iter: self.map.keys() }
261 /// Creates a consuming iterator, that is, one that moves each value out
262 /// of the set in arbitrary order. The set cannot be used after calling
268 /// use std::collections::HashSet;
269 /// let mut set = HashSet::new();
270 /// set.insert("a".to_string());
271 /// set.insert("b".to_string());
273 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
274 /// let v: Vec<String> = set.into_iter().collect();
276 /// // Will print in an arbitrary order.
277 /// for x in v.iter() {
278 /// println!("{}", x);
281 #[stable(feature = "rust1", since = "1.0.0")]
282 pub fn into_iter(self) -> IntoIter<T> {
283 fn first<A, B>((a, _): (A, B)) -> A { a }
284 let first: fn((T, ())) -> T = first;
286 IntoIter { iter: self.map.into_iter().map(first) }
289 /// Visit the values representing the difference.
294 /// use std::collections::HashSet;
295 /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
296 /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect();
298 /// // Can be seen as `a - b`.
299 /// for x in a.difference(&b) {
300 /// println!("{}", x); // Print 1
303 /// let diff: HashSet<int> = a.difference(&b).map(|&x| x).collect();
304 /// assert_eq!(diff, [1].iter().map(|&x| x).collect());
306 /// // Note that difference is not symmetric,
307 /// // and `b - a` means something else:
308 /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect();
309 /// assert_eq!(diff, [4].iter().map(|&x| x).collect());
311 #[stable(feature = "rust1", since = "1.0.0")]
312 pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
319 /// Visit the values representing the symmetric difference.
324 /// use std::collections::HashSet;
325 /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
326 /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect();
328 /// // Print 1, 4 in arbitrary order.
329 /// for x in a.symmetric_difference(&b) {
330 /// println!("{}", x);
333 /// let diff1: HashSet<int> = a.symmetric_difference(&b).map(|&x| x).collect();
334 /// let diff2: HashSet<int> = b.symmetric_difference(&a).map(|&x| x).collect();
336 /// assert_eq!(diff1, diff2);
337 /// assert_eq!(diff1, [1, 4].iter().map(|&x| x).collect());
339 #[stable(feature = "rust1", since = "1.0.0")]
340 pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>)
341 -> SymmetricDifference<'a, T, S> {
342 SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
345 /// Visit the values representing the intersection.
350 /// use std::collections::HashSet;
351 /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
352 /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect();
354 /// // Print 2, 3 in arbitrary order.
355 /// for x in a.intersection(&b) {
356 /// println!("{}", x);
359 /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect();
360 /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect());
362 #[stable(feature = "rust1", since = "1.0.0")]
363 pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
370 /// Visit the values representing the union.
375 /// use std::collections::HashSet;
376 /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
377 /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect();
379 /// // Print 1, 2, 3, 4 in arbitrary order.
380 /// for x in a.union(&b) {
381 /// println!("{}", x);
384 /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect();
385 /// assert_eq!(diff, [1, 2, 3, 4].iter().map(|&x| x).collect());
387 #[stable(feature = "rust1", since = "1.0.0")]
388 pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
389 Union { iter: self.iter().chain(other.difference(self)) }
392 /// Return the number of elements in the set
397 /// use std::collections::HashSet;
399 /// let mut v = HashSet::new();
400 /// assert_eq!(v.len(), 0);
402 /// assert_eq!(v.len(), 1);
404 #[stable(feature = "rust1", since = "1.0.0")]
405 pub fn len(&self) -> uint { self.map.len() }
407 /// Returns true if the set contains no elements
412 /// use std::collections::HashSet;
414 /// let mut v = HashSet::new();
415 /// assert!(v.is_empty());
417 /// assert!(!v.is_empty());
419 #[stable(feature = "rust1", since = "1.0.0")]
420 pub fn is_empty(&self) -> bool { self.map.len() == 0 }
422 /// Clears the set, returning all elements in an iterator.
424 #[unstable(feature = "std_misc",
425 reason = "matches collection reform specification, waiting for dust to settle")]
426 pub fn drain(&mut self) -> Drain<T> {
427 fn first<A, B>((a, _): (A, B)) -> A { a }
428 let first: fn((T, ())) -> T = first; // coerce to fn pointer
430 Drain { iter: self.map.drain().map(first) }
433 /// Clears the set, removing all values.
438 /// use std::collections::HashSet;
440 /// let mut v = HashSet::new();
443 /// assert!(v.is_empty());
445 #[stable(feature = "rust1", since = "1.0.0")]
446 pub fn clear(&mut self) { self.map.clear() }
448 /// Returns `true` if the set contains a value.
450 /// The value may be any borrowed form of the set's value type, but
451 /// `Hash` and `Eq` on the borrowed form *must* match those for
457 /// use std::collections::HashSet;
459 /// let set: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
460 /// assert_eq!(set.contains(&1), true);
461 /// assert_eq!(set.contains(&4), false);
463 #[stable(feature = "rust1", since = "1.0.0")]
464 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
465 where Q: BorrowFrom<T> + Hash<H> + Eq
467 self.map.contains_key(value)
470 /// Returns `true` if the set has no elements in common with `other`.
471 /// This is equivalent to checking for an empty intersection.
476 /// use std::collections::HashSet;
478 /// let a: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
479 /// let mut b: HashSet<uint> = HashSet::new();
481 /// assert_eq!(a.is_disjoint(&b), true);
483 /// assert_eq!(a.is_disjoint(&b), true);
485 /// assert_eq!(a.is_disjoint(&b), false);
487 #[stable(feature = "rust1", since = "1.0.0")]
488 pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
489 self.iter().all(|v| !other.contains(v))
492 /// Returns `true` if the set is a subset of another.
497 /// use std::collections::HashSet;
499 /// let sup: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
500 /// let mut set: HashSet<uint> = HashSet::new();
502 /// assert_eq!(set.is_subset(&sup), true);
504 /// assert_eq!(set.is_subset(&sup), true);
506 /// assert_eq!(set.is_subset(&sup), false);
508 #[stable(feature = "rust1", since = "1.0.0")]
509 pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
510 self.iter().all(|v| other.contains(v))
513 /// Returns `true` if the set is a superset of another.
518 /// use std::collections::HashSet;
520 /// let sub: HashSet<uint> = [1, 2].iter().map(|&x| x).collect();
521 /// let mut set: HashSet<uint> = HashSet::new();
523 /// assert_eq!(set.is_superset(&sub), false);
527 /// assert_eq!(set.is_superset(&sub), false);
530 /// assert_eq!(set.is_superset(&sub), true);
533 #[stable(feature = "rust1", since = "1.0.0")]
534 pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
535 other.is_subset(self)
538 /// Adds a value to the set. Returns `true` if the value was not already
539 /// present in the set.
544 /// use std::collections::HashSet;
546 /// let mut set = HashSet::new();
548 /// assert_eq!(set.insert(2u), true);
549 /// assert_eq!(set.insert(2), false);
550 /// assert_eq!(set.len(), 1);
552 #[stable(feature = "rust1", since = "1.0.0")]
553 pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
555 /// Removes a value from the set. Returns `true` if the value was
556 /// present in the set.
558 /// The value may be any borrowed form of the set's value type, but
559 /// `Hash` and `Eq` on the borrowed form *must* match those for
565 /// use std::collections::HashSet;
567 /// let mut set = HashSet::new();
570 /// assert_eq!(set.remove(&2), true);
571 /// assert_eq!(set.remove(&2), false);
573 #[stable(feature = "rust1", since = "1.0.0")]
574 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
575 where Q: BorrowFrom<T> + Hash<H> + Eq
577 self.map.remove(value).is_some()
581 #[stable(feature = "rust1", since = "1.0.0")]
582 impl<T, S, H> PartialEq for HashSet<T, S>
583 where T: Eq + Hash<H>,
584 S: HashState<Hasher=H>,
585 H: hash::Hasher<Output=u64>
587 fn eq(&self, other: &HashSet<T, S>) -> bool {
588 if self.len() != other.len() { return false; }
590 self.iter().all(|key| other.contains(key))
594 #[stable(feature = "rust1", since = "1.0.0")]
595 impl<T, S, H> Eq for HashSet<T, S>
596 where T: Eq + Hash<H>,
597 S: HashState<Hasher=H>,
598 H: hash::Hasher<Output=u64>
601 #[stable(feature = "rust1", since = "1.0.0")]
602 impl<T, S, H> fmt::Debug for HashSet<T, S>
603 where T: Eq + Hash<H> + fmt::Debug,
604 S: HashState<Hasher=H>,
605 H: hash::Hasher<Output=u64>
607 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
608 try!(write!(f, "HashSet {{"));
610 for (i, x) in self.iter().enumerate() {
611 if i != 0 { try!(write!(f, ", ")); }
612 try!(write!(f, "{:?}", *x));
619 #[stable(feature = "rust1", since = "1.0.0")]
620 impl<T, S, H> FromIterator<T> for HashSet<T, S>
621 where T: Eq + Hash<H>,
622 S: HashState<Hasher=H> + Default,
623 H: hash::Hasher<Output=u64>
625 fn from_iter<I: Iterator<Item=T>>(iter: I) -> HashSet<T, S> {
626 let lower = iter.size_hint().0;
627 let mut set = HashSet::with_capacity_and_hash_state(lower, Default::default());
633 #[stable(feature = "rust1", since = "1.0.0")]
634 impl<T, S, H> Extend<T> for HashSet<T, S>
635 where T: Eq + Hash<H>,
636 S: HashState<Hasher=H>,
637 H: hash::Hasher<Output=u64>
639 fn extend<I: Iterator<Item=T>>(&mut self, mut iter: I) {
646 #[stable(feature = "rust1", since = "1.0.0")]
647 impl<T, S, H> Default for HashSet<T, S>
648 where T: Eq + Hash<H>,
649 S: HashState<Hasher=H> + Default,
650 H: hash::Hasher<Output=u64>
652 #[stable(feature = "rust1", since = "1.0.0")]
653 fn default() -> HashSet<T, S> {
654 HashSet::with_hash_state(Default::default())
658 #[stable(feature = "rust1", since = "1.0.0")]
659 impl<'a, 'b, T, S, H> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S>
660 where T: Eq + Hash<H> + Clone,
661 S: HashState<Hasher=H> + Default,
662 H: hash::Hasher<Output=u64>
664 type Output = HashSet<T, S>;
666 /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
671 /// use std::collections::HashSet;
673 /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
674 /// let b: HashSet<int> = vec![3, 4, 5].into_iter().collect();
676 /// let set: HashSet<int> = &a | &b;
679 /// let expected = [1, 2, 3, 4, 5];
680 /// for x in set.iter() {
681 /// assert!(expected.contains(x));
684 /// assert_eq!(i, expected.len());
686 fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
687 self.union(rhs).cloned().collect()
691 #[stable(feature = "rust1", since = "1.0.0")]
692 impl<'a, 'b, T, S, H> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S>
693 where T: Eq + Hash<H> + Clone,
694 S: HashState<Hasher=H> + Default,
695 H: hash::Hasher<Output=u64>
697 type Output = HashSet<T, S>;
699 /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
704 /// use std::collections::HashSet;
706 /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
707 /// let b: HashSet<int> = vec![2, 3, 4].into_iter().collect();
709 /// let set: HashSet<int> = &a & &b;
712 /// let expected = [2, 3];
713 /// for x in set.iter() {
714 /// assert!(expected.contains(x));
717 /// assert_eq!(i, expected.len());
719 fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
720 self.intersection(rhs).cloned().collect()
724 #[stable(feature = "rust1", since = "1.0.0")]
725 impl<'a, 'b, T, S, H> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S>
726 where T: Eq + Hash<H> + Clone,
727 S: HashState<Hasher=H> + Default,
728 H: hash::Hasher<Output=u64>
730 type Output = HashSet<T, S>;
732 /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
737 /// use std::collections::HashSet;
739 /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
740 /// let b: HashSet<int> = vec![3, 4, 5].into_iter().collect();
742 /// let set: HashSet<int> = &a ^ &b;
745 /// let expected = [1, 2, 4, 5];
746 /// for x in set.iter() {
747 /// assert!(expected.contains(x));
750 /// assert_eq!(i, expected.len());
752 fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
753 self.symmetric_difference(rhs).cloned().collect()
757 #[stable(feature = "rust1", since = "1.0.0")]
758 impl<'a, 'b, T, S, H> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S>
759 where T: Eq + Hash<H> + Clone,
760 S: HashState<Hasher=H> + Default,
761 H: hash::Hasher<Output=u64>
763 type Output = HashSet<T, S>;
765 /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
770 /// use std::collections::HashSet;
772 /// let a: HashSet<int> = vec![1, 2, 3].into_iter().collect();
773 /// let b: HashSet<int> = vec![3, 4, 5].into_iter().collect();
775 /// let set: HashSet<int> = &a - &b;
778 /// let expected = [1, 2];
779 /// for x in set.iter() {
780 /// assert!(expected.contains(x));
783 /// assert_eq!(i, expected.len());
785 fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
786 self.difference(rhs).cloned().collect()
791 #[stable(feature = "rust1", since = "1.0.0")]
792 pub struct Iter<'a, K: 'a> {
793 iter: Keys<'a, K, ()>
796 /// HashSet move iterator
797 #[stable(feature = "rust1", since = "1.0.0")]
798 pub struct IntoIter<K> {
799 iter: Map<(K, ()), K, map::IntoIter<K, ()>, fn((K, ())) -> K>
802 /// HashSet drain iterator
803 #[stable(feature = "rust1", since = "1.0.0")]
804 pub struct Drain<'a, K: 'a> {
805 iter: Map<(K, ()), K, map::Drain<'a, K, ()>, fn((K, ())) -> K>,
808 /// Intersection iterator
809 #[stable(feature = "rust1", since = "1.0.0")]
810 pub struct Intersection<'a, T: 'a, S: 'a> {
811 // iterator of the first set
814 other: &'a HashSet<T, S>,
817 /// Difference iterator
818 #[stable(feature = "rust1", since = "1.0.0")]
819 pub struct Difference<'a, T: 'a, S: 'a> {
820 // iterator of the first set
823 other: &'a HashSet<T, S>,
826 /// Symmetric difference iterator.
827 #[stable(feature = "rust1", since = "1.0.0")]
828 pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
829 iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>
832 /// Set union iterator.
833 #[stable(feature = "rust1", since = "1.0.0")]
834 pub struct Union<'a, T: 'a, S: 'a> {
835 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>
838 impl<'a, T, S, H> IntoIterator for &'a HashSet<T, S>
839 where T: Eq + Hash<H>,
840 S: HashState<Hasher=H>,
841 H: hash::Hasher<Output=u64>
843 type Iter = Iter<'a, T>;
845 fn into_iter(self) -> Iter<'a, T> {
850 impl<T, S, H> IntoIterator for HashSet<T, S>
851 where T: Eq + Hash<H>,
852 S: HashState<Hasher=H>,
853 H: hash::Hasher<Output=u64>
855 type Iter = IntoIter<T>;
857 fn into_iter(self) -> IntoIter<T> {
862 #[stable(feature = "rust1", since = "1.0.0")]
863 impl<'a, K> Iterator for Iter<'a, K> {
866 fn next(&mut self) -> Option<&'a K> { self.iter.next() }
867 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
869 #[stable(feature = "rust1", since = "1.0.0")]
870 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
871 fn len(&self) -> usize { self.iter.len() }
874 #[stable(feature = "rust1", since = "1.0.0")]
875 impl<K> Iterator for IntoIter<K> {
878 fn next(&mut self) -> Option<K> { self.iter.next() }
879 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
881 #[stable(feature = "rust1", since = "1.0.0")]
882 impl<K> ExactSizeIterator for IntoIter<K> {
883 fn len(&self) -> usize { self.iter.len() }
886 #[stable(feature = "rust1", since = "1.0.0")]
887 impl<'a, K> Iterator for Drain<'a, K> {
890 fn next(&mut self) -> Option<K> { self.iter.next() }
891 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
893 #[stable(feature = "rust1", since = "1.0.0")]
894 impl<'a, K> ExactSizeIterator for Drain<'a, K> {
895 fn len(&self) -> usize { self.iter.len() }
898 #[stable(feature = "rust1", since = "1.0.0")]
899 impl<'a, T, S, H> Iterator for Intersection<'a, T, S>
900 where T: Eq + Hash<H>,
901 S: HashState<Hasher=H>,
902 H: hash::Hasher<Output=u64>
906 fn next(&mut self) -> Option<&'a T> {
908 match self.iter.next() {
910 Some(elt) => if self.other.contains(elt) {
917 fn size_hint(&self) -> (usize, Option<usize>) {
918 let (_, upper) = self.iter.size_hint();
923 #[stable(feature = "rust1", since = "1.0.0")]
924 impl<'a, T, S, H> Iterator for Difference<'a, T, S>
925 where T: Eq + Hash<H>,
926 S: HashState<Hasher=H>,
927 H: hash::Hasher<Output=u64>
931 fn next(&mut self) -> Option<&'a T> {
933 match self.iter.next() {
935 Some(elt) => if !self.other.contains(elt) {
942 fn size_hint(&self) -> (usize, Option<usize>) {
943 let (_, upper) = self.iter.size_hint();
948 #[stable(feature = "rust1", since = "1.0.0")]
949 impl<'a, T, S, H> Iterator for SymmetricDifference<'a, T, S>
950 where T: Eq + Hash<H>,
951 S: HashState<Hasher=H>,
952 H: hash::Hasher<Output=u64>
956 fn next(&mut self) -> Option<&'a T> { self.iter.next() }
957 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
960 #[stable(feature = "rust1", since = "1.0.0")]
961 impl<'a, T, S, H> Iterator for Union<'a, T, S>
962 where T: Eq + Hash<H>,
963 S: HashState<Hasher=H>,
964 H: hash::Hasher<Output=u64>
968 fn next(&mut self) -> Option<&'a T> { self.iter.next() }
969 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
980 let mut xs = HashSet::new();
981 let mut ys = HashSet::new();
982 assert!(xs.is_disjoint(&ys));
983 assert!(ys.is_disjoint(&xs));
984 assert!(xs.insert(5));
985 assert!(ys.insert(11));
986 assert!(xs.is_disjoint(&ys));
987 assert!(ys.is_disjoint(&xs));
988 assert!(xs.insert(7));
989 assert!(xs.insert(19));
990 assert!(xs.insert(4));
991 assert!(ys.insert(2));
992 assert!(ys.insert(-11));
993 assert!(xs.is_disjoint(&ys));
994 assert!(ys.is_disjoint(&xs));
995 assert!(ys.insert(7));
996 assert!(!xs.is_disjoint(&ys));
997 assert!(!ys.is_disjoint(&xs));
1001 fn test_subset_and_superset() {
1002 let mut a = HashSet::new();
1003 assert!(a.insert(0));
1004 assert!(a.insert(5));
1005 assert!(a.insert(11));
1006 assert!(a.insert(7));
1008 let mut b = HashSet::new();
1009 assert!(b.insert(0));
1010 assert!(b.insert(7));
1011 assert!(b.insert(19));
1012 assert!(b.insert(250));
1013 assert!(b.insert(11));
1014 assert!(b.insert(200));
1016 assert!(!a.is_subset(&b));
1017 assert!(!a.is_superset(&b));
1018 assert!(!b.is_subset(&a));
1019 assert!(!b.is_superset(&a));
1021 assert!(b.insert(5));
1023 assert!(a.is_subset(&b));
1024 assert!(!a.is_superset(&b));
1025 assert!(!b.is_subset(&a));
1026 assert!(b.is_superset(&a));
1031 let mut a = HashSet::new();
1033 assert!(a.insert(i));
1035 let mut observed: u32 = 0;
1037 observed |= 1 << *k;
1039 assert_eq!(observed, 0xFFFF_FFFF);
1043 fn test_intersection() {
1044 let mut a = HashSet::new();
1045 let mut b = HashSet::new();
1047 assert!(a.insert(11));
1048 assert!(a.insert(1));
1049 assert!(a.insert(3));
1050 assert!(a.insert(77));
1051 assert!(a.insert(103));
1052 assert!(a.insert(5));
1053 assert!(a.insert(-5));
1055 assert!(b.insert(2));
1056 assert!(b.insert(11));
1057 assert!(b.insert(77));
1058 assert!(b.insert(-9));
1059 assert!(b.insert(-42));
1060 assert!(b.insert(5));
1061 assert!(b.insert(3));
1064 let expected = [3, 5, 11, 77];
1065 for x in a.intersection(&b) {
1066 assert!(expected.contains(x));
1069 assert_eq!(i, expected.len());
1073 fn test_difference() {
1074 let mut a = HashSet::new();
1075 let mut b = HashSet::new();
1077 assert!(a.insert(1));
1078 assert!(a.insert(3));
1079 assert!(a.insert(5));
1080 assert!(a.insert(9));
1081 assert!(a.insert(11));
1083 assert!(b.insert(3));
1084 assert!(b.insert(9));
1087 let expected = [1, 5, 11];
1088 for x in a.difference(&b) {
1089 assert!(expected.contains(x));
1092 assert_eq!(i, expected.len());
1096 fn test_symmetric_difference() {
1097 let mut a = HashSet::new();
1098 let mut b = HashSet::new();
1100 assert!(a.insert(1));
1101 assert!(a.insert(3));
1102 assert!(a.insert(5));
1103 assert!(a.insert(9));
1104 assert!(a.insert(11));
1106 assert!(b.insert(-2));
1107 assert!(b.insert(3));
1108 assert!(b.insert(9));
1109 assert!(b.insert(14));
1110 assert!(b.insert(22));
1113 let expected = [-2, 1, 5, 11, 14, 22];
1114 for x in a.symmetric_difference(&b) {
1115 assert!(expected.contains(x));
1118 assert_eq!(i, expected.len());
1123 let mut a = HashSet::new();
1124 let mut b = HashSet::new();
1126 assert!(a.insert(1));
1127 assert!(a.insert(3));
1128 assert!(a.insert(5));
1129 assert!(a.insert(9));
1130 assert!(a.insert(11));
1131 assert!(a.insert(16));
1132 assert!(a.insert(19));
1133 assert!(a.insert(24));
1135 assert!(b.insert(-2));
1136 assert!(b.insert(1));
1137 assert!(b.insert(5));
1138 assert!(b.insert(9));
1139 assert!(b.insert(13));
1140 assert!(b.insert(19));
1143 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1144 for x in a.union(&b) {
1145 assert!(expected.contains(x));
1148 assert_eq!(i, expected.len());
1152 fn test_from_iter() {
1153 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
1155 let set: HashSet<int> = xs.iter().map(|&x| x).collect();
1158 assert!(set.contains(x));
1163 fn test_move_iter() {
1165 let mut hs = HashSet::new();
1173 let v = hs.into_iter().collect::<Vec<char>>();
1174 assert!(['a', 'b'] == v || ['b', 'a'] == v);
1179 // These constants once happened to expose a bug in insert().
1180 // I'm keeping them around to prevent a regression.
1181 let mut s1 = HashSet::new();
1187 let mut s2 = HashSet::new();
1201 let mut set: HashSet<int> = HashSet::new();
1202 let empty: HashSet<int> = HashSet::new();
1207 let set_str = format!("{:?}", set);
1209 assert!(set_str == "HashSet {1, 2}" || set_str == "HashSet {2, 1}");
1210 assert_eq!(format!("{:?}", empty), "HashSet {}");
1214 fn test_trivial_drain() {
1215 let mut s = HashSet::<int>::new();
1216 for _ in s.drain() {}
1217 assert!(s.is_empty());
1220 let mut s = HashSet::<int>::new();
1222 assert!(s.is_empty());
1227 let mut s: HashSet<i32> = (1..100).collect();
1229 // try this a bunch of times to make sure we don't screw up internal state.
1231 assert_eq!(s.len(), 99);
1235 let mut d = s.drain();
1236 for (i, x) in d.by_ref().take(50).enumerate() {
1240 assert_eq!(last_i, 49);
1243 for _ in &s { panic!("s should be empty!"); }
1245 // reset to try again.