1use super::{Bucket, ExtractCore, IndexMap, IndexMapCore, Slice};
2
3use alloc::vec::{self, Vec};
4use core::fmt;
5use core::hash::{BuildHasher, Hash};
6use core::iter::FusedIterator;
7use core::ops::{Index, RangeBounds};
8use core::slice;
9
10impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
11 type Item = (&'a K, &'a V);
12 type IntoIter = Iter<'a, K, V>;
13
14 fn into_iter(self) -> Self::IntoIter {
15 self.iter()
16 }
17}
18
19impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
20 type Item = (&'a K, &'a mut V);
21 type IntoIter = IterMut<'a, K, V>;
22
23 fn into_iter(self) -> Self::IntoIter {
24 self.iter_mut()
25 }
26}
27
28impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
29 type Item = (K, V);
30 type IntoIter = IntoIter<K, V>;
31
32 fn into_iter(self) -> Self::IntoIter {
33 IntoIter::new(self.into_entries())
34 }
35}
36
37pub struct Iter<'a, K, V> {
42 iter: slice::Iter<'a, Bucket<K, V>>,
43}
44
45impl<'a, K, V> Iter<'a, K, V> {
46 pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
47 Self {
48 iter: entries.iter(),
49 }
50 }
51
52 pub fn as_slice(&self) -> &'a Slice<K, V> {
54 Slice::from_slice(self.iter.as_slice())
55 }
56}
57
58impl<'a, K, V> Iterator for Iter<'a, K, V> {
59 type Item = (&'a K, &'a V);
60
61 iterator_methods!(Bucket::refs);
62}
63
64impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
65 double_ended_iterator_methods!(Bucket::refs);
66}
67
68impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
69 fn len(&self) -> usize {
70 self.iter.len()
71 }
72}
73
74impl<K, V> FusedIterator for Iter<'_, K, V> {}
75
76impl<K, V> Clone for Iter<'_, K, V> {
78 fn clone(&self) -> Self {
79 Iter {
80 iter: self.iter.clone(),
81 }
82 }
83}
84
85impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
86 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
87 f.debug_list().entries(self.clone()).finish()
88 }
89}
90
91impl<K, V> Default for Iter<'_, K, V> {
92 fn default() -> Self {
93 Self { iter: [].iter() }
94 }
95}
96
97pub struct IterMut<'a, K, V> {
102 iter: slice::IterMut<'a, Bucket<K, V>>,
103}
104
105impl<'a, K, V> IterMut<'a, K, V> {
106 pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
107 Self {
108 iter: entries.iter_mut(),
109 }
110 }
111
112 pub fn as_slice(&self) -> &Slice<K, V> {
114 Slice::from_slice(self.iter.as_slice())
115 }
116
117 pub fn into_slice(self) -> &'a mut Slice<K, V> {
121 Slice::from_mut_slice(self.iter.into_slice())
122 }
123}
124
125impl<'a, K, V> Iterator for IterMut<'a, K, V> {
126 type Item = (&'a K, &'a mut V);
127
128 iterator_methods!(Bucket::ref_mut);
129}
130
131impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
132 double_ended_iterator_methods!(Bucket::ref_mut);
133}
134
135impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
136 fn len(&self) -> usize {
137 self.iter.len()
138 }
139}
140
141impl<K, V> FusedIterator for IterMut<'_, K, V> {}
142
143impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
144 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
145 let iter = self.iter.as_slice().iter().map(Bucket::refs);
146 f.debug_list().entries(iter).finish()
147 }
148}
149
150impl<K, V> Default for IterMut<'_, K, V> {
151 fn default() -> Self {
152 Self {
153 iter: [].iter_mut(),
154 }
155 }
156}
157
158pub struct IterMut2<'a, K, V> {
163 iter: slice::IterMut<'a, Bucket<K, V>>,
164}
165
166impl<'a, K, V> IterMut2<'a, K, V> {
167 pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
168 Self {
169 iter: entries.iter_mut(),
170 }
171 }
172
173 pub fn as_slice(&self) -> &Slice<K, V> {
175 Slice::from_slice(self.iter.as_slice())
176 }
177
178 pub fn into_slice(self) -> &'a mut Slice<K, V> {
182 Slice::from_mut_slice(self.iter.into_slice())
183 }
184}
185
186impl<'a, K, V> Iterator for IterMut2<'a, K, V> {
187 type Item = (&'a mut K, &'a mut V);
188
189 iterator_methods!(Bucket::muts);
190}
191
192impl<K, V> DoubleEndedIterator for IterMut2<'_, K, V> {
193 double_ended_iterator_methods!(Bucket::muts);
194}
195
196impl<K, V> ExactSizeIterator for IterMut2<'_, K, V> {
197 fn len(&self) -> usize {
198 self.iter.len()
199 }
200}
201
202impl<K, V> FusedIterator for IterMut2<'_, K, V> {}
203
204impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut2<'_, K, V> {
205 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206 let iter = self.iter.as_slice().iter().map(Bucket::refs);
207 f.debug_list().entries(iter).finish()
208 }
209}
210
211impl<K, V> Default for IterMut2<'_, K, V> {
212 fn default() -> Self {
213 Self {
214 iter: [].iter_mut(),
215 }
216 }
217}
218
219#[derive(Clone)]
224pub struct IntoIter<K, V> {
225 iter: vec::IntoIter<Bucket<K, V>>,
226}
227
228impl<K, V> IntoIter<K, V> {
229 pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
230 Self {
231 iter: entries.into_iter(),
232 }
233 }
234
235 pub fn as_slice(&self) -> &Slice<K, V> {
237 Slice::from_slice(self.iter.as_slice())
238 }
239
240 pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> {
242 Slice::from_mut_slice(self.iter.as_mut_slice())
243 }
244}
245
246impl<K, V> Iterator for IntoIter<K, V> {
247 type Item = (K, V);
248
249 iterator_methods!(Bucket::key_value);
250}
251
252impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
253 double_ended_iterator_methods!(Bucket::key_value);
254}
255
256impl<K, V> ExactSizeIterator for IntoIter<K, V> {
257 fn len(&self) -> usize {
258 self.iter.len()
259 }
260}
261
262impl<K, V> FusedIterator for IntoIter<K, V> {}
263
264impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
265 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
266 let iter = self.iter.as_slice().iter().map(Bucket::refs);
267 f.debug_list().entries(iter).finish()
268 }
269}
270
271impl<K, V> Default for IntoIter<K, V> {
272 fn default() -> Self {
273 Self {
274 iter: Vec::new().into_iter(),
275 }
276 }
277}
278
279pub struct Drain<'a, K, V> {
284 iter: vec::Drain<'a, Bucket<K, V>>,
285}
286
287impl<'a, K, V> Drain<'a, K, V> {
288 pub(super) fn new(iter: vec::Drain<'a, Bucket<K, V>>) -> Self {
289 Self { iter }
290 }
291
292 pub fn as_slice(&self) -> &Slice<K, V> {
294 Slice::from_slice(self.iter.as_slice())
295 }
296}
297
298impl<K, V> Iterator for Drain<'_, K, V> {
299 type Item = (K, V);
300
301 iterator_methods!(Bucket::key_value);
302}
303
304impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
305 double_ended_iterator_methods!(Bucket::key_value);
306}
307
308impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
309 fn len(&self) -> usize {
310 self.iter.len()
311 }
312}
313
314impl<K, V> FusedIterator for Drain<'_, K, V> {}
315
316impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
317 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
318 let iter = self.iter.as_slice().iter().map(Bucket::refs);
319 f.debug_list().entries(iter).finish()
320 }
321}
322
323pub struct Keys<'a, K, V> {
328 iter: slice::Iter<'a, Bucket<K, V>>,
329}
330
331impl<'a, K, V> Keys<'a, K, V> {
332 pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
333 Self {
334 iter: entries.iter(),
335 }
336 }
337}
338
339impl<'a, K, V> Iterator for Keys<'a, K, V> {
340 type Item = &'a K;
341
342 iterator_methods!(Bucket::key_ref);
343}
344
345impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
346 double_ended_iterator_methods!(Bucket::key_ref);
347}
348
349impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
350 fn len(&self) -> usize {
351 self.iter.len()
352 }
353}
354
355impl<K, V> FusedIterator for Keys<'_, K, V> {}
356
357impl<K, V> Clone for Keys<'_, K, V> {
359 fn clone(&self) -> Self {
360 Keys {
361 iter: self.iter.clone(),
362 }
363 }
364}
365
366impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
367 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
368 f.debug_list().entries(self.clone()).finish()
369 }
370}
371
372impl<K, V> Default for Keys<'_, K, V> {
373 fn default() -> Self {
374 Self { iter: [].iter() }
375 }
376}
377
378impl<K, V> Index<usize> for Keys<'_, K, V> {
435 type Output = K;
436
437 fn index(&self, index: usize) -> &K {
441 &self.iter.as_slice()[index].key
442 }
443}
444
445pub struct IntoKeys<K, V> {
450 iter: vec::IntoIter<Bucket<K, V>>,
451}
452
453impl<K, V> IntoKeys<K, V> {
454 pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
455 Self {
456 iter: entries.into_iter(),
457 }
458 }
459}
460
461impl<K, V> Iterator for IntoKeys<K, V> {
462 type Item = K;
463
464 iterator_methods!(Bucket::key);
465}
466
467impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
468 double_ended_iterator_methods!(Bucket::key);
469}
470
471impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
472 fn len(&self) -> usize {
473 self.iter.len()
474 }
475}
476
477impl<K, V> FusedIterator for IntoKeys<K, V> {}
478
479impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
480 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
481 let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
482 f.debug_list().entries(iter).finish()
483 }
484}
485
486impl<K, V> Default for IntoKeys<K, V> {
487 fn default() -> Self {
488 Self {
489 iter: Vec::new().into_iter(),
490 }
491 }
492}
493
494pub struct Values<'a, K, V> {
499 iter: slice::Iter<'a, Bucket<K, V>>,
500}
501
502impl<'a, K, V> Values<'a, K, V> {
503 pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
504 Self {
505 iter: entries.iter(),
506 }
507 }
508}
509
510impl<'a, K, V> Iterator for Values<'a, K, V> {
511 type Item = &'a V;
512
513 iterator_methods!(Bucket::value_ref);
514}
515
516impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
517 double_ended_iterator_methods!(Bucket::value_ref);
518}
519
520impl<K, V> ExactSizeIterator for Values<'_, K, V> {
521 fn len(&self) -> usize {
522 self.iter.len()
523 }
524}
525
526impl<K, V> FusedIterator for Values<'_, K, V> {}
527
528impl<K, V> Clone for Values<'_, K, V> {
530 fn clone(&self) -> Self {
531 Values {
532 iter: self.iter.clone(),
533 }
534 }
535}
536
537impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
538 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
539 f.debug_list().entries(self.clone()).finish()
540 }
541}
542
543impl<K, V> Default for Values<'_, K, V> {
544 fn default() -> Self {
545 Self { iter: [].iter() }
546 }
547}
548
549pub struct ValuesMut<'a, K, V> {
554 iter: slice::IterMut<'a, Bucket<K, V>>,
555}
556
557impl<'a, K, V> ValuesMut<'a, K, V> {
558 pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
559 Self {
560 iter: entries.iter_mut(),
561 }
562 }
563}
564
565impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
566 type Item = &'a mut V;
567
568 iterator_methods!(Bucket::value_mut);
569}
570
571impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
572 double_ended_iterator_methods!(Bucket::value_mut);
573}
574
575impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
576 fn len(&self) -> usize {
577 self.iter.len()
578 }
579}
580
581impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
582
583impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
584 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
585 let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
586 f.debug_list().entries(iter).finish()
587 }
588}
589
590impl<K, V> Default for ValuesMut<'_, K, V> {
591 fn default() -> Self {
592 Self {
593 iter: [].iter_mut(),
594 }
595 }
596}
597
598pub struct IntoValues<K, V> {
603 iter: vec::IntoIter<Bucket<K, V>>,
604}
605
606impl<K, V> IntoValues<K, V> {
607 pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
608 Self {
609 iter: entries.into_iter(),
610 }
611 }
612}
613
614impl<K, V> Iterator for IntoValues<K, V> {
615 type Item = V;
616
617 iterator_methods!(Bucket::value);
618}
619
620impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
621 double_ended_iterator_methods!(Bucket::value);
622}
623
624impl<K, V> ExactSizeIterator for IntoValues<K, V> {
625 fn len(&self) -> usize {
626 self.iter.len()
627 }
628}
629
630impl<K, V> FusedIterator for IntoValues<K, V> {}
631
632impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
633 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
634 let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
635 f.debug_list().entries(iter).finish()
636 }
637}
638
639impl<K, V> Default for IntoValues<K, V> {
640 fn default() -> Self {
641 Self {
642 iter: Vec::new().into_iter(),
643 }
644 }
645}
646
647pub struct Splice<'a, I, K, V, S>
652where
653 I: Iterator<Item = (K, V)>,
654 K: Hash + Eq,
655 S: BuildHasher,
656{
657 map: &'a mut IndexMap<K, V, S>,
658 tail: IndexMapCore<K, V>,
659 drain: vec::IntoIter<Bucket<K, V>>,
660 replace_with: I,
661}
662
663impl<'a, I, K, V, S> Splice<'a, I, K, V, S>
664where
665 I: Iterator<Item = (K, V)>,
666 K: Hash + Eq,
667 S: BuildHasher,
668{
669 #[track_caller]
670 pub(super) fn new<R>(map: &'a mut IndexMap<K, V, S>, range: R, replace_with: I) -> Self
671 where
672 R: RangeBounds<usize>,
673 {
674 let (tail, drain) = map.core.split_splice(range);
675 Self {
676 map,
677 tail,
678 drain,
679 replace_with,
680 }
681 }
682}
683
684impl<I, K, V, S> Drop for Splice<'_, I, K, V, S>
685where
686 I: Iterator<Item = (K, V)>,
687 K: Hash + Eq,
688 S: BuildHasher,
689{
690 fn drop(&mut self) {
691 let _ = self.drain.nth(usize::MAX);
695
696 while let Some((key, value)) = self.replace_with.next() {
699 let hash = self.map.hash(&key);
702 if let Some(i) = self.tail.get_index_of(hash, &key) {
703 self.tail.as_entries_mut()[i].value = value;
704 } else {
705 self.map.core.insert_full(hash, key, value);
706 }
707 }
708
709 self.map.core.append_unchecked(&mut self.tail);
711 }
712}
713
714impl<I, K, V, S> Iterator for Splice<'_, I, K, V, S>
715where
716 I: Iterator<Item = (K, V)>,
717 K: Hash + Eq,
718 S: BuildHasher,
719{
720 type Item = (K, V);
721
722 fn next(&mut self) -> Option<Self::Item> {
723 self.drain.next().map(Bucket::key_value)
724 }
725
726 fn size_hint(&self) -> (usize, Option<usize>) {
727 self.drain.size_hint()
728 }
729}
730
731impl<I, K, V, S> DoubleEndedIterator for Splice<'_, I, K, V, S>
732where
733 I: Iterator<Item = (K, V)>,
734 K: Hash + Eq,
735 S: BuildHasher,
736{
737 fn next_back(&mut self) -> Option<Self::Item> {
738 self.drain.next_back().map(Bucket::key_value)
739 }
740}
741
742impl<I, K, V, S> ExactSizeIterator for Splice<'_, I, K, V, S>
743where
744 I: Iterator<Item = (K, V)>,
745 K: Hash + Eq,
746 S: BuildHasher,
747{
748 fn len(&self) -> usize {
749 self.drain.len()
750 }
751}
752
753impl<I, K, V, S> FusedIterator for Splice<'_, I, K, V, S>
754where
755 I: Iterator<Item = (K, V)>,
756 K: Hash + Eq,
757 S: BuildHasher,
758{
759}
760
761impl<I, K, V, S> fmt::Debug for Splice<'_, I, K, V, S>
762where
763 I: fmt::Debug + Iterator<Item = (K, V)>,
764 K: fmt::Debug + Hash + Eq,
765 V: fmt::Debug,
766 S: BuildHasher,
767{
768 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
769 f.debug_struct("Splice")
771 .field("drain", &self.drain)
772 .field("replace_with", &self.replace_with)
773 .finish()
774 }
775}
776
777pub struct ExtractIf<'a, K, V, F> {
782 inner: ExtractCore<'a, K, V>,
783 pred: F,
784}
785
786impl<K, V, F> ExtractIf<'_, K, V, F> {
787 #[track_caller]
788 pub(super) fn new<R>(core: &mut IndexMapCore<K, V>, range: R, pred: F) -> ExtractIf<'_, K, V, F>
789 where
790 R: RangeBounds<usize>,
791 F: FnMut(&K, &mut V) -> bool,
792 {
793 ExtractIf {
794 inner: core.extract(range),
795 pred,
796 }
797 }
798}
799
800impl<K, V, F> Iterator for ExtractIf<'_, K, V, F>
801where
802 F: FnMut(&K, &mut V) -> bool,
803{
804 type Item = (K, V);
805
806 fn next(&mut self) -> Option<Self::Item> {
807 self.inner
808 .extract_if(|bucket| {
809 let (key, value) = bucket.ref_mut();
810 (self.pred)(key, value)
811 })
812 .map(Bucket::key_value)
813 }
814
815 fn size_hint(&self) -> (usize, Option<usize>) {
816 (0, Some(self.inner.remaining()))
817 }
818}
819
820impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
821
822impl<K, V, F> fmt::Debug for ExtractIf<'_, K, V, F>
823where
824 K: fmt::Debug,
825 V: fmt::Debug,
826{
827 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
828 f.debug_struct("ExtractIf").finish_non_exhaustive()
829 }
830}