dada_util/
vecset.rs

1use std::{ops::Deref, vec};
2
3use salsa::Update;
4use serde::Serialize;
5
6/// A set of elements, stored in a sorted vector.
7///
8/// This is more efficient than a `HashSet` for small sets, and allows for
9/// efficient iteration.
10#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
11pub struct VecSet<T: Ord> {
12    /// Elements in the set, always sorted.
13    sorted_elements: Vec<T>,
14}
15
16unsafe impl<T: Update + Ord> salsa::Update for VecSet<T> {
17    unsafe fn maybe_update(old_pointer: *mut Self, new_value: Self) -> bool {
18        unsafe {
19            Update::maybe_update(
20                &mut (*old_pointer).sorted_elements,
21                new_value.sorted_elements,
22            )
23        }
24    }
25}
26
27impl<T: Ord> VecSet<T> {
28    pub fn new() -> Self {
29        VecSet {
30            sorted_elements: Vec::new(),
31        }
32    }
33
34    pub fn singleton(item: T) -> Self {
35        VecSet {
36            sorted_elements: vec![item],
37        }
38    }
39
40    /// Insert `item` into the set.
41    ///
42    /// Returns `true` if the item was not already in the set.
43    pub fn insert(&mut self, item: T) -> bool {
44        match self.sorted_elements.binary_search(&item) {
45            Ok(_) => false,
46            Err(idx) => {
47                self.sorted_elements.insert(idx, item);
48                true
49            }
50        }
51    }
52
53    /// Extend the set with the items from `other`.
54    pub fn extend(&mut self, other: impl IntoIterator<Item = T>) {
55        self.sorted_elements.extend(other);
56        self.sorted_elements.sort_unstable();
57        self.sorted_elements.dedup();
58    }
59
60    /// Check if the set contains `item`.
61    pub fn contains(&self, item: &T) -> bool {
62        self.sorted_elements.binary_search(item).is_ok()
63    }
64
65    /// Get the number of elements in the set.
66    pub fn len(&self) -> usize {
67        self.sorted_elements.len()
68    }
69
70    /// Check if the set is empty.
71    pub fn is_empty(&self) -> bool {
72        self.sorted_elements.is_empty()
73    }
74}
75
76impl<T: Ord> Default for VecSet<T> {
77    fn default() -> Self {
78        VecSet::new()
79    }
80}
81
82impl<T: Ord> Deref for VecSet<T> {
83    type Target = [T];
84
85    fn deref(&self) -> &Self::Target {
86        &self.sorted_elements
87    }
88}
89
90impl<T: Ord> Extend<T> for VecSet<T> {
91    fn extend<TI: IntoIterator<Item = T>>(&mut self, iter: TI) {
92        self.sorted_elements.extend(iter);
93        self.sorted_elements.sort_unstable();
94        self.sorted_elements.dedup();
95    }
96}
97
98impl<T: Ord> IntoIterator for VecSet<T> {
99    type Item = T;
100
101    type IntoIter = vec::IntoIter<Self::Item>;
102
103    fn into_iter(self) -> Self::IntoIter {
104        self.sorted_elements.into_iter()
105    }
106}
107
108impl<'e, T: Ord> IntoIterator for &'e VecSet<T> {
109    type Item = &'e T;
110
111    type IntoIter = std::slice::Iter<'e, T>;
112
113    fn into_iter(self) -> Self::IntoIter {
114        self.sorted_elements.iter()
115    }
116}
117
118impl<T: Ord> From<T> for VecSet<T> {
119    fn from(value: T) -> Self {
120        VecSet::singleton(value)
121    }
122}
dada_util/vecset.rs

dada_util/
vecset.rs
