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, IntoIterator};
  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(feature = "rust1", since = "1.0.0")]
  70 impl<V> Default for VecMap<V> {
  71     #[stable(feature = "rust1", since = "1.0.0")]
  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 {
  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(feature = "rust1", since = "1.0.0")]
 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(feature = "rust1", since = "1.0.0")]
 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(feature = "rust1", since = "1.0.0")]
 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(feature = "rust1", since = "1.0.0")]
 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(feature = "rust1", since = "1.0.0")]
 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 of the keys.
 190     /// The iterator's element type is `uint`.
 191     #[stable(feature = "rust1", since = "1.0.0")]
 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 of the keys.
 200     /// The iterator's element type is `&'r V`.
 201     #[stable(feature = "rust1", since = "1.0.0")]
 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 of 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(feature = "rust1", since = "1.0.0")]
 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 of 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(feature = "rust1", since = "1.0.0")]
 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 of
 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     /// let vec: Vec<(uint, &str)> = map.into_iter().collect();
 282     ///
 283     /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
 284     /// ```
 285     #[stable(feature = "rust1", since = "1.0.0")]
 286     pub fn into_iter(self) -> IntoIter<V> {
 287         fn filter<A>((i, v): (uint, Option<A>)) -> Option<(uint, A)> {
 288             v.map(|v| (i, v))
 289         }
 290         let filter: fn((uint, Option<V>)) -> Option<(uint, V)> = filter; // coerce to fn ptr
 291
 292         IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) }
 293     }
 294
 295     /// Returns an iterator visiting all key-value pairs in ascending order of
 296     /// the keys, emptying (but not consuming) the original `VecMap`.
 297     /// The iterator's element type is `(uint, &'r V)`. Keeps the allocated memory for reuse.
 298     ///
 299     /// # Examples
 300     ///
 301     /// ```
 302     /// use std::collections::VecMap;
 303     ///
 304     /// let mut map = VecMap::new();
 305     /// map.insert(1, "a");
 306     /// map.insert(3, "c");
 307     /// map.insert(2, "b");
 308     ///
 309     /// let vec: Vec<(uint, &str)> = map.drain().collect();
 310     ///
 311     /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
 312     /// ```
 313     #[unstable(feature = "collections",
 314                reason = "matches collection reform specification, waiting for dust to settle")]
 315     pub fn drain<'a>(&'a mut self) -> Drain<'a, V> {
 316         fn filter<A>((i, v): (uint, Option<A>)) -> Option<(uint, A)> {
 317             v.map(|v| (i, v))
 318         }
 319         let filter: fn((uint, Option<V>)) -> Option<(uint, V)> = filter; // coerce to fn ptr
 320
 321         Drain { iter: self.v.drain().enumerate().filter_map(filter) }
 322     }
 323
 324     /// Return the number of elements in the map.
 325     ///
 326     /// # Examples
 327     ///
 328     /// ```
 329     /// use std::collections::VecMap;
 330     ///
 331     /// let mut a = VecMap::new();
 332     /// assert_eq!(a.len(), 0);
 333     /// a.insert(1, "a");
 334     /// assert_eq!(a.len(), 1);
 335     /// ```
 336     #[stable(feature = "rust1", since = "1.0.0")]
 337     pub fn len(&self) -> uint {
 338         self.v.iter().filter(|elt| elt.is_some()).count()
 339     }
 340
 341     /// Return true if the map contains no elements.
 342     ///
 343     /// # Examples
 344     ///
 345     /// ```
 346     /// use std::collections::VecMap;
 347     ///
 348     /// let mut a = VecMap::new();
 349     /// assert!(a.is_empty());
 350     /// a.insert(1, "a");
 351     /// assert!(!a.is_empty());
 352     /// ```
 353     #[stable(feature = "rust1", since = "1.0.0")]
 354     pub fn is_empty(&self) -> bool {
 355         self.v.iter().all(|elt| elt.is_none())
 356     }
 357
 358     /// Clears the map, removing all key-value pairs.
 359     ///
 360     /// # Examples
 361     ///
 362     /// ```
 363     /// use std::collections::VecMap;
 364     ///
 365     /// let mut a = VecMap::new();
 366     /// a.insert(1, "a");
 367     /// a.clear();
 368     /// assert!(a.is_empty());
 369     /// ```
 370     #[stable(feature = "rust1", since = "1.0.0")]
 371     pub fn clear(&mut self) { self.v.clear() }
 372
 373     /// Returns a reference to the value corresponding to the key.
 374     ///
 375     /// # Examples
 376     ///
 377     /// ```
 378     /// use std::collections::VecMap;
 379     ///
 380     /// let mut map = VecMap::new();
 381     /// map.insert(1, "a");
 382     /// assert_eq!(map.get(&1), Some(&"a"));
 383     /// assert_eq!(map.get(&2), None);
 384     /// ```
 385     #[stable(feature = "rust1", since = "1.0.0")]
 386     pub fn get(&self, key: &uint) -> Option<&V> {
 387         if *key < self.v.len() {
 388             match self.v[*key] {
 389               Some(ref value) => Some(value),
 390               None => None
 391             }
 392         } else {
 393             None
 394         }
 395     }
 396
 397     /// Returns true if the map contains a value for the specified key.
 398     ///
 399     /// # Examples
 400     ///
 401     /// ```
 402     /// use std::collections::VecMap;
 403     ///
 404     /// let mut map = VecMap::new();
 405     /// map.insert(1, "a");
 406     /// assert_eq!(map.contains_key(&1), true);
 407     /// assert_eq!(map.contains_key(&2), false);
 408     /// ```
 409     #[inline]
 410     #[stable(feature = "rust1", since = "1.0.0")]
 411     pub fn contains_key(&self, key: &uint) -> bool {
 412         self.get(key).is_some()
 413     }
 414
 415     /// Returns a mutable reference to the value corresponding to the key.
 416     ///
 417     /// # Examples
 418     ///
 419     /// ```
 420     /// use std::collections::VecMap;
 421     ///
 422     /// let mut map = VecMap::new();
 423     /// map.insert(1, "a");
 424     /// match map.get_mut(&1) {
 425     ///     Some(x) => *x = "b",
 426     ///     None => (),
 427     /// }
 428     /// assert_eq!(map[1], "b");
 429     /// ```
 430     #[stable(feature = "rust1", since = "1.0.0")]
 431     pub fn get_mut(&mut self, key: &uint) -> Option<&mut V> {
 432         if *key < self.v.len() {
 433             match *(&mut self.v[*key]) {
 434               Some(ref mut value) => Some(value),
 435               None => None
 436             }
 437         } else {
 438             None
 439         }
 440     }
 441
 442     /// Inserts a key-value pair from the map. If the key already had a value
 443     /// present in the map, that value is returned. Otherwise, `None` is returned.
 444     ///
 445     /// # Examples
 446     ///
 447     /// ```
 448     /// use std::collections::VecMap;
 449     ///
 450     /// let mut map = VecMap::new();
 451     /// assert_eq!(map.insert(37, "a"), None);
 452     /// assert_eq!(map.is_empty(), false);
 453     ///
 454     /// map.insert(37, "b");
 455     /// assert_eq!(map.insert(37, "c"), Some("b"));
 456     /// assert_eq!(map[37], "c");
 457     /// ```
 458     #[stable(feature = "rust1", since = "1.0.0")]
 459     pub fn insert(&mut self, key: uint, value: V) -> Option<V> {
 460         let len = self.v.len();
 461         if len <= key {
 462             self.v.extend((0..key - len + 1).map(|_| None));
 463         }
 464         replace(&mut self.v[key], Some(value))
 465     }
 466
 467     /// Removes a key from the map, returning the value at the key if the key
 468     /// was previously in the map.
 469     ///
 470     /// # Examples
 471     ///
 472     /// ```
 473     /// use std::collections::VecMap;
 474     ///
 475     /// let mut map = VecMap::new();
 476     /// map.insert(1, "a");
 477     /// assert_eq!(map.remove(&1), Some("a"));
 478     /// assert_eq!(map.remove(&1), None);
 479     /// ```
 480     #[stable(feature = "rust1", since = "1.0.0")]
 481     pub fn remove(&mut self, key: &uint) -> Option<V> {
 482         if *key >= self.v.len() {
 483             return None;
 484         }
 485         let result = &mut self.v[*key];
 486         result.take()
 487     }
 488 }
 489
 490 #[stable(feature = "rust1", since = "1.0.0")]
 491 impl<V: PartialEq> PartialEq for VecMap<V> {
 492     fn eq(&self, other: &VecMap<V>) -> bool {
 493         iter::order::eq(self.iter(), other.iter())
 494     }
 495 }
 496
 497 #[stable(feature = "rust1", since = "1.0.0")]
 498 impl<V: Eq> Eq for VecMap<V> {}
 499
 500 #[stable(feature = "rust1", since = "1.0.0")]
 501 impl<V: PartialOrd> PartialOrd for VecMap<V> {
 502     #[inline]
 503     fn partial_cmp(&self, other: &VecMap<V>) -> Option<Ordering> {
 504         iter::order::partial_cmp(self.iter(), other.iter())
 505     }
 506 }
 507
 508 #[stable(feature = "rust1", since = "1.0.0")]
 509 impl<V: Ord> Ord for VecMap<V> {
 510     #[inline]
 511     fn cmp(&self, other: &VecMap<V>) -> Ordering {
 512         iter::order::cmp(self.iter(), other.iter())
 513     }
 514 }
 515
 516 #[stable(feature = "rust1", since = "1.0.0")]
 517 impl<V: fmt::Debug> fmt::Debug for VecMap<V> {
 518     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 519         try!(write!(f, "VecMap {{"));
 520
 521         for (i, (k, v)) in self.iter().enumerate() {
 522             if i != 0 { try!(write!(f, ", ")); }
 523             try!(write!(f, "{}: {:?}", k, *v));
 524         }
 525
 526         write!(f, "}}")
 527     }
 528 }
 529
 530 #[stable(feature = "rust1", since = "1.0.0")]
 531 impl<V> FromIterator<(uint, V)> for VecMap<V> {
 532     fn from_iter<Iter: Iterator<Item=(uint, V)>>(iter: Iter) -> VecMap<V> {
 533         let mut map = VecMap::new();
 534         map.extend(iter);
 535         map
 536     }
 537 }
 538
 539 impl<T> IntoIterator for VecMap<T> {
 540     type Iter = IntoIter<T>;
 541
 542     fn into_iter(self) -> IntoIter<T> {
 543         self.into_iter()
 544     }
 545 }
 546
 547 impl<'a, T> IntoIterator for &'a VecMap<T> {
 548     type Iter = Iter<'a, T>;
 549
 550     fn into_iter(self) -> Iter<'a, T> {
 551         self.iter()
 552     }
 553 }
 554
 555 impl<'a, T> IntoIterator for &'a mut VecMap<T> {
 556     type Iter = IterMut<'a, T>;
 557
 558     fn into_iter(mut self) -> IterMut<'a, T> {
 559         self.iter_mut()
 560     }
 561 }
 562
 563 #[stable(feature = "rust1", since = "1.0.0")]
 564 impl<V> Extend<(uint, V)> for VecMap<V> {
 565     fn extend<Iter: Iterator<Item=(uint, V)>>(&mut self, mut iter: Iter) {
 566         for (k, v) in iter {
 567             self.insert(k, v);
 568         }
 569     }
 570 }
 571
 572 impl<V> Index<uint> for VecMap<V> {
 573     type Output = V;
 574
 575     #[inline]
 576     fn index<'a>(&'a self, i: &uint) -> &'a V {
 577         self.get(i).expect("key not present")
 578     }
 579 }
 580
 581 #[stable(feature = "rust1", since = "1.0.0")]
 582 impl<V> IndexMut<uint> for VecMap<V> {
 583     type Output = V;
 584
 585     #[inline]
 586     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut V {
 587         self.get_mut(i).expect("key not present")
 588     }
 589 }
 590
 591 macro_rules! iterator {
 592     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 593         #[stable(feature = "rust1", since = "1.0.0")]
 594         impl<'a, V> Iterator for $name<'a, V> {
 595             type Item = $elem;
 596
 597             #[inline]
 598             fn next(&mut self) -> Option<$elem> {
 599                 while self.front < self.back {
 600                     match self.iter.next() {
 601                         Some(elem) => {
 602                             match elem$(. $getter ())+ {
 603                                 Some(x) => {
 604                                     let index = self.front;
 605                                     self.front += 1;
 606                                     return Some((index, x));
 607                                 },
 608                                 None => {},
 609                             }
 610                         }
 611                         _ => ()
 612                     }
 613                     self.front += 1;
 614                 }
 615                 None
 616             }
 617
 618             #[inline]
 619             fn size_hint(&self) -> (uint, Option<uint>) {
 620                 (0, Some(self.back - self.front))
 621             }
 622         }
 623     }
 624 }
 625
 626 macro_rules! double_ended_iterator {
 627     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 628         #[stable(feature = "rust1", since = "1.0.0")]
 629         impl<'a, V> DoubleEndedIterator for $name<'a, V> {
 630             #[inline]
 631             fn next_back(&mut self) -> Option<$elem> {
 632                 while self.front < self.back {
 633                     match self.iter.next_back() {
 634                         Some(elem) => {
 635                             match elem$(. $getter ())+ {
 636                                 Some(x) => {
 637                                     self.back -= 1;
 638                                     return Some((self.back, x));
 639                                 },
 640                                 None => {},
 641                             }
 642                         }
 643                         _ => ()
 644                     }
 645                     self.back -= 1;
 646                 }
 647                 None
 648             }
 649         }
 650     }
 651 }
 652
 653 /// An iterator over the key-value pairs of a map.
 654 #[stable(feature = "rust1", since = "1.0.0")]
 655 pub struct Iter<'a, V:'a> {
 656     front: uint,
 657     back: uint,
 658     iter: slice::Iter<'a, Option<V>>
 659 }
 660
 661 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 662 impl<'a, V> Clone for Iter<'a, V> {
 663     fn clone(&self) -> Iter<'a, V> {
 664         Iter {
 665             front: self.front,
 666             back: self.back,
 667             iter: self.iter.clone()
 668         }
 669     }
 670 }
 671
 672 iterator! { impl Iter -> (uint, &'a V), as_ref }
 673 double_ended_iterator! { impl Iter -> (uint, &'a V), as_ref }
 674
 675 /// An iterator over the key-value pairs of a map, with the
 676 /// values being mutable.
 677 #[stable(feature = "rust1", since = "1.0.0")]
 678 pub struct IterMut<'a, V:'a> {
 679     front: uint,
 680     back: uint,
 681     iter: slice::IterMut<'a, Option<V>>
 682 }
 683
 684 iterator! { impl IterMut -> (uint, &'a mut V), as_mut }
 685 double_ended_iterator! { impl IterMut -> (uint, &'a mut V), as_mut }
 686
 687 /// An iterator over the keys of a map.
 688 #[stable(feature = "rust1", since = "1.0.0")]
 689 pub struct Keys<'a, V: 'a> {
 690     iter: Map<(uint, &'a V), uint, Iter<'a, V>, fn((uint, &'a V)) -> uint>
 691 }
 692
 693 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 694 impl<'a, V> Clone for Keys<'a, V> {
 695     fn clone(&self) -> Keys<'a, V> {
 696         Keys {
 697             iter: self.iter.clone()
 698         }
 699     }
 700 }
 701
 702 /// An iterator over the values of a map.
 703 #[stable(feature = "rust1", since = "1.0.0")]
 704 pub struct Values<'a, V: 'a> {
 705     iter: Map<(uint, &'a V), &'a V, Iter<'a, V>, fn((uint, &'a V)) -> &'a V>
 706 }
 707
 708 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 709 impl<'a, V> Clone for Values<'a, V> {
 710     fn clone(&self) -> Values<'a, V> {
 711         Values {
 712             iter: self.iter.clone()
 713         }
 714     }
 715 }
 716
 717 /// A consuming iterator over the key-value pairs of a map.
 718 #[stable(feature = "rust1", since = "1.0.0")]
 719 pub struct IntoIter<V> {
 720     iter: FilterMap<
 721     (uint, Option<V>),
 722     (uint, V),
 723     Enumerate<vec::IntoIter<Option<V>>>,
 724     fn((uint, Option<V>)) -> Option<(uint, V)>>
 725 }
 726
 727 #[unstable(feature = "collections")]
 728 pub struct Drain<'a, V> {
 729     iter: FilterMap<
 730     (uint, Option<V>),
 731     (uint, V),
 732     Enumerate<vec::Drain<'a, Option<V>>>,
 733     fn((uint, Option<V>)) -> Option<(uint, V)>>
 734 }
 735
 736 #[unstable(feature = "collections")]
 737 impl<'a, V> Iterator for Drain<'a, V> {
 738     type Item = (uint, V);
 739
 740     fn next(&mut self) -> Option<(uint, V)> { self.iter.next() }
 741     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 742 }
 743
 744 #[unstable(feature = "collections")]
 745 impl<'a, V> DoubleEndedIterator for Drain<'a, V> {
 746     fn next_back(&mut self) -> Option<(uint, V)> { self.iter.next_back() }
 747 }
 748
 749 #[stable(feature = "rust1", since = "1.0.0")]
 750 impl<'a, V> Iterator for Keys<'a, V> {
 751     type Item = uint;
 752
 753     fn next(&mut self) -> Option<uint> { self.iter.next() }
 754     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 755 }
 756 #[stable(feature = "rust1", since = "1.0.0")]
 757 impl<'a, V> DoubleEndedIterator for Keys<'a, V> {
 758     fn next_back(&mut self) -> Option<uint> { self.iter.next_back() }
 759 }
 760
 761 #[stable(feature = "rust1", since = "1.0.0")]
 762 impl<'a, V> Iterator for Values<'a, V> {
 763     type Item = &'a V;
 764
 765     fn next(&mut self) -> Option<(&'a V)> { self.iter.next() }
 766     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 767 }
 768 #[stable(feature = "rust1", since = "1.0.0")]
 769 impl<'a, V> DoubleEndedIterator for Values<'a, V> {
 770     fn next_back(&mut self) -> Option<(&'a V)> { self.iter.next_back() }
 771 }
 772
 773 #[stable(feature = "rust1", since = "1.0.0")]
 774 impl<V> Iterator for IntoIter<V> {
 775     type Item = (uint, V);
 776
 777     fn next(&mut self) -> Option<(uint, V)> { self.iter.next() }
 778     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 779 }
 780 #[stable(feature = "rust1", since = "1.0.0")]
 781 impl<V> DoubleEndedIterator for IntoIter<V> {
 782     fn next_back(&mut self) -> Option<(uint, V)> { self.iter.next_back() }
 783 }
 784
 785 #[cfg(test)]
 786 mod test_map {
 787     use prelude::*;
 788     use core::hash::{hash, SipHasher};
 789
 790     use super::VecMap;
 791
 792     #[test]
 793     fn test_get_mut() {
 794         let mut m = VecMap::new();
 795         assert!(m.insert(1, 12).is_none());
 796         assert!(m.insert(2, 8).is_none());
 797         assert!(m.insert(5, 14).is_none());
 798         let new = 100;
 799         match m.get_mut(&5) {
 800             None => panic!(), Some(x) => *x = new
 801         }
 802         assert_eq!(m.get(&5), Some(&new));
 803     }
 804
 805     #[test]
 806     fn test_len() {
 807         let mut map = VecMap::new();
 808         assert_eq!(map.len(), 0);
 809         assert!(map.is_empty());
 810         assert!(map.insert(5, 20).is_none());
 811         assert_eq!(map.len(), 1);
 812         assert!(!map.is_empty());
 813         assert!(map.insert(11, 12).is_none());
 814         assert_eq!(map.len(), 2);
 815         assert!(!map.is_empty());
 816         assert!(map.insert(14, 22).is_none());
 817         assert_eq!(map.len(), 3);
 818         assert!(!map.is_empty());
 819     }
 820
 821     #[test]
 822     fn test_clear() {
 823         let mut map = VecMap::new();
 824         assert!(map.insert(5, 20).is_none());
 825         assert!(map.insert(11, 12).is_none());
 826         assert!(map.insert(14, 22).is_none());
 827         map.clear();
 828         assert!(map.is_empty());
 829         assert!(map.get(&5).is_none());
 830         assert!(map.get(&11).is_none());
 831         assert!(map.get(&14).is_none());
 832     }
 833
 834     #[test]
 835     fn test_insert() {
 836         let mut m = VecMap::new();
 837         assert_eq!(m.insert(1, 2), None);
 838         assert_eq!(m.insert(1, 3), Some(2));
 839         assert_eq!(m.insert(1, 4), Some(3));
 840     }
 841
 842     #[test]
 843     fn test_remove() {
 844         let mut m = VecMap::new();
 845         m.insert(1, 2);
 846         assert_eq!(m.remove(&1), Some(2));
 847         assert_eq!(m.remove(&1), None);
 848     }
 849
 850     #[test]
 851     fn test_keys() {
 852         let mut map = VecMap::new();
 853         map.insert(1, 'a');
 854         map.insert(2, 'b');
 855         map.insert(3, 'c');
 856         let keys = map.keys().collect::<Vec<uint>>();
 857         assert_eq!(keys.len(), 3);
 858         assert!(keys.contains(&1));
 859         assert!(keys.contains(&2));
 860         assert!(keys.contains(&3));
 861     }
 862
 863     #[test]
 864     fn test_values() {
 865         let mut map = VecMap::new();
 866         map.insert(1, 'a');
 867         map.insert(2, 'b');
 868         map.insert(3, 'c');
 869         let values = map.values().map(|&v| v).collect::<Vec<char>>();
 870         assert_eq!(values.len(), 3);
 871         assert!(values.contains(&'a'));
 872         assert!(values.contains(&'b'));
 873         assert!(values.contains(&'c'));
 874     }
 875
 876     #[test]
 877     fn test_iterator() {
 878         let mut m = VecMap::new();
 879
 880         assert!(m.insert(0, 1).is_none());
 881         assert!(m.insert(1, 2).is_none());
 882         assert!(m.insert(3, 5).is_none());
 883         assert!(m.insert(6, 10).is_none());
 884         assert!(m.insert(10, 11).is_none());
 885
 886         let mut it = m.iter();
 887         assert_eq!(it.size_hint(), (0, Some(11)));
 888         assert_eq!(it.next().unwrap(), (0, &1));
 889         assert_eq!(it.size_hint(), (0, Some(10)));
 890         assert_eq!(it.next().unwrap(), (1, &2));
 891         assert_eq!(it.size_hint(), (0, Some(9)));
 892         assert_eq!(it.next().unwrap(), (3, &5));
 893         assert_eq!(it.size_hint(), (0, Some(7)));
 894         assert_eq!(it.next().unwrap(), (6, &10));
 895         assert_eq!(it.size_hint(), (0, Some(4)));
 896         assert_eq!(it.next().unwrap(), (10, &11));
 897         assert_eq!(it.size_hint(), (0, Some(0)));
 898         assert!(it.next().is_none());
 899     }
 900
 901     #[test]
 902     fn test_iterator_size_hints() {
 903         let mut m = VecMap::new();
 904
 905         assert!(m.insert(0, 1).is_none());
 906         assert!(m.insert(1, 2).is_none());
 907         assert!(m.insert(3, 5).is_none());
 908         assert!(m.insert(6, 10).is_none());
 909         assert!(m.insert(10, 11).is_none());
 910
 911         assert_eq!(m.iter().size_hint(), (0, Some(11)));
 912         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
 913         assert_eq!(m.iter_mut().size_hint(), (0, Some(11)));
 914         assert_eq!(m.iter_mut().rev().size_hint(), (0, Some(11)));
 915     }
 916
 917     #[test]
 918     fn test_mut_iterator() {
 919         let mut m = VecMap::new();
 920
 921         assert!(m.insert(0, 1).is_none());
 922         assert!(m.insert(1, 2).is_none());
 923         assert!(m.insert(3, 5).is_none());
 924         assert!(m.insert(6, 10).is_none());
 925         assert!(m.insert(10, 11).is_none());
 926
 927         for (k, v) in &mut m {
 928             *v += k as int;
 929         }
 930
 931         let mut it = m.iter();
 932         assert_eq!(it.next().unwrap(), (0, &1));
 933         assert_eq!(it.next().unwrap(), (1, &3));
 934         assert_eq!(it.next().unwrap(), (3, &8));
 935         assert_eq!(it.next().unwrap(), (6, &16));
 936         assert_eq!(it.next().unwrap(), (10, &21));
 937         assert!(it.next().is_none());
 938     }
 939
 940     #[test]
 941     fn test_rev_iterator() {
 942         let mut m = VecMap::new();
 943
 944         assert!(m.insert(0, 1).is_none());
 945         assert!(m.insert(1, 2).is_none());
 946         assert!(m.insert(3, 5).is_none());
 947         assert!(m.insert(6, 10).is_none());
 948         assert!(m.insert(10, 11).is_none());
 949
 950         let mut it = m.iter().rev();
 951         assert_eq!(it.next().unwrap(), (10, &11));
 952         assert_eq!(it.next().unwrap(), (6, &10));
 953         assert_eq!(it.next().unwrap(), (3, &5));
 954         assert_eq!(it.next().unwrap(), (1, &2));
 955         assert_eq!(it.next().unwrap(), (0, &1));
 956         assert!(it.next().is_none());
 957     }
 958
 959     #[test]
 960     fn test_mut_rev_iterator() {
 961         let mut m = VecMap::new();
 962
 963         assert!(m.insert(0, 1).is_none());
 964         assert!(m.insert(1, 2).is_none());
 965         assert!(m.insert(3, 5).is_none());
 966         assert!(m.insert(6, 10).is_none());
 967         assert!(m.insert(10, 11).is_none());
 968
 969         for (k, v) in m.iter_mut().rev() {
 970             *v += k as int;
 971         }
 972
 973         let mut it = m.iter();
 974         assert_eq!(it.next().unwrap(), (0, &1));
 975         assert_eq!(it.next().unwrap(), (1, &3));
 976         assert_eq!(it.next().unwrap(), (3, &8));
 977         assert_eq!(it.next().unwrap(), (6, &16));
 978         assert_eq!(it.next().unwrap(), (10, &21));
 979         assert!(it.next().is_none());
 980     }
 981
 982     #[test]
 983     fn test_move_iter() {
 984         let mut m = VecMap::new();
 985         m.insert(1, box 2);
 986         let mut called = false;
 987         for (k, v) in m {
 988             assert!(!called);
 989             called = true;
 990             assert_eq!(k, 1);
 991             assert_eq!(v, box 2);
 992         }
 993         assert!(called);
 994     }
 995
 996     #[test]
 997     fn test_drain_iterator() {
 998         let mut map = VecMap::new();
 999         map.insert(1, "a");
1000         map.insert(3, "c");
1001         map.insert(2, "b");
1002
1003         let vec: Vec<(usize, &str)> = map.drain().collect();
1004
1005         assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
1006         assert_eq!(map.len(), 0);
1007     }
1008
1009     #[test]
1010     fn test_show() {
1011         let mut map = VecMap::new();
1012         let empty = VecMap::<int>::new();
1013
1014         map.insert(1, 2);
1015         map.insert(3, 4);
1016
1017         let map_str = format!("{:?}", map);
1018         assert!(map_str == "VecMap {1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
1019         assert_eq!(format!("{:?}", empty), "VecMap {}");
1020     }
1021
1022     #[test]
1023     fn test_clone() {
1024         let mut a = VecMap::new();
1025
1026         a.insert(1, 'x');
1027         a.insert(4, 'y');
1028         a.insert(6, 'z');
1029
1030         assert!(a.clone() == a);
1031     }
1032
1033     #[test]
1034     fn test_eq() {
1035         let mut a = VecMap::new();
1036         let mut b = VecMap::new();
1037
1038         assert!(a == b);
1039         assert!(a.insert(0, 5).is_none());
1040         assert!(a != b);
1041         assert!(b.insert(0, 4).is_none());
1042         assert!(a != b);
1043         assert!(a.insert(5, 19).is_none());
1044         assert!(a != b);
1045         assert!(!b.insert(0, 5).is_none());
1046         assert!(a != b);
1047         assert!(b.insert(5, 19).is_none());
1048         assert!(a == b);
1049
1050         a = VecMap::new();
1051         b = VecMap::with_capacity(1);
1052         assert!(a == b);
1053     }
1054
1055     #[test]
1056     fn test_lt() {
1057         let mut a = VecMap::new();
1058         let mut b = VecMap::new();
1059
1060         assert!(!(a < b) && !(b < a));
1061         assert!(b.insert(2u, 5).is_none());
1062         assert!(a < b);
1063         assert!(a.insert(2, 7).is_none());
1064         assert!(!(a < b) && b < a);
1065         assert!(b.insert(1, 0).is_none());
1066         assert!(b < a);
1067         assert!(a.insert(0, 6).is_none());
1068         assert!(a < b);
1069         assert!(a.insert(6, 2).is_none());
1070         assert!(a < b && !(b < a));
1071     }
1072
1073     #[test]
1074     fn test_ord() {
1075         let mut a = VecMap::new();
1076         let mut b = VecMap::new();
1077
1078         assert!(a <= b && a >= b);
1079         assert!(a.insert(1u, 1).is_none());
1080         assert!(a > b && a >= b);
1081         assert!(b < a && b <= a);
1082         assert!(b.insert(2, 2).is_none());
1083         assert!(b > a && b >= a);
1084         assert!(a < b && a <= b);
1085     }
1086
1087     #[test]
1088     fn test_hash() {
1089         let mut x = VecMap::new();
1090         let mut y = VecMap::new();
1091
1092         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1093         x.insert(1, 'a');
1094         x.insert(2, 'b');
1095         x.insert(3, 'c');
1096
1097         y.insert(3, 'c');
1098         y.insert(2, 'b');
1099         y.insert(1, 'a');
1100
1101         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1102
1103         x.insert(1000, 'd');
1104         x.remove(&1000);
1105
1106         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1107     }
1108
1109     #[test]
1110     fn test_from_iter() {
1111         let xs: Vec<(uint, char)> = vec![(1u, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')];
1112
1113         let map: VecMap<char> = xs.iter().map(|&x| x).collect();
1114
1115         for &(k, v) in &xs {
1116             assert_eq!(map.get(&k), Some(&v));
1117         }
1118     }
1119
1120     #[test]
1121     fn test_index() {
1122         let mut map: VecMap<int> = VecMap::new();
1123
1124         map.insert(1, 2);
1125         map.insert(2, 1);
1126         map.insert(3, 4);
1127
1128         assert_eq!(map[3], 4);
1129     }
1130
1131     #[test]
1132     #[should_fail]
1133     fn test_index_nonexistent() {
1134         let mut map: VecMap<int> = VecMap::new();
1135
1136         map.insert(1, 2);
1137         map.insert(2, 1);
1138         map.insert(3, 4);
1139
1140         map[4];
1141     }
1142 }
1143
1144 #[cfg(test)]
1145 mod bench {
1146     use test::Bencher;
1147     use super::VecMap;
1148     use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1149
1150     #[bench]
1151     pub fn insert_rand_100(b: &mut Bencher) {
1152         let mut m : VecMap<uint> = VecMap::new();
1153         insert_rand_n(100, &mut m, b,
1154                       |m, i| { m.insert(i, 1); },
1155                       |m, i| { m.remove(&i); });
1156     }
1157
1158     #[bench]
1159     pub fn insert_rand_10_000(b: &mut Bencher) {
1160         let mut m : VecMap<uint> = VecMap::new();
1161         insert_rand_n(10_000, &mut m, b,
1162                       |m, i| { m.insert(i, 1); },
1163                       |m, i| { m.remove(&i); });
1164     }
1165
1166     // Insert seq
1167     #[bench]
1168     pub fn insert_seq_100(b: &mut Bencher) {
1169         let mut m : VecMap<uint> = VecMap::new();
1170         insert_seq_n(100, &mut m, b,
1171                      |m, i| { m.insert(i, 1); },
1172                      |m, i| { m.remove(&i); });
1173     }
1174
1175     #[bench]
1176     pub fn insert_seq_10_000(b: &mut Bencher) {
1177         let mut m : VecMap<uint> = VecMap::new();
1178         insert_seq_n(10_000, &mut m, b,
1179                      |m, i| { m.insert(i, 1); },
1180                      |m, i| { m.remove(&i); });
1181     }
1182
1183     // Find rand
1184     #[bench]
1185     pub fn find_rand_100(b: &mut Bencher) {
1186         let mut m : VecMap<uint> = VecMap::new();
1187         find_rand_n(100, &mut m, b,
1188                     |m, i| { m.insert(i, 1); },
1189                     |m, i| { m.get(&i); });
1190     }
1191
1192     #[bench]
1193     pub fn find_rand_10_000(b: &mut Bencher) {
1194         let mut m : VecMap<uint> = VecMap::new();
1195         find_rand_n(10_000, &mut m, b,
1196                     |m, i| { m.insert(i, 1); },
1197                     |m, i| { m.get(&i); });
1198     }
1199
1200     // Find seq
1201     #[bench]
1202     pub fn find_seq_100(b: &mut Bencher) {
1203         let mut m : VecMap<uint> = VecMap::new();
1204         find_seq_n(100, &mut m, b,
1205                    |m, i| { m.insert(i, 1); },
1206                    |m, i| { m.get(&i); });
1207     }
1208
1209     #[bench]
1210     pub fn find_seq_10_000(b: &mut Bencher) {
1211         let mut m : VecMap<uint> = VecMap::new();
1212         find_seq_n(10_000, &mut m, b,
1213                    |m, i| { m.insert(i, 1); },
1214                    |m, i| { m.get(&i); });
1215     }
1216 }