]>
Commit | Line | Data |
---|---|---|
e74abb32 | 1 | use crate::vec::{Idx, IndexVec}; |
3dfed10e | 2 | use arrayvec::ArrayVec; |
0bf4aa26 XL |
3 | use std::fmt; |
4 | use std::iter; | |
5 | use std::marker::PhantomData; | |
6 | use std::mem; | |
3dfed10e | 7 | use std::ops::{BitAnd, BitAndAssign, BitOrAssign, Not, Range, Shl}; |
0bf4aa26 | 8 | use std::slice; |
416331ca | 9 | |
3dfed10e XL |
10 | use rustc_macros::{Decodable, Encodable}; |
11 | ||
dc9dc135 | 12 | #[cfg(test)] |
416331ca | 13 | mod tests; |
0bf4aa26 XL |
14 | |
15 | pub type Word = u64; | |
16 | pub const WORD_BYTES: usize = mem::size_of::<Word>(); | |
17 | pub const WORD_BITS: usize = WORD_BYTES * 8; | |
18 | ||
e74abb32 XL |
19 | /// A fixed-size bitset type with a dense representation. |
20 | /// | |
21 | /// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation. | |
0bf4aa26 XL |
22 | /// |
23 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
24 | /// just be `usize`. | |
25 | /// | |
26 | /// All operations that involve an element will panic if the element is equal | |
27 | /// to or greater than the domain size. All operations that involve two bitsets | |
28 | /// will panic if the bitsets have differing domain sizes. | |
e74abb32 | 29 | /// |
1b1a35ee XL |
30 | #[derive(Eq, PartialEq, Decodable, Encodable)] |
31 | pub struct BitSet<T> { | |
0bf4aa26 XL |
32 | domain_size: usize, |
33 | words: Vec<Word>, | |
34 | marker: PhantomData<T>, | |
35 | } | |
36 | ||
1b1a35ee XL |
37 | impl<T> BitSet<T> { |
38 | /// Gets the domain size. | |
39 | pub fn domain_size(&self) -> usize { | |
40 | self.domain_size | |
41 | } | |
42 | } | |
43 | ||
0bf4aa26 | 44 | impl<T: Idx> BitSet<T> { |
9fa01778 | 45 | /// Creates a new, empty bitset with a given `domain_size`. |
0bf4aa26 XL |
46 | #[inline] |
47 | pub fn new_empty(domain_size: usize) -> BitSet<T> { | |
48 | let num_words = num_words(domain_size); | |
dfeec247 | 49 | BitSet { domain_size, words: vec![0; num_words], marker: PhantomData } |
0bf4aa26 XL |
50 | } |
51 | ||
9fa01778 | 52 | /// Creates a new, filled bitset with a given `domain_size`. |
0bf4aa26 XL |
53 | #[inline] |
54 | pub fn new_filled(domain_size: usize) -> BitSet<T> { | |
55 | let num_words = num_words(domain_size); | |
dfeec247 | 56 | let mut result = BitSet { domain_size, words: vec![!0; num_words], marker: PhantomData }; |
0bf4aa26 XL |
57 | result.clear_excess_bits(); |
58 | result | |
59 | } | |
60 | ||
0bf4aa26 XL |
61 | /// Clear all elements. |
62 | #[inline] | |
63 | pub fn clear(&mut self) { | |
64 | for word in &mut self.words { | |
65 | *word = 0; | |
66 | } | |
67 | } | |
68 | ||
69 | /// Clear excess bits in the final word. | |
70 | fn clear_excess_bits(&mut self) { | |
71 | let num_bits_in_final_word = self.domain_size % WORD_BITS; | |
72 | if num_bits_in_final_word > 0 { | |
73 | let mask = (1 << num_bits_in_final_word) - 1; | |
74 | let final_word_idx = self.words.len() - 1; | |
75 | self.words[final_word_idx] &= mask; | |
76 | } | |
77 | } | |
78 | ||
0bf4aa26 XL |
79 | /// Count the number of set bits in the set. |
80 | pub fn count(&self) -> usize { | |
81 | self.words.iter().map(|e| e.count_ones() as usize).sum() | |
82 | } | |
83 | ||
9fa01778 | 84 | /// Returns `true` if `self` contains `elem`. |
0bf4aa26 XL |
85 | #[inline] |
86 | pub fn contains(&self, elem: T) -> bool { | |
87 | assert!(elem.index() < self.domain_size); | |
88 | let (word_index, mask) = word_index_and_mask(elem); | |
89 | (self.words[word_index] & mask) != 0 | |
90 | } | |
91 | ||
92 | /// Is `self` is a (non-strict) superset of `other`? | |
93 | #[inline] | |
94 | pub fn superset(&self, other: &BitSet<T>) -> bool { | |
95 | assert_eq!(self.domain_size, other.domain_size); | |
96 | self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b) | |
97 | } | |
98 | ||
99 | /// Is the set empty? | |
100 | #[inline] | |
101 | pub fn is_empty(&self) -> bool { | |
102 | self.words.iter().all(|a| *a == 0) | |
103 | } | |
104 | ||
9fa01778 | 105 | /// Insert `elem`. Returns whether the set has changed. |
0bf4aa26 XL |
106 | #[inline] |
107 | pub fn insert(&mut self, elem: T) -> bool { | |
108 | assert!(elem.index() < self.domain_size); | |
109 | let (word_index, mask) = word_index_and_mask(elem); | |
110 | let word_ref = &mut self.words[word_index]; | |
111 | let word = *word_ref; | |
112 | let new_word = word | mask; | |
113 | *word_ref = new_word; | |
114 | new_word != word | |
115 | } | |
116 | ||
117 | /// Sets all bits to true. | |
118 | pub fn insert_all(&mut self) { | |
119 | for word in &mut self.words { | |
120 | *word = !0; | |
121 | } | |
122 | self.clear_excess_bits(); | |
123 | } | |
124 | ||
9fa01778 | 125 | /// Returns `true` if the set has changed. |
0bf4aa26 XL |
126 | #[inline] |
127 | pub fn remove(&mut self, elem: T) -> bool { | |
128 | assert!(elem.index() < self.domain_size); | |
129 | let (word_index, mask) = word_index_and_mask(elem); | |
130 | let word_ref = &mut self.words[word_index]; | |
131 | let word = *word_ref; | |
132 | let new_word = word & !mask; | |
133 | *word_ref = new_word; | |
134 | new_word != word | |
135 | } | |
136 | ||
9fa01778 | 137 | /// Sets `self = self | other` and returns `true` if `self` changed |
0bf4aa26 XL |
138 | /// (i.e., if new bits were added). |
139 | pub fn union(&mut self, other: &impl UnionIntoBitSet<T>) -> bool { | |
140 | other.union_into(self) | |
141 | } | |
142 | ||
9fa01778 | 143 | /// Sets `self = self - other` and returns `true` if `self` changed. |
0bf4aa26 XL |
144 | /// (i.e., if any bits were removed). |
145 | pub fn subtract(&mut self, other: &impl SubtractFromBitSet<T>) -> bool { | |
146 | other.subtract_from(self) | |
147 | } | |
148 | ||
9fa01778 | 149 | /// Sets `self = self & other` and return `true` if `self` changed. |
0bf4aa26 XL |
150 | /// (i.e., if any bits were removed). |
151 | pub fn intersect(&mut self, other: &BitSet<T>) -> bool { | |
152 | assert_eq!(self.domain_size, other.domain_size); | |
dfeec247 | 153 | bitwise(&mut self.words, &other.words, |a, b| a & b) |
0bf4aa26 XL |
154 | } |
155 | ||
9fa01778 | 156 | /// Gets a slice of the underlying words. |
0bf4aa26 XL |
157 | pub fn words(&self) -> &[Word] { |
158 | &self.words | |
159 | } | |
160 | ||
161 | /// Iterates over the indices of set bits in a sorted order. | |
162 | #[inline] | |
416331ca | 163 | pub fn iter(&self) -> BitIter<'_, T> { |
e74abb32 | 164 | BitIter::new(&self.words) |
0bf4aa26 XL |
165 | } |
166 | ||
167 | /// Duplicates the set as a hybrid set. | |
168 | pub fn to_hybrid(&self) -> HybridBitSet<T> { | |
169 | // Note: we currently don't bother trying to make a Sparse set. | |
170 | HybridBitSet::Dense(self.to_owned()) | |
171 | } | |
dc9dc135 XL |
172 | |
173 | /// Set `self = self | other`. In contrast to `union` returns `true` if the set contains at | |
174 | /// least one bit that is not in `other` (i.e. `other` is not a superset of `self`). | |
175 | /// | |
176 | /// This is an optimization for union of a hybrid bitset. | |
177 | fn reverse_union_sparse(&mut self, sparse: &SparseBitSet<T>) -> bool { | |
178 | assert!(sparse.domain_size == self.domain_size); | |
179 | self.clear_excess_bits(); | |
180 | ||
181 | let mut not_already = false; | |
182 | // Index of the current word not yet merged. | |
183 | let mut current_index = 0; | |
184 | // Mask of bits that came from the sparse set in the current word. | |
185 | let mut new_bit_mask = 0; | |
186 | for (word_index, mask) in sparse.iter().map(|x| word_index_and_mask(*x)) { | |
187 | // Next bit is in a word not inspected yet. | |
188 | if word_index > current_index { | |
189 | self.words[current_index] |= new_bit_mask; | |
190 | // Were there any bits in the old word that did not occur in the sparse set? | |
191 | not_already |= (self.words[current_index] ^ new_bit_mask) != 0; | |
192 | // Check all words we skipped for any set bit. | |
dfeec247 | 193 | not_already |= self.words[current_index + 1..word_index].iter().any(|&x| x != 0); |
dc9dc135 XL |
194 | // Update next word. |
195 | current_index = word_index; | |
196 | // Reset bit mask, no bits have been merged yet. | |
197 | new_bit_mask = 0; | |
198 | } | |
199 | // Add bit and mark it as coming from the sparse set. | |
200 | // self.words[word_index] |= mask; | |
201 | new_bit_mask |= mask; | |
202 | } | |
203 | self.words[current_index] |= new_bit_mask; | |
204 | // Any bits in the last inspected word that were not in the sparse set? | |
205 | not_already |= (self.words[current_index] ^ new_bit_mask) != 0; | |
206 | // Any bits in the tail? Note `clear_excess_bits` before. | |
dfeec247 | 207 | not_already |= self.words[current_index + 1..].iter().any(|&x| x != 0); |
dc9dc135 XL |
208 | |
209 | not_already | |
210 | } | |
0bf4aa26 XL |
211 | } |
212 | ||
213 | /// This is implemented by all the bitsets so that BitSet::union() can be | |
214 | /// passed any type of bitset. | |
215 | pub trait UnionIntoBitSet<T: Idx> { | |
216 | // Performs `other = other | self`. | |
217 | fn union_into(&self, other: &mut BitSet<T>) -> bool; | |
218 | } | |
219 | ||
220 | /// This is implemented by all the bitsets so that BitSet::subtract() can be | |
221 | /// passed any type of bitset. | |
222 | pub trait SubtractFromBitSet<T: Idx> { | |
223 | // Performs `other = other - self`. | |
224 | fn subtract_from(&self, other: &mut BitSet<T>) -> bool; | |
225 | } | |
226 | ||
227 | impl<T: Idx> UnionIntoBitSet<T> for BitSet<T> { | |
228 | fn union_into(&self, other: &mut BitSet<T>) -> bool { | |
229 | assert_eq!(self.domain_size, other.domain_size); | |
dfeec247 | 230 | bitwise(&mut other.words, &self.words, |a, b| a | b) |
0bf4aa26 XL |
231 | } |
232 | } | |
233 | ||
234 | impl<T: Idx> SubtractFromBitSet<T> for BitSet<T> { | |
235 | fn subtract_from(&self, other: &mut BitSet<T>) -> bool { | |
236 | assert_eq!(self.domain_size, other.domain_size); | |
dfeec247 | 237 | bitwise(&mut other.words, &self.words, |a, b| a & !b) |
0bf4aa26 XL |
238 | } |
239 | } | |
240 | ||
1b1a35ee XL |
241 | impl<T> Clone for BitSet<T> { |
242 | fn clone(&self) -> Self { | |
243 | BitSet { domain_size: self.domain_size, words: self.words.clone(), marker: PhantomData } | |
244 | } | |
245 | ||
246 | fn clone_from(&mut self, from: &Self) { | |
247 | if self.domain_size != from.domain_size { | |
248 | self.words.resize(from.domain_size, 0); | |
249 | self.domain_size = from.domain_size; | |
250 | } | |
251 | ||
252 | self.words.copy_from_slice(&from.words); | |
253 | } | |
254 | } | |
255 | ||
0bf4aa26 | 256 | impl<T: Idx> fmt::Debug for BitSet<T> { |
9fa01778 | 257 | fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { |
dfeec247 | 258 | w.debug_list().entries(self.iter()).finish() |
0bf4aa26 XL |
259 | } |
260 | } | |
261 | ||
262 | impl<T: Idx> ToString for BitSet<T> { | |
263 | fn to_string(&self) -> String { | |
264 | let mut result = String::new(); | |
265 | let mut sep = '['; | |
266 | ||
267 | // Note: this is a little endian printout of bytes. | |
268 | ||
269 | // i tracks how many bits we have printed so far. | |
270 | let mut i = 0; | |
271 | for word in &self.words { | |
272 | let mut word = *word; | |
dfeec247 XL |
273 | for _ in 0..WORD_BYTES { |
274 | // for each byte in `word`: | |
0bf4aa26 XL |
275 | let remain = self.domain_size - i; |
276 | // If less than a byte remains, then mask just that many bits. | |
277 | let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF }; | |
278 | assert!(mask <= 0xFF); | |
279 | let byte = word & mask; | |
280 | ||
281 | result.push_str(&format!("{}{:02x}", sep, byte)); | |
282 | ||
dfeec247 XL |
283 | if remain <= 8 { |
284 | break; | |
285 | } | |
0bf4aa26 XL |
286 | word >>= 8; |
287 | i += 8; | |
288 | sep = '-'; | |
289 | } | |
290 | sep = '|'; | |
291 | } | |
292 | result.push(']'); | |
293 | ||
294 | result | |
295 | } | |
296 | } | |
297 | ||
298 | pub struct BitIter<'a, T: Idx> { | |
e74abb32 XL |
299 | /// A copy of the current word, but with any already-visited bits cleared. |
300 | /// (This lets us use `trailing_zeros()` to find the next set bit.) When it | |
301 | /// is reduced to 0, we move onto the next word. | |
302 | word: Word, | |
303 | ||
304 | /// The offset (measured in bits) of the current word. | |
305 | offset: usize, | |
306 | ||
307 | /// Underlying iterator over the words. | |
308 | iter: slice::Iter<'a, Word>, | |
309 | ||
dfeec247 | 310 | marker: PhantomData<T>, |
0bf4aa26 XL |
311 | } |
312 | ||
e74abb32 XL |
313 | impl<'a, T: Idx> BitIter<'a, T> { |
314 | #[inline] | |
315 | fn new(words: &'a [Word]) -> BitIter<'a, T> { | |
316 | // We initialize `word` and `offset` to degenerate values. On the first | |
317 | // call to `next()` we will fall through to getting the first word from | |
318 | // `iter`, which sets `word` to the first word (if there is one) and | |
319 | // `offset` to 0. Doing it this way saves us from having to maintain | |
320 | // additional state about whether we have started. | |
321 | BitIter { | |
322 | word: 0, | |
ba9703b0 | 323 | offset: usize::MAX - (WORD_BITS - 1), |
e74abb32 XL |
324 | iter: words.iter(), |
325 | marker: PhantomData, | |
326 | } | |
327 | } | |
328 | } | |
329 | ||
0bf4aa26 XL |
330 | impl<'a, T: Idx> Iterator for BitIter<'a, T> { |
331 | type Item = T; | |
332 | fn next(&mut self) -> Option<T> { | |
333 | loop { | |
e74abb32 XL |
334 | if self.word != 0 { |
335 | // Get the position of the next set bit in the current word, | |
336 | // then clear the bit. | |
337 | let bit_pos = self.word.trailing_zeros() as usize; | |
338 | let bit = 1 << bit_pos; | |
339 | self.word ^= bit; | |
dfeec247 | 340 | return Some(T::new(bit_pos + self.offset)); |
0bf4aa26 XL |
341 | } |
342 | ||
e74abb32 XL |
343 | // Move onto the next word. `wrapping_add()` is needed to handle |
344 | // the degenerate initial value given to `offset` in `new()`. | |
345 | let word = self.iter.next()?; | |
346 | self.word = *word; | |
347 | self.offset = self.offset.wrapping_add(WORD_BITS); | |
0bf4aa26 XL |
348 | } |
349 | } | |
350 | } | |
351 | ||
0bf4aa26 XL |
352 | #[inline] |
353 | fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool | |
dfeec247 XL |
354 | where |
355 | Op: Fn(Word, Word) -> Word, | |
0bf4aa26 XL |
356 | { |
357 | assert_eq!(out_vec.len(), in_vec.len()); | |
17df50a5 | 358 | let mut changed = 0; |
cdc7bbd5 | 359 | for (out_elem, in_elem) in iter::zip(out_vec, in_vec) { |
0bf4aa26 XL |
360 | let old_val = *out_elem; |
361 | let new_val = op(old_val, *in_elem); | |
362 | *out_elem = new_val; | |
17df50a5 XL |
363 | // This is essentially equivalent to a != with changed being a bool, but |
364 | // in practice this code gets auto-vectorized by the compiler for most | |
365 | // operators. Using != here causes us to generate quite poor code as the | |
366 | // compiler tries to go back to a boolean on each loop iteration. | |
367 | changed |= old_val ^ new_val; | |
0bf4aa26 | 368 | } |
17df50a5 | 369 | changed != 0 |
0bf4aa26 XL |
370 | } |
371 | ||
372 | const SPARSE_MAX: usize = 8; | |
373 | ||
374 | /// A fixed-size bitset type with a sparse representation and a maximum of | |
3dfed10e XL |
375 | /// `SPARSE_MAX` elements. The elements are stored as a sorted `ArrayVec` with |
376 | /// no duplicates. | |
0bf4aa26 XL |
377 | /// |
378 | /// This type is used by `HybridBitSet`; do not use directly. | |
379 | #[derive(Clone, Debug)] | |
1b1a35ee | 380 | pub struct SparseBitSet<T> { |
0bf4aa26 | 381 | domain_size: usize, |
cdc7bbd5 | 382 | elems: ArrayVec<T, SPARSE_MAX>, |
0bf4aa26 XL |
383 | } |
384 | ||
385 | impl<T: Idx> SparseBitSet<T> { | |
386 | fn new_empty(domain_size: usize) -> Self { | |
3dfed10e | 387 | SparseBitSet { domain_size, elems: ArrayVec::new() } |
0bf4aa26 XL |
388 | } |
389 | ||
390 | fn len(&self) -> usize { | |
391 | self.elems.len() | |
392 | } | |
393 | ||
394 | fn is_empty(&self) -> bool { | |
395 | self.elems.len() == 0 | |
396 | } | |
397 | ||
398 | fn contains(&self, elem: T) -> bool { | |
399 | assert!(elem.index() < self.domain_size); | |
400 | self.elems.contains(&elem) | |
401 | } | |
402 | ||
403 | fn insert(&mut self, elem: T) -> bool { | |
404 | assert!(elem.index() < self.domain_size); | |
405 | let changed = if let Some(i) = self.elems.iter().position(|&e| e >= elem) { | |
406 | if self.elems[i] == elem { | |
407 | // `elem` is already in the set. | |
408 | false | |
409 | } else { | |
410 | // `elem` is smaller than one or more existing elements. | |
411 | self.elems.insert(i, elem); | |
412 | true | |
413 | } | |
414 | } else { | |
415 | // `elem` is larger than all existing elements. | |
416 | self.elems.push(elem); | |
417 | true | |
418 | }; | |
419 | assert!(self.len() <= SPARSE_MAX); | |
420 | changed | |
421 | } | |
422 | ||
423 | fn remove(&mut self, elem: T) -> bool { | |
424 | assert!(elem.index() < self.domain_size); | |
425 | if let Some(i) = self.elems.iter().position(|&e| e == elem) { | |
426 | self.elems.remove(i); | |
427 | true | |
428 | } else { | |
429 | false | |
430 | } | |
431 | } | |
432 | ||
433 | fn to_dense(&self) -> BitSet<T> { | |
434 | let mut dense = BitSet::new_empty(self.domain_size); | |
435 | for elem in self.elems.iter() { | |
436 | dense.insert(*elem); | |
437 | } | |
438 | dense | |
439 | } | |
440 | ||
9fa01778 | 441 | fn iter(&self) -> slice::Iter<'_, T> { |
0bf4aa26 XL |
442 | self.elems.iter() |
443 | } | |
444 | } | |
445 | ||
446 | impl<T: Idx> UnionIntoBitSet<T> for SparseBitSet<T> { | |
447 | fn union_into(&self, other: &mut BitSet<T>) -> bool { | |
448 | assert_eq!(self.domain_size, other.domain_size); | |
449 | let mut changed = false; | |
450 | for elem in self.iter() { | |
451 | changed |= other.insert(*elem); | |
452 | } | |
453 | changed | |
454 | } | |
455 | } | |
456 | ||
457 | impl<T: Idx> SubtractFromBitSet<T> for SparseBitSet<T> { | |
458 | fn subtract_from(&self, other: &mut BitSet<T>) -> bool { | |
459 | assert_eq!(self.domain_size, other.domain_size); | |
460 | let mut changed = false; | |
461 | for elem in self.iter() { | |
462 | changed |= other.remove(*elem); | |
463 | } | |
464 | changed | |
465 | } | |
466 | } | |
467 | ||
468 | /// A fixed-size bitset type with a hybrid representation: sparse when there | |
469 | /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more | |
470 | /// than `SPARSE_MAX`. | |
471 | /// | |
472 | /// This type is especially efficient for sets that typically have a small | |
473 | /// number of elements, but a large `domain_size`, and are cleared frequently. | |
474 | /// | |
475 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
476 | /// just be `usize`. | |
477 | /// | |
478 | /// All operations that involve an element will panic if the element is equal | |
479 | /// to or greater than the domain size. All operations that involve two bitsets | |
480 | /// will panic if the bitsets have differing domain sizes. | |
1b1a35ee XL |
481 | #[derive(Clone)] |
482 | pub enum HybridBitSet<T> { | |
0bf4aa26 XL |
483 | Sparse(SparseBitSet<T>), |
484 | Dense(BitSet<T>), | |
485 | } | |
486 | ||
1b1a35ee XL |
487 | impl<T: Idx> fmt::Debug for HybridBitSet<T> { |
488 | fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { | |
489 | match self { | |
490 | Self::Sparse(b) => b.fmt(w), | |
491 | Self::Dense(b) => b.fmt(w), | |
492 | } | |
493 | } | |
494 | } | |
495 | ||
0bf4aa26 XL |
496 | impl<T: Idx> HybridBitSet<T> { |
497 | pub fn new_empty(domain_size: usize) -> Self { | |
498 | HybridBitSet::Sparse(SparseBitSet::new_empty(domain_size)) | |
499 | } | |
500 | ||
1b1a35ee | 501 | pub fn domain_size(&self) -> usize { |
0bf4aa26 XL |
502 | match self { |
503 | HybridBitSet::Sparse(sparse) => sparse.domain_size, | |
504 | HybridBitSet::Dense(dense) => dense.domain_size, | |
505 | } | |
506 | } | |
507 | ||
508 | pub fn clear(&mut self) { | |
509 | let domain_size = self.domain_size(); | |
510 | *self = HybridBitSet::new_empty(domain_size); | |
511 | } | |
512 | ||
513 | pub fn contains(&self, elem: T) -> bool { | |
514 | match self { | |
515 | HybridBitSet::Sparse(sparse) => sparse.contains(elem), | |
516 | HybridBitSet::Dense(dense) => dense.contains(elem), | |
517 | } | |
518 | } | |
519 | ||
520 | pub fn superset(&self, other: &HybridBitSet<T>) -> bool { | |
521 | match (self, other) { | |
522 | (HybridBitSet::Dense(self_dense), HybridBitSet::Dense(other_dense)) => { | |
523 | self_dense.superset(other_dense) | |
524 | } | |
525 | _ => { | |
526 | assert!(self.domain_size() == other.domain_size()); | |
527 | other.iter().all(|elem| self.contains(elem)) | |
528 | } | |
529 | } | |
530 | } | |
531 | ||
532 | pub fn is_empty(&self) -> bool { | |
533 | match self { | |
534 | HybridBitSet::Sparse(sparse) => sparse.is_empty(), | |
535 | HybridBitSet::Dense(dense) => dense.is_empty(), | |
536 | } | |
537 | } | |
538 | ||
539 | pub fn insert(&mut self, elem: T) -> bool { | |
540 | // No need to check `elem` against `self.domain_size` here because all | |
541 | // the match cases check it, one way or another. | |
542 | match self { | |
543 | HybridBitSet::Sparse(sparse) if sparse.len() < SPARSE_MAX => { | |
544 | // The set is sparse and has space for `elem`. | |
545 | sparse.insert(elem) | |
546 | } | |
547 | HybridBitSet::Sparse(sparse) if sparse.contains(elem) => { | |
548 | // The set is sparse and does not have space for `elem`, but | |
549 | // that doesn't matter because `elem` is already present. | |
550 | false | |
551 | } | |
552 | HybridBitSet::Sparse(sparse) => { | |
553 | // The set is sparse and full. Convert to a dense set. | |
554 | let mut dense = sparse.to_dense(); | |
555 | let changed = dense.insert(elem); | |
556 | assert!(changed); | |
557 | *self = HybridBitSet::Dense(dense); | |
558 | changed | |
559 | } | |
560 | HybridBitSet::Dense(dense) => dense.insert(elem), | |
561 | } | |
562 | } | |
563 | ||
564 | pub fn insert_all(&mut self) { | |
565 | let domain_size = self.domain_size(); | |
566 | match self { | |
567 | HybridBitSet::Sparse(_) => { | |
568 | *self = HybridBitSet::Dense(BitSet::new_filled(domain_size)); | |
569 | } | |
570 | HybridBitSet::Dense(dense) => dense.insert_all(), | |
571 | } | |
572 | } | |
573 | ||
574 | pub fn remove(&mut self, elem: T) -> bool { | |
575 | // Note: we currently don't bother going from Dense back to Sparse. | |
576 | match self { | |
577 | HybridBitSet::Sparse(sparse) => sparse.remove(elem), | |
578 | HybridBitSet::Dense(dense) => dense.remove(elem), | |
579 | } | |
580 | } | |
581 | ||
582 | pub fn union(&mut self, other: &HybridBitSet<T>) -> bool { | |
583 | match self { | |
584 | HybridBitSet::Sparse(self_sparse) => { | |
585 | match other { | |
586 | HybridBitSet::Sparse(other_sparse) => { | |
587 | // Both sets are sparse. Add the elements in | |
588 | // `other_sparse` to `self` one at a time. This | |
589 | // may or may not cause `self` to be densified. | |
590 | assert_eq!(self.domain_size(), other.domain_size()); | |
591 | let mut changed = false; | |
592 | for elem in other_sparse.iter() { | |
593 | changed |= self.insert(*elem); | |
594 | } | |
595 | changed | |
596 | } | |
597 | HybridBitSet::Dense(other_dense) => { | |
dc9dc135 XL |
598 | // `self` is sparse and `other` is dense. To |
599 | // merge them, we have two available strategies: | |
600 | // * Densify `self` then merge other | |
601 | // * Clone other then integrate bits from `self` | |
602 | // The second strategy requires dedicated method | |
603 | // since the usual `union` returns the wrong | |
604 | // result. In the dedicated case the computation | |
605 | // is slightly faster if the bits of the sparse | |
606 | // bitset map to only few words of the dense | |
607 | // representation, i.e. indices are near each | |
608 | // other. | |
609 | // | |
610 | // Benchmarking seems to suggest that the second | |
611 | // option is worth it. | |
612 | let mut new_dense = other_dense.clone(); | |
613 | let changed = new_dense.reverse_union_sparse(self_sparse); | |
0bf4aa26 XL |
614 | *self = HybridBitSet::Dense(new_dense); |
615 | changed | |
616 | } | |
617 | } | |
618 | } | |
619 | ||
620 | HybridBitSet::Dense(self_dense) => self_dense.union(other), | |
621 | } | |
622 | } | |
623 | ||
624 | /// Converts to a dense set, consuming itself in the process. | |
625 | pub fn to_dense(self) -> BitSet<T> { | |
626 | match self { | |
627 | HybridBitSet::Sparse(sparse) => sparse.to_dense(), | |
628 | HybridBitSet::Dense(dense) => dense, | |
629 | } | |
630 | } | |
631 | ||
9fa01778 | 632 | pub fn iter(&self) -> HybridIter<'_, T> { |
0bf4aa26 XL |
633 | match self { |
634 | HybridBitSet::Sparse(sparse) => HybridIter::Sparse(sparse.iter()), | |
635 | HybridBitSet::Dense(dense) => HybridIter::Dense(dense.iter()), | |
636 | } | |
637 | } | |
638 | } | |
639 | ||
640 | impl<T: Idx> UnionIntoBitSet<T> for HybridBitSet<T> { | |
641 | fn union_into(&self, other: &mut BitSet<T>) -> bool { | |
642 | match self { | |
643 | HybridBitSet::Sparse(sparse) => sparse.union_into(other), | |
644 | HybridBitSet::Dense(dense) => dense.union_into(other), | |
645 | } | |
646 | } | |
647 | } | |
648 | ||
649 | impl<T: Idx> SubtractFromBitSet<T> for HybridBitSet<T> { | |
650 | fn subtract_from(&self, other: &mut BitSet<T>) -> bool { | |
651 | match self { | |
652 | HybridBitSet::Sparse(sparse) => sparse.subtract_from(other), | |
653 | HybridBitSet::Dense(dense) => dense.subtract_from(other), | |
654 | } | |
655 | } | |
656 | } | |
657 | ||
658 | pub enum HybridIter<'a, T: Idx> { | |
659 | Sparse(slice::Iter<'a, T>), | |
660 | Dense(BitIter<'a, T>), | |
661 | } | |
662 | ||
663 | impl<'a, T: Idx> Iterator for HybridIter<'a, T> { | |
664 | type Item = T; | |
665 | ||
666 | fn next(&mut self) -> Option<T> { | |
667 | match self { | |
e74abb32 | 668 | HybridIter::Sparse(sparse) => sparse.next().copied(), |
0bf4aa26 XL |
669 | HybridIter::Dense(dense) => dense.next(), |
670 | } | |
671 | } | |
672 | } | |
673 | ||
674 | /// A resizable bitset type with a dense representation. | |
675 | /// | |
676 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
677 | /// just be `usize`. | |
678 | /// | |
679 | /// All operations that involve an element will panic if the element is equal | |
680 | /// to or greater than the domain size. | |
681 | #[derive(Clone, Debug, PartialEq)] | |
682 | pub struct GrowableBitSet<T: Idx> { | |
683 | bit_set: BitSet<T>, | |
684 | } | |
685 | ||
686 | impl<T: Idx> GrowableBitSet<T> { | |
687 | /// Ensure that the set can hold at least `min_domain_size` elements. | |
688 | pub fn ensure(&mut self, min_domain_size: usize) { | |
689 | if self.bit_set.domain_size < min_domain_size { | |
690 | self.bit_set.domain_size = min_domain_size; | |
691 | } | |
692 | ||
693 | let min_num_words = num_words(min_domain_size); | |
694 | if self.bit_set.words.len() < min_num_words { | |
695 | self.bit_set.words.resize(min_num_words, 0) | |
696 | } | |
697 | } | |
698 | ||
699 | pub fn new_empty() -> GrowableBitSet<T> { | |
700 | GrowableBitSet { bit_set: BitSet::new_empty(0) } | |
701 | } | |
702 | ||
48663c56 XL |
703 | pub fn with_capacity(capacity: usize) -> GrowableBitSet<T> { |
704 | GrowableBitSet { bit_set: BitSet::new_empty(capacity) } | |
0bf4aa26 XL |
705 | } |
706 | ||
9fa01778 | 707 | /// Returns `true` if the set has changed. |
0bf4aa26 XL |
708 | #[inline] |
709 | pub fn insert(&mut self, elem: T) -> bool { | |
710 | self.ensure(elem.index() + 1); | |
711 | self.bit_set.insert(elem) | |
712 | } | |
713 | ||
5869c6ff XL |
714 | /// Returns `true` if the set has changed. |
715 | #[inline] | |
716 | pub fn remove(&mut self, elem: T) -> bool { | |
717 | self.ensure(elem.index() + 1); | |
718 | self.bit_set.remove(elem) | |
719 | } | |
720 | ||
721 | #[inline] | |
722 | pub fn is_empty(&self) -> bool { | |
723 | self.bit_set.is_empty() | |
724 | } | |
725 | ||
0bf4aa26 XL |
726 | #[inline] |
727 | pub fn contains(&self, elem: T) -> bool { | |
728 | let (word_index, mask) = word_index_and_mask(elem); | |
dfeec247 | 729 | if let Some(word) = self.bit_set.words.get(word_index) { (word & mask) != 0 } else { false } |
0bf4aa26 XL |
730 | } |
731 | } | |
732 | ||
733 | /// A fixed-size 2D bit matrix type with a dense representation. | |
734 | /// | |
735 | /// `R` and `C` are index types used to identify rows and columns respectively; | |
736 | /// typically newtyped `usize` wrappers, but they can also just be `usize`. | |
737 | /// | |
738 | /// All operations that involve a row and/or column index will panic if the | |
739 | /// index exceeds the relevant bound. | |
3dfed10e | 740 | #[derive(Clone, Eq, PartialEq, Decodable, Encodable)] |
0bf4aa26 XL |
741 | pub struct BitMatrix<R: Idx, C: Idx> { |
742 | num_rows: usize, | |
743 | num_columns: usize, | |
744 | words: Vec<Word>, | |
745 | marker: PhantomData<(R, C)>, | |
746 | } | |
747 | ||
748 | impl<R: Idx, C: Idx> BitMatrix<R, C> { | |
9fa01778 | 749 | /// Creates a new `rows x columns` matrix, initially empty. |
0bf4aa26 XL |
750 | pub fn new(num_rows: usize, num_columns: usize) -> BitMatrix<R, C> { |
751 | // For every element, we need one bit for every other | |
752 | // element. Round up to an even number of words. | |
753 | let words_per_row = num_words(num_columns); | |
754 | BitMatrix { | |
755 | num_rows, | |
756 | num_columns, | |
757 | words: vec![0; num_rows * words_per_row], | |
758 | marker: PhantomData, | |
759 | } | |
760 | } | |
761 | ||
dc9dc135 XL |
762 | /// Creates a new matrix, with `row` used as the value for every row. |
763 | pub fn from_row_n(row: &BitSet<C>, num_rows: usize) -> BitMatrix<R, C> { | |
764 | let num_columns = row.domain_size(); | |
765 | let words_per_row = num_words(num_columns); | |
766 | assert_eq!(words_per_row, row.words().len()); | |
767 | BitMatrix { | |
768 | num_rows, | |
769 | num_columns, | |
770 | words: iter::repeat(row.words()).take(num_rows).flatten().cloned().collect(), | |
771 | marker: PhantomData, | |
772 | } | |
773 | } | |
774 | ||
775 | pub fn rows(&self) -> impl Iterator<Item = R> { | |
776 | (0..self.num_rows).map(R::new) | |
777 | } | |
778 | ||
0bf4aa26 XL |
779 | /// The range of bits for a given row. |
780 | fn range(&self, row: R) -> (usize, usize) { | |
781 | let words_per_row = num_words(self.num_columns); | |
782 | let start = row.index() * words_per_row; | |
783 | (start, start + words_per_row) | |
784 | } | |
785 | ||
786 | /// Sets the cell at `(row, column)` to true. Put another way, insert | |
787 | /// `column` to the bitset for `row`. | |
788 | /// | |
9fa01778 | 789 | /// Returns `true` if this changed the matrix. |
0bf4aa26 XL |
790 | pub fn insert(&mut self, row: R, column: C) -> bool { |
791 | assert!(row.index() < self.num_rows && column.index() < self.num_columns); | |
792 | let (start, _) = self.range(row); | |
793 | let (word_index, mask) = word_index_and_mask(column); | |
794 | let words = &mut self.words[..]; | |
795 | let word = words[start + word_index]; | |
796 | let new_word = word | mask; | |
797 | words[start + word_index] = new_word; | |
798 | word != new_word | |
799 | } | |
800 | ||
801 | /// Do the bits from `row` contain `column`? Put another way, is | |
802 | /// the matrix cell at `(row, column)` true? Put yet another way, | |
803 | /// if the matrix represents (transitive) reachability, can | |
804 | /// `row` reach `column`? | |
805 | pub fn contains(&self, row: R, column: C) -> bool { | |
806 | assert!(row.index() < self.num_rows && column.index() < self.num_columns); | |
807 | let (start, _) = self.range(row); | |
808 | let (word_index, mask) = word_index_and_mask(column); | |
809 | (self.words[start + word_index] & mask) != 0 | |
810 | } | |
811 | ||
9fa01778 | 812 | /// Returns those indices that are true in rows `a` and `b`. This |
3dfed10e | 813 | /// is an *O*(*n*) operation where *n* is the number of elements |
0bf4aa26 XL |
814 | /// (somewhat independent from the actual size of the |
815 | /// intersection, in particular). | |
816 | pub fn intersect_rows(&self, row1: R, row2: R) -> Vec<C> { | |
817 | assert!(row1.index() < self.num_rows && row2.index() < self.num_rows); | |
818 | let (row1_start, row1_end) = self.range(row1); | |
819 | let (row2_start, row2_end) = self.range(row2); | |
820 | let mut result = Vec::with_capacity(self.num_columns); | |
821 | for (base, (i, j)) in (row1_start..row1_end).zip(row2_start..row2_end).enumerate() { | |
822 | let mut v = self.words[i] & self.words[j]; | |
823 | for bit in 0..WORD_BITS { | |
824 | if v == 0 { | |
825 | break; | |
826 | } | |
827 | if v & 0x1 != 0 { | |
828 | result.push(C::new(base * WORD_BITS + bit)); | |
829 | } | |
830 | v >>= 1; | |
831 | } | |
832 | } | |
833 | result | |
834 | } | |
835 | ||
9fa01778 XL |
836 | /// Adds the bits from row `read` to the bits from row `write`, and |
837 | /// returns `true` if anything changed. | |
0bf4aa26 XL |
838 | /// |
839 | /// This is used when computing transitive reachability because if | |
840 | /// you have an edge `write -> read`, because in that case | |
841 | /// `write` can reach everything that `read` can (and | |
842 | /// potentially more). | |
843 | pub fn union_rows(&mut self, read: R, write: R) -> bool { | |
844 | assert!(read.index() < self.num_rows && write.index() < self.num_rows); | |
845 | let (read_start, read_end) = self.range(read); | |
846 | let (write_start, write_end) = self.range(write); | |
847 | let words = &mut self.words[..]; | |
848 | let mut changed = false; | |
cdc7bbd5 | 849 | for (read_index, write_index) in iter::zip(read_start..read_end, write_start..write_end) { |
0bf4aa26 XL |
850 | let word = words[write_index]; |
851 | let new_word = word | words[read_index]; | |
852 | words[write_index] = new_word; | |
853 | changed |= word != new_word; | |
854 | } | |
855 | changed | |
856 | } | |
857 | ||
dc9dc135 XL |
858 | /// Adds the bits from `with` to the bits from row `write`, and |
859 | /// returns `true` if anything changed. | |
860 | pub fn union_row_with(&mut self, with: &BitSet<C>, write: R) -> bool { | |
861 | assert!(write.index() < self.num_rows); | |
862 | assert_eq!(with.domain_size(), self.num_columns); | |
863 | let (write_start, write_end) = self.range(write); | |
864 | let mut changed = false; | |
cdc7bbd5 | 865 | for (read_index, write_index) in iter::zip(0..with.words().len(), write_start..write_end) { |
dc9dc135 XL |
866 | let word = self.words[write_index]; |
867 | let new_word = word | with.words()[read_index]; | |
868 | self.words[write_index] = new_word; | |
869 | changed |= word != new_word; | |
870 | } | |
871 | changed | |
872 | } | |
873 | ||
874 | /// Sets every cell in `row` to true. | |
875 | pub fn insert_all_into_row(&mut self, row: R) { | |
876 | assert!(row.index() < self.num_rows); | |
877 | let (start, end) = self.range(row); | |
878 | let words = &mut self.words[..]; | |
879 | for index in start..end { | |
880 | words[index] = !0; | |
881 | } | |
882 | self.clear_excess_bits(row); | |
883 | } | |
884 | ||
885 | /// Clear excess bits in the final word of the row. | |
886 | fn clear_excess_bits(&mut self, row: R) { | |
887 | let num_bits_in_final_word = self.num_columns % WORD_BITS; | |
888 | if num_bits_in_final_word > 0 { | |
889 | let mask = (1 << num_bits_in_final_word) - 1; | |
890 | let (_, end) = self.range(row); | |
891 | let final_word_idx = end - 1; | |
892 | self.words[final_word_idx] &= mask; | |
893 | } | |
894 | } | |
895 | ||
896 | /// Gets a slice of the underlying words. | |
897 | pub fn words(&self) -> &[Word] { | |
898 | &self.words | |
899 | } | |
900 | ||
0bf4aa26 XL |
901 | /// Iterates through all the columns set to true in a given row of |
902 | /// the matrix. | |
416331ca | 903 | pub fn iter(&self, row: R) -> BitIter<'_, C> { |
0bf4aa26 XL |
904 | assert!(row.index() < self.num_rows); |
905 | let (start, end) = self.range(row); | |
e74abb32 | 906 | BitIter::new(&self.words[start..end]) |
0bf4aa26 | 907 | } |
dc9dc135 XL |
908 | |
909 | /// Returns the number of elements in `row`. | |
910 | pub fn count(&self, row: R) -> usize { | |
911 | let (start, end) = self.range(row); | |
912 | self.words[start..end].iter().map(|e| e.count_ones() as usize).sum() | |
913 | } | |
0bf4aa26 XL |
914 | } |
915 | ||
f035d41b XL |
916 | impl<R: Idx, C: Idx> fmt::Debug for BitMatrix<R, C> { |
917 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { | |
918 | /// Forces its contents to print in regular mode instead of alternate mode. | |
919 | struct OneLinePrinter<T>(T); | |
920 | impl<T: fmt::Debug> fmt::Debug for OneLinePrinter<T> { | |
921 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { | |
922 | write!(fmt, "{:?}", self.0) | |
923 | } | |
924 | } | |
925 | ||
926 | write!(fmt, "BitMatrix({}x{}) ", self.num_rows, self.num_columns)?; | |
927 | let items = self.rows().flat_map(|r| self.iter(r).map(move |c| (r, c))); | |
928 | fmt.debug_set().entries(items.map(OneLinePrinter)).finish() | |
929 | } | |
930 | } | |
931 | ||
0bf4aa26 XL |
932 | /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately |
933 | /// sparse representation. | |
934 | /// | |
935 | /// Initially, every row has no explicit representation. If any bit within a | |
936 | /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`. | |
937 | /// Furthermore, any previously uninstantiated rows prior to it will be | |
938 | /// instantiated as `None`. Those prior rows may themselves become fully | |
939 | /// instantiated later on if any of their bits are set. | |
940 | /// | |
941 | /// `R` and `C` are index types used to identify rows and columns respectively; | |
942 | /// typically newtyped `usize` wrappers, but they can also just be `usize`. | |
943 | #[derive(Clone, Debug)] | |
944 | pub struct SparseBitMatrix<R, C> | |
945 | where | |
946 | R: Idx, | |
947 | C: Idx, | |
948 | { | |
949 | num_columns: usize, | |
950 | rows: IndexVec<R, Option<HybridBitSet<C>>>, | |
951 | } | |
952 | ||
953 | impl<R: Idx, C: Idx> SparseBitMatrix<R, C> { | |
9fa01778 | 954 | /// Creates a new empty sparse bit matrix with no rows or columns. |
0bf4aa26 | 955 | pub fn new(num_columns: usize) -> Self { |
dfeec247 | 956 | Self { num_columns, rows: IndexVec::new() } |
0bf4aa26 XL |
957 | } |
958 | ||
959 | fn ensure_row(&mut self, row: R) -> &mut HybridBitSet<C> { | |
960 | // Instantiate any missing rows up to and including row `row` with an | |
961 | // empty HybridBitSet. | |
962 | self.rows.ensure_contains_elem(row, || None); | |
963 | ||
964 | // Then replace row `row` with a full HybridBitSet if necessary. | |
965 | let num_columns = self.num_columns; | |
966 | self.rows[row].get_or_insert_with(|| HybridBitSet::new_empty(num_columns)) | |
967 | } | |
968 | ||
969 | /// Sets the cell at `(row, column)` to true. Put another way, insert | |
970 | /// `column` to the bitset for `row`. | |
971 | /// | |
9fa01778 | 972 | /// Returns `true` if this changed the matrix. |
0bf4aa26 XL |
973 | pub fn insert(&mut self, row: R, column: C) -> bool { |
974 | self.ensure_row(row).insert(column) | |
975 | } | |
976 | ||
977 | /// Do the bits from `row` contain `column`? Put another way, is | |
978 | /// the matrix cell at `(row, column)` true? Put yet another way, | |
979 | /// if the matrix represents (transitive) reachability, can | |
980 | /// `row` reach `column`? | |
981 | pub fn contains(&self, row: R, column: C) -> bool { | |
982 | self.row(row).map_or(false, |r| r.contains(column)) | |
983 | } | |
984 | ||
9fa01778 XL |
985 | /// Adds the bits from row `read` to the bits from row `write`, and |
986 | /// returns `true` if anything changed. | |
0bf4aa26 XL |
987 | /// |
988 | /// This is used when computing transitive reachability because if | |
989 | /// you have an edge `write -> read`, because in that case | |
990 | /// `write` can reach everything that `read` can (and | |
991 | /// potentially more). | |
992 | pub fn union_rows(&mut self, read: R, write: R) -> bool { | |
993 | if read == write || self.row(read).is_none() { | |
994 | return false; | |
995 | } | |
996 | ||
997 | self.ensure_row(write); | |
998 | if let (Some(read_row), Some(write_row)) = self.rows.pick2_mut(read, write) { | |
999 | write_row.union(read_row) | |
1000 | } else { | |
1001 | unreachable!() | |
1002 | } | |
1003 | } | |
1004 | ||
1005 | /// Union a row, `from`, into the `into` row. | |
1006 | pub fn union_into_row(&mut self, into: R, from: &HybridBitSet<C>) -> bool { | |
1007 | self.ensure_row(into).union(from) | |
1008 | } | |
1009 | ||
1010 | /// Insert all bits in the given row. | |
1011 | pub fn insert_all_into_row(&mut self, row: R) { | |
1012 | self.ensure_row(row).insert_all(); | |
1013 | } | |
1014 | ||
1015 | pub fn rows(&self) -> impl Iterator<Item = R> { | |
1016 | self.rows.indices() | |
1017 | } | |
1018 | ||
1019 | /// Iterates through all the columns set to true in a given row of | |
1020 | /// the matrix. | |
1021 | pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a { | |
1022 | self.row(row).into_iter().flat_map(|r| r.iter()) | |
1023 | } | |
1024 | ||
1025 | pub fn row(&self, row: R) -> Option<&HybridBitSet<C>> { | |
dfeec247 | 1026 | if let Some(Some(row)) = self.rows.get(row) { Some(row) } else { None } |
0bf4aa26 XL |
1027 | } |
1028 | } | |
1029 | ||
1030 | #[inline] | |
1031 | fn num_words<T: Idx>(domain_size: T) -> usize { | |
1032 | (domain_size.index() + WORD_BITS - 1) / WORD_BITS | |
1033 | } | |
1034 | ||
1035 | #[inline] | |
1036 | fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) { | |
1037 | let elem = elem.index(); | |
1038 | let word_index = elem / WORD_BITS; | |
1039 | let mask = 1 << (elem % WORD_BITS); | |
1040 | (word_index, mask) | |
1041 | } | |
3dfed10e XL |
1042 | |
1043 | /// Integral type used to represent the bit set. | |
1044 | pub trait FiniteBitSetTy: | |
1045 | BitAnd<Output = Self> | |
1046 | + BitAndAssign | |
1047 | + BitOrAssign | |
1048 | + Clone | |
1049 | + Copy | |
1050 | + Shl | |
1051 | + Not<Output = Self> | |
1052 | + PartialEq | |
1053 | + Sized | |
1054 | { | |
1055 | /// Size of the domain representable by this type, e.g. 64 for `u64`. | |
1056 | const DOMAIN_SIZE: u32; | |
1057 | ||
1058 | /// Value which represents the `FiniteBitSet` having every bit set. | |
1059 | const FILLED: Self; | |
1060 | /// Value which represents the `FiniteBitSet` having no bits set. | |
1061 | const EMPTY: Self; | |
1062 | ||
1063 | /// Value for one as the integral type. | |
1064 | const ONE: Self; | |
1065 | /// Value for zero as the integral type. | |
1066 | const ZERO: Self; | |
1067 | ||
1068 | /// Perform a checked left shift on the integral type. | |
1069 | fn checked_shl(self, rhs: u32) -> Option<Self>; | |
1070 | /// Perform a checked right shift on the integral type. | |
1071 | fn checked_shr(self, rhs: u32) -> Option<Self>; | |
1072 | } | |
1073 | ||
1074 | impl FiniteBitSetTy for u32 { | |
1075 | const DOMAIN_SIZE: u32 = 32; | |
1076 | ||
1077 | const FILLED: Self = Self::MAX; | |
1078 | const EMPTY: Self = Self::MIN; | |
1079 | ||
1080 | const ONE: Self = 1u32; | |
1081 | const ZERO: Self = 0u32; | |
1082 | ||
1083 | fn checked_shl(self, rhs: u32) -> Option<Self> { | |
1084 | self.checked_shl(rhs) | |
1085 | } | |
1086 | ||
1087 | fn checked_shr(self, rhs: u32) -> Option<Self> { | |
1088 | self.checked_shr(rhs) | |
1089 | } | |
1090 | } | |
1091 | ||
1092 | impl std::fmt::Debug for FiniteBitSet<u32> { | |
1093 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1094 | write!(f, "{:032b}", self.0) | |
1095 | } | |
1096 | } | |
1097 | ||
1098 | impl FiniteBitSetTy for u64 { | |
1099 | const DOMAIN_SIZE: u32 = 64; | |
1100 | ||
1101 | const FILLED: Self = Self::MAX; | |
1102 | const EMPTY: Self = Self::MIN; | |
1103 | ||
1104 | const ONE: Self = 1u64; | |
1105 | const ZERO: Self = 0u64; | |
1106 | ||
1107 | fn checked_shl(self, rhs: u32) -> Option<Self> { | |
1108 | self.checked_shl(rhs) | |
1109 | } | |
1110 | ||
1111 | fn checked_shr(self, rhs: u32) -> Option<Self> { | |
1112 | self.checked_shr(rhs) | |
1113 | } | |
1114 | } | |
1115 | ||
1116 | impl std::fmt::Debug for FiniteBitSet<u64> { | |
1117 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1118 | write!(f, "{:064b}", self.0) | |
1119 | } | |
1120 | } | |
1121 | ||
1122 | impl FiniteBitSetTy for u128 { | |
1123 | const DOMAIN_SIZE: u32 = 128; | |
1124 | ||
1125 | const FILLED: Self = Self::MAX; | |
1126 | const EMPTY: Self = Self::MIN; | |
1127 | ||
1128 | const ONE: Self = 1u128; | |
1129 | const ZERO: Self = 0u128; | |
1130 | ||
1131 | fn checked_shl(self, rhs: u32) -> Option<Self> { | |
1132 | self.checked_shl(rhs) | |
1133 | } | |
1134 | ||
1135 | fn checked_shr(self, rhs: u32) -> Option<Self> { | |
1136 | self.checked_shr(rhs) | |
1137 | } | |
1138 | } | |
1139 | ||
1140 | impl std::fmt::Debug for FiniteBitSet<u128> { | |
1141 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1142 | write!(f, "{:0128b}", self.0) | |
1143 | } | |
1144 | } | |
1145 | ||
1146 | /// A fixed-sized bitset type represented by an integer type. Indices outwith than the range | |
1147 | /// representable by `T` are considered set. | |
1148 | #[derive(Copy, Clone, Eq, PartialEq, Decodable, Encodable)] | |
1149 | pub struct FiniteBitSet<T: FiniteBitSetTy>(pub T); | |
1150 | ||
1151 | impl<T: FiniteBitSetTy> FiniteBitSet<T> { | |
1152 | /// Creates a new, empty bitset. | |
1153 | pub fn new_empty() -> Self { | |
1154 | Self(T::EMPTY) | |
1155 | } | |
1156 | ||
1157 | /// Sets the `index`th bit. | |
1158 | pub fn set(&mut self, index: u32) { | |
1159 | self.0 |= T::ONE.checked_shl(index).unwrap_or(T::ZERO); | |
1160 | } | |
1161 | ||
1162 | /// Unsets the `index`th bit. | |
1163 | pub fn clear(&mut self, index: u32) { | |
1164 | self.0 &= !T::ONE.checked_shl(index).unwrap_or(T::ZERO); | |
1165 | } | |
1166 | ||
1167 | /// Sets the `i`th to `j`th bits. | |
1168 | pub fn set_range(&mut self, range: Range<u32>) { | |
1169 | let bits = T::FILLED | |
1170 | .checked_shl(range.end - range.start) | |
1171 | .unwrap_or(T::ZERO) | |
1172 | .not() | |
1173 | .checked_shl(range.start) | |
1174 | .unwrap_or(T::ZERO); | |
1175 | self.0 |= bits; | |
1176 | } | |
1177 | ||
1178 | /// Is the set empty? | |
1179 | pub fn is_empty(&self) -> bool { | |
1180 | self.0 == T::EMPTY | |
1181 | } | |
1182 | ||
1183 | /// Returns the domain size of the bitset. | |
1184 | pub fn within_domain(&self, index: u32) -> bool { | |
1185 | index < T::DOMAIN_SIZE | |
1186 | } | |
1187 | ||
1188 | /// Returns if the `index`th bit is set. | |
1189 | pub fn contains(&self, index: u32) -> Option<bool> { | |
1190 | self.within_domain(index) | |
1191 | .then(|| ((self.0.checked_shr(index).unwrap_or(T::ONE)) & T::ONE) == T::ONE) | |
1192 | } | |
1193 | } | |
1194 | ||
1195 | impl<T: FiniteBitSetTy> Default for FiniteBitSet<T> { | |
1196 | fn default() -> Self { | |
1197 | Self::new_empty() | |
1198 | } | |
1199 | } |