library/alloc/src/collections/btree/set.rs

   1 // This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface
   2 // to TreeMap
   3
   4 use crate::vec::Vec;
   5 use core::borrow::Borrow;
   6 use core::cmp::Ordering::{Equal, Greater, Less};
   7 use core::cmp::{max, min};
   8 use core::fmt::{self, Debug};
   9 use core::iter::{FromIterator, FusedIterator, Peekable};
  10 use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub};
  11
  12 use super::map::{BTreeMap, Keys};
  13 use super::merge_iter::MergeIterInner;
  14 use super::Recover;
  15
  16 // FIXME(conventions): implement bounded iterators
  17
  18 /// A set based on a B-Tree.
  19 ///
  20 /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
  21 /// benefits and drawbacks.
  22 ///
  23 /// It is a logic error for an item to be modified in such a way that the item's ordering relative
  24 /// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
  25 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
  26 /// The behavior resulting from such a logic error is not specified (it could include panics,
  27 /// incorrect results, aborts, memory leaks, or non-termination) but will not be undefined
  28 /// behavior.
  29 ///
  30 /// [`Ord`]: core::cmp::Ord
  31 /// [`Cell`]: core::cell::Cell
  32 /// [`RefCell`]: core::cell::RefCell
  33 ///
  34 /// # Examples
  35 ///
  36 /// ```
  37 /// use std::collections::BTreeSet;
  38 ///
  39 /// // Type inference lets us omit an explicit type signature (which
  40 /// // would be `BTreeSet<&str>` in this example).
  41 /// let mut books = BTreeSet::new();
  42 ///
  43 /// // Add some books.
  44 /// books.insert("A Dance With Dragons");
  45 /// books.insert("To Kill a Mockingbird");
  46 /// books.insert("The Odyssey");
  47 /// books.insert("The Great Gatsby");
  48 ///
  49 /// // Check for a specific one.
  50 /// if !books.contains("The Winds of Winter") {
  51 ///     println!("We have {} books, but The Winds of Winter ain't one.",
  52 ///              books.len());
  53 /// }
  54 ///
  55 /// // Remove a book.
  56 /// books.remove("The Odyssey");
  57 ///
  58 /// // Iterate over everything.
  59 /// for book in &books {
  60 ///     println!("{}", book);
  61 /// }
  62 /// ```
  63 ///
  64 /// A `BTreeSet` with a known list of items can be initialized from an array:
  65 ///
  66 /// ```
  67 /// use std::collections::BTreeSet;
  68 ///
  69 /// let set = BTreeSet::from([1, 2, 3]);
  70 /// ```
  71 #[derive(Hash, PartialEq, Eq, Ord, PartialOrd)]
  72 #[stable(feature = "rust1", since = "1.0.0")]
  73 #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeSet")]
  74 pub struct BTreeSet<T> {
  75     map: BTreeMap<T, ()>,
  76 }
  77
  78 #[stable(feature = "rust1", since = "1.0.0")]
  79 impl<T: Clone> Clone for BTreeSet<T> {
  80     fn clone(&self) -> Self {
  81         BTreeSet { map: self.map.clone() }
  82     }
  83
  84     fn clone_from(&mut self, other: &Self) {
  85         self.map.clone_from(&other.map);
  86     }
  87 }
  88
  89 /// An iterator over the items of a `BTreeSet`.
  90 ///
  91 /// This `struct` is created by the [`iter`] method on [`BTreeSet`].
  92 /// See its documentation for more.
  93 ///
  94 /// [`iter`]: BTreeSet::iter
  95 #[must_use = "iterators are lazy and do nothing unless consumed"]
  96 #[stable(feature = "rust1", since = "1.0.0")]
  97 pub struct Iter<'a, T: 'a> {
  98     iter: Keys<'a, T, ()>,
  99 }
 100
 101 #[stable(feature = "collection_debug", since = "1.17.0")]
 102 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
 103     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 104         f.debug_tuple("Iter").field(&self.iter.clone()).finish()
 105     }
 106 }
 107
 108 /// An owning iterator over the items of a `BTreeSet`.
 109 ///
 110 /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`]
 111 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 112 ///
 113 /// [`into_iter`]: BTreeSet#method.into_iter
 114 /// [`IntoIterator`]: core::iter::IntoIterator
 115 #[stable(feature = "rust1", since = "1.0.0")]
 116 #[derive(Debug)]
 117 pub struct IntoIter<T> {
 118     iter: super::map::IntoIter<T, ()>,
 119 }
 120
 121 /// An iterator over a sub-range of items in a `BTreeSet`.
 122 ///
 123 /// This `struct` is created by the [`range`] method on [`BTreeSet`].
 124 /// See its documentation for more.
 125 ///
 126 /// [`range`]: BTreeSet::range
 127 #[must_use = "iterators are lazy and do nothing unless consumed"]
 128 #[derive(Debug)]
 129 #[stable(feature = "btree_range", since = "1.17.0")]
 130 pub struct Range<'a, T: 'a> {
 131     iter: super::map::Range<'a, T, ()>,
 132 }
 133
 134 /// A lazy iterator producing elements in the difference of `BTreeSet`s.
 135 ///
 136 /// This `struct` is created by the [`difference`] method on [`BTreeSet`].
 137 /// See its documentation for more.
 138 ///
 139 /// [`difference`]: BTreeSet::difference
 140 #[must_use = "this returns the difference as an iterator, \
 141               without modifying either input set"]
 142 #[stable(feature = "rust1", since = "1.0.0")]
 143 pub struct Difference<'a, T: 'a> {
 144     inner: DifferenceInner<'a, T>,
 145 }
 146 #[derive(Debug)]
 147 enum DifferenceInner<'a, T: 'a> {
 148     Stitch {
 149         // iterate all of `self` and some of `other`, spotting matches along the way
 150         self_iter: Iter<'a, T>,
 151         other_iter: Peekable<Iter<'a, T>>,
 152     },
 153     Search {
 154         // iterate `self`, look up in `other`
 155         self_iter: Iter<'a, T>,
 156         other_set: &'a BTreeSet<T>,
 157     },
 158     Iterate(Iter<'a, T>), // simply produce all values in `self`
 159 }
 160
 161 #[stable(feature = "collection_debug", since = "1.17.0")]
 162 impl<T: fmt::Debug> fmt::Debug for Difference<'_, T> {
 163     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 164         f.debug_tuple("Difference").field(&self.inner).finish()
 165     }
 166 }
 167
 168 /// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s.
 169 ///
 170 /// This `struct` is created by the [`symmetric_difference`] method on
 171 /// [`BTreeSet`]. See its documentation for more.
 172 ///
 173 /// [`symmetric_difference`]: BTreeSet::symmetric_difference
 174 #[must_use = "this returns the difference as an iterator, \
 175               without modifying either input set"]
 176 #[stable(feature = "rust1", since = "1.0.0")]
 177 pub struct SymmetricDifference<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
 178
 179 #[stable(feature = "collection_debug", since = "1.17.0")]
 180 impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> {
 181     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 182         f.debug_tuple("SymmetricDifference").field(&self.0).finish()
 183     }
 184 }
 185
 186 /// A lazy iterator producing elements in the intersection of `BTreeSet`s.
 187 ///
 188 /// This `struct` is created by the [`intersection`] method on [`BTreeSet`].
 189 /// See its documentation for more.
 190 ///
 191 /// [`intersection`]: BTreeSet::intersection
 192 #[must_use = "this returns the intersection as an iterator, \
 193               without modifying either input set"]
 194 #[stable(feature = "rust1", since = "1.0.0")]
 195 pub struct Intersection<'a, T: 'a> {
 196     inner: IntersectionInner<'a, T>,
 197 }
 198 #[derive(Debug)]
 199 enum IntersectionInner<'a, T: 'a> {
 200     Stitch {
 201         // iterate similarly sized sets jointly, spotting matches along the way
 202         a: Iter<'a, T>,
 203         b: Iter<'a, T>,
 204     },
 205     Search {
 206         // iterate a small set, look up in the large set
 207         small_iter: Iter<'a, T>,
 208         large_set: &'a BTreeSet<T>,
 209     },
 210     Answer(Option<&'a T>), // return a specific value or emptiness
 211 }
 212
 213 #[stable(feature = "collection_debug", since = "1.17.0")]
 214 impl<T: fmt::Debug> fmt::Debug for Intersection<'_, T> {
 215     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 216         f.debug_tuple("Intersection").field(&self.inner).finish()
 217     }
 218 }
 219
 220 /// A lazy iterator producing elements in the union of `BTreeSet`s.
 221 ///
 222 /// This `struct` is created by the [`union`] method on [`BTreeSet`].
 223 /// See its documentation for more.
 224 ///
 225 /// [`union`]: BTreeSet::union
 226 #[must_use = "this returns the union as an iterator, \
 227               without modifying either input set"]
 228 #[stable(feature = "rust1", since = "1.0.0")]
 229 pub struct Union<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
 230
 231 #[stable(feature = "collection_debug", since = "1.17.0")]
 232 impl<T: fmt::Debug> fmt::Debug for Union<'_, T> {
 233     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 234         f.debug_tuple("Union").field(&self.0).finish()
 235     }
 236 }
 237
 238 // This constant is used by functions that compare two sets.
 239 // It estimates the relative size at which searching performs better
 240 // than iterating, based on the benchmarks in
 241 // https://github.com/ssomers/rust_bench_btreeset_intersection.
 242 // It's used to divide rather than multiply sizes, to rule out overflow,
 243 // and it's a power of two to make that division cheap.
 244 const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = 16;
 245
 246 impl<T> BTreeSet<T> {
 247     /// Makes a new, empty `BTreeSet`.
 248     ///
 249     /// Does not allocate anything on its own.
 250     ///
 251     /// # Examples
 252     ///
 253     /// ```
 254     /// # #![allow(unused_mut)]
 255     /// use std::collections::BTreeSet;
 256     ///
 257     /// let mut set: BTreeSet<i32> = BTreeSet::new();
 258     /// ```
 259     #[stable(feature = "rust1", since = "1.0.0")]
 260     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
 261     #[must_use]
 262     pub const fn new() -> BTreeSet<T> {
 263         BTreeSet { map: BTreeMap::new() }
 264     }
 265
 266     /// Constructs a double-ended iterator over a sub-range of elements in the set.
 267     /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
 268     /// yield elements from min (inclusive) to max (exclusive).
 269     /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
 270     /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
 271     /// range from 4 to 10.
 272     ///
 273     /// # Examples
 274     ///
 275     /// ```
 276     /// use std::collections::BTreeSet;
 277     /// use std::ops::Bound::Included;
 278     ///
 279     /// let mut set = BTreeSet::new();
 280     /// set.insert(3);
 281     /// set.insert(5);
 282     /// set.insert(8);
 283     /// for &elem in set.range((Included(&4), Included(&8))) {
 284     ///     println!("{}", elem);
 285     /// }
 286     /// assert_eq!(Some(&5), set.range(4..).next());
 287     /// ```
 288     #[stable(feature = "btree_range", since = "1.17.0")]
 289     pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
 290     where
 291         K: Ord,
 292         T: Borrow<K> + Ord,
 293         R: RangeBounds<K>,
 294     {
 295         Range { iter: self.map.range(range) }
 296     }
 297
 298     /// Visits the values representing the difference,
 299     /// i.e., the values that are in `self` but not in `other`,
 300     /// in ascending order.
 301     ///
 302     /// # Examples
 303     ///
 304     /// ```
 305     /// use std::collections::BTreeSet;
 306     ///
 307     /// let mut a = BTreeSet::new();
 308     /// a.insert(1);
 309     /// a.insert(2);
 310     ///
 311     /// let mut b = BTreeSet::new();
 312     /// b.insert(2);
 313     /// b.insert(3);
 314     ///
 315     /// let diff: Vec<_> = a.difference(&b).cloned().collect();
 316     /// assert_eq!(diff, [1]);
 317     /// ```
 318     #[stable(feature = "rust1", since = "1.0.0")]
 319     pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T>
 320     where
 321         T: Ord,
 322     {
 323         let (self_min, self_max) =
 324             if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
 325                 (self_min, self_max)
 326             } else {
 327                 return Difference { inner: DifferenceInner::Iterate(self.iter()) };
 328             };
 329         let (other_min, other_max) =
 330             if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
 331                 (other_min, other_max)
 332             } else {
 333                 return Difference { inner: DifferenceInner::Iterate(self.iter()) };
 334             };
 335         Difference {
 336             inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
 337                 (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()),
 338                 (Equal, _) => {
 339                     let mut self_iter = self.iter();
 340                     self_iter.next();
 341                     DifferenceInner::Iterate(self_iter)
 342                 }
 343                 (_, Equal) => {
 344                     let mut self_iter = self.iter();
 345                     self_iter.next_back();
 346                     DifferenceInner::Iterate(self_iter)
 347                 }
 348                 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
 349                     DifferenceInner::Search { self_iter: self.iter(), other_set: other }
 350                 }
 351                 _ => DifferenceInner::Stitch {
 352                     self_iter: self.iter(),
 353                     other_iter: other.iter().peekable(),
 354                 },
 355             },
 356         }
 357     }
 358
 359     /// Visits the values representing the symmetric difference,
 360     /// i.e., the values that are in `self` or in `other` but not in both,
 361     /// in ascending order.
 362     ///
 363     /// # Examples
 364     ///
 365     /// ```
 366     /// use std::collections::BTreeSet;
 367     ///
 368     /// let mut a = BTreeSet::new();
 369     /// a.insert(1);
 370     /// a.insert(2);
 371     ///
 372     /// let mut b = BTreeSet::new();
 373     /// b.insert(2);
 374     /// b.insert(3);
 375     ///
 376     /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
 377     /// assert_eq!(sym_diff, [1, 3]);
 378     /// ```
 379     #[stable(feature = "rust1", since = "1.0.0")]
 380     pub fn symmetric_difference<'a>(&'a self, other: &'a BTreeSet<T>) -> SymmetricDifference<'a, T>
 381     where
 382         T: Ord,
 383     {
 384         SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
 385     }
 386
 387     /// Visits the values representing the intersection,
 388     /// i.e., the values that are both in `self` and `other`,
 389     /// in ascending order.
 390     ///
 391     /// # Examples
 392     ///
 393     /// ```
 394     /// use std::collections::BTreeSet;
 395     ///
 396     /// let mut a = BTreeSet::new();
 397     /// a.insert(1);
 398     /// a.insert(2);
 399     ///
 400     /// let mut b = BTreeSet::new();
 401     /// b.insert(2);
 402     /// b.insert(3);
 403     ///
 404     /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
 405     /// assert_eq!(intersection, [2]);
 406     /// ```
 407     #[stable(feature = "rust1", since = "1.0.0")]
 408     pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T>
 409     where
 410         T: Ord,
 411     {
 412         let (self_min, self_max) =
 413             if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
 414                 (self_min, self_max)
 415             } else {
 416                 return Intersection { inner: IntersectionInner::Answer(None) };
 417             };
 418         let (other_min, other_max) =
 419             if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
 420                 (other_min, other_max)
 421             } else {
 422                 return Intersection { inner: IntersectionInner::Answer(None) };
 423             };
 424         Intersection {
 425             inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
 426                 (Greater, _) | (_, Less) => IntersectionInner::Answer(None),
 427                 (Equal, _) => IntersectionInner::Answer(Some(self_min)),
 428                 (_, Equal) => IntersectionInner::Answer(Some(self_max)),
 429                 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
 430                     IntersectionInner::Search { small_iter: self.iter(), large_set: other }
 431                 }
 432                 _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
 433                     IntersectionInner::Search { small_iter: other.iter(), large_set: self }
 434                 }
 435                 _ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() },
 436             },
 437         }
 438     }
 439
 440     /// Visits the values representing the union,
 441     /// i.e., all the values in `self` or `other`, without duplicates,
 442     /// in ascending order.
 443     ///
 444     /// # Examples
 445     ///
 446     /// ```
 447     /// use std::collections::BTreeSet;
 448     ///
 449     /// let mut a = BTreeSet::new();
 450     /// a.insert(1);
 451     ///
 452     /// let mut b = BTreeSet::new();
 453     /// b.insert(2);
 454     ///
 455     /// let union: Vec<_> = a.union(&b).cloned().collect();
 456     /// assert_eq!(union, [1, 2]);
 457     /// ```
 458     #[stable(feature = "rust1", since = "1.0.0")]
 459     pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T>
 460     where
 461         T: Ord,
 462     {
 463         Union(MergeIterInner::new(self.iter(), other.iter()))
 464     }
 465
 466     /// Clears the set, removing all values.
 467     ///
 468     /// # Examples
 469     ///
 470     /// ```
 471     /// use std::collections::BTreeSet;
 472     ///
 473     /// let mut v = BTreeSet::new();
 474     /// v.insert(1);
 475     /// v.clear();
 476     /// assert!(v.is_empty());
 477     /// ```
 478     #[stable(feature = "rust1", since = "1.0.0")]
 479     pub fn clear(&mut self) {
 480         self.map.clear()
 481     }
 482
 483     /// Returns `true` if the set contains a value.
 484     ///
 485     /// The value may be any borrowed form of the set's value type,
 486     /// but the ordering on the borrowed form *must* match the
 487     /// ordering on the value type.
 488     ///
 489     /// # Examples
 490     ///
 491     /// ```
 492     /// use std::collections::BTreeSet;
 493     ///
 494     /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 495     /// assert_eq!(set.contains(&1), true);
 496     /// assert_eq!(set.contains(&4), false);
 497     /// ```
 498     #[stable(feature = "rust1", since = "1.0.0")]
 499     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
 500     where
 501         T: Borrow<Q> + Ord,
 502         Q: Ord,
 503     {
 504         self.map.contains_key(value)
 505     }
 506
 507     /// Returns a reference to the value in the set, if any, that is equal to the given value.
 508     ///
 509     /// The value may be any borrowed form of the set's value type,
 510     /// but the ordering on the borrowed form *must* match the
 511     /// ordering on the value type.
 512     ///
 513     /// # Examples
 514     ///
 515     /// ```
 516     /// use std::collections::BTreeSet;
 517     ///
 518     /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 519     /// assert_eq!(set.get(&2), Some(&2));
 520     /// assert_eq!(set.get(&4), None);
 521     /// ```
 522     #[stable(feature = "set_recovery", since = "1.9.0")]
 523     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
 524     where
 525         T: Borrow<Q> + Ord,
 526         Q: Ord,
 527     {
 528         Recover::get(&self.map, value)
 529     }
 530
 531     /// Returns `true` if `self` has no elements in common with `other`.
 532     /// This is equivalent to checking for an empty intersection.
 533     ///
 534     /// # Examples
 535     ///
 536     /// ```
 537     /// use std::collections::BTreeSet;
 538     ///
 539     /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 540     /// let mut b = BTreeSet::new();
 541     ///
 542     /// assert_eq!(a.is_disjoint(&b), true);
 543     /// b.insert(4);
 544     /// assert_eq!(a.is_disjoint(&b), true);
 545     /// b.insert(1);
 546     /// assert_eq!(a.is_disjoint(&b), false);
 547     /// ```
 548     #[must_use]
 549     #[stable(feature = "rust1", since = "1.0.0")]
 550     pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool
 551     where
 552         T: Ord,
 553     {
 554         self.intersection(other).next().is_none()
 555     }
 556
 557     /// Returns `true` if the set is a subset of another,
 558     /// i.e., `other` contains at least all the values in `self`.
 559     ///
 560     /// # Examples
 561     ///
 562     /// ```
 563     /// use std::collections::BTreeSet;
 564     ///
 565     /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 566     /// let mut set = BTreeSet::new();
 567     ///
 568     /// assert_eq!(set.is_subset(&sup), true);
 569     /// set.insert(2);
 570     /// assert_eq!(set.is_subset(&sup), true);
 571     /// set.insert(4);
 572     /// assert_eq!(set.is_subset(&sup), false);
 573     /// ```
 574     #[must_use]
 575     #[stable(feature = "rust1", since = "1.0.0")]
 576     pub fn is_subset(&self, other: &BTreeSet<T>) -> bool
 577     where
 578         T: Ord,
 579     {
 580         // Same result as self.difference(other).next().is_none()
 581         // but the code below is faster (hugely in some cases).
 582         if self.len() > other.len() {
 583             return false;
 584         }
 585         let (self_min, self_max) =
 586             if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
 587                 (self_min, self_max)
 588             } else {
 589                 return true; // self is empty
 590             };
 591         let (other_min, other_max) =
 592             if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
 593                 (other_min, other_max)
 594             } else {
 595                 return false; // other is empty
 596             };
 597         let mut self_iter = self.iter();
 598         match self_min.cmp(other_min) {
 599             Less => return false,
 600             Equal => {
 601                 self_iter.next();
 602             }
 603             Greater => (),
 604         }
 605         match self_max.cmp(other_max) {
 606             Greater => return false,
 607             Equal => {
 608                 self_iter.next_back();
 609             }
 610             Less => (),
 611         }
 612         if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
 613             for next in self_iter {
 614                 if !other.contains(next) {
 615                     return false;
 616                 }
 617             }
 618         } else {
 619             let mut other_iter = other.iter();
 620             other_iter.next();
 621             other_iter.next_back();
 622             let mut self_next = self_iter.next();
 623             while let Some(self1) = self_next {
 624                 match other_iter.next().map_or(Less, |other1| self1.cmp(other1)) {
 625                     Less => return false,
 626                     Equal => self_next = self_iter.next(),
 627                     Greater => (),
 628                 }
 629             }
 630         }
 631         true
 632     }
 633
 634     /// Returns `true` if the set is a superset of another,
 635     /// i.e., `self` contains at least all the values in `other`.
 636     ///
 637     /// # Examples
 638     ///
 639     /// ```
 640     /// use std::collections::BTreeSet;
 641     ///
 642     /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect();
 643     /// let mut set = BTreeSet::new();
 644     ///
 645     /// assert_eq!(set.is_superset(&sub), false);
 646     ///
 647     /// set.insert(0);
 648     /// set.insert(1);
 649     /// assert_eq!(set.is_superset(&sub), false);
 650     ///
 651     /// set.insert(2);
 652     /// assert_eq!(set.is_superset(&sub), true);
 653     /// ```
 654     #[must_use]
 655     #[stable(feature = "rust1", since = "1.0.0")]
 656     pub fn is_superset(&self, other: &BTreeSet<T>) -> bool
 657     where
 658         T: Ord,
 659     {
 660         other.is_subset(self)
 661     }
 662
 663     /// Returns a reference to the first value in the set, if any.
 664     /// This value is always the minimum of all values in the set.
 665     ///
 666     /// # Examples
 667     ///
 668     /// Basic usage:
 669     ///
 670     /// ```
 671     /// #![feature(map_first_last)]
 672     /// use std::collections::BTreeSet;
 673     ///
 674     /// let mut set = BTreeSet::new();
 675     /// assert_eq!(set.first(), None);
 676     /// set.insert(1);
 677     /// assert_eq!(set.first(), Some(&1));
 678     /// set.insert(2);
 679     /// assert_eq!(set.first(), Some(&1));
 680     /// ```
 681     #[must_use]
 682     #[unstable(feature = "map_first_last", issue = "62924")]
 683     pub fn first(&self) -> Option<&T>
 684     where
 685         T: Ord,
 686     {
 687         self.map.first_key_value().map(|(k, _)| k)
 688     }
 689
 690     /// Returns a reference to the last value in the set, if any.
 691     /// This value is always the maximum of all values in the set.
 692     ///
 693     /// # Examples
 694     ///
 695     /// Basic usage:
 696     ///
 697     /// ```
 698     /// #![feature(map_first_last)]
 699     /// use std::collections::BTreeSet;
 700     ///
 701     /// let mut set = BTreeSet::new();
 702     /// assert_eq!(set.last(), None);
 703     /// set.insert(1);
 704     /// assert_eq!(set.last(), Some(&1));
 705     /// set.insert(2);
 706     /// assert_eq!(set.last(), Some(&2));
 707     /// ```
 708     #[must_use]
 709     #[unstable(feature = "map_first_last", issue = "62924")]
 710     pub fn last(&self) -> Option<&T>
 711     where
 712         T: Ord,
 713     {
 714         self.map.last_key_value().map(|(k, _)| k)
 715     }
 716
 717     /// Removes the first value from the set and returns it, if any.
 718     /// The first value is always the minimum value in the set.
 719     ///
 720     /// # Examples
 721     ///
 722     /// ```
 723     /// #![feature(map_first_last)]
 724     /// use std::collections::BTreeSet;
 725     ///
 726     /// let mut set = BTreeSet::new();
 727     ///
 728     /// set.insert(1);
 729     /// while let Some(n) = set.pop_first() {
 730     ///     assert_eq!(n, 1);
 731     /// }
 732     /// assert!(set.is_empty());
 733     /// ```
 734     #[unstable(feature = "map_first_last", issue = "62924")]
 735     pub fn pop_first(&mut self) -> Option<T>
 736     where
 737         T: Ord,
 738     {
 739         self.map.pop_first().map(|kv| kv.0)
 740     }
 741
 742     /// Removes the last value from the set and returns it, if any.
 743     /// The last value is always the maximum value in the set.
 744     ///
 745     /// # Examples
 746     ///
 747     /// ```
 748     /// #![feature(map_first_last)]
 749     /// use std::collections::BTreeSet;
 750     ///
 751     /// let mut set = BTreeSet::new();
 752     ///
 753     /// set.insert(1);
 754     /// while let Some(n) = set.pop_last() {
 755     ///     assert_eq!(n, 1);
 756     /// }
 757     /// assert!(set.is_empty());
 758     /// ```
 759     #[unstable(feature = "map_first_last", issue = "62924")]
 760     pub fn pop_last(&mut self) -> Option<T>
 761     where
 762         T: Ord,
 763     {
 764         self.map.pop_last().map(|kv| kv.0)
 765     }
 766
 767     /// Adds a value to the set.
 768     ///
 769     /// If the set did not have this value present, `true` is returned.
 770     ///
 771     /// If the set did have this value present, `false` is returned, and the
 772     /// entry is not updated. See the [module-level documentation] for more.
 773     ///
 774     /// [module-level documentation]: index.html#insert-and-complex-keys
 775     ///
 776     /// # Examples
 777     ///
 778     /// ```
 779     /// use std::collections::BTreeSet;
 780     ///
 781     /// let mut set = BTreeSet::new();
 782     ///
 783     /// assert_eq!(set.insert(2), true);
 784     /// assert_eq!(set.insert(2), false);
 785     /// assert_eq!(set.len(), 1);
 786     /// ```
 787     #[stable(feature = "rust1", since = "1.0.0")]
 788     pub fn insert(&mut self, value: T) -> bool
 789     where
 790         T: Ord,
 791     {
 792         self.map.insert(value, ()).is_none()
 793     }
 794
 795     /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
 796     /// one. Returns the replaced value.
 797     ///
 798     /// # Examples
 799     ///
 800     /// ```
 801     /// use std::collections::BTreeSet;
 802     ///
 803     /// let mut set = BTreeSet::new();
 804     /// set.insert(Vec::<i32>::new());
 805     ///
 806     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
 807     /// set.replace(Vec::with_capacity(10));
 808     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
 809     /// ```
 810     #[stable(feature = "set_recovery", since = "1.9.0")]
 811     pub fn replace(&mut self, value: T) -> Option<T>
 812     where
 813         T: Ord,
 814     {
 815         Recover::replace(&mut self.map, value)
 816     }
 817
 818     /// Removes a value from the set. Returns whether the value was
 819     /// present in the set.
 820     ///
 821     /// The value may be any borrowed form of the set's value type,
 822     /// but the ordering on the borrowed form *must* match the
 823     /// ordering on the value type.
 824     ///
 825     /// # Examples
 826     ///
 827     /// ```
 828     /// use std::collections::BTreeSet;
 829     ///
 830     /// let mut set = BTreeSet::new();
 831     ///
 832     /// set.insert(2);
 833     /// assert_eq!(set.remove(&2), true);
 834     /// assert_eq!(set.remove(&2), false);
 835     /// ```
 836     #[stable(feature = "rust1", since = "1.0.0")]
 837     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
 838     where
 839         T: Borrow<Q> + Ord,
 840         Q: Ord,
 841     {
 842         self.map.remove(value).is_some()
 843     }
 844
 845     /// Removes and returns the value in the set, if any, that is equal to the given one.
 846     ///
 847     /// The value may be any borrowed form of the set's value type,
 848     /// but the ordering on the borrowed form *must* match the
 849     /// ordering on the value type.
 850     ///
 851     /// # Examples
 852     ///
 853     /// ```
 854     /// use std::collections::BTreeSet;
 855     ///
 856     /// let mut set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 857     /// assert_eq!(set.take(&2), Some(2));
 858     /// assert_eq!(set.take(&2), None);
 859     /// ```
 860     #[stable(feature = "set_recovery", since = "1.9.0")]
 861     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
 862     where
 863         T: Borrow<Q> + Ord,
 864         Q: Ord,
 865     {
 866         Recover::take(&mut self.map, value)
 867     }
 868
 869     /// Retains only the elements specified by the predicate.
 870     ///
 871     /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
 872     /// The elements are visited in ascending order.
 873     ///
 874     /// # Examples
 875     ///
 876     /// ```
 877     /// use std::collections::BTreeSet;
 878     ///
 879     /// let xs = [1, 2, 3, 4, 5, 6];
 880     /// let mut set: BTreeSet<i32> = xs.iter().cloned().collect();
 881     /// // Keep only the even numbers.
 882     /// set.retain(|&k| k % 2 == 0);
 883     /// assert!(set.iter().eq([2, 4, 6].iter()));
 884     /// ```
 885     #[stable(feature = "btree_retain", since = "1.53.0")]
 886     pub fn retain<F>(&mut self, mut f: F)
 887     where
 888         T: Ord,
 889         F: FnMut(&T) -> bool,
 890     {
 891         self.drain_filter(|v| !f(v));
 892     }
 893
 894     /// Moves all elements from `other` into `Self`, leaving `other` empty.
 895     ///
 896     /// # Examples
 897     ///
 898     /// ```
 899     /// use std::collections::BTreeSet;
 900     ///
 901     /// let mut a = BTreeSet::new();
 902     /// a.insert(1);
 903     /// a.insert(2);
 904     /// a.insert(3);
 905     ///
 906     /// let mut b = BTreeSet::new();
 907     /// b.insert(3);
 908     /// b.insert(4);
 909     /// b.insert(5);
 910     ///
 911     /// a.append(&mut b);
 912     ///
 913     /// assert_eq!(a.len(), 5);
 914     /// assert_eq!(b.len(), 0);
 915     ///
 916     /// assert!(a.contains(&1));
 917     /// assert!(a.contains(&2));
 918     /// assert!(a.contains(&3));
 919     /// assert!(a.contains(&4));
 920     /// assert!(a.contains(&5));
 921     /// ```
 922     #[stable(feature = "btree_append", since = "1.11.0")]
 923     pub fn append(&mut self, other: &mut Self)
 924     where
 925         T: Ord,
 926     {
 927         self.map.append(&mut other.map);
 928     }
 929
 930     /// Splits the collection into two at the given value. Returns everything after the given value,
 931     /// including the value.
 932     ///
 933     /// # Examples
 934     ///
 935     /// Basic usage:
 936     ///
 937     /// ```
 938     /// use std::collections::BTreeSet;
 939     ///
 940     /// let mut a = BTreeSet::new();
 941     /// a.insert(1);
 942     /// a.insert(2);
 943     /// a.insert(3);
 944     /// a.insert(17);
 945     /// a.insert(41);
 946     ///
 947     /// let b = a.split_off(&3);
 948     ///
 949     /// assert_eq!(a.len(), 2);
 950     /// assert_eq!(b.len(), 3);
 951     ///
 952     /// assert!(a.contains(&1));
 953     /// assert!(a.contains(&2));
 954     ///
 955     /// assert!(b.contains(&3));
 956     /// assert!(b.contains(&17));
 957     /// assert!(b.contains(&41));
 958     /// ```
 959     #[stable(feature = "btree_split_off", since = "1.11.0")]
 960     pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self
 961     where
 962         T: Borrow<Q> + Ord,
 963     {
 964         BTreeSet { map: self.map.split_off(value) }
 965     }
 966
 967     /// Creates an iterator that visits all values in ascending order and uses a closure
 968     /// to determine if a value should be removed.
 969     ///
 970     /// If the closure returns `true`, the value is removed from the set and yielded. If
 971     /// the closure returns `false`, or panics, the value remains in the set and will
 972     /// not be yielded.
 973     ///
 974     /// If the iterator is only partially consumed or not consumed at all, each of the
 975     /// remaining values is still subjected to the closure and removed and dropped if it
 976     /// returns `true`.
 977     ///
 978     /// It is unspecified how many more values will be subjected to the closure if a
 979     /// panic occurs in the closure, or if a panic occurs while dropping a value, or if
 980     /// the `DrainFilter` itself is leaked.
 981     ///
 982     /// # Examples
 983     ///
 984     /// Splitting a set into even and odd values, reusing the original set:
 985     ///
 986     /// ```
 987     /// #![feature(btree_drain_filter)]
 988     /// use std::collections::BTreeSet;
 989     ///
 990     /// let mut set: BTreeSet<i32> = (0..8).collect();
 991     /// let evens: BTreeSet<_> = set.drain_filter(|v| v % 2 == 0).collect();
 992     /// let odds = set;
 993     /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
 994     /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
 995     /// ```
 996     #[unstable(feature = "btree_drain_filter", issue = "70530")]
 997     pub fn drain_filter<'a, F>(&'a mut self, pred: F) -> DrainFilter<'a, T, F>
 998     where
 999         T: Ord,
