indexmap/map/
iter.rs

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
37/// An iterator over the entries of an [`IndexMap`].
38///
39/// This `struct` is created by the [`IndexMap::iter`] method.
40/// See its documentation for more.
41pub 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    /// Returns a slice of the remaining entries in the iterator.
53    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
76// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
77impl<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
97/// A mutable iterator over the entries of an [`IndexMap`].
98///
99/// This `struct` is created by the [`IndexMap::iter_mut`] method.
100/// See its documentation for more.
101pub 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    /// Returns a slice of the remaining entries in the iterator.
113    pub fn as_slice(&self) -> &Slice<K, V> {
114        Slice::from_slice(self.iter.as_slice())
115    }
116
117    /// Returns a mutable slice of the remaining entries in the iterator.
118    ///
119    /// To avoid creating `&mut` references that alias, this is forced to consume the iterator.
120    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
158/// A mutable iterator over the entries of an [`IndexMap`].
159///
160/// This `struct` is created by the [`MutableKeys::iter_mut2`][super::MutableKeys::iter_mut2] method.
161/// See its documentation for more.
162pub 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    /// Returns a slice of the remaining entries in the iterator.
174    pub fn as_slice(&self) -> &Slice<K, V> {
175        Slice::from_slice(self.iter.as_slice())
176    }
177
178    /// Returns a mutable slice of the remaining entries in the iterator.
179    ///
180    /// To avoid creating `&mut` references that alias, this is forced to consume the iterator.
181    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/// An owning iterator over the entries of an [`IndexMap`].
220///
221/// This `struct` is created by the [`IndexMap::into_iter`] method
222/// (provided by the [`IntoIterator`] trait). See its documentation for more.
223#[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    /// Returns a slice of the remaining entries in the iterator.
236    pub fn as_slice(&self) -> &Slice<K, V> {
237        Slice::from_slice(self.iter.as_slice())
238    }
239
240    /// Returns a mutable slice of the remaining entries in the iterator.
241    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
279/// A draining iterator over the entries of an [`IndexMap`].
280///
281/// This `struct` is created by the [`IndexMap::drain`] method.
282/// See its documentation for more.
283pub 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    /// Returns a slice of the remaining entries in the iterator.
293    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
323/// An iterator over the keys of an [`IndexMap`].
324///
325/// This `struct` is created by the [`IndexMap::keys`] method.
326/// See its documentation for more.
327pub 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
357// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
358impl<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
378/// Access [`IndexMap`] keys at indexed positions.
379///
380/// While [`Index<usize> for IndexMap`][values] accesses a map's values,
381/// indexing through [`IndexMap::keys`] offers an alternative to access a map's
382/// keys instead.
383///
384/// [values]: IndexMap#impl-Index<usize>-for-IndexMap<K,+V,+S>
385///
386/// Since `Keys` is also an iterator, consuming items from the iterator will
387/// offset the effective indices. Similarly, if `Keys` is obtained from
388/// [`Slice::keys`], indices will be interpreted relative to the position of
389/// that slice.
390///
391/// # Examples
392///
393/// ```
394/// use indexmap::IndexMap;
395///
396/// let mut map = IndexMap::new();
397/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
398///     map.insert(word.to_lowercase(), word.to_uppercase());
399/// }
400///
401/// assert_eq!(map[0], "LOREM");
402/// assert_eq!(map.keys()[0], "lorem");
403/// assert_eq!(map[1], "IPSUM");
404/// assert_eq!(map.keys()[1], "ipsum");
405///
406/// map.reverse();
407/// assert_eq!(map.keys()[0], "amet");
408/// assert_eq!(map.keys()[1], "sit");
409///
410/// map.sort_keys();
411/// assert_eq!(map.keys()[0], "amet");
412/// assert_eq!(map.keys()[1], "dolor");
413///
414/// // Advancing the iterator will offset the indexing
415/// let mut keys = map.keys();
416/// assert_eq!(keys[0], "amet");
417/// assert_eq!(keys.next().map(|s| &**s), Some("amet"));
418/// assert_eq!(keys[0], "dolor");
419/// assert_eq!(keys[1], "ipsum");
420///
421/// // Slices may have an offset as well
422/// let slice = &map[2..];
423/// assert_eq!(slice[0], "IPSUM");
424/// assert_eq!(slice.keys()[0], "ipsum");
425/// ```
426///
427/// ```should_panic
428/// use indexmap::IndexMap;
429///
430/// let mut map = IndexMap::new();
431/// map.insert("foo", 1);
432/// println!("{:?}", map.keys()[10]); // panics!
433/// ```
434impl<K, V> Index<usize> for Keys<'_, K, V> {
435    type Output = K;
436
437    /// Returns a reference to the key at the supplied `index`.
438    ///
439    /// ***Panics*** if `index` is out of bounds.
440    fn index(&self, index: usize) -> &K {
441        &self.iter.as_slice()[index].key
442    }
443}
444
445/// An owning iterator over the keys of an [`IndexMap`].
446///
447/// This `struct` is created by the [`IndexMap::into_keys`] method.
448/// See its documentation for more.
449pub 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
494/// An iterator over the values of an [`IndexMap`].
495///
496/// This `struct` is created by the [`IndexMap::values`] method.
497/// See its documentation for more.
498pub 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
528// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
529impl<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
549/// A mutable iterator over the values of an [`IndexMap`].
550///
551/// This `struct` is created by the [`IndexMap::values_mut`] method.
552/// See its documentation for more.
553pub 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
598/// An owning iterator over the values of an [`IndexMap`].
599///
600/// This `struct` is created by the [`IndexMap::into_values`] method.
601/// See its documentation for more.
602pub 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
647/// A splicing iterator for `IndexMap`.
648///
649/// This `struct` is created by [`IndexMap::splice()`].
650/// See its documentation for more.
651pub 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        // Finish draining unconsumed items. We don't strictly *have* to do this
692        // manually, since we already split it into separate memory, but it will
693        // match the drop order of `vec::Splice` items this way.
694        let _ = self.drain.nth(usize::MAX);
695
696        // Now insert all the new items. If a key matches an existing entry, it
697        // keeps the original position and only replaces the value, like `insert`.
698        while let Some((key, value)) = self.replace_with.next() {
699            // Since the tail is disjoint, we can try to update it first,
700            // or else insert (update or append) the primary map.
701            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        // Finally, re-append the tail
710        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        // Follow `vec::Splice` in only printing the drain and replacement
770        f.debug_struct("Splice")
771            .field("drain", &self.drain)
772            .field("replace_with", &self.replace_with)
773            .finish()
774    }
775}
776
777/// An extracting iterator for `IndexMap`.
778///
779/// This `struct` is created by [`IndexMap::extract_if()`].
780/// See its documentation for more.
781pub 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}