ordinal_map/map/
array_map.rs

1use std::fmt;
2use std::fmt::Debug;
3
4use crate::map::iter::IntoIterArray;
5use crate::map::iter::Iter;
6use crate::map::iter::IterMut;
7use crate::map::iter::ValuesMut;
8use crate::map::total::array_map::OrdinalTotalArrayMap;
9use crate::map::Drain;
10use crate::map::Entry;
11use crate::map::Keys;
12use crate::map::Values;
13use crate::Ordinal;
14
15/// Map backed by an array, allocated on the stack.
16///
17/// Due to Rust limitations, the array size must be provided as a type parameter.
18///
19/// # Example
20///
21/// ```
22/// use ordinal_map::map::OrdinalArrayMap;
23/// use ordinal_map::Ordinal;
24/// #[derive(Ordinal)]
25/// enum Weather {
26///     Sunny,
27///     Rainy,
28///     Snowy,
29/// }
30///
31/// let mut map = OrdinalArrayMap::<_, _, { Weather::ORDINAL_SIZE }>::new();
32/// map.insert(Weather::Sunny, "good");
33/// map.insert(Weather::Rainy, "it depends");
34/// ```
35///
36/// This map is sparse (not every key has an associated value).
37/// For a total map, see [`OrdinalTotalMap`](crate::map::total::OrdinalTotalMap)
38/// and [`OrdinalTotalArrayMap`](OrdinalTotalArrayMap).
39pub struct OrdinalArrayMap<K, V, const S: usize> {
40    map: OrdinalTotalArrayMap<K, Option<V>, S>,
41}
42
43impl<K: Ordinal, V, const S: usize> OrdinalArrayMap<K, V, S> {
44    /// Create a new map.
45    #[inline]
46    pub fn new() -> Self {
47        OrdinalArrayMap {
48            map: OrdinalTotalArrayMap::new(|_| None),
49        }
50    }
51
52    /// The number of elements in the map.
53    ///
54    /// This operation is `O(K::ORDINAL_SIZE)`.
55    #[inline]
56    pub fn len(&self) -> usize {
57        self.iter().count()
58    }
59
60    /// Return true if the map container no elements.
61    pub fn is_empty(&self) -> bool {
62        self.iter().next().is_none()
63    }
64
65    /// Look up a value by key.
66    #[inline]
67    pub fn get<'a>(&'a self, key: &K) -> Option<&'a V> {
68        self.map.get(key).as_ref()
69    }
70
71    /// Look up a value by key.
72    #[inline]
73    pub fn get_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
74        self.map.get_mut(key).as_mut()
75    }
76
77    /// Check if the map contains a key.
78    #[inline]
79    pub fn contains_key(&self, key: &K) -> bool {
80        self.get(key).is_some()
81    }
82
83    /// Insert a value into the map, returning the previous value if it existed.
84    #[inline]
85    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
86        self.map.get_mut(&key).replace(value)
87    }
88
89    /// Get an entry in the map for the given key.
90    #[inline]
91    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
92        let entry = &mut self.map[&key];
93        Entry::new(key, entry)
94    }
95
96    /// Remove a value from the map, returning it if it existed.
97    #[inline]
98    pub fn remove(&mut self, key: &K) -> Option<V> {
99        self.map.get_mut(key).take()
100    }
101
102    /// Iterate over the map.
103    #[inline]
104    pub fn iter<'a>(&'a self) -> Iter<'a, K, V> {
105        Iter::new(self.map.iter())
106    }
107
108    /// Iterate over the map mutably.
109    #[inline]
110    pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, K, V> {
111        IterMut::new(self.map.iter_mut())
112    }
113
114    /// Iterate over the keys of the map.
115    #[inline]
116    pub fn keys(&self) -> Keys<'_, K, V> {
117        Keys::new(self.iter())
118    }
119
120    /// Iterate over the values of the map.
121    #[inline]
122    pub fn values(&self) -> Values<'_, K, V> {
123        Values::new(self.iter())
124    }
125
126    /// Iterate over the values of the map mutably.
127    #[inline]
128    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
129        ValuesMut::new(self.iter_mut())
130    }
131
132    /// Remove all elements from the map.
133    #[inline]
134    pub fn drain(&mut self) -> Drain<'_, K, V> {
135        Drain::new(self.map.iter_mut())
136    }
137
138    /// Remove all elements from the map.
139    #[inline]
140    pub fn clear(&mut self) {
141        self.drain();
142    }
143
144    /// Retain only the elements specified by the predicate.
145    pub fn retain<F>(&mut self, mut f: F)
146    where
147        F: FnMut(K, &mut V) -> bool,
148    {
149        for (key, value_opt) in self.map.iter_mut() {
150            if let Some(value) = value_opt {
151                if !f(key, value) {
152                    *value_opt = None;
153                }
154            }
155        }
156    }
157}
158
159impl<K: Ordinal, V, const S: usize> Default for OrdinalArrayMap<K, V, S> {
160    #[inline]
161    fn default() -> Self {
162        OrdinalArrayMap::new()
163    }
164}
165
166impl<K: Ordinal, V, const S: usize> FromIterator<(K, V)> for OrdinalArrayMap<K, V, S> {
167    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
168        let mut map = OrdinalArrayMap::new();
169        for (key, value) in iter {
170            map.insert(key, value);
171        }
172        map
173    }
174}
175
176impl<K: Ordinal, V: Clone, const S: usize> Clone for OrdinalArrayMap<K, V, S> {
177    fn clone(&self) -> Self {
178        OrdinalArrayMap {
179            map: self.map.clone(),
180        }
181    }
182}
183
184impl<K: Ordinal + Debug, V: Debug, const S: usize> Debug for OrdinalArrayMap<K, V, S> {
185    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
186        f.debug_map().entries(self.iter()).finish()
187    }
188}
189
190impl<K: Ordinal, V, const S: usize> IntoIterator for OrdinalArrayMap<K, V, S> {
191    type Item = (K, V);
192    type IntoIter = IntoIterArray<K, V, S>;
193
194    #[inline]
195    fn into_iter(self) -> Self::IntoIter {
196        IntoIterArray::new(self.map.into_iter())
197    }
198}
199
200impl<'a, K: Ordinal, V, const S: usize> IntoIterator for &'a OrdinalArrayMap<K, V, S> {
201    type Item = (K, &'a V);
202    type IntoIter = Iter<'a, K, V>;
203
204    #[inline]
205    fn into_iter(self) -> Self::IntoIter {
206        self.iter()
207    }
208}
209
210#[cfg(test)]
211mod tests {
212    use std::collections::HashMap;
213    use std::collections::HashSet;
214
215    use crate::map::OrdinalArrayMap;
216    use crate::Ordinal;
217
218    #[quickcheck]
219    fn qc(values: Vec<(u8, u32)>, check: Vec<u8>) {
220        let mut map: OrdinalArrayMap<u8, u32, { u8::ORDINAL_SIZE }> = OrdinalArrayMap::new();
221        let mut control: HashMap<u8, u32> = HashMap::new();
222
223        for (key, value) in &values {
224            let control_inserted = control.insert(*key, *value);
225            let inserted = map.insert(*key, *value);
226            assert_eq!(control_inserted, inserted);
227            assert_eq!(control.len(), map.len());
228        }
229
230        for key in &check {
231            assert_eq!(control.get(key), map.get(key));
232        }
233    }
234
235    #[quickcheck]
236    fn qc_retain(values: Vec<(u8, u32)>, retain: Vec<u8>) -> bool {
237        let retain: HashSet<u8> = HashSet::from_iter(retain);
238
239        let mut map = OrdinalArrayMap::<u8, u32, { u8::ORDINAL_SIZE }>::from_iter(values.clone());
240        let mut control: HashMap<u8, u32> = HashMap::from_iter(values);
241
242        map.retain(|key, _| retain.contains(&key));
243        control.retain(|key, _| retain.contains(key));
244
245        control == HashMap::from_iter(map)
246    }
247}
ordinal_map/map/array_map.rs

ordinal_map/map/
array_map.rs
