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