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