hash_trie/
set.rs

1use crate::{traits::*, hash_trie::HashTrie, *};
2use alloc::fmt::Debug;
3
4/// `HashTrieSet` implements a hash set using a hash array mapped trie (HAMT).
5/// 
6/// # Example Usage
7/// 
8/// ```
9/// use fnv::FnvHasher;
10/// use hash_trie::{HashTrieSet, traits::HashLike};
11/// use std::string::String;
12/// 
13/// #[derive(Clone,Debug,Eq,Hash,PartialEq)]
14/// struct Str<'a> {
15///     s: &'a str
16/// }
17/// 
18/// impl <'a> Str<'a> {
19///     fn new(s: &'a str) -> Self {
20///         Self {s}
21///     }
22/// }
23/// 
24/// impl <'a> Default for Str<'a> {
25///     fn default() -> Self {
26///         Self {s: ""}
27///     }
28/// }
29/// impl <'a> From<Str<'a>> for String {
30///     fn from(s: Str<'a>) -> String {
31///         s.s.into()
32///     }
33/// }
34/// impl <'a> PartialEq<Str<'a>> for String {
35///     fn eq(&self, other: &Str<'a>) -> bool {
36///         *self == other.s
37///     }
38/// }
39/// impl <'a> HashLike<String> for Str<'a> {}
40/// impl <'a> HashLike<Str<'a>> for String {}
41/// unsafe impl <'a> Send for Str<'a> {}
42/// unsafe impl <'a> Sync for Str<'a> {}
43/// 
44/// let mut hash_set: HashTrieSet<u64, u32, String, FnvHasher> = HashTrieSet::new();
45/// let hello_world = "Hello, world!";
46///
47/// hash_set = hash_set.insert(Str::new(hello_world), false).unwrap().0;
48/// 
49/// // Inserting an already-inserted key returns a reference to the key in the set...
50/// assert!(*hash_set.insert(Str::new(hello_world), false).map(|_| ()).unwrap_err() == hello_world);
51/// // ... unless you enable replacement.
52/// assert!(hash_set.insert(Str::new(hello_world), true).is_ok());
53///
54/// assert!(hash_set.find(&Str::new(hello_world)).map(|reference| *reference == hello_world).unwrap());
55///
56/// match hash_set.remove(&Str::new(hello_world)) {
57///     Ok((mutated, reference)) => {
58///         // Removing a key returns a reference to the key
59///         // in the set in addition to the mutated set.
60///         println!("Value stored in hash_set: {}", reference);
61///         hash_set = mutated;
62///     },
63///     Err(_) => panic!(),
64/// }
65/// ```
66#[derive(Clone, Debug)]
67#[must_use]
68pub struct HashTrieSet <H: Hashword, F: Flagword<H>, K: Key, M: HasherBv<H, K>> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
69    set: HashTrie<H, F, K, (), M>,
70}
71
72impl <H: Hashword, F: Flagword<H>, K: Key, M: HasherBv<H, K>> HashTrieSet<H, F, K, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
73    /// Get a new, empty HashTrieSet.
74    pub fn new() -> Self {
75        Self {
76            set: HashTrie::new()
77        }
78    }
79
80    /// Get the total number of entries in the set.
81    pub fn size(&self) -> usize {
82        self.set.size()
83    }
84
85    /// Search the HashTrieSet for the given key and return a reference if found, or `HashTrieError::NotFound` if not found.
86    pub fn find<'a, L: Key + HashLike<K>>(&'a self, key: &L) -> Result<&'a K, HashTrieError> where K: PartialEq<L>, M: HasherBv<H, L> {
87        self.set.find(key).map(|(key, _value)| key)
88    }
89
90    /// Search the HashTrieSet for the spot to insert the key and return both a mutated set and, if applicable, a reference to the replaced key.
91    /// If found and replacement is disabled, a reference to the existing key is returned.
92    pub fn insert<'a, L: Key + HashLike<K> + Into<K>>(&'a self, key: L, replace: bool) -> Result<(Self, *const K, Option<&'a K>), &'a K>
93    where
94        K: HashLike<L>,
95        K: PartialEq<L>,
96        M: HasherBv<H, L>
97    {
98        self.set.insert(key, (), replace).map(|(set, key, _value, prev)| (Self {set}, key, prev.map(|(k, _v)| k))).map_err(|(key, _value)| key)
99    }
100
101    /// Search the HashTrieSet for the given key to remove and return a mutated set, or `HashTrieError::NotFound` if not found.
102    pub fn remove<'a, L: Key + HashLike<K>>(&'a self, key: &L) -> Result<(Self, &'a K), HashTrieError> where K: PartialEq<L>, M: HasherBv<H, L> {
103        self.set.remove(key).map(|(set, key, _value)| (Self {set}, key))
104    }
105
106    /// Run an operation on each entry in the set.
107    pub fn visit<Op: Clone>(&self, op: Op) where Op: Fn(&K) {
108        self.set.visit(|key, _value| op(key));
109    }
110
111    /// Run a transform operation on each entry in the set. Returns the transformed set and a reduction of the secondary returns of the transform operations.
112    pub fn transform<ReduceT, ReduceOp, Op>
113        (&self, reduce_op: ReduceOp, op: Op) -> (Self, ReduceT)
114        where
115        Self: Sized,
116        ReduceT: Default,
117        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
118        Op: Fn(&K) -> SetTransformResult<ReduceT> + Clone,
119    {
120        let (set, reduced) = self.set.transform(reduce_op, |key, _value| match op(key) {
121            SetTransformResult::Unchanged(reduced) => MapTransformResult::Unchanged(reduced),
122            SetTransformResult::Removed(reduced) => MapTransformResult::Removed(reduced),
123        });
124        (Self{set}, reduced)
125    }
126
127    /// Run a transmute operation on each entry in the set. Returns the transmuted set and a reduction of the secondary returns of the transmute operations.
128    pub unsafe fn transmute<S: Key + HashLike<S>, ReduceT, ReduceOp, Op>
129        (&self, reduce_op: ReduceOp, op: Op) -> (HashTrieSet<H, F, S, M>, ReduceT)
130        where
131        Self: Sized,
132        ReduceT: Default,
133        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
134        Op: Fn(&K) -> SetTransmuteResult<S, ReduceT> + Clone,
135        K: HashLike<S>,
136        K: PartialEq<S>,
137        M: HasherBv<H, S>,
138    {
139        let (set, reduced) = self.set.transmute(reduce_op, |key, _value| match op(key) {
140            SetTransmuteResult::Transmuted(key, reduced) => MapTransmuteResult::Transmuted(key, (), reduced),
141            SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
142        });
143        (HashTrieSet{set}, reduced)
144    }
145
146    /// Run a transform operation on each entry or pair of entries in the sets. Returns the transformed set and a reduction of the secondary returns of the transmute operations. Can reuse nodes from either set.
147    pub fn transform_with_transformed<ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
148        (&self, right: &Self, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (Self, ReduceT)
149        where
150        Self: Sized,
151        ReduceT: Default,
152        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
153        BothOp: Fn(&K, &K) -> SetJointTransformResult<ReduceT> + Clone,
154        LeftOp: Fn(&K) -> SetTransformResult<ReduceT> + Clone,
155        RightOp: Fn(&K) -> SetTransformResult<ReduceT> + Clone,
156    {
157        let (set, reduced) = self.set.transform_with_transformed(&right.set, reduce_op,
158            |l,_,r,_| both_op(l, r).into(),
159            |l,_| left_op(l).into(),
160            |r,_| right_op(r).into());
161        (HashTrieSet{set}, reduced)
162    }
163
164    /// Run a transform/transmute operation on each entry or pair of entries in the sets. Returns the transmuted set and a reduction of the secondary returns of the transmute operations. Can reuse nodes from the transformed set.
165    pub unsafe fn transform_with_transmuted<L: Key + HashLike<K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
166        (&self, right: &HashTrieSet<H, F, L, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (Self, ReduceT)
167        where
168        Self: Sized,
169        ReduceT: Default,
170        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
171        BothOp: Fn(&K, &L) -> SetTransformResult<ReduceT> + Clone,
172        LeftOp: Fn(&K) -> SetTransformResult<ReduceT> + Clone,
173        RightOp: Fn(&L) -> SetTransmuteResult<K, ReduceT> + Clone,
174        K: HashLike<L>,
175        K: PartialEq<L>,
176        L: HashLike<K>,
177        L: PartialEq<K>,
178        M: HasherBv<H, L>,
179    {
180        let (set, reduced) = self.set.transform_with_transmuted(&right.set, reduce_op,
181            |l,_,r,_| both_op(l, r).into(),
182            |l,_| left_op(l).into(),
183            |r,_| match right_op(r) {
184                SetTransmuteResult::Transmuted(key, reduced) => MapTransmuteResult::Transmuted(key, (), reduced),
185                SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
186            });
187        (HashTrieSet{set}, reduced)
188    }
189
190    /// Run a transmute/transform operation on each entry or pair of entries in the sets. Returns the transmuted set and a reduction of the secondary returns of the transmute operations. Can reuse nodes from the transformed set.
191    pub unsafe fn transmute_with_transformed<L: Key + HashLike<K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
192        (&self, right: &HashTrieSet<H, F, L, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (HashTrieSet<H, F, L, M>, ReduceT)
193        where
194        Self: Sized,
195        ReduceT: Default,
196        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
197        BothOp: Fn(&K, &L) -> SetTransformResult<ReduceT> + Clone,
198        LeftOp: Fn(&K) -> SetTransmuteResult<L, ReduceT> + Clone,
199        RightOp: Fn(&L) -> SetTransformResult<ReduceT> + Clone,
200        K: HashLike<L>,
201        K: PartialEq<L>,
202        L: HashLike<K>,
203        L: PartialEq<K>,
204        M: HasherBv<H, L>,
205    {
206        let (set, reduced) = self.set.transmute_with_transformed(&right.set, reduce_op,
207            |l,_,r,_| both_op(l, r).into(),
208            |l,_| match left_op(l) {
209                SetTransmuteResult::Transmuted(key, reduced) => MapTransmuteResult::Transmuted(key, (), reduced),
210                SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
211            },
212            |r,_| right_op(r).into());
213        (HashTrieSet{set}, reduced)
214    }
215
216    /// Run a transmute operation on each entry or pair of entries in the sets. Returns the transmuted set and a reduction of the secondary returns of the transmute operations.
217    pub unsafe fn transmute_with_transmuted<L: Key + HashLike<K>, S: Key + HashLike<K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
218        (&self, right: &HashTrieSet<H, F, L, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (HashTrieSet<H, F, S, M>, ReduceT)
219        where
220        Self: Sized,
221        ReduceT: Default,
222        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
223        BothOp: Fn(&K, &L) -> SetTransmuteResult<S, ReduceT> + Clone,
224        LeftOp: Fn(&K) -> SetTransmuteResult<S, ReduceT> + Clone,
225        RightOp: Fn(&L) -> SetTransmuteResult<S, ReduceT> + Clone,
226        K: HashLike<L>,
227        K: PartialEq<L>,
228        K: HashLike<S>,
229        K: PartialEq<S>,
230        L: HashLike<K>,
231        L: PartialEq<K>,
232        L: HashLike<S>,
233        L: PartialEq<S>,
234        M: HasherBv<H, L>,
235        M: HasherBv<H, S>,
236    {
237        let (set, reduced) = self.set.transmute_with_transmuted(&right.set, reduce_op, |l,_,r,_| match both_op(l, r) {
238            SetTransmuteResult::Transmuted(key, reduced) => MapTransmuteResult::Transmuted(key, (), reduced),
239            SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
240        }, |l,_| match left_op(l) {
241            SetTransmuteResult::Transmuted(key, reduced) => MapTransmuteResult::Transmuted(key, (), reduced),
242            SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
243        }, |r,_| match right_op(r) {
244            SetTransmuteResult::Transmuted(key, reduced) => MapTransmuteResult::Transmuted(key, (), reduced),
245            SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
246        });
247        (HashTrieSet{set}, reduced)
248    }
249
250}
251
252impl <H: Hashword, F: Flagword<H>, K: Key, M: HasherBv<H, K>> Default for HashTrieSet<H, F, K, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
253    fn default() -> Self {
254        Self::new()
255    }
256}
257
258impl <H: Hashword, F: Flagword<H>, K: Key, M: HasherBv<H, K>> Eq for HashTrieSet<H, F, K, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {}
259
260impl <H: Hashword, F: Flagword<H>, K: Key, M: HasherBv<H, K>> PartialEq for HashTrieSet<H, F, K, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
261    fn eq(&self, other: &Self) -> bool {
262        self.set == other.set
263    }
264}
265
266#[cfg(test)]
267mod tests {
268    use crate::*;
269    use rand::Rng;
270    
271    #[test]
272    fn set_transform() {
273        let mut set = DefaultHashTrieSet::<i32>::new();
274
275        for i in 1..101 {
276            set = set.insert(i, false).unwrap().0;
277        }
278
279        let removed = set.transform(|_,_| (), |_| SetTransformResult::Removed(()));
280        let summed = set.transform(|&l,&r| l + r, |&k| SetTransformResult::Removed(k));
281
282        assert_eq!(removed.0.size(), 0);
283        assert_eq!(summed.1, 5050);
284    }
285
286    #[test]
287    fn set_transmute() {
288        let mut set = DefaultHashTrieSet::<i32>::new();
289
290        for i in 1..101 {
291            set = set.insert(i, false).unwrap().0;
292        }
293
294        let removed = unsafe { set.transmute(|_,_| (), |_| SetTransmuteResult::Removed(())) };
295        let summed = unsafe { set.transmute(|&l,&r| l + r, |&k| SetTransmuteResult::Removed(k)) };
296
297        assert_eq!(removed.0.size(), 0);
298        assert_eq!(summed.1, 5050);
299    }
300    
301    #[test]
302    fn set_joint_transformations() {
303        let mut seta = DefaultHashTrieSet::<i32>::new();
304        let mut setb = DefaultHashTrieSet::<i32>::new();
305
306        let mut rng = rand::thread_rng();
307        let a = (0..25000).map(|_| rng.gen_range(0..100000)).collect::<Vec<i32>>();
308        let b = (0..25000).map(|_| rng.gen_range(0..100000)).collect::<Vec<i32>>();
309        for i in a {
310            seta = seta.insert(i, true).unwrap().0;
311        }
312        for i in b {
313            setb = setb.insert(i, true).unwrap().0;
314        }
315
316        let ff = seta.transform_with_transformed(&setb, |l,r| -> i32 {l.wrapping_add(*r)},
317            |l,r| SetJointTransformResult::Removed(l.wrapping_mul(*r)), |l| SetTransformResult::Unchanged(*l), |r| SetTransformResult::Unchanged(*r));
318        let fm = unsafe { seta.transform_with_transmuted(&setb, |l,r| -> i32 {l.wrapping_add(*r)},
319            |l,r| SetTransformResult::Removed(l.wrapping_mul(*r)), |l| SetTransformResult::Unchanged(*l), |r| SetTransmuteResult::Transmuted(*r, *r)) };
320        let mf = unsafe { seta.transmute_with_transformed(&setb, |l,r| -> i32 {l.wrapping_add(*r)},
321            |l,r| SetTransformResult::Removed(l.wrapping_mul(*r)), |l| SetTransmuteResult::Transmuted(*l, *l), |r| SetTransformResult::Unchanged(*r)) };
322        let mm = unsafe { seta.transmute_with_transmuted(&setb, |l,r| -> i32 {l.wrapping_add(*r)},
323            |l,r| SetTransmuteResult::Removed(l.wrapping_mul(*r)), |l| SetTransmuteResult::Transmuted(*l, *l), |r| SetTransmuteResult::Transmuted(*r, *r)) };
324
325        assert_eq!(ff.1, fm.1);
326        assert_eq!(ff.1, mf.1);
327        assert_eq!(ff.1, mm.1);
328
329        let ffx = ff.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |k| SetTransformResult::Removed(*k));
330        let fmx = fm.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |k| SetTransformResult::Removed(*k));
331        let mfx = mf.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |k| SetTransformResult::Removed(*k));
332        let mmx = mm.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |k| SetTransformResult::Removed(*k));
333
334        assert_eq!(ffx.1, fmx.1);
335        assert_eq!(ffx.1, mfx.1);
336        assert_eq!(ffx.1, mmx.1);
337    }
338
339}
hash_trie/set.rs

hash_trie/
set.rs
