reliakit_collections/
bounded_set.rs

1use crate::{CollectionError, CollectionResult};
2use alloc::vec::Vec;
3use core::ops::Deref;
4
5/// Owned set of unique elements constrained by inclusive count bounds.
6///
7/// `BoundedSet<T, MIN, MAX>` guarantees that the number of elements is always in
8/// the range `MIN..=MAX` and that every element is unique. It is backed by a
9/// `Vec<T>` in insertion order, so iteration is deterministic and pulls in no
10/// hashing or ordering machinery — membership tests are a linear scan, which is
11/// fine 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 elements with
15/// [`CollectionError::Duplicate`].
16///
17/// # Const parameters
18///
19/// - `MIN`: minimum number of elements (inclusive). Use `0` for no lower bound.
20/// - `MAX`: maximum number of elements (inclusive).
21///
22/// Construction fails with [`CollectionError::InvalidBounds`] if `MIN > MAX`.
23#[derive(Debug, Clone, PartialEq, Eq, Hash)]
24pub struct BoundedSet<T, const MIN: usize, const MAX: usize>(Vec<T>);
25
26impl<T, const MIN: usize, const MAX: usize> BoundedSet<T, MIN, MAX> {
27    /// Returns the number of elements.
28    pub fn len(&self) -> usize {
29        self.0.len()
30    }
31
32    /// Returns `true` if the set contains no elements.
33    ///
34    /// Always returns `false` when `MIN > 0`, since construction guarantees at
35    /// least `MIN` elements.
36    pub fn is_empty(&self) -> bool {
37        self.0.is_empty()
38    }
39
40    /// Returns an iterator over the elements in insertion order.
41    pub fn iter(&self) -> core::slice::Iter<'_, T> {
42        self.0.iter()
43    }
44
45    /// Returns the elements as a slice in insertion order.
46    pub fn as_slice(&self) -> &[T] {
47        &self.0
48    }
49
50    /// Consumes the wrapper and returns the inner `Vec<T>`.
51    pub fn into_inner(self) -> Vec<T> {
52        self.0
53    }
54
55    /// Returns the minimum allowed number of elements.
56    pub const fn min_len() -> usize {
57        MIN
58    }
59
60    /// Returns the maximum allowed number of elements.
61    pub const fn max_len() -> usize {
62        MAX
63    }
64}
65
66impl<T: PartialEq, const MIN: usize, const MAX: usize> BoundedSet<T, MIN, MAX> {
67    /// Creates a `BoundedSet` from a vector of elements.
68    ///
69    /// Returns an error if the bounds are invalid (`MIN > MAX`), the element
70    /// count is out of range, or the vector contains duplicates.
71    pub fn new(items: Vec<T>) -> CollectionResult<Self> {
72        if MIN > MAX {
73            return Err(CollectionError::InvalidBounds { min: MIN, max: MAX });
74        }
75        let actual = items.len();
76        if actual < MIN {
77            return Err(CollectionError::TooFew { min: MIN, actual });
78        }
79        if actual > MAX {
80            return Err(CollectionError::TooMany { max: MAX, actual });
81        }
82        for i in 0..items.len() {
83            for j in (i + 1)..items.len() {
84                if items[i] == items[j] {
85                    return Err(CollectionError::Duplicate);
86                }
87            }
88        }
89        Ok(Self(items))
90    }
91
92    /// Inserts an element.
93    ///
94    /// Returns `Ok(true)` if the element was added, or `Ok(false)` if it was
95    /// already present (no change). Returns [`CollectionError::TooMany`] if the
96    /// element is new and the set is already at capacity (`len == MAX`), leaving
97    /// the set unchanged.
98    pub fn insert(&mut self, item: T) -> CollectionResult<bool> {
99        if self.0.contains(&item) {
100            return Ok(false);
101        }
102        if self.0.len() >= MAX {
103            return Err(CollectionError::TooMany {
104                max: MAX,
105                actual: self.0.len().saturating_add(1),
106            });
107        }
108        self.0.push(item);
109        Ok(true)
110    }
111
112    /// Removes an element.
113    ///
114    /// Returns `Ok(true)` if the element was present and removed, or `Ok(false)`
115    /// if it was absent (no change). Returns [`CollectionError::TooFew`] if
116    /// removing would bring the count below `MIN`, leaving the set unchanged.
117    pub fn remove(&mut self, item: &T) -> CollectionResult<bool> {
118        let Some(idx) = self.0.iter().position(|existing| existing == item) else {
119            return Ok(false);
120        };
121        let after_remove = self.0.len() - 1;
122        if after_remove < MIN {
123            return Err(CollectionError::TooFew {
124                min: MIN,
125                actual: after_remove,
126            });
127        }
128        self.0.remove(idx);
129        Ok(true)
130    }
131
132    /// Returns `true` if the set contains `item`.
133    pub fn contains(&self, item: &T) -> bool {
134        self.0.contains(item)
135    }
136}
137
138impl<T, const MIN: usize, const MAX: usize> Deref for BoundedSet<T, MIN, MAX> {
139    type Target = [T];
140
141    fn deref(&self) -> &Self::Target {
142        self.as_slice()
143    }
144}
145
146impl<T: PartialEq, const MIN: usize, const MAX: usize> TryFrom<Vec<T>> for BoundedSet<T, MIN, MAX> {
147    type Error = CollectionError;
148
149    fn try_from(items: Vec<T>) -> Result<Self, Self::Error> {
150        Self::new(items)
151    }
152}
153
154impl<T, const MIN: usize, const MAX: usize> From<BoundedSet<T, MIN, MAX>> for Vec<T> {
155    fn from(value: BoundedSet<T, MIN, MAX>) -> Self {
156        value.into_inner()
157    }
158}
159
160#[cfg(test)]
161mod tests {
162    use super::BoundedSet;
163    use crate::CollectionError;
164
165    fn set_5() -> BoundedSet<i32, 0, 5> {
166        BoundedSet::new(alloc::vec![1, 2, 3]).unwrap()
167    }
168
169    #[test]
170    fn accepts_unique_elements() {
171        let s = set_5();
172        assert_eq!(s.len(), 3);
173        assert!(!s.is_empty());
174        assert!(s.contains(&2));
175        assert!(!s.contains(&9));
176    }
177
178    #[test]
179    fn rejects_duplicates() {
180        assert_eq!(
181            BoundedSet::<i32, 0, 5>::new(alloc::vec![1, 2, 2]).unwrap_err(),
182            CollectionError::Duplicate
183        );
184    }
185
186    #[test]
187    fn rejects_too_few() {
188        assert_eq!(
189            BoundedSet::<i32, 2, 5>::new(alloc::vec![1]).unwrap_err(),
190            CollectionError::TooFew { min: 2, actual: 1 }
191        );
192    }
193
194    #[test]
195    fn rejects_too_many() {
196        assert_eq!(
197            BoundedSet::<i32, 0, 2>::new(alloc::vec![1, 2, 3]).unwrap_err(),
198            CollectionError::TooMany { max: 2, actual: 3 }
199        );
200    }
201
202    #[test]
203    fn rejects_invalid_bounds() {
204        assert_eq!(
205            BoundedSet::<i32, 5, 3>::new(alloc::vec![]).unwrap_err(),
206            CollectionError::InvalidBounds { min: 5, max: 3 }
207        );
208    }
209
210    #[test]
211    fn insert_new_element() {
212        let mut s = set_5();
213        assert!(s.insert(4).unwrap());
214        assert_eq!(s.len(), 4);
215        assert!(s.contains(&4));
216    }
217
218    #[test]
219    fn insert_existing_element_is_noop() {
220        let mut s = set_5();
221        assert!(!s.insert(2).unwrap());
222        assert_eq!(s.len(), 3);
223    }
224
225    #[test]
226    fn insert_at_capacity_new_element_errors() {
227        let mut s = BoundedSet::<i32, 0, 3>::new(alloc::vec![1, 2, 3]).unwrap();
228        assert_eq!(
229            s.insert(4).unwrap_err(),
230            CollectionError::TooMany { max: 3, actual: 4 }
231        );
232        // Re-inserting an existing element at capacity is still a no-op Ok(false).
233        assert!(!s.insert(1).unwrap());
234    }
235
236    #[test]
237    fn remove_present_element() {
238        let mut s = set_5();
239        assert!(s.remove(&2).unwrap());
240        assert_eq!(s.len(), 2);
241        assert!(!s.contains(&2));
242    }
243
244    #[test]
245    fn remove_absent_element_is_noop() {
246        let mut s = set_5();
247        assert!(!s.remove(&9).unwrap());
248        assert_eq!(s.len(), 3);
249    }
250
251    #[test]
252    fn remove_below_minimum_errors() {
253        let mut s = BoundedSet::<i32, 2, 5>::new(alloc::vec![1, 2]).unwrap();
254        assert_eq!(
255            s.remove(&1).unwrap_err(),
256            CollectionError::TooFew { min: 2, actual: 1 }
257        );
258        assert_eq!(s.len(), 2); // unchanged
259    }
260
261    #[test]
262    fn iter_in_insertion_order() {
263        let s = set_5();
264        let collected: alloc::vec::Vec<&i32> = s.iter().collect();
265        assert_eq!(collected, alloc::vec![&1, &2, &3]);
266    }
267
268    #[test]
269    fn deref_to_slice() {
270        let s = set_5();
271        assert_eq!(&s[..], &[1, 2, 3]);
272    }
273
274    #[test]
275    fn into_inner_and_from() {
276        let s = set_5();
277        let inner: alloc::vec::Vec<i32> = alloc::vec::Vec::from(s);
278        assert_eq!(inner, alloc::vec![1, 2, 3]);
279    }
280
281    #[test]
282    fn try_from_vec() {
283        assert!(BoundedSet::<i32, 1, 3>::try_from(alloc::vec![1, 2]).is_ok());
284        assert_eq!(
285            BoundedSet::<i32, 1, 3>::try_from(alloc::vec![1, 1]).unwrap_err(),
286            CollectionError::Duplicate
287        );
288    }
289
290    #[test]
291    fn min_equals_max_exact_size() {
292        assert!(BoundedSet::<i32, 3, 3>::new(alloc::vec![1, 2, 3]).is_ok());
293        assert!(BoundedSet::<i32, 3, 3>::new(alloc::vec![1, 2]).is_err());
294    }
295
296    #[test]
297    fn min_max_len_constants() {
298        assert_eq!(BoundedSet::<i32, 2, 8>::min_len(), 2);
299        assert_eq!(BoundedSet::<i32, 2, 8>::max_len(), 8);
300    }
301}
reliakit_collections/bounded_set.rs

reliakit_collections/
bounded_set.rs
