indexical/
set.rs

1//! An unordered collections of `T`s, implemented with a bit-set.
2
3use std::{borrow::Borrow, fmt};
4
5use index_vec::Idx;
6
7use crate::{
8    FromIndexicalIterator, IndexedDomain, IndexedValue, ToIndex, bitset::BitSet,
9    pointer::PointerFamily,
10};
11
12/// An unordered collections of `T`s, implemented with a bit-set.
13pub struct IndexSet<'a, T: IndexedValue + 'a, S, P: PointerFamily<'a>> {
14    set: S,
15    domain: P::Pointer<IndexedDomain<T>>,
16}
17
18impl<'a, T, S, P> IndexSet<'a, T, S, P>
19where
20    T: IndexedValue + 'a,
21    S: BitSet,
22    P: PointerFamily<'a>,
23{
24    /// Creates an empty index set.
25    pub fn new(domain: &P::Pointer<IndexedDomain<T>>) -> Self {
26        IndexSet {
27            set: S::empty(domain.len()),
28            domain: domain.clone(),
29        }
30    }
31
32    /// Returns an iterator over all the indices contained in `self`.
33    pub fn indices(&self) -> impl Iterator<Item = T::Index> {
34        self.set.iter().map(T::Index::from_usize)
35    }
36
37    /// Returns an iterator over all the objects contained in `self`.
38    pub fn iter(&self) -> impl Iterator<Item = &T> {
39        self.indices().map(move |idx| self.domain.value(idx))
40    }
41
42    /// Returns an iterator over the pairs of indices and objects contained in `self`.
43    pub fn iter_enumerated(&self) -> impl Iterator<Item = (T::Index, &T)> {
44        self.indices().map(move |idx| (idx, self.domain.value(idx)))
45    }
46
47    /// Returns true if `index` is contained in `self`.
48    pub fn contains<M>(&self, index: impl ToIndex<T, M>) -> bool {
49        let elem = index.to_index(&self.domain);
50        self.set.contains(elem.index())
51    }
52
53    /// Returns the number of elements in `self`.
54    pub fn len(&self) -> usize {
55        self.set.len()
56    }
57
58    /// Return true if `self` has no elements.
59    pub fn is_empty(&self) -> bool {
60        self.len() == 0
61    }
62
63    /// Returns true if every element in `other` is also in `self`.
64    pub fn is_superset(&self, other: &IndexSet<'a, T, S, P>) -> bool {
65        self.set.superset(&other.set)
66    }
67
68    /// Adds the element `elt` to `self`, returning true if `self` changed.
69    pub fn insert<M>(&mut self, elt: impl ToIndex<T, M>) -> bool {
70        let elt = elt.to_index(&self.domain);
71        self.set.insert(elt.index())
72    }
73
74    /// Removes the element `elt` from `self`, returning true if `self` changed.
75    pub fn remove<M>(&mut self, elt: impl ToIndex<T, M>) -> bool {
76        let elt = elt.to_index(&self.domain);
77        self.set.remove(elt.index())
78    }
79
80    /// Adds each element of `other` to `self`.
81    pub fn union(&mut self, other: &IndexSet<'a, T, S, P>) {
82        self.set.union(&other.set);
83    }
84
85    /// Adds each element of `other` to `self`, returning true if `self` changed.
86    pub fn union_changed(&mut self, other: &IndexSet<'a, T, S, P>) -> bool {
87        self.set.union_changed(&other.set)
88    }
89
90    /// Removes every element of `other` from `self`.
91    pub fn subtract(&mut self, other: &IndexSet<'a, T, S, P>) {
92        self.set.subtract(&other.set);
93    }
94
95    /// Removes every element of `other` from `self`, returning true if `self` changed.
96    pub fn subtract_changed(&mut self, other: &IndexSet<'a, T, S, P>) -> bool {
97        self.set.subtract_changed(&other.set)
98    }
99
100    /// Removes every element of `self` not in `other`.
101    pub fn intersect(&mut self, other: &IndexSet<'a, T, S, P>) {
102        self.set.intersect(&other.set);
103    }
104
105    /// Removes every element of `self` not in `other`, returning true if `self` changed.
106    pub fn intersect_changed(&mut self, other: &IndexSet<'a, T, S, P>) -> bool {
107        self.set.intersect_changed(&other.set)
108    }
109
110    /// Adds every element of the domain to `self`.
111    pub fn insert_all(&mut self) {
112        self.set.insert_all();
113    }
114
115    /// Removes every element from `self`.
116    pub fn clear(&mut self) {
117        self.set.clear();
118    }
119
120    /// Returns a reference to the inner set.
121    pub fn inner(&self) -> &S {
122        &self.set
123    }
124}
125
126impl<'a, T, S, P> fmt::Debug for IndexSet<'a, T, S, P>
127where
128    T: IndexedValue + fmt::Debug + 'a,
129    S: BitSet,
130    P: PointerFamily<'a>,
131{
132    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
133        f.debug_set().entries(self.iter()).finish()
134    }
135}
136
137impl<'a, T, S, P> PartialEq for IndexSet<'a, T, S, P>
138where
139    T: IndexedValue + 'a,
140    S: BitSet,
141    P: PointerFamily<'a>,
142{
143    fn eq(&self, other: &Self) -> bool {
144        self.set == other.set
145    }
146}
147
148impl<'a, T, S, P> Eq for IndexSet<'a, T, S, P>
149where
150    T: IndexedValue + 'a,
151    S: BitSet,
152    P: PointerFamily<'a>,
153{
154}
155
156impl<'a, T, S, P> Clone for IndexSet<'a, T, S, P>
157where
158    T: IndexedValue + 'a,
159    S: BitSet,
160    P: PointerFamily<'a>,
161{
162    fn clone(&self) -> Self {
163        IndexSet {
164            set: self.set.clone(),
165            domain: self.domain.clone(),
166        }
167    }
168
169    fn clone_from(&mut self, source: &Self) {
170        self.set.copy_from(&source.set);
171        self.domain = source.domain.clone();
172    }
173}
174
175impl<'a, T, U, S, M, P> FromIndexicalIterator<'a, T, P, M, U> for IndexSet<'a, T, S, P>
176where
177    T: IndexedValue + 'a,
178    S: BitSet,
179    P: PointerFamily<'a>,
180    U: ToIndex<T, M>,
181{
182    fn from_indexical_iter(
183        iter: impl Iterator<Item = U>,
184        domain: &P::Pointer<IndexedDomain<T>>,
185    ) -> Self {
186        let mut set = IndexSet::new(domain);
187        for s in iter {
188            set.insert(s);
189        }
190        set
191    }
192}
193
194/// Iterator extension trait for [`IndexSet`].
195pub trait IndexSetIteratorExt<
196    'a,
197    T: IndexedValue + 'a,
198    S: BitSet,
199    P: PointerFamily<'a>,
200    U: Borrow<IndexSet<'a, T, S, P>>,
201>: Iterator<Item = U> + Sized
202{
203    /// Returns the union of the input index sets.
204    fn union_indexical(self, domain: &P::Pointer<IndexedDomain<T>>) -> IndexSet<'a, T, S, P> {
205        let mut set = IndexSet::new(domain);
206        for other in self {
207            set.union(other.borrow());
208        }
209        set
210    }
211}
212
213impl<'a, I, T, S, P, U> IndexSetIteratorExt<'a, T, S, P, U> for I
214where
215    T: IndexedValue + 'a,
216    S: BitSet,
217    P: PointerFamily<'a>,
218    U: Borrow<IndexSet<'a, T, S, P>>,
219    I: Iterator<Item = U> + Sized,
220{
221}
222
223#[cfg(test)]
224mod test {
225    use crate::{IndexedDomain, IndexicalIteratorExt, test_utils::TestIndexSet};
226    use std::rc::Rc;
227
228    fn mk(s: &str) -> String {
229        s.to_string()
230    }
231
232    #[test]
233    fn test_indexset() {
234        let d = Rc::new(IndexedDomain::from_iter([mk("a"), mk("b"), mk("c")]));
235        let mut s = TestIndexSet::new(&d);
236        s.insert(mk("a"));
237        let b = d.index(&mk("b"));
238        s.insert(b);
239        assert!(s.contains(mk("a")));
240        assert!(s.contains(mk("b")));
241        assert_eq!(s.len(), 2);
242
243        assert_eq!(
244            [mk("a"), mk("b")]
245                .into_iter()
246                .collect_indexical::<TestIndexSet<_>>(&d),
247            s
248        );
249        assert_eq!(format!("{s:?}"), r#"{"a", "b"}"#)
250    }
251
252    #[cfg(feature = "bitvec")]
253    #[test]
254    fn test_indexset_reffamily() {
255        let d = &IndexedDomain::from_iter([mk("a"), mk("b"), mk("c")]);
256        let mut s = crate::bitset::bitvec::RefIndexSet::new(&d);
257        s.insert(mk("a"));
258        assert!(s.contains(mk("a")));
259
260        let s2 = s.clone();
261        assert!(std::ptr::eq(s.domain, s2.domain));
262    }
263}
indexical/set.rs

indexical/
set.rs
