use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign};
const BITS: usize = 64;
type Block = u64;
#[inline(always)]
#[no_coverage]
fn div_rem(x: usize, d: usize) -> (usize, usize) {
(x / d, x % d)
}
#[derive(Clone, Debug, Default)]
pub struct FixedBitSet {
data: Vec<Block>,
length: usize,
}
impl FixedBitSet {
#[no_coverage]
pub const fn new() -> Self {
FixedBitSet {
data: Vec::new(),
length: 0,
}
}
#[no_coverage]
pub fn with_capacity(bits: usize) -> Self {
let (mut blocks, rem) = div_rem(bits, BITS);
blocks += (rem > 0) as usize;
FixedBitSet {
data: vec![0; blocks],
length: bits,
}
}
#[no_coverage]
pub fn grow(&mut self, bits: usize) {
if bits > self.length {
let (mut blocks, rem) = div_rem(bits, BITS);
blocks += (rem > 0) as usize;
self.length = bits;
self.data.resize(blocks, 0);
}
}
#[inline]
#[no_coverage]
pub fn len(&self) -> usize {
self.length
}
#[inline]
#[no_coverage]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
#[no_coverage]
pub fn contains(&self, bit: usize) -> bool {
let (block, i) = div_rem(bit, BITS);
match self.data.get(block) {
None => false,
Some(b) => (b & (1 << i)) != 0,
}
}
#[inline]
#[no_coverage]
pub fn clear(&mut self) {
for elt in &mut self.data {
*elt = 0
}
}
#[inline(always)]
#[no_coverage]
pub fn insert(&mut self, bit: usize) {
assert!(
bit < self.length,
"insert at index {} exceeds fixbitset size {}",
bit,
self.length
);
let (block, i) = div_rem(bit, BITS);
unsafe {
*self.data.get_unchecked_mut(block) |= 1 << i;
}
}
#[inline]
#[no_coverage]
pub fn put(&mut self, bit: usize) -> bool {
assert!(
bit < self.length,
"put at index {} exceeds fixbitset size {}",
bit,
self.length
);
let (block, i) = div_rem(bit, BITS);
unsafe {
let word = self.data.get_unchecked_mut(block);
let prev = *word & (1 << i) != 0;
*word |= 1 << i;
prev
}
}
#[inline]
#[no_coverage]
pub fn toggle(&mut self, bit: usize) {
assert!(
bit < self.length,
"toggle at index {} exceeds fixbitset size {}",
bit,
self.length
);
let (block, i) = div_rem(bit, BITS);
unsafe {
*self.data.get_unchecked_mut(block) ^= 1 << i;
}
}
#[inline]
#[no_coverage]
pub fn count_ones(&self) -> usize {
let mut sum = 0;
for block in &self.data {
sum += block.count_ones();
}
sum as usize
}
#[inline]
#[no_coverage]
pub fn ones(&self) -> Ones {
match self.as_slice().split_first() {
Some((&block, rem)) => Ones {
bitset: block,
block_idx: 0,
remaining_blocks: rem,
},
None => Ones {
bitset: 0,
block_idx: 0,
remaining_blocks: &[],
},
}
}
#[inline]
#[no_coverage]
pub fn as_slice(&self) -> &[u64] {
&self.data
}
#[no_coverage]
pub fn union_with(&mut self, other: &FixedBitSet) {
if other.len() >= self.len() {
self.grow(other.len());
}
for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
*x |= *y;
}
}
#[no_coverage]
pub fn intersect_with(&mut self, other: &FixedBitSet) {
for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
*x &= *y;
}
let mn = std::cmp::min(self.data.len(), other.data.len());
for wd in &mut self.data[mn..] {
*wd = 0;
}
}
#[no_coverage]
pub fn difference_with(&mut self, other: &FixedBitSet) {
for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
*x &= !*y;
}
}
#[no_coverage]
pub fn symmetric_difference_with(&mut self, other: &FixedBitSet) {
if other.len() >= self.len() {
self.grow(other.len());
}
for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
*x ^= *y;
}
}
}
pub struct Ones<'a> {
bitset: Block,
block_idx: usize,
remaining_blocks: &'a [Block],
}
impl<'a> Iterator for Ones<'a> {
type Item = usize;
#[inline]
#[no_coverage]
fn next(&mut self) -> Option<Self::Item> {
while self.bitset == 0 {
if self.remaining_blocks.is_empty() {
return None;
}
self.bitset = self.remaining_blocks[0];
self.remaining_blocks = &self.remaining_blocks[1..];
self.block_idx += 1;
}
#[allow(clippy::unnecessary_cast)]
let t = self.bitset & (0 as Block).wrapping_sub(self.bitset);
let r = self.bitset.trailing_zeros() as usize;
self.bitset ^= t;
Some(self.block_idx * BITS + r)
}
}
impl<'a> BitAnd for &'a FixedBitSet {
type Output = FixedBitSet;
#[no_coverage]
fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
let (short, long) = {
if self.len() <= other.len() {
(&self.data, &other.data)
} else {
(&other.data, &self.data)
}
};
let mut data = short.clone();
for (data, block) in data.iter_mut().zip(long.iter()) {
*data &= *block;
}
let len = std::cmp::min(self.len(), other.len());
FixedBitSet { data, length: len }
}
}
impl BitAndAssign for FixedBitSet {
#[no_coverage]
fn bitand_assign(&mut self, other: Self) {
self.intersect_with(&other);
}
}
impl BitAndAssign<&Self> for FixedBitSet {
#[no_coverage]
fn bitand_assign(&mut self, other: &Self) {
self.intersect_with(other);
}
}
impl<'a> BitOr for &'a FixedBitSet {
type Output = FixedBitSet;
#[no_coverage]
fn bitor(self, other: &FixedBitSet) -> FixedBitSet {
let (short, long) = {
if self.len() <= other.len() {
(&self.data, &other.data)
} else {
(&other.data, &self.data)
}
};
let mut data = long.clone();
for (data, block) in data.iter_mut().zip(short.iter()) {
*data |= *block;
}
let len = std::cmp::max(self.len(), other.len());
FixedBitSet { data, length: len }
}
}
impl BitOrAssign for FixedBitSet {
#[no_coverage]
fn bitor_assign(&mut self, other: Self) {
self.union_with(&other);
}
}
impl BitOrAssign<&Self> for FixedBitSet {
#[no_coverage]
fn bitor_assign(&mut self, other: &Self) {
self.union_with(other);
}
}
impl<'a> BitXor for &'a FixedBitSet {
type Output = FixedBitSet;
#[no_coverage]
fn bitxor(self, other: &FixedBitSet) -> FixedBitSet {
let (short, long) = {
if self.len() <= other.len() {
(&self.data, &other.data)
} else {
(&other.data, &self.data)
}
};
let mut data = long.clone();
for (data, block) in data.iter_mut().zip(short.iter()) {
*data ^= *block;
}
let len = std::cmp::max(self.len(), other.len());
FixedBitSet { data, length: len }
}
}
impl BitXorAssign for FixedBitSet {
#[no_coverage]
fn bitxor_assign(&mut self, other: Self) {
self.symmetric_difference_with(&other);
}
}
impl BitXorAssign<&Self> for FixedBitSet {
#[no_coverage]
fn bitxor_assign(&mut self, other: &Self) {
self.symmetric_difference_with(other);
}
}