crdt_kit/
twop_set.rs

1use alloc::collections::BTreeSet;
2
3use crate::Crdt;
4
5/// A two-phase set (2P-Set).
6///
7/// Elements can be added and removed, but once removed, they cannot be
8/// re-added. This is implemented with two G-Sets: one for additions
9/// and one for removals (tombstones).
10///
11/// # Example
12///
13/// ```
14/// use crdt_kit::prelude::*;
15///
16/// let mut s1 = TwoPSet::new();
17/// s1.insert("apple");
18/// s1.insert("banana");
19/// s1.remove(&"banana");
20///
21/// assert!(s1.contains(&"apple"));
22/// assert!(!s1.contains(&"banana")); // removed
23///
24/// let mut s2 = TwoPSet::new();
25/// s2.insert("banana"); // trying to re-add on another replica
26///
27/// s1.merge(&s2);
28/// assert!(!s1.contains(&"banana")); // still removed (tombstone wins)
29/// ```
30#[derive(Debug, Clone, PartialEq, Eq)]
31#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
32pub struct TwoPSet<T: Ord + Clone> {
33    added: BTreeSet<T>,
34    removed: BTreeSet<T>,
35}
36
37impl<T: Ord + Clone> TwoPSet<T> {
38    /// Create a new empty 2P-Set.
39    #[must_use]
40    pub fn new() -> Self {
41        Self {
42            added: BTreeSet::new(),
43            removed: BTreeSet::new(),
44        }
45    }
46
47    /// Insert an element.
48    ///
49    /// Returns `true` if the element was newly added (not previously
50    /// removed). If the element was already removed, it cannot be re-added
51    /// and this returns `false`.
52    pub fn insert(&mut self, value: T) -> bool {
53        if self.removed.contains(&value) {
54            return false;
55        }
56        self.added.insert(value)
57    }
58
59    /// Remove an element.
60    ///
61    /// The element must have been added first. Once removed, it can never
62    /// be re-added. Returns `true` if the element was present and is now removed.
63    pub fn remove(&mut self, value: &T) -> bool {
64        if self.added.contains(value) && !self.removed.contains(value) {
65            self.removed.insert(value.clone());
66            true
67        } else {
68            false
69        }
70    }
71
72    /// Check if the set contains an element (added and not removed).
73    #[must_use]
74    pub fn contains(&self, value: &T) -> bool {
75        self.added.contains(value) && !self.removed.contains(value)
76    }
77
78    /// Get the number of active elements (added minus removed).
79    #[must_use]
80    pub fn len(&self) -> usize {
81        self.added.difference(&self.removed).count()
82    }
83
84    /// Check if the set has no active elements.
85    #[must_use]
86    pub fn is_empty(&self) -> bool {
87        self.len() == 0
88    }
89
90    /// Iterate over active elements (added and not removed).
91    pub fn iter(&self) -> impl Iterator<Item = &T> {
92        self.added.difference(&self.removed)
93    }
94}
95
96impl<T: Ord + Clone> Default for TwoPSet<T> {
97    fn default() -> Self {
98        Self::new()
99    }
100}
101
102impl<T: Ord + Clone> Crdt for TwoPSet<T> {
103    fn merge(&mut self, other: &Self) {
104        for elem in &other.added {
105            self.added.insert(elem.clone());
106        }
107        for elem in &other.removed {
108            self.removed.insert(elem.clone());
109        }
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn new_set_is_empty() {
119        let s = TwoPSet::<String>::new();
120        assert!(s.is_empty());
121    }
122
123    #[test]
124    fn insert_and_contains() {
125        let mut s = TwoPSet::new();
126        s.insert("a");
127        assert!(s.contains(&"a"));
128        assert_eq!(s.len(), 1);
129    }
130
131    #[test]
132    fn remove_element() {
133        let mut s = TwoPSet::new();
134        s.insert("a");
135        assert!(s.remove(&"a"));
136        assert!(!s.contains(&"a"));
137        assert_eq!(s.len(), 0);
138    }
139
140    #[test]
141    fn cannot_readd_removed_element() {
142        let mut s = TwoPSet::new();
143        s.insert("a");
144        s.remove(&"a");
145        assert!(!s.insert("a")); // returns false
146        assert!(!s.contains(&"a"));
147    }
148
149    #[test]
150    fn remove_wins_on_merge() {
151        let mut s1 = TwoPSet::new();
152        s1.insert("a");
153        s1.remove(&"a");
154
155        let mut s2 = TwoPSet::new();
156        s2.insert("a"); // concurrent add
157
158        s1.merge(&s2);
159        assert!(!s1.contains(&"a")); // remove wins
160    }
161
162    #[test]
163    fn merge_is_commutative() {
164        let mut s1 = TwoPSet::new();
165        s1.insert("a");
166        s1.insert("b");
167        s1.remove(&"a");
168
169        let mut s2 = TwoPSet::new();
170        s2.insert("b");
171        s2.insert("c");
172
173        let mut left = s1.clone();
174        left.merge(&s2);
175
176        let mut right = s2.clone();
177        right.merge(&s1);
178
179        assert_eq!(left, right);
180    }
181
182    #[test]
183    fn merge_is_idempotent() {
184        let mut s1 = TwoPSet::new();
185        s1.insert("a");
186
187        let mut s2 = TwoPSet::new();
188        s2.insert("b");
189
190        s1.merge(&s2);
191        let after_first = s1.clone();
192        s1.merge(&s2);
193
194        assert_eq!(s1, after_first);
195    }
196
197    #[test]
198    fn iterate_active_elements() {
199        let mut s = TwoPSet::new();
200        s.insert(1);
201        s.insert(2);
202        s.insert(3);
203        s.remove(&2);
204
205        let active: Vec<&i32> = s.iter().collect();
206        assert_eq!(active, vec![&1, &3]);
207    }
208}
crdt_kit/twop_set.rs

crdt_kit/
twop_set.rs
