reliakit_collections/
bounded_map.rs

1use crate::{CollectionError, CollectionResult};
2use alloc::vec::Vec;
3use core::mem;
4
5/// Owned key-value map constrained by inclusive entry-count bounds.
6///
7/// `BoundedMap<K, V, MIN, MAX>` guarantees that the number of entries is always
8/// in the range `MIN..=MAX` and that every key is unique. It is backed by a
9/// `Vec<(K, V)>` in insertion order, so iteration is deterministic and pulls in
10/// no hashing or ordering machinery — lookups are a linear scan, which is fine
11/// for the small, bounded sizes this type is meant for.
12///
13/// Mutations that would violate the bounds return a [`CollectionError`] instead
14/// of panicking. Construction rejects duplicate keys with
15/// [`CollectionError::Duplicate`].
16///
17/// # Const parameters
18///
19/// - `MIN`: minimum number of entries (inclusive). Use `0` for no lower bound.
20/// - `MAX`: maximum number of entries (inclusive).
21///
22/// Construction fails with [`CollectionError::InvalidBounds`] if `MIN > MAX`.
23///
24/// # Equality
25///
26/// Equality is order-sensitive: two maps with the same entries inserted in a
27/// different order are not equal, matching the insertion-order semantics.
28#[derive(Debug, Clone, PartialEq, Eq, Hash)]
29pub struct BoundedMap<K, V, const MIN: usize, const MAX: usize>(Vec<(K, V)>);
30
31impl<K, V, const MIN: usize, const MAX: usize> BoundedMap<K, V, MIN, MAX> {
32    /// Returns the number of entries.
33    pub fn len(&self) -> usize {
34        self.0.len()
35    }
36
37    /// Returns `true` if the map contains no entries.
38    ///
39    /// Always returns `false` when `MIN > 0`, since construction guarantees at
40    /// least `MIN` entries.
41    pub fn is_empty(&self) -> bool {
42        self.0.is_empty()
43    }
44
45    /// Returns an iterator over the `(K, V)` entries in insertion order.
46    pub fn iter(&self) -> core::slice::Iter<'_, (K, V)> {
47        self.0.iter()
48    }
49
50    /// Returns an iterator over the keys in insertion order.
51    pub fn keys(&self) -> impl Iterator<Item = &K> {
52        self.0.iter().map(|(k, _)| k)
53    }
54
55    /// Returns an iterator over the values in insertion order.
56    pub fn values(&self) -> impl Iterator<Item = &V> {
57        self.0.iter().map(|(_, v)| v)
58    }
59
60    /// Returns the entries as a slice in insertion order.
61    pub fn as_slice(&self) -> &[(K, V)] {
62        &self.0
63    }
64
65    /// Consumes the wrapper and returns the inner `Vec<(K, V)>`.
66    pub fn into_inner(self) -> Vec<(K, V)> {
67        self.0
68    }
69
70    /// Returns the minimum allowed number of entries.
71    pub const fn min_len() -> usize {
72        MIN
73    }
74
75    /// Returns the maximum allowed number of entries.
76    pub const fn max_len() -> usize {
77        MAX
78    }
79}
80
81impl<K: PartialEq, V, const MIN: usize, const MAX: usize> BoundedMap<K, V, MIN, MAX> {
82    /// Creates a `BoundedMap` from a vector of entries.
83    ///
84    /// Returns an error if the bounds are invalid (`MIN > MAX`), the entry count
85    /// is out of range, or two entries share a key.
86    pub fn new(entries: Vec<(K, V)>) -> CollectionResult<Self> {
87        if MIN > MAX {
88            return Err(CollectionError::InvalidBounds { min: MIN, max: MAX });
89        }
90        let actual = entries.len();
91        if actual < MIN {
92            return Err(CollectionError::TooFew { min: MIN, actual });
93        }
94        if actual > MAX {
95            return Err(CollectionError::TooMany { max: MAX, actual });
96        }
97        for i in 0..entries.len() {
98            for j in (i + 1)..entries.len() {
99                if entries[i].0 == entries[j].0 {
100                    return Err(CollectionError::Duplicate);
101                }
102            }
103        }
104        Ok(Self(entries))
105    }
106
107    /// Inserts a key-value pair.
108    ///
109    /// If the key already exists, its value is replaced and the old value is
110    /// returned as `Ok(Some(old))` (the entry count does not change). If the key
111    /// is new, it is appended and `Ok(None)` is returned, unless the map is
112    /// already at capacity (`len == MAX`), in which case
113    /// [`CollectionError::TooMany`] is returned and nothing changes.
114    pub fn insert(&mut self, key: K, value: V) -> CollectionResult<Option<V>> {
115        if let Some(entry) = self.0.iter_mut().find(|entry| entry.0 == key) {
116            return Ok(Some(mem::replace(&mut entry.1, value)));
117        }
118        if self.0.len() >= MAX {
119            return Err(CollectionError::TooMany {
120                max: MAX,
121                actual: self.0.len().saturating_add(1),
122            });
123        }
124        self.0.push((key, value));
125        Ok(None)
126    }
127
128    /// Removes the entry for `key`, returning its value.
129    ///
130    /// Returns `Ok(None)` if the key is absent (no change). Returns
131    /// [`CollectionError::TooFew`] if removing would bring the entry count below
132    /// `MIN`, leaving the map unchanged.
133    pub fn remove(&mut self, key: &K) -> CollectionResult<Option<V>> {
134        let Some(idx) = self.0.iter().position(|entry| &entry.0 == key) else {
135            return Ok(None);
136        };
137        let after_remove = self.0.len() - 1;
138        if after_remove < MIN {
139            return Err(CollectionError::TooFew {
140                min: MIN,
141                actual: after_remove,
142            });
143        }
144        let (_, value) = self.0.remove(idx);
145        Ok(Some(value))
146    }
147
148    /// Returns a reference to the value for `key`, or `None` if absent.
149    pub fn get(&self, key: &K) -> Option<&V> {
150        self.0
151            .iter()
152            .find(|entry| &entry.0 == key)
153            .map(|entry| &entry.1)
154    }
155
156    /// Returns a mutable reference to the value for `key`, or `None` if absent.
157    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
158        self.0
159            .iter_mut()
160            .find(|entry| &entry.0 == key)
161            .map(|entry| &mut entry.1)
162    }
163
164    /// Returns `true` if the map contains `key`.
165    pub fn contains_key(&self, key: &K) -> bool {
166        self.0.iter().any(|entry| &entry.0 == key)
167    }
168}
169
170impl<K: PartialEq, V, const MIN: usize, const MAX: usize> TryFrom<Vec<(K, V)>>
171    for BoundedMap<K, V, MIN, MAX>
172{
173    type Error = CollectionError;
174
175    fn try_from(entries: Vec<(K, V)>) -> Result<Self, Self::Error> {
176        Self::new(entries)
177    }
178}
179
180impl<K, V, const MIN: usize, const MAX: usize> From<BoundedMap<K, V, MIN, MAX>> for Vec<(K, V)> {
181    fn from(value: BoundedMap<K, V, MIN, MAX>) -> Self {
182        value.into_inner()
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use super::BoundedMap;
189    use crate::CollectionError;
190
191    fn map_3() -> BoundedMap<&'static str, i32, 0, 3> {
192        BoundedMap::new(alloc::vec![("a", 1), ("b", 2)]).unwrap()
193    }
194
195    #[test]
196    fn accepts_valid_entries() {
197        let m = map_3();
198        assert_eq!(m.len(), 2);
199        assert!(!m.is_empty());
200        assert_eq!(m.get(&"a"), Some(&1));
201        assert_eq!(m.get(&"b"), Some(&2));
202        assert_eq!(m.get(&"z"), None);
203    }
204
205    #[test]
206    fn rejects_duplicate_keys() {
207        assert_eq!(
208            BoundedMap::<&str, i32, 0, 5>::new(alloc::vec![("a", 1), ("a", 2)]).unwrap_err(),
209            CollectionError::Duplicate
210        );
211    }
212
213    #[test]
214    fn rejects_too_few() {
215        assert_eq!(
216            BoundedMap::<&str, i32, 2, 5>::new(alloc::vec![("a", 1)]).unwrap_err(),
217            CollectionError::TooFew { min: 2, actual: 1 }
218        );
219    }
220
221    #[test]
222    fn rejects_too_many() {
223        assert_eq!(
224            BoundedMap::<&str, i32, 0, 1>::new(alloc::vec![("a", 1), ("b", 2)]).unwrap_err(),
225            CollectionError::TooMany { max: 1, actual: 2 }
226        );
227    }
228
229    #[test]
230    fn rejects_invalid_bounds() {
231        assert_eq!(
232            BoundedMap::<&str, i32, 5, 3>::new(alloc::vec![]).unwrap_err(),
233            CollectionError::InvalidBounds { min: 5, max: 3 }
234        );
235    }
236
237    #[test]
238    fn insert_new_key_appends() {
239        let mut m = map_3();
240        assert_eq!(m.insert("c", 3).unwrap(), None);
241        assert_eq!(m.len(), 3);
242        assert_eq!(m.get(&"c"), Some(&3));
243    }
244
245    #[test]
246    fn insert_existing_key_replaces_value() {
247        let mut m = map_3();
248        assert_eq!(m.insert("a", 99).unwrap(), Some(1));
249        assert_eq!(m.len(), 2); // count unchanged
250        assert_eq!(m.get(&"a"), Some(&99));
251    }
252
253    #[test]
254    fn insert_at_capacity_new_key_errors() {
255        let mut m = BoundedMap::<&str, i32, 0, 2>::new(alloc::vec![("a", 1), ("b", 2)]).unwrap();
256        assert_eq!(
257            m.insert("c", 3).unwrap_err(),
258            CollectionError::TooMany { max: 2, actual: 3 }
259        );
260        // Replacing an existing key still works at capacity.
261        assert_eq!(m.insert("a", 10).unwrap(), Some(1));
262    }
263
264    #[test]
265    fn remove_existing_key_returns_value() {
266        let mut m = map_3();
267        assert_eq!(m.remove(&"a").unwrap(), Some(1));
268        assert_eq!(m.len(), 1);
269        assert_eq!(m.get(&"a"), None);
270    }
271
272    #[test]
273    fn remove_absent_key_is_noop() {
274        let mut m = map_3();
275        assert_eq!(m.remove(&"z").unwrap(), None);
276        assert_eq!(m.len(), 2);
277    }
278
279    #[test]
280    fn remove_below_minimum_errors() {
281        let mut m = BoundedMap::<&str, i32, 2, 5>::new(alloc::vec![("a", 1), ("b", 2)]).unwrap();
282        assert_eq!(
283            m.remove(&"a").unwrap_err(),
284            CollectionError::TooFew { min: 2, actual: 1 }
285        );
286        assert_eq!(m.len(), 2); // unchanged
287    }
288
289    #[test]
290    fn get_mut_updates_in_place() {
291        let mut m = map_3();
292        *m.get_mut(&"b").unwrap() += 10;
293        assert_eq!(m.get(&"b"), Some(&12));
294        assert!(m.get_mut(&"z").is_none());
295    }
296
297    #[test]
298    fn contains_key_works() {
299        let m = map_3();
300        assert!(m.contains_key(&"a"));
301        assert!(!m.contains_key(&"z"));
302    }
303
304    #[test]
305    fn keys_values_iter_in_insertion_order() {
306        let m = map_3();
307        let keys: alloc::vec::Vec<&&str> = m.keys().collect();
308        assert_eq!(keys, alloc::vec![&"a", &"b"]);
309        let values: alloc::vec::Vec<&i32> = m.values().collect();
310        assert_eq!(values, alloc::vec![&1, &2]);
311        let entries: alloc::vec::Vec<&(&str, i32)> = m.iter().collect();
312        assert_eq!(entries, alloc::vec![&("a", 1), &("b", 2)]);
313    }
314
315    #[test]
316    fn into_inner_and_from() {
317        let m = map_3();
318        let inner: alloc::vec::Vec<(&str, i32)> = m.into_inner();
319        assert_eq!(inner, alloc::vec![("a", 1), ("b", 2)]);
320    }
321
322    #[test]
323    fn try_from_vec() {
324        assert!(BoundedMap::<&str, i32, 1, 3>::try_from(alloc::vec![("a", 1)]).is_ok());
325        assert_eq!(
326            BoundedMap::<&str, i32, 1, 3>::try_from(alloc::vec![("a", 1), ("a", 2)]).unwrap_err(),
327            CollectionError::Duplicate
328        );
329    }
330
331    #[test]
332    fn min_equals_max_exact_size() {
333        assert!(BoundedMap::<&str, i32, 2, 2>::new(alloc::vec![("a", 1), ("b", 2)]).is_ok());
334        assert!(BoundedMap::<&str, i32, 2, 2>::new(alloc::vec![("a", 1)]).is_err());
335    }
336
337    #[test]
338    fn equality_is_order_sensitive() {
339        let a = BoundedMap::<&str, i32, 0, 3>::new(alloc::vec![("a", 1), ("b", 2)]).unwrap();
340        let b = BoundedMap::<&str, i32, 0, 3>::new(alloc::vec![("b", 2), ("a", 1)]).unwrap();
341        assert_ne!(a, b);
342    }
343
344    #[test]
345    fn min_max_len_constants() {
346        assert_eq!(BoundedMap::<&str, i32, 2, 8>::min_len(), 2);
347        assert_eq!(BoundedMap::<&str, i32, 2, 8>::max_len(), 8);
348    }
349}
reliakit_collections/bounded_map.rs

reliakit_collections/
bounded_map.rs
