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