unc_sdk/store/iterable_set/mod.rs
1// This suppresses the depreciation warnings for uses of IterableSet in this module
2#![allow(deprecated)]
3
4mod impls;
5mod iter;
6
7pub use self::iter::{Difference, Drain, Intersection, Iter, SymmetricDifference, Union};
8use super::{LookupMap, ERR_INCONSISTENT_STATE};
9use crate::store::key::{Sha256, ToKey};
10use crate::store::Vector;
11use crate::{env, IntoStorageKey};
12use borsh::{BorshDeserialize, BorshSerialize};
13use std::borrow::Borrow;
14use std::fmt;
15
16use unc_sdk_macros::unc;
17
18type VecIndex = u32;
19
20/// A lazily loaded storage set that stores its content directly on the storage trie.
21/// This structure is similar to [`unc_sdk::store::LookupSet`](crate::store::LookupSet), except
22/// that it keeps track of the elements so that [`IterableSet`] can be iterable among other things.
23///
24/// As with the [`LookupSet`] type, an `IterableSet` requires that the elements
25/// implement the [`BorshSerialize`] and [`Ord`] traits. This can frequently be achieved by
26/// using `#[derive(BorshSerialize, Ord)]`. Some functions also require elements to implement the
27/// [`BorshDeserialize`] trait.
28///
29/// This set stores the values under a hash of the set's `prefix` and [`BorshSerialize`] of the
30/// element using the set's [`ToKey`] implementation.
31///
32/// The default hash function for [`IterableSet`] is [`Sha256`] which uses a syscall
33/// (or host function) built into the UNC runtime to hash the element. To use a custom function,
34/// use [`with_hasher`]. Alternative builtin hash functions can be found at
35/// [`unc_sdk::store::key`](crate::store::key).
36///
37/// # Examples
38///
39/// ```
40/// use unc_sdk::store::IterableSet;
41///
42/// // Initializes a set, the generic types can be inferred to `IterableSet<String, Sha256>`
43/// // The `b"a"` parameter is a prefix for the storage keys of this data structure.
44/// let mut set = IterableSet::new(b"a");
45///
46/// set.insert("test".to_string());
47/// assert!(set.contains("test"));
48/// assert!(set.remove("test"));
49/// ```
50///
51/// [`IterableSet`] also implements various binary operations, which allow
52/// for iterating various combinations of two sets.
53///
54/// ```
55/// use unc_sdk::store::IterableSet;
56/// use std::collections::HashSet;
57///
58/// let mut set1 = IterableSet::new(b"m");
59/// set1.insert(1);
60/// set1.insert(2);
61/// set1.insert(3);
62///
63/// let mut set2 = IterableSet::new(b"n");
64/// set2.insert(2);
65/// set2.insert(3);
66/// set2.insert(4);
67///
68/// assert_eq!(
69/// set1.union(&set2).collect::<HashSet<_>>(),
70/// [1, 2, 3, 4].iter().collect()
71/// );
72/// assert_eq!(
73/// set1.intersection(&set2).collect::<HashSet<_>>(),
74/// [2, 3].iter().collect()
75/// );
76/// assert_eq!(
77/// set1.difference(&set2).collect::<HashSet<_>>(),
78/// [1].iter().collect()
79/// );
80/// assert_eq!(
81/// set1.symmetric_difference(&set2).collect::<HashSet<_>>(),
82/// [1, 4].iter().collect()
83/// );
84/// ```
85///
86/// [`with_hasher`]: Self::with_hasher
87/// [`LookupSet`]: crate::store::LookupSet
88#[unc(inside_uncsdk)]
89pub struct IterableSet<T, H = Sha256>
90where
91 T: BorshSerialize + Ord,
92 H: ToKey,
93{
94 #[borsh(bound(serialize = "", deserialize = ""))]
95 elements: Vector<T>,
96 #[borsh(bound(serialize = "", deserialize = ""))]
97 index: LookupMap<T, VecIndex, H>,
98}
99
100impl<T, H> Drop for IterableSet<T, H>
101where
102 T: BorshSerialize + Ord,
103 H: ToKey,
104{
105 fn drop(&mut self) {
106 self.flush()
107 }
108}
109
110impl<T, H> fmt::Debug for IterableSet<T, H>
111where
112 T: BorshSerialize + Ord + BorshDeserialize + fmt::Debug,
113 H: ToKey,
114{
115 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
116 f.debug_struct("IterableSet")
117 .field("elements", &self.elements)
118 .field("index", &self.index)
119 .finish()
120 }
121}
122
123impl<T> IterableSet<T, Sha256>
124where
125 T: BorshSerialize + Ord,
126{
127 /// Create a new iterable set. Use `prefix` as a unique prefix for keys.
128 ///
129 /// This prefix can be anything that implements [`IntoStorageKey`]. The prefix is used when
130 /// storing and looking up values in storage to ensure no collisions with other collections.
131 ///
132 /// # Examples
133 ///
134 /// ```
135 /// use unc_sdk::store::IterableSet;
136 ///
137 /// let mut map: IterableSet<String> = IterableSet::new(b"b");
138 /// ```
139 #[inline]
140 pub fn new<S>(prefix: S) -> Self
141 where
142 S: IntoStorageKey,
143 {
144 Self::with_hasher(prefix)
145 }
146}
147
148impl<T, H> IterableSet<T, H>
149where
150 T: BorshSerialize + Ord,
151 H: ToKey,
152{
153 /// Initialize a [`IterableSet`] with a custom hash function.
154 ///
155 /// # Example
156 /// ```
157 /// use unc_sdk::store::key::Keccak256;
158 /// use unc_sdk::store::IterableSet;
159 ///
160 /// let map = IterableSet::<String, Keccak256>::with_hasher(b"m");
161 /// ```
162 pub fn with_hasher<S>(prefix: S) -> Self
163 where
164 S: IntoStorageKey,
165 {
166 let mut vec_key = prefix.into_storage_key();
167 let map_key = [vec_key.as_slice(), b"m"].concat();
168 vec_key.push(b'v');
169 Self { elements: Vector::new(vec_key), index: LookupMap::with_hasher(map_key) }
170 }
171
172 /// Returns the number of elements in the set.
173 pub fn len(&self) -> u32 {
174 self.elements.len()
175 }
176
177 /// Returns true if the set contains no elements.
178 pub fn is_empty(&self) -> bool {
179 self.elements.is_empty()
180 }
181
182 /// Clears the set, removing all values.
183 pub fn clear(&mut self)
184 where
185 T: BorshDeserialize + Clone,
186 {
187 for e in self.elements.drain(..) {
188 self.index.set(e, None);
189 }
190 }
191
192 /// Visits the values representing the difference, i.e., the values that are in `self` but not
193 /// in `other`.
194 ///
195 /// # Examples
196 ///
197 /// ```
198 /// use unc_sdk::store::IterableSet;
199 ///
200 /// let mut set1 = IterableSet::new(b"m");
201 /// set1.insert("a".to_string());
202 /// set1.insert("b".to_string());
203 /// set1.insert("c".to_string());
204 ///
205 /// let mut set2 = IterableSet::new(b"n");
206 /// set2.insert("b".to_string());
207 /// set2.insert("c".to_string());
208 /// set2.insert("d".to_string());
209 ///
210 /// // Can be seen as `set1 - set2`.
211 /// for x in set1.difference(&set2) {
212 /// println!("{}", x); // Prints "a"
213 /// }
214 /// ```
215 pub fn difference<'a>(&'a self, other: &'a IterableSet<T, H>) -> Difference<'a, T, H>
216 where
217 T: BorshDeserialize,
218 {
219 Difference::new(self, other)
220 }
221
222 /// Visits the values representing the symmetric difference, i.e., the values that are in
223 /// `self` or in `other` but not in both.
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// use unc_sdk::store::IterableSet;
229 ///
230 /// let mut set1 = IterableSet::new(b"m");
231 /// set1.insert("a".to_string());
232 /// set1.insert("b".to_string());
233 /// set1.insert("c".to_string());
234 ///
235 /// let mut set2 = IterableSet::new(b"n");
236 /// set2.insert("b".to_string());
237 /// set2.insert("c".to_string());
238 /// set2.insert("d".to_string());
239 ///
240 /// // Prints "a", "d" in arbitrary order.
241 /// for x in set1.symmetric_difference(&set2) {
242 /// println!("{}", x);
243 /// }
244 /// ```
245 pub fn symmetric_difference<'a>(
246 &'a self,
247 other: &'a IterableSet<T, H>,
248 ) -> SymmetricDifference<'a, T, H>
249 where
250 T: BorshDeserialize + Clone,
251 {
252 SymmetricDifference::new(self, other)
253 }
254
255 /// Visits the values representing the intersection, i.e., the values that are both in `self`
256 /// and `other`.
257 ///
258 /// # Examples
259 ///
260 /// ```
261 /// use unc_sdk::store::IterableSet;
262 ///
263 /// let mut set1 = IterableSet::new(b"m");
264 /// set1.insert("a".to_string());
265 /// set1.insert("b".to_string());
266 /// set1.insert("c".to_string());
267 ///
268 /// let mut set2 = IterableSet::new(b"n");
269 /// set2.insert("b".to_string());
270 /// set2.insert("c".to_string());
271 /// set2.insert("d".to_string());
272 ///
273 /// // Prints "b", "c" in arbitrary order.
274 /// for x in set1.intersection(&set2) {
275 /// println!("{}", x);
276 /// }
277 /// ```
278 pub fn intersection<'a>(&'a self, other: &'a IterableSet<T, H>) -> Intersection<'a, T, H>
279 where
280 T: BorshDeserialize,
281 {
282 Intersection::new(self, other)
283 }
284
285 /// Visits the values representing the union, i.e., all the values in `self` or `other`, without
286 /// duplicates.
287 ///
288 /// # Examples
289 ///
290 /// ```
291 /// use unc_sdk::store::IterableSet;
292 ///
293 /// let mut set1 = IterableSet::new(b"m");
294 /// set1.insert("a".to_string());
295 /// set1.insert("b".to_string());
296 /// set1.insert("c".to_string());
297 ///
298 /// let mut set2 = IterableSet::new(b"n");
299 /// set2.insert("b".to_string());
300 /// set2.insert("c".to_string());
301 /// set2.insert("d".to_string());
302 ///
303 /// // Prints "a", "b", "c", "d" in arbitrary order.
304 /// for x in set1.union(&set2) {
305 /// println!("{}", x);
306 /// }
307 /// ```
308 pub fn union<'a>(&'a self, other: &'a IterableSet<T, H>) -> Union<'a, T, H>
309 where
310 T: BorshDeserialize + Clone,
311 {
312 Union::new(self, other)
313 }
314
315 /// Returns `true` if `self` has no elements in common with `other`. This is equivalent to
316 /// checking for an empty intersection.
317 ///
318 /// # Examples
319 ///
320 /// ```
321 /// use unc_sdk::store::IterableSet;
322 ///
323 /// let mut set1 = IterableSet::new(b"m");
324 /// set1.insert("a".to_string());
325 /// set1.insert("b".to_string());
326 /// set1.insert("c".to_string());
327 ///
328 /// let mut set2 = IterableSet::new(b"n");
329 ///
330 /// assert_eq!(set1.is_disjoint(&set2), true);
331 /// set2.insert("d".to_string());
332 /// assert_eq!(set1.is_disjoint(&set2), true);
333 /// set2.insert("a".to_string());
334 /// assert_eq!(set1.is_disjoint(&set2), false);
335 /// ```
336 pub fn is_disjoint(&self, other: &IterableSet<T, H>) -> bool
337 where
338 T: BorshDeserialize + Clone,
339 {
340 if self.len() <= other.len() {
341 self.iter().all(|v| !other.contains(v))
342 } else {
343 other.iter().all(|v| !self.contains(v))
344 }
345 }
346
347 /// Returns `true` if the set is a subset of another, i.e., `other` contains at least all the
348 /// values in `self`.
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// use unc_sdk::store::IterableSet;
354 ///
355 /// let mut sup = IterableSet::new(b"m");
356 /// sup.insert("a".to_string());
357 /// sup.insert("b".to_string());
358 /// sup.insert("c".to_string());
359 ///
360 /// let mut set = IterableSet::new(b"n");
361 ///
362 /// assert_eq!(set.is_subset(&sup), true);
363 /// set.insert("b".to_string());
364 /// assert_eq!(set.is_subset(&sup), true);
365 /// set.insert("d".to_string());
366 /// assert_eq!(set.is_subset(&sup), false);
367 /// ```
368 pub fn is_subset(&self, other: &IterableSet<T, H>) -> bool
369 where
370 T: BorshDeserialize + Clone,
371 {
372 if self.len() <= other.len() {
373 self.iter().all(|v| other.contains(v))
374 } else {
375 false
376 }
377 }
378
379 /// Returns `true` if the set is a superset of another, i.e., `self` contains at least all the
380 /// values in `other`.
381 ///
382 /// # Examples
383 ///
384 /// ```
385 /// use unc_sdk::store::IterableSet;
386 ///
387 /// let mut sub = IterableSet::new(b"m");
388 /// sub.insert("a".to_string());
389 /// sub.insert("b".to_string());
390 ///
391 /// let mut set = IterableSet::new(b"n");
392 ///
393 /// assert_eq!(set.is_superset(&sub), false);
394 /// set.insert("b".to_string());
395 /// set.insert("d".to_string());
396 /// assert_eq!(set.is_superset(&sub), false);
397 /// set.insert("a".to_string());
398 /// assert_eq!(set.is_superset(&sub), true);
399 /// ```
400 pub fn is_superset(&self, other: &IterableSet<T, H>) -> bool
401 where
402 T: BorshDeserialize + Clone,
403 {
404 other.is_subset(self)
405 }
406
407 /// An iterator visiting all elements in arbitrary order.
408 /// The iterator element type is `&'a T`.
409 ///
410 /// # Examples
411 ///
412 /// ```
413 /// use unc_sdk::store::IterableSet;
414 ///
415 /// let mut set = IterableSet::new(b"m");
416 /// set.insert("a".to_string());
417 /// set.insert("b".to_string());
418 /// set.insert("c".to_string());
419 ///
420 /// for val in set.iter() {
421 /// println!("val: {}", val);
422 /// }
423 /// ```
424 pub fn iter(&self) -> Iter<T>
425 where
426 T: BorshDeserialize,
427 {
428 Iter::new(self)
429 }
430
431 /// Clears the set, returning all elements in an iterator.
432 ///
433 /// # Examples
434 ///
435 /// ```
436 /// use unc_sdk::store::IterableSet;
437 ///
438 /// let mut a = IterableSet::new(b"m");
439 /// a.insert(1);
440 /// a.insert(2);
441 ///
442 /// for v in a.drain().take(1) {
443 /// assert!(v == 1 || v == 2);
444 /// }
445 ///
446 /// assert!(a.is_empty());
447 /// ```
448 pub fn drain(&mut self) -> Drain<T, H>
449 where
450 T: BorshDeserialize,
451 {
452 Drain::new(self)
453 }
454
455 /// Returns `true` if the set contains the specified value.
456 ///
457 /// The value may be any borrowed form of the set's value type, but
458 /// [`BorshSerialize`], [`ToOwned<Owned = T>`](ToOwned) and [`Ord`] on the borrowed form *must*
459 /// match those for the value type.
460 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
461 where
462 T: Borrow<Q>,
463 Q: BorshSerialize + ToOwned<Owned = T> + Ord,
464 {
465 self.index.contains_key(value)
466 }
467
468 /// Adds a value to the set.
469 ///
470 /// If the set did not have this value present, true is returned.
471 ///
472 /// If the set did have this value present, false is returned.
473 pub fn insert(&mut self, value: T) -> bool
474 where
475 T: Clone + BorshDeserialize,
476 {
477 let entry = self.index.get_mut_inner(&value);
478 if entry.value_mut().is_some() {
479 false
480 } else {
481 self.elements.push(value);
482 let element_index = self.elements.len() - 1;
483 entry.replace(Some(element_index));
484 true
485 }
486 }
487
488 /// Removes a value from the set. Returns whether the value was present in the set.
489 ///
490 /// The value may be any borrowed form of the set's value type, but
491 /// [`BorshSerialize`], [`ToOwned<Owned = K>`](ToOwned) and [`Ord`] on the borrowed form *must*
492 /// match those for the value type.
493 ///
494 /// # Performance
495 ///
496 /// When elements are removed, the underlying vector of keys is rearranged by means of swapping
497 /// an obsolete key with the last element in the list and deleting that. Note that that requires
498 /// updating the `index` map due to the fact that it holds `elements` vector indices.
499 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
500 where
501 T: Borrow<Q> + BorshDeserialize + Clone,
502 Q: BorshSerialize + ToOwned<Owned = T> + Ord,
503 {
504 match self.index.remove(value) {
505 Some(element_index) => {
506 let last_index = self.elements.len() - 1;
507 let _ = self.elements.swap_remove(element_index);
508
509 match element_index {
510 // If it's the last/only element - do nothing.
511 x if x == last_index => {}
512 // Otherwise update it's index.
513 _ => {
514 let element = self
515 .elements
516 .get(element_index)
517 .unwrap_or_else(|| env::panic_str(ERR_INCONSISTENT_STATE));
518 self.index.set(element.clone(), Some(element_index));
519 }
520 }
521
522 true
523 }
524 None => false,
525 }
526 }
527
528 /// Flushes the intermediate values of the map before this is called when the structure is
529 /// [`Drop`]ed. This will write all modified values to storage but keep all cached values
530 /// in memory.
531 pub fn flush(&mut self) {
532 self.elements.flush();
533 self.index.flush();
534 }
535}
536
537#[cfg(not(target_arch = "wasm32"))]
538#[cfg(test)]
539mod tests {
540 use crate::store::IterableSet;
541 use crate::test_utils::test_env::setup_free;
542 use arbitrary::{Arbitrary, Unstructured};
543 use borsh::{to_vec, BorshDeserialize};
544 use rand::RngCore;
545 use rand::SeedableRng;
546 use std::collections::HashSet;
547
548 #[test]
549 fn basic_functionality() {
550 let mut set = IterableSet::new(b"b");
551 assert!(set.is_empty());
552 assert!(set.insert("test".to_string()));
553 assert!(set.contains("test"));
554 assert_eq!(set.len(), 1);
555
556 assert!(set.remove("test"));
557 assert_eq!(set.len(), 0);
558 }
559
560 #[test]
561 fn set_iterator() {
562 let mut set = IterableSet::new(b"b");
563
564 set.insert(0u8);
565 set.insert(1);
566 set.insert(2);
567 set.insert(3);
568 set.remove(&1);
569 let iter = set.iter();
570 assert_eq!(iter.len(), 3);
571 assert_eq!(iter.collect::<Vec<_>>(), [(&0), (&3), (&2)]);
572
573 let mut iter = set.iter();
574 assert_eq!(iter.nth(2), Some(&2));
575 // Check fused iterator assumption that each following one will be None
576 assert_eq!(iter.next(), None);
577
578 // Drain
579 assert_eq!(set.drain().collect::<Vec<_>>(), [0, 3, 2]);
580 assert!(set.is_empty());
581 }
582
583 #[test]
584 fn test_drain() {
585 let mut s = IterableSet::new(b"m");
586 s.extend(1..100);
587
588 // Drain the set a few times to make sure that it does have any random residue
589 for _ in 0..20 {
590 assert_eq!(s.len(), 99);
591
592 for _ in s.drain() {}
593
594 #[allow(clippy::never_loop)]
595 for _ in &s {
596 panic!("s should be empty!");
597 }
598
599 assert_eq!(s.len(), 0);
600 assert!(s.is_empty());
601
602 s.extend(1..100);
603 }
604 }
605
606 #[test]
607 fn test_extend() {
608 let mut a = IterableSet::<u64>::new(b"m");
609 a.insert(1);
610
611 a.extend([2, 3, 4]);
612
613 assert_eq!(a.len(), 4);
614 assert!(a.contains(&1));
615 assert!(a.contains(&2));
616 assert!(a.contains(&3));
617 assert!(a.contains(&4));
618 }
619
620 #[test]
621 fn test_difference() {
622 let mut set1 = IterableSet::new(b"m");
623 set1.insert("a".to_string());
624 set1.insert("b".to_string());
625 set1.insert("c".to_string());
626 set1.insert("d".to_string());
627
628 let mut set2 = IterableSet::new(b"n");
629 set2.insert("b".to_string());
630 set2.insert("c".to_string());
631 set2.insert("e".to_string());
632
633 assert_eq!(
634 set1.difference(&set2).collect::<HashSet<_>>(),
635 ["a".to_string(), "d".to_string()].iter().collect::<HashSet<_>>()
636 );
637 assert_eq!(
638 set2.difference(&set1).collect::<HashSet<_>>(),
639 ["e".to_string()].iter().collect::<HashSet<_>>()
640 );
641 assert!(set1.difference(&set2).nth(1).is_some());
642 assert!(set1.difference(&set2).nth(2).is_none());
643 }
644
645 #[test]
646 fn test_difference_empty() {
647 let mut set1 = IterableSet::new(b"m");
648 set1.insert(1);
649 set1.insert(2);
650 set1.insert(3);
651
652 let mut set2 = IterableSet::new(b"n");
653 set2.insert(3);
654 set2.insert(1);
655 set2.insert(2);
656 set2.insert(4);
657
658 assert_eq!(set1.difference(&set2).collect::<HashSet<_>>(), HashSet::new());
659 }
660
661 #[test]
662 fn test_symmetric_difference() {
663 let mut set1 = IterableSet::new(b"m");
664 set1.insert("a".to_string());
665 set1.insert("b".to_string());
666 set1.insert("c".to_string());
667
668 let mut set2 = IterableSet::new(b"n");
669 set2.insert("b".to_string());
670 set2.insert("c".to_string());
671 set2.insert("d".to_string());
672
673 assert_eq!(
674 set1.symmetric_difference(&set2).collect::<HashSet<_>>(),
675 ["a".to_string(), "d".to_string()].iter().collect::<HashSet<_>>()
676 );
677 assert_eq!(
678 set2.symmetric_difference(&set1).collect::<HashSet<_>>(),
679 ["a".to_string(), "d".to_string()].iter().collect::<HashSet<_>>()
680 );
681 }
682
683 #[test]
684 fn test_symmetric_difference_empty() {
685 let mut set1 = IterableSet::new(b"m");
686 set1.insert(1);
687 set1.insert(2);
688 set1.insert(3);
689
690 let mut set2 = IterableSet::new(b"n");
691 set2.insert(3);
692 set2.insert(1);
693 set2.insert(2);
694
695 assert_eq!(set1.symmetric_difference(&set2).collect::<HashSet<_>>(), HashSet::new());
696 }
697
698 #[test]
699 fn test_intersection() {
700 let mut set1 = IterableSet::new(b"m");
701 set1.insert("a".to_string());
702 set1.insert("b".to_string());
703 set1.insert("c".to_string());
704
705 let mut set2 = IterableSet::new(b"n");
706 set2.insert("b".to_string());
707 set2.insert("c".to_string());
708 set2.insert("d".to_string());
709
710 assert_eq!(
711 set1.intersection(&set2).collect::<HashSet<_>>(),
712 ["b".to_string(), "c".to_string()].iter().collect::<HashSet<_>>()
713 );
714 assert_eq!(
715 set2.intersection(&set1).collect::<HashSet<_>>(),
716 ["b".to_string(), "c".to_string()].iter().collect::<HashSet<_>>()
717 );
718 assert!(set1.intersection(&set2).nth(1).is_some());
719 assert!(set1.intersection(&set2).nth(2).is_none());
720 }
721
722 #[test]
723 fn test_intersection_empty() {
724 let mut set1 = IterableSet::new(b"m");
725 set1.insert(1);
726 set1.insert(2);
727 set1.insert(3);
728
729 let mut set2 = IterableSet::new(b"n");
730 set2.insert(4);
731 set2.insert(6);
732 set2.insert(5);
733
734 assert_eq!(set1.intersection(&set2).collect::<HashSet<_>>(), HashSet::new());
735 }
736
737 #[test]
738 fn test_union() {
739 let mut set1 = IterableSet::new(b"m");
740 set1.insert("a".to_string());
741 set1.insert("b".to_string());
742 set1.insert("c".to_string());
743
744 let mut set2 = IterableSet::new(b"n");
745 set2.insert("b".to_string());
746 set2.insert("c".to_string());
747 set2.insert("d".to_string());
748
749 assert_eq!(
750 set1.union(&set2).collect::<HashSet<_>>(),
751 ["a".to_string(), "b".to_string(), "c".to_string(), "d".to_string()]
752 .iter()
753 .collect::<HashSet<_>>()
754 );
755 assert_eq!(
756 set2.union(&set1).collect::<HashSet<_>>(),
757 ["a".to_string(), "b".to_string(), "c".to_string(), "d".to_string()]
758 .iter()
759 .collect::<HashSet<_>>()
760 );
761 }
762
763 #[test]
764 fn test_union_empty() {
765 let set1 = IterableSet::<u64>::new(b"m");
766 let set2 = IterableSet::<u64>::new(b"n");
767
768 assert_eq!(set1.union(&set2).collect::<HashSet<_>>(), HashSet::new());
769 }
770
771 #[test]
772 fn test_subset_and_superset() {
773 let mut a = IterableSet::new(b"m");
774 assert!(a.insert(0));
775 assert!(a.insert(50));
776 assert!(a.insert(110));
777 assert!(a.insert(70));
778
779 let mut b = IterableSet::new(b"n");
780 assert!(b.insert(0));
781 assert!(b.insert(70));
782 assert!(b.insert(190));
783 assert!(b.insert(2500));
784 assert!(b.insert(110));
785 assert!(b.insert(2000));
786
787 assert!(!a.is_subset(&b));
788 assert!(!a.is_superset(&b));
789 assert!(!b.is_subset(&a));
790 assert!(!b.is_superset(&a));
791
792 assert!(b.insert(50));
793
794 assert!(a.is_subset(&b));
795 assert!(!a.is_superset(&b));
796 assert!(!b.is_subset(&a));
797 assert!(b.is_superset(&a));
798 }
799
800 #[test]
801 fn test_disjoint() {
802 let mut xs = IterableSet::new(b"m");
803 let mut ys = IterableSet::new(b"n");
804
805 assert!(xs.is_disjoint(&ys));
806 assert!(ys.is_disjoint(&xs));
807
808 assert!(xs.insert(50));
809 assert!(ys.insert(110));
810 assert!(xs.is_disjoint(&ys));
811 assert!(ys.is_disjoint(&xs));
812
813 assert!(xs.insert(70));
814 assert!(xs.insert(190));
815 assert!(xs.insert(40));
816 assert!(ys.insert(20));
817 assert!(ys.insert(-110));
818 assert!(xs.is_disjoint(&ys));
819 assert!(ys.is_disjoint(&xs));
820
821 assert!(ys.insert(70));
822 assert!(!xs.is_disjoint(&ys));
823 assert!(!ys.is_disjoint(&xs));
824 }
825
826 #[derive(Arbitrary, Debug)]
827 enum Op {
828 Insert(u8),
829 Remove(u8),
830 Flush,
831 Restore,
832 Contains(u8),
833 }
834
835 #[test]
836 fn arbitrary() {
837 setup_free();
838
839 let mut rng = rand_xorshift::XorShiftRng::seed_from_u64(0);
840 let mut buf = vec![0; 4096];
841 for _ in 0..512 {
842 // Clear storage in-between runs
843 crate::mock::with_mocked_blockchain(|b| b.take_storage());
844 rng.fill_bytes(&mut buf);
845
846 let mut us = IterableSet::new(b"l");
847 let mut hs = HashSet::new();
848 let u = Unstructured::new(&buf);
849 if let Ok(ops) = Vec::<Op>::arbitrary_take_rest(u) {
850 for op in ops {
851 match op {
852 Op::Insert(v) => {
853 let r1 = us.insert(v);
854 let r2 = hs.insert(v);
855 assert_eq!(r1, r2)
856 }
857 Op::Remove(v) => {
858 let r1 = us.remove(&v);
859 let r2 = hs.remove(&v);
860 assert_eq!(r1, r2)
861 }
862 Op::Flush => {
863 us.flush();
864 }
865 Op::Restore => {
866 let serialized = to_vec(&us).unwrap();
867 us = IterableSet::deserialize(&mut serialized.as_slice()).unwrap();
868 }
869 Op::Contains(v) => {
870 let r1 = us.contains(&v);
871 let r2 = hs.contains(&v);
872 assert_eq!(r1, r2)
873 }
874 }
875 }
876 }
877 }
878 }
879}