competitive/data_structure/
compress.rs

1use super::SliceBisectExt;
2use std::{
3    collections::HashMap,
4    fmt::{self, Debug},
5    hash::Hash,
6    iter::FromIterator,
7};
8
9pub trait Compressor<T>
10where
11    Self: FromIterator<T>,
12    T: Ord,
13{
14    fn index_exact(&self, index: &T) -> Option<usize>;
15    fn index_lower_bound(&self, index: &T) -> usize;
16    fn size(&self) -> usize;
17}
18
19#[derive(Debug, Clone)]
20pub struct VecCompress<T> {
21    data: Vec<T>,
22}
23
24impl<T> FromIterator<T> for VecCompress<T>
25where
26    T: Ord,
27{
28    fn from_iter<I>(iter: I) -> Self
29    where
30        I: IntoIterator<Item = T>,
31    {
32        let mut data: Vec<_> = iter.into_iter().collect();
33        data.sort_unstable();
34        data.dedup();
35        Self { data }
36    }
37}
38
39impl<T> Compressor<T> for VecCompress<T>
40where
41    T: Ord,
42{
43    fn index_exact(&self, index: &T) -> Option<usize> {
44        self.data.binary_search(index).ok()
45    }
46
47    fn index_lower_bound(&self, index: &T) -> usize {
48        self.data.position_bisect(|x| x >= index)
49    }
50
51    fn size(&self) -> usize {
52        self.data.len()
53    }
54}
55
56#[derive(Clone)]
57pub struct HashCompress<T> {
58    data: HashMap<T, usize>,
59}
60
61impl<T> Debug for HashCompress<T>
62where
63    T: Debug + Eq + Hash,
64{
65    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
66        f.debug_struct("HashCompress")
67            .field("data", &self.data)
68            .finish()
69    }
70}
71
72impl<T> FromIterator<T> for HashCompress<T>
73where
74    T: Ord + Hash,
75{
76    fn from_iter<I>(iter: I) -> Self
77    where
78        I: IntoIterator<Item = T>,
79    {
80        let mut data: Vec<_> = iter.into_iter().collect();
81        data.sort_unstable();
82        data.dedup();
83        let data = data.into_iter().enumerate().map(|(i, t)| (t, i)).collect();
84        Self { data }
85    }
86}
87
88impl<T> Compressor<T> for HashCompress<T>
89where
90    T: Ord + Hash,
91{
92    fn index_exact(&self, index: &T) -> Option<usize> {
93        self.data.get(index).copied()
94    }
95
96    fn index_lower_bound(&self, _index: &T) -> usize {
97        panic!("HashCompress does not implement index_lower_bound")
98    }
99
100    fn size(&self) -> usize {
101        self.data.len()
102    }
103}
competitive/data_structure/compress.rs

competitive/data_structure/
compress.rs
