]>
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; | |
3c0e092e | 7 | use std::ops::{BitAnd, BitAndAssign, BitOrAssign, Bound, Not, Range, RangeBounds, Shl}; |
5e7ed085 | 8 | use std::rc::Rc; |
0bf4aa26 | 9 | use std::slice; |
416331ca | 10 | |
3dfed10e XL |
11 | use rustc_macros::{Decodable, Encodable}; |
12 | ||
5e7ed085 FG |
13 | use Chunk::*; |
14 | ||
dc9dc135 | 15 | #[cfg(test)] |
416331ca | 16 | mod tests; |
0bf4aa26 | 17 | |
5e7ed085 FG |
18 | type Word = u64; |
19 | const WORD_BYTES: usize = mem::size_of::<Word>(); | |
20 | const WORD_BITS: usize = WORD_BYTES * 8; | |
21 | ||
22 | // The choice of chunk size has some trade-offs. | |
23 | // | |
24 | // A big chunk size tends to favour cases where many large `ChunkedBitSet`s are | |
25 | // present, because they require fewer `Chunk`s, reducing the number of | |
26 | // allocations and reducing peak memory usage. Also, fewer chunk operations are | |
27 | // required, though more of them might be `Mixed`. | |
28 | // | |
29 | // A small chunk size tends to favour cases where many small `ChunkedBitSet`s | |
30 | // are present, because less space is wasted at the end of the final chunk (if | |
31 | // it's not full). | |
32 | const CHUNK_WORDS: usize = 32; | |
33 | const CHUNK_BITS: usize = CHUNK_WORDS * WORD_BITS; // 2048 bits | |
34 | ||
35 | /// ChunkSize is small to keep `Chunk` small. The static assertion ensures it's | |
36 | /// not too small. | |
37 | type ChunkSize = u16; | |
38 | const _: () = assert!(CHUNK_BITS <= ChunkSize::MAX as usize); | |
0bf4aa26 | 39 | |
94222f64 XL |
40 | pub trait BitRelations<Rhs> { |
41 | fn union(&mut self, other: &Rhs) -> bool; | |
42 | fn subtract(&mut self, other: &Rhs) -> bool; | |
43 | fn intersect(&mut self, other: &Rhs) -> bool; | |
44 | } | |
45 | ||
3c0e092e XL |
46 | #[inline] |
47 | fn inclusive_start_end<T: Idx>( | |
48 | range: impl RangeBounds<T>, | |
49 | domain: usize, | |
50 | ) -> Option<(usize, usize)> { | |
51 | // Both start and end are inclusive. | |
52 | let start = match range.start_bound().cloned() { | |
53 | Bound::Included(start) => start.index(), | |
54 | Bound::Excluded(start) => start.index() + 1, | |
55 | Bound::Unbounded => 0, | |
56 | }; | |
57 | let end = match range.end_bound().cloned() { | |
58 | Bound::Included(end) => end.index(), | |
59 | Bound::Excluded(end) => end.index().checked_sub(1)?, | |
60 | Bound::Unbounded => domain - 1, | |
61 | }; | |
62 | assert!(end < domain); | |
63 | if start > end { | |
64 | return None; | |
65 | } | |
66 | Some((start, end)) | |
67 | } | |
68 | ||
94222f64 XL |
69 | macro_rules! bit_relations_inherent_impls { |
70 | () => { | |
71 | /// Sets `self = self | other` and returns `true` if `self` changed | |
72 | /// (i.e., if new bits were added). | |
73 | pub fn union<Rhs>(&mut self, other: &Rhs) -> bool | |
74 | where | |
75 | Self: BitRelations<Rhs>, | |
76 | { | |
77 | <Self as BitRelations<Rhs>>::union(self, other) | |
78 | } | |
79 | ||
80 | /// Sets `self = self - other` and returns `true` if `self` changed. | |
81 | /// (i.e., if any bits were removed). | |
82 | pub fn subtract<Rhs>(&mut self, other: &Rhs) -> bool | |
83 | where | |
84 | Self: BitRelations<Rhs>, | |
85 | { | |
86 | <Self as BitRelations<Rhs>>::subtract(self, other) | |
87 | } | |
88 | ||
89 | /// Sets `self = self & other` and return `true` if `self` changed. | |
90 | /// (i.e., if any bits were removed). | |
91 | pub fn intersect<Rhs>(&mut self, other: &Rhs) -> bool | |
92 | where | |
93 | Self: BitRelations<Rhs>, | |
94 | { | |
95 | <Self as BitRelations<Rhs>>::intersect(self, other) | |
96 | } | |
97 | }; | |
98 | } | |
99 | ||
e74abb32 XL |
100 | /// A fixed-size bitset type with a dense representation. |
101 | /// | |
102 | /// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation. | |
0bf4aa26 XL |
103 | /// |
104 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
105 | /// just be `usize`. | |
106 | /// | |
107 | /// All operations that involve an element will panic if the element is equal | |
108 | /// to or greater than the domain size. All operations that involve two bitsets | |
109 | /// will panic if the bitsets have differing domain sizes. | |
e74abb32 | 110 | /// |
a2a8927a | 111 | #[derive(Eq, PartialEq, Hash, Decodable, Encodable)] |
1b1a35ee | 112 | pub struct BitSet<T> { |
0bf4aa26 XL |
113 | domain_size: usize, |
114 | words: Vec<Word>, | |
115 | marker: PhantomData<T>, | |
116 | } | |
117 | ||
1b1a35ee XL |
118 | impl<T> BitSet<T> { |
119 | /// Gets the domain size. | |
120 | pub fn domain_size(&self) -> usize { | |
121 | self.domain_size | |
122 | } | |
123 | } | |
124 | ||
0bf4aa26 | 125 | impl<T: Idx> BitSet<T> { |
9fa01778 | 126 | /// Creates a new, empty bitset with a given `domain_size`. |
0bf4aa26 XL |
127 | #[inline] |
128 | pub fn new_empty(domain_size: usize) -> BitSet<T> { | |
129 | let num_words = num_words(domain_size); | |
dfeec247 | 130 | BitSet { domain_size, words: vec![0; num_words], marker: PhantomData } |
0bf4aa26 XL |
131 | } |
132 | ||
9fa01778 | 133 | /// Creates a new, filled bitset with a given `domain_size`. |
0bf4aa26 XL |
134 | #[inline] |
135 | pub fn new_filled(domain_size: usize) -> BitSet<T> { | |
136 | let num_words = num_words(domain_size); | |
dfeec247 | 137 | let mut result = BitSet { domain_size, words: vec![!0; num_words], marker: PhantomData }; |
0bf4aa26 XL |
138 | result.clear_excess_bits(); |
139 | result | |
140 | } | |
141 | ||
0bf4aa26 XL |
142 | /// Clear all elements. |
143 | #[inline] | |
144 | pub fn clear(&mut self) { | |
5e7ed085 | 145 | self.words.fill(0); |
0bf4aa26 XL |
146 | } |
147 | ||
148 | /// Clear excess bits in the final word. | |
149 | fn clear_excess_bits(&mut self) { | |
5e7ed085 | 150 | clear_excess_bits_in_final_word(self.domain_size, &mut self.words); |
0bf4aa26 XL |
151 | } |
152 | ||
0bf4aa26 XL |
153 | /// Count the number of set bits in the set. |
154 | pub fn count(&self) -> usize { | |
155 | self.words.iter().map(|e| e.count_ones() as usize).sum() | |
156 | } | |
157 | ||
9fa01778 | 158 | /// Returns `true` if `self` contains `elem`. |
0bf4aa26 XL |
159 | #[inline] |
160 | pub fn contains(&self, elem: T) -> bool { | |
161 | assert!(elem.index() < self.domain_size); | |
162 | let (word_index, mask) = word_index_and_mask(elem); | |
163 | (self.words[word_index] & mask) != 0 | |
164 | } | |
165 | ||
166 | /// Is `self` is a (non-strict) superset of `other`? | |
167 | #[inline] | |
168 | pub fn superset(&self, other: &BitSet<T>) -> bool { | |
169 | assert_eq!(self.domain_size, other.domain_size); | |
170 | self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b) | |
171 | } | |
172 | ||
173 | /// Is the set empty? | |
174 | #[inline] | |
175 | pub fn is_empty(&self) -> bool { | |
176 | self.words.iter().all(|a| *a == 0) | |
177 | } | |
178 | ||
9fa01778 | 179 | /// Insert `elem`. Returns whether the set has changed. |
0bf4aa26 XL |
180 | #[inline] |
181 | pub fn insert(&mut self, elem: T) -> bool { | |
182 | assert!(elem.index() < self.domain_size); | |
183 | let (word_index, mask) = word_index_and_mask(elem); | |
184 | let word_ref = &mut self.words[word_index]; | |
185 | let word = *word_ref; | |
186 | let new_word = word | mask; | |
187 | *word_ref = new_word; | |
188 | new_word != word | |
189 | } | |
190 | ||
3c0e092e XL |
191 | #[inline] |
192 | pub fn insert_range(&mut self, elems: impl RangeBounds<T>) { | |
193 | let Some((start, end)) = inclusive_start_end(elems, self.domain_size) else { | |
194 | return; | |
195 | }; | |
196 | ||
197 | let (start_word_index, start_mask) = word_index_and_mask(start); | |
198 | let (end_word_index, end_mask) = word_index_and_mask(end); | |
199 | ||
200 | // Set all words in between start and end (exclusively of both). | |
201 | for word_index in (start_word_index + 1)..end_word_index { | |
202 | self.words[word_index] = !0; | |
203 | } | |
204 | ||
205 | if start_word_index != end_word_index { | |
206 | // Start and end are in different words, so we handle each in turn. | |
207 | // | |
208 | // We set all leading bits. This includes the start_mask bit. | |
209 | self.words[start_word_index] |= !(start_mask - 1); | |
210 | // And all trailing bits (i.e. from 0..=end) in the end word, | |
211 | // including the end. | |
9c376795 | 212 | self.words[end_word_index] |= end_mask | (end_mask - 1); |
3c0e092e XL |
213 | } else { |
214 | self.words[start_word_index] |= end_mask | (end_mask - start_mask); | |
215 | } | |
216 | } | |
217 | ||
0bf4aa26 XL |
218 | /// Sets all bits to true. |
219 | pub fn insert_all(&mut self) { | |
5e7ed085 | 220 | self.words.fill(!0); |
0bf4aa26 XL |
221 | self.clear_excess_bits(); |
222 | } | |
223 | ||
9fa01778 | 224 | /// Returns `true` if the set has changed. |
0bf4aa26 XL |
225 | #[inline] |
226 | pub fn remove(&mut self, elem: T) -> bool { | |
227 | assert!(elem.index() < self.domain_size); | |
228 | let (word_index, mask) = word_index_and_mask(elem); | |
229 | let word_ref = &mut self.words[word_index]; | |
230 | let word = *word_ref; | |
231 | let new_word = word & !mask; | |
232 | *word_ref = new_word; | |
233 | new_word != word | |
234 | } | |
235 | ||
9fa01778 | 236 | /// Gets a slice of the underlying words. |
0bf4aa26 XL |
237 | pub fn words(&self) -> &[Word] { |
238 | &self.words | |
239 | } | |
240 | ||
241 | /// Iterates over the indices of set bits in a sorted order. | |
242 | #[inline] | |
416331ca | 243 | pub fn iter(&self) -> BitIter<'_, T> { |
e74abb32 | 244 | BitIter::new(&self.words) |
0bf4aa26 XL |
245 | } |
246 | ||
247 | /// Duplicates the set as a hybrid set. | |
248 | pub fn to_hybrid(&self) -> HybridBitSet<T> { | |
249 | // Note: we currently don't bother trying to make a Sparse set. | |
250 | HybridBitSet::Dense(self.to_owned()) | |
251 | } | |
dc9dc135 XL |
252 | |
253 | /// Set `self = self | other`. In contrast to `union` returns `true` if the set contains at | |
254 | /// least one bit that is not in `other` (i.e. `other` is not a superset of `self`). | |
255 | /// | |
256 | /// This is an optimization for union of a hybrid bitset. | |
257 | fn reverse_union_sparse(&mut self, sparse: &SparseBitSet<T>) -> bool { | |
258 | assert!(sparse.domain_size == self.domain_size); | |
259 | self.clear_excess_bits(); | |
260 | ||
261 | let mut not_already = false; | |
262 | // Index of the current word not yet merged. | |
263 | let mut current_index = 0; | |
264 | // Mask of bits that came from the sparse set in the current word. | |
265 | let mut new_bit_mask = 0; | |
266 | for (word_index, mask) in sparse.iter().map(|x| word_index_and_mask(*x)) { | |
267 | // Next bit is in a word not inspected yet. | |
268 | if word_index > current_index { | |
269 | self.words[current_index] |= new_bit_mask; | |
270 | // Were there any bits in the old word that did not occur in the sparse set? | |
271 | not_already |= (self.words[current_index] ^ new_bit_mask) != 0; | |
272 | // Check all words we skipped for any set bit. | |
dfeec247 | 273 | not_already |= self.words[current_index + 1..word_index].iter().any(|&x| x != 0); |
dc9dc135 XL |
274 | // Update next word. |
275 | current_index = word_index; | |
276 | // Reset bit mask, no bits have been merged yet. | |
277 | new_bit_mask = 0; | |
278 | } | |
279 | // Add bit and mark it as coming from the sparse set. | |
280 | // self.words[word_index] |= mask; | |
281 | new_bit_mask |= mask; | |
282 | } | |
283 | self.words[current_index] |= new_bit_mask; | |
284 | // Any bits in the last inspected word that were not in the sparse set? | |
285 | not_already |= (self.words[current_index] ^ new_bit_mask) != 0; | |
286 | // Any bits in the tail? Note `clear_excess_bits` before. | |
dfeec247 | 287 | not_already |= self.words[current_index + 1..].iter().any(|&x| x != 0); |
dc9dc135 XL |
288 | |
289 | not_already | |
290 | } | |
94222f64 | 291 | |
3c0e092e XL |
292 | fn last_set_in(&self, range: impl RangeBounds<T>) -> Option<T> { |
293 | let (start, end) = inclusive_start_end(range, self.domain_size)?; | |
294 | let (start_word_index, _) = word_index_and_mask(start); | |
295 | let (end_word_index, end_mask) = word_index_and_mask(end); | |
296 | ||
297 | let end_word = self.words[end_word_index] & (end_mask | (end_mask - 1)); | |
298 | if end_word != 0 { | |
299 | let pos = max_bit(end_word) + WORD_BITS * end_word_index; | |
300 | if start <= pos { | |
301 | return Some(T::new(pos)); | |
302 | } | |
303 | } | |
304 | ||
305 | // We exclude end_word_index from the range here, because we don't want | |
306 | // to limit ourselves to *just* the last word: the bits set it in may be | |
307 | // after `end`, so it may not work out. | |
308 | if let Some(offset) = | |
309 | self.words[start_word_index..end_word_index].iter().rposition(|&w| w != 0) | |
310 | { | |
311 | let word_idx = start_word_index + offset; | |
312 | let start_word = self.words[word_idx]; | |
313 | let pos = max_bit(start_word) + WORD_BITS * word_idx; | |
314 | if start <= pos { | |
315 | return Some(T::new(pos)); | |
316 | } | |
317 | } | |
318 | ||
319 | None | |
320 | } | |
321 | ||
94222f64 | 322 | bit_relations_inherent_impls! {} |
0bf4aa26 XL |
323 | } |
324 | ||
94222f64 XL |
325 | // dense REL dense |
326 | impl<T: Idx> BitRelations<BitSet<T>> for BitSet<T> { | |
327 | fn union(&mut self, other: &BitSet<T>) -> bool { | |
328 | assert_eq!(self.domain_size, other.domain_size); | |
329 | bitwise(&mut self.words, &other.words, |a, b| a | b) | |
330 | } | |
331 | ||
332 | fn subtract(&mut self, other: &BitSet<T>) -> bool { | |
333 | assert_eq!(self.domain_size, other.domain_size); | |
334 | bitwise(&mut self.words, &other.words, |a, b| a & !b) | |
335 | } | |
336 | ||
337 | fn intersect(&mut self, other: &BitSet<T>) -> bool { | |
338 | assert_eq!(self.domain_size, other.domain_size); | |
339 | bitwise(&mut self.words, &other.words, |a, b| a & b) | |
340 | } | |
0bf4aa26 XL |
341 | } |
342 | ||
923072b8 FG |
343 | impl<T: Idx> From<GrowableBitSet<T>> for BitSet<T> { |
344 | fn from(bit_set: GrowableBitSet<T>) -> Self { | |
345 | bit_set.bit_set | |
346 | } | |
347 | } | |
348 | ||
5e7ed085 FG |
349 | /// A fixed-size bitset type with a partially dense, partially sparse |
350 | /// representation. The bitset is broken into chunks, and chunks that are all | |
351 | /// zeros or all ones are represented and handled very efficiently. | |
352 | /// | |
353 | /// This type is especially efficient for sets that typically have a large | |
354 | /// `domain_size` with significant stretches of all zeros or all ones, and also | |
355 | /// some stretches with lots of 0s and 1s mixed in a way that causes trouble | |
356 | /// for `IntervalSet`. | |
357 | /// | |
358 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
359 | /// just be `usize`. | |
360 | /// | |
361 | /// All operations that involve an element will panic if the element is equal | |
362 | /// to or greater than the domain size. All operations that involve two bitsets | |
363 | /// will panic if the bitsets have differing domain sizes. | |
364 | #[derive(Debug, PartialEq, Eq)] | |
365 | pub struct ChunkedBitSet<T> { | |
366 | domain_size: usize, | |
367 | ||
368 | /// The chunks. Each one contains exactly CHUNK_BITS values, except the | |
369 | /// last one which contains 1..=CHUNK_BITS values. | |
370 | chunks: Box<[Chunk]>, | |
371 | ||
372 | marker: PhantomData<T>, | |
373 | } | |
374 | ||
375 | // Note: the chunk domain size is duplicated in each variant. This is a bit | |
376 | // inconvenient, but it allows the type size to be smaller than if we had an | |
377 | // outer struct containing a chunk domain size plus the `Chunk`, because the | |
378 | // compiler can place the chunk domain size after the tag. | |
379 | #[derive(Clone, Debug, PartialEq, Eq)] | |
380 | enum Chunk { | |
381 | /// A chunk that is all zeros; we don't represent the zeros explicitly. | |
382 | Zeros(ChunkSize), | |
383 | ||
384 | /// A chunk that is all ones; we don't represent the ones explicitly. | |
385 | Ones(ChunkSize), | |
386 | ||
387 | /// A chunk that has a mix of zeros and ones, which are represented | |
388 | /// explicitly and densely. It never has all zeros or all ones. | |
389 | /// | |
390 | /// If this is the final chunk there may be excess, unused words. This | |
391 | /// turns out to be both simpler and have better performance than | |
392 | /// allocating the minimum number of words, largely because we avoid having | |
393 | /// to store the length, which would make this type larger. These excess | |
394 | /// words are always be zero, as are any excess bits in the final in-use | |
395 | /// word. | |
396 | /// | |
397 | /// The second field is the count of 1s set in the chunk, and must satisfy | |
398 | /// `0 < count < chunk_domain_size`. | |
399 | /// | |
400 | /// The words are within an `Rc` because it's surprisingly common to | |
401 | /// duplicate an entire chunk, e.g. in `ChunkedBitSet::clone_from()`, or | |
402 | /// when a `Mixed` chunk is union'd into a `Zeros` chunk. When we do need | |
403 | /// to modify a chunk we use `Rc::make_mut`. | |
404 | Mixed(ChunkSize, ChunkSize, Rc<[Word; CHUNK_WORDS]>), | |
405 | } | |
406 | ||
407 | // This type is used a lot. Make sure it doesn't unintentionally get bigger. | |
408 | #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] | |
409 | crate::static_assert_size!(Chunk, 16); | |
410 | ||
411 | impl<T> ChunkedBitSet<T> { | |
412 | pub fn domain_size(&self) -> usize { | |
413 | self.domain_size | |
414 | } | |
415 | ||
416 | #[cfg(test)] | |
417 | fn assert_valid(&self) { | |
418 | if self.domain_size == 0 { | |
419 | assert!(self.chunks.is_empty()); | |
420 | return; | |
421 | } | |
422 | ||
423 | assert!((self.chunks.len() - 1) * CHUNK_BITS <= self.domain_size); | |
424 | assert!(self.chunks.len() * CHUNK_BITS >= self.domain_size); | |
425 | for chunk in self.chunks.iter() { | |
426 | chunk.assert_valid(); | |
427 | } | |
428 | } | |
429 | } | |
430 | ||
431 | impl<T: Idx> ChunkedBitSet<T> { | |
432 | /// Creates a new bitset with a given `domain_size` and chunk kind. | |
433 | fn new(domain_size: usize, is_empty: bool) -> Self { | |
434 | let chunks = if domain_size == 0 { | |
435 | Box::new([]) | |
436 | } else { | |
437 | // All the chunks have a chunk_domain_size of `CHUNK_BITS` except | |
438 | // the final one. | |
439 | let final_chunk_domain_size = { | |
440 | let n = domain_size % CHUNK_BITS; | |
441 | if n == 0 { CHUNK_BITS } else { n } | |
442 | }; | |
443 | let mut chunks = | |
444 | vec![Chunk::new(CHUNK_BITS, is_empty); num_chunks(domain_size)].into_boxed_slice(); | |
445 | *chunks.last_mut().unwrap() = Chunk::new(final_chunk_domain_size, is_empty); | |
446 | chunks | |
447 | }; | |
448 | ChunkedBitSet { domain_size, chunks, marker: PhantomData } | |
449 | } | |
450 | ||
451 | /// Creates a new, empty bitset with a given `domain_size`. | |
452 | #[inline] | |
453 | pub fn new_empty(domain_size: usize) -> Self { | |
454 | ChunkedBitSet::new(domain_size, /* is_empty */ true) | |
455 | } | |
456 | ||
457 | /// Creates a new, filled bitset with a given `domain_size`. | |
458 | #[inline] | |
459 | pub fn new_filled(domain_size: usize) -> Self { | |
460 | ChunkedBitSet::new(domain_size, /* is_empty */ false) | |
461 | } | |
462 | ||
463 | #[cfg(test)] | |
464 | fn chunks(&self) -> &[Chunk] { | |
465 | &self.chunks | |
466 | } | |
467 | ||
468 | /// Count the number of bits in the set. | |
469 | pub fn count(&self) -> usize { | |
470 | self.chunks.iter().map(|chunk| chunk.count()).sum() | |
471 | } | |
472 | ||
473 | /// Returns `true` if `self` contains `elem`. | |
474 | #[inline] | |
475 | pub fn contains(&self, elem: T) -> bool { | |
476 | assert!(elem.index() < self.domain_size); | |
477 | let chunk = &self.chunks[chunk_index(elem)]; | |
478 | match &chunk { | |
479 | Zeros(_) => false, | |
480 | Ones(_) => true, | |
481 | Mixed(_, _, words) => { | |
482 | let (word_index, mask) = chunk_word_index_and_mask(elem); | |
483 | (words[word_index] & mask) != 0 | |
484 | } | |
485 | } | |
486 | } | |
487 | ||
04454e1e FG |
488 | #[inline] |
489 | pub fn iter(&self) -> ChunkedBitIter<'_, T> { | |
490 | ChunkedBitIter::new(self) | |
491 | } | |
492 | ||
5e7ed085 FG |
493 | /// Insert `elem`. Returns whether the set has changed. |
494 | pub fn insert(&mut self, elem: T) -> bool { | |
495 | assert!(elem.index() < self.domain_size); | |
496 | let chunk_index = chunk_index(elem); | |
497 | let chunk = &mut self.chunks[chunk_index]; | |
498 | match *chunk { | |
499 | Zeros(chunk_domain_size) => { | |
500 | if chunk_domain_size > 1 { | |
501 | // We take some effort to avoid copying the words. | |
502 | let words = Rc::<[Word; CHUNK_WORDS]>::new_zeroed(); | |
503 | // SAFETY: `words` can safely be all zeroes. | |
504 | let mut words = unsafe { words.assume_init() }; | |
505 | let words_ref = Rc::get_mut(&mut words).unwrap(); | |
506 | ||
507 | let (word_index, mask) = chunk_word_index_and_mask(elem); | |
508 | words_ref[word_index] |= mask; | |
509 | *chunk = Mixed(chunk_domain_size, 1, words); | |
510 | } else { | |
511 | *chunk = Ones(chunk_domain_size); | |
512 | } | |
513 | true | |
514 | } | |
515 | Ones(_) => false, | |
516 | Mixed(chunk_domain_size, ref mut count, ref mut words) => { | |
517 | // We skip all the work if the bit is already set. | |
518 | let (word_index, mask) = chunk_word_index_and_mask(elem); | |
519 | if (words[word_index] & mask) == 0 { | |
520 | *count += 1; | |
521 | if *count < chunk_domain_size { | |
522 | let words = Rc::make_mut(words); | |
523 | words[word_index] |= mask; | |
524 | } else { | |
525 | *chunk = Ones(chunk_domain_size); | |
526 | } | |
527 | true | |
528 | } else { | |
529 | false | |
530 | } | |
531 | } | |
532 | } | |
533 | } | |
534 | ||
535 | /// Sets all bits to true. | |
536 | pub fn insert_all(&mut self) { | |
537 | for chunk in self.chunks.iter_mut() { | |
538 | *chunk = match *chunk { | |
539 | Zeros(chunk_domain_size) | |
540 | | Ones(chunk_domain_size) | |
541 | | Mixed(chunk_domain_size, ..) => Ones(chunk_domain_size), | |
542 | } | |
543 | } | |
544 | } | |
545 | ||
546 | /// Returns `true` if the set has changed. | |
547 | pub fn remove(&mut self, elem: T) -> bool { | |
548 | assert!(elem.index() < self.domain_size); | |
549 | let chunk_index = chunk_index(elem); | |
550 | let chunk = &mut self.chunks[chunk_index]; | |
551 | match *chunk { | |
552 | Zeros(_) => false, | |
553 | Ones(chunk_domain_size) => { | |
554 | if chunk_domain_size > 1 { | |
555 | // We take some effort to avoid copying the words. | |
556 | let words = Rc::<[Word; CHUNK_WORDS]>::new_zeroed(); | |
557 | // SAFETY: `words` can safely be all zeroes. | |
558 | let mut words = unsafe { words.assume_init() }; | |
559 | let words_ref = Rc::get_mut(&mut words).unwrap(); | |
560 | ||
561 | // Set only the bits in use. | |
562 | let num_words = num_words(chunk_domain_size as usize); | |
563 | words_ref[..num_words].fill(!0); | |
564 | clear_excess_bits_in_final_word( | |
565 | chunk_domain_size as usize, | |
566 | &mut words_ref[..num_words], | |
567 | ); | |
568 | let (word_index, mask) = chunk_word_index_and_mask(elem); | |
569 | words_ref[word_index] &= !mask; | |
570 | *chunk = Mixed(chunk_domain_size, chunk_domain_size - 1, words); | |
571 | } else { | |
572 | *chunk = Zeros(chunk_domain_size); | |
573 | } | |
574 | true | |
575 | } | |
576 | Mixed(chunk_domain_size, ref mut count, ref mut words) => { | |
577 | // We skip all the work if the bit is already clear. | |
578 | let (word_index, mask) = chunk_word_index_and_mask(elem); | |
579 | if (words[word_index] & mask) != 0 { | |
580 | *count -= 1; | |
581 | if *count > 0 { | |
582 | let words = Rc::make_mut(words); | |
583 | words[word_index] &= !mask; | |
584 | } else { | |
585 | *chunk = Zeros(chunk_domain_size); | |
586 | } | |
587 | true | |
588 | } else { | |
589 | false | |
590 | } | |
591 | } | |
592 | } | |
593 | } | |
594 | ||
595 | bit_relations_inherent_impls! {} | |
596 | } | |
597 | ||
598 | impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> { | |
599 | fn union(&mut self, other: &ChunkedBitSet<T>) -> bool { | |
600 | assert_eq!(self.domain_size, other.domain_size); | |
601 | debug_assert_eq!(self.chunks.len(), other.chunks.len()); | |
602 | ||
603 | let mut changed = false; | |
604 | for (mut self_chunk, other_chunk) in self.chunks.iter_mut().zip(other.chunks.iter()) { | |
605 | match (&mut self_chunk, &other_chunk) { | |
606 | (_, Zeros(_)) | (Ones(_), _) => {} | |
607 | (Zeros(self_chunk_domain_size), Ones(other_chunk_domain_size)) | |
608 | | (Mixed(self_chunk_domain_size, ..), Ones(other_chunk_domain_size)) | |
609 | | (Zeros(self_chunk_domain_size), Mixed(other_chunk_domain_size, ..)) => { | |
610 | // `other_chunk` fully overwrites `self_chunk` | |
611 | debug_assert_eq!(self_chunk_domain_size, other_chunk_domain_size); | |
612 | *self_chunk = other_chunk.clone(); | |
613 | changed = true; | |
614 | } | |
615 | ( | |
616 | Mixed( | |
617 | self_chunk_domain_size, | |
618 | ref mut self_chunk_count, | |
619 | ref mut self_chunk_words, | |
620 | ), | |
621 | Mixed(_other_chunk_domain_size, _other_chunk_count, other_chunk_words), | |
622 | ) => { | |
623 | // First check if the operation would change | |
624 | // `self_chunk.words`. If not, we can avoid allocating some | |
625 | // words, and this happens often enough that it's a | |
626 | // performance win. Also, we only need to operate on the | |
627 | // in-use words, hence the slicing. | |
628 | let op = |a, b| a | b; | |
629 | let num_words = num_words(*self_chunk_domain_size as usize); | |
630 | if bitwise_changes( | |
631 | &self_chunk_words[0..num_words], | |
632 | &other_chunk_words[0..num_words], | |
633 | op, | |
634 | ) { | |
635 | let self_chunk_words = Rc::make_mut(self_chunk_words); | |
636 | let has_changed = bitwise( | |
637 | &mut self_chunk_words[0..num_words], | |
638 | &other_chunk_words[0..num_words], | |
639 | op, | |
640 | ); | |
641 | debug_assert!(has_changed); | |
642 | *self_chunk_count = self_chunk_words[0..num_words] | |
643 | .iter() | |
644 | .map(|w| w.count_ones() as ChunkSize) | |
645 | .sum(); | |
646 | if *self_chunk_count == *self_chunk_domain_size { | |
647 | *self_chunk = Ones(*self_chunk_domain_size); | |
648 | } | |
649 | changed = true; | |
650 | } | |
651 | } | |
652 | } | |
653 | } | |
654 | changed | |
655 | } | |
656 | ||
657 | fn subtract(&mut self, _other: &ChunkedBitSet<T>) -> bool { | |
658 | unimplemented!("implement if/when necessary"); | |
659 | } | |
660 | ||
661 | fn intersect(&mut self, _other: &ChunkedBitSet<T>) -> bool { | |
662 | unimplemented!("implement if/when necessary"); | |
663 | } | |
664 | } | |
665 | ||
666 | impl<T: Idx> BitRelations<HybridBitSet<T>> for ChunkedBitSet<T> { | |
667 | fn union(&mut self, other: &HybridBitSet<T>) -> bool { | |
668 | // FIXME: This is slow if `other` is dense, but it hasn't been a problem | |
669 | // in practice so far. | |
670 | // If a faster implementation of this operation is required, consider | |
671 | // reopening https://github.com/rust-lang/rust/pull/94625 | |
672 | assert_eq!(self.domain_size, other.domain_size()); | |
673 | sequential_update(|elem| self.insert(elem), other.iter()) | |
674 | } | |
675 | ||
676 | fn subtract(&mut self, other: &HybridBitSet<T>) -> bool { | |
677 | // FIXME: This is slow if `other` is dense, but it hasn't been a problem | |
678 | // in practice so far. | |
679 | // If a faster implementation of this operation is required, consider | |
680 | // reopening https://github.com/rust-lang/rust/pull/94625 | |
681 | assert_eq!(self.domain_size, other.domain_size()); | |
682 | sequential_update(|elem| self.remove(elem), other.iter()) | |
683 | } | |
684 | ||
685 | fn intersect(&mut self, _other: &HybridBitSet<T>) -> bool { | |
686 | unimplemented!("implement if/when necessary"); | |
687 | } | |
688 | } | |
689 | ||
923072b8 FG |
690 | impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<T> { |
691 | fn union(&mut self, other: &ChunkedBitSet<T>) -> bool { | |
692 | sequential_update(|elem| self.insert(elem), other.iter()) | |
693 | } | |
694 | ||
695 | fn subtract(&mut self, _other: &ChunkedBitSet<T>) -> bool { | |
696 | unimplemented!("implement if/when necessary"); | |
697 | } | |
698 | ||
699 | fn intersect(&mut self, other: &ChunkedBitSet<T>) -> bool { | |
700 | assert_eq!(self.domain_size(), other.domain_size); | |
701 | let mut changed = false; | |
702 | for (i, chunk) in other.chunks.iter().enumerate() { | |
703 | let mut words = &mut self.words[i * CHUNK_WORDS..]; | |
704 | if words.len() > CHUNK_WORDS { | |
705 | words = &mut words[..CHUNK_WORDS]; | |
706 | } | |
707 | match chunk { | |
708 | Chunk::Zeros(..) => { | |
709 | for word in words { | |
710 | if *word != 0 { | |
711 | changed = true; | |
712 | *word = 0; | |
713 | } | |
714 | } | |
715 | } | |
716 | Chunk::Ones(..) => (), | |
717 | Chunk::Mixed(_, _, data) => { | |
718 | for (i, word) in words.iter_mut().enumerate() { | |
719 | let new_val = *word & data[i]; | |
720 | if new_val != *word { | |
721 | changed = true; | |
722 | *word = new_val; | |
723 | } | |
724 | } | |
725 | } | |
726 | } | |
727 | } | |
728 | changed | |
729 | } | |
730 | } | |
731 | ||
5e7ed085 FG |
732 | impl<T> Clone for ChunkedBitSet<T> { |
733 | fn clone(&self) -> Self { | |
734 | ChunkedBitSet { | |
735 | domain_size: self.domain_size, | |
736 | chunks: self.chunks.clone(), | |
737 | marker: PhantomData, | |
738 | } | |
739 | } | |
740 | ||
741 | /// WARNING: this implementation of clone_from will panic if the two | |
742 | /// bitsets have different domain sizes. This constraint is not inherent to | |
743 | /// `clone_from`, but it works with the existing call sites and allows a | |
744 | /// faster implementation, which is important because this function is hot. | |
745 | fn clone_from(&mut self, from: &Self) { | |
746 | assert_eq!(self.domain_size, from.domain_size); | |
747 | debug_assert_eq!(self.chunks.len(), from.chunks.len()); | |
748 | ||
749 | self.chunks.clone_from(&from.chunks) | |
750 | } | |
751 | } | |
752 | ||
04454e1e FG |
753 | pub struct ChunkedBitIter<'a, T: Idx> { |
754 | index: usize, | |
755 | bitset: &'a ChunkedBitSet<T>, | |
756 | } | |
757 | ||
758 | impl<'a, T: Idx> ChunkedBitIter<'a, T> { | |
759 | #[inline] | |
760 | fn new(bitset: &'a ChunkedBitSet<T>) -> ChunkedBitIter<'a, T> { | |
761 | ChunkedBitIter { index: 0, bitset } | |
762 | } | |
763 | } | |
764 | ||
765 | impl<'a, T: Idx> Iterator for ChunkedBitIter<'a, T> { | |
766 | type Item = T; | |
767 | fn next(&mut self) -> Option<T> { | |
768 | while self.index < self.bitset.domain_size() { | |
769 | let elem = T::new(self.index); | |
770 | let chunk = &self.bitset.chunks[chunk_index(elem)]; | |
771 | match &chunk { | |
772 | Zeros(chunk_domain_size) => { | |
773 | self.index += *chunk_domain_size as usize; | |
774 | } | |
775 | Ones(_chunk_domain_size) => { | |
776 | self.index += 1; | |
777 | return Some(elem); | |
778 | } | |
779 | Mixed(_chunk_domain_size, _, words) => loop { | |
780 | let elem = T::new(self.index); | |
781 | self.index += 1; | |
782 | let (word_index, mask) = chunk_word_index_and_mask(elem); | |
783 | if (words[word_index] & mask) != 0 { | |
784 | return Some(elem); | |
785 | } | |
786 | if self.index % CHUNK_BITS == 0 { | |
787 | break; | |
788 | } | |
789 | }, | |
790 | } | |
791 | } | |
792 | None | |
793 | } | |
923072b8 FG |
794 | |
795 | fn fold<B, F>(mut self, mut init: B, mut f: F) -> B | |
796 | where | |
797 | F: FnMut(B, Self::Item) -> B, | |
798 | { | |
799 | // If `next` has already been called, we may not be at the start of a chunk, so we first | |
800 | // advance the iterator to the start of the next chunk, before proceeding in chunk sized | |
801 | // steps. | |
802 | while self.index % CHUNK_BITS != 0 { | |
803 | let Some(item) = self.next() else { | |
804 | return init | |
805 | }; | |
806 | init = f(init, item); | |
807 | } | |
808 | let start_chunk = self.index / CHUNK_BITS; | |
809 | let chunks = &self.bitset.chunks[start_chunk..]; | |
810 | for (i, chunk) in chunks.iter().enumerate() { | |
811 | let base = (start_chunk + i) * CHUNK_BITS; | |
812 | match chunk { | |
813 | Chunk::Zeros(_) => (), | |
814 | Chunk::Ones(limit) => { | |
815 | for j in 0..(*limit as usize) { | |
816 | init = f(init, T::new(base + j)); | |
817 | } | |
818 | } | |
819 | Chunk::Mixed(_, _, words) => { | |
820 | init = BitIter::new(&**words).fold(init, |val, mut item: T| { | |
821 | item.increment_by(base); | |
822 | f(val, item) | |
823 | }); | |
824 | } | |
825 | } | |
826 | } | |
827 | init | |
828 | } | |
04454e1e FG |
829 | } |
830 | ||
5e7ed085 FG |
831 | impl Chunk { |
832 | #[cfg(test)] | |
833 | fn assert_valid(&self) { | |
834 | match *self { | |
835 | Zeros(chunk_domain_size) | Ones(chunk_domain_size) => { | |
836 | assert!(chunk_domain_size as usize <= CHUNK_BITS); | |
837 | } | |
838 | Mixed(chunk_domain_size, count, ref words) => { | |
839 | assert!(chunk_domain_size as usize <= CHUNK_BITS); | |
840 | assert!(0 < count && count < chunk_domain_size); | |
841 | ||
842 | // Check the number of set bits matches `count`. | |
843 | assert_eq!( | |
844 | words.iter().map(|w| w.count_ones() as ChunkSize).sum::<ChunkSize>(), | |
845 | count | |
846 | ); | |
847 | ||
848 | // Check the not-in-use words are all zeroed. | |
849 | let num_words = num_words(chunk_domain_size as usize); | |
850 | if num_words < CHUNK_WORDS { | |
851 | assert_eq!( | |
852 | words[num_words..] | |
853 | .iter() | |
854 | .map(|w| w.count_ones() as ChunkSize) | |
855 | .sum::<ChunkSize>(), | |
856 | 0 | |
857 | ); | |
858 | } | |
859 | } | |
860 | } | |
861 | } | |
862 | ||
863 | fn new(chunk_domain_size: usize, is_empty: bool) -> Self { | |
864 | debug_assert!(chunk_domain_size <= CHUNK_BITS); | |
865 | let chunk_domain_size = chunk_domain_size as ChunkSize; | |
866 | if is_empty { Zeros(chunk_domain_size) } else { Ones(chunk_domain_size) } | |
867 | } | |
868 | ||
869 | /// Count the number of 1s in the chunk. | |
870 | fn count(&self) -> usize { | |
871 | match *self { | |
872 | Zeros(_) => 0, | |
873 | Ones(chunk_domain_size) => chunk_domain_size as usize, | |
874 | Mixed(_, count, _) => count as usize, | |
875 | } | |
876 | } | |
877 | } | |
878 | ||
94222f64 XL |
879 | // Applies a function to mutate a bitset, and returns true if any |
880 | // of the applications return true | |
881 | fn sequential_update<T: Idx>( | |
882 | mut self_update: impl FnMut(T) -> bool, | |
883 | it: impl Iterator<Item = T>, | |
884 | ) -> bool { | |
923072b8 | 885 | it.fold(false, |changed, elem| self_update(elem) | changed) |
0bf4aa26 XL |
886 | } |
887 | ||
94222f64 XL |
888 | // Optimization of intersection for SparseBitSet that's generic |
889 | // over the RHS | |
890 | fn sparse_intersect<T: Idx>( | |
891 | set: &mut SparseBitSet<T>, | |
892 | other_contains: impl Fn(&T) -> bool, | |
893 | ) -> bool { | |
894 | let size = set.elems.len(); | |
895 | set.elems.retain(|elem| other_contains(elem)); | |
896 | set.elems.len() != size | |
897 | } | |
898 | ||
899 | // Optimization of dense/sparse intersection. The resulting set is | |
900 | // guaranteed to be at most the size of the sparse set, and hence can be | |
901 | // represented as a sparse set. Therefore the sparse set is copied and filtered, | |
902 | // then returned as the new set. | |
903 | fn dense_sparse_intersect<T: Idx>( | |
904 | dense: &BitSet<T>, | |
905 | sparse: &SparseBitSet<T>, | |
906 | ) -> (SparseBitSet<T>, bool) { | |
907 | let mut sparse_copy = sparse.clone(); | |
908 | sparse_intersect(&mut sparse_copy, |el| dense.contains(*el)); | |
909 | let n = sparse_copy.len(); | |
910 | (sparse_copy, n != dense.count()) | |
911 | } | |
912 | ||
913 | // hybrid REL dense | |
914 | impl<T: Idx> BitRelations<BitSet<T>> for HybridBitSet<T> { | |
915 | fn union(&mut self, other: &BitSet<T>) -> bool { | |
916 | assert_eq!(self.domain_size(), other.domain_size); | |
917 | match self { | |
918 | HybridBitSet::Sparse(sparse) => { | |
919 | // `self` is sparse and `other` is dense. To | |
920 | // merge them, we have two available strategies: | |
921 | // * Densify `self` then merge other | |
922 | // * Clone other then integrate bits from `self` | |
923 | // The second strategy requires dedicated method | |
924 | // since the usual `union` returns the wrong | |
925 | // result. In the dedicated case the computation | |
926 | // is slightly faster if the bits of the sparse | |
927 | // bitset map to only few words of the dense | |
928 | // representation, i.e. indices are near each | |
929 | // other. | |
930 | // | |
931 | // Benchmarking seems to suggest that the second | |
932 | // option is worth it. | |
933 | let mut new_dense = other.clone(); | |
934 | let changed = new_dense.reverse_union_sparse(sparse); | |
935 | *self = HybridBitSet::Dense(new_dense); | |
936 | changed | |
937 | } | |
938 | ||
939 | HybridBitSet::Dense(dense) => dense.union(other), | |
940 | } | |
941 | } | |
942 | ||
943 | fn subtract(&mut self, other: &BitSet<T>) -> bool { | |
944 | assert_eq!(self.domain_size(), other.domain_size); | |
945 | match self { | |
946 | HybridBitSet::Sparse(sparse) => { | |
947 | sequential_update(|elem| sparse.remove(elem), other.iter()) | |
948 | } | |
949 | HybridBitSet::Dense(dense) => dense.subtract(other), | |
950 | } | |
951 | } | |
952 | ||
953 | fn intersect(&mut self, other: &BitSet<T>) -> bool { | |
954 | assert_eq!(self.domain_size(), other.domain_size); | |
955 | match self { | |
956 | HybridBitSet::Sparse(sparse) => sparse_intersect(sparse, |elem| other.contains(*elem)), | |
957 | HybridBitSet::Dense(dense) => dense.intersect(other), | |
958 | } | |
0bf4aa26 XL |
959 | } |
960 | } | |
961 | ||
94222f64 XL |
962 | // dense REL hybrid |
963 | impl<T: Idx> BitRelations<HybridBitSet<T>> for BitSet<T> { | |
964 | fn union(&mut self, other: &HybridBitSet<T>) -> bool { | |
965 | assert_eq!(self.domain_size, other.domain_size()); | |
966 | match other { | |
967 | HybridBitSet::Sparse(sparse) => { | |
968 | sequential_update(|elem| self.insert(elem), sparse.iter().cloned()) | |
969 | } | |
970 | HybridBitSet::Dense(dense) => self.union(dense), | |
971 | } | |
972 | } | |
973 | ||
974 | fn subtract(&mut self, other: &HybridBitSet<T>) -> bool { | |
975 | assert_eq!(self.domain_size, other.domain_size()); | |
976 | match other { | |
977 | HybridBitSet::Sparse(sparse) => { | |
978 | sequential_update(|elem| self.remove(elem), sparse.iter().cloned()) | |
979 | } | |
980 | HybridBitSet::Dense(dense) => self.subtract(dense), | |
981 | } | |
982 | } | |
983 | ||
984 | fn intersect(&mut self, other: &HybridBitSet<T>) -> bool { | |
985 | assert_eq!(self.domain_size, other.domain_size()); | |
986 | match other { | |
987 | HybridBitSet::Sparse(sparse) => { | |
988 | let (updated, changed) = dense_sparse_intersect(self, sparse); | |
989 | ||
990 | // We can't directly assign the SparseBitSet to the BitSet, and | |
991 | // doing `*self = updated.to_dense()` would cause a drop / reallocation. Instead, | |
992 | // the BitSet is cleared and `updated` is copied into `self`. | |
993 | self.clear(); | |
994 | for elem in updated.iter() { | |
995 | self.insert(*elem); | |
996 | } | |
997 | changed | |
998 | } | |
999 | HybridBitSet::Dense(dense) => self.intersect(dense), | |
1000 | } | |
1001 | } | |
1002 | } | |
1003 | ||
1004 | // hybrid REL hybrid | |
1005 | impl<T: Idx> BitRelations<HybridBitSet<T>> for HybridBitSet<T> { | |
1006 | fn union(&mut self, other: &HybridBitSet<T>) -> bool { | |
1007 | assert_eq!(self.domain_size(), other.domain_size()); | |
1008 | match self { | |
1009 | HybridBitSet::Sparse(_) => { | |
1010 | match other { | |
1011 | HybridBitSet::Sparse(other_sparse) => { | |
1012 | // Both sets are sparse. Add the elements in | |
1013 | // `other_sparse` to `self` one at a time. This | |
1014 | // may or may not cause `self` to be densified. | |
1015 | let mut changed = false; | |
1016 | for elem in other_sparse.iter() { | |
1017 | changed |= self.insert(*elem); | |
1018 | } | |
1019 | changed | |
1020 | } | |
1021 | ||
1022 | HybridBitSet::Dense(other_dense) => self.union(other_dense), | |
1023 | } | |
1024 | } | |
1025 | ||
1026 | HybridBitSet::Dense(self_dense) => self_dense.union(other), | |
1027 | } | |
1028 | } | |
1029 | ||
1030 | fn subtract(&mut self, other: &HybridBitSet<T>) -> bool { | |
1031 | assert_eq!(self.domain_size(), other.domain_size()); | |
1032 | match self { | |
1033 | HybridBitSet::Sparse(self_sparse) => { | |
1034 | sequential_update(|elem| self_sparse.remove(elem), other.iter()) | |
1035 | } | |
1036 | HybridBitSet::Dense(self_dense) => self_dense.subtract(other), | |
1037 | } | |
1038 | } | |
1039 | ||
1040 | fn intersect(&mut self, other: &HybridBitSet<T>) -> bool { | |
1041 | assert_eq!(self.domain_size(), other.domain_size()); | |
1042 | match self { | |
1043 | HybridBitSet::Sparse(self_sparse) => { | |
1044 | sparse_intersect(self_sparse, |elem| other.contains(*elem)) | |
1045 | } | |
1046 | HybridBitSet::Dense(self_dense) => match other { | |
1047 | HybridBitSet::Sparse(other_sparse) => { | |
1048 | let (updated, changed) = dense_sparse_intersect(self_dense, other_sparse); | |
1049 | *self = HybridBitSet::Sparse(updated); | |
1050 | changed | |
1051 | } | |
1052 | HybridBitSet::Dense(other_dense) => self_dense.intersect(other_dense), | |
1053 | }, | |
1054 | } | |
0bf4aa26 XL |
1055 | } |
1056 | } | |
1057 | ||
1b1a35ee XL |
1058 | impl<T> Clone for BitSet<T> { |
1059 | fn clone(&self) -> Self { | |
1060 | BitSet { domain_size: self.domain_size, words: self.words.clone(), marker: PhantomData } | |
1061 | } | |
1062 | ||
1063 | fn clone_from(&mut self, from: &Self) { | |
064997fb FG |
1064 | self.domain_size = from.domain_size; |
1065 | self.words.clone_from(&from.words); | |
1b1a35ee XL |
1066 | } |
1067 | } | |
1068 | ||
0bf4aa26 | 1069 | impl<T: Idx> fmt::Debug for BitSet<T> { |
9fa01778 | 1070 | fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { |
dfeec247 | 1071 | w.debug_list().entries(self.iter()).finish() |
0bf4aa26 XL |
1072 | } |
1073 | } | |
1074 | ||
1075 | impl<T: Idx> ToString for BitSet<T> { | |
1076 | fn to_string(&self) -> String { | |
1077 | let mut result = String::new(); | |
1078 | let mut sep = '['; | |
1079 | ||
1080 | // Note: this is a little endian printout of bytes. | |
1081 | ||
1082 | // i tracks how many bits we have printed so far. | |
1083 | let mut i = 0; | |
1084 | for word in &self.words { | |
1085 | let mut word = *word; | |
dfeec247 XL |
1086 | for _ in 0..WORD_BYTES { |
1087 | // for each byte in `word`: | |
0bf4aa26 XL |
1088 | let remain = self.domain_size - i; |
1089 | // If less than a byte remains, then mask just that many bits. | |
1090 | let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF }; | |
1091 | assert!(mask <= 0xFF); | |
1092 | let byte = word & mask; | |
1093 | ||
9c376795 | 1094 | result.push_str(&format!("{sep}{byte:02x}")); |
0bf4aa26 | 1095 | |
dfeec247 XL |
1096 | if remain <= 8 { |
1097 | break; | |
1098 | } | |
0bf4aa26 XL |
1099 | word >>= 8; |
1100 | i += 8; | |
1101 | sep = '-'; | |
1102 | } | |
1103 | sep = '|'; | |
1104 | } | |
1105 | result.push(']'); | |
1106 | ||
1107 | result | |
1108 | } | |
1109 | } | |
1110 | ||
1111 | pub struct BitIter<'a, T: Idx> { | |
e74abb32 XL |
1112 | /// A copy of the current word, but with any already-visited bits cleared. |
1113 | /// (This lets us use `trailing_zeros()` to find the next set bit.) When it | |
1114 | /// is reduced to 0, we move onto the next word. | |
1115 | word: Word, | |
1116 | ||
1117 | /// The offset (measured in bits) of the current word. | |
1118 | offset: usize, | |
1119 | ||
1120 | /// Underlying iterator over the words. | |
1121 | iter: slice::Iter<'a, Word>, | |
1122 | ||
dfeec247 | 1123 | marker: PhantomData<T>, |
0bf4aa26 XL |
1124 | } |
1125 | ||
e74abb32 XL |
1126 | impl<'a, T: Idx> BitIter<'a, T> { |
1127 | #[inline] | |
1128 | fn new(words: &'a [Word]) -> BitIter<'a, T> { | |
1129 | // We initialize `word` and `offset` to degenerate values. On the first | |
1130 | // call to `next()` we will fall through to getting the first word from | |
1131 | // `iter`, which sets `word` to the first word (if there is one) and | |
1132 | // `offset` to 0. Doing it this way saves us from having to maintain | |
1133 | // additional state about whether we have started. | |
1134 | BitIter { | |
1135 | word: 0, | |
ba9703b0 | 1136 | offset: usize::MAX - (WORD_BITS - 1), |
e74abb32 XL |
1137 | iter: words.iter(), |
1138 | marker: PhantomData, | |
1139 | } | |
1140 | } | |
1141 | } | |
1142 | ||
0bf4aa26 XL |
1143 | impl<'a, T: Idx> Iterator for BitIter<'a, T> { |
1144 | type Item = T; | |
1145 | fn next(&mut self) -> Option<T> { | |
1146 | loop { | |
e74abb32 XL |
1147 | if self.word != 0 { |
1148 | // Get the position of the next set bit in the current word, | |
1149 | // then clear the bit. | |
1150 | let bit_pos = self.word.trailing_zeros() as usize; | |
1151 | let bit = 1 << bit_pos; | |
1152 | self.word ^= bit; | |
dfeec247 | 1153 | return Some(T::new(bit_pos + self.offset)); |
0bf4aa26 XL |
1154 | } |
1155 | ||
e74abb32 XL |
1156 | // Move onto the next word. `wrapping_add()` is needed to handle |
1157 | // the degenerate initial value given to `offset` in `new()`. | |
1158 | let word = self.iter.next()?; | |
1159 | self.word = *word; | |
1160 | self.offset = self.offset.wrapping_add(WORD_BITS); | |
0bf4aa26 XL |
1161 | } |
1162 | } | |
1163 | } | |
1164 | ||
0bf4aa26 XL |
1165 | #[inline] |
1166 | fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool | |
dfeec247 XL |
1167 | where |
1168 | Op: Fn(Word, Word) -> Word, | |
0bf4aa26 XL |
1169 | { |
1170 | assert_eq!(out_vec.len(), in_vec.len()); | |
17df50a5 | 1171 | let mut changed = 0; |
cdc7bbd5 | 1172 | for (out_elem, in_elem) in iter::zip(out_vec, in_vec) { |
0bf4aa26 XL |
1173 | let old_val = *out_elem; |
1174 | let new_val = op(old_val, *in_elem); | |
1175 | *out_elem = new_val; | |
17df50a5 XL |
1176 | // This is essentially equivalent to a != with changed being a bool, but |
1177 | // in practice this code gets auto-vectorized by the compiler for most | |
1178 | // operators. Using != here causes us to generate quite poor code as the | |
1179 | // compiler tries to go back to a boolean on each loop iteration. | |
1180 | changed |= old_val ^ new_val; | |
0bf4aa26 | 1181 | } |
17df50a5 | 1182 | changed != 0 |
0bf4aa26 XL |
1183 | } |
1184 | ||
5e7ed085 FG |
1185 | /// Does this bitwise operation change `out_vec`? |
1186 | #[inline] | |
1187 | fn bitwise_changes<Op>(out_vec: &[Word], in_vec: &[Word], op: Op) -> bool | |
1188 | where | |
1189 | Op: Fn(Word, Word) -> Word, | |
1190 | { | |
1191 | assert_eq!(out_vec.len(), in_vec.len()); | |
1192 | for (out_elem, in_elem) in iter::zip(out_vec, in_vec) { | |
1193 | let old_val = *out_elem; | |
1194 | let new_val = op(old_val, *in_elem); | |
1195 | if old_val != new_val { | |
1196 | return true; | |
1197 | } | |
1198 | } | |
1199 | false | |
1200 | } | |
1201 | ||
0bf4aa26 XL |
1202 | const SPARSE_MAX: usize = 8; |
1203 | ||
1204 | /// A fixed-size bitset type with a sparse representation and a maximum of | |
3dfed10e XL |
1205 | /// `SPARSE_MAX` elements. The elements are stored as a sorted `ArrayVec` with |
1206 | /// no duplicates. | |
0bf4aa26 XL |
1207 | /// |
1208 | /// This type is used by `HybridBitSet`; do not use directly. | |
1209 | #[derive(Clone, Debug)] | |
1b1a35ee | 1210 | pub struct SparseBitSet<T> { |
0bf4aa26 | 1211 | domain_size: usize, |
cdc7bbd5 | 1212 | elems: ArrayVec<T, SPARSE_MAX>, |
0bf4aa26 XL |
1213 | } |
1214 | ||
1215 | impl<T: Idx> SparseBitSet<T> { | |
1216 | fn new_empty(domain_size: usize) -> Self { | |
3dfed10e | 1217 | SparseBitSet { domain_size, elems: ArrayVec::new() } |
0bf4aa26 XL |
1218 | } |
1219 | ||
1220 | fn len(&self) -> usize { | |
1221 | self.elems.len() | |
1222 | } | |
1223 | ||
1224 | fn is_empty(&self) -> bool { | |
1225 | self.elems.len() == 0 | |
1226 | } | |
1227 | ||
1228 | fn contains(&self, elem: T) -> bool { | |
1229 | assert!(elem.index() < self.domain_size); | |
1230 | self.elems.contains(&elem) | |
1231 | } | |
1232 | ||
1233 | fn insert(&mut self, elem: T) -> bool { | |
1234 | assert!(elem.index() < self.domain_size); | |
a2a8927a | 1235 | let changed = if let Some(i) = self.elems.iter().position(|&e| e.index() >= elem.index()) { |
0bf4aa26 XL |
1236 | if self.elems[i] == elem { |
1237 | // `elem` is already in the set. | |
1238 | false | |
1239 | } else { | |
1240 | // `elem` is smaller than one or more existing elements. | |
1241 | self.elems.insert(i, elem); | |
1242 | true | |
1243 | } | |
1244 | } else { | |
1245 | // `elem` is larger than all existing elements. | |
1246 | self.elems.push(elem); | |
1247 | true | |
1248 | }; | |
1249 | assert!(self.len() <= SPARSE_MAX); | |
1250 | changed | |
1251 | } | |
1252 | ||
1253 | fn remove(&mut self, elem: T) -> bool { | |
1254 | assert!(elem.index() < self.domain_size); | |
1255 | if let Some(i) = self.elems.iter().position(|&e| e == elem) { | |
1256 | self.elems.remove(i); | |
1257 | true | |
1258 | } else { | |
1259 | false | |
1260 | } | |
1261 | } | |
1262 | ||
1263 | fn to_dense(&self) -> BitSet<T> { | |
1264 | let mut dense = BitSet::new_empty(self.domain_size); | |
1265 | for elem in self.elems.iter() { | |
1266 | dense.insert(*elem); | |
1267 | } | |
1268 | dense | |
1269 | } | |
1270 | ||
9fa01778 | 1271 | fn iter(&self) -> slice::Iter<'_, T> { |
0bf4aa26 XL |
1272 | self.elems.iter() |
1273 | } | |
0bf4aa26 | 1274 | |
a2a8927a XL |
1275 | bit_relations_inherent_impls! {} |
1276 | } | |
1277 | ||
1278 | impl<T: Idx + Ord> SparseBitSet<T> { | |
3c0e092e XL |
1279 | fn last_set_in(&self, range: impl RangeBounds<T>) -> Option<T> { |
1280 | let mut last_leq = None; | |
1281 | for e in self.iter() { | |
1282 | if range.contains(e) { | |
1283 | last_leq = Some(*e); | |
1284 | } | |
1285 | } | |
1286 | last_leq | |
1287 | } | |
0bf4aa26 XL |
1288 | } |
1289 | ||
1290 | /// A fixed-size bitset type with a hybrid representation: sparse when there | |
1291 | /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more | |
1292 | /// than `SPARSE_MAX`. | |
1293 | /// | |
1294 | /// This type is especially efficient for sets that typically have a small | |
1295 | /// number of elements, but a large `domain_size`, and are cleared frequently. | |
1296 | /// | |
1297 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
1298 | /// just be `usize`. | |
1299 | /// | |
1300 | /// All operations that involve an element will panic if the element is equal | |
1301 | /// to or greater than the domain size. All operations that involve two bitsets | |
1302 | /// will panic if the bitsets have differing domain sizes. | |
1b1a35ee XL |
1303 | #[derive(Clone)] |
1304 | pub enum HybridBitSet<T> { | |
0bf4aa26 XL |
1305 | Sparse(SparseBitSet<T>), |
1306 | Dense(BitSet<T>), | |
1307 | } | |
1308 | ||
1b1a35ee XL |
1309 | impl<T: Idx> fmt::Debug for HybridBitSet<T> { |
1310 | fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1311 | match self { | |
1312 | Self::Sparse(b) => b.fmt(w), | |
1313 | Self::Dense(b) => b.fmt(w), | |
1314 | } | |
1315 | } | |
1316 | } | |
1317 | ||
0bf4aa26 XL |
1318 | impl<T: Idx> HybridBitSet<T> { |
1319 | pub fn new_empty(domain_size: usize) -> Self { | |
1320 | HybridBitSet::Sparse(SparseBitSet::new_empty(domain_size)) | |
1321 | } | |
1322 | ||
1b1a35ee | 1323 | pub fn domain_size(&self) -> usize { |
0bf4aa26 XL |
1324 | match self { |
1325 | HybridBitSet::Sparse(sparse) => sparse.domain_size, | |
1326 | HybridBitSet::Dense(dense) => dense.domain_size, | |
1327 | } | |
1328 | } | |
1329 | ||
1330 | pub fn clear(&mut self) { | |
1331 | let domain_size = self.domain_size(); | |
1332 | *self = HybridBitSet::new_empty(domain_size); | |
1333 | } | |
1334 | ||
1335 | pub fn contains(&self, elem: T) -> bool { | |
1336 | match self { | |
1337 | HybridBitSet::Sparse(sparse) => sparse.contains(elem), | |
1338 | HybridBitSet::Dense(dense) => dense.contains(elem), | |
1339 | } | |
1340 | } | |
1341 | ||
1342 | pub fn superset(&self, other: &HybridBitSet<T>) -> bool { | |
1343 | match (self, other) { | |
1344 | (HybridBitSet::Dense(self_dense), HybridBitSet::Dense(other_dense)) => { | |
1345 | self_dense.superset(other_dense) | |
1346 | } | |
1347 | _ => { | |
1348 | assert!(self.domain_size() == other.domain_size()); | |
1349 | other.iter().all(|elem| self.contains(elem)) | |
1350 | } | |
1351 | } | |
1352 | } | |
1353 | ||
1354 | pub fn is_empty(&self) -> bool { | |
1355 | match self { | |
1356 | HybridBitSet::Sparse(sparse) => sparse.is_empty(), | |
1357 | HybridBitSet::Dense(dense) => dense.is_empty(), | |
1358 | } | |
1359 | } | |
1360 | ||
3c0e092e XL |
1361 | /// Returns the previous element present in the bitset from `elem`, |
1362 | /// inclusively of elem. That is, will return `Some(elem)` if elem is in the | |
1363 | /// bitset. | |
a2a8927a XL |
1364 | pub fn last_set_in(&self, range: impl RangeBounds<T>) -> Option<T> |
1365 | where | |
1366 | T: Ord, | |
1367 | { | |
3c0e092e XL |
1368 | match self { |
1369 | HybridBitSet::Sparse(sparse) => sparse.last_set_in(range), | |
1370 | HybridBitSet::Dense(dense) => dense.last_set_in(range), | |
1371 | } | |
1372 | } | |
1373 | ||
0bf4aa26 XL |
1374 | pub fn insert(&mut self, elem: T) -> bool { |
1375 | // No need to check `elem` against `self.domain_size` here because all | |
1376 | // the match cases check it, one way or another. | |
1377 | match self { | |
1378 | HybridBitSet::Sparse(sparse) if sparse.len() < SPARSE_MAX => { | |
1379 | // The set is sparse and has space for `elem`. | |
1380 | sparse.insert(elem) | |
1381 | } | |
1382 | HybridBitSet::Sparse(sparse) if sparse.contains(elem) => { | |
1383 | // The set is sparse and does not have space for `elem`, but | |
1384 | // that doesn't matter because `elem` is already present. | |
1385 | false | |
1386 | } | |
1387 | HybridBitSet::Sparse(sparse) => { | |
1388 | // The set is sparse and full. Convert to a dense set. | |
1389 | let mut dense = sparse.to_dense(); | |
1390 | let changed = dense.insert(elem); | |
1391 | assert!(changed); | |
1392 | *self = HybridBitSet::Dense(dense); | |
1393 | changed | |
1394 | } | |
1395 | HybridBitSet::Dense(dense) => dense.insert(elem), | |
1396 | } | |
1397 | } | |
1398 | ||
3c0e092e XL |
1399 | pub fn insert_range(&mut self, elems: impl RangeBounds<T>) { |
1400 | // No need to check `elem` against `self.domain_size` here because all | |
1401 | // the match cases check it, one way or another. | |
1402 | let start = match elems.start_bound().cloned() { | |
1403 | Bound::Included(start) => start.index(), | |
1404 | Bound::Excluded(start) => start.index() + 1, | |
1405 | Bound::Unbounded => 0, | |
1406 | }; | |
1407 | let end = match elems.end_bound().cloned() { | |
1408 | Bound::Included(end) => end.index() + 1, | |
1409 | Bound::Excluded(end) => end.index(), | |
1410 | Bound::Unbounded => self.domain_size() - 1, | |
1411 | }; | |
5099ac24 | 1412 | let Some(len) = end.checked_sub(start) else { return }; |
3c0e092e XL |
1413 | match self { |
1414 | HybridBitSet::Sparse(sparse) if sparse.len() + len < SPARSE_MAX => { | |
1415 | // The set is sparse and has space for `elems`. | |
1416 | for elem in start..end { | |
1417 | sparse.insert(T::new(elem)); | |
1418 | } | |
1419 | } | |
1420 | HybridBitSet::Sparse(sparse) => { | |
1421 | // The set is sparse and full. Convert to a dense set. | |
1422 | let mut dense = sparse.to_dense(); | |
1423 | dense.insert_range(elems); | |
1424 | *self = HybridBitSet::Dense(dense); | |
1425 | } | |
1426 | HybridBitSet::Dense(dense) => dense.insert_range(elems), | |
1427 | } | |
1428 | } | |
1429 | ||
0bf4aa26 XL |
1430 | pub fn insert_all(&mut self) { |
1431 | let domain_size = self.domain_size(); | |
1432 | match self { | |
1433 | HybridBitSet::Sparse(_) => { | |
1434 | *self = HybridBitSet::Dense(BitSet::new_filled(domain_size)); | |
1435 | } | |
1436 | HybridBitSet::Dense(dense) => dense.insert_all(), | |
1437 | } | |
1438 | } | |
1439 | ||
1440 | pub fn remove(&mut self, elem: T) -> bool { | |
1441 | // Note: we currently don't bother going from Dense back to Sparse. | |
1442 | match self { | |
1443 | HybridBitSet::Sparse(sparse) => sparse.remove(elem), | |
1444 | HybridBitSet::Dense(dense) => dense.remove(elem), | |
1445 | } | |
1446 | } | |
1447 | ||
0bf4aa26 XL |
1448 | /// Converts to a dense set, consuming itself in the process. |
1449 | pub fn to_dense(self) -> BitSet<T> { | |
1450 | match self { | |
1451 | HybridBitSet::Sparse(sparse) => sparse.to_dense(), | |
1452 | HybridBitSet::Dense(dense) => dense, | |
1453 | } | |
1454 | } | |
1455 | ||
9fa01778 | 1456 | pub fn iter(&self) -> HybridIter<'_, T> { |
0bf4aa26 XL |
1457 | match self { |
1458 | HybridBitSet::Sparse(sparse) => HybridIter::Sparse(sparse.iter()), | |
1459 | HybridBitSet::Dense(dense) => HybridIter::Dense(dense.iter()), | |
1460 | } | |
1461 | } | |
0bf4aa26 | 1462 | |
94222f64 | 1463 | bit_relations_inherent_impls! {} |
0bf4aa26 XL |
1464 | } |
1465 | ||
1466 | pub enum HybridIter<'a, T: Idx> { | |
1467 | Sparse(slice::Iter<'a, T>), | |
1468 | Dense(BitIter<'a, T>), | |
1469 | } | |
1470 | ||
1471 | impl<'a, T: Idx> Iterator for HybridIter<'a, T> { | |
1472 | type Item = T; | |
1473 | ||
1474 | fn next(&mut self) -> Option<T> { | |
1475 | match self { | |
e74abb32 | 1476 | HybridIter::Sparse(sparse) => sparse.next().copied(), |
0bf4aa26 XL |
1477 | HybridIter::Dense(dense) => dense.next(), |
1478 | } | |
1479 | } | |
1480 | } | |
1481 | ||
1482 | /// A resizable bitset type with a dense representation. | |
1483 | /// | |
1484 | /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also | |
1485 | /// just be `usize`. | |
1486 | /// | |
1487 | /// All operations that involve an element will panic if the element is equal | |
1488 | /// to or greater than the domain size. | |
1489 | #[derive(Clone, Debug, PartialEq)] | |
1490 | pub struct GrowableBitSet<T: Idx> { | |
1491 | bit_set: BitSet<T>, | |
1492 | } | |
1493 | ||
5099ac24 FG |
1494 | impl<T: Idx> Default for GrowableBitSet<T> { |
1495 | fn default() -> Self { | |
1496 | GrowableBitSet::new_empty() | |
1497 | } | |
1498 | } | |
1499 | ||
0bf4aa26 XL |
1500 | impl<T: Idx> GrowableBitSet<T> { |
1501 | /// Ensure that the set can hold at least `min_domain_size` elements. | |
1502 | pub fn ensure(&mut self, min_domain_size: usize) { | |
1503 | if self.bit_set.domain_size < min_domain_size { | |
1504 | self.bit_set.domain_size = min_domain_size; | |
1505 | } | |
1506 | ||
1507 | let min_num_words = num_words(min_domain_size); | |
1508 | if self.bit_set.words.len() < min_num_words { | |
1509 | self.bit_set.words.resize(min_num_words, 0) | |
1510 | } | |
1511 | } | |
1512 | ||
1513 | pub fn new_empty() -> GrowableBitSet<T> { | |
1514 | GrowableBitSet { bit_set: BitSet::new_empty(0) } | |
1515 | } | |
1516 | ||
48663c56 XL |
1517 | pub fn with_capacity(capacity: usize) -> GrowableBitSet<T> { |
1518 | GrowableBitSet { bit_set: BitSet::new_empty(capacity) } | |
0bf4aa26 XL |
1519 | } |
1520 | ||
9fa01778 | 1521 | /// Returns `true` if the set has changed. |
0bf4aa26 XL |
1522 | #[inline] |
1523 | pub fn insert(&mut self, elem: T) -> bool { | |
1524 | self.ensure(elem.index() + 1); | |
1525 | self.bit_set.insert(elem) | |
1526 | } | |
1527 | ||
5869c6ff XL |
1528 | /// Returns `true` if the set has changed. |
1529 | #[inline] | |
1530 | pub fn remove(&mut self, elem: T) -> bool { | |
1531 | self.ensure(elem.index() + 1); | |
1532 | self.bit_set.remove(elem) | |
1533 | } | |
1534 | ||
1535 | #[inline] | |
1536 | pub fn is_empty(&self) -> bool { | |
1537 | self.bit_set.is_empty() | |
1538 | } | |
1539 | ||
0bf4aa26 XL |
1540 | #[inline] |
1541 | pub fn contains(&self, elem: T) -> bool { | |
1542 | let (word_index, mask) = word_index_and_mask(elem); | |
c295e0f8 | 1543 | self.bit_set.words.get(word_index).map_or(false, |word| (word & mask) != 0) |
0bf4aa26 | 1544 | } |
064997fb FG |
1545 | |
1546 | #[inline] | |
1547 | pub fn iter(&self) -> BitIter<'_, T> { | |
1548 | self.bit_set.iter() | |
1549 | } | |
1550 | ||
1551 | #[inline] | |
1552 | pub fn len(&self) -> usize { | |
1553 | self.bit_set.count() | |
1554 | } | |
0bf4aa26 XL |
1555 | } |
1556 | ||
923072b8 FG |
1557 | impl<T: Idx> From<BitSet<T>> for GrowableBitSet<T> { |
1558 | fn from(bit_set: BitSet<T>) -> Self { | |
1559 | Self { bit_set } | |
1560 | } | |
1561 | } | |
1562 | ||
0bf4aa26 XL |
1563 | /// A fixed-size 2D bit matrix type with a dense representation. |
1564 | /// | |
1565 | /// `R` and `C` are index types used to identify rows and columns respectively; | |
1566 | /// typically newtyped `usize` wrappers, but they can also just be `usize`. | |
1567 | /// | |
1568 | /// All operations that involve a row and/or column index will panic if the | |
1569 | /// index exceeds the relevant bound. | |
a2a8927a | 1570 | #[derive(Clone, Eq, PartialEq, Hash, Decodable, Encodable)] |
0bf4aa26 XL |
1571 | pub struct BitMatrix<R: Idx, C: Idx> { |
1572 | num_rows: usize, | |
1573 | num_columns: usize, | |
1574 | words: Vec<Word>, | |
1575 | marker: PhantomData<(R, C)>, | |
1576 | } | |
1577 | ||
1578 | impl<R: Idx, C: Idx> BitMatrix<R, C> { | |
9fa01778 | 1579 | /// Creates a new `rows x columns` matrix, initially empty. |
0bf4aa26 XL |
1580 | pub fn new(num_rows: usize, num_columns: usize) -> BitMatrix<R, C> { |
1581 | // For every element, we need one bit for every other | |
1582 | // element. Round up to an even number of words. | |
1583 | let words_per_row = num_words(num_columns); | |
1584 | BitMatrix { | |
1585 | num_rows, | |
1586 | num_columns, | |
1587 | words: vec![0; num_rows * words_per_row], | |
1588 | marker: PhantomData, | |
1589 | } | |
1590 | } | |
1591 | ||
dc9dc135 XL |
1592 | /// Creates a new matrix, with `row` used as the value for every row. |
1593 | pub fn from_row_n(row: &BitSet<C>, num_rows: usize) -> BitMatrix<R, C> { | |
1594 | let num_columns = row.domain_size(); | |
1595 | let words_per_row = num_words(num_columns); | |
1596 | assert_eq!(words_per_row, row.words().len()); | |
1597 | BitMatrix { | |
1598 | num_rows, | |
1599 | num_columns, | |
1600 | words: iter::repeat(row.words()).take(num_rows).flatten().cloned().collect(), | |
1601 | marker: PhantomData, | |
1602 | } | |
1603 | } | |
1604 | ||
1605 | pub fn rows(&self) -> impl Iterator<Item = R> { | |
1606 | (0..self.num_rows).map(R::new) | |
1607 | } | |
1608 | ||
0bf4aa26 XL |
1609 | /// The range of bits for a given row. |
1610 | fn range(&self, row: R) -> (usize, usize) { | |
1611 | let words_per_row = num_words(self.num_columns); | |
1612 | let start = row.index() * words_per_row; | |
1613 | (start, start + words_per_row) | |
1614 | } | |
1615 | ||
1616 | /// Sets the cell at `(row, column)` to true. Put another way, insert | |
1617 | /// `column` to the bitset for `row`. | |
1618 | /// | |
9fa01778 | 1619 | /// Returns `true` if this changed the matrix. |
0bf4aa26 XL |
1620 | pub fn insert(&mut self, row: R, column: C) -> bool { |
1621 | assert!(row.index() < self.num_rows && column.index() < self.num_columns); | |
1622 | let (start, _) = self.range(row); | |
1623 | let (word_index, mask) = word_index_and_mask(column); | |
1624 | let words = &mut self.words[..]; | |
1625 | let word = words[start + word_index]; | |
1626 | let new_word = word | mask; | |
1627 | words[start + word_index] = new_word; | |
1628 | word != new_word | |
1629 | } | |
1630 | ||
1631 | /// Do the bits from `row` contain `column`? Put another way, is | |
1632 | /// the matrix cell at `(row, column)` true? Put yet another way, | |
1633 | /// if the matrix represents (transitive) reachability, can | |
1634 | /// `row` reach `column`? | |
1635 | pub fn contains(&self, row: R, column: C) -> bool { | |
1636 | assert!(row.index() < self.num_rows && column.index() < self.num_columns); | |
1637 | let (start, _) = self.range(row); | |
1638 | let (word_index, mask) = word_index_and_mask(column); | |
1639 | (self.words[start + word_index] & mask) != 0 | |
1640 | } | |
1641 | ||
9fa01778 | 1642 | /// Returns those indices that are true in rows `a` and `b`. This |
3dfed10e | 1643 | /// is an *O*(*n*) operation where *n* is the number of elements |
0bf4aa26 XL |
1644 | /// (somewhat independent from the actual size of the |
1645 | /// intersection, in particular). | |
1646 | pub fn intersect_rows(&self, row1: R, row2: R) -> Vec<C> { | |
1647 | assert!(row1.index() < self.num_rows && row2.index() < self.num_rows); | |
1648 | let (row1_start, row1_end) = self.range(row1); | |
1649 | let (row2_start, row2_end) = self.range(row2); | |
1650 | let mut result = Vec::with_capacity(self.num_columns); | |
1651 | for (base, (i, j)) in (row1_start..row1_end).zip(row2_start..row2_end).enumerate() { | |
1652 | let mut v = self.words[i] & self.words[j]; | |
1653 | for bit in 0..WORD_BITS { | |
1654 | if v == 0 { | |
1655 | break; | |
1656 | } | |
1657 | if v & 0x1 != 0 { | |
1658 | result.push(C::new(base * WORD_BITS + bit)); | |
1659 | } | |
1660 | v >>= 1; | |
1661 | } | |
1662 | } | |
1663 | result | |
1664 | } | |
1665 | ||
9fa01778 XL |
1666 | /// Adds the bits from row `read` to the bits from row `write`, and |
1667 | /// returns `true` if anything changed. | |
0bf4aa26 XL |
1668 | /// |
1669 | /// This is used when computing transitive reachability because if | |
1670 | /// you have an edge `write -> read`, because in that case | |
1671 | /// `write` can reach everything that `read` can (and | |
1672 | /// potentially more). | |
1673 | pub fn union_rows(&mut self, read: R, write: R) -> bool { | |
1674 | assert!(read.index() < self.num_rows && write.index() < self.num_rows); | |
1675 | let (read_start, read_end) = self.range(read); | |
1676 | let (write_start, write_end) = self.range(write); | |
1677 | let words = &mut self.words[..]; | |
1678 | let mut changed = false; | |
cdc7bbd5 | 1679 | for (read_index, write_index) in iter::zip(read_start..read_end, write_start..write_end) { |
0bf4aa26 XL |
1680 | let word = words[write_index]; |
1681 | let new_word = word | words[read_index]; | |
1682 | words[write_index] = new_word; | |
1683 | changed |= word != new_word; | |
1684 | } | |
1685 | changed | |
1686 | } | |
1687 | ||
dc9dc135 XL |
1688 | /// Adds the bits from `with` to the bits from row `write`, and |
1689 | /// returns `true` if anything changed. | |
1690 | pub fn union_row_with(&mut self, with: &BitSet<C>, write: R) -> bool { | |
1691 | assert!(write.index() < self.num_rows); | |
1692 | assert_eq!(with.domain_size(), self.num_columns); | |
1693 | let (write_start, write_end) = self.range(write); | |
1694 | let mut changed = false; | |
cdc7bbd5 | 1695 | for (read_index, write_index) in iter::zip(0..with.words().len(), write_start..write_end) { |
dc9dc135 XL |
1696 | let word = self.words[write_index]; |
1697 | let new_word = word | with.words()[read_index]; | |
1698 | self.words[write_index] = new_word; | |
1699 | changed |= word != new_word; | |
1700 | } | |
1701 | changed | |
1702 | } | |
1703 | ||
1704 | /// Sets every cell in `row` to true. | |
1705 | pub fn insert_all_into_row(&mut self, row: R) { | |
1706 | assert!(row.index() < self.num_rows); | |
1707 | let (start, end) = self.range(row); | |
3c0e092e XL |
1708 | let words = &mut self.words[..]; |
1709 | for index in start..end { | |
1710 | words[index] = !0; | |
dc9dc135 | 1711 | } |
5e7ed085 | 1712 | clear_excess_bits_in_final_word(self.num_columns, &mut self.words[..end]); |
dc9dc135 XL |
1713 | } |
1714 | ||
1715 | /// Gets a slice of the underlying words. | |
1716 | pub fn words(&self) -> &[Word] { | |
1717 | &self.words | |
1718 | } | |
1719 | ||
0bf4aa26 XL |
1720 | /// Iterates through all the columns set to true in a given row of |
1721 | /// the matrix. | |
416331ca | 1722 | pub fn iter(&self, row: R) -> BitIter<'_, C> { |
0bf4aa26 XL |
1723 | assert!(row.index() < self.num_rows); |
1724 | let (start, end) = self.range(row); | |
e74abb32 | 1725 | BitIter::new(&self.words[start..end]) |
0bf4aa26 | 1726 | } |
dc9dc135 XL |
1727 | |
1728 | /// Returns the number of elements in `row`. | |
1729 | pub fn count(&self, row: R) -> usize { | |
1730 | let (start, end) = self.range(row); | |
1731 | self.words[start..end].iter().map(|e| e.count_ones() as usize).sum() | |
1732 | } | |
0bf4aa26 XL |
1733 | } |
1734 | ||
f035d41b XL |
1735 | impl<R: Idx, C: Idx> fmt::Debug for BitMatrix<R, C> { |
1736 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1737 | /// Forces its contents to print in regular mode instead of alternate mode. | |
1738 | struct OneLinePrinter<T>(T); | |
1739 | impl<T: fmt::Debug> fmt::Debug for OneLinePrinter<T> { | |
1740 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1741 | write!(fmt, "{:?}", self.0) | |
1742 | } | |
1743 | } | |
1744 | ||
1745 | write!(fmt, "BitMatrix({}x{}) ", self.num_rows, self.num_columns)?; | |
1746 | let items = self.rows().flat_map(|r| self.iter(r).map(move |c| (r, c))); | |
1747 | fmt.debug_set().entries(items.map(OneLinePrinter)).finish() | |
1748 | } | |
1749 | } | |
1750 | ||
0bf4aa26 XL |
1751 | /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately |
1752 | /// sparse representation. | |
1753 | /// | |
1754 | /// Initially, every row has no explicit representation. If any bit within a | |
1755 | /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`. | |
1756 | /// Furthermore, any previously uninstantiated rows prior to it will be | |
1757 | /// instantiated as `None`. Those prior rows may themselves become fully | |
1758 | /// instantiated later on if any of their bits are set. | |
1759 | /// | |
1760 | /// `R` and `C` are index types used to identify rows and columns respectively; | |
1761 | /// typically newtyped `usize` wrappers, but they can also just be `usize`. | |
1762 | #[derive(Clone, Debug)] | |
1763 | pub struct SparseBitMatrix<R, C> | |
1764 | where | |
1765 | R: Idx, | |
1766 | C: Idx, | |
1767 | { | |
1768 | num_columns: usize, | |
1769 | rows: IndexVec<R, Option<HybridBitSet<C>>>, | |
1770 | } | |
1771 | ||
1772 | impl<R: Idx, C: Idx> SparseBitMatrix<R, C> { | |
9fa01778 | 1773 | /// Creates a new empty sparse bit matrix with no rows or columns. |
0bf4aa26 | 1774 | pub fn new(num_columns: usize) -> Self { |
dfeec247 | 1775 | Self { num_columns, rows: IndexVec::new() } |
0bf4aa26 XL |
1776 | } |
1777 | ||
1778 | fn ensure_row(&mut self, row: R) -> &mut HybridBitSet<C> { | |
c295e0f8 | 1779 | // Instantiate any missing rows up to and including row `row` with an empty HybridBitSet. |
0bf4aa26 | 1780 | // Then replace row `row` with a full HybridBitSet if necessary. |
c295e0f8 | 1781 | self.rows.get_or_insert_with(row, || HybridBitSet::new_empty(self.num_columns)) |
0bf4aa26 XL |
1782 | } |
1783 | ||
1784 | /// Sets the cell at `(row, column)` to true. Put another way, insert | |
1785 | /// `column` to the bitset for `row`. | |
1786 | /// | |
9fa01778 | 1787 | /// Returns `true` if this changed the matrix. |
0bf4aa26 XL |
1788 | pub fn insert(&mut self, row: R, column: C) -> bool { |
1789 | self.ensure_row(row).insert(column) | |
1790 | } | |
1791 | ||
94222f64 XL |
1792 | /// Sets the cell at `(row, column)` to false. Put another way, delete |
1793 | /// `column` from the bitset for `row`. Has no effect if `row` does not | |
1794 | /// exist. | |
1795 | /// | |
1796 | /// Returns `true` if this changed the matrix. | |
1797 | pub fn remove(&mut self, row: R, column: C) -> bool { | |
1798 | match self.rows.get_mut(row) { | |
1799 | Some(Some(row)) => row.remove(column), | |
1800 | _ => false, | |
1801 | } | |
1802 | } | |
1803 | ||
1804 | /// Sets all columns at `row` to false. Has no effect if `row` does | |
1805 | /// not exist. | |
1806 | pub fn clear(&mut self, row: R) { | |
1807 | if let Some(Some(row)) = self.rows.get_mut(row) { | |
1808 | row.clear(); | |
1809 | } | |
1810 | } | |
1811 | ||
0bf4aa26 XL |
1812 | /// Do the bits from `row` contain `column`? Put another way, is |
1813 | /// the matrix cell at `(row, column)` true? Put yet another way, | |
1814 | /// if the matrix represents (transitive) reachability, can | |
1815 | /// `row` reach `column`? | |
1816 | pub fn contains(&self, row: R, column: C) -> bool { | |
1817 | self.row(row).map_or(false, |r| r.contains(column)) | |
1818 | } | |
1819 | ||
9fa01778 XL |
1820 | /// Adds the bits from row `read` to the bits from row `write`, and |
1821 | /// returns `true` if anything changed. | |
0bf4aa26 XL |
1822 | /// |
1823 | /// This is used when computing transitive reachability because if | |
1824 | /// you have an edge `write -> read`, because in that case | |
1825 | /// `write` can reach everything that `read` can (and | |
1826 | /// potentially more). | |
1827 | pub fn union_rows(&mut self, read: R, write: R) -> bool { | |
1828 | if read == write || self.row(read).is_none() { | |
1829 | return false; | |
1830 | } | |
1831 | ||
1832 | self.ensure_row(write); | |
1833 | if let (Some(read_row), Some(write_row)) = self.rows.pick2_mut(read, write) { | |
1834 | write_row.union(read_row) | |
1835 | } else { | |
1836 | unreachable!() | |
1837 | } | |
1838 | } | |
1839 | ||
0bf4aa26 XL |
1840 | /// Insert all bits in the given row. |
1841 | pub fn insert_all_into_row(&mut self, row: R) { | |
1842 | self.ensure_row(row).insert_all(); | |
1843 | } | |
1844 | ||
1845 | pub fn rows(&self) -> impl Iterator<Item = R> { | |
1846 | self.rows.indices() | |
1847 | } | |
1848 | ||
1849 | /// Iterates through all the columns set to true in a given row of | |
1850 | /// the matrix. | |
3c0e092e | 1851 | pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a { |
0bf4aa26 XL |
1852 | self.row(row).into_iter().flat_map(|r| r.iter()) |
1853 | } | |
1854 | ||
1855 | pub fn row(&self, row: R) -> Option<&HybridBitSet<C>> { | |
04454e1e | 1856 | self.rows.get(row)?.as_ref() |
0bf4aa26 | 1857 | } |
94222f64 | 1858 | |
5e7ed085 | 1859 | /// Intersects `row` with `set`. `set` can be either `BitSet` or |
94222f64 XL |
1860 | /// `HybridBitSet`. Has no effect if `row` does not exist. |
1861 | /// | |
1862 | /// Returns true if the row was changed. | |
1863 | pub fn intersect_row<Set>(&mut self, row: R, set: &Set) -> bool | |
1864 | where | |
1865 | HybridBitSet<C>: BitRelations<Set>, | |
1866 | { | |
1867 | match self.rows.get_mut(row) { | |
1868 | Some(Some(row)) => row.intersect(set), | |
1869 | _ => false, | |
1870 | } | |
1871 | } | |
1872 | ||
9ffffee4 | 1873 | /// Subtracts `set` from `row`. `set` can be either `BitSet` or |
94222f64 XL |
1874 | /// `HybridBitSet`. Has no effect if `row` does not exist. |
1875 | /// | |
1876 | /// Returns true if the row was changed. | |
1877 | pub fn subtract_row<Set>(&mut self, row: R, set: &Set) -> bool | |
1878 | where | |
1879 | HybridBitSet<C>: BitRelations<Set>, | |
1880 | { | |
1881 | match self.rows.get_mut(row) { | |
1882 | Some(Some(row)) => row.subtract(set), | |
1883 | _ => false, | |
1884 | } | |
1885 | } | |
1886 | ||
1887 | /// Unions `row` with `set`. `set` can be either `BitSet` or | |
1888 | /// `HybridBitSet`. | |
1889 | /// | |
1890 | /// Returns true if the row was changed. | |
1891 | pub fn union_row<Set>(&mut self, row: R, set: &Set) -> bool | |
1892 | where | |
1893 | HybridBitSet<C>: BitRelations<Set>, | |
1894 | { | |
1895 | self.ensure_row(row).union(set) | |
1896 | } | |
0bf4aa26 XL |
1897 | } |
1898 | ||
1899 | #[inline] | |
1900 | fn num_words<T: Idx>(domain_size: T) -> usize { | |
1901 | (domain_size.index() + WORD_BITS - 1) / WORD_BITS | |
1902 | } | |
1903 | ||
5e7ed085 FG |
1904 | #[inline] |
1905 | fn num_chunks<T: Idx>(domain_size: T) -> usize { | |
1906 | assert!(domain_size.index() > 0); | |
1907 | (domain_size.index() + CHUNK_BITS - 1) / CHUNK_BITS | |
1908 | } | |
1909 | ||
0bf4aa26 XL |
1910 | #[inline] |
1911 | fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) { | |
1912 | let elem = elem.index(); | |
1913 | let word_index = elem / WORD_BITS; | |
1914 | let mask = 1 << (elem % WORD_BITS); | |
1915 | (word_index, mask) | |
1916 | } | |
3dfed10e | 1917 | |
5e7ed085 FG |
1918 | #[inline] |
1919 | fn chunk_index<T: Idx>(elem: T) -> usize { | |
1920 | elem.index() / CHUNK_BITS | |
1921 | } | |
1922 | ||
1923 | #[inline] | |
1924 | fn chunk_word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) { | |
1925 | let chunk_elem = elem.index() % CHUNK_BITS; | |
1926 | word_index_and_mask(chunk_elem) | |
1927 | } | |
1928 | ||
1929 | fn clear_excess_bits_in_final_word(domain_size: usize, words: &mut [Word]) { | |
1930 | let num_bits_in_final_word = domain_size % WORD_BITS; | |
1931 | if num_bits_in_final_word > 0 { | |
1932 | let mask = (1 << num_bits_in_final_word) - 1; | |
1933 | words[words.len() - 1] &= mask; | |
1934 | } | |
1935 | } | |
1936 | ||
3c0e092e XL |
1937 | #[inline] |
1938 | fn max_bit(word: Word) -> usize { | |
1939 | WORD_BITS - 1 - word.leading_zeros() as usize | |
1940 | } | |
1941 | ||
3dfed10e XL |
1942 | /// Integral type used to represent the bit set. |
1943 | pub trait FiniteBitSetTy: | |
1944 | BitAnd<Output = Self> | |
1945 | + BitAndAssign | |
1946 | + BitOrAssign | |
1947 | + Clone | |
1948 | + Copy | |
1949 | + Shl | |
1950 | + Not<Output = Self> | |
1951 | + PartialEq | |
1952 | + Sized | |
1953 | { | |
1954 | /// Size of the domain representable by this type, e.g. 64 for `u64`. | |
1955 | const DOMAIN_SIZE: u32; | |
1956 | ||
1957 | /// Value which represents the `FiniteBitSet` having every bit set. | |
1958 | const FILLED: Self; | |
1959 | /// Value which represents the `FiniteBitSet` having no bits set. | |
1960 | const EMPTY: Self; | |
1961 | ||
1962 | /// Value for one as the integral type. | |
1963 | const ONE: Self; | |
1964 | /// Value for zero as the integral type. | |
1965 | const ZERO: Self; | |
1966 | ||
1967 | /// Perform a checked left shift on the integral type. | |
1968 | fn checked_shl(self, rhs: u32) -> Option<Self>; | |
1969 | /// Perform a checked right shift on the integral type. | |
1970 | fn checked_shr(self, rhs: u32) -> Option<Self>; | |
1971 | } | |
1972 | ||
1973 | impl FiniteBitSetTy for u32 { | |
1974 | const DOMAIN_SIZE: u32 = 32; | |
1975 | ||
1976 | const FILLED: Self = Self::MAX; | |
1977 | const EMPTY: Self = Self::MIN; | |
1978 | ||
1979 | const ONE: Self = 1u32; | |
1980 | const ZERO: Self = 0u32; | |
1981 | ||
1982 | fn checked_shl(self, rhs: u32) -> Option<Self> { | |
1983 | self.checked_shl(rhs) | |
1984 | } | |
1985 | ||
1986 | fn checked_shr(self, rhs: u32) -> Option<Self> { | |
1987 | self.checked_shr(rhs) | |
1988 | } | |
1989 | } | |
1990 | ||
1991 | impl std::fmt::Debug for FiniteBitSet<u32> { | |
1992 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1993 | write!(f, "{:032b}", self.0) | |
1994 | } | |
1995 | } | |
1996 | ||
1997 | impl FiniteBitSetTy for u64 { | |
1998 | const DOMAIN_SIZE: u32 = 64; | |
1999 | ||
2000 | const FILLED: Self = Self::MAX; | |
2001 | const EMPTY: Self = Self::MIN; | |
2002 | ||
2003 | const ONE: Self = 1u64; | |
2004 | const ZERO: Self = 0u64; | |
2005 | ||
2006 | fn checked_shl(self, rhs: u32) -> Option<Self> { | |
2007 | self.checked_shl(rhs) | |
2008 | } | |
2009 | ||
2010 | fn checked_shr(self, rhs: u32) -> Option<Self> { | |
2011 | self.checked_shr(rhs) | |
2012 | } | |
2013 | } | |
2014 | ||
2015 | impl std::fmt::Debug for FiniteBitSet<u64> { | |
2016 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2017 | write!(f, "{:064b}", self.0) | |
2018 | } | |
2019 | } | |
2020 | ||
2021 | impl FiniteBitSetTy for u128 { | |
2022 | const DOMAIN_SIZE: u32 = 128; | |
2023 | ||
2024 | const FILLED: Self = Self::MAX; | |
2025 | const EMPTY: Self = Self::MIN; | |
2026 | ||
2027 | const ONE: Self = 1u128; | |
2028 | const ZERO: Self = 0u128; | |
2029 | ||
2030 | fn checked_shl(self, rhs: u32) -> Option<Self> { | |
2031 | self.checked_shl(rhs) | |
2032 | } | |
2033 | ||
2034 | fn checked_shr(self, rhs: u32) -> Option<Self> { | |
2035 | self.checked_shr(rhs) | |
2036 | } | |
2037 | } | |
2038 | ||
2039 | impl std::fmt::Debug for FiniteBitSet<u128> { | |
2040 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2041 | write!(f, "{:0128b}", self.0) | |
2042 | } | |
2043 | } | |
2044 | ||
2045 | /// A fixed-sized bitset type represented by an integer type. Indices outwith than the range | |
2046 | /// representable by `T` are considered set. | |
2047 | #[derive(Copy, Clone, Eq, PartialEq, Decodable, Encodable)] | |
2048 | pub struct FiniteBitSet<T: FiniteBitSetTy>(pub T); | |
2049 | ||
2050 | impl<T: FiniteBitSetTy> FiniteBitSet<T> { | |
2051 | /// Creates a new, empty bitset. | |
2052 | pub fn new_empty() -> Self { | |
2053 | Self(T::EMPTY) | |
2054 | } | |
2055 | ||
2056 | /// Sets the `index`th bit. | |
2057 | pub fn set(&mut self, index: u32) { | |
2058 | self.0 |= T::ONE.checked_shl(index).unwrap_or(T::ZERO); | |
2059 | } | |
2060 | ||
2061 | /// Unsets the `index`th bit. | |
2062 | pub fn clear(&mut self, index: u32) { | |
2063 | self.0 &= !T::ONE.checked_shl(index).unwrap_or(T::ZERO); | |
2064 | } | |
2065 | ||
2066 | /// Sets the `i`th to `j`th bits. | |
2067 | pub fn set_range(&mut self, range: Range<u32>) { | |
2068 | let bits = T::FILLED | |
2069 | .checked_shl(range.end - range.start) | |
2070 | .unwrap_or(T::ZERO) | |
2071 | .not() | |
2072 | .checked_shl(range.start) | |
2073 | .unwrap_or(T::ZERO); | |
2074 | self.0 |= bits; | |
2075 | } | |
2076 | ||
2077 | /// Is the set empty? | |
2078 | pub fn is_empty(&self) -> bool { | |
2079 | self.0 == T::EMPTY | |
2080 | } | |
2081 | ||
2082 | /// Returns the domain size of the bitset. | |
2083 | pub fn within_domain(&self, index: u32) -> bool { | |
2084 | index < T::DOMAIN_SIZE | |
2085 | } | |
2086 | ||
2087 | /// Returns if the `index`th bit is set. | |
2088 | pub fn contains(&self, index: u32) -> Option<bool> { | |
2089 | self.within_domain(index) | |
2090 | .then(|| ((self.0.checked_shr(index).unwrap_or(T::ONE)) & T::ONE) == T::ONE) | |
2091 | } | |
2092 | } | |
2093 | ||
2094 | impl<T: FiniteBitSetTy> Default for FiniteBitSet<T> { | |
2095 | fn default() -> Self { | |
2096 | Self::new_empty() | |
2097 | } | |
2098 | } |