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