casper_contract_sdk/collections/
iterable_set.rs

1use borsh::{BorshDeserialize, BorshSerialize};
2
3use super::{IterableMap, IterableMapHash};
4
5/// An iterable set backed by a map.
6pub struct IterableSet<V> {
7    pub(crate) map: IterableMap<V, ()>,
8}
9
10impl<V: IterableMapHash + BorshSerialize + BorshDeserialize + Clone> IterableSet<V> {
11    /// Creates an empty [IterableMap] with the given prefix.
12    pub fn new<S: Into<String>>(prefix: S) -> Self {
13        Self {
14            map: IterableMap::new(prefix),
15        }
16    }
17
18    /// Inserts a value into the set.
19    pub fn insert(&mut self, value: V) {
20        self.map.insert(value, ());
21    }
22
23    /// Removes a value from the set.
24    ///
25    /// Has a worst-case runtime of O(n).
26    pub fn remove(&mut self, value: &V) {
27        self.map.remove(value);
28    }
29
30    /// Returns true if the set contains a value.
31    pub fn contains(&self, value: &V) -> bool {
32        self.map.get(value).is_some()
33    }
34
35    /// Creates an iterator visiting all the values in arbitrary order.
36    pub fn iter(&self) -> impl Iterator<Item = V> + '_ {
37        self.map.iter().map(|(value, _)| value)
38    }
39
40    // Returns true if the set contains no elements.
41    pub fn is_empty(&self) -> bool {
42        self.map.is_empty()
43    }
44
45    /// Clears the set, removing all values.
46    pub fn clear(&mut self) {
47        self.map.clear();
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54    use crate::casper::native::dispatch;
55    use borsh::{BorshDeserialize, BorshSerialize};
56
57    #[test]
58    fn basic_insert_contains() {
59        dispatch(|| {
60            let mut set = IterableSet::new("test_set");
61            assert!(!set.contains(&1));
62
63            set.insert(1);
64            assert!(set.contains(&1));
65
66            set.insert(2);
67            assert!(set.contains(&2));
68        })
69        .unwrap();
70    }
71
72    #[test]
73    fn remove_elements() {
74        dispatch(|| {
75            let mut set = IterableSet::new("test_set");
76            set.insert(1);
77            set.insert(2);
78
79            set.remove(&1);
80            assert!(!set.contains(&1));
81            assert!(set.contains(&2));
82
83            set.remove(&2);
84            assert!(set.is_empty());
85        })
86        .unwrap();
87    }
88
89    #[test]
90    fn iterator_order_and_contents() {
91        dispatch(|| {
92            let mut set = IterableSet::new("test_set");
93            set.insert(1);
94            set.insert(2);
95            set.insert(3);
96
97            let mut items: Vec<_> = set.iter().collect();
98            items.sort();
99            assert_eq!(items, vec![1, 2, 3]);
100        })
101        .unwrap();
102    }
103
104    #[test]
105    fn clear_functionality() {
106        dispatch(|| {
107            let mut set = IterableSet::new("test_set");
108            set.insert(1);
109            set.insert(2);
110
111            assert!(!set.is_empty());
112            set.clear();
113            assert!(set.is_empty());
114            assert_eq!(set.iter().count(), 0);
115        })
116        .unwrap();
117    }
118
119    #[test]
120    fn multiple_sets_independence() {
121        dispatch(|| {
122            let mut set1 = IterableSet::new("set1");
123            let mut set2 = IterableSet::new("set2");
124
125            set1.insert(1);
126            set2.insert(1);
127
128            assert!(set1.contains(&1));
129            assert!(set2.contains(&1));
130
131            set1.remove(&1);
132            assert!(!set1.contains(&1));
133            assert!(set2.contains(&1));
134        })
135        .unwrap();
136    }
137
138    #[derive(BorshSerialize, BorshDeserialize, Clone, Debug, PartialEq)]
139    struct TestStruct {
140        field1: u64,
141        field2: String,
142    }
143
144    impl IterableMapHash for TestStruct {}
145
146    #[test]
147    fn struct_values() {
148        dispatch(|| {
149            let val1 = TestStruct {
150                field1: 1,
151                field2: "a".to_string(),
152            };
153            let val2 = TestStruct {
154                field1: 2,
155                field2: "b".to_string(),
156            };
157
158            let mut set = IterableSet::new("test_set");
159            set.insert(val1.clone());
160            set.insert(val2.clone());
161
162            assert!(set.contains(&val1));
163            assert!(set.contains(&val2));
164
165            let mut collected: Vec<_> = set.iter().collect();
166            collected.sort_by(|a, b| a.field1.cmp(&b.field1));
167            assert_eq!(collected, vec![val1, val2]);
168        })
169        .unwrap();
170    }
171
172    #[test]
173    fn duplicate_insertions() {
174        dispatch(|| {
175            let mut set = IterableSet::new("test_set");
176            set.insert(1);
177            set.insert(1); // Should be no-op
178
179            assert_eq!(set.iter().count(), 1);
180            set.remove(&1);
181            assert!(set.is_empty());
182        })
183        .unwrap();
184    }
185
186    #[test]
187    fn empty_set_behavior() {
188        dispatch(|| {
189            let set = IterableSet::<u64>::new("test_set");
190            assert!(set.is_empty());
191            assert_eq!(set.iter().count(), 0);
192
193            let mut set = set;
194            set.remove(&999); // Shouldn't panic
195            assert!(set.is_empty());
196        })
197        .unwrap();
198    }
199
200    #[test]
201    fn complex_operations_sequence() {
202        dispatch(|| {
203            let mut set = IterableSet::new("test_set");
204            set.insert(1);
205            set.insert(2);
206            set.remove(&1);
207            set.insert(3);
208            set.clear();
209            set.insert(4);
210
211            let items: Vec<_> = set.iter().collect();
212            assert_eq!(items, vec![4]);
213        })
214        .unwrap();
215    }
216}
casper_contract_sdk/collections/iterable_set.rs

casper_contract_sdk/collections/
iterable_set.rs
