small_collections/sets/
ordered_set.rs

1#![cfg(feature = "ordered")]
2//! Insertion-order-preserving set that lives on the stack and spills to the heap.
3//!
4//! [`SmallOrderedSet`] is a thin wrapper around `SmallOrderedMap<T, (), N>`, inheriting
5//! the insertion-order-preserving semantics and the stack→heap spill protocol defined
6//! in [`ordered_map`](crate::ordered_map).
7
8use crate::AnySet;
9use crate::SmallOrderedMap;
10use std::borrow::Borrow;
11use std::fmt::{self, Debug};
12use std::hash::Hash;
13use std::iter::FromIterator;
14
15/// An insertion-order-preserving set that lives on the stack for up to `N` elements,
16/// then spills to a heap-backed `ordermap::OrderMap`.
17///
18/// Implemented as a zero-overhead wrapper around `SmallOrderedMap<T, (), N>` so `()`
19/// zero-sized values add no memory cost.
20///
21/// # Generic parameters
22/// | Parameter | Meaning |
23/// |-----------|--------|
24/// | `T` | Element type; must implement `Eq + Hash` |
25/// | `N` | Stack capacity — max elements before spill |
26///
27/// # Design Consideration
28/// - **Insertion order**: unlike `SmallSet` which uses an unordered `FnvIndexMap` on the
29///   stack, this type also preserves insertion order after spill via `OrderMap`.
30///   The trade-off is O(N) lookup on the stack (linear scan) vs. O(1) for `SmallSet`.
31pub struct SmallOrderedSet<T: Eq + Hash, const N: usize> {
32    map: SmallOrderedMap<T, (), N>,
33}
34
35impl<T, const N: usize> SmallOrderedSet<T, N>
36where
37    T: Eq + Hash,
38{
39    /// Creates a new empty ordered set.
40    pub fn new() -> Self {
41        Self {
42            map: SmallOrderedMap::new(),
43        }
44    }
45
46    /// Returns `true` if the set is currently storing data on the stack.
47    #[inline]
48    pub fn is_on_stack(&self) -> bool {
49        self.map.is_on_stack()
50    }
51
52    /// Returns the number of elements in the set.
53    #[inline]
54    pub fn len(&self) -> usize {
55        self.map.len()
56    }
57
58    /// Returns `true` if the set contains no elements.
59    #[inline]
60    pub fn is_empty(&self) -> bool {
61        self.map.is_empty()
62    }
63
64    /// Clears the set, removing all values.
65    #[inline]
66    pub fn clear(&mut self) {
67        self.map.clear();
68    }
69
70    /// Adds a value to the set. Returns `true` if the value was newly inserted.
71    pub fn insert(&mut self, value: T) -> bool {
72        if self.map.contains_key(&value) {
73            false
74        } else {
75            self.map.insert(value, ());
76            true
77        }
78    }
79
80    /// Returns `true` if the set contains a value.
81    pub fn contains<Q>(&self, value: &Q) -> bool
82    where
83        T: Borrow<Q>,
84        Q: Hash + Eq + ?Sized,
85    {
86        self.map.contains_key(value)
87    }
88
89    /// Removes a value from the set. Returns `true` if the value was present.
90    pub fn remove<Q>(&mut self, value: &Q) -> bool
91    where
92        T: Borrow<Q> + PartialEq<Q>,
93        Q: Hash + Eq + ?Sized,
94    {
95        self.map.remove(value).is_some()
96    }
97
98    /// Retains only the elements specified by the predicate.
99    pub fn retain<F>(&mut self, mut f: F)
100    where
101        F: FnMut(&T) -> bool,
102    {
103        let old_map = std::mem::replace(&mut self.map, SmallOrderedMap::new());
104        for (k, _) in old_map {
105            if f(&k) {
106                self.map.insert(k, ());
107            }
108        }
109    }
110
111    /// Returns an iterator visiting all elements in insertion order.
112    pub fn iter(&self) -> SetRefIter<'_, T> {
113        SetRefIter {
114            iter: self.map.iter(),
115        }
116    }
117}
118
119// --- Traits ---
120
121impl<T, const N: usize> AnySet<T> for SmallOrderedSet<T, N>
122where
123    T: Eq + Hash,
124{
125    fn contains(&self, value: &T) -> bool {
126        self.contains(value)
127    }
128
129    fn len(&self) -> usize {
130        self.len()
131    }
132}
133
134impl<T, const N: usize> Clone for SmallOrderedSet<T, N>
135where
136    T: Eq + Hash + Clone,
137{
138    fn clone(&self) -> Self {
139        Self {
140            map: self.map.clone(),
141        }
142    }
143}
144
145impl<T, const N: usize> Default for SmallOrderedSet<T, N>
146where
147    T: Eq + Hash,
148{
149    fn default() -> Self {
150        Self::new()
151    }
152}
153
154impl<T, const N: usize> Debug for SmallOrderedSet<T, N>
155where
156    T: Eq + Hash + Debug,
157{
158    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
159        f.debug_set().entries(self.iter()).finish()
160    }
161}
162
163impl<T, const N: usize> FromIterator<T> for SmallOrderedSet<T, N>
164where
165    T: Eq + Hash,
166{
167    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
168        let mut set = Self::new();
169        for val in iter {
170            set.insert(val);
171        }
172        set
173    }
174}
175
176impl<T, const N: usize> IntoIterator for SmallOrderedSet<T, N>
177where
178    T: Eq + Hash,
179{
180    type Item = T;
181    type IntoIter = SmallSetIntoIter<T, N>;
182
183    fn into_iter(self) -> Self::IntoIter {
184        SmallSetIntoIter {
185            iter: self.map.into_iter(),
186        }
187    }
188}
189
190/// A structure representing `SmallSetIntoIter`.
191pub struct SmallSetIntoIter<T: Eq, const N: usize> {
192    iter: crate::maps::ordered_map::SmallMapIntoIter<T, (), N>,
193}
194
195impl<T, const N: usize> Iterator for SmallSetIntoIter<T, N>
196where
197    T: Eq + Hash,
198{
199    type Item = T;
200    fn next(&mut self) -> Option<Self::Item> {
201        self.iter.next().map(|(k, _)| k)
202    }
203}
204
205/// A structure representing `SetRefIter`.
206pub struct SetRefIter<'a, T> {
207    iter: crate::maps::ordered_map::SmallMapIter<'a, T, ()>,
208}
209
210impl<'a, T> Iterator for SetRefIter<'a, T> {
211    type Item = &'a T;
212    fn next(&mut self) -> Option<Self::Item> {
213        self.iter.next().map(|(k, _)| k)
214    }
215}
216
217impl<T, const N: usize> Extend<T> for SmallOrderedSet<T, N>
218where
219    T: Eq + Hash,
220{
221    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
222        for item in iter {
223            self.insert(item);
224        }
225    }
226}
227
228impl<T, const N: usize, S> PartialEq<S> for SmallOrderedSet<T, N>
229where
230    T: Eq + Hash,
231    S: AnySet<T>,
232{
233    fn eq(&self, other: &S) -> bool {
234        if self.len() != other.len() {
235            return false;
236        }
237        self.iter().all(|v| other.contains(v))
238    }
239}
240
241impl<T, const N: usize> Eq for SmallOrderedSet<T, N> where T: Eq + Hash {}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246
247    #[test]
248    fn test_ordered_set_stack_ops_insertion_order() {
249        let mut set: SmallOrderedSet<i32, 4> = SmallOrderedSet::new();
250        set.insert(3);
251        set.insert(1);
252        set.insert(2);
253
254        let vals: Vec<_> = set.iter().cloned().collect();
255        assert_eq!(vals, vec![3, 1, 2]);
256    }
257
258    #[test]
259    fn test_ordered_set_spill_trigger_on_insert() {
260        let mut set: SmallOrderedSet<i32, 2> = SmallOrderedSet::new();
261        set.insert(1);
262        set.insert(2);
263        assert!(set.is_on_stack());
264
265        set.insert(3);
266        assert!(!set.is_on_stack());
267
268        let vals: Vec<_> = set.iter().cloned().collect();
269        assert_eq!(vals, vec![1, 2, 3]);
270    }
271
272    #[test]
273    fn test_ordered_set_any_storage_lifecycle_duplicates() {
274        let mut set: SmallOrderedSet<String, 2> = SmallOrderedSet::new();
275        assert!(set.insert("a".into()));
276        assert!(!set.insert("a".into())); // Duplicate
277        assert!(set.insert("b".into()));
278        assert_eq!(set.len(), 2);
279        assert!(set.is_on_stack());
280
281        assert!(set.insert("c".into())); // Spill
282        assert!(!set.is_on_stack());
283        assert_eq!(set.len(), 3);
284        assert!(set.contains("a"));
285        assert!(set.contains("b"));
286        assert!(set.contains("c"));
287
288        assert!(set.remove("a"));
289        assert!(!set.contains("a"));
290        assert_eq!(set.len(), 2);
291    }
292
293    #[test]
294    fn test_ordered_set_traits_interop() {
295        use std::collections::HashSet;
296        let set: SmallOrderedSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
297        let mut std_set = HashSet::new();
298        std_set.insert(1);
299        std_set.insert(2);
300        std_set.insert(3);
301
302        assert_eq!(set, std_set);
303    }
304
305    #[test]
306    fn test_ordered_set_any_storage_clear() {
307        let mut set: SmallOrderedSet<i32, 2> = SmallOrderedSet::new();
308        assert!(set.is_empty());
309        set.insert(1);
310        set.clear();
311        assert!(set.is_empty());
312
313        set.insert(1);
314        set.insert(2);
315        set.insert(3); // Spill
316        set.clear();
317        assert!(set.is_empty());
318        assert!(!set.is_on_stack());
319    }
320
321    #[test]
322    fn test_ordered_set_traits_exhaustive() {
323        let mut set: SmallOrderedSet<i32, 4> = SmallOrderedSet::new();
324        set.insert(1);
325        set.insert(2);
326
327        // Clone
328        let cloned = set.clone();
329        assert_eq!(cloned.len(), 2);
330        assert!(cloned.contains(&1));
331
332        // Debug
333        let debug = format!("{:?}", set);
334        assert!(debug.contains("1"));
335
336        // Default
337        let def: SmallOrderedSet<i32, 4> = SmallOrderedSet::default();
338        assert!(def.is_empty());
339
340        // FromIterator / IntoIterator
341        let set2: SmallOrderedSet<i32, 4> = vec![1, 2].into_iter().collect();
342        let vec: Vec<_> = set2.into_iter().collect();
343        assert_eq!(vec, vec![1, 2]);
344
345        // Extend
346        let mut set3 = SmallOrderedSet::<i32, 4>::new();
347        set3.extend(vec![1, 2]);
348        assert_eq!(set3.len(), 2);
349    }
350
351    #[test]
352    fn test_ordered_set_traits_any_set_impl() {
353        let set: SmallOrderedSet<i32, 2> = vec![1, 2, 3].into_iter().collect();
354        assert!(!set.is_on_stack());
355
356        // AnySet trait
357        let any: &dyn AnySet<i32> = &set;
358        assert_eq!(any.len(), 3);
359        assert!(any.contains(&1));
360    }
361
362    #[test]
363    fn test_ordered_set_traits_partial_eq_variants() {
364        let set: SmallOrderedSet<i32, 2> = vec![1, 2, 3].into_iter().collect();
365        let set2: SmallOrderedSet<i32, 2> = vec![1, 2].into_iter().collect();
366        assert_ne!(set, set2);
367    }
368
369    #[test]
370    fn test_ordered_set_coverage_gaps() {
371        let mut set: SmallOrderedSet<i32, 4> = vec![1, 2, 3, 4].into_iter().collect();
372
373        // Retain: keep evens
374        set.retain(|x| x % 2 == 0);
375
376        assert_eq!(set.len(), 2);
377        assert!(set.contains(&2));
378        assert!(set.contains(&4));
379    }
380}
small_collections/sets/ordered_set.rs

small_collections/sets/
ordered_set.rs
