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 self::Entry::*;
  17
  18 use core::prelude::*;
  19
  20 use core::cmp::{max, Ordering};
  21 use core::default::Default;
  22 use core::fmt;
  23 use core::hash::{Hash, Hasher};
  24 use core::iter::{Enumerate, FilterMap, Map, FromIterator, IntoIterator};
  25 use core::iter;
  26 use core::mem::{replace, swap};
  27 use core::ops::{Index, IndexMut};
  28
  29 use {vec, slice};
  30 use vec::Vec;
  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 /// A view into a single entry in a map, which may either be vacant or occupied.
  70 #[unstable(feature = "collections",
  71            reason = "precise API still under development")]
  72 pub enum Entry<'a, V:'a> {
  73     /// A vacant Entry
  74     Vacant(VacantEntry<'a, V>),
  75     /// An occupied Entry
  76     Occupied(OccupiedEntry<'a, V>),
  77 }
  78
  79 /// A vacant Entry.
  80 #[unstable(feature = "collections",
  81            reason = "precise API still under development")]
  82 pub struct VacantEntry<'a, V:'a> {
  83     map: &'a mut VecMap<V>,
  84     index: usize,
  85 }
  86
  87 /// An occupied Entry.
  88 #[unstable(feature = "collections",
  89            reason = "precise API still under development")]
  90 pub struct OccupiedEntry<'a, V:'a> {
  91     map: &'a mut VecMap<V>,
  92     index: usize,
  93 }
  94
  95 #[stable(feature = "rust1", since = "1.0.0")]
  96 impl<V> Default for VecMap<V> {
  97     #[stable(feature = "rust1", since = "1.0.0")]
  98     #[inline]
  99     fn default() -> VecMap<V> { VecMap::new() }
 100 }
 101
 102 #[stable(feature = "rust1", since = "1.0.0")]
 103 impl<V:Clone> Clone for VecMap<V> {
 104     #[inline]
 105     fn clone(&self) -> VecMap<V> {
 106         VecMap { v: self.v.clone() }
 107     }
 108
 109     #[inline]
 110     fn clone_from(&mut self, source: &VecMap<V>) {
 111         self.v.clone_from(&source.v);
 112     }
 113 }
 114
 115 #[stable(feature = "rust1", since = "1.0.0")]
 116 impl<V: Hash> Hash for VecMap<V> {
 117     fn hash<H: Hasher>(&self, state: &mut H) {
 118         // In order to not traverse the `VecMap` twice, count the elements
 119         // during iteration.
 120         let mut count: usize = 0;
 121         for elt in self {
 122             elt.hash(state);
 123             count += 1;
 124         }
 125         count.hash(state);
 126     }
 127 }
 128
 129 impl<V> VecMap<V> {
 130     /// Creates an empty `VecMap`.
 131     ///
 132     /// # Examples
 133     ///
 134     /// ```
 135     /// use std::collections::VecMap;
 136     /// let mut map: VecMap<&str> = VecMap::new();
 137     /// ```
 138     #[stable(feature = "rust1", since = "1.0.0")]
 139     pub fn new() -> VecMap<V> { VecMap { v: vec![] } }
 140
 141     /// Creates an empty `VecMap` with space for at least `capacity`
 142     /// elements before resizing.
 143     ///
 144     /// # Examples
 145     ///
 146     /// ```
 147     /// use std::collections::VecMap;
 148     /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
 149     /// ```
 150     #[stable(feature = "rust1", since = "1.0.0")]
 151     pub fn with_capacity(capacity: usize) -> VecMap<V> {
 152         VecMap { v: Vec::with_capacity(capacity) }
 153     }
 154
 155     /// Returns the number of elements the `VecMap` can hold without
 156     /// reallocating.
 157     ///
 158     /// # Examples
 159     ///
 160     /// ```
 161     /// use std::collections::VecMap;
 162     /// let map: VecMap<String> = VecMap::with_capacity(10);
 163     /// assert!(map.capacity() >= 10);
 164     /// ```
 165     #[inline]
 166     #[stable(feature = "rust1", since = "1.0.0")]
 167     pub fn capacity(&self) -> usize {
 168         self.v.capacity()
 169     }
 170
 171     /// Reserves capacity for the given `VecMap` to contain `len` distinct keys.
 172     /// In the case of `VecMap` this means reallocations will not occur as long
 173     /// as all inserted keys are less than `len`.
 174     ///
 175     /// The collection may reserve more space to avoid frequent reallocations.
 176     ///
 177     /// # Examples
 178     ///
 179     /// ```
 180     /// use std::collections::VecMap;
 181     /// let mut map: VecMap<&str> = VecMap::new();
 182     /// map.reserve_len(10);
 183     /// assert!(map.capacity() >= 10);
 184     /// ```
 185     #[stable(feature = "rust1", since = "1.0.0")]
 186     pub fn reserve_len(&mut self, len: usize) {
 187         let cur_len = self.v.len();
 188         if len >= cur_len {
 189             self.v.reserve(len - cur_len);
 190         }
 191     }
 192
 193     /// Reserves the minimum capacity for the given `VecMap` to contain `len` distinct keys.
 194     /// In the case of `VecMap` this means reallocations will not occur as long as all inserted
 195     /// keys are less than `len`.
 196     ///
 197     /// Note that the allocator may give the collection more space than it requests.
 198     /// Therefore capacity cannot be relied upon to be precisely minimal.  Prefer
 199     /// `reserve_len` if future insertions are expected.
 200     ///
 201     /// # Examples
 202     ///
 203     /// ```
 204     /// use std::collections::VecMap;
 205     /// let mut map: VecMap<&str> = VecMap::new();
 206     /// map.reserve_len_exact(10);
 207     /// assert!(map.capacity() >= 10);
 208     /// ```
 209     #[stable(feature = "rust1", since = "1.0.0")]
 210     pub fn reserve_len_exact(&mut self, len: usize) {
 211         let cur_len = self.v.len();
 212         if len >= cur_len {
 213             self.v.reserve_exact(len - cur_len);
 214         }
 215     }
 216
 217     /// Returns an iterator visiting all keys in ascending order of the keys.
 218     /// The iterator's element type is `usize`.
 219     #[stable(feature = "rust1", since = "1.0.0")]
 220     pub fn keys<'r>(&'r self) -> Keys<'r, V> {
 221         fn first<A, B>((a, _): (A, B)) -> A { a }
 222         let first: fn((usize, &'r V)) -> usize = first; // coerce to fn pointer
 223
 224         Keys { iter: self.iter().map(first) }
 225     }
 226
 227     /// Returns an iterator visiting all values in ascending order of the keys.
 228     /// The iterator's element type is `&'r V`.
 229     #[stable(feature = "rust1", since = "1.0.0")]
 230     pub fn values<'r>(&'r self) -> Values<'r, V> {
 231         fn second<A, B>((_, b): (A, B)) -> B { b }
 232         let second: fn((usize, &'r V)) -> &'r V = second; // coerce to fn pointer
 233
 234         Values { iter: self.iter().map(second) }
 235     }
 236
 237     /// Returns an iterator visiting all key-value pairs in ascending order of the keys.
 238     /// The iterator's element type is `(usize, &'r 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(3, "c");
 248     /// map.insert(2, "b");
 249     ///
 250     /// // Print `1: a` then `2: b` then `3: c`
 251     /// for (key, value) in map.iter() {
 252     ///     println!("{}: {}", key, value);
 253     /// }
 254     /// ```
 255     #[stable(feature = "rust1", since = "1.0.0")]
 256     pub fn iter<'r>(&'r self) -> Iter<'r, V> {
 257         Iter {
 258             front: 0,
 259             back: self.v.len(),
 260             iter: self.v.iter()
 261         }
 262     }
 263
 264     /// Returns an iterator visiting all key-value pairs in ascending order of the keys,
 265     /// with mutable references to the values.
 266     /// The iterator's element type is `(usize, &'r mut V)`.
 267     ///
 268     /// # Examples
 269     ///
 270     /// ```
 271     /// use std::collections::VecMap;
 272     ///
 273     /// let mut map = VecMap::new();
 274     /// map.insert(1, "a");
 275     /// map.insert(2, "b");
 276     /// map.insert(3, "c");
 277     ///
 278     /// for (key, value) in map.iter_mut() {
 279     ///     *value = "x";
 280     /// }
 281     ///
 282     /// for (key, value) in map.iter() {
 283     ///     assert_eq!(value, &"x");
 284     /// }
 285     /// ```
 286     #[stable(feature = "rust1", since = "1.0.0")]
 287     pub fn iter_mut<'r>(&'r mut self) -> IterMut<'r, V> {
 288         IterMut {
 289             front: 0,
 290             back: self.v.len(),
 291             iter: self.v.iter_mut()
 292         }
 293     }
 294
 295     /// Returns an iterator visiting all key-value pairs in ascending order of
 296     /// the keys, consuming the original `VecMap`.
 297     /// The iterator's element type is `(usize, &'r V)`.
 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<(usize, &str)> = map.into_iter().collect();
 310     ///
 311     /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
 312     /// ```
 313     #[stable(feature = "rust1", since = "1.0.0")]
 314     pub fn into_iter(self) -> IntoIter<V> {
 315         fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
 316             v.map(|v| (i, v))
 317         }
 318         let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
 319
 320         IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) }
 321     }
 322
 323     /// Moves all elements from `other` into the map while overwriting existing keys.
 324     ///
 325     /// # Examples
 326     ///
 327     /// ```
 328     /// use std::collections::VecMap;
 329     ///
 330     /// let mut a = VecMap::new();
 331     /// a.insert(1, "a");
 332     /// a.insert(2, "b");
 333     ///
 334     /// let mut b = VecMap::new();
 335     /// b.insert(3, "c");
 336     /// b.insert(4, "d");
 337     ///
 338     /// a.append(&mut b);
 339     ///
 340     /// assert_eq!(a.len(), 4);
 341     /// assert_eq!(b.len(), 0);
 342     /// assert_eq!(a[1], "a");
 343     /// assert_eq!(a[2], "b");
 344     /// assert_eq!(a[3], "c");
 345     /// assert_eq!(a[4], "d");
 346     /// ```
 347     #[unstable(feature = "collections",
 348                reason = "recently added as part of collections reform 2")]
 349     pub fn append(&mut self, other: &mut Self) {
 350         self.extend(other.drain());
 351     }
 352
 353     /// Splits the collection into two at the given key.
 354     ///
 355     /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
 356     /// and the returned `Self` contains elements `[at, max_key)`.
 357     ///
 358     /// Note that the capacity of `self` does not change.
 359     ///
 360     /// # Examples
 361     ///
 362     /// ```
 363     /// use std::collections::VecMap;
 364     ///
 365     /// let mut a = VecMap::new();
 366     /// a.insert(1, "a");
 367     /// a.insert(2, "b");
 368     /// a.insert(3, "c");
 369     /// a.insert(4, "d");
 370     ///
 371     /// let b = a.split_off(3);
 372     ///
 373     /// assert_eq!(a[1], "a");
 374     /// assert_eq!(a[2], "b");
 375     ///
 376     /// assert_eq!(b[3], "c");
 377     /// assert_eq!(b[4], "d");
 378     /// ```
 379     #[unstable(feature = "collections",
 380                reason = "recently added as part of collections reform 2")]
 381     pub fn split_off(&mut self, at: usize) -> Self {
 382         let mut other = VecMap::new();
 383
 384         if at == 0 {
 385             // Move all elements to other
 386             swap(self, &mut other);
 387             return other
 388         } else if at > self.v.len() {
 389             // No elements to copy
 390             return other;
 391         }
 392
 393         // Look up the index of the first non-None item
 394         let first_index = self.v.iter().position(|el| el.is_some());
 395         let start_index = match first_index {
 396             Some(index) => max(at, index),
 397             None => {
 398                 // self has no elements
 399                 return other;
 400             }
 401         };
 402
 403         // Fill the new VecMap with `None`s until `start_index`
 404         other.v.extend((0..start_index).map(|_| None));
 405
 406         // Move elements beginning with `start_index` from `self` into `other`
 407         other.v.extend(self.v[start_index..].iter_mut().map(|el| el.take()));
 408
 409         other
 410     }
 411
 412     /// Returns an iterator visiting all key-value pairs in ascending order of
 413     /// the keys, emptying (but not consuming) the original `VecMap`.
 414     /// The iterator's element type is `(usize, &'r V)`. Keeps the allocated memory for reuse.
 415     ///
 416     /// # Examples
 417     ///
 418     /// ```
 419     /// use std::collections::VecMap;
 420     ///
 421     /// let mut map = VecMap::new();
 422     /// map.insert(1, "a");
 423     /// map.insert(3, "c");
 424     /// map.insert(2, "b");
 425     ///
 426     /// let vec: Vec<(usize, &str)> = map.drain().collect();
 427     ///
 428     /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
 429     /// ```
 430     #[unstable(feature = "collections",
 431                reason = "matches collection reform specification, waiting for dust to settle")]
 432     pub fn drain<'a>(&'a mut self) -> Drain<'a, V> {
 433         fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
 434             v.map(|v| (i, v))
 435         }
 436         let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
 437
 438         Drain { iter: self.v.drain().enumerate().filter_map(filter) }
 439     }
 440
 441     /// Return the number of elements in the map.
 442     ///
 443     /// # Examples
 444     ///
 445     /// ```
 446     /// use std::collections::VecMap;
 447     ///
 448     /// let mut a = VecMap::new();
 449     /// assert_eq!(a.len(), 0);
 450     /// a.insert(1, "a");
 451     /// assert_eq!(a.len(), 1);
 452     /// ```
 453     #[stable(feature = "rust1", since = "1.0.0")]
 454     pub fn len(&self) -> usize {
 455         self.v.iter().filter(|elt| elt.is_some()).count()
 456     }
 457
 458     /// Return true if the map contains no elements.
 459     ///
 460     /// # Examples
 461     ///
 462     /// ```
 463     /// use std::collections::VecMap;
 464     ///
 465     /// let mut a = VecMap::new();
 466     /// assert!(a.is_empty());
 467     /// a.insert(1, "a");
 468     /// assert!(!a.is_empty());
 469     /// ```
 470     #[stable(feature = "rust1", since = "1.0.0")]
 471     pub fn is_empty(&self) -> bool {
 472         self.v.iter().all(|elt| elt.is_none())
 473     }
 474
 475     /// Clears the map, removing all key-value pairs.
 476     ///
 477     /// # Examples
 478     ///
 479     /// ```
 480     /// use std::collections::VecMap;
 481     ///
 482     /// let mut a = VecMap::new();
 483     /// a.insert(1, "a");
 484     /// a.clear();
 485     /// assert!(a.is_empty());
 486     /// ```
 487     #[stable(feature = "rust1", since = "1.0.0")]
 488     pub fn clear(&mut self) { self.v.clear() }
 489
 490     /// Returns a reference to the value corresponding to the key.
 491     ///
 492     /// # Examples
 493     ///
 494     /// ```
 495     /// use std::collections::VecMap;
 496     ///
 497     /// let mut map = VecMap::new();
 498     /// map.insert(1, "a");
 499     /// assert_eq!(map.get(&1), Some(&"a"));
 500     /// assert_eq!(map.get(&2), None);
 501     /// ```
 502     #[stable(feature = "rust1", since = "1.0.0")]
 503     pub fn get(&self, key: &usize) -> Option<&V> {
 504         if *key < self.v.len() {
 505             match self.v[*key] {
 506               Some(ref value) => Some(value),
 507               None => None
 508             }
 509         } else {
 510             None
 511         }
 512     }
 513
 514     /// Returns true if the map contains a value for the specified key.
 515     ///
 516     /// # Examples
 517     ///
 518     /// ```
 519     /// use std::collections::VecMap;
 520     ///
 521     /// let mut map = VecMap::new();
 522     /// map.insert(1, "a");
 523     /// assert_eq!(map.contains_key(&1), true);
 524     /// assert_eq!(map.contains_key(&2), false);
 525     /// ```
 526     #[inline]
 527     #[stable(feature = "rust1", since = "1.0.0")]
 528     pub fn contains_key(&self, key: &usize) -> bool {
 529         self.get(key).is_some()
 530     }
 531
 532     /// Returns a mutable reference to the value corresponding to the key.
 533     ///
 534     /// # Examples
 535     ///
 536     /// ```
 537     /// use std::collections::VecMap;
 538     ///
 539     /// let mut map = VecMap::new();
 540     /// map.insert(1, "a");
 541     /// match map.get_mut(&1) {
 542     ///     Some(x) => *x = "b",
 543     ///     None => (),
 544     /// }
 545     /// assert_eq!(map[1], "b");
 546     /// ```
 547     #[stable(feature = "rust1", since = "1.0.0")]
 548     pub fn get_mut(&mut self, key: &usize) -> Option<&mut V> {
 549         if *key < self.v.len() {
 550             match *(&mut self.v[*key]) {
 551               Some(ref mut value) => Some(value),
 552               None => None
 553             }
 554         } else {
 555             None
 556         }
 557     }
 558
 559     /// Inserts a key-value pair from the map. If the key already had a value
 560     /// present in the map, that value is returned. Otherwise, `None` is returned.
 561     ///
 562     /// # Examples
 563     ///
 564     /// ```
 565     /// use std::collections::VecMap;
 566     ///
 567     /// let mut map = VecMap::new();
 568     /// assert_eq!(map.insert(37, "a"), None);
 569     /// assert_eq!(map.is_empty(), false);
 570     ///
 571     /// map.insert(37, "b");
 572     /// assert_eq!(map.insert(37, "c"), Some("b"));
 573     /// assert_eq!(map[37], "c");
 574     /// ```
 575     #[stable(feature = "rust1", since = "1.0.0")]
 576     pub fn insert(&mut self, key: usize, value: V) -> Option<V> {
 577         let len = self.v.len();
 578         if len <= key {
 579             self.v.extend((0..key - len + 1).map(|_| None));
 580         }
 581         replace(&mut self.v[key], Some(value))
 582     }
 583
 584     /// Removes a key from the map, returning the value at the key if the key
 585     /// was previously in the map.
 586     ///
 587     /// # Examples
 588     ///
 589     /// ```
 590     /// use std::collections::VecMap;
 591     ///
 592     /// let mut map = VecMap::new();
 593     /// map.insert(1, "a");
 594     /// assert_eq!(map.remove(&1), Some("a"));
 595     /// assert_eq!(map.remove(&1), None);
 596     /// ```
 597     #[stable(feature = "rust1", since = "1.0.0")]
 598     pub fn remove(&mut self, key: &usize) -> Option<V> {
 599         if *key >= self.v.len() {
 600             return None;
 601         }
 602         let result = &mut self.v[*key];
 603         result.take()
 604     }
 605
 606     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 607     ///
 608     /// # Examples
 609     ///
 610     /// ```
 611     /// use std::collections::VecMap;
 612     /// use std::collections::vec_map::Entry;
 613     ///
 614     /// let mut count: VecMap<u32> = VecMap::new();
 615     ///
 616     /// // count the number of occurrences of numbers in the vec
 617     /// for x in vec![1, 2, 1, 2, 3, 4, 1, 2, 4].iter() {
 618     ///     match count.entry(*x) {
 619     ///         Entry::Vacant(view) => {
 620     ///             view.insert(1);
 621     ///         },
 622     ///         Entry::Occupied(mut view) => {
 623     ///             let v = view.get_mut();
 624     ///             *v += 1;
 625     ///         },
 626     ///     }
 627     /// }
 628     ///
 629     /// assert_eq!(count[1], 3);
 630     /// ```
 631     #[stable(feature = "rust1", since = "1.0.0")]
 632     pub fn entry(&mut self, key: usize) -> Entry<V> {
 633         // FIXME(Gankro): this is basically the dumbest implementation of
 634         // entry possible, because weird non-lexical borrows issues make it
 635         // completely insane to do any other way. That said, Entry is a border-line
 636         // useless construct on VecMap, so it's hardly a big loss.
 637         if self.contains_key(&key) {
 638             Occupied(OccupiedEntry {
 639                 map: self,
 640                 index: key,
 641             })
 642         } else {
 643             Vacant(VacantEntry {
 644                 map: self,
 645                 index: key,
 646             })
 647         }
 648     }
 649 }
 650
 651
 652 impl<'a, V> Entry<'a, V> {
 653     #[unstable(feature = "collections",
 654                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 655     /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
 656     pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, V>> {
 657         match self {
 658             Occupied(entry) => Ok(entry.into_mut()),
 659             Vacant(entry) => Err(entry),
 660         }
 661     }
 662 }
 663
 664 impl<'a, V> VacantEntry<'a, V> {
 665     /// Sets the value of the entry with the VacantEntry's key,
 666     /// and returns a mutable reference to it.
 667     #[stable(feature = "rust1", since = "1.0.0")]
 668     pub fn insert(self, value: V) -> &'a mut V {
 669         let index = self.index;
 670         self.map.insert(index, value);
 671         &mut self.map[index]
 672     }
 673 }
 674
 675 impl<'a, V> OccupiedEntry<'a, V> {
 676     /// Gets a reference to the value in the entry.
 677     #[stable(feature = "rust1", since = "1.0.0")]
 678     pub fn get(&self) -> &V {
 679         let index = self.index;
 680         &self.map[index]
 681     }
 682
 683     /// Gets a mutable reference to the value in the entry.
 684     #[stable(feature = "rust1", since = "1.0.0")]
 685     pub fn get_mut(&mut self) -> &mut V {
 686         let index = self.index;
 687         &mut self.map[index]
 688     }
 689
 690     /// Converts the entry into a mutable reference to its value.
 691     #[stable(feature = "rust1", since = "1.0.0")]
 692     pub fn into_mut(self) -> &'a mut V {
 693         let index = self.index;
 694         &mut self.map[index]
 695     }
 696
 697     /// Sets the value of the entry with the OccupiedEntry's key,
 698     /// and returns the entry's old value.
 699     #[stable(feature = "rust1", since = "1.0.0")]
 700     pub fn insert(&mut self, value: V) -> V {
 701         let index = self.index;
 702         self.map.insert(index, value).unwrap()
 703     }
 704
 705     /// Takes the value of the entry out of the map, and returns it.
 706     #[stable(feature = "rust1", since = "1.0.0")]
 707     pub fn remove(self) -> V {
 708         let index = self.index;
 709         self.map.remove(&index).unwrap()
 710     }
 711 }
 712
 713 #[stable(feature = "rust1", since = "1.0.0")]
 714 impl<V: PartialEq> PartialEq for VecMap<V> {
 715     fn eq(&self, other: &VecMap<V>) -> bool {
 716         iter::order::eq(self.iter(), other.iter())
 717     }
 718 }
 719
 720 #[stable(feature = "rust1", since = "1.0.0")]
 721 impl<V: Eq> Eq for VecMap<V> {}
 722
 723 #[stable(feature = "rust1", since = "1.0.0")]
 724 impl<V: PartialOrd> PartialOrd for VecMap<V> {
 725     #[inline]
 726     fn partial_cmp(&self, other: &VecMap<V>) -> Option<Ordering> {
 727         iter::order::partial_cmp(self.iter(), other.iter())
 728     }
 729 }
 730
 731 #[stable(feature = "rust1", since = "1.0.0")]
 732 impl<V: Ord> Ord for VecMap<V> {
 733     #[inline]
 734     fn cmp(&self, other: &VecMap<V>) -> Ordering {
 735         iter::order::cmp(self.iter(), other.iter())
 736     }
 737 }
 738
 739 #[stable(feature = "rust1", since = "1.0.0")]
 740 impl<V: fmt::Debug> fmt::Debug for VecMap<V> {
 741     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 742         try!(write!(f, "{{"));
 743
 744         for (i, (k, v)) in self.iter().enumerate() {
 745             if i != 0 { try!(write!(f, ", ")); }
 746             try!(write!(f, "{}: {:?}", k, *v));
 747         }
 748
 749         write!(f, "}}")
 750     }
 751 }
 752
 753 #[stable(feature = "rust1", since = "1.0.0")]
 754 impl<V> FromIterator<(usize, V)> for VecMap<V> {
 755     fn from_iter<I: IntoIterator<Item=(usize, V)>>(iter: I) -> VecMap<V> {
 756         let mut map = VecMap::new();
 757         map.extend(iter);
 758         map
 759     }
 760 }
 761
 762 #[stable(feature = "rust1", since = "1.0.0")]
 763 impl<T> IntoIterator for VecMap<T> {
 764     type Item = (usize, T);
 765     type IntoIter = IntoIter<T>;
 766
 767     fn into_iter(self) -> IntoIter<T> {
 768         self.into_iter()
 769     }
 770 }
 771
 772 #[stable(feature = "rust1", since = "1.0.0")]
 773 impl<'a, T> IntoIterator for &'a VecMap<T> {
 774     type Item = (usize, &'a T);
 775     type IntoIter = Iter<'a, T>;
 776
 777     fn into_iter(self) -> Iter<'a, T> {
 778         self.iter()
 779     }
 780 }
 781
 782 #[stable(feature = "rust1", since = "1.0.0")]
 783 impl<'a, T> IntoIterator for &'a mut VecMap<T> {
 784     type Item = (usize, &'a mut T);
 785     type IntoIter = IterMut<'a, T>;
 786
 787     fn into_iter(mut self) -> IterMut<'a, T> {
 788         self.iter_mut()
 789     }
 790 }
 791
 792 #[stable(feature = "rust1", since = "1.0.0")]
 793 impl<V> Extend<(usize, V)> for VecMap<V> {
 794     fn extend<I: IntoIterator<Item=(usize, V)>>(&mut self, iter: I) {
 795         for (k, v) in iter {
 796             self.insert(k, v);
 797         }
 798     }
 799 }
 800
 801 impl<V> Index<usize> for VecMap<V> {
 802     type Output = V;
 803
 804     #[inline]
 805     fn index<'a>(&'a self, i: &usize) -> &'a V {
 806         self.get(i).expect("key not present")
 807     }
 808 }
 809
 810 #[stable(feature = "rust1", since = "1.0.0")]
 811 impl<V> IndexMut<usize> for VecMap<V> {
 812     #[inline]
 813     fn index_mut<'a>(&'a mut self, i: &usize) -> &'a mut V {
 814         self.get_mut(i).expect("key not present")
 815     }
 816 }
 817
 818 macro_rules! iterator {
 819     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 820         #[stable(feature = "rust1", since = "1.0.0")]
 821         impl<'a, V> Iterator for $name<'a, V> {
 822             type Item = $elem;
 823
 824             #[inline]
 825             fn next(&mut self) -> Option<$elem> {
 826                 while self.front < self.back {
 827                     match self.iter.next() {
 828                         Some(elem) => {
 829                             match elem$(. $getter ())+ {
 830                                 Some(x) => {
 831                                     let index = self.front;
 832                                     self.front += 1;
 833                                     return Some((index, x));
 834                                 },
 835                                 None => {},
 836                             }
 837                         }
 838                         _ => ()
 839                     }
 840                     self.front += 1;
 841                 }
 842                 None
 843             }
 844
 845             #[inline]
 846             fn size_hint(&self) -> (usize, Option<usize>) {
 847                 (0, Some(self.back - self.front))
 848             }
 849         }
 850     }
 851 }
 852
 853 macro_rules! double_ended_iterator {
 854     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 855         #[stable(feature = "rust1", since = "1.0.0")]
 856         impl<'a, V> DoubleEndedIterator for $name<'a, V> {
 857             #[inline]
 858             fn next_back(&mut self) -> Option<$elem> {
 859                 while self.front < self.back {
 860                     match self.iter.next_back() {
 861                         Some(elem) => {
 862                             match elem$(. $getter ())+ {
 863                                 Some(x) => {
 864                                     self.back -= 1;
 865                                     return Some((self.back, x));
 866                                 },
 867                                 None => {},
 868                             }
 869                         }
 870                         _ => ()
 871                     }
 872                     self.back -= 1;
 873                 }
 874                 None
 875             }
 876         }
 877     }
 878 }
 879
 880 /// An iterator over the key-value pairs of a map.
 881 #[stable(feature = "rust1", since = "1.0.0")]
 882 pub struct Iter<'a, V:'a> {
 883     front: usize,
 884     back: usize,
 885     iter: slice::Iter<'a, Option<V>>
 886 }
 887
 888 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 889 impl<'a, V> Clone for Iter<'a, V> {
 890     fn clone(&self) -> Iter<'a, V> {
 891         Iter {
 892             front: self.front,
 893             back: self.back,
 894             iter: self.iter.clone()
 895         }
 896     }
 897 }
 898
 899 iterator! { impl Iter -> (usize, &'a V), as_ref }
 900 double_ended_iterator! { impl Iter -> (usize, &'a V), as_ref }
 901
 902 /// An iterator over the key-value pairs of a map, with the
 903 /// values being mutable.
 904 #[stable(feature = "rust1", since = "1.0.0")]
 905 pub struct IterMut<'a, V:'a> {
 906     front: usize,
 907     back: usize,
 908     iter: slice::IterMut<'a, Option<V>>
 909 }
 910
 911 iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
 912 double_ended_iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
 913
 914 /// An iterator over the keys of a map.
 915 #[stable(feature = "rust1", since = "1.0.0")]
 916 pub struct Keys<'a, V: 'a> {
 917     iter: Map<Iter<'a, V>, fn((usize, &'a V)) -> usize>
 918 }
 919
 920 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 921 impl<'a, V> Clone for Keys<'a, V> {
 922     fn clone(&self) -> Keys<'a, V> {
 923         Keys {
 924             iter: self.iter.clone()
 925         }
 926     }
 927 }
 928
 929 /// An iterator over the values of a map.
 930 #[stable(feature = "rust1", since = "1.0.0")]
 931 pub struct Values<'a, V: 'a> {
 932     iter: Map<Iter<'a, V>, fn((usize, &'a V)) -> &'a V>
 933 }
 934
 935 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 936 impl<'a, V> Clone for Values<'a, V> {
 937     fn clone(&self) -> Values<'a, V> {
 938         Values {
 939             iter: self.iter.clone()
 940         }
 941     }
 942 }
 943
 944 /// A consuming iterator over the key-value pairs of a map.
 945 #[stable(feature = "rust1", since = "1.0.0")]
 946 pub struct IntoIter<V> {
 947     iter: FilterMap<
 948     Enumerate<vec::IntoIter<Option<V>>>,
 949     fn((usize, Option<V>)) -> Option<(usize, V)>>
 950 }
 951
 952 #[unstable(feature = "collections")]
 953 pub struct Drain<'a, V:'a> {
 954     iter: FilterMap<
 955     Enumerate<vec::Drain<'a, Option<V>>>,
 956     fn((usize, Option<V>)) -> Option<(usize, V)>>
 957 }
 958
 959 #[unstable(feature = "collections")]
 960 impl<'a, V> Iterator for Drain<'a, V> {
 961     type Item = (usize, V);
 962
 963     fn next(&mut self) -> Option<(usize, V)> { self.iter.next() }
 964     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 965 }
 966
 967 #[unstable(feature = "collections")]
 968 impl<'a, V> DoubleEndedIterator for Drain<'a, V> {
 969     fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() }
 970 }
 971
 972 #[stable(feature = "rust1", since = "1.0.0")]
 973 impl<'a, V> Iterator for Keys<'a, V> {
 974     type Item = usize;
 975
 976     fn next(&mut self) -> Option<usize> { self.iter.next() }
 977     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 978 }
 979 #[stable(feature = "rust1", since = "1.0.0")]
 980 impl<'a, V> DoubleEndedIterator for Keys<'a, V> {
 981     fn next_back(&mut self) -> Option<usize> { self.iter.next_back() }
 982 }
 983
 984 #[stable(feature = "rust1", since = "1.0.0")]
 985 impl<'a, V> Iterator for Values<'a, V> {
 986     type Item = &'a V;
 987
 988     fn next(&mut self) -> Option<(&'a V)> { self.iter.next() }
 989     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 990 }
 991 #[stable(feature = "rust1", since = "1.0.0")]
 992 impl<'a, V> DoubleEndedIterator for Values<'a, V> {
 993     fn next_back(&mut self) -> Option<(&'a V)> { self.iter.next_back() }
 994 }
 995
 996 #[stable(feature = "rust1", since = "1.0.0")]
 997 impl<V> Iterator for IntoIter<V> {
 998     type Item = (usize, V);
 999
1000     fn next(&mut self) -> Option<(usize, V)> { self.iter.next() }
1001     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1002 }
1003 #[stable(feature = "rust1", since = "1.0.0")]
1004 impl<V> DoubleEndedIterator for IntoIter<V> {
1005     fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() }
1006 }