vendor/itertools-0.8.2/src/merge_join.rs

   1 use std::cmp::Ordering;
   2 use std::iter::Fuse;
   3 use std::fmt;
   4
   5 use super::adaptors::{PutBack, put_back};
   6 use 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.
  11 pub 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"]
  28 pub struct MergeJoinBy<I: Iterator, J: Iterator, F> {
  29     left: PutBack<Fuse<I>>,
  30     right: PutBack<Fuse<J>>,
  31     cmp_fn: F
  32 }
  33
  34 impl<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
  43 impl<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 }