use crate::*;
use core::{
iter::{ExactSizeIterator, FusedIterator},
mem::MaybeUninit,
};
pub struct BitSetIter<W: Word>(pub(crate) W);
impl<W: Word> Iterator for BitSetIter<W> {
type Item = Element;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.0 == W::ZERO {
return None;
}
let item = self.0.trailing_zeros() as Self::Item;
self.0 &= self.0 - W::ONE;
Some(item)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let remaining = self.0.count_ones() as usize;
(remaining, Some(remaining))
}
}
impl<W: Word> DoubleEndedIterator for BitSetIter<W> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
if self.0 == W::ZERO {
return None;
}
let item = BitSet::<W>::MAX - self.0.leading_zeros() as Self::Item;
self.0 &= !(W::ONE << item);
Some(item)
}
}
impl<W: Word> ExactSizeIterator for BitSetIter<W> {}
impl<W: Word> FusedIterator for BitSetIter<W> {}
pub(crate) const MAX_SUBSET_CARDINALITY: usize = u128::BITS as usize;
const SUFFIX_CACHE_SIZE: usize = MAX_SUBSET_CARDINALITY + 1;
pub struct SubsetsOfSizeIter<W> {
suffixes: [MaybeUninit<W>; SUFFIX_CACHE_SIZE],
size: usize,
set: W,
subset: W,
stop: bool,
}
impl<W: Word> SubsetsOfSizeIter<W> {
#[inline]
pub(crate) fn new(set: W, size: usize) -> Self {
let mut suffixes = [const { MaybeUninit::uninit() }; SUFFIX_CACHE_SIZE];
if size > set.count_ones() as usize {
return Self {
suffixes, size: 0, set: W::ZERO, subset: W::ZERO, stop: true,
};
}
assert!(
size <= MAX_SUBSET_CARDINALITY,
"can only generate subsets of size up to {}",
MAX_SUBSET_CARDINALITY
);
let mut suffix = W::ZERO;
let mut remainder = set;
suffixes[0].write(suffix);
for cell in suffixes.iter_mut().skip(1).take(size) {
let next_bit = W::ONE << remainder.trailing_zeros() as usize;
suffix |= next_bit;
remainder &= !next_bit;
cell.write(suffix);
}
debug_assert_eq!(suffix.count_ones() as usize, size);
Self {
suffixes,
size,
set,
subset: suffix,
stop: false,
}
}
}
impl<W: Word> Iterator for SubsetsOfSizeIter<W> {
type Item = BitSet<W>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.stop {
None
} else {
debug_assert!(self.subset & !self.set == W::ZERO);
debug_assert!(self.subset.count_ones() as usize == self.size);
let next = self.subset;
let bit = self.subset & self.subset.wrapping_neg();
if bit != W::ZERO
&& let Some(x) = (self.subset | !self.set).checked_add(&bit)
{
let prefix = x & self.set;
let lost = self.size - prefix.count_ones() as usize;
assert!(lost <= self.size); let suffix = unsafe { self.suffixes.get_unchecked(lost).assume_init() };
debug_assert!(prefix & suffix == W::ZERO);
self.subset = prefix | suffix;
} else {
self.stop = true;
}
Some(BitSet::<W>(next))
}
}
}
impl<W: Word> FusedIterator for SubsetsOfSizeIter<W> {}