1000         F: 'a + FnMut(&T) -> bool,
1001     {
1002         DrainFilter { pred, inner: self.map.drain_filter_inner() }
1003     }
1004
1005     /// Gets an iterator that visits the values in the `BTreeSet` in ascending order.
1006     ///
1007     /// # Examples
1008     ///
1009     /// ```
1010     /// use std::collections::BTreeSet;
1011     ///
1012     /// let set: BTreeSet<usize> = [1, 2, 3].iter().cloned().collect();
1013     /// let mut set_iter = set.iter();
1014     /// assert_eq!(set_iter.next(), Some(&1));
1015     /// assert_eq!(set_iter.next(), Some(&2));
1016     /// assert_eq!(set_iter.next(), Some(&3));
1017     /// assert_eq!(set_iter.next(), None);
1018     /// ```
1019     ///
1020     /// Values returned by the iterator are returned in ascending order:
1021     ///
1022     /// ```
1023     /// use std::collections::BTreeSet;
1024     ///
1025     /// let set: BTreeSet<usize> = [3, 1, 2].iter().cloned().collect();
1026     /// let mut set_iter = set.iter();
1027     /// assert_eq!(set_iter.next(), Some(&1));
1028     /// assert_eq!(set_iter.next(), Some(&2));
1029     /// assert_eq!(set_iter.next(), Some(&3));
1030     /// assert_eq!(set_iter.next(), None);
1031     /// ```
1032     #[stable(feature = "rust1", since = "1.0.0")]
1033     pub fn iter(&self) -> Iter<'_, T> {
1034         Iter { iter: self.map.keys() }
1035     }
1036
1037     /// Returns the number of elements in the set.
1038     ///
1039     /// # Examples
1040     ///
1041     /// ```
1042     /// use std::collections::BTreeSet;
1043     ///
1044     /// let mut v = BTreeSet::new();
1045     /// assert_eq!(v.len(), 0);
1046     /// v.insert(1);
1047     /// assert_eq!(v.len(), 1);
1048     /// ```
1049     #[must_use]
1050     #[stable(feature = "rust1", since = "1.0.0")]
1051     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
1052     pub const fn len(&self) -> usize {
1053         self.map.len()
1054     }
1055
1056     /// Returns `true` if the set contains no elements.
1057     ///
1058     /// # Examples
1059     ///
1060     /// ```
1061     /// use std::collections::BTreeSet;
1062     ///
1063     /// let mut v = BTreeSet::new();
1064     /// assert!(v.is_empty());
1065     /// v.insert(1);
1066     /// assert!(!v.is_empty());
1067     /// ```
1068     #[must_use]
1069     #[stable(feature = "rust1", since = "1.0.0")]
1070     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
1071     pub const fn is_empty(&self) -> bool {
1072         self.len() == 0
1073     }
1074 }
1075
1076 #[stable(feature = "rust1", since = "1.0.0")]
1077 impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1078     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1079         let mut inputs: Vec<_> = iter.into_iter().collect();
1080
1081         if inputs.is_empty() {
1082             return BTreeSet::new();
1083         }
1084
1085         // use stable sort to preserve the insertion order.
1086         inputs.sort();
1087         let iter = inputs.into_iter().map(|k| (k, ()));
1088         let map = BTreeMap::bulk_build_from_sorted_iter(iter);
1089         BTreeSet { map }
1090     }
1091 }
1092
1093 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
1094 impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
1095     /// Converts a `[T; N]` into a `BTreeSet<T>`.
1096     ///
1097     /// ```
1098     /// use std::collections::BTreeSet;
1099     ///
1100     /// let set1 = BTreeSet::from([1, 2, 3, 4]);
1101     /// let set2: BTreeSet<_> = [1, 2, 3, 4].into();
1102     /// assert_eq!(set1, set2);
1103     /// ```
1104     fn from(mut arr: [T; N]) -> Self {
1105         if N == 0 {
1106             return BTreeSet::new();
1107         }
1108
1109         // use stable sort to preserve the insertion order.
1110         arr.sort();
1111         let iter = core::array::IntoIter::new(arr).map(|k| (k, ()));
1112         let map = BTreeMap::bulk_build_from_sorted_iter(iter);
1113         BTreeSet { map }
1114     }
1115 }
1116
1117 #[stable(feature = "rust1", since = "1.0.0")]
1118 impl<T> IntoIterator for BTreeSet<T> {
1119     type Item = T;
1120     type IntoIter = IntoIter<T>;
1121
1122     /// Gets an iterator for moving out the `BTreeSet`'s contents.
1123     ///
1124     /// # Examples
1125     ///
1126     /// ```
1127     /// use std::collections::BTreeSet;
1128     ///
1129     /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
1130     ///
1131     /// let v: Vec<_> = set.into_iter().collect();
1132     /// assert_eq!(v, [1, 2, 3, 4]);
1133     /// ```
1134     fn into_iter(self) -> IntoIter<T> {
1135         IntoIter { iter: self.map.into_iter() }
1136     }
1137 }
1138
1139 #[stable(feature = "rust1", since = "1.0.0")]
1140 impl<'a, T> IntoIterator for &'a BTreeSet<T> {
1141     type Item = &'a T;
1142     type IntoIter = Iter<'a, T>;
1143
1144     fn into_iter(self) -> Iter<'a, T> {
1145         self.iter()
1146     }
1147 }
1148
1149 /// An iterator produced by calling `drain_filter` on BTreeSet.
1150 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1151 pub struct DrainFilter<'a, T, F>
1152 where
1153     T: 'a,
1154     F: 'a + FnMut(&T) -> bool,
1155 {
1156     pred: F,
1157     inner: super::map::DrainFilterInner<'a, T, ()>,
1158 }
1159
1160 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1161 impl<T, F> Drop for DrainFilter<'_, T, F>
1162 where
1163     F: FnMut(&T) -> bool,
1164 {
1165     fn drop(&mut self) {
1166         self.for_each(drop);
1167     }
1168 }
1169
1170 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1171 impl<T, F> fmt::Debug for DrainFilter<'_, T, F>
1172 where
1173     T: fmt::Debug,
1174     F: FnMut(&T) -> bool,
1175 {
1176     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1177         f.debug_tuple("DrainFilter").field(&self.inner.peek().map(|(k, _)| k)).finish()
1178     }
1179 }
1180
1181 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1182 impl<'a, T, F> Iterator for DrainFilter<'_, T, F>
1183 where
1184     F: 'a + FnMut(&T) -> bool,
1185 {
1186     type Item = T;
1187
1188     fn next(&mut self) -> Option<T> {
1189         let pred = &mut self.pred;
1190         let mut mapped_pred = |k: &T, _v: &mut ()| pred(k);
1191         self.inner.next(&mut mapped_pred).map(|(k, _)| k)
1192     }
1193
1194     fn size_hint(&self) -> (usize, Option<usize>) {
1195         self.inner.size_hint()
1196     }
1197 }
1198
1199 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1200 impl<T, F> FusedIterator for DrainFilter<'_, T, F> where F: FnMut(&T) -> bool {}
1201
1202 #[stable(feature = "rust1", since = "1.0.0")]
1203 impl<T: Ord> Extend<T> for BTreeSet<T> {
1204     #[inline]
1205     fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1206         iter.into_iter().for_each(move |elem| {
1207             self.insert(elem);
1208         });
1209     }
1210
1211     #[inline]
1212     fn extend_one(&mut self, elem: T) {
1213         self.insert(elem);
1214     }
1215 }
1216
1217 #[stable(feature = "extend_ref", since = "1.2.0")]
1218 impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> {
1219     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1220         self.extend(iter.into_iter().cloned());
1221     }
1222
1223     #[inline]
1224     fn extend_one(&mut self, &elem: &'a T) {
1225         self.insert(elem);
1226     }
1227 }
1228
1229 #[stable(feature = "rust1", since = "1.0.0")]
1230 impl<T> Default for BTreeSet<T> {
1231     /// Creates an empty `BTreeSet`.
1232     fn default() -> BTreeSet<T> {
1233         BTreeSet::new()
1234     }
1235 }
1236
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 impl<T: Ord + Clone> Sub<&BTreeSet<T>> for &BTreeSet<T> {
1239     type Output = BTreeSet<T>;
1240
1241     /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1242     ///
1243     /// # Examples
1244     ///
1245     /// ```
1246     /// use std::collections::BTreeSet;
1247     ///
1248     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1249     /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
1250     ///
1251     /// let result = &a - &b;
1252     /// let result_vec: Vec<_> = result.into_iter().collect();
1253     /// assert_eq!(result_vec, [1, 2]);
1254     /// ```
1255     fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1256         self.difference(rhs).cloned().collect()
1257     }
1258 }
1259
1260 #[stable(feature = "rust1", since = "1.0.0")]
1261 impl<T: Ord + Clone> BitXor<&BTreeSet<T>> for &BTreeSet<T> {
1262     type Output = BTreeSet<T>;
1263
1264     /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1265     ///
1266     /// # Examples
1267     ///
1268     /// ```
1269     /// use std::collections::BTreeSet;
1270     ///
1271     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1272     /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
1273     ///
1274     /// let result = &a ^ &b;
1275     /// let result_vec: Vec<_> = result.into_iter().collect();
1276     /// assert_eq!(result_vec, [1, 4]);
1277     /// ```
1278     fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1279         self.symmetric_difference(rhs).cloned().collect()
1280     }
1281 }
1282
1283 #[stable(feature = "rust1", since = "1.0.0")]
1284 impl<T: Ord + Clone> BitAnd<&BTreeSet<T>> for &BTreeSet<T> {
1285     type Output = BTreeSet<T>;
1286
1287     /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1288     ///
1289     /// # Examples
1290     ///
1291     /// ```
1292     /// use std::collections::BTreeSet;
1293     ///
1294     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1295     /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
1296     ///
1297     /// let result = &a & &b;
1298     /// let result_vec: Vec<_> = result.into_iter().collect();
1299     /// assert_eq!(result_vec, [2, 3]);
1300     /// ```
1301     fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1302         self.intersection(rhs).cloned().collect()
1303     }
1304 }
1305
1306 #[stable(feature = "rust1", since = "1.0.0")]
1307 impl<T: Ord + Clone> BitOr<&BTreeSet<T>> for &BTreeSet<T> {
1308     type Output = BTreeSet<T>;
1309
1310     /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1311     ///
1312     /// # Examples
1313     ///
1314     /// ```
1315     /// use std::collections::BTreeSet;
1316     ///
1317     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1318     /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
1319     ///
1320     /// let result = &a | &b;
1321     /// let result_vec: Vec<_> = result.into_iter().collect();
1322     /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
1323     /// ```
1324     fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1325         self.union(rhs).cloned().collect()
1326     }
1327 }
1328
1329 #[stable(feature = "rust1", since = "1.0.0")]
1330 impl<T: Debug> Debug for BTreeSet<T> {
1331     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1332         f.debug_set().entries(self.iter()).finish()
1333     }
1334 }
1335
1336 #[stable(feature = "rust1", since = "1.0.0")]
1337 impl<T> Clone for Iter<'_, T> {
1338     fn clone(&self) -> Self {
1339         Iter { iter: self.iter.clone() }
1340     }
1341 }
1342 #[stable(feature = "rust1", since = "1.0.0")]
1343 impl<'a, T> Iterator for Iter<'a, T> {
1344     type Item = &'a T;
1345
1346     fn next(&mut self) -> Option<&'a T> {
1347         self.iter.next()
1348     }
1349
1350     fn size_hint(&self) -> (usize, Option<usize>) {
1351         self.iter.size_hint()
1352     }
1353
1354     fn last(mut self) -> Option<&'a T> {
1355         self.next_back()
1356     }
1357
1358     fn min(mut self) -> Option<&'a T> {
1359         self.next()
1360     }
1361
1362     fn max(mut self) -> Option<&'a T> {
1363         self.next_back()
1364     }
1365 }
1366 #[stable(feature = "rust1", since = "1.0.0")]
1367 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1368     fn next_back(&mut self) -> Option<&'a T> {
1369         self.iter.next_back()
1370     }
1371 }
1372 #[stable(feature = "rust1", since = "1.0.0")]
1373 impl<T> ExactSizeIterator for Iter<'_, T> {
1374     fn len(&self) -> usize {
1375         self.iter.len()
1376     }
1377 }
1378
1379 #[stable(feature = "fused", since = "1.26.0")]
1380 impl<T> FusedIterator for Iter<'_, T> {}
1381
1382 #[stable(feature = "rust1", since = "1.0.0")]
1383 impl<T> Iterator for IntoIter<T> {
1384     type Item = T;
1385
1386     fn next(&mut self) -> Option<T> {
1387         self.iter.next().map(|(k, _)| k)
1388     }
1389
1390     fn size_hint(&self) -> (usize, Option<usize>) {
1391         self.iter.size_hint()
1392     }
1393 }
1394 #[stable(feature = "rust1", since = "1.0.0")]
1395 impl<T> DoubleEndedIterator for IntoIter<T> {
1396     fn next_back(&mut self) -> Option<T> {
1397         self.iter.next_back().map(|(k, _)| k)
1398     }
1399 }
1400 #[stable(feature = "rust1", since = "1.0.0")]
1401 impl<T> ExactSizeIterator for IntoIter<T> {
1402     fn len(&self) -> usize {
1403         self.iter.len()
1404     }
1405 }
1406
1407 #[stable(feature = "fused", since = "1.26.0")]
1408 impl<T> FusedIterator for IntoIter<T> {}
1409
1410 #[stable(feature = "btree_range", since = "1.17.0")]
1411 impl<T> Clone for Range<'_, T> {
1412     fn clone(&self) -> Self {
1413         Range { iter: self.iter.clone() }
1414     }
1415 }
1416
1417 #[stable(feature = "btree_range", since = "1.17.0")]
1418 impl<'a, T> Iterator for Range<'a, T> {
1419     type Item = &'a T;
1420
1421     fn next(&mut self) -> Option<&'a T> {
1422         self.iter.next().map(|(k, _)| k)
1423     }
1424
1425     fn last(mut self) -> Option<&'a T> {
1426         self.next_back()
1427     }
1428
1429     fn min(mut self) -> Option<&'a T> {
1430         self.next()
1431     }
1432
1433     fn max(mut self) -> Option<&'a T> {
1434         self.next_back()
1435     }
1436 }
1437
1438 #[stable(feature = "btree_range", since = "1.17.0")]
1439 impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1440     fn next_back(&mut self) -> Option<&'a T> {
1441         self.iter.next_back().map(|(k, _)| k)
1442     }
1443 }
1444
1445 #[stable(feature = "fused", since = "1.26.0")]
1446 impl<T> FusedIterator for Range<'_, T> {}
1447
1448 #[stable(feature = "rust1", since = "1.0.0")]
1449 impl<T> Clone for Difference<'_, T> {
1450     fn clone(&self) -> Self {
1451         Difference {
1452             inner: match &self.inner {
1453                 DifferenceInner::Stitch { self_iter, other_iter } => DifferenceInner::Stitch {
1454                     self_iter: self_iter.clone(),
1455                     other_iter: other_iter.clone(),
1456                 },
1457                 DifferenceInner::Search { self_iter, other_set } => {
1458                     DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1459                 }
1460                 DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
1461             },
1462         }
1463     }
1464 }
1465 #[stable(feature = "rust1", since = "1.0.0")]
1466 impl<'a, T: Ord> Iterator for Difference<'a, T> {
1467     type Item = &'a T;
1468
1469     fn next(&mut self) -> Option<&'a T> {
1470         match &mut self.inner {
1471             DifferenceInner::Stitch { self_iter, other_iter } => {
1472                 let mut self_next = self_iter.next()?;
1473                 loop {
1474                     match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1475                         Less => return Some(self_next),
1476                         Equal => {
1477                             self_next = self_iter.next()?;
1478                             other_iter.next();
1479                         }
1480                         Greater => {
1481                             other_iter.next();
1482                         }
1483                     }
1484                 }
1485             }
1486             DifferenceInner::Search { self_iter, other_set } => loop {
1487                 let self_next = self_iter.next()?;
1488                 if !other_set.contains(&self_next) {
1489                     return Some(self_next);
1490                 }
1491             },
1492             DifferenceInner::Iterate(iter) => iter.next(),
1493         }
1494     }
1495
1496     fn size_hint(&self) -> (usize, Option<usize>) {
1497         let (self_len, other_len) = match &self.inner {
1498             DifferenceInner::Stitch { self_iter, other_iter } => {
1499                 (self_iter.len(), other_iter.len())
1500             }
1501             DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1502             DifferenceInner::Iterate(iter) => (iter.len(), 0),
1503         };
1504         (self_len.saturating_sub(other_len), Some(self_len))
1505     }
1506
1507     fn min(mut self) -> Option<&'a T> {
1508         self.next()
1509     }
1510 }
1511
1512 #[stable(feature = "fused", since = "1.26.0")]
1513 impl<T: Ord> FusedIterator for Difference<'_, T> {}
1514
1515 #[stable(feature = "rust1", since = "1.0.0")]
1516 impl<T> Clone for SymmetricDifference<'_, T> {
1517     fn clone(&self) -> Self {
1518         SymmetricDifference(self.0.clone())
1519     }
1520 }
1521 #[stable(feature = "rust1", since = "1.0.0")]
1522 impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
1523     type Item = &'a T;
1524
1525     fn next(&mut self) -> Option<&'a T> {
1526         loop {
1527             let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
1528             if a_next.and(b_next).is_none() {
1529                 return a_next.or(b_next);
1530             }
1531         }
1532     }
1533
1534     fn size_hint(&self) -> (usize, Option<usize>) {
1535         let (a_len, b_len) = self.0.lens();
1536         // No checked_add, because even if a and b refer to the same set,
1537         // and T is an empty type, the storage overhead of sets limits
1538         // the number of elements to less than half the range of usize.
1539         (0, Some(a_len + b_len))
1540     }
1541
1542     fn min(mut self) -> Option<&'a T> {
1543         self.next()
1544     }
1545 }
1546
1547 #[stable(feature = "fused", since = "1.26.0")]
1548 impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
1549
1550 #[stable(feature = "rust1", since = "1.0.0")]
1551 impl<T> Clone for Intersection<'_, T> {
1552     fn clone(&self) -> Self {
1553         Intersection {
1554             inner: match &self.inner {
1555                 IntersectionInner::Stitch { a, b } => {
1556                     IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
1557                 }
1558                 IntersectionInner::Search { small_iter, large_set } => {
1559                     IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
1560                 }
1561                 IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
1562             },
1563         }
1564     }
1565 }
1566 #[stable(feature = "rust1", since = "1.0.0")]
1567 impl<'a, T: Ord> Iterator for Intersection<'a, T> {
1568     type Item = &'a T;
1569
1570     fn next(&mut self) -> Option<&'a T> {
1571         match &mut self.inner {
1572             IntersectionInner::Stitch { a, b } => {
1573                 let mut a_next = a.next()?;
1574                 let mut b_next = b.next()?;
1575                 loop {
1576                     match a_next.cmp(b_next) {
1577                         Less => a_next = a.next()?,
1578                         Greater => b_next = b.next()?,
1579                         Equal => return Some(a_next),
1580                     }
1581                 }
1582             }
1583             IntersectionInner::Search { small_iter, large_set } => loop {
1584                 let small_next = small_iter.next()?;
1585                 if large_set.contains(&small_next) {
1586                     return Some(small_next);
1587                 }
1588             },
1589             IntersectionInner::Answer(answer) => answer.take(),
1590         }
1591     }
1592
1593     fn size_hint(&self) -> (usize, Option<usize>) {
1594         match &self.inner {
1595             IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
1596             IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
1597             IntersectionInner::Answer(None) => (0, Some(0)),
1598             IntersectionInner::Answer(Some(_)) => (1, Some(1)),
1599         }
1600     }
1601
1602     fn min(mut self) -> Option<&'a T> {
1603         self.next()
1604     }
1605 }
1606
1607 #[stable(feature = "fused", since = "1.26.0")]
1608 impl<T: Ord> FusedIterator for Intersection<'_, T> {}
1609
1610 #[stable(feature = "rust1", since = "1.0.0")]
1611 impl<T> Clone for Union<'_, T> {
1612     fn clone(&self) -> Self {
1613         Union(self.0.clone())
1614     }
1615 }
1616 #[stable(feature = "rust1", since = "1.0.0")]
1617 impl<'a, T: Ord> Iterator for Union<'a, T> {
1618     type Item = &'a T;
1619
1620     fn next(&mut self) -> Option<&'a T> {
1621         let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
1622         a_next.or(b_next)
1623     }
1624
1625     fn size_hint(&self) -> (usize, Option<usize>) {
1626         let (a_len, b_len) = self.0.lens();
1627         // No checked_add - see SymmetricDifference::size_hint.
1628         (max(a_len, b_len), Some(a_len + b_len))
1629     }
1630
1631     fn min(mut self) -> Option<&'a T> {
1632         self.next()
1633     }
1634 }
1635
1636 #[stable(feature = "fused", since = "1.26.0")]
1637 impl<T: Ord> FusedIterator for Union<'_, T> {}
1638
1639 #[cfg(test)]
1640 mod tests;