use crate::{BitBlock, BitSlice};
#[cfg_attr(feature = "std", derive(Hash))]
pub struct Bits<'a, B: BitBlock> {
slice: &'a BitSlice<B>,
index: usize,
}
impl<'a, B: BitBlock> Bits<'a, B> {
pub(super) fn from_slice(slice: &'a BitSlice<B>) -> Self {
Self { slice, index: 0 }
}
}
impl<'a, B: BitBlock> Iterator for Bits<'a, B> {
type Item = bool;
fn next(&mut self) -> Option<Self::Item> {
let blocks: &[B] = self.slice.as_ref();
let block = blocks.get(B::get_block_index(self.index))?;
let bit = block.wrapping_test_bit(self.index);
self.index += 1;
Some(bit)
}
}
#[cfg_attr(feature = "std", derive(Hash))]
pub struct Ones<'a, B: BitBlock> {
slice: &'a BitSlice<B>,
block_index: usize,
block: B,
}
impl<'a, B: BitBlock> Ones<'a, B> {
pub(super) fn from_slice(slice: &'a BitSlice<B>) -> Self {
let zero = B::ZERO;
let slice_raw: &[B] = slice.as_ref();
let (block, slice_raw) = slice_raw.split_first().unwrap_or((&zero, slice_raw));
Self {
slice: slice_raw.as_ref(),
block_index: 0,
block: *block,
}
}
}
impl<'a, B: BitBlock> Iterator for Ones<'a, B> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.block == B::ZERO {
let slice_raw: &[B] = self.slice.as_ref();
let (block, slice_raw) = slice_raw.split_first()?;
self.block = *block;
self.slice = slice_raw.as_ref();
self.block_index += 1;
}
let bit_index = self.block.leading_zeros();
self.block = self.block.wrapping_without_bit(bit_index);
Some(bit_index | B::bit_index_from_block_index(self.block_index))
}
}
#[cfg_attr(feature = "std", derive(Hash))]
pub struct Zeros<'a, B: BitBlock> {
slice: &'a BitSlice<B>,
block_index: usize,
block: B,
}
impl<'a, B: BitBlock> Zeros<'a, B> {
pub(super) fn from_slice(slice: &'a BitSlice<B>) -> Self {
let zero = B::ZERO;
let slice_raw: &[B] = slice.as_ref();
let (block, slice_raw) = slice_raw.split_first().unwrap_or((&zero, slice_raw));
Self {
slice: slice_raw.as_ref(),
block_index: 0,
block: *block,
}
}
}
impl<'a, B: BitBlock> Iterator for Zeros<'a, B> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.block == !B::ZERO {
let slice_raw: &[B] = self.slice.as_ref();
let (block, slice_raw) = slice_raw.split_first()?;
self.block = *block;
self.slice = slice_raw.as_ref();
self.block_index += 1;
}
let bit_index = self.block.leading_ones();
self.block = self.block.wrapping_with_bit(bit_index);
Some(bit_index | B::bit_index_from_block_index(self.block_index))
}
}
#[cfg(test)]
mod tests {
use crate::BitSlice;
#[test]
fn ones() {
let map: [u8; 4] = [0b00010100, 0b10011100, 0b00000000, 0b11111111];
let map: &BitSlice<u8> = map.as_ref().as_ref();
let mut ones = map.ones();
assert_eq!(ones.next(), Some(3));
assert_eq!(ones.next(), Some(5));
assert_eq!(ones.next(), Some(8));
assert_eq!(ones.next(), Some(11));
assert_eq!(ones.next(), Some(12));
assert_eq!(ones.next(), Some(13));
assert_eq!(ones.next(), Some(24));
assert_eq!(ones.next(), Some(25));
assert_eq!(ones.next(), Some(26));
assert_eq!(ones.next(), Some(27));
assert_eq!(ones.next(), Some(28));
assert_eq!(ones.next(), Some(29));
assert_eq!(ones.next(), Some(30));
assert_eq!(ones.next(), Some(31));
assert_eq!(ones.next(), None);
}
#[test]
fn zeros() {
let map: [u8; 4] = [0b11101011, 0b01100011, 0b11111111, 0b00000000];
let map: &BitSlice<u8> = map.as_ref().as_ref();
let mut zeros = map.zeros();
assert_eq!(zeros.next(), Some(3));
assert_eq!(zeros.next(), Some(5));
assert_eq!(zeros.next(), Some(8));
assert_eq!(zeros.next(), Some(11));
assert_eq!(zeros.next(), Some(12));
assert_eq!(zeros.next(), Some(13));
assert_eq!(zeros.next(), Some(24));
assert_eq!(zeros.next(), Some(25));
assert_eq!(zeros.next(), Some(26));
assert_eq!(zeros.next(), Some(27));
assert_eq!(zeros.next(), Some(28));
assert_eq!(zeros.next(), Some(29));
assert_eq!(zeros.next(), Some(30));
assert_eq!(zeros.next(), Some(31));
assert_eq!(zeros.next(), None);
}
#[test]
fn bits() {
let map: [u8; 2] = [0b00101100, 0b00110111];
let map: &BitSlice<u8> = map.as_ref().as_ref();
let mut bits = map.bits();
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(false));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(true));
assert_eq!(bits.next(), Some(true));
}
}