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