embed_collections/btree/
iter.rs

1use super::BTreeMap;
2use super::inter::*;
3use super::leaf::*;
4use super::node::*;
5use crate::trace_log;
6use core::marker::PhantomData;
7use core::mem::needs_drop;
8
9pub(super) struct IterForward<K, V> {
10    /// Current leaf node for forward iteration
11    pub front_leaf: LeafNode<K, V>,
12    /// Current index within the leaf for forward iteration
13    pub idx: u32,
14}
15
16impl<K, V> IterForward<K, V> {
17    #[inline]
18    pub fn next(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
19        if self.idx >= self.front_leaf.key_count() {
20            if let Some(next) = self.front_leaf.get_right_node() {
21                debug_assert!(next.key_count() > 0);
22                self.front_leaf = next;
23                self.idx = 0;
24            } else {
25                return None;
26            }
27        }
28        let current_idx = self.idx;
29        self.idx = current_idx + 1;
30        Some((&self.front_leaf, current_idx))
31    }
32
33    #[inline]
34    pub unsafe fn next_pair(&mut self) -> Option<(*mut K, *mut V)> {
35        let (leaf, idx) = self.next()?;
36        leaf.get_raw_pair(idx)
37    }
38}
39
40pub(super) struct IterBackward<K, V> {
41    /// Current leaf node for backward iteration
42    pub back_leaf: LeafNode<K, V>,
43    /// back_idx - 1 is the next index within the back leaf, initial to key_count
44    /// When back_idx == 0, should go to previous leaf
45    pub back_idx: u32,
46}
47
48impl<K, V> IterBackward<K, V> {
49    #[inline]
50    pub fn prev(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
51        if self.back_idx == 0 {
52            if let Some(prev) = self.back_leaf.get_left_node() {
53                self.back_idx = prev.key_count();
54                self.back_leaf = prev;
55                debug_assert!(self.back_idx > 0);
56            } else {
57                return None;
58            }
59        }
60        self.back_idx -= 1;
61        Some((&self.back_leaf, self.back_idx))
62    }
63
64    #[inline]
65    pub unsafe fn prev_pair(&mut self) -> Option<(*mut K, *mut V)> {
66        let (leaf, idx) = self.prev()?;
67        leaf.get_raw_pair(idx)
68    }
69}
70
71/// Internal base iterator structure that handles the common logic
72/// for iterating over leaf nodes in both forward and backward directions.
73struct IterBase<K, V> {
74    /// Remaining elements to iterate, it serve as a guard in case forward and backward rendezvous
75    remaining: usize,
76    forward: IterForward<K, V>,
77    backward: IterBackward<K, V>,
78}
79
80impl<K, V> IterBase<K, V> {
81    /// Create a new IterBase
82    /// leaves: (front_leaf, back_leaf) - both Some or both None
83    /// remaining: total remaining elements
84    #[inline]
85    fn new(front_leaf: LeafNode<K, V>, back_leaf: LeafNode<K, V>, remaining: usize) -> Self {
86        Self {
87            forward: IterForward { front_leaf, idx: 0 },
88            backward: IterBackward { back_idx: back_leaf.key_count(), back_leaf },
89            remaining,
90        }
91    }
92
93    /// Advance the forward iterator and return the current leaf and index
94    /// Returns None if we've moved past the end
95    #[inline]
96    fn advance_forward(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
97        if self.remaining == 0 {
98            return None;
99        }
100        self.remaining -= 1;
101        self.forward.next()
102    }
103
104    /// Advance the backward iterator and return the current leaf and index
105    /// Returns None if we've moved past the beginning
106    #[inline]
107    fn advance_backward(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
108        if self.remaining == 0 {
109            return None;
110        }
111        self.remaining -= 1;
112        self.backward.prev()
113    }
114
115    /// Get remaining count
116    #[inline]
117    fn remaining(&self) -> usize {
118        self.remaining
119    }
120}
121
122/// An iterator over the entries of a BTreeMap
123pub struct Iter<'a, K: 'a, V: 'a> {
124    base: Option<IterBase<K, V>>,
125    _marker: PhantomData<&'a ()>,
126}
127
128impl<'a, K: 'a, V: 'a> Iter<'a, K, V> {
129    #[inline]
130    pub(super) fn new(leaves: Option<(LeafNode<K, V>, LeafNode<K, V>)>, remaining: usize) -> Self {
131        if let Some((front, back)) = leaves {
132            Self { base: Some(IterBase::new(front, back, remaining)), _marker: Default::default() }
133        } else {
134            Self { base: None, _marker: Default::default() }
135        }
136    }
137}
138
139impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
140    type Item = (&'a K, &'a V);
141
142    #[inline]
143    fn next(&mut self) -> Option<Self::Item> {
144        let base = self.base.as_mut()?;
145        let (leaf, idx) = base.advance_forward()?;
146        unsafe {
147            let key = (*leaf.key_ptr(idx)).assume_init_ref();
148            let value = (*leaf.value_ptr(idx)).assume_init_ref();
149            Some((key, value))
150        }
151    }
152
153    #[inline]
154    fn size_hint(&self) -> (usize, Option<usize>) {
155        let len = self.len();
156        (len, Some(len))
157    }
158}
159
160impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
161    #[inline]
162    fn len(&self) -> usize {
163        self.base.as_ref().map(|x| x.remaining()).unwrap_or(0)
164    }
165}
166
167impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
168    #[inline]
169    fn next_back(&mut self) -> Option<Self::Item> {
170        let base = self.base.as_mut()?;
171        let (leaf, idx) = base.advance_backward()?;
172        unsafe {
173            let key = (*leaf.key_ptr(idx)).assume_init_ref();
174            let value = (*leaf.value_ptr(idx)).assume_init_ref();
175            Some((key, value))
176        }
177    }
178}
179
180/// A mutable iterator over the entries of a BTreeMap
181pub struct IterMut<'a, K: 'a, V: 'a> {
182    base: Option<IterBase<K, V>>,
183    _marker: PhantomData<&'a mut ()>,
184}
185
186impl<'a, K: 'a, V: 'a> IterMut<'a, K, V> {
187    #[inline]
188    pub(super) fn new(leaves: Option<(LeafNode<K, V>, LeafNode<K, V>)>, remaining: usize) -> Self {
189        if let Some((front, back)) = leaves {
190            Self { base: Some(IterBase::new(front, back, remaining)), _marker: Default::default() }
191        } else {
192            Self { base: None, _marker: Default::default() }
193        }
194    }
195}
196
197impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
198    type Item = (&'a K, &'a mut V);
199
200    #[inline]
201    fn next(&mut self) -> Option<Self::Item> {
202        let base = self.base.as_mut()?;
203        let (leaf, idx) = base.advance_forward()?;
204        unsafe {
205            let key = (*leaf.key_ptr(idx)).assume_init_ref();
206            let value = (*leaf.value_ptr(idx)).assume_init_mut();
207            Some((key, value))
208        }
209    }
210
211    #[inline]
212    fn size_hint(&self) -> (usize, Option<usize>) {
213        let len = self.len();
214        (len, Some(len))
215    }
216}
217
218impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
219    #[inline]
220    fn len(&self) -> usize {
221        self.base.as_ref().map(|x| x.remaining()).unwrap_or(0)
222    }
223}
224
225impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
226    #[inline]
227    fn next_back(&mut self) -> Option<Self::Item> {
228        let base = self.base.as_mut()?;
229        let (leaf, idx) = base.advance_backward()?;
230        unsafe {
231            let key = (*leaf.key_ptr(idx)).assume_init_ref();
232            let value = (*leaf.value_ptr(idx)).assume_init_mut();
233            Some((key, value))
234        }
235    }
236}
237
238/// An iterator over the keys of a BTreeMap
239pub struct Keys<'a, K: 'a, V: 'a> {
240    inner: Iter<'a, K, V>,
241}
242
243impl<'a, K: 'a, V: 'a> Keys<'a, K, V> {
244    #[inline]
245    pub(super) fn new(inner: Iter<'a, K, V>) -> Self {
246        Self { inner }
247    }
248}
249
250impl<'a, K: 'a, V: 'a> Iterator for Keys<'a, K, V> {
251    type Item = &'a K;
252
253    #[inline]
254    fn next(&mut self) -> Option<Self::Item> {
255        self.inner.next().map(|(k, _)| k)
256    }
257
258    #[inline]
259    fn size_hint(&self) -> (usize, Option<usize>) {
260        self.inner.size_hint()
261    }
262}
263
264impl<'a, K: 'a, V: 'a> ExactSizeIterator for Keys<'a, K, V> {
265    #[inline]
266    fn len(&self) -> usize {
267        self.inner.len()
268    }
269}
270
271impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Keys<'a, K, V> {
272    #[inline]
273    fn next_back(&mut self) -> Option<Self::Item> {
274        self.inner.next_back().map(|(k, _)| k)
275    }
276}
277
278/// An iterator over the values of a BTreeMap
279pub struct Values<'a, K: 'a, V: 'a> {
280    inner: Iter<'a, K, V>,
281}
282
283impl<'a, K: 'a, V: 'a> Values<'a, K, V> {
284    #[inline]
285    pub(super) fn new(inner: Iter<'a, K, V>) -> Self {
286        Self { inner }
287    }
288}
289
290impl<'a, K: 'a, V: 'a> Iterator for Values<'a, K, V> {
291    type Item = &'a V;
292
293    #[inline]
294    fn next(&mut self) -> Option<Self::Item> {
295        self.inner.next().map(|(_, v)| v)
296    }
297
298    #[inline]
299    fn size_hint(&self) -> (usize, Option<usize>) {
300        self.inner.size_hint()
301    }
302}
303
304impl<'a, K: 'a, V: 'a> ExactSizeIterator for Values<'a, K, V> {
305    #[inline]
306    fn len(&self) -> usize {
307        self.inner.len()
308    }
309}
310
311impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Values<'a, K, V> {
312    #[inline]
313    fn next_back(&mut self) -> Option<Self::Item> {
314        self.inner.next_back().map(|(_, v)| v)
315    }
316}
317
318/// A mutable iterator over the values of a BTreeMap
319pub struct ValuesMut<'a, K: 'a, V: 'a> {
320    inner: IterMut<'a, K, V>,
321}
322
323impl<'a, K: 'a, V: 'a> ValuesMut<'a, K, V> {
324    #[inline]
325    pub(super) fn new(inner: IterMut<'a, K, V>) -> Self {
326        Self { inner }
327    }
328}
329
330impl<'a, K: 'a, V: 'a> Iterator for ValuesMut<'a, K, V> {
331    type Item = &'a mut V;
332
333    #[inline]
334    fn next(&mut self) -> Option<Self::Item> {
335        self.inner.next().map(|(_, v)| v)
336    }
337
338    #[inline]
339    fn size_hint(&self) -> (usize, Option<usize>) {
340        self.inner.size_hint()
341    }
342}
343
344impl<'a, K: 'a, V: 'a> ExactSizeIterator for ValuesMut<'a, K, V> {
345    #[inline]
346    fn len(&self) -> usize {
347        self.inner.len()
348    }
349}
350
351impl<'a, K: 'a, V: 'a> DoubleEndedIterator for ValuesMut<'a, K, V> {
352    #[inline]
353    fn next_back(&mut self) -> Option<Self::Item> {
354        self.inner.next_back().map(|(_, v)| v)
355    }
356}
357
358// Range and RangeMut implementations with DoubleEndedIterator support
359
360/// Internal base structure for range iteration
361/// Manages forward and backward iteration over a range of entries
362/// When the range is exhausted, the entire struct should be set to None
363pub(super) struct RangeBase<'a, K: 'a, V: 'a> {
364    front_leaf: LeafNode<K, V>,
365    back_leaf: LeafNode<K, V>,
366    front_idx: u32,
367    // back_idx -1 is the next pos, initial to be key_count
368    back_idx: u32,
369    _marker: PhantomData<&'a ()>,
370}
371
372impl<'a, K: 'a, V: 'a> RangeBase<'a, K, V> {
373    #[inline]
374    pub fn new(
375        front_leaf: LeafNode<K, V>, front_idx: u32, back_leaf: LeafNode<K, V>, back_idx: u32,
376    ) -> Self {
377        Self { front_leaf, front_idx, back_leaf, back_idx, _marker: PhantomData }
378    }
379
380    /// Advance forward and return the current leaf and index
381    /// Returns None when range is exhausted, caller should set RangeBase to None
382    #[inline]
383    fn advance_forward(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
384        loop {
385            let idx = self.front_idx;
386            if self.front_leaf == self.back_leaf {
387                if idx < self.back_idx {
388                    self.front_idx = idx + 1;
389                    return Some((&self.front_leaf, idx));
390                } else {
391                    return None;
392                }
393            } else {
394                if idx < self.front_leaf.key_count() {
395                    self.front_idx = idx + 1;
396                    return Some((&self.front_leaf, idx));
397                } else {
398                    self.front_leaf = self.front_leaf.get_right_node().unwrap();
399                    self.front_idx = 0;
400                    // Because we always need to compare front_leaf and back_leaf after cursor
401                    // moves, cannot use IterForward & IterBackward here.
402                }
403            }
404        }
405    }
406
407    /// Advance backward and return the current leaf and index
408    /// Returns None when range is exhausted, caller should set RangeBase to None
409    #[inline]
410    fn advance_backward(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
411        loop {
412            if self.back_leaf == self.front_leaf {
413                if self.back_idx == 0 {
414                    return None;
415                }
416                self.back_idx -= 1;
417                if self.back_idx >= self.front_idx {
418                    return Some((&self.back_leaf, self.back_idx));
419                } else {
420                    return None;
421                }
422            } else {
423                if self.back_idx == 0 {
424                    self.back_leaf = self.back_leaf.get_left_node().unwrap();
425                    self.back_idx = self.back_leaf.key_count();
426                    // Because we always need to compare front_leaf and back_leaf after cursor
427                    // moves, cannot use IterForward & IterBackward here.
428                } else {
429                    self.back_idx -= 1;
430                    return Some((&self.back_leaf, self.back_idx));
431                }
432            }
433        }
434    }
435}
436
437/// An iterator over a sub-range of entries in a BTreeMap
438/// RangeBase is wrapped in Option - when exhausted, it becomes None
439pub struct Range<'a, K: 'a, V: 'a> {
440    base: Option<RangeBase<'a, K, V>>,
441}
442
443impl<'a, K: 'a, V: 'a> Range<'a, K, V> {
444    #[inline]
445    pub(super) fn new(base: Option<RangeBase<'a, K, V>>) -> Self {
446        Self { base }
447    }
448}
449
450impl<'a, K: 'a, V: 'a> Iterator for Range<'a, K, V> {
451    type Item = (&'a K, &'a V);
452
453    #[inline]
454    fn next(&mut self) -> Option<Self::Item> {
455        let base = self.base.as_mut()?;
456        if let Some((leaf, idx)) = base.advance_forward() {
457            unsafe {
458                let key = (*leaf.key_ptr(idx)).assume_init_ref();
459                let value = (*leaf.value_ptr(idx)).assume_init_ref();
460                Some((key, value))
461            }
462        } else {
463            self.base = None;
464            None
465        }
466    }
467}
468
469impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Range<'a, K, V> {
470    #[inline]
471    fn next_back(&mut self) -> Option<Self::Item> {
472        let base = self.base.as_mut()?;
473        if let Some((leaf, idx)) = base.advance_backward() {
474            unsafe {
475                let key = (*leaf.key_ptr(idx)).assume_init_ref();
476                let value = (*leaf.value_ptr(idx)).assume_init_ref();
477                Some((key, value))
478            }
479        } else {
480            self.base = None;
481            None
482        }
483    }
484}
485
486/// A mutable iterator over a sub-range of entries in a BTreeMap
487/// RangeBase is wrapped in Option - when exhausted, it becomes None
488pub struct RangeMut<'a, K: 'a, V: 'a> {
489    base: Option<RangeBase<'a, K, V>>,
490}
491
492impl<'a, K: 'a, V: 'a> RangeMut<'a, K, V> {
493    #[inline]
494    pub(super) fn new(base: Option<RangeBase<'a, K, V>>) -> Self {
495        Self { base }
496    }
497}
498
499impl<'a, K: 'a, V: 'a> Iterator for RangeMut<'a, K, V> {
500    type Item = (&'a K, &'a mut V);
501
502    #[inline]
503    fn next(&mut self) -> Option<Self::Item> {
504        let base = self.base.as_mut()?;
505        if let Some((leaf, idx)) = base.advance_forward() {
506            unsafe {
507                let key = (*leaf.key_ptr(idx)).assume_init_ref();
508                let value = (*leaf.value_ptr(idx)).assume_init_mut();
509                Some((key, value))
510            }
511        } else {
512            self.base = None;
513            None
514        }
515    }
516}
517
518impl<'a, K: 'a, V: 'a> DoubleEndedIterator for RangeMut<'a, K, V> {
519    #[inline]
520    fn next_back(&mut self) -> Option<Self::Item> {
521        let base = self.base.as_mut()?;
522        if let Some((leaf, idx)) = base.advance_backward() {
523            unsafe {
524                let key = (*leaf.key_ptr(idx)).assume_init_ref();
525                let value = (*leaf.value_ptr(idx)).assume_init_mut();
526                Some((key, value))
527            }
528        } else {
529            self.base = None;
530            None
531        }
532    }
533}
534
535struct IntoIterBase<K: Ord + Clone + Sized, V: Sized> {
536    /// Path cache for deallocating internal nodes after iteration
537    cache: PathCache<K, V>,
538    /// Current leaf being iterated
539    leaf: Option<LeafNode<K, V>>,
540    /// Current index within the leaf
541    idx: u32,
542    /// Remaining elements to iterate
543    remaining: usize,
544    is_forward: bool,
545}
546
547impl<K: Ord + Clone + Sized, V: Sized> IntoIterBase<K, V> {
548    #[inline]
549    fn new(tree: &mut BTreeMap<K, V>, is_forward: bool) -> Self {
550        if let Some(root) = tree.root.take() {
551            let mut cache = tree.get_cache().take();
552            let leaf = if is_forward {
553                root.find_first_leaf(Some(&mut cache))
554            } else {
555                root.find_last_leaf(Some(&mut cache))
556            };
557            Self {
558                cache,
559                idx: if is_forward { 0 } else { leaf.key_count() },
560                leaf: Some(leaf),
561                remaining: tree.len,
562                is_forward,
563            }
564        } else {
565            Self { cache: PathCache::new(), leaf: None, idx: 0, remaining: 0, is_forward }
566        }
567    }
568
569    #[inline(always)]
570    fn advance_forward(&mut self) -> LeafNode<K, V> {
571        let _leaf = self.leaf.take().unwrap();
572        _leaf.dealloc::<false>();
573        let (parent, idx) = self.cache.move_right_and_pop_l1(InterNode::dealloc::<true>).unwrap();
574        self.cache.push(parent.clone(), idx);
575        let new_leaf = parent.get_child(idx).into_leaf();
576        self.idx = 0;
577        new_leaf
578    }
579
580    #[inline(always)]
581    fn advance_backward(&mut self) -> LeafNode<K, V> {
582        let _leaf = self.leaf.take().unwrap();
583        _leaf.dealloc::<false>();
584        let (parent, idx) = self.cache.move_left_and_pop_l1(InterNode::dealloc::<true>).unwrap();
585        self.cache.push(parent.clone(), idx);
586        let new_leaf = parent.get_child(idx).into_leaf();
587        self.idx = new_leaf.key_count();
588        new_leaf
589    }
590
591    #[inline]
592    fn next(&mut self) -> Option<(K, V)> {
593        if self.remaining == 0 {
594            return None;
595        }
596        self.remaining -= 1;
597
598        // Check if we need to advance to next/prev leaf
599        if self.is_forward {
600            if let Some(ref leaf) = self.leaf {
601                if self.idx >= leaf.key_count() {
602                    let new_leaf = self.advance_forward();
603                    self.leaf = Some(new_leaf);
604                }
605            } else {
606                return None;
607            }
608            let idx = self.idx;
609            self.idx += 1;
610            if let Some(ref leaf) = self.leaf {
611                trace_log!("into_iter forward: {leaf:?}:{idx}");
612                unsafe {
613                    let key = (*leaf.key_ptr(idx)).assume_init_read();
614                    let value = (*leaf.value_ptr(idx)).assume_init_read();
615                    return Some((key, value));
616                }
617            }
618        } else {
619            if self.idx == 0 {
620                if let Some(ref leaf) = self.leaf {
621                    leaf.get_left_node()?;
622                }
623                let new_leaf = self.advance_backward();
624                self.leaf = Some(new_leaf);
625            }
626            if let Some(ref leaf) = self.leaf {
627                self.idx -= 1;
628                let idx = self.idx;
629                trace_log!("into_iter backward: {leaf:?}:{idx}");
630                unsafe {
631                    let key = (*leaf.key_ptr(idx)).assume_init_read();
632                    let value = (*leaf.value_ptr(idx)).assume_init_read();
633                    return Some((key, value));
634                }
635            }
636        }
637        None
638    }
639}
640
641impl<K: Ord + Clone + Sized, V: Sized> Drop for IntoIterBase<K, V> {
642    fn drop(&mut self) {
643        // NOTE: if the original tree has root, then self.leaf always exists after iteration done
644        if let Some(leaf) = self.leaf.take() {
645            if needs_drop::<K>() {
646                if self.is_forward {
647                    trace_log!("into_iter drop forward {leaf:?} [{}..]", self.idx);
648                    for idx in self.idx..leaf.key_count() {
649                        unsafe { (*leaf.key_ptr(idx)).assume_init_drop() };
650                    }
651                } else {
652                    trace_log!("into_iter drop backward {leaf:?} [..{}]", self.idx);
653                    for idx in 0..self.idx {
654                        unsafe { (*leaf.key_ptr(idx)).assume_init_drop() };
655                    }
656                }
657            }
658            if needs_drop::<V>() {
659                if self.is_forward {
660                    for idx in self.idx..leaf.key_count() {
661                        unsafe { (*leaf.value_ptr(idx)).assume_init_drop() };
662                    }
663                } else {
664                    for idx in 0..self.idx {
665                        unsafe { (*leaf.value_ptr(idx)).assume_init_drop() };
666                    }
667                }
668            }
669            leaf.dealloc::<false>();
670            // We should free the rest internal nodes even after leaf iteration done
671            if self.is_forward {
672                while let Some((parent, idx)) =
673                    self.cache.move_right_and_pop_l1(InterNode::dealloc::<true>)
674                {
675                    trace_log!("into_iter drop forward parent {parent:?}:{idx}");
676                    self.cache.push(parent.clone(), idx);
677                    if let Node::Leaf(leaf) = parent.get_child(idx) {
678                        leaf.dealloc::<true>();
679                    } else {
680                        unreachable!();
681                    }
682                }
683            } else {
684                while let Some((parent, idx)) =
685                    self.cache.move_left_and_pop_l1(InterNode::dealloc::<true>)
686                {
687                    trace_log!("into_iter drop forward parent {parent:?}:{idx}");
688                    self.cache.push(parent.clone(), idx);
689                    if let Node::Leaf(leaf) = parent.get_child(idx) {
690                        leaf.dealloc::<true>();
691                    } else {
692                        unreachable!();
693                    }
694                }
695            }
696        }
697    }
698}
699
700/// An owning iterator over the entries of a BTreeMap
701/// Uses PathCache to manage tree traversal and safe deallocation
702///
703/// NOTE: In order to keep the logic simple, we does not implement `DoubleEndedIterator` here
704pub struct IntoIter<K: Ord + Clone + Sized, V: Sized> {
705    /// If true, iterate in reverse order
706    base: Result<IntoIterBase<K, V>, (BTreeMap<K, V>, bool)>,
707}
708
709impl<K: Ord + Clone + Sized, V: Sized> IntoIter<K, V> {
710    #[inline]
711    pub(super) fn new(tree: BTreeMap<K, V>, is_forward: bool) -> Self {
712        Self { base: Err((tree, is_forward)) }
713    }
714
715    /// Return a iterator in reversed direction
716    ///
717    /// IntoIter only implement one way iteration (either forward or backward).
718    /// this will mock Iterator::rev for DoubleEndIterator trait
719    ///
720    /// # Panic
721    ///
722    /// If iteration already started, cannot change the direction
723    #[inline]
724    pub fn rev(self) -> Self {
725        if let Err((tree, _is_forward)) = self.base {
726            Self { base: Err((tree, false)) }
727        } else {
728            panic!("cannot change direction after iteration start");
729        }
730    }
731}
732
733impl<K: Ord + Clone + Sized, V: Sized> Iterator for IntoIter<K, V> {
734    type Item = (K, V);
735
736    #[inline]
737    fn next(&mut self) -> Option<Self::Item> {
738        match &mut self.base {
739            Ok(base) => base.next(),
740            Err((tree, is_forward)) => {
741                self.base = Ok(IntoIterBase::new(tree, *is_forward));
742                if let Ok(base) = &mut self.base {
743                    base.next()
744                } else {
745                    unreachable!();
746                }
747            }
748        }
749    }
750
751    #[inline]
752    fn size_hint(&self) -> (usize, Option<usize>) {
753        let remaining = match &self.base {
754            Ok(base) => base.remaining,
755            Err((tree, _)) => tree.len(),
756        };
757        (remaining, Some(remaining))
758    }
759}
760
761impl<K: Ord + Clone + Sized, V: Sized> ExactSizeIterator for IntoIter<K, V> {
762    #[inline]
763    fn len(&self) -> usize {
764        match &self.base {
765            Ok(base) => base.remaining,
766            Err((tree, _)) => tree.len(),
767        }
768    }
769}
embed_collections/btree/iter.rs

embed_collections/btree/
iter.rs
