ordinal_map/set/
set.rs

1use std::fmt;
2use std::fmt::Debug;
3use std::fmt::Formatter;
4use std::marker::PhantomData;
5use std::slice;
6
7use crate::set::iter::Iter;
8use crate::set::set_mut::OrdinalSetMut;
9use crate::set::set_ref::OrdinalSetRef;
10use crate::Ordinal;
11
12#[derive(Clone)]
13enum SetImpl {
14    Small(u64),
15    Large(Box<[u64]>),
16}
17
18/// Default set implementation.
19///
20/// All operations are constant time
21/// (provided that [`T::ordinal()`](Ordinal::ordinal) is constant time).
22///
23/// This map allocates memory when the number of elements is greater than 64.
24/// When the number of elements is known to be less than or equal to 64,
25/// consider using [`Set64`](crate::set::OrdinalSet64) instead.
26pub struct OrdinalSet<T> {
27    set: SetImpl,
28    _phantom: PhantomData<T>,
29}
30
31impl<T: Ordinal> OrdinalSet<T> {
32    const IS_SMALL: bool = T::ORDINAL_SIZE <= u64::BITS as usize;
33
34    /// Create a new empty set.
35    #[inline]
36    pub fn new() -> Self {
37        OrdinalSet {
38            set: if Self::IS_SMALL {
39                SetImpl::Small(0)
40            } else {
41                SetImpl::Large(Vec::<u64>::new().into_boxed_slice())
42            },
43            _phantom: PhantomData,
44        }
45    }
46
47    #[inline]
48    fn as_ref(&self) -> OrdinalSetRef<'_, T> {
49        match (Self::IS_SMALL, &self.set) {
50            (true, SetImpl::Small(set)) => OrdinalSetRef::new(slice::from_ref(set)),
51            (false, SetImpl::Large(set)) => OrdinalSetRef::new(set),
52            _ => unreachable!(),
53        }
54    }
55
56    /// Check if the set contains an element.
57    #[inline]
58    pub fn contains(&self, ordinal: &T) -> bool {
59        self.as_ref().contains(ordinal)
60    }
61
62    /// Insert an element into the set, returning `true` if the element was not already present.
63    #[inline]
64    pub fn insert(&mut self, ordinal: T) -> bool {
65        match (Self::IS_SMALL, &mut self.set) {
66            (true, SetImpl::Small(set)) => OrdinalSetMut::new(slice::from_mut(set)).insert(ordinal),
67            (false, SetImpl::Large(set)) => {
68                if set.is_empty() {
69                    *set = vec![
70                        0;
71                        (T::ORDINAL_SIZE.checked_add(u64::BITS as usize).unwrap() - 1)
72                            / u64::BITS as usize
73                    ]
74                    .into_boxed_slice();
75                }
76                OrdinalSetMut::new(set).insert(ordinal)
77            }
78            _ => unreachable!(),
79        }
80    }
81
82    /// Iterate over the elements of the set.
83    #[inline]
84    pub fn iter(&self) -> Iter<'_, T> {
85        self.as_ref().iter()
86    }
87}
88
89impl<T: Ordinal> Default for OrdinalSet<T> {
90    fn default() -> Self {
91        Self::new()
92    }
93}
94
95impl<T: Ordinal> FromIterator<T> for OrdinalSet<T> {
96    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
97        let mut set = OrdinalSet::new();
98        for ordinal in iter {
99            set.insert(ordinal);
100        }
101        set
102    }
103}
104
105impl<T> Clone for OrdinalSet<T> {
106    fn clone(&self) -> Self {
107        OrdinalSet {
108            set: self.set.clone(),
109            _phantom: PhantomData,
110        }
111    }
112}
113
114impl<T: Ordinal + Debug> Debug for OrdinalSet<T> {
115    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
116        Debug::fmt(&self.as_ref(), f)
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use std::collections::HashSet;
123    use std::num::NonZeroU16;
124
125    use crate::set::OrdinalSet;
126    use crate::tests::util::Example4;
127
128    #[quickcheck]
129    fn qc_insert_small(values: Vec<Example4>, check: Vec<Example4>) {
130        let mut set: OrdinalSet<Example4> = OrdinalSet::new();
131        let mut control: HashSet<Example4> = HashSet::new();
132        for value in &values {
133            let control_inserted = control.insert(*value);
134            let inserted = set.insert(*value);
135            assert_eq!(control_inserted, inserted);
136        }
137
138        for value in &check {
139            assert_eq!(control.contains(value), set.contains(value));
140        }
141    }
142
143    #[quickcheck]
144    fn qc_insert_large(values: Vec<NonZeroU16>, check: Vec<NonZeroU16>) {
145        let mut set: OrdinalSet<NonZeroU16> = OrdinalSet::new();
146        let mut control: HashSet<NonZeroU16> = HashSet::new();
147        for value in &values {
148            let control_inserted = control.insert(*value);
149            let inserted = set.insert(*value);
150            assert_eq!(control_inserted, inserted);
151        }
152
153        for value in &check {
154            assert_eq!(control.contains(value), set.contains(value));
155        }
156    }
157
158    #[quickcheck]
159    fn qc_iter_small(mut values: Vec<Example4>) -> bool {
160        let set = OrdinalSet::from_iter(values.iter().copied());
161        values.sort();
162        values.dedup();
163        set.iter().collect::<Vec<_>>() == values
164    }
165
166    #[quickcheck]
167    fn qc_iter_large(mut values: Vec<NonZeroU16>) -> bool {
168        let set = OrdinalSet::from_iter(values.iter().copied());
169        values.sort();
170        values.dedup();
171        set.iter().collect::<Vec<_>>() == values
172    }
173}
ordinal_map/set/set.rs

ordinal_map/set/
set.rs
