use array_vec::ArrayVec;
use std::fmt;
use std::mem;
use std::slice;
use bitvec::{bitwise, BitArray, BitIter, Intersect, Subtract, Union, Word, WORD_BITS};
use indexed_vec::Idx;
use rustc_serialize;
pub trait UnionIntoIdxSet<T: Idx> {
fn union_into(&self, other: &mut IdxSet<T>) -> bool;
}
pub trait SubtractFromIdxSet<T: Idx> {
fn subtract_from(&self, other: &mut IdxSet<T>) -> bool;
}
#[derive(Clone, Eq, PartialEq)]
pub struct IdxSet<T: Idx>(BitArray<T>);
impl<T: Idx> rustc_serialize::Encodable for IdxSet<T> {
fn encode<E: rustc_serialize::Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
self.0.encode(encoder)
}
}
impl<T: Idx> rustc_serialize::Decodable for IdxSet<T> {
fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSet<T>, D::Error> {
Ok(IdxSet(rustc_serialize::Decodable::decode(d)?))
}
}
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> IdxSet<T> {
pub fn new_empty(domain_size: usize) -> Self {
IdxSet(BitArray::new_empty(domain_size))
}
pub fn new_filled(domain_size: usize) -> Self {
IdxSet(BitArray::new_filled(domain_size))
}
pub fn to_hybrid(&self) -> HybridIdxSet<T> {
let domain_size = self.words().len() * WORD_BITS;
HybridIdxSet::Dense(self.to_owned(), domain_size)
}
pub fn clear(&mut self) {
self.0.clear();
}
pub fn set_up_to(&mut self, domain_size: usize) {
self.0.set_up_to(domain_size);
}
pub fn remove(&mut self, elem: &T) -> bool {
self.0.remove(*elem)
}
pub fn add(&mut self, elem: &T) -> bool {
self.0.insert(*elem)
}
pub fn contains(&self, elem: &T) -> bool {
self.0.contains(*elem)
}
pub fn words(&self) -> &[Word] {
self.0.words()
}
pub fn words_mut(&mut self) -> &mut [Word] {
self.0.words_mut()
}
pub fn overwrite(&mut self, other: &IdxSet<T>) {
self.words_mut().clone_from_slice(other.words());
}
pub fn union(&mut self, other: &impl UnionIntoIdxSet<T>) -> bool {
other.union_into(self)
}
pub fn subtract(&mut self, other: &impl SubtractFromIdxSet<T>) -> bool {
other.subtract_from(self)
}
pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
bitwise(self.words_mut(), other.words(), &Intersect)
}
pub fn iter(&self) -> BitIter<T> {
self.0.iter()
}
}
impl<T: Idx> UnionIntoIdxSet<T> for IdxSet<T> {
fn union_into(&self, other: &mut IdxSet<T>) -> bool {
bitwise(other.words_mut(), self.words(), &Union)
}
}
impl<T: Idx> SubtractFromIdxSet<T> for IdxSet<T> {
fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
bitwise(other.words_mut(), self.words(), &Subtract)
}
}
const SPARSE_MAX: usize = 8;
#[derive(Clone, Debug)]
pub struct SparseIdxSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
impl<T: Idx> SparseIdxSet<T> {
fn new() -> Self {
SparseIdxSet(ArrayVec::new())
}
fn len(&self) -> usize {
self.0.len()
}
fn contains(&self, elem: &T) -> bool {
self.0.contains(elem)
}
fn add(&mut self, elem: &T) -> bool {
if self.0.contains(elem) {
false
} else {
self.0.push(*elem);
true
}
}
fn remove(&mut self, elem: &T) -> bool {
if let Some(i) = self.0.iter().position(|e| e == elem) {
let len = self.0.len();
self.0.swap(i, len - 1);
self.0.pop();
true
} else {
false
}
}
fn to_dense(&self, domain_size: usize) -> IdxSet<T> {
let mut dense = IdxSet::new_empty(domain_size);
for elem in self.0.iter() {
dense.add(elem);
}
dense
}
fn iter(&self) -> slice::Iter<T> {
self.0.iter()
}
}
impl<T: Idx> UnionIntoIdxSet<T> for SparseIdxSet<T> {
fn union_into(&self, other: &mut IdxSet<T>) -> bool {
let mut changed = false;
for elem in self.iter() {
changed |= other.add(&elem);
}
changed
}
}
impl<T: Idx> SubtractFromIdxSet<T> for SparseIdxSet<T> {
fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
let mut changed = false;
for elem in self.iter() {
changed |= other.remove(&elem);
}
changed
}
}
#[derive(Clone, Debug)]
pub enum HybridIdxSet<T: Idx> {
Sparse(SparseIdxSet<T>, usize),
Dense(IdxSet<T>, usize),
}
impl<T: Idx> HybridIdxSet<T> {
pub fn new_empty(domain_size: usize) -> Self {
HybridIdxSet::Sparse(SparseIdxSet::new(), domain_size)
}
pub fn clear(&mut self) {
let domain_size = match *self {
HybridIdxSet::Sparse(_, size) => size,
HybridIdxSet::Dense(_, size) => size,
};
*self = HybridIdxSet::new_empty(domain_size);
}
pub fn contains(&self, elem: &T) -> bool {
match self {
HybridIdxSet::Sparse(sparse, _) => sparse.contains(elem),
HybridIdxSet::Dense(dense, _) => dense.contains(elem),
}
}
pub fn add(&mut self, elem: &T) -> bool {
match self {
HybridIdxSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
sparse.add(elem)
}
HybridIdxSet::Sparse(sparse, _) if sparse.contains(elem) => {
false
}
HybridIdxSet::Sparse(_, _) => {
let dummy = HybridIdxSet::Sparse(SparseIdxSet::new(), 0);
match mem::replace(self, dummy) {
HybridIdxSet::Sparse(sparse, domain_size) => {
let mut dense = sparse.to_dense(domain_size);
let changed = dense.add(elem);
assert!(changed);
mem::replace(self, HybridIdxSet::Dense(dense, domain_size));
changed
}
_ => panic!("impossible"),
}
}
HybridIdxSet::Dense(dense, _) => dense.add(elem),
}
}
pub fn remove(&mut self, elem: &T) -> bool {
match self {
HybridIdxSet::Sparse(sparse, _) => sparse.remove(elem),
HybridIdxSet::Dense(dense, _) => dense.remove(elem),
}
}
pub fn to_dense(self) -> IdxSet<T> {
match self {
HybridIdxSet::Sparse(sparse, domain_size) => sparse.to_dense(domain_size),
HybridIdxSet::Dense(dense, _) => dense,
}
}
pub fn iter(&self) -> HybridIter<T> {
match self {
HybridIdxSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
HybridIdxSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
}
}
}
impl<T: Idx> UnionIntoIdxSet<T> for HybridIdxSet<T> {
fn union_into(&self, other: &mut IdxSet<T>) -> bool {
match self {
HybridIdxSet::Sparse(sparse, _) => sparse.union_into(other),
HybridIdxSet::Dense(dense, _) => dense.union_into(other),
}
}
}
impl<T: Idx> SubtractFromIdxSet<T> for HybridIdxSet<T> {
fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
match self {
HybridIdxSet::Sparse(sparse, _) => sparse.subtract_from(other),
HybridIdxSet::Dense(dense, _) => dense.subtract_from(other),
}
}
}
pub enum HybridIter<'a, T: Idx> {
Sparse(slice::Iter<'a, T>),
Dense(BitIter<'a, T>),
}
impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
match self {
HybridIter::Sparse(sparse) => sparse.next().map(|e| *e),
HybridIter::Dense(dense) => dense.next(),
}
}
}