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