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());