pub struct BitSet {
size: usize,
bits: Vec<u64>,
}Fields§
§size: usize§bits: Vec<u64>Implementations§
Source§impl BitSet
impl BitSet
Sourcepub fn new(size: usize) -> Self
pub fn new(size: usize) -> Self
Examples found in repository?
More examples
Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Examples found in repository?
crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 40)
38 pub fn contains(&mut self, sum: usize) -> bool {
39 self.rebuild();
40 if sum < self.dp.len() {
41 self.dp.get(sum)
42 } else {
43 false
44 }
45 }
46
47 fn rebuild(&mut self) {
48 if self.pending_weights.is_empty() {
49 return;
50 }
51 let mut heap = BinaryHeap::from(take(&mut self.pending_weights));
52 let (mut current_weight, mut count) = match heap.pop() {
53 Some(Reverse(w)) => (w, 1),
54 None => return,
55 };
56 while let Some(Reverse(weight)) = heap.pop() {
57 if weight == current_weight {
58 count += 1;
59 if count >= 3 {
60 if let Some(w) = current_weight.checked_mul(2) {
61 heap.push(Reverse(w));
62 }
63 count -= 2;
64 }
65 continue;
66 }
67 for _ in 0..count {
68 if self.size == !0 {
69 self.dp.resize(self.dp.len() + current_weight);
70 }
71 self.dp.shl_bitor_assign(current_weight);
72 }
73 (current_weight, count) = (weight, 1);
74 }
75 for _ in 0..count {
76 if self.size == !0 {
77 self.dp.resize(self.dp.len() + current_weight);
78 }
79 self.dp.shl_bitor_assign(current_weight);
80 }
81 }pub fn is_empty(&self) -> bool
pub fn ones(size: usize) -> Self
Sourcepub fn get(&self, i: usize) -> bool
pub fn get(&self, i: usize) -> bool
Examples found in repository?
More examples
crates/competitive/src/algorithm/automata_learning.rs (line 372)
355 pub fn construct_dfa(&mut self) -> DeterministicFiniteAutomaton {
356 let sigma = self.automaton.sigma();
357 let mut dfa = DeterministicFiniteAutomaton {
358 states: vec![],
359 initial_state: 0,
360 };
361 let mut i_prefix = 0;
362 while i_prefix < self.prefixes.len() {
363 let mut delta = vec![];
364 for x in 0..sigma {
365 let prefix: Vec<usize> =
366 self.prefixes[i_prefix].iter().cloned().chain([x]).collect();
367 let index = self.add_prefix(prefix);
368 delta.push(index);
369 }
370 dfa.states.push(DfaState {
371 delta,
372 accept: self.table[i_prefix].get(0),
373 });
374 i_prefix += 1;
375 }
376 dfa
377 }Sourcepub fn count_ones(&self) -> u64
pub fn count_ones(&self) -> u64
pub fn count_zeros(&self) -> u64
Sourcepub fn push(&mut self, b: bool)
pub fn push(&mut self, b: bool)
Examples found in repository?
crates/competitive/src/algorithm/automata_learning.rs (lines 344-347)
339 fn add_suffix(&mut self, suffix: Vec<usize>) {
340 if self.suffixes.contains(&suffix) {
341 return;
342 }
343 for (prefix, table) in self.prefixes.iter_mut().zip(&mut self.table) {
344 table.push(
345 self.automaton
346 .behavior(prefix.iter().cloned().chain(suffix.iter().cloned())),
347 );
348 }
349 self.suffixes.push(suffix);
350 self.row_map.clear();
351 for (i_prefix, row) in self.table.iter().enumerate() {
352 self.row_map.insert(row.clone(), i_prefix);
353 }
354 }Sourcepub fn resize(&mut self, new_size: usize)
pub fn resize(&mut self, new_size: usize)
Examples found in repository?
crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 69)
47 fn rebuild(&mut self) {
48 if self.pending_weights.is_empty() {
49 return;
50 }
51 let mut heap = BinaryHeap::from(take(&mut self.pending_weights));
52 let (mut current_weight, mut count) = match heap.pop() {
53 Some(Reverse(w)) => (w, 1),
54 None => return,
55 };
56 while let Some(Reverse(weight)) = heap.pop() {
57 if weight == current_weight {
58 count += 1;
59 if count >= 3 {
60 if let Some(w) = current_weight.checked_mul(2) {
61 heap.push(Reverse(w));
62 }
63 count -= 2;
64 }
65 continue;
66 }
67 for _ in 0..count {
68 if self.size == !0 {
69 self.dp.resize(self.dp.len() + current_weight);
70 }
71 self.dp.shl_bitor_assign(current_weight);
72 }
73 (current_weight, count) = (weight, 1);
74 }
75 for _ in 0..count {
76 if self.size == !0 {
77 self.dp.resize(self.dp.len() + current_weight);
78 }
79 self.dp.shl_bitor_assign(current_weight);
80 }
81 }Sourcefn trim(&mut self)
fn trim(&mut self)
Examples found in repository?
crates/competitive/src/data_structure/bitset.rs (line 36)
31 pub fn ones(size: usize) -> Self {
32 let mut self_ = Self {
33 size,
34 bits: vec![u64::MAX; size.div_ceil(64)],
35 };
36 self_.trim();
37 self_
38 }
39
40 pub fn get(&self, i: usize) -> bool {
41 self.bits[i >> 6] & (1 << (i & 63)) != 0
42 }
43
44 pub fn set(&mut self, i: usize, b: bool) {
45 if b {
46 self.bits[i >> 6] |= 1 << (i & 63);
47 } else {
48 self.bits[i >> 6] &= !(1 << (i & 63));
49 }
50 }
51
52 pub fn count_ones(&self) -> u64 {
53 self.bits.iter().map(|x| x.count_ones() as u64).sum()
54 }
55
56 pub fn count_zeros(&self) -> u64 {
57 self.size as u64 - self.count_ones()
58 }
59
60 pub fn push(&mut self, b: bool) {
61 let d = self.size & 63;
62 if d == 0 {
63 self.bits.push(b as u64);
64 } else {
65 *self.bits.last_mut().unwrap() |= (b as u64) << d;
66 }
67 self.size += 1;
68 }
69
70 pub fn resize(&mut self, new_size: usize) {
71 match self.size.cmp(&new_size) {
72 Ordering::Less => self.bits.resize(new_size.div_ceil(64), 0),
73 Ordering::Equal => {}
74 Ordering::Greater => self.bits.truncate(new_size.div_ceil(64)),
75 }
76 self.size = new_size;
77 self.trim();
78 }
79
80 fn trim(&mut self) {
81 if self.size & 63 != 0
82 && let Some(x) = self.bits.last_mut()
83 {
84 *x &= 0xffff_ffff_ffff_ffff >> (64 - (self.size & 63));
85 }
86 }
87
88 pub fn shl_bitor_assign(&mut self, rhs: usize) {
89 let n = self.bits.len();
90 let k = rhs >> 6;
91 let d = rhs & 63;
92 if k < n {
93 if d == 0 {
94 for i in (0..n - k).rev() {
95 self.bits[i + k] |= self.bits[i];
96 }
97 } else {
98 for i in (1..n - k).rev() {
99 self.bits[i + k] |= (self.bits[i] << d) | (self.bits[i - 1] >> (64 - d));
100 }
101 self.bits[k] |= self.bits[0] << d;
102 }
103 self.trim();
104 }
105 }
106
107 pub fn shr_bitor_assign(&mut self, rhs: usize) {
108 let n = self.bits.len();
109 let k = rhs >> 6;
110 let d = rhs & 63;
111 if k < n {
112 if d == 0 {
113 for i in k..n {
114 self.bits[i - k] |= self.bits[i];
115 }
116 } else {
117 for i in k..n - 1 {
118 self.bits[i - k] |= (self.bits[i] >> d) | (self.bits[i + 1] << (64 - d));
119 }
120 self.bits[n - k - 1] |= self.bits[n - 1] >> d;
121 }
122 }
123 }
124}
125
126impl Extend<bool> for BitSet {
127 fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
128 let d = self.size & 63;
129 let mut iter = iter.into_iter();
130 let Some(first) = iter.next() else {
131 return;
132 };
133 if d == 0 {
134 self.bits.push(0);
135 }
136 let mut e = self.bits.last_mut().unwrap();
137 *e |= (first as u64) << d;
138 self.size += 1;
139 for b in iter {
140 let d = self.size & 63;
141 if d == 0 {
142 self.bits.push(b as u64);
143 e = self.bits.last_mut().unwrap();
144 } else {
145 *e |= (b as u64) << d;
146 }
147 self.size += 1;
148 }
149 }
150}
151
152impl FromIterator<bool> for BitSet {
153 fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
154 let mut set = BitSet::new(0);
155 set.extend(iter);
156 set
157 }
158}
159
160impl ShlAssign<usize> for BitSet {
161 fn shl_assign(&mut self, rhs: usize) {
162 let n = self.bits.len();
163 let k = rhs >> 6;
164 let d = rhs & 63;
165 if k >= n {
166 for x in self.bits.iter_mut() {
167 *x = 0;
168 }
169 } else {
170 if d == 0 {
171 for i in (0..n - k).rev() {
172 self.bits[i + k] = self.bits[i];
173 }
174 } else {
175 for i in (1..n - k).rev() {
176 self.bits[i + k] = (self.bits[i] << d) | (self.bits[i - 1] >> (64 - d));
177 }
178 self.bits[k] = self.bits[0] << d;
179 }
180 for x in self.bits[..k].iter_mut() {
181 *x = 0;
182 }
183 self.trim();
184 }
185 }
186}
187
188impl Shl<usize> for BitSet {
189 type Output = Self;
190 fn shl(mut self, rhs: usize) -> Self::Output {
191 self <<= rhs;
192 self
193 }
194}
195
196impl ShrAssign<usize> for BitSet {
197 fn shr_assign(&mut self, rhs: usize) {
198 let n = self.bits.len();
199 let k = rhs >> 6;
200 let d = rhs & 63;
201 if k >= n {
202 for x in self.bits.iter_mut() {
203 *x = 0;
204 }
205 } else {
206 if d == 0 {
207 for i in k..n {
208 self.bits[i - k] = self.bits[i];
209 }
210 } else {
211 for i in k..n - 1 {
212 self.bits[i - k] = (self.bits[i] >> d) | (self.bits[i + 1] << (64 - d));
213 }
214 self.bits[n - k - 1] = self.bits[n - 1] >> d;
215 }
216 for x in self.bits[n - k..].iter_mut() {
217 *x = 0;
218 }
219 }
220 }
221}
222
223impl Shr<usize> for BitSet {
224 type Output = Self;
225 fn shr(mut self, rhs: usize) -> Self::Output {
226 self >>= rhs;
227 self
228 }
229}
230
231impl<'a> BitOrAssign<&'a BitSet> for BitSet {
232 fn bitor_assign(&mut self, rhs: &'a Self) {
233 for (l, r) in self.bits.iter_mut().zip(rhs.bits.iter()) {
234 *l |= *r;
235 }
236 self.trim();
237 }
238}
239
240impl<'a> BitOr<&'a BitSet> for BitSet {
241 type Output = Self;
242 fn bitor(mut self, rhs: &'a Self) -> Self::Output {
243 self |= rhs;
244 self
245 }
246}
247
248impl<'b> BitOr<&'b BitSet> for &BitSet {
249 type Output = BitSet;
250 fn bitor(self, rhs: &'b BitSet) -> Self::Output {
251 let mut res = self.clone();
252 res |= rhs;
253 res
254 }
255}
256
257impl<'a> BitAndAssign<&'a BitSet> for BitSet {
258 fn bitand_assign(&mut self, rhs: &'a Self) {
259 for (l, r) in self.bits.iter_mut().zip(rhs.bits.iter()) {
260 *l &= *r;
261 }
262 }
263}
264
265impl<'a> BitAnd<&'a BitSet> for BitSet {
266 type Output = Self;
267 fn bitand(mut self, rhs: &'a Self) -> Self::Output {
268 self &= rhs;
269 self
270 }
271}
272
273impl<'b> BitAnd<&'b BitSet> for &BitSet {
274 type Output = BitSet;
275 fn bitand(self, rhs: &'b BitSet) -> Self::Output {
276 let mut res = self.clone();
277 res &= rhs;
278 res
279 }
280}
281
282impl<'a> BitXorAssign<&'a BitSet> for BitSet {
283 fn bitxor_assign(&mut self, rhs: &'a Self) {
284 for (l, r) in self.bits.iter_mut().zip(rhs.bits.iter()) {
285 *l ^= *r;
286 }
287 self.trim();
288 }
289}
290
291impl<'a> BitXor<&'a BitSet> for BitSet {
292 type Output = Self;
293 fn bitxor(mut self, rhs: &'a Self) -> Self::Output {
294 self ^= rhs;
295 self
296 }
297}
298
299impl<'b> BitXor<&'b BitSet> for &BitSet {
300 type Output = BitSet;
301 fn bitxor(self, rhs: &'b BitSet) -> Self::Output {
302 let mut res = self.clone();
303 res ^= rhs;
304 res
305 }
306}
307
308impl Not for BitSet {
309 type Output = Self;
310 fn not(mut self) -> Self::Output {
311 for x in self.bits.iter_mut() {
312 *x = !*x;
313 }
314 self.trim();
315 self
316 }Sourcepub fn shl_bitor_assign(&mut self, rhs: usize)
pub fn shl_bitor_assign(&mut self, rhs: usize)
Examples found in repository?
crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 71)
47 fn rebuild(&mut self) {
48 if self.pending_weights.is_empty() {
49 return;
50 }
51 let mut heap = BinaryHeap::from(take(&mut self.pending_weights));
52 let (mut current_weight, mut count) = match heap.pop() {
53 Some(Reverse(w)) => (w, 1),
54 None => return,
55 };
56 while let Some(Reverse(weight)) = heap.pop() {
57 if weight == current_weight {
58 count += 1;
59 if count >= 3 {
60 if let Some(w) = current_weight.checked_mul(2) {
61 heap.push(Reverse(w));
62 }
63 count -= 2;
64 }
65 continue;
66 }
67 for _ in 0..count {
68 if self.size == !0 {
69 self.dp.resize(self.dp.len() + current_weight);
70 }
71 self.dp.shl_bitor_assign(current_weight);
72 }
73 (current_weight, count) = (weight, 1);
74 }
75 for _ in 0..count {
76 if self.size == !0 {
77 self.dp.resize(self.dp.len() + current_weight);
78 }
79 self.dp.shl_bitor_assign(current_weight);
80 }
81 }pub fn shr_bitor_assign(&mut self, rhs: usize)
Trait Implementations§
Source§impl<'a> BitAndAssign<&'a BitSet> for BitSet
impl<'a> BitAndAssign<&'a BitSet> for BitSet
Source§fn bitand_assign(&mut self, rhs: &'a Self)
fn bitand_assign(&mut self, rhs: &'a Self)
Performs the
&= operation. Read moreSource§impl<'a> BitOrAssign<&'a BitSet> for BitSet
impl<'a> BitOrAssign<&'a BitSet> for BitSet
Source§fn bitor_assign(&mut self, rhs: &'a Self)
fn bitor_assign(&mut self, rhs: &'a Self)
Performs the
|= operation. Read moreSource§impl<'a> BitXorAssign<&'a BitSet> for BitSet
impl<'a> BitXorAssign<&'a BitSet> for BitSet
Source§fn bitxor_assign(&mut self, rhs: &'a Self)
fn bitxor_assign(&mut self, rhs: &'a Self)
Performs the
^= operation. Read moreSource§impl Extend<bool> for BitSet
impl Extend<bool> for BitSet
Source§fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T)
fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T)
Extends a collection with the contents of an iterator. Read more
Source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
🔬This is a nightly-only experimental API. (
extend_one)Extends a collection with exactly one element.
Source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
🔬This is a nightly-only experimental API. (
extend_one)Reserves capacity in a collection for the given number of additional elements. Read more
Source§impl FromIterator<bool> for BitSet
impl FromIterator<bool> for BitSet
Source§impl Ord for BitSet
impl Ord for BitSet
Source§impl PartialOrd for BitSet
impl PartialOrd for BitSet
Source§impl ShlAssign<usize> for BitSet
impl ShlAssign<usize> for BitSet
Source§fn shl_assign(&mut self, rhs: usize)
fn shl_assign(&mut self, rhs: usize)
Performs the
<<= operation. Read moreSource§impl ShrAssign<usize> for BitSet
impl ShrAssign<usize> for BitSet
Source§fn shr_assign(&mut self, rhs: usize)
fn shr_assign(&mut self, rhs: usize)
Performs the
>>= operation. Read moreimpl Eq for BitSet
impl StructuralPartialEq for BitSet
Auto Trait Implementations§
impl Freeze for BitSet
impl RefUnwindSafe for BitSet
impl Send for BitSet
impl Sync for BitSet
impl Unpin for BitSet
impl UnwindSafe for BitSet
Blanket Implementations§
Source§impl<T> AsTotalOrd for Twhere
T: PartialOrd,
impl<T> AsTotalOrd for Twhere
T: PartialOrd,
fn as_total_ord(&self) -> TotalOrd<&T>
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more