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