ic_stable_structures/btreeset.rs
1//! This module implements a set based on a B-Tree in stable memory.
2
3use crate::{btreemap::Iter as IterMap, BTreeMap, Memory, Storable};
4use core::ops::RangeBounds;
5
6#[cfg(test)]
7mod proptests;
8
9/// An iterator over the entries of a [`BTreeSet`].
10pub struct Iter<'a, K, M>
11where
12 K: Storable + Ord + Clone,
13 M: Memory,
14{
15 iter_internal: IterMap<'a, K, (), M>,
16}
17
18impl<'a, K, M> Iter<'a, K, M>
19where
20 K: Storable + Ord + Clone,
21 M: Memory,
22{
23 fn new(iter: IterMap<'a, K, (), M>) -> Self {
24 Iter {
25 iter_internal: iter,
26 }
27 }
28}
29
30impl<K, M> Iterator for Iter<'_, K, M>
31where
32 K: Storable + Ord + Clone,
33 M: Memory,
34{
35 type Item = K;
36
37 fn next(&mut self) -> Option<Self::Item> {
38 self.iter_internal.next().map(|entry| entry.key().clone())
39 }
40}
41
42/// A B-Tree set implementation that stores its data into a designated memory.
43///
44/// # Overview
45///
46/// A `BTreeSet` is a "stable" set implementation based on a B-tree, designed to work directly in stable memory.
47///
48/// # Memory Implementations
49///
50/// `BTreeSet` works with any memory implementation that satisfies the [`Memory`] trait:
51///
52/// - [`Ic0StableMemory`](crate::Ic0StableMemory): Stores data in the Internet Computer's stable memory.
53/// - [`VectorMemory`](crate::VectorMemory): In-memory implementation backed by a Rust `Vec<u8>`.
54/// - [`FileMemory`](crate::FileMemory): Persists data to disk using a file.
55/// - [`DefaultMemoryImpl`](crate::DefaultMemoryImpl): Automatically selects the appropriate memory backend
56/// based on the environment:
57/// - Uses `Ic0StableMemory` when running in an Internet Computer canister (wasm32 target).
58/// - Falls back to `VectorMemory` in other environments (like tests or non-IC contexts).
59///
60/// For most use cases, [`DefaultMemoryImpl`](crate::DefaultMemoryImpl) is recommended as it provides
61/// the right implementation based on the runtime context.
62///
63/// # Examples
64///
65/// ## Basic Usage
66///
67/// ```rust
68/// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
69/// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
70///
71/// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
72/// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
73///
74/// set.insert(42);
75/// assert!(set.contains(&42));
76/// assert_eq!(set.pop_first(), Some(42));
77/// assert!(set.is_empty());
78/// ```
79///
80/// ## Range Queries
81///
82/// ```rust
83/// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
84/// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
85///
86/// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
87/// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
88/// set.insert(1);
89/// set.insert(2);
90/// set.insert(3);
91///
92/// let range: Vec<_> = set.range(2..).collect();
93/// assert_eq!(range, vec![2, 3]);
94/// ```
95///
96/// ## Custom Types
97///
98/// You can store custom types in a `BTreeSet` by implementing the `Storable` trait:
99///
100/// ```rust
101/// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl, Storable};
102/// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
103/// use std::borrow::Cow;
104///
105/// #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
106/// struct CustomType {
107/// id: u64,
108/// }
109///
110/// impl Storable for CustomType {
111/// fn to_bytes(&self) -> Cow<'_, [u8]> {
112/// Cow::Owned(self.id.to_le_bytes().to_vec())
113/// }
114///
115/// fn into_bytes(self) -> Vec<u8> {
116/// self.id.to_le_bytes().to_vec()
117/// }
118///
119/// fn from_bytes(bytes: Cow<[u8]>) -> Self {
120/// let id = u64::from_le_bytes(bytes.as_ref().try_into().unwrap());
121/// CustomType { id }
122/// }
123///
124/// const BOUND: ic_stable_structures::storable::Bound =
125/// ic_stable_structures::storable::Bound::Bounded {
126/// max_size: 8,
127/// is_fixed_size: true,
128/// };
129/// }
130///
131/// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
132/// let mut set: BTreeSet<CustomType, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
133/// set.insert(CustomType { id: 42 });
134/// assert!(set.contains(&CustomType { id: 42 }));
135/// ```
136///
137/// ### Bounded vs Unbounded Types
138///
139/// When implementing `Storable`, you must specify whether your type is bounded or unbounded:
140///
141/// - **Unbounded (`Bound::Unbounded`)**:
142/// - Use when your type's serialized size can vary or has no fixed maximum.
143/// - Recommended for most custom types, especially those containing Strings or Vecs.
144/// - Example: `const BOUND: Bound = Bound::Unbounded;`
145///
146/// - **Bounded (`Bound::Bounded{ max_size, is_fixed_size }`)**:
147/// - Use when you know the maximum serialized size of your type.
148/// - Enables memory optimizations in the `BTreeSet`.
149/// - Example: `const BOUND: Bound = Bound::Bounded { max_size: 100, is_fixed_size: false };`
150/// - For types with truly fixed size (like primitive types), set `is_fixed_size: true`.
151///
152/// If unsure, use `Bound::Unbounded` as it's the safer choice.
153///
154/// # Warning
155///
156/// Once you've deployed with a bounded type, you cannot increase its `max_size` in
157/// future versions without risking data corruption. You can, however, migrate from a bounded type
158/// to an unbounded type if needed. For evolving data structures, prefer `Bound::Unbounded`.
159pub struct BTreeSet<K, M>
160where
161 K: Storable + Ord + Clone,
162 M: Memory,
163{
164 // The underlying implementation uses a BTreeMap with unit values.
165 // This design allows us to reuse the existing BTreeMap implementation.
166 // However, if needed, this could be optimized in the future to avoid
167 // the overhead of storing unit values.
168 map: BTreeMap<K, (), M>,
169}
170
171impl<K, M> BTreeSet<K, M>
172where
173 K: Storable + Ord + Clone,
174 M: Memory,
175{
176 /// Initializes a `BTreeSet`.
177 ///
178 /// If the memory provided already contains a `BTreeSet`, then that
179 /// map is loaded. Otherwise, a new `BTreeSet` instance is created.
180 ///
181 /// # Example
182 ///
183 /// ```rust
184 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
185 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
186 ///
187 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
188 /// let set: BTreeSet<u64, _> = BTreeSet::init(mem_mgr.get(MemoryId::new(0)));
189 /// ```
190 pub fn init(memory: M) -> Self {
191 BTreeSet {
192 map: BTreeMap::<K, (), M>::init(memory),
193 }
194 }
195
196 /// Creates a new instance of a `BTreeSet`.
197 ///
198 /// # Example
199 ///
200 /// ```rust
201 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
202 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
203 ///
204 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
205 /// let set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
206 /// ```
207 pub fn new(memory: M) -> Self {
208 BTreeSet {
209 map: BTreeMap::<K, (), M>::new(memory),
210 }
211 }
212
213 /// Loads the `BTreeSet` from memory.
214 ///
215 /// # Example
216 ///
217 /// ```rust
218 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
219 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
220 ///
221 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
222 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
223 /// set.insert(42);
224 ///
225 /// // Save the set to memory
226 /// let memory = set.into_memory();
227 ///
228 /// // Load the set from memory
229 /// let loaded_set: BTreeSet<u64, _> = BTreeSet::load(memory);
230 /// assert!(loaded_set.contains(&42));
231 /// ```
232 pub fn load(memory: M) -> Self {
233 BTreeSet {
234 map: BTreeMap::<K, (), M>::load(memory),
235 }
236 }
237
238 /// Inserts a key into the set. Returns `true` if the key
239 /// did not exist in the set before.
240 ///
241 /// # Complexity
242 /// O(log n), where n is the number of elements in the set.
243 ///
244 /// # Example
245 ///
246 /// ```rust
247 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
248 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
249 ///
250 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
251 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
252 /// assert!(set.insert(42));
253 /// assert!(!set.insert(42)); // Key already exists
254 /// ```
255 pub fn insert(&mut self, key: K) -> bool {
256 self.map.insert(key, ()).is_none()
257 }
258
259 /// Returns `true` if the key exists in the set, `false` otherwise.
260 ///
261 /// # Complexity
262 /// O(log n), where n is the number of elements in the set.
263 ///
264 /// # Example
265 ///
266 /// ```rust
267 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
268 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
269 ///
270 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
271 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
272 /// set.insert(42);
273 /// assert!(set.contains(&42));
274 /// assert!(!set.contains(&7));
275 /// ```
276 pub fn contains(&self, key: &K) -> bool {
277 self.map.get(key).is_some()
278 }
279
280 /// Returns `true` if the set contains no elements.
281 ///
282 /// # Complexity
283 /// O(1)
284 ///
285 /// # Example
286 ///
287 /// ```rust
288 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
289 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
290 ///
291 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
292 /// let set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
293 /// assert!(set.is_empty());
294 /// ```
295 pub fn is_empty(&self) -> bool {
296 self.map.is_empty()
297 }
298
299 /// Returns the number of elements in the set.
300 ///
301 /// # Complexity
302 /// O(1)
303 ///
304 /// # Example
305 ///
306 /// ```rust
307 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
308 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
309 ///
310 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
311 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
312 /// set.insert(42);
313 /// set.insert(7);
314 /// assert_eq!(set.len(), 2);
315 /// ```
316 pub fn len(&self) -> u64 {
317 self.map.len()
318 }
319
320 /// Returns the underlying memory.
321 ///
322 /// # Example
323 ///
324 /// ```rust
325 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
326 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
327 ///
328 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
329 /// let set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
330 /// let memory = set.into_memory();
331 /// ```
332 pub fn into_memory(self) -> M {
333 self.map.into_memory()
334 }
335
336 /// Removes all elements from the set.
337 ///
338 /// This operation clears the set by deallocating all memory used by its elements.
339 ///
340 /// # Complexity
341 /// O(n), where n is the number of elements in the set.
342 ///
343 /// # Example
344 ///
345 /// ```rust
346 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
347 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
348 ///
349 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
350 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
351 /// set.insert(42);
352 /// set.clear();
353 /// assert!(set.is_empty());
354 /// ```
355 pub fn clear(&mut self) {
356 self.map.clear_new();
357 }
358
359 /// Returns the first key in the set. This key
360 /// is the minimum key in the set.
361 ///
362 /// # Complexity
363 /// O(log n), where n is the number of elements in the set.
364 ///
365 /// # Example
366 ///
367 /// ```rust
368 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
369 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
370 ///
371 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
372 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
373 /// set.insert(42);
374 /// set.insert(7);
375 /// assert_eq!(set.first(), Some(7));
376 /// ```
377 pub fn first(&self) -> Option<K> {
378 self.map.first_key_value().map(|(a, _)| a)
379 }
380
381 /// Returns the last key in the set. This key
382 /// is the maximum key in the set.
383 ///
384 /// # Complexity
385 /// O(log n), where n is the number of elements in the set.
386 ///
387 /// # Example
388 ///
389 /// ```rust
390 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
391 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
392 ///
393 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
394 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
395 /// set.insert(42);
396 /// set.insert(7);
397 /// assert_eq!(set.last(), Some(42));
398 /// ```
399 pub fn last(&self) -> Option<K> {
400 self.map.last_key_value().map(|(a, _)| a)
401 }
402
403 /// Removes a key from the set, returning `true` if it exists.
404 ///
405 /// # Complexity
406 /// O(log n), where n is the number of elements in the set.
407 ///
408 /// # Example
409 ///
410 /// ```rust
411 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
412 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
413 ///
414 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
415 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
416 /// set.insert(42);
417 /// assert!(set.remove(&42));
418 /// assert!(!set.contains(&42));
419 /// ```
420 pub fn remove(&mut self, key: &K) -> bool {
421 self.map.remove(key).is_some()
422 }
423
424 /// Removes and returns the last element in the set. The key of this element is the maximum key that was in the set.
425 ///
426 /// # Complexity
427 /// O(log n), where n is the number of elements in the set.
428 ///
429 /// # Example
430 ///
431 /// ```rust
432 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
433 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
434 ///
435 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
436 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
437 /// set.insert(42);
438 /// set.insert(7);
439 /// assert_eq!(set.pop_last(), Some(42));
440 /// ```
441 pub fn pop_last(&mut self) -> Option<K> {
442 self.map.pop_last().map(|(a, _)| a)
443 }
444
445 /// Removes and returns the first element in the set. The key of this element is the minimum key that was in the set.
446 ///
447 /// # Complexity
448 /// O(log n), where n is the number of elements in the set.
449 ///
450 /// # Example
451 ///
452 /// ```rust
453 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
454 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
455 ///
456 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
457 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
458 /// set.insert(42);
459 /// set.insert(7);
460 /// assert_eq!(set.pop_first(), Some(7));
461 /// ```
462 pub fn pop_first(&mut self) -> Option<K> {
463 self.map.pop_first().map(|(a, _)| a)
464 }
465
466 /// Returns an iterator over the entries of the set, sorted by key.
467 ///
468 /// # Complexity
469 /// Creating the iterator is O(1), and iterating over k elements is O(k).
470 ///
471 /// # Example
472 ///
473 /// ```rust
474 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
475 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
476 ///
477 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
478 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
479 /// set.insert(42);
480 /// set.insert(7);
481 /// for key in set.iter() {
482 /// println!("{}", key);
483 /// }
484 /// ```
485 pub fn iter(&self) -> Iter<'_, K, M> {
486 Iter::new(self.map.iter())
487 }
488
489 /// Returns an iterator over the entries in the set where keys
490 /// belong to the specified range.
491 ///
492 /// # Complexity
493 /// O(log n) for creating the iterator. Iterating over the range is O(k), where k is the number of elements in the range.
494 ///
495 /// # Example
496 ///
497 /// ```rust
498 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
499 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
500 ///
501 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
502 /// let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
503 /// set.insert(1);
504 /// set.insert(2);
505 /// set.insert(3);
506 /// let range: Vec<_> = set.range(2..).collect();
507 /// assert_eq!(range, vec![2, 3]);
508 /// ```
509 pub fn range(&self, key_range: impl RangeBounds<K>) -> Iter<'_, K, M> {
510 Iter::new(self.map.range(key_range))
511 }
512
513 /// Returns an iterator over the union of this set and another.
514 ///
515 /// The union of two sets is a set containing all elements that are in either set.
516 ///
517 /// # Complexity
518 /// O(n + m), where:
519 /// - n is the size of the first set.
520 /// - m is the size of the second set.
521 ///
522 /// # Example
523 ///
524 /// ```rust
525 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
526 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
527 ///
528 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
529 /// let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
530 /// let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));
531 ///
532 /// set1.insert(1);
533 /// set1.insert(2);
534 /// set2.insert(2);
535 /// set2.insert(3);
536 ///
537 /// let union: Vec<_> = set1.union(&set2).collect();
538 /// assert_eq!(union, vec![1, 2, 3]);
539 /// ```
540 pub fn union<'a>(&'a self, other: &'a BTreeSet<K, M>) -> impl Iterator<Item = K> + 'a {
541 let mut iter_self = self.iter();
542 let mut iter_other = other.iter();
543 let mut next_self = iter_self.next();
544 let mut next_other = iter_other.next();
545
546 // Use a closure to merge the two iterators while maintaining sorted order.
547 std::iter::from_fn(move || {
548 match (next_self.clone(), next_other.clone()) {
549 // If both iterators have elements, compare the current elements.
550 (Some(ref a), Some(ref b)) => match a.cmp(b) {
551 std::cmp::Ordering::Less => {
552 // If the element from `self` is smaller, yield it and advance `self`.
553 next_self = iter_self.next();
554 Some(a.clone())
555 }
556 std::cmp::Ordering::Greater => {
557 // If the element from `other` is smaller, yield it and advance `other`.
558 next_other = iter_other.next();
559 Some(b.clone())
560 }
561 std::cmp::Ordering::Equal => {
562 // If the elements are equal, yield one and advance both iterators.
563 next_self = iter_self.next();
564 next_other = iter_other.next();
565 Some(a.clone())
566 }
567 },
568 // If only `self` has elements remaining, yield them.
569 (Some(ref a), None) => {
570 next_self = iter_self.next();
571 Some(a.clone())
572 }
573 // If only `other` has elements remaining, yield them.
574 (None, Some(ref b)) => {
575 next_other = iter_other.next();
576 Some(b.clone())
577 }
578 // If both iterators are exhausted, stop the iteration.
579 (None, None) => None,
580 }
581 })
582 }
583
584 /// Returns an iterator over the intersection of this set and another.
585 ///
586 /// The intersection of two sets is a set containing only the elements that are in both sets.
587 ///
588 /// # Complexity
589 /// O(n + m), where:
590 /// - n is the size of the first set.
591 /// - m is the size of the second set.
592 ///
593 /// # Example
594 ///
595 /// ```rust
596 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
597 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
598 ///
599 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
600 /// let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
601 /// let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));
602 ///
603 /// set1.insert(1);
604 /// set1.insert(2);
605 /// set1.insert(3);
606 ///
607 /// set2.insert(2);
608 /// set2.insert(3);
609 /// set2.insert(4);
610 ///
611 /// let intersection: Vec<_> = set1.intersection(&set2).collect();
612 /// assert_eq!(intersection, vec![2, 3]);
613 /// ```
614 pub fn intersection<'a>(&'a self, other: &'a BTreeSet<K, M>) -> impl Iterator<Item = K> + 'a {
615 let mut iter_self = self.iter();
616 let mut iter_other = other.iter();
617 let mut next_self = iter_self.next();
618 let mut next_other = iter_other.next();
619
620 // Use a closure to find common elements by traversing both iterators simultaneously.
621 std::iter::from_fn(move || {
622 // Loop until we find a common element or exhaust either iterator.
623 while let (Some(ref a), Some(ref b)) = (next_self.clone(), next_other.clone()) {
624 match a.cmp(b) {
625 std::cmp::Ordering::Less => {
626 // If the element from `self` is smaller, advance `self`.
627 next_self = iter_self.next();
628 }
629 std::cmp::Ordering::Greater => {
630 // If the element from `other` is smaller, advance `other`.
631 next_other = iter_other.next();
632 }
633 std::cmp::Ordering::Equal => {
634 // If the elements are equal, yield one and advance both iterators.
635 next_self = iter_self.next();
636 next_other = iter_other.next();
637 return Some(a.clone());
638 }
639 }
640 }
641 // Stop the iteration when either iterator is exhausted.
642 None
643 })
644 }
645
646 /// Returns `true` if this set has no elements in common with another set.
647 ///
648 /// # Complexity
649 /// O(n + m), where:
650 /// - n is the size of the first set.
651 /// - m is the size of the second set.
652 ///
653 /// # Example
654 ///
655 /// ```rust
656 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
657 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
658 ///
659 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
660 /// let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
661 /// let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));
662 ///
663 /// set1.insert(1);
664 /// set1.insert(2);
665 /// set2.insert(3);
666 /// set2.insert(4);
667 ///
668 /// assert!(set1.is_disjoint(&set2));
669 /// set2.insert(2);
670 /// assert!(!set1.is_disjoint(&set2));
671 /// ```
672 pub fn is_disjoint(&self, other: &BTreeSet<K, M>) -> bool {
673 let mut iter_self = self.iter();
674 let mut iter_other = other.iter();
675 let mut next_self = iter_self.next();
676 let mut next_other = iter_other.next();
677
678 while let (Some(a), Some(b)) = (next_self.as_ref(), next_other.as_ref()) {
679 match a.cmp(b) {
680 std::cmp::Ordering::Less => next_self = iter_self.next(),
681 std::cmp::Ordering::Greater => next_other = iter_other.next(),
682 std::cmp::Ordering::Equal => return false, // Common element found
683 }
684 }
685
686 true // No common elements
687 }
688
689 /// Returns `true` if this set is a subset of another set.
690 ///
691 /// A set `A` is a subset of a set `B` if all elements of `A` are also elements of `B`.
692 ///
693 /// # Complexity
694 /// O(n + m), where:
695 /// - n is the size of the first set.
696 /// - m is the size of the second set.
697 ///
698 /// # Example
699 ///
700 /// ```rust
701 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
702 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
703 ///
704 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
705 /// let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
706 /// let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));
707 ///
708 /// set1.insert(1);
709 /// set1.insert(2);
710 /// set2.insert(1);
711 /// set2.insert(2);
712 /// set2.insert(3);
713 ///
714 /// assert!(set1.is_subset(&set2));
715 /// assert!(!set2.is_subset(&set1));
716 /// ```
717 pub fn is_subset(&self, other: &BTreeSet<K, M>) -> bool {
718 let mut self_iter = self.iter();
719 let mut other_iter = other.iter();
720
721 let mut self_next = self_iter.next();
722 let mut other_next = other_iter.next();
723
724 while let Some(ref self_key) = self_next {
725 match other_next {
726 Some(ref other_key) => match self_key.cmp(other_key) {
727 std::cmp::Ordering::Equal => {
728 // Keys match, advance both iterators.
729 self_next = self_iter.next();
730 other_next = other_iter.next();
731 }
732 std::cmp::Ordering::Greater => {
733 // Advance the `other` iterator if its key is smaller.
734 other_next = other_iter.next();
735 }
736 std::cmp::Ordering::Less => {
737 // `self_key` is smaller than the current smallest item of
738 // other which means that it cannot be found in `other`,
739 // so return false.
740 return false;
741 }
742 },
743 None => {
744 // If `other` is exhausted but `self` is not, return false.
745 return false;
746 }
747 }
748 }
749
750 // If we exhaust `self`, it is a subset of `other`.
751 true
752 }
753
754 /// Returns `true` if this set is a superset of another set.
755 ///
756 /// A set `A` is a superset of a set `B` if all elements of `B` are also elements of `A`.
757 ///
758 /// # Complexity
759 /// O(n + m), where:
760 /// - n is the size of the first set.
761 /// - m is the size of the second set.
762 ///
763 /// # Example
764 ///
765 /// ```rust
766 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
767 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
768 ///
769 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
770 /// let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
771 /// let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));
772 ///
773 /// set1.insert(1);
774 /// set1.insert(2);
775 /// set1.insert(3);
776 /// set2.insert(1);
777 /// set2.insert(2);
778 ///
779 /// assert!(set1.is_superset(&set2));
780 /// assert!(!set2.is_superset(&set1));
781 /// ```
782 pub fn is_superset(&self, other: &BTreeSet<K, M>) -> bool {
783 other.is_subset(self)
784 }
785
786 /// Returns an iterator over the symmetric difference of this set and another.
787 ///
788 /// The symmetric difference of two sets is the set of elements that are in either of the sets,
789 /// but not in their intersection.
790 ///
791 /// # Complexity
792 /// O(n + m), where:
793 /// - n is the size of the first set.
794 /// - m is the size of the second set.
795 ///
796 /// # Example
797 ///
798 /// ```rust
799 /// use ic_stable_structures::{BTreeSet, DefaultMemoryImpl};
800 /// use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
801 ///
802 /// let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
803 /// let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
804 /// let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));
805 ///
806 /// set1.insert(1);
807 /// set1.insert(2);
808 /// set2.insert(2);
809 /// set2.insert(3);
810 ///
811 /// let symmetric_diff: Vec<_> = set1.symmetric_difference(&set2).collect();
812 /// assert_eq!(symmetric_diff, vec![1, 3]);
813 /// ```
814 pub fn symmetric_difference<'a>(
815 &'a self,
816 other: &'a BTreeSet<K, M>,
817 ) -> impl Iterator<Item = K> + 'a {
818 let mut iter_self = self.iter();
819 let mut iter_other = other.iter();
820 let mut next_self = iter_self.next();
821 let mut next_other = iter_other.next();
822
823 // Use a closure to find common elements by traversing both iterators simultaneously.
824 std::iter::from_fn(move || {
825 // Loop until we detect a difference or exhaust either iterator.
826 loop {
827 return match (next_self.clone(), next_other.clone()) {
828 (Some(ref a), Some(ref b)) => {
829 match a.cmp(b) {
830 std::cmp::Ordering::Less => {
831 // If the element from `self` is smaller, yield it and advance `self`.
832 next_self = iter_self.next();
833 Some(a.clone())
834 }
835 std::cmp::Ordering::Greater => {
836 // If the element from `other` is smaller, yield it and advance `other`.
837 next_other = iter_other.next();
838 Some(b.clone())
839 }
840 std::cmp::Ordering::Equal => {
841 // Skip elements that are in both sets and advance both iterators.
842 next_self = iter_self.next();
843 next_other = iter_other.next();
844 continue;
845 }
846 }
847 }
848 (Some(ref a), None) => {
849 // If only `self` has elements remaining, yield them.
850 next_self = iter_self.next();
851 Some(a.clone())
852 }
853 (None, Some(ref b)) => {
854 // If only `other` has elements remaining, yield them.
855 next_other = iter_other.next();
856 Some(b.clone())
857 }
858 (None, None) => None,
859 };
860 }
861 })
862 }
863}
864
865#[cfg(test)]
866mod test {
867 use super::*;
868 use crate::storable::Blob;
869 use crate::VectorMemory;
870 use std::cell::RefCell;
871 use std::rc::Rc;
872
873 /// Creates a new shared memory instance.
874 pub(crate) fn make_memory() -> Rc<RefCell<Vec<u8>>> {
875 Rc::new(RefCell::new(Vec::new()))
876 }
877
878 pub(crate) fn b(x: &[u8]) -> Blob<10> {
879 Blob::<10>::try_from(x).unwrap()
880 }
881
882 /// A test runner that runs the test using `BTreeSet`.
883 pub fn run_btree_test<K, R, F>(f: F)
884 where
885 K: Storable + Ord + Clone,
886 F: Fn(BTreeSet<K, VectorMemory>) -> R,
887 {
888 let mem = make_memory();
889 let btree = BTreeSet::new(mem);
890 f(btree);
891 }
892
893 #[test]
894 fn test_union_with_duplicates() {
895 let mem1 = make_memory();
896 let mem2 = make_memory();
897 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
898 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
899
900 set1.insert(1);
901 set1.insert(2);
902 set1.insert(3);
903
904 set2.insert(2);
905 set2.insert(3);
906 set2.insert(4);
907
908 let union: Vec<_> = set1.union(&set2).collect();
909 assert_eq!(union, vec![1, 2, 3, 4]);
910 }
911
912 #[test]
913 fn test_intersection_with_duplicates() {
914 let mem1 = make_memory();
915 let mem2 = make_memory();
916 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
917 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
918
919 set1.insert(1);
920 set1.insert(2);
921 set1.insert(3);
922
923 set2.insert(2);
924 set2.insert(3);
925 set2.insert(4);
926
927 let intersection: Vec<_> = set1.intersection(&set2).collect();
928 assert_eq!(intersection, vec![2, 3]);
929 }
930
931 #[test]
932 fn test_union_and_intersection_with_identical_sets() {
933 let mem1 = Rc::new(RefCell::new(Vec::new()));
934 let mem2 = Rc::new(RefCell::new(Vec::new()));
935 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
936 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
937
938 for i in 0..100 {
939 set1.insert(i);
940 set2.insert(i);
941 }
942
943 let union: Vec<_> = set1.union(&set2).collect();
944 assert_eq!(union.len(), 100);
945 assert_eq!(union, (0..100).collect::<Vec<_>>());
946
947 let intersection: Vec<_> = set1.intersection(&set2).collect();
948 assert_eq!(intersection.len(), 100);
949 assert_eq!(intersection, (0..100).collect::<Vec<_>>());
950 }
951
952 #[test]
953 fn test_union_and_intersection_with_disjoin_sets() {
954 let mem1 = Rc::new(RefCell::new(Vec::new()));
955 let mem2 = Rc::new(RefCell::new(Vec::new()));
956 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
957 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
958
959 for i in 0..50 {
960 set1.insert(i);
961 }
962 for i in 50..100 {
963 set2.insert(i);
964 }
965
966 let union: Vec<_> = set1.union(&set2).collect();
967 assert_eq!(union.len(), 100);
968 assert_eq!(union, (0..100).collect::<Vec<_>>());
969
970 let intersection: Vec<_> = set1.intersection(&set2).collect();
971 assert!(intersection.is_empty());
972 }
973
974 #[test]
975 fn test_union_with_large_sets() {
976 let mem1 = Rc::new(RefCell::new(Vec::new()));
977 let mem2 = Rc::new(RefCell::new(Vec::new()));
978 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
979 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
980
981 for i in 0..1000 {
982 set1.insert(i);
983 }
984 for i in 500..1500 {
985 set2.insert(i);
986 }
987
988 let union: Vec<_> = set1.union(&set2).collect();
989 assert_eq!(union.len(), 1500);
990 assert_eq!(union[0], 0);
991 assert_eq!(union[1499], 1499);
992 }
993
994 #[test]
995 fn test_union_odd_even() {
996 let mem1 = Rc::new(RefCell::new(Vec::new()));
997 let mem2 = Rc::new(RefCell::new(Vec::new()));
998 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
999 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1000
1001 for i in 0..1000 {
1002 if i % 2 != 0 {
1003 set1.insert(i);
1004 } else {
1005 set2.insert(i);
1006 }
1007 }
1008
1009 let intersection: Vec<_> = set1.union(&set2).collect();
1010 assert_eq!(intersection.len(), 1000);
1011 assert_eq!(intersection, (0..1000).collect::<Vec<_>>());
1012 }
1013
1014 #[test]
1015 fn test_intersection_even() {
1016 let mem1 = Rc::new(RefCell::new(Vec::new()));
1017 let mem2 = Rc::new(RefCell::new(Vec::new()));
1018 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1019 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1020
1021 for i in 0..1000 {
1022 set1.insert(i);
1023 if i % 2 == 0 {
1024 set2.insert(i);
1025 }
1026 }
1027
1028 let intersection: Vec<_> = set1.intersection(&set2).collect();
1029 assert_eq!(intersection.len(), 500);
1030 assert_eq!(intersection, set2.iter().collect::<Vec<_>>());
1031 }
1032
1033 #[test]
1034 fn test_intersection_with_large_sets() {
1035 let mem1 = Rc::new(RefCell::new(Vec::new()));
1036 let mem2 = Rc::new(RefCell::new(Vec::new()));
1037 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1038 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1039
1040 for i in 0..1000 {
1041 set1.insert(i);
1042 }
1043 for i in 500..1500 {
1044 set2.insert(i);
1045 }
1046
1047 let intersection: Vec<_> = set1.intersection(&set2).collect();
1048 assert_eq!(intersection.len(), 500);
1049 assert_eq!(intersection[0], 500);
1050 assert_eq!(intersection[499], 999);
1051 }
1052
1053 #[test]
1054 fn init_preserves_data_set() {
1055 run_btree_test(|mut btree| {
1056 assert!(btree.insert(b(&[1, 2, 3])));
1057 assert!(btree.contains(&b(&[1, 2, 3])));
1058
1059 // Reload the btree
1060 let btree = BTreeSet::init(btree.into_memory());
1061
1062 // Data still exists.
1063 assert!(btree.contains(&b(&[1, 2, 3])));
1064 });
1065 }
1066
1067 #[test]
1068 fn test_insert_and_contains() {
1069 let mem = make_memory();
1070 let mut btreeset = BTreeSet::new(mem);
1071
1072 assert!(!btreeset.contains(&1u32));
1073 btreeset.insert(1u32);
1074 assert!(btreeset.contains(&1u32));
1075 }
1076
1077 #[test]
1078 fn test_remove() {
1079 let mem = make_memory();
1080 let mut btreeset = BTreeSet::new(mem);
1081
1082 btreeset.insert(1u32);
1083 assert!(btreeset.contains(&1u32));
1084 btreeset.remove(&1u32);
1085 assert!(!btreeset.contains(&1u32));
1086 }
1087
1088 #[test]
1089 fn test_iter() {
1090 let mem = make_memory();
1091 let mut btreeset = BTreeSet::new(mem);
1092
1093 btreeset.insert(1u32);
1094 btreeset.insert(2u32);
1095 btreeset.insert(3u32);
1096
1097 let elements: Vec<_> = btreeset.iter().collect();
1098 assert_eq!(elements, vec![1u32, 2u32, 3u32]);
1099 }
1100
1101 #[test]
1102 fn test_range() {
1103 let mem = make_memory();
1104 let mut btreeset = BTreeSet::new(mem);
1105
1106 for i in 1u32..=10 {
1107 btreeset.insert(i);
1108 }
1109
1110 let range: Vec<_> = btreeset.range(4u32..8u32).collect();
1111 assert_eq!(range, vec![4u32, 5u32, 6u32, 7u32]);
1112 }
1113
1114 #[test]
1115 fn test_first_and_last() {
1116 let mem = make_memory();
1117 let mut btreeset = BTreeSet::new(mem);
1118
1119 btreeset.insert(3u32);
1120 btreeset.insert(1u32);
1121 btreeset.insert(2u32);
1122
1123 assert_eq!(btreeset.first(), Some(1u32));
1124 assert_eq!(btreeset.last(), Some(3u32));
1125 }
1126
1127 #[test]
1128 fn test_len_and_is_empty() {
1129 let mem = make_memory();
1130 let mut btreeset = BTreeSet::new(mem);
1131
1132 assert!(btreeset.is_empty());
1133 assert_eq!(btreeset.len(), 0);
1134
1135 btreeset.insert(1u32);
1136 assert!(!btreeset.is_empty());
1137 assert_eq!(btreeset.len(), 1);
1138 }
1139
1140 #[test]
1141 fn test_pop_first_and_last() {
1142 let mem = make_memory();
1143 let mut btreeset = BTreeSet::new(mem);
1144
1145 btreeset.insert(3u32);
1146 btreeset.insert(1u32);
1147 btreeset.insert(2u32);
1148
1149 assert_eq!(btreeset.pop_first(), Some(1u32));
1150 assert_eq!(btreeset.pop_last(), Some(3u32));
1151 assert_eq!(btreeset.len(), 1);
1152 assert_eq!(btreeset.first(), Some(2u32));
1153 assert_eq!(btreeset.last(), Some(2u32));
1154 }
1155
1156 #[test]
1157 fn test_clear() {
1158 let mem = make_memory();
1159 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1160
1161 btreeset.insert(1);
1162 btreeset.insert(2);
1163 btreeset.insert(3);
1164
1165 assert_eq!(btreeset.len(), 3);
1166 btreeset.clear();
1167 assert!(btreeset.is_empty());
1168 assert_eq!(btreeset.len(), 0);
1169 assert_eq!(btreeset.iter().next(), None);
1170 }
1171
1172 #[test]
1173 fn test_iterate_large_set() {
1174 let mem = make_memory();
1175 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1176
1177 for i in 0..1000 {
1178 btreeset.insert(i);
1179 }
1180
1181 let elements: Vec<_> = btreeset.iter().collect();
1182 assert_eq!(elements.len(), 1000);
1183 assert_eq!(elements[0], 0);
1184 assert_eq!(elements[999], 999);
1185 }
1186
1187 #[test]
1188 fn test_range_large_set() {
1189 let mem = make_memory();
1190 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1191
1192 for i in 0u32..1000 {
1193 btreeset.insert(i);
1194 }
1195
1196 let range: Vec<_> = btreeset.range(100..200).collect();
1197 assert_eq!(range.len(), 100);
1198 assert_eq!(range[0], 100);
1199 assert_eq!(range[99], 199);
1200 }
1201
1202 #[test]
1203 fn test_empty_set() {
1204 let mem = make_memory();
1205 let btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1206
1207 assert!(btreeset.is_empty());
1208 assert_eq!(btreeset.len(), 0);
1209 assert_eq!(btreeset.first(), None);
1210 assert_eq!(btreeset.last(), None);
1211 assert_eq!(btreeset.iter().next(), None);
1212 }
1213
1214 #[test]
1215 fn test_insert_duplicate() {
1216 let mem = make_memory();
1217 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1218
1219 assert!(btreeset.insert(42));
1220 assert!(!btreeset.insert(42)); // Duplicate insert
1221 assert_eq!(btreeset.len(), 1);
1222 assert!(btreeset.contains(&42));
1223 }
1224
1225 #[test]
1226 fn test_remove_nonexistent() {
1227 let mem = make_memory();
1228 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1229
1230 assert!(!btreeset.remove(&42)); // Removing a non-existent element
1231 assert!(btreeset.is_empty());
1232 }
1233
1234 #[test]
1235 fn test_pop_first_and_last_empty() {
1236 let mem = make_memory();
1237 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1238
1239 assert_eq!(btreeset.pop_first(), None);
1240 assert_eq!(btreeset.pop_last(), None);
1241 }
1242
1243 #[test]
1244 fn test_range_empty() {
1245 let mem = make_memory();
1246 let btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1247
1248 let range: Vec<_> = btreeset.range(10..20).collect();
1249 assert!(range.is_empty());
1250 }
1251
1252 #[test]
1253 fn test_insert_and_remove_large_set() {
1254 let mem = make_memory();
1255 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1256
1257 for i in 0..1_000 {
1258 assert!(btreeset.insert(i));
1259 }
1260 assert_eq!(btreeset.len(), 1_000);
1261
1262 for i in 0..1_000 {
1263 assert!(btreeset.remove(&i));
1264 }
1265 assert!(btreeset.is_empty());
1266 }
1267
1268 #[test]
1269 fn test_remove_nonexistent_large_set() {
1270 let mem = make_memory();
1271 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1272
1273 for i in 0..1_000 {
1274 assert!(btreeset.insert(i));
1275 }
1276
1277 for i in 1_000..2_000 {
1278 assert!(!btreeset.remove(&i)); // Non-existent elements
1279 }
1280 assert_eq!(btreeset.len(), 1_000);
1281 }
1282
1283 #[test]
1284 fn test_iterate_empty_set() {
1285 let mem = make_memory();
1286 let btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1287
1288 let elements: Vec<_> = btreeset.iter().collect();
1289 assert!(elements.is_empty());
1290 }
1291
1292 #[test]
1293 fn test_range_with_no_matches() {
1294 let mem = make_memory();
1295 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1296
1297 for i in 0..10 {
1298 btreeset.insert(i);
1299 }
1300
1301 let range: Vec<_> = btreeset.range(20..30).collect();
1302 assert!(range.is_empty());
1303 }
1304
1305 #[test]
1306 fn test_clear_and_reuse() {
1307 let mem = make_memory();
1308 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1309
1310 for i in 0..100 {
1311 btreeset.insert(i);
1312 }
1313 assert_eq!(btreeset.len(), 100);
1314
1315 btreeset.clear();
1316 assert!(btreeset.is_empty());
1317
1318 for i in 100..200 {
1319 btreeset.insert(i);
1320 }
1321 assert_eq!(btreeset.len(), 100);
1322 assert!(btreeset.contains(&150));
1323 }
1324
1325 #[test]
1326 fn test_pop_first_and_last_large_set() {
1327 let mem = make_memory();
1328 let mut btreeset: BTreeSet<u32, _> = BTreeSet::new(mem);
1329
1330 for i in 0..1_000 {
1331 btreeset.insert(i);
1332 }
1333
1334 for i in 0..500 {
1335 assert_eq!(btreeset.pop_first(), Some(i));
1336 }
1337
1338 for i in (500..1_000).rev() {
1339 assert_eq!(btreeset.pop_last(), Some(i));
1340 }
1341
1342 assert!(btreeset.is_empty());
1343 }
1344
1345 #[test]
1346 fn test_is_disjoint_with_disjoint_sets() {
1347 let mem1 = make_memory();
1348 let mem2 = make_memory();
1349 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1350 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1351
1352 set1.insert(1);
1353 set1.insert(2);
1354
1355 set2.insert(3);
1356 set2.insert(4);
1357
1358 assert!(set1.is_disjoint(&set2));
1359 }
1360
1361 #[test]
1362 fn test_is_disjoint_with_overlapping_sets() {
1363 let mem1 = make_memory();
1364 let mem2 = make_memory();
1365 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1366 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1367
1368 set1.insert(1);
1369 set1.insert(2);
1370
1371 set2.insert(2);
1372 set2.insert(3);
1373
1374 assert!(!set1.is_disjoint(&set2));
1375 }
1376
1377 #[test]
1378 fn test_is_disjoint_with_large_sets() {
1379 let mem1 = make_memory();
1380 let mem2 = make_memory();
1381 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1382 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1383
1384 for i in 0..1000 {
1385 set1.insert(i);
1386 }
1387 for i in 1000..2000 {
1388 set2.insert(i);
1389 }
1390
1391 assert!(set1.is_disjoint(&set2));
1392
1393 set2.insert(500);
1394 assert!(!set1.is_disjoint(&set2));
1395 }
1396
1397 #[test]
1398 fn test_is_subset_with_subset() {
1399 let mem1 = make_memory();
1400 let mem2 = make_memory();
1401 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1402 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1403
1404 set1.insert(1);
1405 set1.insert(2);
1406
1407 set2.insert(1);
1408 set2.insert(2);
1409 set2.insert(3);
1410
1411 assert!(set1.is_subset(&set2));
1412 }
1413
1414 #[test]
1415 fn test_is_subset_with_non_subset() {
1416 let mem1 = make_memory();
1417 let mem2 = make_memory();
1418 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1419 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1420
1421 set1.insert(1);
1422 set1.insert(4);
1423
1424 set2.insert(1);
1425 set2.insert(2);
1426 set2.insert(3);
1427
1428 assert!(!set1.is_subset(&set2));
1429 }
1430
1431 #[test]
1432 fn test_is_subset_with_large_sets() {
1433 let mem1 = make_memory();
1434 let mem2 = make_memory();
1435 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1436 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1437
1438 for i in 0..500 {
1439 set1.insert(i);
1440 }
1441 for i in 0..1500 {
1442 set2.insert(i);
1443 }
1444
1445 assert!(set1.is_subset(&set2));
1446
1447 set1.insert(1500);
1448 assert!(!set1.is_subset(&set2));
1449 }
1450
1451 #[test]
1452 fn test_is_superset_with_superset() {
1453 let mem1 = make_memory();
1454 let mem2 = make_memory();
1455 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1456 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1457
1458 set1.insert(1);
1459 set1.insert(2);
1460 set1.insert(3);
1461
1462 set2.insert(1);
1463 set2.insert(2);
1464
1465 assert!(set1.is_superset(&set2));
1466 }
1467
1468 #[test]
1469 fn test_is_superset_with_non_superset() {
1470 let mem1 = make_memory();
1471 let mem2 = make_memory();
1472 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1473 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1474
1475 set1.insert(1);
1476 set1.insert(2);
1477
1478 set2.insert(1);
1479 set2.insert(3);
1480
1481 assert!(!set1.is_superset(&set2));
1482 }
1483
1484 #[test]
1485 fn test_is_superset_with_large_sets() {
1486 let mem1 = make_memory();
1487 let mem2 = make_memory();
1488 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1489 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1490
1491 for i in 0..1000 {
1492 set1.insert(i);
1493 }
1494 for i in 500..1000 {
1495 set2.insert(i);
1496 }
1497
1498 assert!(set1.is_superset(&set2));
1499
1500 set2.insert(1500);
1501 assert!(!set1.is_superset(&set2));
1502 }
1503
1504 #[test]
1505 fn test_symmetric_difference_with_disjoint_sets() {
1506 let mem1 = make_memory();
1507 let mem2 = make_memory();
1508 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1509 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1510
1511 set1.insert(1);
1512 set1.insert(2);
1513
1514 set2.insert(3);
1515 set2.insert(4);
1516
1517 let symmetric_diff: Vec<_> = set1.symmetric_difference(&set2).collect();
1518 assert_eq!(symmetric_diff, vec![1, 2, 3, 4]);
1519 }
1520
1521 #[test]
1522 fn test_symmetric_difference_with_overlapping_sets() {
1523 let mem1 = make_memory();
1524 let mem2 = make_memory();
1525 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1526 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1527
1528 set1.insert(1);
1529 set1.insert(2);
1530 set1.insert(3);
1531
1532 set2.insert(2);
1533 set2.insert(3);
1534 set2.insert(4);
1535
1536 let symmetric_diff: Vec<_> = set1.symmetric_difference(&set2).collect();
1537 assert_eq!(symmetric_diff, vec![1, 4]);
1538 }
1539
1540 #[test]
1541 fn test_symmetric_difference_with_identical_sets() {
1542 let mem1 = make_memory();
1543 let mem2 = make_memory();
1544 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1545 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1546
1547 set1.insert(1);
1548 set1.insert(2);
1549 set1.insert(3);
1550
1551 set2.insert(1);
1552 set2.insert(2);
1553 set2.insert(3);
1554
1555 let symmetric_diff: Vec<_> = set1.symmetric_difference(&set2).collect();
1556 assert!(symmetric_diff.is_empty());
1557 }
1558
1559 #[test]
1560 fn test_symmetric_difference_with_large_sets() {
1561 let mem1 = make_memory();
1562 let mem2 = make_memory();
1563 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1564 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1565
1566 for i in 0..1000 {
1567 set1.insert(i);
1568 }
1569 for i in 500..1500 {
1570 set2.insert(i);
1571 }
1572
1573 let symmetric_diff: Vec<_> = set1.symmetric_difference(&set2).collect();
1574 assert_eq!(symmetric_diff.len(), 1000);
1575 assert_eq!(symmetric_diff[..500], (0..500).collect::<Vec<_>>());
1576 assert_eq!(symmetric_diff[500..], (1000..1500).collect::<Vec<_>>());
1577 }
1578
1579 #[test]
1580 fn test_symmetric_difference_odd_even() {
1581 let mem1 = Rc::new(RefCell::new(Vec::new()));
1582 let mem2 = Rc::new(RefCell::new(Vec::new()));
1583 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1584 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1585
1586 for i in 0..1000 {
1587 if i % 2 != 0 {
1588 set1.insert(i);
1589 } else {
1590 set2.insert(i);
1591 }
1592 }
1593
1594 let intersection: Vec<_> = set1.symmetric_difference(&set2).collect();
1595 assert_eq!(intersection.len(), 1000);
1596 assert_eq!(intersection, (0..1000).collect::<Vec<_>>());
1597 }
1598
1599 #[test]
1600 fn test_symmetric_difference_even() {
1601 let mem1 = Rc::new(RefCell::new(Vec::new()));
1602 let mem2 = Rc::new(RefCell::new(Vec::new()));
1603 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1604 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1605
1606 let mut expected_res = vec![];
1607
1608 for i in 0..1000 {
1609 set1.insert(i);
1610
1611 if i % 2 == 0 {
1612 set2.insert(i);
1613 } else {
1614 expected_res.push(i);
1615 }
1616 }
1617
1618 let intersection: Vec<_> = set1.symmetric_difference(&set2).collect();
1619 assert_eq!(intersection.len(), 500);
1620 assert_eq!(intersection, expected_res);
1621 }
1622
1623 #[test]
1624 fn test_is_subset_with_sparse_elements() {
1625 let mem1 = make_memory();
1626 let mem2 = make_memory();
1627 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1628 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1629
1630 for i in (0..1000).step_by(10) {
1631 set1.insert(i);
1632 }
1633 for i in (0..2000).step_by(5) {
1634 set2.insert(i);
1635 }
1636
1637 assert!(set1.is_subset(&set2));
1638
1639 set1.insert(2001);
1640 assert!(!set1.is_subset(&set2));
1641 }
1642
1643 #[test]
1644 fn test_is_disjoint_with_sparse_elements() {
1645 let mem1 = make_memory();
1646 let mem2 = make_memory();
1647 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1648 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1649
1650 for i in (0..1000).step_by(10) {
1651 set1.insert(i);
1652 }
1653 for i in (1..1000).step_by(10) {
1654 set2.insert(i);
1655 }
1656
1657 assert!(set1.is_disjoint(&set2));
1658
1659 set2.insert(20);
1660 assert!(!set1.is_disjoint(&set2));
1661 }
1662
1663 #[test]
1664 fn test_is_superset_with_sparse_elements() {
1665 let mem1 = make_memory();
1666 let mem2 = make_memory();
1667 let mut set1: BTreeSet<u32, _> = BTreeSet::new(mem1);
1668 let mut set2: BTreeSet<u32, _> = BTreeSet::new(mem2);
1669
1670 for i in (0..2000).step_by(5) {
1671 set1.insert(i);
1672 }
1673 for i in (0..1000).step_by(10) {
1674 set2.insert(i);
1675 }
1676
1677 assert!(set1.is_superset(&set2));
1678
1679 set2.insert(2001);
1680 assert!(!set1.is_superset(&set2));
1681 }
1682}