| 1 |
|
| 2 |
/// `MinMaxResult` is an enum returned by `minmax`. |
| 3 |
/// |
| 4 |
/// See [`.minmax()`](crate::Itertools::minmax) for more detail. |
| 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 |
} |