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
use std::cmp::Ord;
use std::iter::Fuse;
enum Pending<T> {
None,
A(T),
B(T),
}
impl<T> Pending<T> {
fn take(&mut self) -> Self {
::std::mem::replace(self, Pending::None)
}
}
pub struct InterleaveOrdered<A, B> where A: Iterator, B: Iterator<Item=A::Item> {
pending_next: Pending<A::Item>,
a: Fuse<A>,
b: Fuse<B>,
}
impl<A, B> Iterator for InterleaveOrdered<A, B>
where A: Iterator,
B: Iterator<Item=A::Item>,
A::Item: Ord
{
type Item = A::Item;
fn next(&mut self) -> Option<Self::Item> {
let (a, b) = match self.pending_next.take() {
Pending::None => (self.a.next(), self.b.next()),
Pending::A(a) => (Some(a), self.b.next()),
Pending::B(b) => (self.a.next(), Some(b)),
};
match (a, b) {
(Some(a), Some(b)) => {
let (res, pending) = if a < b {
(a, Pending::B(b))
} else {
(b, Pending::A(a))
};
self.pending_next = pending;
Some(res)
}
(Some(x), _) | (_, Some(x)) => Some(x),
(None, None) => None
}
}
}
pub fn interleave_ordered<A, B>(a: A, b: B) -> InterleaveOrdered<A::IntoIter, B::IntoIter>
where A: IntoIterator, B: IntoIterator<Item=A::Item>
{
InterleaveOrdered {
pending_next: Pending::None,
a: a.into_iter().fuse(),
b: b.into_iter().fuse(),
}
}