ordinal_map/set/
array.rs

1use std::fmt;
2use std::fmt::Debug;
3use std::marker::PhantomData;
4
5use crate::set::set_mut::OrdinalSetMut;
6use crate::set::set_ref::OrdinalSetRef;
7use crate::Ordinal;
8
9/// Compute the size of `S` parameter for [`OrdinalArraySet`](crate::set::OrdinalArraySet).
10/// This is simply `(T::ORDINAL_SIZE + 63) / 64`.
11pub const fn ordinal_array_set_s<T: Ordinal>() -> usize {
12    T::ORDINAL_SIZE.div_ceil(u64::BITS as usize)
13}
14
15/// Set of ordinals implemented as an array of words.
16///
17/// # Size parameter
18///
19/// Parameter `S` must be explicitly specified as
20/// [`ordinal_array_set_s::<T>()`](ordinal_array_set_s)
21/// due to limitations of const generics in stable Rust.
22///
23/// If this is not convenient, consider using:
24/// - [`OrdinalSet64`](crate::set::OrdinalSet64) for types where `T::ORDINAL_SIZE <= 64`.
25/// - [`OrdinalSet`](crate::set::OrdinalSet) which allocates storage dynamically.
26///
27/// # Example
28///
29/// ```
30/// use ordinal_map::set::ordinal_array_set_s;
31/// use ordinal_map::set::OrdinalArraySet;
32/// let mut set: OrdinalArraySet<u8, { ordinal_array_set_s::<u8>() }> = OrdinalArraySet::new();
33///
34/// set.insert(17);
35/// ```
36pub struct OrdinalArraySet<T, const S: usize> {
37    words: [u64; S],
38    _phantom: PhantomData<T>,
39}
40
41impl<T: Ordinal, const S: usize> OrdinalArraySet<T, S> {
42    const ASSERT: () = assert!(S == ordinal_array_set_s::<T>());
43
44    /// Create a new empty set.
45    #[inline]
46    pub fn new() -> Self {
47        const { Self::ASSERT };
48        OrdinalArraySet::default()
49    }
50
51    #[inline]
52    fn as_ref(&self) -> OrdinalSetRef<'_, T> {
53        const { Self::ASSERT };
54        OrdinalSetRef::new(&self.words)
55    }
56
57    #[inline]
58    fn as_mut(&mut self) -> OrdinalSetMut<'_, T> {
59        const { Self::ASSERT };
60        OrdinalSetMut::new(&mut self.words)
61    }
62
63    /// Check if the set contains an ordinal.
64    #[inline]
65    pub fn contains(&self, ordinal: &T) -> bool {
66        self.as_ref().contains(ordinal)
67    }
68
69    /// Insert an ordinal into the set, returning `true` if the ordinal was not already present.
70    #[inline]
71    pub fn insert(&mut self, ordinal: T) -> bool {
72        self.as_mut().insert(ordinal)
73    }
74}
75
76impl<T, const S: usize> Default for OrdinalArraySet<T, S> {
77    #[inline]
78    fn default() -> Self {
79        OrdinalArraySet {
80            words: [0; S],
81            _phantom: PhantomData,
82        }
83    }
84}
85
86impl<T: Ordinal, const S: usize> FromIterator<T> for OrdinalArraySet<T, S> {
87    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
88        let mut set = OrdinalArraySet::new();
89        for value in iter {
90            set.insert(value);
91        }
92        set
93    }
94}
95
96impl<T, const S: usize> Clone for OrdinalArraySet<T, S> {
97    fn clone(&self) -> Self {
98        OrdinalArraySet {
99            words: self.words,
100            _phantom: PhantomData,
101        }
102    }
103}
104
105impl<T: Ordinal + Debug, const S: usize> Debug for OrdinalArraySet<T, S> {
106    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
107        Debug::fmt(&self.as_ref(), f)
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use std::collections::HashSet;
114
115    use crate::set::array::ordinal_array_set_s;
116    use crate::set::OrdinalArraySet;
117
118    #[quickcheck]
119    fn qc_insert(values: Vec<i8>, check: Vec<i8>) {
120        let mut control: HashSet<i8> = HashSet::new();
121        let mut set: OrdinalArraySet<i8, { ordinal_array_set_s::<i8>() }> = OrdinalArraySet::new();
122
123        for &value in &values {
124            assert_eq!(control.insert(value), set.insert(value));
125        }
126
127        for &value in &check {
128            assert_eq!(control.contains(&value), set.contains(&value));
129        }
130    }
131}
ordinal_map/set/array.rs

ordinal_map/set/
array.rs
