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