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