Function nekolib::algo::minmax_by

pub fn minmax_by<T, F: FnMut(&T, &T) -> Ordering>(
    buf: &[T],
    compare: F
) -> Option<(&T, &T)>

比較関数 compare におけるスライスの最小値および最大値を求める。

該当する要素が複数個あった場合、最小値は最左のもの、最大値は最右のものが選ばれる。 スライスが空の場合は None を返す。

Complexity

要素数を $n \gt 0$ として、compare の呼び出しを $\lceil\frac{3n}{2}\rceil -2 \lt 1.5n$ 回行う。 スライスが空の場合は $0$ 回の呼び出しを行う。

この比較回数は最適であり、下界は adversary argument によって示すことができる。

Notes

C++ では比較を bool の二値で行うため std::minmax_element は等価な要素の扱いに困る。 最小値も最大値も最左のものを返そうとすると、比較回数の下界を達成できないはず。 一方 Rust では、Ordering の三値を返すので、実装を変えることで任意のペアを返すことが可能。

Examples

use nekolib::algo::minmax_by;

let buf: Vec<_> =
    vec![3, 9, 0, 1, 2, 0, 9].into_iter().enumerate().collect();
let rev = |&(_, x): &(usize, i32), &(_, y): &(usize, i32)| y.cmp(&x);
assert_eq!(minmax_by(&buf, rev), Some((&(1, 9), &(5, 0))));

let buf = vec![];
assert_eq!(minmax_by(&buf, rev), None);