competitive/data_structure/
compress.rs

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

competitive/data_structure/
compress.rs
