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