Struct VecCompress

Source

pub struct VecCompress<T> {
    data: Vec<T>,
}

Fields§

§data: Vec<T>

Implementations§

Source §

impl<T> VecCompress<T>

Source

pub fn values(&self) -> &[T]

Examples found in repository ?

crates/competitive/src/data_structure/wavelet_matrix.rs (line 135)

124    pub fn access(&self, mut k: usize) -> T {
125        let mut idx = 0;
126        for d in (0..self.bit_length).rev() {
127            let level = self.level(d);
128            if self.bit_vector.access(level * self.len + k) {
129                idx |= 1 << d;
130                k = self.zeros[level] + self.rank1(level, k);
131            } else {
132                k = self.rank0(level, k);
133            }
134        }
135        self.compress.values()[idx].clone()
136    }
137
138    /// the number of val in range
139    pub fn rank(&self, val: T, range: Range<usize>) -> usize {
140        match self.compress.index_exact(&val) {
141            Some(idx) => self.rank_by_index(idx, range),
142            None => 0,
143        }
144    }
145
146    /// index of k-th val
147    pub fn select(&self, val: T, k: usize) -> Option<usize> {
148        let idx = self.compress.index_exact(&val)?;
149        if self.rank_by_index(idx, 0..self.len) <= k {
150            return None;
151        }
152        let mut i = 0;
153        for d in (0..self.bit_length).rev() {
154            let level = self.level(d);
155            if ((idx >> d) & 1) != 0 {
156                i = self.zeros[level] + self.rank1(level, i);
157            } else {
158                i = self.rank0(level, i);
159            }
160        }
161        i += k;
162        for level in (0..self.bit_length).rev() {
163            let offset = level * self.len;
164            if i >= self.zeros[level] {
165                let global_k = self.ones_prefix[level] + (i - self.zeros[level]);
166                let pos = self.bit_vector.select1(global_k).unwrap();
167                i = pos - offset;
168            } else {
169                let zeros_before = offset - self.ones_prefix[level];
170                let global_k = zeros_before + i;
171                let pos = self.bit_vector.select0(global_k).unwrap();
172                i = pos - offset;
173            }
174        }
175        Some(i)
176    }
177
178    /// get k-th smallest value in range
179    pub fn quantile(&self, mut range: Range<usize>, mut k: usize) -> T {
180        let mut idx = 0;
181        for d in (0..self.bit_length).rev() {
182            let level = self.level(d);
183            let z = self.rank0(level, range.end) - self.rank0(level, range.start);
184            if z <= k {
185                k -= z;
186                idx |= 1 << d;
187                range.start = self.zeros[level] + self.rank1(level, range.start);
188                range.end = self.zeros[level] + self.rank1(level, range.end);
189            } else {
190                range.start = self.rank0(level, range.start);
191                range.end = self.rank0(level, range.end);
192            }
193        }
194        self.compress.values()[idx].clone()
195    }
196
197    /// get k-th smallest value out of range
198    pub fn quantile_outer(&self, mut range: Range<usize>, mut k: usize) -> T {
199        let mut idx = 0;
200        let mut orange = 0..self.len;
201        for d in (0..self.bit_length).rev() {
202            let level = self.level(d);
203            let z = self.rank0(level, orange.end) - self.rank0(level, orange.start)
204                + self.rank0(level, range.start)
205                - self.rank0(level, range.end);
206            if z <= k {
207                k -= z;
208                idx |= 1 << d;
209                range.start = self.zeros[level] + self.rank1(level, range.start);
210                range.end = self.zeros[level] + self.rank1(level, range.end);
211                orange.start = self.zeros[level] + self.rank1(level, orange.start);
212                orange.end = self.zeros[level] + self.rank1(level, orange.end);
213            } else {
214                range.start = self.rank0(level, range.start);
215                range.end = self.rank0(level, range.end);
216                orange.start = self.rank0(level, orange.start);
217                orange.end = self.rank0(level, orange.end);
218            }
219        }
220        self.compress.values()[idx].clone()
221    }