merging_iterator/
lib.rs

1#![deny(unused, missing_docs)]
2//! `MergeIter` is an iterator that returns the elements of two iterators in order, given both
3//! iterators are sorted.
4//!
5//! **Important note**: This iterator only works as intended, if both input iterators are sorted.
6//! There are no checks in place to validate this property.
7
8#[cfg(test)]
9#[macro_use]
10extern crate proptest;
11
12use std::iter::Peekable;
13
14/// A sorted iterator over two independent sorted iterators.
15pub struct MergeIter<L, R, T>
16where
17    L: Iterator<Item = T>,
18    R: Iterator<Item = T>,
19{
20    left: Peekable<L>,
21    right: Peekable<R>,
22    cmp_function: fn(&T, &T) -> bool,
23}
24
25impl<L, R, T> From<(L, R)> for MergeIter<L, R, T>
26where
27    L: Iterator<Item = T>,
28    R: Iterator<Item = T>,
29    T: Ord,
30{
31    #[inline]
32    fn from((left, right): (L, R)) -> Self {
33        Self::new(left, right)
34    }
35}
36
37impl<L, R, T> MergeIter<L, R, T>
38where
39    L: Iterator<Item = T>,
40    R: Iterator<Item = T>,
41    T: Ord,
42{
43    /// Creates a new `MergeIter` that returns elements from both supplied iterators in order,
44    /// given they are sorted.
45    ///
46    /// # Examples
47    /// ```
48    /// use merging_iterator::MergeIter;
49    /// let a = vec![0, 2, 4, 6, 8];
50    /// let b = vec![1, 3, 5, 7, 9];
51    /// let merger = MergeIter::new(a, b);
52    /// assert_eq!(
53    ///     vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
54    ///     merger.collect::<Vec<_>>()
55    /// );
56    /// ```
57    #[inline]
58    pub fn new<IL, IR>(left: IL, right: IR) -> Self
59    where
60        IL: IntoIterator<IntoIter = L, Item = T>,
61        IR: IntoIterator<IntoIter = R, Item = T>,
62    {
63        Self {
64            left: left.into_iter().peekable(),
65            right: right.into_iter().peekable(),
66            cmp_function: |a, b| a < b,
67        }
68    }
69}
70
71impl<L, R, T> MergeIter<L, R, T>
72where
73    L: Iterator<Item = T>,
74    R: Iterator<Item = T>,
75{
76    /// Creates a new `MergeIter` that uses a custom ordering function.
77    ///
78    /// # Examples
79    /// ```
80    /// use merging_iterator::MergeIter;
81    /// let a = vec![8, 6, 4, 2, 0];
82    /// let b = vec![9, 7, 5, 3, 1];
83    /// let cmp = |a: &u8, b: &u8| b < a;
84    /// let merger = MergeIter::with_custom_ordering(a, b, cmp);
85    /// assert_eq!(
86    ///     vec![9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
87    ///     merger.collect::<Vec<_>>()
88    /// );
89    /// ```
90    #[inline]
91    pub fn with_custom_ordering<IL, IR>(left: IL, right: IR, cmp: fn(&T, &T) -> bool) -> Self
92    where
93        IL: IntoIterator<IntoIter = L, Item = T>,
94        IR: IntoIterator<IntoIter = R, Item = T>,
95    {
96        Self {
97            left: left.into_iter().peekable(),
98            right: right.into_iter().peekable(),
99            cmp_function: cmp,
100        }
101    }
102}
103
104impl<L, R, T> Iterator for MergeIter<L, R, T>
105where
106    L: Iterator<Item = T>,
107    R: Iterator<Item = T>,
108{
109    type Item = T;
110
111    fn next(&mut self) -> Option<Self::Item> {
112        // Temporary enum to prevent issues with the borrow checker
113        enum Next {
114            Left,
115            Right,
116            None,
117        }
118        let n = match (self.left.peek(), self.right.peek()) {
119            (Some(ref l), Some(ref r)) => {
120                if (self.cmp_function)(l, r) {
121                    Next::Left
122                } else {
123                    Next::Right
124                }
125            }
126            (Some(_), None) => Next::Left,
127            (None, Some(_)) => Next::Right,
128            (None, None) => Next::None,
129        };
130        match n {
131            Next::Left => self.left.next(),
132            Next::Right => self.right.next(),
133            Next::None => None,
134        }
135    }
136
137    fn size_hint(&self) -> (usize, Option<usize>) {
138        let (l, lo) = self.left.size_hint();
139        let (r, ro) = self.right.size_hint();
140        (
141            l + r,
142            match (lo, ro) {
143                (Some(lo), Some(ro)) => Some(lo + ro),
144                // no predictable upper bound
145                _ => None,
146            },
147        )
148    }
149}
150
151#[cfg(test)]
152mod tests {
153    use super::*;
154
155    proptest! {
156        #[test]
157        fn test_is_sorted_property(mut a: Vec<i32>, mut b: Vec<i32>) {
158            a.sort_unstable();
159            b.sort_unstable();
160            let merger = MergeIter::new(a, b);
161            assert!(is_sorted(merger));
162        }
163
164        #[test]
165        fn test_is_sorted_property_for_multiple_iterators(
166            mut a: Vec<i32>,
167            mut b: Vec<i32>,
168            mut c: Vec<i32>
169        ) {
170            a.sort_unstable();
171            b.sort_unstable();
172            c.sort_unstable();
173            let merger = MergeIter::new(
174                MergeIter::new(a, b),
175                c
176            );
177            assert!(is_sorted(merger));
178        }
179    }
180
181    #[test]
182    fn test_merge_sorted_iterators() {
183        let expected = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
184
185        let a = vec![1, 3, 5, 7, 9];
186        let b = vec![2, 4, 6, 8];
187        let merger = MergeIter::new(a, b);
188        assert_eq!(expected, merger.collect::<Vec<_>>());
189
190        let a = vec![1, 2, 3, 4, 5];
191        let b = vec![6, 7, 8, 9];
192        let merger = MergeIter::new(a, b);
193        assert_eq!(expected, merger.collect::<Vec<_>>());
194
195        let a = vec![3, 5, 6, 8];
196        let b = vec![1, 2, 4, 7, 9];
197        let merger = MergeIter::new(a, b);
198        assert_eq!(expected, merger.collect::<Vec<_>>());
199
200        let a = vec![];
201        let b = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
202        let merger = MergeIter::new(a, b);
203        assert_eq!(expected, merger.collect::<Vec<_>>());
204
205        let a = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
206        let b = vec![];
207        let merger = MergeIter::new(a, b);
208        assert_eq!(expected, merger.collect::<Vec<_>>());
209    }
210
211    #[test]
212    fn test_multiple_iterators() {
213        let expected = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
214
215        let a = vec![1, 4, 7];
216        let b = vec![2, 5, 8];
217        let c = vec![3, 6, 9];
218        let merger = MergeIter::new(a, b);
219        let merger = MergeIter::new(c, merger);
220        let merger = merger.collect::<Vec<_>>();
221        assert_eq!(expected, merger);
222        assert!(is_sorted(merger.iter()));
223    }
224
225    #[test]
226    fn test_merge_unord() {
227        struct UnOrd;
228
229        let a = vec![UnOrd];
230        let b = vec![UnOrd];
231        let merger = MergeIter::with_custom_ordering(a, b, |_, _| true);
232        let _ = merger.collect::<Vec<_>>();
233    }
234
235    fn is_sorted<I, T>(iter: I) -> bool
236    where
237        I: Iterator<Item = T>,
238        T: Ord,
239    {
240        iter.fold((true, None), |(res, last), next| {
241            (res && last.map(|v| v < next).unwrap_or(true), Some(next))
242        })
243        .0
244    }
245}
merging_iterator/lib.rs

merging_iterator/
lib.rs
