typst_utils/
listset.rs

1use std::ops::DerefMut;
2
3/// Picked by gut feeling. Could probably even be a bit larger.
4const CUT_OFF: usize = 15;
5
6/// A set backed by a mutable slice-like data structure.
7///
8/// This data structure uses two different strategies depending on size:
9///
10/// - When the list is small, it is just kept as is and searched linearly in
11///   [`contains`](Self::contains).
12///
13/// - When the list is a bit bigger, it's sorted in [`new`](Self::new) and then
14///   binary-searched for containment checks.
15pub struct ListSet<S>(S);
16
17impl<T, S> ListSet<S>
18where
19    S: DerefMut<Target = [T]>,
20    T: Ord,
21{
22    /// Creates a new list set.
23    ///
24    /// If the list is longer than the cutoff point, it is sorted.
25    pub fn new(mut list: S) -> Self {
26        if list.len() > CUT_OFF {
27            list.sort_unstable();
28        }
29        Self(list)
30    }
31
32    /// Whether the set contains no elements.
33    pub fn is_empty(&self) -> bool {
34        self.0.is_empty()
35    }
36
37    /// Checks whether the set contains the given value.
38    ///
39    /// If the list is shorter than the cutoff point, performs a linear search.
40    /// If it is longer, performs a binary search.
41    pub fn contains(&self, value: &T) -> bool {
42        if self.0.len() > CUT_OFF {
43            self.0.binary_search(value).is_ok()
44        } else {
45            self.0.contains(value)
46        }
47    }
48}
typst_utils/listset.rs

typst_utils/
listset.rs
