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};
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::{Allocator, 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_api", issue = "32838")] A: Allocator + Clone = Global,
81> {
82    map: BTreeMap<T, SetValZST, A>,
83}
84
85#[stable(feature = "rust1", since = "1.0.0")]
86impl<T: Hash, A: Allocator + Clone> 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: Allocator + Clone> 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: Allocator + Clone> Eq for BTreeSet<T, A> {}
101
102#[stable(feature = "rust1", since = "1.0.0")]
103impl<T: PartialOrd, A: Allocator + Clone> 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: Allocator + Clone> 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: Allocator + Clone> 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_api", issue = "32838")] A: Allocator + Clone = 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_api", issue = "32838")] A: Allocator + Clone = Global,
187> {
188    inner: DifferenceInner<'a, T, A>,
189}
190enum DifferenceInner<'a, T: 'a, A: Allocator + Clone> {
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: Allocator + Clone> 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: Allocator + Clone> 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_api", issue = "32838")] A: Allocator + Clone = Global,
261> {
262    inner: IntersectionInner<'a, T, A>,
263}
264enum IntersectionInner<'a, T: 'a, A: Allocator + Clone> {
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: Allocator + Clone> 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: Allocator + Clone> 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: Allocator + Clone> 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(allocator_api)]
357    /// # #![feature(btreemap_alloc)]
358    /// use std::collections::BTreeSet;
359    /// use std::alloc::Global;
360    ///
361    /// let mut set: BTreeSet<i32> = BTreeSet::new_in(Global);
362    /// ```
363    #[unstable(feature = "btreemap_alloc", issue = "32838")]
364    pub const fn new_in(alloc: A) -> BTreeSet<T, A> {
365        BTreeSet { map: BTreeMap::new_in(alloc) }
366    }
367
368    /// Constructs a double-ended iterator over a sub-range of elements in the set.
369    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
370    /// yield elements from min (inclusive) to max (exclusive).
371    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
372    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
373    /// range from 4 to 10.
374    ///
375    /// # Panics
376    ///
377    /// Panics if range `start > end`.
378    /// Panics if range `start == end` and both bounds are `Excluded`.
379    ///
380    /// # Examples
381    ///
382    /// ```
383    /// use std::collections::BTreeSet;
384    /// use std::ops::Bound::Included;
385    ///
386    /// let mut set = BTreeSet::new();
387    /// set.insert(3);
388    /// set.insert(5);
389    /// set.insert(8);
390    /// for &elem in set.range((Included(&4), Included(&8))) {
391    ///     println!("{elem}");
392    /// }
393    /// assert_eq!(Some(&5), set.range(4..).next());
394    /// ```
395    #[stable(feature = "btree_range", since = "1.17.0")]
396    pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
397    where
398        K: Ord,
399        T: Borrow<K> + Ord,
400        R: RangeBounds<K>,
401    {
402        Range { iter: self.map.range(range) }
403    }
404
405    /// Visits the elements representing the difference,
406    /// i.e., the elements that are in `self` but not in `other`,
407    /// in ascending order.
408    ///
409    /// # Examples
410    ///
411    /// ```
412    /// use std::collections::BTreeSet;
413    ///
414    /// let mut a = BTreeSet::new();
415    /// a.insert(1);
416    /// a.insert(2);
417    ///
418    /// let mut b = BTreeSet::new();
419    /// b.insert(2);
420    /// b.insert(3);
421    ///
422    /// let diff: Vec<_> = a.difference(&b).cloned().collect();
423    /// assert_eq!(diff, [1]);
424    /// ```
425    #[stable(feature = "rust1", since = "1.0.0")]
426    pub fn difference<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Difference<'a, T, A>
427    where
428        T: Ord,
429    {
430        let (self_min, self_max) =
431            if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
432                (self_min, self_max)
433            } else {
434                return Difference { inner: DifferenceInner::Iterate(self.iter()) };
435            };
436        let (other_min, other_max) =
437            if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
438                (other_min, other_max)
439            } else {
440                return Difference { inner: DifferenceInner::Iterate(self.iter()) };
441            };
442        Difference {
443            inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
444                (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()),
445                (Equal, _) => {
446                    let mut self_iter = self.iter();
447                    self_iter.next();
448                    DifferenceInner::Iterate(self_iter)
449                }
450                (_, Equal) => {
451                    let mut self_iter = self.iter();
452                    self_iter.next_back();
453                    DifferenceInner::Iterate(self_iter)
454                }
455                _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
456                    DifferenceInner::Search { self_iter: self.iter(), other_set: other }
457                }
458                _ => DifferenceInner::Stitch {
459                    self_iter: self.iter(),
460                    other_iter: other.iter().peekable(),
461                },
462            },
463        }
464    }
465
466    /// Visits the elements representing the symmetric difference,
467    /// i.e., the elements that are in `self` or in `other` but not in both,
468    /// in ascending order.
469    ///
470    /// # Examples
471    ///
472    /// ```
473    /// use std::collections::BTreeSet;
474    ///
475    /// let mut a = BTreeSet::new();
476    /// a.insert(1);
477    /// a.insert(2);
478    ///
479    /// let mut b = BTreeSet::new();
480    /// b.insert(2);
481    /// b.insert(3);
482    ///
483    /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
484    /// assert_eq!(sym_diff, [1, 3]);
485    /// ```
486    #[stable(feature = "rust1", since = "1.0.0")]
487    pub fn symmetric_difference<'a>(
488        &'a self,
489        other: &'a BTreeSet<T, A>,
490    ) -> SymmetricDifference<'a, T>
491    where
492        T: Ord,
493    {
494        SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
495    }
496
497    /// Visits the elements representing the intersection,
498    /// i.e., the elements that are both in `self` and `other`,
499    /// in ascending order.
500    ///
501    /// # Examples
502    ///
503    /// ```
504    /// use std::collections::BTreeSet;
505    ///
506    /// let mut a = BTreeSet::new();
507    /// a.insert(1);
508    /// a.insert(2);
509    ///
510    /// let mut b = BTreeSet::new();
511    /// b.insert(2);
512    /// b.insert(3);
513    ///
514    /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
515    /// assert_eq!(intersection, [2]);
516    /// ```
517    #[stable(feature = "rust1", since = "1.0.0")]
518    pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Intersection<'a, T, A>
519    where
520        T: Ord,
521    {
522        let (self_min, self_max) =
523            if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
524                (self_min, self_max)
525            } else {
526                return Intersection { inner: IntersectionInner::Answer(None) };
527            };
528        let (other_min, other_max) =
529            if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
530                (other_min, other_max)
531            } else {
532                return Intersection { inner: IntersectionInner::Answer(None) };
533            };
534        Intersection {
535            inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
536                (Greater, _) | (_, Less) => IntersectionInner::Answer(None),
537                (Equal, _) => IntersectionInner::Answer(Some(self_min)),
538                (_, Equal) => IntersectionInner::Answer(Some(self_max)),
539                _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
540                    IntersectionInner::Search { small_iter: self.iter(), large_set: other }
541                }
542                _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
543                    IntersectionInner::Search { small_iter: other.iter(), large_set: self }
544                }
545                _ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() },
546            },
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;
698        }
699        let (self_min, self_max) =
700            if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
701                (self_min, self_max)
702            } else {
703                return true; // self is empty
704            };
705        let (other_min, other_max) =
706            if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
707                (other_min, other_max)
708            } else {
709                return false; // other is empty
710            };
711        let mut self_iter = self.iter();
712        match self_min.cmp(other_min) {
713            Less => return false,
714            Equal => {
715                self_iter.next();
716            }
717            Greater => (),
718        }
719        match self_max.cmp(other_max) {
720            Greater => return false,
721            Equal => {
722                self_iter.next_back();
723            }
724            Less => (),
725        }
726        if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
727            for next in self_iter {
728                if !other.contains(next) {
729                    return false;
730                }
731            }
732        } else {
733            let mut other_iter = other.iter();
734            other_iter.next();
735            other_iter.next_back();
736            let mut self_next = self_iter.next();
737            while let Some(self1) = self_next {
738                match other_iter.next().map_or(Less, |other1| self1.cmp(other1)) {
739                    Less => return false,
740                    Equal => self_next = self_iter.next(),
741                    Greater => (),
742                }
743            }
744        }
745        true
746    }
747
748    /// Returns `true` if the set is a superset of another,
749    /// i.e., `self` contains at least all the elements in `other`.
750    ///
751    /// # Examples
752    ///
753    /// ```
754    /// use std::collections::BTreeSet;
755    ///
756    /// let sub = BTreeSet::from([1, 2]);
757    /// let mut set = BTreeSet::new();
758    ///
759    /// assert_eq!(set.is_superset(&sub), false);
760    ///
761    /// set.insert(0);
762    /// set.insert(1);
763    /// assert_eq!(set.is_superset(&sub), false);
764    ///
765    /// set.insert(2);
766    /// assert_eq!(set.is_superset(&sub), true);
767    /// ```
768    #[must_use]
769    #[stable(feature = "rust1", since = "1.0.0")]
770    pub fn is_superset(&self, other: &BTreeSet<T, A>) -> bool
771    where
772        T: Ord,
773    {
774        other.is_subset(self)
775    }
776
777    /// Returns a reference to the first element in the set, if any.
778    /// This element is always the minimum of all elements in the set.
779    ///
780    /// # Examples
781    ///
782    /// Basic usage:
783    ///
784    /// ```
785    /// use std::collections::BTreeSet;
786    ///
787    /// let mut set = BTreeSet::new();
788    /// assert_eq!(set.first(), None);
789    /// set.insert(1);
790    /// assert_eq!(set.first(), Some(&1));
791    /// set.insert(2);
792    /// assert_eq!(set.first(), Some(&1));
793    /// ```
794    #[must_use]
795    #[stable(feature = "map_first_last", since = "1.66.0")]
796    #[rustc_confusables("front")]
797    pub fn first(&self) -> Option<&T>
798    where
799        T: Ord,
800    {
801        self.map.first_key_value().map(|(k, _)| k)
802    }
803
804    /// Returns a reference to the last element in the set, if any.
805    /// This element is always the maximum of all elements in the set.
806    ///
807    /// # Examples
808    ///
809    /// Basic usage:
810    ///
811    /// ```
812    /// use std::collections::BTreeSet;
813    ///
814    /// let mut set = BTreeSet::new();
815    /// assert_eq!(set.last(), None);
816    /// set.insert(1);
817    /// assert_eq!(set.last(), Some(&1));
818    /// set.insert(2);
819    /// assert_eq!(set.last(), Some(&2));
820    /// ```
821    #[must_use]
822    #[stable(feature = "map_first_last", since = "1.66.0")]
823    #[rustc_confusables("back")]
824    pub fn last(&self) -> Option<&T>
825    where
826        T: Ord,
827    {
828        self.map.last_key_value().map(|(k, _)| k)
829    }
830
831    /// Removes the first element from the set and returns it, if any.
832    /// The first element is always the minimum element in the set.
833    ///
834    /// # Examples
835    ///
836    /// ```
837    /// use std::collections::BTreeSet;
838    ///
839    /// let mut set = BTreeSet::new();
840    ///
841    /// set.insert(1);
842    /// while let Some(n) = set.pop_first() {
843    ///     assert_eq!(n, 1);
844    /// }
845    /// assert!(set.is_empty());
846    /// ```
847    #[stable(feature = "map_first_last", since = "1.66.0")]
848    pub fn pop_first(&mut self) -> Option<T>
849    where
850        T: Ord,
851    {
852        self.map.pop_first().map(|kv| kv.0)
853    }
854
855    /// Removes the last element from the set and returns it, if any.
856    /// The last element is always the maximum element in the set.
857    ///
858    /// # Examples
859    ///
860    /// ```
861    /// use std::collections::BTreeSet;
862    ///
863    /// let mut set = BTreeSet::new();
864    ///
865    /// set.insert(1);
866    /// while let Some(n) = set.pop_last() {
867    ///     assert_eq!(n, 1);
868    /// }
869    /// assert!(set.is_empty());
870    /// ```
871    #[stable(feature = "map_first_last", since = "1.66.0")]
872    pub fn pop_last(&mut self) -> Option<T>
873    where
874        T: Ord,
875    {
876        self.map.pop_last().map(|kv| kv.0)
877    }
878
879    /// Adds a value to the set.
880    ///
881    /// Returns whether the value was newly inserted. That is:
882    ///
883    /// - If the set did not previously contain an equal value, `true` is
884    ///   returned.
885    /// - If the set already contained an equal value, `false` is returned, and
886    ///   the entry is not updated.
887    ///
888    /// See the [module-level documentation] for more.
889    ///
890    /// [module-level documentation]: index.html#insert-and-complex-keys
891    ///
892    /// # Examples
893    ///
894    /// ```
895    /// use std::collections::BTreeSet;
896    ///
897    /// let mut set = BTreeSet::new();
898    ///
899    /// assert_eq!(set.insert(2), true);
900    /// assert_eq!(set.insert(2), false);
901    /// assert_eq!(set.len(), 1);
902    /// ```
903    #[stable(feature = "rust1", since = "1.0.0")]
904    #[rustc_confusables("push", "put")]
905    pub fn insert(&mut self, value: T) -> bool
906    where
907        T: Ord,
908    {
909        self.map.insert(value, SetValZST::default()).is_none()
910    }
911
912    /// Adds a value to the set, replacing the existing element, if any, that is
913    /// equal to the value. Returns the replaced element.
914    ///
915    /// # Examples
916    ///
917    /// ```
918    /// use std::collections::BTreeSet;
919    ///
920    /// let mut set = BTreeSet::new();
921    /// set.insert(Vec::<i32>::new());
922    ///
923    /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
924    /// set.replace(Vec::with_capacity(10));
925    /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
926    /// ```
927    #[stable(feature = "set_recovery", since = "1.9.0")]
928    #[rustc_confusables("swap")]
929    pub fn replace(&mut self, value: T) -> Option<T>
930    where
931        T: Ord,
932    {
933        self.map.replace(value)
934    }
935
936    /// Inserts the given `value` into the set if it is not present, then
937    /// returns a reference to the value in the set.
938    ///
939    /// # Examples
940    ///
941    /// ```
942    /// #![feature(btree_set_entry)]
943    ///
944    /// use std::collections::BTreeSet;
945    ///
946    /// let mut set = BTreeSet::from([1, 2, 3]);
947    /// assert_eq!(set.len(), 3);
948    /// assert_eq!(set.get_or_insert(2), &2);
949    /// assert_eq!(set.get_or_insert(100), &100);
950    /// assert_eq!(set.len(), 4); // 100 was inserted
951    /// ```
952    #[inline]
953    #[unstable(feature = "btree_set_entry", issue = "133549")]
954    pub fn get_or_insert(&mut self, value: T) -> &T
955    where
956        T: Ord,
957    {
958        self.map.entry(value).insert_entry(SetValZST).into_key()
959    }
960
961    /// Inserts a value computed from `f` into the set if the given `value` is
962    /// not present, then returns a reference to the value in the set.
963    ///
964    /// # Examples
965    ///
966    /// ```
967    /// #![feature(btree_set_entry)]
968    ///
969    /// use std::collections::BTreeSet;
970    ///
971    /// let mut set: BTreeSet<String> = ["cat", "dog", "horse"]
972    ///     .iter().map(|&pet| pet.to_owned()).collect();
973    ///
974    /// assert_eq!(set.len(), 3);
975    /// for &pet in &["cat", "dog", "fish"] {
976    ///     let value = set.get_or_insert_with(pet, str::to_owned);
977    ///     assert_eq!(value, pet);
978    /// }
979    /// assert_eq!(set.len(), 4); // a new "fish" was inserted
980    /// ```
981    #[inline]
982    #[unstable(feature = "btree_set_entry", issue = "133549")]
983    pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
984    where
985        T: Borrow<Q> + Ord,
986        Q: Ord,
987        F: FnOnce(&Q) -> T,
988    {
989        self.map.get_or_insert_with(value, f)
990    }
991
992    /// Gets the given value's corresponding entry in the set for in-place manipulation.
993    ///
994    /// # Examples
995    ///
996    /// ```
997    /// #![feature(btree_set_entry)]
998    ///
999    /// use std::collections::BTreeSet;
1000    /// use std::collections::btree_set::Entry::*;
1001    ///
1002    /// let mut singles = BTreeSet::new();
1003    /// let mut dupes = BTreeSet::new();
1004    ///
1005    /// for ch in "a short treatise on fungi".chars() {
1006    ///     if let Vacant(dupe_entry) = dupes.entry(ch) {
1007    ///         // We haven't already seen a duplicate, so
1008    ///         // check if we've at least seen it once.
1009    ///         match singles.entry(ch) {
1010    ///             Vacant(single_entry) => {
1011    ///                 // We found a new character for the first time.
1012    ///                 single_entry.insert()
1013    ///             }
1014    ///             Occupied(single_entry) => {
1015    ///                 // We've already seen this once, "move" it to dupes.
1016    ///                 single_entry.remove();
1017    ///                 dupe_entry.insert();
1018    ///             }
1019    ///         }
1020    ///     }
1021    /// }
1022    ///
1023    /// assert!(!singles.contains(&'t') && dupes.contains(&'t'));
1024    /// assert!(singles.contains(&'u') && !dupes.contains(&'u'));
1025    /// assert!(!singles.contains(&'v') && !dupes.contains(&'v'));
1026    /// ```
1027    #[inline]
1028    #[unstable(feature = "btree_set_entry", issue = "133549")]
1029    pub fn entry(&mut self, value: T) -> Entry<'_, T, A>
1030    where
1031        T: Ord,
1032    {
1033        match self.map.entry(value) {
1034            map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
1035            map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
1036        }
1037    }
1038
1039    /// If the set contains an element equal to the value, removes it from the
1040    /// set and drops it. Returns whether such an element was present.
1041    ///
1042    /// The value may be any borrowed form of the set's element type,
1043    /// but the ordering on the borrowed form *must* match the
1044    /// ordering on the element type.
1045    ///
1046    /// # Examples
1047    ///
1048    /// ```
1049    /// use std::collections::BTreeSet;
1050    ///
1051    /// let mut set = BTreeSet::new();
1052    ///
1053    /// set.insert(2);
1054    /// assert_eq!(set.remove(&2), true);
1055    /// assert_eq!(set.remove(&2), false);
1056    /// ```
1057    #[stable(feature = "rust1", since = "1.0.0")]
1058    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
1059    where
1060        T: Borrow<Q> + Ord,
1061        Q: Ord,
1062    {
1063        self.map.remove(value).is_some()
1064    }
1065
1066    /// Removes and returns the element in the set, if any, that is equal to
1067    /// the value.
1068    ///
1069    /// The value may be any borrowed form of the set's element type,
1070    /// but the ordering on the borrowed form *must* match the
1071    /// ordering on the element type.
1072    ///
1073    /// # Examples
1074    ///
1075    /// ```
1076    /// use std::collections::BTreeSet;
1077    ///
1078    /// let mut set = BTreeSet::from([1, 2, 3]);
1079    /// assert_eq!(set.take(&2), Some(2));
1080    /// assert_eq!(set.take(&2), None);
1081    /// ```
1082    #[stable(feature = "set_recovery", since = "1.9.0")]
1083    pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
1084    where
1085        T: Borrow<Q> + Ord,
1086        Q: Ord,
1087    {
1088        self.map.remove_entry(value).map(|(k, _)| k)
1089    }
1090
1091    /// Retains only the elements specified by the predicate.
1092    ///
1093    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
1094    /// The elements are visited in ascending order.
1095    ///
1096    /// # Examples
1097    ///
1098    /// ```
1099    /// use std::collections::BTreeSet;
1100    ///
1101    /// let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
1102    /// // Keep only the even numbers.
1103    /// set.retain(|&k| k % 2 == 0);
1104    /// assert!(set.iter().eq([2, 4, 6].iter()));
1105    /// ```
1106    #[stable(feature = "btree_retain", since = "1.53.0")]
1107    pub fn retain<F>(&mut self, mut f: F)
1108    where
1109        T: Ord,
1110        F: FnMut(&T) -> bool,
1111    {
1112        self.extract_if(.., |v| !f(v)).for_each(drop);
1113    }
1114
1115    /// Moves all elements from `other` into `self`, leaving `other` empty.
1116    ///
1117    /// # Examples
1118    ///
1119    /// ```
1120    /// use std::collections::BTreeSet;
1121    ///
1122    /// let mut a = BTreeSet::new();
1123    /// a.insert(1);
1124    /// a.insert(2);
1125    /// a.insert(3);
1126    ///
1127    /// let mut b = BTreeSet::new();
1128    /// b.insert(3);
1129    /// b.insert(4);
1130    /// b.insert(5);
1131    ///
1132    /// a.append(&mut b);
1133    ///
1134    /// assert_eq!(a.len(), 5);
1135    /// assert_eq!(b.len(), 0);
1136    ///
1137    /// assert!(a.contains(&1));
1138    /// assert!(a.contains(&2));
1139    /// assert!(a.contains(&3));
1140    /// assert!(a.contains(&4));
1141    /// assert!(a.contains(&5));
1142    /// ```
1143    #[stable(feature = "btree_append", since = "1.11.0")]
1144    pub fn append(&mut self, other: &mut Self)
1145    where
1146        T: Ord,
1147        A: Clone,
1148    {
1149        self.map.append(&mut other.map);
1150    }
1151
1152    /// Splits the collection into two at the value. Returns a new collection
1153    /// with all elements greater than or equal to the value.
1154    ///
1155    /// # Examples
1156    ///
1157    /// Basic usage:
1158    ///
1159    /// ```
1160    /// use std::collections::BTreeSet;
1161    ///
1162    /// let mut a = BTreeSet::new();
1163    /// a.insert(1);
1164    /// a.insert(2);
1165    /// a.insert(3);
1166    /// a.insert(17);
1167    /// a.insert(41);
1168    ///
1169    /// let b = a.split_off(&3);
1170    ///
1171    /// assert_eq!(a.len(), 2);
1172    /// assert_eq!(b.len(), 3);
1173    ///
1174    /// assert!(a.contains(&1));
1175    /// assert!(a.contains(&2));
1176    ///
1177    /// assert!(b.contains(&3));
1178    /// assert!(b.contains(&17));
1179    /// assert!(b.contains(&41));
1180    /// ```
1181    #[stable(feature = "btree_split_off", since = "1.11.0")]
1182    pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self
1183    where
1184        T: Borrow<Q> + Ord,
1185        A: Clone,
1186    {
1187        BTreeSet { map: self.map.split_off(value) }
1188    }
1189
1190    /// Creates an iterator that visits elements in the specified range in ascending order and
1191    /// uses a closure to determine if an element should be removed.
1192    ///
1193    /// If the closure returns `true`, the element is removed from the set and
1194    /// yielded. If the closure returns `false`, or panics, the element remains
1195    /// in the set and will not be yielded.
1196    ///
1197    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1198    /// or the iteration short-circuits, then the remaining elements will be retained.
1199    /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
1200    ///
1201    /// [`retain`]: BTreeSet::retain
1202    /// # Examples
1203    ///
1204    /// ```
1205    /// #![feature(btree_extract_if)]
1206    /// use std::collections::BTreeSet;
1207    ///
1208    /// // Splitting a set into even and odd values, reusing the original set:
1209    /// let mut set: BTreeSet<i32> = (0..8).collect();
1210    /// let evens: BTreeSet<_> = set.extract_if(.., |v| v % 2 == 0).collect();
1211    /// let odds = set;
1212    /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
1213    /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
1214    ///
1215    /// // Splitting a set into low and high halves, reusing the original set:
1216    /// let mut set: BTreeSet<i32> = (0..8).collect();
1217    /// let low: BTreeSet<_> = set.extract_if(0..4, |_v| true).collect();
1218    /// let high = set;
1219    /// assert_eq!(low.into_iter().collect::<Vec<_>>(), [0, 1, 2, 3]);
1220    /// assert_eq!(high.into_iter().collect::<Vec<_>>(), [4, 5, 6, 7]);
1221    /// ```
1222    #[unstable(feature = "btree_extract_if", issue = "70530")]
1223    pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, T, R, F, A>
1224    where
1225        T: Ord,
1226        R: RangeBounds<T>,
1227        F: FnMut(&T) -> bool,
1228    {
1229        let (inner, alloc) = self.map.extract_if_inner(range);
1230        ExtractIf { pred, inner, alloc }
1231    }
1232
1233    /// Gets an iterator that visits the elements in the `BTreeSet` in ascending
1234    /// order.
1235    ///
1236    /// # Examples
1237    ///
1238    /// ```
1239    /// use std::collections::BTreeSet;
1240    ///
1241    /// let set = BTreeSet::from([3, 1, 2]);
1242    /// let mut set_iter = set.iter();
1243    /// assert_eq!(set_iter.next(), Some(&1));
1244    /// assert_eq!(set_iter.next(), Some(&2));
1245    /// assert_eq!(set_iter.next(), Some(&3));
1246    /// assert_eq!(set_iter.next(), None);
1247    /// ```
1248    #[stable(feature = "rust1", since = "1.0.0")]
1249    #[cfg_attr(not(test), rustc_diagnostic_item = "btreeset_iter")]
1250    pub fn iter(&self) -> Iter<'_, T> {
1251        Iter { iter: self.map.keys() }
1252    }
1253
1254    /// Returns the number of elements in the set.
1255    ///
1256    /// # Examples
1257    ///
1258    /// ```
1259    /// use std::collections::BTreeSet;
1260    ///
1261    /// let mut v = BTreeSet::new();
1262    /// assert_eq!(v.len(), 0);
1263    /// v.insert(1);
1264    /// assert_eq!(v.len(), 1);
1265    /// ```
1266    #[must_use]
1267    #[stable(feature = "rust1", since = "1.0.0")]
1268    #[rustc_const_unstable(
1269        feature = "const_btree_len",
1270        issue = "71835",
1271        implied_by = "const_btree_new"
1272    )]
1273    #[rustc_confusables("length", "size")]
1274    pub const fn len(&self) -> usize {
1275        self.map.len()
1276    }
1277
1278    /// Returns `true` if the set contains no elements.
1279    ///
1280    /// # Examples
1281    ///
1282    /// ```
1283    /// use std::collections::BTreeSet;
1284    ///
1285    /// let mut v = BTreeSet::new();
1286    /// assert!(v.is_empty());
1287    /// v.insert(1);
1288    /// assert!(!v.is_empty());
1289    /// ```
1290    #[must_use]
1291    #[stable(feature = "rust1", since = "1.0.0")]
1292    #[rustc_const_unstable(
1293        feature = "const_btree_len",
1294        issue = "71835",
1295        implied_by = "const_btree_new"
1296    )]
1297    pub const fn is_empty(&self) -> bool {
1298        self.len() == 0
1299    }
1300
1301    /// Returns a [`Cursor`] pointing at the gap before the smallest element
1302    /// greater than the given bound.
1303    ///
1304    /// Passing `Bound::Included(x)` will return a cursor pointing to the
1305    /// gap before the smallest element greater than or equal to `x`.
1306    ///
1307    /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1308    /// gap before the smallest element greater than `x`.
1309    ///
1310    /// Passing `Bound::Unbounded` will return a cursor pointing to the
1311    /// gap before the smallest element in the set.
1312    ///
1313    /// # Examples
1314    ///
1315    /// ```
1316    /// #![feature(btree_cursors)]
1317    ///
1318    /// use std::collections::BTreeSet;
1319    /// use std::ops::Bound;
1320    ///
1321    /// let set = BTreeSet::from([1, 2, 3, 4]);
1322    ///
1323    /// let cursor = set.lower_bound(Bound::Included(&2));
1324    /// assert_eq!(cursor.peek_prev(), Some(&1));
1325    /// assert_eq!(cursor.peek_next(), Some(&2));
1326    ///
1327    /// let cursor = set.lower_bound(Bound::Excluded(&2));
1328    /// assert_eq!(cursor.peek_prev(), Some(&2));
1329    /// assert_eq!(cursor.peek_next(), Some(&3));
1330    ///
1331    /// let cursor = set.lower_bound(Bound::Unbounded);
1332    /// assert_eq!(cursor.peek_prev(), None);
1333    /// assert_eq!(cursor.peek_next(), Some(&1));
1334    /// ```
1335    #[unstable(feature = "btree_cursors", issue = "107540")]
1336    pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
1337    where
1338        T: Borrow<Q> + Ord,
1339        Q: Ord,
1340    {
1341        Cursor { inner: self.map.lower_bound(bound) }
1342    }
1343
1344    /// Returns a [`CursorMut`] pointing at the gap before the smallest element
1345    /// greater than the given bound.
1346    ///
1347    /// Passing `Bound::Included(x)` will return a cursor pointing to the
1348    /// gap before the smallest element greater than or equal to `x`.
1349    ///
1350    /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1351    /// gap before the smallest element greater than `x`.
1352    ///
1353    /// Passing `Bound::Unbounded` will return a cursor pointing to the
1354    /// gap before the smallest element in the set.
1355    ///
1356    /// # Examples
1357    ///
1358    /// ```
1359    /// #![feature(btree_cursors)]
1360    ///
1361    /// use std::collections::BTreeSet;
1362    /// use std::ops::Bound;
1363    ///
1364    /// let mut set = BTreeSet::from([1, 2, 3, 4]);
1365    ///
1366    /// let mut cursor = set.lower_bound_mut(Bound::Included(&2));
1367    /// assert_eq!(cursor.peek_prev(), Some(&1));
1368    /// assert_eq!(cursor.peek_next(), Some(&2));
1369    ///
1370    /// let mut cursor = set.lower_bound_mut(Bound::Excluded(&2));
1371    /// assert_eq!(cursor.peek_prev(), Some(&2));
1372    /// assert_eq!(cursor.peek_next(), Some(&3));
1373    ///
1374    /// let mut cursor = set.lower_bound_mut(Bound::Unbounded);
1375    /// assert_eq!(cursor.peek_prev(), None);
1376    /// assert_eq!(cursor.peek_next(), Some(&1));
1377    /// ```
1378    #[unstable(feature = "btree_cursors", issue = "107540")]
1379    pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1380    where
1381        T: Borrow<Q> + Ord,
1382        Q: Ord,
1383    {
1384        CursorMut { inner: self.map.lower_bound_mut(bound) }
1385    }
1386
1387    /// Returns a [`Cursor`] pointing at the gap after the greatest element
1388    /// smaller than the given bound.
1389    ///
1390    /// Passing `Bound::Included(x)` will return a cursor pointing to the
1391    /// gap after the greatest element smaller than or equal to `x`.
1392    ///
1393    /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1394    /// gap after the greatest element smaller than `x`.
1395    ///
1396    /// Passing `Bound::Unbounded` will return a cursor pointing to the
1397    /// gap after the greatest element in the set.
1398    ///
1399    /// # Examples
1400    ///
1401    /// ```
1402    /// #![feature(btree_cursors)]
1403    ///
1404    /// use std::collections::BTreeSet;
1405    /// use std::ops::Bound;
1406    ///
1407    /// let set = BTreeSet::from([1, 2, 3, 4]);
1408    ///
1409    /// let cursor = set.upper_bound(Bound::Included(&3));
1410    /// assert_eq!(cursor.peek_prev(), Some(&3));
1411    /// assert_eq!(cursor.peek_next(), Some(&4));
1412    ///
1413    /// let cursor = set.upper_bound(Bound::Excluded(&3));
1414    /// assert_eq!(cursor.peek_prev(), Some(&2));
1415    /// assert_eq!(cursor.peek_next(), Some(&3));
1416    ///
1417    /// let cursor = set.upper_bound(Bound::Unbounded);
1418    /// assert_eq!(cursor.peek_prev(), Some(&4));
1419    /// assert_eq!(cursor.peek_next(), None);
1420    /// ```
1421    #[unstable(feature = "btree_cursors", issue = "107540")]
1422    pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
1423    where
1424        T: Borrow<Q> + Ord,
1425        Q: Ord,
1426    {
1427        Cursor { inner: self.map.upper_bound(bound) }
1428    }
1429
1430    /// Returns a [`CursorMut`] pointing at the gap after the greatest element
1431    /// smaller than the given bound.
1432    ///
1433    /// Passing `Bound::Included(x)` will return a cursor pointing to the
1434    /// gap after the greatest element smaller than or equal to `x`.
1435    ///
1436    /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1437    /// gap after the greatest element smaller than `x`.
1438    ///
1439    /// Passing `Bound::Unbounded` will return a cursor pointing to the
1440    /// gap after the greatest element in the set.
1441    ///
1442    /// # Examples
1443    ///
1444    /// ```
1445    /// #![feature(btree_cursors)]
1446    ///
1447    /// use std::collections::BTreeSet;
1448    /// use std::ops::Bound;
1449    ///
1450    /// let mut set = BTreeSet::from([1, 2, 3, 4]);
1451    ///
1452    /// let mut cursor = set.upper_bound_mut(Bound::Included(&3));
1453    /// assert_eq!(cursor.peek_prev(), Some(&3));
1454    /// assert_eq!(cursor.peek_next(), Some(&4));
1455    ///
1456    /// let mut cursor = set.upper_bound_mut(Bound::Excluded(&3));
1457    /// assert_eq!(cursor.peek_prev(), Some(&2));
1458    /// assert_eq!(cursor.peek_next(), Some(&3));
1459    ///
1460    /// let mut cursor = set.upper_bound_mut(Bound::Unbounded);
1461    /// assert_eq!(cursor.peek_prev(), Some(&4));
1462    /// assert_eq!(cursor.peek_next(), None);
1463    /// ```
1464    #[unstable(feature = "btree_cursors", issue = "107540")]
1465    pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1466    where
1467        T: Borrow<Q> + Ord,
1468        Q: Ord,
1469    {
1470        CursorMut { inner: self.map.upper_bound_mut(bound) }
1471    }
1472}
1473
1474#[stable(feature = "rust1", since = "1.0.0")]
1475impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1476    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1477        let mut inputs: Vec<_> = iter.into_iter().collect();
1478
1479        if inputs.is_empty() {
1480            return BTreeSet::new();
1481        }
1482
1483        // use stable sort to preserve the insertion order.
1484        inputs.sort();
1485        BTreeSet::from_sorted_iter(inputs.into_iter(), Global)
1486    }
1487}
1488
1489impl<T: Ord, A: Allocator + Clone> BTreeSet<T, A> {
1490    fn from_sorted_iter<I: Iterator<Item = T>>(iter: I, alloc: A) -> BTreeSet<T, A> {
1491        let iter = iter.map(|k| (k, SetValZST::default()));
1492        let map = BTreeMap::bulk_build_from_sorted_iter(iter, alloc);
1493        BTreeSet { map }
1494    }
1495}
1496
1497#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1498impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
1499    /// Converts a `[T; N]` into a `BTreeSet<T>`.
1500    ///
1501    /// If the array contains any equal values,
1502    /// all but one will be dropped.
1503    ///
1504    /// # Examples
1505    ///
1506    /// ```
1507    /// use std::collections::BTreeSet;
1508    ///
1509    /// let set1 = BTreeSet::from([1, 2, 3, 4]);
1510    /// let set2: BTreeSet<_> = [1, 2, 3, 4].into();
1511    /// assert_eq!(set1, set2);
1512    /// ```
1513    fn from(mut arr: [T; N]) -> Self {
1514        if N == 0 {
1515            return BTreeSet::new();
1516        }
1517
1518        // use stable sort to preserve the insertion order.
1519        arr.sort();
1520        let iter = IntoIterator::into_iter(arr).map(|k| (k, SetValZST::default()));
1521        let map = BTreeMap::bulk_build_from_sorted_iter(iter, Global);
1522        BTreeSet { map }
1523    }
1524}
1525
1526#[stable(feature = "rust1", since = "1.0.0")]
1527impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> {
1528    type Item = T;
1529    type IntoIter = IntoIter<T, A>;
1530
1531    /// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order.
1532    ///
1533    /// # Examples
1534    ///
1535    /// ```
1536    /// use std::collections::BTreeSet;
1537    ///
1538    /// let set = BTreeSet::from([1, 2, 3, 4]);
1539    ///
1540    /// let v: Vec<_> = set.into_iter().collect();
1541    /// assert_eq!(v, [1, 2, 3, 4]);
1542    /// ```
1543    fn into_iter(self) -> IntoIter<T, A> {
1544        IntoIter { iter: self.map.into_iter() }
1545    }
1546}
1547
1548#[stable(feature = "rust1", since = "1.0.0")]
1549impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> {
1550    type Item = &'a T;
1551    type IntoIter = Iter<'a, T>;
1552
1553    fn into_iter(self) -> Iter<'a, T> {
1554        self.iter()
1555    }
1556}
1557
1558/// An iterator produced by calling `extract_if` on BTreeSet.
1559#[unstable(feature = "btree_extract_if", issue = "70530")]
1560#[must_use = "iterators are lazy and do nothing unless consumed"]
1561pub struct ExtractIf<
1562    'a,
1563    T,
1564    R,
1565    F,
1566    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1567> {
1568    pred: F,
1569    inner: super::map::ExtractIfInner<'a, T, SetValZST, R>,
1570    /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1571    alloc: A,
1572}
1573
1574#[unstable(feature = "btree_extract_if", issue = "70530")]
1575impl<T, R, F, A> fmt::Debug for ExtractIf<'_, T, R, F, A>
1576where
1577    T: fmt::Debug,
1578    A: Allocator + Clone,
1579{
1580    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1581        f.debug_struct("ExtractIf")
1582            .field("peek", &self.inner.peek().map(|(k, _)| k))
1583            .finish_non_exhaustive()
1584    }
1585}
1586
1587#[unstable(feature = "btree_extract_if", issue = "70530")]
1588impl<T, R, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, R, F, A>
1589where
1590    T: PartialOrd,
1591    R: RangeBounds<T>,
1592    F: FnMut(&T) -> bool,
1593{
1594    type Item = T;
1595
1596    fn next(&mut self) -> Option<T> {
1597        let pred = &mut self.pred;
1598        let mut mapped_pred = |k: &T, _v: &mut SetValZST| pred(k);
1599        self.inner.next(&mut mapped_pred, self.alloc.clone()).map(|(k, _)| k)
1600    }
1601
1602    fn size_hint(&self) -> (usize, Option<usize>) {
1603        self.inner.size_hint()
1604    }
1605}
1606
1607#[unstable(feature = "btree_extract_if", issue = "70530")]
1608impl<T, R, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, R, F, A>
1609where
1610    T: PartialOrd,
1611    R: RangeBounds<T>,
1612    F: FnMut(&T) -> bool,
1613{
1614}
1615
1616#[stable(feature = "rust1", since = "1.0.0")]
1617impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> {
1618    #[inline]
1619    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1620        iter.into_iter().for_each(move |elem| {
1621            self.insert(elem);
1622        });
1623    }
1624
1625    #[inline]
1626    fn extend_one(&mut self, elem: T) {
1627        self.insert(elem);
1628    }
1629}
1630
1631#[stable(feature = "extend_ref", since = "1.2.0")]
1632impl<'a, T: 'a + Ord + Copy, A: Allocator + Clone> Extend<&'a T> for BTreeSet<T, A> {
1633    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1634        self.extend(iter.into_iter().cloned());
1635    }
1636
1637    #[inline]
1638    fn extend_one(&mut self, &elem: &'a T) {
1639        self.insert(elem);
1640    }
1641}
1642
1643#[stable(feature = "rust1", since = "1.0.0")]
1644impl<T> Default for BTreeSet<T> {
1645    /// Creates an empty `BTreeSet`.
1646    fn default() -> BTreeSet<T> {
1647        BTreeSet::new()
1648    }
1649}
1650
1651#[stable(feature = "rust1", since = "1.0.0")]
1652impl<T: Ord + Clone, A: Allocator + Clone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1653    type Output = BTreeSet<T, A>;
1654
1655    /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1656    ///
1657    /// # Examples
1658    ///
1659    /// ```
1660    /// use std::collections::BTreeSet;
1661    ///
1662    /// let a = BTreeSet::from([1, 2, 3]);
1663    /// let b = BTreeSet::from([3, 4, 5]);
1664    ///
1665    /// let result = &a - &b;
1666    /// assert_eq!(result, BTreeSet::from([1, 2]));
1667    /// ```
1668    fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1669        BTreeSet::from_sorted_iter(
1670            self.difference(rhs).cloned(),
1671            ManuallyDrop::into_inner(self.map.alloc.clone()),
1672        )
1673    }
1674}
1675
1676#[stable(feature = "rust1", since = "1.0.0")]
1677impl<T: Ord + Clone, A: Allocator + Clone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1678    type Output = BTreeSet<T, A>;
1679
1680    /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1681    ///
1682    /// # Examples
1683    ///
1684    /// ```
1685    /// use std::collections::BTreeSet;
1686    ///
1687    /// let a = BTreeSet::from([1, 2, 3]);
1688    /// let b = BTreeSet::from([2, 3, 4]);
1689    ///
1690    /// let result = &a ^ &b;
1691    /// assert_eq!(result, BTreeSet::from([1, 4]));
1692    /// ```
1693    fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1694        BTreeSet::from_sorted_iter(
1695            self.symmetric_difference(rhs).cloned(),
1696            ManuallyDrop::into_inner(self.map.alloc.clone()),
1697        )
1698    }
1699}
1700
1701#[stable(feature = "rust1", since = "1.0.0")]
1702impl<T: Ord + Clone, A: Allocator + Clone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1703    type Output = BTreeSet<T, A>;
1704
1705    /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1706    ///
1707    /// # Examples
1708    ///
1709    /// ```
1710    /// use std::collections::BTreeSet;
1711    ///
1712    /// let a = BTreeSet::from([1, 2, 3]);
1713    /// let b = BTreeSet::from([2, 3, 4]);
1714    ///
1715    /// let result = &a & &b;
1716    /// assert_eq!(result, BTreeSet::from([2, 3]));
1717    /// ```
1718    fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1719        BTreeSet::from_sorted_iter(
1720            self.intersection(rhs).cloned(),
1721            ManuallyDrop::into_inner(self.map.alloc.clone()),
1722        )
1723    }
1724}
1725
1726#[stable(feature = "rust1", since = "1.0.0")]
1727impl<T: Ord + Clone, A: Allocator + Clone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1728    type Output = BTreeSet<T, A>;
1729
1730    /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1731    ///
1732    /// # Examples
1733    ///
1734    /// ```
1735    /// use std::collections::BTreeSet;
1736    ///
1737    /// let a = BTreeSet::from([1, 2, 3]);
1738    /// let b = BTreeSet::from([3, 4, 5]);
1739    ///
1740    /// let result = &a | &b;
1741    /// assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5]));
1742    /// ```
1743    fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1744        BTreeSet::from_sorted_iter(
1745            self.union(rhs).cloned(),
1746            ManuallyDrop::into_inner(self.map.alloc.clone()),
1747        )
1748    }
1749}
1750
1751#[stable(feature = "rust1", since = "1.0.0")]
1752impl<T: Debug, A: Allocator + Clone> Debug for BTreeSet<T, A> {
1753    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1754        f.debug_set().entries(self.iter()).finish()
1755    }
1756}
1757
1758#[stable(feature = "rust1", since = "1.0.0")]
1759impl<T> Clone for Iter<'_, T> {
1760    fn clone(&self) -> Self {
1761        Iter { iter: self.iter.clone() }
1762    }
1763}
1764#[stable(feature = "rust1", since = "1.0.0")]
1765impl<'a, T> Iterator for Iter<'a, T> {
1766    type Item = &'a T;
1767
1768    fn next(&mut self) -> Option<&'a T> {
1769        self.iter.next()
1770    }
1771
1772    fn size_hint(&self) -> (usize, Option<usize>) {
1773        self.iter.size_hint()
1774    }
1775
1776    fn last(mut self) -> Option<&'a T> {
1777        self.next_back()
1778    }
1779
1780    fn min(mut self) -> Option<&'a T>
1781    where
1782        &'a T: Ord,
1783    {
1784        self.next()
1785    }
1786
1787    fn max(mut self) -> Option<&'a T>
1788    where
1789        &'a T: Ord,
1790    {
1791        self.next_back()
1792    }
1793}
1794#[stable(feature = "rust1", since = "1.0.0")]
1795impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1796    fn next_back(&mut self) -> Option<&'a T> {
1797        self.iter.next_back()
1798    }
1799}
1800#[stable(feature = "rust1", since = "1.0.0")]
1801impl<T> ExactSizeIterator for Iter<'_, T> {
1802    fn len(&self) -> usize {
1803        self.iter.len()
1804    }
1805}
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: Allocator + Clone> 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: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> {
1839    fn next_back(&mut self) -> Option<T> {
1840        self.iter.next_back().map(|(k, _)| k)
1841    }
1842}
1843#[stable(feature = "rust1", since = "1.0.0")]
1844impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> {
1845    fn len(&self) -> usize {
1846        self.iter.len()
1847    }
1848}
1849
1850#[stable(feature = "fused", since = "1.26.0")]
1851impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {}
1852
1853#[stable(feature = "default_iters", since = "1.70.0")]
1854impl<T, A> Default for IntoIter<T, A>
1855where
1856    A: Allocator + Default + Clone,
1857{
1858    /// Creates an empty `btree_set::IntoIter`.
1859    ///
1860    /// ```
1861    /// # use std::collections::btree_set;
1862    /// let iter: btree_set::IntoIter<u8> = Default::default();
1863    /// assert_eq!(iter.len(), 0);
1864    /// ```
1865    fn default() -> Self {
1866        IntoIter { iter: Default::default() }
1867    }
1868}
1869
1870#[stable(feature = "btree_range", since = "1.17.0")]
1871impl<T> Clone for Range<'_, T> {
1872    fn clone(&self) -> Self {
1873        Range { iter: self.iter.clone() }
1874    }
1875}
1876
1877#[stable(feature = "btree_range", since = "1.17.0")]
1878impl<'a, T> Iterator for Range<'a, T> {
1879    type Item = &'a T;
1880
1881    fn next(&mut self) -> Option<&'a T> {
1882        self.iter.next().map(|(k, _)| k)
1883    }
1884
1885    fn last(mut self) -> Option<&'a T> {
1886        self.next_back()
1887    }
1888
1889    fn min(mut self) -> Option<&'a T>
1890    where
1891        &'a T: Ord,
1892    {
1893        self.next()
1894    }
1895
1896    fn max(mut self) -> Option<&'a T>
1897    where
1898        &'a T: Ord,
1899    {
1900        self.next_back()
1901    }
1902}
1903
1904#[stable(feature = "btree_range", since = "1.17.0")]
1905impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1906    fn next_back(&mut self) -> Option<&'a T> {
1907        self.iter.next_back().map(|(k, _)| k)
1908    }
1909}
1910
1911#[stable(feature = "fused", since = "1.26.0")]
1912impl<T> FusedIterator for Range<'_, T> {}
1913
1914#[stable(feature = "default_iters", since = "1.70.0")]
1915impl<T> Default for Range<'_, T> {
1916    /// Creates an empty `btree_set::Range`.
1917    ///
1918    /// ```
1919    /// # use std::collections::btree_set;
1920    /// let iter: btree_set::Range<'_, u8> = Default::default();
1921    /// assert_eq!(iter.count(), 0);
1922    /// ```
1923    fn default() -> Self {
1924        Range { iter: Default::default() }
1925    }
1926}
1927
1928#[stable(feature = "rust1", since = "1.0.0")]
1929impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> {
1930    fn clone(&self) -> Self {
1931        Difference {
1932            inner: match &self.inner {
1933                DifferenceInner::Stitch { self_iter, other_iter } => DifferenceInner::Stitch {
1934                    self_iter: self_iter.clone(),
1935                    other_iter: other_iter.clone(),
1936                },
1937                DifferenceInner::Search { self_iter, other_set } => {
1938                    DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1939                }
1940                DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
1941            },
1942        }
1943    }
1944}
1945#[stable(feature = "rust1", since = "1.0.0")]
1946impl<'a, T: Ord, A: Allocator + Clone> Iterator for Difference<'a, T, A> {
1947    type Item = &'a T;
1948
1949    fn next(&mut self) -> Option<&'a T> {
1950        match &mut self.inner {
1951            DifferenceInner::Stitch { self_iter, other_iter } => {
1952                let mut self_next = self_iter.next()?;
1953                loop {
1954                    match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1955                        Less => return Some(self_next),
1956                        Equal => {
1957                            self_next = self_iter.next()?;
1958                            other_iter.next();
1959                        }
1960                        Greater => {
1961                            other_iter.next();
1962                        }
1963                    }
1964                }
1965            }
1966            DifferenceInner::Search { self_iter, other_set } => loop {
1967                let self_next = self_iter.next()?;
1968                if !other_set.contains(&self_next) {
1969                    return Some(self_next);
1970                }
1971            },
1972            DifferenceInner::Iterate(iter) => iter.next(),
1973        }
1974    }
1975
1976    fn size_hint(&self) -> (usize, Option<usize>) {
1977        let (self_len, other_len) = match &self.inner {
1978            DifferenceInner::Stitch { self_iter, other_iter } => {
1979                (self_iter.len(), other_iter.len())
1980            }
1981            DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1982            DifferenceInner::Iterate(iter) => (iter.len(), 0),
1983        };
1984        (self_len.saturating_sub(other_len), Some(self_len))
1985    }
1986
1987    fn min(mut self) -> Option<&'a T> {
1988        self.next()
1989    }
1990}
1991
1992#[stable(feature = "fused", since = "1.26.0")]
1993impl<T: Ord, A: Allocator + Clone> FusedIterator for Difference<'_, T, A> {}
1994
1995#[stable(feature = "rust1", since = "1.0.0")]
1996impl<T> Clone for SymmetricDifference<'_, T> {
1997    fn clone(&self) -> Self {
1998        SymmetricDifference(self.0.clone())
1999    }
2000}
2001#[stable(feature = "rust1", since = "1.0.0")]
2002impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
2003    type Item = &'a T;
2004
2005    fn next(&mut self) -> Option<&'a T> {
2006        loop {
2007            let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
2008            if a_next.and(b_next).is_none() {
2009                return a_next.or(b_next);
2010            }
2011        }
2012    }
2013
2014    fn size_hint(&self) -> (usize, Option<usize>) {
2015        let (a_len, b_len) = self.0.lens();
2016        // No checked_add, because even if a and b refer to the same set,
2017        // and T is a zero-sized type, the storage overhead of sets limits
2018        // the number of elements to less than half the range of usize.
2019        (0, Some(a_len + b_len))
2020    }
2021
2022    fn min(mut self) -> Option<&'a T> {
2023        self.next()
2024    }
2025}
2026
2027#[stable(feature = "fused", since = "1.26.0")]
2028impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
2029
2030#[stable(feature = "rust1", since = "1.0.0")]
2031impl<T, A: Allocator + Clone> Clone for Intersection<'_, T, A> {
2032    fn clone(&self) -> Self {
2033        Intersection {
2034            inner: match &self.inner {
2035                IntersectionInner::Stitch { a, b } => {
2036                    IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
2037                }
2038                IntersectionInner::Search { small_iter, large_set } => {
2039                    IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
2040                }
2041                IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
2042            },
2043        }
2044    }
2045}
2046#[stable(feature = "rust1", since = "1.0.0")]
2047impl<'a, T: Ord, A: Allocator + Clone> Iterator for Intersection<'a, T, A> {
2048    type Item = &'a T;
2049
2050    fn next(&mut self) -> Option<&'a T> {
2051        match &mut self.inner {
2052            IntersectionInner::Stitch { a, b } => {
2053                let mut a_next = a.next()?;
2054                let mut b_next = b.next()?;
2055                loop {
2056                    match a_next.cmp(b_next) {
2057                        Less => a_next = a.next()?,
2058                        Greater => b_next = b.next()?,
2059                        Equal => return Some(a_next),
2060                    }
2061                }
2062            }
2063            IntersectionInner::Search { small_iter, large_set } => loop {
2064                let small_next = small_iter.next()?;
2065                if large_set.contains(&small_next) {
2066                    return Some(small_next);
2067                }
2068            },
2069            IntersectionInner::Answer(answer) => answer.take(),
2070        }
2071    }
2072
2073    fn size_hint(&self) -> (usize, Option<usize>) {
2074        match &self.inner {
2075            IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
2076            IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
2077            IntersectionInner::Answer(None) => (0, Some(0)),
2078            IntersectionInner::Answer(Some(_)) => (1, Some(1)),
2079        }
2080    }
2081
2082    fn min(mut self) -> Option<&'a T> {
2083        self.next()
2084    }
2085}
2086
2087#[stable(feature = "fused", since = "1.26.0")]
2088impl<T: Ord, A: Allocator + Clone> FusedIterator for Intersection<'_, T, A> {}
2089
2090#[stable(feature = "rust1", since = "1.0.0")]
2091impl<T> Clone for Union<'_, T> {
2092    fn clone(&self) -> Self {
2093        Union(self.0.clone())
2094    }
2095}
2096#[stable(feature = "rust1", since = "1.0.0")]
2097impl<'a, T: Ord> Iterator for Union<'a, T> {
2098    type Item = &'a T;
2099
2100    fn next(&mut self) -> Option<&'a T> {
2101        let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
2102        a_next.or(b_next)
2103    }
2104
2105    fn size_hint(&self) -> (usize, Option<usize>) {
2106        let (a_len, b_len) = self.0.lens();
2107        // No checked_add - see SymmetricDifference::size_hint.
2108        (max(a_len, b_len), Some(a_len + b_len))
2109    }
2110
2111    fn min(mut self) -> Option<&'a T> {
2112        self.next()
2113    }
2114}
2115
2116#[stable(feature = "fused", since = "1.26.0")]
2117impl<T: Ord> FusedIterator for Union<'_, T> {}
2118
2119/// A cursor over a `BTreeSet`.
2120///
2121/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
2122///
2123/// Cursors always point to a gap between two elements in the set, and can
2124/// operate on the two immediately adjacent elements.
2125///
2126/// A `Cursor` is created with the [`BTreeSet::lower_bound`] and [`BTreeSet::upper_bound`] methods.
2127#[derive(Clone)]
2128#[unstable(feature = "btree_cursors", issue = "107540")]
2129pub struct Cursor<'a, K: 'a> {
2130    inner: super::map::Cursor<'a, K, SetValZST>,
2131}
2132
2133#[unstable(feature = "btree_cursors", issue = "107540")]
2134impl<K: Debug> Debug for Cursor<'_, K> {
2135    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2136        f.write_str("Cursor")
2137    }
2138}
2139
2140/// A cursor over a `BTreeSet` with editing operations.
2141///
2142/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2143/// safely mutate the set during iteration. This is because the lifetime of its yielded
2144/// references is tied to its own lifetime, instead of just the underlying map. This means
2145/// cursors cannot yield multiple elements at once.
2146///
2147/// Cursors always point to a gap between two elements in the set, and can
2148/// operate on the two immediately adjacent elements.
2149///
2150/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and [`BTreeSet::upper_bound_mut`]
2151/// methods.
2152#[unstable(feature = "btree_cursors", issue = "107540")]
2153pub struct CursorMut<'a, K: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
2154{
2155    inner: super::map::CursorMut<'a, K, SetValZST, A>,
2156}
2157
2158#[unstable(feature = "btree_cursors", issue = "107540")]
2159impl<K: Debug, A> Debug for CursorMut<'_, K, A> {
2160    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2161        f.write_str("CursorMut")
2162    }
2163}
2164
2165/// A cursor over a `BTreeSet` with editing operations, and which allows
2166/// mutating elements.
2167///
2168/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2169/// safely mutate the set during iteration. This is because the lifetime of its yielded
2170/// references is tied to its own lifetime, instead of just the underlying set. This means
2171/// cursors cannot yield multiple elements at once.
2172///
2173/// Cursors always point to a gap between two elements in the set, and can
2174/// operate on the two immediately adjacent elements.
2175///
2176/// A `CursorMutKey` is created from a [`CursorMut`] with the
2177/// [`CursorMut::with_mutable_key`] method.
2178///
2179/// # Safety
2180///
2181/// Since this cursor allows mutating elements, you must ensure that the
2182/// `BTreeSet` invariants are maintained. Specifically:
2183///
2184/// * The newly inserted element must be unique in the tree.
2185/// * All elements in the tree must remain in sorted order.
2186#[unstable(feature = "btree_cursors", issue = "107540")]
2187pub struct CursorMutKey<
2188    'a,
2189    K: 'a,
2190    #[unstable(feature = "allocator_api", issue = "32838")] A = Global,
2191> {
2192    inner: super::map::CursorMutKey<'a, K, SetValZST, A>,
2193}
2194
2195#[unstable(feature = "btree_cursors", issue = "107540")]
2196impl<K: Debug, A> Debug for CursorMutKey<'_, K, A> {
2197    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2198        f.write_str("CursorMutKey")
2199    }
2200}
2201
2202impl<'a, K> Cursor<'a, K> {
2203    /// Advances the cursor to the next gap, returning the element that it
2204    /// moved over.
2205    ///
2206    /// If the cursor is already at the end of the set then `None` is returned
2207    /// and the cursor is not moved.
2208    #[unstable(feature = "btree_cursors", issue = "107540")]
2209    pub fn next(&mut self) -> Option<&'a K> {
2210        self.inner.next().map(|(k, _)| k)
2211    }
2212
2213    /// Advances the cursor to the previous gap, returning the element that it
2214    /// moved over.
2215    ///
2216    /// If the cursor is already at the start of the set then `None` is returned
2217    /// and the cursor is not moved.
2218    #[unstable(feature = "btree_cursors", issue = "107540")]
2219    pub fn prev(&mut self) -> Option<&'a K> {
2220        self.inner.prev().map(|(k, _)| k)
2221    }
2222
2223    /// Returns a reference to next element without moving the cursor.
2224    ///
2225    /// If the cursor is at the end of the set then `None` is returned
2226    #[unstable(feature = "btree_cursors", issue = "107540")]
2227    pub fn peek_next(&self) -> Option<&'a K> {
2228        self.inner.peek_next().map(|(k, _)| k)
2229    }
2230
2231    /// Returns a reference to the previous element without moving the cursor.
2232    ///
2233    /// If the cursor is at the start of the set then `None` is returned.
2234    #[unstable(feature = "btree_cursors", issue = "107540")]
2235    pub fn peek_prev(&self) -> Option<&'a K> {
2236        self.inner.peek_prev().map(|(k, _)| k)
2237    }
2238}
2239
2240impl<'a, T, A> CursorMut<'a, T, A> {
2241    /// Advances the cursor to the next gap, returning the element that it
2242    /// moved over.
2243    ///
2244    /// If the cursor is already at the end of the set then `None` is returned
2245    /// and the cursor is not moved.
2246    #[unstable(feature = "btree_cursors", issue = "107540")]
2247    pub fn next(&mut self) -> Option<&T> {
2248        self.inner.next().map(|(k, _)| k)
2249    }
2250
2251    /// Advances the cursor to the previous gap, returning the element that it
2252    /// moved over.
2253    ///
2254    /// If the cursor is already at the start of the set then `None` is returned
2255    /// and the cursor is not moved.
2256    #[unstable(feature = "btree_cursors", issue = "107540")]
2257    pub fn prev(&mut self) -> Option<&T> {
2258        self.inner.prev().map(|(k, _)| k)
2259    }
2260
2261    /// Returns a reference to the next element without moving the cursor.
2262    ///
2263    /// If the cursor is at the end of the set then `None` is returned.
2264    #[unstable(feature = "btree_cursors", issue = "107540")]
2265    pub fn peek_next(&mut self) -> Option<&T> {
2266        self.inner.peek_next().map(|(k, _)| k)
2267    }
2268
2269    /// Returns a reference to the previous element without moving the cursor.
2270    ///
2271    /// If the cursor is at the start of the set then `None` is returned.
2272    #[unstable(feature = "btree_cursors", issue = "107540")]
2273    pub fn peek_prev(&mut self) -> Option<&T> {
2274        self.inner.peek_prev().map(|(k, _)| k)
2275    }
2276
2277    /// Returns a read-only cursor pointing to the same location as the
2278    /// `CursorMut`.
2279    ///
2280    /// The lifetime of the returned `Cursor` is bound to that of the
2281    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
2282    /// `CursorMut` is frozen for the lifetime of the `Cursor`.
2283    #[unstable(feature = "btree_cursors", issue = "107540")]
2284    pub fn as_cursor(&self) -> Cursor<'_, T> {
2285        Cursor { inner: self.inner.as_cursor() }
2286    }
2287
2288    /// Converts the cursor into a [`CursorMutKey`], which allows mutating
2289    /// elements in the tree.
2290    ///
2291    /// # Safety
2292    ///
2293    /// Since this cursor allows mutating elements, you must ensure that the
2294    /// `BTreeSet` invariants are maintained. Specifically:
2295    ///
2296    /// * The newly inserted element must be unique in the tree.
2297    /// * All elements in the tree must remain in sorted order.
2298    #[unstable(feature = "btree_cursors", issue = "107540")]
2299    pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, T, A> {
2300        CursorMutKey { inner: unsafe { self.inner.with_mutable_key() } }
2301    }
2302}
2303
2304impl<'a, T, A> CursorMutKey<'a, T, A> {
2305    /// Advances the cursor to the next gap, returning the  element that it
2306    /// moved over.
2307    ///
2308    /// If the cursor is already at the end of the set then `None` is returned
2309    /// and the cursor is not moved.
2310    #[unstable(feature = "btree_cursors", issue = "107540")]
2311    pub fn next(&mut self) -> Option<&mut T> {
2312        self.inner.next().map(|(k, _)| k)
2313    }
2314
2315    /// Advances the cursor to the previous gap, returning the element that it
2316    /// moved over.
2317    ///
2318    /// If the cursor is already at the start of the set then `None` is returned
2319    /// and the cursor is not moved.
2320    #[unstable(feature = "btree_cursors", issue = "107540")]
2321    pub fn prev(&mut self) -> Option<&mut T> {
2322        self.inner.prev().map(|(k, _)| k)
2323    }
2324
2325    /// Returns a reference to the next element without moving the cursor.
2326    ///
2327    /// If the cursor is at the end of the set then `None` is returned
2328    #[unstable(feature = "btree_cursors", issue = "107540")]
2329    pub fn peek_next(&mut self) -> Option<&mut T> {
2330        self.inner.peek_next().map(|(k, _)| k)
2331    }
2332
2333    /// Returns a reference to the previous element without moving the cursor.
2334    ///
2335    /// If the cursor is at the start of the set then `None` is returned.
2336    #[unstable(feature = "btree_cursors", issue = "107540")]
2337    pub fn peek_prev(&mut self) -> Option<&mut T> {
2338        self.inner.peek_prev().map(|(k, _)| k)
2339    }
2340
2341    /// Returns a read-only cursor pointing to the same location as the
2342    /// `CursorMutKey`.
2343    ///
2344    /// The lifetime of the returned `Cursor` is bound to that of the
2345    /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
2346    /// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
2347    #[unstable(feature = "btree_cursors", issue = "107540")]
2348    pub fn as_cursor(&self) -> Cursor<'_, T> {
2349        Cursor { inner: self.inner.as_cursor() }
2350    }
2351}
2352
2353impl<'a, T: Ord, A: Allocator + Clone> CursorMut<'a, T, A> {
2354    /// Inserts a new element into the set in the gap that the
2355    /// cursor is currently pointing to.
2356    ///
2357    /// After the insertion the cursor will be pointing at the gap before the
2358    /// newly inserted element.
2359    ///
2360    /// # Safety
2361    ///
2362    /// You must ensure that the `BTreeSet` invariants are maintained.
2363    /// Specifically:
2364    ///
2365    /// * The newly inserted element must be unique in the tree.
2366    /// * All elements in the tree must remain in sorted order.
2367    #[unstable(feature = "btree_cursors", issue = "107540")]
2368    pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2369        unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2370    }
2371
2372    /// Inserts a new element into the set in the gap that the
2373    /// cursor is currently pointing to.
2374    ///
2375    /// After the insertion the cursor will be pointing at the gap after the
2376    /// newly inserted element.
2377    ///
2378    /// # Safety
2379    ///
2380    /// You must ensure that the `BTreeSet` invariants are maintained.
2381    /// Specifically:
2382    ///
2383    /// * The newly inserted element must be unique in the tree.
2384    /// * All elements in the tree must remain in sorted order.
2385    #[unstable(feature = "btree_cursors", issue = "107540")]
2386    pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2387        unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2388    }
2389
2390    /// Inserts a new element into the set in the gap that the
2391    /// cursor is currently pointing to.
2392    ///
2393    /// After the insertion the cursor will be pointing at the gap before the
2394    /// newly inserted element.
2395    ///
2396    /// If the inserted element is not greater than the element before the
2397    /// cursor (if any), or if it not less than the element after the cursor (if
2398    /// any), then an [`UnorderedKeyError`] is returned since this would
2399    /// invalidate the [`Ord`] invariant between the elements of the set.
2400    #[unstable(feature = "btree_cursors", issue = "107540")]
2401    pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2402        self.inner.insert_after(value, SetValZST)
2403    }
2404
2405    /// Inserts a new element into the set in the gap that the
2406    /// cursor is currently pointing to.
2407    ///
2408    /// After the insertion the cursor will be pointing at the gap after the
2409    /// newly inserted element.
2410    ///
2411    /// If the inserted element is not greater than the element before the
2412    /// cursor (if any), or if it not less than the element after the cursor (if
2413    /// any), then an [`UnorderedKeyError`] is returned since this would
2414    /// invalidate the [`Ord`] invariant between the elements of the set.
2415    #[unstable(feature = "btree_cursors", issue = "107540")]
2416    pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2417        self.inner.insert_before(value, SetValZST)
2418    }
2419
2420    /// Removes the next element from the `BTreeSet`.
2421    ///
2422    /// The element that was removed is returned. The cursor position is
2423    /// unchanged (before the removed element).
2424    #[unstable(feature = "btree_cursors", issue = "107540")]
2425    pub fn remove_next(&mut self) -> Option<T> {
2426        self.inner.remove_next().map(|(k, _)| k)
2427    }
2428
2429    /// Removes the preceding element from the `BTreeSet`.
2430    ///
2431    /// The element that was removed is returned. The cursor position is
2432    /// unchanged (after the removed element).
2433    #[unstable(feature = "btree_cursors", issue = "107540")]
2434    pub fn remove_prev(&mut self) -> Option<T> {
2435        self.inner.remove_prev().map(|(k, _)| k)
2436    }
2437}
2438
2439impl<'a, T: Ord, A: Allocator + Clone> CursorMutKey<'a, T, A> {
2440    /// Inserts a new element into the set in the gap that the
2441    /// cursor is currently pointing to.
2442    ///
2443    /// After the insertion the cursor will be pointing at the gap before the
2444    /// newly inserted element.
2445    ///
2446    /// # Safety
2447    ///
2448    /// You must ensure that the `BTreeSet` invariants are maintained.
2449    /// Specifically:
2450    ///
2451    /// * The key of the newly inserted element must be unique in the tree.
2452    /// * All elements in the tree must remain in sorted order.
2453    #[unstable(feature = "btree_cursors", issue = "107540")]
2454    pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2455        unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2456    }
2457
2458    /// Inserts a new element into the set in the gap that the
2459    /// cursor is currently pointing to.
2460    ///
2461    /// After the insertion the cursor will be pointing at the gap after the
2462    /// newly inserted element.
2463    ///
2464    /// # Safety
2465    ///
2466    /// You must ensure that the `BTreeSet` invariants are maintained.
2467    /// Specifically:
2468    ///
2469    /// * The newly inserted element must be unique in the tree.
2470    /// * All elements in the tree must remain in sorted order.
2471    #[unstable(feature = "btree_cursors", issue = "107540")]
2472    pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2473        unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2474    }
2475
2476    /// Inserts a new element into the set in the gap that the
2477    /// cursor is currently pointing to.
2478    ///
2479    /// After the insertion the cursor will be pointing at the gap before the
2480    /// newly inserted element.
2481    ///
2482    /// If the inserted element is not greater than the element before the
2483    /// cursor (if any), or if it not less than the element after the cursor (if
2484    /// any), then an [`UnorderedKeyError`] is returned since this would
2485    /// invalidate the [`Ord`] invariant between the elements of the set.
2486    #[unstable(feature = "btree_cursors", issue = "107540")]
2487    pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2488        self.inner.insert_after(value, SetValZST)
2489    }
2490
2491    /// Inserts a new element into the set in the gap that the
2492    /// cursor is currently pointing to.
2493    ///
2494    /// After the insertion the cursor will be pointing at the gap after the
2495    /// newly inserted element.
2496    ///
2497    /// If the inserted element is not greater than the element before the
2498    /// cursor (if any), or if it not less than the element after the cursor (if
2499    /// any), then an [`UnorderedKeyError`] is returned since this would
2500    /// invalidate the [`Ord`] invariant between the elements of the set.
2501    #[unstable(feature = "btree_cursors", issue = "107540")]
2502    pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2503        self.inner.insert_before(value, SetValZST)
2504    }
2505
2506    /// Removes the next element from the `BTreeSet`.
2507    ///
2508    /// The element that was removed is returned. The cursor position is
2509    /// unchanged (before the removed element).
2510    #[unstable(feature = "btree_cursors", issue = "107540")]
2511    pub fn remove_next(&mut self) -> Option<T> {
2512        self.inner.remove_next().map(|(k, _)| k)
2513    }
2514
2515    /// Removes the preceding element from the `BTreeSet`.
2516    ///
2517    /// The element that was removed is returned. The cursor position is
2518    /// unchanged (after the removed element).
2519    #[unstable(feature = "btree_cursors", issue = "107540")]
2520    pub fn remove_prev(&mut self) -> Option<T> {
2521        self.inner.remove_prev().map(|(k, _)| k)
2522    }
2523}
2524
2525#[unstable(feature = "btree_cursors", issue = "107540")]
2526pub use super::map::UnorderedKeyError;
2527
2528#[cfg(test)]
2529mod tests;