src/libcollections/tree/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 use core::prelude::*;
  12
  13 use core::borrow::BorrowFrom;
  14 use core::default::Default;
  15 use core::fmt;
  16 use core::fmt::Show;
  17 use core::iter::Peekable;
  18 use core::iter;
  19 use std::hash::{Writer, Hash};
  20
  21 use tree_map::{TreeMap, Entries, RevEntries, MoveEntries};
  22
  23 // FIXME(conventions): implement bounded iterators
  24 // FIXME(conventions): replace rev_iter(_mut) by making iter(_mut) DoubleEnded
  25
  26 /// An implementation of the `Set` trait on top of the `TreeMap` container. The
  27 /// only requirement is that the type of the elements contained ascribes to the
  28 /// `Ord` trait.
  29 ///
  30 /// ## Example
  31 ///
  32 /// ```{rust}
  33 /// use std::collections::TreeSet;
  34 ///
  35 /// let mut set = TreeSet::new();
  36 ///
  37 /// set.insert(2i);
  38 /// set.insert(1i);
  39 /// set.insert(3i);
  40 ///
  41 /// for i in set.iter() {
  42 ///    println!("{}", i) // prints 1, then 2, then 3
  43 /// }
  44 ///
  45 /// set.remove(&3);
  46 ///
  47 /// if !set.contains(&3) {
  48 ///     println!("set does not contain a 3 anymore");
  49 /// }
  50 /// ```
  51 ///
  52 /// The easiest way to use `TreeSet` with a custom type is to implement `Ord`.
  53 /// We must also implement `PartialEq`, `Eq` and `PartialOrd`.
  54 ///
  55 /// ```
  56 /// use std::collections::TreeSet;
  57 ///
  58 /// // We need `Eq` and `PartialEq`, these can be derived.
  59 /// #[deriving(Eq, PartialEq)]
  60 /// struct Troll<'a> {
  61 ///     name: &'a str,
  62 ///     level: uint,
  63 /// }
  64 ///
  65 /// // Implement `Ord` and sort trolls by level.
  66 /// impl<'a> Ord for Troll<'a> {
  67 ///     fn cmp(&self, other: &Troll) -> Ordering {
  68 ///         // If we swap `self` and `other`, we get descending ordering.
  69 ///         self.level.cmp(&other.level)
  70 ///     }
  71 /// }
  72 ///
  73 /// // `PartialOrd` needs to be implemented as well.
  74 /// impl<'a> PartialOrd for Troll<'a> {
  75 ///     fn partial_cmp(&self, other: &Troll) -> Option<Ordering> {
  76 ///         Some(self.cmp(other))
  77 ///     }
  78 /// }
  79 ///
  80 /// let mut trolls = TreeSet::new();
  81 ///
  82 /// trolls.insert(Troll { name: "Orgarr", level: 2 });
  83 /// trolls.insert(Troll { name: "Blargarr", level: 3 });
  84 /// trolls.insert(Troll { name: "Kron the Smelly One", level: 4 });
  85 /// trolls.insert(Troll { name: "Wartilda", level: 1 });
  86 ///
  87 /// println!("You are facing {} trolls!", trolls.len());
  88 ///
  89 /// // Print the trolls, ordered by level with smallest level first
  90 /// for x in trolls.iter() {
  91 ///     println!("level {}: {}!", x.level, x.name);
  92 /// }
  93 ///
  94 /// // Kill all trolls
  95 /// trolls.clear();
  96 /// assert_eq!(trolls.len(), 0);
  97 /// ```
  98 #[deriving(Clone)]
  99 pub struct TreeSet<T> {
 100     map: TreeMap<T, ()>
 101 }
 102
 103 impl<T: PartialEq + Ord> PartialEq for TreeSet<T> {
 104     #[inline]
 105     fn eq(&self, other: &TreeSet<T>) -> bool { self.map == other.map }
 106 }
 107
 108 impl<T: Eq + Ord> Eq for TreeSet<T> {}
 109
 110 impl<T: Ord> PartialOrd for TreeSet<T> {
 111     #[inline]
 112     fn partial_cmp(&self, other: &TreeSet<T>) -> Option<Ordering> {
 113         self.map.partial_cmp(&other.map)
 114     }
 115 }
 116
 117 impl<T: Ord> Ord for TreeSet<T> {
 118     #[inline]
 119     fn cmp(&self, other: &TreeSet<T>) -> Ordering {
 120         iter::order::cmp(self.iter(), other.iter())
 121     }
 122 }
 123
 124 impl<T: Ord + Show> Show for TreeSet<T> {
 125     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 126         try!(write!(f, "{{"));
 127
 128         for (i, x) in self.iter().enumerate() {
 129             if i != 0 { try!(write!(f, ", ")); }
 130             try!(write!(f, "{}", *x));
 131         }
 132
 133         write!(f, "}}")
 134     }
 135 }
 136
 137 impl<T: Ord> Default for TreeSet<T> {
 138     #[inline]
 139     fn default() -> TreeSet<T> { TreeSet::new() }
 140 }
 141
 142 impl<T: Ord> TreeSet<T> {
 143     /// Creates an empty `TreeSet`.
 144     ///
 145     /// # Example
 146     ///
 147     /// ```
 148     /// use std::collections::TreeSet;
 149     /// let mut set: TreeSet<int> = TreeSet::new();
 150     /// ```
 151     #[inline]
 152     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 153     pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} }
 154
 155     /// Gets a lazy iterator over the values in the set, in ascending order.
 156     ///
 157     /// # Example
 158     ///
 159     /// ```
 160     /// use std::collections::TreeSet;
 161     /// let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect();
 162     ///
 163     /// // Will print in ascending order.
 164     /// for x in set.iter() {
 165     ///     println!("{}", x);
 166     /// }
 167     /// ```
 168     #[inline]
 169     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 170     pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
 171         SetItems{iter: self.map.iter()}
 172     }
 173
 174     /// Gets a lazy iterator over the values in the set, in descending order.
 175     ///
 176     /// # Example
 177     ///
 178     /// ```
 179     /// use std::collections::TreeSet;
 180     /// let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect();
 181     ///
 182     /// // Will print in descending order.
 183     /// for x in set.rev_iter() {
 184     ///     println!("{}", x);
 185     /// }
 186     /// ```
 187     #[inline]
 188     pub fn rev_iter<'a>(&'a self) -> RevSetItems<'a, T> {
 189         RevSetItems{iter: self.map.rev_iter()}
 190     }
 191
 192     /// Creates a consuming iterator, that is, one that moves each value out of the
 193     /// set in ascending order. The set cannot be used after calling this.
 194     ///
 195     /// # Example
 196     ///
 197     /// ```
 198     /// use std::collections::TreeSet;
 199     /// let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect();
 200     ///
 201     /// // Not possible with a regular `.iter()`
 202     /// let v: Vec<int> = set.into_iter().collect();
 203     /// assert_eq!(v, vec![1, 2, 3, 4, 5]);
 204     /// ```
 205     #[inline]
 206     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 207     pub fn into_iter(self) -> MoveSetItems<T> {
 208         self.map.into_iter().map(|(value, _)| value)
 209     }
 210
 211     /// Gets a lazy iterator pointing to the first value not less than `v` (greater or equal).
 212     /// If all elements in the set are less than `v` empty iterator is returned.
 213     ///
 214     /// # Example
 215     ///
 216     /// ```
 217     /// use std::collections::TreeSet;
 218     /// let set: TreeSet<int> = [2, 4, 6, 8].iter().map(|&x| x).collect();
 219     ///
 220     /// assert_eq!(set.lower_bound(&4).next(), Some(&4));
 221     /// assert_eq!(set.lower_bound(&5).next(), Some(&6));
 222     /// assert_eq!(set.lower_bound(&10).next(), None);
 223     /// ```
 224     #[inline]
 225     pub fn lower_bound<'a>(&'a self, v: &T) -> SetItems<'a, T> {
 226         SetItems{iter: self.map.lower_bound(v)}
 227     }
 228
 229     /// Gets a lazy iterator pointing to the first value greater than `v`.
 230     /// If all elements in the set are less than or equal to `v` an
 231     /// empty iterator is returned.
 232     ///
 233     /// # Example
 234     ///
 235     /// ```
 236     /// use std::collections::TreeSet;
 237     /// let set: TreeSet<int> = [2, 4, 6, 8].iter().map(|&x| x).collect();
 238     ///
 239     /// assert_eq!(set.upper_bound(&4).next(), Some(&6));
 240     /// assert_eq!(set.upper_bound(&5).next(), Some(&6));
 241     /// assert_eq!(set.upper_bound(&10).next(), None);
 242     /// ```
 243     #[inline]
 244     pub fn upper_bound<'a>(&'a self, v: &T) -> SetItems<'a, T> {
 245         SetItems{iter: self.map.upper_bound(v)}
 246     }
 247
 248     /// Visits the values representing the difference, in ascending order.
 249     ///
 250     /// # Example
 251     ///
 252     /// ```
 253     /// use std::collections::TreeSet;
 254     ///
 255     /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
 256     /// let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect();
 257     ///
 258     /// // Can be seen as `a - b`.
 259     /// for x in a.difference(&b) {
 260     ///     println!("{}", x); // Print 1 then 2
 261     /// }
 262     ///
 263     /// let diff: TreeSet<int> = a.difference(&b).map(|&x| x).collect();
 264     /// assert_eq!(diff, [1, 2].iter().map(|&x| x).collect());
 265     ///
 266     /// // Note that difference is not symmetric,
 267     /// // and `b - a` means something else:
 268     /// let diff: TreeSet<int> = b.difference(&a).map(|&x| x).collect();
 269     /// assert_eq!(diff, [4, 5].iter().map(|&x| x).collect());
 270     /// ```
 271     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 272     pub fn difference<'a>(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T> {
 273         DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
 274     }
 275
 276     /// Visits the values representing the symmetric difference, in ascending order.
 277     ///
 278     /// # Example
 279     ///
 280     /// ```
 281     /// use std::collections::TreeSet;
 282     ///
 283     /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
 284     /// let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect();
 285     ///
 286     /// // Print 1, 2, 4, 5 in ascending order.
 287     /// for x in a.symmetric_difference(&b) {
 288     ///     println!("{}", x);
 289     /// }
 290     ///
 291     /// let diff1: TreeSet<int> = a.symmetric_difference(&b).map(|&x| x).collect();
 292     /// let diff2: TreeSet<int> = b.symmetric_difference(&a).map(|&x| x).collect();
 293     ///
 294     /// assert_eq!(diff1, diff2);
 295     /// assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect());
 296     /// ```
 297     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 298     pub fn symmetric_difference<'a>(&'a self, other: &'a TreeSet<T>)
 299         -> SymDifferenceItems<'a, T> {
 300         SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
 301     }
 302
 303     /// Visits the values representing the intersection, in ascending order.
 304     ///
 305     /// # Example
 306     ///
 307     /// ```
 308     /// use std::collections::TreeSet;
 309     ///
 310     /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
 311     /// let b: TreeSet<int> = [2, 3, 4].iter().map(|&x| x).collect();
 312     ///
 313     /// // Print 2, 3 in ascending order.
 314     /// for x in a.intersection(&b) {
 315     ///     println!("{}", x);
 316     /// }
 317     ///
 318     /// let diff: TreeSet<int> = a.intersection(&b).map(|&x| x).collect();
 319     /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect());
 320     /// ```
 321     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 322     pub fn intersection<'a>(&'a self, other: &'a TreeSet<T>)
 323         -> IntersectionItems<'a, T> {
 324         IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()}
 325     }
 326
 327     /// Visits the values representing the union, in ascending order.
 328     ///
 329     /// # Example
 330     ///
 331     /// ```
 332     /// use std::collections::TreeSet;
 333     ///
 334     /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect();
 335     /// let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect();
 336     ///
 337     /// // Print 1, 2, 3, 4, 5 in ascending order.
 338     /// for x in a.union(&b) {
 339     ///     println!("{}", x);
 340     /// }
 341     ///
 342     /// let diff: TreeSet<int> = a.union(&b).map(|&x| x).collect();
 343     /// assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect());
 344     /// ```
 345     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 346     pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> {
 347         UnionItems{a: self.iter().peekable(), b: other.iter().peekable()}
 348     }
 349
 350     /// Return the number of elements in the set
 351     ///
 352     /// # Example
 353     ///
 354     /// ```
 355     /// use std::collections::TreeSet;
 356     ///
 357     /// let mut v = TreeSet::new();
 358     /// assert_eq!(v.len(), 0);
 359     /// v.insert(1i);
 360     /// assert_eq!(v.len(), 1);
 361     /// ```
 362     #[inline]
 363     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 364     pub fn len(&self) -> uint { self.map.len() }
 365
 366     /// Returns true if the set contains no elements
 367     ///
 368     /// # Example
 369     ///
 370     /// ```
 371     /// use std::collections::TreeSet;
 372     ///
 373     /// let mut v = TreeSet::new();
 374     /// assert!(v.is_empty());
 375     /// v.insert(1i);
 376     /// assert!(!v.is_empty());
 377     /// ```
 378     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 379     pub fn is_empty(&self) -> bool { self.len() == 0 }
 380
 381     /// Clears the set, removing all values.
 382     ///
 383     /// # Example
 384     ///
 385     /// ```
 386     /// use std::collections::TreeSet;
 387     ///
 388     /// let mut v = TreeSet::new();
 389     /// v.insert(1i);
 390     /// v.clear();
 391     /// assert!(v.is_empty());
 392     /// ```
 393     #[inline]
 394     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 395     pub fn clear(&mut self) { self.map.clear() }
 396
 397     /// Returns `true` if the set contains a value.
 398     ///
 399     /// The value may be any borrowed form of the set's value type,
 400     /// but the ordering on the borrowed form *must* match the
 401     /// ordering on the value type.
 402     ///
 403     /// # Example
 404     ///
 405     /// ```
 406     /// use std::collections::TreeSet;
 407     ///
 408     /// let set: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 409     /// assert_eq!(set.contains(&1), true);
 410     /// assert_eq!(set.contains(&4), false);
 411     /// ```
 412     #[inline]
 413     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 414     pub fn contains<Sized? Q>(&self, value: &Q) -> bool
 415         where Q: Ord + BorrowFrom<T>
 416     {
 417         self.map.contains_key(value)
 418     }
 419
 420     /// Returns `true` if the set has no elements in common with `other`.
 421     /// This is equivalent to checking for an empty intersection.
 422     ///
 423     /// # Example
 424     ///
 425     /// ```
 426     /// use std::collections::TreeSet;
 427     ///
 428     /// let a: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 429     /// let mut b: TreeSet<int> = TreeSet::new();
 430     ///
 431     /// assert_eq!(a.is_disjoint(&b), true);
 432     /// b.insert(4);
 433     /// assert_eq!(a.is_disjoint(&b), true);
 434     /// b.insert(1);
 435     /// assert_eq!(a.is_disjoint(&b), false);
 436     /// ```
 437     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 438     pub fn is_disjoint(&self, other: &TreeSet<T>) -> bool {
 439         self.intersection(other).next().is_none()
 440     }
 441
 442     /// Returns `true` if the set is a subset of another.
 443     ///
 444     /// # Example
 445     ///
 446     /// ```
 447     /// use std::collections::TreeSet;
 448     ///
 449     /// let sup: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 450     /// let mut set: TreeSet<int> = TreeSet::new();
 451     ///
 452     /// assert_eq!(set.is_subset(&sup), true);
 453     /// set.insert(2);
 454     /// assert_eq!(set.is_subset(&sup), true);
 455     /// set.insert(4);
 456     /// assert_eq!(set.is_subset(&sup), false);
 457     /// ```
 458     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 459     pub fn is_subset(&self, other: &TreeSet<T>) -> bool {
 460         let mut x = self.iter();
 461         let mut y = other.iter();
 462         let mut a = x.next();
 463         let mut b = y.next();
 464         while a.is_some() {
 465             if b.is_none() {
 466                 return false;
 467             }
 468
 469             let a1 = a.unwrap();
 470             let b1 = b.unwrap();
 471
 472             match b1.cmp(a1) {
 473                 Less => (),
 474                 Greater => return false,
 475                 Equal => a = x.next(),
 476             }
 477
 478             b = y.next();
 479         }
 480         true
 481     }
 482
 483     /// Returns `true` if the set is a superset of another.
 484     ///
 485     /// # Example
 486     ///
 487     /// ```
 488     /// use std::collections::TreeSet;
 489     ///
 490     /// let sub: TreeSet<int> = [1i, 2].iter().map(|&x| x).collect();
 491     /// let mut set: TreeSet<int> = TreeSet::new();
 492     ///
 493     /// assert_eq!(set.is_superset(&sub), false);
 494     ///
 495     /// set.insert(0);
 496     /// set.insert(1);
 497     /// assert_eq!(set.is_superset(&sub), false);
 498     ///
 499     /// set.insert(2);
 500     /// assert_eq!(set.is_superset(&sub), true);
 501     /// ```
 502     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 503     pub fn is_superset(&self, other: &TreeSet<T>) -> bool {
 504         other.is_subset(self)
 505     }
 506
 507     /// Adds a value to the set. Returns `true` if the value was not already
 508     /// present in the set.
 509     ///
 510     /// # Example
 511     ///
 512     /// ```
 513     /// use std::collections::TreeSet;
 514     ///
 515     /// let mut set = TreeSet::new();
 516     ///
 517     /// assert_eq!(set.insert(2i), true);
 518     /// assert_eq!(set.insert(2i), false);
 519     /// assert_eq!(set.len(), 1);
 520     /// ```
 521     #[inline]
 522     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 523     pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 524
 525     /// Removes a value from the set. Returns `true` if the value was
 526     /// present in the set.
 527     ///
 528     /// The value may be any borrowed form of the set's value type,
 529     /// but the ordering on the borrowed form *must* match the
 530     /// ordering on the value type.
 531     ///
 532     /// # Example
 533     ///
 534     /// ```
 535     /// use std::collections::TreeSet;
 536     ///
 537     /// let mut set = TreeSet::new();
 538     ///
 539     /// set.insert(2i);
 540     /// assert_eq!(set.remove(&2), true);
 541     /// assert_eq!(set.remove(&2), false);
 542     /// ```
 543     #[inline]
 544     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 545     pub fn remove<Sized? Q>(&mut self, value: &Q) -> bool
 546         where Q: Ord + BorrowFrom<T>
 547     {
 548         self.map.remove(value).is_some()
 549     }
 550 }
 551
 552 /// A lazy forward iterator over a set.
 553 pub struct SetItems<'a, T:'a> {
 554     iter: Entries<'a, T, ()>
 555 }
 556
 557 /// A lazy backward iterator over a set.
 558 pub struct RevSetItems<'a, T:'a> {
 559     iter: RevEntries<'a, T, ()>
 560 }
 561
 562 /// A lazy forward iterator over a set that consumes the set while iterating.
 563 pub type MoveSetItems<T> = iter::Map<'static, (T, ()), T, MoveEntries<T, ()>>;
 564
 565 /// A lazy iterator producing elements in the set difference (in-order).
 566 pub struct DifferenceItems<'a, T:'a> {
 567     a: Peekable<&'a T, SetItems<'a, T>>,
 568     b: Peekable<&'a T, SetItems<'a, T>>,
 569 }
 570
 571 /// A lazy iterator producing elements in the set symmetric difference (in-order).
 572 pub struct SymDifferenceItems<'a, T:'a> {
 573     a: Peekable<&'a T, SetItems<'a, T>>,
 574     b: Peekable<&'a T, SetItems<'a, T>>,
 575 }
 576
 577 /// A lazy iterator producing elements in the set intersection (in-order).
 578 pub struct IntersectionItems<'a, T:'a> {
 579     a: Peekable<&'a T, SetItems<'a, T>>,
 580     b: Peekable<&'a T, SetItems<'a, T>>,
 581 }
 582
 583 /// A lazy iterator producing elements in the set union (in-order).
 584 pub struct UnionItems<'a, T:'a> {
 585     a: Peekable<&'a T, SetItems<'a, T>>,
 586     b: Peekable<&'a T, SetItems<'a, T>>,
 587 }
 588
 589 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
 590 fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>,
 591                         short: Ordering, long: Ordering) -> Ordering {
 592     match (x, y) {
 593         (None    , _       ) => short,
 594         (_       , None    ) => long,
 595         (Some(x1), Some(y1)) => x1.cmp(y1),
 596     }
 597 }
 598
 599
 600 impl<'a, T> Iterator<&'a T> for SetItems<'a, T> {
 601     #[inline]
 602     fn next(&mut self) -> Option<&'a T> {
 603         self.iter.next().map(|(value, _)| value)
 604     }
 605 }
 606
 607 impl<'a, T> Iterator<&'a T> for RevSetItems<'a, T> {
 608     #[inline]
 609     fn next(&mut self) -> Option<&'a T> {
 610         self.iter.next().map(|(value, _)| value)
 611     }
 612 }
 613
 614 impl<'a, T: Ord> Iterator<&'a T> for DifferenceItems<'a, T> {
 615     fn next(&mut self) -> Option<&'a T> {
 616         loop {
 617             match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
 618                 Less    => return self.a.next(),
 619                 Equal   => { self.a.next(); self.b.next(); }
 620                 Greater => { self.b.next(); }
 621             }
 622         }
 623     }
 624 }
 625
 626 impl<'a, T: Ord> Iterator<&'a T> for SymDifferenceItems<'a, T> {
 627     fn next(&mut self) -> Option<&'a T> {
 628         loop {
 629             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 630                 Less    => return self.a.next(),
 631                 Equal   => { self.a.next(); self.b.next(); }
 632                 Greater => return self.b.next(),
 633             }
 634         }
 635     }
 636 }
 637
 638 impl<'a, T: Ord> Iterator<&'a T> for IntersectionItems<'a, T> {
 639     fn next(&mut self) -> Option<&'a T> {
 640         loop {
 641             let o_cmp = match (self.a.peek(), self.b.peek()) {
 642                 (None    , _       ) => None,
 643                 (_       , None    ) => None,
 644                 (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
 645             };
 646             match o_cmp {
 647                 None          => return None,
 648                 Some(Less)    => { self.a.next(); }
 649                 Some(Equal)   => { self.b.next(); return self.a.next() }
 650                 Some(Greater) => { self.b.next(); }
 651             }
 652         }
 653     }
 654 }
 655
 656 impl<'a, T: Ord> Iterator<&'a T> for UnionItems<'a, T> {
 657     fn next(&mut self) -> Option<&'a T> {
 658         loop {
 659             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 660                 Less    => return self.a.next(),
 661                 Equal   => { self.b.next(); return self.a.next() }
 662                 Greater => return self.b.next(),
 663             }
 664         }
 665     }
 666 }
 667
 668 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 669 impl<T: Ord + Clone> BitOr<TreeSet<T>, TreeSet<T>> for TreeSet<T> {
 670     /// Returns the union of `self` and `rhs` as a new `TreeSet<T>`.
 671     ///
 672     /// # Example
 673     ///
 674     /// ```
 675     /// use std::collections::TreeSet;
 676     ///
 677     /// let a: TreeSet<int> = vec![1, 2, 3].into_iter().collect();
 678     /// let b: TreeSet<int> = vec![3, 4, 5].into_iter().collect();
 679     ///
 680     /// let set: TreeSet<int> = a | b;
 681     /// let v: Vec<int> = set.into_iter().collect();
 682     /// assert_eq!(v, vec![1, 2, 3, 4, 5]);
 683     /// ```
 684     fn bitor(&self, rhs: &TreeSet<T>) -> TreeSet<T> {
 685         self.union(rhs).cloned().collect()
 686     }
 687 }
 688
 689 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 690 impl<T: Ord + Clone> BitAnd<TreeSet<T>, TreeSet<T>> for TreeSet<T> {
 691     /// Returns the intersection of `self` and `rhs` as a new `TreeSet<T>`.
 692     ///
 693     /// # Example
 694     ///
 695     /// ```
 696     /// use std::collections::TreeSet;
 697     ///
 698     /// let a: TreeSet<int> = vec![1, 2, 3].into_iter().collect();
 699     /// let b: TreeSet<int> = vec![2, 3, 4].into_iter().collect();
 700     ///
 701     /// let set: TreeSet<int> = a & b;
 702     /// let v: Vec<int> = set.into_iter().collect();
 703     /// assert_eq!(v, vec![2, 3]);
 704     /// ```
 705     fn bitand(&self, rhs: &TreeSet<T>) -> TreeSet<T> {
 706         self.intersection(rhs).cloned().collect()
 707     }
 708 }
 709
 710 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 711 impl<T: Ord + Clone> BitXor<TreeSet<T>, TreeSet<T>> for TreeSet<T> {
 712     /// Returns the symmetric difference of `self` and `rhs` as a new `TreeSet<T>`.
 713     ///
 714     /// # Example
 715     ///
 716     /// ```
 717     /// use std::collections::TreeSet;
 718     ///
 719     /// let a: TreeSet<int> = vec![1, 2, 3].into_iter().collect();
 720     /// let b: TreeSet<int> = vec![3, 4, 5].into_iter().collect();
 721     ///
 722     /// let set: TreeSet<int> = a ^ b;
 723     /// let v: Vec<int> = set.into_iter().collect();
 724     /// assert_eq!(v, vec![1, 2, 4, 5]);
 725     /// ```
 726     fn bitxor(&self, rhs: &TreeSet<T>) -> TreeSet<T> {
 727         self.symmetric_difference(rhs).cloned().collect()
 728     }
 729 }
 730
 731 #[unstable = "matches collection reform specification, waiting for dust to settle"]
 732 impl<T: Ord + Clone> Sub<TreeSet<T>, TreeSet<T>> for TreeSet<T> {
 733     /// Returns the difference of `self` and `rhs` as a new `TreeSet<T>`.
 734     ///
 735     /// # Example
 736     ///
 737     /// ```
 738     /// use std::collections::TreeSet;
 739     ///
 740     /// let a: TreeSet<int> = vec![1, 2, 3].into_iter().collect();
 741     /// let b: TreeSet<int> = vec![3, 4, 5].into_iter().collect();
 742     ///
 743     /// let set: TreeSet<int> = a - b;
 744     /// let v: Vec<int> = set.into_iter().collect();
 745     /// assert_eq!(v, vec![1, 2]);
 746     /// ```
 747     fn sub(&self, rhs: &TreeSet<T>) -> TreeSet<T> {
 748         self.difference(rhs).cloned().collect()
 749     }
 750 }
 751
 752 impl<T: Ord> FromIterator<T> for TreeSet<T> {
 753     fn from_iter<Iter: Iterator<T>>(iter: Iter) -> TreeSet<T> {
 754         let mut set = TreeSet::new();
 755         set.extend(iter);
 756         set
 757     }
 758 }
 759
 760 impl<T: Ord> Extend<T> for TreeSet<T> {
 761     #[inline]
 762     fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) {
 763         for elem in iter {
 764             self.insert(elem);
 765         }
 766     }
 767 }
 768
 769 impl<S: Writer, T: Ord + Hash<S>> Hash<S> for TreeSet<T> {
 770     fn hash(&self, state: &mut S) {
 771         for elt in self.iter() {
 772             elt.hash(state);
 773         }
 774     }
 775 }
 776
 777 #[cfg(test)]
 778 mod test {
 779     use std::prelude::*;
 780     use std::hash;
 781     use vec::Vec;
 782
 783     use super::TreeSet;
 784
 785     #[test]
 786     fn test_clear() {
 787         let mut s = TreeSet::new();
 788         s.clear();
 789         assert!(s.insert(5i));
 790         assert!(s.insert(12));
 791         assert!(s.insert(19));
 792         s.clear();
 793         assert!(!s.contains(&5));
 794         assert!(!s.contains(&12));
 795         assert!(!s.contains(&19));
 796         assert!(s.is_empty());
 797     }
 798
 799     #[test]
 800     fn test_disjoint() {
 801         let mut xs = TreeSet::new();
 802         let mut ys = TreeSet::new();
 803         assert!(xs.is_disjoint(&ys));
 804         assert!(ys.is_disjoint(&xs));
 805         assert!(xs.insert(5i));
 806         assert!(ys.insert(11i));
 807         assert!(xs.is_disjoint(&ys));
 808         assert!(ys.is_disjoint(&xs));
 809         assert!(xs.insert(7));
 810         assert!(xs.insert(19));
 811         assert!(xs.insert(4));
 812         assert!(ys.insert(2));
 813         assert!(ys.insert(-11));
 814         assert!(xs.is_disjoint(&ys));
 815         assert!(ys.is_disjoint(&xs));
 816         assert!(ys.insert(7));
 817         assert!(!xs.is_disjoint(&ys));
 818         assert!(!ys.is_disjoint(&xs));
 819     }
 820
 821     #[test]
 822     fn test_subset_and_superset() {
 823         let mut a = TreeSet::new();
 824         assert!(a.insert(0i));
 825         assert!(a.insert(5));
 826         assert!(a.insert(11));
 827         assert!(a.insert(7));
 828
 829         let mut b = TreeSet::new();
 830         assert!(b.insert(0i));
 831         assert!(b.insert(7));
 832         assert!(b.insert(19));
 833         assert!(b.insert(250));
 834         assert!(b.insert(11));
 835         assert!(b.insert(200));
 836
 837         assert!(!a.is_subset(&b));
 838         assert!(!a.is_superset(&b));
 839         assert!(!b.is_subset(&a));
 840         assert!(!b.is_superset(&a));
 841
 842         assert!(b.insert(5));
 843
 844         assert!(a.is_subset(&b));
 845         assert!(!a.is_superset(&b));
 846         assert!(!b.is_subset(&a));
 847         assert!(b.is_superset(&a));
 848     }
 849
 850     #[test]
 851     fn test_iterator() {
 852         let mut m = TreeSet::new();
 853
 854         assert!(m.insert(3i));
 855         assert!(m.insert(0));
 856         assert!(m.insert(4));
 857         assert!(m.insert(2));
 858         assert!(m.insert(1));
 859
 860         let mut n = 0;
 861         for x in m.iter() {
 862             assert_eq!(*x, n);
 863             n += 1
 864         }
 865     }
 866
 867     #[test]
 868     fn test_rev_iter() {
 869         let mut m = TreeSet::new();
 870
 871         assert!(m.insert(3i));
 872         assert!(m.insert(0));
 873         assert!(m.insert(4));
 874         assert!(m.insert(2));
 875         assert!(m.insert(1));
 876
 877         let mut n = 4;
 878         for x in m.rev_iter() {
 879             assert_eq!(*x, n);
 880             n -= 1;
 881         }
 882     }
 883
 884     #[test]
 885     fn test_move_iter() {
 886         let s: TreeSet<int> = range(0i, 5).collect();
 887
 888         let mut n = 0;
 889         for x in s.into_iter() {
 890             assert_eq!(x, n);
 891             n += 1;
 892         }
 893     }
 894
 895     #[test]
 896     fn test_move_iter_size_hint() {
 897         let s: TreeSet<int> = vec!(0i, 1).into_iter().collect();
 898
 899         let mut it = s.into_iter();
 900
 901         assert_eq!(it.size_hint(), (2, Some(2)));
 902         assert!(it.next() != None);
 903
 904         assert_eq!(it.size_hint(), (1, Some(1)));
 905         assert!(it.next() != None);
 906
 907         assert_eq!(it.size_hint(), (0, Some(0)));
 908         assert_eq!(it.next(), None);
 909     }
 910
 911     #[test]
 912     fn test_clone_eq() {
 913       let mut m = TreeSet::new();
 914
 915       m.insert(1i);
 916       m.insert(2);
 917
 918       assert!(m.clone() == m);
 919     }
 920
 921     #[test]
 922     fn test_hash() {
 923       let mut x = TreeSet::new();
 924       let mut y = TreeSet::new();
 925
 926       x.insert(1i);
 927       x.insert(2);
 928       x.insert(3);
 929
 930       y.insert(3i);
 931       y.insert(2);
 932       y.insert(1);
 933
 934       assert!(hash::hash(&x) == hash::hash(&y));
 935     }
 936
 937     fn check(a: &[int],
 938              b: &[int],
 939              expected: &[int],
 940              f: |&TreeSet<int>, &TreeSet<int>, f: |&int| -> bool| -> bool) {
 941         let mut set_a = TreeSet::new();
 942         let mut set_b = TreeSet::new();
 943
 944         for x in a.iter() { assert!(set_a.insert(*x)) }
 945         for y in b.iter() { assert!(set_b.insert(*y)) }
 946
 947         let mut i = 0;
 948         f(&set_a, &set_b, |x| {
 949             assert_eq!(*x, expected[i]);
 950             i += 1;
 951             true
 952         });
 953         assert_eq!(i, expected.len());
 954     }
 955
 956     #[test]
 957     fn test_intersection() {
 958         fn check_intersection(a: &[int], b: &[int], expected: &[int]) {
 959             check(a, b, expected, |x, y, f| x.intersection(y).all(f))
 960         }
 961
 962         check_intersection(&[], &[], &[]);
 963         check_intersection(&[1, 2, 3], &[], &[]);
 964         check_intersection(&[], &[1, 2, 3], &[]);
 965         check_intersection(&[2], &[1, 2, 3], &[2]);
 966         check_intersection(&[1, 2, 3], &[2], &[2]);
 967         check_intersection(&[11, 1, 3, 77, 103, 5, -5],
 968                            &[2, 11, 77, -9, -42, 5, 3],
 969                            &[3, 5, 11, 77]);
 970     }
 971
 972     #[test]
 973     fn test_difference() {
 974         fn check_difference(a: &[int], b: &[int], expected: &[int]) {
 975             check(a, b, expected, |x, y, f| x.difference(y).all(f))
 976         }
 977
 978         check_difference(&[], &[], &[]);
 979         check_difference(&[1, 12], &[], &[1, 12]);
 980         check_difference(&[], &[1, 2, 3, 9], &[]);
 981         check_difference(&[1, 3, 5, 9, 11],
 982                          &[3, 9],
 983                          &[1, 5, 11]);
 984         check_difference(&[-5, 11, 22, 33, 40, 42],
 985                          &[-12, -5, 14, 23, 34, 38, 39, 50],
 986                          &[11, 22, 33, 40, 42]);
 987     }
 988
 989     #[test]
 990     fn test_symmetric_difference() {
 991         fn check_symmetric_difference(a: &[int], b: &[int],
 992                                       expected: &[int]) {
 993             check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
 994         }
 995
 996         check_symmetric_difference(&[], &[], &[]);
 997         check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
 998         check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
 999         check_symmetric_difference(&[1, 3, 5, 9, 11],
1000                                    &[-2, 3, 9, 14, 22],
1001                                    &[-2, 1, 5, 11, 14, 22]);
1002     }
1003
1004     #[test]
1005     fn test_union() {
1006         fn check_union(a: &[int], b: &[int],
1007                                       expected: &[int]) {
1008             check(a, b, expected, |x, y, f| x.union(y).all(f))
1009         }
1010
1011         check_union(&[], &[], &[]);
1012         check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
1013         check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
1014         check_union(&[1, 3, 5, 9, 11, 16, 19, 24],
1015                     &[-2, 1, 5, 9, 13, 19],
1016                     &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
1017     }
1018
1019     #[test]
1020     fn test_bit_or() {
1021         let a: TreeSet<int> = vec![1, 3, 5, 9, 11, 16, 19, 24].into_iter().collect();
1022         let b: TreeSet<int> = vec![-2, 1, 5, 9, 13, 19].into_iter().collect();
1023
1024         let set: TreeSet<int> = a | b;
1025         let v: Vec<int> = set.into_iter().collect();
1026         assert_eq!(v, vec![-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
1027     }
1028
1029     #[test]
1030     fn test_bit_and() {
1031         let a: TreeSet<int> = vec![11, 1, 3, 77, 103, 5, -5].into_iter().collect();
1032         let b: TreeSet<int> = vec![2, 11, 77, -9, -42, 5, 3].into_iter().collect();
1033
1034         let set: TreeSet<int> = a & b;
1035         let v: Vec<int> = set.into_iter().collect();
1036         assert_eq!(v, vec![3, 5, 11, 77]);
1037     }
1038
1039     #[test]
1040     fn test_bit_xor() {
1041         let a: TreeSet<int> = vec![1, 3, 5, 9, 11].into_iter().collect();
1042         let b: TreeSet<int> = vec![-2, 3, 9, 14, 22].into_iter().collect();
1043
1044         let set: TreeSet<int> = a ^ b;
1045         let v: Vec<int> = set.into_iter().collect();
1046         assert_eq!(v, vec![-2, 1, 5, 11, 14, 22]);
1047     }
1048
1049     #[test]
1050     fn test_sub() {
1051         let a: TreeSet<int> = vec![-5, 11, 22, 33, 40, 42].into_iter().collect();
1052         let b: TreeSet<int> = vec![-12, -5, 14, 23, 34, 38, 39, 50].into_iter().collect();
1053
1054         let set: TreeSet<int> = a - b;
1055         let v: Vec<int> = set.into_iter().collect();
1056         assert_eq!(v, vec![11, 22, 33, 40, 42]);
1057     }
1058
1059     #[test]
1060     fn test_zip() {
1061         let mut x = TreeSet::new();
1062         x.insert(5u);
1063         x.insert(12u);
1064         x.insert(11u);
1065
1066         let mut y = TreeSet::new();
1067         y.insert("foo");
1068         y.insert("bar");
1069
1070         let x = x;
1071         let y = y;
1072         let mut z = x.iter().zip(y.iter());
1073
1074         // FIXME: #5801: this needs a type hint to compile...
1075         let result: Option<(&uint, & &'static str)> = z.next();
1076         assert_eq!(result.unwrap(), (&5u, &("bar")));
1077
1078         let result: Option<(&uint, & &'static str)> = z.next();
1079         assert_eq!(result.unwrap(), (&11u, &("foo")));
1080
1081         let result: Option<(&uint, & &'static str)> = z.next();
1082         assert!(result.is_none());
1083     }
1084
1085     #[test]
1086     fn test_from_iter() {
1087         let xs = [1i, 2, 3, 4, 5, 6, 7, 8, 9];
1088
1089         let set: TreeSet<int> = xs.iter().map(|&x| x).collect();
1090
1091         for x in xs.iter() {
1092             assert!(set.contains(x));
1093         }
1094     }
1095
1096     #[test]
1097     fn test_show() {
1098         let mut set: TreeSet<int> = TreeSet::new();
1099         let empty: TreeSet<int> = TreeSet::new();
1100
1101         set.insert(1);
1102         set.insert(2);
1103
1104         let set_str = format!("{}", set);
1105
1106         assert!(set_str == "{1, 2}");
1107         assert_eq!(format!("{}", empty), "{}");
1108     }
1109 }