itertools/
merge_join.rs

1use std::cmp::Ordering;
2use std::iter::Fuse;
3use std::fmt;
4
5use super::adaptors::{PutBack, put_back};
6use either_or_both::EitherOrBoth;
7
8/// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order.
9///
10/// See [`.merge_join_by()`](trait.Itertools.html#method.merge_join_by) for more information.
11pub fn merge_join_by<I, J, F>(left: I, right: J, cmp_fn: F)
12    -> MergeJoinBy<I::IntoIter, J::IntoIter, F>
13    where I: IntoIterator,
14          J: IntoIterator,
15          F: FnMut(&I::Item, &J::Item) -> Ordering
16{
17    MergeJoinBy {
18        left: put_back(left.into_iter().fuse()),
19        right: put_back(right.into_iter().fuse()),
20        cmp_fn: cmp_fn
21    }
22}
23
24/// An iterator adaptor that merge-joins items from the two base iterators in ascending order.
25///
26/// See [`.merge_join_by()`](../trait.Itertools.html#method.merge_join_by) for more information.
27#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
28pub struct MergeJoinBy<I: Iterator, J: Iterator, F> {
29    left: PutBack<Fuse<I>>,
30    right: PutBack<Fuse<J>>,
31    cmp_fn: F
32}
33
34impl<I, J, F> fmt::Debug for MergeJoinBy<I, J, F>
35    where I: Iterator + fmt::Debug,
36          I::Item: fmt::Debug,
37          J: Iterator + fmt::Debug,
38          J::Item: fmt::Debug,
39{
40    debug_fmt_fields!(MergeJoinBy, left, right);
41}
42
43impl<I, J, F> Iterator for MergeJoinBy<I, J, F>
44    where I: Iterator,
45          J: Iterator,
46          F: FnMut(&I::Item, &J::Item) -> Ordering
47{
48    type Item = EitherOrBoth<I::Item, J::Item>;
49
50    fn next(&mut self) -> Option<Self::Item> {
51        match (self.left.next(), self.right.next()) {
52            (None, None) => None,
53            (Some(left), None) =>
54                Some(EitherOrBoth::Left(left)),
55            (None, Some(right)) =>
56                Some(EitherOrBoth::Right(right)),
57            (Some(left), Some(right)) => {
58                match (self.cmp_fn)(&left, &right) {
59                    Ordering::Equal =>
60                        Some(EitherOrBoth::Both(left, right)),
61                    Ordering::Less => {
62                        self.right.put_back(right);
63                        Some(EitherOrBoth::Left(left))
64                    },
65                    Ordering::Greater => {
66                        self.left.put_back(left);
67                        Some(EitherOrBoth::Right(right))
68                    }
69                }
70            }
71        }
72    }
73
74    fn size_hint(&self) -> (usize, Option<usize>) {
75        let (a_lower, a_upper) = self.left.size_hint();
76        let (b_lower, b_upper) = self.right.size_hint();
77
78        let lower = ::std::cmp::max(a_lower, b_lower);
79
80        let upper = match (a_upper, b_upper) {
81            (Some(x), Some(y)) => Some(x + y),
82            _ => None,
83        };
84
85        (lower, upper)
86    }
87}