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#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
10pub struct GSet<T: Ord + Clone> {
11    elements: BTreeSet<T>,
12}
13
14impl<T: Ord + Clone> GSet<T> {
15    pub fn new() -> Self {
16        Self {
17            elements: BTreeSet::new(),
18        }
19    }
20
21    /// Add an element (the only mutation allowed)
22    pub fn insert(&mut self, value: T) {
23        self.elements.insert(value);
24    }
25
26    pub fn contains(&self, value: &T) -> bool {
27        self.elements.contains(value)
28    }
29
30    pub fn iter(&self) -> impl Iterator<Item = &T> {
31        self.elements.iter()
32    }
33
34    pub fn len(&self) -> usize {
35        self.elements.len()
36    }
37
38    pub fn is_empty(&self) -> bool {
39        self.elements.is_empty()
40    }
41}
42
43impl<T: Ord + Clone> Default for GSet<T> {
44    fn default() -> Self {
45        Self::new()
46    }
47}
48
49impl<T: Ord + Clone> Lattice for GSet<T> {
50    fn bottom() -> Self {
51        Self::new()
52    }
53
54    fn join(&self, other: &Self) -> Self {
55        Self {
56            elements: self.elements.union(&other.elements).cloned().collect(),
57        }
58    }
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64    use proptest::prelude::*;
65
66    // Property-based tests for lattice laws
67    proptest! {
68        #[test]
69        fn gset_join_is_commutative(
70            a in prop::collection::btree_set(0i32..100, 0.. 20),
71            b in prop::collection::btree_set(0i32..100, 0..20)
72        ) {
73            let set_a = GSet { elements: a };
74            let set_b = GSet { elements: b };
75
76            prop_assert_eq!(set_a.join(&set_b), set_b.join(&set_a));
77        }
78
79        #[test]
80        fn gset_join_is_associative(
81            a in prop::collection::btree_set(0i32.. 100, 0.. 10),
82            b in prop::collection::btree_set(0i32..100, 0..10),
83            c in prop::collection::btree_set(0i32..100, 0..10)
84        ) {
85            let set_a = GSet { elements:  a };
86            let set_b = GSet { elements: b };
87            let set_c = GSet { elements: c };
88
89            let left = set_a. join(&set_b).join(&set_c);
90            let right = set_a.join(&set_b. join(&set_c));
91
92            prop_assert_eq!(left, right);
93        }
94
95        #[test]
96        fn gset_join_is_idempotent(
97            a in prop:: collection::btree_set(0i32..100, 0..20)
98        ) {
99            let set_a = GSet { elements: a };
100
101            prop_assert_eq!(set_a.join(&set_a), set_a);
102        }
103    }
104}
mdcs_core/gset.rs

mdcs_core/
gset.rs
