1 use indexed_vec::{Idx, IndexVec};
2 use smallvec::SmallVec;
5 use std::marker::PhantomData;
10 pub const WORD_BYTES: usize = mem::size_of::<Word>();
11 pub const WORD_BITS: usize = WORD_BYTES * 8;
13 /// A fixed-size bitset type with a dense representation. It does not support
14 /// resizing after creation; use `GrowableBitSet` for that.
16 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
19 /// All operations that involve an element will panic if the element is equal
20 /// to or greater than the domain size. All operations that involve two bitsets
21 /// will panic if the bitsets have differing domain sizes.
22 #[derive(Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
23 pub struct BitSet<T: Idx> {
26 marker: PhantomData<T>,
29 impl<T: Idx> BitSet<T> {
30 /// Create a new, empty bitset with a given `domain_size`.
32 pub fn new_empty(domain_size: usize) -> BitSet<T> {
33 let num_words = num_words(domain_size);
36 words: vec![0; num_words],
41 /// Create a new, filled bitset with a given `domain_size`.
43 pub fn new_filled(domain_size: usize) -> BitSet<T> {
44 let num_words = num_words(domain_size);
45 let mut result = BitSet {
47 words: vec![!0; num_words],
50 result.clear_excess_bits();
54 /// Get the domain size.
55 pub fn domain_size(&self) -> usize {
59 /// Clear all elements.
61 pub fn clear(&mut self) {
62 for word in &mut self.words {
67 /// Clear excess bits in the final word.
68 fn clear_excess_bits(&mut self) {
69 let num_bits_in_final_word = self.domain_size % WORD_BITS;
70 if num_bits_in_final_word > 0 {
71 let mask = (1 << num_bits_in_final_word) - 1;
72 let final_word_idx = self.words.len() - 1;
73 self.words[final_word_idx] &= mask;
77 /// Efficiently overwrite `self` with `other`.
78 pub fn overwrite(&mut self, other: &BitSet<T>) {
79 assert!(self.domain_size == other.domain_size);
80 self.words.clone_from_slice(&other.words);
83 /// Count the number of set bits in the set.
84 pub fn count(&self) -> usize {
85 self.words.iter().map(|e| e.count_ones() as usize).sum()
88 /// True if `self` contains `elem`.
90 pub fn contains(&self, elem: T) -> bool {
91 assert!(elem.index() < self.domain_size);
92 let (word_index, mask) = word_index_and_mask(elem);
93 (self.words[word_index] & mask) != 0
96 /// Is `self` is a (non-strict) superset of `other`?
98 pub fn superset(&self, other: &BitSet<T>) -> bool {
99 assert_eq!(self.domain_size, other.domain_size);
100 self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b)
103 /// Is the set empty?
105 pub fn is_empty(&self) -> bool {
106 self.words.iter().all(|a| *a == 0)
109 /// Insert `elem`. Returns true if the set has changed.
111 pub fn insert(&mut self, elem: T) -> bool {
112 assert!(elem.index() < self.domain_size);
113 let (word_index, mask) = word_index_and_mask(elem);
114 let word_ref = &mut self.words[word_index];
115 let word = *word_ref;
116 let new_word = word | mask;
117 *word_ref = new_word;
121 /// Sets all bits to true.
122 pub fn insert_all(&mut self) {
123 for word in &mut self.words {
126 self.clear_excess_bits();
129 /// Returns true if the set has changed.
131 pub fn remove(&mut self, elem: T) -> bool {
132 assert!(elem.index() < self.domain_size);
133 let (word_index, mask) = word_index_and_mask(elem);
134 let word_ref = &mut self.words[word_index];
135 let word = *word_ref;
136 let new_word = word & !mask;
137 *word_ref = new_word;
141 /// Set `self = self | other` and return true if `self` changed
142 /// (i.e., if new bits were added).
143 pub fn union(&mut self, other: &impl UnionIntoBitSet<T>) -> bool {
144 other.union_into(self)
147 /// Set `self = self - other` and return true if `self` changed.
148 /// (i.e., if any bits were removed).
149 pub fn subtract(&mut self, other: &impl SubtractFromBitSet<T>) -> bool {
150 other.subtract_from(self)
153 /// Set `self = self & other` and return true if `self` changed.
154 /// (i.e., if any bits were removed).
155 pub fn intersect(&mut self, other: &BitSet<T>) -> bool {
156 assert_eq!(self.domain_size, other.domain_size);
157 bitwise(&mut self.words, &other.words, |a, b| { a & b })
160 /// Get a slice of the underlying words.
161 pub fn words(&self) -> &[Word] {
165 /// Iterates over the indices of set bits in a sorted order.
167 pub fn iter<'a>(&'a self) -> BitIter<'a, T> {
170 iter: self.words.iter().enumerate(),
175 /// Duplicates the set as a hybrid set.
176 pub fn to_hybrid(&self) -> HybridBitSet<T> {
177 // Note: we currently don't bother trying to make a Sparse set.
178 HybridBitSet::Dense(self.to_owned())
182 /// This is implemented by all the bitsets so that BitSet::union() can be
183 /// passed any type of bitset.
184 pub trait UnionIntoBitSet<T: Idx> {
185 // Performs `other = other | self`.
186 fn union_into(&self, other: &mut BitSet<T>) -> bool;
189 /// This is implemented by all the bitsets so that BitSet::subtract() can be
190 /// passed any type of bitset.
191 pub trait SubtractFromBitSet<T: Idx> {
192 // Performs `other = other - self`.
193 fn subtract_from(&self, other: &mut BitSet<T>) -> bool;
196 impl<T: Idx> UnionIntoBitSet<T> for BitSet<T> {
197 fn union_into(&self, other: &mut BitSet<T>) -> bool {
198 assert_eq!(self.domain_size, other.domain_size);
199 bitwise(&mut other.words, &self.words, |a, b| { a | b })
203 impl<T: Idx> SubtractFromBitSet<T> for BitSet<T> {
204 fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
205 assert_eq!(self.domain_size, other.domain_size);
206 bitwise(&mut other.words, &self.words, |a, b| { a & !b })
210 impl<T: Idx> fmt::Debug for BitSet<T> {
211 fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
213 .entries(self.iter())
218 impl<T: Idx> ToString for BitSet<T> {
219 fn to_string(&self) -> String {
220 let mut result = String::new();
223 // Note: this is a little endian printout of bytes.
225 // i tracks how many bits we have printed so far.
227 for word in &self.words {
228 let mut word = *word;
229 for _ in 0..WORD_BYTES { // for each byte in `word`:
230 let remain = self.domain_size - i;
231 // If less than a byte remains, then mask just that many bits.
232 let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
233 assert!(mask <= 0xFF);
234 let byte = word & mask;
236 result.push_str(&format!("{}{:02x}", sep, byte));
238 if remain <= 8 { break; }
251 pub struct BitIter<'a, T: Idx> {
252 cur: Option<(Word, usize)>,
253 iter: iter::Enumerate<slice::Iter<'a, Word>>,
254 marker: PhantomData<T>
257 impl<'a, T: Idx> Iterator for BitIter<'a, T> {
259 fn next(&mut self) -> Option<T> {
261 if let Some((ref mut word, offset)) = self.cur {
262 let bit_pos = word.trailing_zeros() as usize;
263 if bit_pos != WORD_BITS {
264 let bit = 1 << bit_pos;
266 return Some(T::new(bit_pos + offset))
270 let (i, word) = self.iter.next()?;
271 self.cur = Some((*word, WORD_BITS * i));
276 pub trait BitSetOperator {
277 /// Combine one bitset into another.
278 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool;
282 fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool
283 where Op: Fn(Word, Word) -> Word
285 assert_eq!(out_vec.len(), in_vec.len());
286 let mut changed = false;
287 for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec.iter()) {
288 let old_val = *out_elem;
289 let new_val = op(old_val, *in_elem);
291 changed |= old_val != new_val;
296 const SPARSE_MAX: usize = 8;
298 /// A fixed-size bitset type with a sparse representation and a maximum of
299 /// `SPARSE_MAX` elements. The elements are stored as a sorted `SmallVec` with
300 /// no duplicates; although `SmallVec` can spill its elements to the heap, that
301 /// never happens within this type because of the `SPARSE_MAX` limit.
303 /// This type is used by `HybridBitSet`; do not use directly.
304 #[derive(Clone, Debug)]
305 pub struct SparseBitSet<T: Idx> {
307 elems: SmallVec<[T; SPARSE_MAX]>,
310 impl<T: Idx> SparseBitSet<T> {
311 fn new_empty(domain_size: usize) -> Self {
314 elems: SmallVec::new()
318 fn len(&self) -> usize {
322 fn is_empty(&self) -> bool {
323 self.elems.len() == 0
326 fn contains(&self, elem: T) -> bool {
327 assert!(elem.index() < self.domain_size);
328 self.elems.contains(&elem)
331 fn insert(&mut self, elem: T) -> bool {
332 assert!(elem.index() < self.domain_size);
333 let changed = if let Some(i) = self.elems.iter().position(|&e| e >= elem) {
334 if self.elems[i] == elem {
335 // `elem` is already in the set.
338 // `elem` is smaller than one or more existing elements.
339 self.elems.insert(i, elem);
343 // `elem` is larger than all existing elements.
344 self.elems.push(elem);
347 assert!(self.len() <= SPARSE_MAX);
351 fn remove(&mut self, elem: T) -> bool {
352 assert!(elem.index() < self.domain_size);
353 if let Some(i) = self.elems.iter().position(|&e| e == elem) {
354 self.elems.remove(i);
361 fn to_dense(&self) -> BitSet<T> {
362 let mut dense = BitSet::new_empty(self.domain_size);
363 for elem in self.elems.iter() {
369 fn iter(&self) -> slice::Iter<T> {
374 impl<T: Idx> UnionIntoBitSet<T> for SparseBitSet<T> {
375 fn union_into(&self, other: &mut BitSet<T>) -> bool {
376 assert_eq!(self.domain_size, other.domain_size);
377 let mut changed = false;
378 for elem in self.iter() {
379 changed |= other.insert(*elem);
385 impl<T: Idx> SubtractFromBitSet<T> for SparseBitSet<T> {
386 fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
387 assert_eq!(self.domain_size, other.domain_size);
388 let mut changed = false;
389 for elem in self.iter() {
390 changed |= other.remove(*elem);
396 /// A fixed-size bitset type with a hybrid representation: sparse when there
397 /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more
398 /// than `SPARSE_MAX`.
400 /// This type is especially efficient for sets that typically have a small
401 /// number of elements, but a large `domain_size`, and are cleared frequently.
403 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
406 /// All operations that involve an element will panic if the element is equal
407 /// to or greater than the domain size. All operations that involve two bitsets
408 /// will panic if the bitsets have differing domain sizes.
409 #[derive(Clone, Debug)]
410 pub enum HybridBitSet<T: Idx> {
411 Sparse(SparseBitSet<T>),
415 impl<T: Idx> HybridBitSet<T> {
416 pub fn new_empty(domain_size: usize) -> Self {
417 HybridBitSet::Sparse(SparseBitSet::new_empty(domain_size))
420 fn domain_size(&self) -> usize {
422 HybridBitSet::Sparse(sparse) => sparse.domain_size,
423 HybridBitSet::Dense(dense) => dense.domain_size,
427 pub fn clear(&mut self) {
428 let domain_size = self.domain_size();
429 *self = HybridBitSet::new_empty(domain_size);
432 pub fn contains(&self, elem: T) -> bool {
434 HybridBitSet::Sparse(sparse) => sparse.contains(elem),
435 HybridBitSet::Dense(dense) => dense.contains(elem),
439 pub fn superset(&self, other: &HybridBitSet<T>) -> bool {
440 match (self, other) {
441 (HybridBitSet::Dense(self_dense), HybridBitSet::Dense(other_dense)) => {
442 self_dense.superset(other_dense)
445 assert!(self.domain_size() == other.domain_size());
446 other.iter().all(|elem| self.contains(elem))
451 pub fn is_empty(&self) -> bool {
453 HybridBitSet::Sparse(sparse) => sparse.is_empty(),
454 HybridBitSet::Dense(dense) => dense.is_empty(),
458 pub fn insert(&mut self, elem: T) -> bool {
459 // No need to check `elem` against `self.domain_size` here because all
460 // the match cases check it, one way or another.
462 HybridBitSet::Sparse(sparse) if sparse.len() < SPARSE_MAX => {
463 // The set is sparse and has space for `elem`.
466 HybridBitSet::Sparse(sparse) if sparse.contains(elem) => {
467 // The set is sparse and does not have space for `elem`, but
468 // that doesn't matter because `elem` is already present.
471 HybridBitSet::Sparse(sparse) => {
472 // The set is sparse and full. Convert to a dense set.
473 let mut dense = sparse.to_dense();
474 let changed = dense.insert(elem);
476 *self = HybridBitSet::Dense(dense);
479 HybridBitSet::Dense(dense) => dense.insert(elem),
483 pub fn insert_all(&mut self) {
484 let domain_size = self.domain_size();
486 HybridBitSet::Sparse(_) => {
487 *self = HybridBitSet::Dense(BitSet::new_filled(domain_size));
489 HybridBitSet::Dense(dense) => dense.insert_all(),
493 pub fn remove(&mut self, elem: T) -> bool {
494 // Note: we currently don't bother going from Dense back to Sparse.
496 HybridBitSet::Sparse(sparse) => sparse.remove(elem),
497 HybridBitSet::Dense(dense) => dense.remove(elem),
501 pub fn union(&mut self, other: &HybridBitSet<T>) -> bool {
503 HybridBitSet::Sparse(self_sparse) => {
505 HybridBitSet::Sparse(other_sparse) => {
506 // Both sets are sparse. Add the elements in
507 // `other_sparse` to `self` one at a time. This
508 // may or may not cause `self` to be densified.
509 assert_eq!(self.domain_size(), other.domain_size());
510 let mut changed = false;
511 for elem in other_sparse.iter() {
512 changed |= self.insert(*elem);
516 HybridBitSet::Dense(other_dense) => {
517 // `self` is sparse and `other` is dense. Densify
518 // `self` and then do the bitwise union.
519 let mut new_dense = self_sparse.to_dense();
520 let changed = new_dense.union(other_dense);
521 *self = HybridBitSet::Dense(new_dense);
527 HybridBitSet::Dense(self_dense) => self_dense.union(other),
531 /// Converts to a dense set, consuming itself in the process.
532 pub fn to_dense(self) -> BitSet<T> {
534 HybridBitSet::Sparse(sparse) => sparse.to_dense(),
535 HybridBitSet::Dense(dense) => dense,
539 pub fn iter(&self) -> HybridIter<T> {
541 HybridBitSet::Sparse(sparse) => HybridIter::Sparse(sparse.iter()),
542 HybridBitSet::Dense(dense) => HybridIter::Dense(dense.iter()),
547 impl<T: Idx> UnionIntoBitSet<T> for HybridBitSet<T> {
548 fn union_into(&self, other: &mut BitSet<T>) -> bool {
550 HybridBitSet::Sparse(sparse) => sparse.union_into(other),
551 HybridBitSet::Dense(dense) => dense.union_into(other),
556 impl<T: Idx> SubtractFromBitSet<T> for HybridBitSet<T> {
557 fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
559 HybridBitSet::Sparse(sparse) => sparse.subtract_from(other),
560 HybridBitSet::Dense(dense) => dense.subtract_from(other),
565 pub enum HybridIter<'a, T: Idx> {
566 Sparse(slice::Iter<'a, T>),
567 Dense(BitIter<'a, T>),
570 impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
573 fn next(&mut self) -> Option<T> {
575 HybridIter::Sparse(sparse) => sparse.next().map(|e| *e),
576 HybridIter::Dense(dense) => dense.next(),
581 /// A resizable bitset type with a dense representation.
583 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
586 /// All operations that involve an element will panic if the element is equal
587 /// to or greater than the domain size.
588 #[derive(Clone, Debug, PartialEq)]
589 pub struct GrowableBitSet<T: Idx> {
593 impl<T: Idx> GrowableBitSet<T> {
594 /// Ensure that the set can hold at least `min_domain_size` elements.
595 pub fn ensure(&mut self, min_domain_size: usize) {
596 if self.bit_set.domain_size < min_domain_size {
597 self.bit_set.domain_size = min_domain_size;
600 let min_num_words = num_words(min_domain_size);
601 if self.bit_set.words.len() < min_num_words {
602 self.bit_set.words.resize(min_num_words, 0)
606 pub fn new_empty() -> GrowableBitSet<T> {
607 GrowableBitSet { bit_set: BitSet::new_empty(0) }
610 pub fn with_capacity(bits: usize) -> GrowableBitSet<T> {
611 GrowableBitSet { bit_set: BitSet::new_empty(bits) }
614 /// Returns true if the set has changed.
616 pub fn insert(&mut self, elem: T) -> bool {
617 self.ensure(elem.index() + 1);
618 self.bit_set.insert(elem)
622 pub fn contains(&self, elem: T) -> bool {
623 let (word_index, mask) = word_index_and_mask(elem);
624 if let Some(word) = self.bit_set.words.get(word_index) {
632 /// A fixed-size 2D bit matrix type with a dense representation.
634 /// `R` and `C` are index types used to identify rows and columns respectively;
635 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
637 /// All operations that involve a row and/or column index will panic if the
638 /// index exceeds the relevant bound.
639 #[derive(Clone, Debug)]
640 pub struct BitMatrix<R: Idx, C: Idx> {
644 marker: PhantomData<(R, C)>,
647 impl<R: Idx, C: Idx> BitMatrix<R, C> {
648 /// Create a new `rows x columns` matrix, initially empty.
649 pub fn new(num_rows: usize, num_columns: usize) -> BitMatrix<R, C> {
650 // For every element, we need one bit for every other
651 // element. Round up to an even number of words.
652 let words_per_row = num_words(num_columns);
656 words: vec![0; num_rows * words_per_row],
661 /// The range of bits for a given row.
662 fn range(&self, row: R) -> (usize, usize) {
663 let words_per_row = num_words(self.num_columns);
664 let start = row.index() * words_per_row;
665 (start, start + words_per_row)
668 /// Sets the cell at `(row, column)` to true. Put another way, insert
669 /// `column` to the bitset for `row`.
671 /// Returns true if this changed the matrix, and false otherwise.
672 pub fn insert(&mut self, row: R, column: C) -> bool {
673 assert!(row.index() < self.num_rows && column.index() < self.num_columns);
674 let (start, _) = self.range(row);
675 let (word_index, mask) = word_index_and_mask(column);
676 let words = &mut self.words[..];
677 let word = words[start + word_index];
678 let new_word = word | mask;
679 words[start + word_index] = new_word;
683 /// Do the bits from `row` contain `column`? Put another way, is
684 /// the matrix cell at `(row, column)` true? Put yet another way,
685 /// if the matrix represents (transitive) reachability, can
686 /// `row` reach `column`?
687 pub fn contains(&self, row: R, column: C) -> bool {
688 assert!(row.index() < self.num_rows && column.index() < self.num_columns);
689 let (start, _) = self.range(row);
690 let (word_index, mask) = word_index_and_mask(column);
691 (self.words[start + word_index] & mask) != 0
694 /// Returns those indices that are true in rows `a` and `b`. This
695 /// is an O(n) operation where `n` is the number of elements
696 /// (somewhat independent from the actual size of the
697 /// intersection, in particular).
698 pub fn intersect_rows(&self, row1: R, row2: R) -> Vec<C> {
699 assert!(row1.index() < self.num_rows && row2.index() < self.num_rows);
700 let (row1_start, row1_end) = self.range(row1);
701 let (row2_start, row2_end) = self.range(row2);
702 let mut result = Vec::with_capacity(self.num_columns);
703 for (base, (i, j)) in (row1_start..row1_end).zip(row2_start..row2_end).enumerate() {
704 let mut v = self.words[i] & self.words[j];
705 for bit in 0..WORD_BITS {
710 result.push(C::new(base * WORD_BITS + bit));
718 /// Add the bits from row `read` to the bits from row `write`,
719 /// return true if anything changed.
721 /// This is used when computing transitive reachability because if
722 /// you have an edge `write -> read`, because in that case
723 /// `write` can reach everything that `read` can (and
724 /// potentially more).
725 pub fn union_rows(&mut self, read: R, write: R) -> bool {
726 assert!(read.index() < self.num_rows && write.index() < self.num_rows);
727 let (read_start, read_end) = self.range(read);
728 let (write_start, write_end) = self.range(write);
729 let words = &mut self.words[..];
730 let mut changed = false;
731 for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
732 let word = words[write_index];
733 let new_word = word | words[read_index];
734 words[write_index] = new_word;
735 changed |= word != new_word;
740 /// Iterates through all the columns set to true in a given row of
742 pub fn iter<'a>(&'a self, row: R) -> BitIter<'a, C> {
743 assert!(row.index() < self.num_rows);
744 let (start, end) = self.range(row);
747 iter: self.words[start..end].iter().enumerate(),
753 /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
754 /// sparse representation.
756 /// Initially, every row has no explicit representation. If any bit within a
757 /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`.
758 /// Furthermore, any previously uninstantiated rows prior to it will be
759 /// instantiated as `None`. Those prior rows may themselves become fully
760 /// instantiated later on if any of their bits are set.
762 /// `R` and `C` are index types used to identify rows and columns respectively;
763 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
764 #[derive(Clone, Debug)]
765 pub struct SparseBitMatrix<R, C>
771 rows: IndexVec<R, Option<HybridBitSet<C>>>,
774 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
775 /// Create a new empty sparse bit matrix with no rows or columns.
776 pub fn new(num_columns: usize) -> Self {
779 rows: IndexVec::new(),
783 fn ensure_row(&mut self, row: R) -> &mut HybridBitSet<C> {
784 // Instantiate any missing rows up to and including row `row` with an
785 // empty HybridBitSet.
786 self.rows.ensure_contains_elem(row, || None);
788 // Then replace row `row` with a full HybridBitSet if necessary.
789 let num_columns = self.num_columns;
790 self.rows[row].get_or_insert_with(|| HybridBitSet::new_empty(num_columns))
793 /// Sets the cell at `(row, column)` to true. Put another way, insert
794 /// `column` to the bitset for `row`.
796 /// Returns true if this changed the matrix, and false otherwise.
797 pub fn insert(&mut self, row: R, column: C) -> bool {
798 self.ensure_row(row).insert(column)
801 /// Do the bits from `row` contain `column`? Put another way, is
802 /// the matrix cell at `(row, column)` true? Put yet another way,
803 /// if the matrix represents (transitive) reachability, can
804 /// `row` reach `column`?
805 pub fn contains(&self, row: R, column: C) -> bool {
806 self.row(row).map_or(false, |r| r.contains(column))
809 /// Add the bits from row `read` to the bits from row `write`,
810 /// return true if anything changed.
812 /// This is used when computing transitive reachability because if
813 /// you have an edge `write -> read`, because in that case
814 /// `write` can reach everything that `read` can (and
815 /// potentially more).
816 pub fn union_rows(&mut self, read: R, write: R) -> bool {
817 if read == write || self.row(read).is_none() {
821 self.ensure_row(write);
822 if let (Some(read_row), Some(write_row)) = self.rows.pick2_mut(read, write) {
823 write_row.union(read_row)
829 /// Union a row, `from`, into the `into` row.
830 pub fn union_into_row(&mut self, into: R, from: &HybridBitSet<C>) -> bool {
831 self.ensure_row(into).union(from)
834 /// Insert all bits in the given row.
835 pub fn insert_all_into_row(&mut self, row: R) {
836 self.ensure_row(row).insert_all();
839 pub fn rows(&self) -> impl Iterator<Item = R> {
843 /// Iterates through all the columns set to true in a given row of
845 pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
846 self.row(row).into_iter().flat_map(|r| r.iter())
849 pub fn row(&self, row: R) -> Option<&HybridBitSet<C>> {
850 if let Some(Some(row)) = self.rows.get(row) {
859 fn num_words<T: Idx>(domain_size: T) -> usize {
860 (domain_size.index() + WORD_BITS - 1) / WORD_BITS
864 fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) {
865 let elem = elem.index();
866 let word_index = elem / WORD_BITS;
867 let mask = 1 << (elem % WORD_BITS);
872 fn test_new_filled() {
874 let idx_buf = BitSet::new_filled(i);
875 let elems: Vec<usize> = idx_buf.iter().collect();
876 let expected: Vec<usize> = (0..i).collect();
877 assert_eq!(elems, expected);
882 fn bitset_iter_works() {
883 let mut bitset: BitSet<usize> = BitSet::new_empty(100);
894 bitset.iter().collect::<Vec<_>>(),
895 [1, 10, 19, 62, 63, 64, 65, 66, 99]
900 fn bitset_iter_works_2() {
901 let mut bitset: BitSet<usize> = BitSet::new_empty(320);
907 assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
911 fn union_two_sets() {
912 let mut set1: BitSet<usize> = BitSet::new_empty(65);
913 let mut set2: BitSet<usize> = BitSet::new_empty(65);
914 assert!(set1.insert(3));
915 assert!(!set1.insert(3));
916 assert!(set2.insert(5));
917 assert!(set2.insert(64));
918 assert!(set1.union(&set2));
919 assert!(!set1.union(&set2));
920 assert!(set1.contains(3));
921 assert!(!set1.contains(4));
922 assert!(set1.contains(5));
923 assert!(!set1.contains(63));
924 assert!(set1.contains(64));
929 let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
930 assert!(sparse038.is_empty());
931 assert!(sparse038.insert(0));
932 assert!(sparse038.insert(1));
933 assert!(sparse038.insert(8));
934 assert!(sparse038.insert(3));
935 assert!(!sparse038.insert(3));
936 assert!(sparse038.remove(1));
937 assert!(!sparse038.is_empty());
938 assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
941 if i == 0 || i == 3 || i == 8 {
942 assert!(sparse038.contains(i));
944 assert!(!sparse038.contains(i));
948 let mut sparse01358 = sparse038.clone();
949 assert!(sparse01358.insert(1));
950 assert!(sparse01358.insert(5));
951 assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
953 let mut dense10 = HybridBitSet::new_empty(256);
955 assert!(dense10.insert(i));
957 assert!(!dense10.is_empty());
958 assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
960 let mut dense256 = HybridBitSet::new_empty(256);
961 assert!(dense256.is_empty());
962 dense256.insert_all();
963 assert!(!dense256.is_empty());
965 assert!(dense256.contains(i));
968 assert!(sparse038.superset(&sparse038)); // sparse + sparse (self)
969 assert!(sparse01358.superset(&sparse038)); // sparse + sparse
970 assert!(dense10.superset(&sparse038)); // dense + sparse
971 assert!(dense10.superset(&dense10)); // dense + dense (self)
972 assert!(dense256.superset(&dense10)); // dense + dense
974 let mut hybrid = sparse038;
975 assert!(!sparse01358.union(&hybrid)); // no change
976 assert!(hybrid.union(&sparse01358));
977 assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
978 assert!(!dense10.union(&sparse01358));
979 assert!(!dense256.union(&dense10));
980 let mut dense = dense10;
981 assert!(dense.union(&dense256));
982 assert!(dense.superset(&dense256) && dense256.superset(&dense));
983 assert!(hybrid.union(&dense256));
984 assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
986 assert_eq!(dense256.iter().count(), 256);
987 let mut dense0 = dense256;
989 assert!(dense0.remove(i));
991 assert!(!dense0.remove(0));
992 assert!(dense0.is_empty());
997 let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
999 assert!(set.insert(index));
1000 assert!(!set.insert(index));
1004 // Check if the bits set before growing are still set
1005 for index in 0..65 {
1006 assert!(set.contains(index));
1009 // Check if the new bits are all un-set
1010 for index in 65..128 {
1011 assert!(!set.contains(index));
1014 // Check that we can set all new bits without running out of bounds
1015 for index in 65..128 {
1016 assert!(set.insert(index));
1017 assert!(!set.insert(index));
1022 fn matrix_intersection() {
1023 let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
1025 // (*) Elements reachable from both 2 and 65.
1027 matrix.insert(2, 3);
1028 matrix.insert(2, 6);
1029 matrix.insert(2, 10); // (*)
1030 matrix.insert(2, 64); // (*)
1031 matrix.insert(2, 65);
1032 matrix.insert(2, 130);
1033 matrix.insert(2, 160); // (*)
1035 matrix.insert(64, 133);
1037 matrix.insert(65, 2);
1038 matrix.insert(65, 8);
1039 matrix.insert(65, 10); // (*)
1040 matrix.insert(65, 64); // (*)
1041 matrix.insert(65, 68);
1042 matrix.insert(65, 133);
1043 matrix.insert(65, 160); // (*)
1045 let intersection = matrix.intersect_rows(2, 64);
1046 assert!(intersection.is_empty());
1048 let intersection = matrix.intersect_rows(2, 65);
1049 assert_eq!(intersection, &[10, 64, 160]);
1054 let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
1055 matrix.insert(3, 22);
1056 matrix.insert(3, 75);
1057 matrix.insert(2, 99);
1058 matrix.insert(4, 0);
1059 matrix.union_rows(3, 5);
1061 let expected = [99];
1062 let mut iter = expected.iter();
1063 for i in matrix.iter(2) {
1064 let j = *iter.next().unwrap();
1067 assert!(iter.next().is_none());
1069 let expected = [22, 75];
1070 let mut iter = expected.iter();
1071 for i in matrix.iter(3) {
1072 let j = *iter.next().unwrap();
1075 assert!(iter.next().is_none());
1078 let mut iter = expected.iter();
1079 for i in matrix.iter(4) {
1080 let j = *iter.next().unwrap();
1083 assert!(iter.next().is_none());
1085 let expected = [22, 75];
1086 let mut iter = expected.iter();
1087 for i in matrix.iter(5) {
1088 let j = *iter.next().unwrap();
1091 assert!(iter.next().is_none());
1095 fn sparse_matrix_iter() {
1096 let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
1097 matrix.insert(3, 22);
1098 matrix.insert(3, 75);
1099 matrix.insert(2, 99);
1100 matrix.insert(4, 0);
1101 matrix.union_rows(3, 5);
1103 let expected = [99];
1104 let mut iter = expected.iter();
1105 for i in matrix.iter(2) {
1106 let j = *iter.next().unwrap();
1109 assert!(iter.next().is_none());
1111 let expected = [22, 75];
1112 let mut iter = expected.iter();
1113 for i in matrix.iter(3) {
1114 let j = *iter.next().unwrap();
1117 assert!(iter.next().is_none());
1120 let mut iter = expected.iter();
1121 for i in matrix.iter(4) {
1122 let j = *iter.next().unwrap();
1125 assert!(iter.next().is_none());
1127 let expected = [22, 75];
1128 let mut iter = expected.iter();
1129 for i in matrix.iter(5) {
1130 let j = *iter.next().unwrap();
1133 assert!(iter.next().is_none());