1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use indexed_vec
::{Idx, IndexVec}
;
12 use smallvec
::SmallVec
;
15 use std
::marker
::PhantomData
;
20 pub const WORD_BYTES
: usize = mem
::size_of
::<Word
>();
21 pub const WORD_BITS
: usize = WORD_BYTES
* 8;
23 /// A fixed-size bitset type with a dense representation. It does not support
24 /// resizing after creation; use `GrowableBitSet` for that.
26 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
29 /// All operations that involve an element will panic if the element is equal
30 /// to or greater than the domain size. All operations that involve two bitsets
31 /// will panic if the bitsets have differing domain sizes.
32 #[derive(Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
33 pub struct BitSet
<T
: Idx
> {
36 marker
: PhantomData
<T
>,
39 impl<T
: Idx
> BitSet
<T
> {
40 /// Create a new, empty bitset with a given `domain_size`.
42 pub fn new_empty(domain_size
: usize) -> BitSet
<T
> {
43 let num_words
= num_words(domain_size
);
46 words
: vec
![0; num_words
],
51 /// Create a new, filled bitset with a given `domain_size`.
53 pub fn new_filled(domain_size
: usize) -> BitSet
<T
> {
54 let num_words
= num_words(domain_size
);
55 let mut result
= BitSet
{
57 words
: vec
![!0; num_words
],
60 result
.clear_excess_bits();
64 /// Get the domain size.
65 pub fn domain_size(&self) -> usize {
69 /// Clear all elements.
71 pub fn clear(&mut self) {
72 for word
in &mut self.words
{
77 /// Clear excess bits in the final word.
78 fn clear_excess_bits(&mut self) {
79 let num_bits_in_final_word
= self.domain_size
% WORD_BITS
;
80 if num_bits_in_final_word
> 0 {
81 let mask
= (1 << num_bits_in_final_word
) - 1;
82 let final_word_idx
= self.words
.len() - 1;
83 self.words
[final_word_idx
] &= mask
;
87 /// Efficiently overwrite `self` with `other`.
88 pub fn overwrite(&mut self, other
: &BitSet
<T
>) {
89 assert
!(self.domain_size
== other
.domain_size
);
90 self.words
.clone_from_slice(&other
.words
);
93 /// Count the number of set bits in the set.
94 pub fn count(&self) -> usize {
95 self.words
.iter().map(|e
| e
.count_ones() as usize).sum()
98 /// True if `self` contains `elem`.
100 pub fn contains(&self, elem
: T
) -> bool
{
101 assert
!(elem
.index() < self.domain_size
);
102 let (word_index
, mask
) = word_index_and_mask(elem
);
103 (self.words
[word_index
] & mask
) != 0
106 /// Is `self` is a (non-strict) superset of `other`?
108 pub fn superset(&self, other
: &BitSet
<T
>) -> bool
{
109 assert_eq
!(self.domain_size
, other
.domain_size
);
110 self.words
.iter().zip(&other
.words
).all(|(a
, b
)| (a
& b
) == *b
)
113 /// Is the set empty?
115 pub fn is_empty(&self) -> bool
{
116 self.words
.iter().all(|a
| *a
== 0)
119 /// Insert `elem`. Returns true if the set has changed.
121 pub fn insert(&mut self, elem
: T
) -> bool
{
122 assert
!(elem
.index() < self.domain_size
);
123 let (word_index
, mask
) = word_index_and_mask(elem
);
124 let word_ref
= &mut self.words
[word_index
];
125 let word
= *word_ref
;
126 let new_word
= word
| mask
;
127 *word_ref
= new_word
;
131 /// Sets all bits to true.
132 pub fn insert_all(&mut self) {
133 for word
in &mut self.words
{
136 self.clear_excess_bits();
139 /// Returns true if the set has changed.
141 pub fn remove(&mut self, elem
: T
) -> bool
{
142 assert
!(elem
.index() < self.domain_size
);
143 let (word_index
, mask
) = word_index_and_mask(elem
);
144 let word_ref
= &mut self.words
[word_index
];
145 let word
= *word_ref
;
146 let new_word
= word
& !mask
;
147 *word_ref
= new_word
;
151 /// Set `self = self | other` and return true if `self` changed
152 /// (i.e., if new bits were added).
153 pub fn union(&mut self, other
: &impl UnionIntoBitSet
<T
>) -> bool
{
154 other
.union_into(self)
157 /// Set `self = self - other` and return true if `self` changed.
158 /// (i.e., if any bits were removed).
159 pub fn subtract(&mut self, other
: &impl SubtractFromBitSet
<T
>) -> bool
{
160 other
.subtract_from(self)
163 /// Set `self = self & other` and return true if `self` changed.
164 /// (i.e., if any bits were removed).
165 pub fn intersect(&mut self, other
: &BitSet
<T
>) -> bool
{
166 assert_eq
!(self.domain_size
, other
.domain_size
);
167 bitwise(&mut self.words
, &other
.words
, |a
, b
| { a & b }
)
170 /// Get a slice of the underlying words.
171 pub fn words(&self) -> &[Word
] {
175 /// Iterates over the indices of set bits in a sorted order.
177 pub fn iter
<'a
>(&'a
self) -> BitIter
<'a
, T
> {
180 iter
: self.words
.iter().enumerate(),
185 /// Duplicates the set as a hybrid set.
186 pub fn to_hybrid(&self) -> HybridBitSet
<T
> {
187 // Note: we currently don't bother trying to make a Sparse set.
188 HybridBitSet
::Dense(self.to_owned())
192 /// This is implemented by all the bitsets so that BitSet::union() can be
193 /// passed any type of bitset.
194 pub trait UnionIntoBitSet
<T
: Idx
> {
195 // Performs `other = other | self`.
196 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
;
199 /// This is implemented by all the bitsets so that BitSet::subtract() can be
200 /// passed any type of bitset.
201 pub trait SubtractFromBitSet
<T
: Idx
> {
202 // Performs `other = other - self`.
203 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
;
206 impl<T
: Idx
> UnionIntoBitSet
<T
> for BitSet
<T
> {
207 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
{
208 assert_eq
!(self.domain_size
, other
.domain_size
);
209 bitwise(&mut other
.words
, &self.words
, |a
, b
| { a | b }
)
213 impl<T
: Idx
> SubtractFromBitSet
<T
> for BitSet
<T
> {
214 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
{
215 assert_eq
!(self.domain_size
, other
.domain_size
);
216 bitwise(&mut other
.words
, &self.words
, |a
, b
| { a & !b }
)
220 impl<T
: Idx
> fmt
::Debug
for BitSet
<T
> {
221 fn fmt(&self, w
: &mut fmt
::Formatter
) -> fmt
::Result
{
223 .entries(self.iter())
228 impl<T
: Idx
> ToString
for BitSet
<T
> {
229 fn to_string(&self) -> String
{
230 let mut result
= String
::new();
233 // Note: this is a little endian printout of bytes.
235 // i tracks how many bits we have printed so far.
237 for word
in &self.words
{
238 let mut word
= *word
;
239 for _
in 0..WORD_BYTES
{ // for each byte in `word`:
240 let remain
= self.domain_size
- i
;
241 // If less than a byte remains, then mask just that many bits.
242 let mask
= if remain
<= 8 { (1 << remain) - 1 }
else { 0xFF }
;
243 assert
!(mask
<= 0xFF);
244 let byte
= word
& mask
;
246 result
.push_str(&format
!("{}{:02x}", sep
, byte
));
248 if remain
<= 8 { break; }
261 pub struct BitIter
<'a
, T
: Idx
> {
262 cur
: Option
<(Word
, usize)>,
263 iter
: iter
::Enumerate
<slice
::Iter
<'a
, Word
>>,
264 marker
: PhantomData
<T
>
267 impl<'a
, T
: Idx
> Iterator
for BitIter
<'a
, T
> {
269 fn next(&mut self) -> Option
<T
> {
271 if let Some((ref mut word
, offset
)) = self.cur
{
272 let bit_pos
= word
.trailing_zeros() as usize;
273 if bit_pos
!= WORD_BITS
{
274 let bit
= 1 << bit_pos
;
276 return Some(T
::new(bit_pos
+ offset
))
280 let (i
, word
) = self.iter
.next()?
;
281 self.cur
= Some((*word
, WORD_BITS
* i
));
286 pub trait BitSetOperator
{
287 /// Combine one bitset into another.
288 fn join
<T
: Idx
>(&self, inout_set
: &mut BitSet
<T
>, in_set
: &BitSet
<T
>) -> bool
;
292 fn bitwise
<Op
>(out_vec
: &mut [Word
], in_vec
: &[Word
], op
: Op
) -> bool
293 where Op
: Fn(Word
, Word
) -> Word
295 assert_eq
!(out_vec
.len(), in_vec
.len());
296 let mut changed
= false;
297 for (out_elem
, in_elem
) in out_vec
.iter_mut().zip(in_vec
.iter()) {
298 let old_val
= *out_elem
;
299 let new_val
= op(old_val
, *in_elem
);
301 changed
|= old_val
!= new_val
;
306 const SPARSE_MAX
: usize = 8;
308 /// A fixed-size bitset type with a sparse representation and a maximum of
309 /// `SPARSE_MAX` elements. The elements are stored as a sorted `SmallVec` with
310 /// no duplicates; although `SmallVec` can spill its elements to the heap, that
311 /// never happens within this type because of the `SPARSE_MAX` limit.
313 /// This type is used by `HybridBitSet`; do not use directly.
314 #[derive(Clone, Debug)]
315 pub struct SparseBitSet
<T
: Idx
> {
317 elems
: SmallVec
<[T
; SPARSE_MAX
]>,
320 impl<T
: Idx
> SparseBitSet
<T
> {
321 fn new_empty(domain_size
: usize) -> Self {
324 elems
: SmallVec
::new()
328 fn len(&self) -> usize {
332 fn is_empty(&self) -> bool
{
333 self.elems
.len() == 0
336 fn contains(&self, elem
: T
) -> bool
{
337 assert
!(elem
.index() < self.domain_size
);
338 self.elems
.contains(&elem
)
341 fn insert(&mut self, elem
: T
) -> bool
{
342 assert
!(elem
.index() < self.domain_size
);
343 let changed
= if let Some(i
) = self.elems
.iter().position(|&e
| e
>= elem
) {
344 if self.elems
[i
] == elem
{
345 // `elem` is already in the set.
348 // `elem` is smaller than one or more existing elements.
349 self.elems
.insert(i
, elem
);
353 // `elem` is larger than all existing elements.
354 self.elems
.push(elem
);
357 assert
!(self.len() <= SPARSE_MAX
);
361 fn remove(&mut self, elem
: T
) -> bool
{
362 assert
!(elem
.index() < self.domain_size
);
363 if let Some(i
) = self.elems
.iter().position(|&e
| e
== elem
) {
364 self.elems
.remove(i
);
371 fn to_dense(&self) -> BitSet
<T
> {
372 let mut dense
= BitSet
::new_empty(self.domain_size
);
373 for elem
in self.elems
.iter() {
379 fn iter(&self) -> slice
::Iter
<T
> {
384 impl<T
: Idx
> UnionIntoBitSet
<T
> for SparseBitSet
<T
> {
385 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
{
386 assert_eq
!(self.domain_size
, other
.domain_size
);
387 let mut changed
= false;
388 for elem
in self.iter() {
389 changed
|= other
.insert(*elem
);
395 impl<T
: Idx
> SubtractFromBitSet
<T
> for SparseBitSet
<T
> {
396 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
{
397 assert_eq
!(self.domain_size
, other
.domain_size
);
398 let mut changed
= false;
399 for elem
in self.iter() {
400 changed
|= other
.remove(*elem
);
406 /// A fixed-size bitset type with a hybrid representation: sparse when there
407 /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more
408 /// than `SPARSE_MAX`.
410 /// This type is especially efficient for sets that typically have a small
411 /// number of elements, but a large `domain_size`, and are cleared frequently.
413 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
416 /// All operations that involve an element will panic if the element is equal
417 /// to or greater than the domain size. All operations that involve two bitsets
418 /// will panic if the bitsets have differing domain sizes.
419 #[derive(Clone, Debug)]
420 pub enum HybridBitSet
<T
: Idx
> {
421 Sparse(SparseBitSet
<T
>),
425 impl<T
: Idx
> HybridBitSet
<T
> {
426 pub fn new_empty(domain_size
: usize) -> Self {
427 HybridBitSet
::Sparse(SparseBitSet
::new_empty(domain_size
))
430 fn domain_size(&self) -> usize {
432 HybridBitSet
::Sparse(sparse
) => sparse
.domain_size
,
433 HybridBitSet
::Dense(dense
) => dense
.domain_size
,
437 pub fn clear(&mut self) {
438 let domain_size
= self.domain_size();
439 *self = HybridBitSet
::new_empty(domain_size
);
442 pub fn contains(&self, elem
: T
) -> bool
{
444 HybridBitSet
::Sparse(sparse
) => sparse
.contains(elem
),
445 HybridBitSet
::Dense(dense
) => dense
.contains(elem
),
449 pub fn superset(&self, other
: &HybridBitSet
<T
>) -> bool
{
450 match (self, other
) {
451 (HybridBitSet
::Dense(self_dense
), HybridBitSet
::Dense(other_dense
)) => {
452 self_dense
.superset(other_dense
)
455 assert
!(self.domain_size() == other
.domain_size());
456 other
.iter().all(|elem
| self.contains(elem
))
461 pub fn is_empty(&self) -> bool
{
463 HybridBitSet
::Sparse(sparse
) => sparse
.is_empty(),
464 HybridBitSet
::Dense(dense
) => dense
.is_empty(),
468 pub fn insert(&mut self, elem
: T
) -> bool
{
469 // No need to check `elem` against `self.domain_size` here because all
470 // the match cases check it, one way or another.
472 HybridBitSet
::Sparse(sparse
) if sparse
.len() < SPARSE_MAX
=> {
473 // The set is sparse and has space for `elem`.
476 HybridBitSet
::Sparse(sparse
) if sparse
.contains(elem
) => {
477 // The set is sparse and does not have space for `elem`, but
478 // that doesn't matter because `elem` is already present.
481 HybridBitSet
::Sparse(sparse
) => {
482 // The set is sparse and full. Convert to a dense set.
483 let mut dense
= sparse
.to_dense();
484 let changed
= dense
.insert(elem
);
486 *self = HybridBitSet
::Dense(dense
);
489 HybridBitSet
::Dense(dense
) => dense
.insert(elem
),
493 pub fn insert_all(&mut self) {
494 let domain_size
= self.domain_size();
496 HybridBitSet
::Sparse(_
) => {
497 *self = HybridBitSet
::Dense(BitSet
::new_filled(domain_size
));
499 HybridBitSet
::Dense(dense
) => dense
.insert_all(),
503 pub fn remove(&mut self, elem
: T
) -> bool
{
504 // Note: we currently don't bother going from Dense back to Sparse.
506 HybridBitSet
::Sparse(sparse
) => sparse
.remove(elem
),
507 HybridBitSet
::Dense(dense
) => dense
.remove(elem
),
511 pub fn union(&mut self, other
: &HybridBitSet
<T
>) -> bool
{
513 HybridBitSet
::Sparse(self_sparse
) => {
515 HybridBitSet
::Sparse(other_sparse
) => {
516 // Both sets are sparse. Add the elements in
517 // `other_sparse` to `self` one at a time. This
518 // may or may not cause `self` to be densified.
519 assert_eq
!(self.domain_size(), other
.domain_size());
520 let mut changed
= false;
521 for elem
in other_sparse
.iter() {
522 changed
|= self.insert(*elem
);
526 HybridBitSet
::Dense(other_dense
) => {
527 // `self` is sparse and `other` is dense. Densify
528 // `self` and then do the bitwise union.
529 let mut new_dense
= self_sparse
.to_dense();
530 let changed
= new_dense
.union(other_dense
);
531 *self = HybridBitSet
::Dense(new_dense
);
537 HybridBitSet
::Dense(self_dense
) => self_dense
.union(other
),
541 /// Converts to a dense set, consuming itself in the process.
542 pub fn to_dense(self) -> BitSet
<T
> {
544 HybridBitSet
::Sparse(sparse
) => sparse
.to_dense(),
545 HybridBitSet
::Dense(dense
) => dense
,
549 pub fn iter(&self) -> HybridIter
<T
> {
551 HybridBitSet
::Sparse(sparse
) => HybridIter
::Sparse(sparse
.iter()),
552 HybridBitSet
::Dense(dense
) => HybridIter
::Dense(dense
.iter()),
557 impl<T
: Idx
> UnionIntoBitSet
<T
> for HybridBitSet
<T
> {
558 fn union_into(&self, other
: &mut BitSet
<T
>) -> bool
{
560 HybridBitSet
::Sparse(sparse
) => sparse
.union_into(other
),
561 HybridBitSet
::Dense(dense
) => dense
.union_into(other
),
566 impl<T
: Idx
> SubtractFromBitSet
<T
> for HybridBitSet
<T
> {
567 fn subtract_from(&self, other
: &mut BitSet
<T
>) -> bool
{
569 HybridBitSet
::Sparse(sparse
) => sparse
.subtract_from(other
),
570 HybridBitSet
::Dense(dense
) => dense
.subtract_from(other
),
575 pub enum HybridIter
<'a
, T
: Idx
> {
576 Sparse(slice
::Iter
<'a
, T
>),
577 Dense(BitIter
<'a
, T
>),
580 impl<'a
, T
: Idx
> Iterator
for HybridIter
<'a
, T
> {
583 fn next(&mut self) -> Option
<T
> {
585 HybridIter
::Sparse(sparse
) => sparse
.next().map(|e
| *e
),
586 HybridIter
::Dense(dense
) => dense
.next(),
591 /// A resizable bitset type with a dense representation.
593 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
596 /// All operations that involve an element will panic if the element is equal
597 /// to or greater than the domain size.
598 #[derive(Clone, Debug, PartialEq)]
599 pub struct GrowableBitSet
<T
: Idx
> {
603 impl<T
: Idx
> GrowableBitSet
<T
> {
604 /// Ensure that the set can hold at least `min_domain_size` elements.
605 pub fn ensure(&mut self, min_domain_size
: usize) {
606 if self.bit_set
.domain_size
< min_domain_size
{
607 self.bit_set
.domain_size
= min_domain_size
;
610 let min_num_words
= num_words(min_domain_size
);
611 if self.bit_set
.words
.len() < min_num_words
{
612 self.bit_set
.words
.resize(min_num_words
, 0)
616 pub fn new_empty() -> GrowableBitSet
<T
> {
617 GrowableBitSet { bit_set: BitSet::new_empty(0) }
620 pub fn with_capacity(bits
: usize) -> GrowableBitSet
<T
> {
621 GrowableBitSet { bit_set: BitSet::new_empty(bits) }
624 /// Returns true if the set has changed.
626 pub fn insert(&mut self, elem
: T
) -> bool
{
627 self.ensure(elem
.index() + 1);
628 self.bit_set
.insert(elem
)
632 pub fn contains(&self, elem
: T
) -> bool
{
633 let (word_index
, mask
) = word_index_and_mask(elem
);
634 if let Some(word
) = self.bit_set
.words
.get(word_index
) {
642 /// A fixed-size 2D bit matrix type with a dense representation.
644 /// `R` and `C` are index types used to identify rows and columns respectively;
645 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
647 /// All operations that involve a row and/or column index will panic if the
648 /// index exceeds the relevant bound.
649 #[derive(Clone, Debug)]
650 pub struct BitMatrix
<R
: Idx
, C
: Idx
> {
654 marker
: PhantomData
<(R
, C
)>,
657 impl<R
: Idx
, C
: Idx
> BitMatrix
<R
, C
> {
658 /// Create a new `rows x columns` matrix, initially empty.
659 pub fn new(num_rows
: usize, num_columns
: usize) -> BitMatrix
<R
, C
> {
660 // For every element, we need one bit for every other
661 // element. Round up to an even number of words.
662 let words_per_row
= num_words(num_columns
);
666 words
: vec
![0; num_rows
* words_per_row
],
671 /// The range of bits for a given row.
672 fn range(&self, row
: R
) -> (usize, usize) {
673 let words_per_row
= num_words(self.num_columns
);
674 let start
= row
.index() * words_per_row
;
675 (start
, start
+ words_per_row
)
678 /// Sets the cell at `(row, column)` to true. Put another way, insert
679 /// `column` to the bitset for `row`.
681 /// Returns true if this changed the matrix, and false otherwise.
682 pub fn insert(&mut self, row
: R
, column
: C
) -> bool
{
683 assert
!(row
.index() < self.num_rows
&& column
.index() < self.num_columns
);
684 let (start
, _
) = self.range(row
);
685 let (word_index
, mask
) = word_index_and_mask(column
);
686 let words
= &mut self.words
[..];
687 let word
= words
[start
+ word_index
];
688 let new_word
= word
| mask
;
689 words
[start
+ word_index
] = new_word
;
693 /// Do the bits from `row` contain `column`? Put another way, is
694 /// the matrix cell at `(row, column)` true? Put yet another way,
695 /// if the matrix represents (transitive) reachability, can
696 /// `row` reach `column`?
697 pub fn contains(&self, row
: R
, column
: C
) -> bool
{
698 assert
!(row
.index() < self.num_rows
&& column
.index() < self.num_columns
);
699 let (start
, _
) = self.range(row
);
700 let (word_index
, mask
) = word_index_and_mask(column
);
701 (self.words
[start
+ word_index
] & mask
) != 0
704 /// Returns those indices that are true in rows `a` and `b`. This
705 /// is an O(n) operation where `n` is the number of elements
706 /// (somewhat independent from the actual size of the
707 /// intersection, in particular).
708 pub fn intersect_rows(&self, row1
: R
, row2
: R
) -> Vec
<C
> {
709 assert
!(row1
.index() < self.num_rows
&& row2
.index() < self.num_rows
);
710 let (row1_start
, row1_end
) = self.range(row1
);
711 let (row2_start
, row2_end
) = self.range(row2
);
712 let mut result
= Vec
::with_capacity(self.num_columns
);
713 for (base
, (i
, j
)) in (row1_start
..row1_end
).zip(row2_start
..row2_end
).enumerate() {
714 let mut v
= self.words
[i
] & self.words
[j
];
715 for bit
in 0..WORD_BITS
{
720 result
.push(C
::new(base
* WORD_BITS
+ bit
));
728 /// Add the bits from row `read` to the bits from row `write`,
729 /// return true if anything changed.
731 /// This is used when computing transitive reachability because if
732 /// you have an edge `write -> read`, because in that case
733 /// `write` can reach everything that `read` can (and
734 /// potentially more).
735 pub fn union_rows(&mut self, read
: R
, write
: R
) -> bool
{
736 assert
!(read
.index() < self.num_rows
&& write
.index() < self.num_rows
);
737 let (read_start
, read_end
) = self.range(read
);
738 let (write_start
, write_end
) = self.range(write
);
739 let words
= &mut self.words
[..];
740 let mut changed
= false;
741 for (read_index
, write_index
) in (read_start
..read_end
).zip(write_start
..write_end
) {
742 let word
= words
[write_index
];
743 let new_word
= word
| words
[read_index
];
744 words
[write_index
] = new_word
;
745 changed
|= word
!= new_word
;
750 /// Iterates through all the columns set to true in a given row of
752 pub fn iter
<'a
>(&'a
self, row
: R
) -> BitIter
<'a
, C
> {
753 assert
!(row
.index() < self.num_rows
);
754 let (start
, end
) = self.range(row
);
757 iter
: self.words
[start
..end
].iter().enumerate(),
763 /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
764 /// sparse representation.
766 /// Initially, every row has no explicit representation. If any bit within a
767 /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`.
768 /// Furthermore, any previously uninstantiated rows prior to it will be
769 /// instantiated as `None`. Those prior rows may themselves become fully
770 /// instantiated later on if any of their bits are set.
772 /// `R` and `C` are index types used to identify rows and columns respectively;
773 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
774 #[derive(Clone, Debug)]
775 pub struct SparseBitMatrix
<R
, C
>
781 rows
: IndexVec
<R
, Option
<HybridBitSet
<C
>>>,
784 impl<R
: Idx
, C
: Idx
> SparseBitMatrix
<R
, C
> {
785 /// Create a new empty sparse bit matrix with no rows or columns.
786 pub fn new(num_columns
: usize) -> Self {
789 rows
: IndexVec
::new(),
793 fn ensure_row(&mut self, row
: R
) -> &mut HybridBitSet
<C
> {
794 // Instantiate any missing rows up to and including row `row` with an
795 // empty HybridBitSet.
796 self.rows
.ensure_contains_elem(row
, || None
);
798 // Then replace row `row` with a full HybridBitSet if necessary.
799 let num_columns
= self.num_columns
;
800 self.rows
[row
].get_or_insert_with(|| HybridBitSet
::new_empty(num_columns
))
803 /// Sets the cell at `(row, column)` to true. Put another way, insert
804 /// `column` to the bitset for `row`.
806 /// Returns true if this changed the matrix, and false otherwise.
807 pub fn insert(&mut self, row
: R
, column
: C
) -> bool
{
808 self.ensure_row(row
).insert(column
)
811 /// Do the bits from `row` contain `column`? Put another way, is
812 /// the matrix cell at `(row, column)` true? Put yet another way,
813 /// if the matrix represents (transitive) reachability, can
814 /// `row` reach `column`?
815 pub fn contains(&self, row
: R
, column
: C
) -> bool
{
816 self.row(row
).map_or(false, |r
| r
.contains(column
))
819 /// Add the bits from row `read` to the bits from row `write`,
820 /// return true if anything changed.
822 /// This is used when computing transitive reachability because if
823 /// you have an edge `write -> read`, because in that case
824 /// `write` can reach everything that `read` can (and
825 /// potentially more).
826 pub fn union_rows(&mut self, read
: R
, write
: R
) -> bool
{
827 if read
== write
|| self.row(read
).is_none() {
831 self.ensure_row(write
);
832 if let (Some(read_row
), Some(write_row
)) = self.rows
.pick2_mut(read
, write
) {
833 write_row
.union(read_row
)
839 /// Union a row, `from`, into the `into` row.
840 pub fn union_into_row(&mut self, into
: R
, from
: &HybridBitSet
<C
>) -> bool
{
841 self.ensure_row(into
).union(from
)
844 /// Insert all bits in the given row.
845 pub fn insert_all_into_row(&mut self, row
: R
) {
846 self.ensure_row(row
).insert_all();
849 pub fn rows(&self) -> impl Iterator
<Item
= R
> {
853 /// Iterates through all the columns set to true in a given row of
855 pub fn iter
<'a
>(&'a
self, row
: R
) -> impl Iterator
<Item
= C
> + 'a
{
856 self.row(row
).into_iter().flat_map(|r
| r
.iter())
859 pub fn row(&self, row
: R
) -> Option
<&HybridBitSet
<C
>> {
860 if let Some(Some(row
)) = self.rows
.get(row
) {
869 fn num_words
<T
: Idx
>(domain_size
: T
) -> usize {
870 (domain_size
.index() + WORD_BITS
- 1) / WORD_BITS
874 fn word_index_and_mask
<T
: Idx
>(elem
: T
) -> (usize, Word
) {
875 let elem
= elem
.index();
876 let word_index
= elem
/ WORD_BITS
;
877 let mask
= 1 << (elem
% WORD_BITS
);
882 fn test_new_filled() {
884 let idx_buf
= BitSet
::new_filled(i
);
885 let elems
: Vec
<usize> = idx_buf
.iter().collect();
886 let expected
: Vec
<usize> = (0..i
).collect();
887 assert_eq
!(elems
, expected
);
892 fn bitset_iter_works() {
893 let mut bitset
: BitSet
<usize> = BitSet
::new_empty(100);
904 bitset
.iter().collect
::<Vec
<_
>>(),
905 [1, 10, 19, 62, 63, 64, 65, 66, 99]
910 fn bitset_iter_works_2() {
911 let mut bitset
: BitSet
<usize> = BitSet
::new_empty(320);
917 assert_eq
!(bitset
.iter().collect
::<Vec
<_
>>(), [0, 127, 191, 255, 319]);
921 fn union_two_sets() {
922 let mut set1
: BitSet
<usize> = BitSet
::new_empty(65);
923 let mut set2
: BitSet
<usize> = BitSet
::new_empty(65);
924 assert
!(set1
.insert(3));
925 assert
!(!set1
.insert(3));
926 assert
!(set2
.insert(5));
927 assert
!(set2
.insert(64));
928 assert
!(set1
.union(&set2
));
929 assert
!(!set1
.union(&set2
));
930 assert
!(set1
.contains(3));
931 assert
!(!set1
.contains(4));
932 assert
!(set1
.contains(5));
933 assert
!(!set1
.contains(63));
934 assert
!(set1
.contains(64));
939 let mut sparse038
: HybridBitSet
<usize> = HybridBitSet
::new_empty(256);
940 assert
!(sparse038
.is_empty());
941 assert
!(sparse038
.insert(0));
942 assert
!(sparse038
.insert(1));
943 assert
!(sparse038
.insert(8));
944 assert
!(sparse038
.insert(3));
945 assert
!(!sparse038
.insert(3));
946 assert
!(sparse038
.remove(1));
947 assert
!(!sparse038
.is_empty());
948 assert_eq
!(sparse038
.iter().collect
::<Vec
<_
>>(), [0, 3, 8]);
951 if i
== 0 || i
== 3 || i
== 8 {
952 assert
!(sparse038
.contains(i
));
954 assert
!(!sparse038
.contains(i
));
958 let mut sparse01358
= sparse038
.clone();
959 assert
!(sparse01358
.insert(1));
960 assert
!(sparse01358
.insert(5));
961 assert_eq
!(sparse01358
.iter().collect
::<Vec
<_
>>(), [0, 1, 3, 5, 8]);
963 let mut dense10
= HybridBitSet
::new_empty(256);
965 assert
!(dense10
.insert(i
));
967 assert
!(!dense10
.is_empty());
968 assert_eq
!(dense10
.iter().collect
::<Vec
<_
>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
970 let mut dense256
= HybridBitSet
::new_empty(256);
971 assert
!(dense256
.is_empty());
972 dense256
.insert_all();
973 assert
!(!dense256
.is_empty());
975 assert
!(dense256
.contains(i
));
978 assert
!(sparse038
.superset(&sparse038
)); // sparse + sparse (self)
979 assert
!(sparse01358
.superset(&sparse038
)); // sparse + sparse
980 assert
!(dense10
.superset(&sparse038
)); // dense + sparse
981 assert
!(dense10
.superset(&dense10
)); // dense + dense (self)
982 assert
!(dense256
.superset(&dense10
)); // dense + dense
984 let mut hybrid
= sparse038
;
985 assert
!(!sparse01358
.union(&hybrid
)); // no change
986 assert
!(hybrid
.union(&sparse01358
));
987 assert
!(hybrid
.superset(&sparse01358
) && sparse01358
.superset(&hybrid
));
988 assert
!(!dense10
.union(&sparse01358
));
989 assert
!(!dense256
.union(&dense10
));
990 let mut dense
= dense10
;
991 assert
!(dense
.union(&dense256
));
992 assert
!(dense
.superset(&dense256
) && dense256
.superset(&dense
));
993 assert
!(hybrid
.union(&dense256
));
994 assert
!(hybrid
.superset(&dense256
) && dense256
.superset(&hybrid
));
996 assert_eq
!(dense256
.iter().count(), 256);
997 let mut dense0
= dense256
;
999 assert
!(dense0
.remove(i
));
1001 assert
!(!dense0
.remove(0));
1002 assert
!(dense0
.is_empty());
1007 let mut set
: GrowableBitSet
<usize> = GrowableBitSet
::with_capacity(65);
1008 for index
in 0..65 {
1009 assert
!(set
.insert(index
));
1010 assert
!(!set
.insert(index
));
1014 // Check if the bits set before growing are still set
1015 for index
in 0..65 {
1016 assert
!(set
.contains(index
));
1019 // Check if the new bits are all un-set
1020 for index
in 65..128 {
1021 assert
!(!set
.contains(index
));
1024 // Check that we can set all new bits without running out of bounds
1025 for index
in 65..128 {
1026 assert
!(set
.insert(index
));
1027 assert
!(!set
.insert(index
));
1032 fn matrix_intersection() {
1033 let mut matrix
: BitMatrix
<usize, usize> = BitMatrix
::new(200, 200);
1035 // (*) Elements reachable from both 2 and 65.
1037 matrix
.insert(2, 3);
1038 matrix
.insert(2, 6);
1039 matrix
.insert(2, 10); // (*)
1040 matrix
.insert(2, 64); // (*)
1041 matrix
.insert(2, 65);
1042 matrix
.insert(2, 130);
1043 matrix
.insert(2, 160); // (*)
1045 matrix
.insert(64, 133);
1047 matrix
.insert(65, 2);
1048 matrix
.insert(65, 8);
1049 matrix
.insert(65, 10); // (*)
1050 matrix
.insert(65, 64); // (*)
1051 matrix
.insert(65, 68);
1052 matrix
.insert(65, 133);
1053 matrix
.insert(65, 160); // (*)
1055 let intersection
= matrix
.intersect_rows(2, 64);
1056 assert
!(intersection
.is_empty());
1058 let intersection
= matrix
.intersect_rows(2, 65);
1059 assert_eq
!(intersection
, &[10, 64, 160]);
1064 let mut matrix
: BitMatrix
<usize, usize> = BitMatrix
::new(64, 100);
1065 matrix
.insert(3, 22);
1066 matrix
.insert(3, 75);
1067 matrix
.insert(2, 99);
1068 matrix
.insert(4, 0);
1069 matrix
.union_rows(3, 5);
1071 let expected
= [99];
1072 let mut iter
= expected
.iter();
1073 for i
in matrix
.iter(2) {
1074 let j
= *iter
.next().unwrap();
1077 assert
!(iter
.next().is_none());
1079 let expected
= [22, 75];
1080 let mut iter
= expected
.iter();
1081 for i
in matrix
.iter(3) {
1082 let j
= *iter
.next().unwrap();
1085 assert
!(iter
.next().is_none());
1088 let mut iter
= expected
.iter();
1089 for i
in matrix
.iter(4) {
1090 let j
= *iter
.next().unwrap();
1093 assert
!(iter
.next().is_none());
1095 let expected
= [22, 75];
1096 let mut iter
= expected
.iter();
1097 for i
in matrix
.iter(5) {
1098 let j
= *iter
.next().unwrap();
1101 assert
!(iter
.next().is_none());
1105 fn sparse_matrix_iter() {
1106 let mut matrix
: SparseBitMatrix
<usize, usize> = SparseBitMatrix
::new(100);
1107 matrix
.insert(3, 22);
1108 matrix
.insert(3, 75);
1109 matrix
.insert(2, 99);
1110 matrix
.insert(4, 0);
1111 matrix
.union_rows(3, 5);
1113 let expected
= [99];
1114 let mut iter
= expected
.iter();
1115 for i
in matrix
.iter(2) {
1116 let j
= *iter
.next().unwrap();
1119 assert
!(iter
.next().is_none());
1121 let expected
= [22, 75];
1122 let mut iter
= expected
.iter();
1123 for i
in matrix
.iter(3) {
1124 let j
= *iter
.next().unwrap();
1127 assert
!(iter
.next().is_none());
1130 let mut iter
= expected
.iter();
1131 for i
in matrix
.iter(4) {
1132 let j
= *iter
.next().unwrap();
1135 assert
!(iter
.next().is_none());
1137 let expected
= [22, 75];
1138 let mut iter
= expected
.iter();
1139 for i
in matrix
.iter(5) {
1140 let j
= *iter
.next().unwrap();
1143 assert
!(iter
.next().is_none());