src/libcollections/btree/set.rs

   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.
   4 //
   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.
  10
  11 // This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface
  12 // to TreeMap
  13
  14 use core::cmp::Ordering::{self, Less, Greater, Equal};
  15 use core::fmt::Debug;
  16 use core::fmt;
  17 use core::iter::{Peekable, Map, FromIterator};
  18 use core::ops::{BitOr, BitAnd, BitXor, Sub};
  19
  20 use borrow::Borrow;
  21 use btree_map::{BTreeMap, Keys};
  22 use super::Recover;
  23 use Bound;
  24
  25 // FIXME(conventions): implement bounded iterators
  26
  27 /// A set based on a B-Tree.
  28 ///
  29 /// See BTreeMap's documentation for a detailed discussion of this collection's performance
  30 /// benefits and drawbacks.
  31 ///
  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.
  35 #[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
  36 #[stable(feature = "rust1", since = "1.0.0")]
  37 pub struct BTreeSet<T> {
  38     map: BTreeMap<T, ()>,
  39 }
  40
  41 /// An iterator over a BTreeSet's items.
  42 #[stable(feature = "rust1", since = "1.0.0")]
  43 pub struct Iter<'a, T: 'a> {
  44     iter: Keys<'a, T, ()>,
  45 }
  46
  47 /// An owning iterator over a BTreeSet's items.
  48 #[stable(feature = "rust1", since = "1.0.0")]
  49 pub struct IntoIter<T> {
  50     iter: Map<::btree_map::IntoIter<T, ()>, fn((T, ())) -> T>,
  51 }
  52
  53 /// An iterator over a sub-range of BTreeSet's items.
  54 pub struct Range<'a, T: 'a> {
  55     iter: Map<::btree_map::Range<'a, T, ()>, fn((&'a T, &'a ())) -> &'a T>,
  56 }
  57
  58 /// A lazy iterator producing elements in the set difference (in-order).
  59 #[stable(feature = "rust1", since = "1.0.0")]
  60 pub struct Difference<'a, T: 'a> {
  61     a: Peekable<Iter<'a, T>>,
  62     b: Peekable<Iter<'a, T>>,
  63 }
  64
  65 /// A lazy iterator producing elements in the set symmetric difference (in-order).
  66 #[stable(feature = "rust1", since = "1.0.0")]
  67 pub struct SymmetricDifference<'a, T: 'a> {
  68     a: Peekable<Iter<'a, T>>,
  69     b: Peekable<Iter<'a, T>>,
  70 }
  71
  72 /// A lazy iterator producing elements in the set intersection (in-order).
  73 #[stable(feature = "rust1", since = "1.0.0")]
  74 pub struct Intersection<'a, T: 'a> {
  75     a: Peekable<Iter<'a, T>>,
  76     b: Peekable<Iter<'a, T>>,
  77 }
  78
  79 /// A lazy iterator producing elements in the set union (in-order).
  80 #[stable(feature = "rust1", since = "1.0.0")]
  81 pub struct Union<'a, T: 'a> {
  82     a: Peekable<Iter<'a, T>>,
  83     b: Peekable<Iter<'a, T>>,
  84 }
  85
  86 impl<T: Ord> BTreeSet<T> {
  87     /// Makes a new BTreeSet with a reasonable choice of B.
  88     ///
  89     /// # Examples
  90     ///
  91     /// ```
  92     /// # #![allow(unused_mut)]
  93     /// use std::collections::BTreeSet;
  94     ///
  95     /// let mut set: BTreeSet<i32> = BTreeSet::new();
  96     /// ```
  97     #[stable(feature = "rust1", since = "1.0.0")]
  98     pub fn new() -> BTreeSet<T> {
  99         BTreeSet { map: BTreeMap::new() }
 100     }
 101 }
 102
 103 impl<T> BTreeSet<T> {
 104     /// Gets an iterator over the BTreeSet's contents.
 105     ///
 106     /// # Examples
 107     ///
 108     /// ```
 109     /// use std::collections::BTreeSet;
 110     ///
 111     /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
 112     ///
 113     /// for x in set.iter() {
 114     ///     println!("{}", x);
 115     /// }
 116     ///
 117     /// let v: Vec<_> = set.iter().cloned().collect();
 118     /// assert_eq!(v, [1, 2, 3, 4]);
 119     /// ```
 120     #[stable(feature = "rust1", since = "1.0.0")]
 121     pub fn iter(&self) -> Iter<T> {
 122         Iter { iter: self.map.keys() }
 123     }
 124 }
 125
 126 impl<T: Ord> BTreeSet<T> {
 127     /// Constructs a double-ended iterator over a sub-range of elements in the set, starting
 128     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
 129     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
 130     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
 131     ///
 132     /// # Examples
 133     ///
 134     /// ```
 135     /// #![feature(btree_range, collections_bound)]
 136     ///
 137     /// use std::collections::BTreeSet;
 138     /// use std::collections::Bound::{Included, Unbounded};
 139     ///
 140     /// let mut set = BTreeSet::new();
 141     /// set.insert(3);
 142     /// set.insert(5);
 143     /// set.insert(8);
 144     /// for &elem in set.range(Included(&4), Included(&8)) {
 145     ///     println!("{}", elem);
 146     /// }
 147     /// assert_eq!(Some(&5), set.range(Included(&4), Unbounded).next());
 148     /// ```
 149     #[unstable(feature = "btree_range",
 150                reason = "matches collection reform specification, waiting for dust to settle",
 151                issue = "27787")]
 152     pub fn range<'a, Min: ?Sized + Ord = T, Max: ?Sized + Ord = T>(&'a self,
 153                                                                    min: Bound<&Min>,
 154                                                                    max: Bound<&Max>)
 155                                                                    -> Range<'a, T>
 156         where T: Borrow<Min> + Borrow<Max>
 157     {
 158         fn first<A, B>((a, _): (A, B)) -> A {
 159             a
 160         }
 161         let first: fn((&'a T, &'a ())) -> &'a T = first; // coerce to fn pointer
 162
 163         Range { iter: self.map.range(min, max).map(first) }
 164     }
 165 }
 166
 167 impl<T: Ord> BTreeSet<T> {
 168     /// Visits the values representing the difference, in ascending order.
 169     ///
 170     /// # Examples
 171     ///
 172     /// ```
 173     /// use std::collections::BTreeSet;
 174     ///
 175     /// let mut a = BTreeSet::new();
 176     /// a.insert(1);
 177     /// a.insert(2);
 178     ///
 179     /// let mut b = BTreeSet::new();
 180     /// b.insert(2);
 181     /// b.insert(3);
 182     ///
 183     /// let diff: Vec<_> = a.difference(&b).cloned().collect();
 184     /// assert_eq!(diff, [1]);
 185     /// ```
 186     #[stable(feature = "rust1", since = "1.0.0")]
 187     pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> {
 188         Difference {
 189             a: self.iter().peekable(),
 190             b: other.iter().peekable(),
 191         }
 192     }
 193
 194     /// Visits the values representing the symmetric difference, in ascending order.
 195     ///
 196     /// # Examples
 197     ///
 198     /// ```
 199     /// use std::collections::BTreeSet;
 200     ///
 201     /// let mut a = BTreeSet::new();
 202     /// a.insert(1);
 203     /// a.insert(2);
 204     ///
 205     /// let mut b = BTreeSet::new();
 206     /// b.insert(2);
 207     /// b.insert(3);
 208     ///
 209     /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
 210     /// assert_eq!(sym_diff, [1, 3]);
 211     /// ```
 212     #[stable(feature = "rust1", since = "1.0.0")]
 213     pub fn symmetric_difference<'a>(&'a self,
 214                                     other: &'a BTreeSet<T>)
 215                                     -> SymmetricDifference<'a, T> {
 216         SymmetricDifference {
 217             a: self.iter().peekable(),
 218             b: other.iter().peekable(),
 219         }
 220     }
 221
 222     /// Visits the values representing the intersection, in ascending order.
 223     ///
 224     /// # Examples
 225     ///
 226     /// ```
 227     /// use std::collections::BTreeSet;
 228     ///
 229     /// let mut a = BTreeSet::new();
 230     /// a.insert(1);
 231     /// a.insert(2);
 232     ///
 233     /// let mut b = BTreeSet::new();
 234     /// b.insert(2);
 235     /// b.insert(3);
 236     ///
 237     /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
 238     /// assert_eq!(intersection, [2]);
 239     /// ```
 240     #[stable(feature = "rust1", since = "1.0.0")]
 241     pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> {
 242         Intersection {
 243             a: self.iter().peekable(),
 244             b: other.iter().peekable(),
 245         }
 246     }
 247
 248     /// Visits the values representing the union, in ascending order.
 249     ///
 250     /// # Examples
 251     ///
 252     /// ```
 253     /// use std::collections::BTreeSet;
 254     ///
 255     /// let mut a = BTreeSet::new();
 256     /// a.insert(1);
 257     ///
 258     /// let mut b = BTreeSet::new();
 259     /// b.insert(2);
 260     ///
 261     /// let union: Vec<_> = a.union(&b).cloned().collect();
 262     /// assert_eq!(union, [1, 2]);
 263     /// ```
 264     #[stable(feature = "rust1", since = "1.0.0")]
 265     pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T> {
 266         Union {
 267             a: self.iter().peekable(),
 268             b: other.iter().peekable(),
 269         }
 270     }
 271
 272     /// Returns the number of elements in the set.
 273     ///
 274     /// # Examples
 275     ///
 276     /// ```
 277     /// use std::collections::BTreeSet;
 278     ///
 279     /// let mut v = BTreeSet::new();
 280     /// assert_eq!(v.len(), 0);
 281     /// v.insert(1);
 282     /// assert_eq!(v.len(), 1);
 283     /// ```
 284     #[stable(feature = "rust1", since = "1.0.0")]
 285     pub fn len(&self) -> usize {
 286         self.map.len()
 287     }
 288
 289     /// Returns true if the set contains no elements.
 290     ///
 291     /// # Examples
 292     ///
 293     /// ```
 294     /// use std::collections::BTreeSet;
 295     ///
 296     /// let mut v = BTreeSet::new();
 297     /// assert!(v.is_empty());
 298     /// v.insert(1);
 299     /// assert!(!v.is_empty());
 300     /// ```
 301     #[stable(feature = "rust1", since = "1.0.0")]
 302     pub fn is_empty(&self) -> bool {
 303         self.len() == 0
 304     }
 305
 306     /// Clears the set, removing all values.
 307     ///
 308     /// # Examples
 309     ///
 310     /// ```
 311     /// use std::collections::BTreeSet;
 312     ///
 313     /// let mut v = BTreeSet::new();
 314     /// v.insert(1);
 315     /// v.clear();
 316     /// assert!(v.is_empty());
 317     /// ```
 318     #[stable(feature = "rust1", since = "1.0.0")]
 319     pub fn clear(&mut self) {
 320         self.map.clear()
 321     }
 322
 323     /// Returns `true` if the set contains a value.
 324     ///
 325     /// The value may be any borrowed form of the set's value type,
 326     /// but the ordering on the borrowed form *must* match the
 327     /// ordering on the value type.
 328     ///
 329     /// # Examples
 330     ///
 331     /// ```
 332     /// use std::collections::BTreeSet;
 333     ///
 334     /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 335     /// assert_eq!(set.contains(&1), true);
 336     /// assert_eq!(set.contains(&4), false);
 337     /// ```
 338     #[stable(feature = "rust1", since = "1.0.0")]
 339     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
 340         where T: Borrow<Q>,
 341               Q: Ord
 342     {
 343         self.map.contains_key(value)
 344     }
 345
 346     /// Returns a reference to the value in the set, if any, that is equal to the given value.
 347     ///
 348     /// The value may be any borrowed form of the set's value type,
 349     /// but the ordering on the borrowed form *must* match the
 350     /// ordering on the value type.
 351     #[unstable(feature = "set_recovery", issue = "28050")]
 352     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
 353         where T: Borrow<Q>,
 354               Q: Ord
 355     {
 356         Recover::get(&self.map, value)
 357     }
 358
 359     /// Returns `true` if the set has no elements in common with `other`.
 360     /// This is equivalent to checking for an empty intersection.
 361     ///
 362     /// # Examples
 363     ///
 364     /// ```
 365     /// use std::collections::BTreeSet;
 366     ///
 367     /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 368     /// let mut b = BTreeSet::new();
 369     ///
 370     /// assert_eq!(a.is_disjoint(&b), true);
 371     /// b.insert(4);
 372     /// assert_eq!(a.is_disjoint(&b), true);
 373     /// b.insert(1);
 374     /// assert_eq!(a.is_disjoint(&b), false);
 375     /// ```
 376     #[stable(feature = "rust1", since = "1.0.0")]
 377     pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool {
 378         self.intersection(other).next().is_none()
 379     }
 380
 381     /// Returns `true` if the set is a subset of another.
 382     ///
 383     /// # Examples
 384     ///
 385     /// ```
 386     /// use std::collections::BTreeSet;
 387     ///
 388     /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
 389     /// let mut set = BTreeSet::new();
 390     ///
 391     /// assert_eq!(set.is_subset(&sup), true);
 392     /// set.insert(2);
 393     /// assert_eq!(set.is_subset(&sup), true);
 394     /// set.insert(4);
 395     /// assert_eq!(set.is_subset(&sup), false);
 396     /// ```
 397     #[stable(feature = "rust1", since = "1.0.0")]
 398     pub fn is_subset(&self, other: &BTreeSet<T>) -> bool {
 399         // Stolen from TreeMap
 400         let mut x = self.iter();
 401         let mut y = other.iter();
 402         let mut a = x.next();
 403         let mut b = y.next();
 404         while a.is_some() {
 405             if b.is_none() {
 406                 return false;
 407             }
 408
 409             let a1 = a.unwrap();
 410             let b1 = b.unwrap();
 411
 412             match b1.cmp(a1) {
 413                 Less => (),
 414                 Greater => return false,
 415                 Equal => a = x.next(),
 416             }
 417
 418             b = y.next();
 419         }
 420         true
 421     }
 422
 423     /// Returns `true` if the set is a superset of another.
 424     ///
 425     /// # Examples
 426     ///
 427     /// ```
 428     /// use std::collections::BTreeSet;
 429     ///
 430     /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect();
 431     /// let mut set = BTreeSet::new();
 432     ///
 433     /// assert_eq!(set.is_superset(&sub), false);
 434     ///
 435     /// set.insert(0);
 436     /// set.insert(1);
 437     /// assert_eq!(set.is_superset(&sub), false);
 438     ///
 439     /// set.insert(2);
 440     /// assert_eq!(set.is_superset(&sub), true);
 441     /// ```
 442     #[stable(feature = "rust1", since = "1.0.0")]
 443     pub fn is_superset(&self, other: &BTreeSet<T>) -> bool {
 444         other.is_subset(self)
 445     }
 446
 447     /// Adds a value to the set.
 448     ///
 449     /// If the set did not have a value present, `true` is returned.
 450     ///
 451     /// If the set did have this key present, that value is returned, and the
 452     /// entry is not updated. See the [module-level documentation] for more.
 453     ///
 454     /// [module-level documentation]: index.html#insert-and-complex-keys
 455     ///
 456     /// # Examples
 457     ///
 458     /// ```
 459     /// use std::collections::BTreeSet;
 460     ///
 461     /// let mut set = BTreeSet::new();
 462     ///
 463     /// assert_eq!(set.insert(2), true);
 464     /// assert_eq!(set.insert(2), false);
 465     /// assert_eq!(set.len(), 1);
 466     /// ```
 467     #[stable(feature = "rust1", since = "1.0.0")]
 468     pub fn insert(&mut self, value: T) -> bool {
 469         self.map.insert(value, ()).is_none()
 470     }
 471
 472     /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
 473     /// one. Returns the replaced value.
 474     #[unstable(feature = "set_recovery", issue = "28050")]
 475     pub fn replace(&mut self, value: T) -> Option<T> {
 476         Recover::replace(&mut self.map, value)
 477     }
 478
 479     /// Removes a value from the set. Returns `true` if the value was
 480     /// present in the set.
 481     ///
 482     /// The value may be any borrowed form of the set's value type,
 483     /// but the ordering on the borrowed form *must* match the
 484     /// ordering on the value type.
 485     ///
 486     /// # Examples
 487     ///
 488     /// ```
 489     /// use std::collections::BTreeSet;
 490     ///
 491     /// let mut set = BTreeSet::new();
 492     ///
 493     /// set.insert(2);
 494     /// assert_eq!(set.remove(&2), true);
 495     /// assert_eq!(set.remove(&2), false);
 496     /// ```
 497     #[stable(feature = "rust1", since = "1.0.0")]
 498     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
 499         where T: Borrow<Q>,
 500               Q: Ord
 501     {
 502         self.map.remove(value).is_some()
 503     }
 504
 505     /// Removes and returns the value in the set, if any, that is equal to the given one.
 506     ///
 507     /// The value may be any borrowed form of the set's value type,
 508     /// but the ordering on the borrowed form *must* match the
 509     /// ordering on the value type.
 510     #[unstable(feature = "set_recovery", issue = "28050")]
 511     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
 512         where T: Borrow<Q>,
 513               Q: Ord
 514     {
 515         Recover::take(&mut self.map, value)
 516     }
 517 }
 518
 519 #[stable(feature = "rust1", since = "1.0.0")]
 520 impl<T: Ord> FromIterator<T> for BTreeSet<T> {
 521     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
 522         let mut set = BTreeSet::new();
 523         set.extend(iter);
 524         set
 525     }
 526 }
 527
 528 #[stable(feature = "rust1", since = "1.0.0")]
 529 impl<T> IntoIterator for BTreeSet<T> {
 530     type Item = T;
 531     type IntoIter = IntoIter<T>;
 532
 533     /// Gets an iterator for moving out the BtreeSet's contents.
 534     ///
 535     /// # Examples
 536     ///
 537     /// ```
 538     /// use std::collections::BTreeSet;
 539     ///
 540     /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
 541     ///
 542     /// let v: Vec<_> = set.into_iter().collect();
 543     /// assert_eq!(v, [1, 2, 3, 4]);
 544     /// ```
 545     fn into_iter(self) -> IntoIter<T> {
 546         fn first<A, B>((a, _): (A, B)) -> A {
 547             a
 548         }
 549         let first: fn((T, ())) -> T = first; // coerce to fn pointer
 550
 551         IntoIter { iter: self.map.into_iter().map(first) }
 552     }
 553 }
 554
 555 #[stable(feature = "rust1", since = "1.0.0")]
 556 impl<'a, T> IntoIterator for &'a BTreeSet<T> {
 557     type Item = &'a T;
 558     type IntoIter = Iter<'a, T>;
 559
 560     fn into_iter(self) -> Iter<'a, T> {
 561         self.iter()
 562     }
 563 }
 564
 565 #[stable(feature = "rust1", since = "1.0.0")]
 566 impl<T: Ord> Extend<T> for BTreeSet<T> {
 567     #[inline]
 568     fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
 569         for elem in iter {
 570             self.insert(elem);
 571         }
 572     }
 573 }
 574
 575 #[stable(feature = "extend_ref", since = "1.2.0")]
 576 impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> {
 577     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
 578         self.extend(iter.into_iter().cloned());
 579     }
 580 }
 581
 582 #[stable(feature = "rust1", since = "1.0.0")]
 583 impl<T: Ord> Default for BTreeSet<T> {
 584     fn default() -> BTreeSet<T> {
 585         BTreeSet::new()
 586     }
 587 }
 588
 589 #[stable(feature = "rust1", since = "1.0.0")]
 590 impl<'a, 'b, T: Ord + Clone> Sub<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 591     type Output = BTreeSet<T>;
 592
 593     /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
 594     ///
 595     /// # Examples
 596     ///
 597     /// ```
 598     /// use std::collections::BTreeSet;
 599     ///
 600     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
 601     /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
 602     ///
 603     /// let result = &a - &b;
 604     /// let result_vec: Vec<_> = result.into_iter().collect();
 605     /// assert_eq!(result_vec, [1, 2]);
 606     /// ```
 607     fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 608         self.difference(rhs).cloned().collect()
 609     }
 610 }
 611
 612 #[stable(feature = "rust1", since = "1.0.0")]
 613 impl<'a, 'b, T: Ord + Clone> BitXor<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 614     type Output = BTreeSet<T>;
 615
 616     /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
 617     ///
 618     /// # Examples
 619     ///
 620     /// ```
 621     /// use std::collections::BTreeSet;
 622     ///
 623     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
 624     /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
 625     ///
 626     /// let result = &a ^ &b;
 627     /// let result_vec: Vec<_> = result.into_iter().collect();
 628     /// assert_eq!(result_vec, [1, 4]);
 629     /// ```
 630     fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 631         self.symmetric_difference(rhs).cloned().collect()
 632     }
 633 }
 634
 635 #[stable(feature = "rust1", since = "1.0.0")]
 636 impl<'a, 'b, T: Ord + Clone> BitAnd<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 637     type Output = BTreeSet<T>;
 638
 639     /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
 640     ///
 641     /// # Examples
 642     ///
 643     /// ```
 644     /// use std::collections::BTreeSet;
 645     ///
 646     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
 647     /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
 648     ///
 649     /// let result = &a & &b;
 650     /// let result_vec: Vec<_> = result.into_iter().collect();
 651     /// assert_eq!(result_vec, [2, 3]);
 652     /// ```
 653     fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 654         self.intersection(rhs).cloned().collect()
 655     }
 656 }
 657
 658 #[stable(feature = "rust1", since = "1.0.0")]
 659 impl<'a, 'b, T: Ord + Clone> BitOr<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 660     type Output = BTreeSet<T>;
 661
 662     /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
 663     ///
 664     /// # Examples
 665     ///
 666     /// ```
 667     /// use std::collections::BTreeSet;
 668     ///
 669     /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
 670     /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
 671     ///
 672     /// let result = &a | &b;
 673     /// let result_vec: Vec<_> = result.into_iter().collect();
 674     /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
 675     /// ```
 676     fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 677         self.union(rhs).cloned().collect()
 678     }
 679 }
 680
 681 #[stable(feature = "rust1", since = "1.0.0")]
 682 impl<T: Debug> Debug for BTreeSet<T> {
 683     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 684         f.debug_set().entries(self.iter()).finish()
 685     }
 686 }
 687
 688 impl<'a, T> Clone for Iter<'a, T> {
 689     fn clone(&self) -> Iter<'a, T> {
 690         Iter { iter: self.iter.clone() }
 691     }
 692 }
 693 #[stable(feature = "rust1", since = "1.0.0")]
 694 impl<'a, T> Iterator for Iter<'a, T> {
 695     type Item = &'a T;
 696
 697     fn next(&mut self) -> Option<&'a T> {
 698         self.iter.next()
 699     }
 700     fn size_hint(&self) -> (usize, Option<usize>) {
 701         self.iter.size_hint()
 702     }
 703 }
 704 #[stable(feature = "rust1", since = "1.0.0")]
 705 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
 706     fn next_back(&mut self) -> Option<&'a T> {
 707         self.iter.next_back()
 708     }
 709 }
 710 #[stable(feature = "rust1", since = "1.0.0")]
 711 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
 712
 713
 714 #[stable(feature = "rust1", since = "1.0.0")]
 715 impl<T> Iterator for IntoIter<T> {
 716     type Item = T;
 717
 718     fn next(&mut self) -> Option<T> {
 719         self.iter.next()
 720     }
 721     fn size_hint(&self) -> (usize, Option<usize>) {
 722         self.iter.size_hint()
 723     }
 724 }
 725 #[stable(feature = "rust1", since = "1.0.0")]
 726 impl<T> DoubleEndedIterator for IntoIter<T> {
 727     fn next_back(&mut self) -> Option<T> {
 728         self.iter.next_back()
 729     }
 730 }
 731 #[stable(feature = "rust1", since = "1.0.0")]
 732 impl<T> ExactSizeIterator for IntoIter<T> {}
 733
 734
 735 impl<'a, T> Clone for Range<'a, T> {
 736     fn clone(&self) -> Range<'a, T> {
 737         Range { iter: self.iter.clone() }
 738     }
 739 }
 740 impl<'a, T> Iterator for Range<'a, T> {
 741     type Item = &'a T;
 742
 743     fn next(&mut self) -> Option<&'a T> {
 744         self.iter.next()
 745     }
 746 }
 747 impl<'a, T> DoubleEndedIterator for Range<'a, T> {
 748     fn next_back(&mut self) -> Option<&'a T> {
 749         self.iter.next_back()
 750     }
 751 }
 752
 753 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
 754 fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering {
 755     match (x, y) {
 756         (None, _) => short,
 757         (_, None) => long,
 758         (Some(x1), Some(y1)) => x1.cmp(y1),
 759     }
 760 }
 761
 762 impl<'a, T> Clone for Difference<'a, T> {
 763     fn clone(&self) -> Difference<'a, T> {
 764         Difference {
 765             a: self.a.clone(),
 766             b: self.b.clone(),
 767         }
 768     }
 769 }
 770 #[stable(feature = "rust1", since = "1.0.0")]
 771 impl<'a, T: Ord> Iterator for Difference<'a, T> {
 772     type Item = &'a T;
 773
 774     fn next(&mut self) -> Option<&'a T> {
 775         loop {
 776             match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
 777                 Less => return self.a.next(),
 778                 Equal => {
 779                     self.a.next();
 780                     self.b.next();
 781                 }
 782                 Greater => {
 783                     self.b.next();
 784                 }
 785             }
 786         }
 787     }
 788 }
 789
 790 impl<'a, T> Clone for SymmetricDifference<'a, T> {
 791     fn clone(&self) -> SymmetricDifference<'a, T> {
 792         SymmetricDifference {
 793             a: self.a.clone(),
 794             b: self.b.clone(),
 795         }
 796     }
 797 }
 798 #[stable(feature = "rust1", since = "1.0.0")]
 799 impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
 800     type Item = &'a T;
 801
 802     fn next(&mut self) -> Option<&'a T> {
 803         loop {
 804             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 805                 Less => return self.a.next(),
 806                 Equal => {
 807                     self.a.next();
 808                     self.b.next();
 809                 }
 810                 Greater => return self.b.next(),
 811             }
 812         }
 813     }
 814 }
 815
 816 impl<'a, T> Clone for Intersection<'a, T> {
 817     fn clone(&self) -> Intersection<'a, T> {
 818         Intersection {
 819             a: self.a.clone(),
 820             b: self.b.clone(),
 821         }
 822     }
 823 }
 824 #[stable(feature = "rust1", since = "1.0.0")]
 825 impl<'a, T: Ord> Iterator for Intersection<'a, T> {
 826     type Item = &'a T;
 827
 828     fn next(&mut self) -> Option<&'a T> {
 829         loop {
 830             let o_cmp = match (self.a.peek(), self.b.peek()) {
 831                 (None, _) => None,
 832                 (_, None) => None,
 833                 (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
 834             };
 835             match o_cmp {
 836                 None => return None,
 837                 Some(Less) => {
 838                     self.a.next();
 839                 }
 840                 Some(Equal) => {
 841                     self.b.next();
 842                     return self.a.next();
 843                 }
 844                 Some(Greater) => {
 845                     self.b.next();
 846                 }
 847             }
 848         }
 849     }
 850 }
 851
 852 impl<'a, T> Clone for Union<'a, T> {
 853     fn clone(&self) -> Union<'a, T> {
 854         Union {
 855             a: self.a.clone(),
 856             b: self.b.clone(),
 857         }
 858     }
 859 }
 860 #[stable(feature = "rust1", since = "1.0.0")]
 861 impl<'a, T: Ord> Iterator for Union<'a, T> {
 862     type Item = &'a T;
 863
 864     fn next(&mut self) -> Option<&'a T> {
 865         loop {
 866             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 867                 Less => return self.a.next(),
 868                 Equal => {
 869                     self.b.next();
 870                     return self.a.next();
 871                 }
 872                 Greater => return self.b.next(),
 873             }
 874         }
 875     }
 876 }