bones_core/crdt/
gset.rs

1use serde::{Deserialize, Serialize};
2use std::collections::HashSet;
3
4/// Grow-only Set (G-Set) CRDT.
5///
6/// Elements are typically event hashes (Strings) referencing comment content.
7/// The merge operation is a simple set union.
8///
9/// Satisfies semilattice properties:
10/// - Commutative: a ∪ b = b ∪ a
11/// - Associative: (a ∪ b) ∪ c = a ∪ (b ∪ c)
12/// - Idempotent: a ∪ a = a
13#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Default)]
14pub struct GSet<T: Eq + std::hash::Hash + Clone> {
15    pub elements: HashSet<T>,
16}
17
18impl<T: Eq + std::hash::Hash + Clone> GSet<T> {
19    /// Create a new empty G-Set.
20    #[must_use]
21    pub fn new() -> Self {
22        Self {
23            elements: HashSet::new(),
24        }
25    }
26
27    /// Insert an element into the set.
28    pub fn insert(&mut self, element: T) {
29        self.elements.insert(element);
30    }
31
32    /// Merge another G-Set into this one (set union).
33    pub fn merge(&mut self, other: Self) {
34        for element in other.elements {
35            self.elements.insert(element);
36        }
37    }
38
39    /// Returns true if the set contains the element.
40    pub fn contains(&self, element: &T) -> bool {
41        self.elements.contains(element)
42    }
43
44    /// Returns the number of elements in the set.
45    #[must_use]
46    pub fn len(&self) -> usize {
47        self.elements.len()
48    }
49
50    /// Returns true if the set is empty.
51    #[must_use]
52    pub fn is_empty(&self) -> bool {
53        self.elements.is_empty()
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_gset_insert() {
63        let mut set = GSet::new();
64        set.insert("hash1".to_string());
65        set.insert("hash2".to_string());
66        assert_eq!(set.len(), 2);
67        assert!(set.contains(&"hash1".to_string()));
68        assert!(set.contains(&"hash2".to_string()));
69    }
70
71    #[test]
72    fn test_gset_idempotent_insert() {
73        let mut set = GSet::new();
74        set.insert("hash1".to_string());
75        set.insert("hash1".to_string());
76        assert_eq!(set.len(), 1);
77    }
78
79    #[test]
80    fn test_gset_merge() {
81        let mut a = GSet::new();
82        a.insert("hash1".to_string());
83
84        let mut b = GSet::new();
85        b.insert("hash2".to_string());
86
87        a.merge(b);
88        assert_eq!(a.len(), 2);
89        assert!(a.contains(&"hash1".to_string()));
90        assert!(a.contains(&"hash2".to_string()));
91    }
92
93    #[test]
94    fn test_gset_semilattice_commutative() {
95        let mut a = GSet::new();
96        a.insert("hash1".to_string());
97        let mut b = GSet::new();
98        b.insert("hash2".to_string());
99
100        let mut a_merge_b = a.clone();
101        a_merge_b.merge(b.clone());
102
103        let mut b_merge_a = b.clone();
104        b_merge_a.merge(a.clone());
105
106        assert_eq!(a_merge_b, b_merge_a);
107    }
108
109    #[test]
110    fn test_gset_semilattice_associative() {
111        let mut a = GSet::new();
112        a.insert("hash1".to_string());
113        let mut b = GSet::new();
114        b.insert("hash2".to_string());
115        let mut c = GSet::new();
116        c.insert("hash3".to_string());
117
118        let mut left = a.clone();
119        left.merge(b.clone());
120        left.merge(c.clone());
121
122        let mut right_inner = b.clone();
123        right_inner.merge(c.clone());
124        let mut right = a.clone();
125        right.merge(right_inner);
126
127        assert_eq!(left, right);
128    }
129
130    #[test]
131    fn test_gset_semilattice_idempotent() {
132        let mut a = GSet::new();
133        a.insert("hash1".to_string());
134
135        let mut a_merge_a = a.clone();
136        a_merge_a.merge(a.clone());
137
138        assert_eq!(a, a_merge_a);
139    }
140}
bones_core/crdt/gset.rs

bones_core/crdt/
gset.rs
