rune_alloc/btree/
merge_iter.rs

Help
1use core::cmp::Ordering;
2use core::fmt::{self, Debug};
3use core::iter::FusedIterator;
4
5/// Core of an iterator that merges the output of two strictly ascending iterators,
6/// for instance a union or a symmetric difference.
7pub(crate) struct MergeIterInner<I: Iterator> {
8    a: I,
9    b: I,
10    peeked: Option<Peeked<I>>,
11}
12
13/// Benchmarks faster than wrapping both iterators in a Peekable,
14/// probably because we can afford to impose a FusedIterator bound.
15#[derive(Clone, Debug)]
16enum Peeked<I: Iterator> {
17    A(I::Item),
18    B(I::Item),
19}
20
21impl<I: Iterator> Clone for MergeIterInner<I>
22where
23    I: Clone,
24    I::Item: Clone,
25{
26    fn clone(&self) -> Self {
27        Self {
28            a: self.a.clone(),
29            b: self.b.clone(),
30            peeked: self.peeked.clone(),
31        }
32    }
33}
34
35impl<I: Iterator> Debug for MergeIterInner<I>
36where
37    I: Debug,
38    I::Item: Debug,
39{
40    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
41        f.debug_tuple("MergeIterInner")
42            .field(&self.a)
43            .field(&self.b)
44            .field(&self.peeked)
45            .finish()
46    }
47}
48
49impl<I: Iterator> MergeIterInner<I> {
50    /// Creates a new core for an iterator merging a pair of sources.
51    pub(crate) fn new(a: I, b: I) -> Self {
52        MergeIterInner { a, b, peeked: None }
53    }
54
55    /// Returns the next pair of items stemming from the pair of sources
56    /// being merged. If both returned options contain a value, that value
57    /// is equal and occurs in both sources. If one of the returned options
58    /// contains a value, that value doesn't occur in the other source (or
59    /// the sources are not strictly ascending). If neither returned option
60    /// contains a value, iteration has finished and subsequent calls will
61    /// return the same empty pair.
62    pub(crate) fn nexts<Cmp: Fn(&I::Item, &I::Item) -> Ordering>(
63        &mut self,
64        cmp: Cmp,
65    ) -> (Option<I::Item>, Option<I::Item>)
66    where
67        I: FusedIterator,
68    {
69        let mut a_next;
70        let mut b_next;
71        match self.peeked.take() {
72            Some(Peeked::A(next)) => {
73                a_next = Some(next);
74                b_next = self.b.next();
75            }
76            Some(Peeked::B(next)) => {
77                b_next = Some(next);
78                a_next = self.a.next();
79            }
80            None => {
81                a_next = self.a.next();
82                b_next = self.b.next();
83            }
84        }
85        if let (Some(ref a1), Some(ref b1)) = (&a_next, &b_next) {
86            match cmp(a1, b1) {
87                Ordering::Less => self.peeked = b_next.take().map(Peeked::B),
88                Ordering::Greater => self.peeked = a_next.take().map(Peeked::A),
89                Ordering::Equal => (),
90            }
91        }
92        (a_next, b_next)
93    }
94
95    /// Returns a pair of upper bounds for the `size_hint` of the final iterator.
96    pub(crate) fn lens(&self) -> (usize, usize)
97    where
98        I: ExactSizeIterator,
99    {
100        match self.peeked {
101            Some(Peeked::A(_)) => (1 + self.a.len(), self.b.len()),
102            Some(Peeked::B(_)) => (self.a.len(), 1 + self.b.len()),
103            _ => (self.a.len(), self.b.len()),
104        }
105    }
106}
rune_alloc/btree/merge_iter.rs

rune_alloc/btree/
merge_iter.rs
