auto_hash_map/
set.rs

1use std::{
2    fmt::Debug,
3    hash::{BuildHasher, BuildHasherDefault, Hash},
4    marker::PhantomData,
5};
6
7use rustc_hash::FxHasher;
8use serde::{Deserialize, Serialize};
9use shrink_to_fit::ShrinkToFit;
10
11use crate::AutoMap;
12
13#[derive(Clone)]
14pub struct AutoSet<K, H = BuildHasherDefault<FxHasher>, const I: usize = 0> {
15    map: AutoMap<K, (), H, I>,
16}
17
18impl<K, H, const I: usize> Default for AutoSet<K, H, I> {
19    fn default() -> Self {
20        Self {
21            map: Default::default(),
22        }
23    }
24}
25
26impl<K: Debug, H, const I: usize> Debug for AutoSet<K, H, I> {
27    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
28        f.debug_set().entries(self.iter()).finish()
29    }
30}
31
32impl<K> AutoSet<K, BuildHasherDefault<FxHasher>, 0> {
33    /// see [HashSet::new](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.new)
34    pub const fn new() -> Self {
35        Self {
36            map: AutoMap::new(),
37        }
38    }
39
40    /// see [HashSet::with_capacity](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.with_capacity)
41    pub fn with_capacity(capacity: usize) -> Self {
42        Self {
43            map: AutoMap::with_capacity(capacity),
44        }
45    }
46}
47
48impl<K, H: BuildHasher, const I: usize> AutoSet<K, H, I> {
49    /// see [HashSet::with_hasher](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.with_hasher)
50    pub const fn with_hasher() -> Self {
51        Self {
52            map: AutoMap::with_hasher(),
53        }
54    }
55
56    /// see [HashSet::with_capacity_and_hasher](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.with_capacity_and_hasher)
57    pub fn with_capacity_and_hasher(capacity: usize, hasher: H) -> Self {
58        Self {
59            map: AutoMap::with_capacity_and_hasher(capacity, hasher),
60        }
61    }
62
63    /// see [HashSet::clear](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.clear)
64    pub fn clear(&mut self) {
65        self.map.clear();
66    }
67}
68
69impl<K: Hash + Eq, H: BuildHasher + Default, const I: usize> AutoSet<K, H, I> {
70    /// see [HashSet::insert](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.insert)
71    pub fn insert(&mut self, key: K) -> bool {
72        self.map.insert(key, ()).is_none()
73    }
74
75    /// see [HashSet::remove](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.remove)
76    pub fn remove(&mut self, key: &K) -> bool {
77        self.map.remove(key).is_some()
78    }
79
80    /// see [HashSet::extend](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.extend)
81    pub fn extend(&mut self, iter: impl IntoIterator<Item = K>) {
82        self.map.extend(iter.into_iter().map(|item| (item, ())))
83    }
84
85    /// see [HashSet::shrink_to_fit](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.shrink_to_fit)
86    pub fn shrink_to_fit(&mut self) {
87        self.map.shrink_to_fit();
88    }
89
90    /// see [HashSet::contains](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.contains)
91    pub fn contains(&self, key: &K) -> bool {
92        self.map.contains_key(key)
93    }
94}
95
96impl<K, H, const I: usize> AutoSet<K, H, I> {
97    /// see [HashSet::len](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.len)
98    pub fn len(&self) -> usize {
99        self.map.len()
100    }
101
102    /// see [HashSet::is_empty](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.is_empty)
103    pub fn is_empty(&self) -> bool {
104        self.map.is_empty()
105    }
106
107    /// see [HashSet::iter](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.iter)
108    pub fn iter(&self) -> Iter<'_, K> {
109        Iter(self.map.iter())
110    }
111}
112
113impl<K, H, const I: usize> IntoIterator for AutoSet<K, H, I> {
114    type Item = K;
115    type IntoIter = IntoIter<K, I>;
116
117    fn into_iter(self) -> Self::IntoIter {
118        IntoIter(self.map.into_iter())
119    }
120}
121
122impl<'a, K, H, const I: usize> IntoIterator for &'a AutoSet<K, H, I> {
123    type Item = &'a K;
124    type IntoIter = Iter<'a, K>;
125
126    fn into_iter(self) -> Self::IntoIter {
127        self.iter()
128    }
129}
130
131pub struct Iter<'a, K>(super::map::Iter<'a, K, ()>);
132
133impl<'a, K> Iterator for Iter<'a, K> {
134    type Item = &'a K;
135
136    fn next(&mut self) -> Option<Self::Item> {
137        self.0.next().map(|(k, _)| k)
138    }
139
140    fn size_hint(&self) -> (usize, Option<usize>) {
141        self.0.size_hint()
142    }
143}
144
145impl<K> Clone for Iter<'_, K> {
146    fn clone(&self) -> Self {
147        Self(self.0.clone())
148    }
149}
150
151pub struct IntoIter<K, const I: usize>(super::map::IntoIter<K, (), I>);
152
153impl<K, const I: usize> Iterator for IntoIter<K, I> {
154    type Item = K;
155
156    fn next(&mut self) -> Option<Self::Item> {
157        self.0.next().map(|(k, _)| k)
158    }
159
160    fn size_hint(&self) -> (usize, Option<usize>) {
161        self.0.size_hint()
162    }
163}
164
165impl<K, H, const I: usize> Serialize for AutoSet<K, H, I>
166where
167    K: Serialize,
168    H: BuildHasher,
169{
170    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
171        serializer.collect_seq(self.iter())
172    }
173}
174
175impl<'de, K, H, const I: usize> Deserialize<'de> for AutoSet<K, H, I>
176where
177    K: Deserialize<'de> + Hash + Eq,
178    H: BuildHasher + Default,
179{
180    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
181        struct AutoSetVisitor<K, H, const I: usize>(PhantomData<AutoSet<K, H, I>>);
182
183        impl<'de, K, H, const I: usize> serde::de::Visitor<'de> for AutoSetVisitor<K, H, I>
184        where
185            K: Deserialize<'de> + Hash + Eq,
186            H: BuildHasher + Default,
187        {
188            type Value = AutoSet<K, H, I>;
189
190            fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
191                formatter.write_str("a set")
192            }
193
194            fn visit_seq<A: serde::de::SeqAccess<'de>>(
195                self,
196                mut seq: A,
197            ) -> Result<Self::Value, A::Error> {
198                let mut set = if let Some(size) = seq.size_hint() {
199                    AutoSet::with_capacity_and_hasher(size, H::default())
200                } else {
201                    AutoSet::with_hasher()
202                };
203                while let Some(item) = seq.next_element()? {
204                    set.insert(item);
205                }
206                Ok(set)
207            }
208        }
209
210        deserializer.deserialize_seq(AutoSetVisitor(std::marker::PhantomData))
211    }
212}
213
214impl<K: Eq + Hash, H: BuildHasher, const I: usize> PartialEq for AutoSet<K, H, I> {
215    fn eq(&self, other: &Self) -> bool {
216        self.map == other.map
217    }
218}
219
220impl<K: Eq + Hash, H: BuildHasher, const I: usize> Eq for AutoSet<K, H, I> {}
221
222impl<K, H, const I: usize> FromIterator<K> for AutoSet<K, H, I>
223where
224    K: Hash + Eq,
225    H: BuildHasher + Default,
226{
227    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
228        Self {
229            map: AutoMap::from_iter(iter.into_iter().map(|item| (item, ()))),
230        }
231    }
232}
233
234impl<K, H, const N: usize, const I: usize> From<[K; N]> for AutoSet<K, H, I>
235where
236    K: Hash + Eq,
237    H: BuildHasher + Default,
238{
239    fn from(array: [K; N]) -> Self {
240        Self::from_iter(array)
241    }
242}
243
244impl<K, H, const I: usize> ShrinkToFit for AutoSet<K, H, I>
245where
246    K: Eq + Hash,
247    H: BuildHasher + Default,
248{
249    fn shrink_to_fit(&mut self) {
250        self.map.shrink_to_fit();
251    }
252}
253
254#[cfg(test)]
255mod tests {
256    use super::*;
257    use crate::MAX_LIST_SIZE;
258
259    #[test]
260    fn test_auto_set() {
261        let mut set = AutoSet::new();
262        for i in 0..MAX_LIST_SIZE * 2 {
263            set.insert(i);
264        }
265        for i in 0..MAX_LIST_SIZE * 2 {
266            assert!(set.contains(&i));
267        }
268        assert!(!set.contains(&(MAX_LIST_SIZE * 2)));
269        for i in 0..MAX_LIST_SIZE * 2 {
270            assert!(!set.remove(&(MAX_LIST_SIZE * 2)));
271            assert!(set.remove(&i));
272        }
273        assert!(!set.remove(&(MAX_LIST_SIZE * 2)));
274    }
275}
auto_hash_map/set.rs

auto_hash_map/
set.rs
