itertools/
minmax.rs

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)]
6pub 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
18impl<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`.
49pub 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}
itertools/minmax.rs

itertools/
minmax.rs
