auto_hash_map/
set.rs

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

auto_hash_map/
set.rs
