rpds/set/hash_trie_set/
mod.rs

1use crate::HashTrieMap;
2use crate::map::hash_trie_map;
3use crate::utils::DefaultBuildHasher;
4use archery::{ArcTK, RcK, SharedPointerKind};
5use core::borrow::Borrow;
6use core::fmt::Display;
7use core::hash::BuildHasher;
8use core::hash::Hash;
9use core::iter::FromIterator;
10
11// TODO Use impl trait instead of this when available.
12pub type Iter<'a, T, P> = hash_trie_map::IterKeys<'a, T, (), P>;
13
14/// Creates a [`HashTrieSet`](crate::HashTrieSet) containing the given arguments:
15///
16/// ```
17/// # use rpds::*;
18/// #
19/// let s = HashTrieSet::new()
20///     .insert(1)
21///     .insert(2)
22///     .insert(3);
23///
24/// assert_eq!(ht_set![1, 2, 3], s);
25/// ```
26#[macro_export]
27macro_rules! ht_set {
28    ($($e:expr),*) => {
29        {
30            #[allow(unused_mut)]
31            let mut s = $crate::HashTrieSet::new();
32            $(
33                s.insert_mut($e);
34            )*
35            s
36        }
37    };
38}
39
40/// Creates a [`HashTrieSet`](crate::HashTrieSet) that implements `Sync`, containing the given
41/// arguments:
42///
43/// ```
44/// # use rpds::*;
45/// #
46/// let s = HashTrieSet::new_sync()
47///     .insert(1)
48///     .insert(2)
49///     .insert(3);
50///
51/// assert_eq!(ht_set_sync![1, 2, 3], s);
52/// ```
53#[macro_export]
54macro_rules! ht_set_sync {
55    ($($e:expr),*) => {
56        {
57            #[allow(unused_mut)]
58            let mut s = $crate::HashTrieSet::new_sync();
59            $(
60                s.insert_mut($e);
61            )*
62            s
63        }
64    };
65}
66
67/// A persistent set with structural sharing.  This implementation uses a
68/// [hash array mapped trie](https://en.wikipedia.org/wiki/Hash_array_mapped_trie).
69///
70/// # Complexity
71///
72/// Let *n* be the number of elements in the set.
73///
74/// ## Temporal complexity
75///
76/// | Operation         | Average | Worst case  |
77/// |:----------------- | -------:| -----------:|
78/// | `new()`           |    Θ(1) |        Θ(1) |
79/// | `insert()`        |    Θ(1) |        Θ(n) |
80/// | `remove()`        |    Θ(1) |        Θ(n) |
81/// | `get()`           |    Θ(1) |        Θ(n) |
82/// | `contains()`      |    Θ(1) |        Θ(n) |
83/// | `size()`          |    Θ(1) |        Θ(1) |
84/// | `clone()`         |    Θ(1) |        Θ(1) |
85/// | iterator creation |    Θ(1) |        Θ(1) |
86/// | iterator step     |    Θ(1) |        Θ(1) |
87/// | iterator full     |    Θ(n) |        Θ(n) |
88///
89/// # Implementation details
90///
91/// This is a thin wrapper around a [`HashTrieMap`](crate::HashTrieMap).
92#[derive(Debug)]
93pub struct HashTrieSet<T, P = RcK, H: BuildHasher = DefaultBuildHasher>
94where
95    T: Eq + Hash,
96    H: Clone,
97    P: SharedPointerKind,
98{
99    map: HashTrieMap<T, (), P, H>,
100}
101
102pub type HashTrieSetSync<T, H = DefaultBuildHasher> = HashTrieSet<T, ArcTK, H>;
103
104impl<T> HashTrieSet<T, RcK, DefaultBuildHasher>
105where
106    T: Eq + Hash,
107{
108    #[must_use]
109    pub fn new() -> HashTrieSet<T> {
110        HashTrieSet {
111            map: HashTrieMap::new_with_hasher_and_ptr_kind(DefaultBuildHasher::default()),
112        }
113    }
114
115    #[must_use]
116    pub fn new_with_degree(degree: u8) -> HashTrieSet<T> {
117        HashTrieSet::new_with_hasher_and_degree_and_ptr_kind(DefaultBuildHasher::default(), degree)
118    }
119}
120
121impl<T> HashTrieSetSync<T>
122where
123    T: Eq + Hash,
124{
125    #[must_use]
126    pub fn new_sync() -> HashTrieSetSync<T> {
127        HashTrieSet {
128            map: HashTrieMap::new_with_hasher_and_ptr_kind(DefaultBuildHasher::default()),
129        }
130    }
131
132    #[must_use]
133    pub fn new_with_degree_sync(degree: u8) -> HashTrieSetSync<T> {
134        HashTrieSet::new_with_hasher_and_degree_and_ptr_kind(DefaultBuildHasher::default(), degree)
135    }
136}
137
138impl<T, P, H: BuildHasher> HashTrieSet<T, P, H>
139where
140    T: Eq + Hash,
141    H: Clone,
142    P: SharedPointerKind,
143{
144    #[must_use]
145    pub fn new_with_hasher_with_ptr_kind(hasher_builder: H) -> HashTrieSet<T, P, H> {
146        HashTrieSet { map: HashTrieMap::new_with_hasher_and_ptr_kind(hasher_builder) }
147    }
148
149    #[must_use]
150    pub fn new_with_hasher_and_degree_and_ptr_kind(
151        hasher_builder: H,
152        degree: u8,
153    ) -> HashTrieSet<T, P, H> {
154        HashTrieSet {
155            map: HashTrieMap::new_with_hasher_and_degree_and_ptr_kind(hasher_builder, degree),
156        }
157    }
158
159    #[must_use]
160    pub fn insert(&self, v: T) -> HashTrieSet<T, P, H> {
161        HashTrieSet { map: self.map.insert(v, ()) }
162    }
163
164    pub fn insert_mut(&mut self, v: T) {
165        self.map.insert_mut(v, ());
166    }
167
168    #[must_use]
169    pub fn remove<V: ?Sized>(&self, v: &V) -> HashTrieSet<T, P, H>
170    where
171        T: Borrow<V>,
172        V: Hash + Eq,
173    {
174        HashTrieSet { map: self.map.remove(v) }
175    }
176
177    pub fn remove_mut<V: ?Sized>(&mut self, v: &V) -> bool
178    where
179        T: Borrow<V>,
180        V: Hash + Eq,
181    {
182        self.map.remove_mut(v)
183    }
184
185    #[must_use]
186    pub fn get<V: ?Sized>(&self, v: &V) -> Option<&T>
187    where
188        T: Borrow<V>,
189        V: Hash + Eq,
190    {
191        self.map.get_key_value(v).map(|(k, ())| k)
192    }
193
194    #[must_use]
195    pub fn contains<V: ?Sized>(&self, v: &V) -> bool
196    where
197        T: Borrow<V>,
198        V: Hash + Eq,
199    {
200        self.map.contains_key(v)
201    }
202
203    #[must_use]
204    pub fn is_disjoint<HO: BuildHasher + Clone>(&self, other: &HashTrieSet<T, P, HO>) -> bool {
205        self.iter().all(|v| !other.contains(v))
206    }
207
208    /// Test whether the two sets refer to the same content in memory.
209    ///
210    /// This would return true if you’re comparing a set to itself,
211    /// or if you’re comparing a set to a fresh clone of itself.
212    fn ptr_eq<PO: SharedPointerKind, HO: BuildHasher + Clone>(
213        &self,
214        other: &HashTrieSet<T, PO, HO>,
215    ) -> bool {
216        self.map.ptr_eq(&other.map)
217    }
218
219    #[must_use]
220    pub fn is_subset<HO: BuildHasher + Clone>(&self, other: &HashTrieSet<T, P, HO>) -> bool {
221        if self.ptr_eq(other) {
222            return true;
223        }
224
225        self.size() <= other.size() && self.iter().all(|v| other.contains(v))
226    }
227
228    #[must_use]
229    pub fn is_superset<HO: BuildHasher + Clone>(&self, other: &HashTrieSet<T, P, HO>) -> bool {
230        other.is_subset(self)
231    }
232
233    #[must_use]
234    #[inline]
235    pub fn size(&self) -> usize {
236        self.map.size()
237    }
238
239    #[must_use]
240    #[inline]
241    pub fn is_empty(&self) -> bool {
242        self.size() == 0
243    }
244
245    #[allow(clippy::iter_without_into_iter)]
246    pub fn iter(&self) -> Iter<'_, T, P> {
247        self.map.keys()
248    }
249}
250
251impl<T, P, H: BuildHasher> Clone for HashTrieSet<T, P, H>
252where
253    T: Eq + Hash,
254    H: Clone,
255    P: SharedPointerKind,
256{
257    fn clone(&self) -> HashTrieSet<T, P, H> {
258        HashTrieSet { map: self.map.clone() }
259    }
260}
261
262impl<T, P, H: BuildHasher> Default for HashTrieSet<T, P, H>
263where
264    T: Eq + Hash,
265    H: Default + Clone,
266    P: SharedPointerKind,
267{
268    fn default() -> HashTrieSet<T, P, H> {
269        HashTrieSet::new_with_hasher_with_ptr_kind(H::default())
270    }
271}
272
273impl<T: Eq, P, PO, H: BuildHasher> PartialEq<HashTrieSet<T, PO, H>> for HashTrieSet<T, P, H>
274where
275    T: Hash,
276    H: Clone,
277    P: SharedPointerKind,
278    PO: SharedPointerKind,
279{
280    fn eq(&self, other: &HashTrieSet<T, PO, H>) -> bool {
281        self.map.eq(&other.map)
282    }
283}
284
285impl<T: Eq, P, H: BuildHasher> Eq for HashTrieSet<T, P, H>
286where
287    T: Hash,
288    H: Clone,
289    P: SharedPointerKind,
290{
291}
292
293impl<T, P, H: BuildHasher> Display for HashTrieSet<T, P, H>
294where
295    T: Eq + Hash + Display,
296    H: Clone,
297    P: SharedPointerKind,
298{
299    fn fmt(&self, fmt: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
300        let mut first = true;
301
302        fmt.write_str("{")?;
303
304        for v in self.iter() {
305            if !first {
306                fmt.write_str(", ")?;
307            }
308            v.fmt(fmt)?;
309            first = false;
310        }
311
312        fmt.write_str("}")
313    }
314}
315
316impl<'a, T, P, H: BuildHasher> IntoIterator for &'a HashTrieSet<T, P, H>
317where
318    T: Eq + Hash,
319    H: Default + Clone,
320    P: SharedPointerKind,
321{
322    type Item = &'a T;
323    type IntoIter = Iter<'a, T, P>;
324
325    fn into_iter(self) -> Iter<'a, T, P> {
326        self.iter()
327    }
328}
329
330impl<T, P, H> FromIterator<T> for HashTrieSet<T, P, H>
331where
332    T: Eq + Hash,
333    H: BuildHasher + Clone + Default,
334    P: SharedPointerKind,
335{
336    fn from_iter<I: IntoIterator<Item = T>>(into_iter: I) -> HashTrieSet<T, P, H> {
337        let mut set = HashTrieSet::new_with_hasher_with_ptr_kind(Default::default());
338
339        for v in into_iter {
340            set.insert_mut(v);
341        }
342
343        set
344    }
345}
346
347#[cfg(feature = "serde")]
348pub mod serde {
349    use super::*;
350    use ::serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
351    use ::serde::ser::{Serialize, Serializer};
352    use core::fmt;
353    use core::marker::PhantomData;
354
355    impl<T, P, H> Serialize for HashTrieSet<T, P, H>
356    where
357        T: Eq + Hash + Serialize,
358        H: BuildHasher + Clone + Default,
359        P: SharedPointerKind,
360    {
361        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
362            serializer.collect_seq(self)
363        }
364    }
365
366    impl<'de, T, P, H> Deserialize<'de> for HashTrieSet<T, P, H>
367    where
368        T: Eq + Hash + Deserialize<'de>,
369        H: BuildHasher + Clone + Default,
370        P: SharedPointerKind,
371    {
372        fn deserialize<D: Deserializer<'de>>(
373            deserializer: D,
374        ) -> Result<HashTrieSet<T, P, H>, D::Error> {
375            deserializer.deserialize_seq(HashTrieSetVisitor {
376                _phantom_t: PhantomData,
377                _phantom_h: PhantomData,
378                _phantom_p: PhantomData,
379            })
380        }
381    }
382
383    struct HashTrieSetVisitor<T, P, H> {
384        _phantom_t: PhantomData<T>,
385        _phantom_h: PhantomData<H>,
386        _phantom_p: PhantomData<P>,
387    }
388
389    impl<'de, T, P, H> Visitor<'de> for HashTrieSetVisitor<T, P, H>
390    where
391        T: Eq + Hash + Deserialize<'de>,
392        H: BuildHasher + Clone + Default,
393        P: SharedPointerKind,
394    {
395        type Value = HashTrieSet<T, P, H>;
396
397        fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
398            formatter.write_str("a sequence")
399        }
400
401        fn visit_seq<A>(self, mut seq: A) -> Result<HashTrieSet<T, P, H>, A::Error>
402        where
403            A: SeqAccess<'de>,
404        {
405            let mut set = HashTrieSet::new_with_hasher_with_ptr_kind(Default::default());
406
407            while let Some(value) = seq.next_element()? {
408                set.insert_mut(value);
409            }
410
411            Ok(set)
412        }
413    }
414}
415
416#[cfg(test)]
417mod test;
rpds/set/hash_trie_set/mod.rs

rpds/set/hash_trie_set/
mod.rs
