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     #[doc(alias = "delete")]
 814     #[stable(feature = "rust1", since = "1.0.0")]
 815     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
 816     where
 817         T: Borrow<Q> + Ord,
 818         Q: Ord,
 819     {
 820         self.map.remove(value).is_some()
 821     }
 822
 823     /// Removes and returns the value in the set, if any, that is equal to the given one.
 824     ///
 825     /// The value may be any borrowed form of the set's value type,
 826     /// but the ordering on the borrowed form *must* match the
 827     /// ordering on the value type.
 828     ///
 829     /// # Examples
 830     ///
 831     /// ```
 832     /// use std::collections::BTreeSet;
 833     ///
 834     /// let mut set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 835     /// assert_eq!(set.take(&2), Some(2));
 836     /// assert_eq!(set.take(&2), None);
 837     /// ```
 838     #[stable(feature = "set_recovery", since = "1.9.0")]
 839     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
 840     where
 841         T: Borrow<Q> + Ord,
 842         Q: Ord,
 843     {
 844         Recover::take(&mut self.map, value)
 845     }
 846
 847     /// Retains only the elements specified by the predicate.
 848     ///
 849     /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
 850     ///
 851     /// # Examples
 852     ///
 853     /// ```
 854     /// #![feature(btree_retain)]
 855     /// use std::collections::BTreeSet;
 856     ///
 857     /// let xs = [1, 2, 3, 4, 5, 6];
 858     /// let mut set: BTreeSet<i32> = xs.iter().cloned().collect();
 859     /// // Keep only the even numbers.
 860     /// set.retain(|&k| k % 2 == 0);
 861     /// assert!(set.iter().eq([2, 4, 6].iter()));
 862     /// ```
 863     #[unstable(feature = "btree_retain", issue = "79025")]
 864     pub fn retain<F>(&mut self, mut f: F)
 865     where
 866         T: Ord,
 867         F: FnMut(&T) -> bool,
 868     {
 869         self.drain_filter(|v| !f(v));
 870     }
 871
 872     /// Moves all elements from `other` into `Self`, leaving `other` empty.
 873     ///
 874     /// # Examples
 875     ///
 876     /// ```
 877     /// use std::collections::BTreeSet;
 878     ///
 879     /// let mut a = BTreeSet::new();
 880     /// a.insert(1);
 881     /// a.insert(2);
 882     /// a.insert(3);
 883     ///
 884     /// let mut b = BTreeSet::new();
 885     /// b.insert(3);
 886     /// b.insert(4);
 887     /// b.insert(5);
 888     ///
 889     /// a.append(&mut b);
 890     ///
 891     /// assert_eq!(a.len(), 5);
 892     /// assert_eq!(b.len(), 0);
 893     ///
 894     /// assert!(a.contains(&1));
 895     /// assert!(a.contains(&2));
 896     /// assert!(a.contains(&3));
 897     /// assert!(a.contains(&4));
 898     /// assert!(a.contains(&5));
 899     /// ```
 900     #[stable(feature = "btree_append", since = "1.11.0")]
 901     pub fn append(&mut self, other: &mut Self)
 902     where
 903         T: Ord,
 904     {
 905         self.map.append(&mut other.map);
 906     }
 907
 908     /// Splits the collection into two at the given key. Returns everything after the given key,
 909     /// including the key.
 910     ///
 911     /// # Examples
 912     ///
 913     /// Basic usage:
 914     ///
 915     /// ```
 916     /// use std::collections::BTreeSet;
 917     ///
 918     /// let mut a = BTreeSet::new();
 919     /// a.insert(1);
 920     /// a.insert(2);
 921     /// a.insert(3);
 922     /// a.insert(17);
 923     /// a.insert(41);
 924     ///
 925     /// let b = a.split_off(&3);
 926     ///
 927     /// assert_eq!(a.len(), 2);
 928     /// assert_eq!(b.len(), 3);
 929     ///
 930     /// assert!(a.contains(&1));
 931     /// assert!(a.contains(&2));
 932     ///
 933     /// assert!(b.contains(&3));
 934     /// assert!(b.contains(&17));
 935     /// assert!(b.contains(&41));
 936     /// ```
 937     #[stable(feature = "btree_split_off", since = "1.11.0")]
 938     pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
 939     where
 940         T: Borrow<Q> + Ord,
 941     {
 942         BTreeSet { map: self.map.split_off(key) }
 943     }
 944
 945     /// Creates an iterator which uses a closure to determine if a value should be removed.
 946     ///
 947     /// If the closure returns true, then the value is removed and yielded.
 948     /// If the closure returns false, the value will remain in the list and will not be yielded
 949     /// by the iterator.
 950     ///
 951     /// If the iterator is only partially consumed or not consumed at all, each of the remaining
 952     /// values will still be subjected to the closure and removed and dropped if it returns true.
 953     ///
 954     /// It is unspecified how many more values will be subjected to the closure
 955     /// if a panic occurs in the closure, or if a panic occurs while dropping a value, or if the
 956     /// `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     #[doc(alias = "length")]
