mdcs_core/
gset.rs

1//! Grow-only Set - elements can only be added, never removed
2//!  This is the simplest useful CRDT and a good starting point.
3
4use crate::lattice::Lattice;
5use serde::{Deserialize, Serialize};
6use std::collections::BTreeSet;
7// use std::hash:: Hash;
8
9/// A Grow-only Set (GSet) CRDT.
10///
11/// The simplest useful CRDT: elements can only be added, never removed.
12/// The join operation is set union, which is commutative, associative, and
13/// idempotent by definition.
14///
15/// # Example
16///
17/// ```rust
18/// use mdcs_core::GSet;
19/// use mdcs_core::Lattice;
20///
21/// let mut a = GSet::new();
22/// a.insert("hello");
23///
24/// let mut b = GSet::new();
25/// b.insert("world");
26///
27/// let merged = a.join(&b);
28/// assert!(merged.contains(&"hello"));
29/// assert!(merged.contains(&"world"));
30/// ```
31#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
32pub struct GSet<T: Ord + Clone> {
33    elements: BTreeSet<T>,
34}
35
36impl<T: Ord + Clone> GSet<T> {
37    /// Create a new empty GSet.
38    pub fn new() -> Self {
39        Self {
40            elements: BTreeSet::new(),
41        }
42    }
43
44    /// Add an element (the only mutation allowed)
45    pub fn insert(&mut self, value: T) {
46        self.elements.insert(value);
47    }
48
49    /// Check whether `value` is a member of this set.
50    pub fn contains(&self, value: &T) -> bool {
51        self.elements.contains(value)
52    }
53
54    /// Iterate over all elements in the set.
55    pub fn iter(&self) -> impl Iterator<Item = &T> {
56        self.elements.iter()
57    }
58
59    /// Return the number of elements in the set.
60    pub fn len(&self) -> usize {
61        self.elements.len()
62    }
63
64    /// Return `true` if the set contains no elements.
65    pub fn is_empty(&self) -> bool {
66        self.elements.is_empty()
67    }
68}
69
70impl<T: Ord + Clone> Default for GSet<T> {
71    fn default() -> Self {
72        Self::new()
73    }
74}
75
76impl<T: Ord + Clone> Lattice for GSet<T> {
77    fn bottom() -> Self {
78        Self::new()
79    }
80
81    fn join(&self, other: &Self) -> Self {
82        Self {
83            elements: self.elements.union(&other.elements).cloned().collect(),
84        }
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91    use proptest::prelude::*;
92
93    // Property-based tests for lattice laws
94    proptest! {
95        #[test]
96        fn gset_join_is_commutative(
97            a in prop::collection::btree_set(0i32..100, 0.. 20),
98            b in prop::collection::btree_set(0i32..100, 0..20)
99        ) {
100            let set_a = GSet { elements: a };
101            let set_b = GSet { elements: b };
102
103            prop_assert_eq!(set_a.join(&set_b), set_b.join(&set_a));
104        }
105
106        #[test]
107        fn gset_join_is_associative(
108            a in prop::collection::btree_set(0i32.. 100, 0.. 10),
109            b in prop::collection::btree_set(0i32..100, 0..10),
110            c in prop::collection::btree_set(0i32..100, 0..10)
111        ) {
112            let set_a = GSet { elements:  a };
113            let set_b = GSet { elements: b };
114            let set_c = GSet { elements: c };
115
116            let left = set_a. join(&set_b).join(&set_c);
117            let right = set_a.join(&set_b. join(&set_c));
118
119            prop_assert_eq!(left, right);
120        }
121
122        #[test]
123        fn gset_join_is_idempotent(
124            a in prop:: collection::btree_set(0i32..100, 0..20)
125        ) {
126            let set_a = GSet { elements: a };
127
128            prop_assert_eq!(set_a.join(&set_a), set_a);
129        }
130    }
131}
mdcs_core/gset.rs

mdcs_core/
gset.rs
