atcoder/lib/algorithm/
compress.rs

1//! 座標圧縮です。
2
3/// スライスを大小関係を保った連番へ変換する拡張トレイトです。
4///
5/// `Ord` を実装する型に利用できます。`[T]` に実装されているため、ベクタや配列からも
6/// スライスとして呼び出せます。
7pub trait Compress<T> {
8    /// 元の値を、重複を除いた昇順列内の順位へ置き換えます。
9    ///
10    /// # Returns
11    ///
12    /// `compressed[i]` は元の `self[i]` に対応する 0-indexed の順位です。`values[j]` は順位
13    /// `j` の元の値で、昇順かつ重複なしです。要素数を `N` とすると `O(N log N)` です。
14    /// 空スライスの場合は、どちらも空のベクタを返します。
15    ///
16    /// # Examples
17    ///
18    /// ```
19    /// use atcoder::algorithm::compress::Compress;
20    ///
21    /// let (compressed, values) = [40, 10, 40, 20].compressed();
22    /// assert_eq!(compressed, [2, 0, 2, 1]);
23    /// assert_eq!(values, [10, 20, 40]);
24    /// ```
25    fn compressed(&self) -> (Vec<usize>, Vec<T>);
26}
27
28impl<T: Ord + Clone> Compress<T> for [T] {
29    fn compressed(&self) -> (Vec<usize>, Vec<T>) {
30        let mut values = self.to_vec();
31        values.sort_unstable();
32        values.dedup();
33        let compressed = self
34            .iter()
35            .map(|value| values.binary_search(value).unwrap())
36            .collect();
37        (compressed, values)
38    }
39}
40
41#[cfg(test)]
42mod tests {
43    use super::Compress;
44
45    #[test]
46    fn compresses_duplicates() {
47        assert_eq!([3, 1, 3].compressed(), (vec![1, 0, 1], vec![1, 3]));
48    }
49}
atcoder/lib/algorithm/compress.rs

atcoder/lib/algorithm/
compress.rs
