src/libcollections/vec_map.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A simple map based on a vector for small integer keys. Space requirements
  12 //! are O(highest integer key).
  13
  14 #![allow(missing_docs)]
  15
  16 use core::prelude::*;
  17
  18 use core::cmp::Ordering;
  19 use core::default::Default;
  20 use core::fmt;
  21 use core::hash::{Hash, Writer, Hasher};
  22 use core::iter::{Enumerate, FilterMap, Map, FromIterator};
  23 use core::iter;
  24 use core::mem::replace;
  25 use core::ops::{Index, IndexMut};
  26
  27 use {vec, slice};
  28 use vec::Vec;
  29
  30 // FIXME(conventions): capacity management???
  31
  32 /// A map optimized for small integer keys.
  33 ///
  34 /// # Examples
  35 ///
  36 /// ```
  37 /// use std::collections::VecMap;
  38 ///
  39 /// let mut months = VecMap::new();
  40 /// months.insert(1, "Jan");
  41 /// months.insert(2, "Feb");
  42 /// months.insert(3, "Mar");
  43 ///
  44 /// if !months.contains_key(&12) {
  45 ///     println!("The end is near!");
  46 /// }
  47 ///
  48 /// assert_eq!(months.get(&1), Some(&"Jan"));
  49 ///
  50 /// match months.get_mut(&3) {
  51 ///     Some(value) => *value = "Venus",
  52 ///     None => (),
  53 /// }
  54 ///
  55 /// assert_eq!(months.get(&3), Some(&"Venus"));
  56 ///
  57 /// // Print out all months
  58 /// for (key, value) in months.iter() {
  59 ///     println!("month {} is {}", key, value);
  60 /// }
  61 ///
  62 /// months.clear();
  63 /// assert!(months.is_empty());
  64 /// ```
  65 pub struct VecMap<V> {
  66     v: Vec<Option<V>>,
  67 }
  68
  69 #[stable]
  70 impl<V> Default for VecMap<V> {
  71     #[stable]
  72     #[inline]
  73     fn default() -> VecMap<V> { VecMap::new() }
  74 }
  75
  76 impl<V:Clone> Clone for VecMap<V> {
  77     #[inline]
  78     fn clone(&self) -> VecMap<V> {
  79         VecMap { v: self.v.clone() }
  80     }
  81
  82     #[inline]
  83     fn clone_from(&mut self, source: &VecMap<V>) {
  84         self.v.clone_from(&source.v);
  85     }
  86 }
  87
  88 impl<S: Writer + Hasher, V: Hash<S>> Hash<S> for VecMap<V> {
  89     fn hash(&self, state: &mut S) {
  90         // In order to not traverse the `VecMap` twice, count the elements
  91         // during iteration.
  92         let mut count: uint = 0;
  93         for elt in self.iter() {
  94             elt.hash(state);
  95             count += 1;
  96         }
  97         count.hash(state);
  98     }
  99 }
 100
 101 impl<V> VecMap<V> {
 102     /// Creates an empty `VecMap`.
 103     ///
 104     /// # Examples
 105     ///
 106     /// ```
 107     /// use std::collections::VecMap;
 108     /// let mut map: VecMap<&str> = VecMap::new();
 109     /// ```
 110     #[stable]
 111     pub fn new() -> VecMap<V> { VecMap { v: vec![] } }
 112
 113     /// Creates an empty `VecMap` with space for at least `capacity`
 114     /// elements before resizing.
 115     ///
 116     /// # Examples
 117     ///
 118     /// ```
 119     /// use std::collections::VecMap;
 120     /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
 121     /// ```
 122     #[stable]
 123     pub fn with_capacity(capacity: uint) -> VecMap<V> {
 124         VecMap { v: Vec::with_capacity(capacity) }
 125     }
 126
 127     /// Returns the number of elements the `VecMap` can hold without
 128     /// reallocating.
 129     ///
 130     /// # Examples
 131     ///
 132     /// ```
 133     /// use std::collections::VecMap;
 134     /// let map: VecMap<String> = VecMap::with_capacity(10);
 135     /// assert!(map.capacity() >= 10);
 136     /// ```
 137     #[inline]
 138     #[stable]
 139     pub fn capacity(&self) -> uint {
 140         self.v.capacity()
 141     }
 142
 143     /// Reserves capacity for the given `VecMap` to contain `len` distinct keys.
 144     /// In the case of `VecMap` this means reallocations will not occur as long
 145     /// as all inserted keys are less than `len`.
 146     ///
 147     /// The collection may reserve more space to avoid frequent reallocations.
 148     ///
 149     /// # Examples
 150     ///
 151     /// ```
 152     /// use std::collections::VecMap;
 153     /// let mut map: VecMap<&str> = VecMap::new();
 154     /// map.reserve_len(10);
 155     /// assert!(map.capacity() >= 10);
 156     /// ```
 157     #[stable]
 158     pub fn reserve_len(&mut self, len: uint) {
 159         let cur_len = self.v.len();
 160         if len >= cur_len {
 161             self.v.reserve(len - cur_len);
 162         }
 163     }
 164
 165     /// Reserves the minimum capacity for the given `VecMap` to contain `len` distinct keys.
 166     /// In the case of `VecMap` this means reallocations will not occur as long as all inserted
 167     /// keys are less than `len`.
 168     ///
 169     /// Note that the allocator may give the collection more space than it requests.
 170     /// Therefore capacity cannot be relied upon to be precisely minimal.  Prefer
 171     /// `reserve_len` if future insertions are expected.
 172     ///
 173     /// # Examples
 174     ///
 175     /// ```
 176     /// use std::collections::VecMap;
 177     /// let mut map: VecMap<&str> = VecMap::new();
 178     /// map.reserve_len_exact(10);
 179     /// assert!(map.capacity() >= 10);
 180     /// ```
 181     #[stable]
 182     pub fn reserve_len_exact(&mut self, len: uint) {
 183         let cur_len = self.v.len();
 184         if len >= cur_len {
 185             self.v.reserve_exact(len - cur_len);
 186         }
 187     }
 188
 189     /// Returns an iterator visiting all keys in ascending order by the keys.
 190     /// The iterator's element type is `uint`.
 191     #[stable]
 192     pub fn keys<'r>(&'r self) -> Keys<'r, V> {
 193         fn first<A, B>((a, _): (A, B)) -> A { a }
 194         let first: fn((uint, &'r V)) -> uint = first; // coerce to fn pointer
 195
 196         Keys { iter: self.iter().map(first) }
 197     }
 198
 199     /// Returns an iterator visiting all values in ascending order by the keys.
 200     /// The iterator's element type is `&'r V`.
 201     #[stable]
 202     pub fn values<'r>(&'r self) -> Values<'r, V> {
 203         fn second<A, B>((_, b): (A, B)) -> B { b }
 204         let second: fn((uint, &'r V)) -> &'r V = second; // coerce to fn pointer
 205
 206         Values { iter: self.iter().map(second) }
 207     }
 208
 209     /// Returns an iterator visiting all key-value pairs in ascending order by the keys.
 210     /// The iterator's element type is `(uint, &'r V)`.
 211     ///
 212     /// # Examples
 213     ///
 214     /// ```
 215     /// use std::collections::VecMap;
 216     ///
 217     /// let mut map = VecMap::new();
 218     /// map.insert(1, "a");
 219     /// map.insert(3, "c");
 220     /// map.insert(2, "b");
 221     ///
 222     /// // Print `1: a` then `2: b` then `3: c`
 223     /// for (key, value) in map.iter() {
 224     ///     println!("{}: {}", key, value);
 225     /// }
 226     /// ```
 227     #[stable]
 228     pub fn iter<'r>(&'r self) -> Iter<'r, V> {
 229         Iter {
 230             front: 0,
 231             back: self.v.len(),
 232             iter: self.v.iter()
 233         }
 234     }
 235
 236     /// Returns an iterator visiting all key-value pairs in ascending order by the keys,
 237     /// with mutable references to the values.
 238     /// The iterator's element type is `(uint, &'r mut V)`.
 239     ///
 240     /// # Examples
 241     ///
 242     /// ```
 243     /// use std::collections::VecMap;
 244     ///
 245     /// let mut map = VecMap::new();
 246     /// map.insert(1, "a");
 247     /// map.insert(2, "b");
 248     /// map.insert(3, "c");
 249     ///
 250     /// for (key, value) in map.iter_mut() {
 251     ///     *value = "x";
 252     /// }
 253     ///
 254     /// for (key, value) in map.iter() {
 255     ///     assert_eq!(value, &"x");
 256     /// }
 257     /// ```
 258     #[stable]
 259     pub fn iter_mut<'r>(&'r mut self) -> IterMut<'r, V> {
 260         IterMut {
 261             front: 0,
 262             back: self.v.len(),
 263             iter: self.v.iter_mut()
 264         }
 265     }
 266
 267     /// Returns an iterator visiting all key-value pairs in ascending order by
 268     /// the keys, consuming the original `VecMap`.
 269     /// The iterator's element type is `(uint, &'r V)`.
 270     ///
 271     /// # Examples
 272     ///
 273     /// ```
 274     /// use std::collections::VecMap;
 275     ///
 276     /// let mut map = VecMap::new();
 277     /// map.insert(1, "a");
 278     /// map.insert(3, "c");
 279     /// map.insert(2, "b");
 280     ///
 281     /// // Not possible with .iter()
 282     /// let vec: Vec<(uint, &str)> = map.into_iter().collect();
 283     ///
 284     /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
 285     /// ```
 286     #[stable]
 287     pub fn into_iter(self) -> IntoIter<V> {
 288         fn filter<A>((i, v): (uint, Option<A>)) -> Option<(uint, A)> {
 289             v.map(|v| (i, v))
 290         }
 291         let filter: fn((uint, Option<V>)) -> Option<(uint, V)> = filter; // coerce to fn ptr
 292
 293         IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) }
 294     }
 295
 296     /// Return the number of elements in the map.
 297     ///
 298     /// # Examples
 299     ///
 300     /// ```
 301     /// use std::collections::VecMap;
 302     ///
 303     /// let mut a = VecMap::new();
 304     /// assert_eq!(a.len(), 0);
 305     /// a.insert(1, "a");
 306     /// assert_eq!(a.len(), 1);
 307     /// ```
 308     #[stable]
 309     pub fn len(&self) -> uint {
 310         self.v.iter().filter(|elt| elt.is_some()).count()
 311     }
 312
 313     /// Return true if the map contains no elements.
 314     ///
 315     /// # Examples
 316     ///
 317     /// ```
 318     /// use std::collections::VecMap;
 319     ///
 320     /// let mut a = VecMap::new();
 321     /// assert!(a.is_empty());
 322     /// a.insert(1, "a");
 323     /// assert!(!a.is_empty());
 324     /// ```
 325     #[stable]
 326     pub fn is_empty(&self) -> bool {
 327         self.v.iter().all(|elt| elt.is_none())
 328     }
 329
 330     /// Clears the map, removing all key-value pairs.
 331     ///
 332     /// # Examples
 333     ///
 334     /// ```
 335     /// use std::collections::VecMap;
 336     ///
 337     /// let mut a = VecMap::new();
 338     /// a.insert(1, "a");
 339     /// a.clear();
 340     /// assert!(a.is_empty());
 341     /// ```
 342     #[stable]
 343     pub fn clear(&mut self) { self.v.clear() }
 344
 345     /// Returns a reference to the value corresponding to the key.
 346     ///
 347     /// # Examples
 348     ///
 349     /// ```
 350     /// use std::collections::VecMap;
 351     ///
 352     /// let mut map = VecMap::new();
 353     /// map.insert(1, "a");
 354     /// assert_eq!(map.get(&1), Some(&"a"));
 355     /// assert_eq!(map.get(&2), None);
 356     /// ```
 357     #[stable]
 358     pub fn get(&self, key: &uint) -> Option<&V> {
 359         if *key < self.v.len() {
 360             match self.v[*key] {
 361               Some(ref value) => Some(value),
 362               None => None
 363             }
 364         } else {
 365             None
 366         }
 367     }
 368
 369     /// Returns true if the map contains a value for the specified key.
 370     ///
 371     /// # Examples
 372     ///
 373     /// ```
 374     /// use std::collections::VecMap;
 375     ///
 376     /// let mut map = VecMap::new();
 377     /// map.insert(1, "a");
 378     /// assert_eq!(map.contains_key(&1), true);
 379     /// assert_eq!(map.contains_key(&2), false);
 380     /// ```
 381     #[inline]
 382     #[stable]
 383     pub fn contains_key(&self, key: &uint) -> bool {
 384         self.get(key).is_some()
 385     }
 386
 387     /// Returns a mutable reference to the value corresponding to the key.
 388     ///
 389     /// # Examples
 390     ///
 391     /// ```
 392     /// use std::collections::VecMap;
 393     ///
 394     /// let mut map = VecMap::new();
 395     /// map.insert(1, "a");
 396     /// match map.get_mut(&1) {
 397     ///     Some(x) => *x = "b",
 398     ///     None => (),
 399     /// }
 400     /// assert_eq!(map[1], "b");
 401     /// ```
 402     #[stable]
 403     pub fn get_mut(&mut self, key: &uint) -> Option<&mut V> {
 404         if *key < self.v.len() {
 405             match *(&mut self.v[*key]) {
 406               Some(ref mut value) => Some(value),
 407               None => None
 408             }
 409         } else {
 410             None
 411         }
 412     }
 413
 414     /// Inserts a key-value pair from the map. If the key already had a value
 415     /// present in the map, that value is returned. Otherwise, `None` is returned.
 416     ///
 417     /// # Examples
 418     ///
 419     /// ```
 420     /// use std::collections::VecMap;
 421     ///
 422     /// let mut map = VecMap::new();
 423     /// assert_eq!(map.insert(37, "a"), None);
 424     /// assert_eq!(map.is_empty(), false);
 425     ///
 426     /// map.insert(37, "b");
 427     /// assert_eq!(map.insert(37, "c"), Some("b"));
 428     /// assert_eq!(map[37], "c");
 429     /// ```
 430     #[stable]
 431     pub fn insert(&mut self, key: uint, value: V) -> Option<V> {
 432         let len = self.v.len();
 433         if len <= key {
 434             self.v.extend(range(0, key - len + 1).map(|_| None));
 435         }
 436         replace(&mut self.v[key], Some(value))
 437     }
 438
 439     /// Removes a key from the map, returning the value at the key if the key
 440     /// was previously in the map.
 441     ///
 442     /// # Examples
 443     ///
 444     /// ```
 445     /// use std::collections::VecMap;
 446     ///
 447     /// let mut map = VecMap::new();
 448     /// map.insert(1, "a");
 449     /// assert_eq!(map.remove(&1), Some("a"));
 450     /// assert_eq!(map.remove(&1), None);
 451     /// ```
 452     #[stable]
 453     pub fn remove(&mut self, key: &uint) -> Option<V> {
 454         if *key >= self.v.len() {
 455             return None;
 456         }
 457         let result = &mut self.v[*key];
 458         result.take()
 459     }
 460 }
 461
 462 #[stable]
 463 impl<V: PartialEq> PartialEq for VecMap<V> {
 464     fn eq(&self, other: &VecMap<V>) -> bool {
 465         iter::order::eq(self.iter(), other.iter())
 466     }
 467 }
 468
 469 #[stable]
 470 impl<V: Eq> Eq for VecMap<V> {}
 471
 472 #[stable]
 473 impl<V: PartialOrd> PartialOrd for VecMap<V> {
 474     #[inline]
 475     fn partial_cmp(&self, other: &VecMap<V>) -> Option<Ordering> {
 476         iter::order::partial_cmp(self.iter(), other.iter())
 477     }
 478 }
 479
 480 #[stable]
 481 impl<V: Ord> Ord for VecMap<V> {
 482     #[inline]
 483     fn cmp(&self, other: &VecMap<V>) -> Ordering {
 484         iter::order::cmp(self.iter(), other.iter())
 485     }
 486 }
 487
 488 #[stable]
 489 impl<V: fmt::Show> fmt::Show for VecMap<V> {
 490     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 491         try!(write!(f, "VecMap {{"));
 492
 493         for (i, (k, v)) in self.iter().enumerate() {
 494             if i != 0 { try!(write!(f, ", ")); }
 495             try!(write!(f, "{}: {:?}", k, *v));
 496         }
 497
 498         write!(f, "}}")
 499     }
 500 }
 501
 502 #[stable]
 503 impl<V> FromIterator<(uint, V)> for VecMap<V> {
 504     fn from_iter<Iter: Iterator<Item=(uint, V)>>(iter: Iter) -> VecMap<V> {
 505         let mut map = VecMap::new();
 506         map.extend(iter);
 507         map
 508     }
 509 }
 510
 511 #[stable]
 512 impl<V> Extend<(uint, V)> for VecMap<V> {
 513     fn extend<Iter: Iterator<Item=(uint, V)>>(&mut self, mut iter: Iter) {
 514         for (k, v) in iter {
 515             self.insert(k, v);
 516         }
 517     }
 518 }
 519
 520 impl<V> Index<uint> for VecMap<V> {
 521     type Output = V;
 522
 523     #[inline]
 524     fn index<'a>(&'a self, i: &uint) -> &'a V {
 525         self.get(i).expect("key not present")
 526     }
 527 }
 528
 529 #[stable]
 530 impl<V> IndexMut<uint> for VecMap<V> {
 531     type Output = V;
 532
 533     #[inline]
 534     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut V {
 535         self.get_mut(i).expect("key not present")
 536     }
 537 }
 538
 539 macro_rules! iterator {
 540     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 541         #[stable]
 542         impl<'a, V> Iterator for $name<'a, V> {
 543             type Item = $elem;
 544
 545             #[inline]
 546             fn next(&mut self) -> Option<$elem> {
 547                 while self.front < self.back {
 548                     match self.iter.next() {
 549                         Some(elem) => {
 550                             match elem$(. $getter ())+ {
 551                                 Some(x) => {
 552                                     let index = self.front;
 553                                     self.front += 1;
 554                                     return Some((index, x));
 555                                 },
 556                                 None => {},
 557                             }
 558                         }
 559                         _ => ()
 560                     }
 561                     self.front += 1;
 562                 }
 563                 None
 564             }
 565
 566             #[inline]
 567             fn size_hint(&self) -> (uint, Option<uint>) {
 568                 (0, Some(self.back - self.front))
 569             }
 570         }
 571     }
 572 }
 573
 574 macro_rules! double_ended_iterator {
 575     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 576         #[stable]
 577         impl<'a, V> DoubleEndedIterator for $name<'a, V> {
 578             #[inline]
 579             fn next_back(&mut self) -> Option<$elem> {
 580                 while self.front < self.back {
 581                     match self.iter.next_back() {
 582                         Some(elem) => {
 583                             match elem$(. $getter ())+ {
 584                                 Some(x) => {
 585                                     self.back -= 1;
 586                                     return Some((self.back, x));
 587                                 },
 588                                 None => {},
 589                             }
 590                         }
 591                         _ => ()
 592                     }
 593                     self.back -= 1;
 594                 }
 595                 None
 596             }
 597         }
 598     }
 599 }
 600
 601 /// An iterator over the key-value pairs of a map.
 602 #[stable]
 603 pub struct Iter<'a, V:'a> {
 604     front: uint,
 605     back: uint,
 606     iter: slice::Iter<'a, Option<V>>
 607 }
 608
 609 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 610 impl<'a, V> Clone for Iter<'a, V> {
 611     fn clone(&self) -> Iter<'a, V> {
 612         Iter {
 613             front: self.front,
 614             back: self.back,
 615             iter: self.iter.clone()
 616         }
 617     }
 618 }
 619
 620 iterator! { impl Iter -> (uint, &'a V), as_ref }
 621 double_ended_iterator! { impl Iter -> (uint, &'a V), as_ref }
 622
 623 /// An iterator over the key-value pairs of a map, with the
 624 /// values being mutable.
 625 #[stable]
 626 pub struct IterMut<'a, V:'a> {
 627     front: uint,
 628     back: uint,
 629     iter: slice::IterMut<'a, Option<V>>
 630 }
 631
 632 iterator! { impl IterMut -> (uint, &'a mut V), as_mut }
 633 double_ended_iterator! { impl IterMut -> (uint, &'a mut V), as_mut }
 634
 635 /// An iterator over the keys of a map.
 636 #[stable]
 637 pub struct Keys<'a, V: 'a> {
 638     iter: Map<(uint, &'a V), uint, Iter<'a, V>, fn((uint, &'a V)) -> uint>
 639 }
 640
 641 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 642 impl<'a, V> Clone for Keys<'a, V> {
 643     fn clone(&self) -> Keys<'a, V> {
 644         Keys {
 645             iter: self.iter.clone()
 646         }
 647     }
 648 }
 649
 650 /// An iterator over the values of a map.
 651 #[stable]
 652 pub struct Values<'a, V: 'a> {
 653     iter: Map<(uint, &'a V), &'a V, Iter<'a, V>, fn((uint, &'a V)) -> &'a V>
 654 }
 655
 656 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 657 impl<'a, V> Clone for Values<'a, V> {
 658     fn clone(&self) -> Values<'a, V> {
 659         Values {
 660             iter: self.iter.clone()
 661         }
 662     }
 663 }
 664
 665 /// A consuming iterator over the key-value pairs of a map.
 666 #[stable]
 667 pub struct IntoIter<V> {
 668     iter: FilterMap<
 669     (uint, Option<V>),
 670     (uint, V),
 671     Enumerate<vec::IntoIter<Option<V>>>,
 672     fn((uint, Option<V>)) -> Option<(uint, V)>>
 673 }
 674
 675 #[stable]
 676 impl<'a, V> Iterator for Keys<'a, V> {
 677     type Item = uint;
 678
 679     fn next(&mut self) -> Option<uint> { self.iter.next() }
 680     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 681 }
 682 #[stable]
 683 impl<'a, V> DoubleEndedIterator for Keys<'a, V> {
 684     fn next_back(&mut self) -> Option<uint> { self.iter.next_back() }
 685 }
 686
 687 #[stable]
 688 impl<'a, V> Iterator for Values<'a, V> {
 689     type Item = &'a V;
 690
 691     fn next(&mut self) -> Option<(&'a V)> { self.iter.next() }
 692     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 693 }
 694 #[stable]
 695 impl<'a, V> DoubleEndedIterator for Values<'a, V> {
 696     fn next_back(&mut self) -> Option<(&'a V)> { self.iter.next_back() }
 697 }
 698
 699 #[stable]
 700 impl<V> Iterator for IntoIter<V> {
 701     type Item = (uint, V);
 702
 703     fn next(&mut self) -> Option<(uint, V)> { self.iter.next() }
 704     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 705 }
 706 #[stable]
 707 impl<V> DoubleEndedIterator for IntoIter<V> {
 708     fn next_back(&mut self) -> Option<(uint, V)> { self.iter.next_back() }
 709 }
 710
 711 #[cfg(test)]
 712 mod test_map {
 713     use prelude::*;
 714     use core::hash::{hash, SipHasher};
 715
 716     use super::VecMap;
 717
 718     #[test]
 719     fn test_get_mut() {
 720         let mut m = VecMap::new();
 721         assert!(m.insert(1, 12i).is_none());
 722         assert!(m.insert(2, 8).is_none());
 723         assert!(m.insert(5, 14).is_none());
 724         let new = 100;
 725         match m.get_mut(&5) {
 726             None => panic!(), Some(x) => *x = new
 727         }
 728         assert_eq!(m.get(&5), Some(&new));
 729     }
 730
 731     #[test]
 732     fn test_len() {
 733         let mut map = VecMap::new();
 734         assert_eq!(map.len(), 0);
 735         assert!(map.is_empty());
 736         assert!(map.insert(5, 20i).is_none());
 737         assert_eq!(map.len(), 1);
 738         assert!(!map.is_empty());
 739         assert!(map.insert(11, 12).is_none());
 740         assert_eq!(map.len(), 2);
 741         assert!(!map.is_empty());
 742         assert!(map.insert(14, 22).is_none());
 743         assert_eq!(map.len(), 3);
 744         assert!(!map.is_empty());
 745     }
 746
 747     #[test]
 748     fn test_clear() {
 749         let mut map = VecMap::new();
 750         assert!(map.insert(5, 20i).is_none());
 751         assert!(map.insert(11, 12).is_none());
 752         assert!(map.insert(14, 22).is_none());
 753         map.clear();
 754         assert!(map.is_empty());
 755         assert!(map.get(&5).is_none());
 756         assert!(map.get(&11).is_none());
 757         assert!(map.get(&14).is_none());
 758     }
 759
 760     #[test]
 761     fn test_insert() {
 762         let mut m = VecMap::new();
 763         assert_eq!(m.insert(1, 2i), None);
 764         assert_eq!(m.insert(1, 3i), Some(2));
 765         assert_eq!(m.insert(1, 4i), Some(3));
 766     }
 767
 768     #[test]
 769     fn test_remove() {
 770         let mut m = VecMap::new();
 771         m.insert(1, 2i);
 772         assert_eq!(m.remove(&1), Some(2));
 773         assert_eq!(m.remove(&1), None);
 774     }
 775
 776     #[test]
 777     fn test_keys() {
 778         let mut map = VecMap::new();
 779         map.insert(1, 'a');
 780         map.insert(2, 'b');
 781         map.insert(3, 'c');
 782         let keys = map.keys().collect::<Vec<uint>>();
 783         assert_eq!(keys.len(), 3);
 784         assert!(keys.contains(&1));
 785         assert!(keys.contains(&2));
 786         assert!(keys.contains(&3));
 787     }
 788
 789     #[test]
 790     fn test_values() {
 791         let mut map = VecMap::new();
 792         map.insert(1, 'a');
 793         map.insert(2, 'b');
 794         map.insert(3, 'c');
 795         let values = map.values().map(|&v| v).collect::<Vec<char>>();
 796         assert_eq!(values.len(), 3);
 797         assert!(values.contains(&'a'));
 798         assert!(values.contains(&'b'));
 799         assert!(values.contains(&'c'));
 800     }
 801
 802     #[test]
 803     fn test_iterator() {
 804         let mut m = VecMap::new();
 805
 806         assert!(m.insert(0, 1i).is_none());
 807         assert!(m.insert(1, 2).is_none());
 808         assert!(m.insert(3, 5).is_none());
 809         assert!(m.insert(6, 10).is_none());
 810         assert!(m.insert(10, 11).is_none());
 811
 812         let mut it = m.iter();
 813         assert_eq!(it.size_hint(), (0, Some(11)));
 814         assert_eq!(it.next().unwrap(), (0, &1));
 815         assert_eq!(it.size_hint(), (0, Some(10)));
 816         assert_eq!(it.next().unwrap(), (1, &2));
 817         assert_eq!(it.size_hint(), (0, Some(9)));
 818         assert_eq!(it.next().unwrap(), (3, &5));
 819         assert_eq!(it.size_hint(), (0, Some(7)));
 820         assert_eq!(it.next().unwrap(), (6, &10));
 821         assert_eq!(it.size_hint(), (0, Some(4)));
 822         assert_eq!(it.next().unwrap(), (10, &11));
 823         assert_eq!(it.size_hint(), (0, Some(0)));
 824         assert!(it.next().is_none());
 825     }
 826
 827     #[test]
 828     fn test_iterator_size_hints() {
 829         let mut m = VecMap::new();
 830
 831         assert!(m.insert(0, 1i).is_none());
 832         assert!(m.insert(1, 2).is_none());
 833         assert!(m.insert(3, 5).is_none());
 834         assert!(m.insert(6, 10).is_none());
 835         assert!(m.insert(10, 11).is_none());
 836
 837         assert_eq!(m.iter().size_hint(), (0, Some(11)));
 838         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
 839         assert_eq!(m.iter_mut().size_hint(), (0, Some(11)));
 840         assert_eq!(m.iter_mut().rev().size_hint(), (0, Some(11)));
 841     }
 842
 843     #[test]
 844     fn test_mut_iterator() {
 845         let mut m = VecMap::new();
 846
 847         assert!(m.insert(0, 1i).is_none());
 848         assert!(m.insert(1, 2).is_none());
 849         assert!(m.insert(3, 5).is_none());
 850         assert!(m.insert(6, 10).is_none());
 851         assert!(m.insert(10, 11).is_none());
 852
 853         for (k, v) in m.iter_mut() {
 854             *v += k as int;
 855         }
 856
 857         let mut it = m.iter();
 858         assert_eq!(it.next().unwrap(), (0, &1));
 859         assert_eq!(it.next().unwrap(), (1, &3));
 860         assert_eq!(it.next().unwrap(), (3, &8));
 861         assert_eq!(it.next().unwrap(), (6, &16));
 862         assert_eq!(it.next().unwrap(), (10, &21));
 863         assert!(it.next().is_none());
 864     }
 865
 866     #[test]
 867     fn test_rev_iterator() {
 868         let mut m = VecMap::new();
 869
 870         assert!(m.insert(0, 1i).is_none());
 871         assert!(m.insert(1, 2).is_none());
 872         assert!(m.insert(3, 5).is_none());
 873         assert!(m.insert(6, 10).is_none());
 874         assert!(m.insert(10, 11).is_none());
 875
 876         let mut it = m.iter().rev();
 877         assert_eq!(it.next().unwrap(), (10, &11));
 878         assert_eq!(it.next().unwrap(), (6, &10));
 879         assert_eq!(it.next().unwrap(), (3, &5));
 880         assert_eq!(it.next().unwrap(), (1, &2));
 881         assert_eq!(it.next().unwrap(), (0, &1));
 882         assert!(it.next().is_none());
 883     }
 884
 885     #[test]
 886     fn test_mut_rev_iterator() {
 887         let mut m = VecMap::new();
 888
 889         assert!(m.insert(0, 1i).is_none());
 890         assert!(m.insert(1, 2).is_none());
 891         assert!(m.insert(3, 5).is_none());
 892         assert!(m.insert(6, 10).is_none());
 893         assert!(m.insert(10, 11).is_none());
 894
 895         for (k, v) in m.iter_mut().rev() {
 896             *v += k as int;
 897         }
 898
 899         let mut it = m.iter();
 900         assert_eq!(it.next().unwrap(), (0, &1));
 901         assert_eq!(it.next().unwrap(), (1, &3));
 902         assert_eq!(it.next().unwrap(), (3, &8));
 903         assert_eq!(it.next().unwrap(), (6, &16));
 904         assert_eq!(it.next().unwrap(), (10, &21));
 905         assert!(it.next().is_none());
 906     }
 907
 908     #[test]
 909     fn test_move_iter() {
 910         let mut m = VecMap::new();
 911         m.insert(1, box 2i);
 912         let mut called = false;
 913         for (k, v) in m.into_iter() {
 914             assert!(!called);
 915             called = true;
 916             assert_eq!(k, 1);
 917             assert_eq!(v, box 2i);
 918         }
 919         assert!(called);
 920         m.insert(2, box 1i);
 921     }
 922
 923     #[test]
 924     fn test_show() {
 925         let mut map = VecMap::new();
 926         let empty = VecMap::<int>::new();
 927
 928         map.insert(1, 2i);
 929         map.insert(3, 4i);
 930
 931         let map_str = format!("{:?}", map);
 932         assert!(map_str == "VecMap {1: 2i, 3: 4i}" || map_str == "{3: 4i, 1: 2i}");
 933         assert_eq!(format!("{:?}", empty), "VecMap {}");
 934     }
 935
 936     #[test]
 937     fn test_clone() {
 938         let mut a = VecMap::new();
 939
 940         a.insert(1, 'x');
 941         a.insert(4, 'y');
 942         a.insert(6, 'z');
 943
 944         assert!(a.clone() == a);
 945     }
 946
 947     #[test]
 948     fn test_eq() {
 949         let mut a = VecMap::new();
 950         let mut b = VecMap::new();
 951
 952         assert!(a == b);
 953         assert!(a.insert(0, 5i).is_none());
 954         assert!(a != b);
 955         assert!(b.insert(0, 4i).is_none());
 956         assert!(a != b);
 957         assert!(a.insert(5, 19).is_none());
 958         assert!(a != b);
 959         assert!(!b.insert(0, 5).is_none());
 960         assert!(a != b);
 961         assert!(b.insert(5, 19).is_none());
 962         assert!(a == b);
 963
 964         a = VecMap::new();
 965         b = VecMap::with_capacity(1);
 966         assert!(a == b);
 967     }
 968
 969     #[test]
 970     fn test_lt() {
 971         let mut a = VecMap::new();
 972         let mut b = VecMap::new();
 973
 974         assert!(!(a < b) && !(b < a));
 975         assert!(b.insert(2u, 5i).is_none());
 976         assert!(a < b);
 977         assert!(a.insert(2, 7).is_none());
 978         assert!(!(a < b) && b < a);
 979         assert!(b.insert(1, 0).is_none());
 980         assert!(b < a);
 981         assert!(a.insert(0, 6).is_none());
 982         assert!(a < b);
 983         assert!(a.insert(6, 2).is_none());
 984         assert!(a < b && !(b < a));
 985     }
 986
 987     #[test]
 988     fn test_ord() {
 989         let mut a = VecMap::new();
 990         let mut b = VecMap::new();
 991
 992         assert!(a <= b && a >= b);
 993         assert!(a.insert(1u, 1i).is_none());
 994         assert!(a > b && a >= b);
 995         assert!(b < a && b <= a);
 996         assert!(b.insert(2, 2).is_none());
 997         assert!(b > a && b >= a);
 998         assert!(a < b && a <= b);
 999     }
1000
1001     #[test]
1002     fn test_hash() {
1003         let mut x = VecMap::new();
1004         let mut y = VecMap::new();
1005
1006         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1007         x.insert(1, 'a');
1008         x.insert(2, 'b');
1009         x.insert(3, 'c');
1010
1011         y.insert(3, 'c');
1012         y.insert(2, 'b');
1013         y.insert(1, 'a');
1014
1015         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1016
1017         x.insert(1000, 'd');
1018         x.remove(&1000);
1019
1020         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1021     }
1022
1023     #[test]
1024     fn test_from_iter() {
1025         let xs: Vec<(uint, char)> = vec![(1u, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')];
1026
1027         let map: VecMap<char> = xs.iter().map(|&x| x).collect();
1028
1029         for &(k, v) in xs.iter() {
1030             assert_eq!(map.get(&k), Some(&v));
1031         }
1032     }
1033
1034     #[test]
1035     fn test_index() {
1036         let mut map: VecMap<int> = VecMap::new();
1037
1038         map.insert(1, 2);
1039         map.insert(2, 1);
1040         map.insert(3, 4);
1041
1042         assert_eq!(map[3], 4);
1043     }
1044
1045     #[test]
1046     #[should_fail]
1047     fn test_index_nonexistent() {
1048         let mut map: VecMap<int> = VecMap::new();
1049
1050         map.insert(1, 2);
1051         map.insert(2, 1);
1052         map.insert(3, 4);
1053
1054         map[4];
1055     }
1056 }
1057
1058 #[cfg(test)]
1059 mod bench {
1060     use test::Bencher;
1061     use super::VecMap;
1062     use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1063
1064     #[bench]
1065     pub fn insert_rand_100(b: &mut Bencher) {
1066         let mut m : VecMap<uint> = VecMap::new();
1067         insert_rand_n(100, &mut m, b,
1068                       |m, i| { m.insert(i, 1); },
1069                       |m, i| { m.remove(&i); });
1070     }
1071
1072     #[bench]
1073     pub fn insert_rand_10_000(b: &mut Bencher) {
1074         let mut m : VecMap<uint> = VecMap::new();
1075         insert_rand_n(10_000, &mut m, b,
1076                       |m, i| { m.insert(i, 1); },
1077                       |m, i| { m.remove(&i); });
1078     }
1079
1080     // Insert seq
1081     #[bench]
1082     pub fn insert_seq_100(b: &mut Bencher) {
1083         let mut m : VecMap<uint> = VecMap::new();
1084         insert_seq_n(100, &mut m, b,
1085                      |m, i| { m.insert(i, 1); },
1086                      |m, i| { m.remove(&i); });
1087     }
1088
1089     #[bench]
1090     pub fn insert_seq_10_000(b: &mut Bencher) {
1091         let mut m : VecMap<uint> = VecMap::new();
1092         insert_seq_n(10_000, &mut m, b,
1093                      |m, i| { m.insert(i, 1); },
1094                      |m, i| { m.remove(&i); });
1095     }
1096
1097     // Find rand
1098     #[bench]
1099     pub fn find_rand_100(b: &mut Bencher) {
1100         let mut m : VecMap<uint> = VecMap::new();
1101         find_rand_n(100, &mut m, b,
1102                     |m, i| { m.insert(i, 1); },
1103                     |m, i| { m.get(&i); });
1104     }
1105
1106     #[bench]
1107     pub fn find_rand_10_000(b: &mut Bencher) {
1108         let mut m : VecMap<uint> = VecMap::new();
1109         find_rand_n(10_000, &mut m, b,
1110                     |m, i| { m.insert(i, 1); },
1111                     |m, i| { m.get(&i); });
1112     }
1113
1114     // Find seq
1115     #[bench]
1116     pub fn find_seq_100(b: &mut Bencher) {
1117         let mut m : VecMap<uint> = VecMap::new();
1118         find_seq_n(100, &mut m, b,
1119                    |m, i| { m.insert(i, 1); },
1120                    |m, i| { m.get(&i); });
1121     }
1122
1123     #[bench]
1124     pub fn find_seq_10_000(b: &mut Bencher) {
1125         let mut m : VecMap<uint> = VecMap::new();
1126         find_seq_n(10_000, &mut m, b,
1127                    |m, i| { m.insert(i, 1); },
1128                    |m, i| { m.get(&i); });
1129     }
1130 }