src/libcollections/treemap.rs

   1 // Copyright 2013 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 //! An ordered map and set implemented as self-balancing binary search
  12 //! trees. The only requirement for the types is that the key implements
  13 //! `Ord`.
  14 //!
  15 //! ## Example
  16 //!
  17 //! ```{rust}
  18 //! use std::collections::TreeSet;
  19 //!
  20 //! let mut tree_set = TreeSet::new();
  21 //!
  22 //! tree_set.insert(2i);
  23 //! tree_set.insert(1i);
  24 //! tree_set.insert(3i);
  25 //!
  26 //! for i in tree_set.iter() {
  27 //!    println!("{}", i) // prints 1, then 2, then 3
  28 //! }
  29 //! ```
  30
  31 use core::prelude::*;
  32
  33 use alloc::boxed::Box;
  34 use core::default::Default;
  35 use core::fmt;
  36 use core::fmt::Show;
  37 use core::iter::Peekable;
  38 use core::iter;
  39 use core::mem::{replace, swap};
  40 use core::ptr;
  41 use std::hash::{Writer, Hash};
  42
  43 use {Collection, Mutable, Set, MutableSet, MutableMap, Map};
  44 use vec::Vec;
  45
  46 // This is implemented as an AA tree, which is a simplified variation of
  47 // a red-black tree where red (horizontal) nodes can only be added
  48 // as a right child. The time complexity is the same, and re-balancing
  49 // operations are more frequent but also cheaper.
  50
  51 // Future improvements:
  52
  53 // range search - O(log n) retrieval of an iterator from some key
  54
  55 // (possibly) implement the overloads Python does for sets:
  56 //   * intersection: &
  57 //   * difference: -
  58 //   * symmetric difference: ^
  59 //   * union: |
  60 // These would be convenient since the methods work like `each`
  61
  62 #[allow(missing_doc)]
  63 #[deriving(Clone)]
  64 pub struct TreeMap<K, V> {
  65     root: Option<Box<TreeNode<K, V>>>,
  66     length: uint
  67 }
  68
  69 impl<K: PartialEq + Ord, V: PartialEq> PartialEq for TreeMap<K, V> {
  70     fn eq(&self, other: &TreeMap<K, V>) -> bool {
  71         self.len() == other.len() &&
  72             self.iter().zip(other.iter()).all(|(a, b)| a == b)
  73     }
  74 }
  75
  76 impl<K: Ord, V: PartialOrd> PartialOrd for TreeMap<K, V> {
  77     #[inline]
  78     fn partial_cmp(&self, other: &TreeMap<K, V>) -> Option<Ordering> {
  79         iter::order::partial_cmp(self.iter(), other.iter())
  80     }
  81 }
  82
  83 impl<K: Ord + Show, V: Show> Show for TreeMap<K, V> {
  84     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  85         try!(write!(f, "{{"));
  86
  87         for (i, (k, v)) in self.iter().enumerate() {
  88             if i != 0 { try!(write!(f, ", ")); }
  89             try!(write!(f, "{}: {}", *k, *v));
  90         }
  91
  92         write!(f, "}}")
  93     }
  94 }
  95
  96 impl<K: Ord, V> Collection for TreeMap<K, V> {
  97     fn len(&self) -> uint { self.length }
  98 }
  99
 100 impl<K: Ord, V> Mutable for TreeMap<K, V> {
 101     fn clear(&mut self) {
 102         self.root = None;
 103         self.length = 0
 104     }
 105 }
 106
 107 impl<K: Ord, V> Map<K, V> for TreeMap<K, V> {
 108     // See comments on tree_find_with
 109     #[inline]
 110     fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
 111         tree_find_with(&self.root, |k2| key.cmp(k2))
 112     }
 113 }
 114
 115 impl<K: Ord, V> MutableMap<K, V> for TreeMap<K, V> {
 116     // See comments on def_tree_find_mut_with
 117     #[inline]
 118     fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
 119         tree_find_mut_with(&mut self.root, |x| key.cmp(x))
 120     }
 121
 122     fn swap(&mut self, key: K, value: V) -> Option<V> {
 123         let ret = insert(&mut self.root, key, value);
 124         if ret.is_none() { self.length += 1 }
 125         ret
 126     }
 127
 128     fn pop(&mut self, key: &K) -> Option<V> {
 129         let ret = remove(&mut self.root, key);
 130         if ret.is_some() { self.length -= 1 }
 131         ret
 132     }
 133 }
 134
 135 impl<K: Ord, V> Default for TreeMap<K,V> {
 136     #[inline]
 137     fn default() -> TreeMap<K, V> { TreeMap::new() }
 138 }
 139
 140 impl<K: Ord, V> TreeMap<K, V> {
 141     /// Create an empty TreeMap
 142     pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
 143
 144     /// Get a lazy iterator over the key-value pairs in the map.
 145     /// Requires that it be frozen (immutable).
 146     pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
 147         Entries {
 148             stack: vec!(),
 149             node: deref(&self.root),
 150             remaining_min: self.length,
 151             remaining_max: self.length
 152         }
 153     }
 154
 155     /// Get a lazy reverse iterator over the key-value pairs in the map.
 156     /// Requires that it be frozen (immutable).
 157     pub fn rev_iter<'a>(&'a self) -> RevEntries<'a, K, V> {
 158         RevEntries{iter: self.iter()}
 159     }
 160
 161     /// Get a lazy forward iterator over the key-value pairs in the
 162     /// map, with the values being mutable.
 163     pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
 164         MutEntries {
 165             stack: vec!(),
 166             node: mut_deref(&mut self.root),
 167             remaining_min: self.length,
 168             remaining_max: self.length
 169         }
 170     }
 171     /// Get a lazy reverse iterator over the key-value pairs in the
 172     /// map, with the values being mutable.
 173     pub fn mut_rev_iter<'a>(&'a mut self) -> RevMutEntries<'a, K, V> {
 174         RevMutEntries{iter: self.mut_iter()}
 175     }
 176
 177
 178     /// Get a lazy iterator that consumes the treemap.
 179     pub fn move_iter(self) -> MoveEntries<K, V> {
 180         let TreeMap { root: root, length: length } = self;
 181         let stk = match root {
 182             None => vec!(),
 183             Some(box tn) => vec!(tn)
 184         };
 185         MoveEntries {
 186             stack: stk,
 187             remaining: length
 188         }
 189     }
 190 }
 191
 192 impl<K, V> TreeMap<K, V> {
 193     /// Return the value for which `f(key)` returns `Equal`. `f` is invoked
 194     /// with current key and guides tree navigation. That means `f` should
 195     /// be aware of natural ordering of the tree.
 196     ///
 197     /// # Example
 198     ///
 199     /// ```
 200     /// use collections::treemap::TreeMap;
 201     ///
 202     /// fn get_headers() -> TreeMap<String, String> {
 203     ///     let mut result = TreeMap::new();
 204     ///     result.insert("Content-Type".to_string(), "application/xml".to_string());
 205     ///     result.insert("User-Agent".to_string(), "Curl-Rust/0.1".to_string());
 206     ///     result
 207     /// }
 208     ///
 209     /// let headers = get_headers();
 210     /// let ua_key = "User-Agent";
 211     /// let ua = headers.find_with(|k| {
 212     ///    ua_key.cmp(&k.as_slice())
 213     /// });
 214     ///
 215     /// assert_eq!((*ua.unwrap()).as_slice(), "Curl-Rust/0.1");
 216     /// ```
 217     #[inline]
 218     pub fn find_with<'a>(&'a self, f:|&K| -> Ordering) -> Option<&'a V> {
 219         tree_find_with(&self.root, f)
 220     }
 221
 222     /// Return the value for which `f(key)` returns `Equal`. `f` is invoked
 223     /// with current key and guides tree navigation. That means `f` should
 224     /// be aware of natural ordering of the tree.
 225     /// # Example
 226     ///
 227     /// ```
 228     /// let mut t = collections::treemap::TreeMap::new();
 229     /// t.insert("Content-Type", "application/xml");
 230     /// t.insert("User-Agent", "Curl-Rust/0.1");
 231     ///
 232     /// let new_ua = "Safari/156.0";
 233     /// match t.find_mut_with(|k| "User-Agent".cmp(k)) {
 234     ///    Some(x) => *x = new_ua,
 235     ///    None => fail!(),
 236     /// }
 237     ///
 238     /// assert_eq!(t.find(&"User-Agent"), Some(&new_ua));
 239     /// ```
 240     #[inline]
 241     pub fn find_mut_with<'a>(&'a mut self, f:|&K| -> Ordering) -> Option<&'a mut V> {
 242         tree_find_mut_with(&mut self.root, f)
 243     }
 244 }
 245
 246 // range iterators.
 247
 248 macro_rules! bound_setup {
 249     // initialiser of the iterator to manipulate
 250     ($iter:expr, $k:expr,
 251      // whether we are looking for the lower or upper bound.
 252      $is_lower_bound:expr) => {
 253         {
 254             let mut iter = $iter;
 255             loop {
 256                 if !iter.node.is_null() {
 257                     let node_k = unsafe {&(*iter.node).key};
 258                     match $k.cmp(node_k) {
 259                         Less => iter.traverse_left(),
 260                         Greater => iter.traverse_right(),
 261                         Equal => {
 262                             if $is_lower_bound {
 263                                 iter.traverse_complete();
 264                                 return iter;
 265                             } else {
 266                                 iter.traverse_right()
 267                             }
 268                         }
 269                     }
 270                 } else {
 271                     iter.traverse_complete();
 272                     return iter;
 273                 }
 274             }
 275         }
 276     }
 277 }
 278
 279
 280 impl<K: Ord, V> TreeMap<K, V> {
 281     /// Get a lazy iterator that should be initialized using
 282     /// `traverse_left`/`traverse_right`/`traverse_complete`.
 283     fn iter_for_traversal<'a>(&'a self) -> Entries<'a, K, V> {
 284         Entries {
 285             stack: vec!(),
 286             node: deref(&self.root),
 287             remaining_min: 0,
 288             remaining_max: self.length
 289         }
 290     }
 291
 292     /// Return a lazy iterator to the first key-value pair whose key is not less than `k`
 293     /// If all keys in map are less than `k` an empty iterator is returned.
 294     pub fn lower_bound<'a>(&'a self, k: &K) -> Entries<'a, K, V> {
 295         bound_setup!(self.iter_for_traversal(), k, true)
 296     }
 297
 298     /// Return a lazy iterator to the first key-value pair whose key is greater than `k`
 299     /// If all keys in map are not greater than `k` an empty iterator is returned.
 300     pub fn upper_bound<'a>(&'a self, k: &K) -> Entries<'a, K, V> {
 301         bound_setup!(self.iter_for_traversal(), k, false)
 302     }
 303
 304     /// Get a lazy iterator that should be initialized using
 305     /// `traverse_left`/`traverse_right`/`traverse_complete`.
 306     fn mut_iter_for_traversal<'a>(&'a mut self) -> MutEntries<'a, K, V> {
 307         MutEntries {
 308             stack: vec!(),
 309             node: mut_deref(&mut self.root),
 310             remaining_min: 0,
 311             remaining_max: self.length
 312         }
 313     }
 314
 315     /// Return a lazy value iterator to the first key-value pair (with
 316     /// the value being mutable) whose key is not less than `k`.
 317     ///
 318     /// If all keys in map are less than `k` an empty iterator is
 319     /// returned.
 320     pub fn mut_lower_bound<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
 321         bound_setup!(self.mut_iter_for_traversal(), k, true)
 322     }
 323
 324     /// Return a lazy iterator to the first key-value pair (with the
 325     /// value being mutable) whose key is greater than `k`.
 326     ///
 327     /// If all keys in map are not greater than `k` an empty iterator
 328     /// is returned.
 329     pub fn mut_upper_bound<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
 330         bound_setup!(self.mut_iter_for_traversal(), k, false)
 331     }
 332 }
 333
 334 /// Lazy forward iterator over a map
 335 pub struct Entries<'a, K, V> {
 336     stack: Vec<&'a TreeNode<K, V>>,
 337     // See the comment on MutEntries; this is just to allow
 338     // code-sharing (for this immutable-values iterator it *could* very
 339     // well be Option<&'a TreeNode<K,V>>).
 340     node: *const TreeNode<K, V>,
 341     remaining_min: uint,
 342     remaining_max: uint
 343 }
 344
 345 /// Lazy backward iterator over a map
 346 pub struct RevEntries<'a, K, V> {
 347     iter: Entries<'a, K, V>,
 348 }
 349
 350 /// Lazy forward iterator over a map that allows for the mutation of
 351 /// the values.
 352 pub struct MutEntries<'a, K, V> {
 353     stack: Vec<&'a mut TreeNode<K, V>>,
 354     // Unfortunately, we require some unsafe-ness to get around the
 355     // fact that we would be storing a reference *into* one of the
 356     // nodes in the stack.
 357     //
 358     // As far as the compiler knows, this would let us invalidate the
 359     // reference by assigning a new value to this node's position in
 360     // its parent, which would cause this current one to be
 361     // deallocated so this reference would be invalid. (i.e. the
 362     // compilers complaints are 100% correct.)
 363     //
 364     // However, as far as you humans reading this code know (or are
 365     // about to know, if you haven't read far enough down yet), we are
 366     // only reading from the TreeNode.{left,right} fields. the only
 367     // thing that is ever mutated is the .value field (although any
 368     // actual mutation that happens is done externally, by the
 369     // iterator consumer). So, don't be so concerned, rustc, we've got
 370     // it under control.
 371     //
 372     // (This field can legitimately be null.)
 373     node: *mut TreeNode<K, V>,
 374     remaining_min: uint,
 375     remaining_max: uint
 376 }
 377
 378 /// Lazy backward iterator over a map
 379 pub struct RevMutEntries<'a, K, V> {
 380     iter: MutEntries<'a, K, V>,
 381 }
 382
 383
 384 // FIXME #5846 we want to be able to choose between &x and &mut x
 385 // (with many different `x`) below, so we need to optionally pass mut
 386 // as a tt, but the only thing we can do with a `tt` is pass them to
 387 // other macros, so this takes the `& <mutability> <operand>` token
 388 // sequence and forces their evaluation as an expression.
 389 macro_rules! addr { ($e:expr) => { $e }}
 390 // putting an optional mut into type signatures
 391 macro_rules! item { ($i:item) => { $i }}
 392
 393 macro_rules! define_iterator {
 394     ($name:ident,
 395      $rev_name:ident,
 396
 397      // the function to go from &m Option<Box<TreeNode>> to *m TreeNode
 398      deref = $deref:ident,
 399
 400      // see comment on `addr!`, this is just an optional `mut`, but
 401      // there's no support for 0-or-1 repeats.
 402      addr_mut = $($addr_mut:tt)*
 403      ) => {
 404         // private methods on the forward iterator (item!() for the
 405         // addr_mut in the next_ return value)
 406         item!(impl<'a, K, V> $name<'a, K, V> {
 407             #[inline(always)]
 408             fn next_(&mut self, forward: bool) -> Option<(&'a K, &'a $($addr_mut)* V)> {
 409                 while !self.stack.is_empty() || !self.node.is_null() {
 410                     if !self.node.is_null() {
 411                         let node = unsafe {addr!(& $($addr_mut)* *self.node)};
 412                         {
 413                             let next_node = if forward {
 414                                 addr!(& $($addr_mut)* node.left)
 415                             } else {
 416                                 addr!(& $($addr_mut)* node.right)
 417                             };
 418                             self.node = $deref(next_node);
 419                         }
 420                         self.stack.push(node);
 421                     } else {
 422                         let node = self.stack.pop().unwrap();
 423                         let next_node = if forward {
 424                             addr!(& $($addr_mut)* node.right)
 425                         } else {
 426                             addr!(& $($addr_mut)* node.left)
 427                         };
 428                         self.node = $deref(next_node);
 429                         self.remaining_max -= 1;
 430                         if self.remaining_min > 0 {
 431                             self.remaining_min -= 1;
 432                         }
 433                         return Some((&node.key, addr!(& $($addr_mut)* node.value)));
 434                     }
 435                 }
 436                 None
 437             }
 438
 439             /// traverse_left, traverse_right and traverse_complete are
 440             /// used to initialize Entries/MutEntries
 441             /// pointing to element inside tree structure.
 442             ///
 443             /// They should be used in following manner:
 444             ///   - create iterator using TreeMap::[mut_]iter_for_traversal
 445             ///   - find required node using `traverse_left`/`traverse_right`
 446             ///     (current node is `Entries::node` field)
 447             ///   - complete initialization with `traverse_complete`
 448             ///
 449             /// After this, iteration will start from `self.node`.  If
 450             /// `self.node` is None iteration will start from last
 451             /// node from which we traversed left.
 452             #[inline]
 453             fn traverse_left(&mut self) {
 454                 let node = unsafe {addr!(& $($addr_mut)* *self.node)};
 455                 self.node = $deref(addr!(& $($addr_mut)* node.left));
 456                 self.stack.push(node);
 457             }
 458
 459             #[inline]
 460             fn traverse_right(&mut self) {
 461                 let node = unsafe {addr!(& $($addr_mut)* *self.node)};
 462                 self.node = $deref(addr!(& $($addr_mut)* node.right));
 463             }
 464
 465             #[inline]
 466             fn traverse_complete(&mut self) {
 467                 if !self.node.is_null() {
 468                     unsafe {
 469                         self.stack.push(addr!(& $($addr_mut)* *self.node));
 470                     }
 471                     self.node = ptr::RawPtr::null();
 472                 }
 473             }
 474         })
 475
 476         // the forward Iterator impl.
 477         item!(impl<'a, K, V> Iterator<(&'a K, &'a $($addr_mut)* V)> for $name<'a, K, V> {
 478             /// Advance the iterator to the next node (in order) and return a
 479             /// tuple with a reference to the key and value. If there are no
 480             /// more nodes, return `None`.
 481             fn next(&mut self) -> Option<(&'a K, &'a $($addr_mut)* V)> {
 482                 self.next_(true)
 483             }
 484
 485             #[inline]
 486             fn size_hint(&self) -> (uint, Option<uint>) {
 487                 (self.remaining_min, Some(self.remaining_max))
 488             }
 489         })
 490
 491         // the reverse Iterator impl.
 492         item!(impl<'a, K, V> Iterator<(&'a K, &'a $($addr_mut)* V)> for $rev_name<'a, K, V> {
 493             fn next(&mut self) -> Option<(&'a K, &'a $($addr_mut)* V)> {
 494                 self.iter.next_(false)
 495             }
 496
 497             #[inline]
 498             fn size_hint(&self) -> (uint, Option<uint>) {
 499                 self.iter.size_hint()
 500             }
 501         })
 502     }
 503 } // end of define_iterator
 504
 505 define_iterator! {
 506     Entries,
 507     RevEntries,
 508     deref = deref,
 509
 510     // immutable, so no mut
 511     addr_mut =
 512 }
 513 define_iterator! {
 514     MutEntries,
 515     RevMutEntries,
 516     deref = mut_deref,
 517
 518     addr_mut = mut
 519 }
 520
 521 fn deref<'a, K, V>(node: &'a Option<Box<TreeNode<K, V>>>) -> *const TreeNode<K, V> {
 522     match *node {
 523         Some(ref n) => {
 524             let n: &TreeNode<K, V> = &**n;
 525             n as *const TreeNode<K, V>
 526         }
 527         None => ptr::null()
 528     }
 529 }
 530
 531 fn mut_deref<K, V>(x: &mut Option<Box<TreeNode<K, V>>>)
 532              -> *mut TreeNode<K, V> {
 533     match *x {
 534         Some(ref mut n) => {
 535             let n: &mut TreeNode<K, V> = &mut **n;
 536             n as *mut TreeNode<K, V>
 537         }
 538         None => ptr::mut_null()
 539     }
 540 }
 541
 542
 543
 544 /// Lazy forward iterator over a map that consumes the map while iterating
 545 pub struct MoveEntries<K, V> {
 546     stack: Vec<TreeNode<K, V>>,
 547     remaining: uint
 548 }
 549
 550 impl<K, V> Iterator<(K, V)> for MoveEntries<K,V> {
 551     #[inline]
 552     fn next(&mut self) -> Option<(K, V)> {
 553         while !self.stack.is_empty() {
 554             let TreeNode {
 555                 key: key,
 556                 value: value,
 557                 left: left,
 558                 right: right,
 559                 level: level
 560             } = self.stack.pop().unwrap();
 561
 562             match left {
 563                 Some(box left) => {
 564                     let n = TreeNode {
 565                         key: key,
 566                         value: value,
 567                         left: None,
 568                         right: right,
 569                         level: level
 570                     };
 571                     self.stack.push(n);
 572                     self.stack.push(left);
 573                 }
 574                 None => {
 575                     match right {
 576                         Some(box right) => self.stack.push(right),
 577                         None => ()
 578                     }
 579                     self.remaining -= 1;
 580                     return Some((key, value))
 581                 }
 582             }
 583         }
 584         None
 585     }
 586
 587     #[inline]
 588     fn size_hint(&self) -> (uint, Option<uint>) {
 589         (self.remaining, Some(self.remaining))
 590     }
 591
 592 }
 593
 594 impl<'a, T> Iterator<&'a T> for SetItems<'a, T> {
 595     #[inline]
 596     fn next(&mut self) -> Option<&'a T> {
 597         self.iter.next().map(|(value, _)| value)
 598     }
 599 }
 600
 601 impl<'a, T> Iterator<&'a T> for RevSetItems<'a, T> {
 602     #[inline]
 603     fn next(&mut self) -> Option<&'a T> {
 604         self.iter.next().map(|(value, _)| value)
 605     }
 606 }
 607
 608 /// A implementation of the `Set` trait on top of the `TreeMap` container. The
 609 /// only requirement is that the type of the elements contained ascribes to the
 610 /// `Ord` trait.
 611 ///
 612 /// ## Example
 613 ///
 614 /// ```{rust}
 615 /// use std::collections::TreeSet;
 616 ///
 617 /// let mut tree_set = TreeSet::new();
 618 ///
 619 /// tree_set.insert(2i);
 620 /// tree_set.insert(1i);
 621 /// tree_set.insert(3i);
 622 ///
 623 /// for i in tree_set.iter() {
 624 ///    println!("{}", i) // prints 1, then 2, then 3
 625 /// }
 626 /// ```
 627 #[deriving(Clone)]
 628 pub struct TreeSet<T> {
 629     map: TreeMap<T, ()>
 630 }
 631
 632 impl<T: PartialEq + Ord> PartialEq for TreeSet<T> {
 633     #[inline]
 634     fn eq(&self, other: &TreeSet<T>) -> bool { self.map == other.map }
 635 }
 636
 637 impl<T: Ord> PartialOrd for TreeSet<T> {
 638     #[inline]
 639     fn partial_cmp(&self, other: &TreeSet<T>) -> Option<Ordering> {
 640         self.map.partial_cmp(&other.map)
 641     }
 642 }
 643
 644 impl<T: Ord + Show> Show for TreeSet<T> {
 645     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 646         try!(write!(f, "{{"));
 647
 648         for (i, x) in self.iter().enumerate() {
 649             if i != 0 { try!(write!(f, ", ")); }
 650             try!(write!(f, "{}", *x));
 651         }
 652
 653         write!(f, "}}")
 654     }
 655 }
 656
 657 impl<T: Ord> Collection for TreeSet<T> {
 658     #[inline]
 659     fn len(&self) -> uint { self.map.len() }
 660 }
 661
 662 impl<T: Ord> Mutable for TreeSet<T> {
 663     #[inline]
 664     fn clear(&mut self) { self.map.clear() }
 665 }
 666
 667 impl<T: Ord> Set<T> for TreeSet<T> {
 668     #[inline]
 669     fn contains(&self, value: &T) -> bool {
 670         self.map.contains_key(value)
 671     }
 672
 673     fn is_disjoint(&self, other: &TreeSet<T>) -> bool {
 674         self.intersection(other).next().is_none()
 675     }
 676
 677     fn is_subset(&self, other: &TreeSet<T>) -> bool {
 678         let mut x = self.iter();
 679         let mut y = other.iter();
 680         let mut a = x.next();
 681         let mut b = y.next();
 682         while a.is_some() {
 683             if b.is_none() {
 684                 return false;
 685             }
 686
 687             let a1 = a.unwrap();
 688             let b1 = b.unwrap();
 689
 690             match b1.cmp(a1) {
 691                 Less => (),
 692                 Greater => return false,
 693                 Equal => a = x.next(),
 694             }
 695
 696             b = y.next();
 697         }
 698         true
 699     }
 700 }
 701
 702 impl<T: Ord> MutableSet<T> for TreeSet<T> {
 703     #[inline]
 704     fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
 705
 706     #[inline]
 707     fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
 708 }
 709
 710 impl<T: Ord> Default for TreeSet<T> {
 711     #[inline]
 712     fn default() -> TreeSet<T> { TreeSet::new() }
 713 }
 714
 715 impl<T: Ord> TreeSet<T> {
 716     /// Create an empty TreeSet
 717     #[inline]
 718     pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} }
 719
 720     /// Get a lazy iterator over the values in the set.
 721     /// Requires that it be frozen (immutable).
 722     #[inline]
 723     pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
 724         SetItems{iter: self.map.iter()}
 725     }
 726
 727     /// Get a lazy iterator over the values in the set.
 728     /// Requires that it be frozen (immutable).
 729     #[inline]
 730     pub fn rev_iter<'a>(&'a self) -> RevSetItems<'a, T> {
 731         RevSetItems{iter: self.map.rev_iter()}
 732     }
 733
 734     /// Get a lazy iterator that consumes the set.
 735     #[inline]
 736     pub fn move_iter(self) -> MoveSetItems<T> {
 737         self.map.move_iter().map(|(value, _)| value)
 738     }
 739
 740     /// Get a lazy iterator pointing to the first value not less than `v` (greater or equal).
 741     /// If all elements in the set are less than `v` empty iterator is returned.
 742     #[inline]
 743     pub fn lower_bound<'a>(&'a self, v: &T) -> SetItems<'a, T> {
 744         SetItems{iter: self.map.lower_bound(v)}
 745     }
 746
 747     /// Get a lazy iterator pointing to the first value greater than `v`.
 748     /// If all elements in the set are not greater than `v` empty iterator is returned.
 749     #[inline]
 750     pub fn upper_bound<'a>(&'a self, v: &T) -> SetItems<'a, T> {
 751         SetItems{iter: self.map.upper_bound(v)}
 752     }
 753
 754     /// Visit the values (in-order) representing the difference
 755     pub fn difference<'a>(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T> {
 756         DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
 757     }
 758
 759     /// Visit the values (in-order) representing the symmetric difference
 760     pub fn symmetric_difference<'a>(&'a self, other: &'a TreeSet<T>)
 761         -> SymDifferenceItems<'a, T> {
 762         SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
 763     }
 764
 765     /// Visit the values (in-order) representing the intersection
 766     pub fn intersection<'a>(&'a self, other: &'a TreeSet<T>)
 767         -> IntersectionItems<'a, T> {
 768         IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()}
 769     }
 770
 771     /// Visit the values (in-order) representing the union
 772     pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> {
 773         UnionItems{a: self.iter().peekable(), b: other.iter().peekable()}
 774     }
 775 }
 776
 777 /// Lazy forward iterator over a set
 778 pub struct SetItems<'a, T> {
 779     iter: Entries<'a, T, ()>
 780 }
 781
 782 /// Lazy backward iterator over a set
 783 pub struct RevSetItems<'a, T> {
 784     iter: RevEntries<'a, T, ()>
 785 }
 786
 787 /// Lazy forward iterator over a set that consumes the set while iterating
 788 pub type MoveSetItems<T> = iter::Map<'static, (T, ()), T, MoveEntries<T, ()>>;
 789
 790 /// Lazy iterator producing elements in the set difference (in-order)
 791 pub struct DifferenceItems<'a, T> {
 792     a: Peekable<&'a T, SetItems<'a, T>>,
 793     b: Peekable<&'a T, SetItems<'a, T>>,
 794 }
 795
 796 /// Lazy iterator producing elements in the set symmetric difference (in-order)
 797 pub struct SymDifferenceItems<'a, T> {
 798     a: Peekable<&'a T, SetItems<'a, T>>,
 799     b: Peekable<&'a T, SetItems<'a, T>>,
 800 }
 801
 802 /// Lazy iterator producing elements in the set intersection (in-order)
 803 pub struct IntersectionItems<'a, T> {
 804     a: Peekable<&'a T, SetItems<'a, T>>,
 805     b: Peekable<&'a T, SetItems<'a, T>>,
 806 }
 807
 808 /// Lazy iterator producing elements in the set union (in-order)
 809 pub struct UnionItems<'a, T> {
 810     a: Peekable<&'a T, SetItems<'a, T>>,
 811     b: Peekable<&'a T, SetItems<'a, T>>,
 812 }
 813
 814 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
 815 fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>,
 816                         short: Ordering, long: Ordering) -> Ordering {
 817     match (x, y) {
 818         (None    , _       ) => short,
 819         (_       , None    ) => long,
 820         (Some(x1), Some(y1)) => x1.cmp(y1),
 821     }
 822 }
 823
 824 impl<'a, T: Ord> Iterator<&'a T> for DifferenceItems<'a, T> {
 825     fn next(&mut self) -> Option<&'a T> {
 826         loop {
 827             match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
 828                 Less    => return self.a.next(),
 829                 Equal   => { self.a.next(); self.b.next(); }
 830                 Greater => { self.b.next(); }
 831             }
 832         }
 833     }
 834 }
 835
 836 impl<'a, T: Ord> Iterator<&'a T> for SymDifferenceItems<'a, T> {
 837     fn next(&mut self) -> Option<&'a T> {
 838         loop {
 839             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 840                 Less    => return self.a.next(),
 841                 Equal   => { self.a.next(); self.b.next(); }
 842                 Greater => return self.b.next(),
 843             }
 844         }
 845     }
 846 }
 847
 848 impl<'a, T: Ord> Iterator<&'a T> for IntersectionItems<'a, T> {
 849     fn next(&mut self) -> Option<&'a T> {
 850         loop {
 851             let o_cmp = match (self.a.peek(), self.b.peek()) {
 852                 (None    , _       ) => None,
 853                 (_       , None    ) => None,
 854                 (Some(a1), Some(b1)) => Some(a1.cmp(b1)),
 855             };
 856             match o_cmp {
 857                 None          => return None,
 858                 Some(Less)    => { self.a.next(); }
 859                 Some(Equal)   => { self.b.next(); return self.a.next() }
 860                 Some(Greater) => { self.b.next(); }
 861             }
 862         }
 863     }
 864 }
 865
 866 impl<'a, T: Ord> Iterator<&'a T> for UnionItems<'a, T> {
 867     fn next(&mut self) -> Option<&'a T> {
 868         loop {
 869             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
 870                 Less    => return self.a.next(),
 871                 Equal   => { self.b.next(); return self.a.next() }
 872                 Greater => return self.b.next(),
 873             }
 874         }
 875     }
 876 }
 877
 878
 879 // Nodes keep track of their level in the tree, starting at 1 in the
 880 // leaves and with a red child sharing the level of the parent.
 881 #[deriving(Clone)]
 882 struct TreeNode<K, V> {
 883     key: K,
 884     value: V,
 885     left: Option<Box<TreeNode<K, V>>>,
 886     right: Option<Box<TreeNode<K, V>>>,
 887     level: uint
 888 }
 889
 890 impl<K: Ord, V> TreeNode<K, V> {
 891     /// Creates a new tree node.
 892     #[inline]
 893     pub fn new(key: K, value: V) -> TreeNode<K, V> {
 894         TreeNode{key: key, value: value, left: None, right: None, level: 1}
 895     }
 896 }
 897
 898 // Remove left horizontal link by rotating right
 899 fn skew<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
 900     if node.left.as_ref().map_or(false, |x| x.level == node.level) {
 901         let mut save = node.left.take_unwrap();
 902         swap(&mut node.left, &mut save.right); // save.right now None
 903         swap(node, &mut save);
 904         node.right = Some(save);
 905     }
 906 }
 907
 908 // Remove dual horizontal link by rotating left and increasing level of
 909 // the parent
 910 fn split<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
 911     if node.right.as_ref().map_or(false,
 912       |x| x.right.as_ref().map_or(false, |y| y.level == node.level)) {
 913         let mut save = node.right.take_unwrap();
 914         swap(&mut node.right, &mut save.left); // save.left now None
 915         save.level += 1;
 916         swap(node, &mut save);
 917         node.left = Some(save);
 918     }
 919 }
 920
 921 // Next 2 functions have the same convention: comparator gets
 922 // at input current key and returns search_key cmp cur_key
 923 // (i.e. search_key.cmp(&cur_key))
 924 fn tree_find_with<'r, K, V>(node: &'r Option<Box<TreeNode<K, V>>>,
 925                             f: |&K| -> Ordering) -> Option<&'r V> {
 926     let mut current: &'r Option<Box<TreeNode<K, V>>> = node;
 927     loop {
 928         match *current {
 929             Some(ref r) => {
 930                 match f(&r.key) {
 931                     Less => current = &r.left,
 932                     Greater => current = &r.right,
 933                     Equal => return Some(&r.value)
 934                 }
 935             }
 936             None => return None
 937         }
 938     }
 939 }
 940
 941 // See comments above tree_find_with
 942 fn tree_find_mut_with<'r, K, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
 943                                 f: |&K| -> Ordering) -> Option<&'r mut V> {
 944
 945     let mut current = node;
 946     loop {
 947         let temp = current; // hack to appease borrowck
 948         match *temp {
 949             Some(ref mut r) => {
 950                 match f(&r.key) {
 951                     Less => current = &mut r.left,
 952                     Greater => current = &mut r.right,
 953                     Equal => return Some(&mut r.value)
 954                 }
 955             }
 956             None => return None
 957         }
 958     }
 959 }
 960
 961 fn insert<K: Ord, V>(node: &mut Option<Box<TreeNode<K, V>>>,
 962                           key: K, value: V) -> Option<V> {
 963     match *node {
 964       Some(ref mut save) => {
 965         match key.cmp(&save.key) {
 966           Less => {
 967             let inserted = insert(&mut save.left, key, value);
 968             skew(save);
 969             split(save);
 970             inserted
 971           }
 972           Greater => {
 973             let inserted = insert(&mut save.right, key, value);
 974             skew(save);
 975             split(save);
 976             inserted
 977           }
 978           Equal => {
 979             save.key = key;
 980             Some(replace(&mut save.value, value))
 981           }
 982         }
 983       }
 984       None => {
 985        *node = Some(box TreeNode::new(key, value));
 986         None
 987       }
 988     }
 989 }
 990
 991 fn remove<K: Ord, V>(node: &mut Option<Box<TreeNode<K, V>>>,
 992                           key: &K) -> Option<V> {
 993     fn heir_swap<K: Ord, V>(node: &mut Box<TreeNode<K, V>>,
 994                                  child: &mut Option<Box<TreeNode<K, V>>>) {
 995         // *could* be done without recursion, but it won't borrow check
 996         for x in child.mut_iter() {
 997             if x.right.is_some() {
 998                 heir_swap(node, &mut x.right);
 999             } else {
1000                 swap(&mut node.key, &mut x.key);
1001                 swap(&mut node.value, &mut x.value);
1002             }
1003         }
1004     }
1005
1006     match *node {
1007       None => {
1008         return None; // bottom of tree
1009       }
1010       Some(ref mut save) => {
1011         let (ret, rebalance) = match key.cmp(&save.key) {
1012           Less => (remove(&mut save.left, key), true),
1013           Greater => (remove(&mut save.right, key), true),
1014           Equal => {
1015             if save.left.is_some() {
1016                 if save.right.is_some() {
1017                     let mut left = save.left.take_unwrap();
1018                     if left.right.is_some() {
1019                         heir_swap(save, &mut left.right);
1020                     } else {
1021                         swap(&mut save.key, &mut left.key);
1022                         swap(&mut save.value, &mut left.value);
1023                     }
1024                     save.left = Some(left);
1025                     (remove(&mut save.left, key), true)
1026                 } else {
1027                     let new = save.left.take_unwrap();
1028                     let box TreeNode{value, ..} = replace(save, new);
1029                     *save = save.left.take_unwrap();
1030                     (Some(value), true)
1031                 }
1032             } else if save.right.is_some() {
1033                 let new = save.right.take_unwrap();
1034                 let box TreeNode{value, ..} = replace(save, new);
1035                 (Some(value), true)
1036             } else {
1037                 (None, false)
1038             }
1039           }
1040         };
1041
1042         if rebalance {
1043             let left_level = save.left.as_ref().map_or(0, |x| x.level);
1044             let right_level = save.right.as_ref().map_or(0, |x| x.level);
1045
1046             // re-balance, if necessary
1047             if left_level < save.level - 1 || right_level < save.level - 1 {
1048                 save.level -= 1;
1049
1050                 if right_level > save.level {
1051                     for x in save.right.mut_iter() { x.level = save.level }
1052                 }
1053
1054                 skew(save);
1055
1056                 for right in save.right.mut_iter() {
1057                     skew(right);
1058                     for x in right.right.mut_iter() { skew(x) }
1059                 }
1060
1061                 split(save);
1062                 for x in save.right.mut_iter() { split(x) }
1063             }
1064
1065             return ret;
1066         }
1067       }
1068     }
1069     return match node.take() {
1070         Some(box TreeNode{value, ..}) => Some(value), None => fail!()
1071     };
1072 }
1073
1074 impl<K: Ord, V> FromIterator<(K, V)> for TreeMap<K, V> {
1075     fn from_iter<T: Iterator<(K, V)>>(iter: T) -> TreeMap<K, V> {
1076         let mut map = TreeMap::new();
1077         map.extend(iter);
1078         map
1079     }
1080 }
1081
1082 impl<K: Ord, V> Extendable<(K, V)> for TreeMap<K, V> {
1083     #[inline]
1084     fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1085         for (k, v) in iter {
1086             self.insert(k, v);
1087         }
1088     }
1089 }
1090
1091 impl<S: Writer, K: Ord + Hash<S>, V: Hash<S>> Hash<S> for TreeMap<K, V> {
1092     fn hash(&self, state: &mut S) {
1093         for elt in self.iter() {
1094             elt.hash(state);
1095         }
1096     }
1097 }
1098
1099 impl<T: Ord> FromIterator<T> for TreeSet<T> {
1100     fn from_iter<Iter: Iterator<T>>(iter: Iter) -> TreeSet<T> {
1101         let mut set = TreeSet::new();
1102         set.extend(iter);
1103         set
1104     }
1105 }
1106
1107 impl<T: Ord> Extendable<T> for TreeSet<T> {
1108     #[inline]
1109     fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) {
1110         for elem in iter {
1111             self.insert(elem);
1112         }
1113     }
1114 }
1115
1116 impl<S: Writer, T: Ord + Hash<S>> Hash<S> for TreeSet<T> {
1117     fn hash(&self, state: &mut S) {
1118         for elt in self.iter() {
1119             elt.hash(state);
1120         }
1121     }
1122 }
1123
1124 #[cfg(test)]
1125 mod test_treemap {
1126     use std::prelude::*;
1127     use std::rand::Rng;
1128     use std::rand;
1129
1130     use {Map, MutableMap, Mutable};
1131     use super::{TreeMap, TreeNode};
1132
1133     #[test]
1134     fn find_empty() {
1135         let m: TreeMap<int,int> = TreeMap::new();
1136         assert!(m.find(&5) == None);
1137     }
1138
1139     #[test]
1140     fn find_not_found() {
1141         let mut m = TreeMap::new();
1142         assert!(m.insert(1i, 2i));
1143         assert!(m.insert(5i, 3i));
1144         assert!(m.insert(9i, 3i));
1145         assert_eq!(m.find(&2), None);
1146     }
1147
1148     #[test]
1149     fn find_with_empty() {
1150         let m: TreeMap<&'static str,int> = TreeMap::new();
1151         assert!(m.find_with(|k| "test".cmp(k)) == None);
1152     }
1153
1154     #[test]
1155     fn find_with_not_found() {
1156         let mut m = TreeMap::new();
1157         assert!(m.insert("test1", 2i));
1158         assert!(m.insert("test2", 3i));
1159         assert!(m.insert("test3", 3i));
1160         assert_eq!(m.find_with(|k| "test4".cmp(k)), None);
1161     }
1162
1163     #[test]
1164     fn find_with_found() {
1165         let mut m = TreeMap::new();
1166         assert!(m.insert("test1", 2i));
1167         assert!(m.insert("test2", 3i));
1168         assert!(m.insert("test3", 4i));
1169         assert_eq!(m.find_with(|k| "test2".cmp(k)), Some(&3i));
1170     }
1171
1172     #[test]
1173     fn test_find_mut() {
1174         let mut m = TreeMap::new();
1175         assert!(m.insert(1i, 12i));
1176         assert!(m.insert(2, 8));
1177         assert!(m.insert(5, 14));
1178         let new = 100;
1179         match m.find_mut(&5) {
1180           None => fail!(), Some(x) => *x = new
1181         }
1182         assert_eq!(m.find(&5), Some(&new));
1183     }
1184
1185     #[test]
1186     fn test_find_with_mut() {
1187         let mut m = TreeMap::new();
1188         assert!(m.insert("t1", 12i));
1189         assert!(m.insert("t2", 8));
1190         assert!(m.insert("t5", 14));
1191         let new = 100;
1192         match m.find_mut_with(|k| "t5".cmp(k)) {
1193           None => fail!(), Some(x) => *x = new
1194         }
1195         assert_eq!(m.find_with(|k| "t5".cmp(k)), Some(&new));
1196     }
1197
1198     #[test]
1199     fn insert_replace() {
1200         let mut m = TreeMap::new();
1201         assert!(m.insert(5i, 2i));
1202         assert!(m.insert(2, 9));
1203         assert!(!m.insert(2, 11));
1204         assert_eq!(m.find(&2).unwrap(), &11);
1205     }
1206
1207     #[test]
1208     fn test_clear() {
1209         let mut m = TreeMap::new();
1210         m.clear();
1211         assert!(m.insert(5i, 11i));
1212         assert!(m.insert(12, -3));
1213         assert!(m.insert(19, 2));
1214         m.clear();
1215         assert!(m.find(&5).is_none());
1216         assert!(m.find(&12).is_none());
1217         assert!(m.find(&19).is_none());
1218         assert!(m.is_empty());
1219     }
1220
1221     #[test]
1222     fn u8_map() {
1223         let mut m = TreeMap::new();
1224
1225         let k1 = "foo".as_bytes();
1226         let k2 = "bar".as_bytes();
1227         let v1 = "baz".as_bytes();
1228         let v2 = "foobar".as_bytes();
1229
1230         m.insert(k1.clone(), v1.clone());
1231         m.insert(k2.clone(), v2.clone());
1232
1233         assert_eq!(m.find(&k2), Some(&v2));
1234         assert_eq!(m.find(&k1), Some(&v1));
1235     }
1236
1237     fn check_equal<K: PartialEq + Ord, V: PartialEq>(ctrl: &[(K, V)],
1238                                             map: &TreeMap<K, V>) {
1239         assert_eq!(ctrl.is_empty(), map.is_empty());
1240         for x in ctrl.iter() {
1241             let &(ref k, ref v) = x;
1242             assert!(map.find(k).unwrap() == v)
1243         }
1244         for (map_k, map_v) in map.iter() {
1245             let mut found = false;
1246             for x in ctrl.iter() {
1247                 let &(ref ctrl_k, ref ctrl_v) = x;
1248                 if *map_k == *ctrl_k {
1249                     assert!(*map_v == *ctrl_v);
1250                     found = true;
1251                     break;
1252                 }
1253             }
1254             assert!(found);
1255         }
1256     }
1257
1258     fn check_left<K: Ord, V>(node: &Option<Box<TreeNode<K, V>>>,
1259                                   parent: &Box<TreeNode<K, V>>) {
1260         match *node {
1261           Some(ref r) => {
1262             assert_eq!(r.key.cmp(&parent.key), Less);
1263             assert!(r.level == parent.level - 1); // left is black
1264             check_left(&r.left, r);
1265             check_right(&r.right, r, false);
1266           }
1267           None => assert!(parent.level == 1) // parent is leaf
1268         }
1269     }
1270
1271     fn check_right<K: Ord, V>(node: &Option<Box<TreeNode<K, V>>>,
1272                                    parent: &Box<TreeNode<K, V>>,
1273                                    parent_red: bool) {
1274         match *node {
1275           Some(ref r) => {
1276             assert_eq!(r.key.cmp(&parent.key), Greater);
1277             let red = r.level == parent.level;
1278             if parent_red { assert!(!red) } // no dual horizontal links
1279             // Right red or black
1280             assert!(red || r.level == parent.level - 1);
1281             check_left(&r.left, r);
1282             check_right(&r.right, r, red);
1283           }
1284           None => assert!(parent.level == 1) // parent is leaf
1285         }
1286     }
1287
1288     fn check_structure<K: Ord, V>(map: &TreeMap<K, V>) {
1289         match map.root {
1290           Some(ref r) => {
1291             check_left(&r.left, r);
1292             check_right(&r.right, r, false);
1293           }
1294           None => ()
1295         }
1296     }
1297
1298     #[test]
1299     fn test_rand_int() {
1300         let mut map: TreeMap<int,int> = TreeMap::new();
1301         let mut ctrl = vec![];
1302
1303         check_equal(ctrl.as_slice(), &map);
1304         assert!(map.find(&5).is_none());
1305
1306         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(&[42]);
1307
1308         for _ in range(0u, 3) {
1309             for _ in range(0u, 90) {
1310                 let k = rng.gen();
1311                 let v = rng.gen();
1312                 if !ctrl.iter().any(|x| x == &(k, v)) {
1313                     assert!(map.insert(k, v));
1314                     ctrl.push((k, v));
1315                     check_structure(&map);
1316                     check_equal(ctrl.as_slice(), &map);
1317                 }
1318             }
1319
1320             for _ in range(0u, 30) {
1321                 let r = rng.gen_range(0, ctrl.len());
1322                 let (key, _) = ctrl.remove(r).unwrap();
1323                 assert!(map.remove(&key));
1324                 check_structure(&map);
1325                 check_equal(ctrl.as_slice(), &map);
1326             }
1327         }
1328     }
1329
1330     #[test]
1331     fn test_len() {
1332         let mut m = TreeMap::new();
1333         assert!(m.insert(3i, 6i));
1334         assert_eq!(m.len(), 1);
1335         assert!(m.insert(0, 0));
1336         assert_eq!(m.len(), 2);
1337         assert!(m.insert(4, 8));
1338         assert_eq!(m.len(), 3);
1339         assert!(m.remove(&3));
1340         assert_eq!(m.len(), 2);
1341         assert!(!m.remove(&5));
1342         assert_eq!(m.len(), 2);
1343         assert!(m.insert(2, 4));
1344         assert_eq!(m.len(), 3);
1345         assert!(m.insert(1, 2));
1346         assert_eq!(m.len(), 4);
1347     }
1348
1349     #[test]
1350     fn test_iterator() {
1351         let mut m = TreeMap::new();
1352
1353         assert!(m.insert(3i, 6i));
1354         assert!(m.insert(0, 0));
1355         assert!(m.insert(4, 8));
1356         assert!(m.insert(2, 4));
1357         assert!(m.insert(1, 2));
1358
1359         let mut n = 0;
1360         for (k, v) in m.iter() {
1361             assert_eq!(*k, n);
1362             assert_eq!(*v, n * 2);
1363             n += 1;
1364         }
1365         assert_eq!(n, 5);
1366     }
1367
1368     #[test]
1369     fn test_interval_iteration() {
1370         let mut m = TreeMap::new();
1371         for i in range(1i, 100i) {
1372             assert!(m.insert(i * 2, i * 4));
1373         }
1374
1375         for i in range(1i, 198i) {
1376             let mut lb_it = m.lower_bound(&i);
1377             let (&k, &v) = lb_it.next().unwrap();
1378             let lb = i + i % 2;
1379             assert_eq!(lb, k);
1380             assert_eq!(lb * 2, v);
1381
1382             let mut ub_it = m.upper_bound(&i);
1383             let (&k, &v) = ub_it.next().unwrap();
1384             let ub = i + 2 - i % 2;
1385             assert_eq!(ub, k);
1386             assert_eq!(ub * 2, v);
1387         }
1388         let mut end_it = m.lower_bound(&199);
1389         assert_eq!(end_it.next(), None);
1390     }
1391
1392     #[test]
1393     fn test_rev_iter() {
1394         let mut m = TreeMap::new();
1395
1396         assert!(m.insert(3i, 6i));
1397         assert!(m.insert(0, 0));
1398         assert!(m.insert(4, 8));
1399         assert!(m.insert(2, 4));
1400         assert!(m.insert(1, 2));
1401
1402         let mut n = 4;
1403         for (k, v) in m.rev_iter() {
1404             assert_eq!(*k, n);
1405             assert_eq!(*v, n * 2);
1406             n -= 1;
1407         }
1408     }
1409
1410     #[test]
1411     fn test_mut_iter() {
1412         let mut m = TreeMap::new();
1413         for i in range(0u, 10) {
1414             assert!(m.insert(i, 100 * i));
1415         }
1416
1417         for (i, (&k, v)) in m.mut_iter().enumerate() {
1418             *v += k * 10 + i; // 000 + 00 + 0, 100 + 10 + 1, ...
1419         }
1420
1421         for (&k, &v) in m.iter() {
1422             assert_eq!(v, 111 * k);
1423         }
1424     }
1425     #[test]
1426     fn test_mut_rev_iter() {
1427         let mut m = TreeMap::new();
1428         for i in range(0u, 10) {
1429             assert!(m.insert(i, 100 * i));
1430         }
1431
1432         for (i, (&k, v)) in m.mut_rev_iter().enumerate() {
1433             *v += k * 10 + (9 - i); // 900 + 90 + (9 - 0), 800 + 80 + (9 - 1), ...
1434         }
1435
1436         for (&k, &v) in m.iter() {
1437             assert_eq!(v, 111 * k);
1438         }
1439     }
1440
1441     #[test]
1442     fn test_mut_interval_iter() {
1443         let mut m_lower = TreeMap::new();
1444         let mut m_upper = TreeMap::new();
1445         for i in range(1i, 100i) {
1446             assert!(m_lower.insert(i * 2, i * 4));
1447             assert!(m_upper.insert(i * 2, i * 4));
1448         }
1449
1450         for i in range(1i, 199) {
1451             let mut lb_it = m_lower.mut_lower_bound(&i);
1452             let (&k, v) = lb_it.next().unwrap();
1453             let lb = i + i % 2;
1454             assert_eq!(lb, k);
1455             *v -= k;
1456         }
1457         for i in range(0i, 198) {
1458             let mut ub_it = m_upper.mut_upper_bound(&i);
1459             let (&k, v) = ub_it.next().unwrap();
1460             let ub = i + 2 - i % 2;
1461             assert_eq!(ub, k);
1462             *v -= k;
1463         }
1464
1465         assert!(m_lower.mut_lower_bound(&199).next().is_none());
1466
1467         assert!(m_upper.mut_upper_bound(&198).next().is_none());
1468
1469         assert!(m_lower.iter().all(|(_, &x)| x == 0));
1470         assert!(m_upper.iter().all(|(_, &x)| x == 0));
1471     }
1472
1473     #[test]
1474     fn test_eq() {
1475         let mut a = TreeMap::new();
1476         let mut b = TreeMap::new();
1477
1478         assert!(a == b);
1479         assert!(a.insert(0i, 5i));
1480         assert!(a != b);
1481         assert!(b.insert(0, 4));
1482         assert!(a != b);
1483         assert!(a.insert(5, 19));
1484         assert!(a != b);
1485         assert!(!b.insert(0, 5));
1486         assert!(a != b);
1487         assert!(b.insert(5, 19));
1488         assert!(a == b);
1489     }
1490
1491     #[test]
1492     fn test_lt() {
1493         let mut a = TreeMap::new();
1494         let mut b = TreeMap::new();
1495
1496         assert!(!(a < b) && !(b < a));
1497         assert!(b.insert(0i, 5i));
1498         assert!(a < b);
1499         assert!(a.insert(0, 7));
1500         assert!(!(a < b) && b < a);
1501         assert!(b.insert(-2, 0));
1502         assert!(b < a);
1503         assert!(a.insert(-5, 2));
1504         assert!(a < b);
1505         assert!(a.insert(6, 2));
1506         assert!(a < b && !(b < a));
1507     }
1508
1509     #[test]
1510     fn test_ord() {
1511         let mut a = TreeMap::new();
1512         let mut b = TreeMap::new();
1513
1514         assert!(a <= b && a >= b);
1515         assert!(a.insert(1i, 1i));
1516         assert!(a > b && a >= b);
1517         assert!(b < a && b <= a);
1518         assert!(b.insert(2, 2));
1519         assert!(b > a && b >= a);
1520         assert!(a < b && a <= b);
1521     }
1522
1523     #[test]
1524     fn test_show() {
1525         let mut map: TreeMap<int, int> = TreeMap::new();
1526         let empty: TreeMap<int, int> = TreeMap::new();
1527
1528         map.insert(1, 2);
1529         map.insert(3, 4);
1530
1531         let map_str = format!("{}", map);
1532
1533         assert!(map_str == "{1: 2, 3: 4}".to_string());
1534         assert_eq!(format!("{}", empty), "{}".to_string());
1535     }
1536
1537     #[test]
1538     fn test_lazy_iterator() {
1539         let mut m = TreeMap::new();
1540         let (x1, y1) = (2i, 5i);
1541         let (x2, y2) = (9, 12);
1542         let (x3, y3) = (20, -3);
1543         let (x4, y4) = (29, 5);
1544         let (x5, y5) = (103, 3);
1545
1546         assert!(m.insert(x1, y1));
1547         assert!(m.insert(x2, y2));
1548         assert!(m.insert(x3, y3));
1549         assert!(m.insert(x4, y4));
1550         assert!(m.insert(x5, y5));
1551
1552         let m = m;
1553         let mut a = m.iter();
1554
1555         assert_eq!(a.next().unwrap(), (&x1, &y1));
1556         assert_eq!(a.next().unwrap(), (&x2, &y2));
1557         assert_eq!(a.next().unwrap(), (&x3, &y3));
1558         assert_eq!(a.next().unwrap(), (&x4, &y4));
1559         assert_eq!(a.next().unwrap(), (&x5, &y5));
1560
1561         assert!(a.next().is_none());
1562
1563         let mut b = m.iter();
1564
1565         let expected = [(&x1, &y1), (&x2, &y2), (&x3, &y3), (&x4, &y4),
1566                         (&x5, &y5)];
1567         let mut i = 0;
1568
1569         for x in b {
1570             assert_eq!(expected[i], x);
1571             i += 1;
1572
1573             if i == 2 {
1574                 break
1575             }
1576         }
1577
1578         for x in b {
1579             assert_eq!(expected[i], x);
1580             i += 1;
1581         }
1582     }
1583
1584     #[test]
1585     fn test_from_iter() {
1586         let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1587
1588         let map: TreeMap<int, int> = xs.iter().map(|&x| x).collect();
1589
1590         for &(k, v) in xs.iter() {
1591             assert_eq!(map.find(&k), Some(&v));
1592         }
1593     }
1594
1595 }
1596
1597 #[cfg(test)]
1598 mod bench {
1599     use test::Bencher;
1600
1601     use super::TreeMap;
1602     use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1603
1604     // Find seq
1605     #[bench]
1606     pub fn insert_rand_100(b: &mut Bencher) {
1607         let mut m : TreeMap<uint,uint> = TreeMap::new();
1608         insert_rand_n(100, &mut m, b);
1609     }
1610
1611     #[bench]
1612     pub fn insert_rand_10_000(b: &mut Bencher) {
1613         let mut m : TreeMap<uint,uint> = TreeMap::new();
1614         insert_rand_n(10_000, &mut m, b);
1615     }
1616
1617     // Insert seq
1618     #[bench]
1619     pub fn insert_seq_100(b: &mut Bencher) {
1620         let mut m : TreeMap<uint,uint> = TreeMap::new();
1621         insert_seq_n(100, &mut m, b);
1622     }
1623
1624     #[bench]
1625     pub fn insert_seq_10_000(b: &mut Bencher) {
1626         let mut m : TreeMap<uint,uint> = TreeMap::new();
1627         insert_seq_n(10_000, &mut m, b);
1628     }
1629
1630     // Find rand
1631     #[bench]
1632     pub fn find_rand_100(b: &mut Bencher) {
1633         let mut m : TreeMap<uint,uint> = TreeMap::new();
1634         find_rand_n(100, &mut m, b);
1635     }
1636
1637     #[bench]
1638     pub fn find_rand_10_000(b: &mut Bencher) {
1639         let mut m : TreeMap<uint,uint> = TreeMap::new();
1640         find_rand_n(10_000, &mut m, b);
1641     }
1642
1643     // Find seq
1644     #[bench]
1645     pub fn find_seq_100(b: &mut Bencher) {
1646         let mut m : TreeMap<uint,uint> = TreeMap::new();
1647         find_seq_n(100, &mut m, b);
1648     }
1649
1650     #[bench]
1651     pub fn find_seq_10_000(b: &mut Bencher) {
1652         let mut m : TreeMap<uint,uint> = TreeMap::new();
1653         find_seq_n(10_000, &mut m, b);
1654     }
1655 }
1656
1657 #[cfg(test)]
1658 mod test_set {
1659     use std::prelude::*;
1660     use std::hash;
1661
1662     use {Set, MutableSet, Mutable, MutableMap};
1663     use super::{TreeMap, TreeSet};
1664
1665     #[test]
1666     fn test_clear() {
1667         let mut s = TreeSet::new();
1668         s.clear();
1669         assert!(s.insert(5i));
1670         assert!(s.insert(12));
1671         assert!(s.insert(19));
1672         s.clear();
1673         assert!(!s.contains(&5));
1674         assert!(!s.contains(&12));
1675         assert!(!s.contains(&19));
1676         assert!(s.is_empty());
1677     }
1678
1679     #[test]
1680     fn test_disjoint() {
1681         let mut xs = TreeSet::new();
1682         let mut ys = TreeSet::new();
1683         assert!(xs.is_disjoint(&ys));
1684         assert!(ys.is_disjoint(&xs));
1685         assert!(xs.insert(5i));
1686         assert!(ys.insert(11i));
1687         assert!(xs.is_disjoint(&ys));
1688         assert!(ys.is_disjoint(&xs));
1689         assert!(xs.insert(7));
1690         assert!(xs.insert(19));
1691         assert!(xs.insert(4));
1692         assert!(ys.insert(2));
1693         assert!(ys.insert(-11));
1694         assert!(xs.is_disjoint(&ys));
1695         assert!(ys.is_disjoint(&xs));
1696         assert!(ys.insert(7));
1697         assert!(!xs.is_disjoint(&ys));
1698         assert!(!ys.is_disjoint(&xs));
1699     }
1700
1701     #[test]
1702     fn test_subset_and_superset() {
1703         let mut a = TreeSet::new();
1704         assert!(a.insert(0i));
1705         assert!(a.insert(5));
1706         assert!(a.insert(11));
1707         assert!(a.insert(7));
1708
1709         let mut b = TreeSet::new();
1710         assert!(b.insert(0i));
1711         assert!(b.insert(7));
1712         assert!(b.insert(19));
1713         assert!(b.insert(250));
1714         assert!(b.insert(11));
1715         assert!(b.insert(200));
1716
1717         assert!(!a.is_subset(&b));
1718         assert!(!a.is_superset(&b));
1719         assert!(!b.is_subset(&a));
1720         assert!(!b.is_superset(&a));
1721
1722         assert!(b.insert(5));
1723
1724         assert!(a.is_subset(&b));
1725         assert!(!a.is_superset(&b));
1726         assert!(!b.is_subset(&a));
1727         assert!(b.is_superset(&a));
1728     }
1729
1730     #[test]
1731     fn test_iterator() {
1732         let mut m = TreeSet::new();
1733
1734         assert!(m.insert(3i));
1735         assert!(m.insert(0));
1736         assert!(m.insert(4));
1737         assert!(m.insert(2));
1738         assert!(m.insert(1));
1739
1740         let mut n = 0;
1741         for x in m.iter() {
1742             assert_eq!(*x, n);
1743             n += 1
1744         }
1745     }
1746
1747     #[test]
1748     fn test_rev_iter() {
1749         let mut m = TreeSet::new();
1750
1751         assert!(m.insert(3i));
1752         assert!(m.insert(0));
1753         assert!(m.insert(4));
1754         assert!(m.insert(2));
1755         assert!(m.insert(1));
1756
1757         let mut n = 4;
1758         for x in m.rev_iter() {
1759             assert_eq!(*x, n);
1760             n -= 1;
1761         }
1762     }
1763
1764     #[test]
1765     fn test_move_iter() {
1766         let s: TreeSet<int> = range(0i, 5).collect();
1767
1768         let mut n = 0;
1769         for x in s.move_iter() {
1770             assert_eq!(x, n);
1771             n += 1;
1772         }
1773     }
1774
1775     #[test]
1776     fn test_move_iter_size_hint() {
1777         let s: TreeSet<int> = vec!(0i, 1).move_iter().collect();
1778
1779         let mut it = s.move_iter();
1780
1781         assert_eq!(it.size_hint(), (2, Some(2)));
1782         assert!(it.next() != None);
1783
1784         assert_eq!(it.size_hint(), (1, Some(1)));
1785         assert!(it.next() != None);
1786
1787         assert_eq!(it.size_hint(), (0, Some(0)));
1788         assert_eq!(it.next(), None);
1789     }
1790
1791     #[test]
1792     fn test_clone_eq() {
1793       let mut m = TreeSet::new();
1794
1795       m.insert(1i);
1796       m.insert(2);
1797
1798       assert!(m.clone() == m);
1799     }
1800
1801     #[test]
1802     fn test_hash() {
1803       let mut x = TreeSet::new();
1804       let mut y = TreeSet::new();
1805
1806       x.insert(1i);
1807       x.insert(2);
1808       x.insert(3);
1809
1810       y.insert(3i);
1811       y.insert(2);
1812       y.insert(1);
1813
1814       assert!(hash::hash(&x) == hash::hash(&y));
1815     }
1816
1817     fn check(a: &[int],
1818              b: &[int],
1819              expected: &[int],
1820              f: |&TreeSet<int>, &TreeSet<int>, f: |&int| -> bool| -> bool) {
1821         let mut set_a = TreeSet::new();
1822         let mut set_b = TreeSet::new();
1823
1824         for x in a.iter() { assert!(set_a.insert(*x)) }
1825         for y in b.iter() { assert!(set_b.insert(*y)) }
1826
1827         let mut i = 0;
1828         f(&set_a, &set_b, |x| {
1829             assert_eq!(*x, expected[i]);
1830             i += 1;
1831             true
1832         });
1833         assert_eq!(i, expected.len());
1834     }
1835
1836     #[test]
1837     fn test_intersection() {
1838         fn check_intersection(a: &[int], b: &[int], expected: &[int]) {
1839             check(a, b, expected, |x, y, f| x.intersection(y).all(f))
1840         }
1841
1842         check_intersection([], [], []);
1843         check_intersection([1, 2, 3], [], []);
1844         check_intersection([], [1, 2, 3], []);
1845         check_intersection([2], [1, 2, 3], [2]);
1846         check_intersection([1, 2, 3], [2], [2]);
1847         check_intersection([11, 1, 3, 77, 103, 5, -5],
1848                            [2, 11, 77, -9, -42, 5, 3],
1849                            [3, 5, 11, 77]);
1850     }
1851
1852     #[test]
1853     fn test_difference() {
1854         fn check_difference(a: &[int], b: &[int], expected: &[int]) {
1855             check(a, b, expected, |x, y, f| x.difference(y).all(f))
1856         }
1857
1858         check_difference([], [], []);
1859         check_difference([1, 12], [], [1, 12]);
1860         check_difference([], [1, 2, 3, 9], []);
1861         check_difference([1, 3, 5, 9, 11],
1862                          [3, 9],
1863                          [1, 5, 11]);
1864         check_difference([-5, 11, 22, 33, 40, 42],
1865                          [-12, -5, 14, 23, 34, 38, 39, 50],
1866                          [11, 22, 33, 40, 42]);
1867     }
1868
1869     #[test]
1870     fn test_symmetric_difference() {
1871         fn check_symmetric_difference(a: &[int], b: &[int],
1872                                       expected: &[int]) {
1873             check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
1874         }
1875
1876         check_symmetric_difference([], [], []);
1877         check_symmetric_difference([1, 2, 3], [2], [1, 3]);
1878         check_symmetric_difference([2], [1, 2, 3], [1, 3]);
1879         check_symmetric_difference([1, 3, 5, 9, 11],
1880                                    [-2, 3, 9, 14, 22],
1881                                    [-2, 1, 5, 11, 14, 22]);
1882     }
1883
1884     #[test]
1885     fn test_union() {
1886         fn check_union(a: &[int], b: &[int],
1887                                       expected: &[int]) {
1888             check(a, b, expected, |x, y, f| x.union(y).all(f))
1889         }
1890
1891         check_union([], [], []);
1892         check_union([1, 2, 3], [2], [1, 2, 3]);
1893         check_union([2], [1, 2, 3], [1, 2, 3]);
1894         check_union([1, 3, 5, 9, 11, 16, 19, 24],
1895                     [-2, 1, 5, 9, 13, 19],
1896                     [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
1897     }
1898
1899     #[test]
1900     fn test_zip() {
1901         let mut x = TreeSet::new();
1902         x.insert(5u);
1903         x.insert(12u);
1904         x.insert(11u);
1905
1906         let mut y = TreeSet::new();
1907         y.insert("foo");
1908         y.insert("bar");
1909
1910         let x = x;
1911         let y = y;
1912         let mut z = x.iter().zip(y.iter());
1913
1914         // FIXME: #5801: this needs a type hint to compile...
1915         let result: Option<(&uint, & &'static str)> = z.next();
1916         assert_eq!(result.unwrap(), (&5u, &("bar")));
1917
1918         let result: Option<(&uint, & &'static str)> = z.next();
1919         assert_eq!(result.unwrap(), (&11u, &("foo")));
1920
1921         let result: Option<(&uint, & &'static str)> = z.next();
1922         assert!(result.is_none());
1923     }
1924
1925     #[test]
1926     fn test_swap() {
1927         let mut m = TreeMap::new();
1928         assert_eq!(m.swap(1u, 2i), None);
1929         assert_eq!(m.swap(1u, 3i), Some(2));
1930         assert_eq!(m.swap(1u, 4i), Some(3));
1931     }
1932
1933     #[test]
1934     fn test_pop() {
1935         let mut m = TreeMap::new();
1936         m.insert(1u, 2i);
1937         assert_eq!(m.pop(&1), Some(2));
1938         assert_eq!(m.pop(&1), None);
1939     }
1940
1941     #[test]
1942     fn test_from_iter() {
1943         let xs = [1i, 2, 3, 4, 5, 6, 7, 8, 9];
1944
1945         let set: TreeSet<int> = xs.iter().map(|&x| x).collect();
1946
1947         for x in xs.iter() {
1948             assert!(set.contains(x));
1949         }
1950     }
1951
1952     #[test]
1953     fn test_show() {
1954         let mut set: TreeSet<int> = TreeSet::new();
1955         let empty: TreeSet<int> = TreeSet::new();
1956
1957         set.insert(1);
1958         set.insert(2);
1959
1960         let set_str = format!("{}", set);
1961
1962         assert!(set_str == "{1, 2}".to_string());
1963         assert_eq!(format!("{}", empty), "{}".to_string());
1964     }
1965 }