1 use crate::RandomState;
2 use std::collections::{hash_set, HashSet};
3 use std::fmt::{self, Debug};
4 use std::hash::{BuildHasher, Hash};
5 use std::iter::FromIterator;
6 use std::ops::{BitAnd, BitOr, BitXor, Deref, DerefMut, Sub};
7 
8 #[cfg(feature = "serde")]
9 use serde::{
10     de::{Deserialize, Deserializer},
11     ser::{Serialize, Serializer},
12 };
13 
14 /// A [`HashSet`](std::collections::HashSet) using [`RandomState`](crate::RandomState) to hash the items.
15 /// (Requires the `std` feature to be enabled.)
16 #[derive(Clone)]
17 pub struct AHashSet<T, S = RandomState>(HashSet<T, S>);
18 
19 impl<T> From<HashSet<T, RandomState>> for AHashSet<T> {
from(item: HashSet<T, RandomState>) -> Self20     fn from(item: HashSet<T, RandomState>) -> Self {
21         AHashSet(item)
22     }
23 }
24 
25 impl<T, const N: usize> From<[T; N]> for AHashSet<T>
26 where
27     T: Eq + Hash,
28 {
29     /// # Examples
30     ///
31     /// ```
32     /// use ahash::AHashSet;
33     ///
34     /// let set1 = AHashSet::from([1, 2, 3, 4]);
35     /// let set2: AHashSet<_> = [1, 2, 3, 4].into();
36     /// assert_eq!(set1, set2);
37     /// ```
from(arr: [T; N]) -> Self38     fn from(arr: [T; N]) -> Self {
39         Self::from_iter(arr)
40     }
41 }
42 
43 impl<T> Into<HashSet<T, RandomState>> for AHashSet<T> {
into(self) -> HashSet<T, RandomState>44     fn into(self) -> HashSet<T, RandomState> {
45         self.0
46     }
47 }
48 
49 impl<T> AHashSet<T, RandomState> {
50     /// This crates a hashset using [RandomState::new].
51     /// See the documentation in [RandomSource] for notes about key strength.
new() -> Self52     pub fn new() -> Self {
53         AHashSet(HashSet::with_hasher(RandomState::new()))
54     }
55 
56     /// This crates a hashset with the specified capacity using [RandomState::new].
57     /// See the documentation in [RandomSource] for notes about key strength.
with_capacity(capacity: usize) -> Self58     pub fn with_capacity(capacity: usize) -> Self {
59         AHashSet(HashSet::with_capacity_and_hasher(capacity, RandomState::new()))
60     }
61 }
62 
63 impl<T, S> AHashSet<T, S>
64 where
65     S: BuildHasher,
66 {
with_hasher(hash_builder: S) -> Self67     pub fn with_hasher(hash_builder: S) -> Self {
68         AHashSet(HashSet::with_hasher(hash_builder))
69     }
70 
with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self71     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
72         AHashSet(HashSet::with_capacity_and_hasher(capacity, hash_builder))
73     }
74 }
75 
76 impl<T, S> Deref for AHashSet<T, S> {
77     type Target = HashSet<T, S>;
deref(&self) -> &Self::Target78     fn deref(&self) -> &Self::Target {
79         &self.0
80     }
81 }
82 
83 impl<T, S> DerefMut for AHashSet<T, S> {
deref_mut(&mut self) -> &mut Self::Target84     fn deref_mut(&mut self) -> &mut Self::Target {
85         &mut self.0
86     }
87 }
88 
89 impl<T, S> PartialEq for AHashSet<T, S>
90 where
91     T: Eq + Hash,
92     S: BuildHasher,
93 {
eq(&self, other: &AHashSet<T, S>) -> bool94     fn eq(&self, other: &AHashSet<T, S>) -> bool {
95         self.0.eq(&other.0)
96     }
97 }
98 
99 impl<T, S> Eq for AHashSet<T, S>
100 where
101     T: Eq + Hash,
102     S: BuildHasher,
103 {
104 }
105 
106 impl<T, S> BitOr<&AHashSet<T, S>> for &AHashSet<T, S>
107 where
108     T: Eq + Hash + Clone,
109     S: BuildHasher + Default,
110 {
111     type Output = AHashSet<T, S>;
112 
113     /// Returns the union of `self` and `rhs` as a new `AHashSet<T, S>`.
114     ///
115     /// # Examples
116     ///
117     /// ```
118     /// use ahash::AHashSet;
119     ///
120     /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect();
121     /// let b: AHashSet<_> = vec![3, 4, 5].into_iter().collect();
122     ///
123     /// let set = &a | &b;
124     ///
125     /// let mut i = 0;
126     /// let expected = [1, 2, 3, 4, 5];
127     /// for x in &set {
128     ///     assert!(expected.contains(x));
129     ///     i += 1;
130     /// }
131     /// assert_eq!(i, expected.len());
132     /// ```
bitor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>133     fn bitor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> {
134         AHashSet(self.0.bitor(&rhs.0))
135     }
136 }
137 
138 impl<T, S> BitAnd<&AHashSet<T, S>> for &AHashSet<T, S>
139 where
140     T: Eq + Hash + Clone,
141     S: BuildHasher + Default,
142 {
143     type Output = AHashSet<T, S>;
144 
145     /// Returns the intersection of `self` and `rhs` as a new `AHashSet<T, S>`.
146     ///
147     /// # Examples
148     ///
149     /// ```
150     /// use ahash::AHashSet;
151     ///
152     /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect();
153     /// let b: AHashSet<_> = vec![2, 3, 4].into_iter().collect();
154     ///
155     /// let set = &a & &b;
156     ///
157     /// let mut i = 0;
158     /// let expected = [2, 3];
159     /// for x in &set {
160     ///     assert!(expected.contains(x));
161     ///     i += 1;
162     /// }
163     /// assert_eq!(i, expected.len());
164     /// ```
bitand(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>165     fn bitand(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> {
166         AHashSet(self.0.bitand(&rhs.0))
167     }
168 }
169 
170 impl<T, S> BitXor<&AHashSet<T, S>> for &AHashSet<T, S>
171 where
172     T: Eq + Hash + Clone,
173     S: BuildHasher + Default,
174 {
175     type Output = AHashSet<T, S>;
176 
177     /// Returns the symmetric difference of `self` and `rhs` as a new `AHashSet<T, S>`.
178     ///
179     /// # Examples
180     ///
181     /// ```
182     /// use ahash::AHashSet;
183     ///
184     /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect();
185     /// let b: AHashSet<_> = vec![3, 4, 5].into_iter().collect();
186     ///
187     /// let set = &a ^ &b;
188     ///
189     /// let mut i = 0;
190     /// let expected = [1, 2, 4, 5];
191     /// for x in &set {
192     ///     assert!(expected.contains(x));
193     ///     i += 1;
194     /// }
195     /// assert_eq!(i, expected.len());
196     /// ```
bitxor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>197     fn bitxor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> {
198         AHashSet(self.0.bitxor(&rhs.0))
199     }
200 }
201 
202 impl<T, S> Sub<&AHashSet<T, S>> for &AHashSet<T, S>
203 where
204     T: Eq + Hash + Clone,
205     S: BuildHasher + Default,
206 {
207     type Output = AHashSet<T, S>;
208 
209     /// Returns the difference of `self` and `rhs` as a new `AHashSet<T, S>`.
210     ///
211     /// # Examples
212     ///
213     /// ```
214     /// use ahash::AHashSet;
215     ///
216     /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect();
217     /// let b: AHashSet<_> = vec![3, 4, 5].into_iter().collect();
218     ///
219     /// let set = &a - &b;
220     ///
221     /// let mut i = 0;
222     /// let expected = [1, 2];
223     /// for x in &set {
224     ///     assert!(expected.contains(x));
225     ///     i += 1;
226     /// }
227     /// assert_eq!(i, expected.len());
228     /// ```
sub(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>229     fn sub(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> {
230         AHashSet(self.0.sub(&rhs.0))
231     }
232 }
233 
234 impl<T, S> Debug for AHashSet<T, S>
235 where
236     T: Debug,
237     S: BuildHasher,
238 {
fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result239     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
240         self.0.fmt(fmt)
241     }
242 }
243 
244 impl<T> FromIterator<T> for AHashSet<T, RandomState>
245 where
246     T: Eq + Hash,
247 {
248     /// This crates a hashset from the provided iterator using [RandomState::new].
249     /// See the documentation in [RandomSource] for notes about key strength.
250     #[inline]
from_iter<I: IntoIterator<Item = T>>(iter: I) -> AHashSet<T>251     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> AHashSet<T> {
252         let mut inner = HashSet::with_hasher(RandomState::new());
253         inner.extend(iter);
254         AHashSet(inner)
255     }
256 }
257 
258 impl<'a, T, S> IntoIterator for &'a AHashSet<T, S> {
259     type Item = &'a T;
260     type IntoIter = hash_set::Iter<'a, T>;
into_iter(self) -> Self::IntoIter261     fn into_iter(self) -> Self::IntoIter {
262         (&self.0).iter()
263     }
264 }
265 
266 impl<T, S> IntoIterator for AHashSet<T, S> {
267     type Item = T;
268     type IntoIter = hash_set::IntoIter<T>;
into_iter(self) -> Self::IntoIter269     fn into_iter(self) -> Self::IntoIter {
270         self.0.into_iter()
271     }
272 }
273 
274 impl<T, S> Extend<T> for AHashSet<T, S>
275 where
276     T: Eq + Hash,
277     S: BuildHasher,
278 {
279     #[inline]
extend<I: IntoIterator<Item = T>>(&mut self, iter: I)280     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
281         self.0.extend(iter)
282     }
283 }
284 
285 impl<'a, T, S> Extend<&'a T> for AHashSet<T, S>
286 where
287     T: 'a + Eq + Hash + Copy,
288     S: BuildHasher,
289 {
290     #[inline]
extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)291     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
292         self.0.extend(iter)
293     }
294 }
295 
296 /// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or
297 /// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of
298 /// constructors for [RandomState] must be used.
299 #[cfg(any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng"))]
300 impl<T> Default for AHashSet<T, RandomState> {
301     /// Creates an empty `AHashSet<T, S>` with the `Default` value for the hasher.
302     #[inline]
default() -> AHashSet<T, RandomState>303     fn default() -> AHashSet<T, RandomState> {
304         AHashSet(HashSet::default())
305     }
306 }
307 
308 #[cfg(feature = "serde")]
309 impl<T> Serialize for AHashSet<T>
310 where
311     T: Serialize + Eq + Hash,
312 {
serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>313     fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
314         self.deref().serialize(serializer)
315     }
316 }
317 
318 #[cfg(feature = "serde")]
319 impl<'de, T> Deserialize<'de> for AHashSet<T>
320 where
321     T: Deserialize<'de> + Eq + Hash,
322 {
deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>323     fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
324         let hash_set = HashSet::deserialize(deserializer);
325         hash_set.map(|hash_set| Self(hash_set))
326     }
327 
deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error>328     fn deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error> {
329         HashSet::deserialize_in_place(deserializer, place)
330     }
331 }
332 
333 #[cfg(all(test, feature = "serde"))]
334 mod test {
335     use super::*;
336 
337     #[test]
test_serde()338     fn test_serde() {
339         let mut set = AHashSet::new();
340         set.insert("for".to_string());
341         set.insert("bar".to_string());
342         let mut serialization = serde_json::to_string(&set).unwrap();
343         let mut deserialization: AHashSet<String> = serde_json::from_str(&serialization).unwrap();
344         assert_eq!(deserialization, set);
345 
346         set.insert("baz".to_string());
347         serialization = serde_json::to_string(&set).unwrap();
348         let mut deserializer = serde_json::Deserializer::from_str(&serialization);
349         AHashSet::deserialize_in_place(&mut deserializer, &mut deserialization).unwrap();
350         assert_eq!(deserialization, set);
351     }
352 }
353