ringmap/map/
iter.rs

1use super::core::RingMapCore;
2use super::{Bucket, Entries, RingMap};
3
4use alloc::collections::vec_deque::{self, VecDeque};
5use core::hash::{BuildHasher, Hash};
6use core::iter::FusedIterator;
7use core::ops::{Index, RangeBounds};
8use core::{fmt, mem, slice};
9
10impl<'a, K, V, S> IntoIterator for &'a RingMap<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 RingMap<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 RingMap<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/// Internal iterator over `VecDeque` slices
38pub(crate) struct Buckets<'a, K, V> {
39    head: slice::Iter<'a, Bucket<K, V>>,
40    tail: slice::Iter<'a, Bucket<K, V>>,
41}
42
43impl<'a, K, V> Buckets<'a, K, V> {
44    pub(crate) fn new(entries: &'a VecDeque<Bucket<K, V>>) -> Self {
45        let (head, tail) = entries.as_slices();
46        Self {
47            head: head.iter(),
48            tail: tail.iter(),
49        }
50    }
51
52    pub(crate) fn from_slice(slice: &'a [Bucket<K, V>]) -> Self {
53        Self {
54            head: slice.iter(),
55            tail: [].iter(),
56        }
57    }
58}
59
60impl<'a, K, V> Iterator for Buckets<'a, K, V> {
61    type Item = &'a Bucket<K, V>;
62
63    fn next(&mut self) -> Option<Self::Item> {
64        match self.head.next() {
65            next @ Some(_) => next,
66            None => {
67                // Swap so the rest is found on the first branch next time.
68                // (Like `VecDeque` does in its own iterators.)
69                mem::swap(&mut self.head, &mut self.tail);
70                self.head.next()
71            }
72        }
73    }
74
75    fn size_hint(&self) -> (usize, Option<usize>) {
76        let len = self.len();
77        (len, Some(len))
78    }
79
80    fn count(self) -> usize {
81        self.len()
82    }
83
84    fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
85        if n >= self.head.len() {
86            n -= self.head.len();
87            self.head = [].iter();
88            mem::swap(&mut self.head, &mut self.tail);
89        }
90        self.head.nth(n)
91    }
92
93    fn last(mut self) -> Option<Self::Item> {
94        self.next_back()
95    }
96
97    fn fold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
98    where
99        F: FnMut(Acc, Self::Item) -> Acc,
100    {
101        acc = self.head.fold(acc, &mut f);
102        self.tail.fold(acc, &mut f)
103    }
104
105    fn collect<C>(self) -> C
106    where
107        C: FromIterator<Self::Item>,
108    {
109        self.head.chain(self.tail).collect()
110    }
111}
112
113impl<K, V> DoubleEndedIterator for Buckets<'_, K, V> {
114    fn next_back(&mut self) -> Option<Self::Item> {
115        match self.tail.next_back() {
116            next @ Some(_) => next,
117            None => {
118                // Swap so the rest is found on the first branch next time.
119                // (Like `VecDeque` does in its own iterators.)
120                mem::swap(&mut self.head, &mut self.tail);
121                self.tail.next_back()
122            }
123        }
124    }
125
126    fn nth_back(&mut self, mut n: usize) -> Option<Self::Item> {
127        if n >= self.tail.len() {
128            n -= self.tail.len();
129            self.tail = [].iter();
130            mem::swap(&mut self.head, &mut self.tail);
131        }
132        self.tail.nth_back(n)
133    }
134
135    fn rfold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
136    where
137        F: FnMut(Acc, Self::Item) -> Acc,
138    {
139        acc = self.tail.rfold(acc, &mut f);
140        self.head.rfold(acc, &mut f)
141    }
142}
143
144impl<K, V> ExactSizeIterator for Buckets<'_, K, V> {
145    fn len(&self) -> usize {
146        self.head.len() + self.tail.len()
147    }
148}
149
150impl<K, V> Clone for Buckets<'_, K, V> {
151    fn clone(&self) -> Self {
152        Self {
153            head: self.head.clone(),
154            tail: self.tail.clone(),
155        }
156    }
157}
158
159impl<K, V> Default for Buckets<'_, K, V> {
160    fn default() -> Self {
161        Self {
162            head: [].iter(),
163            tail: [].iter(),
164        }
165    }
166}
167
168/// Internal iterator over `VecDeque` mutable slices
169struct BucketsMut<'a, K, V> {
170    head: slice::IterMut<'a, Bucket<K, V>>,
171    tail: slice::IterMut<'a, Bucket<K, V>>,
172}
173
174impl<'a, K, V> BucketsMut<'a, K, V> {
175    fn new(entries: &'a mut VecDeque<Bucket<K, V>>) -> Self {
176        let (head, tail) = entries.as_mut_slices();
177        Self {
178            head: head.iter_mut(),
179            tail: tail.iter_mut(),
180        }
181    }
182
183    fn from_mut_slice(slice: &'a mut [Bucket<K, V>]) -> Self {
184        Self {
185            head: slice.iter_mut(),
186            tail: [].iter_mut(),
187        }
188    }
189
190    fn iter(&self) -> Buckets<'_, K, V> {
191        Buckets {
192            head: self.head.as_slice().iter(),
193            tail: self.tail.as_slice().iter(),
194        }
195    }
196}
197
198impl<'a, K, V> Iterator for BucketsMut<'a, K, V> {
199    type Item = &'a mut Bucket<K, V>;
200
201    fn next(&mut self) -> Option<Self::Item> {
202        match self.head.next() {
203            next @ Some(_) => next,
204            None => {
205                // Swap so the rest is found on the first branch next time.
206                // (Like `VecDeque` does in its own iterators.)
207                mem::swap(&mut self.head, &mut self.tail);
208                self.head.next()
209            }
210        }
211    }
212
213    fn size_hint(&self) -> (usize, Option<usize>) {
214        let len = self.len();
215        (len, Some(len))
216    }
217
218    fn count(self) -> usize {
219        self.len()
220    }
221
222    fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
223        if n >= self.head.len() {
224            n -= self.head.len();
225            self.head = [].iter_mut();
226            mem::swap(&mut self.head, &mut self.tail);
227        }
228        self.head.nth(n)
229    }
230
231    fn last(mut self) -> Option<Self::Item> {
232        self.next_back()
233    }
234
235    fn fold<Acc, F>(self, acc: Acc, mut f: F) -> Acc
236    where
237        F: FnMut(Acc, Self::Item) -> Acc,
238    {
239        let acc = self.head.fold(acc, &mut f);
240        self.tail.fold(acc, &mut f)
241    }
242
243    fn collect<C>(self) -> C
244    where
245        C: FromIterator<Self::Item>,
246    {
247        self.head.chain(self.tail).collect()
248    }
249}
250
251impl<K, V> DoubleEndedIterator for BucketsMut<'_, K, V> {
252    fn next_back(&mut self) -> Option<Self::Item> {
253        match self.tail.next_back() {
254            next @ Some(_) => next,
255            None => {
256                // Swap so the rest is found on the first branch next time.
257                // (Like `VecDeque` does in its own iterators.)
258                mem::swap(&mut self.head, &mut self.tail);
259                self.tail.next_back()
260            }
261        }
262    }
263
264    fn nth_back(&mut self, mut n: usize) -> Option<Self::Item> {
265        if n >= self.tail.len() {
266            n -= self.tail.len();
267            self.tail = [].iter_mut();
268            mem::swap(&mut self.head, &mut self.tail);
269        }
270        self.tail.nth_back(n)
271    }
272
273    fn rfold<Acc, F>(self, acc: Acc, mut f: F) -> Acc
274    where
275        F: FnMut(Acc, Self::Item) -> Acc,
276    {
277        let acc = self.tail.rfold(acc, &mut f);
278        self.head.rfold(acc, &mut f)
279    }
280}
281
282impl<K, V> ExactSizeIterator for BucketsMut<'_, K, V> {
283    fn len(&self) -> usize {
284        self.head.len() + self.tail.len()
285    }
286}
287
288impl<K, V> Default for BucketsMut<'_, K, V> {
289    fn default() -> Self {
290        Self {
291            head: [].iter_mut(),
292            tail: [].iter_mut(),
293        }
294    }
295}
296
297/// An iterator over the entries of an [`RingMap`].
298///
299/// This `struct` is created by the [`RingMap::iter`] method.
300/// See its documentation for more.
301pub struct Iter<'a, K, V> {
302    iter: Buckets<'a, K, V>,
303}
304
305impl<'a, K, V> Iter<'a, K, V> {
306    pub(super) fn new(entries: &'a VecDeque<Bucket<K, V>>) -> Self {
307        Self {
308            iter: Buckets::new(entries),
309        }
310    }
311
312    pub(super) fn from_slice(slice: &'a [Bucket<K, V>]) -> Self {
313        Self {
314            iter: Buckets::from_slice(slice),
315        }
316    }
317}
318
319impl<'a, K, V> Iterator for Iter<'a, K, V> {
320    type Item = (&'a K, &'a V);
321
322    iterator_methods!(Bucket::refs);
323}
324
325impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
326    double_ended_iterator_methods!(Bucket::refs);
327}
328
329impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
330    fn len(&self) -> usize {
331        self.iter.len()
332    }
333}
334
335impl<K, V> FusedIterator for Iter<'_, K, V> {}
336
337// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
338impl<K, V> Clone for Iter<'_, K, V> {
339    fn clone(&self) -> Self {
340        Iter {
341            iter: self.iter.clone(),
342        }
343    }
344}
345
346impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
347    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
348        f.debug_list().entries(self.clone()).finish()
349    }
350}
351
352impl<K, V> Default for Iter<'_, K, V> {
353    fn default() -> Self {
354        Self {
355            iter: Default::default(),
356        }
357    }
358}
359
360/// A mutable iterator over the entries of an [`RingMap`].
361///
362/// This `struct` is created by the [`RingMap::iter_mut`] method.
363/// See its documentation for more.
364pub struct IterMut<'a, K, V> {
365    iter: BucketsMut<'a, K, V>,
366}
367
368impl<'a, K, V> IterMut<'a, K, V> {
369    pub(super) fn new(entries: &'a mut VecDeque<Bucket<K, V>>) -> Self {
370        Self {
371            iter: BucketsMut::new(entries),
372        }
373    }
374
375    pub(super) fn from_mut_slice(slice: &'a mut [Bucket<K, V>]) -> Self {
376        Self {
377            iter: BucketsMut::from_mut_slice(slice),
378        }
379    }
380}
381
382impl<'a, K, V> Iterator for IterMut<'a, K, V> {
383    type Item = (&'a K, &'a mut V);
384
385    iterator_methods!(Bucket::ref_mut);
386}
387
388impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
389    double_ended_iterator_methods!(Bucket::ref_mut);
390}
391
392impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
393    fn len(&self) -> usize {
394        self.iter.len()
395    }
396}
397
398impl<K, V> FusedIterator for IterMut<'_, K, V> {}
399
400impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
401    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
402        let iter = self.iter.iter().map(Bucket::refs);
403        f.debug_list().entries(iter).finish()
404    }
405}
406
407impl<K, V> Default for IterMut<'_, K, V> {
408    fn default() -> Self {
409        Self {
410            iter: Default::default(),
411        }
412    }
413}
414
415/// A mutable iterator over the entries of an [`RingMap`].
416///
417/// This `struct` is created by the [`MutableKeys::iter_mut2`][super::MutableKeys::iter_mut2] method.
418/// See its documentation for more.
419pub struct IterMut2<'a, K, V> {
420    iter: BucketsMut<'a, K, V>,
421}
422
423impl<'a, K, V> IterMut2<'a, K, V> {
424    pub(super) fn new(entries: &'a mut VecDeque<Bucket<K, V>>) -> Self {
425        Self {
426            iter: BucketsMut::new(entries),
427        }
428    }
429}
430
431impl<'a, K, V> Iterator for IterMut2<'a, K, V> {
432    type Item = (&'a mut K, &'a mut V);
433
434    iterator_methods!(Bucket::muts);
435}
436
437impl<K, V> DoubleEndedIterator for IterMut2<'_, K, V> {
438    double_ended_iterator_methods!(Bucket::muts);
439}
440
441impl<K, V> ExactSizeIterator for IterMut2<'_, K, V> {
442    fn len(&self) -> usize {
443        self.iter.len()
444    }
445}
446
447impl<K, V> FusedIterator for IterMut2<'_, K, V> {}
448
449impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut2<'_, K, V> {
450    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
451        let iter = self.iter.iter().map(Bucket::refs);
452        f.debug_list().entries(iter).finish()
453    }
454}
455
456impl<K, V> Default for IterMut2<'_, K, V> {
457    fn default() -> Self {
458        Self {
459            iter: Default::default(),
460        }
461    }
462}
463
464/// An owning iterator over the entries of an [`RingMap`].
465///
466/// This `struct` is created by the [`RingMap::into_iter`] method
467/// (provided by the [`IntoIterator`] trait). See its documentation for more.
468#[derive(Clone)]
469pub struct IntoIter<K, V> {
470    iter: vec_deque::IntoIter<Bucket<K, V>>,
471}
472
473impl<K, V> IntoIter<K, V> {
474    pub(super) fn new(entries: VecDeque<Bucket<K, V>>) -> Self {
475        Self {
476            iter: entries.into_iter(),
477        }
478    }
479}
480
481impl<K, V> Iterator for IntoIter<K, V> {
482    type Item = (K, V);
483
484    iterator_methods!(Bucket::key_value);
485}
486
487impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
488    double_ended_iterator_methods!(Bucket::key_value);
489}
490
491impl<K, V> ExactSizeIterator for IntoIter<K, V> {
492    fn len(&self) -> usize {
493        self.iter.len()
494    }
495}
496
497impl<K, V> FusedIterator for IntoIter<K, V> {}
498
499impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
500    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
501        // FIXME
502        // let iter = self.iter.as_slice().iter().map(Bucket::refs);
503        // f.debug_list().entries(iter).finish()
504        f.debug_struct("IntoIter").finish_non_exhaustive()
505    }
506}
507
508impl<K, V> Default for IntoIter<K, V> {
509    fn default() -> Self {
510        Self {
511            iter: VecDeque::new().into_iter(),
512        }
513    }
514}
515
516/// A draining iterator over the entries of an [`RingMap`].
517///
518/// This `struct` is created by the [`RingMap::drain`] method.
519/// See its documentation for more.
520pub struct Drain<'a, K, V> {
521    iter: vec_deque::Drain<'a, Bucket<K, V>>,
522}
523
524impl<'a, K, V> Drain<'a, K, V> {
525    pub(super) fn new(iter: vec_deque::Drain<'a, Bucket<K, V>>) -> Self {
526        Self { iter }
527    }
528}
529
530impl<K, V> Iterator for Drain<'_, K, V> {
531    type Item = (K, V);
532
533    iterator_methods!(Bucket::key_value);
534}
535
536impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
537    double_ended_iterator_methods!(Bucket::key_value);
538}
539
540impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
541    fn len(&self) -> usize {
542        self.iter.len()
543    }
544}
545
546impl<K, V> FusedIterator for Drain<'_, K, V> {}
547
548impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
549    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
550        // FIXME
551        // let iter = self.iter.as_slice().iter().map(Bucket::refs);
552        // f.debug_list().entries(iter).finish()
553        f.debug_struct("Drain").finish_non_exhaustive()
554    }
555}
556
557/// An iterator over the keys of an [`RingMap`].
558///
559/// This `struct` is created by the [`RingMap::keys`] method.
560/// See its documentation for more.
561pub struct Keys<'a, K, V> {
562    iter: Buckets<'a, K, V>,
563}
564
565impl<'a, K, V> Keys<'a, K, V> {
566    pub(super) fn new(entries: &'a VecDeque<Bucket<K, V>>) -> Self {
567        Self {
568            iter: Buckets::new(entries),
569        }
570    }
571
572    pub(super) fn from_slice(slice: &'a [Bucket<K, V>]) -> Self {
573        Self {
574            iter: Buckets::from_slice(slice),
575        }
576    }
577}
578
579impl<'a, K, V> Iterator for Keys<'a, K, V> {
580    type Item = &'a K;
581
582    iterator_methods!(Bucket::key_ref);
583}
584
585impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
586    double_ended_iterator_methods!(Bucket::key_ref);
587}
588
589impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
590    fn len(&self) -> usize {
591        self.iter.len()
592    }
593}
594
595impl<K, V> FusedIterator for Keys<'_, K, V> {}
596
597// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
598impl<K, V> Clone for Keys<'_, K, V> {
599    fn clone(&self) -> Self {
600        Keys {
601            iter: self.iter.clone(),
602        }
603    }
604}
605
606impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
607    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
608        f.debug_list().entries(self.clone()).finish()
609    }
610}
611
612impl<K, V> Default for Keys<'_, K, V> {
613    fn default() -> Self {
614        Self {
615            iter: Default::default(),
616        }
617    }
618}
619
620/// Access [`RingMap`] keys at indexed positions.
621///
622/// While [`Index<usize> for RingMap`][values] accesses a map's values,
623/// indexing through [`RingMap::keys`] offers an alternative to access a map's
624/// keys instead.
625///
626/// [values]: RingMap#impl-Index<usize>-for-RingMap<K,+V,+S>
627///
628/// Since `Keys` is also an iterator, consuming items from the iterator will
629/// offset the effective indices. Similarly, if `Keys` is obtained from
630/// [`Slice::keys`][super::Slice::keys], indices will be interpreted relative to the position of
631/// that slice.
632///
633/// # Examples
634///
635/// ```
636/// use ringmap::RingMap;
637///
638/// let mut map = RingMap::new();
639/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
640///     map.insert(word.to_lowercase(), word.to_uppercase());
641/// }
642///
643/// assert_eq!(map[0], "LOREM");
644/// assert_eq!(map.keys()[0], "lorem");
645/// assert_eq!(map[1], "IPSUM");
646/// assert_eq!(map.keys()[1], "ipsum");
647///
648/// map.reverse();
649/// assert_eq!(map.keys()[0], "amet");
650/// assert_eq!(map.keys()[1], "sit");
651///
652/// map.sort_keys();
653/// assert_eq!(map.keys()[0], "amet");
654/// assert_eq!(map.keys()[1], "dolor");
655///
656/// // Advancing the iterator will offset the indexing
657/// let mut keys = map.keys();
658/// assert_eq!(keys[0], "amet");
659/// assert_eq!(keys.next().map(|s| &**s), Some("amet"));
660/// assert_eq!(keys[0], "dolor");
661/// assert_eq!(keys[1], "ipsum");
662///
663/// // Slices may have an offset as well
664/// let (head, tail) = map.as_slices();
665/// assert!(tail.is_empty());
666/// let slice = &head[2..];
667/// assert_eq!(slice[0], "IPSUM");
668/// assert_eq!(slice.keys()[0], "ipsum");
669/// ```
670///
671/// ```should_panic
672/// use ringmap::RingMap;
673///
674/// let mut map = RingMap::new();
675/// map.insert("foo", 1);
676/// println!("{:?}", map.keys()[10]); // panics!
677/// ```
678impl<K, V> Index<usize> for Keys<'_, K, V> {
679    type Output = K;
680
681    /// Returns a reference to the key at the supplied `index`.
682    ///
683    /// ***Panics*** if `index` is out of bounds.
684    fn index(&self, index: usize) -> &K {
685        let Buckets { head, tail } = &self.iter;
686        if index < head.len() {
687            &head.as_slice()[index].key
688        } else {
689            &tail.as_slice()[index - head.len()].key
690        }
691    }
692}
693
694/// An owning iterator over the keys of an [`RingMap`].
695///
696/// This `struct` is created by the [`RingMap::into_keys`] method.
697/// See its documentation for more.
698pub struct IntoKeys<K, V> {
699    iter: vec_deque::IntoIter<Bucket<K, V>>,
700}
701
702impl<K, V> IntoKeys<K, V> {
703    pub(super) fn new(entries: VecDeque<Bucket<K, V>>) -> Self {
704        Self {
705            iter: entries.into_iter(),
706        }
707    }
708}
709
710impl<K, V> Iterator for IntoKeys<K, V> {
711    type Item = K;
712
713    iterator_methods!(Bucket::key);
714}
715
716impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
717    double_ended_iterator_methods!(Bucket::key);
718}
719
720impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
721    fn len(&self) -> usize {
722        self.iter.len()
723    }
724}
725
726impl<K, V> FusedIterator for IntoKeys<K, V> {}
727
728impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
729    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
730        // FIXME
731        // let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
732        // f.debug_list().entries(iter).finish()
733        f.debug_struct("IntoKeys").finish_non_exhaustive()
734    }
735}
736
737impl<K, V> Default for IntoKeys<K, V> {
738    fn default() -> Self {
739        Self {
740            iter: VecDeque::new().into_iter(),
741        }
742    }
743}
744
745/// An iterator over the values of an [`RingMap`].
746///
747/// This `struct` is created by the [`RingMap::values`] method.
748/// See its documentation for more.
749pub struct Values<'a, K, V> {
750    iter: Buckets<'a, K, V>,
751}
752
753impl<'a, K, V> Values<'a, K, V> {
754    pub(super) fn new(entries: &'a VecDeque<Bucket<K, V>>) -> Self {
755        Self {
756            iter: Buckets::new(entries),
757        }
758    }
759
760    pub(super) fn from_slice(slice: &'a [Bucket<K, V>]) -> Self {
761        Self {
762            iter: Buckets::from_slice(slice),
763        }
764    }
765}
766
767impl<'a, K, V> Iterator for Values<'a, K, V> {
768    type Item = &'a V;
769
770    iterator_methods!(Bucket::value_ref);
771}
772
773impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
774    double_ended_iterator_methods!(Bucket::value_ref);
775}
776
777impl<K, V> ExactSizeIterator for Values<'_, K, V> {
778    fn len(&self) -> usize {
779        self.iter.len()
780    }
781}
782
783impl<K, V> FusedIterator for Values<'_, K, V> {}
784
785// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
786impl<K, V> Clone for Values<'_, K, V> {
787    fn clone(&self) -> Self {
788        Values {
789            iter: self.iter.clone(),
790        }
791    }
792}
793
794impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
795    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
796        f.debug_list().entries(self.clone()).finish()
797    }
798}
799
800impl<K, V> Default for Values<'_, K, V> {
801    fn default() -> Self {
802        Self {
803            iter: Default::default(),
804        }
805    }
806}
807
808/// A mutable iterator over the values of an [`RingMap`].
809///
810/// This `struct` is created by the [`RingMap::values_mut`] method.
811/// See its documentation for more.
812pub struct ValuesMut<'a, K, V> {
813    iter: BucketsMut<'a, K, V>,
814}
815
816impl<'a, K, V> ValuesMut<'a, K, V> {
817    pub(super) fn new(entries: &'a mut VecDeque<Bucket<K, V>>) -> Self {
818        Self {
819            iter: BucketsMut::new(entries),
820        }
821    }
822
823    pub(super) fn from_mut_slice(slice: &'a mut [Bucket<K, V>]) -> Self {
824        Self {
825            iter: BucketsMut::from_mut_slice(slice),
826        }
827    }
828}
829
830impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
831    type Item = &'a mut V;
832
833    iterator_methods!(Bucket::value_mut);
834}
835
836impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
837    double_ended_iterator_methods!(Bucket::value_mut);
838}
839
840impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
841    fn len(&self) -> usize {
842        self.iter.len()
843    }
844}
845
846impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
847
848impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
849    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
850        let iter = self.iter.iter().map(Bucket::value_ref);
851        f.debug_list().entries(iter).finish()
852    }
853}
854
855impl<K, V> Default for ValuesMut<'_, K, V> {
856    fn default() -> Self {
857        Self {
858            iter: Default::default(),
859        }
860    }
861}
862
863/// An owning iterator over the values of an [`RingMap`].
864///
865/// This `struct` is created by the [`RingMap::into_values`] method.
866/// See its documentation for more.
867pub struct IntoValues<K, V> {
868    iter: vec_deque::IntoIter<Bucket<K, V>>,
869}
870
871impl<K, V> IntoValues<K, V> {
872    pub(super) fn new(entries: VecDeque<Bucket<K, V>>) -> Self {
873        Self {
874            iter: entries.into_iter(),
875        }
876    }
877}
878
879impl<K, V> Iterator for IntoValues<K, V> {
880    type Item = V;
881
882    iterator_methods!(Bucket::value);
883}
884
885impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
886    double_ended_iterator_methods!(Bucket::value);
887}
888
889impl<K, V> ExactSizeIterator for IntoValues<K, V> {
890    fn len(&self) -> usize {
891        self.iter.len()
892    }
893}
894
895impl<K, V> FusedIterator for IntoValues<K, V> {}
896
897impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
898    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
899        // FIXME
900        // let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
901        // f.debug_list().entries(iter).finish()
902        f.debug_struct("IntoValues").finish_non_exhaustive()
903    }
904}
905
906impl<K, V> Default for IntoValues<K, V> {
907    fn default() -> Self {
908        Self {
909            iter: VecDeque::new().into_iter(),
910        }
911    }
912}
913
914/// A splicing iterator for `RingMap`.
915///
916/// This `struct` is created by [`RingMap::splice()`].
917/// See its documentation for more.
918pub struct Splice<'a, I, K, V, S>
919where
920    I: Iterator<Item = (K, V)>,
921    K: Hash + Eq,
922    S: BuildHasher,
923{
924    map: &'a mut RingMap<K, V, S>,
925    tail: RingMapCore<K, V>,
926    drain: vec_deque::IntoIter<Bucket<K, V>>,
927    replace_with: I,
928}
929
930impl<'a, I, K, V, S> Splice<'a, I, K, V, S>
931where
932    I: Iterator<Item = (K, V)>,
933    K: Hash + Eq,
934    S: BuildHasher,
935{
936    #[track_caller]
937    pub(super) fn new<R>(map: &'a mut RingMap<K, V, S>, range: R, replace_with: I) -> Self
938    where
939        R: RangeBounds<usize>,
940    {
941        let (tail, drain) = map.core.split_splice(range);
942        Self {
943            map,
944            tail,
945            drain,
946            replace_with,
947        }
948    }
949}
950
951impl<I, K, V, S> Drop for Splice<'_, I, K, V, S>
952where
953    I: Iterator<Item = (K, V)>,
954    K: Hash + Eq,
955    S: BuildHasher,
956{
957    fn drop(&mut self) {
958        // Finish draining unconsumed items. We don't strictly *have* to do this
959        // manually, since we already split it into separate memory, but it will
960        // match the drop order of `vec::Splice` items this way.
961        let _ = self.drain.nth(usize::MAX);
962
963        // Now insert all the new items. If a key matches an existing entry, it
964        // keeps the original position and only replaces the value, like `insert`.
965        while let Some((key, value)) = self.replace_with.next() {
966            // Since the tail is disjoint, we can try to update it first,
967            // or else insert (update or append) the primary map.
968            let hash = self.map.hash(&key);
969            if let Some(i) = self.tail.get_index_of(hash, &key) {
970                self.tail.as_entries_mut()[i].value = value;
971            } else {
972                self.map.core.push_back(hash, key, value);
973            }
974        }
975
976        // Finally, re-append the tail
977        self.map.core.append_unchecked(&mut self.tail);
978    }
979}
980
981impl<I, K, V, S> Iterator for Splice<'_, I, K, V, S>
982where
983    I: Iterator<Item = (K, V)>,
984    K: Hash + Eq,
985    S: BuildHasher,
986{
987    type Item = (K, V);
988
989    fn next(&mut self) -> Option<Self::Item> {
990        self.drain.next().map(Bucket::key_value)
991    }
992
993    fn size_hint(&self) -> (usize, Option<usize>) {
994        self.drain.size_hint()
995    }
996}
997
998impl<I, K, V, S> DoubleEndedIterator for Splice<'_, I, K, V, S>
999where
1000    I: Iterator<Item = (K, V)>,
1001    K: Hash + Eq,
1002    S: BuildHasher,
1003{
1004    fn next_back(&mut self) -> Option<Self::Item> {
1005        self.drain.next_back().map(Bucket::key_value)
1006    }
1007}
1008
1009impl<I, K, V, S> ExactSizeIterator for Splice<'_, I, K, V, S>
1010where
1011    I: Iterator<Item = (K, V)>,
1012    K: Hash + Eq,
1013    S: BuildHasher,
1014{
1015    fn len(&self) -> usize {
1016        self.drain.len()
1017    }
1018}
1019
1020impl<I, K, V, S> FusedIterator for Splice<'_, I, K, V, S>
1021where
1022    I: Iterator<Item = (K, V)>,
1023    K: Hash + Eq,
1024    S: BuildHasher,
1025{
1026}
1027
1028impl<I, K, V, S> fmt::Debug for Splice<'_, I, K, V, S>
1029where
1030    I: fmt::Debug + Iterator<Item = (K, V)>,
1031    K: fmt::Debug + Hash + Eq,
1032    V: fmt::Debug,
1033    S: BuildHasher,
1034{
1035    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1036        // Follow `vec::Splice` in only printing the drain and replacement
1037        f.debug_struct("Splice")
1038            .field("drain", &self.drain)
1039            .field("replace_with", &self.replace_with)
1040            .finish()
1041    }
1042}
ringmap/map/iter.rs

ringmap/map/
iter.rs
