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.clone()).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 all elements 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    /// Splitting a set into even and odd values, reusing the original set:
1205    ///
1206    /// ```
1207    /// #![feature(btree_extract_if)]
1208    /// use std::collections::BTreeSet;
1209    ///
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    #[unstable(feature = "btree_extract_if", issue = "70530")]
1217    pub fn extract_if<'a, F>(&'a mut self, pred: F) -> ExtractIf<'a, T, F, A>
1218    where
1219        T: Ord,
1220        F: 'a + FnMut(&T) -> bool,
1221    {
1222        let (inner, alloc) = self.map.extract_if_inner();
1223        ExtractIf { pred, inner, alloc }
1224    }
1225
1226    /// Gets an iterator that visits the elements in the `BTreeSet` in ascending
1227    /// order.
1228    ///
1229    /// # Examples
1230    ///
1231    /// ```
1232    /// use std::collections::BTreeSet;
1233    ///
1234    /// let set = BTreeSet::from([3, 1, 2]);
1235    /// let mut set_iter = set.iter();
1236    /// assert_eq!(set_iter.next(), Some(&1));
1237    /// assert_eq!(set_iter.next(), Some(&2));
1238    /// assert_eq!(set_iter.next(), Some(&3));
1239    /// assert_eq!(set_iter.next(), None);
1240    /// ```
1241    #[stable(feature = "rust1", since = "1.0.0")]
1242    #[cfg_attr(not(test), rustc_diagnostic_item = "btreeset_iter")]
1243    pub fn iter(&self) -> Iter<'_, T> {
1244        Iter { iter: self.map.keys() }
1245    }
1246
1247    /// Returns the number of elements in the set.
1248    ///
1249    /// # Examples
1250    ///
1251    /// ```
1252    /// use std::collections::BTreeSet;
1253    ///
1254    /// let mut v = BTreeSet::new();
1255    /// assert_eq!(v.len(), 0);
1256    /// v.insert(1);
1257    /// assert_eq!(v.len(), 1);
1258    /// ```
1259    #[must_use]
1260    #[stable(feature = "rust1", since = "1.0.0")]
1261    #[rustc_const_unstable(
1262        feature = "const_btree_len",
1263        issue = "71835",
1264        implied_by = "const_btree_new"
1265    )]
1266    #[rustc_confusables("length", "size")]
1267    pub const fn len(&self) -> usize {
1268        self.map.len()
1269    }
1270
1271    /// Returns `true` if the set contains no elements.
1272    ///
1273    /// # Examples
1274    ///
1275    /// ```
1276    /// use std::collections::BTreeSet;
1277    ///
1278    /// let mut v = BTreeSet::new();
1279    /// assert!(v.is_empty());
1280    /// v.insert(1);
1281    /// assert!(!v.is_empty());
1282    /// ```
1283    #[must_use]
1284    #[stable(feature = "rust1", since = "1.0.0")]
1285    #[rustc_const_unstable(
1286        feature = "const_btree_len",
1287        issue = "71835",
1288        implied_by = "const_btree_new"
1289    )]
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: Allocator + Clone> 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::default()));
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        let iter = IntoIterator::into_iter(arr).map(|k| (k, SetValZST::default()));
1514        let map = BTreeMap::bulk_build_from_sorted_iter(iter, Global);
1515        BTreeSet { map }
1516    }
1517}
1518
1519#[stable(feature = "rust1", since = "1.0.0")]
1520impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> {
1521    type Item = T;
1522    type IntoIter = IntoIter<T, A>;
1523
1524    /// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order.
1525    ///
1526    /// # Examples
1527    ///
1528    /// ```
1529    /// use std::collections::BTreeSet;
1530    ///
1531    /// let set = BTreeSet::from([1, 2, 3, 4]);
1532    ///
1533    /// let v: Vec<_> = set.into_iter().collect();
1534    /// assert_eq!(v, [1, 2, 3, 4]);
1535    /// ```
1536    fn into_iter(self) -> IntoIter<T, A> {
1537        IntoIter { iter: self.map.into_iter() }
1538    }
1539}
1540
1541#[stable(feature = "rust1", since = "1.0.0")]
1542impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> {
1543    type Item = &'a T;
1544    type IntoIter = Iter<'a, T>;
1545
1546    fn into_iter(self) -> Iter<'a, T> {
1547        self.iter()
1548    }
1549}
1550
1551/// An iterator produced by calling `extract_if` on BTreeSet.
1552#[unstable(feature = "btree_extract_if", issue = "70530")]
1553#[must_use = "iterators are lazy and do nothing unless consumed"]
1554pub struct ExtractIf<
1555    'a,
1556    T,
1557    F,
1558    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1559> where
1560    T: 'a,
1561    F: 'a + FnMut(&T) -> bool,
1562{
1563    pred: F,
1564    inner: super::map::ExtractIfInner<'a, T, SetValZST>,
1565    /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1566    alloc: A,
1567}
1568
1569#[unstable(feature = "btree_extract_if", issue = "70530")]
1570impl<T, F, A: Allocator + Clone> fmt::Debug for ExtractIf<'_, T, F, A>
1571where
1572    T: fmt::Debug,
1573    F: FnMut(&T) -> bool,
1574{
1575    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1576        f.debug_tuple("ExtractIf").field(&self.inner.peek().map(|(k, _)| k)).finish()
1577    }
1578}
1579
1580#[unstable(feature = "btree_extract_if", issue = "70530")]
1581impl<'a, T, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, F, A>
1582where
1583    F: 'a + FnMut(&T) -> bool,
1584{
1585    type Item = T;
1586
1587    fn next(&mut self) -> Option<T> {
1588        let pred = &mut self.pred;
1589        let mut mapped_pred = |k: &T, _v: &mut SetValZST| pred(k);
1590        self.inner.next(&mut mapped_pred, self.alloc.clone()).map(|(k, _)| k)
1591    }
1592
1593    fn size_hint(&self) -> (usize, Option<usize>) {
1594        self.inner.size_hint()
1595    }
1596}
1597
1598#[unstable(feature = "btree_extract_if", issue = "70530")]
1599impl<T, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&T) -> bool {}
1600
1601#[stable(feature = "rust1", since = "1.0.0")]
1602impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> {
1603    #[inline]
1604    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1605        iter.into_iter().for_each(move |elem| {
1606            self.insert(elem);
1607        });
1608    }
1609
1610    #[inline]
1611    fn extend_one(&mut self, elem: T) {
1612        self.insert(elem);
1613    }
1614}
1615
1616#[stable(feature = "extend_ref", since = "1.2.0")]
1617impl<'a, T: 'a + Ord + Copy, A: Allocator + Clone> Extend<&'a T> for BTreeSet<T, A> {
1618    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1619        self.extend(iter.into_iter().cloned());
1620    }
1621
1622    #[inline]
1623    fn extend_one(&mut self, &elem: &'a T) {
1624        self.insert(elem);
1625    }
1626}
1627
1628#[stable(feature = "rust1", since = "1.0.0")]
1629impl<T> Default for BTreeSet<T> {
1630    /// Creates an empty `BTreeSet`.
1631    fn default() -> BTreeSet<T> {
1632        BTreeSet::new()
1633    }
1634}
1635
1636#[stable(feature = "rust1", since = "1.0.0")]
1637impl<T: Ord + Clone, A: Allocator + Clone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1638    type Output = BTreeSet<T, A>;
1639
1640    /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1641    ///
1642    /// # Examples
1643    ///
1644    /// ```
1645    /// use std::collections::BTreeSet;
1646    ///
1647    /// let a = BTreeSet::from([1, 2, 3]);
1648    /// let b = BTreeSet::from([3, 4, 5]);
1649    ///
1650    /// let result = &a - &b;
1651    /// assert_eq!(result, BTreeSet::from([1, 2]));
1652    /// ```
1653    fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1654        BTreeSet::from_sorted_iter(
1655            self.difference(rhs).cloned(),
1656            ManuallyDrop::into_inner(self.map.alloc.clone()),
1657        )
1658    }
1659}
1660
1661#[stable(feature = "rust1", since = "1.0.0")]
1662impl<T: Ord + Clone, A: Allocator + Clone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1663    type Output = BTreeSet<T, A>;
1664
1665    /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1666    ///
1667    /// # Examples
1668    ///
1669    /// ```
1670    /// use std::collections::BTreeSet;
1671    ///
1672    /// let a = BTreeSet::from([1, 2, 3]);
1673    /// let b = BTreeSet::from([2, 3, 4]);
1674    ///
1675    /// let result = &a ^ &b;
1676    /// assert_eq!(result, BTreeSet::from([1, 4]));
1677    /// ```
1678    fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1679        BTreeSet::from_sorted_iter(
1680            self.symmetric_difference(rhs).cloned(),
1681            ManuallyDrop::into_inner(self.map.alloc.clone()),
1682        )
1683    }
1684}
1685
1686#[stable(feature = "rust1", since = "1.0.0")]
1687impl<T: Ord + Clone, A: Allocator + Clone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1688    type Output = BTreeSet<T, A>;
1689
1690    /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1691    ///
1692    /// # Examples
1693    ///
1694    /// ```
1695    /// use std::collections::BTreeSet;
1696    ///
1697    /// let a = BTreeSet::from([1, 2, 3]);
1698    /// let b = BTreeSet::from([2, 3, 4]);
1699    ///
1700    /// let result = &a & &b;
1701    /// assert_eq!(result, BTreeSet::from([2, 3]));
1702    /// ```
1703    fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1704        BTreeSet::from_sorted_iter(
1705            self.intersection(rhs).cloned(),
1706            ManuallyDrop::into_inner(self.map.alloc.clone()),
1707        )
1708    }
1709}
1710
1711#[stable(feature = "rust1", since = "1.0.0")]
1712impl<T: Ord + Clone, A: Allocator + Clone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1713    type Output = BTreeSet<T, A>;
1714
1715    /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1716    ///
1717    /// # Examples
1718    ///
1719    /// ```
1720    /// use std::collections::BTreeSet;
1721    ///
1722    /// let a = BTreeSet::from([1, 2, 3]);
1723    /// let b = BTreeSet::from([3, 4, 5]);
1724    ///
1725    /// let result = &a | &b;
1726    /// assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5]));
1727    /// ```
1728    fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1729        BTreeSet::from_sorted_iter(
1730            self.union(rhs).cloned(),
1731            ManuallyDrop::into_inner(self.map.alloc.clone()),
1732        )
1733    }
1734}
1735
1736#[stable(feature = "rust1", since = "1.0.0")]
1737impl<T: Debug, A: Allocator + Clone> Debug for BTreeSet<T, A> {
1738    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1739        f.debug_set().entries(self.iter()).finish()
1740    }
1741}
1742
1743#[stable(feature = "rust1", since = "1.0.0")]
1744impl<T> Clone for Iter<'_, T> {
1745    fn clone(&self) -> Self {
1746        Iter { iter: self.iter.clone() }
1747    }
1748}
1749#[stable(feature = "rust1", since = "1.0.0")]
1750impl<'a, T> Iterator for Iter<'a, T> {
1751    type Item = &'a T;
1752
1753    fn next(&mut self) -> Option<&'a T> {
1754        self.iter.next()
1755    }
1756
1757    fn size_hint(&self) -> (usize, Option<usize>) {
1758        self.iter.size_hint()
1759    }
1760
1761    fn last(mut self) -> Option<&'a T> {
1762        self.next_back()
1763    }
1764
1765    fn min(mut self) -> Option<&'a T>
1766    where
1767        &'a T: Ord,
1768    {
1769        self.next()
1770    }
1771
1772    fn max(mut self) -> Option<&'a T>
1773    where
1774        &'a T: Ord,
1775    {
1776        self.next_back()
1777    }
1778}
1779#[stable(feature = "rust1", since = "1.0.0")]
1780impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1781    fn next_back(&mut self) -> Option<&'a T> {
1782        self.iter.next_back()
1783    }
1784}
1785#[stable(feature = "rust1", since = "1.0.0")]
1786impl<T> ExactSizeIterator for Iter<'_, T> {
1787    fn len(&self) -> usize {
1788        self.iter.len()
1789    }
1790}
1791
1792#[stable(feature = "fused", since = "1.26.0")]
1793impl<T> FusedIterator for Iter<'_, T> {}
1794
1795#[stable(feature = "rust1", since = "1.0.0")]
1796impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> {
1797    type Item = T;
1798
1799    fn next(&mut self) -> Option<T> {
1800        self.iter.next().map(|(k, _)| k)
1801    }
1802
1803    fn size_hint(&self) -> (usize, Option<usize>) {
1804        self.iter.size_hint()
1805    }
1806}
1807
1808#[stable(feature = "default_iters", since = "1.70.0")]
1809impl<T> Default for Iter<'_, T> {
1810    /// Creates an empty `btree_set::Iter`.
1811    ///
1812    /// ```
1813    /// # use std::collections::btree_set;
1814    /// let iter: btree_set::Iter<'_, u8> = Default::default();
1815    /// assert_eq!(iter.len(), 0);
1816    /// ```
1817    fn default() -> Self {
1818        Iter { iter: Default::default() }
1819    }
1820}
1821
1822#[stable(feature = "rust1", since = "1.0.0")]
1823impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> {
1824    fn next_back(&mut self) -> Option<T> {
1825        self.iter.next_back().map(|(k, _)| k)
1826    }
1827}
1828#[stable(feature = "rust1", since = "1.0.0")]
1829impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> {
1830    fn len(&self) -> usize {
1831        self.iter.len()
1832    }
1833}
1834
1835#[stable(feature = "fused", since = "1.26.0")]
1836impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {}
1837
1838#[stable(feature = "default_iters", since = "1.70.0")]
1839impl<T, A> Default for IntoIter<T, A>
1840where
1841    A: Allocator + Default + Clone,
1842{
1843    /// Creates an empty `btree_set::IntoIter`.
1844    ///
1845    /// ```
1846    /// # use std::collections::btree_set;
1847    /// let iter: btree_set::IntoIter<u8> = Default::default();
1848    /// assert_eq!(iter.len(), 0);
1849    /// ```
1850    fn default() -> Self {
1851        IntoIter { iter: Default::default() }
1852    }
1853}
1854
1855#[stable(feature = "btree_range", since = "1.17.0")]
1856impl<T> Clone for Range<'_, T> {
1857    fn clone(&self) -> Self {
1858        Range { iter: self.iter.clone() }
1859    }
1860}
1861
1862#[stable(feature = "btree_range", since = "1.17.0")]
1863impl<'a, T> Iterator for Range<'a, T> {
1864    type Item = &'a T;
1865
1866    fn next(&mut self) -> Option<&'a T> {
1867        self.iter.next().map(|(k, _)| k)
1868    }
1869
1870    fn last(mut self) -> Option<&'a T> {
1871        self.next_back()
1872    }
1873
1874    fn min(mut self) -> Option<&'a T>
1875    where
1876        &'a T: Ord,
1877    {
1878        self.next()
1879    }
1880
1881    fn max(mut self) -> Option<&'a T>
1882    where
1883        &'a T: Ord,
1884    {
1885        self.next_back()
1886    }
1887}
1888
1889#[stable(feature = "btree_range", since = "1.17.0")]
1890impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1891    fn next_back(&mut self) -> Option<&'a T> {
1892        self.iter.next_back().map(|(k, _)| k)
1893    }
1894}
1895
1896#[stable(feature = "fused", since = "1.26.0")]
1897impl<T> FusedIterator for Range<'_, T> {}
1898
1899#[stable(feature = "default_iters", since = "1.70.0")]
1900impl<T> Default for Range<'_, T> {
1901    /// Creates an empty `btree_set::Range`.
1902    ///
1903    /// ```
1904    /// # use std::collections::btree_set;
1905    /// let iter: btree_set::Range<'_, u8> = Default::default();
1906    /// assert_eq!(iter.count(), 0);
1907    /// ```
1908    fn default() -> Self {
1909        Range { iter: Default::default() }
1910    }
1911}
1912
1913#[stable(feature = "rust1", since = "1.0.0")]
1914impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> {
1915    fn clone(&self) -> Self {
1916        Difference {
1917            inner: match &self.inner {
1918                DifferenceInner::Stitch { self_iter, other_iter } => DifferenceInner::Stitch {
1919                    self_iter: self_iter.clone(),
1920                    other_iter: other_iter.clone(),
1921                },
1922                DifferenceInner::Search { self_iter, other_set } => {
1923                    DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1924                }
1925                DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
1926            },
1927        }
1928    }
1929}
1930#[stable(feature = "rust1", since = "1.0.0")]
1931impl<'a, T: Ord, A: Allocator + Clone> Iterator for Difference<'a, T, A> {
1932    type Item = &'a T;
1933
1934    fn next(&mut self) -> Option<&'a T> {
1935        match &mut self.inner {
1936            DifferenceInner::Stitch { self_iter, other_iter } => {
1937                let mut self_next = self_iter.next()?;
1938                loop {
1939                    match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1940                        Less => return Some(self_next),
1941                        Equal => {
1942                            self_next = self_iter.next()?;
1943                            other_iter.next();
1944                        }
1945                        Greater => {
1946                            other_iter.next();
1947                        }
1948                    }
1949                }
1950            }
1951            DifferenceInner::Search { self_iter, other_set } => loop {
1952                let self_next = self_iter.next()?;
1953                if !other_set.contains(&self_next) {
1954                    return Some(self_next);
1955                }
1956            },
1957            DifferenceInner::Iterate(iter) => iter.next(),
1958        }
1959    }
1960
1961    fn size_hint(&self) -> (usize, Option<usize>) {
1962        let (self_len, other_len) = match &self.inner {
1963            DifferenceInner::Stitch { self_iter, other_iter } => {
1964                (self_iter.len(), other_iter.len())
1965            }
1966            DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1967            DifferenceInner::Iterate(iter) => (iter.len(), 0),
1968        };
1969        (self_len.saturating_sub(other_len), Some(self_len))
1970    }
1971
1972    fn min(mut self) -> Option<&'a T> {
1973        self.next()
1974    }
1975}
1976
1977#[stable(feature = "fused", since = "1.26.0")]
1978impl<T: Ord, A: Allocator + Clone> FusedIterator for Difference<'_, T, A> {}
1979
1980#[stable(feature = "rust1", since = "1.0.0")]
1981impl<T> Clone for SymmetricDifference<'_, T> {
1982    fn clone(&self) -> Self {
1983        SymmetricDifference(self.0.clone())
1984    }
1985}
1986#[stable(feature = "rust1", since = "1.0.0")]
1987impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
1988    type Item = &'a T;
1989
1990    fn next(&mut self) -> Option<&'a T> {
1991        loop {
1992            let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
1993            if a_next.and(b_next).is_none() {
1994                return a_next.or(b_next);
1995            }
1996        }
1997    }
1998
1999    fn size_hint(&self) -> (usize, Option<usize>) {
2000        let (a_len, b_len) = self.0.lens();
2001        // No checked_add, because even if a and b refer to the same set,
2002        // and T is a zero-sized type, the storage overhead of sets limits
2003        // the number of elements to less than half the range of usize.
2004        (0, Some(a_len + b_len))
2005    }
2006
2007    fn min(mut self) -> Option<&'a T> {
2008        self.next()
2009    }
2010}
2011
2012#[stable(feature = "fused", since = "1.26.0")]
2013impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
2014
2015#[stable(feature = "rust1", since = "1.0.0")]
2016impl<T, A: Allocator + Clone> Clone for Intersection<'_, T, A> {
2017    fn clone(&self) -> Self {
2018        Intersection {
2019            inner: match &self.inner {
2020                IntersectionInner::Stitch { a, b } => {
2021                    IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
2022                }
2023                IntersectionInner::Search { small_iter, large_set } => {
2024                    IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
2025                }
2026                IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
2027            },
2028        }
2029    }
2030}
2031#[stable(feature = "rust1", since = "1.0.0")]
2032impl<'a, T: Ord, A: Allocator + Clone> Iterator for Intersection<'a, T, A> {
2033    type Item = &'a T;
2034
2035    fn next(&mut self) -> Option<&'a T> {
2036        match &mut self.inner {
2037            IntersectionInner::Stitch { a, b } => {
2038                let mut a_next = a.next()?;
2039                let mut b_next = b.next()?;
2040                loop {
2041                    match a_next.cmp(b_next) {
2042                        Less => a_next = a.next()?,
2043                        Greater => b_next = b.next()?,
2044                        Equal => return Some(a_next),
2045                    }
2046                }
2047            }
2048            IntersectionInner::Search { small_iter, large_set } => loop {
2049                let small_next = small_iter.next()?;
2050                if large_set.contains(&small_next) {
2051                    return Some(small_next);
2052                }
2053            },
2054            IntersectionInner::Answer(answer) => answer.take(),
2055        }
2056    }
2057
2058    fn size_hint(&self) -> (usize, Option<usize>) {
2059        match &self.inner {
2060            IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
2061            IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
2062            IntersectionInner::Answer(None) => (0, Some(0)),
2063            IntersectionInner::Answer(Some(_)) => (1, Some(1)),
2064        }
2065    }
2066
2067    fn min(mut self) -> Option<&'a T> {
2068        self.next()
2069    }
2070}
2071
2072#[stable(feature = "fused", since = "1.26.0")]
2073impl<T: Ord, A: Allocator + Clone> FusedIterator for Intersection<'_, T, A> {}
2074
2075#[stable(feature = "rust1", since = "1.0.0")]
2076impl<T> Clone for Union<'_, T> {
2077    fn clone(&self) -> Self {
2078        Union(self.0.clone())
2079    }
2080}
2081#[stable(feature = "rust1", since = "1.0.0")]
2082impl<'a, T: Ord> Iterator for Union<'a, T> {
2083    type Item = &'a T;
2084
2085    fn next(&mut self) -> Option<&'a T> {
2086        let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
2087        a_next.or(b_next)
2088    }
2089
2090    fn size_hint(&self) -> (usize, Option<usize>) {
2091        let (a_len, b_len) = self.0.lens();
2092        // No checked_add - see SymmetricDifference::size_hint.
2093        (max(a_len, b_len), Some(a_len + b_len))
2094    }
2095
2096    fn min(mut self) -> Option<&'a T> {
2097        self.next()
2098    }
2099}
2100
2101#[stable(feature = "fused", since = "1.26.0")]
2102impl<T: Ord> FusedIterator for Union<'_, T> {}
2103
2104/// A cursor over a `BTreeSet`.
2105///
2106/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
2107///
2108/// Cursors always point to a gap between two elements in the set, and can
2109/// operate on the two immediately adjacent elements.
2110///
2111/// A `Cursor` is created with the [`BTreeSet::lower_bound`] and [`BTreeSet::upper_bound`] methods.
2112#[derive(Clone)]
2113#[unstable(feature = "btree_cursors", issue = "107540")]
2114pub struct Cursor<'a, K: 'a> {
2115    inner: super::map::Cursor<'a, K, SetValZST>,
2116}
2117
2118#[unstable(feature = "btree_cursors", issue = "107540")]
2119impl<K: Debug> Debug for Cursor<'_, K> {
2120    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2121        f.write_str("Cursor")
2122    }
2123}
2124
2125/// A cursor over a `BTreeSet` with editing operations.
2126///
2127/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2128/// safely mutate the set during iteration. This is because the lifetime of its yielded
2129/// references is tied to its own lifetime, instead of just the underlying map. This means
2130/// cursors cannot yield multiple elements at once.
2131///
2132/// Cursors always point to a gap between two elements in the set, and can
2133/// operate on the two immediately adjacent elements.
2134///
2135/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and [`BTreeSet::upper_bound_mut`]
2136/// methods.
2137#[unstable(feature = "btree_cursors", issue = "107540")]
2138pub struct CursorMut<'a, K: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
2139{
2140    inner: super::map::CursorMut<'a, K, SetValZST, A>,
2141}
2142
2143#[unstable(feature = "btree_cursors", issue = "107540")]
2144impl<K: Debug, A> Debug for CursorMut<'_, K, A> {
2145    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2146        f.write_str("CursorMut")
2147    }
2148}
2149
2150/// A cursor over a `BTreeSet` with editing operations, and which allows
2151/// mutating elements.
2152///
2153/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2154/// safely mutate the set during iteration. This is because the lifetime of its yielded
2155/// references is tied to its own lifetime, instead of just the underlying set. This means
2156/// cursors cannot yield multiple elements at once.
2157///
2158/// Cursors always point to a gap between two elements in the set, and can
2159/// operate on the two immediately adjacent elements.
2160///
2161/// A `CursorMutKey` is created from a [`CursorMut`] with the
2162/// [`CursorMut::with_mutable_key`] method.
2163///
2164/// # Safety
2165///
2166/// Since this cursor allows mutating elements, you must ensure that the
2167/// `BTreeSet` invariants are maintained. Specifically:
2168///
2169/// * The newly inserted element must be unique in the tree.
2170/// * All elements in the tree must remain in sorted order.
2171#[unstable(feature = "btree_cursors", issue = "107540")]
2172pub struct CursorMutKey<
2173    'a,
2174    K: 'a,
2175    #[unstable(feature = "allocator_api", issue = "32838")] A = Global,
2176> {
2177    inner: super::map::CursorMutKey<'a, K, SetValZST, A>,
2178}
2179
2180#[unstable(feature = "btree_cursors", issue = "107540")]
2181impl<K: Debug, A> Debug for CursorMutKey<'_, K, A> {
2182    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2183        f.write_str("CursorMutKey")
2184    }
2185}
2186
2187impl<'a, K> Cursor<'a, K> {
2188    /// Advances the cursor to the next gap, returning the element that it
2189    /// moved over.
2190    ///
2191    /// If the cursor is already at the end of the set then `None` is returned
2192    /// and the cursor is not moved.
2193    #[unstable(feature = "btree_cursors", issue = "107540")]
2194    pub fn next(&mut self) -> Option<&'a K> {
2195        self.inner.next().map(|(k, _)| k)
2196    }
2197
2198    /// Advances the cursor to the previous gap, returning the element that it
2199    /// moved over.
2200    ///
2201    /// If the cursor is already at the start of the set then `None` is returned
2202    /// and the cursor is not moved.
2203    #[unstable(feature = "btree_cursors", issue = "107540")]
2204    pub fn prev(&mut self) -> Option<&'a K> {
2205        self.inner.prev().map(|(k, _)| k)
2206    }
2207
2208    /// Returns a reference to next element without moving the cursor.
2209    ///
2210    /// If the cursor is at the end of the set then `None` is returned
2211    #[unstable(feature = "btree_cursors", issue = "107540")]
2212    pub fn peek_next(&self) -> Option<&'a K> {
2213        self.inner.peek_next().map(|(k, _)| k)
2214    }
2215
2216    /// Returns a reference to the previous element without moving the cursor.
2217    ///
2218    /// If the cursor is at the start of the set then `None` is returned.
2219    #[unstable(feature = "btree_cursors", issue = "107540")]
2220    pub fn peek_prev(&self) -> Option<&'a K> {
2221        self.inner.peek_prev().map(|(k, _)| k)
2222    }
2223}
2224
2225impl<'a, T, A> CursorMut<'a, T, A> {
2226    /// Advances the cursor to the next gap, returning the element that it
2227    /// moved over.
2228    ///
2229    /// If the cursor is already at the end of the set then `None` is returned
2230    /// and the cursor is not moved.
2231    #[unstable(feature = "btree_cursors", issue = "107540")]
2232    pub fn next(&mut self) -> Option<&T> {
2233        self.inner.next().map(|(k, _)| k)
2234    }
2235
2236    /// Advances the cursor to the previous gap, returning the element that it
2237    /// moved over.
2238    ///
2239    /// If the cursor is already at the start of the set then `None` is returned
2240    /// and the cursor is not moved.
2241    #[unstable(feature = "btree_cursors", issue = "107540")]
2242    pub fn prev(&mut self) -> Option<&T> {
2243        self.inner.prev().map(|(k, _)| k)
2244    }
2245
2246    /// Returns a reference to the next element without moving the cursor.
2247    ///
2248    /// If the cursor is at the end of the set then `None` is returned.
2249    #[unstable(feature = "btree_cursors", issue = "107540")]
2250    pub fn peek_next(&mut self) -> Option<&T> {
2251        self.inner.peek_next().map(|(k, _)| k)
2252    }
2253
2254    /// Returns a reference to the previous element without moving the cursor.
2255    ///
2256    /// If the cursor is at the start of the set then `None` is returned.
2257    #[unstable(feature = "btree_cursors", issue = "107540")]
2258    pub fn peek_prev(&mut self) -> Option<&T> {
2259        self.inner.peek_prev().map(|(k, _)| k)
2260    }
2261
2262    /// Returns a read-only cursor pointing to the same location as the
2263    /// `CursorMut`.
2264    ///
2265    /// The lifetime of the returned `Cursor` is bound to that of the
2266    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
2267    /// `CursorMut` is frozen for the lifetime of the `Cursor`.
2268    #[unstable(feature = "btree_cursors", issue = "107540")]
2269    pub fn as_cursor(&self) -> Cursor<'_, T> {
2270        Cursor { inner: self.inner.as_cursor() }
2271    }
2272
2273    /// Converts the cursor into a [`CursorMutKey`], which allows mutating
2274    /// elements in the tree.
2275    ///
2276    /// # Safety
2277    ///
2278    /// Since this cursor allows mutating elements, you must ensure that the
2279    /// `BTreeSet` invariants are maintained. Specifically:
2280    ///
2281    /// * The newly inserted element must be unique in the tree.
2282    /// * All elements in the tree must remain in sorted order.
2283    #[unstable(feature = "btree_cursors", issue = "107540")]
2284    pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, T, A> {
2285        CursorMutKey { inner: unsafe { self.inner.with_mutable_key() } }
2286    }
2287}
2288
2289impl<'a, T, A> CursorMutKey<'a, T, A> {
2290    /// Advances the cursor to the next gap, returning the  element that it
2291    /// moved over.
2292    ///
2293    /// If the cursor is already at the end of the set then `None` is returned
2294    /// and the cursor is not moved.
2295    #[unstable(feature = "btree_cursors", issue = "107540")]
2296    pub fn next(&mut self) -> Option<&mut T> {
2297        self.inner.next().map(|(k, _)| k)
2298    }
2299
2300    /// Advances the cursor to the previous gap, returning the element that it
2301    /// moved over.
2302    ///
2303    /// If the cursor is already at the start of the set then `None` is returned
2304    /// and the cursor is not moved.
2305    #[unstable(feature = "btree_cursors", issue = "107540")]
2306    pub fn prev(&mut self) -> Option<&mut T> {
2307        self.inner.prev().map(|(k, _)| k)
2308    }
2309
2310    /// Returns a reference to the next element without moving the cursor.
2311    ///
2312    /// If the cursor is at the end of the set then `None` is returned
2313    #[unstable(feature = "btree_cursors", issue = "107540")]
2314    pub fn peek_next(&mut self) -> Option<&mut T> {
2315        self.inner.peek_next().map(|(k, _)| k)
2316    }
2317
2318    /// Returns a reference to the previous element without moving the cursor.
2319    ///
2320    /// If the cursor is at the start of the set then `None` is returned.
2321    #[unstable(feature = "btree_cursors", issue = "107540")]
2322    pub fn peek_prev(&mut self) -> Option<&mut T> {
2323        self.inner.peek_prev().map(|(k, _)| k)
2324    }
2325
2326    /// Returns a read-only cursor pointing to the same location as the
2327    /// `CursorMutKey`.
2328    ///
2329    /// The lifetime of the returned `Cursor` is bound to that of the
2330    /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
2331    /// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
2332    #[unstable(feature = "btree_cursors", issue = "107540")]
2333    pub fn as_cursor(&self) -> Cursor<'_, T> {
2334        Cursor { inner: self.inner.as_cursor() }
2335    }
2336}
2337
2338impl<'a, T: Ord, A: Allocator + Clone> CursorMut<'a, T, A> {
2339    /// Inserts a new element into the set in the gap that the
2340    /// cursor is currently pointing to.
2341    ///
2342    /// After the insertion the cursor will be pointing at the gap before the
2343    /// newly inserted element.
2344    ///
2345    /// # Safety
2346    ///
2347    /// You must ensure that the `BTreeSet` invariants are maintained.
2348    /// Specifically:
2349    ///
2350    /// * The newly inserted element must be unique in the tree.
2351    /// * All elements in the tree must remain in sorted order.
2352    #[unstable(feature = "btree_cursors", issue = "107540")]
2353    pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2354        unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2355    }
2356
2357    /// Inserts a new element into the set in the gap that the
2358    /// cursor is currently pointing to.
2359    ///
2360    /// After the insertion the cursor will be pointing at the gap after the
2361    /// newly inserted element.
2362    ///
2363    /// # Safety
2364    ///
2365    /// You must ensure that the `BTreeSet` invariants are maintained.
2366    /// Specifically:
2367    ///
2368    /// * The newly inserted element must be unique in the tree.
2369    /// * All elements in the tree must remain in sorted order.
2370    #[unstable(feature = "btree_cursors", issue = "107540")]
2371    pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2372        unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2373    }
2374
2375    /// Inserts a new element into the set in the gap that the
2376    /// cursor is currently pointing to.
2377    ///
2378    /// After the insertion the cursor will be pointing at the gap before the
2379    /// newly inserted element.
2380    ///
2381    /// If the inserted element is not greater than the element before the
2382    /// cursor (if any), or if it not less than the element after the cursor (if
2383    /// any), then an [`UnorderedKeyError`] is returned since this would
2384    /// invalidate the [`Ord`] invariant between the elements of the set.
2385    #[unstable(feature = "btree_cursors", issue = "107540")]
2386    pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2387        self.inner.insert_after(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 after 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_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2402        self.inner.insert_before(value, SetValZST)
2403    }
2404
2405    /// Removes the next element from the `BTreeSet`.
2406    ///
2407    /// The element that was removed is returned. The cursor position is
2408    /// unchanged (before the removed element).
2409    #[unstable(feature = "btree_cursors", issue = "107540")]
2410    pub fn remove_next(&mut self) -> Option<T> {
2411        self.inner.remove_next().map(|(k, _)| k)
2412    }
2413
2414    /// Removes the preceding element from the `BTreeSet`.
2415    ///
2416    /// The element that was removed is returned. The cursor position is
2417    /// unchanged (after the removed element).
2418    #[unstable(feature = "btree_cursors", issue = "107540")]
2419    pub fn remove_prev(&mut self) -> Option<T> {
2420        self.inner.remove_prev().map(|(k, _)| k)
2421    }
2422}
2423
2424impl<'a, T: Ord, A: Allocator + Clone> CursorMutKey<'a, T, A> {
2425    /// Inserts a new element into the set in the gap that the
2426    /// cursor is currently pointing to.
2427    ///
2428    /// After the insertion the cursor will be pointing at the gap before the
2429    /// newly inserted element.
2430    ///
2431    /// # Safety
2432    ///
2433    /// You must ensure that the `BTreeSet` invariants are maintained.
2434    /// Specifically:
2435    ///
2436    /// * The key of the newly inserted element must be unique in the tree.
2437    /// * All elements in the tree must remain in sorted order.
2438    #[unstable(feature = "btree_cursors", issue = "107540")]
2439    pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2440        unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2441    }
2442
2443    /// Inserts a new element into the set in the gap that the
2444    /// cursor is currently pointing to.
2445    ///
2446    /// After the insertion the cursor will be pointing at the gap after the
2447    /// newly inserted element.
2448    ///
2449    /// # Safety
2450    ///
2451    /// You must ensure that the `BTreeSet` invariants are maintained.
2452    /// Specifically:
2453    ///
2454    /// * The newly inserted element must be unique in the tree.
2455    /// * All elements in the tree must remain in sorted order.
2456    #[unstable(feature = "btree_cursors", issue = "107540")]
2457    pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2458        unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2459    }
2460
2461    /// Inserts a new element into the set in the gap that the
2462    /// cursor is currently pointing to.
2463    ///
2464    /// After the insertion the cursor will be pointing at the gap before the
2465    /// newly inserted element.
2466    ///
2467    /// If the inserted element is not greater than the element before the
2468    /// cursor (if any), or if it not less than the element after the cursor (if
2469    /// any), then an [`UnorderedKeyError`] is returned since this would
2470    /// invalidate the [`Ord`] invariant between the elements of the set.
2471    #[unstable(feature = "btree_cursors", issue = "107540")]
2472    pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2473        self.inner.insert_after(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 after 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_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2488        self.inner.insert_before(value, SetValZST)
2489    }
2490
2491    /// Removes the next element from the `BTreeSet`.
2492    ///
2493    /// The element that was removed is returned. The cursor position is
2494    /// unchanged (before the removed element).
2495    #[unstable(feature = "btree_cursors", issue = "107540")]
2496    pub fn remove_next(&mut self) -> Option<T> {
2497        self.inner.remove_next().map(|(k, _)| k)
2498    }
2499
2500    /// Removes the preceding element from the `BTreeSet`.
2501    ///
2502    /// The element that was removed is returned. The cursor position is
2503    /// unchanged (after the removed element).
2504    #[unstable(feature = "btree_cursors", issue = "107540")]
2505    pub fn remove_prev(&mut self) -> Option<T> {
2506        self.inner.remove_prev().map(|(k, _)| k)
2507    }
2508}
2509
2510#[unstable(feature = "btree_cursors", issue = "107540")]
2511pub use super::map::UnorderedKeyError;
2512
2513#[cfg(test)]
2514mod tests;