alloc/collections/btree/set.rs
1use core::borrow::Borrow;
2use core::cmp::Ordering::{self, Equal, Greater, Less};
3use core::cmp::{max, min};
4use core::fmt::{self, Debug};
5use core::hash::{Hash, Hasher};
6use core::iter::{FusedIterator, Peekable, TrustedLen};
7use core::mem::ManuallyDrop;
8use core::ops::{BitAnd, BitOr, BitXor, Bound, RangeBounds, Sub};
9
10use super::map::{self, BTreeMap, Keys};
11use super::merge_iter::MergeIterInner;
12use super::set_val::SetValZST;
13use crate::alloc::{AllocatorClone, Global};
14use crate::vec::Vec;
15
16mod entry;
17
18#[unstable(feature = "btree_set_entry", issue = "133549")]
19pub use self::entry::{Entry, OccupiedEntry, VacantEntry};
20
21/// An ordered set based on a B-Tree.
22///
23/// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
24/// benefits and drawbacks.
25///
26/// It is a logic error for an item to be modified in such a way that the item's ordering relative
27/// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
28/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
29/// The behavior resulting from such a logic error is not specified, but will be encapsulated to the
30/// `BTreeSet` that observed the logic error and not result in undefined behavior. This could
31/// include panics, incorrect results, aborts, memory leaks, and non-termination.
32///
33/// Iterators returned by [`BTreeSet::iter`] and [`BTreeSet::into_iter`] produce their items in order, and take worst-case
34/// logarithmic and amortized constant time per item returned.
35///
36/// [`Cell`]: core::cell::Cell
37/// [`RefCell`]: core::cell::RefCell
38///
39/// # Examples
40///
41/// ```
42/// use std::collections::BTreeSet;
43///
44/// // Type inference lets us omit an explicit type signature (which
45/// // would be `BTreeSet<&str>` in this example).
46/// let mut books = BTreeSet::new();
47///
48/// // Add some books.
49/// books.insert("A Dance With Dragons");
50/// books.insert("To Kill a Mockingbird");
51/// books.insert("The Odyssey");
52/// books.insert("The Great Gatsby");
53///
54/// // Check for a specific one.
55/// if !books.contains("The Winds of Winter") {
56/// println!("We have {} books, but The Winds of Winter ain't one.",
57/// books.len());
58/// }
59///
60/// // Remove a book.
61/// books.remove("The Odyssey");
62///
63/// // Iterate over everything.
64/// for book in &books {
65/// println!("{book}");
66/// }
67/// ```
68///
69/// A `BTreeSet` with a known list of items can be initialized from an array:
70///
71/// ```
72/// use std::collections::BTreeSet;
73///
74/// let set = BTreeSet::from([1, 2, 3]);
75/// ```
76#[stable(feature = "rust1", since = "1.0.0")]
77#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeSet")]
78pub struct BTreeSet<
79 T,
80 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
81> {
82 map: BTreeMap<T, SetValZST, A>,
83}
84
85#[stable(feature = "rust1", since = "1.0.0")]
86impl<T: Hash, A: AllocatorClone> Hash for BTreeSet<T, A> {
87 fn hash<H: Hasher>(&self, state: &mut H) {
88 self.map.hash(state)
89 }
90}
91
92#[stable(feature = "rust1", since = "1.0.0")]
93impl<T: PartialEq, A: AllocatorClone> PartialEq for BTreeSet<T, A> {
94 fn eq(&self, other: &BTreeSet<T, A>) -> bool {
95 self.map.eq(&other.map)
96 }
97}
98
99#[stable(feature = "rust1", since = "1.0.0")]
100impl<T: Eq, A: AllocatorClone> Eq for BTreeSet<T, A> {}
101
102#[stable(feature = "rust1", since = "1.0.0")]
103impl<T: PartialOrd, A: AllocatorClone> PartialOrd for BTreeSet<T, A> {
104 fn partial_cmp(&self, other: &BTreeSet<T, A>) -> Option<Ordering> {
105 self.map.partial_cmp(&other.map)
106 }
107}
108
109#[stable(feature = "rust1", since = "1.0.0")]
110impl<T: Ord, A: AllocatorClone> Ord for BTreeSet<T, A> {
111 fn cmp(&self, other: &BTreeSet<T, A>) -> Ordering {
112 self.map.cmp(&other.map)
113 }
114}
115
116#[stable(feature = "rust1", since = "1.0.0")]
117impl<T: Clone, A: AllocatorClone> Clone for BTreeSet<T, A> {
118 fn clone(&self) -> Self {
119 BTreeSet { map: self.map.clone() }
120 }
121
122 fn clone_from(&mut self, source: &Self) {
123 self.map.clone_from(&source.map);
124 }
125}
126
127/// An iterator over the items of a `BTreeSet`.
128///
129/// This `struct` is created by the [`iter`] method on [`BTreeSet`].
130/// See its documentation for more.
131///
132/// [`iter`]: BTreeSet::iter
133#[must_use = "iterators are lazy and do nothing unless consumed"]
134#[stable(feature = "rust1", since = "1.0.0")]
135pub struct Iter<'a, T: 'a> {
136 iter: Keys<'a, T, SetValZST>,
137}
138
139#[stable(feature = "collection_debug", since = "1.17.0")]
140impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
141 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
142 f.debug_tuple("Iter").field(&self.iter).finish()
143 }
144}
145
146/// An owning iterator over the items of a `BTreeSet` in ascending order.
147///
148/// This `struct` is created by the [`into_iter`] method on [`BTreeSet`]
149/// (provided by the [`IntoIterator`] trait). See its documentation for more.
150///
151/// [`into_iter`]: BTreeSet#method.into_iter
152#[stable(feature = "rust1", since = "1.0.0")]
153#[derive(Debug)]
154pub struct IntoIter<
155 T,
156 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
157> {
158 iter: super::map::IntoIter<T, SetValZST, A>,
159}
160
161/// An iterator over a sub-range of items in a `BTreeSet`.
162///
163/// This `struct` is created by the [`range`] method on [`BTreeSet`].
164/// See its documentation for more.
165///
166/// [`range`]: BTreeSet::range
167#[must_use = "iterators are lazy and do nothing unless consumed"]
168#[derive(Debug)]
169#[stable(feature = "btree_range", since = "1.17.0")]
170pub struct Range<'a, T: 'a> {
171 iter: super::map::Range<'a, T, SetValZST>,
172}
173
174/// A lazy iterator producing elements in the difference of `BTreeSet`s.
175///
176/// This `struct` is created by the [`difference`] method on [`BTreeSet`].
177/// See its documentation for more.
178///
179/// [`difference`]: BTreeSet::difference
180#[must_use = "this returns the difference as an iterator, \
181 without modifying either input set"]
182#[stable(feature = "rust1", since = "1.0.0")]
183pub struct Difference<
184 'a,
185 T: 'a,
186 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
187> {
188 inner: DifferenceInner<'a, T, A>,
189}
190enum DifferenceInner<'a, T: 'a, A: AllocatorClone> {
191 Stitch {
192 // iterate all of `self` and some of `other`, spotting matches along the way
193 self_iter: Iter<'a, T>,
194 other_iter: Peekable<Iter<'a, T>>,
195 },
196 Search {
197 // iterate `self`, look up in `other`
198 self_iter: Iter<'a, T>,
199 other_set: &'a BTreeSet<T, A>,
200 },
201 Iterate(Iter<'a, T>), // simply produce all elements in `self`
202}
203
204// Explicit Debug impl necessary because of issue #26925
205impl<T: Debug, A: AllocatorClone> Debug for DifferenceInner<'_, T, A> {
206 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
207 match self {
208 DifferenceInner::Stitch { self_iter, other_iter } => f
209 .debug_struct("Stitch")
210 .field("self_iter", self_iter)
211 .field("other_iter", other_iter)
212 .finish(),
213 DifferenceInner::Search { self_iter, other_set } => f
214 .debug_struct("Search")
215 .field("self_iter", self_iter)
216 .field("other_iter", other_set)
217 .finish(),
218 DifferenceInner::Iterate(x) => f.debug_tuple("Iterate").field(x).finish(),
219 }
220 }
221}
222
223#[stable(feature = "collection_debug", since = "1.17.0")]
224impl<T: fmt::Debug, A: AllocatorClone> fmt::Debug for Difference<'_, T, A> {
225 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
226 f.debug_tuple("Difference").field(&self.inner).finish()
227 }
228}
229
230/// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s.
231///
232/// This `struct` is created by the [`symmetric_difference`] method on
233/// [`BTreeSet`]. See its documentation for more.
234///
235/// [`symmetric_difference`]: BTreeSet::symmetric_difference
236#[must_use = "this returns the difference as an iterator, \
237 without modifying either input set"]
238#[stable(feature = "rust1", since = "1.0.0")]
239pub struct SymmetricDifference<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
240
241#[stable(feature = "collection_debug", since = "1.17.0")]
242impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> {
243 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244 f.debug_tuple("SymmetricDifference").field(&self.0).finish()
245 }
246}
247
248/// A lazy iterator producing elements in the intersection of `BTreeSet`s.
249///
250/// This `struct` is created by the [`intersection`] method on [`BTreeSet`].
251/// See its documentation for more.
252///
253/// [`intersection`]: BTreeSet::intersection
254#[must_use = "this returns the intersection as an iterator, \
255 without modifying either input set"]
256#[stable(feature = "rust1", since = "1.0.0")]
257pub struct Intersection<
258 'a,
259 T: 'a,
260 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
261> {
262 inner: IntersectionInner<'a, T, A>,
263}
264enum IntersectionInner<'a, T: 'a, A: AllocatorClone> {
265 Stitch {
266 // iterate similarly sized sets jointly, spotting matches along the way
267 a: Iter<'a, T>,
268 b: Iter<'a, T>,
269 },
270 Search {
271 // iterate a small set, look up in the large set
272 small_iter: Iter<'a, T>,
273 large_set: &'a BTreeSet<T, A>,
274 },
275 Answer(Option<&'a T>), // return a specific element or emptiness
276}
277
278// Explicit Debug impl necessary because of issue #26925
279impl<T: Debug, A: AllocatorClone> Debug for IntersectionInner<'_, T, A> {
280 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
281 match self {
282 IntersectionInner::Stitch { a, b } => {
283 f.debug_struct("Stitch").field("a", a).field("b", b).finish()
284 }
285 IntersectionInner::Search { small_iter, large_set } => f
286 .debug_struct("Search")
287 .field("small_iter", small_iter)
288 .field("large_set", large_set)
289 .finish(),
290 IntersectionInner::Answer(x) => f.debug_tuple("Answer").field(x).finish(),
291 }
292 }
293}
294
295#[stable(feature = "collection_debug", since = "1.17.0")]
296impl<T: Debug, A: AllocatorClone> Debug for Intersection<'_, T, A> {
297 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
298 f.debug_tuple("Intersection").field(&self.inner).finish()
299 }
300}
301
302/// A lazy iterator producing elements in the union of `BTreeSet`s.
303///
304/// This `struct` is created by the [`union`] method on [`BTreeSet`].
305/// See its documentation for more.
306///
307/// [`union`]: BTreeSet::union
308#[must_use = "this returns the union as an iterator, \
309 without modifying either input set"]
310#[stable(feature = "rust1", since = "1.0.0")]
311pub struct Union<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
312
313#[stable(feature = "collection_debug", since = "1.17.0")]
314impl<T: fmt::Debug> fmt::Debug for Union<'_, T> {
315 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
316 f.debug_tuple("Union").field(&self.0).finish()
317 }
318}
319
320// This constant is used by functions that compare two sets.
321// It estimates the relative size at which searching performs better
322// than iterating, based on the benchmarks in
323// https://github.com/ssomers/rust_bench_btreeset_intersection.
324// It's used to divide rather than multiply sizes, to rule out overflow,
325// and it's a power of two to make that division cheap.
326const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = 16;
327
328impl<T> BTreeSet<T> {
329 /// Makes a new, empty `BTreeSet`.
330 ///
331 /// Does not allocate anything on its own.
332 ///
333 /// # Examples
334 ///
335 /// ```
336 /// # #![allow(unused_mut)]
337 /// use std::collections::BTreeSet;
338 ///
339 /// let mut set: BTreeSet<i32> = BTreeSet::new();
340 /// ```
341 #[stable(feature = "rust1", since = "1.0.0")]
342 #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
343 #[must_use]
344 pub const fn new() -> BTreeSet<T> {
345 BTreeSet { map: BTreeMap::new() }
346 }
347}
348
349impl<T, A: AllocatorClone> BTreeSet<T, A> {
350 /// Makes a new `BTreeSet` with a reasonable choice of B.
351 ///
352 /// # Examples
353 ///
354 /// ```
355 /// # #![allow(unused_mut)]
356 /// # #![feature(btreemap_alloc)]
357 ///
358 /// use std::collections::BTreeSet;
359 /// use std::alloc::Global;
360 ///
361 /// let set: BTreeSet<i32> = BTreeSet::new_in(Global);
362 /// ```
363 #[unstable(feature = "btreemap_alloc", issue = "163177")]
364 #[must_use]
365 pub const fn new_in(alloc: A) -> BTreeSet<T, A> {
366 BTreeSet { map: BTreeMap::new_in(alloc) }
367 }
368
369 /// Returns a reference to the underlying allocator.
370 #[unstable(feature = "btreemap_alloc", issue = "163177")]
371 #[inline]
372 pub fn allocator(&self) -> &A {
373 self.map.allocator()
374 }
375
376 /// Constructs a double-ended iterator over a sub-range of elements in the set.
377 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
378 /// yield elements from min (inclusive) to max (exclusive).
379 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
380 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
381 /// range from 4 to 10.
382 ///
383 /// # Panics
384 ///
385 /// Panics if range `start > end`.
386 /// Panics if range `start == end` and both bounds are `Excluded`.
387 ///
388 /// # Examples
389 ///
390 /// ```
391 /// use std::collections::BTreeSet;
392 /// use std::ops::Bound::Included;
393 ///
394 /// let mut set = BTreeSet::new();
395 /// set.insert(3);
396 /// set.insert(5);
397 /// set.insert(8);
398 /// for &elem in set.range((Included(&4), Included(&8))) {
399 /// println!("{elem}");
400 /// }
401 /// assert_eq!(Some(&5), set.range(4..).next());
402 /// ```
403 #[stable(feature = "btree_range", since = "1.17.0")]
404 pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
405 where
406 K: Ord,
407 T: Borrow<K> + Ord,
408 R: RangeBounds<K>,
409 {
410 Range { iter: self.map.range(range) }
411 }
412
413 /// Visits the elements representing the difference,
414 /// i.e., the elements that are in `self` but not in `other`,
415 /// in ascending order.
416 ///
417 /// # Examples
418 ///
419 /// ```
420 /// use std::collections::BTreeSet;
421 ///
422 /// let mut a = BTreeSet::new();
423 /// a.insert(1);
424 /// a.insert(2);
425 ///
426 /// let mut b = BTreeSet::new();
427 /// b.insert(2);
428 /// b.insert(3);
429 ///
430 /// let diff: Vec<_> = a.difference(&b).cloned().collect();
431 /// assert_eq!(diff, [1]);
432 /// ```
433 #[stable(feature = "rust1", since = "1.0.0")]
434 pub fn difference<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Difference<'a, T, A>
435 where
436 T: Ord,
437 {
438 if let Some(self_min) = self.first()
439 && let Some(self_max) = self.last()
440 && let Some(other_min) = other.first()
441 && let Some(other_max) = other.last()
442 {
443 Difference {
444 inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
445 (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()),
446 (Equal, _) => {
447 let mut self_iter = self.iter();
448 self_iter.next();
449 DifferenceInner::Iterate(self_iter)
450 }
451 (_, Equal) => {
452 let mut self_iter = self.iter();
453 self_iter.next_back();
454 DifferenceInner::Iterate(self_iter)
455 }
456 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
457 DifferenceInner::Search { self_iter: self.iter(), other_set: other }
458 }
459 _ => DifferenceInner::Stitch {
460 self_iter: self.iter(),
461 other_iter: other.iter().peekable(),
462 },
463 },
464 }
465 } else {
466 Difference { inner: DifferenceInner::Iterate(self.iter()) }
467 }
468 }
469
470 /// Visits the elements representing the symmetric difference,
471 /// i.e., the elements that are in `self` or in `other` but not in both,
472 /// in ascending order.
473 ///
474 /// # Examples
475 ///
476 /// ```
477 /// use std::collections::BTreeSet;
478 ///
479 /// let mut a = BTreeSet::new();
480 /// a.insert(1);
481 /// a.insert(2);
482 ///
483 /// let mut b = BTreeSet::new();
484 /// b.insert(2);
485 /// b.insert(3);
486 ///
487 /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
488 /// assert_eq!(sym_diff, [1, 3]);
489 /// ```
490 #[stable(feature = "rust1", since = "1.0.0")]
491 pub fn symmetric_difference<'a>(
492 &'a self,
493 other: &'a BTreeSet<T, A>,
494 ) -> SymmetricDifference<'a, T>
495 where
496 T: Ord,
497 {
498 SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
499 }
500
501 /// Visits the elements representing the intersection,
502 /// i.e., the elements that are both in `self` and `other`,
503 /// in ascending order.
504 ///
505 /// # Examples
506 ///
507 /// ```
508 /// use std::collections::BTreeSet;
509 ///
510 /// let mut a = BTreeSet::new();
511 /// a.insert(1);
512 /// a.insert(2);
513 ///
514 /// let mut b = BTreeSet::new();
515 /// b.insert(2);
516 /// b.insert(3);
517 ///
518 /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
519 /// assert_eq!(intersection, [2]);
520 /// ```
521 #[stable(feature = "rust1", since = "1.0.0")]
522 pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Intersection<'a, T, A>
523 where
524 T: Ord,
525 {
526 if let Some(self_min) = self.first()
527 && let Some(self_max) = self.last()
528 && let Some(other_min) = other.first()
529 && let Some(other_max) = other.last()
530 {
531 Intersection {
532 inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
533 (Greater, _) | (_, Less) => IntersectionInner::Answer(None),
534 (Equal, _) => IntersectionInner::Answer(Some(self_min)),
535 (_, Equal) => IntersectionInner::Answer(Some(self_max)),
536 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
537 IntersectionInner::Search { small_iter: self.iter(), large_set: other }
538 }
539 _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
540 IntersectionInner::Search { small_iter: other.iter(), large_set: self }
541 }
542 _ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() },
543 },
544 }
545 } else {
546 Intersection { inner: IntersectionInner::Answer(None) }
547 }
548 }
549
550 /// Visits the elements representing the union,
551 /// i.e., all the elements in `self` or `other`, without duplicates,
552 /// in ascending order.
553 ///
554 /// # Examples
555 ///
556 /// ```
557 /// use std::collections::BTreeSet;
558 ///
559 /// let mut a = BTreeSet::new();
560 /// a.insert(1);
561 ///
562 /// let mut b = BTreeSet::new();
563 /// b.insert(2);
564 ///
565 /// let union: Vec<_> = a.union(&b).cloned().collect();
566 /// assert_eq!(union, [1, 2]);
567 /// ```
568 #[stable(feature = "rust1", since = "1.0.0")]
569 pub fn union<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Union<'a, T>
570 where
571 T: Ord,
572 {
573 Union(MergeIterInner::new(self.iter(), other.iter()))
574 }
575
576 /// Clears the set, removing all elements.
577 ///
578 /// # Examples
579 ///
580 /// ```
581 /// use std::collections::BTreeSet;
582 ///
583 /// let mut v = BTreeSet::new();
584 /// v.insert(1);
585 /// v.clear();
586 /// assert!(v.is_empty());
587 /// ```
588 #[stable(feature = "rust1", since = "1.0.0")]
589 pub fn clear(&mut self)
590 where
591 A: Clone,
592 {
593 self.map.clear()
594 }
595
596 /// Returns `true` if the set contains an element equal to the value.
597 ///
598 /// The value may be any borrowed form of the set's element type,
599 /// but the ordering on the borrowed form *must* match the
600 /// ordering on the element type.
601 ///
602 /// # Examples
603 ///
604 /// ```
605 /// use std::collections::BTreeSet;
606 ///
607 /// let set = BTreeSet::from([1, 2, 3]);
608 /// assert_eq!(set.contains(&1), true);
609 /// assert_eq!(set.contains(&4), false);
610 /// ```
611 #[stable(feature = "rust1", since = "1.0.0")]
612 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
613 where
614 T: Borrow<Q> + Ord,
615 Q: Ord,
616 {
617 self.map.contains_key(value)
618 }
619
620 /// Returns a reference to the element in the set, if any, that is equal to
621 /// the value.
622 ///
623 /// The value may be any borrowed form of the set's element type,
624 /// but the ordering on the borrowed form *must* match the
625 /// ordering on the element type.
626 ///
627 /// # Examples
628 ///
629 /// ```
630 /// use std::collections::BTreeSet;
631 ///
632 /// let set = BTreeSet::from([1, 2, 3]);
633 /// assert_eq!(set.get(&2), Some(&2));
634 /// assert_eq!(set.get(&4), None);
635 /// ```
636 #[stable(feature = "set_recovery", since = "1.9.0")]
637 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
638 where
639 T: Borrow<Q> + Ord,
640 Q: Ord,
641 {
642 self.map.get_key_value(value).map(|(k, _)| k)
643 }
644
645 /// Returns `true` if `self` has no elements in common with `other`.
646 /// This is equivalent to checking for an empty intersection.
647 ///
648 /// # Examples
649 ///
650 /// ```
651 /// use std::collections::BTreeSet;
652 ///
653 /// let a = BTreeSet::from([1, 2, 3]);
654 /// let mut b = BTreeSet::new();
655 ///
656 /// assert_eq!(a.is_disjoint(&b), true);
657 /// b.insert(4);
658 /// assert_eq!(a.is_disjoint(&b), true);
659 /// b.insert(1);
660 /// assert_eq!(a.is_disjoint(&b), false);
661 /// ```
662 #[must_use]
663 #[stable(feature = "rust1", since = "1.0.0")]
664 pub fn is_disjoint(&self, other: &BTreeSet<T, A>) -> bool
665 where
666 T: Ord,
667 {
668 self.intersection(other).next().is_none()
669 }
670
671 /// Returns `true` if the set is a subset of another,
672 /// i.e., `other` contains at least all the elements in `self`.
673 ///
674 /// # Examples
675 ///
676 /// ```
677 /// use std::collections::BTreeSet;
678 ///
679 /// let sup = BTreeSet::from([1, 2, 3]);
680 /// let mut set = BTreeSet::new();
681 ///
682 /// assert_eq!(set.is_subset(&sup), true);
683 /// set.insert(2);
684 /// assert_eq!(set.is_subset(&sup), true);
685 /// set.insert(4);
686 /// assert_eq!(set.is_subset(&sup), false);
687 /// ```
688 #[must_use]
689 #[stable(feature = "rust1", since = "1.0.0")]
690 pub fn is_subset(&self, other: &BTreeSet<T, A>) -> bool
691 where
692 T: Ord,
693 {
694 // Same result as self.difference(other).next().is_none()
695 // but the code below is faster (hugely in some cases).
696 if self.len() > other.len() {
697 return false; // self has more elements than other
698 }
699 let (Some(self_min), Some(self_max)) = (self.first(), self.last()) else {
700 return true; // self is empty
701 };
702 let (Some(other_min), Some(other_max)) = (other.first(), other.last()) else {
703 return false; // other is empty
704 };
705 let mut self_iter = self.iter();
706 match self_min.cmp(other_min) {
707 Less => return false, // other does not contain self_min
708 Equal => {
709 self_iter.next(); // self_min is contained in other, so remove it from consideration
710 // other_min is now not in self_iter (used below)
711 }
712 Greater => {} // other_min is not in self_iter (used below)
713 };
714
715 match self_max.cmp(other_max) {
716 Greater => return false, // other does not contain self_max
717 Equal => {
718 self_iter.next_back(); // self_max is contained in other, so remove it from consideration
719 // other_max is now not in self_iter (used below)
720 }
721 Less => {} // other_max is not in self_iter (used below)
722 };
723 if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
724 self_iter.all(|e| other.contains(e))
725 } else {
726 let mut other_iter = other.iter();
727 {
728 // remove other_min and other_max as they are not in self_iter (see above)
729 other_iter.next();
730 other_iter.next_back();
731 }
732 // custom `self_iter.all(|e| other.contains(e))`
733 self_iter.all(|self1| {
734 while let Some(other1) = other_iter.next() {
735 match other1.cmp(self1) {
736 // happens up to `ITER_PERFORMANCE_TIPPING_SIZE_DIFF * self.len() - 1` times
737 Less => continue, // skip over elements that are smaller
738 // happens `self.len()` times
739 Equal => return true, // self1 is in other
740 // happens only once
741 Greater => return false, // self1 is not in other
742 }
743 }
744 false
745 })
746 }
747 }
748
749 /// Returns `true` if the set is a superset of another,
750 /// i.e., `self` contains at least all the elements in `other`.
751 ///
752 /// # Examples
753 ///
754 /// ```
755 /// use std::collections::BTreeSet;
756 ///
757 /// let sub = BTreeSet::from([1, 2]);
758 /// let mut set = BTreeSet::new();
759 ///
760 /// assert_eq!(set.is_superset(&sub), false);
761 ///
762 /// set.insert(0);
763 /// set.insert(1);
764 /// assert_eq!(set.is_superset(&sub), false);
765 ///
766 /// set.insert(2);
767 /// assert_eq!(set.is_superset(&sub), true);
768 /// ```
769 #[must_use]
770 #[stable(feature = "rust1", since = "1.0.0")]
771 pub fn is_superset(&self, other: &BTreeSet<T, A>) -> bool
772 where
773 T: Ord,
774 {
775 other.is_subset(self)
776 }
777
778 /// Returns a reference to the first element in the set, if any.
779 /// This element is always the minimum of all elements in the set.
780 ///
781 /// # Examples
782 ///
783 /// Basic usage:
784 ///
785 /// ```
786 /// use std::collections::BTreeSet;
787 ///
788 /// let mut set = BTreeSet::new();
789 /// assert_eq!(set.first(), None);
790 /// set.insert(1);
791 /// assert_eq!(set.first(), Some(&1));
792 /// set.insert(2);
793 /// assert_eq!(set.first(), Some(&1));
794 /// ```
795 #[must_use]
796 #[stable(feature = "map_first_last", since = "1.66.0")]
797 #[rustc_confusables("front")]
798 pub fn first(&self) -> Option<&T>
799 where
800 T: Ord,
801 {
802 self.map.first_key_value().map(|(k, _)| k)
803 }
804
805 /// Returns a reference to the last element in the set, if any.
806 /// This element is always the maximum of all elements in the set.
807 ///
808 /// # Examples
809 ///
810 /// Basic usage:
811 ///
812 /// ```
813 /// use std::collections::BTreeSet;
814 ///
815 /// let mut set = BTreeSet::new();
816 /// assert_eq!(set.last(), None);
817 /// set.insert(1);
818 /// assert_eq!(set.last(), Some(&1));
819 /// set.insert(2);
820 /// assert_eq!(set.last(), Some(&2));
821 /// ```
822 #[must_use]
823 #[stable(feature = "map_first_last", since = "1.66.0")]
824 #[rustc_confusables("back")]
825 pub fn last(&self) -> Option<&T>
826 where
827 T: Ord,
828 {
829 self.map.last_key_value().map(|(k, _)| k)
830 }
831
832 /// Removes the first element from the set and returns it, if any.
833 /// The first element is always the minimum element in the set.
834 ///
835 /// # Examples
836 ///
837 /// ```
838 /// use std::collections::BTreeSet;
839 ///
840 /// let mut set = BTreeSet::new();
841 ///
842 /// set.insert(1);
843 /// while let Some(n) = set.pop_first() {
844 /// assert_eq!(n, 1);
845 /// }
846 /// assert!(set.is_empty());
847 /// ```
848 #[stable(feature = "map_first_last", since = "1.66.0")]
849 pub fn pop_first(&mut self) -> Option<T>
850 where
851 T: Ord,
852 {
853 self.map.pop_first().map(|kv| kv.0)
854 }
855
856 /// Removes the last element from the set and returns it, if any.
857 /// The last element is always the maximum element in the set.
858 ///
859 /// # Examples
860 ///
861 /// ```
862 /// use std::collections::BTreeSet;
863 ///
864 /// let mut set = BTreeSet::new();
865 ///
866 /// set.insert(1);
867 /// while let Some(n) = set.pop_last() {
868 /// assert_eq!(n, 1);
869 /// }
870 /// assert!(set.is_empty());
871 /// ```
872 #[stable(feature = "map_first_last", since = "1.66.0")]
873 pub fn pop_last(&mut self) -> Option<T>
874 where
875 T: Ord,
876 {
877 self.map.pop_last().map(|kv| kv.0)
878 }
879
880 /// Adds a value to the set.
881 ///
882 /// Returns whether the value was newly inserted. That is:
883 ///
884 /// - If the set did not previously contain an equal value, `true` is
885 /// returned.
886 /// - If the set already contained an equal value, `false` is returned, and
887 /// the entry is not updated.
888 ///
889 /// See the [module-level documentation] for more.
890 ///
891 /// [module-level documentation]: index.html#insert-and-complex-keys
892 ///
893 /// # Examples
894 ///
895 /// ```
896 /// use std::collections::BTreeSet;
897 ///
898 /// let mut set = BTreeSet::new();
899 ///
900 /// assert_eq!(set.insert(2), true);
901 /// assert_eq!(set.insert(2), false);
902 /// assert_eq!(set.len(), 1);
903 /// ```
904 #[stable(feature = "rust1", since = "1.0.0")]
905 #[rustc_confusables("push", "put")]
906 pub fn insert(&mut self, value: T) -> bool
907 where
908 T: Ord,
909 {
910 self.map.insert(value, SetValZST).is_none()
911 }
912
913 /// Adds a value to the set, replacing the existing element, if any, that is
914 /// equal to the value. Returns the replaced element.
915 ///
916 /// # Examples
917 ///
918 /// ```
919 /// use std::collections::BTreeSet;
920 ///
921 /// let mut set = BTreeSet::new();
922 /// set.insert(Vec::<i32>::new());
923 ///
924 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
925 /// set.replace(Vec::with_capacity(10));
926 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
927 /// ```
928 #[stable(feature = "set_recovery", since = "1.9.0")]
929 #[rustc_confusables("swap")]
930 pub fn replace(&mut self, value: T) -> Option<T>
931 where
932 T: Ord,
933 {
934 self.map.replace(value)
935 }
936
937 /// Inserts the given `value` into the set if it is not present, then
938 /// returns a reference to the value in the set.
939 ///
940 /// # Examples
941 ///
942 /// ```
943 /// #![feature(btree_set_entry)]
944 ///
945 /// use std::collections::BTreeSet;
946 ///
947 /// let mut set = BTreeSet::from([1, 2, 3]);
948 /// assert_eq!(set.len(), 3);
949 /// assert_eq!(set.get_or_insert(2), &2);
950 /// assert_eq!(set.get_or_insert(100), &100);
951 /// assert_eq!(set.len(), 4); // 100 was inserted
952 /// ```
953 #[inline]
954 #[unstable(feature = "btree_set_entry", issue = "133549")]
955 pub fn get_or_insert(&mut self, value: T) -> &T
956 where
957 T: Ord,
958 {
959 self.map.entry(value).insert_entry(SetValZST).into_key()
960 }
961
962 /// Inserts a value computed from `f` into the set if the given `value` is
963 /// not present, then returns a reference to the value in the set.
964 ///
965 /// # Examples
966 ///
967 /// ```
968 /// #![feature(btree_set_entry)]
969 ///
970 /// use std::collections::BTreeSet;
971 ///
972 /// let mut set: BTreeSet<String> = ["cat", "dog", "horse"]
973 /// .iter().map(|&pet| pet.to_owned()).collect();
974 ///
975 /// assert_eq!(set.len(), 3);
976 /// for &pet in &["cat", "dog", "fish"] {
977 /// let value = set.get_or_insert_with(pet, str::to_owned);
978 /// assert_eq!(value, pet);
979 /// }
980 /// assert_eq!(set.len(), 4); // a new "fish" was inserted
981 /// ```
982 #[inline]
983 #[unstable(feature = "btree_set_entry", issue = "133549")]
984 pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
985 where
986 T: Borrow<Q> + Ord,
987 Q: Ord,
988 F: FnOnce(&Q) -> T,
989 {
990 self.map.get_or_insert_with(value, f)
991 }
992
993 /// Gets the given value's corresponding entry in the set for in-place manipulation.
994 ///
995 /// # Examples
996 ///
997 /// ```
998 /// #![feature(btree_set_entry)]
999 ///
1000 /// use std::collections::BTreeSet;
1001 /// use std::collections::btree_set::Entry::*;
1002 ///
1003 /// let mut singles = BTreeSet::new();
1004 /// let mut dupes = BTreeSet::new();
1005 ///
1006 /// for ch in "a short treatise on fungi".chars() {
1007 /// if let Vacant(dupe_entry) = dupes.entry(ch) {
1008 /// // We haven't already seen a duplicate, so
1009 /// // check if we've at least seen it once.
1010 /// match singles.entry(ch) {
1011 /// Vacant(single_entry) => {
1012 /// // We found a new character for the first time.
1013 /// single_entry.insert()
1014 /// }
1015 /// Occupied(single_entry) => {
1016 /// // We've already seen this once, "move" it to dupes.
1017 /// single_entry.remove();
1018 /// dupe_entry.insert();
1019 /// }
1020 /// }
1021 /// }
1022 /// }
1023 ///
1024 /// assert!(!singles.contains(&'t') && dupes.contains(&'t'));
1025 /// assert!(singles.contains(&'u') && !dupes.contains(&'u'));
1026 /// assert!(!singles.contains(&'v') && !dupes.contains(&'v'));
1027 /// ```
1028 #[inline]
1029 #[unstable(feature = "btree_set_entry", issue = "133549")]
1030 pub fn entry(&mut self, value: T) -> Entry<'_, T, A>
1031 where
1032 T: Ord,
1033 {
1034 match self.map.entry(value) {
1035 map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
1036 map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
1037 }
1038 }
1039
1040 /// If the set contains an element equal to the value, removes it from the
1041 /// set and drops it. Returns whether such an element was present.
1042 ///
1043 /// The value may be any borrowed form of the set's element type,
1044 /// but the ordering on the borrowed form *must* match the
1045 /// ordering on the element type.
1046 ///
1047 /// # Examples
1048 ///
1049 /// ```
1050 /// use std::collections::BTreeSet;
1051 ///
1052 /// let mut set = BTreeSet::new();
1053 ///
1054 /// set.insert(2);
1055 /// assert_eq!(set.remove(&2), true);
1056 /// assert_eq!(set.remove(&2), false);
1057 /// ```
1058 #[stable(feature = "rust1", since = "1.0.0")]
1059 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
1060 where
1061 T: Borrow<Q> + Ord,
1062 Q: Ord,
1063 {
1064 self.map.remove(value).is_some()
1065 }
1066
1067 /// Removes and returns the element in the set, if any, that is equal to
1068 /// the value.
1069 ///
1070 /// The value may be any borrowed form of the set's element type,
1071 /// but the ordering on the borrowed form *must* match the
1072 /// ordering on the element type.
1073 ///
1074 /// # Examples
1075 ///
1076 /// ```
1077 /// use std::collections::BTreeSet;
1078 ///
1079 /// let mut set = BTreeSet::from([1, 2, 3]);
1080 /// assert_eq!(set.take(&2), Some(2));
1081 /// assert_eq!(set.take(&2), None);
1082 /// ```
1083 #[stable(feature = "set_recovery", since = "1.9.0")]
1084 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
1085 where
1086 T: Borrow<Q> + Ord,
1087 Q: Ord,
1088 {
1089 self.map.remove_entry(value).map(|(k, _)| k)
1090 }
1091
1092 /// Retains only the elements specified by the predicate.
1093 ///
1094 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
1095 /// The elements are visited in ascending order.
1096 ///
1097 /// # Examples
1098 ///
1099 /// ```
1100 /// use std::collections::BTreeSet;
1101 ///
1102 /// let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
1103 /// // Keep only the even numbers.
1104 /// set.retain(|&k| k % 2 == 0);
1105 /// assert!(set.iter().eq([2, 4, 6].iter()));
1106 /// ```
1107 #[stable(feature = "btree_retain", since = "1.53.0")]
1108 pub fn retain<F>(&mut self, mut f: F)
1109 where
1110 T: Ord,
1111 F: FnMut(&T) -> bool,
1112 {
1113 self.extract_if(.., |v| !f(v)).for_each(drop);
1114 }
1115
1116 /// Moves all elements from `other` into `self`, leaving `other` empty.
1117 ///
1118 /// # Examples
1119 ///
1120 /// ```
1121 /// use std::collections::BTreeSet;
1122 ///
1123 /// let mut a = BTreeSet::new();
1124 /// a.insert(1);
1125 /// a.insert(2);
1126 /// a.insert(3);
1127 ///
1128 /// let mut b = BTreeSet::new();
1129 /// b.insert(3);
1130 /// b.insert(4);
1131 /// b.insert(5);
1132 ///
1133 /// a.append(&mut b);
1134 ///
1135 /// assert_eq!(a.len(), 5);
1136 /// assert_eq!(b.len(), 0);
1137 ///
1138 /// assert!(a.contains(&1));
1139 /// assert!(a.contains(&2));
1140 /// assert!(a.contains(&3));
1141 /// assert!(a.contains(&4));
1142 /// assert!(a.contains(&5));
1143 /// ```
1144 #[stable(feature = "btree_append", since = "1.11.0")]
1145 pub fn append(&mut self, other: &mut Self)
1146 where
1147 T: Ord,
1148 A: Clone,
1149 {
1150 self.map.append(&mut other.map);
1151 }
1152
1153 /// Splits the collection into two at the value. Returns a new collection
1154 /// with all elements greater than or equal to the value.
1155 ///
1156 /// # Examples
1157 ///
1158 /// Basic usage:
1159 ///
1160 /// ```
1161 /// use std::collections::BTreeSet;
1162 ///
1163 /// let mut a = BTreeSet::new();
1164 /// a.insert(1);
1165 /// a.insert(2);
1166 /// a.insert(3);
1167 /// a.insert(17);
1168 /// a.insert(41);
1169 ///
1170 /// let b = a.split_off(&3);
1171 ///
1172 /// assert_eq!(a.len(), 2);
1173 /// assert_eq!(b.len(), 3);
1174 ///
1175 /// assert!(a.contains(&1));
1176 /// assert!(a.contains(&2));
1177 ///
1178 /// assert!(b.contains(&3));
1179 /// assert!(b.contains(&17));
1180 /// assert!(b.contains(&41));
1181 /// ```
1182 #[stable(feature = "btree_split_off", since = "1.11.0")]
1183 pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self
1184 where
1185 T: Borrow<Q> + Ord,
1186 A: Clone,
1187 {
1188 BTreeSet { map: self.map.split_off(value) }
1189 }
1190
1191 /// Creates an iterator that visits elements in the specified range in ascending order and
1192 /// uses a closure to determine if an element should be removed.
1193 ///
1194 /// If the closure returns `true`, the element is removed from the set and
1195 /// yielded. If the closure returns `false`, or panics, the element remains
1196 /// in the set and will not be yielded.
1197 ///
1198 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1199 /// or the iteration short-circuits, then the remaining elements will be retained.
1200 /// Use `extract_if().for_each(drop)` if you do not need the returned iterator,
1201 /// or [`retain`] with a negated predicate if you also do not need to restrict the range.
1202 ///
1203 /// [`retain`]: BTreeSet::retain
1204 /// # Examples
1205 ///
1206 /// ```
1207 /// use std::collections::BTreeSet;
1208 ///
1209 /// // Splitting a set into even and odd values, reusing the original set:
1210 /// let mut set: BTreeSet<i32> = (0..8).collect();
1211 /// let evens: BTreeSet<_> = set.extract_if(.., |v| v % 2 == 0).collect();
1212 /// let odds = set;
1213 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
1214 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
1215 ///
1216 /// // Splitting a set into low and high halves, reusing the original set:
1217 /// let mut set: BTreeSet<i32> = (0..8).collect();
1218 /// let low: BTreeSet<_> = set.extract_if(0..4, |_v| true).collect();
1219 /// let high = set;
1220 /// assert_eq!(low.into_iter().collect::<Vec<_>>(), [0, 1, 2, 3]);
1221 /// assert_eq!(high.into_iter().collect::<Vec<_>>(), [4, 5, 6, 7]);
1222 /// ```
1223 #[stable(feature = "btree_extract_if", since = "1.91.0")]
1224 pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, T, R, F, A>
1225 where
1226 T: Ord,
1227 R: RangeBounds<T>,
1228 F: FnMut(&T) -> bool,
1229 {
1230 let (inner, alloc) = self.map.extract_if_inner(range);
1231 ExtractIf { pred, inner, alloc }
1232 }
1233
1234 /// Gets an iterator that visits the elements in the `BTreeSet` in ascending
1235 /// order.
1236 ///
1237 /// # Examples
1238 ///
1239 /// ```
1240 /// use std::collections::BTreeSet;
1241 ///
1242 /// let set = BTreeSet::from([3, 1, 2]);
1243 /// let mut set_iter = set.iter();
1244 /// assert_eq!(set_iter.next(), Some(&1));
1245 /// assert_eq!(set_iter.next(), Some(&2));
1246 /// assert_eq!(set_iter.next(), Some(&3));
1247 /// assert_eq!(set_iter.next(), None);
1248 /// ```
1249 #[stable(feature = "rust1", since = "1.0.0")]
1250 #[cfg_attr(not(test), rustc_diagnostic_item = "btreeset_iter")]
1251 pub fn iter(&self) -> Iter<'_, T> {
1252 Iter { iter: self.map.keys() }
1253 }
1254
1255 /// Returns the number of elements in the set.
1256 ///
1257 /// # Examples
1258 ///
1259 /// ```
1260 /// use std::collections::BTreeSet;
1261 ///
1262 /// let mut v = BTreeSet::new();
1263 /// assert_eq!(v.len(), 0);
1264 /// v.insert(1);
1265 /// assert_eq!(v.len(), 1);
1266 /// ```
1267 #[must_use]
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 #[rustc_const_stable(feature = "const_btree_len", since = "CURRENT_RUSTC_VERSION")]
1270 #[rustc_confusables("length", "size")]
1271 pub const fn len(&self) -> usize {
1272 self.map.len()
1273 }
1274
1275 /// Returns `true` if the set contains no elements.
1276 ///
1277 /// # Examples
1278 ///
1279 /// ```
1280 /// use std::collections::BTreeSet;
1281 ///
1282 /// let mut v = BTreeSet::new();
1283 /// assert!(v.is_empty());
1284 /// v.insert(1);
1285 /// assert!(!v.is_empty());
1286 /// ```
1287 #[must_use]
1288 #[stable(feature = "rust1", since = "1.0.0")]
1289 #[rustc_const_stable(feature = "const_btree_len", since = "CURRENT_RUSTC_VERSION")]
1290 pub const fn is_empty(&self) -> bool {
1291 self.len() == 0
1292 }
1293
1294 /// Returns a [`Cursor`] pointing at the gap before the smallest element
1295 /// greater than the given bound.
1296 ///
1297 /// Passing `Bound::Included(x)` will return a cursor pointing to the
1298 /// gap before the smallest element greater than or equal to `x`.
1299 ///
1300 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1301 /// gap before the smallest element greater than `x`.
1302 ///
1303 /// Passing `Bound::Unbounded` will return a cursor pointing to the
1304 /// gap before the smallest element in the set.
1305 ///
1306 /// # Examples
1307 ///
1308 /// ```
1309 /// #![feature(btree_cursors)]
1310 ///
1311 /// use std::collections::BTreeSet;
1312 /// use std::ops::Bound;
1313 ///
1314 /// let set = BTreeSet::from([1, 2, 3, 4]);
1315 ///
1316 /// let cursor = set.lower_bound(Bound::Included(&2));
1317 /// assert_eq!(cursor.peek_prev(), Some(&1));
1318 /// assert_eq!(cursor.peek_next(), Some(&2));
1319 ///
1320 /// let cursor = set.lower_bound(Bound::Excluded(&2));
1321 /// assert_eq!(cursor.peek_prev(), Some(&2));
1322 /// assert_eq!(cursor.peek_next(), Some(&3));
1323 ///
1324 /// let cursor = set.lower_bound(Bound::Unbounded);
1325 /// assert_eq!(cursor.peek_prev(), None);
1326 /// assert_eq!(cursor.peek_next(), Some(&1));
1327 /// ```
1328 #[unstable(feature = "btree_cursors", issue = "107540")]
1329 pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
1330 where
1331 T: Borrow<Q> + Ord,
1332 Q: Ord,
1333 {
1334 Cursor { inner: self.map.lower_bound(bound) }
1335 }
1336
1337 /// Returns a [`CursorMut`] pointing at the gap before the smallest element
1338 /// greater than the given bound.
1339 ///
1340 /// Passing `Bound::Included(x)` will return a cursor pointing to the
1341 /// gap before the smallest element greater than or equal to `x`.
1342 ///
1343 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1344 /// gap before the smallest element greater than `x`.
1345 ///
1346 /// Passing `Bound::Unbounded` will return a cursor pointing to the
1347 /// gap before the smallest element in the set.
1348 ///
1349 /// # Examples
1350 ///
1351 /// ```
1352 /// #![feature(btree_cursors)]
1353 ///
1354 /// use std::collections::BTreeSet;
1355 /// use std::ops::Bound;
1356 ///
1357 /// let mut set = BTreeSet::from([1, 2, 3, 4]);
1358 ///
1359 /// let mut cursor = set.lower_bound_mut(Bound::Included(&2));
1360 /// assert_eq!(cursor.peek_prev(), Some(&1));
1361 /// assert_eq!(cursor.peek_next(), Some(&2));
1362 ///
1363 /// let mut cursor = set.lower_bound_mut(Bound::Excluded(&2));
1364 /// assert_eq!(cursor.peek_prev(), Some(&2));
1365 /// assert_eq!(cursor.peek_next(), Some(&3));
1366 ///
1367 /// let mut cursor = set.lower_bound_mut(Bound::Unbounded);
1368 /// assert_eq!(cursor.peek_prev(), None);
1369 /// assert_eq!(cursor.peek_next(), Some(&1));
1370 /// ```
1371 #[unstable(feature = "btree_cursors", issue = "107540")]
1372 pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1373 where
1374 T: Borrow<Q> + Ord,
1375 Q: Ord,
1376 {
1377 CursorMut { inner: self.map.lower_bound_mut(bound) }
1378 }
1379
1380 /// Returns a [`Cursor`] pointing at the gap after the greatest element
1381 /// smaller than the given bound.
1382 ///
1383 /// Passing `Bound::Included(x)` will return a cursor pointing to the
1384 /// gap after the greatest element smaller than or equal to `x`.
1385 ///
1386 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1387 /// gap after the greatest element smaller than `x`.
1388 ///
1389 /// Passing `Bound::Unbounded` will return a cursor pointing to the
1390 /// gap after the greatest element in the set.
1391 ///
1392 /// # Examples
1393 ///
1394 /// ```
1395 /// #![feature(btree_cursors)]
1396 ///
1397 /// use std::collections::BTreeSet;
1398 /// use std::ops::Bound;
1399 ///
1400 /// let set = BTreeSet::from([1, 2, 3, 4]);
1401 ///
1402 /// let cursor = set.upper_bound(Bound::Included(&3));
1403 /// assert_eq!(cursor.peek_prev(), Some(&3));
1404 /// assert_eq!(cursor.peek_next(), Some(&4));
1405 ///
1406 /// let cursor = set.upper_bound(Bound::Excluded(&3));
1407 /// assert_eq!(cursor.peek_prev(), Some(&2));
1408 /// assert_eq!(cursor.peek_next(), Some(&3));
1409 ///
1410 /// let cursor = set.upper_bound(Bound::Unbounded);
1411 /// assert_eq!(cursor.peek_prev(), Some(&4));
1412 /// assert_eq!(cursor.peek_next(), None);
1413 /// ```
1414 #[unstable(feature = "btree_cursors", issue = "107540")]
1415 pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
1416 where
1417 T: Borrow<Q> + Ord,
1418 Q: Ord,
1419 {
1420 Cursor { inner: self.map.upper_bound(bound) }
1421 }
1422
1423 /// Returns a [`CursorMut`] pointing at the gap after the greatest element
1424 /// smaller than the given bound.
1425 ///
1426 /// Passing `Bound::Included(x)` will return a cursor pointing to the
1427 /// gap after the greatest element smaller than or equal to `x`.
1428 ///
1429 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1430 /// gap after the greatest element smaller than `x`.
1431 ///
1432 /// Passing `Bound::Unbounded` will return a cursor pointing to the
1433 /// gap after the greatest element in the set.
1434 ///
1435 /// # Examples
1436 ///
1437 /// ```
1438 /// #![feature(btree_cursors)]
1439 ///
1440 /// use std::collections::BTreeSet;
1441 /// use std::ops::Bound;
1442 ///
1443 /// let mut set = BTreeSet::from([1, 2, 3, 4]);
1444 ///
1445 /// let mut cursor = set.upper_bound_mut(Bound::Included(&3));
1446 /// assert_eq!(cursor.peek_prev(), Some(&3));
1447 /// assert_eq!(cursor.peek_next(), Some(&4));
1448 ///
1449 /// let mut cursor = set.upper_bound_mut(Bound::Excluded(&3));
1450 /// assert_eq!(cursor.peek_prev(), Some(&2));
1451 /// assert_eq!(cursor.peek_next(), Some(&3));
1452 ///
1453 /// let mut cursor = set.upper_bound_mut(Bound::Unbounded);
1454 /// assert_eq!(cursor.peek_prev(), Some(&4));
1455 /// assert_eq!(cursor.peek_next(), None);
1456 /// ```
1457 #[unstable(feature = "btree_cursors", issue = "107540")]
1458 pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1459 where
1460 T: Borrow<Q> + Ord,
1461 Q: Ord,
1462 {
1463 CursorMut { inner: self.map.upper_bound_mut(bound) }
1464 }
1465}
1466
1467#[stable(feature = "rust1", since = "1.0.0")]
1468impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1469 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1470 let mut inputs: Vec<_> = iter.into_iter().collect();
1471
1472 if inputs.is_empty() {
1473 return BTreeSet::new();
1474 }
1475
1476 // use stable sort to preserve the insertion order.
1477 inputs.sort();
1478 BTreeSet::from_sorted_iter(inputs.into_iter(), Global)
1479 }
1480}
1481
1482impl<T: Ord, A: AllocatorClone> BTreeSet<T, A> {
1483 fn from_sorted_iter<I: Iterator<Item = T>>(iter: I, alloc: A) -> BTreeSet<T, A> {
1484 let iter = iter.map(|k| (k, SetValZST));
1485 let map = BTreeMap::bulk_build_from_sorted_iter(iter, alloc);
1486 BTreeSet { map }
1487 }
1488}
1489
1490#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1491impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
1492 /// Converts a `[T; N]` into a `BTreeSet<T>`.
1493 ///
1494 /// If the array contains any equal values,
1495 /// all but one will be dropped.
1496 ///
1497 /// # Examples
1498 ///
1499 /// ```
1500 /// use std::collections::BTreeSet;
1501 ///
1502 /// let set1 = BTreeSet::from([1, 2, 3, 4]);
1503 /// let set2: BTreeSet<_> = [1, 2, 3, 4].into();
1504 /// assert_eq!(set1, set2);
1505 /// ```
1506 fn from(mut arr: [T; N]) -> Self {
1507 if N == 0 {
1508 return BTreeSet::new();
1509 }
1510
1511 // use stable sort to preserve the insertion order.
1512 arr.sort();
1513 BTreeSet::from_sorted_iter(IntoIterator::into_iter(arr), Global)
1514 }
1515}
1516
1517#[stable(feature = "rust1", since = "1.0.0")]
1518impl<T, A: AllocatorClone> IntoIterator for BTreeSet<T, A> {
1519 type Item = T;
1520 type IntoIter = IntoIter<T, A>;
1521
1522 /// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order.
1523 ///
1524 /// # Examples
1525 ///
1526 /// ```
1527 /// use std::collections::BTreeSet;
1528 ///
1529 /// let set = BTreeSet::from([1, 2, 3, 4]);
1530 ///
1531 /// let v: Vec<_> = set.into_iter().collect();
1532 /// assert_eq!(v, [1, 2, 3, 4]);
1533 /// ```
1534 fn into_iter(self) -> IntoIter<T, A> {
1535 IntoIter { iter: self.map.into_iter() }
1536 }
1537}
1538
1539#[stable(feature = "rust1", since = "1.0.0")]
1540impl<'a, T, A: AllocatorClone> IntoIterator for &'a BTreeSet<T, A> {
1541 type Item = &'a T;
1542 type IntoIter = Iter<'a, T>;
1543
1544 fn into_iter(self) -> Iter<'a, T> {
1545 self.iter()
1546 }
1547}
1548
1549/// This `struct` is created by the [`extract_if`] method on [`BTreeSet`].
1550///
1551/// [`extract_if`]: BTreeSet::extract_if
1552#[stable(feature = "btree_extract_if", since = "1.91.0")]
1553#[must_use = "iterators are lazy and do nothing unless consumed; \
1554 use `retain` or `extract_if().for_each(drop)` to remove and discard elements"]
1555pub struct ExtractIf<
1556 'a,
1557 T,
1558 R,
1559 F,
1560 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
1561> {
1562 pred: F,
1563 inner: super::map::ExtractIfInner<'a, T, SetValZST, R>,
1564 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1565 alloc: A,
1566}
1567
1568#[stable(feature = "btree_extract_if", since = "1.91.0")]
1569impl<T, R, F, A> fmt::Debug for ExtractIf<'_, T, R, F, A>
1570where
1571 T: fmt::Debug,
1572 A: AllocatorClone,
1573{
1574 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1575 f.debug_struct("ExtractIf")
1576 .field("peek", &self.inner.peek().map(|(k, _)| k))
1577 .finish_non_exhaustive()
1578 }
1579}
1580
1581#[stable(feature = "btree_extract_if", since = "1.91.0")]
1582impl<T, R, F, A: AllocatorClone> Iterator for ExtractIf<'_, T, R, F, A>
1583where
1584 T: PartialOrd,
1585 R: RangeBounds<T>,
1586 F: FnMut(&T) -> bool,
1587{
1588 type Item = T;
1589
1590 fn next(&mut self) -> Option<T> {
1591 let pred = &mut self.pred;
1592 let mut mapped_pred = |k: &T, _v: &mut SetValZST| pred(k);
1593 self.inner.next(&mut mapped_pred, self.alloc.clone()).map(|(k, _)| k)
1594 }
1595
1596 fn size_hint(&self) -> (usize, Option<usize>) {
1597 self.inner.size_hint()
1598 }
1599}
1600
1601#[stable(feature = "btree_extract_if", since = "1.91.0")]
1602impl<T, R, F, A: AllocatorClone> FusedIterator for ExtractIf<'_, T, R, F, A>
1603where
1604 T: PartialOrd,
1605 R: RangeBounds<T>,
1606 F: FnMut(&T) -> bool,
1607{
1608}
1609
1610#[stable(feature = "rust1", since = "1.0.0")]
1611impl<T: Ord, A: AllocatorClone> Extend<T> for BTreeSet<T, A> {
1612 #[inline]
1613 fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1614 iter.into_iter().for_each(move |elem| {
1615 self.insert(elem);
1616 });
1617 }
1618
1619 #[inline]
1620 fn extend_one(&mut self, elem: T) {
1621 self.insert(elem);
1622 }
1623}
1624
1625#[stable(feature = "extend_ref", since = "1.2.0")]
1626impl<'a, T: 'a + Ord + Copy, A: AllocatorClone> Extend<&'a T> for BTreeSet<T, A> {
1627 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1628 self.extend(iter.into_iter().cloned());
1629 }
1630
1631 #[inline]
1632 fn extend_one(&mut self, &elem: &'a T) {
1633 self.insert(elem);
1634 }
1635}
1636
1637#[stable(feature = "rust1", since = "1.0.0")]
1638impl<T> Default for BTreeSet<T> {
1639 /// Creates an empty `BTreeSet`.
1640 fn default() -> BTreeSet<T> {
1641 BTreeSet::new()
1642 }
1643}
1644
1645#[stable(feature = "rust1", since = "1.0.0")]
1646impl<T: Ord + Clone, A: AllocatorClone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1647 type Output = BTreeSet<T, A>;
1648
1649 /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1650 ///
1651 /// # Examples
1652 ///
1653 /// ```
1654 /// use std::collections::BTreeSet;
1655 ///
1656 /// let a = BTreeSet::from([1, 2, 3]);
1657 /// let b = BTreeSet::from([3, 4, 5]);
1658 ///
1659 /// let result = &a - &b;
1660 /// assert_eq!(result, BTreeSet::from([1, 2]));
1661 /// ```
1662 fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1663 BTreeSet::from_sorted_iter(
1664 self.difference(rhs).cloned(),
1665 ManuallyDrop::into_inner(self.map.alloc.clone()),
1666 )
1667 }
1668}
1669
1670#[stable(feature = "rust1", since = "1.0.0")]
1671impl<T: Ord + Clone, A: AllocatorClone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1672 type Output = BTreeSet<T, A>;
1673
1674 /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1675 ///
1676 /// # Examples
1677 ///
1678 /// ```
1679 /// use std::collections::BTreeSet;
1680 ///
1681 /// let a = BTreeSet::from([1, 2, 3]);
1682 /// let b = BTreeSet::from([2, 3, 4]);
1683 ///
1684 /// let result = &a ^ &b;
1685 /// assert_eq!(result, BTreeSet::from([1, 4]));
1686 /// ```
1687 fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1688 BTreeSet::from_sorted_iter(
1689 self.symmetric_difference(rhs).cloned(),
1690 ManuallyDrop::into_inner(self.map.alloc.clone()),
1691 )
1692 }
1693}
1694
1695#[stable(feature = "rust1", since = "1.0.0")]
1696impl<T: Ord + Clone, A: AllocatorClone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1697 type Output = BTreeSet<T, A>;
1698
1699 /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1700 ///
1701 /// # Examples
1702 ///
1703 /// ```
1704 /// use std::collections::BTreeSet;
1705 ///
1706 /// let a = BTreeSet::from([1, 2, 3]);
1707 /// let b = BTreeSet::from([2, 3, 4]);
1708 ///
1709 /// let result = &a & &b;
1710 /// assert_eq!(result, BTreeSet::from([2, 3]));
1711 /// ```
1712 fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1713 BTreeSet::from_sorted_iter(
1714 self.intersection(rhs).cloned(),
1715 ManuallyDrop::into_inner(self.map.alloc.clone()),
1716 )
1717 }
1718}
1719
1720#[stable(feature = "rust1", since = "1.0.0")]
1721impl<T: Ord + Clone, A: AllocatorClone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1722 type Output = BTreeSet<T, A>;
1723
1724 /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1725 ///
1726 /// # Examples
1727 ///
1728 /// ```
1729 /// use std::collections::BTreeSet;
1730 ///
1731 /// let a = BTreeSet::from([1, 2, 3]);
1732 /// let b = BTreeSet::from([3, 4, 5]);
1733 ///
1734 /// let result = &a | &b;
1735 /// assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5]));
1736 /// ```
1737 fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1738 BTreeSet::from_sorted_iter(
1739 self.union(rhs).cloned(),
1740 ManuallyDrop::into_inner(self.map.alloc.clone()),
1741 )
1742 }
1743}
1744
1745#[stable(feature = "rust1", since = "1.0.0")]
1746impl<T: Debug, A: AllocatorClone> Debug for BTreeSet<T, A> {
1747 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1748 f.debug_set().entries(self.iter()).finish()
1749 }
1750}
1751
1752#[stable(feature = "rust1", since = "1.0.0")]
1753impl<T> Clone for Iter<'_, T> {
1754 fn clone(&self) -> Self {
1755 Iter { iter: self.iter.clone() }
1756 }
1757}
1758
1759#[stable(feature = "rust1", since = "1.0.0")]
1760impl<'a, T> Iterator for Iter<'a, T> {
1761 type Item = &'a T;
1762
1763 fn next(&mut self) -> Option<&'a T> {
1764 self.iter.next()
1765 }
1766
1767 fn size_hint(&self) -> (usize, Option<usize>) {
1768 self.iter.size_hint()
1769 }
1770
1771 fn last(mut self) -> Option<&'a T> {
1772 self.next_back()
1773 }
1774
1775 fn min(mut self) -> Option<&'a T>
1776 where
1777 &'a T: Ord,
1778 {
1779 self.next()
1780 }
1781
1782 fn max(mut self) -> Option<&'a T>
1783 where
1784 &'a T: Ord,
1785 {
1786 self.next_back()
1787 }
1788}
1789
1790#[stable(feature = "rust1", since = "1.0.0")]
1791impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1792 fn next_back(&mut self) -> Option<&'a T> {
1793 self.iter.next_back()
1794 }
1795}
1796
1797#[stable(feature = "rust1", since = "1.0.0")]
1798impl<T> ExactSizeIterator for Iter<'_, T> {
1799 fn len(&self) -> usize {
1800 self.iter.len()
1801 }
1802}
1803
1804#[unstable(feature = "trusted_len", issue = "37572")]
1805unsafe impl<T> TrustedLen for Iter<'_, T> {}
1806
1807#[stable(feature = "fused", since = "1.26.0")]
1808impl<T> FusedIterator for Iter<'_, T> {}
1809
1810#[stable(feature = "rust1", since = "1.0.0")]
1811impl<T, A: AllocatorClone> Iterator for IntoIter<T, A> {
1812 type Item = T;
1813
1814 fn next(&mut self) -> Option<T> {
1815 self.iter.next().map(|(k, _)| k)
1816 }
1817
1818 fn size_hint(&self) -> (usize, Option<usize>) {
1819 self.iter.size_hint()
1820 }
1821}
1822
1823#[stable(feature = "default_iters", since = "1.70.0")]
1824impl<T> Default for Iter<'_, T> {
1825 /// Creates an empty `btree_set::Iter`.
1826 ///
1827 /// ```
1828 /// # use std::collections::btree_set;
1829 /// let iter: btree_set::Iter<'_, u8> = Default::default();
1830 /// assert_eq!(iter.len(), 0);
1831 /// ```
1832 fn default() -> Self {
1833 Iter { iter: Default::default() }
1834 }
1835}
1836
1837#[stable(feature = "rust1", since = "1.0.0")]
1838impl<T, A: AllocatorClone> DoubleEndedIterator for IntoIter<T, A> {
1839 fn next_back(&mut self) -> Option<T> {
1840 self.iter.next_back().map(|(k, _)| k)
1841 }
1842}
1843
1844#[stable(feature = "rust1", since = "1.0.0")]
1845impl<T, A: AllocatorClone> ExactSizeIterator for IntoIter<T, A> {
1846 fn len(&self) -> usize {
1847 self.iter.len()
1848 }
1849}
1850
1851#[unstable(feature = "trusted_len", issue = "37572")]
1852unsafe impl<T, A: AllocatorClone> TrustedLen for IntoIter<T, A> {}
1853
1854#[stable(feature = "fused", since = "1.26.0")]
1855impl<T, A: AllocatorClone> FusedIterator for IntoIter<T, A> {}
1856
1857#[stable(feature = "default_iters", since = "1.70.0")]
1858impl<T, A> Default for IntoIter<T, A>
1859where
1860 A: AllocatorClone + Default,
1861{
1862 /// Creates an empty `btree_set::IntoIter`.
1863 ///
1864 /// ```
1865 /// # use std::collections::btree_set;
1866 /// let iter: btree_set::IntoIter<u8> = Default::default();
1867 /// assert_eq!(iter.len(), 0);
1868 /// ```
1869 fn default() -> Self {
1870 IntoIter { iter: Default::default() }
1871 }
1872}
1873
1874#[stable(feature = "btree_range", since = "1.17.0")]
1875impl<T> Clone for Range<'_, T> {
1876 fn clone(&self) -> Self {
1877 Range { iter: self.iter.clone() }
1878 }
1879}
1880
1881#[stable(feature = "btree_range", since = "1.17.0")]
1882impl<'a, T> Iterator for Range<'a, T> {
1883 type Item = &'a T;
1884
1885 fn next(&mut self) -> Option<&'a T> {
1886 self.iter.next().map(|(k, _)| k)
1887 }
1888
1889 fn last(mut self) -> Option<&'a T> {
1890 self.next_back()
1891 }
1892
1893 fn min(mut self) -> Option<&'a T>
1894 where
1895 &'a T: Ord,
1896 {
1897 self.next()
1898 }
1899
1900 fn max(mut self) -> Option<&'a T>
1901 where
1902 &'a T: Ord,
1903 {
1904 self.next_back()
1905 }
1906}
1907
1908#[stable(feature = "btree_range", since = "1.17.0")]
1909impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1910 fn next_back(&mut self) -> Option<&'a T> {
1911 self.iter.next_back().map(|(k, _)| k)
1912 }
1913}
1914
1915#[stable(feature = "fused", since = "1.26.0")]
1916impl<T> FusedIterator for Range<'_, T> {}
1917
1918#[stable(feature = "default_iters", since = "1.70.0")]
1919impl<T> Default for Range<'_, T> {
1920 /// Creates an empty `btree_set::Range`.
1921 ///
1922 /// ```
1923 /// # use std::collections::btree_set;
1924 /// let iter: btree_set::Range<'_, u8> = Default::default();
1925 /// assert_eq!(iter.count(), 0);
1926 /// ```
1927 fn default() -> Self {
1928 Range { iter: Default::default() }
1929 }
1930}
1931
1932#[stable(feature = "rust1", since = "1.0.0")]
1933impl<T, A: AllocatorClone> Clone for Difference<'_, T, A> {
1934 fn clone(&self) -> Self {
1935 Difference {
1936 inner: match &self.inner {
1937 DifferenceInner::Stitch { self_iter, other_iter } => DifferenceInner::Stitch {
1938 self_iter: self_iter.clone(),
1939 other_iter: other_iter.clone(),
1940 },
1941 DifferenceInner::Search { self_iter, other_set } => {
1942 DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1943 }
1944 DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
1945 },
1946 }
1947 }
1948}
1949#[stable(feature = "rust1", since = "1.0.0")]
1950impl<'a, T: Ord, A: AllocatorClone> Iterator for Difference<'a, T, A> {
1951 type Item = &'a T;
1952
1953 fn next(&mut self) -> Option<&'a T> {
1954 match &mut self.inner {
1955 DifferenceInner::Stitch { self_iter, other_iter } => {
1956 let mut self_next = self_iter.next()?;
1957 loop {
1958 match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1959 Less => return Some(self_next),
1960 Equal => {
1961 self_next = self_iter.next()?;
1962 other_iter.next();
1963 }
1964 Greater => {
1965 other_iter.next();
1966 }
1967 }
1968 }
1969 }
1970 DifferenceInner::Search { self_iter, other_set } => loop {
1971 let self_next = self_iter.next()?;
1972 if !other_set.contains(self_next) {
1973 return Some(self_next);
1974 }
1975 },
1976 DifferenceInner::Iterate(iter) => iter.next(),
1977 }
1978 }
1979
1980 fn size_hint(&self) -> (usize, Option<usize>) {
1981 let (self_len, other_len) = match &self.inner {
1982 DifferenceInner::Stitch { self_iter, other_iter } => {
1983 (self_iter.len(), other_iter.len())
1984 }
1985 DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1986 DifferenceInner::Iterate(iter) => (iter.len(), 0),
1987 };
1988 (self_len.saturating_sub(other_len), Some(self_len))
1989 }
1990
1991 fn min(mut self) -> Option<&'a T> {
1992 self.next()
1993 }
1994}
1995
1996#[stable(feature = "fused", since = "1.26.0")]
1997impl<T: Ord, A: AllocatorClone> FusedIterator for Difference<'_, T, A> {}
1998
1999#[stable(feature = "rust1", since = "1.0.0")]
2000impl<T> Clone for SymmetricDifference<'_, T> {
2001 fn clone(&self) -> Self {
2002 SymmetricDifference(self.0.clone())
2003 }
2004}
2005#[stable(feature = "rust1", since = "1.0.0")]
2006impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
2007 type Item = &'a T;
2008
2009 fn next(&mut self) -> Option<&'a T> {
2010 loop {
2011 let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
2012 if a_next.and(b_next).is_none() {
2013 return a_next.or(b_next);
2014 }
2015 }
2016 }
2017
2018 fn size_hint(&self) -> (usize, Option<usize>) {
2019 let (a_len, b_len) = self.0.lens();
2020 // No checked_add, because even if a and b refer to the same set,
2021 // and T is a zero-sized type, the storage overhead of sets limits
2022 // the number of elements to less than half the range of usize.
2023 (0, Some(a_len + b_len))
2024 }
2025
2026 fn min(mut self) -> Option<&'a T> {
2027 self.next()
2028 }
2029}
2030
2031#[stable(feature = "fused", since = "1.26.0")]
2032impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
2033
2034#[stable(feature = "rust1", since = "1.0.0")]
2035impl<T, A: AllocatorClone> Clone for Intersection<'_, T, A> {
2036 fn clone(&self) -> Self {
2037 Intersection {
2038 inner: match &self.inner {
2039 IntersectionInner::Stitch { a, b } => {
2040 IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
2041 }
2042 IntersectionInner::Search { small_iter, large_set } => {
2043 IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
2044 }
2045 IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
2046 },
2047 }
2048 }
2049}
2050#[stable(feature = "rust1", since = "1.0.0")]
2051impl<'a, T: Ord, A: AllocatorClone> Iterator for Intersection<'a, T, A> {
2052 type Item = &'a T;
2053
2054 fn next(&mut self) -> Option<&'a T> {
2055 match &mut self.inner {
2056 IntersectionInner::Stitch { a, b } => {
2057 let mut a_next = a.next()?;
2058 let mut b_next = b.next()?;
2059 loop {
2060 match a_next.cmp(b_next) {
2061 Less => a_next = a.next()?,
2062 Greater => b_next = b.next()?,
2063 Equal => return Some(a_next),
2064 }
2065 }
2066 }
2067 IntersectionInner::Search { small_iter, large_set } => loop {
2068 let small_next = small_iter.next()?;
2069 if large_set.contains(small_next) {
2070 return Some(small_next);
2071 }
2072 },
2073 IntersectionInner::Answer(answer) => answer.take(),
2074 }
2075 }
2076
2077 fn size_hint(&self) -> (usize, Option<usize>) {
2078 match &self.inner {
2079 IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
2080 IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
2081 IntersectionInner::Answer(None) => (0, Some(0)),
2082 IntersectionInner::Answer(Some(_)) => (1, Some(1)),
2083 }
2084 }
2085
2086 fn min(mut self) -> Option<&'a T> {
2087 self.next()
2088 }
2089}
2090
2091#[stable(feature = "fused", since = "1.26.0")]
2092impl<T: Ord, A: AllocatorClone> FusedIterator for Intersection<'_, T, A> {}
2093
2094#[stable(feature = "rust1", since = "1.0.0")]
2095impl<T> Clone for Union<'_, T> {
2096 fn clone(&self) -> Self {
2097 Union(self.0.clone())
2098 }
2099}
2100#[stable(feature = "rust1", since = "1.0.0")]
2101impl<'a, T: Ord> Iterator for Union<'a, T> {
2102 type Item = &'a T;
2103
2104 fn next(&mut self) -> Option<&'a T> {
2105 let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
2106 a_next.or(b_next)
2107 }
2108
2109 fn size_hint(&self) -> (usize, Option<usize>) {
2110 let (a_len, b_len) = self.0.lens();
2111 // No checked_add - see SymmetricDifference::size_hint.
2112 (max(a_len, b_len), Some(a_len + b_len))
2113 }
2114
2115 fn min(mut self) -> Option<&'a T> {
2116 self.next()
2117 }
2118}
2119
2120#[stable(feature = "fused", since = "1.26.0")]
2121impl<T: Ord> FusedIterator for Union<'_, T> {}
2122
2123/// A cursor over a `BTreeSet`.
2124///
2125/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
2126///
2127/// Cursors always point to a gap between two elements in the set, and can
2128/// operate on the two immediately adjacent elements.
2129///
2130/// A `Cursor` is created with the [`BTreeSet::lower_bound`] and [`BTreeSet::upper_bound`] methods.
2131#[derive(Clone)]
2132#[unstable(feature = "btree_cursors", issue = "107540")]
2133pub struct Cursor<'a, K: 'a> {
2134 inner: super::map::Cursor<'a, K, SetValZST>,
2135}
2136
2137#[unstable(feature = "btree_cursors", issue = "107540")]
2138impl<K: Debug> Debug for Cursor<'_, K> {
2139 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2140 f.write_str("Cursor")
2141 }
2142}
2143
2144/// A cursor over a `BTreeSet` with editing operations.
2145///
2146/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2147/// safely mutate the set during iteration. This is because the lifetime of its yielded
2148/// references is tied to its own lifetime, instead of just the underlying map. This means
2149/// cursors cannot yield multiple elements at once.
2150///
2151/// Cursors always point to a gap between two elements in the set, and can
2152/// operate on the two immediately adjacent elements.
2153///
2154/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and [`BTreeSet::upper_bound_mut`]
2155/// methods.
2156#[unstable(feature = "btree_cursors", issue = "107540")]
2157pub struct CursorMut<
2158 'a,
2159 K: 'a,
2160 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A = Global,
2161> {
2162 inner: super::map::CursorMut<'a, K, SetValZST, A>,
2163}
2164
2165#[unstable(feature = "btree_cursors", issue = "107540")]
2166impl<K: Debug, A> Debug for CursorMut<'_, K, A> {
2167 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2168 f.write_str("CursorMut")
2169 }
2170}
2171
2172/// A cursor over a `BTreeSet` with editing operations, and which allows
2173/// mutating elements.
2174///
2175/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2176/// safely mutate the set during iteration. This is because the lifetime of its yielded
2177/// references is tied to its own lifetime, instead of just the underlying set. This means
2178/// cursors cannot yield multiple elements at once.
2179///
2180/// Cursors always point to a gap between two elements in the set, and can
2181/// operate on the two immediately adjacent elements.
2182///
2183/// A `CursorMutKey` is created from a [`CursorMut`] with the
2184/// [`CursorMut::with_mutable_key`] method.
2185///
2186/// # Safety
2187///
2188/// Since this cursor allows mutating elements, you must ensure that the
2189/// `BTreeSet` invariants are maintained. Specifically:
2190///
2191/// * The newly inserted element must be unique in the tree.
2192/// * All elements in the tree must remain in sorted order.
2193#[unstable(feature = "btree_cursors", issue = "107540")]
2194pub struct CursorMutKey<
2195 'a,
2196 K: 'a,
2197 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A = Global,
2198> {
2199 inner: super::map::CursorMutKey<'a, K, SetValZST, A>,
2200}
2201
2202#[unstable(feature = "btree_cursors", issue = "107540")]
2203impl<K: Debug, A> Debug for CursorMutKey<'_, K, A> {
2204 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2205 f.write_str("CursorMutKey")
2206 }
2207}
2208
2209impl<'a, K> Cursor<'a, K> {
2210 /// Advances the cursor to the next gap, returning the element that it
2211 /// moved over.
2212 ///
2213 /// If the cursor is already at the end of the set then `None` is returned
2214 /// and the cursor is not moved.
2215 #[unstable(feature = "btree_cursors", issue = "107540")]
2216 pub fn next(&mut self) -> Option<&'a K> {
2217 self.inner.next().map(|(k, _)| k)
2218 }
2219
2220 /// Advances the cursor to the previous gap, returning the element that it
2221 /// moved over.
2222 ///
2223 /// If the cursor is already at the start of the set then `None` is returned
2224 /// and the cursor is not moved.
2225 #[unstable(feature = "btree_cursors", issue = "107540")]
2226 pub fn prev(&mut self) -> Option<&'a K> {
2227 self.inner.prev().map(|(k, _)| k)
2228 }
2229
2230 /// Returns a reference to next element without moving the cursor.
2231 ///
2232 /// If the cursor is at the end of the set then `None` is returned
2233 #[unstable(feature = "btree_cursors", issue = "107540")]
2234 pub fn peek_next(&self) -> Option<&'a K> {
2235 self.inner.peek_next().map(|(k, _)| k)
2236 }
2237
2238 /// Returns a reference to the previous element without moving the cursor.
2239 ///
2240 /// If the cursor is at the start of the set then `None` is returned.
2241 #[unstable(feature = "btree_cursors", issue = "107540")]
2242 pub fn peek_prev(&self) -> Option<&'a K> {
2243 self.inner.peek_prev().map(|(k, _)| k)
2244 }
2245}
2246
2247impl<'a, T, A> CursorMut<'a, T, A> {
2248 /// Advances the cursor to the next gap, returning the element that it
2249 /// moved over.
2250 ///
2251 /// If the cursor is already at the end of the set then `None` is returned
2252 /// and the cursor is not moved.
2253 #[unstable(feature = "btree_cursors", issue = "107540")]
2254 pub fn next(&mut self) -> Option<&T> {
2255 self.inner.next().map(|(k, _)| k)
2256 }
2257
2258 /// Advances the cursor to the previous gap, returning the element that it
2259 /// moved over.
2260 ///
2261 /// If the cursor is already at the start of the set then `None` is returned
2262 /// and the cursor is not moved.
2263 #[unstable(feature = "btree_cursors", issue = "107540")]
2264 pub fn prev(&mut self) -> Option<&T> {
2265 self.inner.prev().map(|(k, _)| k)
2266 }
2267
2268 /// Returns a reference to the next element without moving the cursor.
2269 ///
2270 /// If the cursor is at the end of the set then `None` is returned.
2271 #[unstable(feature = "btree_cursors", issue = "107540")]
2272 pub fn peek_next(&mut self) -> Option<&T> {
2273 self.inner.peek_next().map(|(k, _)| k)
2274 }
2275
2276 /// Returns a reference to the previous element without moving the cursor.
2277 ///
2278 /// If the cursor is at the start of the set then `None` is returned.
2279 #[unstable(feature = "btree_cursors", issue = "107540")]
2280 pub fn peek_prev(&mut self) -> Option<&T> {
2281 self.inner.peek_prev().map(|(k, _)| k)
2282 }
2283
2284 /// Returns a read-only cursor pointing to the same location as the
2285 /// `CursorMut`.
2286 ///
2287 /// The lifetime of the returned `Cursor` is bound to that of the
2288 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
2289 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
2290 #[unstable(feature = "btree_cursors", issue = "107540")]
2291 pub fn as_cursor(&self) -> Cursor<'_, T> {
2292 Cursor { inner: self.inner.as_cursor() }
2293 }
2294
2295 /// Converts the cursor into a [`CursorMutKey`], which allows mutating
2296 /// elements in the tree.
2297 ///
2298 /// # Safety
2299 ///
2300 /// Since this cursor allows mutating elements, you must ensure that the
2301 /// `BTreeSet` invariants are maintained. Specifically:
2302 ///
2303 /// * The newly inserted element must be unique in the tree.
2304 /// * All elements in the tree must remain in sorted order.
2305 #[unstable(feature = "btree_cursors", issue = "107540")]
2306 pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, T, A> {
2307 // ignore-tidy-undocumented-unsafe
2308 CursorMutKey { inner: unsafe { self.inner.with_mutable_key() } }
2309 }
2310}
2311
2312impl<'a, T, A> CursorMutKey<'a, T, A> {
2313 /// Advances the cursor to the next gap, returning the element that it
2314 /// moved over.
2315 ///
2316 /// If the cursor is already at the end of the set then `None` is returned
2317 /// and the cursor is not moved.
2318 #[unstable(feature = "btree_cursors", issue = "107540")]
2319 pub fn next(&mut self) -> Option<&mut T> {
2320 self.inner.next().map(|(k, _)| k)
2321 }
2322
2323 /// Advances the cursor to the previous gap, returning the element that it
2324 /// moved over.
2325 ///
2326 /// If the cursor is already at the start of the set then `None` is returned
2327 /// and the cursor is not moved.
2328 #[unstable(feature = "btree_cursors", issue = "107540")]
2329 pub fn prev(&mut self) -> Option<&mut T> {
2330 self.inner.prev().map(|(k, _)| k)
2331 }
2332
2333 /// Returns a reference to the next element without moving the cursor.
2334 ///
2335 /// If the cursor is at the end of the set then `None` is returned
2336 #[unstable(feature = "btree_cursors", issue = "107540")]
2337 pub fn peek_next(&mut self) -> Option<&mut T> {
2338 self.inner.peek_next().map(|(k, _)| k)
2339 }
2340
2341 /// Returns a reference to the previous element without moving the cursor.
2342 ///
2343 /// If the cursor is at the start of the set then `None` is returned.
2344 #[unstable(feature = "btree_cursors", issue = "107540")]
2345 pub fn peek_prev(&mut self) -> Option<&mut T> {
2346 self.inner.peek_prev().map(|(k, _)| k)
2347 }
2348
2349 /// Returns a read-only cursor pointing to the same location as the
2350 /// `CursorMutKey`.
2351 ///
2352 /// The lifetime of the returned `Cursor` is bound to that of the
2353 /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
2354 /// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
2355 #[unstable(feature = "btree_cursors", issue = "107540")]
2356 pub fn as_cursor(&self) -> Cursor<'_, T> {
2357 Cursor { inner: self.inner.as_cursor() }
2358 }
2359}
2360
2361impl<'a, T: Ord, A: AllocatorClone> CursorMut<'a, T, A> {
2362 /// Inserts a new element into the set in the gap that the
2363 /// cursor is currently pointing to.
2364 ///
2365 /// After the insertion the cursor will be pointing at the gap before the
2366 /// newly inserted element.
2367 ///
2368 /// # Safety
2369 ///
2370 /// You must ensure that the `BTreeSet` invariants are maintained.
2371 /// Specifically:
2372 ///
2373 /// * The newly inserted element must be unique in the tree.
2374 /// * All elements in the tree must remain in sorted order.
2375 #[unstable(feature = "btree_cursors", issue = "107540")]
2376 pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2377 // SAFETY: Upheld by caller.
2378 unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2379 }
2380
2381 /// Inserts a new element into the set in the gap that the
2382 /// cursor is currently pointing to.
2383 ///
2384 /// After the insertion the cursor will be pointing at the gap after the
2385 /// newly inserted element.
2386 ///
2387 /// # Safety
2388 ///
2389 /// You must ensure that the `BTreeSet` invariants are maintained.
2390 /// Specifically:
2391 ///
2392 /// * The newly inserted element must be unique in the tree.
2393 /// * All elements in the tree must remain in sorted order.
2394 #[unstable(feature = "btree_cursors", issue = "107540")]
2395 pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2396 // SAFETY: Upheld by caller.
2397 unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2398 }
2399
2400 /// Inserts a new element into the set in the gap that the
2401 /// cursor is currently pointing to.
2402 ///
2403 /// After the insertion the cursor will be pointing at the gap before the
2404 /// newly inserted element.
2405 ///
2406 /// If the inserted element is not greater than the element before the
2407 /// cursor (if any), or if it not less than the element after the cursor (if
2408 /// any), then an [`UnorderedKeyError`] is returned since this would
2409 /// invalidate the [`Ord`] invariant between the elements of the set.
2410 #[unstable(feature = "btree_cursors", issue = "107540")]
2411 pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2412 self.inner.insert_after(value, SetValZST)
2413 }
2414
2415 /// Inserts a new element into the set in the gap that the
2416 /// cursor is currently pointing to.
2417 ///
2418 /// After the insertion the cursor will be pointing at the gap after the
2419 /// newly inserted element.
2420 ///
2421 /// If the inserted element is not greater than the element before the
2422 /// cursor (if any), or if it not less than the element after the cursor (if
2423 /// any), then an [`UnorderedKeyError`] is returned since this would
2424 /// invalidate the [`Ord`] invariant between the elements of the set.
2425 #[unstable(feature = "btree_cursors", issue = "107540")]
2426 pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2427 self.inner.insert_before(value, SetValZST)
2428 }
2429
2430 /// Removes the next element from the `BTreeSet`.
2431 ///
2432 /// The element that was removed is returned. The cursor position is
2433 /// unchanged (before the removed element).
2434 #[unstable(feature = "btree_cursors", issue = "107540")]
2435 pub fn remove_next(&mut self) -> Option<T> {
2436 self.inner.remove_next().map(|(k, _)| k)
2437 }
2438
2439 /// Removes the preceding element from the `BTreeSet`.
2440 ///
2441 /// The element that was removed is returned. The cursor position is
2442 /// unchanged (after the removed element).
2443 #[unstable(feature = "btree_cursors", issue = "107540")]
2444 pub fn remove_prev(&mut self) -> Option<T> {
2445 self.inner.remove_prev().map(|(k, _)| k)
2446 }
2447}
2448
2449impl<'a, T: Ord, A: AllocatorClone> CursorMutKey<'a, T, A> {
2450 /// Inserts a new element into the set in the gap that the
2451 /// cursor is currently pointing to.
2452 ///
2453 /// After the insertion the cursor will be pointing at the gap before the
2454 /// newly inserted element.
2455 ///
2456 /// # Safety
2457 ///
2458 /// You must ensure that the `BTreeSet` invariants are maintained.
2459 /// Specifically:
2460 ///
2461 /// * The key of the newly inserted element must be unique in the tree.
2462 /// * All elements in the tree must remain in sorted order.
2463 #[unstable(feature = "btree_cursors", issue = "107540")]
2464 pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2465 // SAFETY: Upheld by caller.
2466 unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2467 }
2468
2469 /// Inserts a new element into the set in the gap that the
2470 /// cursor is currently pointing to.
2471 ///
2472 /// After the insertion the cursor will be pointing at the gap after the
2473 /// newly inserted element.
2474 ///
2475 /// # Safety
2476 ///
2477 /// You must ensure that the `BTreeSet` invariants are maintained.
2478 /// Specifically:
2479 ///
2480 /// * The newly inserted element must be unique in the tree.
2481 /// * All elements in the tree must remain in sorted order.
2482 #[unstable(feature = "btree_cursors", issue = "107540")]
2483 pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2484 // SAFETY: Upheld by caller.
2485 unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2486 }
2487
2488 /// Inserts a new element into the set in the gap that the
2489 /// cursor is currently pointing to.
2490 ///
2491 /// After the insertion the cursor will be pointing at the gap before the
2492 /// newly inserted element.
2493 ///
2494 /// If the inserted element is not greater than the element before the
2495 /// cursor (if any), or if it not less than the element after the cursor (if
2496 /// any), then an [`UnorderedKeyError`] is returned since this would
2497 /// invalidate the [`Ord`] invariant between the elements of the set.
2498 #[unstable(feature = "btree_cursors", issue = "107540")]
2499 pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2500 self.inner.insert_after(value, SetValZST)
2501 }
2502
2503 /// Inserts a new element into the set in the gap that the
2504 /// cursor is currently pointing to.
2505 ///
2506 /// After the insertion the cursor will be pointing at the gap after the
2507 /// newly inserted element.
2508 ///
2509 /// If the inserted element is not greater than the element before the
2510 /// cursor (if any), or if it not less than the element after the cursor (if
2511 /// any), then an [`UnorderedKeyError`] is returned since this would
2512 /// invalidate the [`Ord`] invariant between the elements of the set.
2513 #[unstable(feature = "btree_cursors", issue = "107540")]
2514 pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2515 self.inner.insert_before(value, SetValZST)
2516 }
2517
2518 /// Removes the next element from the `BTreeSet`.
2519 ///
2520 /// The element that was removed is returned. The cursor position is
2521 /// unchanged (before the removed element).
2522 #[unstable(feature = "btree_cursors", issue = "107540")]
2523 pub fn remove_next(&mut self) -> Option<T> {
2524 self.inner.remove_next().map(|(k, _)| k)
2525 }
2526
2527 /// Removes the preceding element from the `BTreeSet`.
2528 ///
2529 /// The element that was removed is returned. The cursor position is
2530 /// unchanged (after the removed element).
2531 #[unstable(feature = "btree_cursors", issue = "107540")]
2532 pub fn remove_prev(&mut self) -> Option<T> {
2533 self.inner.remove_prev().map(|(k, _)| k)
2534 }
2535}
2536
2537#[unstable(feature = "btree_cursors", issue = "107540")]
2538pub use super::map::UnorderedKeyError;
2539
2540#[cfg(test)]
2541mod tests;