cvrdt_exposition/
two_phase_set.rs

1use crate::traits::{Grow, Shrink};
2use std::collections::HashSet;
3use std::hash::Hash;
4
5/// A set that can add or delete values
6///
7/// # Panics
8///
9/// Any attempt to `del` an element that one did  not previously `add` will panic:
10///
11/// ```should_panic
12/// // this will panic
13/// use std::collections::HashSet;
14/// use cvrdt_exposition::{Grow, Shrink, TwoPhaseSet};
15/// let mut x = TwoPhaseSet::new((HashSet::new(), HashSet::new()));
16/// x.del("this will panic");
17/// ```
18///
19/// # Examples
20///
21/// Example usage, including demonstrating some properties:
22///
23/// ```
24/// use std::collections::HashSet;
25/// use cvrdt_exposition::{Grow, Shrink, TwoPhaseSet};
26/// let mut x = TwoPhaseSet::new((HashSet::new(), HashSet::new()));
27/// for c in "abc".chars() {
28///     x.add(c);
29/// }
30/// x.del('c');
31/// assert_eq!(x.query(&'a'), true);
32/// assert_eq!(x.query(&'z'), false);
33/// assert_eq!(x.query(&'c'), false);
34/// let y = TwoPhaseSet::new(("abcdef".chars().collect(), HashSet::new()));
35/// assert_eq!(x.merge(&y).payload(), y.merge(&x).payload());
36/// let z = TwoPhaseSet::new(("8675309abcdefg".chars().collect(), "toremove".chars().collect()));
37/// assert_eq!(x.merge(&y.merge(&z)).payload(), x.merge(&y).merge(&z).payload());
38/// ```
39#[derive(Debug, Clone)]
40pub struct TwoPhaseSet<X: Clone + Eq + Hash> {
41    /// The elements that have been added to this set
42    pub added: HashSet<X>,
43    /// The elements that have been removed from this set
44    pub removed: HashSet<X>,
45}
46
47impl<X: Clone + Eq + Hash> Grow for TwoPhaseSet<X> {
48    type Payload = (HashSet<X>, HashSet<X>);
49    type Update = X;
50    type Query = X;
51    type Value = bool;
52
53    fn new(payload: Self::Payload) -> Self {
54        TwoPhaseSet {
55            added: payload.0,
56            removed: payload.1,
57        }
58    }
59    fn payload(&self) -> Self::Payload {
60        (self.added.clone(), self.removed.clone())
61    }
62    fn add(&mut self, update: Self::Update) {
63        self.added.insert(update);
64    }
65    fn le(&self, other: &Self) -> bool {
66        self.added.is_subset(&other.added) && self.removed.is_subset(&other.removed)
67    }
68    fn merge(&self, other: &Self) -> Self {
69        TwoPhaseSet {
70            added: self.added.union(&other.added).cloned().collect(),
71            removed: self.removed.union(&other.removed).cloned().collect(),
72        }
73    }
74    fn query(&self, query: &Self::Query) -> Self::Value {
75        self.added.contains(query) && !self.removed.contains(query)
76    }
77}
78
79impl<X: Clone + Eq + Hash> Shrink for TwoPhaseSet<X> {
80    fn del(&mut self, x: X) {
81        assert!(
82            self.query(&x),
83            "Only allowed for elements contained in 2PSet"
84        );
85        self.removed.insert(x);
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use crate::properties::{grow, shrink};
93    use proptest::prelude::*;
94
95    static MAX_SIZE: usize = 100;
96
97    fn cvrdt() -> impl Strategy<Value = TwoPhaseSet<String>> {
98        (
99            prop::collection::hash_set(any::<String>(), 0..MAX_SIZE),
100            prop::collection::hash_set(any::<String>(), 0..MAX_SIZE),
101        )
102            .prop_map(|(added, removed)| TwoPhaseSet { added, removed })
103    }
104
105    fn cvrdt_and_addend() -> impl Strategy<Value = (TwoPhaseSet<String>, String)> {
106        (cvrdt(), ".*")
107    }
108
109    fn cvrdt_and_subtrahend() -> impl Strategy<Value = (TwoPhaseSet<i8>, i8)> {
110        (
111            prop::collection::hash_set(any::<i8>(), 0..MAX_SIZE),
112            prop::collection::hash_set(any::<i8>(), 0..MAX_SIZE),
113            any::<i8>(),
114        )
115            .prop_flat_map(|(mut added, mut removed, x)| {
116                added.insert(x);
117                removed.remove(&x);
118                let t = TwoPhaseSet { added, removed };
119                (Just(t), Just(x))
120            })
121    }
122
123    grow!(cvrdt, cvrdt_and_addend);
124    shrink!(cvrdt_and_subtrahend);
125}
cvrdt_exposition/two_phase_set.rs

cvrdt_exposition/
two_phase_set.rs
