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}
;
22 use btree_map
::{BTreeMap, Keys}
;
24 use range
::RangeArgument
;
26 // FIXME(conventions): implement bounded iterators
28 /// A set based on a B-Tree.
30 /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
31 /// benefits and drawbacks.
33 /// It is a logic error for an item to be modified in such a way that the item's ordering relative
34 /// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
35 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
37 /// [`BTreeMap`]: struct.BTreeMap.html
38 /// [`Ord`]: ../../std/cmp/trait.Ord.html
39 /// [`Cell`]: ../../std/cell/struct.Cell.html
40 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
45 /// use std::collections::BTreeSet;
47 /// // Type inference lets us omit an explicit type signature (which
48 /// // would be `BTreeSet<&str>` in this example).
49 /// let mut books = BTreeSet::new();
51 /// // Add some books.
52 /// books.insert("A Dance With Dragons");
53 /// books.insert("To Kill a Mockingbird");
54 /// books.insert("The Odyssey");
55 /// books.insert("The Great Gatsby");
57 /// // Check for a specific one.
58 /// if !books.contains("The Winds of Winter") {
59 /// println!("We have {} books, but The Winds of Winter ain't one.",
64 /// books.remove("The Odyssey");
66 /// // Iterate over everything.
67 /// for book in &books {
68 /// println!("{}", book);
71 #[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
72 #[stable(feature = "rust1", since = "1.0.0")]
73 pub struct BTreeSet
<T
> {
77 /// An iterator over a `BTreeSet`'s items.
79 /// This structure is created by the [`iter`] method on [`BTreeSet`].
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 a `BTreeSet`'s items.
99 /// This structure is created by the `into_iter` method on [`BTreeSet`]
100 /// [`BTreeSet`] (provided by the `IntoIterator` trait).
102 /// [`BTreeSet`]: struct.BTreeSet.html
103 #[stable(feature = "rust1", since = "1.0.0")]
105 pub struct IntoIter
<T
> {
106 iter
: ::btree_map
::IntoIter
<T
, ()>,
109 /// An iterator over a sub-range of `BTreeSet`'s items.
111 /// This structure is created by the [`range`] method on [`BTreeSet`].
113 /// [`BTreeSet`]: struct.BTreeSet.html
114 /// [`range`]: struct.BTreeSet.html#method.range
116 #[stable(feature = "btree_range", since = "1.17.0")]
117 pub struct Range
<'a
, T
: 'a
> {
118 iter
: ::btree_map
::Range
<'a
, T
, ()>,
121 /// A lazy iterator producing elements in the set difference (in-order).
123 /// This structure is created by the [`difference`] method on [`BTreeSet`].
125 /// [`BTreeSet`]: struct.BTreeSet.html
126 /// [`difference`]: struct.BTreeSet.html#method.difference
127 #[stable(feature = "rust1", since = "1.0.0")]
128 pub struct Difference
<'a
, T
: 'a
> {
129 a
: Peekable
<Iter
<'a
, T
>>,
130 b
: Peekable
<Iter
<'a
, T
>>,
133 #[stable(feature = "collection_debug", since = "1.17.0")]
134 impl<'a
, T
: 'a
+ fmt
::Debug
> fmt
::Debug
for Difference
<'a
, T
> {
135 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
136 f
.debug_tuple("Difference")
137 .field(&self.clone())
142 /// A lazy iterator producing elements in the set symmetric difference (in-order).
144 /// This structure is created by the [`symmetric_difference`] method on
147 /// [`BTreeSet`]: struct.BTreeSet.html
148 /// [`symmetric_difference`]: struct.BTreeSet.html#method.symmetric_difference
149 #[stable(feature = "rust1", since = "1.0.0")]
150 pub struct SymmetricDifference
<'a
, T
: 'a
> {
151 a
: Peekable
<Iter
<'a
, T
>>,
152 b
: Peekable
<Iter
<'a
, T
>>,
155 #[stable(feature = "collection_debug", since = "1.17.0")]
156 impl<'a
, T
: 'a
+ fmt
::Debug
> fmt
::Debug
for SymmetricDifference
<'a
, T
> {
157 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
158 f
.debug_tuple("SymmetricDifference")
159 .field(&self.clone())
164 /// A lazy iterator producing elements in the set intersection (in-order).
166 /// This structure is created by the [`intersection`] method on [`BTreeSet`].
168 /// [`BTreeSet`]: struct.BTreeSet.html
169 /// [`intersection`]: struct.BTreeSet.html#method.intersection
170 #[stable(feature = "rust1", since = "1.0.0")]
171 pub struct Intersection
<'a
, T
: 'a
> {
172 a
: Peekable
<Iter
<'a
, T
>>,
173 b
: Peekable
<Iter
<'a
, T
>>,
176 #[stable(feature = "collection_debug", since = "1.17.0")]
177 impl<'a
, T
: 'a
+ fmt
::Debug
> fmt
::Debug
for Intersection
<'a
, T
> {
178 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
179 f
.debug_tuple("Intersection")
180 .field(&self.clone())
185 /// A lazy iterator producing elements in the set union (in-order).
187 /// This structure is created by the [`union`] method on [`BTreeSet`].
189 /// [`BTreeSet`]: struct.BTreeSet.html
190 /// [`union`]: struct.BTreeSet.html#method.union
191 #[stable(feature = "rust1", since = "1.0.0")]
192 pub struct Union
<'a
, T
: 'a
> {
193 a
: Peekable
<Iter
<'a
, T
>>,
194 b
: Peekable
<Iter
<'a
, T
>>,
197 #[stable(feature = "collection_debug", since = "1.17.0")]
198 impl<'a
, T
: 'a
+ fmt
::Debug
> fmt
::Debug
for Union
<'a
, T
> {
199 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
200 f
.debug_tuple("Union")
201 .field(&self.clone())
206 impl<T
: Ord
> BTreeSet
<T
> {
207 /// Makes a new `BTreeSet` with a reasonable choice of B.
212 /// # #![allow(unused_mut)]
213 /// use std::collections::BTreeSet;
215 /// let mut set: BTreeSet<i32> = BTreeSet::new();
217 #[stable(feature = "rust1", since = "1.0.0")]
218 pub fn new() -> BTreeSet
<T
> {
219 BTreeSet { map: BTreeMap::new() }
223 impl<T
> BTreeSet
<T
> {
224 /// Gets an iterator that visits the values in the `BTreeSet` in ascending order.
229 /// use std::collections::BTreeSet;
231 /// let set: BTreeSet<usize> = [1, 2, 3].iter().cloned().collect();
232 /// let mut set_iter = set.iter();
233 /// assert_eq!(set_iter.next(), Some(&1));
234 /// assert_eq!(set_iter.next(), Some(&2));
235 /// assert_eq!(set_iter.next(), Some(&3));
236 /// assert_eq!(set_iter.next(), None);
239 /// Values returned by the iterator are returned in ascending order:
242 /// use std::collections::BTreeSet;
244 /// let set: BTreeSet<usize> = [3, 1, 2].iter().cloned().collect();
245 /// let mut set_iter = set.iter();
246 /// assert_eq!(set_iter.next(), Some(&1));
247 /// assert_eq!(set_iter.next(), Some(&2));
248 /// assert_eq!(set_iter.next(), Some(&3));
249 /// assert_eq!(set_iter.next(), None);
251 #[stable(feature = "rust1", since = "1.0.0")]
252 pub fn iter(&self) -> Iter
<T
> {
253 Iter { iter: self.map.keys() }
257 impl<T
: Ord
> BTreeSet
<T
> {
258 /// Constructs a double-ended iterator over a sub-range of elements in the set.
259 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
260 /// yield elements from min (inclusive) to max (exclusive).
261 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
262 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
263 /// range from 4 to 10.
268 /// use std::collections::BTreeSet;
269 /// use std::collections::Bound::Included;
271 /// let mut set = BTreeSet::new();
275 /// for &elem in set.range((Included(&4), Included(&8))) {
276 /// println!("{}", elem);
278 /// assert_eq!(Some(&5), set.range(4..).next());
280 #[stable(feature = "btree_range", since = "1.17.0")]
281 pub fn range
<K
: ?Sized
, R
>(&self, range
: R
) -> Range
<T
>
282 where K
: Ord
, T
: Borrow
<K
>, R
: RangeArgument
<K
>
284 Range { iter: self.map.range(range) }
288 impl<T
: Ord
> BTreeSet
<T
> {
289 /// Visits the values representing the difference,
290 /// i.e. the values that are in `self` but not in `other`,
291 /// in ascending order.
296 /// use std::collections::BTreeSet;
298 /// let mut a = BTreeSet::new();
302 /// let mut b = BTreeSet::new();
306 /// let diff: Vec<_> = a.difference(&b).cloned().collect();
307 /// assert_eq!(diff, [1]);
309 #[stable(feature = "rust1", since = "1.0.0")]
310 pub fn difference
<'a
>(&'a
self, other
: &'a BTreeSet
<T
>) -> Difference
<'a
, T
> {
312 a
: self.iter().peekable(),
313 b
: other
.iter().peekable(),
317 /// Visits the values representing the symmetric difference,
318 /// i.e. the values that are in `self` or in `other` but not in both,
319 /// in ascending order.
324 /// use std::collections::BTreeSet;
326 /// let mut a = BTreeSet::new();
330 /// let mut b = BTreeSet::new();
334 /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
335 /// assert_eq!(sym_diff, [1, 3]);
337 #[stable(feature = "rust1", since = "1.0.0")]
338 pub fn symmetric_difference
<'a
>(&'a
self,
339 other
: &'a BTreeSet
<T
>)
340 -> SymmetricDifference
<'a
, T
> {
341 SymmetricDifference
{
342 a
: self.iter().peekable(),
343 b
: other
.iter().peekable(),
347 /// Visits the values representing the intersection,
348 /// i.e. the values that are both in `self` and `other`,
349 /// in ascending order.
354 /// use std::collections::BTreeSet;
356 /// let mut a = BTreeSet::new();
360 /// let mut b = BTreeSet::new();
364 /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
365 /// assert_eq!(intersection, [2]);
367 #[stable(feature = "rust1", since = "1.0.0")]
368 pub fn intersection
<'a
>(&'a
self, other
: &'a BTreeSet
<T
>) -> Intersection
<'a
, T
> {
370 a
: self.iter().peekable(),
371 b
: other
.iter().peekable(),
375 /// Visits the values representing the union,
376 /// i.e. all the values in `self` or `other`, without duplicates,
377 /// in ascending order.
382 /// use std::collections::BTreeSet;
384 /// let mut a = BTreeSet::new();
387 /// let mut b = BTreeSet::new();
390 /// let union: Vec<_> = a.union(&b).cloned().collect();
391 /// assert_eq!(union, [1, 2]);
393 #[stable(feature = "rust1", since = "1.0.0")]
394 pub fn union<'a
>(&'a
self, other
: &'a BTreeSet
<T
>) -> Union
<'a
, T
> {
396 a
: self.iter().peekable(),
397 b
: other
.iter().peekable(),
401 /// Returns the number of elements in the set.
406 /// use std::collections::BTreeSet;
408 /// let mut v = BTreeSet::new();
409 /// assert_eq!(v.len(), 0);
411 /// assert_eq!(v.len(), 1);
413 #[stable(feature = "rust1", since = "1.0.0")]
414 pub fn len(&self) -> usize {
418 /// Returns true if the set contains no elements.
423 /// use std::collections::BTreeSet;
425 /// let mut v = BTreeSet::new();
426 /// assert!(v.is_empty());
428 /// assert!(!v.is_empty());
430 #[stable(feature = "rust1", since = "1.0.0")]
431 pub fn is_empty(&self) -> bool
{
435 /// Clears the set, removing all values.
440 /// use std::collections::BTreeSet;
442 /// let mut v = BTreeSet::new();
445 /// assert!(v.is_empty());
447 #[stable(feature = "rust1", since = "1.0.0")]
448 pub fn clear(&mut self) {
452 /// Returns `true` if the set contains a value.
454 /// The value may be any borrowed form of the set's value type,
455 /// but the ordering on the borrowed form *must* match the
456 /// ordering on the value type.
461 /// use std::collections::BTreeSet;
463 /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
464 /// assert_eq!(set.contains(&1), true);
465 /// assert_eq!(set.contains(&4), false);
467 #[stable(feature = "rust1", since = "1.0.0")]
468 pub fn contains
<Q
: ?Sized
>(&self, value
: &Q
) -> bool
472 self.map
.contains_key(value
)
475 /// Returns a reference to the value in the set, if any, that is equal to the given value.
477 /// The value may be any borrowed form of the set's value type,
478 /// but the ordering on the borrowed form *must* match the
479 /// ordering on the value type.
480 #[stable(feature = "set_recovery", since = "1.9.0")]
481 pub fn get
<Q
: ?Sized
>(&self, value
: &Q
) -> Option
<&T
>
485 Recover
::get(&self.map
, value
)
488 /// Returns `true` if `self` has no elements in common with `other`.
489 /// This is equivalent to checking for an empty intersection.
494 /// use std::collections::BTreeSet;
496 /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
497 /// let mut b = BTreeSet::new();
499 /// assert_eq!(a.is_disjoint(&b), true);
501 /// assert_eq!(a.is_disjoint(&b), true);
503 /// assert_eq!(a.is_disjoint(&b), false);
505 #[stable(feature = "rust1", since = "1.0.0")]
506 pub fn is_disjoint(&self, other
: &BTreeSet
<T
>) -> bool
{
507 self.intersection(other
).next().is_none()
510 /// Returns `true` if the set is a subset of another,
511 /// i.e. `other` contains at least all the values in `self`.
516 /// use std::collections::BTreeSet;
518 /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
519 /// let mut set = BTreeSet::new();
521 /// assert_eq!(set.is_subset(&sup), true);
523 /// assert_eq!(set.is_subset(&sup), true);
525 /// assert_eq!(set.is_subset(&sup), false);
527 #[stable(feature = "rust1", since = "1.0.0")]
528 pub fn is_subset(&self, other
: &BTreeSet
<T
>) -> bool
{
529 // Stolen from TreeMap
530 let mut x
= self.iter();
531 let mut y
= other
.iter();
532 let mut a
= x
.next();
533 let mut b
= y
.next();
544 Greater
=> return false,
545 Equal
=> a
= x
.next(),
553 /// Returns `true` if the set is a superset of another,
554 /// i.e. `self` contains at least all the values in `other`.
559 /// use std::collections::BTreeSet;
561 /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect();
562 /// let mut set = BTreeSet::new();
564 /// assert_eq!(set.is_superset(&sub), false);
568 /// assert_eq!(set.is_superset(&sub), false);
571 /// assert_eq!(set.is_superset(&sub), true);
573 #[stable(feature = "rust1", since = "1.0.0")]
574 pub fn is_superset(&self, other
: &BTreeSet
<T
>) -> bool
{
575 other
.is_subset(self)
578 /// Adds a value to the set.
580 /// If the set did not have this value present, `true` is returned.
582 /// If the set did have this value present, `false` is returned, and the
583 /// entry is not updated. See the [module-level documentation] for more.
585 /// [module-level documentation]: index.html#insert-and-complex-keys
590 /// use std::collections::BTreeSet;
592 /// let mut set = BTreeSet::new();
594 /// assert_eq!(set.insert(2), true);
595 /// assert_eq!(set.insert(2), false);
596 /// assert_eq!(set.len(), 1);
598 #[stable(feature = "rust1", since = "1.0.0")]
599 pub fn insert(&mut self, value
: T
) -> bool
{
600 self.map
.insert(value
, ()).is_none()
603 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
604 /// one. Returns the replaced value.
605 #[stable(feature = "set_recovery", since = "1.9.0")]
606 pub fn replace(&mut self, value
: T
) -> Option
<T
> {
607 Recover
::replace(&mut self.map
, value
)
610 /// Removes a value from the set. Returns `true` if the value was
611 /// present in the set.
613 /// The value may be any borrowed form of the set's value type,
614 /// but the ordering on the borrowed form *must* match the
615 /// ordering on the value type.
620 /// use std::collections::BTreeSet;
622 /// let mut set = BTreeSet::new();
625 /// assert_eq!(set.remove(&2), true);
626 /// assert_eq!(set.remove(&2), false);
628 #[stable(feature = "rust1", since = "1.0.0")]
629 pub fn remove
<Q
: ?Sized
>(&mut self, value
: &Q
) -> bool
633 self.map
.remove(value
).is_some()
636 /// Removes and returns the value in the set, if any, that is equal to the given one.
638 /// The value may be any borrowed form of the set's value type,
639 /// but the ordering on the borrowed form *must* match the
640 /// ordering on the value type.
641 #[stable(feature = "set_recovery", since = "1.9.0")]
642 pub fn take
<Q
: ?Sized
>(&mut self, value
: &Q
) -> Option
<T
>
646 Recover
::take(&mut self.map
, value
)
649 /// Moves all elements from `other` into `Self`, leaving `other` empty.
654 /// use std::collections::BTreeSet;
656 /// let mut a = BTreeSet::new();
661 /// let mut b = BTreeSet::new();
666 /// a.append(&mut b);
668 /// assert_eq!(a.len(), 5);
669 /// assert_eq!(b.len(), 0);
671 /// assert!(a.contains(&1));
672 /// assert!(a.contains(&2));
673 /// assert!(a.contains(&3));
674 /// assert!(a.contains(&4));
675 /// assert!(a.contains(&5));
677 #[stable(feature = "btree_append", since = "1.11.0")]
678 pub fn append(&mut self, other
: &mut Self) {
679 self.map
.append(&mut other
.map
);
682 /// Splits the collection into two at the given key. Returns everything after the given key,
683 /// including the key.
690 /// use std::collections::BTreeMap;
692 /// let mut a = BTreeMap::new();
693 /// a.insert(1, "a");
694 /// a.insert(2, "b");
695 /// a.insert(3, "c");
696 /// a.insert(17, "d");
697 /// a.insert(41, "e");
699 /// let b = a.split_off(&3);
701 /// assert_eq!(a.len(), 2);
702 /// assert_eq!(b.len(), 3);
704 /// assert_eq!(a[&1], "a");
705 /// assert_eq!(a[&2], "b");
707 /// assert_eq!(b[&3], "c");
708 /// assert_eq!(b[&17], "d");
709 /// assert_eq!(b[&41], "e");
711 #[stable(feature = "btree_split_off", since = "1.11.0")]
712 pub fn split_off
<Q
: ?Sized
+ Ord
>(&mut self, key
: &Q
) -> Self where T
: Borrow
<Q
> {
713 BTreeSet { map: self.map.split_off(key) }
717 #[stable(feature = "rust1", since = "1.0.0")]
718 impl<T
: Ord
> FromIterator
<T
> for BTreeSet
<T
> {
719 fn from_iter
<I
: IntoIterator
<Item
= T
>>(iter
: I
) -> BTreeSet
<T
> {
720 let mut set
= BTreeSet
::new();
726 #[stable(feature = "rust1", since = "1.0.0")]
727 impl<T
> IntoIterator
for BTreeSet
<T
> {
729 type IntoIter
= IntoIter
<T
>;
731 /// Gets an iterator for moving out the BtreeSet's contents.
736 /// use std::collections::BTreeSet;
738 /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
740 /// let v: Vec<_> = set.into_iter().collect();
741 /// assert_eq!(v, [1, 2, 3, 4]);
743 fn into_iter(self) -> IntoIter
<T
> {
744 IntoIter { iter: self.map.into_iter() }
748 #[stable(feature = "rust1", since = "1.0.0")]
749 impl<'a
, T
> IntoIterator
for &'a BTreeSet
<T
> {
751 type IntoIter
= Iter
<'a
, T
>;
753 fn into_iter(self) -> Iter
<'a
, T
> {
758 #[stable(feature = "rust1", since = "1.0.0")]
759 impl<T
: Ord
> Extend
<T
> for BTreeSet
<T
> {
761 fn extend
<Iter
: IntoIterator
<Item
= T
>>(&mut self, iter
: Iter
) {
768 #[stable(feature = "extend_ref", since = "1.2.0")]
769 impl<'a
, T
: 'a
+ Ord
+ Copy
> Extend
<&'a T
> for BTreeSet
<T
> {
770 fn extend
<I
: IntoIterator
<Item
= &'a T
>>(&mut self, iter
: I
) {
771 self.extend(iter
.into_iter().cloned());
775 #[stable(feature = "rust1", since = "1.0.0")]
776 impl<T
: Ord
> Default
for BTreeSet
<T
> {
777 /// Makes an empty `BTreeSet<T>` with a reasonable choice of B.
778 fn default() -> BTreeSet
<T
> {
783 #[stable(feature = "rust1", since = "1.0.0")]
784 impl<'a
, 'b
, T
: Ord
+ Clone
> Sub
<&'b BTreeSet
<T
>> for &'a BTreeSet
<T
> {
785 type Output
= BTreeSet
<T
>;
787 /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
792 /// use std::collections::BTreeSet;
794 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
795 /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
797 /// let result = &a - &b;
798 /// let result_vec: Vec<_> = result.into_iter().collect();
799 /// assert_eq!(result_vec, [1, 2]);
801 fn sub(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
802 self.difference(rhs
).cloned().collect()
806 #[stable(feature = "rust1", since = "1.0.0")]
807 impl<'a
, 'b
, T
: Ord
+ Clone
> BitXor
<&'b BTreeSet
<T
>> for &'a BTreeSet
<T
> {
808 type Output
= BTreeSet
<T
>;
810 /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
815 /// use std::collections::BTreeSet;
817 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
818 /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
820 /// let result = &a ^ &b;
821 /// let result_vec: Vec<_> = result.into_iter().collect();
822 /// assert_eq!(result_vec, [1, 4]);
824 fn bitxor(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
825 self.symmetric_difference(rhs
).cloned().collect()
829 #[stable(feature = "rust1", since = "1.0.0")]
830 impl<'a
, 'b
, T
: Ord
+ Clone
> BitAnd
<&'b BTreeSet
<T
>> for &'a BTreeSet
<T
> {
831 type Output
= BTreeSet
<T
>;
833 /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
838 /// use std::collections::BTreeSet;
840 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
841 /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
843 /// let result = &a & &b;
844 /// let result_vec: Vec<_> = result.into_iter().collect();
845 /// assert_eq!(result_vec, [2, 3]);
847 fn bitand(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
848 self.intersection(rhs
).cloned().collect()
852 #[stable(feature = "rust1", since = "1.0.0")]
853 impl<'a
, 'b
, T
: Ord
+ Clone
> BitOr
<&'b BTreeSet
<T
>> for &'a BTreeSet
<T
> {
854 type Output
= BTreeSet
<T
>;
856 /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
861 /// use std::collections::BTreeSet;
863 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
864 /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
866 /// let result = &a | &b;
867 /// let result_vec: Vec<_> = result.into_iter().collect();
868 /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
870 fn bitor(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
871 self.union(rhs
).cloned().collect()
875 #[stable(feature = "rust1", since = "1.0.0")]
876 impl<T
: Debug
> Debug
for BTreeSet
<T
> {
877 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
878 f
.debug_set().entries(self.iter()).finish()
882 #[stable(feature = "rust1", since = "1.0.0")]
883 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
884 fn clone(&self) -> Iter
<'a
, T
> {
885 Iter { iter: self.iter.clone() }
888 #[stable(feature = "rust1", since = "1.0.0")]
889 impl<'a
, T
> Iterator
for Iter
<'a
, T
> {
892 fn next(&mut self) -> Option
<&'a T
> {
895 fn size_hint(&self) -> (usize, Option
<usize>) {
896 self.iter
.size_hint()
899 #[stable(feature = "rust1", since = "1.0.0")]
900 impl<'a
, T
> DoubleEndedIterator
for Iter
<'a
, T
> {
901 fn next_back(&mut self) -> Option
<&'a T
> {
902 self.iter
.next_back()
905 #[stable(feature = "rust1", since = "1.0.0")]
906 impl<'a
, T
> ExactSizeIterator
for Iter
<'a
, T
> {
907 fn len(&self) -> usize { self.iter.len() }
910 #[unstable(feature = "fused", issue = "35602")]
911 impl<'a
, T
> FusedIterator
for Iter
<'a
, T
> {}
913 #[stable(feature = "rust1", since = "1.0.0")]
914 impl<T
> Iterator
for IntoIter
<T
> {
917 fn next(&mut self) -> Option
<T
> {
918 self.iter
.next().map(|(k
, _
)| k
)
920 fn size_hint(&self) -> (usize, Option
<usize>) {
921 self.iter
.size_hint()
924 #[stable(feature = "rust1", since = "1.0.0")]
925 impl<T
> DoubleEndedIterator
for IntoIter
<T
> {
926 fn next_back(&mut self) -> Option
<T
> {
927 self.iter
.next_back().map(|(k
, _
)| k
)
930 #[stable(feature = "rust1", since = "1.0.0")]
931 impl<T
> ExactSizeIterator
for IntoIter
<T
> {
932 fn len(&self) -> usize { self.iter.len() }
935 #[unstable(feature = "fused", issue = "35602")]
936 impl<T
> FusedIterator
for IntoIter
<T
> {}
938 impl<'a
, T
> Clone
for Range
<'a
, T
> {
939 fn clone(&self) -> Range
<'a
, T
> {
940 Range { iter: self.iter.clone() }
943 impl<'a
, T
> Iterator
for Range
<'a
, T
> {
946 fn next(&mut self) -> Option
<&'a T
> {
947 self.iter
.next().map(|(k
, _
)| k
)
950 impl<'a
, T
> DoubleEndedIterator
for Range
<'a
, T
> {
951 fn next_back(&mut self) -> Option
<&'a T
> {
952 self.iter
.next_back().map(|(k
, _
)| k
)
956 #[unstable(feature = "fused", issue = "35602")]
957 impl<'a
, T
> FusedIterator
for Range
<'a
, T
> {}
959 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
960 fn cmp_opt
<T
: Ord
>(x
: Option
<&T
>, y
: Option
<&T
>, short
: Ordering
, long
: Ordering
) -> Ordering
{
964 (Some(x1
), Some(y1
)) => x1
.cmp(y1
),
968 #[stable(feature = "rust1", since = "1.0.0")]
969 impl<'a
, T
> Clone
for Difference
<'a
, T
> {
970 fn clone(&self) -> Difference
<'a
, T
> {
977 #[stable(feature = "rust1", since = "1.0.0")]
978 impl<'a
, T
: Ord
> Iterator
for Difference
<'a
, T
> {
981 fn next(&mut self) -> Option
<&'a T
> {
983 match cmp_opt(self.a
.peek(), self.b
.peek(), Less
, Less
) {
984 Less
=> return self.a
.next(),
996 fn size_hint(&self) -> (usize, Option
<usize>) {
997 let a_len
= self.a
.len();
998 let b_len
= self.b
.len();
999 (a_len
.saturating_sub(b_len
), Some(a_len
))
1003 #[unstable(feature = "fused", issue = "35602")]
1004 impl<'a
, T
: Ord
> FusedIterator
for Difference
<'a
, T
> {}
1006 #[stable(feature = "rust1", since = "1.0.0")]
1007 impl<'a
, T
> Clone
for SymmetricDifference
<'a
, T
> {
1008 fn clone(&self) -> SymmetricDifference
<'a
, T
> {
1009 SymmetricDifference
{
1015 #[stable(feature = "rust1", since = "1.0.0")]
1016 impl<'a
, T
: Ord
> Iterator
for SymmetricDifference
<'a
, T
> {
1019 fn next(&mut self) -> Option
<&'a T
> {
1021 match cmp_opt(self.a
.peek(), self.b
.peek(), Greater
, Less
) {
1022 Less
=> return self.a
.next(),
1027 Greater
=> return self.b
.next(),
1032 fn size_hint(&self) -> (usize, Option
<usize>) {
1033 (0, Some(self.a
.len() + self.b
.len()))
1037 #[unstable(feature = "fused", issue = "35602")]
1038 impl<'a
, T
: Ord
> FusedIterator
for SymmetricDifference
<'a
, T
> {}
1040 #[stable(feature = "rust1", since = "1.0.0")]
1041 impl<'a
, T
> Clone
for Intersection
<'a
, T
> {
1042 fn clone(&self) -> Intersection
<'a
, T
> {
1049 #[stable(feature = "rust1", since = "1.0.0")]
1050 impl<'a
, T
: Ord
> Iterator
for Intersection
<'a
, T
> {
1053 fn next(&mut self) -> Option
<&'a T
> {
1055 let o_cmp
= match (self.a
.peek(), self.b
.peek()) {
1058 (Some(a1
), Some(b1
)) => Some(a1
.cmp(b1
)),
1061 None
=> return None
,
1067 return self.a
.next();
1076 fn size_hint(&self) -> (usize, Option
<usize>) {
1077 (0, Some(min(self.a
.len(), self.b
.len())))
1081 #[unstable(feature = "fused", issue = "35602")]
1082 impl<'a
, T
: Ord
> FusedIterator
for Intersection
<'a
, T
> {}
1084 #[stable(feature = "rust1", since = "1.0.0")]
1085 impl<'a
, T
> Clone
for Union
<'a
, T
> {
1086 fn clone(&self) -> Union
<'a
, T
> {
1093 #[stable(feature = "rust1", since = "1.0.0")]
1094 impl<'a
, T
: Ord
> Iterator
for Union
<'a
, T
> {
1097 fn next(&mut self) -> Option
<&'a T
> {
1099 match cmp_opt(self.a
.peek(), self.b
.peek(), Greater
, Less
) {
1100 Less
=> return self.a
.next(),
1103 return self.a
.next();
1105 Greater
=> return self.b
.next(),
1110 fn size_hint(&self) -> (usize, Option
<usize>) {
1111 let a_len
= self.a
.len();
1112 let b_len
= self.b
.len();
1113 (max(a_len
, b_len
), Some(a_len
+ b_len
))
1117 #[unstable(feature = "fused", issue = "35602")]
1118 impl<'a
, T
: Ord
> FusedIterator
for Union
<'a
, T
> {}