itertools/
minmax.rs

Help
1
2/// `MinMaxResult` is an enum returned by `minmax`. See `Itertools::minmax()` for
3/// more detail.
4#[derive(Copy, Clone, PartialEq, 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            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`.
48pub 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}
itertools/minmax.rs

itertools/
minmax.rs
