crdt_kit/
gset.rs

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

crdt_kit/
gset.rs
