quickphf/
set.rs

1//! An immutable set constructed at compile time with perfect hashing.
2use core::hash::Hash;
3
4// TODO: Debug impls
5
6use crate::RawPhfMap;
7
8/// An immutable set constructed at compile time with perfect hashing.
9#[derive(Debug)]
10pub struct PhfSet<K: 'static> {
11    raw_map: RawPhfMap<K, K>,
12}
13
14impl<K> PhfSet<K> {
15    #[doc(hidden)]
16    /// This function is public because it is used by `quickphf_codegen` to
17    /// instantiate the set—users should never directly write calls to it.
18    pub const fn new(
19        seed: u64,
20        pilots_table: &'static [u16],
21        elements: &'static [K],
22        free: &'static [u32],
23    ) -> PhfSet<K> {
24        PhfSet {
25            raw_map: RawPhfMap::new(seed, pilots_table, elements, free),
26        }
27    }
28}
29
30impl<K> PhfSet<K> {
31    /// Returns the number of elements in the set.
32    ///   
33    /// # Examples
34    ///
35    /// ```
36    /// use quickphf::examples::*;
37    ///
38    /// assert_eq!(EVEN_DIGITS.len(), 5);
39    /// assert_eq!(EMPTY_SET.len(), 0);
40    /// ```
41    pub const fn len(&self) -> usize {
42        self.raw_map.len()
43    }
44
45    /// Returns `true` if the set does not contain any elements.
46    ///   
47    /// # Examples
48    ///
49    /// ```
50    /// use quickphf::examples::*;
51    ///
52    /// assert!(!DIGITS.is_empty());
53    /// assert!(EMPTY_SET.is_empty());
54    /// ```
55    pub const fn is_empty(&self) -> bool {
56        self.len() == 0
57    }
58
59    /// Returns an iterator over the elements of the set in no particular order.
60    ///   
61    /// # Examples
62    ///
63    /// ```
64    /// use quickphf::examples::*;
65    ///
66    /// let mut items = EVEN_DIGITS.iter().copied().collect::<Vec<_>>();
67    /// items.sort();
68    ///
69    /// assert_eq!(&items, &[0, 2, 4, 6, 8]);
70    /// ```
71    pub fn iter(&self) -> Iter<'_, K> {
72        Iter {
73            iter: self.raw_map.iter(),
74        }
75    }
76}
77
78impl<K: Eq + Hash> PhfSet<K> {
79    /// Returns `true` if the set contains the given element.
80    ///
81    /// # Examples
82    ///
83    /// ```
84    /// use quickphf::examples::*;
85    ///
86    /// assert!(PRIME_DIGITS.contains(&2));
87    /// assert!(!PRIME_DIGITS.contains(&1));
88    /// ```
89    pub fn contains(&self, element: &K) -> bool {
90        self.get(element).is_some()
91    }
92
93    /// Returns a reference to the copy of the element stored in the set, if
94    /// present.
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// use quickphf::examples::*;
100    ///
101    /// assert_eq!(EVEN_DIGITS.get(&2), Some(&2));
102    /// assert_eq!(EVEN_DIGITS.get(&3), None);
103    /// ```
104    pub fn get(&self, element: &K) -> Option<&K> {
105        if self.is_empty() {
106            return None;
107        }
108
109        let result = self.raw_map.get(element);
110        if result == element {
111            Some(result)
112        } else {
113            None
114        }
115    }
116
117    /// Returns an iterator over the set difference in no particular order.
118    ///
119    /// The iterator yields all items that are in `self` but not in `other`.
120    ///
121    /// # Examples
122    ///
123    /// ```
124    /// use quickphf::examples::*;
125    ///
126    /// let mut difference = EVEN_DIGITS
127    ///     .difference(&PRIME_DIGITS)
128    ///     .copied()
129    ///     .collect::<Vec<_>>();
130    /// difference.sort();
131    ///
132    /// assert_eq!(&difference, &[0, 4, 6, 8]);
133    /// ```
134    pub fn difference<'a>(&'a self, other: &'a PhfSet<K>) -> Difference<'a, K> {
135        Difference {
136            iter: self.iter(),
137            other,
138        }
139    }
140
141    /// Returns an iterator over the intersection in no particular order.
142    ///
143    /// The iterator yields all items that are in both `self` and `other`.
144    ///
145    /// # Examples
146    ///
147    /// ```
148    /// use quickphf::examples::*;
149    ///
150    /// let mut intersection = PRIME_DIGITS.intersection(&EVEN_DIGITS);
151    ///
152    /// assert_eq!(intersection.next(), Some(&2));
153    /// assert!(intersection.next().is_none());
154    /// ```
155    pub fn intersection<'a>(&'a self, other: &'a PhfSet<K>) -> Intersection<'a, K> {
156        Intersection {
157            iter: self.iter(),
158            other,
159        }
160    }
161
162    /// Returns an iterator over the symmetric difference of the two sets in no particular order.
163    ///
164    /// The iterator yields all items that are in `self` but not in `other`, or vice versa.
165    ///
166    /// # Examples
167    ///
168    /// ```
169    /// use quickphf::examples::*;
170    ///
171    /// let mut symmetric_difference = PRIME_DIGITS
172    ///     .symmetric_difference(&EVEN_DIGITS)
173    ///     .copied()
174    ///     .collect::<Vec<_>>();
175    /// symmetric_difference.sort();
176    ///
177    /// assert_eq!(&symmetric_difference, &[0, 3, 4, 5, 6, 7, 8]);
178    /// ```
179    pub fn symmetric_difference<'a>(&'a self, other: &'a PhfSet<K>) -> SymmetricDifference<'a, K> {
180        SymmetricDifference {
181            iter: self.difference(other).chain(other.difference(self)),
182        }
183    }
184
185    /// Returns an iterator over the union in no particular order.
186    ///
187    /// The iterator yields all items that are in `self` or `other`.
188    ///
189    /// # Examples
190    ///
191    /// ```
192    /// use quickphf::examples::*;
193    ///
194    /// let mut union = PRIME_DIGITS
195    ///     .union(&EVEN_DIGITS)
196    ///     .copied()
197    ///     .collect::<Vec<_>>();
198    /// union.sort();
199    ///
200    /// assert_eq!(&union, &[0, 2, 3, 4, 5, 6, 7, 8]);
201    /// ```
202    pub fn union<'a>(&'a self, other: &'a PhfSet<K>) -> Union<'a, K> {
203        Union {
204            iter: self.iter().chain(other.difference(self)),
205        }
206    }
207
208    /// Returns `true` if `self` and `other` have no elements in common.
209    ///
210    /// # Examples
211    ///
212    /// ```
213    /// use quickphf::examples::*;
214    ///
215    /// assert!(!EVEN_DIGITS.is_disjoint(&PRIME_DIGITS));
216    /// ```
217    pub fn is_disjoint(&self, other: &PhfSet<K>) -> bool {
218        self.intersection(other).next().is_none()
219    }
220
221    /// Returns `true` if there are no elements in `self` that are not in `other` as well.
222    ///
223    /// # Examples
224    ///
225    /// ```
226    /// use quickphf::examples::*;
227    ///
228    /// assert!(EVEN_DIGITS.is_subset(&DIGITS));
229    /// ```
230    pub fn is_subset(&self, other: &PhfSet<K>) -> bool {
231        self.difference(other).next().is_none()
232    }
233
234    /// Returns `true` if there are no elements of `other` that are not in `self`.
235    ///
236    /// # Examples
237    ///
238    /// ```
239    /// use quickphf::examples::*;
240    ///
241    /// assert!(DIGITS.is_superset(&EVEN_DIGITS));
242    /// ```
243    pub fn is_superset(&self, other: &PhfSet<K>) -> bool {
244        other.is_subset(self)
245    }
246}
247
248impl<'a, K> IntoIterator for &'a PhfSet<K> {
249    type Item = &'a K;
250    type IntoIter = Iter<'a, K>;
251
252    fn into_iter(self) -> Iter<'a, K> {
253        self.iter()
254    }
255}
256
257impl<K: Eq + Hash> PartialEq for PhfSet<K> {
258    fn eq(&self, other: &Self) -> bool {
259        if self.len() != other.len() {
260            return false;
261        }
262
263        self.iter().all(|k| other.contains(k))
264    }
265}
266
267impl<K: Eq + Hash> Eq for PhfSet<K> {}
268
269#[derive(Clone)]
270/// An iterator over the elements of a `PhfSet`.
271pub struct Iter<'a, K: 'a> {
272    iter: crate::raw_map::Iter<'a, K>,
273}
274
275impl<'a, K> Iterator for Iter<'a, K> {
276    type Item = &'a K;
277
278    fn next(&mut self) -> Option<Self::Item> {
279        self.iter.next()
280    }
281
282    fn size_hint(&self) -> (usize, Option<usize>) {
283        self.iter.size_hint()
284    }
285}
286
287impl<'a, K> ExactSizeIterator for Iter<'a, K> {}
288
289impl<'a, K> core::iter::FusedIterator for Iter<'a, K> {}
290
291#[derive(Clone)]
292/// A lazy iterator producing elements from the difference of two `PhfSets`s.
293pub struct Difference<'a, K: 'static> {
294    iter: Iter<'a, K>,
295    other: &'a PhfSet<K>,
296}
297
298impl<'a, K> Iterator for Difference<'a, K>
299where
300    K: Eq + Hash,
301{
302    type Item = &'a K;
303
304    fn next(&mut self) -> Option<Self::Item> {
305        self.iter.by_ref().find(|&k| !self.other.contains(k))
306    }
307
308    fn size_hint(&self) -> (usize, Option<usize>) {
309        let self_size = self.iter.size_hint().0;
310        let other_size = self.other.len();
311        let min_size = self_size.saturating_sub(other_size);
312
313        (min_size, Some(self_size))
314    }
315}
316
317impl<'a, K> core::iter::FusedIterator for Difference<'a, K> where K: Eq + Hash {}
318
319#[derive(Clone)]
320/// A lazy iterator producing elements from the intersection of two `PhfSet`s.
321pub struct Intersection<'a, K: 'static> {
322    iter: Iter<'a, K>,
323    other: &'a PhfSet<K>,
324}
325
326impl<'a, K> Iterator for Intersection<'a, K>
327where
328    K: Eq + Hash,
329{
330    type Item = &'a K;
331
332    fn next(&mut self) -> Option<Self::Item> {
333        self.iter.by_ref().find(|&k| self.other.contains(k))
334    }
335
336    fn size_hint(&self) -> (usize, Option<usize>) {
337        let self_size = self.iter.size_hint().0;
338        let other_size = self.other.len();
339        let max_size = usize::min(self_size, other_size);
340
341        (0, Some(max_size))
342    }
343}
344
345impl<'a, K> core::iter::FusedIterator for Intersection<'a, K> where K: Eq + Hash {}
346
347#[derive(Clone)]
348/// A lazy iterator producing elements from the symmetric difference of two `PhfSet`s.
349pub struct SymmetricDifference<'a, K: 'static> {
350    iter: core::iter::Chain<Difference<'a, K>, Difference<'a, K>>,
351}
352
353impl<'a, K> Iterator for SymmetricDifference<'a, K>
354where
355    K: Eq + Hash,
356{
357    type Item = &'a K;
358
359    fn next(&mut self) -> Option<Self::Item> {
360        self.iter.next()
361    }
362
363    fn size_hint(&self) -> (usize, Option<usize>) {
364        self.iter.size_hint()
365    }
366}
367
368impl<'a, K> core::iter::FusedIterator for SymmetricDifference<'a, K> where K: Eq + Hash {}
369
370#[derive(Clone)]
371/// A lazy iterator producing elements from the union of two `PhfSet`s.
372pub struct Union<'a, K: 'static> {
373    iter: core::iter::Chain<Iter<'a, K>, Difference<'a, K>>,
374}
375
376impl<'a, K> Iterator for Union<'a, K>
377where
378    K: Eq + Hash,
379{
380    type Item = &'a K;
381
382    fn next(&mut self) -> Option<Self::Item> {
383        self.iter.next()
384    }
385
386    fn size_hint(&self) -> (usize, Option<usize>) {
387        self.iter.size_hint()
388    }
389}
390
391impl<'a, K> core::iter::FusedIterator for Union<'a, K> where K: Eq + Hash {}
392
393#[cfg(test)]
394mod tests {
395    use crate::examples::EMPTY_SET;
396
397    use super::*;
398
399    #[test]
400    fn test_empty() {
401        assert_eq!(EMPTY_SET.get(&17), None);
402        assert!(!EMPTY_SET.contains(&620));
403        assert!(EMPTY_SET.iter().next().is_none())
404    }
405
406    #[test]
407    fn test_sync() {
408        fn assert_sync<T: Sync>() {}
409        assert_sync::<PhfSet<u64>>();
410    }
411}
quickphf/set.rs

quickphf/
set.rs
