haar_lib/algo/
compressor.rs

1//! 座標圧縮
2use crate::algo::bsearch_slice::BinarySearch;
3
4/// 座標圧縮のための構造体
5#[derive(Clone)]
6pub struct Compressor<T> {
7    data: Vec<T>,
8}
9
10/// [`Compressor<T>`]を生成する
11#[derive(Clone, Default)]
12pub struct CompressorBuilder<T> {
13    data: Vec<T>,
14}
15
16impl<T: Ord + Eq> Compressor<T> {
17    /// `value`が何番目の値(0-index)かを返す。
18    ///
19    /// **Time complexity** $O(\log n)$
20    pub fn index(&self, value: &T) -> usize {
21        self.data.lower_bound(value)
22    }
23
24    /// `i`番目の値を返す。
25    ///
26    /// **Time complexity** $O(1)$
27    pub fn get(&self, i: usize) -> &T {
28        &self.data[i]
29    }
30
31    /// 最小値を返す。
32    pub fn min(&self) -> Option<&T> {
33        self.data.first()
34    }
35
36    /// 最大値を返す。
37    pub fn max(&self) -> Option<&T> {
38        self.data.last()
39    }
40
41    /// `values`の要素をすべて座標圧縮する。
42    pub fn compress<'a>(
43        &'a self,
44        values: impl IntoIterator<Item = T> + 'a,
45    ) -> impl Iterator<Item = usize> + 'a {
46        values.into_iter().map(move |x| self.index(&x))
47    }
48
49    /// `values`の要素をすべて復元する。
50    pub fn decompress<'a>(
51        &'a self,
52        indices: impl IntoIterator<Item = usize> + 'a,
53    ) -> impl Iterator<Item = &'a T> + 'a {
54        indices.into_iter().map(move |i| self.get(i))
55    }
56
57    /// 座標圧縮後の要素の種類数
58    pub fn size(&self) -> usize {
59        self.data.len()
60    }
61}
62
63impl<T: Ord + Eq> CompressorBuilder<T> {
64    /// `CompressorBuilder<T>`を生成する。
65    pub fn new() -> Self {
66        CompressorBuilder { data: vec![] }
67    }
68
69    /// 座標圧縮対象に`value`を追加する。
70    pub fn add(&mut self, value: T) {
71        self.data.push(value);
72    }
73
74    /// **Time complexity** $O(n \log n)$
75    pub fn build(mut self) -> Compressor<T> {
76        self.data.sort();
77        self.data.dedup();
78        Compressor { data: self.data }
79    }
80}
81
82impl<U> Extend<U> for CompressorBuilder<U> {
83    fn extend<T: IntoIterator<Item = U>>(&mut self, iter: T) {
84        self.data.extend(iter);
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91    use crate::hashset;
92    use std::collections::HashSet;
93
94    #[test]
95    fn test() {
96        let data = vec![1, 3, 2, 4, 5, 9, 0, -1, 3];
97        let mut builder = CompressorBuilder::<_>::new();
98        builder.extend(data.clone());
99        let compressor = builder.build();
100
101        assert_eq!(
102            compressor.compress(data.clone()).collect::<Vec<_>>(),
103            vec![2, 4, 3, 5, 6, 7, 1, 0, 4]
104        );
105        assert_eq!(
106            compressor
107                .decompress(vec![2, 4, 3, 5, 6, 7, 1, 0, 4])
108                .copied()
109                .collect::<Vec<_>>(),
110            data
111        );
112
113        let data = hashset![1, 3, 2, 4, 5, 9, 0, -1, 3];
114        let mut builder = CompressorBuilder::<_>::new();
115        builder.extend(data.clone());
116        let compressor = builder.build();
117
118        assert_eq!(
119            compressor.compress(data.clone()).collect::<HashSet<_>>(),
120            hashset![2, 4, 3, 5, 6, 7, 1, 0, 4]
121        );
122        assert_eq!(
123            compressor
124                .decompress(vec![2, 4, 3, 5, 6, 7, 1, 0, 4])
125                .copied()
126                .collect::<HashSet<_>>(),
127            data
128        );
129    }
130}
haar_lib/algo/compressor.rs

haar_lib/algo/
compressor.rs
