cp_library_rs/utils/
coordinate_compression.rs

1//! 座標圧縮
2
3/// # 座標圧縮
4#[derive(Debug)]
5pub struct Compression<'a, T> {
6    pub size: usize,
7    pub sorted_array: Vec<&'a T>,
8}
9
10impl<'a, T: Ord> Compression<'a, T> {
11    /// スライス`array`で配列を初期化する
12    pub fn new(array: &'a [T]) -> Self {
13        array.iter().collect()
14    }
15
16    /// 圧縮後の`val`の番号を返す
17    pub fn idx(&self, val: &T) -> Option<usize> {
18        let idx = self.sorted_array.binary_search(&val);
19        idx.ok()
20    }
21
22    /// 圧縮前の要素`idx`を返す
23    pub fn val(&self, idx: usize) -> Option<&T> {
24        if let Some(&val) = self.sorted_array.get(idx) {
25            Some(val)
26        } else {
27            None
28        }
29    }
30}
31
32impl<'a, T: Ord> FromIterator<&'a T> for Compression<'a, T> {
33    fn from_iter<I: IntoIterator<Item = &'a T>>(iter: I) -> Self {
34        let mut comp: Vec<&'a T> = iter.into_iter().collect();
35        comp.sort();
36        comp.dedup();
37        Self {
38            size: comp.len(),
39            sorted_array: comp,
40        }
41    }
42}

cp_library_rs/utils/coordinate_compression.rs

cp_library_rs/utils/
coordinate_compression.rs