1026     #[stable(feature = "rust1", since = "1.0.0")]
1027     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
1028     pub const fn len(&self) -> usize {
1029         self.map.len()
1030     }
1031
1032     /// Returns `true` if the set contains no elements.
1033     ///
1034     /// # Examples
1035     ///
1036     /// ```
1037     /// use std::collections::BTreeSet;
1038     ///
1039     /// let mut v = BTreeSet::new();
1040     /// assert!(v.is_empty());
1041     /// v.insert(1);
1042     /// assert!(!v.is_empty());
1043     /// ```
1044     #[stable(feature = "rust1", since = "1.0.0")]
1045     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
1046     pub const fn is_empty(&self) -> bool {
1047         self.len() == 0
1048     }
1049 }
1050
1051 #[stable(feature = "rust1", since = "1.0.0")]
1052 impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1053     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1054         let mut set = BTreeSet::new();
1055         set.extend(iter);
1056         set
1057     }
1058 }
1059
1060 #[stable(feature = "rust1", since = "1.0.0")]
1061 impl<T> IntoIterator for BTreeSet<T> {
1062     type Item = T;
1063     type IntoIter = IntoIter<T>;
1064
1065     /// Gets an iterator for moving out the `BTreeSet`'s contents.
1066     ///
1067     /// # Examples
1068     ///
1069     /// ```
1070     /// use std::collections::BTreeSet;
1071     ///
1072     /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
1073     ///
1074     /// let v: Vec<_> = set.into_iter().collect();
1075     /// assert_eq!(v, [1, 2, 3, 4]);
1076     /// ```
1077     fn into_iter(self) -> IntoIter<T> {
1078         IntoIter { iter: self.map.into_iter() }
1079     }
1080 }
1081
1082 #[stable(feature = "rust1", since = "1.0.0")]
1083 impl<'a, T> IntoIterator for &'a BTreeSet<T> {
1084     type Item = &'a T;
1085     type IntoIter = Iter<'a, T>;
1086
1087     fn into_iter(self) -> Iter<'a, T> {
1088         self.iter()
1089     }
1090 }
1091
1092 /// An iterator produced by calling `drain_filter` on BTreeSet.
1093 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1094 pub struct DrainFilter<'a, T, F>
1095 where
1096     T: 'a,
1097     F: 'a + FnMut(&T) -> bool,
1098 {
1099     pred: F,
1100     inner: super::map::DrainFilterInner<'a, T, ()>,
1101 }
1102
1103 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1104 impl<T, F> Drop for DrainFilter<'_, T, F>
1105 where
1106     F: FnMut(&T) -> bool,
1107 {
1108     fn drop(&mut self) {
1109         self.for_each(drop);
1110     }
1111 }
1112
1113 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1114 impl<T, F> fmt::Debug for DrainFilter<'_, T, F>
1115 where
1116     T: fmt::Debug,
1117     F: FnMut(&T) -> bool,
1118 {
1119     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1120         f.debug_tuple("DrainFilter").field(&self.inner.peek().map(|(k, _)| k)).finish()
1121     }
1122 }
1123
1124 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1125 impl<'a, T, F> Iterator for DrainFilter<'_, T, F>
1126 where
1127     F: 'a + FnMut(&T) -> bool,
1128 {
1129     type Item = T;
1130
1131     fn next(&mut self) -> Option<T> {
1132         let pred = &mut self.pred;
1133         let mut mapped_pred = |k: &T, _v: &mut ()| pred(k);
1134         self.inner.next(&mut mapped_pred).map(|(k, _)| k)
1135     }
1136
1137     fn size_hint(&self) -> (usize, Option<usize>) {
1138         self.inner.size_hint()
1139     }
1140 }
1141
1142 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1143 impl<T, F> FusedIterator for DrainFilter<'_, T, F> where F: FnMut(&T) -> bool {}
1144
1145 #[stable(feature = "rust1", since = "1.0.0")]
1146 impl<T: Ord> Extend<T> for BTreeSet<T> {
1147     #[inline]
1148     fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1149         iter.into_iter().for_each(move |elem| {
1150             self.insert(elem);
1151         });
1152     }
1153
1154     #[inline]
1155     fn extend_one(&mut self, elem: T) {
1156         self.insert(elem);
1157     }
1158 }
1159
1160 #[stable(feature = "extend_ref", since = "1.2.0")]
1161 impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> {
1162     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1163         self.extend(iter.into_iter().cloned());
1164     }
1165
1166     #[inline]
1167     fn extend_one(&mut self, &elem: &'a T) {
1168         self.insert(elem);
1169     }
1170 }
1171
1172 #[stable(feature = "rust1", since = "1.0.0")]
1173 impl<T: Ord> Default for BTreeSet<T> {
1174     /// Creates an empty `BTreeSet`.
1175     fn default() -> BTreeSet<T> {
1176         BTreeSet::new()
1177     }
1178 }
1179
1180 #[stable(feature = "rust1", since = "1.0.0")]
1181 impl<T: Ord + Clone> Sub<&BTreeSet<T>> for &BTreeSet<T> {
1182     type Output = BTreeSet<T>;
1183
1184     /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1185     ///
1186     /// # Examples
1187     ///
1188     /// ```
1189     /// use std::collections::BTreeSet;
1190     ///
1191     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1192     /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
1193     ///
1194     /// let result = &a - &b;
1195     /// let result_vec: Vec<_> = result.into_iter().collect();
1196     /// assert_eq!(result_vec, [1, 2]);
1197     /// ```
1198     fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1199         self.difference(rhs).cloned().collect()
1200     }
1201 }
1202
1203 #[stable(feature = "rust1", since = "1.0.0")]
1204 impl<T: Ord + Clone> BitXor<&BTreeSet<T>> for &BTreeSet<T> {
1205     type Output = BTreeSet<T>;
1206
1207     /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1208     ///
1209     /// # Examples
1210     ///
1211     /// ```
1212     /// use std::collections::BTreeSet;
1213     ///
1214     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1215     /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
1216     ///
1217     /// let result = &a ^ &b;
1218     /// let result_vec: Vec<_> = result.into_iter().collect();
1219     /// assert_eq!(result_vec, [1, 4]);
1220     /// ```
1221     fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1222         self.symmetric_difference(rhs).cloned().collect()
1223     }
1224 }
1225
1226 #[stable(feature = "rust1", since = "1.0.0")]
1227 impl<T: Ord + Clone> BitAnd<&BTreeSet<T>> for &BTreeSet<T> {
1228     type Output = BTreeSet<T>;
1229
1230     /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1231     ///
1232     /// # Examples
1233     ///
1234     /// ```
1235     /// use std::collections::BTreeSet;
1236     ///
1237     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1238     /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
1239     ///
1240     /// let result = &a & &b;
1241     /// let result_vec: Vec<_> = result.into_iter().collect();
1242     /// assert_eq!(result_vec, [2, 3]);
1243     /// ```
1244     fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1245         self.intersection(rhs).cloned().collect()
1246     }
1247 }
1248
1249 #[stable(feature = "rust1", since = "1.0.0")]
1250 impl<T: Ord + Clone> BitOr<&BTreeSet<T>> for &BTreeSet<T> {
1251     type Output = BTreeSet<T>;
1252
1253     /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1254     ///
1255     /// # Examples
1256     ///
1257     /// ```
1258     /// use std::collections::BTreeSet;
1259     ///
1260     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1261     /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
1262     ///
1263     /// let result = &a | &b;
1264     /// let result_vec: Vec<_> = result.into_iter().collect();
1265     /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
1266     /// ```
1267     fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
1268         self.union(rhs).cloned().collect()
1269     }
1270 }
1271
1272 #[stable(feature = "rust1", since = "1.0.0")]
1273 impl<T: Debug> Debug for BTreeSet<T> {
1274     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1275         f.debug_set().entries(self.iter()).finish()
1276     }
1277 }
1278
1279 #[stable(feature = "rust1", since = "1.0.0")]
1280 impl<T> Clone for Iter<'_, T> {
1281     fn clone(&self) -> Self {
1282         Iter { iter: self.iter.clone() }
1283     }
1284 }
1285 #[stable(feature = "rust1", since = "1.0.0")]
1286 impl<'a, T> Iterator for Iter<'a, T> {
1287     type Item = &'a T;
1288
1289     fn next(&mut self) -> Option<&'a T> {
1290         self.iter.next()
1291     }
1292
1293     fn size_hint(&self) -> (usize, Option<usize>) {
1294         self.iter.size_hint()
1295     }
1296
1297     fn last(mut self) -> Option<&'a T> {
1298         self.next_back()
1299     }
1300
1301     fn min(mut self) -> Option<&'a T> {
1302         self.next()
1303     }
1304
1305     fn max(mut self) -> Option<&'a T> {
1306         self.next_back()
1307     }
1308 }
1309 #[stable(feature = "rust1", since = "1.0.0")]
1310 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1311     fn next_back(&mut self) -> Option<&'a T> {
1312         self.iter.next_back()
1313     }
1314 }
1315 #[stable(feature = "rust1", since = "1.0.0")]
1316 impl<T> ExactSizeIterator for Iter<'_, T> {
1317     fn len(&self) -> usize {
1318         self.iter.len()
1319     }
1320 }
1321
1322 #[stable(feature = "fused", since = "1.26.0")]
1323 impl<T> FusedIterator for Iter<'_, T> {}
1324
1325 #[stable(feature = "rust1", since = "1.0.0")]
1326 impl<T> Iterator for IntoIter<T> {
1327     type Item = T;
1328
1329     fn next(&mut self) -> Option<T> {
1330         self.iter.next().map(|(k, _)| k)
1331     }
1332
1333     fn size_hint(&self) -> (usize, Option<usize>) {
1334         self.iter.size_hint()
1335     }
1336 }
1337 #[stable(feature = "rust1", since = "1.0.0")]
1338 impl<T> DoubleEndedIterator for IntoIter<T> {
1339     fn next_back(&mut self) -> Option<T> {
1340         self.iter.next_back().map(|(k, _)| k)
1341     }
1342 }
1343 #[stable(feature = "rust1", since = "1.0.0")]
1344 impl<T> ExactSizeIterator for IntoIter<T> {
1345     fn len(&self) -> usize {
1346         self.iter.len()
1347     }
1348 }
1349
1350 #[stable(feature = "fused", since = "1.26.0")]
1351 impl<T> FusedIterator for IntoIter<T> {}
1352
1353 #[stable(feature = "btree_range", since = "1.17.0")]
1354 impl<T> Clone for Range<'_, T> {
1355     fn clone(&self) -> Self {
1356         Range { iter: self.iter.clone() }
1357     }
1358 }
1359
1360 #[stable(feature = "btree_range", since = "1.17.0")]
1361 impl<'a, T> Iterator for Range<'a, T> {
1362     type Item = &'a T;
1363
1364     fn next(&mut self) -> Option<&'a T> {
1365         self.iter.next().map(|(k, _)| k)
1366     }
1367
1368     fn last(mut self) -> Option<&'a T> {
1369         self.next_back()
1370     }
1371
1372     fn min(mut self) -> Option<&'a T> {
1373         self.next()
1374     }
1375
1376     fn max(mut self) -> Option<&'a T> {
1377         self.next_back()
1378     }
1379 }
1380
1381 #[stable(feature = "btree_range", since = "1.17.0")]
1382 impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1383     fn next_back(&mut self) -> Option<&'a T> {
1384         self.iter.next_back().map(|(k, _)| k)
1385     }
1386 }
1387
1388 #[stable(feature = "fused", since = "1.26.0")]
1389 impl<T> FusedIterator for Range<'_, T> {}
1390
1391 #[stable(feature = "rust1", since = "1.0.0")]
1392 impl<T> Clone for Difference<'_, T> {
1393     fn clone(&self) -> Self {
1394         Difference {
1395             inner: match &self.inner {
1396                 DifferenceInner::Stitch { self_iter, other_iter } => DifferenceInner::Stitch {
1397                     self_iter: self_iter.clone(),
1398                     other_iter: other_iter.clone(),
1399                 },
1400                 DifferenceInner::Search { self_iter, other_set } => {
1401                     DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1402                 }
1403                 DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
1404             },
1405         }
1406     }
1407 }
1408 #[stable(feature = "rust1", since = "1.0.0")]
1409 impl<'a, T: Ord> Iterator for Difference<'a, T> {
1410     type Item = &'a T;
1411
1412     fn next(&mut self) -> Option<&'a T> {
1413         match &mut self.inner {
1414             DifferenceInner::Stitch { self_iter, other_iter } => {
1415                 let mut self_next = self_iter.next()?;
1416                 loop {
1417                     match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1418                         Less => return Some(self_next),
1419                         Equal => {
1420                             self_next = self_iter.next()?;
1421                             other_iter.next();
1422                         }
1423                         Greater => {
1424                             other_iter.next();
1425                         }
1426                     }
1427                 }
1428             }
1429             DifferenceInner::Search { self_iter, other_set } => loop {
1430                 let self_next = self_iter.next()?;
1431                 if !other_set.contains(&self_next) {
1432                     return Some(self_next);
1433                 }
1434             },
1435             DifferenceInner::Iterate(iter) => iter.next(),
1436         }
1437     }
1438
1439     fn size_hint(&self) -> (usize, Option<usize>) {
1440         let (self_len, other_len) = match &self.inner {
1441             DifferenceInner::Stitch { self_iter, other_iter } => {
1442                 (self_iter.len(), other_iter.len())
1443             }
1444             DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1445             DifferenceInner::Iterate(iter) => (iter.len(), 0),
1446         };
1447         (self_len.saturating_sub(other_len), Some(self_len))
1448     }
1449
1450     fn min(mut self) -> Option<&'a T> {
1451         self.next()
1452     }
1453 }
1454
1455 #[stable(feature = "fused", since = "1.26.0")]
1456 impl<T: Ord> FusedIterator for Difference<'_, T> {}
1457
1458 #[stable(feature = "rust1", since = "1.0.0")]
1459 impl<T> Clone for SymmetricDifference<'_, T> {
1460     fn clone(&self) -> Self {
1461         SymmetricDifference(self.0.clone())
1462     }
1463 }
1464 #[stable(feature = "rust1", since = "1.0.0")]
1465 impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
1466     type Item = &'a T;
1467
1468     fn next(&mut self) -> Option<&'a T> {
1469         loop {
1470             let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
1471             if a_next.and(b_next).is_none() {
1472                 return a_next.or(b_next);
1473             }
1474         }
1475     }
1476
1477     fn size_hint(&self) -> (usize, Option<usize>) {
1478         let (a_len, b_len) = self.0.lens();
1479         // No checked_add, because even if a and b refer to the same set,
1480         // and T is an empty type, the storage overhead of sets limits
1481         // the number of elements to less than half the range of usize.
1482         (0, Some(a_len + b_len))
1483     }
1484
1485     fn min(mut self) -> Option<&'a T> {
1486         self.next()
1487     }
1488 }
1489
1490 #[stable(feature = "fused", since = "1.26.0")]
1491 impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
1492
1493 #[stable(feature = "rust1", since = "1.0.0")]
1494 impl<T> Clone for Intersection<'_, T> {
1495     fn clone(&self) -> Self {
1496         Intersection {
1497             inner: match &self.inner {
1498                 IntersectionInner::Stitch { a, b } => {
1499                     IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
1500                 }
1501                 IntersectionInner::Search { small_iter, large_set } => {
1502                     IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
1503                 }
1504                 IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
1505             },
1506         }
1507     }
1508 }
1509 #[stable(feature = "rust1", since = "1.0.0")]
1510 impl<'a, T: Ord> Iterator for Intersection<'a, T> {
1511     type Item = &'a T;
1512
1513     fn next(&mut self) -> Option<&'a T> {
1514         match &mut self.inner {
1515             IntersectionInner::Stitch { a, b } => {
1516                 let mut a_next = a.next()?;
1517                 let mut b_next = b.next()?;
1518                 loop {
1519                     match a_next.cmp(b_next) {
1520                         Less => a_next = a.next()?,
1521                         Greater => b_next = b.next()?,
1522                         Equal => return Some(a_next),
1523                     }
1524                 }
1525             }
1526             IntersectionInner::Search { small_iter, large_set } => loop {
1527                 let small_next = small_iter.next()?;
1528                 if large_set.contains(&small_next) {
1529                     return Some(small_next);
1530                 }
1531             },
1532             IntersectionInner::Answer(answer) => answer.take(),
1533         }
1534     }
1535
1536     fn size_hint(&self) -> (usize, Option<usize>) {
1537         match &self.inner {
1538             IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
1539             IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
1540             IntersectionInner::Answer(None) => (0, Some(0)),
1541             IntersectionInner::Answer(Some(_)) => (1, Some(1)),
1542         }
1543     }
1544
1545     fn min(mut self) -> Option<&'a T> {
1546         self.next()
1547     }
1548 }
1549
1550 #[stable(feature = "fused", since = "1.26.0")]
1551 impl<T: Ord> FusedIterator for Intersection<'_, T> {}
1552
1553 #[stable(feature = "rust1", since = "1.0.0")]
1554 impl<T> Clone for Union<'_, T> {
1555     fn clone(&self) -> Self {
1556         Union(self.0.clone())
1557     }
1558 }
1559 #[stable(feature = "rust1", since = "1.0.0")]
1560 impl<'a, T: Ord> Iterator for Union<'a, T> {
1561     type Item = &'a T;
1562
1563     fn next(&mut self) -> Option<&'a T> {
1564         let (a_next, b_next) = self.0.nexts(Self::Item::cmp);
1565         a_next.or(b_next)
1566     }
1567
1568     fn size_hint(&self) -> (usize, Option<usize>) {
1569         let (a_len, b_len) = self.0.lens();
1570         // No checked_add - see SymmetricDifference::size_hint.
1571         (max(a_len, b_len), Some(a_len + b_len))
1572     }
1573
1574     fn min(mut self) -> Option<&'a T> {
1575         self.next()
1576     }
1577 }
1578
1579 #[stable(feature = "fused", since = "1.26.0")]
1580 impl<T: Ord> FusedIterator for Union<'_, T> {}
1581
1582 #[cfg(test)]
1583 mod tests;