1 use crate::vec
::{Idx, IndexVec}
;
2 use arrayvec
::ArrayVec
;
5 use std
::marker
::PhantomData
;
7 use std
::ops
::{BitAnd, BitAndAssign, BitOrAssign, Not, Range, Shl}
;
10 use rustc_macros
::{Decodable, Encodable}
;
16 pub const WORD_BYTES
: usize = mem
::size_of
::<Word
>();
17 pub const WORD_BITS
: usize = WORD_BYTES
* 8;
19 /// A fixed-size bitset type with a dense representation.
21 /// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation.
23 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
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.
30 /// [`GrowableBitSet`]: struct.GrowableBitSet.html
31 #[derive(Eq, PartialEq, Decodable, Encodable)]
32 pub struct BitSet
<T
> {
35 marker
: PhantomData
<T
>,
39 /// Gets the domain size.
40 pub fn domain_size(&self) -> usize {
45 impl<T
: Idx
> BitSet
<T
> {
46 /// Creates a new, empty bitset with a given `domain_size`.
48 pub fn new_empty(domain_size
: usize) -> BitSet
<T
> {
49 let num_words
= num_words(domain_size
);
50 BitSet { domain_size, words: vec![0; num_words], marker: PhantomData }
53 /// Creates a new, filled bitset with a given `domain_size`.
55 pub fn new_filled(domain_size
: usize) -> BitSet
<T
> {
56 let num_words
= num_words(domain_size
);
57 let mut result
= BitSet { domain_size, words: vec![!0; num_words], marker: PhantomData }
;
58 result
.clear_excess_bits();
62 /// Clear all elements.
64 pub fn clear(&mut self) {
65 for word
in &mut self.words
{
70 /// Clear excess bits in the final word.
71 fn clear_excess_bits(&mut self) {
72 let num_bits_in_final_word
= self.domain_size
% WORD_BITS
;
73 if num_bits_in_final_word
> 0 {
74 let mask
= (1 << num_bits_in_final_word
) - 1;
75 let final_word_idx
= self.words
.len() - 1;
76 self.words
[final_word_idx
] &= mask
;
80 /// Count the number of set bits in the set.
81 pub fn count(&self) -> usize {
82 self.words
.iter().map(|e
| e
.count_ones() as usize).sum()
85 /// Returns `true` if `self` contains `elem`.
87 pub fn contains(&self, elem
: T
) -> bool
{
88 assert
!(elem
.index() < self.domain_size
);
89 let (word_index
, mask
) = word_index_and_mask(elem
);
90 (self.words
[word_index
] & mask
) != 0
93 /// Is `self` is a (non-strict) superset of `other`?
95 pub fn superset(&self, other
: &BitSet
<T
>) -> bool
{
96 assert_eq
!(self.domain_size
, other
.domain_size
);
97 self.words
.iter().zip(&other
.words
).all(|(a
, b
)| (a
& b
) == *b
)
100 /// Is the set empty?
102 pub fn is_empty(&self) -> bool
{
103 self.words
.iter().all(|a
| *a
== 0)
106 /// Insert `elem`. Returns whether the set has changed.
108 pub fn insert(&mut self, elem
: T
) -> bool
{
109 assert
!(elem
.index() < self.domain_size
);
110 let (word_index
, mask
) = word_index_and_mask(elem
);
111 let word_ref
= &mut self.words
[word_index
];
112 let word
= *word_ref
;
113 let new_word
= word
| mask
;
114 *word_ref
= new_word
;
118 /// Sets all bits to true.
119 pub fn insert_all(&mut self) {
120 for word
in &mut self.words
{
123 self.clear_excess_bits();
126 /// Returns `true` if the set has changed.
128 pub fn remove(&mut self, elem
: T
) -> bool
{
129 assert
!(elem
.index() < self.domain_size
);
130 let (word_index
, mask
) = word_index_and_mask(elem
);
131 let word_ref
= &mut self.words
[word_index
];
132 let word
= *word_ref
;
133 let new_word
= word
& !mask
;
134 *word_ref
= new_word
;
138 /// Sets `self = self | other` and returns `true` if `self` changed
139 /// (i.e., if new bits were added).
140 pub fn union(&mut self, other
: &impl UnionIntoBitSet
<T
>) -> bool
{
141 other
.union_into(self)
144 /// Sets `self = self - other` and returns `true` if `self` changed.
145 /// (i.e., if any bits were removed).
146 pub fn subtract(&mut self, other
: &impl SubtractFromBitSet
<T
>) -> bool
{
147 other
.subtract_from(self)
150 /// Sets `self = self & other` and return `true` if `self` changed.
151 /// (i.e., if any bits were removed).
152 pub fn intersect(&mut self, other
: &BitSet
<T
>) -> bool
{
153 assert_eq
!(self.domain_size
, other
.domain_size
);
154 bitwise(&mut self.words
, &other
.words
, |a
, b
| a
& b
)
157 /// Gets a slice of the underlying words.
158 pub fn words(&self) -> &[Word
] {
162 /// Iterates over the indices of set bits in a sorted order.
164 pub fn iter(&self) -> BitIter
<'_
, T
> {
165 BitIter
::new(&self.words
)
168 /// Duplicates the set as a hybrid set.
169 pub fn to_hybrid(&self) -> HybridBitSet
<T
> {
170 // Note: we currently don't bother trying to make a Sparse set.
171 HybridBitSet
::Dense(self.to_owned())
174 /// Set `self = self | other`. In contrast to `union` returns `true` if the set contains at
175 /// least one bit that is not in `other` (i.e. `other` is not a superset of `self`).
177 /// This is an optimization for union of a hybrid bitset.
178 fn reverse_union_sparse(&mut self, sparse
: &SparseBitSet
<T
>) -> bool
{
179 assert
!(sparse
.domain_size
== self.domain_size
);
180 self.clear_excess_bits();
182 let mut not_already
= false;
183 // Index of the current word not yet merged.
184 let mut current_index
= 0;
185 // Mask of bits that came from the sparse set in the current word.
186 let mut new_bit_mask
= 0;
187 for (word_index
, mask
) in sparse
.iter().map(|x
| word_index_and_mask(*x
)) {
188 // Next bit is in a word not inspected yet.
189 if word_index
> current_index
{
190 self.words
[current_index
] |= new_bit_mask
;
191 // Were there any bits in the old word that did not occur in the sparse set?
192 not_already
|= (self.words
[current_index
] ^ new_bit_mask
) != 0;
193 // Check all words we skipped for any set bit.
194 not_already
|= self.words
[current_index
+ 1..word_index
].iter().any(|&x
| x
!= 0);
196 current_index
= word_index
;
197 // Reset bit mask, no bits have been merged yet.
200 // Add bit and mark it as coming from the sparse set.
201 // self.words[word_index] |= mask;
202 new_bit_mask
|= mask
;
204 self.words
[current_index
] |= new_bit_mask
;
205 // Any bits in the last inspected word that were not in the sparse set?
206 not_already
|= (self.words
[current_index
] ^ new_bit_mask
) != 0;
207 // Any bits in the tail? Note `clear_excess_bits` before.
208 not_already
|= self.words
[current_index
+ 1..].iter().any(|&x
| x
!= 0);
214 /// This is implemented by all the bitsets so that BitSet::union() can be
215 /// passed any type of bitset.
216 pub trait UnionIntoBitSet
<T
: Idx
> {
217 // Performs `other = other | self`.
218 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
;
221 /// This is implemented by all the bitsets so that BitSet::subtract() can be
222 /// passed any type of bitset.
223 pub trait SubtractFromBitSet
<T
: Idx
> {
224 // Performs `other = other - self`.
225 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
;
228 impl<T
: Idx
> UnionIntoBitSet
<T
> for BitSet
<T
> {
229 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
{
230 assert_eq
!(self.domain_size
, other
.domain_size
);
231 bitwise(&mut other
.words
, &self.words
, |a
, b
| a
| b
)
235 impl<T
: Idx
> SubtractFromBitSet
<T
> for BitSet
<T
> {
236 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
{
237 assert_eq
!(self.domain_size
, other
.domain_size
);
238 bitwise(&mut other
.words
, &self.words
, |a
, b
| a
& !b
)
242 impl<T
> Clone
for BitSet
<T
> {
243 fn clone(&self) -> Self {
244 BitSet { domain_size: self.domain_size, words: self.words.clone(), marker: PhantomData }
247 fn clone_from(&mut self, from
: &Self) {
248 if self.domain_size
!= from
.domain_size
{
249 self.words
.resize(from
.domain_size
, 0);
250 self.domain_size
= from
.domain_size
;
253 self.words
.copy_from_slice(&from
.words
);
257 impl<T
: Idx
> fmt
::Debug
for BitSet
<T
> {
258 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
259 w
.debug_list().entries(self.iter()).finish()
263 impl<T
: Idx
> ToString
for BitSet
<T
> {
264 fn to_string(&self) -> String
{
265 let mut result
= String
::new();
268 // Note: this is a little endian printout of bytes.
270 // i tracks how many bits we have printed so far.
272 for word
in &self.words
{
273 let mut word
= *word
;
274 for _
in 0..WORD_BYTES
{
275 // for each byte in `word`:
276 let remain
= self.domain_size
- i
;
277 // If less than a byte remains, then mask just that many bits.
278 let mask
= if remain
<= 8 { (1 << remain) - 1 }
else { 0xFF }
;
279 assert
!(mask
<= 0xFF);
280 let byte
= word
& mask
;
282 result
.push_str(&format
!("{}{:02x}", sep
, byte
));
299 pub struct BitIter
<'a
, T
: Idx
> {
300 /// A copy of the current word, but with any already-visited bits cleared.
301 /// (This lets us use `trailing_zeros()` to find the next set bit.) When it
302 /// is reduced to 0, we move onto the next word.
305 /// The offset (measured in bits) of the current word.
308 /// Underlying iterator over the words.
309 iter
: slice
::Iter
<'a
, Word
>,
311 marker
: PhantomData
<T
>,
314 impl<'a
, T
: Idx
> BitIter
<'a
, T
> {
316 fn new(words
: &'a
[Word
]) -> BitIter
<'a
, T
> {
317 // We initialize `word` and `offset` to degenerate values. On the first
318 // call to `next()` we will fall through to getting the first word from
319 // `iter`, which sets `word` to the first word (if there is one) and
320 // `offset` to 0. Doing it this way saves us from having to maintain
321 // additional state about whether we have started.
324 offset
: usize::MAX
- (WORD_BITS
- 1),
331 impl<'a
, T
: Idx
> Iterator
for BitIter
<'a
, T
> {
333 fn next(&mut self) -> Option
<T
> {
336 // Get the position of the next set bit in the current word,
337 // then clear the bit.
338 let bit_pos
= self.word
.trailing_zeros() as usize;
339 let bit
= 1 << bit_pos
;
341 return Some(T
::new(bit_pos
+ self.offset
));
344 // Move onto the next word. `wrapping_add()` is needed to handle
345 // the degenerate initial value given to `offset` in `new()`.
346 let word
= self.iter
.next()?
;
348 self.offset
= self.offset
.wrapping_add(WORD_BITS
);
354 fn bitwise
<Op
>(out_vec
: &mut [Word
], in_vec
: &[Word
], op
: Op
) -> bool
356 Op
: Fn(Word
, Word
) -> Word
,
358 assert_eq
!(out_vec
.len(), in_vec
.len());
359 let mut changed
= false;
360 for (out_elem
, in_elem
) in out_vec
.iter_mut().zip(in_vec
.iter()) {
361 let old_val
= *out_elem
;
362 let new_val
= op(old_val
, *in_elem
);
364 changed
|= old_val
!= new_val
;
369 const SPARSE_MAX
: usize = 8;
371 /// A fixed-size bitset type with a sparse representation and a maximum of
372 /// `SPARSE_MAX` elements. The elements are stored as a sorted `ArrayVec` with
375 /// This type is used by `HybridBitSet`; do not use directly.
376 #[derive(Clone, Debug)]
377 pub struct SparseBitSet
<T
> {
379 elems
: ArrayVec
<[T
; SPARSE_MAX
]>,
382 impl<T
: Idx
> SparseBitSet
<T
> {
383 fn new_empty(domain_size
: usize) -> Self {
384 SparseBitSet { domain_size, elems: ArrayVec::new() }
387 fn len(&self) -> usize {
391 fn is_empty(&self) -> bool
{
392 self.elems
.len() == 0
395 fn contains(&self, elem
: T
) -> bool
{
396 assert
!(elem
.index() < self.domain_size
);
397 self.elems
.contains(&elem
)
400 fn insert(&mut self, elem
: T
) -> bool
{
401 assert
!(elem
.index() < self.domain_size
);
402 let changed
= if let Some(i
) = self.elems
.iter().position(|&e
| e
>= elem
) {
403 if self.elems
[i
] == elem
{
404 // `elem` is already in the set.
407 // `elem` is smaller than one or more existing elements.
408 self.elems
.insert(i
, elem
);
412 // `elem` is larger than all existing elements.
413 self.elems
.push(elem
);
416 assert
!(self.len() <= SPARSE_MAX
);
420 fn remove(&mut self, elem
: T
) -> bool
{
421 assert
!(elem
.index() < self.domain_size
);
422 if let Some(i
) = self.elems
.iter().position(|&e
| e
== elem
) {
423 self.elems
.remove(i
);
430 fn to_dense(&self) -> BitSet
<T
> {
431 let mut dense
= BitSet
::new_empty(self.domain_size
);
432 for elem
in self.elems
.iter() {
438 fn iter(&self) -> slice
::Iter
<'_
, T
> {
443 impl<T
: Idx
> UnionIntoBitSet
<T
> for SparseBitSet
<T
> {
444 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
{
445 assert_eq
!(self.domain_size
, other
.domain_size
);
446 let mut changed
= false;
447 for elem
in self.iter() {
448 changed
|= other
.insert(*elem
);
454 impl<T
: Idx
> SubtractFromBitSet
<T
> for SparseBitSet
<T
> {
455 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
{
456 assert_eq
!(self.domain_size
, other
.domain_size
);
457 let mut changed
= false;
458 for elem
in self.iter() {
459 changed
|= other
.remove(*elem
);
465 /// A fixed-size bitset type with a hybrid representation: sparse when there
466 /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more
467 /// than `SPARSE_MAX`.
469 /// This type is especially efficient for sets that typically have a small
470 /// number of elements, but a large `domain_size`, and are cleared frequently.
472 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
475 /// All operations that involve an element will panic if the element is equal
476 /// to or greater than the domain size. All operations that involve two bitsets
477 /// will panic if the bitsets have differing domain sizes.
479 pub enum HybridBitSet
<T
> {
480 Sparse(SparseBitSet
<T
>),
484 impl<T
: Idx
> fmt
::Debug
for HybridBitSet
<T
> {
485 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
487 Self::Sparse(b
) => b
.fmt(w
),
488 Self::Dense(b
) => b
.fmt(w
),
493 impl<T
: Idx
> HybridBitSet
<T
> {
494 pub fn new_empty(domain_size
: usize) -> Self {
495 HybridBitSet
::Sparse(SparseBitSet
::new_empty(domain_size
))
498 pub fn domain_size(&self) -> usize {
500 HybridBitSet
::Sparse(sparse
) => sparse
.domain_size
,
501 HybridBitSet
::Dense(dense
) => dense
.domain_size
,
505 pub fn clear(&mut self) {
506 let domain_size
= self.domain_size();
507 *self = HybridBitSet
::new_empty(domain_size
);
510 pub fn contains(&self, elem
: T
) -> bool
{
512 HybridBitSet
::Sparse(sparse
) => sparse
.contains(elem
),
513 HybridBitSet
::Dense(dense
) => dense
.contains(elem
),
517 pub fn superset(&self, other
: &HybridBitSet
<T
>) -> bool
{
518 match (self, other
) {
519 (HybridBitSet
::Dense(self_dense
), HybridBitSet
::Dense(other_dense
)) => {
520 self_dense
.superset(other_dense
)
523 assert
!(self.domain_size() == other
.domain_size());
524 other
.iter().all(|elem
| self.contains(elem
))
529 pub fn is_empty(&self) -> bool
{
531 HybridBitSet
::Sparse(sparse
) => sparse
.is_empty(),
532 HybridBitSet
::Dense(dense
) => dense
.is_empty(),
536 pub fn insert(&mut self, elem
: T
) -> bool
{
537 // No need to check `elem` against `self.domain_size` here because all
538 // the match cases check it, one way or another.
540 HybridBitSet
::Sparse(sparse
) if sparse
.len() < SPARSE_MAX
=> {
541 // The set is sparse and has space for `elem`.
544 HybridBitSet
::Sparse(sparse
) if sparse
.contains(elem
) => {
545 // The set is sparse and does not have space for `elem`, but
546 // that doesn't matter because `elem` is already present.
549 HybridBitSet
::Sparse(sparse
) => {
550 // The set is sparse and full. Convert to a dense set.
551 let mut dense
= sparse
.to_dense();
552 let changed
= dense
.insert(elem
);
554 *self = HybridBitSet
::Dense(dense
);
557 HybridBitSet
::Dense(dense
) => dense
.insert(elem
),
561 pub fn insert_all(&mut self) {
562 let domain_size
= self.domain_size();
564 HybridBitSet
::Sparse(_
) => {
565 *self = HybridBitSet
::Dense(BitSet
::new_filled(domain_size
));
567 HybridBitSet
::Dense(dense
) => dense
.insert_all(),
571 pub fn remove(&mut self, elem
: T
) -> bool
{
572 // Note: we currently don't bother going from Dense back to Sparse.
574 HybridBitSet
::Sparse(sparse
) => sparse
.remove(elem
),
575 HybridBitSet
::Dense(dense
) => dense
.remove(elem
),
579 pub fn union(&mut self, other
: &HybridBitSet
<T
>) -> bool
{
581 HybridBitSet
::Sparse(self_sparse
) => {
583 HybridBitSet
::Sparse(other_sparse
) => {
584 // Both sets are sparse. Add the elements in
585 // `other_sparse` to `self` one at a time. This
586 // may or may not cause `self` to be densified.
587 assert_eq
!(self.domain_size(), other
.domain_size());
588 let mut changed
= false;
589 for elem
in other_sparse
.iter() {
590 changed
|= self.insert(*elem
);
594 HybridBitSet
::Dense(other_dense
) => {
595 // `self` is sparse and `other` is dense. To
596 // merge them, we have two available strategies:
597 // * Densify `self` then merge other
598 // * Clone other then integrate bits from `self`
599 // The second strategy requires dedicated method
600 // since the usual `union` returns the wrong
601 // result. In the dedicated case the computation
602 // is slightly faster if the bits of the sparse
603 // bitset map to only few words of the dense
604 // representation, i.e. indices are near each
607 // Benchmarking seems to suggest that the second
608 // option is worth it.
609 let mut new_dense
= other_dense
.clone();
610 let changed
= new_dense
.reverse_union_sparse(self_sparse
);
611 *self = HybridBitSet
::Dense(new_dense
);
617 HybridBitSet
::Dense(self_dense
) => self_dense
.union(other
),
621 /// Converts to a dense set, consuming itself in the process.
622 pub fn to_dense(self) -> BitSet
<T
> {
624 HybridBitSet
::Sparse(sparse
) => sparse
.to_dense(),
625 HybridBitSet
::Dense(dense
) => dense
,
629 pub fn iter(&self) -> HybridIter
<'_
, T
> {
631 HybridBitSet
::Sparse(sparse
) => HybridIter
::Sparse(sparse
.iter()),
632 HybridBitSet
::Dense(dense
) => HybridIter
::Dense(dense
.iter()),
637 impl<T
: Idx
> UnionIntoBitSet
<T
> for HybridBitSet
<T
> {
638 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
{
640 HybridBitSet
::Sparse(sparse
) => sparse
.union_into(other
),
641 HybridBitSet
::Dense(dense
) => dense
.union_into(other
),
646 impl<T
: Idx
> SubtractFromBitSet
<T
> for HybridBitSet
<T
> {
647 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
{
649 HybridBitSet
::Sparse(sparse
) => sparse
.subtract_from(other
),
650 HybridBitSet
::Dense(dense
) => dense
.subtract_from(other
),
655 pub enum HybridIter
<'a
, T
: Idx
> {
656 Sparse(slice
::Iter
<'a
, T
>),
657 Dense(BitIter
<'a
, T
>),
660 impl<'a
, T
: Idx
> Iterator
for HybridIter
<'a
, T
> {
663 fn next(&mut self) -> Option
<T
> {
665 HybridIter
::Sparse(sparse
) => sparse
.next().copied(),
666 HybridIter
::Dense(dense
) => dense
.next(),
671 /// A resizable bitset type with a dense representation.
673 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
676 /// All operations that involve an element will panic if the element is equal
677 /// to or greater than the domain size.
678 #[derive(Clone, Debug, PartialEq)]
679 pub struct GrowableBitSet
<T
: Idx
> {
683 impl<T
: Idx
> GrowableBitSet
<T
> {
684 /// Ensure that the set can hold at least `min_domain_size` elements.
685 pub fn ensure(&mut self, min_domain_size
: usize) {
686 if self.bit_set
.domain_size
< min_domain_size
{
687 self.bit_set
.domain_size
= min_domain_size
;
690 let min_num_words
= num_words(min_domain_size
);
691 if self.bit_set
.words
.len() < min_num_words
{
692 self.bit_set
.words
.resize(min_num_words
, 0)
696 pub fn new_empty() -> GrowableBitSet
<T
> {
697 GrowableBitSet { bit_set: BitSet::new_empty(0) }
700 pub fn with_capacity(capacity
: usize) -> GrowableBitSet
<T
> {
701 GrowableBitSet { bit_set: BitSet::new_empty(capacity) }
704 /// Returns `true` if the set has changed.
706 pub fn insert(&mut self, elem
: T
) -> bool
{
707 self.ensure(elem
.index() + 1);
708 self.bit_set
.insert(elem
)
712 pub fn contains(&self, elem
: T
) -> bool
{
713 let (word_index
, mask
) = word_index_and_mask(elem
);
714 if let Some(word
) = self.bit_set
.words
.get(word_index
) { (word & mask) != 0 }
else { false }
718 /// A fixed-size 2D bit matrix type with a dense representation.
720 /// `R` and `C` are index types used to identify rows and columns respectively;
721 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
723 /// All operations that involve a row and/or column index will panic if the
724 /// index exceeds the relevant bound.
725 #[derive(Clone, Eq, PartialEq, Decodable, Encodable)]
726 pub struct BitMatrix
<R
: Idx
, C
: Idx
> {
730 marker
: PhantomData
<(R
, C
)>,
733 impl<R
: Idx
, C
: Idx
> BitMatrix
<R
, C
> {
734 /// Creates a new `rows x columns` matrix, initially empty.
735 pub fn new(num_rows
: usize, num_columns
: usize) -> BitMatrix
<R
, C
> {
736 // For every element, we need one bit for every other
737 // element. Round up to an even number of words.
738 let words_per_row
= num_words(num_columns
);
742 words
: vec
![0; num_rows
* words_per_row
],
747 /// Creates a new matrix, with `row` used as the value for every row.
748 pub fn from_row_n(row
: &BitSet
<C
>, num_rows
: usize) -> BitMatrix
<R
, C
> {
749 let num_columns
= row
.domain_size();
750 let words_per_row
= num_words(num_columns
);
751 assert_eq
!(words_per_row
, row
.words().len());
755 words
: iter
::repeat(row
.words()).take(num_rows
).flatten().cloned().collect(),
760 pub fn rows(&self) -> impl Iterator
<Item
= R
> {
761 (0..self.num_rows
).map(R
::new
)
764 /// The range of bits for a given row.
765 fn range(&self, row
: R
) -> (usize, usize) {
766 let words_per_row
= num_words(self.num_columns
);
767 let start
= row
.index() * words_per_row
;
768 (start
, start
+ words_per_row
)
771 /// Sets the cell at `(row, column)` to true. Put another way, insert
772 /// `column` to the bitset for `row`.
774 /// Returns `true` if this changed the matrix.
775 pub fn insert(&mut self, row
: R
, column
: C
) -> bool
{
776 assert
!(row
.index() < self.num_rows
&& column
.index() < self.num_columns
);
777 let (start
, _
) = self.range(row
);
778 let (word_index
, mask
) = word_index_and_mask(column
);
779 let words
= &mut self.words
[..];
780 let word
= words
[start
+ word_index
];
781 let new_word
= word
| mask
;
782 words
[start
+ word_index
] = new_word
;
786 /// Do the bits from `row` contain `column`? Put another way, is
787 /// the matrix cell at `(row, column)` true? Put yet another way,
788 /// if the matrix represents (transitive) reachability, can
789 /// `row` reach `column`?
790 pub fn contains(&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 (self.words
[start
+ word_index
] & mask
) != 0
797 /// Returns those indices that are true in rows `a` and `b`. This
798 /// is an *O*(*n*) operation where *n* is the number of elements
799 /// (somewhat independent from the actual size of the
800 /// intersection, in particular).
801 pub fn intersect_rows(&self, row1
: R
, row2
: R
) -> Vec
<C
> {
802 assert
!(row1
.index() < self.num_rows
&& row2
.index() < self.num_rows
);
803 let (row1_start
, row1_end
) = self.range(row1
);
804 let (row2_start
, row2_end
) = self.range(row2
);
805 let mut result
= Vec
::with_capacity(self.num_columns
);
806 for (base
, (i
, j
)) in (row1_start
..row1_end
).zip(row2_start
..row2_end
).enumerate() {
807 let mut v
= self.words
[i
] & self.words
[j
];
808 for bit
in 0..WORD_BITS
{
813 result
.push(C
::new(base
* WORD_BITS
+ bit
));
821 /// Adds the bits from row `read` to the bits from row `write`, and
822 /// returns `true` if anything changed.
824 /// This is used when computing transitive reachability because if
825 /// you have an edge `write -> read`, because in that case
826 /// `write` can reach everything that `read` can (and
827 /// potentially more).
828 pub fn union_rows(&mut self, read
: R
, write
: R
) -> bool
{
829 assert
!(read
.index() < self.num_rows
&& write
.index() < self.num_rows
);
830 let (read_start
, read_end
) = self.range(read
);
831 let (write_start
, write_end
) = self.range(write
);
832 let words
= &mut self.words
[..];
833 let mut changed
= false;
834 for (read_index
, write_index
) in (read_start
..read_end
).zip(write_start
..write_end
) {
835 let word
= words
[write_index
];
836 let new_word
= word
| words
[read_index
];
837 words
[write_index
] = new_word
;
838 changed
|= word
!= new_word
;
843 /// Adds the bits from `with` to the bits from row `write`, and
844 /// returns `true` if anything changed.
845 pub fn union_row_with(&mut self, with
: &BitSet
<C
>, write
: R
) -> bool
{
846 assert
!(write
.index() < self.num_rows
);
847 assert_eq
!(with
.domain_size(), self.num_columns
);
848 let (write_start
, write_end
) = self.range(write
);
849 let mut changed
= false;
850 for (read_index
, write_index
) in (0..with
.words().len()).zip(write_start
..write_end
) {
851 let word
= self.words
[write_index
];
852 let new_word
= word
| with
.words()[read_index
];
853 self.words
[write_index
] = new_word
;
854 changed
|= word
!= new_word
;
859 /// Sets every cell in `row` to true.
860 pub fn insert_all_into_row(&mut self, row
: R
) {
861 assert
!(row
.index() < self.num_rows
);
862 let (start
, end
) = self.range(row
);
863 let words
= &mut self.words
[..];
864 for index
in start
..end
{
867 self.clear_excess_bits(row
);
870 /// Clear excess bits in the final word of the row.
871 fn clear_excess_bits(&mut self, row
: R
) {
872 let num_bits_in_final_word
= self.num_columns
% WORD_BITS
;
873 if num_bits_in_final_word
> 0 {
874 let mask
= (1 << num_bits_in_final_word
) - 1;
875 let (_
, end
) = self.range(row
);
876 let final_word_idx
= end
- 1;
877 self.words
[final_word_idx
] &= mask
;
881 /// Gets a slice of the underlying words.
882 pub fn words(&self) -> &[Word
] {
886 /// Iterates through all the columns set to true in a given row of
888 pub fn iter(&self, row
: R
) -> BitIter
<'_
, C
> {
889 assert
!(row
.index() < self.num_rows
);
890 let (start
, end
) = self.range(row
);
891 BitIter
::new(&self.words
[start
..end
])
894 /// Returns the number of elements in `row`.
895 pub fn count(&self, row
: R
) -> usize {
896 let (start
, end
) = self.range(row
);
897 self.words
[start
..end
].iter().map(|e
| e
.count_ones() as usize).sum()
901 impl<R
: Idx
, C
: Idx
> fmt
::Debug
for BitMatrix
<R
, C
> {
902 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
903 /// Forces its contents to print in regular mode instead of alternate mode.
904 struct OneLinePrinter
<T
>(T
);
905 impl<T
: fmt
::Debug
> fmt
::Debug
for OneLinePrinter
<T
> {
906 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
907 write
!(fmt
, "{:?}", self.0)
911 write
!(fmt
, "BitMatrix({}x{}) ", self.num_rows
, self.num_columns
)?
;
912 let items
= self.rows().flat_map(|r
| self.iter(r
).map(move |c
| (r
, c
)));
913 fmt
.debug_set().entries(items
.map(OneLinePrinter
)).finish()
917 /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
918 /// sparse representation.
920 /// Initially, every row has no explicit representation. If any bit within a
921 /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`.
922 /// Furthermore, any previously uninstantiated rows prior to it will be
923 /// instantiated as `None`. Those prior rows may themselves become fully
924 /// instantiated later on if any of their bits are set.
926 /// `R` and `C` are index types used to identify rows and columns respectively;
927 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
928 #[derive(Clone, Debug)]
929 pub struct SparseBitMatrix
<R
, C
>
935 rows
: IndexVec
<R
, Option
<HybridBitSet
<C
>>>,
938 impl<R
: Idx
, C
: Idx
> SparseBitMatrix
<R
, C
> {
939 /// Creates a new empty sparse bit matrix with no rows or columns.
940 pub fn new(num_columns
: usize) -> Self {
941 Self { num_columns, rows: IndexVec::new() }
944 fn ensure_row(&mut self, row
: R
) -> &mut HybridBitSet
<C
> {
945 // Instantiate any missing rows up to and including row `row` with an
946 // empty HybridBitSet.
947 self.rows
.ensure_contains_elem(row
, || None
);
949 // Then replace row `row` with a full HybridBitSet if necessary.
950 let num_columns
= self.num_columns
;
951 self.rows
[row
].get_or_insert_with(|| HybridBitSet
::new_empty(num_columns
))
954 /// Sets the cell at `(row, column)` to true. Put another way, insert
955 /// `column` to the bitset for `row`.
957 /// Returns `true` if this changed the matrix.
958 pub fn insert(&mut self, row
: R
, column
: C
) -> bool
{
959 self.ensure_row(row
).insert(column
)
962 /// Do the bits from `row` contain `column`? Put another way, is
963 /// the matrix cell at `(row, column)` true? Put yet another way,
964 /// if the matrix represents (transitive) reachability, can
965 /// `row` reach `column`?
966 pub fn contains(&self, row
: R
, column
: C
) -> bool
{
967 self.row(row
).map_or(false, |r
| r
.contains(column
))
970 /// Adds the bits from row `read` to the bits from row `write`, and
971 /// returns `true` if anything changed.
973 /// This is used when computing transitive reachability because if
974 /// you have an edge `write -> read`, because in that case
975 /// `write` can reach everything that `read` can (and
976 /// potentially more).
977 pub fn union_rows(&mut self, read
: R
, write
: R
) -> bool
{
978 if read
== write
|| self.row(read
).is_none() {
982 self.ensure_row(write
);
983 if let (Some(read_row
), Some(write_row
)) = self.rows
.pick2_mut(read
, write
) {
984 write_row
.union(read_row
)
990 /// Union a row, `from`, into the `into` row.
991 pub fn union_into_row(&mut self, into
: R
, from
: &HybridBitSet
<C
>) -> bool
{
992 self.ensure_row(into
).union(from
)
995 /// Insert all bits in the given row.
996 pub fn insert_all_into_row(&mut self, row
: R
) {
997 self.ensure_row(row
).insert_all();
1000 pub fn rows(&self) -> impl Iterator
<Item
= R
> {
1004 /// Iterates through all the columns set to true in a given row of
1006 pub fn iter
<'a
>(&'a
self, row
: R
) -> impl Iterator
<Item
= C
> + 'a
{
1007 self.row(row
).into_iter().flat_map(|r
| r
.iter())
1010 pub fn row(&self, row
: R
) -> Option
<&HybridBitSet
<C
>> {
1011 if let Some(Some(row
)) = self.rows
.get(row
) { Some(row) }
else { None }
1016 fn num_words
<T
: Idx
>(domain_size
: T
) -> usize {
1017 (domain_size
.index() + WORD_BITS
- 1) / WORD_BITS
1021 fn word_index_and_mask
<T
: Idx
>(elem
: T
) -> (usize, Word
) {
1022 let elem
= elem
.index();
1023 let word_index
= elem
/ WORD_BITS
;
1024 let mask
= 1 << (elem
% WORD_BITS
);
1028 /// Integral type used to represent the bit set.
1029 pub trait FiniteBitSetTy
:
1030 BitAnd
<Output
= Self>
1036 + Not
<Output
= Self>
1040 /// Size of the domain representable by this type, e.g. 64 for `u64`.
1041 const DOMAIN_SIZE
: u32;
1043 /// Value which represents the `FiniteBitSet` having every bit set.
1045 /// Value which represents the `FiniteBitSet` having no bits set.
1048 /// Value for one as the integral type.
1050 /// Value for zero as the integral type.
1053 /// Perform a checked left shift on the integral type.
1054 fn checked_shl(self, rhs
: u32) -> Option
<Self>;
1055 /// Perform a checked right shift on the integral type.
1056 fn checked_shr(self, rhs
: u32) -> Option
<Self>;
1059 impl FiniteBitSetTy
for u32 {
1060 const DOMAIN_SIZE
: u32 = 32;
1062 const FILLED
: Self = Self::MAX
;
1063 const EMPTY
: Self = Self::MIN
;
1065 const ONE
: Self = 1u32;
1066 const ZERO
: Self = 0u32;
1068 fn checked_shl(self, rhs
: u32) -> Option
<Self> {
1069 self.checked_shl(rhs
)
1072 fn checked_shr(self, rhs
: u32) -> Option
<Self> {
1073 self.checked_shr(rhs
)
1077 impl std
::fmt
::Debug
for FiniteBitSet
<u32> {
1078 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1079 write
!(f
, "{:032b}", self.0)
1083 impl FiniteBitSetTy
for u64 {
1084 const DOMAIN_SIZE
: u32 = 64;
1086 const FILLED
: Self = Self::MAX
;
1087 const EMPTY
: Self = Self::MIN
;
1089 const ONE
: Self = 1u64;
1090 const ZERO
: Self = 0u64;
1092 fn checked_shl(self, rhs
: u32) -> Option
<Self> {
1093 self.checked_shl(rhs
)
1096 fn checked_shr(self, rhs
: u32) -> Option
<Self> {
1097 self.checked_shr(rhs
)
1101 impl std
::fmt
::Debug
for FiniteBitSet
<u64> {
1102 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1103 write
!(f
, "{:064b}", self.0)
1107 impl FiniteBitSetTy
for u128
{
1108 const DOMAIN_SIZE
: u32 = 128;
1110 const FILLED
: Self = Self::MAX
;
1111 const EMPTY
: Self = Self::MIN
;
1113 const ONE
: Self = 1u128;
1114 const ZERO
: Self = 0u128;
1116 fn checked_shl(self, rhs
: u32) -> Option
<Self> {
1117 self.checked_shl(rhs
)
1120 fn checked_shr(self, rhs
: u32) -> Option
<Self> {
1121 self.checked_shr(rhs
)
1125 impl std
::fmt
::Debug
for FiniteBitSet
<u128
> {
1126 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1127 write
!(f
, "{:0128b}", self.0)
1131 /// A fixed-sized bitset type represented by an integer type. Indices outwith than the range
1132 /// representable by `T` are considered set.
1133 #[derive(Copy, Clone, Eq, PartialEq, Decodable, Encodable)]
1134 pub struct FiniteBitSet
<T
: FiniteBitSetTy
>(pub T
);
1136 impl<T
: FiniteBitSetTy
> FiniteBitSet
<T
> {
1137 /// Creates a new, empty bitset.
1138 pub fn new_empty() -> Self {
1142 /// Sets the `index`th bit.
1143 pub fn set(&mut self, index
: u32) {
1144 self.0 |= T
::ONE
.checked_shl(index
).unwrap_or(T
::ZERO
);
1147 /// Unsets the `index`th bit.
1148 pub fn clear(&mut self, index
: u32) {
1149 self.0 &= !T
::ONE
.checked_shl(index
).unwrap_or(T
::ZERO
);
1152 /// Sets the `i`th to `j`th bits.
1153 pub fn set_range(&mut self, range
: Range
<u32>) {
1154 let bits
= T
::FILLED
1155 .checked_shl(range
.end
- range
.start
)
1158 .checked_shl(range
.start
)
1159 .unwrap_or(T
::ZERO
);
1163 /// Is the set empty?
1164 pub fn is_empty(&self) -> bool
{
1168 /// Returns the domain size of the bitset.
1169 pub fn within_domain(&self, index
: u32) -> bool
{
1170 index
< T
::DOMAIN_SIZE
1173 /// Returns if the `index`th bit is set.
1174 pub fn contains(&self, index
: u32) -> Option
<bool
> {
1175 self.within_domain(index
)
1176 .then(|| ((self.0.checked_shr(index
).unwrap_or(T
::ONE
)) & T
::ONE
) == T
::ONE
)
1180 impl<T
: FiniteBitSetTy
> Default
for FiniteBitSet
<T
> {
1181 fn default() -> Self {