1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface
14 use core::cmp::Ordering::{self, Less, Greater, Equal};
15 use core::cmp::{min, max};
18 use core::iter::{Peekable, FromIterator, FusedIterator};
19 use core::ops::{BitOr, BitAnd, BitXor, Sub, RangeBounds};
22 use collections::btree_map::{self, BTreeMap, Keys};
25 // FIXME(conventions): implement bounded iterators
27 /// A set based on a B-Tree.
29 /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
30 /// benefits and drawbacks.
32 /// It is a logic error for an item to be modified in such a way that the item's ordering relative
33 /// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
34 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
36 /// [`BTreeMap`]: struct.BTreeMap.html
37 /// [`Ord`]: ../../std/cmp/trait.Ord.html
38 /// [`Cell`]: ../../std/cell/struct.Cell.html
39 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
44 /// use std::collections::BTreeSet;
46 /// // Type inference lets us omit an explicit type signature (which
47 /// // would be `BTreeSet<&str>` in this example).
48 /// let mut books = BTreeSet::new();
50 /// // Add some books.
51 /// books.insert("A Dance With Dragons");
52 /// books.insert("To Kill a Mockingbird");
53 /// books.insert("The Odyssey");
54 /// books.insert("The Great Gatsby");
56 /// // Check for a specific one.
57 /// if !books.contains("The Winds of Winter") {
58 /// println!("We have {} books, but The Winds of Winter ain't one.",
63 /// books.remove("The Odyssey");
65 /// // Iterate over everything.
66 /// for book in &books {
67 /// println!("{}", book);
70 #[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
71 #[stable(feature = "rust1", since = "1.0.0")]
72 pub struct BTreeSet<T> {
76 /// An iterator over the items of a `BTreeSet`.
78 /// This `struct` is created by the [`iter`] method on [`BTreeSet`].
79 /// See its documentation for more.
81 /// [`BTreeSet`]: struct.BTreeSet.html
82 /// [`iter`]: struct.BTreeSet.html#method.iter
83 #[stable(feature = "rust1", since = "1.0.0")]
84 pub struct Iter<'a, T: 'a> {
85 iter: Keys<'a, T, ()>,
88 #[stable(feature = "collection_debug", since = "1.17.0")]
89 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
90 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
92 .field(&self.iter.clone())
97 /// An owning iterator over the items of a `BTreeSet`.
99 /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`][`BTreeSet`]
100 /// (provided by the `IntoIterator` trait). See its documentation for more.
102 /// [`BTreeSet`]: struct.BTreeSet.html
103 /// [`into_iter`]: struct.BTreeSet.html#method.into_iter
104 #[stable(feature = "rust1", since = "1.0.0")]
106 pub struct IntoIter<T> {
107 iter: btree_map::IntoIter<T, ()>,
110 /// An iterator over a sub-range of items in a `BTreeSet`.
112 /// This `struct` is created by the [`range`] method on [`BTreeSet`].
113 /// See its documentation for more.
115 /// [`BTreeSet`]: struct.BTreeSet.html
116 /// [`range`]: struct.BTreeSet.html#method.range
118 #[stable(feature = "btree_range", since = "1.17.0")]
119 pub struct Range<'a, T: 'a> {
120 iter: btree_map::Range<'a, T, ()>,
123 /// A lazy iterator producing elements in the difference of `BTreeSet`s.
125 /// This `struct` is created by the [`difference`] method on [`BTreeSet`].
126 /// See its documentation for more.
128 /// [`BTreeSet`]: struct.BTreeSet.html
129 /// [`difference`]: struct.BTreeSet.html#method.difference
130 #[stable(feature = "rust1", since = "1.0.0")]
131 pub struct Difference<'a, T: 'a> {
132 a: Peekable<Iter<'a, T>>,
133 b: Peekable<Iter<'a, T>>,
136 #[stable(feature = "collection_debug", since = "1.17.0")]
137 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Difference<'a, T> {
138 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
139 f.debug_tuple("Difference")
146 /// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s.
148 /// This `struct` is created by the [`symmetric_difference`] method on
149 /// [`BTreeSet`]. See its documentation for more.
151 /// [`BTreeSet`]: struct.BTreeSet.html
152 /// [`symmetric_difference`]: struct.BTreeSet.html#method.symmetric_difference
153 #[stable(feature = "rust1", since = "1.0.0")]
154 pub struct SymmetricDifference<'a, T: 'a> {
155 a: Peekable<Iter<'a, T>>,
156 b: Peekable<Iter<'a, T>>,
159 #[stable(feature = "collection_debug", since = "1.17.0")]
160 impl<'a, T: 'a + fmt::Debug> fmt::Debug for SymmetricDifference<'a, T> {
161 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
162 f.debug_tuple("SymmetricDifference")
169 /// A lazy iterator producing elements in the intersection of `BTreeSet`s.
171 /// This `struct` is created by the [`intersection`] method on [`BTreeSet`].
172 /// See its documentation for more.
174 /// [`BTreeSet`]: struct.BTreeSet.html
175 /// [`intersection`]: struct.BTreeSet.html#method.intersection
176 #[stable(feature = "rust1", since = "1.0.0")]
177 pub struct Intersection<'a, T: 'a> {
178 a: Peekable<Iter<'a, T>>,
179 b: Peekable<Iter<'a, T>>,
182 #[stable(feature = "collection_debug", since = "1.17.0")]
183 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Intersection<'a, T> {
184 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
185 f.debug_tuple("Intersection")
192 /// A lazy iterator producing elements in the union of `BTreeSet`s.
194 /// This `struct` is created by the [`union`] method on [`BTreeSet`].
195 /// See its documentation for more.
197 /// [`BTreeSet`]: struct.BTreeSet.html
198 /// [`union`]: struct.BTreeSet.html#method.union
199 #[stable(feature = "rust1", since = "1.0.0")]
200 pub struct Union<'a, T: 'a> {
201 a: Peekable<Iter<'a, T>>,
202 b: Peekable<Iter<'a, T>>,
205 #[stable(feature = "collection_debug", since = "1.17.0")]
206 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Union<'a, T> {
207 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
208 f.debug_tuple("Union")
215 impl<T: Ord> BTreeSet<T> {
216 /// Makes a new `BTreeSet` with a reasonable choice of B.
221 /// # #![allow(unused_mut)]
222 /// use std::collections::BTreeSet;
224 /// let mut set: BTreeSet<i32> = BTreeSet::new();
226 #[stable(feature = "rust1", since = "1.0.0")]
227 pub fn new() -> BTreeSet<T> {
228 BTreeSet { map: BTreeMap::new() }
231 /// Constructs a double-ended iterator over a sub-range of elements in the set.
232 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
233 /// yield elements from min (inclusive) to max (exclusive).
234 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
235 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
236 /// range from 4 to 10.
241 /// use std::collections::BTreeSet;
242 /// use std::ops::Bound::Included;
244 /// let mut set = BTreeSet::new();
248 /// for &elem in set.range((Included(&4), Included(&8))) {
249 /// println!("{}", elem);
251 /// assert_eq!(Some(&5), set.range(4..).next());
253 #[stable(feature = "btree_range", since = "1.17.0")]
254 pub fn range<K: ?Sized, R>(&self, range: R) -> Range<T>
255 where K: Ord, T: Borrow<K>, R: RangeBounds<K>
257 Range { iter: self.map.range(range) }
260 /// Visits the values representing the difference,
261 /// i.e., the values that are in `self` but not in `other`,
262 /// in ascending order.
267 /// use std::collections::BTreeSet;
269 /// let mut a = BTreeSet::new();
273 /// let mut b = BTreeSet::new();
277 /// let diff: Vec<_> = a.difference(&b).cloned().collect();
278 /// assert_eq!(diff, [1]);
280 #[stable(feature = "rust1", since = "1.0.0")]
281 pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> {
283 a: self.iter().peekable(),
284 b: other.iter().peekable(),
288 /// Visits the values representing the symmetric difference,
289 /// i.e., the values that are in `self` or in `other` but not in both,
290 /// in ascending order.
295 /// use std::collections::BTreeSet;
297 /// let mut a = BTreeSet::new();
301 /// let mut b = BTreeSet::new();
305 /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
306 /// assert_eq!(sym_diff, [1, 3]);
308 #[stable(feature = "rust1", since = "1.0.0")]
309 pub fn symmetric_difference<'a>(&'a self,
310 other: &'a BTreeSet<T>)
311 -> SymmetricDifference<'a, T> {
312 SymmetricDifference {
313 a: self.iter().peekable(),
314 b: other.iter().peekable(),
318 /// Visits the values representing the intersection,
319 /// i.e., the values that are both in `self` and `other`,
320 /// in ascending order.
325 /// use std::collections::BTreeSet;
327 /// let mut a = BTreeSet::new();
331 /// let mut b = BTreeSet::new();
335 /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
336 /// assert_eq!(intersection, [2]);
338 #[stable(feature = "rust1", since = "1.0.0")]
339 pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> {
341 a: self.iter().peekable(),
342 b: other.iter().peekable(),
346 /// Visits the values representing the union,
347 /// i.e., all the values in `self` or `other`, without duplicates,
348 /// in ascending order.
353 /// use std::collections::BTreeSet;
355 /// let mut a = BTreeSet::new();
358 /// let mut b = BTreeSet::new();
361 /// let union: Vec<_> = a.union(&b).cloned().collect();
362 /// assert_eq!(union, [1, 2]);
364 #[stable(feature = "rust1", since = "1.0.0")]
365 pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T> {
367 a: self.iter().peekable(),
368 b: other.iter().peekable(),
372 /// Clears the set, removing all values.
377 /// use std::collections::BTreeSet;
379 /// let mut v = BTreeSet::new();
382 /// assert!(v.is_empty());
384 #[stable(feature = "rust1", since = "1.0.0")]
385 pub fn clear(&mut self) {
389 /// Returns `true` if the set contains a value.
391 /// The value may be any borrowed form of the set's value type,
392 /// but the ordering on the borrowed form *must* match the
393 /// ordering on the value type.
398 /// use std::collections::BTreeSet;
400 /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
401 /// assert_eq!(set.contains(&1), true);
402 /// assert_eq!(set.contains(&4), false);
404 #[stable(feature = "rust1", since = "1.0.0")]
405 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
409 self.map.contains_key(value)
412 /// Returns a reference to the value in the set, if any, that is equal to the given value.
414 /// The value may be any borrowed form of the set's value type,
415 /// but the ordering on the borrowed form *must* match the
416 /// ordering on the value type.
421 /// use std::collections::BTreeSet;
423 /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
424 /// assert_eq!(set.get(&2), Some(&2));
425 /// assert_eq!(set.get(&4), None);
427 #[stable(feature = "set_recovery", since = "1.9.0")]
428 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
432 Recover::get(&self.map, value)
435 /// Returns `true` if `self` has no elements in common with `other`.
436 /// This is equivalent to checking for an empty intersection.
441 /// use std::collections::BTreeSet;
443 /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
444 /// let mut b = BTreeSet::new();
446 /// assert_eq!(a.is_disjoint(&b), true);
448 /// assert_eq!(a.is_disjoint(&b), true);
450 /// assert_eq!(a.is_disjoint(&b), false);
452 #[stable(feature = "rust1", since = "1.0.0")]
453 pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool {
454 self.intersection(other).next().is_none()
457 /// Returns `true` if the set is a subset of another,
458 /// i.e., `other` contains at least all the values in `self`.
463 /// use std::collections::BTreeSet;
465 /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
466 /// let mut set = BTreeSet::new();
468 /// assert_eq!(set.is_subset(&sup), true);
470 /// assert_eq!(set.is_subset(&sup), true);
472 /// assert_eq!(set.is_subset(&sup), false);
474 #[stable(feature = "rust1", since = "1.0.0")]
475 pub fn is_subset(&self, other: &BTreeSet<T>) -> bool {
476 // Stolen from TreeMap
477 let mut x = self.iter();
478 let mut y = other.iter();
479 let mut a = x.next();
480 let mut b = y.next();
491 Greater => return false,
492 Equal => a = x.next(),
500 /// Returns `true` if the set is a superset of another,
501 /// i.e., `self` contains at least all the values in `other`.
506 /// use std::collections::BTreeSet;
508 /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect();
509 /// let mut set = BTreeSet::new();
511 /// assert_eq!(set.is_superset(&sub), false);
515 /// assert_eq!(set.is_superset(&sub), false);
518 /// assert_eq!(set.is_superset(&sub), true);
520 #[stable(feature = "rust1", since = "1.0.0")]
521 pub fn is_superset(&self, other: &BTreeSet<T>) -> bool {
522 other.is_subset(self)
525 /// Adds a value to the set.
527 /// If the set did not have this value present, `true` is returned.
529 /// If the set did have this value present, `false` is returned, and the
530 /// entry is not updated. See the [module-level documentation] for more.
532 /// [module-level documentation]: index.html#insert-and-complex-keys
537 /// use std::collections::BTreeSet;
539 /// let mut set = BTreeSet::new();
541 /// assert_eq!(set.insert(2), true);
542 /// assert_eq!(set.insert(2), false);
543 /// assert_eq!(set.len(), 1);
545 #[stable(feature = "rust1", since = "1.0.0")]
546 pub fn insert(&mut self, value: T) -> bool {
547 self.map.insert(value, ()).is_none()
550 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
551 /// one. Returns the replaced value.
556 /// use std::collections::BTreeSet;
558 /// let mut set = BTreeSet::new();
559 /// set.insert(Vec::<i32>::new());
561 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
562 /// set.replace(Vec::with_capacity(10));
563 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
565 #[stable(feature = "set_recovery", since = "1.9.0")]
566 pub fn replace(&mut self, value: T) -> Option<T> {
567 Recover::replace(&mut self.map, value)
570 /// Removes a value from the set. Returns `true` if the value was
571 /// present in the set.
573 /// The value may be any borrowed form of the set's value type,
574 /// but the ordering on the borrowed form *must* match the
575 /// ordering on the value type.
580 /// use std::collections::BTreeSet;
582 /// let mut set = BTreeSet::new();
585 /// assert_eq!(set.remove(&2), true);
586 /// assert_eq!(set.remove(&2), false);
588 #[stable(feature = "rust1", since = "1.0.0")]
589 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
593 self.map.remove(value).is_some()
596 /// Removes and returns the value in the set, if any, that is equal to the given one.
598 /// The value may be any borrowed form of the set's value type,
599 /// but the ordering on the borrowed form *must* match the
600 /// ordering on the value type.
605 /// use std::collections::BTreeSet;
607 /// let mut set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
608 /// assert_eq!(set.take(&2), Some(2));
609 /// assert_eq!(set.take(&2), None);
611 #[stable(feature = "set_recovery", since = "1.9.0")]
612 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
616 Recover::take(&mut self.map, value)
619 /// Moves all elements from `other` into `Self`, leaving `other` empty.
624 /// use std::collections::BTreeSet;
626 /// let mut a = BTreeSet::new();
631 /// let mut b = BTreeSet::new();
636 /// a.append(&mut b);
638 /// assert_eq!(a.len(), 5);
639 /// assert_eq!(b.len(), 0);
641 /// assert!(a.contains(&1));
642 /// assert!(a.contains(&2));
643 /// assert!(a.contains(&3));
644 /// assert!(a.contains(&4));
645 /// assert!(a.contains(&5));
647 #[stable(feature = "btree_append", since = "1.11.0")]
648 pub fn append(&mut self, other: &mut Self) {
649 self.map.append(&mut other.map);
652 /// Splits the collection into two at the given key. Returns everything after the given key,
653 /// including the key.
660 /// use std::collections::BTreeSet;
662 /// let mut a = BTreeSet::new();
669 /// let b = a.split_off(&3);
671 /// assert_eq!(a.len(), 2);
672 /// assert_eq!(b.len(), 3);
674 /// assert!(a.contains(&1));
675 /// assert!(a.contains(&2));
677 /// assert!(b.contains(&3));
678 /// assert!(b.contains(&17));
679 /// assert!(b.contains(&41));
681 #[stable(feature = "btree_split_off", since = "1.11.0")]
682 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where T: Borrow<Q> {
683 BTreeSet { map: self.map.split_off(key) }
687 impl<T> BTreeSet<T> {
688 /// Gets an iterator that visits the values in the `BTreeSet` in ascending order.
693 /// use std::collections::BTreeSet;
695 /// let set: BTreeSet<usize> = [1, 2, 3].iter().cloned().collect();
696 /// let mut set_iter = set.iter();
697 /// assert_eq!(set_iter.next(), Some(&1));
698 /// assert_eq!(set_iter.next(), Some(&2));
699 /// assert_eq!(set_iter.next(), Some(&3));
700 /// assert_eq!(set_iter.next(), None);
703 /// Values returned by the iterator are returned in ascending order:
706 /// use std::collections::BTreeSet;
708 /// let set: BTreeSet<usize> = [3, 1, 2].iter().cloned().collect();
709 /// let mut set_iter = set.iter();
710 /// assert_eq!(set_iter.next(), Some(&1));
711 /// assert_eq!(set_iter.next(), Some(&2));
712 /// assert_eq!(set_iter.next(), Some(&3));
713 /// assert_eq!(set_iter.next(), None);
715 #[stable(feature = "rust1", since = "1.0.0")]
716 pub fn iter(&self) -> Iter<T> {
717 Iter { iter: self.map.keys() }
720 /// Returns the number of elements in the set.
725 /// use std::collections::BTreeSet;
727 /// let mut v = BTreeSet::new();
728 /// assert_eq!(v.len(), 0);
730 /// assert_eq!(v.len(), 1);
732 #[stable(feature = "rust1", since = "1.0.0")]
733 pub fn len(&self) -> usize {
737 /// Returns `true` if the set contains no elements.
742 /// use std::collections::BTreeSet;
744 /// let mut v = BTreeSet::new();
745 /// assert!(v.is_empty());
747 /// assert!(!v.is_empty());
749 #[stable(feature = "rust1", since = "1.0.0")]
750 pub fn is_empty(&self) -> bool {
755 #[stable(feature = "rust1", since = "1.0.0")]
756 impl<T: Ord> FromIterator<T> for BTreeSet<T> {
757 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
758 let mut set = BTreeSet::new();
764 #[stable(feature = "rust1", since = "1.0.0")]
765 impl<T> IntoIterator for BTreeSet<T> {
767 type IntoIter = IntoIter<T>;
769 /// Gets an iterator for moving out the `BTreeSet`'s contents.
774 /// use std::collections::BTreeSet;
776 /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
778 /// let v: Vec<_> = set.into_iter().collect();
779 /// assert_eq!(v, [1, 2, 3, 4]);
781 fn into_iter(self) -> IntoIter<T> {
782 IntoIter { iter: self.map.into_iter() }
786 #[stable(feature = "rust1", since = "1.0.0")]
787 impl<'a, T> IntoIterator for &'a BTreeSet<T> {
789 type IntoIter = Iter<'a, T>;
791 fn into_iter(self) -> Iter<'a, T> {
796 #[stable(feature = "rust1", since = "1.0.0")]
797 impl<T: Ord> Extend<T> for BTreeSet<T> {
799 fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
806 #[stable(feature = "extend_ref", since = "1.2.0")]
807 impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> {
808 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
809 self.extend(iter.into_iter().cloned());
813 #[stable(feature = "rust1", since = "1.0.0")]
814 impl<T: Ord> Default for BTreeSet<T> {
815 /// Makes an empty `BTreeSet<T>` with a reasonable choice of B.
816 fn default() -> BTreeSet<T> {
821 #[stable(feature = "rust1", since = "1.0.0")]
822 impl<'a, 'b, T: Ord + Clone> Sub<&'b BTreeSet<T>> for &'a BTreeSet<T> {
823 type Output = BTreeSet<T>;
825 /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
830 /// use std::collections::BTreeSet;
832 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
833 /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
835 /// let result = &a - &b;
836 /// let result_vec: Vec<_> = result.into_iter().collect();
837 /// assert_eq!(result_vec, [1, 2]);
839 fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
840 self.difference(rhs).cloned().collect()
844 #[stable(feature = "rust1", since = "1.0.0")]
845 impl<'a, 'b, T: Ord + Clone> BitXor<&'b BTreeSet<T>> for &'a BTreeSet<T> {
846 type Output = BTreeSet<T>;
848 /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
853 /// use std::collections::BTreeSet;
855 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
856 /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
858 /// let result = &a ^ &b;
859 /// let result_vec: Vec<_> = result.into_iter().collect();
860 /// assert_eq!(result_vec, [1, 4]);
862 fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
863 self.symmetric_difference(rhs).cloned().collect()
867 #[stable(feature = "rust1", since = "1.0.0")]
868 impl<'a, 'b, T: Ord + Clone> BitAnd<&'b BTreeSet<T>> for &'a BTreeSet<T> {
869 type Output = BTreeSet<T>;
871 /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
876 /// use std::collections::BTreeSet;
878 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
879 /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
881 /// let result = &a & &b;
882 /// let result_vec: Vec<_> = result.into_iter().collect();
883 /// assert_eq!(result_vec, [2, 3]);
885 fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
886 self.intersection(rhs).cloned().collect()
890 #[stable(feature = "rust1", since = "1.0.0")]
891 impl<'a, 'b, T: Ord + Clone> BitOr<&'b BTreeSet<T>> for &'a BTreeSet<T> {
892 type Output = BTreeSet<T>;
894 /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
899 /// use std::collections::BTreeSet;
901 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
902 /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
904 /// let result = &a | &b;
905 /// let result_vec: Vec<_> = result.into_iter().collect();
906 /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
908 fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
909 self.union(rhs).cloned().collect()
913 #[stable(feature = "rust1", since = "1.0.0")]
914 impl<T: Debug> Debug for BTreeSet<T> {
915 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
916 f.debug_set().entries(self.iter()).finish()
920 #[stable(feature = "rust1", since = "1.0.0")]
921 impl<'a, T> Clone for Iter<'a, T> {
922 fn clone(&self) -> Iter<'a, T> {
923 Iter { iter: self.iter.clone() }
926 #[stable(feature = "rust1", since = "1.0.0")]
927 impl<'a, T> Iterator for Iter<'a, T> {
930 fn next(&mut self) -> Option<&'a T> {
933 fn size_hint(&self) -> (usize, Option<usize>) {
934 self.iter.size_hint()
937 #[stable(feature = "rust1", since = "1.0.0")]
938 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
939 fn next_back(&mut self) -> Option<&'a T> {
940 self.iter.next_back()
943 #[stable(feature = "rust1", since = "1.0.0")]
944 impl<'a, T> ExactSizeIterator for Iter<'a, T> {
945 fn len(&self) -> usize { self.iter.len() }
948 #[stable(feature = "fused", since = "1.26.0")]
949 impl<'a, T> FusedIterator for Iter<'a, T> {}
951 #[stable(feature = "rust1", since = "1.0.0")]
952 impl<T> Iterator for IntoIter<T> {
955 fn next(&mut self) -> Option<T> {
956 self.iter.next().map(|(k, _)| k)
958 fn size_hint(&self) -> (usize, Option<usize>) {
959 self.iter.size_hint()
962 #[stable(feature = "rust1", since = "1.0.0")]
963 impl<T> DoubleEndedIterator for IntoIter<T> {
964 fn next_back(&mut self) -> Option<T> {
965 self.iter.next_back().map(|(k, _)| k)
968 #[stable(feature = "rust1", since = "1.0.0")]
969 impl<T> ExactSizeIterator for IntoIter<T> {
970 fn len(&self) -> usize { self.iter.len() }
973 #[stable(feature = "fused", since = "1.26.0")]
974 impl<T> FusedIterator for IntoIter<T> {}
976 #[stable(feature = "btree_range", since = "1.17.0")]
977 impl<'a, T> Clone for Range<'a, T> {
978 fn clone(&self) -> Range<'a, T> {
979 Range { iter: self.iter.clone() }
983 #[stable(feature = "btree_range", since = "1.17.0")]
984 impl<'a, T> Iterator for Range<'a, T> {
987 fn next(&mut self) -> Option<&'a T> {
988 self.iter.next().map(|(k, _)| k)
992 #[stable(feature = "btree_range", since = "1.17.0")]
993 impl<'a, T> DoubleEndedIterator for Range<'a, T> {
994 fn next_back(&mut self) -> Option<&'a T> {
995 self.iter.next_back().map(|(k, _)| k)
999 #[stable(feature = "fused", since = "1.26.0")]
1000 impl<'a, T> FusedIterator for Range<'a, T> {}
1002 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
1003 fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering {
1007 (Some(x1), Some(y1)) => x1.cmp(y1),
1011 #[stable(feature = "rust1", since = "1.0.0")]
1012 impl<'a, T> Clone for Difference<'a, T> {
1013 fn clone(&self) -> Difference<'a, T> {
1020 #[stable(feature = "rust1", since = "1.0.0")]
1021 impl<'a, T: Ord> Iterator for Difference<'a, T> {
1024 fn next(&mut self) -> Option<&'a T> {
1026 match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
1027 Less => return self.a.next(),
1039 fn size_hint(&self) -> (usize, Option<usize>) {
1040 let a_len = self.a.len();
1041 let b_len = self.b.len();
1042 (a_len.saturating_sub(b_len), Some(a_len))
1046 #[stable(feature = "fused", since = "1.26.0")]
1047 impl<'a, T: Ord> FusedIterator for Difference<'a, T> {}
1049 #[stable(feature = "rust1", since = "1.0.0")]
1050 impl<'a, T> Clone for SymmetricDifference<'a, T> {
1051 fn clone(&self) -> SymmetricDifference<'a, T> {
1052 SymmetricDifference {
1058 #[stable(feature = "rust1", since = "1.0.0")]
1059 impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
1062 fn next(&mut self) -> Option<&'a T> {
1064 match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
1065 Less => return self.a.next(),
1070 Greater => return self.b.next(),
1075 fn size_hint(&self) -> (usize, Option<usize>) {
1076 (0, Some(self.a.len() + self.b.len()))
1080 #[stable(feature = "fused", since = "1.26.0")]
1081 impl<'a, T: Ord> FusedIterator for SymmetricDifference<'a, T> {}
1083 #[stable(feature = "rust1", since = "1.0.0")]
1084 impl<'a, T> Clone for Intersection<'a, T> {
1085 fn clone(&self) -> Intersection<'a, T> {
1092 #[stable(feature = "rust1", since = "1.0.0")]
1093 impl<'a, T: Ord> Iterator for Intersection<'a, T> {
1096 fn next(&mut self) -> Option<&'a T> {
1098 match Ord::cmp(self.a.peek()?, self.b.peek()?) {
1104 return self.a.next();
1113 fn size_hint(&self) -> (usize, Option<usize>) {
1114 (0, Some(min(self.a.len(), self.b.len())))
1118 #[stable(feature = "fused", since = "1.26.0")]
1119 impl<'a, T: Ord> FusedIterator for Intersection<'a, T> {}
1121 #[stable(feature = "rust1", since = "1.0.0")]
1122 impl<'a, T> Clone for Union<'a, T> {
1123 fn clone(&self) -> Union<'a, T> {
1130 #[stable(feature = "rust1", since = "1.0.0")]
1131 impl<'a, T: Ord> Iterator for Union<'a, T> {
1134 fn next(&mut self) -> Option<&'a T> {
1135 match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
1136 Less => self.a.next(),
1141 Greater => self.b.next(),
1145 fn size_hint(&self) -> (usize, Option<usize>) {
1146 let a_len = self.a.len();
1147 let b_len = self.b.len();
1148 (max(a_len, b_len), Some(a_len + b_len))
1152 #[stable(feature = "fused", since = "1.26.0")]
1153 impl<'a, T: Ord> FusedIterator for Union<'a, T> {}