ordinal_map/set/
set64.rs

1use std::fmt;
2use std::fmt::Debug;
3use std::fmt::Formatter;
4use std::marker::PhantomData;
5use std::slice;
6
7use crate::set::set_ref::OrdinalSetRef;
8use crate::Ordinal;
9
10/// Iterator over [`OrdinalSet64`].
11pub struct Iter64<T> {
12    set: u64,
13    _phantom: PhantomData<T>,
14}
15
16impl<T: Ordinal> Iterator for Iter64<T> {
17    type Item = T;
18
19    #[inline]
20    fn next(&mut self) -> Option<Self::Item> {
21        let ordinal = self.set.trailing_zeros();
22        if ordinal == u64::BITS {
23            None
24        } else {
25            self.set &= !(1 << ordinal);
26            Some(T::from_ordinal(ordinal as usize).unwrap())
27        }
28    }
29
30    #[inline]
31    fn size_hint(&self) -> (usize, Option<usize>) {
32        let len = self.len();
33        (len, Some(len))
34    }
35}
36
37impl<T: Ordinal> ExactSizeIterator for Iter64<T> {
38    #[inline]
39    fn len(&self) -> usize {
40        self.set.count_ones() as usize
41    }
42}
43
44impl<T: Ordinal> DoubleEndedIterator for Iter64<T> {
45    #[inline]
46    fn next_back(&mut self) -> Option<Self::Item> {
47        let ordinal = (u64::BITS - 1).checked_sub(self.set.leading_zeros())?;
48        self.set &= !(1 << ordinal);
49        Some(T::from_ordinal(ordinal as usize).unwrap())
50    }
51}
52
53impl<T> Clone for Iter64<T> {
54    #[inline]
55    fn clone(&self) -> Self {
56        Iter64 {
57            set: self.set,
58            _phantom: PhantomData,
59        }
60    }
61}
62
63impl<T: Ordinal + Debug> Debug for Iter64<T> {
64    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
65        f.debug_list().entries(self.clone()).finish()
66    }
67}
68
69/// Set for implementations of [`Ordinal`](crate::Ordinal) with a maximum ordinal size of 64.
70///
71/// This is implemented using a single `u64` value to store the set of elements.
72/// To store set of arbitrary size, consider using [`OrdinalSet`](crate::set::OrdinalSet).
73#[derive(Eq, PartialEq)]
74pub struct OrdinalSet64<T> {
75    set: u64,
76    _phantom: PhantomData<T>,
77}
78
79impl<T: Ordinal> OrdinalSet64<T> {
80    const ASSERT: () = {
81        assert!(T::ORDINAL_SIZE <= u64::BITS as usize);
82    };
83
84    /// Create a new empty set.
85    #[inline]
86    pub const fn new() -> Self {
87        const { Self::ASSERT };
88        OrdinalSet64 {
89            set: 0,
90            _phantom: PhantomData,
91        }
92    }
93
94    fn as_ref(&self) -> OrdinalSetRef<'_, T> {
95        OrdinalSetRef::new(slice::from_ref(&self.set))
96    }
97
98    /// Create a set containing all possible elements of [`K`](Ordinal).
99    #[inline]
100    pub fn all() -> Self {
101        const { Self::ASSERT };
102        OrdinalSet64 {
103            set: (1 << T::ORDINAL_SIZE) - 1,
104            _phantom: PhantomData,
105        }
106    }
107
108    /// Insert an element into the set, returning `true` if the element was not already present.
109    #[inline]
110    pub fn insert(&mut self, ordinal: T) -> bool {
111        const { Self::ASSERT };
112        let r = !self.contains(&ordinal);
113        self.set |= 1 << ordinal.ordinal();
114        r
115    }
116
117    /// Iterate over the elements of the set.
118    #[inline]
119    pub fn iter(&self) -> Iter64<T> {
120        const { Self::ASSERT };
121        Iter64 {
122            set: self.set,
123            _phantom: PhantomData,
124        }
125    }
126
127    /// Check if the set contains an element.
128    #[inline]
129    pub fn contains(&self, ordinal: &T) -> bool {
130        const { Self::ASSERT };
131        self.set & (1 << ordinal.ordinal()) != 0
132    }
133}
134
135impl<T: Ordinal> Default for OrdinalSet64<T> {
136    fn default() -> Self {
137        OrdinalSet64::new()
138    }
139}
140
141impl<T: Ordinal> FromIterator<T> for OrdinalSet64<T> {
142    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
143        let mut set = OrdinalSet64::new();
144        for ordinal in iter {
145            set.set |= 1 << ordinal.ordinal();
146        }
147        set
148    }
149}
150
151impl<T> Clone for OrdinalSet64<T> {
152    fn clone(&self) -> Self {
153        OrdinalSet64 {
154            set: self.set,
155            _phantom: PhantomData,
156        }
157    }
158}
159
160impl<T: Ordinal + Debug> Debug for OrdinalSet64<T> {
161    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
162        Debug::fmt(&self.as_ref(), f)
163    }
164}
165
166#[cfg(test)]
167mod tests {
168    use crate::set::OrdinalSet64;
169    use crate::tests::util::test_exact_size_iterator;
170    use crate::tests::util::Example4;
171
172    // Fails at compilation time (as expected).
173    // #[test]
174    // fn test_more_than_64() {
175    //     Set64::<u8>::new();
176    // }
177
178    #[test]
179    fn test_all() {
180        let set = OrdinalSet64::<Example4>::all();
181        assert_eq!(set.set, 0b1111);
182    }
183
184    #[quickcheck]
185    fn qc_iterator(mut values: Vec<Example4>) -> bool {
186        let set = OrdinalSet64::from_iter(values.iter().copied());
187        values.sort();
188        values.dedup();
189        set.iter().collect::<Vec<_>>() == values
190    }
191
192    #[quickcheck]
193    fn qc_double_ended_iterator(mut values: Vec<Example4>) -> bool {
194        let set = OrdinalSet64::from_iter(values.iter().copied());
195        values.sort();
196        values.dedup();
197        set.iter().rev().collect::<Vec<_>>() == values.into_iter().rev().collect::<Vec<_>>()
198    }
199
200    #[quickcheck]
201    fn qc_exact_size_iterator(values: Vec<Example4>) {
202        test_exact_size_iterator(OrdinalSet64::from_iter(values).iter());
203    }
204}
ordinal_map/set/set64.rs

ordinal_map/set/
set64.rs
