alloc/collections/btree/
merge_iter.rs

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(super) 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(#[automatically_derived]
impl<I: ::core::clone::Clone + Iterator> ::core::clone::Clone for Peeked<I>
    where I::Item: ::core::clone::Clone, I::Item: ::core::clone::Clone {
    #[inline]
    fn clone(&self) -> Peeked<I> {
        match self {
            Peeked::A(__self_0) =>
                Peeked::A(::core::clone::Clone::clone(__self_0)),
            Peeked::B(__self_0) =>
                Peeked::B(::core::clone::Clone::clone(__self_0)),
        }
    }
}Clone, #[automatically_derived]
impl<I: ::core::fmt::Debug + Iterator> ::core::fmt::Debug for Peeked<I> where
    I::Item: ::core::fmt::Debug, I::Item: ::core::fmt::Debug {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        match self {
            Peeked::A(__self_0) =>
                ::core::fmt::Formatter::debug_tuple_field1_finish(f, "A",
                    &__self_0),
            Peeked::B(__self_0) =>
                ::core::fmt::Formatter::debug_tuple_field1_finish(f, "B",
                    &__self_0),
        }
    }
}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 { a: self.a.clone(), b: self.b.clone(), peeked: self.peeked.clone() }
28    }
29}
30
31impl<I: Iterator> Debug for MergeIterInner<I>
32where
33    I: Debug,
34    I::Item: Debug,
35{
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        f.debug_tuple("MergeIterInner").field(&self.a).field(&self.b).field(&self.peeked).finish()
38    }
39}
40
41impl<I: Iterator> MergeIterInner<I> {
42    /// Creates a new core for an iterator merging a pair of sources.
43    pub(super) fn new(a: I, b: I) -> Self {
44        MergeIterInner { a, b, peeked: None }
45    }
46
47    /// Returns the next pair of items stemming from the pair of sources
48    /// being merged. If both returned options contain a value, that value
49    /// is equal and occurs in both sources. If one of the returned options
50    /// contains a value, that value doesn't occur in the other source (or
51    /// the sources are not strictly ascending). If neither returned option
52    /// contains a value, iteration has finished and subsequent calls will
53    /// return the same empty pair.
54    pub(super) fn nexts<Cmp: Fn(&I::Item, &I::Item) -> Ordering>(
55        &mut self,
56        cmp: Cmp,
57    ) -> (Option<I::Item>, Option<I::Item>)
58    where
59        I: FusedIterator,
60    {
61        let mut a_next;
62        let mut b_next;
63        match self.peeked.take() {
64            Some(Peeked::A(next)) => {
65                a_next = Some(next);
66                b_next = self.b.next();
67            }
68            Some(Peeked::B(next)) => {
69                b_next = Some(next);
70                a_next = self.a.next();
71            }
72            None => {
73                a_next = self.a.next();
74                b_next = self.b.next();
75            }
76        }
77        if let (Some(a1), Some(b1)) = (&a_next, &b_next) {
78            match cmp(a1, b1) {
79                Ordering::Less => self.peeked = b_next.take().map(Peeked::B),
80                Ordering::Greater => self.peeked = a_next.take().map(Peeked::A),
81                Ordering::Equal => (),
82            }
83        }
84        (a_next, b_next)
85    }
86
87    /// Returns a pair of upper bounds for the `size_hint` of the final iterator.
88    pub(super) fn lens(&self) -> (usize, usize)
89    where
90        I: ExactSizeIterator,
91    {
92        match self.peeked {
93            Some(Peeked::A(_)) => (1 + self.a.len(), self.b.len()),
94            Some(Peeked::B(_)) => (self.a.len(), 1 + self.b.len()),
95            _ => (self.a.len(), self.b.len()),
96        }
97    }
98}
alloc/collections/btree/merge_iter.rs

alloc/collections/btree/
merge_iter.rs
