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
102impl<K, H, const I: usize> AutoSet<K, H, I> {
103    /// see [HashSet::len](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.len)
104    pub fn len(&self) -> usize {
105        self.map.len()
106    }
107
108    /// see [HashSet::is_empty](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.is_empty)
109    pub fn is_empty(&self) -> bool {
110        self.map.is_empty()
111    }
112
113    /// see [HashSet::iter](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html#method.iter)
114    pub fn iter(&self) -> Iter<'_, K> {
115        Iter(self.map.iter())
116    }
117}
118
119impl<K, H, const I: usize> IntoIterator for AutoSet<K, H, I> {
120    type Item = K;
121    type IntoIter = IntoIter<K, I>;
122
123    fn into_iter(self) -> Self::IntoIter {
124        IntoIter(self.map.into_iter())
125    }
126}
127
128impl<'a, K, H, const I: usize> IntoIterator for &'a AutoSet<K, H, I> {
129    type Item = &'a K;
130    type IntoIter = Iter<'a, K>;
131
132    fn into_iter(self) -> Self::IntoIter {
133        self.iter()
134    }
135}
136
137pub struct Iter<'a, K>(super::map::Iter<'a, K, ()>);
138
139impl<'a, K> Iterator for Iter<'a, K> {
140    type Item = &'a K;
141
142    fn next(&mut self) -> Option<Self::Item> {
143        self.0.next().map(|(k, _)| k)
144    }
145
146    fn size_hint(&self) -> (usize, Option<usize>) {
147        self.0.size_hint()
148    }
149}
150
151impl<K> Clone for Iter<'_, K> {
152    fn clone(&self) -> Self {
153        Self(self.0.clone())
154    }
155}
156
157pub struct IntoIter<K, const I: usize>(super::map::IntoIter<K, (), I>);
158
159impl<K, const I: usize> Iterator for IntoIter<K, I> {
160    type Item = K;
161
162    fn next(&mut self) -> Option<Self::Item> {
163        self.0.next().map(|(k, _)| k)
164    }
165
166    fn size_hint(&self) -> (usize, Option<usize>) {
167        self.0.size_hint()
168    }
169}
170
171impl<K, H, const I: usize> Serialize for AutoSet<K, H, I>
172where
173    K: Serialize,
174    H: BuildHasher,
175{
176    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
177        serializer.collect_seq(self.iter())
178    }
179}
180
181impl<'de, K, H, const I: usize> Deserialize<'de> for AutoSet<K, H, I>
182where
183    K: Deserialize<'de> + Hash + Eq,
184    H: BuildHasher + Default,
185{
186    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
187        struct AutoSetVisitor<K, H, const I: usize>(PhantomData<AutoSet<K, H, I>>);
188
189        impl<'de, K, H, const I: usize> serde::de::Visitor<'de> for AutoSetVisitor<K, H, I>
190        where
191            K: Deserialize<'de> + Hash + Eq,
192            H: BuildHasher + Default,
193        {
194            type Value = AutoSet<K, H, I>;
195
196            fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
197                formatter.write_str("a set")
198            }
199
200            fn visit_seq<A: serde::de::SeqAccess<'de>>(
201                self,
202                mut seq: A,
203            ) -> Result<Self::Value, A::Error> {
204                let mut set = if let Some(size) = seq.size_hint() {
205                    AutoSet::with_capacity_and_hasher(size, H::default())
206                } else {
207                    AutoSet::with_hasher()
208                };
209                while let Some(item) = seq.next_element()? {
210                    set.insert(item);
211                }
212                Ok(set)
213            }
214        }
215
216        deserializer.deserialize_seq(AutoSetVisitor(std::marker::PhantomData))
217    }
218}
219
220impl<K: Eq + Hash, H: BuildHasher, const I: usize> PartialEq for AutoSet<K, H, I> {
221    fn eq(&self, other: &Self) -> bool {
222        self.map == other.map
223    }
224}
225
226impl<K: Eq + Hash, H: BuildHasher, const I: usize> Eq for AutoSet<K, H, I> {}
227
228impl<K: Eq + Hash, SH: BuildHasher + Default, const I: usize> Hash for AutoSet<K, SH, I> {
229    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
230        self.map.hash(state);
231    }
232}
233
234impl<K, H, const I: usize> FromIterator<K> for AutoSet<K, H, I>
235where
236    K: Hash + Eq,
237    H: BuildHasher + Default,
238{
239    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
240        Self {
241            map: AutoMap::from_iter(iter.into_iter().map(|item| (item, ()))),
242        }
243    }
244}
245
246impl<K, H, const N: usize, const I: usize> From<[K; N]> for AutoSet<K, H, I>
247where
248    K: Hash + Eq,
249    H: BuildHasher + Default,
250{
251    fn from(array: [K; N]) -> Self {
252        Self::from_iter(array)
253    }
254}
255
256impl<K, H, const I: usize> ShrinkToFit for AutoSet<K, H, I>
257where
258    K: Eq + Hash,
259    H: BuildHasher + Default,
260{
261    fn shrink_to_fit(&mut self) {
262        self.map.shrink_to_fit();
263    }
264}
265
266#[cfg(test)]
267mod tests {
268    use super::*;
269    use crate::MAX_LIST_SIZE;
270
271    #[test]
272    fn test_auto_set() {
273        let mut set = AutoSet::new();
274        for i in 0..MAX_LIST_SIZE * 2 {
275            set.insert(i);
276        }
277        for i in 0..MAX_LIST_SIZE * 2 {
278            assert!(set.contains(&i));
279        }
280        assert!(!set.contains(&(MAX_LIST_SIZE * 2)));
281        for i in 0..MAX_LIST_SIZE * 2 {
282            assert!(!set.remove(&(MAX_LIST_SIZE * 2)));
283            assert!(set.remove(&i));
284        }
285        assert!(!set.remove(&(MAX_LIST_SIZE * 2)));
286    }
287}
auto_hash_map/set.rs

auto_hash_map/
set.rs
