lattices/
set_union.rs

Help
1//! Module containing the [`SetUnion`] lattice and aliases for different datastructures.
2
3use std::cmp::Ordering::{self, *};
4use std::collections::{BTreeSet, HashSet};
5use std::marker::PhantomData;
6
7use cc_traits::SimpleCollectionRef;
8
9use crate::cc_traits::{Iter, Len, Set};
10use crate::collections::{ArraySet, OptionSet, SingletonSet};
11use crate::{Atomize, DeepReveal, IsBot, IsTop, LatticeBimorphism, LatticeFrom, LatticeOrd, Merge};
12
13/// Set-union lattice.
14///
15/// Merging set-union lattices is done by unioning the keys.
16#[repr(transparent)]
17#[derive(Copy, Clone, Debug, Default)]
18#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
19pub struct SetUnion<Set>(pub Set);
20impl<Set> SetUnion<Set> {
21    /// Create a new `SetUnion` from a `Set`.
22    pub fn new(val: Set) -> Self {
23        Self(val)
24    }
25
26    /// Create a new `SetUnion` from an `Into<Set>`.
27    pub fn new_from(val: impl Into<Set>) -> Self {
28        Self::new(val.into())
29    }
30
31    /// Reveal the inner value as a shared reference.
32    pub fn as_reveal_ref(&self) -> &Set {
33        &self.0
34    }
35
36    /// Reveal the inner value as an exclusive reference.
37    pub fn as_reveal_mut(&mut self) -> &mut Set {
38        &mut self.0
39    }
40
41    /// Gets the inner by value, consuming self.
42    pub fn into_reveal(self) -> Set {
43        self.0
44    }
45}
46
47impl<Set> DeepReveal for SetUnion<Set> {
48    type Revealed = Set;
49
50    fn deep_reveal(self) -> Self::Revealed {
51        self.0
52    }
53}
54
55impl<SetSelf, SetOther, Item> Merge<SetUnion<SetOther>> for SetUnion<SetSelf>
56where
57    SetSelf: Extend<Item> + Len,
58    SetOther: IntoIterator<Item = Item>,
59{
60    fn merge(&mut self, other: SetUnion<SetOther>) -> bool {
61        let old_len = self.0.len();
62        self.0.extend(other.0);
63        self.0.len() > old_len
64    }
65}
66
67impl<SetSelf, SetOther, Item> LatticeFrom<SetUnion<SetOther>> for SetUnion<SetSelf>
68where
69    SetSelf: FromIterator<Item>,
70    SetOther: IntoIterator<Item = Item>,
71{
72    fn lattice_from(other: SetUnion<SetOther>) -> Self {
73        Self(other.0.into_iter().collect())
74    }
75}
76
77impl<SetSelf, SetOther, Item> PartialOrd<SetUnion<SetOther>> for SetUnion<SetSelf>
78where
79    SetSelf: Set<Item, Item = Item> + Iter,
80    SetOther: Set<Item, Item = Item> + Iter,
81{
82    fn partial_cmp(&self, other: &SetUnion<SetOther>) -> Option<Ordering> {
83        match self.0.len().cmp(&other.0.len()) {
84            Greater => {
85                if other.0.iter().all(|key| self.0.contains(&*key)) {
86                    Some(Greater)
87                } else {
88                    None
89                }
90            }
91            Equal => {
92                if self.0.iter().all(|key| other.0.contains(&*key)) {
93                    Some(Equal)
94                } else {
95                    None
96                }
97            }
98            Less => {
99                if self.0.iter().all(|key| other.0.contains(&*key)) {
100                    Some(Less)
101                } else {
102                    None
103                }
104            }
105        }
106    }
107}
108impl<SetSelf, SetOther> LatticeOrd<SetUnion<SetOther>> for SetUnion<SetSelf> where
109    Self: PartialOrd<SetUnion<SetOther>>
110{
111}
112
113impl<SetSelf, SetOther, Item> PartialEq<SetUnion<SetOther>> for SetUnion<SetSelf>
114where
115    SetSelf: Set<Item, Item = Item> + Iter,
116    SetOther: Set<Item, Item = Item> + Iter,
117{
118    fn eq(&self, other: &SetUnion<SetOther>) -> bool {
119        if self.0.len() != other.0.len() {
120            return false;
121        }
122
123        self.0.iter().all(|key| other.0.contains(&*key))
124    }
125}
126impl<SetSelf> Eq for SetUnion<SetSelf> where Self: PartialEq {}
127
128impl<Set> IsBot for SetUnion<Set>
129where
130    Set: Len,
131{
132    fn is_bot(&self) -> bool {
133        self.0.is_empty()
134    }
135}
136
137impl<Set> IsTop for SetUnion<Set> {
138    fn is_top(&self) -> bool {
139        false
140    }
141}
142
143impl<Set, Item> Atomize for SetUnion<Set>
144where
145    Set: Len + IntoIterator<Item = Item> + Extend<Item>,
146    Set::IntoIter: 'static,
147    Item: 'static,
148{
149    type Atom = SetUnionSingletonSet<Item>;
150
151    // TODO: use impl trait, then remove 'static.
152    type AtomIter = Box<dyn Iterator<Item = Self::Atom>>;
153
154    fn atomize(self) -> Self::AtomIter {
155        Box::new(self.0.into_iter().map(SetUnionSingletonSet::new_from))
156    }
157}
158
159/// [`std::collections::HashSet`]-backed [`SetUnion`] lattice.
160pub type SetUnionHashSet<Item> = SetUnion<HashSet<Item>>;
161
162/// [`std::collections::BTreeSet`]-backed [`SetUnion`] lattice.
163pub type SetUnionBTreeSet<Item> = SetUnion<BTreeSet<Item>>;
164
165/// [`Vec`]-backed [`SetUnion`] lattice.
166pub type SetUnionVec<Item> = SetUnion<Vec<Item>>;
167
168/// [`crate::collections::ArraySet`]-backed [`SetUnion`] lattice.
169pub type SetUnionArray<Item, const N: usize> = SetUnion<ArraySet<Item, N>>;
170
171/// [`crate::collections::SingletonSet`]-backed [`SetUnion`] lattice.
172pub type SetUnionSingletonSet<Item> = SetUnion<SingletonSet<Item>>;
173
174/// [`Option`]-backed [`SetUnion`] lattice.
175pub type SetUnionOptionSet<Item> = SetUnion<OptionSet<Item>>;
176
177/// Bimorphism for the cartesian product of two sets. Output is a set of all possible pairs of
178/// items from the two input sets.
179pub struct CartesianProductBimorphism<SetOut> {
180    _phantom: PhantomData<fn() -> SetOut>,
181}
182impl<SetOut> Default for CartesianProductBimorphism<SetOut> {
183    fn default() -> Self {
184        Self {
185            _phantom: Default::default(),
186        }
187    }
188}
189impl<SetA, SetB, SetOut> LatticeBimorphism<SetUnion<SetA>, SetUnion<SetB>>
190    for CartesianProductBimorphism<SetOut>
191where
192    SetA: IntoIterator,
193    SetB: Iter + SimpleCollectionRef,
194    SetA::Item: Clone,
195    SetB::Item: Clone,
196    SetOut: FromIterator<(SetA::Item, SetB::Item)>,
197{
198    type Output = SetUnion<SetOut>;
199
200    fn call(&mut self, lat_a: SetUnion<SetA>, lat_b: SetUnion<SetB>) -> Self::Output {
201        let set_a = lat_a.into_reveal();
202        let set_b = lat_b.into_reveal();
203        let set_out = set_a
204            .into_iter()
205            .flat_map(|a_item| {
206                set_b
207                    .iter()
208                    .map(<SetB as SimpleCollectionRef>::into_ref)
209                    .cloned()
210                    .map(move |b_item| (a_item.clone(), b_item))
211            })
212            .collect::<SetOut>();
213        SetUnion::new(set_out)
214    }
215}
216
217#[cfg(test)]
218mod test {
219    use super::*;
220    use crate::test::{check_all, check_atomize_each, check_lattice_bimorphism};
221
222    #[test]
223    fn test_set_union() {
224        let mut my_set_a = SetUnionHashSet::<&str>::new(HashSet::new());
225        let my_set_b = SetUnionBTreeSet::<&str>::new(BTreeSet::new());
226        let my_set_c = SetUnionSingletonSet::new(SingletonSet("hello world"));
227
228        assert_eq!(Some(Equal), my_set_a.partial_cmp(&my_set_a));
229        assert_eq!(Some(Equal), my_set_a.partial_cmp(&my_set_b));
230        assert_eq!(Some(Less), my_set_a.partial_cmp(&my_set_c));
231        assert_eq!(Some(Equal), my_set_b.partial_cmp(&my_set_a));
232        assert_eq!(Some(Equal), my_set_b.partial_cmp(&my_set_b));
233        assert_eq!(Some(Less), my_set_b.partial_cmp(&my_set_c));
234        assert_eq!(Some(Greater), my_set_c.partial_cmp(&my_set_a));
235        assert_eq!(Some(Greater), my_set_c.partial_cmp(&my_set_b));
236        assert_eq!(Some(Equal), my_set_c.partial_cmp(&my_set_c));
237
238        assert!(!my_set_a.merge(my_set_b));
239        assert!(my_set_a.merge(my_set_c));
240    }
241
242    #[test]
243    fn test_singleton_example() {
244        let mut my_hash_set = SetUnionHashSet::<&str>::default();
245        let my_delta_set = SetUnionSingletonSet::new_from("hello world");
246        let my_array_set = SetUnionArray::new_from(["hello world", "b", "c", "d"]);
247
248        assert_eq!(Some(Equal), my_delta_set.partial_cmp(&my_delta_set));
249        assert_eq!(Some(Less), my_delta_set.partial_cmp(&my_array_set));
250        assert_eq!(Some(Greater), my_array_set.partial_cmp(&my_delta_set));
251        assert_eq!(Some(Equal), my_array_set.partial_cmp(&my_array_set));
252
253        assert!(my_hash_set.merge(my_array_set)); // Changes
254        assert!(!my_hash_set.merge(my_delta_set)); // No changes
255    }
256
257    #[test]
258    fn consistency() {
259        check_all(&[
260            SetUnionHashSet::new_from([]),
261            SetUnionHashSet::new_from([0]),
262            SetUnionHashSet::new_from([1]),
263            SetUnionHashSet::new_from([0, 1]),
264        ]);
265    }
266
267    #[test]
268    fn atomize() {
269        check_atomize_each(&[
270            SetUnionHashSet::new_from([]),
271            SetUnionHashSet::new_from([0]),
272            SetUnionHashSet::new_from([1]),
273            SetUnionHashSet::new_from([0, 1]),
274            SetUnionHashSet::new((0..10).collect()),
275        ]);
276    }
277
278    #[test]
279    fn cartesian_product() {
280        let items_a = &[
281            SetUnionHashSet::new_from([]),
282            SetUnionHashSet::new_from([0]),
283            SetUnionHashSet::new_from([1]),
284            SetUnionHashSet::new_from([0, 1]),
285        ];
286        let items_b = &[
287            SetUnionBTreeSet::new("hello".chars().collect()),
288            SetUnionBTreeSet::new("world".chars().collect()),
289        ];
290
291        check_lattice_bimorphism(
292            CartesianProductBimorphism::<HashSet<_>>::default(),
293            items_a,
294            items_a,
295        );
296        check_lattice_bimorphism(
297            CartesianProductBimorphism::<HashSet<_>>::default(),
298            items_a,
299            items_b,
300        );
301        check_lattice_bimorphism(
302            CartesianProductBimorphism::<HashSet<_>>::default(),
303            items_b,
304            items_a,
305        );
306        check_lattice_bimorphism(
307            CartesianProductBimorphism::<HashSet<_>>::default(),
308            items_b,
309            items_b,
310        );
311    }
312}
lattices/set_union.rs

lattices/
set_union.rs
