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, IntoIterator};
  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(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<(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(feature = "rust1", since = "1.0.0")]
  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(feature = "rust1", since = "1.0.0")]
  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(feature = "rust1", since = "1.0.0")]
  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(feature = "rust1", since = "1.0.0")]
  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(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: uint) -> 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<uint> = [1u, 2, 3, 4].iter().map(|&x| x).collect();
 118     ///
 119     /// for x in set.iter() {
 120     ///     println!("{}", x);
 121     /// }
 122     ///
 123     /// let v: Vec<uint> = set.iter().map(|&x| x).collect();
 124     /// assert_eq!(v, vec![1u,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<uint> = [1u, 2, 3, 4].iter().map(|&x| x).collect();
 139     ///
 140     /// let v: Vec<uint> = set.into_iter().collect();
 141     /// assert_eq!(v, vec![1u,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(3u);
 166     /// set.insert(5u);
 167     /// set.insert(8u);
 168     /// for &elem in set.range(Included(&4), Included(&8)) {
 169     ///     println!("{}", elem);
 170     /// }
 171     /// assert_eq!(Some(&5u), 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(1u);
 193     /// a.insert(2u);
 194     ///
 195     /// let mut b = BTreeSet::new();
 196     /// b.insert(2u);
 197     /// b.insert(3u);
 198     ///
 199     /// let diff: Vec<uint> = a.difference(&b).cloned().collect();
 200     /// assert_eq!(diff, vec![1u]);
 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(1u);
 216     /// a.insert(2u);
 217     ///
 218     /// let mut b = BTreeSet::new();
 219     /// b.insert(2u);
 220     /// b.insert(3u);
 221     ///
 222     /// let sym_diff: Vec<uint> = a.symmetric_difference(&b).cloned().collect();
 223     /// assert_eq!(sym_diff, vec![1u,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(1u);
 240     /// a.insert(2u);
 241     ///
 242     /// let mut b = BTreeSet::new();
 243     /// b.insert(2u);
 244     /// b.insert(3u);
 245     ///
 246     /// let intersection: Vec<uint> = a.intersection(&b).cloned().collect();
 247     /// assert_eq!(intersection, vec![2u]);
 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(1u);
 264     ///
 265     /// let mut b = BTreeSet::new();
 266     /// b.insert(2u);
 267     ///
 268     /// let union: Vec<uint> = a.union(&b).cloned().collect();
 269     /// assert_eq!(union, vec![1u,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) -> uint { 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<int> = [1, 2, 3].iter().map(|&x| x).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 Q: BorrowFrom<T> + 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<int> = [1, 2, 3].iter().map(|&x| x).collect();
 352     /// let mut b: BTreeSet<int> = 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<int> = [1, 2, 3].iter().map(|&x| x).collect();
 373     /// let mut set: BTreeSet<int> = 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<int> = [1, 2].iter().map(|&x| x).collect();
 415     /// let mut set: BTreeSet<int> = 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 Q: BorrowFrom<T> + 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<Iter: Iterator<Item=T>>(iter: Iter) -> BTreeSet<T> {
 477         let mut set = BTreeSet::new();
 478         set.extend(iter);
 479         set
 480     }
 481 }
 482
 483 impl<T> IntoIterator for BTreeSet<T> {
 484     type Iter = IntoIter<T>;
 485
 486     fn into_iter(self) -> IntoIter<T> {
 487         self.into_iter()
 488     }
 489 }
 490
 491 impl<'a, T> IntoIterator for &'a BTreeSet<T> {
 492     type Iter = Iter<'a, T>;
 493
 494     fn into_iter(self) -> Iter<'a, T> {
 495         self.iter()
 496     }
 497 }
 498
 499 #[stable(feature = "rust1", since = "1.0.0")]
 500 impl<T: Ord> Extend<T> for BTreeSet<T> {
 501     #[inline]
 502     fn extend<Iter: Iterator<Item=T>>(&mut self, iter: Iter) {
 503         for elem in iter {
 504             self.insert(elem);
 505         }
 506     }
 507 }
 508
 509 #[stable(feature = "rust1", since = "1.0.0")]
 510 impl<T: Ord> Default for BTreeSet<T> {
 511     #[stable(feature = "rust1", since = "1.0.0")]
 512     fn default() -> BTreeSet<T> {
 513         BTreeSet::new()
 514     }
 515 }
 516
 517 #[stable(feature = "rust1", since = "1.0.0")]
 518 impl<'a, 'b, T: Ord + Clone> Sub<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 519     type Output = BTreeSet<T>;
 520
 521     /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
 522     ///
 523     /// # Examples
 524     ///
 525     /// ```
 526     /// use std::collections::BTreeSet;
 527     ///
 528     /// let a: BTreeSet<int> = vec![1, 2, 3].into_iter().collect();
 529     /// let b: BTreeSet<int> = vec![3, 4, 5].into_iter().collect();
 530     ///
 531     /// let result: BTreeSet<int> = &a - &b;
 532     /// let result_vec: Vec<int> = result.into_iter().collect();
 533     /// assert_eq!(result_vec, vec![1, 2]);
 534     /// ```
 535     fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 536         self.difference(rhs).cloned().collect()
 537     }
 538 }
 539
 540 #[stable(feature = "rust1", since = "1.0.0")]
 541 impl<'a, 'b, T: Ord + Clone> BitXor<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 542     type Output = BTreeSet<T>;
 543
 544     /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
 545     ///
 546     /// # Examples
 547     ///
 548     /// ```
 549     /// use std::collections::BTreeSet;
 550     ///
 551     /// let a: BTreeSet<int> = vec![1, 2, 3].into_iter().collect();
 552     /// let b: BTreeSet<int> = vec![2, 3, 4].into_iter().collect();
 553     ///
 554     /// let result: BTreeSet<int> = &a ^ &b;
 555     /// let result_vec: Vec<int> = result.into_iter().collect();
 556     /// assert_eq!(result_vec, vec![1, 4]);
 557     /// ```
 558     fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 559         self.symmetric_difference(rhs).cloned().collect()
 560     }
 561 }
 562
 563 #[stable(feature = "rust1", since = "1.0.0")]
 564 impl<'a, 'b, T: Ord + Clone> BitAnd<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 565     type Output = BTreeSet<T>;
 566
 567     /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
 568     ///
 569     /// # Examples
 570     ///
 571     /// ```
 572     /// use std::collections::BTreeSet;
 573     ///
 574     /// let a: BTreeSet<int> = vec![1, 2, 3].into_iter().collect();
 575     /// let b: BTreeSet<int> = vec![2, 3, 4].into_iter().collect();
 576     ///
 577     /// let result: BTreeSet<int> = &a & &b;
 578     /// let result_vec: Vec<int> = result.into_iter().collect();
 579     /// assert_eq!(result_vec, vec![2, 3]);
 580     /// ```
 581     fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 582         self.intersection(rhs).cloned().collect()
 583     }
 584 }
 585
 586 #[stable(feature = "rust1", since = "1.0.0")]
 587 impl<'a, 'b, T: Ord + Clone> BitOr<&'b BTreeSet<T>> for &'a BTreeSet<T> {
 588     type Output = BTreeSet<T>;
 589
 590     /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
 591     ///
 592     /// # Examples
 593     ///
 594     /// ```
 595     /// use std::collections::BTreeSet;
 596     ///
 597     /// let a: BTreeSet<int> = vec![1, 2, 3].into_iter().collect();
 598     /// let b: BTreeSet<int> = vec![3, 4, 5].into_iter().collect();
 599     ///
 600     /// let result: BTreeSet<int> = &a | &b;
 601     /// let result_vec: Vec<int> = result.into_iter().collect();
 602     /// assert_eq!(result_vec, vec![1, 2, 3, 4, 5]);
 603     /// ```
 604     fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> {
 605         self.union(rhs).cloned().collect()
 606     }
 607 }
 608
 609 #[stable(feature = "rust1", since = "1.0.0")]
 610 impl<T: Debug> Debug for BTreeSet<T> {
 611     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 612         try!(write!(f, "BTreeSet {{"));
 613
 614         for (i, x) in self.iter().enumerate() {
 615             if i != 0 { try!(write!(f, ", ")); }
 616             try!(write!(f, "{:?}", *x));
 617         }
 618
 619         write!(f, "}}")
 620     }
 621 }
 622
 623 #[stable(feature = "rust1", since = "1.0.0")]
 624 impl<'a, T> Iterator for Iter<'a, T> {
 625     type Item = &'a T;
 626
 627     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 628     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 629 }
 630 #[stable(feature = "rust1", since = "1.0.0")]
 631 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
 632     fn next_back(&mut self) -> Option<&'a T> { self.iter.next_back() }
 633 }
 634 #[stable(feature = "rust1", since = "1.0.0")]
 635 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
 636
 637
 638 #[stable(feature = "rust1", since = "1.0.0")]
 639 impl<T> Iterator for IntoIter<T> {
 640     type Item = T;
 641
 642     fn next(&mut self) -> Option<T> { self.iter.next() }
 643     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 644 }
 645 #[stable(feature = "rust1", since = "1.0.0")]
 646 impl<T> DoubleEndedIterator for IntoIter<T> {
 647     fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
 648 }
 649 #[stable(feature = "rust1", since = "1.0.0")]
 650 impl<T> ExactSizeIterator for IntoIter<T> {}
 651
 652
 653 impl<'a, T> Iterator for Range<'a, T> {
 654     type Item = &'a T;
 655
 656     fn next(&mut self) -> Option<&'a T> { self.iter.next() }
 657 }
 658 impl<'a, T> DoubleEndedIterator for Range<'a, T> {
 659     fn next_back(&mut self) -> Option<&'a T> { self.iter.next_back() }
 660 }
 661
 662 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
 663 fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>,
 664                         short: Ordering, long: Ordering) -> Ordering {
 665     match (x, y) {
 666         (None    , _       ) => short,
 667         (_       , None    ) => long,
 668         (Some(x1), Some(y1)) => x1.cmp(y1),
 669     }
 670 }
 671
 672 #[stable(feature = "rust1", since = "1.0.0")]
 673 impl<'a, T: Ord> Iterator for Difference<'a, T> {
 674     type Item = &'a T;
 675
 676     fn next(&mut self) -> Option<&'a T> {
 677         loop {
 678             match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
 679                 Less    => return self.a.next(),
 680                 Equal   => { self.a.next(); self.b.next(); }
 681                 Greater => { self.b.next(); }
 682             }
 683         }
 684     }
 685 }
 686
 687 #[stable(feature = "rust1", since = "1.0.0")]
 688 impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
 689     type Item = &'a T;
 690
 691     fn next(&mut self) -> Option<&'a T> {
 692         loop {
 693             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 694                 Less    => return self.a.next(),
 695                 Equal   => { self.a.next(); self.b.next(); }
 696                 Greater => return self.b.next(),
 697             }
 698         }
 699     }
 700 }
 701
 702 #[stable(feature = "rust1", since = "1.0.0")]
 703 impl<'a, T: Ord> Iterator for Intersection<'a, T> {
 704     type Item = &'a T;
 705
 706     fn next(&mut self) -> Option<&'a T> {
 707         loop {
 708             let o_cmp = match (self.a.peek(), self.b.peek()) {
 709                 (None    , _       ) => None,
 710                 (_       , None    ) => None,
 711                 (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
 712             };
 713             match o_cmp {
 714                 None          => return None,
 715                 Some(Less)    => { self.a.next(); }
 716                 Some(Equal)   => { self.b.next(); return self.a.next() }
 717                 Some(Greater) => { self.b.next(); }
 718             }
 719         }
 720     }
 721 }
 722
 723 #[stable(feature = "rust1", since = "1.0.0")]
 724 impl<'a, T: Ord> Iterator for Union<'a, T> {
 725     type Item = &'a T;
 726
 727     fn next(&mut self) -> Option<&'a T> {
 728         loop {
 729             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 730                 Less    => return self.a.next(),
 731                 Equal   => { self.b.next(); return self.a.next() }
 732                 Greater => return self.b.next(),
 733             }
 734         }
 735     }
 736 }
 737
 738
 739 #[cfg(test)]
 740 mod test {
 741     use prelude::*;
 742
 743     use super::BTreeSet;
 744     use std::hash::{self, SipHasher};
 745
 746     #[test]
 747     fn test_clone_eq() {
 748       let mut m = BTreeSet::new();
 749
 750       m.insert(1);
 751       m.insert(2);
 752
 753       assert!(m.clone() == m);
 754     }
 755
 756     #[test]
 757     fn test_hash() {
 758       let mut x = BTreeSet::new();
 759       let mut y = BTreeSet::new();
 760
 761       x.insert(1);
 762       x.insert(2);
 763       x.insert(3);
 764
 765       y.insert(3);
 766       y.insert(2);
 767       y.insert(1);
 768
 769       assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
 770     }
 771
 772     struct Counter<'a, 'b> {
 773         i: &'a mut uint,
 774         expected: &'b [int],
 775     }
 776
 777     impl<'a, 'b, 'c> FnMut<(&'c int,)> for Counter<'a, 'b> {
 778         type Output = bool;
 779
 780         extern "rust-call" fn call_mut(&mut self, (&x,): (&'c int,)) -> bool {
 781             assert_eq!(x, self.expected[*self.i]);
 782             *self.i += 1;
 783             true
 784         }
 785     }
 786
 787     fn check<F>(a: &[int], b: &[int], expected: &[int], f: F) where
 788         // FIXME Replace Counter with `Box<FnMut(_) -> _>`
 789         F: FnOnce(&BTreeSet<int>, &BTreeSet<int>, Counter) -> bool,
 790     {
 791         let mut set_a = BTreeSet::new();
 792         let mut set_b = BTreeSet::new();
 793
 794         for x in a { assert!(set_a.insert(*x)) }
 795         for y in b { assert!(set_b.insert(*y)) }
 796
 797         let mut i = 0;
 798         f(&set_a, &set_b, Counter { i: &mut i, expected: expected });
 799         assert_eq!(i, expected.len());
 800     }
 801
 802     #[test]
 803     fn test_intersection() {
 804         fn check_intersection(a: &[int], b: &[int], expected: &[int]) {
 805             check(a, b, expected, |x, y, f| x.intersection(y).all(f))
 806         }
 807
 808         check_intersection(&[], &[], &[]);
 809         check_intersection(&[1, 2, 3], &[], &[]);
 810         check_intersection(&[], &[1, 2, 3], &[]);
 811         check_intersection(&[2], &[1, 2, 3], &[2]);
 812         check_intersection(&[1, 2, 3], &[2], &[2]);
 813         check_intersection(&[11, 1, 3, 77, 103, 5, -5],
 814                            &[2, 11, 77, -9, -42, 5, 3],
 815                            &[3, 5, 11, 77]);
 816     }
 817
 818     #[test]
 819     fn test_difference() {
 820         fn check_difference(a: &[int], b: &[int], expected: &[int]) {
 821             check(a, b, expected, |x, y, f| x.difference(y).all(f))
 822         }
 823
 824         check_difference(&[], &[], &[]);
 825         check_difference(&[1, 12], &[], &[1, 12]);
 826         check_difference(&[], &[1, 2, 3, 9], &[]);
 827         check_difference(&[1, 3, 5, 9, 11],
 828                          &[3, 9],
 829                          &[1, 5, 11]);
 830         check_difference(&[-5, 11, 22, 33, 40, 42],
 831                          &[-12, -5, 14, 23, 34, 38, 39, 50],
 832                          &[11, 22, 33, 40, 42]);
 833     }
 834
 835     #[test]
 836     fn test_symmetric_difference() {
 837         fn check_symmetric_difference(a: &[int], b: &[int],
 838                                       expected: &[int]) {
 839             check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
 840         }
 841
 842         check_symmetric_difference(&[], &[], &[]);
 843         check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
 844         check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
 845         check_symmetric_difference(&[1, 3, 5, 9, 11],
 846                                    &[-2, 3, 9, 14, 22],
 847                                    &[-2, 1, 5, 11, 14, 22]);
 848     }
 849
 850     #[test]
 851     fn test_union() {
 852         fn check_union(a: &[int], b: &[int],
 853                                       expected: &[int]) {
 854             check(a, b, expected, |x, y, f| x.union(y).all(f))
 855         }
 856
 857         check_union(&[], &[], &[]);
 858         check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
 859         check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
 860         check_union(&[1, 3, 5, 9, 11, 16, 19, 24],
 861                     &[-2, 1, 5, 9, 13, 19],
 862                     &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
 863     }
 864
 865     #[test]
 866     fn test_zip() {
 867         let mut x = BTreeSet::new();
 868         x.insert(5u);
 869         x.insert(12u);
 870         x.insert(11u);
 871
 872         let mut y = BTreeSet::new();
 873         y.insert("foo");
 874         y.insert("bar");
 875
 876         let x = x;
 877         let y = y;
 878         let mut z = x.iter().zip(y.iter());
 879
 880         // FIXME: #5801: this needs a type hint to compile...
 881         let result: Option<(&uint, & &'static str)> = z.next();
 882         assert_eq!(result.unwrap(), (&5u, &("bar")));
 883
 884         let result: Option<(&uint, & &'static str)> = z.next();
 885         assert_eq!(result.unwrap(), (&11u, &("foo")));
 886
 887         let result: Option<(&uint, & &'static str)> = z.next();
 888         assert!(result.is_none());
 889     }
 890
 891     #[test]
 892     fn test_from_iter() {
 893         let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
 894
 895         let set: BTreeSet<int> = xs.iter().map(|&x| x).collect();
 896
 897         for x in &xs {
 898             assert!(set.contains(x));
 899         }
 900     }
 901
 902     #[test]
 903     fn test_show() {
 904         let mut set: BTreeSet<int> = BTreeSet::new();
 905         let empty: BTreeSet<int> = BTreeSet::new();
 906
 907         set.insert(1);
 908         set.insert(2);
 909
 910         let set_str = format!("{:?}", set);
 911
 912         assert_eq!(set_str, "BTreeSet {1, 2}");
 913         assert_eq!(format!("{:?}", empty), "BTreeSet {}");
 914     }
 915 }