vendor/itertools-0.8.0/src/minmax.rs

   1
   2 /// `MinMaxResult` is an enum returned by `minmax`. See `Itertools::minmax()` for
   3 /// more detail.
   4 #[derive(Copy, Clone, PartialEq, Debug)]
   5 pub enum MinMaxResult<T> {
   6     /// Empty iterator
   7     NoElements,
   8
   9     /// Iterator with one element, so the minimum and maximum are the same
  10     OneElement(T),
  11
  12     /// More than one element in the iterator, the first element is not larger
  13     /// than the second
  14     MinMax(T, T)
  15 }
  16
  17 impl<T: Clone> MinMaxResult<T> {
  18     /// `into_option` creates an `Option` of type `(T, T)`. The returned `Option`
  19     /// has variant `None` if and only if the `MinMaxResult` has variant
  20     /// `NoElements`. Otherwise `Some((x, y))` is returned where `x <= y`.
  21     /// If the `MinMaxResult` has variant `OneElement(x)`, performing this
  22     /// operation will make one clone of `x`.
  23     ///
  24     /// # Examples
  25     ///
  26     /// ```
  27     /// use itertools::MinMaxResult::{self, NoElements, OneElement, MinMax};
  28     ///
  29     /// let r: MinMaxResult<i32> = NoElements;
  30     /// assert_eq!(r.into_option(), None);
  31     ///
  32     /// let r = OneElement(1);
  33     /// assert_eq!(r.into_option(), Some((1, 1)));
  34     ///
  35     /// let r = MinMax(1, 2);
  36     /// assert_eq!(r.into_option(), Some((1, 2)));
  37     /// ```
  38     pub fn into_option(self) -> Option<(T,T)> {
  39         match self {
  40             MinMaxResult::NoElements => None,
  41             MinMaxResult::OneElement(x) => Some((x.clone(), x)),
  42             MinMaxResult::MinMax(x, y) => Some((x, y))
  43         }
  44     }
  45 }
  46
  47 /// Implementation guts for `minmax` and `minmax_by_key`.
  48 pub fn minmax_impl<I, K, F, L>(mut it: I, mut key_for: F,
  49                                mut lt: L) -> MinMaxResult<I::Item>
  50     where I: Iterator,
  51           F: FnMut(&I::Item) -> K,
  52           L: FnMut(&I::Item, &I::Item, &K, &K) -> bool,
  53 {
  54     let (mut min, mut max, mut min_key, mut max_key) = match it.next() {
  55         None => return MinMaxResult::NoElements,
  56         Some(x) => {
  57             match it.next() {
  58                 None => return MinMaxResult::OneElement(x),
  59                 Some(y) => {
  60                     let xk = key_for(&x);
  61                     let yk = key_for(&y);
  62                     if !lt(&y, &x, &yk, &xk) {(x, y, xk, yk)} else {(y, x, yk, xk)}
  63                 }
  64             }
  65         }
  66     };
  67
  68     loop {
  69         // `first` and `second` are the two next elements we want to look
  70         // at.  We first compare `first` and `second` (#1). The smaller one
  71         // is then compared to current minimum (#2). The larger one is
  72         // compared to current maximum (#3). This way we do 3 comparisons
  73         // for 2 elements.
  74         let first = match it.next() {
  75             None => break,
  76             Some(x) => x
  77         };
  78         let second = match it.next() {
  79             None => {
  80                 let first_key = key_for(&first);
  81                 if lt(&first, &min, &first_key, &min_key) {
  82                     min = first;
  83                 } else if !lt(&first, &max, &first_key, &max_key) {
  84                     max = first;
  85                 }
  86                 break;
  87             }
  88             Some(x) => x
  89         };
  90         let first_key = key_for(&first);
  91         let second_key = key_for(&second);
  92         if !lt(&second, &first, &second_key, &first_key) {
  93             if lt(&first, &min, &first_key, &min_key) {
  94                 min = first;
  95                 min_key = first_key;
  96             }
  97             if !lt(&second, &max, &second_key, &max_key) {
  98                 max = second;
  99                 max_key = second_key;
 100             }
 101         } else {
 102             if lt(&second, &min, &second_key, &min_key) {
 103                 min = second;
 104                 min_key = second_key;
 105             }
 106             if !lt(&first, &max, &first_key, &max_key) {
 107                 max = first;
 108                 max_key = first_key;
 109             }
 110         }
 111     }
 112
 113     MinMaxResult::MinMax(min, max)
 114 }