interleaved_ordered/
lib.rs

1//! Interleave two ordered iterators to create a new ordered iterator.
2
3use std::cmp::Ord;
4use std::iter::Fuse;
5
6enum Pending<T> {
7    None,
8    A(T),
9    B(T),
10}
11
12impl<T> Pending<T> {
13    fn take(&mut self) -> Self {
14        ::std::mem::replace(self, Pending::None)
15    }
16}
17
18/// Iterator that encapsulates two other ordered iterators to yield their results
19/// in order.
20pub struct InterleaveOrdered<A, B> where A: Iterator, B: Iterator<Item=A::Item> {
21    pending_next: Pending<A::Item>,
22    a: Fuse<A>,
23    b: Fuse<B>,
24}
25
26impl<A, B> Iterator for InterleaveOrdered<A, B> 
27    where A: Iterator, 
28          B: Iterator<Item=A::Item>,
29          A::Item: Ord
30{
31    type Item = A::Item;
32    
33    fn next(&mut self) -> Option<Self::Item> {
34        let (a, b) = match self.pending_next.take() {
35            Pending::None => (self.a.next(), self.b.next()),
36            Pending::A(a) => (Some(a), self.b.next()),
37            Pending::B(b) => (self.a.next(), Some(b)),
38        };
39        
40        match (a, b) {
41            (Some(a), Some(b)) => {
42                let (res, pending) = if a < b {
43                    (a, Pending::B(b))
44                } else {
45                    (b, Pending::A(a))
46                };
47                
48                self.pending_next = pending;
49                Some(res)
50            }
51            (Some(x), _) | (_, Some(x)) => Some(x),
52            (None, None) => None
53        }
54    }
55}
56
57/// Interleave two ordered iterators, yielding a new iterator whose items are also ordered.
58///
59/// ```rust
60/// use interleaved_ordered::interleave_ordered;
61/// let a = [1, 1, 2, 3, 5, 7, 9];
62/// let b = [2, 3, 4, 5, 6, 7, 10];
63/// let iter = interleave_ordered(&a, b.iter());
64    
65/// assert_eq!(
66///    interleave_ordered(&a, &b).cloned().collect::<Vec<_>>(), 
67///    vec![1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 9, 10]
68/// )
69/// ```
70pub fn interleave_ordered<A, B>(a: A, b: B) -> InterleaveOrdered<A::IntoIter, B::IntoIter>
71    where A: IntoIterator, B: IntoIterator<Item=A::Item>
72{
73    InterleaveOrdered {
74        pending_next: Pending::None,
75        a: a.into_iter().fuse(),
76        b: b.into_iter().fuse(),
77    }
78}
interleaved_ordered/lib.rs

interleaved_ordered/
lib.rs
