tirea_state/lattice/
g_set.rs

1use std::collections::BTreeSet;
2
3use serde::{Deserialize, Serialize};
4
5use super::Lattice;
6
7/// A grow-only set (G-Set). Elements can be added but never removed.
8///
9/// Merge semantics: set union.
10#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
11#[serde(transparent)]
12pub struct GSet<T: Ord>(BTreeSet<T>);
13
14impl<T: Ord> GSet<T> {
15    /// Create an empty set.
16    pub fn new() -> Self {
17        Self(BTreeSet::new())
18    }
19
20    /// Insert an element. Returns `true` if the element was newly inserted.
21    pub fn insert(&mut self, value: T) -> bool {
22        self.0.insert(value)
23    }
24
25    /// Returns `true` if the set contains the given element.
26    pub fn contains(&self, value: &T) -> bool {
27        self.0.contains(value)
28    }
29
30    /// Returns the number of elements.
31    pub fn len(&self) -> usize {
32        self.0.len()
33    }
34
35    /// Returns `true` if the set is empty.
36    pub fn is_empty(&self) -> bool {
37        self.0.is_empty()
38    }
39
40    /// Returns an iterator over the elements in sorted order.
41    pub fn iter(&self) -> std::collections::btree_set::Iter<'_, T> {
42        self.0.iter()
43    }
44}
45
46impl<T: Ord> Default for GSet<T> {
47    fn default() -> Self {
48        Self::new()
49    }
50}
51
52impl<T: Ord> IntoIterator for GSet<T> {
53    type Item = T;
54    type IntoIter = std::collections::btree_set::IntoIter<T>;
55
56    fn into_iter(self) -> Self::IntoIter {
57        self.0.into_iter()
58    }
59}
60
61impl<'a, T: Ord> IntoIterator for &'a GSet<T> {
62    type Item = &'a T;
63    type IntoIter = std::collections::btree_set::Iter<'a, T>;
64
65    fn into_iter(self) -> Self::IntoIter {
66        self.0.iter()
67    }
68}
69
70impl<T: Ord + Clone + PartialEq> Lattice for GSet<T> {
71    fn merge(&self, other: &Self) -> Self {
72        Self(self.0.union(&other.0).cloned().collect())
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79    use crate::lattice::assert_lattice_laws;
80
81    #[test]
82    fn new_is_empty() {
83        let s: GSet<i32> = GSet::new();
84        assert!(s.is_empty());
85        assert_eq!(s.len(), 0);
86    }
87
88    #[test]
89    fn insert_and_contains() {
90        let mut s = GSet::new();
91        assert!(s.insert(1));
92        assert!(s.insert(2));
93        assert!(!s.insert(1)); // duplicate
94        assert!(s.contains(&1));
95        assert!(s.contains(&2));
96        assert!(!s.contains(&3));
97        assert_eq!(s.len(), 2);
98    }
99
100    #[test]
101    fn iter_sorted() {
102        let mut s = GSet::new();
103        s.insert(3);
104        s.insert(1);
105        s.insert(2);
106        let items: Vec<_> = s.iter().copied().collect();
107        assert_eq!(items, vec![1, 2, 3]);
108    }
109
110    #[test]
111    fn into_iter() {
112        let mut s = GSet::new();
113        s.insert(3);
114        s.insert(1);
115        let items: Vec<_> = s.into_iter().collect();
116        assert_eq!(items, vec![1, 3]);
117    }
118
119    #[test]
120    fn lattice_laws() {
121        let mut a = GSet::new();
122        a.insert(1);
123        a.insert(2);
124
125        let mut b = GSet::new();
126        b.insert(2);
127        b.insert(3);
128
129        let mut c = GSet::new();
130        c.insert(3);
131        c.insert(4);
132
133        assert_lattice_laws(&a, &b, &c);
134    }
135
136    #[test]
137    fn lattice_laws_disjoint() {
138        let mut a = GSet::new();
139        a.insert("x".to_string());
140
141        let mut b = GSet::new();
142        b.insert("y".to_string());
143
144        let mut c = GSet::new();
145        c.insert("z".to_string());
146
147        assert_lattice_laws(&a, &b, &c);
148    }
149
150    #[test]
151    fn merge_union() {
152        let mut a = GSet::new();
153        a.insert(1);
154        a.insert(2);
155
156        let mut b = GSet::new();
157        b.insert(2);
158        b.insert(3);
159
160        let merged = a.merge(&b);
161        assert_eq!(merged.len(), 3);
162        assert!(merged.contains(&1));
163        assert!(merged.contains(&2));
164        assert!(merged.contains(&3));
165    }
166
167    #[test]
168    fn merge_empty() {
169        let a: GSet<i32> = GSet::new();
170        let mut b = GSet::new();
171        b.insert(1);
172
173        assert_eq!(a.merge(&b).len(), 1);
174        assert_eq!(b.merge(&a).len(), 1);
175        assert_eq!(a.merge(&a).len(), 0);
176    }
177
178    #[test]
179    fn serde_roundtrip() {
180        let mut s = GSet::new();
181        s.insert(3);
182        s.insert(1);
183        s.insert(2);
184
185        let json = serde_json::to_value(&s).unwrap();
186        assert_eq!(json, serde_json::json!([1, 2, 3]));
187
188        let back: GSet<i32> = serde_json::from_value(json).unwrap();
189        assert_eq!(back, s);
190    }
191
192    #[test]
193    fn serde_empty() {
194        let s: GSet<i32> = GSet::new();
195        let json = serde_json::to_value(&s).unwrap();
196        assert_eq!(json, serde_json::json!([]));
197
198        let back: GSet<i32> = serde_json::from_value(json).unwrap();
199        assert_eq!(back, s);
200    }
201}
tirea_state/lattice/g_set.rs

tirea_state/lattice/
g_set.rs
