use std::borrow::{Borrow, BorrowMut, ToOwned};
use std::fmt;
use std::iter;
use std::marker::PhantomData;
use std::mem;
use std::ops::{Deref, DerefMut, Range};
use std::slice;
use bitslice::{BitSlice, Word};
use bitslice::{bitwise, Union, Subtract, Intersect};
use indexed_vec::Idx;
use rustc_serialize;
#[derive(Eq, PartialEq)]
pub struct IdxSetBuf<T: Idx> {
_pd: PhantomData<fn(&T)>,
bits: Vec<Word>,
}
impl<T: Idx> Clone for IdxSetBuf<T> {
fn clone(&self) -> Self {
IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() }
}
}
impl<T: Idx> rustc_serialize::Encodable for IdxSetBuf<T> {
fn encode<E: rustc_serialize::Encoder>(&self,
encoder: &mut E)
-> Result<(), E::Error> {
self.bits.encode(encoder)
}
}
impl<T: Idx> rustc_serialize::Decodable for IdxSetBuf<T> {
fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSetBuf<T>, D::Error> {
let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
Ok(IdxSetBuf {
_pd: PhantomData,
bits: words,
})
}
}
pub struct IdxSet<T: Idx> {
_pd: PhantomData<fn(&T)>,
bits: [Word],
}
impl<T: Idx> Borrow<IdxSet<T>> for IdxSetBuf<T> {
fn borrow(&self) -> &IdxSet<T> {
&*self
}
}
impl<T: Idx> BorrowMut<IdxSet<T>> for IdxSetBuf<T> {
fn borrow_mut(&mut self) -> &mut IdxSet<T> {
&mut *self
}
}
impl<T: Idx> ToOwned for IdxSet<T> {
type Owned = IdxSetBuf<T>;
fn to_owned(&self) -> Self::Owned {
IdxSet::to_owned(self)
}
}
impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
w.debug_list()
.entries(self.iter())
.finish()
}
}
impl<T: Idx> fmt::Debug for IdxSet<T> {
fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
w.debug_list()
.entries(self.iter())
.finish()
}
}
impl<T: Idx> IdxSetBuf<T> {
fn new(init: Word, universe_size: usize) -> Self {
let bits_per_word = mem::size_of::<Word>() * 8;
let num_words = (universe_size + (bits_per_word - 1)) / bits_per_word;
IdxSetBuf {
_pd: Default::default(),
bits: vec![init; num_words],
}
}
pub fn new_filled(universe_size: usize) -> Self {
Self::new(!0, universe_size)
}
pub fn new_empty(universe_size: usize) -> Self {
Self::new(0, universe_size)
}
}
impl<T: Idx> IdxSet<T> {
unsafe fn from_slice(s: &[Word]) -> &Self {
mem::transmute(s) }
unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self {
mem::transmute(s) }
}
impl<T: Idx> Deref for IdxSetBuf<T> {
type Target = IdxSet<T>;
fn deref(&self) -> &IdxSet<T> {
unsafe { IdxSet::from_slice(&self.bits) }
}
}
impl<T: Idx> DerefMut for IdxSetBuf<T> {
fn deref_mut(&mut self) -> &mut IdxSet<T> {
unsafe { IdxSet::from_slice_mut(&mut self.bits) }
}
}
impl<T: Idx> IdxSet<T> {
pub fn to_owned(&self) -> IdxSetBuf<T> {
IdxSetBuf {
_pd: Default::default(),
bits: self.bits.to_owned(),
}
}
pub fn clear(&mut self) {
for b in &mut self.bits {
*b = 0;
}
}
pub fn remove(&mut self, elem: &T) -> bool {
self.bits.clear_bit(elem.index())
}
pub fn add(&mut self, elem: &T) -> bool {
self.bits.set_bit(elem.index())
}
pub fn range(&self, elems: &Range<T>) -> &Self {
let elems = elems.start.index()..elems.end.index();
unsafe { Self::from_slice(&self.bits[elems]) }
}
pub fn range_mut(&mut self, elems: &Range<T>) -> &mut Self {
let elems = elems.start.index()..elems.end.index();
unsafe { Self::from_slice_mut(&mut self.bits[elems]) }
}
pub fn contains(&self, elem: &T) -> bool {
self.bits.get_bit(elem.index())
}
pub fn words(&self) -> &[Word] {
&self.bits
}
pub fn words_mut(&mut self) -> &mut [Word] {
&mut self.bits
}
pub fn clone_from(&mut self, other: &IdxSet<T>) {
self.words_mut().clone_from_slice(other.words());
}
pub fn union(&mut self, other: &IdxSet<T>) -> bool {
bitwise(self.words_mut(), other.words(), &Union)
}
pub fn subtract(&mut self, other: &IdxSet<T>) -> bool {
bitwise(self.words_mut(), other.words(), &Subtract)
}
pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
bitwise(self.words_mut(), other.words(), &Intersect)
}
pub fn iter(&self) -> Iter<T> {
Iter {
cur: None,
iter: self.words().iter().enumerate(),
_pd: PhantomData,
}
}
pub fn each_bit<F>(&self, max_bits: usize, f: F) where F: FnMut(T) {
each_bit(self, max_bits, f)
}
pub fn reset_to_empty(&mut self) {
for word in self.words_mut() { *word = 0; }
}
pub fn elems(&self, universe_size: usize) -> Elems<T> {
Elems { i: 0, set: self, universe_size: universe_size }
}
}
pub struct Elems<'a, T: Idx> { i: usize, set: &'a IdxSet<T>, universe_size: usize }
impl<'a, T: Idx> Iterator for Elems<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.i >= self.universe_size { return None; }
let mut i = self.i;
loop {
if i >= self.universe_size {
self.i = i; return None;
}
if self.set.contains(&T::new(i)) {
self.i = i + 1; return Some(T::new(i));
}
i = i + 1;
}
}
}
fn each_bit<T: Idx, F>(words: &IdxSet<T>, max_bits: usize, mut f: F) where F: FnMut(T) {
let usize_bits: usize = mem::size_of::<usize>() * 8;
for (word_index, &word) in words.words().iter().enumerate() {
if word != 0 {
let base_index = word_index * usize_bits;
for offset in 0..usize_bits {
let bit = 1 << offset;
if (word & bit) != 0 {
let bit_index = base_index + offset as usize;
if bit_index >= max_bits {
return;
} else {
f(Idx::new(bit_index));
}
}
}
}
}
}
pub struct Iter<'a, T: Idx> {
cur: Option<(Word, usize)>,
iter: iter::Enumerate<slice::Iter<'a, Word>>,
_pd: PhantomData<fn(&T)>,
}
impl<'a, T: Idx> Iterator for Iter<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
let word_bits = mem::size_of::<Word>() * 8;
loop {
if let Some((ref mut word, offset)) = self.cur {
let bit_pos = word.trailing_zeros() as usize;
if bit_pos != word_bits {
let bit = 1 << bit_pos;
*word ^= bit;
return Some(T::new(bit_pos + offset))
}
}
let (i, word) = self.iter.next()?;
self.cur = Some((*word, word_bits * i));
}
}
}