1use super::core::IndexMapCore;
2use super::{Bucket, Entries, IndexMap, Slice};
3
4use alloc::vec::{self, Vec};
5use core::fmt;
6use core::hash::{BuildHasher, Hash};
7use core::iter::FusedIterator;
8use core::ops::{Index, RangeBounds};
9use core::slice;
10
11impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
12 type Item = (&'a K, &'a V);
13 type IntoIter = Iter<'a, K, V>;
14
15 fn into_iter(self) -> Self::IntoIter {
16 self.iter()
17 }
18}
19
20impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
21 type Item = (&'a K, &'a mut V);
22 type IntoIter = IterMut<'a, K, V>;
23
24 fn into_iter(self) -> Self::IntoIter {
25 self.iter_mut()
26 }
27}
28
29impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
30 type Item = (K, V);
31 type IntoIter = IntoIter<K, V>;
32
33 fn into_iter(self) -> Self::IntoIter {
34 IntoIter::new(self.into_entries())
35 }
36}
37
38/// An iterator over the entries of an [`IndexMap`].
39///
40/// This `struct` is created by the [`IndexMap::iter`] method.
41/// See its documentation for more.
42pub struct Iter<'a, K, V> {
43 iter: slice::Iter<'a, Bucket<K, V>>,
44}
45
46impl<'a, K, V> Iter<'a, K, V> {
47 pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
48 Self {
49 iter: entries.iter(),
50 }
51 }
52
53 /// Returns a slice of the remaining entries in the iterator.
54 pub fn as_slice(&self) -> &'a Slice<K, V> {
55 Slice::from_slice(self.iter.as_slice())
56 }
57}
58
59impl<'a, K, V> Iterator for Iter<'a, K, V> {
60 type Item = (&'a K, &'a V);
61
62 iterator_methods!(Bucket::refs);
63}
64
65impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
66 double_ended_iterator_methods!(Bucket::refs);
67}
68
69impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
70 fn len(&self) -> usize {
71 self.iter.len()
72 }
73}
74
75impl<K, V> FusedIterator for Iter<'_, K, V> {}
76
77// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
78impl<K, V> Clone for Iter<'_, K, V> {
79 fn clone(&self) -> Self {
80 Iter {
81 iter: self.iter.clone(),
82 }
83 }
84}
85
86impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 f.debug_list().entries(self.clone()).finish()
89 }
90}
91
92impl<K, V> Default for Iter<'_, K, V> {
93 fn default() -> Self {
94 Self { iter: [].iter() }
95 }
96}
97
98/// A mutable iterator over the entries of an [`IndexMap`].
99///
100/// This `struct` is created by the [`IndexMap::iter_mut`] method.
101/// See its documentation for more.
102pub struct IterMut<'a, K, V> {
103 iter: slice::IterMut<'a, Bucket<K, V>>,
104}
105
106impl<'a, K, V> IterMut<'a, K, V> {
107 pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
108 Self {
109 iter: entries.iter_mut(),
110 }
111 }
112
113 /// Returns a slice of the remaining entries in the iterator.
114 pub fn as_slice(&self) -> &Slice<K, V> {
115 Slice::from_slice(self.iter.as_slice())
116 }
117
118 /// Returns a mutable slice of the remaining entries in the iterator.
119 ///
120 /// To avoid creating `&mut` references that alias, this is forced to consume the iterator.
121 pub fn into_slice(self) -> &'a mut Slice<K, V> {
122 Slice::from_mut_slice(self.iter.into_slice())
123 }
124}
125
126impl<'a, K, V> Iterator for IterMut<'a, K, V> {
127 type Item = (&'a K, &'a mut V);
128
129 iterator_methods!(Bucket::ref_mut);
130}
131
132impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
133 double_ended_iterator_methods!(Bucket::ref_mut);
134}
135
136impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
137 fn len(&self) -> usize {
138 self.iter.len()
139 }
140}
141
142impl<K, V> FusedIterator for IterMut<'_, K, V> {}
143
144impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
145 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
146 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::refs);
147 f.debug_list().entries(iter).finish()
148 }
149}
150
151impl<K, V> Default for IterMut<'_, K, V> {
152 fn default() -> Self {
153 Self {
154 iter: [].iter_mut(),
155 }
156 }
157}
158
159/// An owning iterator over the entries of an [`IndexMap`].
160///
161/// This `struct` is created by the [`IndexMap::into_iter`] method
162/// (provided by the [`IntoIterator`] trait). See its documentation for more.
163pub struct IntoIter<K, V> {
164 iter: vec::IntoIter<Bucket<K, V>>,
165}
166
167impl<K, V> IntoIter<K, V> {
168 pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
169 Self {
170 iter: entries.into_iter(),
171 }
172 }
173
174 /// Returns a slice of the remaining entries in the iterator.
175 pub fn as_slice(&self) -> &Slice<K, V> {
176 Slice::from_slice(self.iter.as_slice())
177 }
178
179 /// Returns a mutable slice of the remaining entries in the iterator.
180 pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> {
181 Slice::from_mut_slice(self.iter.as_mut_slice())
182 }
183}
184
185impl<K, V> Iterator for IntoIter<K, V> {
186 type Item = (K, V);
187
188 iterator_methods!(Bucket::key_value);
189}
190
191impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
192 double_ended_iterator_methods!(Bucket::key_value);
193}
194
195impl<K, V> ExactSizeIterator for IntoIter<K, V> {
196 fn len(&self) -> usize {
197 self.iter.len()
198 }
199}
200
201impl<K, V> FusedIterator for IntoIter<K, V> {}
202
203impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
204 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
205 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::refs);
206 f.debug_list().entries(iter).finish()
207 }
208}
209
210impl<K, V> Default for IntoIter<K, V> {
211 fn default() -> Self {
212 Self {
213 iter: Vec::new().into_iter(),
214 }
215 }
216}
217
218/// A draining iterator over the entries of an [`IndexMap`].
219///
220/// This `struct` is created by the [`IndexMap::drain`] method.
221/// See its documentation for more.
222pub struct Drain<'a, K, V> {
223 iter: vec::Drain<'a, Bucket<K, V>>,
224}
225
226impl<'a, K, V> Drain<'a, K, V> {
227 pub(super) fn new(iter: vec::Drain<'a, Bucket<K, V>>) -> Self {
228 Self { iter }
229 }
230
231 /// Returns a slice of the remaining entries in the iterator.
232 pub fn as_slice(&self) -> &Slice<K, V> {
233 Slice::from_slice(self.iter.as_slice())
234 }
235}
236
237impl<K, V> Iterator for Drain<'_, K, V> {
238 type Item = (K, V);
239
240 iterator_methods!(Bucket::key_value);
241}
242
243impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
244 double_ended_iterator_methods!(Bucket::key_value);
245}
246
247impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
248 fn len(&self) -> usize {
249 self.iter.len()
250 }
251}
252
253impl<K, V> FusedIterator for Drain<'_, K, V> {}
254
255impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
256 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
257 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::refs);
258 f.debug_list().entries(iter).finish()
259 }
260}
261
262/// An iterator over the keys of an [`IndexMap`].
263///
264/// This `struct` is created by the [`IndexMap::keys`] method.
265/// See its documentation for more.
266pub struct Keys<'a, K, V> {
267 iter: slice::Iter<'a, Bucket<K, V>>,
268}
269
270impl<'a, K, V> Keys<'a, K, V> {
271 pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
272 Self {
273 iter: entries.iter(),
274 }
275 }
276}
277
278impl<'a, K, V> Iterator for Keys<'a, K, V> {
279 type Item = &'a K;
280
281 iterator_methods!(Bucket::key_ref);
282}
283
284impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
285 double_ended_iterator_methods!(Bucket::key_ref);
286}
287
288impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
289 fn len(&self) -> usize {
290 self.iter.len()
291 }
292}
293
294impl<K, V> FusedIterator for Keys<'_, K, V> {}
295
296// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
297impl<K, V> Clone for Keys<'_, K, V> {
298 fn clone(&self) -> Self {
299 Keys {
300 iter: self.iter.clone(),
301 }
302 }
303}
304
305impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
306 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307 f.debug_list().entries(self.clone()).finish()
308 }
309}
310
311impl<K, V> Default for Keys<'_, K, V> {
312 fn default() -> Self {
313 Self { iter: [].iter() }
314 }
315}
316
317/// Access [`IndexMap`] keys at indexed positions.
318///
319/// While [`Index<usize> for IndexMap`][values] accesses a map's values,
320/// indexing through [`IndexMap::keys`] offers an alternative to access a map's
321/// keys instead.
322///
323/// [values]: IndexMap#impl-Index<usize>-for-IndexMap<K,+V,+S>
324///
325/// Since `Keys` is also an iterator, consuming items from the iterator will
326/// offset the effective indexes. Similarly, if `Keys` is obtained from
327/// [`Slice::keys`], indexes will be interpreted relative to the position of
328/// that slice.
329///
330/// # Examples
331///
332/// ```
333/// use indexmap::IndexMap;
334///
335/// let mut map = IndexMap::new();
336/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
337/// map.insert(word.to_lowercase(), word.to_uppercase());
338/// }
339///
340/// assert_eq!(map[0], "LOREM");
341/// assert_eq!(map.keys()[0], "lorem");
342/// assert_eq!(map[1], "IPSUM");
343/// assert_eq!(map.keys()[1], "ipsum");
344///
345/// map.reverse();
346/// assert_eq!(map.keys()[0], "amet");
347/// assert_eq!(map.keys()[1], "sit");
348///
349/// map.sort_keys();
350/// assert_eq!(map.keys()[0], "amet");
351/// assert_eq!(map.keys()[1], "dolor");
352///
353/// // Advancing the iterator will offset the indexing
354/// let mut keys = map.keys();
355/// assert_eq!(keys[0], "amet");
356/// assert_eq!(keys.next().map(|s| &**s), Some("amet"));
357/// assert_eq!(keys[0], "dolor");
358/// assert_eq!(keys[1], "ipsum");
359///
360/// // Slices may have an offset as well
361/// let slice = &map[2..];
362/// assert_eq!(slice[0], "IPSUM");
363/// assert_eq!(slice.keys()[0], "ipsum");
364/// ```
365///
366/// ```should_panic
367/// use indexmap::IndexMap;
368///
369/// let mut map = IndexMap::new();
370/// map.insert("foo", 1);
371/// println!("{:?}", map.keys()[10]); // panics!
372/// ```
373impl<'a, K, V> Index<usize> for Keys<'a, K, V> {
374 type Output = K;
375
376 /// Returns a reference to the key at the supplied `index`.
377 ///
378 /// ***Panics*** if `index` is out of bounds.
379 fn index(&self, index: usize) -> &K {
380 &self.iter.as_slice()[index].key
381 }
382}
383
384/// An owning iterator over the keys of an [`IndexMap`].
385///
386/// This `struct` is created by the [`IndexMap::into_keys`] method.
387/// See its documentation for more.
388pub struct IntoKeys<K, V> {
389 iter: vec::IntoIter<Bucket<K, V>>,
390}
391
392impl<K, V> IntoKeys<K, V> {
393 pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
394 Self {
395 iter: entries.into_iter(),
396 }
397 }
398}
399
400impl<K, V> Iterator for IntoKeys<K, V> {
401 type Item = K;
402
403 iterator_methods!(Bucket::key);
404}
405
406impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
407 double_ended_iterator_methods!(Bucket::key);
408}
409
410impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
411 fn len(&self) -> usize {
412 self.iter.len()
413 }
414}
415
416impl<K, V> FusedIterator for IntoKeys<K, V> {}
417
418impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
419 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
420 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::key_ref);
421 f.debug_list().entries(iter).finish()
422 }
423}
424
425impl<K, V> Default for IntoKeys<K, V> {
426 fn default() -> Self {
427 Self {
428 iter: Vec::new().into_iter(),
429 }
430 }
431}
432
433/// An iterator over the values of an [`IndexMap`].
434///
435/// This `struct` is created by the [`IndexMap::values`] method.
436/// See its documentation for more.
437pub struct Values<'a, K, V> {
438 iter: slice::Iter<'a, Bucket<K, V>>,
439}
440
441impl<'a, K, V> Values<'a, K, V> {
442 pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
443 Self {
444 iter: entries.iter(),
445 }
446 }
447}
448
449impl<'a, K, V> Iterator for Values<'a, K, V> {
450 type Item = &'a V;
451
452 iterator_methods!(Bucket::value_ref);
453}
454
455impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
456 double_ended_iterator_methods!(Bucket::value_ref);
457}
458
459impl<K, V> ExactSizeIterator for Values<'_, K, V> {
460 fn len(&self) -> usize {
461 self.iter.len()
462 }
463}
464
465impl<K, V> FusedIterator for Values<'_, K, V> {}
466
467// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
468impl<K, V> Clone for Values<'_, K, V> {
469 fn clone(&self) -> Self {
470 Values {
471 iter: self.iter.clone(),
472 }
473 }
474}
475
476impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
477 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
478 f.debug_list().entries(self.clone()).finish()
479 }
480}
481
482impl<K, V> Default for Values<'_, K, V> {
483 fn default() -> Self {
484 Self { iter: [].iter() }
485 }
486}
487
488/// A mutable iterator over the values of an [`IndexMap`].
489///
490/// This `struct` is created by the [`IndexMap::values_mut`] method.
491/// See its documentation for more.
492pub struct ValuesMut<'a, K, V> {
493 iter: slice::IterMut<'a, Bucket<K, V>>,
494}
495
496impl<'a, K, V> ValuesMut<'a, K, V> {
497 pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
498 Self {
499 iter: entries.iter_mut(),
500 }
501 }
502}
503
504impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
505 type Item = &'a mut V;
506
507 iterator_methods!(Bucket::value_mut);
508}
509
510impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
511 double_ended_iterator_methods!(Bucket::value_mut);
512}
513
514impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
515 fn len(&self) -> usize {
516 self.iter.len()
517 }
518}
519
520impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
521
522impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
523 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
524 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::value_ref);
525 f.debug_list().entries(iter).finish()
526 }
527}
528
529impl<K, V> Default for ValuesMut<'_, K, V> {
530 fn default() -> Self {
531 Self {
532 iter: [].iter_mut(),
533 }
534 }
535}
536
537/// An owning iterator over the values of an [`IndexMap`].
538///
539/// This `struct` is created by the [`IndexMap::into_values`] method.
540/// See its documentation for more.
541pub struct IntoValues<K, V> {
542 iter: vec::IntoIter<Bucket<K, V>>,
543}
544
545impl<K, V> IntoValues<K, V> {
546 pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
547 Self {
548 iter: entries.into_iter(),
549 }
550 }
551}
552
553impl<K, V> Iterator for IntoValues<K, V> {
554 type Item = V;
555
556 iterator_methods!(Bucket::value);
557}
558
559impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
560 double_ended_iterator_methods!(Bucket::value);
561}
562
563impl<K, V> ExactSizeIterator for IntoValues<K, V> {
564 fn len(&self) -> usize {
565 self.iter.len()
566 }
567}
568
569impl<K, V> FusedIterator for IntoValues<K, V> {}
570
571impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
572 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
573 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::value_ref);
574 f.debug_list().entries(iter).finish()
575 }
576}
577
578impl<K, V> Default for IntoValues<K, V> {
579 fn default() -> Self {
580 Self {
581 iter: Vec::new().into_iter(),
582 }
583 }
584}
585
586/// A splicing iterator for `IndexMap`.
587///
588/// This `struct` is created by [`IndexMap::splice()`].
589/// See its documentation for more.
590pub struct Splice<'a, I, K, V, S>
591where
592 I: Iterator<Item = (K, V)>,
593 K: Hash + Eq,
594 S: BuildHasher,
595{
596 map: &'a mut IndexMap<K, V, S>,
597 tail: IndexMapCore<K, V>,
598 drain: vec::IntoIter<Bucket<K, V>>,
599 replace_with: I,
600}
601
602impl<'a, I, K, V, S> Splice<'a, I, K, V, S>
603where
604 I: Iterator<Item = (K, V)>,
605 K: Hash + Eq,
606 S: BuildHasher,
607{
608 pub(super) fn new<R>(map: &'a mut IndexMap<K, V, S>, range: R, replace_with: I) -> Self
609 where
610 R: RangeBounds<usize>,
611 {
612 let (tail: IndexMapCore, drain: IntoIter>) = map.core.split_splice(range);
613 Self {
614 map,
615 tail,
616 drain,
617 replace_with,
618 }
619 }
620}
621
622impl<I, K, V, S> Drop for Splice<'_, I, K, V, S>
623where
624 I: Iterator<Item = (K, V)>,
625 K: Hash + Eq,
626 S: BuildHasher,
627{
628 fn drop(&mut self) {
629 // Finish draining unconsumed items. We don't strictly *have* to do this
630 // manually, since we already split it into separate memory, but it will
631 // match the drop order of `vec::Splice` items this way.
632 let _ = self.drain.nth(usize::MAX);
633
634 // Now insert all the new items. If a key matches an existing entry, it
635 // keeps the original position and only replaces the value, like `insert`.
636 while let Some((key: K, value: V)) = self.replace_with.next() {
637 // Since the tail is disjoint, we can try to update it first,
638 // or else insert (update or append) the primary map.
639 let hash: HashValue = self.map.hash(&key);
640 if let Some(i: usize) = self.tail.get_index_of(hash, &key) {
641 self.tail.as_entries_mut()[i].value = value;
642 } else {
643 self.map.core.insert_full(hash, key, value);
644 }
645 }
646
647 // Finally, re-append the tail
648 self.map.core.append_unchecked(&mut self.tail);
649 }
650}
651
652impl<I, K, V, S> Iterator for Splice<'_, I, K, V, S>
653where
654 I: Iterator<Item = (K, V)>,
655 K: Hash + Eq,
656 S: BuildHasher,
657{
658 type Item = (K, V);
659
660 fn next(&mut self) -> Option<Self::Item> {
661 self.drain.next().map(Bucket::key_value)
662 }
663
664 fn size_hint(&self) -> (usize, Option<usize>) {
665 self.drain.size_hint()
666 }
667}
668
669impl<I, K, V, S> DoubleEndedIterator for Splice<'_, I, K, V, S>
670where
671 I: Iterator<Item = (K, V)>,
672 K: Hash + Eq,
673 S: BuildHasher,
674{
675 fn next_back(&mut self) -> Option<Self::Item> {
676 self.drain.next_back().map(Bucket::key_value)
677 }
678}
679
680impl<I, K, V, S> ExactSizeIterator for Splice<'_, I, K, V, S>
681where
682 I: Iterator<Item = (K, V)>,
683 K: Hash + Eq,
684 S: BuildHasher,
685{
686 fn len(&self) -> usize {
687 self.drain.len()
688 }
689}
690
691impl<I, K, V, S> FusedIterator for Splice<'_, I, K, V, S>
692where
693 I: Iterator<Item = (K, V)>,
694 K: Hash + Eq,
695 S: BuildHasher,
696{
697}
698
699impl<'a, I, K, V, S> fmt::Debug for Splice<'a, I, K, V, S>
700where
701 I: fmt::Debug + Iterator<Item = (K, V)>,
702 K: fmt::Debug + Hash + Eq,
703 V: fmt::Debug,
704 S: BuildHasher,
705{
706 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
707 // Follow `vec::Splice` in only printing the drain and replacement
708 f&mut DebugStruct<'_, '_>.debug_struct("Splice")
709 .field("drain", &self.drain)
710 .field(name:"replace_with", &self.replace_with)
711 .finish()
712 }
713}
714