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