1 //! `IndexMap` is a hash table where the iteration order of the key-value 2 //! pairs is independent of the hash values of the keys. 3 4 mod core; 5 6 #[cfg(not(has_std))] 7 use std::vec::Vec; 8 9 pub use mutable_keys::MutableKeys; 10 11 #[cfg(feature = "rayon")] 12 pub use rayon::map as rayon; 13 14 use std::hash::BuildHasher; 15 use std::hash::Hash; 16 use std::hash::Hasher; 17 use std::iter::FromIterator; 18 use std::ops::RangeFull; 19 20 #[cfg(has_std)] 21 use std::collections::hash_map::RandomState; 22 23 use std::cmp::Ordering; 24 use std::fmt; 25 26 use self::core::IndexMapCore; 27 use equivalent::Equivalent; 28 use util::third; 29 use {Bucket, Entries, HashValue}; 30 31 pub use self::core::{Entry, OccupiedEntry, VacantEntry}; 32 33 /// A hash table where the iteration order of the key-value pairs is independent 34 /// of the hash values of the keys. 35 /// 36 /// The interface is closely compatible with the standard `HashMap`, but also 37 /// has additional features. 38 /// 39 /// # Order 40 /// 41 /// The key-value pairs have a consistent order that is determined by 42 /// the sequence of insertion and removal calls on the map. The order does 43 /// not depend on the keys or the hash function at all. 44 /// 45 /// All iterators traverse the map in *the order*. 46 /// 47 /// The insertion order is preserved, with **notable exceptions** like the 48 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of 49 /// course result in a new order, depending on the sorting order. 50 /// 51 /// # Indices 52 /// 53 /// The key-value pairs are indexed in a compact range without holes in the 54 /// range `0..self.len()`. For example, the method `.get_full` looks up the 55 /// index for a key, and the method `.get_index` looks up the key-value pair by 56 /// index. 57 /// 58 /// # Examples 59 /// 60 /// ``` 61 /// use indexmap::IndexMap; 62 /// 63 /// // count the frequency of each letter in a sentence. 64 /// let mut letters = IndexMap::new(); 65 /// for ch in "a short treatise on fungi".chars() { 66 /// *letters.entry(ch).or_insert(0) += 1; 67 /// } 68 /// 69 /// assert_eq!(letters[&'s'], 2); 70 /// assert_eq!(letters[&'t'], 3); 71 /// assert_eq!(letters[&'u'], 1); 72 /// assert_eq!(letters.get(&'y'), None); 73 /// ``` 74 #[cfg(has_std)] 75 pub struct IndexMap<K, V, S = RandomState> { 76 core: IndexMapCore<K, V>, 77 hash_builder: S, 78 } 79 #[cfg(not(has_std))] 80 pub struct IndexMap<K, V, S> { 81 core: IndexMapCore<K, V>, 82 hash_builder: S, 83 } 84 85 impl<K, V, S> Clone for IndexMap<K, V, S> 86 where 87 K: Clone, 88 V: Clone, 89 S: Clone, 90 { clone(&self) -> Self91 fn clone(&self) -> Self { 92 IndexMap { 93 core: self.core.clone(), 94 hash_builder: self.hash_builder.clone(), 95 } 96 } 97 clone_from(&mut self, other: &Self)98 fn clone_from(&mut self, other: &Self) { 99 self.core.clone_from(&other.core); 100 self.hash_builder.clone_from(&other.hash_builder); 101 } 102 } 103 104 impl<K, V, S> Entries for IndexMap<K, V, S> { 105 type Entry = Bucket<K, V>; 106 107 #[inline] into_entries(self) -> Vec<Self::Entry>108 fn into_entries(self) -> Vec<Self::Entry> { 109 self.core.into_entries() 110 } 111 112 #[inline] as_entries(&self) -> &[Self::Entry]113 fn as_entries(&self) -> &[Self::Entry] { 114 self.core.as_entries() 115 } 116 117 #[inline] as_entries_mut(&mut self) -> &mut [Self::Entry]118 fn as_entries_mut(&mut self) -> &mut [Self::Entry] { 119 self.core.as_entries_mut() 120 } 121 with_entries<F>(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]),122 fn with_entries<F>(&mut self, f: F) 123 where 124 F: FnOnce(&mut [Self::Entry]), 125 { 126 self.core.with_entries(f); 127 } 128 } 129 130 impl<K, V, S> fmt::Debug for IndexMap<K, V, S> 131 where 132 K: fmt::Debug + Hash + Eq, 133 V: fmt::Debug, 134 S: BuildHasher, 135 { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result136 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 137 if cfg!(not(feature = "test_debug")) { 138 f.debug_map().entries(self.iter()).finish() 139 } else { 140 // Let the inner `IndexMapCore` print all of its details 141 f.debug_struct("IndexMap") 142 .field("core", &self.core) 143 .finish() 144 } 145 } 146 } 147 148 #[cfg(has_std)] 149 impl<K, V> IndexMap<K, V> { 150 /// Create a new map. (Does not allocate.) 151 #[inline] new() -> Self152 pub fn new() -> Self { 153 Self::with_capacity(0) 154 } 155 156 /// Create a new map with capacity for `n` key-value pairs. (Does not 157 /// allocate if `n` is zero.) 158 /// 159 /// Computes in **O(n)** time. 160 #[inline] with_capacity(n: usize) -> Self161 pub fn with_capacity(n: usize) -> Self { 162 Self::with_capacity_and_hasher(n, <_>::default()) 163 } 164 } 165 166 impl<K, V, S> IndexMap<K, V, S> { 167 /// Create a new map with capacity for `n` key-value pairs. (Does not 168 /// allocate if `n` is zero.) 169 /// 170 /// Computes in **O(n)** time. 171 #[inline] with_capacity_and_hasher(n: usize, hash_builder: S) -> Self where S: BuildHasher,172 pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self 173 where 174 S: BuildHasher, 175 { 176 if n == 0 { 177 IndexMap { 178 core: IndexMapCore::new(), 179 hash_builder, 180 } 181 } else { 182 IndexMap { 183 core: IndexMapCore::with_capacity(n), 184 hash_builder, 185 } 186 } 187 } 188 189 /// Return the number of key-value pairs in the map. 190 /// 191 /// Computes in **O(1)** time. 192 #[inline] len(&self) -> usize193 pub fn len(&self) -> usize { 194 self.core.len() 195 } 196 197 /// Returns true if the map contains no elements. 198 /// 199 /// Computes in **O(1)** time. 200 #[inline] is_empty(&self) -> bool201 pub fn is_empty(&self) -> bool { 202 self.len() == 0 203 } 204 205 /// Create a new map with `hash_builder` with_hasher(hash_builder: S) -> Self where S: BuildHasher,206 pub fn with_hasher(hash_builder: S) -> Self 207 where 208 S: BuildHasher, 209 { 210 Self::with_capacity_and_hasher(0, hash_builder) 211 } 212 213 /// Return a reference to the map's `BuildHasher`. hasher(&self) -> &S where S: BuildHasher,214 pub fn hasher(&self) -> &S 215 where 216 S: BuildHasher, 217 { 218 &self.hash_builder 219 } 220 221 /// Computes in **O(1)** time. capacity(&self) -> usize222 pub fn capacity(&self) -> usize { 223 self.core.capacity() 224 } 225 } 226 227 impl<K, V, S> IndexMap<K, V, S> 228 where 229 K: Hash + Eq, 230 S: BuildHasher, 231 { 232 /// Remove all key-value pairs in the map, while preserving its capacity. 233 /// 234 /// Computes in **O(n)** time. clear(&mut self)235 pub fn clear(&mut self) { 236 self.core.clear(); 237 } 238 239 /// Reserve capacity for `additional` more key-value pairs. 240 /// 241 /// Computes in **O(n)** time. reserve(&mut self, additional: usize)242 pub fn reserve(&mut self, additional: usize) { 243 self.core.reserve(additional); 244 } 245 246 /// Shrink the capacity of the map as much as possible. 247 /// 248 /// Computes in **O(n)** time. shrink_to_fit(&mut self)249 pub fn shrink_to_fit(&mut self) { 250 self.core.shrink_to_fit(); 251 } 252 hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue253 fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue { 254 let mut h = self.hash_builder.build_hasher(); 255 key.hash(&mut h); 256 HashValue(h.finish() as usize) 257 } 258 259 /// Insert a key-value pair in the map. 260 /// 261 /// If an equivalent key already exists in the map: the key remains and 262 /// retains in its place in the order, its corresponding value is updated 263 /// with `value` and the older value is returned inside `Some(_)`. 264 /// 265 /// If no equivalent key existed in the map: the new key-value pair is 266 /// inserted, last in order, and `None` is returned. 267 /// 268 /// Computes in **O(1)** time (amortized average). 269 /// 270 /// See also [`entry`](#method.entry) if you you want to insert *or* modify 271 /// or if you need to get the index of the corresponding key-value pair. insert(&mut self, key: K, value: V) -> Option<V>272 pub fn insert(&mut self, key: K, value: V) -> Option<V> { 273 self.insert_full(key, value).1 274 } 275 276 /// Insert a key-value pair in the map, and get their index. 277 /// 278 /// If an equivalent key already exists in the map: the key remains and 279 /// retains in its place in the order, its corresponding value is updated 280 /// with `value` and the older value is returned inside `(index, Some(_))`. 281 /// 282 /// If no equivalent key existed in the map: the new key-value pair is 283 /// inserted, last in order, and `(index, None)` is returned. 284 /// 285 /// Computes in **O(1)** time (amortized average). 286 /// 287 /// See also [`entry`](#method.entry) if you you want to insert *or* modify 288 /// or if you need to get the index of the corresponding key-value pair. insert_full(&mut self, key: K, value: V) -> (usize, Option<V>)289 pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) { 290 let hash = self.hash(&key); 291 self.core.insert_full(hash, key, value) 292 } 293 294 /// Get the given key’s corresponding entry in the map for insertion and/or 295 /// in-place manipulation. 296 /// 297 /// Computes in **O(1)** time (amortized average). entry(&mut self, key: K) -> Entry<K, V>298 pub fn entry(&mut self, key: K) -> Entry<K, V> { 299 let hash = self.hash(&key); 300 self.core.entry(hash, key) 301 } 302 303 /// Return an iterator over the key-value pairs of the map, in their order iter(&self) -> Iter<K, V>304 pub fn iter(&self) -> Iter<K, V> { 305 Iter { 306 iter: self.as_entries().iter(), 307 } 308 } 309 310 /// Return an iterator over the key-value pairs of the map, in their order iter_mut(&mut self) -> IterMut<K, V>311 pub fn iter_mut(&mut self) -> IterMut<K, V> { 312 IterMut { 313 iter: self.as_entries_mut().iter_mut(), 314 } 315 } 316 317 /// Return an iterator over the keys of the map, in their order keys(&self) -> Keys<K, V>318 pub fn keys(&self) -> Keys<K, V> { 319 Keys { 320 iter: self.as_entries().iter(), 321 } 322 } 323 324 /// Return an iterator over the values of the map, in their order values(&self) -> Values<K, V>325 pub fn values(&self) -> Values<K, V> { 326 Values { 327 iter: self.as_entries().iter(), 328 } 329 } 330 331 /// Return an iterator over mutable references to the the values of the map, 332 /// in their order values_mut(&mut self) -> ValuesMut<K, V>333 pub fn values_mut(&mut self) -> ValuesMut<K, V> { 334 ValuesMut { 335 iter: self.as_entries_mut().iter_mut(), 336 } 337 } 338 339 /// Return `true` if an equivalent to `key` exists in the map. 340 /// 341 /// Computes in **O(1)** time (average). contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: Hash + Equivalent<K>,342 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool 343 where 344 Q: Hash + Equivalent<K>, 345 { 346 self.get_index_of(key).is_some() 347 } 348 349 /// Return a reference to the value stored for `key`, if it is present, 350 /// else `None`. 351 /// 352 /// Computes in **O(1)** time (average). get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: Hash + Equivalent<K>,353 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> 354 where 355 Q: Hash + Equivalent<K>, 356 { 357 if let Some(i) = self.get_index_of(key) { 358 let entry = &self.as_entries()[i]; 359 Some(&entry.value) 360 } else { 361 None 362 } 363 } 364 365 /// Return references to the key-value pair stored for `key`, 366 /// if it is present, else `None`. 367 /// 368 /// Computes in **O(1)** time (average). get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)> where Q: Hash + Equivalent<K>,369 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)> 370 where 371 Q: Hash + Equivalent<K>, 372 { 373 if let Some(i) = self.get_index_of(key) { 374 let entry = &self.as_entries()[i]; 375 Some((&entry.key, &entry.value)) 376 } else { 377 None 378 } 379 } 380 381 /// Return item index, key and value get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> where Q: Hash + Equivalent<K>,382 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> 383 where 384 Q: Hash + Equivalent<K>, 385 { 386 if let Some(i) = self.get_index_of(key) { 387 let entry = &self.as_entries()[i]; 388 Some((i, &entry.key, &entry.value)) 389 } else { 390 None 391 } 392 } 393 394 /// Return item index, if it exists in the map get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize> where Q: Hash + Equivalent<K>,395 pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize> 396 where 397 Q: Hash + Equivalent<K>, 398 { 399 if self.is_empty() { 400 None 401 } else { 402 let hash = self.hash(key); 403 self.core.get_index_of(hash, key) 404 } 405 } 406 get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: Hash + Equivalent<K>,407 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> 408 where 409 Q: Hash + Equivalent<K>, 410 { 411 if let Some(i) = self.get_index_of(key) { 412 let entry = &mut self.as_entries_mut()[i]; 413 Some(&mut entry.value) 414 } else { 415 None 416 } 417 } 418 get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> where Q: Hash + Equivalent<K>,419 pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> 420 where 421 Q: Hash + Equivalent<K>, 422 { 423 if let Some(i) = self.get_index_of(key) { 424 let entry = &mut self.as_entries_mut()[i]; 425 Some((i, &entry.key, &mut entry.value)) 426 } else { 427 None 428 } 429 } 430 get_full_mut2_impl<Q: ?Sized>( &mut self, key: &Q, ) -> Option<(usize, &mut K, &mut V)> where Q: Hash + Equivalent<K>,431 pub(crate) fn get_full_mut2_impl<Q: ?Sized>( 432 &mut self, 433 key: &Q, 434 ) -> Option<(usize, &mut K, &mut V)> 435 where 436 Q: Hash + Equivalent<K>, 437 { 438 if let Some(i) = self.get_index_of(key) { 439 let entry = &mut self.as_entries_mut()[i]; 440 Some((i, &mut entry.key, &mut entry.value)) 441 } else { 442 None 443 } 444 } 445 446 /// Remove the key-value pair equivalent to `key` and return 447 /// its value. 448 /// 449 /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to 450 /// preserve the order of the keys in the map, use `.shift_remove(key)` 451 /// instead. 452 /// 453 /// Computes in **O(1)** time (average). remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,454 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 455 where 456 Q: Hash + Equivalent<K>, 457 { 458 self.swap_remove(key) 459 } 460 461 /// Remove and return the key-value pair equivalent to `key`. 462 /// 463 /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to 464 /// preserve the order of the keys in the map, use `.shift_remove_entry(key)` 465 /// instead. 466 /// 467 /// Computes in **O(1)** time (average). remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where Q: Hash + Equivalent<K>,468 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> 469 where 470 Q: Hash + Equivalent<K>, 471 { 472 self.swap_remove_entry(key) 473 } 474 475 /// Remove the key-value pair equivalent to `key` and return 476 /// its value. 477 /// 478 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 479 /// last element of the map and popping it off. **This perturbs 480 /// the postion of what used to be the last element!** 481 /// 482 /// Return `None` if `key` is not in map. 483 /// 484 /// Computes in **O(1)** time (average). swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,485 pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 486 where 487 Q: Hash + Equivalent<K>, 488 { 489 self.swap_remove_full(key).map(third) 490 } 491 492 /// Remove and return the key-value pair equivalent to `key`. 493 /// 494 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 495 /// last element of the map and popping it off. **This perturbs 496 /// the postion of what used to be the last element!** 497 /// 498 /// Return `None` if `key` is not in map. 499 /// 500 /// Computes in **O(1)** time (average). swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where Q: Hash + Equivalent<K>,501 pub fn swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> 502 where 503 Q: Hash + Equivalent<K>, 504 { 505 match self.swap_remove_full(key) { 506 Some((_, key, value)) => Some((key, value)), 507 None => None, 508 } 509 } 510 511 /// Remove the key-value pair equivalent to `key` and return it and 512 /// the index it had. 513 /// 514 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 515 /// last element of the map and popping it off. **This perturbs 516 /// the postion of what used to be the last element!** 517 /// 518 /// Return `None` if `key` is not in map. 519 /// 520 /// Computes in **O(1)** time (average). swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> where Q: Hash + Equivalent<K>,521 pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> 522 where 523 Q: Hash + Equivalent<K>, 524 { 525 if self.is_empty() { 526 return None; 527 } 528 let hash = self.hash(key); 529 self.core.swap_remove_full(hash, key) 530 } 531 532 /// Remove the key-value pair equivalent to `key` and return 533 /// its value. 534 /// 535 /// Like `Vec::remove`, the pair is removed by shifting all of the 536 /// elements that follow it, preserving their relative order. 537 /// **This perturbs the index of all of those elements!** 538 /// 539 /// Return `None` if `key` is not in map. 540 /// 541 /// Computes in **O(n)** time (average). shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,542 pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 543 where 544 Q: Hash + Equivalent<K>, 545 { 546 self.shift_remove_full(key).map(third) 547 } 548 549 /// Remove and return the key-value pair equivalent to `key`. 550 /// 551 /// Like `Vec::remove`, the pair is removed by shifting all of the 552 /// elements that follow it, preserving their relative order. 553 /// **This perturbs the index of all of those elements!** 554 /// 555 /// Return `None` if `key` is not in map. 556 /// 557 /// Computes in **O(n)** time (average). shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where Q: Hash + Equivalent<K>,558 pub fn shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> 559 where 560 Q: Hash + Equivalent<K>, 561 { 562 match self.shift_remove_full(key) { 563 Some((_, key, value)) => Some((key, value)), 564 None => None, 565 } 566 } 567 568 /// Remove the key-value pair equivalent to `key` and return it and 569 /// the index it had. 570 /// 571 /// Like `Vec::remove`, the pair is removed by shifting all of the 572 /// elements that follow it, preserving their relative order. 573 /// **This perturbs the index of all of those elements!** 574 /// 575 /// Return `None` if `key` is not in map. 576 /// 577 /// Computes in **O(n)** time (average). shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> where Q: Hash + Equivalent<K>,578 pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> 579 where 580 Q: Hash + Equivalent<K>, 581 { 582 if self.is_empty() { 583 return None; 584 } 585 let hash = self.hash(key); 586 self.core.shift_remove_full(hash, key) 587 } 588 589 /// Remove the last key-value pair 590 /// 591 /// Computes in **O(1)** time (average). pop(&mut self) -> Option<(K, V)>592 pub fn pop(&mut self) -> Option<(K, V)> { 593 self.core.pop() 594 } 595 596 /// Scan through each key-value pair in the map and keep those where the 597 /// closure `keep` returns `true`. 598 /// 599 /// The elements are visited in order, and remaining elements keep their 600 /// order. 601 /// 602 /// Computes in **O(n)** time (average). retain<F>(&mut self, mut keep: F) where F: FnMut(&K, &mut V) -> bool,603 pub fn retain<F>(&mut self, mut keep: F) 604 where 605 F: FnMut(&K, &mut V) -> bool, 606 { 607 self.core.retain_in_order(move |k, v| keep(k, v)); 608 } 609 retain_mut<F>(&mut self, keep: F) where F: FnMut(&mut K, &mut V) -> bool,610 pub(crate) fn retain_mut<F>(&mut self, keep: F) 611 where 612 F: FnMut(&mut K, &mut V) -> bool, 613 { 614 self.core.retain_in_order(keep); 615 } 616 617 /// Sort the map’s key-value pairs by the default ordering of the keys. 618 /// 619 /// See `sort_by` for details. sort_keys(&mut self) where K: Ord,620 pub fn sort_keys(&mut self) 621 where 622 K: Ord, 623 { 624 self.with_entries(|entries| { 625 entries.sort_by(|a, b| Ord::cmp(&a.key, &b.key)); 626 }); 627 } 628 629 /// Sort the map’s key-value pairs in place using the comparison 630 /// function `compare`. 631 /// 632 /// The comparison function receives two key and value pairs to compare (you 633 /// can sort by keys or values or their combination as needed). 634 /// 635 /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is 636 /// the length of the map and *c* the capacity. The sort is stable. sort_by<F>(&mut self, mut cmp: F) where F: FnMut(&K, &V, &K, &V) -> Ordering,637 pub fn sort_by<F>(&mut self, mut cmp: F) 638 where 639 F: FnMut(&K, &V, &K, &V) -> Ordering, 640 { 641 self.with_entries(move |entries| { 642 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); 643 }); 644 } 645 646 /// Sort the key-value pairs of the map and return a by value iterator of 647 /// the key-value pairs with the result. 648 /// 649 /// The sort is stable. sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V> where F: FnMut(&K, &V, &K, &V) -> Ordering,650 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V> 651 where 652 F: FnMut(&K, &V, &K, &V) -> Ordering, 653 { 654 let mut entries = self.into_entries(); 655 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); 656 IntoIter { 657 iter: entries.into_iter(), 658 } 659 } 660 661 /// Reverses the order of the map’s key-value pairs in place. 662 /// 663 /// Computes in **O(n)** time and **O(1)** space. reverse(&mut self)664 pub fn reverse(&mut self) { 665 self.core.reverse() 666 } 667 668 /// Clears the `IndexMap`, returning all key-value pairs as a drain iterator. 669 /// Keeps the allocated memory for reuse. drain(&mut self, range: RangeFull) -> Drain<K, V>670 pub fn drain(&mut self, range: RangeFull) -> Drain<K, V> { 671 Drain { 672 iter: self.core.drain(range), 673 } 674 } 675 } 676 677 impl<K, V, S> IndexMap<K, V, S> { 678 /// Get a key-value pair by index 679 /// 680 /// Valid indices are *0 <= index < self.len()* 681 /// 682 /// Computes in **O(1)** time. get_index(&self, index: usize) -> Option<(&K, &V)>683 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { 684 self.as_entries().get(index).map(Bucket::refs) 685 } 686 687 /// Get a key-value pair by index 688 /// 689 /// Valid indices are *0 <= index < self.len()* 690 /// 691 /// Computes in **O(1)** time. get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)>692 pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> { 693 self.as_entries_mut().get_mut(index).map(Bucket::muts) 694 } 695 696 /// Remove the key-value pair by index 697 /// 698 /// Valid indices are *0 <= index < self.len()* 699 /// 700 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 701 /// last element of the map and popping it off. **This perturbs 702 /// the postion of what used to be the last element!** 703 /// 704 /// Computes in **O(1)** time (average). swap_remove_index(&mut self, index: usize) -> Option<(K, V)>705 pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { 706 self.core.swap_remove_index(index) 707 } 708 709 /// Remove the key-value pair by index 710 /// 711 /// Valid indices are *0 <= index < self.len()* 712 /// 713 /// Like `Vec::remove`, the pair is removed by shifting all of the 714 /// elements that follow it, preserving their relative order. 715 /// **This perturbs the index of all of those elements!** 716 /// 717 /// Computes in **O(n)** time (average). shift_remove_index(&mut self, index: usize) -> Option<(K, V)>718 pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { 719 self.core.shift_remove_index(index) 720 } 721 } 722 723 use std::slice::Iter as SliceIter; 724 use std::slice::IterMut as SliceIterMut; 725 use std::vec::IntoIter as VecIntoIter; 726 727 /// An iterator over the keys of a `IndexMap`. 728 /// 729 /// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its 730 /// documentation for more. 731 /// 732 /// [`keys`]: struct.IndexMap.html#method.keys 733 /// [`IndexMap`]: struct.IndexMap.html 734 pub struct Keys<'a, K: 'a, V: 'a> { 735 pub(crate) iter: SliceIter<'a, Bucket<K, V>>, 736 } 737 738 impl<'a, K, V> Iterator for Keys<'a, K, V> { 739 type Item = &'a K; 740 741 iterator_methods!(Bucket::key_ref); 742 } 743 744 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { next_back(&mut self) -> Option<&'a K>745 fn next_back(&mut self) -> Option<&'a K> { 746 self.iter.next_back().map(Bucket::key_ref) 747 } 748 } 749 750 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> { len(&self) -> usize751 fn len(&self) -> usize { 752 self.iter.len() 753 } 754 } 755 756 // FIXME(#26925) Remove in favor of `#[derive(Clone)]` 757 impl<'a, K, V> Clone for Keys<'a, K, V> { clone(&self) -> Keys<'a, K, V>758 fn clone(&self) -> Keys<'a, K, V> { 759 Keys { 760 iter: self.iter.clone(), 761 } 762 } 763 } 764 765 impl<'a, K: fmt::Debug, V> fmt::Debug for Keys<'a, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result766 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 767 f.debug_list().entries(self.clone()).finish() 768 } 769 } 770 771 /// An iterator over the values of a `IndexMap`. 772 /// 773 /// This `struct` is created by the [`values`] method on [`IndexMap`]. See its 774 /// documentation for more. 775 /// 776 /// [`values`]: struct.IndexMap.html#method.values 777 /// [`IndexMap`]: struct.IndexMap.html 778 pub struct Values<'a, K: 'a, V: 'a> { 779 iter: SliceIter<'a, Bucket<K, V>>, 780 } 781 782 impl<'a, K, V> Iterator for Values<'a, K, V> { 783 type Item = &'a V; 784 785 iterator_methods!(Bucket::value_ref); 786 } 787 788 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { next_back(&mut self) -> Option<Self::Item>789 fn next_back(&mut self) -> Option<Self::Item> { 790 self.iter.next_back().map(Bucket::value_ref) 791 } 792 } 793 794 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> { len(&self) -> usize795 fn len(&self) -> usize { 796 self.iter.len() 797 } 798 } 799 800 // FIXME(#26925) Remove in favor of `#[derive(Clone)]` 801 impl<'a, K, V> Clone for Values<'a, K, V> { clone(&self) -> Values<'a, K, V>802 fn clone(&self) -> Values<'a, K, V> { 803 Values { 804 iter: self.iter.clone(), 805 } 806 } 807 } 808 809 impl<'a, K, V: fmt::Debug> fmt::Debug for Values<'a, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result810 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 811 f.debug_list().entries(self.clone()).finish() 812 } 813 } 814 815 /// A mutable iterator over the values of a `IndexMap`. 816 /// 817 /// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its 818 /// documentation for more. 819 /// 820 /// [`values_mut`]: struct.IndexMap.html#method.values_mut 821 /// [`IndexMap`]: struct.IndexMap.html 822 pub struct ValuesMut<'a, K: 'a, V: 'a> { 823 iter: SliceIterMut<'a, Bucket<K, V>>, 824 } 825 826 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { 827 type Item = &'a mut V; 828 829 iterator_methods!(Bucket::value_mut); 830 } 831 832 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> { next_back(&mut self) -> Option<Self::Item>833 fn next_back(&mut self) -> Option<Self::Item> { 834 self.iter.next_back().map(Bucket::value_mut) 835 } 836 } 837 838 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> { len(&self) -> usize839 fn len(&self) -> usize { 840 self.iter.len() 841 } 842 } 843 844 /// An iterator over the entries of a `IndexMap`. 845 /// 846 /// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its 847 /// documentation for more. 848 /// 849 /// [`iter`]: struct.IndexMap.html#method.iter 850 /// [`IndexMap`]: struct.IndexMap.html 851 pub struct Iter<'a, K: 'a, V: 'a> { 852 iter: SliceIter<'a, Bucket<K, V>>, 853 } 854 855 impl<'a, K, V> Iterator for Iter<'a, K, V> { 856 type Item = (&'a K, &'a V); 857 858 iterator_methods!(Bucket::refs); 859 } 860 861 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> { next_back(&mut self) -> Option<Self::Item>862 fn next_back(&mut self) -> Option<Self::Item> { 863 self.iter.next_back().map(Bucket::refs) 864 } 865 } 866 867 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { len(&self) -> usize868 fn len(&self) -> usize { 869 self.iter.len() 870 } 871 } 872 873 // FIXME(#26925) Remove in favor of `#[derive(Clone)]` 874 impl<'a, K, V> Clone for Iter<'a, K, V> { clone(&self) -> Iter<'a, K, V>875 fn clone(&self) -> Iter<'a, K, V> { 876 Iter { 877 iter: self.iter.clone(), 878 } 879 } 880 } 881 882 impl<'a, K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'a, K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result883 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 884 f.debug_list().entries(self.clone()).finish() 885 } 886 } 887 888 /// A mutable iterator over the entries of a `IndexMap`. 889 /// 890 /// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its 891 /// documentation for more. 892 /// 893 /// [`iter_mut`]: struct.IndexMap.html#method.iter_mut 894 /// [`IndexMap`]: struct.IndexMap.html 895 pub struct IterMut<'a, K: 'a, V: 'a> { 896 iter: SliceIterMut<'a, Bucket<K, V>>, 897 } 898 899 impl<'a, K, V> Iterator for IterMut<'a, K, V> { 900 type Item = (&'a K, &'a mut V); 901 902 iterator_methods!(Bucket::ref_mut); 903 } 904 905 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> { next_back(&mut self) -> Option<Self::Item>906 fn next_back(&mut self) -> Option<Self::Item> { 907 self.iter.next_back().map(Bucket::ref_mut) 908 } 909 } 910 911 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { len(&self) -> usize912 fn len(&self) -> usize { 913 self.iter.len() 914 } 915 } 916 917 /// An owning iterator over the entries of a `IndexMap`. 918 /// 919 /// This `struct` is created by the [`into_iter`] method on [`IndexMap`] 920 /// (provided by the `IntoIterator` trait). See its documentation for more. 921 /// 922 /// [`into_iter`]: struct.IndexMap.html#method.into_iter 923 /// [`IndexMap`]: struct.IndexMap.html 924 pub struct IntoIter<K, V> { 925 pub(crate) iter: VecIntoIter<Bucket<K, V>>, 926 } 927 928 impl<K, V> Iterator for IntoIter<K, V> { 929 type Item = (K, V); 930 931 iterator_methods!(Bucket::key_value); 932 } 933 934 impl<'a, K, V> DoubleEndedIterator for IntoIter<K, V> { next_back(&mut self) -> Option<Self::Item>935 fn next_back(&mut self) -> Option<Self::Item> { 936 self.iter.next_back().map(Bucket::key_value) 937 } 938 } 939 940 impl<K, V> ExactSizeIterator for IntoIter<K, V> { len(&self) -> usize941 fn len(&self) -> usize { 942 self.iter.len() 943 } 944 } 945 946 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result947 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 948 let iter = self.iter.as_slice().iter().map(Bucket::refs); 949 f.debug_list().entries(iter).finish() 950 } 951 } 952 953 /// A draining iterator over the entries of a `IndexMap`. 954 /// 955 /// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its 956 /// documentation for more. 957 /// 958 /// [`drain`]: struct.IndexMap.html#method.drain 959 /// [`IndexMap`]: struct.IndexMap.html 960 pub struct Drain<'a, K, V> 961 where 962 K: 'a, 963 V: 'a, 964 { 965 pub(crate) iter: ::std::vec::Drain<'a, Bucket<K, V>>, 966 } 967 968 impl<'a, K, V> Iterator for Drain<'a, K, V> { 969 type Item = (K, V); 970 971 iterator_methods!(Bucket::key_value); 972 } 973 974 impl<'a, K, V> DoubleEndedIterator for Drain<'a, K, V> { 975 double_ended_iterator_methods!(Bucket::key_value); 976 } 977 978 impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> 979 where 980 K: Hash + Eq, 981 S: BuildHasher, 982 { 983 type Item = (&'a K, &'a V); 984 type IntoIter = Iter<'a, K, V>; into_iter(self) -> Self::IntoIter985 fn into_iter(self) -> Self::IntoIter { 986 self.iter() 987 } 988 } 989 990 impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> 991 where 992 K: Hash + Eq, 993 S: BuildHasher, 994 { 995 type Item = (&'a K, &'a mut V); 996 type IntoIter = IterMut<'a, K, V>; into_iter(self) -> Self::IntoIter997 fn into_iter(self) -> Self::IntoIter { 998 self.iter_mut() 999 } 1000 } 1001 1002 impl<K, V, S> IntoIterator for IndexMap<K, V, S> 1003 where 1004 K: Hash + Eq, 1005 S: BuildHasher, 1006 { 1007 type Item = (K, V); 1008 type IntoIter = IntoIter<K, V>; into_iter(self) -> Self::IntoIter1009 fn into_iter(self) -> Self::IntoIter { 1010 IntoIter { 1011 iter: self.into_entries().into_iter(), 1012 } 1013 } 1014 } 1015 1016 use std::ops::{Index, IndexMut}; 1017 1018 impl<'a, K, V, Q: ?Sized, S> Index<&'a Q> for IndexMap<K, V, S> 1019 where 1020 Q: Hash + Equivalent<K>, 1021 K: Hash + Eq, 1022 S: BuildHasher, 1023 { 1024 type Output = V; 1025 1026 /// ***Panics*** if `key` is not present in the map. index(&self, key: &'a Q) -> &V1027 fn index(&self, key: &'a Q) -> &V { 1028 self.get(key).expect("IndexMap: key not found") 1029 } 1030 } 1031 1032 /// Mutable indexing allows changing / updating values of key-value 1033 /// pairs that are already present. 1034 /// 1035 /// You can **not** insert new pairs with index syntax, use `.insert()`. 1036 impl<'a, K, V, Q: ?Sized, S> IndexMut<&'a Q> for IndexMap<K, V, S> 1037 where 1038 Q: Hash + Equivalent<K>, 1039 K: Hash + Eq, 1040 S: BuildHasher, 1041 { 1042 /// ***Panics*** if `key` is not present in the map. index_mut(&mut self, key: &'a Q) -> &mut V1043 fn index_mut(&mut self, key: &'a Q) -> &mut V { 1044 self.get_mut(key).expect("IndexMap: key not found") 1045 } 1046 } 1047 1048 impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S> 1049 where 1050 K: Hash + Eq, 1051 S: BuildHasher + Default, 1052 { 1053 /// Create an `IndexMap` from the sequence of key-value pairs in the 1054 /// iterable. 1055 /// 1056 /// `from_iter` uses the same logic as `extend`. See 1057 /// [`extend`](#method.extend) for more details. from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self1058 fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self { 1059 let iter = iterable.into_iter(); 1060 let (low, _) = iter.size_hint(); 1061 let mut map = Self::with_capacity_and_hasher(low, <_>::default()); 1062 map.extend(iter); 1063 map 1064 } 1065 } 1066 1067 impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S> 1068 where 1069 K: Hash + Eq, 1070 S: BuildHasher, 1071 { 1072 /// Extend the map with all key-value pairs in the iterable. 1073 /// 1074 /// This is equivalent to calling [`insert`](#method.insert) for each of 1075 /// them in order, which means that for keys that already existed 1076 /// in the map, their value is updated but it keeps the existing order. 1077 /// 1078 /// New keys are inserted in the order they appear in the sequence. If 1079 /// equivalents of a key occur more than once, the last corresponding value 1080 /// prevails. extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I)1081 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) { 1082 // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.) 1083 // Keys may be already present or show multiple times in the iterator. 1084 // Reserve the entire hint lower bound if the map is empty. 1085 // Otherwise reserve half the hint (rounded up), so the map 1086 // will only resize twice in the worst case. 1087 let iter = iterable.into_iter(); 1088 let reserve = if self.is_empty() { 1089 iter.size_hint().0 1090 } else { 1091 (iter.size_hint().0 + 1) / 2 1092 }; 1093 self.reserve(reserve); 1094 iter.for_each(move |(k, v)| { 1095 self.insert(k, v); 1096 }); 1097 } 1098 } 1099 1100 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S> 1101 where 1102 K: Hash + Eq + Copy, 1103 V: Copy, 1104 S: BuildHasher, 1105 { 1106 /// Extend the map with all key-value pairs in the iterable. 1107 /// 1108 /// See the first extend method for more details. extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I)1109 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) { 1110 self.extend(iterable.into_iter().map(|(&key, &value)| (key, value))); 1111 } 1112 } 1113 1114 impl<K, V, S> Default for IndexMap<K, V, S> 1115 where 1116 S: BuildHasher + Default, 1117 { 1118 /// Return an empty `IndexMap` default() -> Self1119 fn default() -> Self { 1120 Self::with_capacity_and_hasher(0, S::default()) 1121 } 1122 } 1123 1124 impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1> 1125 where 1126 K: Hash + Eq, 1127 V1: PartialEq<V2>, 1128 S1: BuildHasher, 1129 S2: BuildHasher, 1130 { eq(&self, other: &IndexMap<K, V2, S2>) -> bool1131 fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool { 1132 if self.len() != other.len() { 1133 return false; 1134 } 1135 1136 self.iter() 1137 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) 1138 } 1139 } 1140 1141 impl<K, V, S> Eq for IndexMap<K, V, S> 1142 where 1143 K: Eq + Hash, 1144 V: Eq, 1145 S: BuildHasher, 1146 { 1147 } 1148 1149 #[cfg(test)] 1150 mod tests { 1151 use super::*; 1152 use util::enumerate; 1153 1154 #[test] it_works()1155 fn it_works() { 1156 let mut map = IndexMap::new(); 1157 assert_eq!(map.is_empty(), true); 1158 map.insert(1, ()); 1159 map.insert(1, ()); 1160 assert_eq!(map.len(), 1); 1161 assert!(map.get(&1).is_some()); 1162 assert_eq!(map.is_empty(), false); 1163 } 1164 1165 #[test] new()1166 fn new() { 1167 let map = IndexMap::<String, String>::new(); 1168 println!("{:?}", map); 1169 assert_eq!(map.capacity(), 0); 1170 assert_eq!(map.len(), 0); 1171 assert_eq!(map.is_empty(), true); 1172 } 1173 1174 #[test] insert()1175 fn insert() { 1176 let insert = [0, 4, 2, 12, 8, 7, 11, 5]; 1177 let not_present = [1, 3, 6, 9, 10]; 1178 let mut map = IndexMap::with_capacity(insert.len()); 1179 1180 for (i, &elt) in enumerate(&insert) { 1181 assert_eq!(map.len(), i); 1182 map.insert(elt, elt); 1183 assert_eq!(map.len(), i + 1); 1184 assert_eq!(map.get(&elt), Some(&elt)); 1185 assert_eq!(map[&elt], elt); 1186 } 1187 println!("{:?}", map); 1188 1189 for &elt in ¬_present { 1190 assert!(map.get(&elt).is_none()); 1191 } 1192 } 1193 1194 #[test] insert_full()1195 fn insert_full() { 1196 let insert = vec![9, 2, 7, 1, 4, 6, 13]; 1197 let present = vec![1, 6, 2]; 1198 let mut map = IndexMap::with_capacity(insert.len()); 1199 1200 for (i, &elt) in enumerate(&insert) { 1201 assert_eq!(map.len(), i); 1202 let (index, existing) = map.insert_full(elt, elt); 1203 assert_eq!(existing, None); 1204 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); 1205 assert_eq!(map.len(), i + 1); 1206 } 1207 1208 let len = map.len(); 1209 for &elt in &present { 1210 let (index, existing) = map.insert_full(elt, elt); 1211 assert_eq!(existing, Some(elt)); 1212 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); 1213 assert_eq!(map.len(), len); 1214 } 1215 } 1216 1217 #[test] insert_2()1218 fn insert_2() { 1219 let mut map = IndexMap::with_capacity(16); 1220 1221 let mut keys = vec![]; 1222 keys.extend(0..16); 1223 keys.extend(128..267); 1224 1225 for &i in &keys { 1226 let old_map = map.clone(); 1227 map.insert(i, ()); 1228 for key in old_map.keys() { 1229 if map.get(key).is_none() { 1230 println!("old_map: {:?}", old_map); 1231 println!("map: {:?}", map); 1232 panic!("did not find {} in map", key); 1233 } 1234 } 1235 } 1236 1237 for &i in &keys { 1238 assert!(map.get(&i).is_some(), "did not find {}", i); 1239 } 1240 } 1241 1242 #[test] insert_order()1243 fn insert_order() { 1244 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1245 let mut map = IndexMap::new(); 1246 1247 for &elt in &insert { 1248 map.insert(elt, ()); 1249 } 1250 1251 assert_eq!(map.keys().count(), map.len()); 1252 assert_eq!(map.keys().count(), insert.len()); 1253 for (a, b) in insert.iter().zip(map.keys()) { 1254 assert_eq!(a, b); 1255 } 1256 for (i, k) in (0..insert.len()).zip(map.keys()) { 1257 assert_eq!(map.get_index(i).unwrap().0, k); 1258 } 1259 } 1260 1261 #[test] grow()1262 fn grow() { 1263 let insert = [0, 4, 2, 12, 8, 7, 11]; 1264 let not_present = [1, 3, 6, 9, 10]; 1265 let mut map = IndexMap::with_capacity(insert.len()); 1266 1267 for (i, &elt) in enumerate(&insert) { 1268 assert_eq!(map.len(), i); 1269 map.insert(elt, elt); 1270 assert_eq!(map.len(), i + 1); 1271 assert_eq!(map.get(&elt), Some(&elt)); 1272 assert_eq!(map[&elt], elt); 1273 } 1274 1275 println!("{:?}", map); 1276 for &elt in &insert { 1277 map.insert(elt * 10, elt); 1278 } 1279 for &elt in &insert { 1280 map.insert(elt * 100, elt); 1281 } 1282 for (i, &elt) in insert.iter().cycle().enumerate().take(100) { 1283 map.insert(elt * 100 + i as i32, elt); 1284 } 1285 println!("{:?}", map); 1286 for &elt in ¬_present { 1287 assert!(map.get(&elt).is_none()); 1288 } 1289 } 1290 1291 #[test] reserve()1292 fn reserve() { 1293 let mut map = IndexMap::<usize, usize>::new(); 1294 assert_eq!(map.capacity(), 0); 1295 map.reserve(100); 1296 let capacity = map.capacity(); 1297 assert!(capacity >= 100); 1298 for i in 0..capacity { 1299 assert_eq!(map.len(), i); 1300 map.insert(i, i * i); 1301 assert_eq!(map.len(), i + 1); 1302 assert_eq!(map.capacity(), capacity); 1303 assert_eq!(map.get(&i), Some(&(i * i))); 1304 } 1305 map.insert(capacity, std::usize::MAX); 1306 assert_eq!(map.len(), capacity + 1); 1307 assert!(map.capacity() > capacity); 1308 assert_eq!(map.get(&capacity), Some(&std::usize::MAX)); 1309 } 1310 1311 #[test] shrink_to_fit()1312 fn shrink_to_fit() { 1313 let mut map = IndexMap::<usize, usize>::new(); 1314 assert_eq!(map.capacity(), 0); 1315 for i in 0..100 { 1316 assert_eq!(map.len(), i); 1317 map.insert(i, i * i); 1318 assert_eq!(map.len(), i + 1); 1319 assert!(map.capacity() >= i + 1); 1320 assert_eq!(map.get(&i), Some(&(i * i))); 1321 map.shrink_to_fit(); 1322 assert_eq!(map.len(), i + 1); 1323 assert_eq!(map.capacity(), i + 1); 1324 assert_eq!(map.get(&i), Some(&(i * i))); 1325 } 1326 } 1327 1328 #[test] remove()1329 fn remove() { 1330 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1331 let mut map = IndexMap::new(); 1332 1333 for &elt in &insert { 1334 map.insert(elt, elt); 1335 } 1336 1337 assert_eq!(map.keys().count(), map.len()); 1338 assert_eq!(map.keys().count(), insert.len()); 1339 for (a, b) in insert.iter().zip(map.keys()) { 1340 assert_eq!(a, b); 1341 } 1342 1343 let remove_fail = [99, 77]; 1344 let remove = [4, 12, 8, 7]; 1345 1346 for &key in &remove_fail { 1347 assert!(map.swap_remove_full(&key).is_none()); 1348 } 1349 println!("{:?}", map); 1350 for &key in &remove { 1351 //println!("{:?}", map); 1352 let index = map.get_full(&key).unwrap().0; 1353 assert_eq!(map.swap_remove_full(&key), Some((index, key, key))); 1354 } 1355 println!("{:?}", map); 1356 1357 for key in &insert { 1358 assert_eq!(map.get(key).is_some(), !remove.contains(key)); 1359 } 1360 assert_eq!(map.len(), insert.len() - remove.len()); 1361 assert_eq!(map.keys().count(), insert.len() - remove.len()); 1362 } 1363 1364 #[test] remove_to_empty()1365 fn remove_to_empty() { 1366 let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 }; 1367 map.swap_remove(&5).unwrap(); 1368 map.swap_remove(&4).unwrap(); 1369 map.swap_remove(&0).unwrap(); 1370 assert!(map.is_empty()); 1371 } 1372 1373 #[test] swap_remove_index()1374 fn swap_remove_index() { 1375 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1376 let mut map = IndexMap::new(); 1377 1378 for &elt in &insert { 1379 map.insert(elt, elt * 2); 1380 } 1381 1382 let mut vector = insert.to_vec(); 1383 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; 1384 1385 // check that the same swap remove sequence on vec and map 1386 // have the same result. 1387 for &rm in remove_sequence { 1388 let out_vec = vector.swap_remove(rm); 1389 let (out_map, _) = map.swap_remove_index(rm).unwrap(); 1390 assert_eq!(out_vec, out_map); 1391 } 1392 assert_eq!(vector.len(), map.len()); 1393 for (a, b) in vector.iter().zip(map.keys()) { 1394 assert_eq!(a, b); 1395 } 1396 } 1397 1398 #[test] partial_eq_and_eq()1399 fn partial_eq_and_eq() { 1400 let mut map_a = IndexMap::new(); 1401 map_a.insert(1, "1"); 1402 map_a.insert(2, "2"); 1403 let mut map_b = map_a.clone(); 1404 assert_eq!(map_a, map_b); 1405 map_b.swap_remove(&1); 1406 assert_ne!(map_a, map_b); 1407 1408 let map_c: IndexMap<_, String> = 1409 map_b.into_iter().map(|(k, v)| (k, v.to_owned())).collect(); 1410 assert_ne!(map_a, map_c); 1411 assert_ne!(map_c, map_a); 1412 } 1413 1414 #[test] extend()1415 fn extend() { 1416 let mut map = IndexMap::new(); 1417 map.extend(vec![(&1, &2), (&3, &4)]); 1418 map.extend(vec![(5, 6)]); 1419 assert_eq!( 1420 map.into_iter().collect::<Vec<_>>(), 1421 vec![(1, 2), (3, 4), (5, 6)] 1422 ); 1423 } 1424 1425 #[test] entry()1426 fn entry() { 1427 let mut map = IndexMap::new(); 1428 1429 map.insert(1, "1"); 1430 map.insert(2, "2"); 1431 { 1432 let e = map.entry(3); 1433 assert_eq!(e.index(), 2); 1434 let e = e.or_insert("3"); 1435 assert_eq!(e, &"3"); 1436 } 1437 1438 let e = map.entry(2); 1439 assert_eq!(e.index(), 1); 1440 assert_eq!(e.key(), &2); 1441 match e { 1442 Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"), 1443 Entry::Vacant(_) => panic!(), 1444 } 1445 assert_eq!(e.or_insert("4"), &"2"); 1446 } 1447 1448 #[test] entry_and_modify()1449 fn entry_and_modify() { 1450 let mut map = IndexMap::new(); 1451 1452 map.insert(1, "1"); 1453 map.entry(1).and_modify(|x| *x = "2"); 1454 assert_eq!(Some(&"2"), map.get(&1)); 1455 1456 map.entry(2).and_modify(|x| *x = "doesn't exist"); 1457 assert_eq!(None, map.get(&2)); 1458 } 1459 1460 #[test] entry_or_default()1461 fn entry_or_default() { 1462 let mut map = IndexMap::new(); 1463 1464 #[derive(Debug, PartialEq)] 1465 enum TestEnum { 1466 DefaultValue, 1467 NonDefaultValue, 1468 } 1469 1470 impl Default for TestEnum { 1471 fn default() -> Self { 1472 TestEnum::DefaultValue 1473 } 1474 } 1475 1476 map.insert(1, TestEnum::NonDefaultValue); 1477 assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default()); 1478 1479 assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default()); 1480 } 1481 1482 #[test] keys()1483 fn keys() { 1484 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1485 let map: IndexMap<_, _> = vec.into_iter().collect(); 1486 let keys: Vec<_> = map.keys().cloned().collect(); 1487 assert_eq!(keys.len(), 3); 1488 assert!(keys.contains(&1)); 1489 assert!(keys.contains(&2)); 1490 assert!(keys.contains(&3)); 1491 } 1492 1493 #[test] values()1494 fn values() { 1495 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1496 let map: IndexMap<_, _> = vec.into_iter().collect(); 1497 let values: Vec<_> = map.values().cloned().collect(); 1498 assert_eq!(values.len(), 3); 1499 assert!(values.contains(&'a')); 1500 assert!(values.contains(&'b')); 1501 assert!(values.contains(&'c')); 1502 } 1503 1504 #[test] values_mut()1505 fn values_mut() { 1506 let vec = vec![(1, 1), (2, 2), (3, 3)]; 1507 let mut map: IndexMap<_, _> = vec.into_iter().collect(); 1508 for value in map.values_mut() { 1509 *value *= 2 1510 } 1511 let values: Vec<_> = map.values().cloned().collect(); 1512 assert_eq!(values.len(), 3); 1513 assert!(values.contains(&2)); 1514 assert!(values.contains(&4)); 1515 assert!(values.contains(&6)); 1516 } 1517 } 1518