]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
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 | { | |
87 | fn clone(&self) -> Self { | |
88 | IndexMap { | |
89 | core: self.core.clone(), | |
90 | hash_builder: self.hash_builder.clone(), | |
91 | } | |
92 | } | |
93 | ||
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] | |
104 | fn into_entries(self) -> Vec<Self::Entry> { | |
105 | self.core.into_entries() | |
106 | } | |
107 | ||
108 | #[inline] | |
109 | fn as_entries(&self) -> &[Self::Entry] { | |
110 | self.core.as_entries() | |
111 | } | |
112 | ||
113 | #[inline] | |
114 | fn as_entries_mut(&mut self) -> &mut [Self::Entry] { | |
115 | self.core.as_entries_mut() | |
116 | } | |
117 | ||
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 | { | |
131 | 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] | |
147 | 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] | |
156 | 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] | |
167 | 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` | |
182 | 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. | |
187 | pub fn capacity(&self) -> usize { | |
188 | self.core.capacity() | |
189 | } | |
190 | ||
191 | /// Return a reference to the map's `BuildHasher`. | |
192 | 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] | |
200 | 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] | |
208 | 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 | |
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 | |
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 | |
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 | |
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 | |
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. | |
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. | |
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. | |
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. | |
293 | pub fn shrink_to_fit(&mut self) { | |
294 | self.core.shrink_to_fit(); | |
295 | } | |
296 | ||
297 | 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. | |
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. | |
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). | |
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). | |
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). | |
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). | |
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 | |
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 | |
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 | ||
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 | ||
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 | ||
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). | |
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). | |
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). | |
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). | |
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). | |
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). | |
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). | |
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). | |
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). | |
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). | |
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 | ||
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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). | |
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). | |
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> { | |
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> { | |
747 | 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> { | |
754 | 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> { | |
762 | 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> { | |
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> { | |
791 | 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> { | |
798 | 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> { | |
806 | 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> { | |
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> { | |
835 | 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> { | |
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> { | |
864 | 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> { | |
871 | 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> { | |
879 | 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> { | |
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> { | |
908 | 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> { | |
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> { | |
937 | 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> { | |
943 | 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>; | |
973 | 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>; | |
981 | 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>; | |
989 | 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. | |
1029 | 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. | |
1072 | 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. | |
1111 | 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. | |
1151 | 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. | |
1168 | 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. | |
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. | |
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` | |
1229 | 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 | { | |
1241 | 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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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] | |
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 | } |