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

competitive/data_structure/
compress.rs
