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        // Clone current elements and extend with elements from `other`.
83        let mut elements = self.elements.clone();
84        elements.extend(other.elements.iter().cloned());
85        Self { elements }
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use proptest::prelude::*;
93
94    // Property-based tests for lattice laws
95    proptest! {
96        #[test]
97        fn gset_join_is_commutative(
98            a in prop::collection::btree_set(0i32..100, 0.. 20),
99            b in prop::collection::btree_set(0i32..100, 0..20)
100        ) {
101            let set_a = GSet { elements: a };
102            let set_b = GSet { elements: b };
103
104            prop_assert_eq!(set_a.join(&set_b), set_b.join(&set_a));
105        }
106
107        #[test]
108        fn gset_join_is_associative(
109            a in prop::collection::btree_set(0i32.. 100, 0.. 10),
110            b in prop::collection::btree_set(0i32..100, 0..10),
111            c in prop::collection::btree_set(0i32..100, 0..10)
112        ) {
113            let set_a = GSet { elements:  a };
114            let set_b = GSet { elements: b };
115            let set_c = GSet { elements: c };
116
117            let left = set_a. join(&set_b).join(&set_c);
118            let right = set_a.join(&set_b. join(&set_c));
119
120            prop_assert_eq!(left, right);
121        }
122
123        #[test]
124        fn gset_join_is_idempotent(
125            a in prop:: collection::btree_set(0i32..100, 0..20)
126        ) {
127            let set_a = GSet { elements: a };
128
129            prop_assert_eq!(set_a.join(&set_a), set_a);
130        }
131    }
132}
mdcs_core/gset.rs

mdcs_core/
gset.rs
