catlog/zero/
set.rs

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

catlog/zero/
set.rs
