lattices/
set_union.rs

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

lattices/
set_union.rs
