turbo_frozenmap/
set.rs

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

turbo_frozenmap/
set.rs
