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