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