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