use indexed_vec::{Idx, IndexVec};
use std::iter::FromIterator;
use std::marker::PhantomData;
type Word = u128;
const WORD_BITS: usize = 128;
#[derive(Clone, Debug, PartialEq)]
pub struct BitVector<C: Idx> {
data: Vec<Word>,
marker: PhantomData<C>,
}
impl<C: Idx> BitVector<C> {
#[inline]
pub fn new(num_bits: usize) -> BitVector<C> {
let num_words = words(num_bits);
BitVector {
data: vec![0; num_words],
marker: PhantomData,
}
}
#[inline]
pub fn clear(&mut self) {
for p in &mut self.data {
*p = 0;
}
}
pub fn count(&self) -> usize {
self.data.iter().map(|e| e.count_ones() as usize).sum()
}
#[inline]
pub fn contains(&self, bit: C) -> bool {
let (word, mask) = word_mask(bit);
(self.data[word] & mask) != 0
}
#[inline]
pub fn contains_all(&self, other: &BitVector<C>) -> bool {
assert_eq!(self.data.len(), other.data.len());
self.data.iter().zip(&other.data).all(|(a, b)| (a & b) == *b)
}
#[inline]
pub fn is_empty(&self) -> bool {
self.data.iter().all(|a| *a == 0)
}
#[inline]
pub fn insert(&mut self, bit: C) -> bool {
let (word, mask) = word_mask(bit);
let data = &mut self.data[word];
let value = *data;
let new_value = value | mask;
*data = new_value;
new_value != value
}
pub fn insert_all(&mut self) {
for data in &mut self.data {
*data = u128::max_value();
}
}
#[inline]
pub fn remove(&mut self, bit: C) -> bool {
let (word, mask) = word_mask(bit);
let data = &mut self.data[word];
let value = *data;
let new_value = value & !mask;
*data = new_value;
new_value != value
}
#[inline]
pub fn merge(&mut self, all: &BitVector<C>) -> bool {
assert!(self.data.len() == all.data.len());
let mut changed = false;
for (i, j) in self.data.iter_mut().zip(&all.data) {
let value = *i;
*i = value | *j;
if value != *i {
changed = true;
}
}
changed
}
#[inline]
pub fn grow(&mut self, num_bits: C) {
let num_words = words(num_bits);
if self.data.len() < num_words {
self.data.resize(num_words, 0)
}
}
#[inline]
pub fn iter<'a>(&'a self) -> BitVectorIter<'a, C> {
BitVectorIter {
iter: self.data.iter(),
current: 0,
idx: 0,
marker: PhantomData,
}
}
}
pub struct BitVectorIter<'a, C: Idx> {
iter: ::std::slice::Iter<'a, Word>,
current: Word,
idx: usize,
marker: PhantomData<C>
}
impl<'a, C: Idx> Iterator for BitVectorIter<'a, C> {
type Item = C;
fn next(&mut self) -> Option<C> {
while self.current == 0 {
self.current = if let Some(&i) = self.iter.next() {
if i == 0 {
self.idx += WORD_BITS;
continue;
} else {
self.idx = words(self.idx) * WORD_BITS;
i
}
} else {
return None;
}
}
let offset = self.current.trailing_zeros() as usize;
self.current >>= offset;
self.current >>= 1; self.idx += offset + 1;
return Some(C::new(self.idx - 1));
}
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
}
impl<C: Idx> FromIterator<bool> for BitVector<C> {
fn from_iter<I>(iter: I) -> BitVector<C>
where
I: IntoIterator<Item = bool>,
{
let iter = iter.into_iter();
let (len, _) = iter.size_hint();
let len = if len < WORD_BITS { WORD_BITS } else { len };
let mut bv = BitVector::new(len);
for (idx, val) in iter.enumerate() {
if idx > len {
bv.grow(C::new(idx));
}
if val {
bv.insert(C::new(idx));
}
}
bv
}
}
#[derive(Clone, Debug)]
pub struct BitMatrix<R: Idx, C: Idx> {
columns: usize,
vector: Vec<Word>,
phantom: PhantomData<(R, C)>,
}
impl<R: Idx, C: Idx> BitMatrix<R, C> {
pub fn new(rows: usize, columns: usize) -> BitMatrix<R, C> {
let words_per_row = words(columns);
BitMatrix {
columns,
vector: vec![0; rows * words_per_row],
phantom: PhantomData,
}
}
fn range(&self, row: R) -> (usize, usize) {
let row = row.index();
let words_per_row = words(self.columns);
let start = row * words_per_row;
(start, start + words_per_row)
}
pub fn add(&mut self, row: R, column: R) -> bool {
let (start, _) = self.range(row);
let (word, mask) = word_mask(column);
let vector = &mut self.vector[..];
let v1 = vector[start + word];
let v2 = v1 | mask;
vector[start + word] = v2;
v1 != v2
}
pub fn contains(&self, row: R, column: R) -> bool {
let (start, _) = self.range(row);
let (word, mask) = word_mask(column);
(self.vector[start + word] & mask) != 0
}
pub fn intersection(&self, a: R, b: R) -> Vec<C> {
let (a_start, a_end) = self.range(a);
let (b_start, b_end) = self.range(b);
let mut result = Vec::with_capacity(self.columns);
for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
let mut v = self.vector[i] & self.vector[j];
for bit in 0..WORD_BITS {
if v == 0 {
break;
}
if v & 0x1 != 0 {
result.push(C::new(base * WORD_BITS + bit));
}
v >>= 1;
}
}
result
}
pub fn merge(&mut self, read: R, write: R) -> bool {
let (read_start, read_end) = self.range(read);
let (write_start, write_end) = self.range(write);
let vector = &mut self.vector[..];
let mut changed = false;
for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
let v1 = vector[write_index];
let v2 = v1 | vector[read_index];
vector[write_index] = v2;
changed = changed | (v1 != v2);
}
changed
}
pub fn iter<'a>(&'a self, row: R) -> BitVectorIter<'a, C> {
let (start, end) = self.range(row);
BitVectorIter {
iter: self.vector[start..end].iter(),
current: 0,
idx: 0,
marker: PhantomData,
}
}
}
#[derive(Clone, Debug)]
pub struct SparseBitMatrix<R, C>
where
R: Idx,
C: Idx,
{
columns: usize,
vector: IndexVec<R, BitVector<C>>,
}
impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
pub fn new(columns: usize) -> Self {
Self {
columns,
vector: IndexVec::new(),
}
}
fn ensure_row(&mut self, row: R) {
let columns = self.columns;
self.vector
.ensure_contains_elem(row, || BitVector::new(columns));
}
pub fn add(&mut self, row: R, column: C) -> bool {
self.ensure_row(row);
self.vector[row].insert(column)
}
pub fn contains(&self, row: R, column: C) -> bool {
self.vector.get(row).map_or(false, |r| r.contains(column))
}
pub fn merge(&mut self, read: R, write: R) -> bool {
if read == write || self.vector.get(read).is_none() {
return false;
}
self.ensure_row(write);
let (bitvec_read, bitvec_write) = self.vector.pick2_mut(read, write);
bitvec_write.merge(bitvec_read)
}
pub fn merge_into(&mut self, into: R, from: &BitVector<C>) -> bool {
self.ensure_row(into);
self.vector[into].merge(from)
}
pub fn add_all(&mut self, row: R) {
self.ensure_row(row);
self.vector[row].insert_all();
}
pub fn len(&self) -> usize {
self.vector.len()
}
pub fn rows(&self) -> impl Iterator<Item = R> {
self.vector.indices()
}
pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
self.vector.get(row).into_iter().flat_map(|r| r.iter())
}
pub fn iter_enumerated<'a>(&'a self) -> impl Iterator<Item = (R, &'a BitVector<C>)> + 'a {
self.vector.iter_enumerated()
}
pub fn row(&self, row: R) -> Option<&BitVector<C>> {
self.vector.get(row)
}
}
#[inline]
fn words<C: Idx>(elements: C) -> usize {
(elements.index() + WORD_BITS - 1) / WORD_BITS
}
#[inline]
fn word_mask<C: Idx>(index: C) -> (usize, Word) {
let index = index.index();
let word = index / WORD_BITS;
let mask = 1 << (index % WORD_BITS);
(word, mask)
}
#[test]
fn bitvec_iter_works() {
let mut bitvec: BitVector<usize> = BitVector::new(100);
bitvec.insert(1);
bitvec.insert(10);
bitvec.insert(19);
bitvec.insert(62);
bitvec.insert(63);
bitvec.insert(64);
bitvec.insert(65);
bitvec.insert(66);
bitvec.insert(99);
assert_eq!(
bitvec.iter().collect::<Vec<_>>(),
[1, 10, 19, 62, 63, 64, 65, 66, 99]
);
}
#[test]
fn bitvec_iter_works_2() {
let mut bitvec: BitVector<usize> = BitVector::new(319);
bitvec.insert(0);
bitvec.insert(127);
bitvec.insert(191);
bitvec.insert(255);
bitvec.insert(319);
assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
}
#[test]
fn union_two_vecs() {
let mut vec1: BitVector<usize> = BitVector::new(65);
let mut vec2: BitVector<usize> = BitVector::new(65);
assert!(vec1.insert(3));
assert!(!vec1.insert(3));
assert!(vec2.insert(5));
assert!(vec2.insert(64));
assert!(vec1.merge(&vec2));
assert!(!vec1.merge(&vec2));
assert!(vec1.contains(3));
assert!(!vec1.contains(4));
assert!(vec1.contains(5));
assert!(!vec1.contains(63));
assert!(vec1.contains(64));
}
#[test]
fn grow() {
let mut vec1: BitVector<usize> = BitVector::new(65);
for index in 0..65 {
assert!(vec1.insert(index));
assert!(!vec1.insert(index));
}
vec1.grow(128);
for index in 0..65 {
assert!(vec1.contains(index));
}
for index in 65..128 {
assert!(!vec1.contains(index));
}
for index in 65..128 {
assert!(vec1.insert(index));
assert!(!vec1.insert(index));
}
}
#[test]
fn matrix_intersection() {
let mut vec1: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
vec1.add(2, 3);
vec1.add(2, 6);
vec1.add(2, 10); vec1.add(2, 64); vec1.add(2, 65);
vec1.add(2, 130);
vec1.add(2, 160);
vec1.add(64, 133);
vec1.add(65, 2);
vec1.add(65, 8);
vec1.add(65, 10); vec1.add(65, 64); vec1.add(65, 68);
vec1.add(65, 133);
vec1.add(65, 160);
let intersection = vec1.intersection(2, 64);
assert!(intersection.is_empty());
let intersection = vec1.intersection(2, 65);
assert_eq!(intersection, &[10, 64, 160]);
}
#[test]
fn matrix_iter() {
let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
matrix.add(3, 22);
matrix.add(3, 75);
matrix.add(2, 99);
matrix.add(4, 0);
matrix.merge(3, 5);
let expected = [99];
let mut iter = expected.iter();
for i in matrix.iter(2) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
let expected = [22, 75];
let mut iter = expected.iter();
for i in matrix.iter(3) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
let expected = [0];
let mut iter = expected.iter();
for i in matrix.iter(4) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
let expected = [22, 75];
let mut iter = expected.iter();
for i in matrix.iter(5) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
}
#[test]
fn sparse_matrix_iter() {
let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
matrix.add(3, 22);
matrix.add(3, 75);
matrix.add(2, 99);
matrix.add(4, 0);
matrix.merge(3, 5);
let expected = [99];
let mut iter = expected.iter();
for i in matrix.iter(2) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
let expected = [22, 75];
let mut iter = expected.iter();
for i in matrix.iter(3) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
let expected = [0];
let mut iter = expected.iter();
for i in matrix.iter(4) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
let expected = [22, 75];
let mut iter = expected.iter();
for i in matrix.iter(5) {
let j = *iter.next().unwrap();
assert_eq!(i, j);
}
assert!(iter.next().is_none());
}