itertools/
minmax.rs

1/// `MinMaxResult` is an enum returned by `minmax`.
2///
3/// See [`.minmax()`](crate::Itertools::minmax) for more detail.
4#[derive(Copy, Clone, PartialEq, Eq, Debug)]
5pub 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
17impl<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            Self::NoElements => None,
41            Self::OneElement(x) => Some((x.clone(), x)),
42            Self::MinMax(x, y) => Some((x, y)),
43        }
44    }
45}
46
47/// Implementation guts for `minmax` and `minmax_by_key`.
48pub fn minmax_impl<I, K, F, L>(mut it: I, mut key_for: F, mut lt: L) -> MinMaxResult<I::Item>
49where
50    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) => match it.next() {
57            None => return MinMaxResult::OneElement(x),
58            Some(y) => {
59                let xk = key_for(&x);
60                let yk = key_for(&y);
61                if !lt(&y, &x, &yk, &xk) {
62                    (x, y, xk, yk)
63                } else {
64                    (y, x, yk, xk)
65                }
66            }
67        },
68    };
69
70    loop {
71        // `first` and `second` are the two next elements we want to look
72        // at.  We first compare `first` and `second` (#1). The smaller one
73        // is then compared to current minimum (#2). The larger one is
74        // compared to current maximum (#3). This way we do 3 comparisons
75        // for 2 elements.
76        let first = match it.next() {
77            None => break,
78            Some(x) => x,
79        };
80        let second = match it.next() {
81            None => {
82                let first_key = key_for(&first);
83                if lt(&first, &min, &first_key, &min_key) {
84                    min = first;
85                } else if !lt(&first, &max, &first_key, &max_key) {
86                    max = first;
87                }
88                break;
89            }
90            Some(x) => x,
91        };
92        let first_key = key_for(&first);
93        let second_key = key_for(&second);
94        if !lt(&second, &first, &second_key, &first_key) {
95            if lt(&first, &min, &first_key, &min_key) {
96                min = first;
97                min_key = first_key;
98            }
99            if !lt(&second, &max, &second_key, &max_key) {
100                max = second;
101                max_key = second_key;
102            }
103        } else {
104            if lt(&second, &min, &second_key, &min_key) {
105                min = second;
106                min_key = second_key;
107            }
108            if !lt(&first, &max, &first_key, &max_key) {
109                max = first;
110                max_key = first_key;
111            }
112        }
113    }
114
115    MinMaxResult::MinMax(min, max)
116}
itertools/minmax.rs

itertools/
minmax.rs
