Function nekolib::algo::index_order_by

pub fn index_order_by<T>(
    buf: &[T],
    compare: impl FnMut((usize, &T), (usize, &T)) -> Ordering
) -> Vec<usize>

添字の順序。

次で定義される $b = (b_0, b_1, \dots, b_{|a|-1})$ を返す。

• $b_i$ は相異なる
• $b_i \in [0, |a|)$
• $a_{b_0} \preceq a_{b_1} \preceq \cdots \preceq a_{b_{|a|-1}}$

ただし $\preceq$ は compare による順序とする。

See also

index_order_by_key.

Examples

use std::cmp::Ordering;

use nekolib::algo::index_order_by;

// See <https://ngtkana.hatenablog.com/entry/2021/11/13/202103>
let argcmp = |[x0, y0]: [i64; 2], [x1, y1]: [i64; 2]| {
    (([y0, x0] < [0; 2]).cmp(&([y1, x1] < [0; 2])))
        .then_with(|| (x1 * y0).cmp(&(x0 * y1)))
};

let a = [[1, 1], [1, -1], [-1, 0], [0, 1], [1, 0], [0, -1], [-1, 1], [-1, -1]];
let compare =
    |(_, &al): (usize, &[i64; 2]), (_, &ar): (usize, &[i64; 2])| argcmp(al, ar);

// [6] [3] [0]
// [2]  O  [4]
// [7] [5] [1]
assert_eq!(index_order_by(&a, compare), [4, 0, 3, 6, 2, 7, 5, 1]);