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