src/vendor/vec_map/src/lib.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 #![deny(missing_docs)]
  12
  13 //! A simple map based on a vector for small integer keys. Space requirements
  14 //! are O(highest integer key).
  15
  16 // optional serde support
  17 #![cfg_attr(feature = "eders", feature(const_fn, custom_derive, plugin))]
  18 #![cfg_attr(feature = "eders", plugin(serde_macros))]
  19 #[cfg(feature = "eders")]
  20 extern crate serde;
  21
  22 use self::Entry::*;
  23
  24 use std::cmp::{Ordering, max};
  25 use std::fmt;
  26 use std::hash::{Hash, Hasher};
  27 use std::iter::{Enumerate, FilterMap, FromIterator};
  28 use std::mem::{replace, swap};
  29 use std::ops::{Index, IndexMut};
  30 use std::slice;
  31 use std::vec;
  32
  33 /// A map optimized for small integer keys.
  34 ///
  35 /// # Examples
  36 ///
  37 /// ```
  38 /// use vec_map::VecMap;
  39 ///
  40 /// let mut months = VecMap::new();
  41 /// months.insert(1, "Jan");
  42 /// months.insert(2, "Feb");
  43 /// months.insert(3, "Mar");
  44 ///
  45 /// if !months.contains_key(12) {
  46 ///     println!("The end is near!");
  47 /// }
  48 ///
  49 /// assert_eq!(months.get(1), Some(&"Jan"));
  50 ///
  51 /// if let Some(value) = months.get_mut(3) {
  52 ///     *value = "Venus";
  53 /// }
  54 ///
  55 /// assert_eq!(months.get(3), Some(&"Venus"));
  56 ///
  57 /// // Print out all months
  58 /// for (key, value) in &months {
  59 ///     println!("month {} is {}", key, value);
  60 /// }
  61 ///
  62 /// months.clear();
  63 /// assert!(months.is_empty());
  64 /// ```
  65 #[derive(Clone)]
  66 #[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
  67 pub struct VecMap<V> {
  68     v: Vec<Option<V>>,
  69 }
  70
  71 /// A view into a single entry in a map, which may either be vacant or occupied.
  72 pub enum Entry<'a, V: 'a> {
  73     /// A vacant Entry
  74     Vacant(VacantEntry<'a, V>),
  75
  76     /// An occupied Entry
  77     Occupied(OccupiedEntry<'a, V>),
  78 }
  79
  80 /// A vacant Entry.
  81 pub struct VacantEntry<'a, V: 'a> {
  82     map: &'a mut VecMap<V>,
  83     index: usize,
  84 }
  85
  86 /// An occupied Entry.
  87 pub struct OccupiedEntry<'a, V: 'a> {
  88     map: &'a mut VecMap<V>,
  89     index: usize,
  90 }
  91
  92 impl<V> Default for VecMap<V> {
  93     #[inline]
  94     fn default() -> Self { Self::new() }
  95 }
  96
  97 impl<V: Hash> Hash for VecMap<V> {
  98     fn hash<H: Hasher>(&self, state: &mut H) {
  99         // In order to not traverse the `VecMap` twice, count the elements
 100         // during iteration.
 101         let mut count: usize = 0;
 102         for elt in self {
 103             elt.hash(state);
 104             count += 1;
 105         }
 106         count.hash(state);
 107     }
 108 }
 109
 110 impl<V> VecMap<V> {
 111     /// Creates an empty `VecMap`.
 112     ///
 113     /// # Examples
 114     ///
 115     /// ```
 116     /// use vec_map::VecMap;
 117     /// let mut map: VecMap<&str> = VecMap::new();
 118     /// ```
 119     pub fn new() -> Self { VecMap { v: vec![] } }
 120
 121     /// Creates an empty `VecMap` with space for at least `capacity`
 122     /// elements before resizing.
 123     ///
 124     /// # Examples
 125     ///
 126     /// ```
 127     /// use vec_map::VecMap;
 128     /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
 129     /// ```
 130     pub fn with_capacity(capacity: usize) -> Self {
 131         VecMap { v: Vec::with_capacity(capacity) }
 132     }
 133
 134     /// Returns the number of elements the `VecMap` can hold without
 135     /// reallocating.
 136     ///
 137     /// # Examples
 138     ///
 139     /// ```
 140     /// use vec_map::VecMap;
 141     /// let map: VecMap<String> = VecMap::with_capacity(10);
 142     /// assert!(map.capacity() >= 10);
 143     /// ```
 144     #[inline]
 145     pub fn capacity(&self) -> usize {
 146         self.v.capacity()
 147     }
 148
 149     /// Reserves capacity for the given `VecMap` to contain `len` distinct keys.
 150     /// In the case of `VecMap` this means reallocations will not occur as long
 151     /// as all inserted keys are less than `len`.
 152     ///
 153     /// The collection may reserve more space to avoid frequent reallocations.
 154     ///
 155     /// # Examples
 156     ///
 157     /// ```
 158     /// use vec_map::VecMap;
 159     /// let mut map: VecMap<&str> = VecMap::new();
 160     /// map.reserve_len(10);
 161     /// assert!(map.capacity() >= 10);
 162     /// ```
 163     pub fn reserve_len(&mut self, len: usize) {
 164         let cur_len = self.v.len();
 165         if len >= cur_len {
 166             self.v.reserve(len - cur_len);
 167         }
 168     }
 169
 170     /// Reserves the minimum capacity for the given `VecMap` to contain `len` distinct keys.
 171     /// In the case of `VecMap` this means reallocations will not occur as long as all inserted
 172     /// keys are less than `len`.
 173     ///
 174     /// Note that the allocator may give the collection more space than it requests.
 175     /// Therefore capacity cannot be relied upon to be precisely minimal.  Prefer
 176     /// `reserve_len` if future insertions are expected.
 177     ///
 178     /// # Examples
 179     ///
 180     /// ```
 181     /// use vec_map::VecMap;
 182     /// let mut map: VecMap<&str> = VecMap::new();
 183     /// map.reserve_len_exact(10);
 184     /// assert!(map.capacity() >= 10);
 185     /// ```
 186     pub fn reserve_len_exact(&mut self, len: usize) {
 187         let cur_len = self.v.len();
 188         if len >= cur_len {
 189             self.v.reserve_exact(len - cur_len);
 190         }
 191     }
 192
 193     /// Returns an iterator visiting all keys in ascending order of the keys.
 194     /// The iterator's element type is `usize`.
 195     pub fn keys(&self) -> Keys<V> {
 196         Keys { iter: self.iter() }
 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     pub fn values(&self) -> Values<V> {
 202         Values { iter: self.iter() }
 203     }
 204
 205     /// Returns an iterator visiting all key-value pairs in ascending order of the keys.
 206     /// The iterator's element type is `(usize, &'r V)`.
 207     ///
 208     /// # Examples
 209     ///
 210     /// ```
 211     /// use vec_map::VecMap;
 212     ///
 213     /// let mut map = VecMap::new();
 214     /// map.insert(1, "a");
 215     /// map.insert(3, "c");
 216     /// map.insert(2, "b");
 217     ///
 218     /// // Print `1: a` then `2: b` then `3: c`
 219     /// for (key, value) in map.iter() {
 220     ///     println!("{}: {}", key, value);
 221     /// }
 222     /// ```
 223     pub fn iter(&self) -> Iter<V> {
 224         Iter {
 225             front: 0,
 226             back: self.v.len(),
 227             iter: self.v.iter()
 228         }
 229     }
 230
 231     /// Returns an iterator visiting all key-value pairs in ascending order of the keys,
 232     /// with mutable references to the values.
 233     /// The iterator's element type is `(usize, &'r mut V)`.
 234     ///
 235     /// # Examples
 236     ///
 237     /// ```
 238     /// use vec_map::VecMap;
 239     ///
 240     /// let mut map = VecMap::new();
 241     /// map.insert(1, "a");
 242     /// map.insert(2, "b");
 243     /// map.insert(3, "c");
 244     ///
 245     /// for (key, value) in map.iter_mut() {
 246     ///     *value = "x";
 247     /// }
 248     ///
 249     /// for (key, value) in &map {
 250     ///     assert_eq!(value, &"x");
 251     /// }
 252     /// ```
 253     pub fn iter_mut(&mut self) -> IterMut<V> {
 254         IterMut {
 255             front: 0,
 256             back: self.v.len(),
 257             iter: self.v.iter_mut()
 258         }
 259     }
 260
 261     /// Moves all elements from `other` into the map while overwriting existing keys.
 262     ///
 263     /// # Examples
 264     ///
 265     /// ```
 266     /// use vec_map::VecMap;
 267     ///
 268     /// let mut a = VecMap::new();
 269     /// a.insert(1, "a");
 270     /// a.insert(2, "b");
 271     ///
 272     /// let mut b = VecMap::new();
 273     /// b.insert(3, "c");
 274     /// b.insert(4, "d");
 275     ///
 276     /// a.append(&mut b);
 277     ///
 278     /// assert_eq!(a.len(), 4);
 279     /// assert_eq!(b.len(), 0);
 280     /// assert_eq!(a[1], "a");
 281     /// assert_eq!(a[2], "b");
 282     /// assert_eq!(a[3], "c");
 283     /// assert_eq!(a[4], "d");
 284     /// ```
 285     pub fn append(&mut self, other: &mut Self) {
 286         self.extend(other.drain());
 287     }
 288
 289     /// Splits the collection into two at the given key.
 290     ///
 291     /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
 292     /// and the returned `Self` contains elements `[at, max_key)`.
 293     ///
 294     /// Note that the capacity of `self` does not change.
 295     ///
 296     /// # Examples
 297     ///
 298     /// ```
 299     /// use vec_map::VecMap;
 300     ///
 301     /// let mut a = VecMap::new();
 302     /// a.insert(1, "a");
 303     /// a.insert(2, "b");
 304     /// a.insert(3, "c");
 305     /// a.insert(4, "d");
 306     ///
 307     /// let b = a.split_off(3);
 308     ///
 309     /// assert_eq!(a[1], "a");
 310     /// assert_eq!(a[2], "b");
 311     ///
 312     /// assert_eq!(b[3], "c");
 313     /// assert_eq!(b[4], "d");
 314     /// ```
 315     pub fn split_off(&mut self, at: usize) -> Self {
 316         let mut other = VecMap::new();
 317
 318         if at == 0 {
 319             // Move all elements to other
 320             swap(self, &mut other);
 321             return other
 322         } else if at >= self.v.len() {
 323             // No elements to copy
 324             return other;
 325         }
 326
 327         // Look up the index of the first non-None item
 328         let first_index = self.v.iter().position(|el| el.is_some());
 329         let start_index = match first_index {
 330             Some(index) => max(at, index),
 331             None => {
 332                 // self has no elements
 333                 return other;
 334             }
 335         };
 336
 337         // Fill the new VecMap with `None`s until `start_index`
 338         other.v.extend((0..start_index).map(|_| None));
 339
 340         // Move elements beginning with `start_index` from `self` into `other`
 341         other.v.extend(self.v[start_index..].iter_mut().map(|el| el.take()));
 342
 343         other
 344     }
 345
 346     /// Returns an iterator visiting all key-value pairs in ascending order of
 347     /// the keys, emptying (but not consuming) the original `VecMap`.
 348     /// The iterator's element type is `(usize, &'r V)`. Keeps the allocated memory for reuse.
 349     ///
 350     /// # Examples
 351     ///
 352     /// ```
 353     /// use vec_map::VecMap;
 354     ///
 355     /// let mut map = VecMap::new();
 356     /// map.insert(1, "a");
 357     /// map.insert(3, "c");
 358     /// map.insert(2, "b");
 359     ///
 360     /// let vec: Vec<(usize, &str)> = map.drain().collect();
 361     ///
 362     /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
 363     /// ```
 364     pub fn drain(&mut self) -> Drain<V> {
 365         fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
 366             v.map(|v| (i, v))
 367         }
 368         let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
 369
 370         Drain { iter: self.v.drain(..).enumerate().filter_map(filter) }
 371     }
 372
 373     /// Returns the number of elements in the map.
 374     ///
 375     /// # Examples
 376     ///
 377     /// ```
 378     /// use vec_map::VecMap;
 379     ///
 380     /// let mut a = VecMap::new();
 381     /// assert_eq!(a.len(), 0);
 382     /// a.insert(1, "a");
 383     /// assert_eq!(a.len(), 1);
 384     /// ```
 385     pub fn len(&self) -> usize {
 386         self.v.iter().filter(|elt| elt.is_some()).count()
 387     }
 388
 389     /// Returns true if the map contains no elements.
 390     ///
 391     /// # Examples
 392     ///
 393     /// ```
 394     /// use vec_map::VecMap;
 395     ///
 396     /// let mut a = VecMap::new();
 397     /// assert!(a.is_empty());
 398     /// a.insert(1, "a");
 399     /// assert!(!a.is_empty());
 400     /// ```
 401     pub fn is_empty(&self) -> bool {
 402         self.v.iter().all(|elt| elt.is_none())
 403     }
 404
 405     /// Clears the map, removing all key-value pairs.
 406     ///
 407     /// # Examples
 408     ///
 409     /// ```
 410     /// use vec_map::VecMap;
 411     ///
 412     /// let mut a = VecMap::new();
 413     /// a.insert(1, "a");
 414     /// a.clear();
 415     /// assert!(a.is_empty());
 416     /// ```
 417     pub fn clear(&mut self) { self.v.clear() }
 418
 419     /// Returns a reference to the value corresponding to the key.
 420     ///
 421     /// # Examples
 422     ///
 423     /// ```
 424     /// use vec_map::VecMap;
 425     ///
 426     /// let mut map = VecMap::new();
 427     /// map.insert(1, "a");
 428     /// assert_eq!(map.get(1), Some(&"a"));
 429     /// assert_eq!(map.get(2), None);
 430     /// ```
 431     pub fn get(&self, key: usize) -> Option<&V> {
 432         if key < self.v.len() {
 433             match self.v[key] {
 434               Some(ref value) => Some(value),
 435               None => None
 436             }
 437         } else {
 438             None
 439         }
 440     }
 441
 442     /// Returns true if the map contains a value for the specified key.
 443     ///
 444     /// # Examples
 445     ///
 446     /// ```
 447     /// use vec_map::VecMap;
 448     ///
 449     /// let mut map = VecMap::new();
 450     /// map.insert(1, "a");
 451     /// assert_eq!(map.contains_key(1), true);
 452     /// assert_eq!(map.contains_key(2), false);
 453     /// ```
 454     #[inline]
 455     pub fn contains_key(&self, key: usize) -> bool {
 456         self.get(key).is_some()
 457     }
 458
 459     /// Returns a mutable reference to the value corresponding to the key.
 460     ///
 461     /// # Examples
 462     ///
 463     /// ```
 464     /// use vec_map::VecMap;
 465     ///
 466     /// let mut map = VecMap::new();
 467     /// map.insert(1, "a");
 468     /// if let Some(x) = map.get_mut(1) {
 469     ///     *x = "b";
 470     /// }
 471     /// assert_eq!(map[1], "b");
 472     /// ```
 473     pub fn get_mut(&mut self, key: usize) -> Option<&mut V> {
 474         if key < self.v.len() {
 475             match *(&mut self.v[key]) {
 476               Some(ref mut value) => Some(value),
 477               None => None
 478             }
 479         } else {
 480             None
 481         }
 482     }
 483
 484     /// Inserts a key-value pair into the map. If the key already had a value
 485     /// present in the map, that value is returned. Otherwise, `None` is returned.
 486     ///
 487     /// # Examples
 488     ///
 489     /// ```
 490     /// use vec_map::VecMap;
 491     ///
 492     /// let mut map = VecMap::new();
 493     /// assert_eq!(map.insert(37, "a"), None);
 494     /// assert_eq!(map.is_empty(), false);
 495     ///
 496     /// map.insert(37, "b");
 497     /// assert_eq!(map.insert(37, "c"), Some("b"));
 498     /// assert_eq!(map[37], "c");
 499     /// ```
 500     pub fn insert(&mut self, key: usize, value: V) -> Option<V> {
 501         let len = self.v.len();
 502         if len <= key {
 503             self.v.extend((0..key - len + 1).map(|_| None));
 504         }
 505         replace(&mut self.v[key], Some(value))
 506     }
 507
 508     /// Removes a key from the map, returning the value at the key if the key
 509     /// was previously in the map.
 510     ///
 511     /// # Examples
 512     ///
 513     /// ```
 514     /// use vec_map::VecMap;
 515     ///
 516     /// let mut map = VecMap::new();
 517     /// map.insert(1, "a");
 518     /// assert_eq!(map.remove(1), Some("a"));
 519     /// assert_eq!(map.remove(1), None);
 520     /// ```
 521     pub fn remove(&mut self, key: usize) -> Option<V> {
 522         if key >= self.v.len() {
 523             return None;
 524         }
 525         let result = &mut self.v[key];
 526         result.take()
 527     }
 528
 529     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 530     ///
 531     /// # Examples
 532     ///
 533     /// ```
 534     /// use vec_map::VecMap;
 535     ///
 536     /// let mut count: VecMap<u32> = VecMap::new();
 537     ///
 538     /// // count the number of occurrences of numbers in the vec
 539     /// for x in vec![1, 2, 1, 2, 3, 4, 1, 2, 4] {
 540     ///     *count.entry(x).or_insert(0) += 1;
 541     /// }
 542     ///
 543     /// assert_eq!(count[1], 3);
 544     /// ```
 545     pub fn entry(&mut self, key: usize) -> Entry<V> {
 546         // FIXME(Gankro): this is basically the dumbest implementation of
 547         // entry possible, because weird non-lexical borrows issues make it
 548         // completely insane to do any other way. That said, Entry is a border-line
 549         // useless construct on VecMap, so it's hardly a big loss.
 550         if self.contains_key(key) {
 551             Occupied(OccupiedEntry {
 552                 map: self,
 553                 index: key,
 554             })
 555         } else {
 556             Vacant(VacantEntry {
 557                 map: self,
 558                 index: key,
 559             })
 560         }
 561     }
 562 }
 563
 564 impl<'a, V> Entry<'a, V> {
 565     /// Ensures a value is in the entry by inserting the default if empty, and
 566     /// returns a mutable reference to the value in the entry.
 567     pub fn or_insert(self, default: V) -> &'a mut V {
 568         match self {
 569             Occupied(entry) => entry.into_mut(),
 570             Vacant(entry) => entry.insert(default),
 571         }
 572     }
 573
 574     /// Ensures a value is in the entry by inserting the result of the default
 575     /// function if empty, and returns a mutable reference to the value in the
 576     /// entry.
 577     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
 578         match self {
 579             Occupied(entry) => entry.into_mut(),
 580             Vacant(entry) => entry.insert(default()),
 581         }
 582     }
 583 }
 584
 585 impl<'a, V> VacantEntry<'a, V> {
 586     /// Sets the value of the entry with the VacantEntry's key,
 587     /// and returns a mutable reference to it.
 588     pub fn insert(self, value: V) -> &'a mut V {
 589         let index = self.index;
 590         self.map.insert(index, value);
 591         &mut self.map[index]
 592     }
 593 }
 594
 595 impl<'a, V> OccupiedEntry<'a, V> {
 596     /// Gets a reference to the value in the entry.
 597     pub fn get(&self) -> &V {
 598         let index = self.index;
 599         &self.map[index]
 600     }
 601
 602     /// Gets a mutable reference to the value in the entry.
 603     pub fn get_mut(&mut self) -> &mut V {
 604         let index = self.index;
 605         &mut self.map[index]
 606     }
 607
 608     /// Converts the entry into a mutable reference to its value.
 609     pub fn into_mut(self) -> &'a mut V {
 610         let index = self.index;
 611         &mut self.map[index]
 612     }
 613
 614     /// Sets the value of the entry with the OccupiedEntry's key,
 615     /// and returns the entry's old value.
 616     pub fn insert(&mut self, value: V) -> V {
 617         let index = self.index;
 618         self.map.insert(index, value).unwrap()
 619     }
 620
 621     /// Takes the value of the entry out of the map, and returns it.
 622     pub fn remove(self) -> V {
 623         let index = self.index;
 624         self.map.remove(index).unwrap()
 625     }
 626 }
 627
 628 impl<V: PartialEq> PartialEq for VecMap<V> {
 629     fn eq(&self, other: &Self) -> bool {
 630         self.iter().eq(other.iter())
 631     }
 632 }
 633
 634 impl<V: Eq> Eq for VecMap<V> {}
 635
 636 impl<V: PartialOrd> PartialOrd for VecMap<V> {
 637     #[inline]
 638     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 639         self.iter().partial_cmp(other.iter())
 640     }
 641 }
 642
 643 impl<V: Ord> Ord for VecMap<V> {
 644     #[inline]
 645     fn cmp(&self, other: &Self) -> Ordering {
 646         self.iter().cmp(other.iter())
 647     }
 648 }
 649
 650 impl<V: fmt::Debug> fmt::Debug for VecMap<V> {
 651     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 652         f.debug_map().entries(self).finish()
 653     }
 654 }
 655
 656 impl<V> FromIterator<(usize, V)> for VecMap<V> {
 657     fn from_iter<I: IntoIterator<Item = (usize, V)>>(iter: I) -> Self {
 658         let mut map = Self::new();
 659         map.extend(iter);
 660         map
 661     }
 662 }
 663
 664 impl<T> IntoIterator for VecMap<T> {
 665     type Item = (usize, T);
 666     type IntoIter = IntoIter<T>;
 667
 668     /// Returns an iterator visiting all key-value pairs in ascending order of
 669     /// the keys, consuming the original `VecMap`.
 670     /// The iterator's element type is `(usize, &'r V)`.
 671     ///
 672     /// # Examples
 673     ///
 674     /// ```
 675     /// use vec_map::VecMap;
 676     ///
 677     /// let mut map = VecMap::new();
 678     /// map.insert(1, "a");
 679     /// map.insert(3, "c");
 680     /// map.insert(2, "b");
 681     ///
 682     /// let vec: Vec<(usize, &str)> = map.into_iter().collect();
 683     ///
 684     /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
 685     /// ```
 686     fn into_iter(self) -> IntoIter<T> {
 687         IntoIter { iter: self.v.into_iter().enumerate() }
 688     }
 689 }
 690
 691 impl<'a, T> IntoIterator for &'a VecMap<T> {
 692     type Item = (usize, &'a T);
 693     type IntoIter = Iter<'a, T>;
 694
 695     fn into_iter(self) -> Iter<'a, T> {
 696         self.iter()
 697     }
 698 }
 699
 700 impl<'a, T> IntoIterator for &'a mut VecMap<T> {
 701     type Item = (usize, &'a mut T);
 702     type IntoIter = IterMut<'a, T>;
 703
 704     fn into_iter(mut self) -> IterMut<'a, T> {
 705         self.iter_mut()
 706     }
 707 }
 708
 709 impl<V> Extend<(usize, V)> for VecMap<V> {
 710     fn extend<I: IntoIterator<Item = (usize, V)>>(&mut self, iter: I) {
 711         for (k, v) in iter {
 712             self.insert(k, v);
 713         }
 714     }
 715 }
 716
 717 impl<'a, V: Copy> Extend<(usize, &'a V)> for VecMap<V> {
 718     fn extend<I: IntoIterator<Item = (usize, &'a V)>>(&mut self, iter: I) {
 719         self.extend(iter.into_iter().map(|(key, &value)| (key, value)));
 720     }
 721 }
 722
 723 impl<V> Index<usize> for VecMap<V> {
 724     type Output = V;
 725
 726     #[inline]
 727     fn index(&self, i: usize) -> &V {
 728         self.get(i).expect("key not present")
 729     }
 730 }
 731
 732 impl<'a, V> Index<&'a usize> for VecMap<V> {
 733     type Output = V;
 734
 735     #[inline]
 736     fn index(&self, i: &usize) -> &V {
 737         self.get(*i).expect("key not present")
 738     }
 739 }
 740
 741 impl<V> IndexMut<usize> for VecMap<V> {
 742     #[inline]
 743     fn index_mut(&mut self, i: usize) -> &mut V {
 744         self.get_mut(i).expect("key not present")
 745     }
 746 }
 747
 748 impl<'a, V> IndexMut<&'a usize> for VecMap<V> {
 749     #[inline]
 750     fn index_mut(&mut self, i: &usize) -> &mut V {
 751         self.get_mut(*i).expect("key not present")
 752     }
 753 }
 754
 755 macro_rules! iterator {
 756     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 757         impl<'a, V> Iterator for $name<'a, V> {
 758             type Item = $elem;
 759
 760             #[inline]
 761             fn next(&mut self) -> Option<$elem> {
 762                 while self.front < self.back {
 763                     match self.iter.next() {
 764                         Some(elem) => {
 765                             match elem$(. $getter ())+ {
 766                                 Some(x) => {
 767                                     let index = self.front;
 768                                     self.front += 1;
 769                                     return Some((index, x));
 770                                 },
 771                                 None => {},
 772                             }
 773                         }
 774                         _ => ()
 775                     }
 776                     self.front += 1;
 777                 }
 778                 None
 779             }
 780
 781             #[inline]
 782             fn size_hint(&self) -> (usize, Option<usize>) {
 783                 (0, Some(self.back - self.front))
 784             }
 785         }
 786     }
 787 }
 788
 789 macro_rules! double_ended_iterator {
 790     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 791         impl<'a, V> DoubleEndedIterator for $name<'a, V> {
 792             #[inline]
 793             fn next_back(&mut self) -> Option<$elem> {
 794                 while self.front < self.back {
 795                     match self.iter.next_back() {
 796                         Some(elem) => {
 797                             match elem$(. $getter ())+ {
 798                                 Some(x) => {
 799                                     self.back -= 1;
 800                                     return Some((self.back, x));
 801                                 },
 802                                 None => {},
 803                             }
 804                         }
 805                         _ => ()
 806                     }
 807                     self.back -= 1;
 808                 }
 809                 None
 810             }
 811         }
 812     }
 813 }
 814
 815 /// An iterator over the key-value pairs of a map.
 816 pub struct Iter<'a, V: 'a> {
 817     front: usize,
 818     back: usize,
 819     iter: slice::Iter<'a, Option<V>>
 820 }
 821
 822 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 823 impl<'a, V> Clone for Iter<'a, V> {
 824     fn clone(&self) -> Iter<'a, V> {
 825         Iter {
 826             front: self.front,
 827             back: self.back,
 828             iter: self.iter.clone()
 829         }
 830     }
 831 }
 832
 833 iterator! { impl Iter -> (usize, &'a V), as_ref }
 834 double_ended_iterator! { impl Iter -> (usize, &'a V), as_ref }
 835
 836 /// An iterator over the key-value pairs of a map, with the
 837 /// values being mutable.
 838 pub struct IterMut<'a, V: 'a> {
 839     front: usize,
 840     back: usize,
 841     iter: slice::IterMut<'a, Option<V>>
 842 }
 843
 844 iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
 845 double_ended_iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
 846
 847 /// An iterator over the keys of a map.
 848 pub struct Keys<'a, V: 'a> {
 849     iter: Iter<'a, V>,
 850 }
 851
 852 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 853 impl<'a, V> Clone for Keys<'a, V> {
 854     fn clone(&self) -> Keys<'a, V> {
 855         Keys {
 856             iter: self.iter.clone()
 857         }
 858     }
 859 }
 860
 861 /// An iterator over the values of a map.
 862 pub struct Values<'a, V: 'a> {
 863     iter: Iter<'a, V>,
 864 }
 865
 866 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 867 impl<'a, V> Clone for Values<'a, V> {
 868     fn clone(&self) -> Values<'a, V> {
 869         Values {
 870             iter: self.iter.clone()
 871         }
 872     }
 873 }
 874
 875 /// A consuming iterator over the key-value pairs of a map.
 876 pub struct IntoIter<V> {
 877     iter: Enumerate<vec::IntoIter<Option<V>>>,
 878 }
 879
 880 /// A draining iterator over the key-value pairs of a map.
 881 pub struct Drain<'a, V: 'a> {
 882     iter: FilterMap<
 883     Enumerate<vec::Drain<'a, Option<V>>>,
 884     fn((usize, Option<V>)) -> Option<(usize, V)>>
 885 }
 886
 887 impl<'a, V> Iterator for Drain<'a, V> {
 888     type Item = (usize, V);
 889
 890     fn next(&mut self) -> Option<(usize, V)> { self.iter.next() }
 891     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 892 }
 893
 894 impl<'a, V> DoubleEndedIterator for Drain<'a, V> {
 895     fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() }
 896 }
 897
 898 impl<'a, V> Iterator for Keys<'a, V> {
 899     type Item = usize;
 900
 901     fn next(&mut self) -> Option<usize> { self.iter.next().map(|e| e.0) }
 902     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 903 }
 904
 905 impl<'a, V> DoubleEndedIterator for Keys<'a, V> {
 906     fn next_back(&mut self) -> Option<usize> { self.iter.next_back().map(|e| e.0) }
 907 }
 908
 909 impl<'a, V> Iterator for Values<'a, V> {
 910     type Item = &'a V;
 911
 912     fn next(&mut self) -> Option<(&'a V)> { self.iter.next().map(|e| e.1) }
 913     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 914 }
 915
 916 impl<'a, V> DoubleEndedIterator for Values<'a, V> {
 917     fn next_back(&mut self) -> Option<(&'a V)> { self.iter.next_back().map(|e| e.1) }
 918 }
 919
 920 impl<V> Iterator for IntoIter<V> {
 921     type Item = (usize, V);
 922
 923     fn next(&mut self) -> Option<(usize, V)> {
 924         loop {
 925             match self.iter.next() {
 926                 None => return None,
 927                 Some((i, Some(value))) => return Some((i, value)),
 928                 _ => {}
 929             }
 930         }
 931     }
 932
 933     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 934 }
 935
 936 impl<V> DoubleEndedIterator for IntoIter<V> {
 937     fn next_back(&mut self) -> Option<(usize, V)> {
 938         loop {
 939             match self.iter.next_back() {
 940                 None => return None,
 941                 Some((i, Some(value))) => return Some((i, value)),
 942                 _ => {}
 943             }
 944         }
 945     }
 946 }
 947
 948 #[allow(dead_code)]
 949 fn assert_properties() {
 950     fn vec_map_covariant<'a, T>(map: VecMap<&'static T>) -> VecMap<&'a T> { map }
 951
 952     fn into_iter_covariant<'a, T>(iter: IntoIter<&'static T>) -> IntoIter<&'a T> { iter }
 953
 954     fn iter_covariant<'i, 'a, T>(iter: Iter<'i, &'static T>) -> Iter<'i, &'a T> { iter }
 955
 956     fn keys_covariant<'i, 'a, T>(iter: Keys<'i, &'static T>) -> Keys<'i, &'a T> { iter }
 957
 958     fn values_covariant<'i, 'a, T>(iter: Values<'i, &'static T>) -> Values<'i, &'a T> { iter }
 959 }
 960
 961 #[cfg(test)]
 962 mod test {
 963     use super::VecMap;
 964     use super::Entry::{Occupied, Vacant};
 965     use std::hash::{Hash, Hasher, SipHasher};
 966
 967     #[test]
 968     fn test_get_mut() {
 969         let mut m = VecMap::new();
 970         assert!(m.insert(1, 12).is_none());
 971         assert!(m.insert(2, 8).is_none());
 972         assert!(m.insert(5, 14).is_none());
 973         let new = 100;
 974         match m.get_mut(5) {
 975             None => panic!(), Some(x) => *x = new
 976         }
 977         assert_eq!(m.get(5), Some(&new));
 978     }
 979
 980     #[test]
 981     fn test_len() {
 982         let mut map = VecMap::new();
 983         assert_eq!(map.len(), 0);
 984         assert!(map.is_empty());
 985         assert!(map.insert(5, 20).is_none());
 986         assert_eq!(map.len(), 1);
 987         assert!(!map.is_empty());
 988         assert!(map.insert(11, 12).is_none());
 989         assert_eq!(map.len(), 2);
 990         assert!(!map.is_empty());
 991         assert!(map.insert(14, 22).is_none());
 992         assert_eq!(map.len(), 3);
 993         assert!(!map.is_empty());
 994     }
 995
 996     #[test]
 997     fn test_clear() {
 998         let mut map = VecMap::new();
 999         assert!(map.insert(5, 20).is_none());
1000         assert!(map.insert(11, 12).is_none());
1001         assert!(map.insert(14, 22).is_none());
1002         map.clear();
1003         assert!(map.is_empty());
1004         assert!(map.get(5).is_none());
1005         assert!(map.get(11).is_none());
1006         assert!(map.get(14).is_none());
1007     }
1008
1009     #[test]
1010     fn test_insert() {
1011         let mut m = VecMap::new();
1012         assert_eq!(m.insert(1, 2), None);
1013         assert_eq!(m.insert(1, 3), Some(2));
1014         assert_eq!(m.insert(1, 4), Some(3));
1015     }
1016
1017     #[test]
1018     fn test_remove() {
1019         let mut m = VecMap::new();
1020         m.insert(1, 2);
1021         assert_eq!(m.remove(1), Some(2));
1022         assert_eq!(m.remove(1), None);
1023     }
1024
1025     #[test]
1026     fn test_keys() {
1027         let mut map = VecMap::new();
1028         map.insert(1, 'a');
1029         map.insert(2, 'b');
1030         map.insert(3, 'c');
1031         let keys: Vec<_> = map.keys().collect();
1032         assert_eq!(keys.len(), 3);
1033         assert!(keys.contains(&1));
1034         assert!(keys.contains(&2));
1035         assert!(keys.contains(&3));
1036     }
1037
1038     #[test]
1039     fn test_values() {
1040         let mut map = VecMap::new();
1041         map.insert(1, 'a');
1042         map.insert(2, 'b');
1043         map.insert(3, 'c');
1044         let values: Vec<_> = map.values().cloned().collect();
1045         assert_eq!(values.len(), 3);
1046         assert!(values.contains(&'a'));
1047         assert!(values.contains(&'b'));
1048         assert!(values.contains(&'c'));
1049     }
1050
1051     #[test]
1052     fn test_iterator() {
1053         let mut m = VecMap::new();
1054
1055         assert!(m.insert(0, 1).is_none());
1056         assert!(m.insert(1, 2).is_none());
1057         assert!(m.insert(3, 5).is_none());
1058         assert!(m.insert(6, 10).is_none());
1059         assert!(m.insert(10, 11).is_none());
1060
1061         let mut it = m.iter();
1062         assert_eq!(it.size_hint(), (0, Some(11)));
1063         assert_eq!(it.next().unwrap(), (0, &1));
1064         assert_eq!(it.size_hint(), (0, Some(10)));
1065         assert_eq!(it.next().unwrap(), (1, &2));
1066         assert_eq!(it.size_hint(), (0, Some(9)));
1067         assert_eq!(it.next().unwrap(), (3, &5));
1068         assert_eq!(it.size_hint(), (0, Some(7)));
1069         assert_eq!(it.next().unwrap(), (6, &10));
1070         assert_eq!(it.size_hint(), (0, Some(4)));
1071         assert_eq!(it.next().unwrap(), (10, &11));
1072         assert_eq!(it.size_hint(), (0, Some(0)));
1073         assert!(it.next().is_none());
1074     }
1075
1076     #[test]
1077     fn test_iterator_size_hints() {
1078         let mut m = VecMap::new();
1079
1080         assert!(m.insert(0, 1).is_none());
1081         assert!(m.insert(1, 2).is_none());
1082         assert!(m.insert(3, 5).is_none());
1083         assert!(m.insert(6, 10).is_none());
1084         assert!(m.insert(10, 11).is_none());
1085
1086         assert_eq!(m.iter().size_hint(), (0, Some(11)));
1087         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
1088         assert_eq!(m.iter_mut().size_hint(), (0, Some(11)));
1089         assert_eq!(m.iter_mut().rev().size_hint(), (0, Some(11)));
1090     }
1091
1092     #[test]
1093     fn test_mut_iterator() {
1094         let mut m = VecMap::new();
1095
1096         assert!(m.insert(0, 1).is_none());
1097         assert!(m.insert(1, 2).is_none());
1098         assert!(m.insert(3, 5).is_none());
1099         assert!(m.insert(6, 10).is_none());
1100         assert!(m.insert(10, 11).is_none());
1101
1102         for (k, v) in &mut m {
1103             *v += k as isize;
1104         }
1105
1106         let mut it = m.iter();
1107         assert_eq!(it.next().unwrap(), (0, &1));
1108         assert_eq!(it.next().unwrap(), (1, &3));
1109         assert_eq!(it.next().unwrap(), (3, &8));
1110         assert_eq!(it.next().unwrap(), (6, &16));
1111         assert_eq!(it.next().unwrap(), (10, &21));
1112         assert!(it.next().is_none());
1113     }
1114
1115     #[test]
1116     fn test_rev_iterator() {
1117         let mut m = VecMap::new();
1118
1119         assert!(m.insert(0, 1).is_none());
1120         assert!(m.insert(1, 2).is_none());
1121         assert!(m.insert(3, 5).is_none());
1122         assert!(m.insert(6, 10).is_none());
1123         assert!(m.insert(10, 11).is_none());
1124
1125         let mut it = m.iter().rev();
1126         assert_eq!(it.next().unwrap(), (10, &11));
1127         assert_eq!(it.next().unwrap(), (6, &10));
1128         assert_eq!(it.next().unwrap(), (3, &5));
1129         assert_eq!(it.next().unwrap(), (1, &2));
1130         assert_eq!(it.next().unwrap(), (0, &1));
1131         assert!(it.next().is_none());
1132     }
1133
1134     #[test]
1135     fn test_mut_rev_iterator() {
1136         let mut m = VecMap::new();
1137
1138         assert!(m.insert(0, 1).is_none());
1139         assert!(m.insert(1, 2).is_none());
1140         assert!(m.insert(3, 5).is_none());
1141         assert!(m.insert(6, 10).is_none());
1142         assert!(m.insert(10, 11).is_none());
1143
1144         for (k, v) in m.iter_mut().rev() {
1145             *v += k as isize;
1146         }
1147
1148         let mut it = m.iter();
1149         assert_eq!(it.next().unwrap(), (0, &1));
1150         assert_eq!(it.next().unwrap(), (1, &3));
1151         assert_eq!(it.next().unwrap(), (3, &8));
1152         assert_eq!(it.next().unwrap(), (6, &16));
1153         assert_eq!(it.next().unwrap(), (10, &21));
1154         assert!(it.next().is_none());
1155     }
1156
1157     #[test]
1158     fn test_move_iter() {
1159         let mut m: VecMap<Box<_>> = VecMap::new();
1160         m.insert(1, Box::new(2));
1161         let mut called = false;
1162         for (k, v) in m {
1163             assert!(!called);
1164             called = true;
1165             assert_eq!(k, 1);
1166             assert_eq!(v, Box::new(2));
1167         }
1168         assert!(called);
1169     }
1170
1171     #[test]
1172     fn test_drain_iterator() {
1173         let mut map = VecMap::new();
1174         map.insert(1, "a");
1175         map.insert(3, "c");
1176         map.insert(2, "b");
1177
1178         let vec: Vec<_> = map.drain().collect();
1179
1180         assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]);
1181         assert_eq!(map.len(), 0);
1182     }
1183
1184     #[test]
1185     fn test_append() {
1186         let mut a = VecMap::new();
1187         a.insert(1, "a");
1188         a.insert(2, "b");
1189         a.insert(3, "c");
1190
1191         let mut b = VecMap::new();
1192         b.insert(3, "d");  // Overwrite element from a
1193         b.insert(4, "e");
1194         b.insert(5, "f");
1195
1196         a.append(&mut b);
1197
1198         assert_eq!(a.len(), 5);
1199         assert_eq!(b.len(), 0);
1200         // Capacity shouldn't change for possible reuse
1201         assert!(b.capacity() >= 4);
1202
1203         assert_eq!(a[1], "a");
1204         assert_eq!(a[2], "b");
1205         assert_eq!(a[3], "d");
1206         assert_eq!(a[4], "e");
1207         assert_eq!(a[5], "f");
1208     }
1209
1210     #[test]
1211     fn test_split_off() {
1212         // Split within the key range
1213         let mut a = VecMap::new();
1214         a.insert(1, "a");
1215         a.insert(2, "b");
1216         a.insert(3, "c");
1217         a.insert(4, "d");
1218
1219         let b = a.split_off(3);
1220
1221         assert_eq!(a.len(), 2);
1222         assert_eq!(b.len(), 2);
1223
1224         assert_eq!(a[1], "a");
1225         assert_eq!(a[2], "b");
1226
1227         assert_eq!(b[3], "c");
1228         assert_eq!(b[4], "d");
1229
1230         // Split at 0
1231         a.clear();
1232         a.insert(1, "a");
1233         a.insert(2, "b");
1234         a.insert(3, "c");
1235         a.insert(4, "d");
1236
1237         let b = a.split_off(0);
1238
1239         assert_eq!(a.len(), 0);
1240         assert_eq!(b.len(), 4);
1241         assert_eq!(b[1], "a");
1242         assert_eq!(b[2], "b");
1243         assert_eq!(b[3], "c");
1244         assert_eq!(b[4], "d");
1245
1246         // Split behind max_key
1247         a.clear();
1248         a.insert(1, "a");
1249         a.insert(2, "b");
1250         a.insert(3, "c");
1251         a.insert(4, "d");
1252
1253         let b = a.split_off(5);
1254
1255         assert_eq!(a.len(), 4);
1256         assert_eq!(b.len(), 0);
1257         assert_eq!(a[1], "a");
1258         assert_eq!(a[2], "b");
1259         assert_eq!(a[3], "c");
1260         assert_eq!(a[4], "d");
1261     }
1262
1263     #[test]
1264     fn test_show() {
1265         let mut map = VecMap::new();
1266         let empty = VecMap::<i32>::new();
1267
1268         map.insert(1, 2);
1269         map.insert(3, 4);
1270
1271         let map_str = format!("{:?}", map);
1272         assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
1273         assert_eq!(format!("{:?}", empty), "{}");
1274     }
1275
1276     #[test]
1277     fn test_clone() {
1278         let mut a = VecMap::new();
1279
1280         a.insert(1, 'x');
1281         a.insert(4, 'y');
1282         a.insert(6, 'z');
1283
1284         assert_eq!(a.clone().iter().collect::<Vec<_>>(), [(1, &'x'), (4, &'y'), (6, &'z')]);
1285     }
1286
1287     #[test]
1288     fn test_eq() {
1289         let mut a = VecMap::new();
1290         let mut b = VecMap::new();
1291
1292         assert!(a == b);
1293         assert!(a.insert(0, 5).is_none());
1294         assert!(a != b);
1295         assert!(b.insert(0, 4).is_none());
1296         assert!(a != b);
1297         assert!(a.insert(5, 19).is_none());
1298         assert!(a != b);
1299         assert!(!b.insert(0, 5).is_none());
1300         assert!(a != b);
1301         assert!(b.insert(5, 19).is_none());
1302         assert!(a == b);
1303
1304         a = VecMap::new();
1305         b = VecMap::with_capacity(1);
1306         assert!(a == b);
1307     }
1308
1309     #[test]
1310     fn test_lt() {
1311         let mut a = VecMap::new();
1312         let mut b = VecMap::new();
1313
1314         assert!(!(a < b) && !(b < a));
1315         assert!(b.insert(2, 5).is_none());
1316         assert!(a < b);
1317         assert!(a.insert(2, 7).is_none());
1318         assert!(!(a < b) && b < a);
1319         assert!(b.insert(1, 0).is_none());
1320         assert!(b < a);
1321         assert!(a.insert(0, 6).is_none());
1322         assert!(a < b);
1323         assert!(a.insert(6, 2).is_none());
1324         assert!(a < b && !(b < a));
1325     }
1326
1327     #[test]
1328     fn test_ord() {
1329         let mut a = VecMap::new();
1330         let mut b = VecMap::new();
1331
1332         assert!(a <= b && a >= b);
1333         assert!(a.insert(1, 1).is_none());
1334         assert!(a > b && a >= b);
1335         assert!(b < a && b <= a);
1336         assert!(b.insert(2, 2).is_none());
1337         assert!(b > a && b >= a);
1338         assert!(a < b && a <= b);
1339     }
1340
1341     #[test]
1342     fn test_hash() {
1343         fn hash<T: Hash>(t: &T) -> u64 {
1344             let mut s = SipHasher::new();
1345             t.hash(&mut s);
1346             s.finish()
1347         }
1348
1349         let mut x = VecMap::new();
1350         let mut y = VecMap::new();
1351
1352         assert!(hash(&x) == hash(&y));
1353         x.insert(1, 'a');
1354         x.insert(2, 'b');
1355         x.insert(3, 'c');
1356
1357         y.insert(3, 'c');
1358         y.insert(2, 'b');
1359         y.insert(1, 'a');
1360
1361         assert!(hash(&x) == hash(&y));
1362
1363         x.insert(1000, 'd');
1364         x.remove(1000);
1365
1366         assert!(hash(&x) == hash(&y));
1367     }
1368
1369     #[test]
1370     fn test_from_iter() {
1371         let xs = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')];
1372
1373         let map: VecMap<_> = xs.iter().cloned().collect();
1374
1375         for &(k, v) in &xs {
1376             assert_eq!(map.get(k), Some(&v));
1377         }
1378     }
1379
1380     #[test]
1381     fn test_index() {
1382         let mut map = VecMap::new();
1383
1384         map.insert(1, 2);
1385         map.insert(2, 1);
1386         map.insert(3, 4);
1387
1388         assert_eq!(map[3], 4);
1389     }
1390
1391     #[test]
1392     #[should_panic]
1393     fn test_index_nonexistent() {
1394         let mut map = VecMap::new();
1395
1396         map.insert(1, 2);
1397         map.insert(2, 1);
1398         map.insert(3, 4);
1399
1400         map[4];
1401     }
1402
1403     #[test]
1404     fn test_entry() {
1405         let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1406
1407         let mut map: VecMap<_> = xs.iter().cloned().collect();
1408
1409         // Existing key (insert)
1410         match map.entry(1) {
1411             Vacant(_) => unreachable!(),
1412             Occupied(mut view) => {
1413                 assert_eq!(view.get(), &10);
1414                 assert_eq!(view.insert(100), 10);
1415             }
1416         }
1417
1418         assert_eq!(map.get(1).unwrap(), &100);
1419         assert_eq!(map.len(), 6);
1420
1421         // Existing key (update)
1422         match map.entry(2) {
1423             Vacant(_) => unreachable!(),
1424             Occupied(mut view) => {
1425                 let v = view.get_mut();
1426                 *v *= 10;
1427             }
1428         }
1429
1430         assert_eq!(map.get(2).unwrap(), &200);
1431         assert_eq!(map.len(), 6);
1432
1433         // Existing key (take)
1434         match map.entry(3) {
1435             Vacant(_) => unreachable!(),
1436             Occupied(view) => {
1437                 assert_eq!(view.remove(), 30);
1438             }
1439         }
1440
1441         assert_eq!(map.get(3), None);
1442         assert_eq!(map.len(), 5);
1443
1444         // Inexistent key (insert)
1445         match map.entry(10) {
1446             Occupied(_) => unreachable!(),
1447             Vacant(view) => {
1448                 assert_eq!(*view.insert(1000), 1000);
1449             }
1450         }
1451
1452         assert_eq!(map.get(10).unwrap(), &1000);
1453         assert_eq!(map.len(), 6);
1454     }
1455
1456     #[test]
1457     fn test_extend_ref() {
1458         let mut a = VecMap::new();
1459         a.insert(1, "one");
1460         let mut b = VecMap::new();
1461         b.insert(2, "two");
1462         b.insert(3, "three");
1463
1464         a.extend(&b);
1465
1466         assert_eq!(a.len(), 3);
1467         assert_eq!(a[&1], "one");
1468         assert_eq!(a[&2], "two");
1469         assert_eq!(a[&3], "three");
1470     }
1471
1472     #[test]
1473     #[cfg(feature = "eders")]
1474     fn test_serde() {
1475         use serde::{Serialize, Deserialize};
1476         fn impls_serde_traits<S: Serialize + Deserialize>() {}
1477
1478         impls_serde_traits::<VecMap<u32>>();
1479     }
1480 }