#![deny(missing_docs)]
mod primitive;
use std::ops::*;
use std::{fmt, iter};
use generic_array::{GenericArray, ArrayLength};
use typenum::Unsigned;
use self::primitive::{Primitive, CeilDiv};
type CeilQuot<T, Q> = <T as CeilDiv<Q>>::Output;
fn bits<B>(mut block: B) -> impl Iterator<Item = usize> + Clone
where B: Primitive
{
iter::from_fn(move || {
if block.is_zero() {
None
} else {
let next_bit = block.trailing_zeros() as usize;
block ^= B::one() << next_bit;
Some(next_bit)
}
})
}
pub struct Bitset<N, B = usize>
where B: Primitive,
N: CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
blocks: GenericArray<B, CeilQuot<N, B::Size>>,
}
impl<N, B> fmt::Debug for Bitset<N, B>
where B: Primitive,
N: Unsigned + CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_set()
.entries(self.iter())
.finish()
}
}
impl<N, B> Default for Bitset<N, B>
where B: Primitive,
N: CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
fn default() -> Self {
Bitset {
blocks: Default::default(),
}
}
}
impl<N, B> Clone for Bitset<N, B>
where B: Primitive,
N: CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
fn clone(&self) -> Self {
Bitset {
blocks: self.blocks.clone(),
}
}
}
impl<N, B> Copy for Bitset<N, B>
where B: Primitive,
N: CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
GenericArray<B, CeilQuot<N, B::Size>>: Copy,
{}
impl<N, B> PartialEq for Bitset<N, B>
where B: Primitive,
N: CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
fn eq(&self, other: &Self) -> bool {
self.blocks == other.blocks
}
}
impl<N, B> std::cmp::Eq for Bitset<N, B>
where B: Primitive,
N: CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{}
impl<N, B> iter::FromIterator<usize> for Bitset<N, B>
where B: Primitive,
N: Unsigned + CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
fn from_iter<T>(iter: T ) -> Self
where T: IntoIterator<Item = usize>
{
let mut ret = Self::default();
for n in iter.into_iter() {
ret.insert(n);
}
ret
}
}
impl<N, B> Bitset<N, B>
where B: Primitive,
N: Unsigned + CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
pub fn new() -> Self {
Default::default()
}
fn loc(bit: usize) -> (usize, usize) {
(bit / B::SIZE, bit % B::SIZE)
}
pub fn contains(&self, value: usize) -> bool {
assert!(value < N::USIZE);
let (block, shift) = Self::loc(value);
(self.blocks[block] >> shift) & B::one() == B::one()
}
pub fn insert(&mut self, value: usize) {
assert!(value < N::USIZE);
let (block, shift) = Self::loc(value);
self.blocks[block] |= B::one() << shift;
}
pub fn remove(&mut self, value: usize) {
assert!(value < N::USIZE);
let (block, shift) = Self::loc(value);
self.blocks[block] &= !(B::one() << shift);
}
pub fn is_empty(&self) -> bool {
self.blocks
.iter()
.all(|b| b.is_zero())
}
pub fn len(&self) -> usize {
self.blocks
.iter()
.map(|b| b.count_ones() as usize)
.sum()
}
pub fn iter(&self) -> impl '_ + Iterator<Item = usize> + Clone {
self.blocks
.iter()
.cloned()
.enumerate()
.flat_map(|(i, b)| bits(b).map(move |j| B::SIZE * i + j))
}
pub fn clear(&mut self) {
for b in &mut self.blocks {
*b = B::zero();
}
}
fn apply_blocks(&mut self, other: &Self, f: impl Fn(&mut B, B)) {
for (a, &b) in self.blocks.iter_mut().zip(other.blocks.iter()) {
f(a, b);
}
}
fn iter_blocks<'a>(&'a self, other: &'a Self, f: impl 'a + Fn(B, B) -> B)
-> impl 'a + Iterator<Item = usize>
{
self.blocks
.iter()
.zip(other.blocks.iter())
.map(move |(&a, &b)| f(a, b))
.enumerate()
.flat_map(|(i, b)| bits(b).map(move |j| B::SIZE * i + j))
}
pub fn union<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
self.iter_blocks(other, |a, b| a | b)
}
pub fn intersection<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
self.iter_blocks(other, |a, b| a & b)
}
pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
self.iter_blocks(other, |a, b| a ^ b)
}
pub fn difference<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
self.iter_blocks(other, |a, b| a & !b)
}
pub fn is_disjoint(&self, other: &Self) -> bool {
self.blocks
.iter()
.zip(other.blocks.iter())
.all(|(&a, &b)| (a & b).is_zero())
}
pub fn is_subset(&self, other: &Self) -> bool {
self.blocks
.iter()
.zip(other.blocks.iter())
.all(|(&a, &b)| a & b == a)
}
pub fn is_superset(&self, other: &Self) -> bool {
self.blocks
.iter()
.zip(other.blocks.iter())
.all(|(&a, &b)| a & b == b)
}
}
macro_rules! ops {
($( $( #[$meta:meta] )* $OpAssign:ident, $op_assign:ident, $Op:ident, $op:ident => $f:expr ),* $(,)?) => {
$(
$(#[$meta])*
impl<N, B> $OpAssign<&Self> for Bitset<N, B>
where B: Primitive,
N: Unsigned + CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
{
fn $op_assign(&mut self, other: &Self) {
self.apply_blocks(other, $f);
}
}
$(#[$meta])*
impl<'a, 'b, N, B> $Op<&'b Bitset<N, B>> for &'a Bitset<N, B>
where B: Primitive,
N: Unsigned + CeilDiv<B::Size>,
CeilQuot<N, B::Size>: ArrayLength<B>,
Bitset<N, B>: Clone,
{
type Output = Bitset<N, B>;
fn $op(self, other: &'b Bitset<N, B>) -> Self::Output {
let mut ret = (*self).clone();
(&mut ret).$op_assign(other);
ret
}
}
)*
}
}
ops! {
BitOrAssign, bitor_assign, BitOr, bitor => |a, b| *a |= b,
BitAndAssign, bitand_assign, BitAnd, bitand => |a, b| *a &= b,
BitXorAssign, bitxor_assign, BitXor, bitxor => |a, b| *a ^= b,
SubAssign, sub_assign, Sub, sub => |a, b| *a &= !b,
}