pub trait RankSelectDictionaries {
// Required methods
fn bit_length(&self) -> usize;
fn access(&self, k: usize) -> bool;
// Provided methods
fn rank1(&self, k: usize) -> usize { ... }
fn rank0(&self, k: usize) -> usize { ... }
fn select1(&self, k: usize) -> Option<usize> { ... }
fn select0(&self, k: usize) -> Option<usize> { ... }
}Expand description
rank_i(select_i(k)) = k rank_i(select_i(k) + 1) = k + 1
Required Methods§
Provided Methods§
Sourcefn rank1(&self, k: usize) -> usize
fn rank1(&self, k: usize) -> usize
the number of 1 in [0, k)
Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 15)
14 fn rank0(&self, k: usize) -> usize {
15 k - self.rank1(k)
16 }
17 /// index of k-th 1
18 fn select1(&self, k: usize) -> Option<usize> {
19 let n = self.bit_length();
20 if self.rank1(n) <= k {
21 return None;
22 }
23 let (mut l, mut r) = (0, n);
24 while r - l > 1 {
25 let m = l.midpoint(r);
26 if self.rank1(m) <= k {
27 l = m;
28 } else {
29 r = m;
30 }
31 }
32 Some(l)
33 }More examples
Sourcefn rank0(&self, k: usize) -> usize
fn rank0(&self, k: usize) -> usize
the number of 0 in [0, k)
Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 37)
35 fn select0(&self, k: usize) -> Option<usize> {
36 let n = self.bit_length();
37 if self.rank0(n) <= k {
38 return None;
39 }
40 let (mut l, mut r) = (0, n);
41 while r - l > 1 {
42 let m = l.midpoint(r);
43 if self.rank0(m) <= k {
44 l = m;
45 } else {
46 r = m;
47 }
48 }
49 Some(l)
50 }Sourcefn select1(&self, k: usize) -> Option<usize>
fn select1(&self, k: usize) -> Option<usize>
index of k-th 1
Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 143)
128 fn select1(&self, mut k: usize) -> Option<usize> {
129 let (mut l, mut r) = (0, self.data.len());
130 if self.sum <= k {
131 return None;
132 }
133 while r - l > 1 {
134 let m = l.midpoint(r);
135 if self.data[m].1 <= k {
136 l = m;
137 } else {
138 r = m;
139 }
140 }
141 let (bit, sum) = self.data[l];
142 k -= sum;
143 Some(l * Self::WORD_SIZE + bit.select1(k).unwrap())
144 }More examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 166)
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 }Sourcefn select0(&self, k: usize) -> Option<usize>
fn select0(&self, k: usize) -> Option<usize>
index of k-th 0
Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 160)
145 fn select0(&self, mut k: usize) -> Option<usize> {
146 let (mut l, mut r) = (0, self.data.len());
147 if self.len - self.sum <= k {
148 return None;
149 }
150 while r - l > 1 {
151 let m = l.midpoint(r);
152 if m * Self::WORD_SIZE - self.data[m].1 <= k {
153 l = m;
154 } else {
155 r = m;
156 }
157 }
158 let (bit, sum) = self.data[l];
159 k -= l * Self::WORD_SIZE - sum;
160 Some(l * Self::WORD_SIZE + bit.select0(k).unwrap())
161 }More examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 171)
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 }