catlog/zero/
set.rs

1/*! Sets, finite and infinite.
2
3This module provides interfaces and simple wrapper types to enable sets to be
4treated in a generic way.
5 */
6
7use std::collections::HashSet;
8use std::hash::{BuildHasher, BuildHasherDefault, Hash, RandomState};
9use std::ops::Range;
10
11use derivative::Derivative;
12use derive_more::{From, Into};
13use ref_cast::RefCast;
14use ustr::{IdentityHasher, Ustr};
15
16/** A set.
17
18The interface is minimal. A set has an element type ([`Elem`](Self::Elem)) and
19can check whether values of that type belongs to the set. Sets are not assumed
20to be finite.
21 */
22pub trait Set {
23    /** Type of elements of the set.
24
25    Elements can be compared for equality, as required by ordinary mathematics.
26    Elements can also be cloned and, in practice, we tend to assume that they
27    can be *cheaply* cloned.
28    */
29    type Elem: Eq + Clone;
30
31    /// Does the set contain the element `x`?
32    fn contains(&self, x: &Self::Elem) -> bool;
33}
34
35/** A finite set.
36
37In addition to checking for element containment, finite sets know their size and
38are iterable. The elements of a finite set are assumed to be cheaply cloneable
39values, such as integers or interned strings. Thus, iteration of elements is by
40value, not by reference.
41 */
42pub trait FinSet: Set {
43    /** Iterates over elements of the finite set.
44
45    Though finite sets have a definite size, the iterator is not required to be
46    an [`ExactSizeIterator`] because they are not stable under even predictable
47    operations like chaining. Instead, retrieve the size of the set through the
48    separate method [`len`](FinSet::len).
49    */
50    fn iter(&self) -> impl Iterator<Item = Self::Elem>;
51
52    /// The size of the finite set.
53    fn len(&self) -> usize {
54        self.iter().count()
55    }
56
57    /// Is the set empty?
58    fn is_empty(&self) -> bool {
59        self.len() == 0
60    }
61}
62
63/** A skeletal finite set.
64
65The elements of the skeletal finite set of size `n` are the numbers `0..n`
66(excluding `n`).
67 */
68#[derive(Clone, Copy, Debug, From, Into, PartialEq, Eq, RefCast)]
69#[repr(transparent)]
70pub struct SkelFinSet(usize);
71
72impl SkelFinSet {
73    /// Adds the (unique possible) next element to the skeletal finite set.
74    pub fn insert(&mut self) -> usize {
75        let new = self.0;
76        self.0 += 1;
77        new
78    }
79
80    /// Adds the next `n` elements to the skeletal finite set.
81    pub fn extend(&mut self, n: usize) -> Range<usize> {
82        let start = self.0;
83        self.0 += n;
84        start..(self.0)
85    }
86}
87
88impl Default for SkelFinSet {
89    fn default() -> Self {
90        Self::from(0)
91    }
92}
93
94impl Set for SkelFinSet {
95    type Elem = usize;
96
97    fn contains(&self, x: &usize) -> bool {
98        *x < self.0
99    }
100}
101
102impl FinSet for SkelFinSet {
103    fn iter(&self) -> impl Iterator<Item = usize> {
104        0..(self.0)
105    }
106    fn len(&self) -> usize {
107        self.0
108    }
109}
110
111impl IntoIterator for SkelFinSet {
112    type Item = usize;
113    type IntoIter = Range<usize>;
114
115    fn into_iter(self) -> Self::IntoIter {
116        0..(self.0)
117    }
118}
119
120/// A finite set backed by a hash set.
121#[derive(Clone, Debug, From, Into, Derivative)]
122#[derivative(Default(bound = "S: Default"))]
123#[derivative(PartialEq(bound = "T: Eq + Hash, S: BuildHasher"))]
124#[derivative(Eq(bound = "T: Eq + Hash, S: BuildHasher"))]
125pub struct HashFinSet<T, S = RandomState>(HashSet<T, S>);
126
127/// A finite set with elements of type `Ustr`.
128pub type UstrFinSet = HashFinSet<Ustr, BuildHasherDefault<IdentityHasher>>;
129
130impl<T, S> HashFinSet<T, S>
131where
132    T: Eq + Hash,
133    S: BuildHasher,
134{
135    /// Adds an element to the set.
136    pub fn insert(&mut self, x: T) -> bool {
137        self.0.insert(x)
138    }
139}
140
141impl<T, S> Extend<T> for HashFinSet<T, S>
142where
143    T: Eq + Hash,
144    S: BuildHasher,
145{
146    fn extend<Iter>(&mut self, iter: Iter)
147    where
148        Iter: IntoIterator<Item = T>,
149    {
150        self.0.extend(iter)
151    }
152}
153
154impl<T, S> Set for HashFinSet<T, S>
155where
156    T: Eq + Clone + Hash,
157    S: BuildHasher,
158{
159    type Elem = T;
160
161    fn contains(&self, x: &T) -> bool {
162        self.0.contains(x)
163    }
164}
165
166impl<T, S> FinSet for HashFinSet<T, S>
167where
168    T: Eq + Hash + Clone,
169    S: BuildHasher,
170{
171    fn iter(&self) -> impl Iterator<Item = T> {
172        self.0.iter().cloned()
173    }
174    fn len(&self) -> usize {
175        self.0.len()
176    }
177    fn is_empty(&self) -> bool {
178        self.0.is_empty()
179    }
180}
181
182impl<T, S> IntoIterator for HashFinSet<T, S>
183where
184    T: Eq + Hash,
185    S: BuildHasher,
186{
187    type Item = T;
188    type IntoIter = std::collections::hash_set::IntoIter<T>;
189
190    fn into_iter(self) -> Self::IntoIter {
191        self.0.into_iter()
192    }
193}
194
195/** A skeletal finite set with a data attribute.
196
197The internal representation is simply a vector.
198*/
199#[derive(Clone, Debug, From, Derivative)]
200#[derivative(Default(bound = ""))]
201#[derivative(PartialEq(bound = "T: PartialEq"))]
202#[derivative(Eq(bound = "T: Eq"))]
203pub struct AttributedSkelSet<T>(Vec<T>);
204
205impl<T> AttributedSkelSet<T> {
206    /// Adds a new element with an associated data value.
207    pub fn insert(&mut self, value: T) -> usize {
208        let new = self.0.len();
209        self.0.push(value);
210        new
211    }
212
213    /// Adds multiple new elements with associated values.
214    pub fn extend<Iter>(&mut self, iter: Iter) -> Range<usize>
215    where
216        Iter: IntoIterator<Item = T>,
217    {
218        let start = self.0.len();
219        self.0.extend(iter);
220        start..(self.0.len())
221    }
222
223    /// View the data value associated with an element.
224    pub fn view(&self, x: usize) -> &T {
225        &self.0[x]
226    }
227}
228
229impl<T> Set for AttributedSkelSet<T> {
230    type Elem = usize;
231
232    fn contains(&self, x: &usize) -> bool {
233        *x < self.0.len()
234    }
235}
236
237impl<T> FinSet for AttributedSkelSet<T> {
238    fn iter(&self) -> impl Iterator<Item = usize> {
239        0..(self.0.len())
240    }
241    fn len(&self) -> usize {
242        self.0.len()
243    }
244    fn is_empty(&self) -> bool {
245        self.0.is_empty()
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252
253    #[test]
254    fn skel_fin_set() {
255        let mut s: SkelFinSet = Default::default();
256        assert!(s.is_empty());
257        assert_eq!(s.insert(), 0);
258        assert!(!s.is_empty());
259        assert_eq!(s.extend(2), 1..3);
260        assert_eq!(s.len(), 3);
261        assert!(s.contains(&2));
262        assert!(!s.contains(&3));
263        let n: usize = s.into();
264        assert_eq!(n, 3);
265
266        let s = SkelFinSet::from(3);
267        let sum: usize = s.iter().sum();
268        assert_eq!(sum, 3);
269        let elems: Vec<usize> = s.into_iter().collect();
270        assert_eq!(elems, vec![0, 1, 2]);
271    }
272
273    #[test]
274    fn hash_fin_set() {
275        let mut s: HashFinSet<i32> = Default::default();
276        assert!(s.is_empty());
277        s.insert(3);
278        s.extend([5, 7]);
279        assert!(!s.is_empty());
280        assert_eq!(s.len(), 3);
281        assert!(s.contains(&3));
282        assert!(s.contains(&7));
283        assert!(!s.contains(&2));
284
285        let s = HashFinSet::from(HashSet::from([3, 5, 7]));
286        let sum: i32 = s.iter().sum();
287        assert_eq!(sum, 15);
288        assert_eq!(s.len(), 3);
289    }
290
291    #[test]
292    fn attributed_skel_set() {
293        let mut s: AttributedSkelSet<char> = Default::default();
294        assert!(s.is_empty());
295        assert_eq!(s.insert('a'), 0);
296        assert_eq!(s.extend(['b', 'c'].into_iter()), 1..3);
297        assert!(!s.is_empty());
298        assert_eq!(s.len(), 3);
299        assert!(s.contains(&2));
300        assert!(!s.contains(&3));
301        assert_eq!(*s.view(1), 'b');
302    }
303}
catlog/zero/set.rs

catlog/zero/
set.rs
