nekolib/algo/
minmax.rs

1//! スライスの最小値・最大値を求める。
2
3use std::cmp::Ordering::{self, Equal, Greater, Less};
4
5/// スライスの最小値および最大値を求める。
6///
7/// 該当する要素が複数個あった場合、最小値は最左のもの、最大値は最右のものが選ばれる。
8/// スライスが空の場合は `None` を返す。
9///
10/// # Suggestions
11/// 最小値・最大値の添字ではなく最小値・最大値自体を返すようになっている。
12/// 添字が欲しい場合は [`minmax_by_key`] を利用するのがよい？ あるいは設計を変える？
13///
14/// # Complexity
15/// [`minmax_by`] における `compare` の呼び出し回数と同じだけ、要素間の比較を行う。
16///
17/// # Notes
18/// 詳細については [`minmax_by`] を参照。
19///
20/// # Examples
21/// ```
22/// use nekolib::algo::minmax;
23///
24/// assert_eq!(minmax(&[3, 2, 4, 1, 2, 0, 6]), Some((&0, &6)));
25/// assert_eq!(minmax(&Vec::<i32>::new()), None);
26/// ```
27///
28/// [`minmax_by`]: fn.minmax_by.html
29/// [`minmax_by_key`]: fn.minmax_by_key.html
30pub fn minmax<T: Ord>(buf: &[T]) -> Option<(&T, &T)> {
31    minmax_by(buf, |x: &T, y: &T| x.cmp(y))
32}
33
34/// キー `key` におけるスライスの最小値および最大値を求める。
35///
36/// 該当する要素が複数個あった場合、最小値は最左のもの、最大値は最右のものが選ばれる。
37/// スライスが空の場合は `None` を返す。
38///
39/// # Complexity
40/// [`minmax_by`] における `compare` の呼び出し回数と同じだけ、要素間の比較を行う。
41/// また、`key` の呼び出しをその $2$ 倍の回数だけ行う。
42///
43/// # Implementation notes
44/// 実装を [`minmax_by`] に丸投げしているので `key` を $3n$ 回程度呼び出しうるが、
45/// 適切に実装することで $n$ 回に抑えられるはず。
46///
47/// `key` のコストが大きい場合は予め別の配列を作る方がよさそう。
48///
49/// # Notes
50/// 詳細については [`minmax_by`] を参照。
51///
52/// # Examples
53/// ```
54/// use nekolib::algo::minmax_by_key;
55///
56/// let buf: Vec<_> =
57///     vec![3, 5, 0, 1, 2, 0, 5].into_iter().enumerate().collect();
58/// assert_eq!(minmax_by_key(&buf, |&(_, x)| x), Some((&(2, 0), &(6, 5))));
59///
60/// let buf: Vec<i32> = vec![];
61/// assert_eq!(minmax_by_key(&buf, |&x| x), None);
62/// ```
63///
64/// [`minmax_by`]: fn.minmax_by.html
65pub fn minmax_by_key<T, K, U>(buf: &[T], mut key: K) -> Option<(&T, &T)>
66where
67    K: FnMut(&T) -> U,
68    U: Ord,
69{
70    minmax_by(buf, |x: &T, y: &T| key(&x).cmp(&key(&y)))
71}
72
73/// 比較関数 `compare` におけるスライスの最小値および最大値を求める。
74///
75/// 該当する要素が複数個あった場合、最小値は最左のもの、最大値は最右のものが選ばれる。
76/// スライスが空の場合は `None` を返す。
77///
78/// # Complexity
79/// 要素数を $n \\gt 0$ として、`compare` の呼び出しを
80/// $\\lceil\\frac{3n}{2}\\rceil -2 \\lt 1.5n$
81/// 回行う。
82/// スライスが空の場合は $0$ 回の呼び出しを行う。
83///
84/// この比較回数は最適であり、下界は [adversary argument] によって示すことができる。
85///
86/// [adversary argument]: https://jeffe.cs.illinois.edu/teaching/algorithms/notes/13-adversary.pdf
87///
88/// # Notes
89///
90/// C++ では比較を `bool` の二値で行うため [`std::minmax_element`] は等価な要素の扱いに困る。
91/// 最小値も最大値も最左のものを返そうとすると、比較回数の下界を達成できないはず。
92/// 一方 Rust では、[`Ordering`] の三値を返すので、実装を変えることで任意のペアを返すことが可能。
93///
94/// [`std::minmax_element`]: https://en.cppreference.com/w/cpp/algorithm/minmax_element
95/// [`Ordering`]: https://doc.rust-lang.org/std/cmp/enum.Ordering.html
96///
97/// # Examples
98/// ```
99/// use nekolib::algo::minmax_by;
100///
101/// let buf: Vec<_> =
102///     vec![3, 9, 0, 1, 2, 0, 9].into_iter().enumerate().collect();
103/// let rev = |&(_, x): &(usize, i32), &(_, y): &(usize, i32)| y.cmp(&x);
104/// assert_eq!(minmax_by(&buf, rev), Some((&(1, 9), &(5, 0))));
105///
106/// let buf = vec![];
107/// assert_eq!(minmax_by(&buf, rev), None);
108/// ```
109pub fn minmax_by<T, F: FnMut(&T, &T) -> Ordering>(
110    buf: &[T],
111    mut compare: F,
112) -> Option<(&T, &T)> {
113    if buf.is_empty() {
114        return None;
115    }
116    if buf.len() == 1 {
117        return Some((&buf[0], &buf[0]));
118    }
119    let (mut min, mut max) = match compare(&buf[0], &buf[1]) {
120        Less | Equal => (&buf[0], &buf[1]),
121        Greater => (&buf[1], &buf[0]),
122    };
123    for i in (2..buf.len()).step_by(2) {
124        let (min_i, max_i) = match (buf.get(i), buf.get(i + 1)) {
125            (Some(f), None) => (f, f),
126            (Some(f), Some(s)) => match compare(f, s) {
127                Less | Equal => (f, s),
128                Greater => (s, f),
129            },
130            (None, _) => unreachable!(),
131        };
132        if compare(min_i, min) == Less {
133            min = min_i;
134        }
135        if compare(max_i, max) != Less {
136            max = max_i;
137        }
138    }
139    Some((min, max))
140}
141
142#[test]
143fn test() {
144    use std::fmt::Debug;
145    fn test_inner<T: Debug + Eq + Ord>(
146        expected: Option<(&(usize, &T), &(usize, &T))>,
147        buf: &[T],
148    ) {
149        let mut cmped = 0;
150        let counted_cmp = |x: &(usize, &T), y: &(usize, &T)| {
151            cmped += 1;
152            x.1.cmp(y.1)
153        };
154        let buf: Vec<_> = buf.iter().enumerate().collect();
155        let n = buf.len();
156        assert_eq!(minmax_by(&buf, counted_cmp), expected);
157        if n == 0 {
158            assert_eq!(cmped, 0);
159        } else {
160            assert_eq!(cmped, n / 2 + (n - 1) / 2 * 2);
161        }
162    }
163
164    test_inner(Some((&(0, &0), &(0, &0))), &[0]);
165
166    test_inner(Some((&(0, &0), &(1, &0))), &[0, 0]);
167    test_inner(Some((&(0, &0), &(1, &10))), &[0, 10]);
168    test_inner(Some((&(1, &0), &(0, &10))), &[10, 0]);
169
170    test_inner(Some((&(0, &0), &(2, &0))), &[0, 0, 0]);
171    test_inner(Some((&(0, &0), &(2, &20))), &[0, 10, 20]);
172    test_inner(Some((&(0, &0), &(2, &10))), &[0, 10, 10]);
173    test_inner(Some((&(0, &10), &(1, &20))), &[10, 20, 10]);
174
175    test_inner(Some((&(0, &0), &(3, &0))), &[0, 0, 0, 0]);
176    test_inner(Some((&(0, &0), &(3, &10))), &[0, 10, 0, 10]);
177    test_inner(Some((&(1, &0), &(2, &10))), &[10, 0, 10, 0]);
178    test_inner(Some((&(0, &0), &(3, &10))), &[0, 0, 10, 10]);
179    test_inner(Some((&(2, &0), &(1, &10))), &[10, 10, 0, 0]);
180
181    let rev = |&(_, x): &(usize, i32), &(_, y): &(usize, i32)| y.cmp(&x);
182    let buf = vec![];
183    assert_eq!(minmax_by(&buf, rev), None);
184}
nekolib/algo/minmax.rs

nekolib/algo/
minmax.rs
