turbo_frozenmap/
set.rs

1use std::{
2    borrow::Borrow,
3    collections::{BTreeSet, HashSet},
4    fmt::{self, Debug},
5    hash::BuildHasher,
6    iter::FusedIterator,
7    ops::RangeBounds,
8};
9
10use bincode::{BorrowDecode, Decode, Encode};
11use indexmap::IndexSet;
12use serde::{Deserialize, Serialize};
13
14use crate::map::{self, FrozenMap};
15
16/// A compact frozen (immutable) ordered set backed by a [`FrozenMap<T, ()>`].
17///
18/// This is a read-only set that stores elements in a contiguous, sorted array. It provides
19/// efficient binary search lookups and iteration, but cannot be modified after construction.
20///
21/// # Construction
22///
23/// If you're building a new set, and you don't expect many overlapping items, consider pushing
24/// items into a [`Vec`] and calling [`FrozenSet::from`] or using the [`FromIterator`]
25/// implementation via [`Iterator::collect`]. It is typically cheaper to collect into a [`Vec`] and
26/// sort the items once at the end than it is to maintain a temporary set data structure.
27///
28/// If you already have a set, or you have many overlapping items that you don't want to temporarily
29/// hold onto, you can use the [`From`] or [`Into`] traits to create a [`FrozenSet`] from one of
30/// many common collections. You should prefer using a [`BTreeSet`], as it matches the sorted
31/// semantics of [`FrozenSet`] and avoids a sort operation during conversion.
32///
33/// Overlapping items encountered during construction preserve the last overlapping item, matching
34/// similar behavior for other sets in the standard library.
35///
36/// Similar to the API of [`BTreeSet`], there are no convenience methods for constructing from a
37/// [`Vec`] or boxed slice. Because of limitations of the internal representation and Rust's memory
38/// layout rules, the most efficient way to convert from these data structures is via an
39/// [`Iterator`].
40#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Encode, Decode, Serialize, Deserialize)]
41#[bincode(
42    decode_bounds = "T: Decode<__Context> + 'static",
43    borrow_decode_bounds = "T: BorrowDecode<'__de, __Context> + '__de"
44)]
45pub struct FrozenSet<T> {
46    map: FrozenMap<T, ()>,
47}
48
49impl<T> FrozenSet<T> {
50    /// Creates an empty [`FrozenSet`]. Does not perform any heap allocations.
51    pub fn new() -> Self {
52        FrozenSet {
53            map: FrozenMap::new(),
54        }
55    }
56}
57
58impl<T> FrozenSet<T>
59where
60    T: Ord,
61{
62    /// Creates a [`FrozenSet`] from a pre-sorted iterator with unique items.
63    ///
64    /// This is more efficient than [`Iterator::collect`] or [`FromIterator::from_iter`] if you know
65    /// that the iterator is sorted and has no overlapping items.
66    ///
67    /// Panics if the `items` are not unique and sorted.
68    pub fn from_unique_sorted_iter(items: impl IntoIterator<Item = T>) -> Self {
69        FrozenSet {
70            map: FrozenMap::from_unique_sorted_box(items.into_iter().map(|t| (t, ())).collect()),
71        }
72    }
73
74    /// Creates a [`FrozenSet`] from a pre-sorted iterator with unique items.
75    ///
76    /// This is more efficient than [`Iterator::collect`] or [`FromIterator::from_iter`] if you know
77    /// that the iterator is sorted and has no overlapping items.
78    ///
79    /// # Correctness
80    ///
81    /// The caller must ensure that:
82    /// - The iterator yields items in ascending order according to [`T: Ord`][Ord]
83    /// - There are no overlapping items
84    ///
85    /// If these invariants are not upheld, the set will behave incorrectly (e.g.,
86    /// [`FrozenSet::contains`] may fail to find items that are present), but no memory unsafety
87    /// will occur.
88    ///
89    /// When `debug_assertions` is enabled, this will panic if an invariant is not upheld.
90    pub fn from_unique_sorted_iter_unchecked(items: impl IntoIterator<Item = T>) -> Self {
91        FrozenSet {
92            map: FrozenMap::from_unique_sorted_box_unchecked(
93                items.into_iter().map(|t| (t, ())).collect(),
94            ),
95        }
96    }
97}
98
99impl<T: Ord> FromIterator<T> for FrozenSet<T> {
100    /// Creates a [`FrozenSet`] from an iterator of items. If there are overlapping items, only the
101    /// last copy is kept.
102    fn from_iter<I: IntoIterator<Item = T>>(items: I) -> Self {
103        FrozenSet {
104            map: FrozenMap::from_iter(items.into_iter().map(|t| (t, ()))),
105        }
106    }
107}
108
109impl<T> From<BTreeSet<T>> for FrozenSet<T> {
110    /// Creates a [`FrozenSet`] from a [`BTreeSet`].
111    ///
112    /// This is more efficient than `From<HashSet<T>>` because [`BTreeSet`] already iterates in
113    /// sorted order, so no re-sorting is needed.
114    fn from(set: BTreeSet<T>) -> Self {
115        if set.is_empty() {
116            return Self::new();
117        }
118        FrozenSet {
119            map: FrozenMap {
120                entries: set.into_iter().map(|t| (t, ())).collect(),
121            },
122        }
123    }
124}
125
126impl<T, S> From<HashSet<T, S>> for FrozenSet<T>
127where
128    T: Ord,
129    S: BuildHasher,
130{
131    /// Creates a [`FrozenSet`] from a [`HashSet`].
132    ///
133    /// The items are sorted during construction.
134    fn from(set: HashSet<T, S>) -> Self {
135        if set.is_empty() {
136            return Self::new();
137        }
138        FrozenSet {
139            map: FrozenMap::from_unique_box_inner(set.into_iter().map(|t| (t, ())).collect()),
140        }
141    }
142}
143
144impl<T, S> From<IndexSet<T, S>> for FrozenSet<T>
145where
146    T: Ord,
147    S: BuildHasher,
148{
149    /// Creates a [`FrozenSet`] from an [`IndexSet`].
150    ///
151    /// The items are sorted during construction.
152    fn from(set: IndexSet<T, S>) -> Self {
153        if set.is_empty() {
154            return Self::new();
155        }
156        FrozenSet {
157            map: FrozenMap::from_unique_box_inner(set.into_iter().map(|t| (t, ())).collect()),
158        }
159    }
160}
161
162impl<T: Ord, const N: usize> From<[T; N]> for FrozenSet<T> {
163    /// Creates a [`FrozenSet`] from an array of items. If there are overlapping items, the last
164    /// copy is kept.
165    ///
166    /// The items are sorted during construction.
167    fn from(items: [T; N]) -> Self {
168        Self::from_iter(items)
169    }
170}
171
172impl<T> FrozenSet<T> {
173    /// Returns the number of elements in the set.
174    pub const fn len(&self) -> usize {
175        self.map.len()
176    }
177
178    /// Returns `true` if the set contains no elements.
179    pub const fn is_empty(&self) -> bool {
180        self.map.is_empty()
181    }
182
183    /// Returns `true` if the set contains an element equal to the value.
184    pub fn contains<Q>(&self, value: &Q) -> bool
185    where
186        T: Borrow<Q> + Ord,
187        Q: Ord + ?Sized,
188    {
189        self.map.contains_key(value)
190    }
191
192    /// Returns a reference to the element in the set, if any, that is equal to the value.
193    pub fn get<Q>(&self, value: &Q) -> Option<&T>
194    where
195        T: Borrow<Q> + Ord,
196        Q: Ord + ?Sized,
197    {
198        self.map.get_key_value(value).map(|(t, _)| t)
199    }
200
201    /// Returns a reference to the first element in the set, if any. This element is always the
202    /// minimum of all elements in the set.
203    pub fn first(&self) -> Option<&T> {
204        self.map.first_key_value().map(|(t, _)| t)
205    }
206
207    /// Returns a reference to the last element in the set, if any. This element is always the
208    /// maximum of all elements in the set.
209    pub fn last(&self) -> Option<&T> {
210        self.map.last_key_value().map(|(t, _)| t)
211    }
212
213    /// Gets an iterator that visits the elements in the [`FrozenSet`] in ascending order.
214    pub fn iter(&self) -> Iter<'_, T> {
215        self.map.keys()
216    }
217
218    /// Constructs a double-ended iterator over a sub-range of elements in the set.
219    pub fn range<Q, R>(&self, range: R) -> Range<'_, T>
220    where
221        Q: Ord + ?Sized,
222        T: Borrow<Q> + Ord,
223        R: RangeBounds<Q>,
224    {
225        Range {
226            inner: self.map.range(range),
227        }
228    }
229
230    /// Returns `true` if `self` has no elements in common with `other`. This is equivalent to
231    /// checking for an empty intersection.
232    pub fn is_disjoint(&self, other: &Self) -> bool
233    where
234        T: Ord,
235    {
236        if self.len() <= other.len() {
237            self.iter().all(|v| !other.contains(v))
238        } else {
239            other.iter().all(|v| !self.contains(v))
240        }
241    }
242
243    /// Returns `true` if the set is a subset of another, i.e., `other` contains at least all the
244    /// elements in `self`.
245    pub fn is_subset(&self, other: &Self) -> bool
246    where
247        T: Ord,
248    {
249        if self.len() > other.len() {
250            return false;
251        }
252        self.iter().all(|v| other.contains(v))
253    }
254
255    /// Returns `true` if the set is a superset of another, i.e., `self` contains at least all the
256    /// elements in `other`.
257    pub fn is_superset(&self, other: &Self) -> bool
258    where
259        T: Ord,
260    {
261        other.is_subset(self)
262    }
263}
264
265// Manual implementation because the derive would add unnecessary `T: Default` bounds.
266impl<T> Default for FrozenSet<T> {
267    fn default() -> Self {
268        Self::new()
269    }
270}
271
272impl<T: Debug> Debug for FrozenSet<T> {
273    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
274        f.debug_set().entries(self.iter()).finish()
275    }
276}
277
278impl<'a, T> IntoIterator for &'a FrozenSet<T> {
279    type Item = &'a T;
280    type IntoIter = Iter<'a, T>;
281
282    fn into_iter(self) -> Iter<'a, T> {
283        self.iter()
284    }
285}
286
287impl<T> IntoIterator for FrozenSet<T> {
288    type Item = T;
289    type IntoIter = IntoIter<T>;
290
291    fn into_iter(self) -> IntoIter<T> {
292        self.map.into_keys()
293    }
294}
295
296// These could be newtype wrappers (BTreeSet does this), but type aliases are simpler to implement.
297pub type Iter<'a, T> = map::Keys<'a, T, ()>;
298pub type IntoIter<T> = map::IntoKeys<T, ()>;
299
300/// An iterator over a sub-range of elements in a [`FrozenSet`].
301pub struct Range<'a, T> {
302    inner: map::Range<'a, T, ()>,
303}
304
305impl<T: Debug> Debug for Range<'_, T> {
306    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307        f.debug_list().entries(self.clone()).finish()
308    }
309}
310
311impl<'a, T> Iterator for Range<'a, T> {
312    type Item = &'a T;
313
314    fn next(&mut self) -> Option<&'a T> {
315        self.inner.next().map(|(t, _)| t)
316    }
317
318    fn size_hint(&self) -> (usize, Option<usize>) {
319        self.inner.size_hint()
320    }
321
322    fn last(self) -> Option<&'a T> {
323        self.inner.last().map(|(t, _)| t)
324    }
325
326    fn count(self) -> usize {
327        self.inner.len()
328    }
329}
330
331impl<'a, T> DoubleEndedIterator for Range<'a, T> {
332    fn next_back(&mut self) -> Option<&'a T> {
333        self.inner.next_back().map(|(t, _)| t)
334    }
335}
336
337impl<T> ExactSizeIterator for Range<'_, T> {
338    fn len(&self) -> usize {
339        self.inner.len()
340    }
341}
342
343impl<T> FusedIterator for Range<'_, T> {}
344
345// Manual implementation because the derive would add an unnecessary `T: Clone` type bound.
346impl<T> Clone for Range<'_, T> {
347    fn clone(&self) -> Self {
348        Self {
349            inner: self.inner.clone(),
350        }
351    }
352}
353
354#[cfg(test)]
355mod tests {
356    use super::*;
357
358    #[test]
359    fn test_empty() {
360        let set = FrozenSet::<i32>::new();
361        assert!(set.is_empty());
362        assert_eq!(set.len(), 0);
363        assert!(!set.contains(&1));
364    }
365
366    #[test]
367    fn test_from_btreeset() {
368        let mut btree = BTreeSet::new();
369        btree.insert(3);
370        btree.insert(1);
371        btree.insert(2);
372
373        let frozen = FrozenSet::from(btree);
374        assert_eq!(frozen.len(), 3);
375        assert!(frozen.contains(&1));
376        assert!(frozen.contains(&2));
377        assert!(frozen.contains(&3));
378
379        let elements: Vec<_> = frozen.iter().copied().collect();
380        assert_eq!(elements, vec![1, 2, 3]);
381    }
382
383    #[test]
384    fn test_from_array() {
385        let frozen = FrozenSet::from([3, 1, 2]);
386        assert_eq!(frozen.len(), 3);
387        assert!(frozen.contains(&1));
388
389        let elements: Vec<_> = frozen.iter().copied().collect();
390        assert_eq!(elements, vec![1, 2, 3]);
391    }
392
393    #[test]
394    fn test_from_iter_with_duplicates() {
395        let frozen: FrozenSet<_> = [1, 1, 2].into_iter().collect();
396        assert_eq!(frozen.len(), 2);
397        assert!(frozen.contains(&1));
398        assert!(frozen.contains(&2));
399    }
400
401    #[test]
402    fn test_range() {
403        let frozen = FrozenSet::from([1, 2, 3, 4, 5]);
404
405        let range: Vec<_> = frozen.range(2..4).copied().collect();
406        assert_eq!(range, vec![2, 3]);
407
408        let range: Vec<_> = frozen.range(2..=4).copied().collect();
409        assert_eq!(range, vec![2, 3, 4]);
410
411        let range: Vec<_> = frozen.range(..3).copied().collect();
412        assert_eq!(range, vec![1, 2]);
413    }
414
415    #[test]
416    fn test_first_last() {
417        let frozen = FrozenSet::from([2, 1, 3]);
418        assert_eq!(frozen.first(), Some(&1));
419        assert_eq!(frozen.last(), Some(&3));
420
421        let empty = FrozenSet::<i32>::new();
422        assert_eq!(empty.first(), None);
423        assert_eq!(empty.last(), None);
424    }
425
426    #[test]
427    fn test_is_disjoint() {
428        let a = FrozenSet::from([1, 2, 3]);
429        let b = FrozenSet::from([4, 5, 6]);
430        let c = FrozenSet::from([3, 4, 5]);
431
432        assert!(a.is_disjoint(&b));
433        assert!(!a.is_disjoint(&c));
434    }
435
436    #[test]
437    fn test_is_subset() {
438        let a = FrozenSet::from([1, 2]);
439        let b = FrozenSet::from([1, 2, 3]);
440        let c = FrozenSet::from([2, 3, 4]);
441
442        assert!(a.is_subset(&b));
443        assert!(!a.is_subset(&c));
444        assert!(a.is_subset(&a));
445    }
446
447    #[test]
448    fn test_is_superset() {
449        let a = FrozenSet::from([1, 2, 3]);
450        let b = FrozenSet::from([1, 2]);
451        let c = FrozenSet::from([2, 3, 4]);
452
453        assert!(a.is_superset(&b));
454        assert!(!a.is_superset(&c));
455        assert!(a.is_superset(&a));
456    }
457
458    #[test]
459    fn test_from_hashset() {
460        let mut set = HashSet::new();
461        set.insert(3);
462        set.insert(1);
463        set.insert(2);
464
465        let frozen = FrozenSet::from(set);
466        assert_eq!(frozen.len(), 3);
467        assert!(frozen.contains(&1));
468        let elements: Vec<_> = frozen.iter().copied().collect();
469        assert_eq!(elements, vec![1, 2, 3]);
470    }
471
472    #[test]
473    fn test_from_unique_sorted_iter() {
474        let frozen = FrozenSet::from_unique_sorted_iter([1, 2]);
475        assert_eq!(frozen.len(), 2);
476        assert!(frozen.contains(&1));
477        assert!(frozen.contains(&2));
478    }
479
480    #[test]
481    #[should_panic(expected = "FrozenMap entries must be unique and sorted")]
482    fn test_from_unique_sorted_iter_panics() {
483        let _ = FrozenSet::from_unique_sorted_iter([1, 1, 2]);
484    }
485}
turbo_frozenmap/set.rs

turbo_frozenmap/
set.rs
