pub const WORD_BYTES: usize = mem::size_of::<Word>();
pub const WORD_BITS: usize = WORD_BYTES * 8;
-/// A fixed-size bitset type with a dense representation. It does not support
-/// resizing after creation; use `GrowableBitSet` for that.
+/// A fixed-size bitset type with a dense representation.
+///
+/// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation.
///
/// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
/// just be `usize`.
/// All operations that involve an element will panic if the element is equal
/// to or greater than the domain size. All operations that involve two bitsets
/// will panic if the bitsets have differing domain sizes.
+///
+/// [`GrowableBitSet`]: struct.GrowableBitSet.html
#[derive(Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
pub struct BitSet<T: Idx> {
domain_size: usize,
#[inline]
pub fn new_empty(domain_size: usize) -> BitSet<T> {
let num_words = num_words(domain_size);
- BitSet {
- domain_size,
- words: vec![0; num_words],
- marker: PhantomData,
- }
+ BitSet { domain_size, words: vec![0; num_words], marker: PhantomData }
}
/// Creates a new, filled bitset with a given `domain_size`.
#[inline]
pub fn new_filled(domain_size: usize) -> BitSet<T> {
let num_words = num_words(domain_size);
- let mut result = BitSet {
- domain_size,
- words: vec![!0; num_words],
- marker: PhantomData,
- };
+ let mut result = BitSet { domain_size, words: vec![!0; num_words], marker: PhantomData };
result.clear_excess_bits();
result
}
/// (i.e., if any bits were removed).
pub fn intersect(&mut self, other: &BitSet<T>) -> bool {
assert_eq!(self.domain_size, other.domain_size);
- bitwise(&mut self.words, &other.words, |a, b| { a & b })
+ bitwise(&mut self.words, &other.words, |a, b| a & b)
}
/// Gets a slice of the underlying words.
// Were there any bits in the old word that did not occur in the sparse set?
not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
// Check all words we skipped for any set bit.
- not_already |= self.words[current_index+1..word_index].iter().any(|&x| x != 0);
+ not_already |= self.words[current_index + 1..word_index].iter().any(|&x| x != 0);
// Update next word.
current_index = word_index;
// Reset bit mask, no bits have been merged yet.
// Any bits in the last inspected word that were not in the sparse set?
not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
// Any bits in the tail? Note `clear_excess_bits` before.
- not_already |= self.words[current_index+1..].iter().any(|&x| x != 0);
+ not_already |= self.words[current_index + 1..].iter().any(|&x| x != 0);
not_already
}
impl<T: Idx> UnionIntoBitSet<T> for BitSet<T> {
fn union_into(&self, other: &mut BitSet<T>) -> bool {
assert_eq!(self.domain_size, other.domain_size);
- bitwise(&mut other.words, &self.words, |a, b| { a | b })
+ bitwise(&mut other.words, &self.words, |a, b| a | b)
}
}
impl<T: Idx> SubtractFromBitSet<T> for BitSet<T> {
fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
assert_eq!(self.domain_size, other.domain_size);
- bitwise(&mut other.words, &self.words, |a, b| { a & !b })
+ bitwise(&mut other.words, &self.words, |a, b| a & !b)
}
}
impl<T: Idx> fmt::Debug for BitSet<T> {
fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
- w.debug_list()
- .entries(self.iter())
- .finish()
+ w.debug_list().entries(self.iter()).finish()
}
}
let mut i = 0;
for word in &self.words {
let mut word = *word;
- for _ in 0..WORD_BYTES { // for each byte in `word`:
+ for _ in 0..WORD_BYTES {
+ // for each byte in `word`:
let remain = self.domain_size - i;
// If less than a byte remains, then mask just that many bits.
let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
result.push_str(&format!("{}{:02x}", sep, byte));
- if remain <= 8 { break; }
+ if remain <= 8 {
+ break;
+ }
word >>= 8;
i += 8;
sep = '-';
/// Underlying iterator over the words.
iter: slice::Iter<'a, Word>,
- marker: PhantomData<T>
+ marker: PhantomData<T>,
}
impl<'a, T: Idx> BitIter<'a, T> {
let bit_pos = self.word.trailing_zeros() as usize;
let bit = 1 << bit_pos;
self.word ^= bit;
- return Some(T::new(bit_pos + self.offset))
+ return Some(T::new(bit_pos + self.offset));
}
// Move onto the next word. `wrapping_add()` is needed to handle
#[inline]
fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool
- where Op: Fn(Word, Word) -> Word
+where
+ Op: Fn(Word, Word) -> Word,
{
assert_eq!(out_vec.len(), in_vec.len());
let mut changed = false;
impl<T: Idx> SparseBitSet<T> {
fn new_empty(domain_size: usize) -> Self {
- SparseBitSet {
- domain_size,
- elems: SmallVec::new()
- }
+ SparseBitSet { domain_size, elems: SmallVec::new() }
}
fn len(&self) -> usize {
#[inline]
pub fn contains(&self, elem: T) -> bool {
let (word_index, mask) = word_index_and_mask(elem);
- if let Some(word) = self.bit_set.words.get(word_index) {
- (word & mask) != 0
- } else {
- false
- }
+ if let Some(word) = self.bit_set.words.get(word_index) { (word & mask) != 0 } else { false }
}
}
impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
/// Creates a new empty sparse bit matrix with no rows or columns.
pub fn new(num_columns: usize) -> Self {
- Self {
- num_columns,
- rows: IndexVec::new(),
- }
+ Self { num_columns, rows: IndexVec::new() }
}
fn ensure_row(&mut self, row: R) -> &mut HybridBitSet<C> {
}
pub fn row(&self, row: R) -> Option<&HybridBitSet<C>> {
- if let Some(Some(row)) = self.rows.get(row) {
- Some(row)
- } else {
- None
- }
+ if let Some(Some(row)) = self.rows.get(row) { Some(row) } else { None }
}
}