diff options
Diffstat (limited to 'vendor/im-rc/src/hash/set.rs')
| -rw-r--r-- | vendor/im-rc/src/hash/set.rs | 1134 |
1 files changed, 1134 insertions, 0 deletions
diff --git a/vendor/im-rc/src/hash/set.rs b/vendor/im-rc/src/hash/set.rs new file mode 100644 index 000000000..edc4ad60c --- /dev/null +++ b/vendor/im-rc/src/hash/set.rs @@ -0,0 +1,1134 @@ +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. + +//! An unordered set. +//! +//! An immutable hash set using [hash array mapped tries] [1]. +//! +//! Most operations on this set are O(log<sub>x</sub> n) for a +//! suitably high *x* that it should be nearly O(1) for most sets. +//! Because of this, it's a great choice for a generic set as long as +//! you don't mind that values will need to implement +//! [`Hash`][std::hash::Hash] and [`Eq`][std::cmp::Eq]. +//! +//! Values will have a predictable order based on the hasher +//! being used. Unless otherwise specified, this will be the standard +//! [`RandomState`][std::collections::hash_map::RandomState] hasher. +//! +//! [1]: https://en.wikipedia.org/wiki/Hash_array_mapped_trie +//! [std::cmp::Eq]: https://doc.rust-lang.org/std/cmp/trait.Eq.html +//! [std::hash::Hash]: https://doc.rust-lang.org/std/hash/trait.Hash.html +//! [std::collections::hash_map::RandomState]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + +use std::borrow::Borrow; +use std::cmp::Ordering; +use std::collections::hash_map::RandomState; +use std::collections::{self, BTreeSet}; +use std::fmt::{Debug, Error, Formatter}; +use std::hash::{BuildHasher, Hash, Hasher}; +use std::iter::FusedIterator; +use std::iter::{FromIterator, IntoIterator, Sum}; +use std::ops::{Add, Deref, Mul}; + +use crate::nodes::hamt::{hash_key, Drain as NodeDrain, HashValue, Iter as NodeIter, Node}; +use crate::ordset::OrdSet; +use crate::util::{Pool, PoolRef, Ref}; +use crate::Vector; + +/// Construct a set from a sequence of values. +/// +/// # Examples +/// +/// ``` +/// # #[macro_use] extern crate im_rc as im; +/// # use im::hashset::HashSet; +/// # fn main() { +/// assert_eq!( +/// hashset![1, 2, 3], +/// HashSet::from(vec![1, 2, 3]) +/// ); +/// # } +/// ``` +#[macro_export] +macro_rules! hashset { + () => { $crate::hashset::HashSet::new() }; + + ( $($x:expr),* ) => {{ + let mut l = $crate::hashset::HashSet::new(); + $( + l.insert($x); + )* + l + }}; + + ( $($x:expr ,)* ) => {{ + let mut l = $crate::hashset::HashSet::new(); + $( + l.insert($x); + )* + l + }}; +} + +def_pool!(HashSetPool<A>, Node<Value<A>>); + +/// An unordered set. +/// +/// An immutable hash set using [hash array mapped tries] [1]. +/// +/// Most operations on this set are O(log<sub>x</sub> n) for a +/// suitably high *x* that it should be nearly O(1) for most sets. +/// Because of this, it's a great choice for a generic set as long as +/// you don't mind that values will need to implement +/// [`Hash`][std::hash::Hash] and [`Eq`][std::cmp::Eq]. +/// +/// Values will have a predictable order based on the hasher +/// being used. Unless otherwise specified, this will be the standard +/// [`RandomState`][std::collections::hash_map::RandomState] hasher. +/// +/// [1]: https://en.wikipedia.org/wiki/Hash_array_mapped_trie +/// [std::cmp::Eq]: https://doc.rust-lang.org/std/cmp/trait.Eq.html +/// [std::hash::Hash]: https://doc.rust-lang.org/std/hash/trait.Hash.html +/// [std::collections::hash_map::RandomState]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html +pub struct HashSet<A, S = RandomState> { + hasher: Ref<S>, + pool: HashSetPool<A>, + root: PoolRef<Node<Value<A>>>, + size: usize, +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)] +struct Value<A>(A); + +impl<A> Deref for Value<A> { + type Target = A; + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +// FIXME lacking specialisation, we can't simply implement `HashValue` +// for `A`, we have to use the `Value<A>` indirection. +impl<A> HashValue for Value<A> +where + A: Hash + Eq, +{ + type Key = A; + + fn extract_key(&self) -> &Self::Key { + &self.0 + } + + fn ptr_eq(&self, _other: &Self) -> bool { + false + } +} + +impl<A> HashSet<A, RandomState> { + /// Construct an empty set. + #[must_use] + pub fn new() -> Self { + Self::default() + } + + /// Construct an empty set using a specific memory pool. + #[cfg(feature = "pool")] + #[must_use] + pub fn with_pool(pool: &HashSetPool<A>) -> Self { + Self { + pool: pool.clone(), + hasher: Default::default(), + size: 0, + root: PoolRef::default(&pool.0), + } + } +} + +impl<A> HashSet<A, RandomState> +where + A: Hash + Eq + Clone, +{ + /// Construct a set with a single value. + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// # use std::sync::Arc; + /// let set = HashSet::unit(123); + /// assert!(set.contains(&123)); + /// ``` + #[inline] + #[must_use] + pub fn unit(a: A) -> Self { + HashSet::new().update(a) + } +} + +impl<A, S> HashSet<A, S> { + /// Test whether a set is empty. + /// + /// Time: O(1) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// assert!( + /// !hashset![1, 2, 3].is_empty() + /// ); + /// assert!( + /// HashSet::<i32>::new().is_empty() + /// ); + /// ``` + #[inline] + #[must_use] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Get the size of a set. + /// + /// Time: O(1) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// assert_eq!(3, hashset![1, 2, 3].len()); + /// ``` + #[inline] + #[must_use] + pub fn len(&self) -> usize { + self.size + } + + /// Test whether two sets refer to the same content in memory. + /// + /// This is true if the two sides are references to the same set, + /// or if the two sets refer to the same root node. + /// + /// This would return true if you're comparing a set to itself, or + /// if you're comparing a set to a fresh clone of itself. + /// + /// Time: O(1) + pub fn ptr_eq(&self, other: &Self) -> bool { + std::ptr::eq(self, other) || PoolRef::ptr_eq(&self.root, &other.root) + } + + /// Get a reference to the memory pool used by this set. + /// + /// Note that if you didn't specifically construct it with a pool, you'll + /// get back a reference to a pool of size 0. + #[cfg(feature = "pool")] + pub fn pool(&self) -> &HashSetPool<A> { + &self.pool + } + + /// Construct an empty hash set using the provided hasher. + #[inline] + #[must_use] + pub fn with_hasher<RS>(hasher: RS) -> Self + where + Ref<S>: From<RS>, + { + let pool = HashSetPool::default(); + let root = PoolRef::default(&pool.0); + HashSet { + size: 0, + pool, + root, + hasher: From::from(hasher), + } + } + + /// Construct an empty hash set using the provided memory pool and hasher. + #[cfg(feature = "pool")] + #[inline] + #[must_use] + pub fn with_pool_hasher<RS>(pool: &HashSetPool<A>, hasher: RS) -> Self + where + Ref<S>: From<RS>, + { + let root = PoolRef::default(&pool.0); + HashSet { + size: 0, + pool: pool.clone(), + root, + hasher: From::from(hasher), + } + } + + /// Get a reference to the set's [`BuildHasher`][BuildHasher]. + /// + /// [BuildHasher]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html + #[must_use] + pub fn hasher(&self) -> &Ref<S> { + &self.hasher + } + + /// Construct an empty hash set using the same hasher as the current hash set. + #[inline] + #[must_use] + pub fn new_from<A1>(&self) -> HashSet<A1, S> + where + A1: Hash + Eq + Clone, + { + let pool = HashSetPool::default(); + let root = PoolRef::default(&pool.0); + HashSet { + size: 0, + pool, + root, + hasher: self.hasher.clone(), + } + } + + /// Discard all elements from the set. + /// + /// This leaves you with an empty set, and all elements that + /// were previously inside it are dropped. + /// + /// Time: O(n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::HashSet; + /// let mut set = hashset![1, 2, 3]; + /// set.clear(); + /// assert!(set.is_empty()); + /// ``` + pub fn clear(&mut self) { + if !self.is_empty() { + self.root = PoolRef::default(&self.pool.0); + self.size = 0; + } + } + + /// Get an iterator over the values in a hash set. + /// + /// Please note that the order is consistent between sets using + /// the same hasher, but no other ordering guarantee is offered. + /// Items will not come out in insertion order or sort order. + /// They will, however, come out in the same order every time for + /// the same set. + #[must_use] + pub fn iter(&self) -> Iter<'_, A> { + Iter { + it: NodeIter::new(&self.root, self.size), + } + } +} + +impl<A, S> HashSet<A, S> +where + A: Hash + Eq, + S: BuildHasher, +{ + fn test_eq(&self, other: &Self) -> bool { + if self.len() != other.len() { + return false; + } + let mut seen = collections::HashSet::new(); + for value in self.iter() { + if !other.contains(value) { + return false; + } + seen.insert(value); + } + for value in other.iter() { + if !seen.contains(&value) { + return false; + } + } + true + } + + /// Test if a value is part of a set. + /// + /// Time: O(log n) + #[must_use] + pub fn contains<BA>(&self, a: &BA) -> bool + where + BA: Hash + Eq + ?Sized, + A: Borrow<BA>, + { + self.root.get(hash_key(&*self.hasher, a), 0, a).is_some() + } + + /// Test whether a set is a subset of another set, meaning that + /// all values in our set must also be in the other set. + /// + /// Time: O(n log n) + #[must_use] + pub fn is_subset<RS>(&self, other: RS) -> bool + where + RS: Borrow<Self>, + { + let o = other.borrow(); + self.iter().all(|a| o.contains(a)) + } + + /// Test whether a set is a proper subset of another set, meaning + /// that all values in our set must also be in the other set. A + /// proper subset must also be smaller than the other set. + /// + /// Time: O(n log n) + #[must_use] + pub fn is_proper_subset<RS>(&self, other: RS) -> bool + where + RS: Borrow<Self>, + { + self.len() != other.borrow().len() && self.is_subset(other) + } +} + +impl<A, S> HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher, +{ + /// Insert a value into a set. + /// + /// Time: O(log n) + #[inline] + pub fn insert(&mut self, a: A) -> Option<A> { + let hash = hash_key(&*self.hasher, &a); + let root = PoolRef::make_mut(&self.pool.0, &mut self.root); + match root.insert(&self.pool.0, hash, 0, Value(a)) { + None => { + self.size += 1; + None + } + Some(Value(old_value)) => Some(old_value), + } + } + + /// Remove a value from a set if it exists. + /// + /// Time: O(log n) + pub fn remove<BA>(&mut self, a: &BA) -> Option<A> + where + BA: Hash + Eq + ?Sized, + A: Borrow<BA>, + { + let root = PoolRef::make_mut(&self.pool.0, &mut self.root); + let result = root.remove(&self.pool.0, hash_key(&*self.hasher, a), 0, a); + if result.is_some() { + self.size -= 1; + } + result.map(|v| v.0) + } + + /// Construct a new set from the current set with the given value + /// added. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// # use std::sync::Arc; + /// let set = hashset![123]; + /// assert_eq!( + /// set.update(456), + /// hashset![123, 456] + /// ); + /// ``` + #[must_use] + pub fn update(&self, a: A) -> Self { + let mut out = self.clone(); + out.insert(a); + out + } + + /// Construct a new set with the given value removed if it's in + /// the set. + /// + /// Time: O(log n) + #[must_use] + pub fn without<BA>(&self, a: &BA) -> Self + where + BA: Hash + Eq + ?Sized, + A: Borrow<BA>, + { + let mut out = self.clone(); + out.remove(a); + out + } + + /// Filter out values from a set which don't satisfy a predicate. + /// + /// This is slightly more efficient than filtering using an + /// iterator, in that it doesn't need to rehash the retained + /// values, but it still needs to reconstruct the entire tree + /// structure of the set. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::HashSet; + /// let mut set = hashset![1, 2, 3]; + /// set.retain(|v| *v > 1); + /// let expected = hashset![2, 3]; + /// assert_eq!(expected, set); + /// ``` + pub fn retain<F>(&mut self, mut f: F) + where + F: FnMut(&A) -> bool, + { + let old_root = self.root.clone(); + let root = PoolRef::make_mut(&self.pool.0, &mut self.root); + for (value, hash) in NodeIter::new(&old_root, self.size) { + if !f(value) && root.remove(&self.pool.0, hash, 0, value).is_some() { + self.size -= 1; + } + } + } + + /// Construct the union of two sets. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// let set1 = hashset!{1, 2}; + /// let set2 = hashset!{2, 3}; + /// let expected = hashset!{1, 2, 3}; + /// assert_eq!(expected, set1.union(set2)); + /// ``` + #[must_use] + pub fn union(self, other: Self) -> Self { + let (mut to_mutate, to_consume) = if self.len() >= other.len() { + (self, other) + } else { + (other, self) + }; + for value in to_consume { + to_mutate.insert(value); + } + to_mutate + } + + /// Construct the union of multiple sets. + /// + /// Time: O(n log n) + #[must_use] + pub fn unions<I>(i: I) -> Self + where + I: IntoIterator<Item = Self>, + S: Default, + { + i.into_iter().fold(Self::default(), Self::union) + } + + /// Construct the symmetric difference between two sets. + /// + /// This is an alias for the + /// [`symmetric_difference`][symmetric_difference] method. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// let set1 = hashset!{1, 2}; + /// let set2 = hashset!{2, 3}; + /// let expected = hashset!{1, 3}; + /// assert_eq!(expected, set1.difference(set2)); + /// ``` + /// + /// [symmetric_difference]: #method.symmetric_difference + #[must_use] + pub fn difference(self, other: Self) -> Self { + self.symmetric_difference(other) + } + + /// Construct the symmetric difference between two sets. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// let set1 = hashset!{1, 2}; + /// let set2 = hashset!{2, 3}; + /// let expected = hashset!{1, 3}; + /// assert_eq!(expected, set1.symmetric_difference(set2)); + /// ``` + #[must_use] + pub fn symmetric_difference(mut self, other: Self) -> Self { + for value in other { + if self.remove(&value).is_none() { + self.insert(value); + } + } + self + } + + /// Construct the relative complement between two sets, that is the set + /// of values in `self` that do not occur in `other`. + /// + /// Time: O(m log n) where m is the size of the other set + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::ordset::OrdSet; + /// let set1 = ordset!{1, 2}; + /// let set2 = ordset!{2, 3}; + /// let expected = ordset!{1}; + /// assert_eq!(expected, set1.relative_complement(set2)); + /// ``` + #[must_use] + pub fn relative_complement(mut self, other: Self) -> Self { + for value in other { + let _ = self.remove(&value); + } + self + } + + /// Construct the intersection of two sets. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::hashset::HashSet; + /// let set1 = hashset!{1, 2}; + /// let set2 = hashset!{2, 3}; + /// let expected = hashset!{2}; + /// assert_eq!(expected, set1.intersection(set2)); + /// ``` + #[must_use] + pub fn intersection(self, other: Self) -> Self { + let mut out = self.new_from(); + for value in other { + if self.contains(&value) { + out.insert(value); + } + } + out + } +} + +// Core traits + +impl<A, S> Clone for HashSet<A, S> +where + A: Clone, +{ + /// Clone a set. + /// + /// Time: O(1) + #[inline] + fn clone(&self) -> Self { + HashSet { + hasher: self.hasher.clone(), + pool: self.pool.clone(), + root: self.root.clone(), + size: self.size, + } + } +} + +impl<A, S> PartialEq for HashSet<A, S> +where + A: Hash + Eq, + S: BuildHasher + Default, +{ + fn eq(&self, other: &Self) -> bool { + self.test_eq(other) + } +} + +impl<A, S> Eq for HashSet<A, S> +where + A: Hash + Eq, + S: BuildHasher + Default, +{ +} + +impl<A, S> PartialOrd for HashSet<A, S> +where + A: Hash + Eq + Clone + PartialOrd, + S: BuildHasher + Default, +{ + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + if Ref::ptr_eq(&self.hasher, &other.hasher) { + return self.iter().partial_cmp(other.iter()); + } + self.iter().partial_cmp(other.iter()) + } +} + +impl<A, S> Ord for HashSet<A, S> +where + A: Hash + Eq + Clone + Ord, + S: BuildHasher + Default, +{ + fn cmp(&self, other: &Self) -> Ordering { + if Ref::ptr_eq(&self.hasher, &other.hasher) { + return self.iter().cmp(other.iter()); + } + self.iter().cmp(other.iter()) + } +} + +impl<A, S> Hash for HashSet<A, S> +where + A: Hash + Eq, + S: BuildHasher + Default, +{ + fn hash<H>(&self, state: &mut H) + where + H: Hasher, + { + for i in self.iter() { + i.hash(state); + } + } +} + +impl<A, S> Default for HashSet<A, S> +where + S: BuildHasher + Default, +{ + fn default() -> Self { + let pool = HashSetPool::default(); + let root = PoolRef::default(&pool.0); + HashSet { + hasher: Ref::<S>::default(), + pool, + root, + size: 0, + } + } +} + +impl<A, S> Add for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher, +{ + type Output = HashSet<A, S>; + + fn add(self, other: Self) -> Self::Output { + self.union(other) + } +} + +impl<A, S> Mul for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher, +{ + type Output = HashSet<A, S>; + + fn mul(self, other: Self) -> Self::Output { + self.intersection(other) + } +} + +impl<'a, A, S> Add for &'a HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher, +{ + type Output = HashSet<A, S>; + + fn add(self, other: Self) -> Self::Output { + self.clone().union(other.clone()) + } +} + +impl<'a, A, S> Mul for &'a HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher, +{ + type Output = HashSet<A, S>; + + fn mul(self, other: Self) -> Self::Output { + self.clone().intersection(other.clone()) + } +} + +impl<A, S> Sum for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn sum<I>(it: I) -> Self + where + I: Iterator<Item = Self>, + { + it.fold(Self::default(), |a, b| a + b) + } +} + +impl<A, S, R> Extend<R> for HashSet<A, S> +where + A: Hash + Eq + Clone + From<R>, + S: BuildHasher, +{ + fn extend<I>(&mut self, iter: I) + where + I: IntoIterator<Item = R>, + { + for value in iter { + self.insert(From::from(value)); + } + } +} + +#[cfg(not(has_specialisation))] +impl<A, S> Debug for HashSet<A, S> +where + A: Hash + Eq + Debug, + S: BuildHasher, +{ + fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { + f.debug_set().entries(self.iter()).finish() + } +} + +#[cfg(has_specialisation)] +impl<A, S> Debug for HashSet<A, S> +where + A: Hash + Eq + Debug, + S: BuildHasher, +{ + default fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { + f.debug_set().entries(self.iter()).finish() + } +} + +#[cfg(has_specialisation)] +impl<A, S> Debug for HashSet<A, S> +where + A: Hash + Eq + Debug + Ord, + S: BuildHasher, +{ + fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { + f.debug_set().entries(self.iter()).finish() + } +} + +// Iterators + +/// An iterator over the elements of a set. +pub struct Iter<'a, A> { + it: NodeIter<'a, Value<A>>, +} + +impl<'a, A> Iterator for Iter<'a, A> +where + A: 'a, +{ + type Item = &'a A; + + fn next(&mut self) -> Option<Self::Item> { + self.it.next().map(|(v, _)| &v.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.it.size_hint() + } +} + +impl<'a, A> ExactSizeIterator for Iter<'a, A> {} + +impl<'a, A> FusedIterator for Iter<'a, A> {} + +/// A consuming iterator over the elements of a set. +pub struct ConsumingIter<A> +where + A: Hash + Eq + Clone, +{ + it: NodeDrain<Value<A>>, +} + +impl<A> Iterator for ConsumingIter<A> +where + A: Hash + Eq + Clone, +{ + type Item = A; + + fn next(&mut self) -> Option<Self::Item> { + self.it.next().map(|(v, _)| v.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.it.size_hint() + } +} + +impl<A> ExactSizeIterator for ConsumingIter<A> where A: Hash + Eq + Clone {} + +impl<A> FusedIterator for ConsumingIter<A> where A: Hash + Eq + Clone {} + +// Iterator conversions + +impl<A, RA, S> FromIterator<RA> for HashSet<A, S> +where + A: Hash + Eq + Clone + From<RA>, + S: BuildHasher + Default, +{ + fn from_iter<T>(i: T) -> Self + where + T: IntoIterator<Item = RA>, + { + let mut set = Self::default(); + for value in i { + set.insert(From::from(value)); + } + set + } +} + +impl<'a, A, S> IntoIterator for &'a HashSet<A, S> +where + A: Hash + Eq, + S: BuildHasher, +{ + type Item = &'a A; + type IntoIter = Iter<'a, A>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<A, S> IntoIterator for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher, +{ + type Item = A; + type IntoIter = ConsumingIter<Self::Item>; + + fn into_iter(self) -> Self::IntoIter { + ConsumingIter { + it: NodeDrain::new(&self.pool.0, self.root, self.size), + } + } +} + +// Conversions + +impl<'s, 'a, A, OA, SA, SB> From<&'s HashSet<&'a A, SA>> for HashSet<OA, SB> +where + A: ToOwned<Owned = OA> + Hash + Eq + ?Sized, + OA: Borrow<A> + Hash + Eq + Clone, + SA: BuildHasher, + SB: BuildHasher + Default, +{ + fn from(set: &HashSet<&A, SA>) -> Self { + set.iter().map(|a| (*a).to_owned()).collect() + } +} + +impl<'a, A, S> From<&'a [A]> for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(slice: &'a [A]) -> Self { + slice.iter().cloned().collect() + } +} + +impl<A, S> From<Vec<A>> for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(vec: Vec<A>) -> Self { + vec.into_iter().collect() + } +} + +impl<'a, A, S> From<&'a Vec<A>> for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(vec: &Vec<A>) -> Self { + vec.iter().cloned().collect() + } +} + +impl<A, S> From<Vector<A>> for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(vector: Vector<A>) -> Self { + vector.into_iter().collect() + } +} + +impl<'a, A, S> From<&'a Vector<A>> for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(vector: &Vector<A>) -> Self { + vector.iter().cloned().collect() + } +} + +impl<A, S> From<collections::HashSet<A>> for HashSet<A, S> +where + A: Eq + Hash + Clone, + S: BuildHasher + Default, +{ + fn from(hash_set: collections::HashSet<A>) -> Self { + hash_set.into_iter().collect() + } +} + +impl<'a, A, S> From<&'a collections::HashSet<A>> for HashSet<A, S> +where + A: Eq + Hash + Clone, + S: BuildHasher + Default, +{ + fn from(hash_set: &collections::HashSet<A>) -> Self { + hash_set.iter().cloned().collect() + } +} + +impl<'a, A, S> From<&'a BTreeSet<A>> for HashSet<A, S> +where + A: Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(btree_set: &BTreeSet<A>) -> Self { + btree_set.iter().cloned().collect() + } +} + +impl<A, S> From<OrdSet<A>> for HashSet<A, S> +where + A: Ord + Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(ordset: OrdSet<A>) -> Self { + ordset.into_iter().collect() + } +} + +impl<'a, A, S> From<&'a OrdSet<A>> for HashSet<A, S> +where + A: Ord + Hash + Eq + Clone, + S: BuildHasher + Default, +{ + fn from(ordset: &OrdSet<A>) -> Self { + ordset.into_iter().cloned().collect() + } +} + +// Proptest +#[cfg(any(test, feature = "proptest"))] +#[doc(hidden)] +pub mod proptest { + #[deprecated( + since = "14.3.0", + note = "proptest strategies have moved to im::proptest" + )] + pub use crate::proptest::hash_set; +} + +#[cfg(test)] +mod test { + use super::proptest::*; + use super::*; + use crate::test::LolHasher; + use ::proptest::num::i16; + use ::proptest::proptest; + use std::hash::BuildHasherDefault; + + #[test] + fn insert_failing() { + let mut set: HashSet<i16, BuildHasherDefault<LolHasher>> = Default::default(); + set.insert(14658); + assert_eq!(1, set.len()); + set.insert(-19198); + assert_eq!(2, set.len()); + } + + #[test] + fn match_strings_with_string_slices() { + let mut set: HashSet<String> = From::from(&hashset!["foo", "bar"]); + set = set.without("bar"); + assert!(!set.contains("bar")); + set.remove("foo"); + assert!(!set.contains("foo")); + } + + #[test] + fn macro_allows_trailing_comma() { + let set1 = hashset! {"foo", "bar"}; + let set2 = hashset! { + "foo", + "bar", + }; + assert_eq!(set1, set2); + } + + #[test] + fn issue_60_drain_iterator_memory_corruption() { + use crate::test::MetroHashBuilder; + for i in 0..1000 { + let mut lhs = vec![0, 1, 2]; + lhs.sort_unstable(); + + let hasher = Ref::from(MetroHashBuilder::new(i)); + let mut iset: HashSet<_, MetroHashBuilder> = HashSet::with_hasher(hasher.clone()); + for &i in &lhs { + iset.insert(i); + } + + let mut rhs: Vec<_> = iset.clone().into_iter().collect(); + rhs.sort_unstable(); + + if lhs != rhs { + println!("iteration: {}", i); + println!("seed: {}", hasher.seed()); + println!("lhs: {}: {:?}", lhs.len(), &lhs); + println!("rhs: {}: {:?}", rhs.len(), &rhs); + panic!(); + } + } + } + + proptest! { + #[test] + fn proptest_a_set(ref s in hash_set(".*", 10..100)) { + assert!(s.len() < 100); + assert!(s.len() >= 10); + } + } +} |