nekolib/algo/
index_order.rs

1//! 添字の順序。
2
3use std::cmp::Ordering;
4
5/// 添字の順序。
6///
7/// See [`index_order_by`].
8///
9/// [`index_order_by`]: fn.index_order_by.html
10///
11/// # Examples
12/// ```
13/// use std::cmp::Reverse;
14///
15/// use nekolib::algo::index_order_by_key;
16///
17/// let a = [0, 2, 1, 4, 5, 1, 3];
18/// let key = |(i, &ai): (usize, &i32)| (ai, Reverse(i));
19/// assert_eq!(index_order_by_key(&a, key), [0, 5, 2, 1, 6, 3, 4]);
20/// ```
21pub fn index_order_by_key<T, K: Ord>(
22    buf: &[T],
23    mut key: impl FnMut((usize, &T)) -> K,
24) -> Vec<usize> {
25    index_order_by(buf, |l, r| key(l).cmp(&key(r)))
26}
27
28/// 添字の順序。
29///
30/// 次で定義される $b = (b\_0, b\_1, \\dots, b\_{|a|-1})$ を返す。
31/// - $b\_i$ は相異なる
32/// - $b\_i \\in [0, |a|)$
33/// - $a\_{b\_0} \\preceq a\_{b\_1} \\preceq \\cdots \\preceq a\_{b\_{|a|-1}}$
34///
35/// ただし $\\preceq$ は `compare` による順序とする。
36///
37/// # See also
38///
39/// [`index_order_by_key`].
40///
41/// [`index_order_by_key`]: fn.index_order_by_key.html
42///
43/// # Examples
44/// ```
45/// use std::cmp::Ordering;
46///
47/// use nekolib::algo::index_order_by;
48///
49/// // See <https://ngtkana.hatenablog.com/entry/2021/11/13/202103>
50/// let argcmp = |[x0, y0]: [i64; 2], [x1, y1]: [i64; 2]| {
51///     (([y0, x0] < [0; 2]).cmp(&([y1, x1] < [0; 2])))
52///         .then_with(|| (x1 * y0).cmp(&(x0 * y1)))
53/// };
54///
55/// let a = [[1, 1], [1, -1], [-1, 0], [0, 1], [1, 0], [0, -1], [-1, 1], [-1, -1]];
56/// let compare =
57///     |(_, &al): (usize, &[i64; 2]), (_, &ar): (usize, &[i64; 2])| argcmp(al, ar);
58///
59/// // [6] [3] [0]
60/// // [2]  O  [4]
61/// // [7] [5] [1]
62/// assert_eq!(index_order_by(&a, compare), [4, 0, 3, 6, 2, 7, 5, 1]);
63/// ```
64pub fn index_order_by<T>(
65    buf: &[T],
66    mut compare: impl FnMut((usize, &T), (usize, &T)) -> Ordering,
67) -> Vec<usize> {
68    let n = buf.len();
69    let mut res: Vec<_> = (0..n).collect();
70    res.sort_unstable_by(|&l, &r| compare((l, &buf[l]), (r, &buf[r])));
71    res
72}
nekolib/algo/index_order.rs

nekolib/algo/
index_order.rs
