small_collections/sets/
set.rs

1//! Hash set that lives on the stack and spills to the heap.
2//!
3//! Provides [`SmallSet`] — a zero-overhead wrapper around `SmallMap<T, (), N>` that
4//! inherits automatic stack→heap spill behaviour and full set-algebra operations
5//! (`difference`, `intersection`, `union`, `symmetric_difference`, `is_subset`, …).
6//!
7//! [`AnySet`] is an object-safe trait implemented by `SmallSet`, `HashSet`, and `BTreeSet`
8//! so that set-algebra methods can accept any of these types as the `other` argument.
9
10use crate::SmallMap;
11use std::borrow::Borrow;
12use std::collections::{BTreeSet, HashSet};
13use std::fmt::{self, Debug};
14use std::hash::{BuildHasher, Hash};
15use std::iter::FromIterator;
16
17// ==================================================================================
18// 1. The Interoperability Trait
19// ==================================================================================
20
21/// A trait for any collection that supports efficient containment checks.
22///
23/// This allows `SmallSet` to perform set operations (like `difference` or `is_subset`)
24/// against standard library sets (`HashSet`, `BTreeSet`) without converting them first.
25pub trait AnySet<T> {
26    /// Returns `true` if the collection contains the value.
27    fn contains(&self, value: &T) -> bool;
28
29    /// Returns the number of elements in the collection.
30    fn len(&self) -> usize;
31
32    /// Returns `true` if the collection is empty.
33    fn is_empty(&self) -> bool {
34        self.len() == 0
35    }
36}
37// Support SmallSet
38impl<T, const N: usize> AnySet<T> for SmallSet<T, N>
39where
40    T: Eq + Hash,
41{
42    fn contains(&self, value: &T) -> bool {
43        SmallSet::contains(self, value)
44    }
45
46    fn len(&self) -> usize {
47        SmallSet::len(&self)
48    }
49}
50
51// Support standard HashSet
52impl<T, S> AnySet<T> for HashSet<T, S>
53where
54    T: Eq + Hash,
55    S: BuildHasher,
56{
57    fn contains(&self, value: &T) -> bool {
58        self.contains(value)
59    }
60
61    fn len(&self) -> usize {
62        self.len()
63    }
64}
65
66// Support standard BTreeSet
67impl<T> AnySet<T> for BTreeSet<T>
68where
69    T: Ord,
70{
71    fn contains(&self, value: &T) -> bool {
72        self.contains(value)
73    }
74
75    fn len(&self) -> usize {
76        self.len()
77    }
78}
79
80// ==================================================================================
81// 2. SmallSet Implementation
82// ==================================================================================
83
84/// A set that lives on the stack for `N` items, then automatically spills to the heap.
85///
86/// # Implementation Details
87/// This is a wrapper around `SmallMap<T, (), N>`. Since `()` is a zero-sized type in Rust,
88/// this wrapper has **zero memory overhead** compared to a raw set implementation.
89///
90/// * **Stack State:** Zero allocations. Extremely fast FNV hashing.
91/// * **Heap State:** Standard `HashMap` performance.
92/// * **Spill:** Zero-allocation move. Keys are moved, not cloned.
93pub struct SmallSet<T, const N: usize> {
94    map: SmallMap<T, (), N>,
95}
96
97impl<T, const N: usize> SmallSet<T, N>
98where
99    T: Eq + Hash,
100{
101    /// Creates a new empty set.
102    ///
103    /// The set initially lives on the stack.
104    pub fn new() -> Self {
105        Self {
106            map: SmallMap::new(),
107        }
108    }
109
110    /// Returns `true` if the set is currently storing data on the stack.
111    #[inline]
112    pub fn is_on_stack(&self) -> bool {
113        self.map.is_on_stack()
114    }
115
116    /// Returns the number of elements in the set.
117    #[inline]
118    pub fn len(&self) -> usize {
119        self.map.len()
120    }
121
122    /// Returns `true` if the set contains no elements.
123    #[inline]
124    pub fn is_empty(&self) -> bool {
125        self.map.is_empty()
126    }
127
128    /// Clears the set, removing all values.
129    ///
130    /// This keeps the allocated memory (if on heap) for reuse.
131    #[inline]
132    pub fn clear(&mut self) {
133        self.map.clear();
134    }
135
136    /// Adds a value to the set.
137    ///
138    /// Returns `true` if the value was newly inserted.
139    /// Returns `false` if the value was already present.
140    ///
141    /// If the stack capacity `N` is exceeded, this triggers a spill to the heap.
142    pub fn insert(&mut self, value: T) -> bool {
143        if self.map.contains_key(&value) {
144            false
145        } else {
146            self.map.insert(value, ());
147            true
148        }
149    }
150
151    /// Returns `true` if the set contains a value.
152    ///
153    /// This method is generic over `Q` to allow looking up `String` keys with `&str`.
154    pub fn contains<Q>(&self, value: &Q) -> bool
155    where
156        T: Borrow<Q>,
157        Q: Hash + Eq + ?Sized,
158    {
159        self.map.contains_key(value)
160    }
161
162    /// Removes a value from the set. Returns `true` if the value was present.
163    pub fn remove<Q>(&mut self, value: &Q) -> bool
164    where
165        T: Borrow<Q>,
166        Q: Hash + Eq + ?Sized,
167    {
168        self.map.remove(value).is_some()
169    }
170
171    /// Retains only the elements specified by the predicate.
172    ///
173    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
174    /// This method operates in O(n) time.
175    pub fn retain<F>(&mut self, mut f: F)
176    where
177        F: FnMut(&T) -> bool,
178    {
179        // Safe implementation: We replace the map with a new empty one,
180        // iterate the old one, and re-insert items that pass the filter.
181        // This ensures proper Move semantics (items are moved back in, not cloned).
182        let old_map = std::mem::replace(&mut self.map, SmallMap::new());
183        for (k, _) in old_map {
184            if f(&k) {
185                self.map.insert(k, ());
186            }
187        }
188    }
189
190    // --- Set Operations ---
191
192    /// Returns an iterator visiting all elements in arbitrary order.
193    pub fn iter(&self) -> SetRefIter<'_, T> {
194        SetRefIter {
195            iter: self.map.iter(),
196        }
197    }
198
199    /// Visits the values representing the difference, i.e., the values that are in `self` but not in `other`.
200    ///
201    /// `other` can be any collection implementing `AnySet` (`SmallSet`, `HashSet`, `BTreeSet`).
202    pub fn difference<'a, S>(&'a self, other: &'a S) -> impl Iterator<Item = &'a T>
203    where
204        S: AnySet<T>,
205    {
206        self.iter().filter(move |v| !other.contains(v))
207    }
208
209    /// Visits the values representing the intersection, i.e., the values that are both in `self` and `other`.
210    pub fn intersection<'a, S>(&'a self, other: &'a S) -> impl Iterator<Item = &'a T>
211    where
212        S: AnySet<T>,
213    {
214        self.iter().filter(move |v| other.contains(v))
215    }
216
217    /// Visits the values representing the union, i.e., all the values in `self` or `other`, without duplicates.
218    ///
219    /// `other` can be any iterator yielding `&T`.
220    pub fn union<'a, I>(&'a self, other: I) -> impl Iterator<Item = &'a T>
221    where
222        I: IntoIterator<Item = &'a T>,
223        I::IntoIter: 'a,
224    {
225        // Iterate self, then iterate 'other' ONLY if 'self' doesn't contain the item.
226        self.iter()
227            .chain(other.into_iter().filter(move |v| !self.contains(v)))
228    }
229
230    /// Returns `true` if `self` has no elements in common with `other`.
231    pub fn is_disjoint<S>(&self, other: &S) -> bool
232    where
233        S: AnySet<T>,
234    {
235        self.iter().all(|v| !other.contains(v))
236    }
237
238    /// Returns `true` if `self` is a subset of `other`.
239    ///
240    /// `other` must be a Set (implement `AnySet`) to ensure O(1) lookups.
241    pub fn is_subset<S>(&self, other: &S) -> bool
242    where
243        S: AnySet<T>,
244    {
245        self.iter().all(|v| other.contains(v))
246    }
247
248    /// Returns `true` if `self` is a superset of `other`.
249    ///
250    /// `other` can be any iterator. We must ensure `T` lives as long as the iterator `'a`.
251    pub fn is_superset<'a, I>(&self, other: I) -> bool
252    where
253        T: 'a,
254        I: IntoIterator<Item = &'a T>,
255    {
256        other.into_iter().all(|v| self.contains(v))
257    }
258
259    /// Visits the values representing the symmetric difference,
260    /// i.e., values that are in `self` or `other` but not in both.
261    pub fn symmetric_difference<'a>(
262        &'a self,
263        other: &'a SmallSet<T, N>,
264    ) -> impl Iterator<Item = &'a T> {
265        // A ^ B = (A - B) U (B - A)
266        self.difference(other).chain(other.difference(self))
267    }
268}
269
270// ==================================================================================
271// 3. Trait Implementations
272// ==================================================================================
273
274impl<T, const N: usize> Clone for SmallSet<T, N>
275where
276    T: Eq + Hash + Clone,
277{
278    fn clone(&self) -> Self {
279        Self {
280            map: self.map.clone(),
281        }
282    }
283}
284
285impl<T: Eq + Hash, const N: usize> Default for SmallSet<T, N> {
286    fn default() -> Self {
287        Self::new()
288    }
289}
290
291impl<T: Debug + Eq + Hash, const N: usize> Debug for SmallSet<T, N> {
292    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
293        f.debug_set().entries(self.iter()).finish()
294    }
295}
296
297// Allows `set.iter().collect()` or `vec.into_iter().collect()`
298impl<T: Eq + Hash, const N: usize> FromIterator<T> for SmallSet<T, N> {
299    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
300        let mut set = SmallSet::new();
301        for val in iter {
302            set.insert(val);
303        }
304        set
305    }
306}
307
308// Allows `for x in set` (Consuming Iterator)
309impl<T: Eq + Hash, const N: usize> IntoIterator for SmallSet<T, N> {
310    type Item = T;
311    type IntoIter = SmallSetIntoIter<T, N>;
312
313    fn into_iter(self) -> Self::IntoIter {
314        SmallSetIntoIter {
315            iter: self.map.into_iter(),
316        }
317    }
318}
319
320/// A consuming iterator for `SmallSet`.
321pub struct SmallSetIntoIter<T, const N: usize> {
322    // We reuse the map's iterator logic. It yields (K, V).
323    iter: crate::SmallMapIntoIter<T, (), N>,
324}
325
326impl<T, const N: usize> Iterator for SmallSetIntoIter<T, N> {
327    type Item = T;
328    fn next(&mut self) -> Option<Self::Item> {
329        // Discard the empty tuple value, return key.
330        self.iter.next().map(|(k, _)| k)
331    }
332}
333
334impl<T, const N: usize> Extend<T> for SmallSet<T, N>
335where
336    T: Eq + Hash + Clone,
337{
338    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
339        for item in iter {
340            self.insert(item);
341        }
342    }
343}
344
345// Allows extending with references: set.extend(&vec)
346impl<'a, T, const N: usize> Extend<&'a T> for SmallSet<T, N>
347where
348    T: 'a + Eq + Hash + Clone + Copy,
349{
350    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
351        for item in iter {
352            self.insert(*item);
353        }
354    }
355}
356
357// --- Equality (PartialEq / Eq) ---
358
359// Allows comparing SmallSets with AnySet.
360// 1. SmallSet<T, 4> == SmallSet<T, 8>
361// 2. SmallSet<T, 4> == HashSet<T>
362// 3. SmallSet<T, 4> == BTreeSet<T>
363impl<T, const N: usize, S> PartialEq<S> for SmallSet<T, N>
364where
365    T: Eq + Hash + Clone,
366    S: AnySet<T>, // S is the target set (SmallSet, HashSet, etc.)
367{
368    fn eq(&self, other: &S) -> bool {
369        // Optimization: Sets of different sizes cannot be equal.
370        if self.len() != other.len() {
371            return false;
372        }
373
374        // Logic: If lengths are equal and A is a subset of B, then A == B.
375        // We rely on the `is_subset` method which uses `AnySet`.
376        self.is_subset(other)
377    }
378}
379
380// Eq implies PartialEq<Self>, which is covered by the implementation above where M = N.
381impl<T, const N: usize> Eq for SmallSet<T, N> where T: Eq + Hash + Clone {}
382
383// ==================================================================================
384// 4. Reference Iterator Support
385// ==================================================================================
386
387/// An iterator over the references to values in a SmallSet.
388pub struct SetRefIter<'a, T> {
389    // We wrap the underlying map iterator
390    iter: crate::SmallMapIter<'a, T, ()>,
391}
392
393impl<'a, T: 'a> Iterator for SetRefIter<'a, T> {
394    type Item = &'a T;
395
396    fn next(&mut self) -> Option<Self::Item> {
397        // The map yields (&Key, &Value). We only want the Key.
398        self.iter.next().map(|(k, _)| k)
399    }
400}
401
402// Allows `for x in &set` or passing `&set` to methods like `union`
403impl<'a, T, const N: usize> IntoIterator for &'a SmallSet<T, N>
404where
405    T: Eq + Hash,
406{
407    type Item = &'a T;
408    type IntoIter = SetRefIter<'a, T>;
409
410    fn into_iter(self) -> Self::IntoIter {
411        self.iter()
412    }
413}
414
415// ==================================================================================
416// 5. Tests
417// ==================================================================================
418
419#[cfg(test)]
420mod tests {
421    use super::*;
422    use std::collections::{BTreeSet, HashSet};
423
424    // --- 1. Basic CRUD & Stack Behavior ---
425    #[test]
426    fn test_set_stack_ops_basic() {
427        let mut set: SmallSet<i32, 4> = SmallSet::new();
428
429        assert!(set.is_empty());
430        assert_eq!(set.len(), 0);
431        assert!(set.is_on_stack());
432
433        // Insert
434        assert!(set.insert(10));
435        assert!(set.insert(20));
436        assert_eq!(set.len(), 2);
437
438        // Contains
439        assert!(set.contains(&10));
440        assert!(!set.contains(&99));
441
442        // Remove
443        assert!(set.remove(&10));
444        assert!(!set.contains(&10));
445        assert_eq!(set.len(), 1);
446
447        // Clear
448        set.clear();
449        assert!(set.is_empty());
450        assert!(set.is_on_stack()); // Clearing shouldn't change storage mode
451    }
452
453    #[test]
454    fn test_set_stack_duplicate_insertion() {
455        let mut set: SmallSet<String, 4> = SmallSet::new();
456
457        assert!(set.insert("A".to_string()));
458        assert_eq!(set.len(), 1);
459
460        // Duplicate insert returns false
461        assert!(!set.insert("A".to_string()));
462        assert_eq!(set.len(), 1); // Length should not increase
463    }
464
465    // --- 2. Spill Logic (The Critical Test) ---
466    #[test]
467    fn test_set_spill_trigger_on_insert() {
468        // N = 2. Should hold 2 items on stack. 3rd item triggers spill.
469        let mut set: SmallSet<i32, 2> = SmallSet::new();
470
471        set.insert(1);
472        set.insert(2);
473        assert!(set.is_on_stack());
474
475        // Trigger Spill
476        set.insert(3);
477
478        assert!(!set.is_on_stack());
479        assert_eq!(set.len(), 3);
480        assert!(set.contains(&1));
481        assert!(set.contains(&2));
482        assert!(set.contains(&3));
483    }
484
485    #[test]
486    fn test_set_any_storage_growth_on_heap() {
487        let mut set: SmallSet<i32, 2> = SmallSet::new();
488
489        // Push well past stack capacity
490        for i in 0..100 {
491            set.insert(i);
492        }
493
494        assert!(!set.is_on_stack());
495        assert_eq!(set.len(), 100);
496        assert!(set.contains(&50));
497    }
498
499    // --- 3. Iterators ---
500    #[test]
501    fn test_set_traits_iter() {
502        let set: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
503        let collected: Vec<_> = set.iter().cloned().collect(); // Arbitrary order
504
505        assert_eq!(collected.len(), 3);
506        assert!(collected.contains(&1));
507        assert!(collected.contains(&2));
508        assert!(collected.contains(&3));
509    }
510
511    #[test]
512    fn test_set_stack_into_iter() {
513        let mut set: SmallSet<i32, 4> = SmallSet::new();
514        set.insert(1);
515        set.insert(2);
516
517        // Consuming iterator from Stack state
518        let vec: Vec<i32> = set.into_iter().collect();
519        assert_eq!(vec.len(), 2);
520        assert!(vec.contains(&1));
521        assert!(vec.contains(&2));
522    }
523
524    #[test]
525    fn test_set_any_storage_into_iter_heap() {
526        let mut set: SmallSet<i32, 2> = SmallSet::new();
527        set.insert(1);
528        set.insert(2);
529        set.insert(3); // Spilled
530
531        // Consuming iterator from Heap state
532        let vec: Vec<i32> = set.into_iter().collect();
533        assert_eq!(vec.len(), 3);
534        assert!(vec.contains(&1));
535    }
536
537    // --- 4. Set Algebra (Difference, Union, Intersection) ---
538    #[test]
539    fn test_set_any_set_difference() {
540        let a: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
541        let b: SmallSet<i32, 4> = vec![3, 4, 5].into_iter().collect();
542
543        // A - B = {1, 2}
544        let diff: Vec<_> = a.difference(&b).cloned().collect();
545        assert_eq!(diff.len(), 2);
546        assert!(diff.contains(&1));
547        assert!(diff.contains(&2));
548        assert!(!diff.contains(&3));
549    }
550
551    #[test]
552    fn test_set_any_set_intersection() {
553        let a: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
554        let b: SmallSet<i32, 4> = vec![2, 3, 4].into_iter().collect();
555
556        // A & B = {2, 3}
557        let int: Vec<_> = a.intersection(&b).cloned().collect();
558        assert_eq!(int.len(), 2);
559        assert!(int.contains(&2));
560        assert!(int.contains(&3));
561        assert!(!int.contains(&1));
562    }
563
564    #[test]
565    fn test_set_any_set_union() {
566        let a: SmallSet<i32, 4> = vec![1, 2].into_iter().collect();
567        let b: SmallSet<i32, 4> = vec![2, 3].into_iter().collect();
568
569        // A | B = {1, 2, 3}
570        // Passing &b works because we implemented IntoIterator for &SmallSet
571        let u: Vec<_> = a.union(&b).cloned().collect();
572        assert_eq!(u.len(), 3);
573        assert!(u.contains(&1));
574        assert!(u.contains(&2));
575        assert!(u.contains(&3));
576    }
577
578    // --- 5. Boolean Logic (Subset, Disjoint) ---
579    #[test]
580    fn test_set_any_set_disjoint() {
581        let a: SmallSet<i32, 4> = vec![1, 2].into_iter().collect();
582        let b: SmallSet<i32, 4> = vec![3, 4].into_iter().collect();
583        let c: SmallSet<i32, 4> = vec![2, 3].into_iter().collect();
584
585        assert!(a.is_disjoint(&b)); // No shared elements
586        assert!(!a.is_disjoint(&c)); // Shares '2'
587    }
588
589    #[test]
590    fn test_set_any_set_subset() {
591        let sub: SmallSet<i32, 4> = vec![1, 2].into_iter().collect();
592        let sup: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
593
594        assert!(sub.is_subset(&sup));
595        assert!(!sup.is_subset(&sub));
596
597        // Empty set is subset of everything
598        let empty: SmallSet<i32, 4> = SmallSet::new();
599        assert!(empty.is_subset(&sub));
600    }
601
602    #[test]
603    fn test_set_any_set_superset() {
604        let sup: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
605        let sub_vec = vec![1, 2];
606
607        assert!(sup.is_superset(&sub_vec)); // Works with Vec iterator
608        assert!(!sup.is_superset(&vec![1, 99])); // Missing 99
609    }
610
611    // --- 6. Interoperability (Std Sets) ---
612    #[test]
613    fn test_set_traits_interop_hashset() {
614        let small: SmallSet<i32, 4> = vec![1, 2].into_iter().collect();
615        let std_set: HashSet<i32> = vec![1, 2, 3].into_iter().collect();
616
617        assert!(small.is_subset(&std_set));
618
619        // Difference against std::HashSet
620        let diff: Vec<_> = small.difference(&std_set).collect();
621        assert!(diff.is_empty());
622    }
623
624    #[test]
625    fn test_set_traits_interop_btreeset() {
626        let small: SmallSet<i32, 4> = vec![1, 2].into_iter().collect();
627        let btree: BTreeSet<i32> = vec![2, 3].into_iter().collect();
628
629        // Intersection with BTreeSet
630        let int: Vec<_> = small.intersection(&btree).cloned().collect();
631        assert_eq!(int, vec![2]);
632    }
633
634    // --- 7. Retain (Filter) ---
635    #[test]
636    fn test_set_any_storage_retain() {
637        let mut set: SmallSet<i32, 4> = vec![1, 2, 3, 4, 5].into_iter().collect();
638        // Should spill (5 > 4)
639        assert!(!set.is_on_stack());
640
641        // Keep only even numbers
642        set.retain(|x| x % 2 == 0);
643
644        assert_eq!(set.len(), 2);
645        assert!(set.contains(&2));
646        assert!(set.contains(&4));
647        assert!(!set.contains(&1));
648    }
649
650    #[test]
651    fn test_set_any_set_symmetric_difference() {
652        let a: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
653        let b: SmallSet<i32, 4> = vec![3, 4, 5].into_iter().collect();
654
655        // Items in A or B, but not both: {1, 2, 4, 5}
656        let sym: Vec<_> = a.symmetric_difference(&b).cloned().collect();
657        assert_eq!(sym.len(), 4);
658        assert!(sym.contains(&1));
659        assert!(sym.contains(&4));
660        assert!(!sym.contains(&3)); // 3 is in both
661    }
662
663    #[test]
664    fn test_set_traits_equality() {
665        let a: SmallSet<i32, 4> = vec![1, 2, 3].into_iter().collect();
666        let b: SmallSet<i32, 4> = vec![3, 2, 1].into_iter().collect(); // Different insertion order
667        let c: SmallSet<i32, 2> = vec![1, 2].into_iter().collect();
668
669        assert_eq!(a, b); // Should be equal despite order
670        assert_ne!(a, c);
671    }
672
673    #[test]
674    fn test_set_traits_extend() {
675        let mut set: SmallSet<i32, 4> = SmallSet::new();
676        set.insert(1);
677
678        let more = vec![2, 3, 4, 5]; // Triggers spill
679        set.extend(more);
680
681        assert_eq!(set.len(), 5);
682        assert!(!set.is_on_stack());
683        assert!(set.contains(&5));
684    }
685
686    #[test]
687    fn test_set_traits_clone() {
688        let mut a: SmallSet<i32, 4> = SmallSet::new();
689        a.insert(1);
690
691        let mut b = a.clone();
692        b.insert(2);
693
694        assert!(a.contains(&1));
695        assert!(!a.contains(&2)); // A should be unaffected
696        assert!(b.contains(&1));
697        assert!(b.contains(&2));
698    }
699
700    #[test]
701    fn test_set_any_storage_clone_heap() {
702        let mut original: SmallSet<String, 4> = SmallSet::new();
703        original.insert("A".to_string());
704        original.insert("B".to_string());
705
706        // Clone the set
707        let mut copy = original.clone();
708
709        // Modify the copy
710        copy.insert("C".to_string());
711        copy.remove("A");
712
713        // Verify Original is untouched
714        assert!(original.contains("A"));
715        assert!(!original.contains("C"));
716        assert_eq!(original.len(), 2);
717
718        // Verify Copy is modified
719        assert!(!copy.contains("A"));
720        assert!(copy.contains("C"));
721        assert_eq!(copy.len(), 2);
722    }
723
724    #[test]
725    fn test_set_traits_equality_different_capacities() {
726        let mut s1: SmallSet<i32, 4> = SmallSet::new();
727        let mut s2: SmallSet<i32, 8> = SmallSet::new();
728
729        s1.insert(1);
730        s1.insert(2);
731
732        s2.insert(2);
733        s2.insert(1);
734
735        // 1. Equal content, different capacity types
736        assert_eq!(s1, s2);
737
738        // 2. Different content
739        s2.insert(3);
740        assert_ne!(s1, s2);
741    }
742
743    #[test]
744    fn test_set_traits_equality_interop() {
745        let mut small: SmallSet<i32, 4> = SmallSet::new();
746        small.insert(1);
747        small.insert(2);
748
749        // 1. Check against HashSet
750        let mut hash_set = HashSet::new();
751        hash_set.insert(1);
752        hash_set.insert(2);
753
754        assert_eq!(small, hash_set); // SmallSet == HashSet
755
756        hash_set.insert(3);
757        assert_ne!(small, hash_set); // Lengths differ
758
759        // 2. Check against BTreeSet
760        let mut btree_set = BTreeSet::new();
761        btree_set.insert(1);
762        btree_set.insert(2);
763
764        assert_eq!(small, btree_set); // SmallSet == BTreeSet
765    }
766
767    #[test]
768    fn test_set_any_storage_heap_remove() {
769        let mut set: SmallSet<i32, 2> = vec![1, 2, 3].into_iter().collect();
770        assert!(!set.is_on_stack());
771        assert!(set.remove(&2));
772        assert_eq!(set.len(), 2);
773    }
774
775    #[test]
776    fn test_set_any_storage_clone_heap_v2() {
777        let set: SmallSet<i32, 2> = vec![1, 2, 3].into_iter().collect();
778        let cloned = set.clone();
779        assert_eq!(cloned.len(), 3);
780        assert!(!cloned.is_on_stack());
781    }
782
783    #[test]
784    fn test_set_traits_debug_display() {
785        let set: SmallSet<i32, 2> = vec![1].into_iter().collect();
786        let debug = format!("{:?}", set);
787        assert!(debug.contains("1"));
788    }
789
790    #[test]
791    fn test_set_traits_any_set_impl() {
792        let set: SmallSet<i32, 2> = vec![1, 2].into_iter().collect();
793        let any: &dyn AnySet<i32> = &set;
794        assert_eq!(any.len(), 2);
795        assert!(any.contains(&1));
796        assert!(!any.is_empty());
797    }
798
799    #[test]
800    fn test_set_coverage_gaps() {
801        // Default
802        let set: SmallSet<i32, 4> = Default::default();
803        assert!(set.is_empty());
804
805        // Extend with references
806        let mut set: SmallSet<i32, 4> = SmallSet::new();
807        let refs = vec![1, 2, 3];
808        set.extend(&refs);
809        assert_eq!(set.len(), 3);
810        assert!(set.contains(&2));
811    }
812}
small_collections/sets/set.rs

small_collections/sets/
set.rs
