1 use core::cmp::Ordering;
2 use core::fmt::{self, Debug};
3 use core::iter::FusedIterator;
5 /// Core of an iterator that merges the output of two strictly ascending iterators,
6 /// for instance a union or a symmetric difference.
7 pub struct MergeIterInner<I: Iterator> {
10 peeked: Option<Peeked<I>>,
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)]
16 enum Peeked<I: Iterator> {
21 impl<I: Iterator> Clone for MergeIterInner<I>
26 fn clone(&self) -> Self {
27 Self { a: self.a.clone(), b: self.b.clone(), peeked: self.peeked.clone() }
31 impl<I: Iterator> Debug for MergeIterInner<I>
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()
41 impl<I: Iterator> MergeIterInner<I> {
42 /// Creates a new core for an iterator merging a pair of sources.
43 pub fn new(a: I, b: I) -> Self {
44 MergeIterInner { a, b, peeked: None }
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 fn nexts<Cmp: Fn(&I::Item, &I::Item) -> Ordering>(
57 ) -> (Option<I::Item>, Option<I::Item>)
63 match self.peeked.take() {
64 Some(Peeked::A(next)) => {
66 b_next = self.b.next();
68 Some(Peeked::B(next)) => {
70 a_next = self.a.next();
73 a_next = self.a.next();
74 b_next = self.b.next();
77 if let (Some(ref a1), Some(ref b1)) = (&a_next, &b_next) {
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 => (),
87 /// Returns a pair of upper bounds for the `size_hint` of the final iterator.
88 pub fn lens(&self) -> (usize, usize)
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()),