use std::mem;
pub type Word = usize;
pub trait BitSlice {
fn clear_bit(&mut self, idx: usize) -> bool;
fn set_bit(&mut self, idx: usize) -> bool;
fn get_bit(&self, idx: usize) -> bool;
}
impl BitSlice for [Word] {
#[inline]
fn clear_bit(&mut self, idx: usize) -> bool {
let words = self;
debug!("clear_bit: words={} idx={}",
bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
let oldv = words[word];
let newv = oldv & !bit_mask;
words[word] = newv;
oldv != newv
}
#[inline]
fn set_bit(&mut self, idx: usize) -> bool {
let words = self;
debug!("set_bit: words={} idx={}",
bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
let oldv = words[word];
let newv = oldv | bit_mask;
words[word] = newv;
oldv != newv
}
#[inline]
fn get_bit(&self, idx: usize) -> bool {
let words = self;
let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
(words[word] & bit_mask) != 0
}
}
struct BitLookup {
word: usize,
bit_in_word: usize,
bit_mask: Word,
}
#[inline]
fn bit_lookup(bit: usize) -> BitLookup {
let word_bits = mem::size_of::<Word>() * 8;
let word = bit / word_bits;
let bit_in_word = bit % word_bits;
let bit_mask = 1 << bit_in_word;
BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask }
}
fn bit_str(bit: Word) -> String {
let byte = bit >> 3;
let lobits = 1 << (bit & 0b111);
format!("[{}:{}-{:02x}]", bit, byte, lobits)
}
pub fn bits_to_string(words: &[Word], bits: usize) -> String {
let mut result = String::new();
let mut sep = '[';
let mut i = 0;
for &word in words.iter() {
let mut v = word;
loop { let remain = bits - i;
let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
assert!(mask <= 0xFF);
let byte = v & mask;
result.push(sep);
result.push_str(&format!("{:02x}", byte));
if remain <= 8 { break; }
v >>= 8;
i += 8;
sep = '-';
}
}
result.push(']');
return result
}
#[inline]
pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
in_vec: &[usize],
op: &Op) -> bool {
assert_eq!(out_vec.len(), in_vec.len());
let mut changed = false;
for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
let old_val = *out_elt;
let new_val = op.join(old_val, *in_elt);
*out_elt = new_val;
changed |= old_val != new_val;
}
changed
}
pub trait BitwiseOperator {
fn join(&self, pred1: usize, pred2: usize) -> usize;
}
pub struct Intersect;
impl BitwiseOperator for Intersect {
#[inline]
fn join(&self, a: usize, b: usize) -> usize { a & b }
}
pub struct Union;
impl BitwiseOperator for Union {
#[inline]
fn join(&self, a: usize, b: usize) -> usize { a | b }
}
pub struct Subtract;
impl BitwiseOperator for Subtract {
#[inline]
fn join(&self, a: usize, b: usize) -> usize { a & !b }
}