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