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}
116