+#[cfg(test)]
+mod tests;
+
+use hashbrown::hash_set as base;
+
use crate::borrow::Borrow;
use crate::collections::TryReserveError;
use crate::fmt;
use crate::iter::{Chain, FromIterator, FusedIterator};
use crate::ops::{BitAnd, BitOr, BitXor, Sub};
-use super::map::{self, HashMap, Keys, RandomState};
+use super::map::{map_try_reserve_error, RandomState};
// Future Optimization (FIXME!)
// ============================
/// // use the values stored in the set
/// ```
///
+/// [`HashMap`]: crate::collections::HashMap
/// [`RefCell`]: crate::cell::RefCell
/// [`Cell`]: crate::cell::Cell
#[derive(Clone)]
#[cfg_attr(not(test), rustc_diagnostic_item = "hashset_type")]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct HashSet<T, S = RandomState> {
- map: HashMap<T, (), S>,
+ base: base::HashSet<T, S>,
}
impl<T> HashSet<T, RandomState> {
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn new() -> HashSet<T, RandomState> {
- HashSet { map: HashMap::new() }
+ Default::default()
}
/// Creates an empty `HashSet` with the specified capacity.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> {
- HashSet { map: HashMap::with_capacity(capacity) }
+ HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, Default::default()) }
}
}
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn capacity(&self) -> usize {
- self.map.capacity()
+ self.base.capacity()
}
/// An iterator visiting all elements in arbitrary order.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn iter(&self) -> Iter<'_, T> {
- Iter { iter: self.map.keys() }
+ Iter { base: self.base.iter() }
}
/// Returns the number of elements in the set.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn len(&self) -> usize {
- self.map.len()
+ self.base.len()
}
/// Returns `true` if the set contains no elements.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn is_empty(&self) -> bool {
- self.map.is_empty()
+ self.base.is_empty()
}
/// Clears the set, returning all elements in an iterator.
#[inline]
#[stable(feature = "drain", since = "1.6.0")]
pub fn drain(&mut self) -> Drain<'_, T> {
- Drain { iter: self.map.drain() }
+ Drain { base: self.base.drain() }
+ }
+
+ /// Creates an iterator which uses a closure to determine if a value should be removed.
+ ///
+ /// If the closure returns true, then the value is removed and yielded.
+ /// If the closure returns false, the value will remain in the list and will not be yielded
+ /// by the iterator.
+ ///
+ /// If the iterator is only partially consumed or not consumed at all, each of the remaining
+ /// values will still be subjected to the closure and removed and dropped if it returns true.
+ ///
+ /// It is unspecified how many more values will be subjected to the closure
+ /// if a panic occurs in the closure, or if a panic occurs while dropping a value, or if the
+ /// `DrainFilter` itself is leaked.
+ ///
+ /// # Examples
+ ///
+ /// Splitting a set into even and odd values, reusing the original set:
+ ///
+ /// ```
+ /// #![feature(hash_drain_filter)]
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set: HashSet<i32> = (0..8).collect();
+ /// let drained: HashSet<i32> = set.drain_filter(|v| v % 2 == 0).collect();
+ ///
+ /// let mut evens = drained.into_iter().collect::<Vec<_>>();
+ /// let mut odds = set.into_iter().collect::<Vec<_>>();
+ /// evens.sort();
+ /// odds.sort();
+ ///
+ /// assert_eq!(evens, vec![0, 2, 4, 6]);
+ /// assert_eq!(odds, vec![1, 3, 5, 7]);
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_drain_filter", issue = "59618")]
+ pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>
+ where
+ F: FnMut(&T) -> bool,
+ {
+ DrainFilter { base: self.base.drain_filter(pred) }
}
/// Clears the set, removing all values.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn clear(&mut self) {
- self.map.clear()
+ self.base.clear()
}
/// Creates a new empty hash set which will use the given hasher to hash
#[inline]
#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
pub fn with_hasher(hasher: S) -> HashSet<T, S> {
- HashSet { map: HashMap::with_hasher(hasher) }
+ HashSet { base: base::HashSet::with_hasher(hasher) }
}
/// Creates an empty `HashSet` with the specified capacity, using
#[inline]
#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashSet<T, S> {
- HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
+ HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, hasher) }
}
/// Returns a reference to the set's [`BuildHasher`].
#[inline]
#[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
pub fn hasher(&self) -> &S {
- self.map.hasher()
+ self.base.hasher()
}
}
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn reserve(&mut self, additional: usize) {
- self.map.reserve(additional)
+ self.base.reserve(additional)
}
/// Tries to reserve capacity for at least `additional` more elements to be inserted
#[inline]
#[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
- self.map.try_reserve(additional)
+ self.base.try_reserve(additional).map_err(map_try_reserve_error)
}
/// Shrinks the capacity of the set as much as possible. It will drop
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn shrink_to_fit(&mut self) {
- self.map.shrink_to_fit()
+ self.base.shrink_to_fit()
}
/// Shrinks the capacity of the set with a lower limit. It will drop
#[inline]
#[unstable(feature = "shrink_to", reason = "new API", issue = "56431")]
pub fn shrink_to(&mut self, min_capacity: usize) {
- self.map.shrink_to(min_capacity)
+ self.base.shrink_to(min_capacity)
}
/// Visits the values representing the difference,
T: Borrow<Q>,
Q: Hash + Eq,
{
- self.map.contains_key(value)
+ self.base.contains(value)
}
/// Returns a reference to the value in the set, if any, that is equal to the given value.
T: Borrow<Q>,
Q: Hash + Eq,
{
- self.map.get_key_value(value).map(|(k, _)| k)
+ self.base.get(value)
}
/// Inserts the given `value` into the set if it is not present, then
pub fn get_or_insert(&mut self, value: T) -> &T {
// Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
// `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
- self.map.raw_entry_mut().from_key(&value).or_insert(value, ()).0
+ self.base.get_or_insert(value)
}
/// Inserts an owned copy of the given `value` into the set if it is not
{
// Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
// `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
- self.map.raw_entry_mut().from_key(value).or_insert_with(|| (value.to_owned(), ())).0
+ self.base.get_or_insert_owned(value)
}
/// Inserts a value computed from `f` into the set if the given `value` is
{
// Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
// `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
- self.map.raw_entry_mut().from_key(value).or_insert_with(|| (f(value), ())).0
+ self.base.get_or_insert_with(value, f)
}
/// Returns `true` if `self` has no elements in common with `other`.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn insert(&mut self, value: T) -> bool {
- self.map.insert(value, ()).is_none()
+ self.base.insert(value)
}
/// Adds a value to the set, replacing the existing value, if any, that is equal to the given
#[inline]
#[stable(feature = "set_recovery", since = "1.9.0")]
pub fn replace(&mut self, value: T) -> Option<T> {
- match self.map.entry(value) {
- map::Entry::Occupied(occupied) => Some(occupied.replace_key()),
- map::Entry::Vacant(vacant) => {
- vacant.insert(());
- None
- }
- }
+ self.base.replace(value)
}
/// Removes a value from the set. Returns whether the value was
T: Borrow<Q>,
Q: Hash + Eq,
{
- self.map.remove(value).is_some()
+ self.base.remove(value)
}
/// Removes and returns the value in the set, if any, that is equal to the given one.
T: Borrow<Q>,
Q: Hash + Eq,
{
- self.map.remove_entry(value).map(|(k, _)| k)
+ self.base.take(value)
}
/// Retains only the elements specified by the predicate.
/// assert_eq!(set.len(), 3);
/// ```
#[stable(feature = "retain_hash_collection", since = "1.18.0")]
- pub fn retain<F>(&mut self, mut f: F)
+ pub fn retain<F>(&mut self, f: F)
where
F: FnMut(&T) -> bool,
{
- self.map.retain(|k, _| f(k));
+ self.base.retain(f)
}
}
{
#[inline]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
- self.map.extend(iter.into_iter().map(|k| (k, ())));
+ self.base.extend(iter);
}
#[inline]
fn extend_one(&mut self, item: T) {
- self.map.insert(item, ());
+ self.base.insert(item);
}
#[inline]
fn extend_reserve(&mut self, additional: usize) {
- self.map.extend_reserve(additional);
+ self.base.extend_reserve(additional);
}
}
#[inline]
fn extend_one(&mut self, &item: &'a T) {
- self.map.insert(item, ());
+ self.base.insert(item);
}
#[inline]
/// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
#[inline]
fn default() -> HashSet<T, S> {
- HashSet { map: HashMap::default() }
+ HashSet { base: Default::default() }
}
}
/// See its documentation for more.
///
/// [`iter`]: HashSet::iter
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+///
+/// let mut iter = a.iter();
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Iter<'a, K: 'a> {
- iter: Keys<'a, K, ()>,
+ base: base::Iter<'a, K>,
}
/// An owning iterator over the items of a `HashSet`.
/// (provided by the `IntoIterator` trait). See its documentation for more.
///
/// [`into_iter`]: IntoIterator::into_iter
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+///
+/// let mut iter = a.into_iter();
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<K> {
- iter: map::IntoIter<K, ()>,
+ base: base::IntoIter<K>,
}
/// A draining iterator over the items of a `HashSet`.
/// See its documentation for more.
///
/// [`drain`]: HashSet::drain
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let mut a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+///
+/// let mut drain = a.drain();
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Drain<'a, K: 'a> {
- iter: map::Drain<'a, K, ()>,
+ base: base::Drain<'a, K>,
+}
+
+/// A draining, filtering iterator over the items of a `HashSet`.
+///
+/// This `struct` is created by the [`drain_filter`] method on [`HashSet`].
+///
+/// [`drain_filter`]: HashSet::drain_filter
+///
+/// # Examples
+///
+/// ```
+/// #![feature(hash_drain_filter)]
+///
+/// use std::collections::HashSet;
+///
+/// let mut a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+///
+/// let mut drain_filtered = a.drain_filter(|v| v % 2 == 0);
+/// ```
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+pub struct DrainFilter<'a, K, F>
+where
+ F: FnMut(&K) -> bool,
+{
+ base: base::DrainFilter<'a, K, F>,
}
/// A lazy iterator producing elements in the intersection of `HashSet`s.
/// See its documentation for more.
///
/// [`intersection`]: HashSet::intersection
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+/// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
+///
+/// let mut intersection = a.intersection(&b);
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Intersection<'a, T: 'a, S: 'a> {
// iterator of the first set
/// See its documentation for more.
///
/// [`difference`]: HashSet::difference
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+/// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
+///
+/// let mut difference = a.difference(&b);
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Difference<'a, T: 'a, S: 'a> {
// iterator of the first set
/// [`HashSet`]. See its documentation for more.
///
/// [`symmetric_difference`]: HashSet::symmetric_difference
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+/// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
+///
+/// let mut intersection = a.symmetric_difference(&b);
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
/// See its documentation for more.
///
/// [`union`]: HashSet::union
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
+/// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
+///
+/// let mut union_iter = a.union(&b);
+/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Union<'a, T: 'a, S: 'a> {
iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
/// ```
#[inline]
fn into_iter(self) -> IntoIter<T> {
- IntoIter { iter: self.map.into_iter() }
+ IntoIter { base: self.base.into_iter() }
}
}
impl<K> Clone for Iter<'_, K> {
#[inline]
fn clone(&self) -> Self {
- Iter { iter: self.iter.clone() }
+ Iter { base: self.base.clone() }
}
}
#[stable(feature = "rust1", since = "1.0.0")]
#[inline]
fn next(&mut self) -> Option<&'a K> {
- self.iter.next()
+ self.base.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
+ self.base.size_hint()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K> ExactSizeIterator for Iter<'_, K> {
#[inline]
fn len(&self) -> usize {
- self.iter.len()
+ self.base.len()
}
}
#[stable(feature = "fused", since = "1.26.0")]
#[inline]
fn next(&mut self) -> Option<K> {
- self.iter.next().map(|(k, _)| k)
+ self.base.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
+ self.base.size_hint()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K> ExactSizeIterator for IntoIter<K> {
#[inline]
fn len(&self) -> usize {
- self.iter.len()
+ self.base.len()
}
}
#[stable(feature = "fused", since = "1.26.0")]
#[stable(feature = "std_debug", since = "1.16.0")]
impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- let entries_iter = self.iter.iter().map(|(k, _)| k);
- f.debug_list().entries(entries_iter).finish()
+ fmt::Debug::fmt(&self.base, f)
}
}
#[inline]
fn next(&mut self) -> Option<K> {
- self.iter.next().map(|(k, _)| k)
+ self.base.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
+ self.base.size_hint()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K> ExactSizeIterator for Drain<'_, K> {
#[inline]
fn len(&self) -> usize {
- self.iter.len()
+ self.base.len()
}
}
#[stable(feature = "fused", since = "1.26.0")]
#[stable(feature = "std_debug", since = "1.16.0")]
impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- let entries_iter = self.iter.iter().map(|(k, _)| k);
- f.debug_list().entries(entries_iter).finish()
+ fmt::Debug::fmt(&self.base, f)
+ }
+}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<K, F> Iterator for DrainFilter<'_, K, F>
+where
+ F: FnMut(&K) -> bool,
+{
+ type Item = K;
+
+ #[inline]
+ fn next(&mut self) -> Option<K> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<K, F> FusedIterator for DrainFilter<'_, K, F> where F: FnMut(&K) -> bool {}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<'a, K, F> fmt::Debug for DrainFilter<'a, K, F>
+where
+ F: FnMut(&K) -> bool,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.pad("DrainFilter { .. }")
}
}
d
}
}
-
-#[cfg(test)]
-mod test_set {
- use super::super::map::RandomState;
- use super::HashSet;
-
- #[test]
- fn test_zero_capacities() {
- type HS = HashSet<i32>;
-
- let s = HS::new();
- assert_eq!(s.capacity(), 0);
-
- let s = HS::default();
- assert_eq!(s.capacity(), 0);
-
- let s = HS::with_hasher(RandomState::new());
- assert_eq!(s.capacity(), 0);
-
- let s = HS::with_capacity(0);
- assert_eq!(s.capacity(), 0);
-
- let s = HS::with_capacity_and_hasher(0, RandomState::new());
- assert_eq!(s.capacity(), 0);
-
- let mut s = HS::new();
- s.insert(1);
- s.insert(2);
- s.remove(&1);
- s.remove(&2);
- s.shrink_to_fit();
- assert_eq!(s.capacity(), 0);
-
- let mut s = HS::new();
- s.reserve(0);
- assert_eq!(s.capacity(), 0);
- }
-
- #[test]
- fn test_disjoint() {
- let mut xs = HashSet::new();
- let mut ys = HashSet::new();
- assert!(xs.is_disjoint(&ys));
- assert!(ys.is_disjoint(&xs));
- assert!(xs.insert(5));
- assert!(ys.insert(11));
- assert!(xs.is_disjoint(&ys));
- assert!(ys.is_disjoint(&xs));
- assert!(xs.insert(7));
- assert!(xs.insert(19));
- assert!(xs.insert(4));
- assert!(ys.insert(2));
- assert!(ys.insert(-11));
- assert!(xs.is_disjoint(&ys));
- assert!(ys.is_disjoint(&xs));
- assert!(ys.insert(7));
- assert!(!xs.is_disjoint(&ys));
- assert!(!ys.is_disjoint(&xs));
- }
-
- #[test]
- fn test_subset_and_superset() {
- let mut a = HashSet::new();
- assert!(a.insert(0));
- assert!(a.insert(5));
- assert!(a.insert(11));
- assert!(a.insert(7));
-
- let mut b = HashSet::new();
- assert!(b.insert(0));
- assert!(b.insert(7));
- assert!(b.insert(19));
- assert!(b.insert(250));
- assert!(b.insert(11));
- assert!(b.insert(200));
-
- assert!(!a.is_subset(&b));
- assert!(!a.is_superset(&b));
- assert!(!b.is_subset(&a));
- assert!(!b.is_superset(&a));
-
- assert!(b.insert(5));
-
- assert!(a.is_subset(&b));
- assert!(!a.is_superset(&b));
- assert!(!b.is_subset(&a));
- assert!(b.is_superset(&a));
- }
-
- #[test]
- fn test_iterate() {
- let mut a = HashSet::new();
- for i in 0..32 {
- assert!(a.insert(i));
- }
- let mut observed: u32 = 0;
- for k in &a {
- observed |= 1 << *k;
- }
- assert_eq!(observed, 0xFFFF_FFFF);
- }
-
- #[test]
- fn test_intersection() {
- let mut a = HashSet::new();
- let mut b = HashSet::new();
- assert!(a.intersection(&b).next().is_none());
-
- assert!(a.insert(11));
- assert!(a.insert(1));
- assert!(a.insert(3));
- assert!(a.insert(77));
- assert!(a.insert(103));
- assert!(a.insert(5));
- assert!(a.insert(-5));
-
- assert!(b.insert(2));
- assert!(b.insert(11));
- assert!(b.insert(77));
- assert!(b.insert(-9));
- assert!(b.insert(-42));
- assert!(b.insert(5));
- assert!(b.insert(3));
-
- let mut i = 0;
- let expected = [3, 5, 11, 77];
- for x in a.intersection(&b) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
-
- assert!(a.insert(9)); // make a bigger than b
-
- i = 0;
- for x in a.intersection(&b) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
-
- i = 0;
- for x in b.intersection(&a) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
- }
-
- #[test]
- fn test_difference() {
- let mut a = HashSet::new();
- let mut b = HashSet::new();
-
- assert!(a.insert(1));
- assert!(a.insert(3));
- assert!(a.insert(5));
- assert!(a.insert(9));
- assert!(a.insert(11));
-
- assert!(b.insert(3));
- assert!(b.insert(9));
-
- let mut i = 0;
- let expected = [1, 5, 11];
- for x in a.difference(&b) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
- }
-
- #[test]
- fn test_symmetric_difference() {
- let mut a = HashSet::new();
- let mut b = HashSet::new();
-
- assert!(a.insert(1));
- assert!(a.insert(3));
- assert!(a.insert(5));
- assert!(a.insert(9));
- assert!(a.insert(11));
-
- assert!(b.insert(-2));
- assert!(b.insert(3));
- assert!(b.insert(9));
- assert!(b.insert(14));
- assert!(b.insert(22));
-
- let mut i = 0;
- let expected = [-2, 1, 5, 11, 14, 22];
- for x in a.symmetric_difference(&b) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
- }
-
- #[test]
- fn test_union() {
- let mut a = HashSet::new();
- let mut b = HashSet::new();
- assert!(a.union(&b).next().is_none());
- assert!(b.union(&a).next().is_none());
-
- assert!(a.insert(1));
- assert!(a.insert(3));
- assert!(a.insert(11));
- assert!(a.insert(16));
- assert!(a.insert(19));
- assert!(a.insert(24));
-
- assert!(b.insert(-2));
- assert!(b.insert(1));
- assert!(b.insert(5));
- assert!(b.insert(9));
- assert!(b.insert(13));
- assert!(b.insert(19));
-
- let mut i = 0;
- let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
- for x in a.union(&b) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
-
- assert!(a.insert(9)); // make a bigger than b
- assert!(a.insert(5));
-
- i = 0;
- for x in a.union(&b) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
-
- i = 0;
- for x in b.union(&a) {
- assert!(expected.contains(x));
- i += 1
- }
- assert_eq!(i, expected.len());
- }
-
- #[test]
- fn test_from_iter() {
- let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
-
- let set: HashSet<_> = xs.iter().cloned().collect();
-
- for x in &xs {
- assert!(set.contains(x));
- }
-
- assert_eq!(set.iter().len(), xs.len() - 1);
- }
-
- #[test]
- fn test_move_iter() {
- let hs = {
- let mut hs = HashSet::new();
-
- hs.insert('a');
- hs.insert('b');
-
- hs
- };
-
- let v = hs.into_iter().collect::<Vec<char>>();
- assert!(v == ['a', 'b'] || v == ['b', 'a']);
- }
-
- #[test]
- fn test_eq() {
- // These constants once happened to expose a bug in insert().
- // I'm keeping them around to prevent a regression.
- let mut s1 = HashSet::new();
-
- s1.insert(1);
- s1.insert(2);
- s1.insert(3);
-
- let mut s2 = HashSet::new();
-
- s2.insert(1);
- s2.insert(2);
-
- assert!(s1 != s2);
-
- s2.insert(3);
-
- assert_eq!(s1, s2);
- }
-
- #[test]
- fn test_show() {
- let mut set = HashSet::new();
- let empty = HashSet::<i32>::new();
-
- set.insert(1);
- set.insert(2);
-
- let set_str = format!("{:?}", set);
-
- assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
- assert_eq!(format!("{:?}", empty), "{}");
- }
-
- #[test]
- fn test_trivial_drain() {
- let mut s = HashSet::<i32>::new();
- for _ in s.drain() {}
- assert!(s.is_empty());
- drop(s);
-
- let mut s = HashSet::<i32>::new();
- drop(s.drain());
- assert!(s.is_empty());
- }
-
- #[test]
- fn test_drain() {
- let mut s: HashSet<_> = (1..100).collect();
-
- // try this a bunch of times to make sure we don't screw up internal state.
- for _ in 0..20 {
- assert_eq!(s.len(), 99);
-
- {
- let mut last_i = 0;
- let mut d = s.drain();
- for (i, x) in d.by_ref().take(50).enumerate() {
- last_i = i;
- assert!(x != 0);
- }
- assert_eq!(last_i, 49);
- }
-
- for _ in &s {
- panic!("s should be empty!");
- }
-
- // reset to try again.
- s.extend(1..100);
- }
- }
-
- #[test]
- fn test_replace() {
- use crate::hash;
-
- #[derive(Debug)]
- struct Foo(&'static str, i32);
-
- impl PartialEq for Foo {
- fn eq(&self, other: &Self) -> bool {
- self.0 == other.0
- }
- }
-
- impl Eq for Foo {}
-
- impl hash::Hash for Foo {
- fn hash<H: hash::Hasher>(&self, h: &mut H) {
- self.0.hash(h);
- }
- }
-
- let mut s = HashSet::new();
- assert_eq!(s.replace(Foo("a", 1)), None);
- assert_eq!(s.len(), 1);
- assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
- assert_eq!(s.len(), 1);
-
- let mut it = s.iter();
- assert_eq!(it.next(), Some(&Foo("a", 2)));
- assert_eq!(it.next(), None);
- }
-
- #[test]
- fn test_extend_ref() {
- let mut a = HashSet::new();
- a.insert(1);
-
- a.extend(&[2, 3, 4]);
-
- assert_eq!(a.len(), 4);
- assert!(a.contains(&1));
- assert!(a.contains(&2));
- assert!(a.contains(&3));
- assert!(a.contains(&4));
-
- let mut b = HashSet::new();
- b.insert(5);
- b.insert(6);
-
- a.extend(&b);
-
- assert_eq!(a.len(), 6);
- assert!(a.contains(&1));
- assert!(a.contains(&2));
- assert!(a.contains(&3));
- assert!(a.contains(&4));
- assert!(a.contains(&5));
- assert!(a.contains(&6));
- }
-
- #[test]
- fn test_retain() {
- let xs = [1, 2, 3, 4, 5, 6];
- let mut set: HashSet<i32> = xs.iter().cloned().collect();
- set.retain(|&k| k % 2 == 0);
- assert_eq!(set.len(), 3);
- assert!(set.contains(&2));
- assert!(set.contains(&4));
- assert!(set.contains(&6));
- }
-}
projects / rustc.git / blobdiff