crdt_kit/
gset.rs

1use std::collections::BTreeSet;
2
3use crate::Crdt;
4
5/// A grow-only set (G-Set).
6///
7/// Elements can be added but never removed. Merge is simply the union
8/// of both sets. This is the simplest set CRDT.
9///
10/// # Example
11///
12/// ```
13/// use crdt_kit::prelude::*;
14///
15/// let mut s1 = GSet::new();
16/// s1.insert("apple");
17/// s1.insert("banana");
18///
19/// let mut s2 = GSet::new();
20/// s2.insert("cherry");
21///
22/// s1.merge(&s2);
23/// assert_eq!(s1.len(), 3);
24/// assert!(s1.contains(&"cherry"));
25/// ```
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct GSet<T: Ord + Clone> {
28    elements: BTreeSet<T>,
29}
30
31impl<T: Ord + Clone> GSet<T> {
32    /// Create a new empty G-Set.
33    #[must_use]
34    pub fn new() -> Self {
35        Self {
36            elements: BTreeSet::new(),
37        }
38    }
39
40    /// Insert an element into the set.
41    ///
42    /// Returns `true` if the element was newly inserted.
43    pub fn insert(&mut self, value: T) -> bool {
44        self.elements.insert(value)
45    }
46
47    /// Check if the set contains an element.
48    #[must_use]
49    pub fn contains(&self, value: &T) -> bool {
50        self.elements.contains(value)
51    }
52
53    /// Get the number of elements in the set.
54    #[must_use]
55    pub fn len(&self) -> usize {
56        self.elements.len()
57    }
58
59    /// Check if the set is empty.
60    #[must_use]
61    pub fn is_empty(&self) -> bool {
62        self.elements.is_empty()
63    }
64
65    /// Iterate over the elements in the set.
66    pub fn iter(&self) -> impl Iterator<Item = &T> {
67        self.elements.iter()
68    }
69}
70
71impl<T: Ord + Clone> Default for GSet<T> {
72    fn default() -> Self {
73        Self::new()
74    }
75}
76
77impl<T: Ord + Clone> Crdt for GSet<T> {
78    fn merge(&mut self, other: &Self) {
79        for elem in &other.elements {
80            self.elements.insert(elem.clone());
81        }
82    }
83}
84
85impl<T: Ord + Clone> IntoIterator for GSet<T> {
86    type Item = T;
87    type IntoIter = std::collections::btree_set::IntoIter<T>;
88
89    fn into_iter(self) -> Self::IntoIter {
90        self.elements.into_iter()
91    }
92}
93
94impl<T: Ord + Clone> FromIterator<T> for GSet<T> {
95    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
96        Self {
97            elements: BTreeSet::from_iter(iter),
98        }
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn new_set_is_empty() {
108        let s = GSet::<String>::new();
109        assert!(s.is_empty());
110        assert_eq!(s.len(), 0);
111    }
112
113    #[test]
114    fn insert_and_contains() {
115        let mut s = GSet::new();
116        assert!(s.insert("a"));
117        assert!(s.contains(&"a"));
118        assert!(!s.contains(&"b"));
119    }
120
121    #[test]
122    fn insert_duplicate_returns_false() {
123        let mut s = GSet::new();
124        assert!(s.insert("a"));
125        assert!(!s.insert("a"));
126        assert_eq!(s.len(), 1);
127    }
128
129    #[test]
130    fn merge_is_union() {
131        let mut s1 = GSet::new();
132        s1.insert(1);
133        s1.insert(2);
134
135        let mut s2 = GSet::new();
136        s2.insert(2);
137        s2.insert(3);
138
139        s1.merge(&s2);
140        assert_eq!(s1.len(), 3);
141        assert!(s1.contains(&1));
142        assert!(s1.contains(&2));
143        assert!(s1.contains(&3));
144    }
145
146    #[test]
147    fn merge_is_commutative() {
148        let mut s1 = GSet::new();
149        s1.insert("a");
150
151        let mut s2 = GSet::new();
152        s2.insert("b");
153
154        let mut left = s1.clone();
155        left.merge(&s2);
156
157        let mut right = s2.clone();
158        right.merge(&s1);
159
160        assert_eq!(left, right);
161    }
162
163    #[test]
164    fn merge_is_idempotent() {
165        let mut s1 = GSet::new();
166        s1.insert(1);
167
168        let mut s2 = GSet::new();
169        s2.insert(2);
170
171        s1.merge(&s2);
172        let after_first = s1.clone();
173        s1.merge(&s2);
174
175        assert_eq!(s1, after_first);
176    }
177
178    #[test]
179    fn from_iterator() {
180        let s: GSet<i32> = vec![1, 2, 3].into_iter().collect();
181        assert_eq!(s.len(), 3);
182    }
183}
crdt_kit/gset.rs

crdt_kit/
gset.rs
