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