use crate::{
index::BitIdx,
mem::BitMemory,
order::BitOrder,
pointer::BitPtr,
slice::{
proxy::BitMut,
BitSlice,
BitSliceIndex,
},
store::BitStore,
};
use core::{
cmp,
fmt::{
self,
Debug,
Formatter,
},
iter::FusedIterator,
marker::PhantomData,
mem,
ptr::NonNull,
};
#[derive(Debug)]
pub struct Iter<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
base: *const T,
last: *const T,
head: BitIdx<T::Mem>,
tail: BitIdx<T::Mem>,
_ref: PhantomData<&'a BitSlice<O, T>>,
}
impl<'a, O, T> Iter<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
#[inline]
pub fn as_bitslice(&self) -> &'a BitSlice<O, T> {
unsafe { BitPtr::new_unchecked(self.base, self.head, self.len()) }
.to_bitslice_ref()
}
#[inline]
#[doc(hidden)]
#[cfg(not(tarpaulin_include))]
#[deprecated(
note = "Use `.as_bitslice` on iterators to view the remaining data"
)]
pub fn as_slice(&self) -> &'a BitSlice<O, T> {
self.as_bitslice()
}
fn pop_front(&mut self) -> <Self as Iterator>::Item {
let out = unsafe { &*self.base }.get_bit::<O>(self.head);
let (head, incr) = self.head.incr();
self.base = unsafe { self.base.add(incr as usize) };
self.head = head;
if out { &true } else { &false }
}
fn pop_back(&mut self) -> <Self as Iterator>::Item {
let (tail, offset) = self.tail.decr();
self.last = unsafe { self.last.offset(-(offset as isize)) };
self.tail = tail;
if unsafe { &*self.last }.get_bit::<O>(self.tail) {
&true
}
else {
&false
}
}
}
#[cfg(not(tarpaulin_include))]
impl<O, T> Clone for Iter<'_, O, T>
where
O: BitOrder,
T: BitStore,
{
fn clone(&self) -> Self {
*self
}
}
#[cfg(not(tarpaulin_include))]
impl<O, T> AsRef<BitSlice<O, T>> for Iter<'_, O, T>
where
O: BitOrder,
T: BitStore,
{
fn as_ref(&self) -> &BitSlice<O, T> {
self.as_bitslice()
}
}
impl<'a, O, T> IntoIterator for &'a BitSlice<O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
type IntoIter = Iter<'a, O, T>;
type Item = <Self::IntoIter as Iterator>::Item;
fn into_iter(self) -> Self::IntoIter {
let (addr, head, bits) = self.bitptr().raw_parts();
let base = addr.to_const();
let (elts, tail) = head.offset(bits as isize);
let last = unsafe { base.offset(elts) };
Self::IntoIter {
base,
last,
head,
tail,
_ref: PhantomData,
}
}
}
impl<O, T> Copy for Iter<'_, O, T>
where
O: BitOrder,
T: BitStore,
{
}
#[derive(Debug)]
pub struct IterMut<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
base: NonNull<<T::Alias as BitStore>::Access>,
last: NonNull<<T::Alias as BitStore>::Access>,
head: BitIdx<<T::Alias as BitStore>::Mem>,
tail: BitIdx<<T::Alias as BitStore>::Mem>,
_ref: PhantomData<&'a mut BitSlice<O, T::Alias>>,
}
impl<'a, O, T> IterMut<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
pub fn into_bitslice(self) -> &'a mut BitSlice<O, T::Alias> {
unsafe {
BitPtr::new_unchecked(
self.base.as_ptr()
as *const <<T as BitStore>::Alias as BitStore>::Access
as *const <T as BitStore>::Alias,
self.head,
self.len(),
)
}
.to_bitslice_mut()
}
#[inline]
#[doc(hidden)]
#[cfg(not(tarpaulin_include))]
#[deprecated(note = "Use `.into_bitslice` on mutable iterators to view \
the remaining data")]
pub fn into_slice(self) -> &'a mut BitSlice<O, T::Alias> {
self.into_bitslice()
}
fn pop_front(&mut self) -> <Self as Iterator>::Item {
let out =
unsafe { BitMut::new_unchecked(self.base.as_ptr(), self.head) };
let (head, incr) = self.head.incr();
self.base = unsafe {
NonNull::new_unchecked(self.base.as_ptr().add(incr as usize))
};
self.head = head;
out
}
fn pop_back(&mut self) -> <Self as Iterator>::Item {
let (tail, decr) = self.tail.decr();
self.last = unsafe {
NonNull::new_unchecked(self.last.as_ptr().sub(decr as usize))
};
self.tail = tail;
unsafe { BitMut::new_unchecked(self.last.as_ptr(), self.tail) }
}
}
impl<'a, O, T> IntoIterator for &'a mut BitSlice<O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
type IntoIter = IterMut<'a, O, T>;
type Item = <Self::IntoIter as Iterator>::Item;
fn into_iter(self) -> Self::IntoIter {
let (addr, head, bits) = self.alias().bitptr().raw_parts();
let addr = addr.to_access()
as *mut <<T as BitStore>::Alias as BitStore>::Access;
let base = unsafe { NonNull::new_unchecked(addr) };
let (elts, tail) = head.offset(bits as isize);
let last = unsafe { NonNull::new_unchecked(addr.offset(elts)) };
Self::IntoIter {
base,
last,
head,
tail,
_ref: PhantomData,
}
}
}
impl<'a, O, T> Iter<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
const EMPTY: Self = Self {
base: NonNull::dangling().as_ptr() as *const T,
last: NonNull::dangling().as_ptr() as *const T,
head: BitIdx::ZERO,
tail: BitIdx::ZERO,
_ref: PhantomData,
};
#[inline(always)]
fn get_base(&self) -> *const T {
self.base
}
#[inline(always)]
fn get_last(&self) -> *const T {
self.last
}
#[inline(always)]
fn set_base(&mut self, base: *const T) {
self.base = base
}
#[inline(always)]
fn set_last(&mut self, last: *const T) {
self.last = last
}
}
impl<'a, O, T> IterMut<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
const EMPTY: Self = Self {
base: NonNull::dangling(),
last: NonNull::dangling(),
head: BitIdx::ZERO,
tail: BitIdx::ZERO,
_ref: PhantomData,
};
#[inline(always)]
fn get_base(&self) -> *mut <T::Alias as BitStore>::Access {
self.base.as_ptr()
}
#[inline(always)]
fn get_last(&self) -> *mut <T::Alias as BitStore>::Access {
self.last.as_ptr()
}
#[inline(always)]
fn set_base(&mut self, base: *mut <T::Alias as BitStore>::Access) {
self.base = unsafe { NonNull::new_unchecked(base) }
}
#[inline(always)]
fn set_last(&mut self, last: *mut <T::Alias as BitStore>::Access) {
self.last = unsafe { NonNull::new_unchecked(last) }
}
}
macro_rules! iter {
($($t:ident => $i:ty),+ $(,)?) => { $(
impl<'a, O, T> $t<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
pub(crate) fn inherent_is_empty(&self) -> bool {
self.base == self.last && self.head == self.tail
}
}
impl<'a, O, T> Iterator for $t<'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
type Item = $i;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.inherent_is_empty() {
return None;
}
Some(self.pop_front())
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
#[inline]
fn count(self) -> usize {
self.len()
}
#[inline]
fn nth(&mut self, n: usize) -> Option<Self::Item> {
if n >= self.len() {
*self = Self::EMPTY;
return None;
}
let (elts, head) = self.head.offset(n as isize);
self.set_base(unsafe{self.get_base().offset(elts)});
self.head = head;
Some(self.pop_front())
}
#[inline]
fn last(mut self) -> Option<Self::Item> {
self.next_back()
}
}
impl<'a, O, T> DoubleEndedIterator for $t <'a, O, T>
where
O: 'a + BitOrder,
T: 'a + BitStore,
{
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
if self.inherent_is_empty() {
return None;
}
Some(self.pop_back())
}
#[inline]
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
if n >= self.len() {
*self = Self::EMPTY;
return None;
}
let (elts, tail) = self.tail.offset(-(n as isize));
self.set_last(unsafe{self.get_last().offset(elts)});
self.tail = tail;
Some(self.pop_back())
}
}
impl<O, T> ExactSizeIterator for $t <'_, O, T>
where
O: BitOrder,
T: BitStore,
{
fn len(&self) -> usize {
let (base, last) =
(self.get_base() as usize, self.get_last() as usize);
last.wrapping_sub(base)
.wrapping_shl(<u8 as BitMemory>::INDX as u32)
.wrapping_add(self.tail.value() as usize)
.wrapping_sub(self.head.value() as usize)
}
}
impl<O, T> FusedIterator for $t <'_, O, T>
where
O: BitOrder,
T: BitStore
{
}
unsafe impl<O, T> Send for $t <'_, O, T>
where
O: BitOrder,
T: BitStore,
{
}
unsafe impl<O, T> Sync for $t <'_, O, T>
where
O: BitOrder,
T: BitStore,
{
}
)+ };
}
iter!(
Iter => <usize as BitSliceIndex<'a, O, T>>::Immut,
IterMut => <usize as BitSliceIndex<'a, O, T::Alias>>::Mut,
);
macro_rules! group {
(
$iter:ident => $item:ty $( where $alias:ident )? {
$next:item
$nth:item
$next_back:item
$nth_back:item
$len:item
}
) => {
impl<'a, O, T> Iterator for $iter <'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
type Item = $item;
#[inline]
$next
#[inline]
$nth
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
#[inline]
fn count(self) -> usize {
self.len()
}
#[inline]
fn last(mut self) -> Option<Self::Item> {
self.next_back()
}
}
impl<'a, O, T> DoubleEndedIterator for $iter <'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
#[inline]
$next_back
#[inline]
$nth_back
}
impl<O, T> ExactSizeIterator for $iter <'_, O, T>
where
O: BitOrder,
T: BitStore,
{
#[inline]
$len
}
impl<O, T> FusedIterator for $iter <'_, O, T>
where
O: BitOrder,
T: BitStore,
{
}
}
}
#[derive(Clone, Debug)]
pub struct Windows<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a BitSlice<O, T>,
width: usize,
}
group!(Windows => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
if self.width > self.slice.len() {
self.slice = Default::default();
return None;
}
unsafe {
let out = self.slice.get_unchecked(.. self.width);
self.slice = self.slice.get_unchecked(1 ..);
Some(out)
}
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let (end, ovf) = self.width.overflowing_add(n);
if end > self.slice.len() || ovf {
self.slice = Default::default();
return None;
}
unsafe {
let out = self.slice.get_unchecked(n .. end);
self.slice = self.slice.get_unchecked(n + 1 ..);
Some(out)
}
}
fn next_back(&mut self) -> Option<Self::Item> {
let len = self.slice.len();
if self.width > len {
self.slice = Default::default();
return None;
}
unsafe {
let out = self.slice.get_unchecked(len - self.width ..);
self.slice = self.slice.get_unchecked(.. len - 1);
Some(out)
}
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let (end, ovf) = self.slice.len().overflowing_sub(n);
if end < self.width || ovf {
self.slice = Default::default();
return None;
}
unsafe {
let out = self.slice.get_unchecked(end - self.width .. end);
self.slice = self.slice.get_unchecked(.. end - 1);
Some(out)
}
}
fn len(&self) -> usize {
let len = self.slice.len();
if self.width > len {
return 0;
}
len - self.width + 1
}
});
#[derive(Clone, Debug)]
pub struct Chunks<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a BitSlice<O, T>,
width: usize,
}
group!(Chunks => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
let len = self.slice.len();
if len == 0 {
return None;
}
let mid = cmp::min(len, self.width);
let (out, rest) = unsafe { self.slice.split_at_unchecked(mid) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let len = self.slice.len();
let (start, ovf) = n.overflowing_mul(self.width);
if start >= len || ovf {
self.slice = Default::default();
return None;
}
let (out, rest) = unsafe {
self.slice
.get_unchecked(start ..)
.split_at_unchecked(cmp::min(len, self.width))
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
match self.slice.len() {
0 => None,
len => {
let rem = len % self.width;
let size = if rem == 0 { self.width } else { rem };
let (rest, out) =
unsafe { self.slice.split_at_unchecked(len - size) };
self.slice = rest;
Some(out)
},
}
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.len();
if n >= len {
self.slice = Default::default();
return None;
}
let start = (len - 1 - n) * self.width;
let width = cmp::min(start + self.width, self.slice.len());
let (rest, out) = unsafe {
self.slice
.get_unchecked(.. start + width)
.split_at_unchecked(start)
};
self.slice = rest;
Some(out)
}
fn len(&self) -> usize {
match self.slice.len() {
0 => 0,
len => {
let (n, r) = (len / self.width, len % self.width);
n + (r > 0) as usize
},
}
}
});
#[derive(Debug)]
pub struct ChunksMut<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a mut BitSlice<O, T::Alias>,
width: usize,
}
group!(ChunksMut => &'a mut BitSlice<O, T::Alias> {
fn next(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
if len == 0 {
return None;
}
let mid = cmp::min(len, self.width);
let (out, rest) = unsafe { slice.split_at_unchecked_mut_noalias(mid) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
let (start, ovf) = n.overflowing_mul(self.width);
if start >= len || ovf {
return None;
}
let (out, rest) = unsafe {
slice
.get_unchecked_mut(start ..)
.split_at_unchecked_mut_noalias(cmp::min(len, self.width))
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
match slice.len() {
0 => None,
len => {
let rem = len % self.width;
let size = if rem == 0 { self.width } else { rem };
let (rest, out) =
unsafe { slice.split_at_unchecked_mut_noalias(len - size) };
self.slice = rest;
Some(out)
},
}
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.len();
let slice = mem::take(&mut self.slice);
if n >= len {
return None;
}
let start = (len - 1 - n) * self.width;
let width = cmp::min(start + self.width, slice.len());
let (rest, out) = unsafe {
slice
.get_unchecked_mut(.. start + width)
.split_at_unchecked_mut_noalias(start)
};
self.slice = rest;
Some(out)
}
fn len(&self) -> usize {
match self.slice.len() {
0 => 0,
len => {
let (n, r) = (len / self.width, len % self.width);
n + (r > 0) as usize
},
}
}
});
#[derive(Clone, Debug)]
pub struct ChunksExact<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a BitSlice<O, T>,
extra: &'a BitSlice<O, T>,
width: usize,
}
impl<'a, O, T> ChunksExact<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
#[cfg_attr(not(tarpaulin), inline(always))]
pub(super) fn new(slice: &'a BitSlice<O, T>, width: usize) -> Self {
let len = slice.len();
let rem = len % width;
let (slice, extra) = unsafe { slice.split_at_unchecked(len - rem) };
Self {
slice,
extra,
width,
}
}
pub fn remainder(&self) -> &'a BitSlice<O, T> {
self.extra
}
}
group!(ChunksExact => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
if self.slice.len() < self.width {
return None;
}
let (out, rest) = unsafe { self.slice.split_at_unchecked(self.width) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let (start, ovf) = n.overflowing_mul(self.width);
if start + self.width >= self.slice.len() || ovf {
self.slice = Default::default();
return None;
}
let (out, rest) = unsafe {
self.slice
.get_unchecked(start ..)
.split_at_unchecked(self.width)
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
let len = self.slice.len();
if len < self.width {
return None;
}
let (rest, out) =
unsafe { self.slice.split_at_unchecked(len - self.width) };
self.slice = rest;
Some(out)
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.len();
if n >= len {
self.slice = Default::default();
return None;
}
let end = (len - n) * self.width;
let (rest, out) = unsafe {
self.slice
.get_unchecked(.. end)
.split_at_unchecked(end - self.width)
};
self.slice = rest;
Some(out)
}
fn len(&self) -> usize {
self.slice.len() / self.width
}
});
#[derive(Debug)]
pub struct ChunksExactMut<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a mut BitSlice<O, T::Alias>,
extra: &'a mut BitSlice<O, T::Alias>,
width: usize,
}
impl<'a, O, T> ChunksExactMut<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
#[cfg_attr(not(tarpaulin), inline(always))]
pub(super) fn new(slice: &'a mut BitSlice<O, T>, width: usize) -> Self {
let len = slice.len();
let rem = len % width;
let (slice, extra) = unsafe { slice.split_at_unchecked_mut(len - rem) };
Self {
slice,
extra,
width,
}
}
#[inline]
pub fn into_remainder(self) -> &'a mut BitSlice<O, T::Alias> {
self.extra
}
}
group!(ChunksExactMut => &'a mut BitSlice<O, T::Alias> {
fn next(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
if slice.len() < self.width {
return None;
}
let (out, rest) =
unsafe { slice.split_at_unchecked_mut_noalias(self.width) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let (start, ovf) = n.overflowing_mul(self.width);
if start + self.width >= slice.len() || ovf {
return None;
}
let (out, rest) = unsafe {
slice.get_unchecked_mut(start ..)
.split_at_unchecked_mut_noalias(self.width)
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
if len < self.width {
return None;
}
let (rest, out) =
unsafe { slice.split_at_unchecked_mut_noalias(len - self.width) };
self.slice = rest;
Some(out)
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.len();
let slice = mem::take(&mut self.slice);
if n >= len {
return None;
}
let end = (len - n) * self.width;
let (rest, out) = unsafe {
slice.get_unchecked_mut(.. end)
.split_at_unchecked_mut_noalias(end - self.width)
};
self.slice = rest;
Some(out)
}
fn len(&self) -> usize {
self.slice.len() / self.width
}
});
#[derive(Clone, Debug)]
pub struct RChunks<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a BitSlice<O, T>,
width: usize,
}
group!(RChunks => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
let len = self.slice.len();
if len == 0 {
return None;
}
let mid = len - cmp::min(len, self.width);
let (rest, out) = unsafe { self.slice.split_at_unchecked(mid) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let len = self.slice.len();
let (num, ovf) = n.overflowing_mul(self.width);
if num >= len || ovf {
self.slice = Default::default();
return None;
}
let end = len - num;
let mid = end.saturating_sub(self.width);
let (rest, out) = unsafe {
self.slice
.get_unchecked(.. end)
.split_at_unchecked(mid)
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
match self.slice.len() {
0 => None,
n => {
let rem = n % self.width;
let len = if rem == 0 { self.width } else { rem };
let (out, rest) = unsafe { self.slice.split_at_unchecked(len) };
self.slice = rest;
Some(out)
},
}
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.len();
if n >= len {
self.slice = Default::default();
return None;
}
let from_end = (len - 1 - n) * self.width;
let end = self.slice.len() - from_end;
let start = end.saturating_sub(self.width);
let (out, rest) = unsafe { self.slice.split_at_unchecked(end) };
self.slice = rest;
Some(unsafe { out.get_unchecked(start ..) })
}
fn len(&self) -> usize {
match self.slice.len() {
0 => 0,
len => {
let (n, r) = (len / self.width, len % self.width);
n + (r > 0) as usize
},
}
}
});
#[derive(Debug)]
pub struct RChunksMut<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a mut BitSlice<O, T::Alias>,
width: usize,
}
group!(RChunksMut => &'a mut BitSlice<O, T::Alias> {
fn next(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
if len == 0 {
return None;
}
let mid = len - cmp::min(len, self.width);
let (rest, out) = unsafe { slice.split_at_unchecked_mut_noalias(mid) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
let (num, ovf) = n.overflowing_mul(self.width);
if num >= len || ovf {
return None;
}
let end = len - num;
let mid = end.saturating_sub(self.width);
let (rest, out) = unsafe {
slice.get_unchecked_mut(.. end)
.split_at_unchecked_mut_noalias(mid)
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
match slice.len() {
0 => None,
n => {
let rem = n % self.width;
let len = if rem == 0 { self.width } else { rem };
let (out, rest) =
unsafe { slice.split_at_unchecked_mut_noalias(len) };
self.slice = rest;
Some(out)
},
}
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.len();
let slice = mem::take(&mut self.slice);
if n >= len {
return None;
}
let from_end = (len - 1 - n) * self.width;
let end = slice.len() - from_end;
let start = end.saturating_sub(self.width);
let (out, rest) = unsafe { slice.split_at_unchecked_mut_noalias(end) };
self.slice = rest;
Some(unsafe { out.get_unchecked_mut(start ..) })
}
fn len(&self) -> usize {
match self.slice.len() {
0 => 0,
len => {
let (n, r) = (len / self.width, len % self.width);
n + (r > 0) as usize
},
}
}
});
#[derive(Clone, Debug)]
pub struct RChunksExact<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a BitSlice<O, T>,
extra: &'a BitSlice<O, T>,
width: usize,
}
impl<'a, O, T> RChunksExact<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
#[cfg_attr(not(tarpaulin), inline(always))]
pub(super) fn new(slice: &'a BitSlice<O, T>, width: usize) -> Self {
let (extra, slice) =
unsafe { slice.split_at_unchecked(slice.len() % width) };
Self {
slice,
extra,
width,
}
}
#[inline]
pub fn remainder(&self) -> &'a BitSlice<O, T> {
self.extra
}
}
group!(RChunksExact => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
let len = self.slice.len();
if len < self.width {
return None;
}
let (rest, out) =
unsafe { self.slice.split_at_unchecked(len - self.width) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let len = self.slice.len();
let (split, ovf) = n.overflowing_mul(self.width);
if split >= len || ovf {
self.slice = Default::default();
return None;
}
let end = len - split;
let (rest, out) = unsafe {
self.slice
.get_unchecked(.. end)
.split_at_unchecked(end - self.width)
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
if self.slice.len() < self.width {
return None;
}
let (out, rest) = unsafe { self.slice.split_at_unchecked(self.width) };
self.slice = rest;
Some(out)
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let len = self.slice.len();
let (start, ovf) = n.overflowing_mul(self.width);
if start >= len || ovf {
self.slice = Default::default();
return None;
}
let (out, rest) = unsafe {
self.slice.get_unchecked(start ..).split_at_unchecked(self.width)
};
self.slice = rest;
Some(out)
}
fn len(&self) -> usize {
self.slice.len() / self.width
}
});
#[derive(Debug)]
pub struct RChunksExactMut<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
slice: &'a mut BitSlice<O, T::Alias>,
extra: &'a mut BitSlice<O, T::Alias>,
width: usize,
}
impl<'a, O, T> RChunksExactMut<'a, O, T>
where
O: BitOrder,
T: 'a + BitStore,
{
#[cfg_attr(not(tarpaulin), inline(always))]
pub(super) fn new(slice: &'a mut BitSlice<O, T>, width: usize) -> Self {
let (extra, slice) =
unsafe { slice.split_at_unchecked_mut(slice.len() % width) };
Self {
slice,
extra,
width,
}
}
#[inline]
pub fn into_remainder(self) -> &'a mut BitSlice<O, T::Alias> {
self.extra
}
}
group!(RChunksExactMut => &'a mut BitSlice<O, T::Alias> {
fn next(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
if len < self.width {
return None;
}
let (rest, out) =
unsafe { slice.split_at_unchecked_mut_noalias(len - self.width) };
self.slice = rest;
Some(out)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
let (split, ovf) = n.overflowing_mul(self.width);
if split >= len || ovf {
return None;
}
let end = len - split;
let (rest, out) = unsafe {
slice.get_unchecked_mut(.. end)
.split_at_unchecked_mut_noalias(end - self.width)
};
self.slice = rest;
Some(out)
}
fn next_back(&mut self) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
if slice.len() < self.width {
return None;
}
let (out, rest) =
unsafe { slice.split_at_unchecked_mut_noalias(self.width) };
self.slice = rest;
Some(out)
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let slice = mem::take(&mut self.slice);
let len = slice.len();
let (start, ovf) = n.overflowing_mul(self.width);
if start >= len || ovf {
return None;
}
let (out, rest) = unsafe {
slice.get_unchecked_mut(start ..)
.split_at_unchecked_mut_noalias(self.width)
};
self.slice = rest;
Some(out)
}
fn len(&self) -> usize {
self.slice.len() / self.width
}
});
macro_rules! new_group {
($($t:ident $($m:ident)? $( . $a:ident ())?),+ $(,)?) => { $(
impl<'a, O, T> $t <'a, O, T>
where
O: BitOrder,
T: BitStore
{
#[cfg_attr(not(tarpaulin), inline(always))]
#[allow(clippy::redundant_field_names)]
pub(super) fn new(
slice: &'a $($m)? BitSlice<O, T>,
width: usize,
) -> Self {
Self { slice: slice $( . $a () )?, width }
}
}
)+ };
}
new_group!(
Windows,
Chunks,
ChunksMut mut .alias_mut(),
RChunks,
RChunksMut mut .alias_mut(),
);
macro_rules! split {
($iter:ident => $item:ty $( where $alias:ident )? {
$next:item
$next_back:item
}) => {
impl<'a, O, T, P> $iter <'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
#[inline]
pub(super) fn new(slice: $item, pred: P) -> Self {
Self {
slice,
pred,
done: false,
}
}
}
impl<O, T, P> Debug for $iter <'_, O, T, P>
where
O: BitOrder,
T: BitStore,
P: FnMut(usize, &bool) -> bool,
{
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
fmt.debug_struct(stringify!($iter))
.field("slice", &self.slice)
.field("done", &self.done)
.finish()
}
}
impl<'a, O, T, P> Iterator for $iter <'a, O, T, P>
where
O: 'a + BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
type Item = $item;
#[inline]
$next
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
if self.done {
(0, Some(0))
}
else {
(1, Some(self.slice.len() + 1))
}
}
}
impl<'a, O, T, P> DoubleEndedIterator for $iter <'a, O, T, P>
where
O: 'a + BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
#[inline]
$next_back
}
impl<'a, O, T, P> core::iter::FusedIterator for $iter <'a, O, T, P>
where
O: 'a + BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
}
impl<'a, O, T, P> SplitIter for $iter <'a, O, T, P>
where
O: 'a + BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
#[inline]
fn finish(&mut self) -> Option<Self::Item> {
if self.done {
None
}
else {
self.done = true;
Some(mem::take(&mut self.slice))
}
}
}
};
}
#[derive(Clone)]
pub struct Split<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
slice: &'a BitSlice<O, T>,
pred: P,
done: bool,
}
split!(Split => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
match self.slice
.iter()
.enumerate()
.position(|(idx, bit)| (self.pred)(idx, bit))
{
None => self.finish(),
Some(idx) => unsafe {
let out = self.slice.get_unchecked(.. idx);
self.slice = self.slice.get_unchecked(idx + 1 ..);
Some(out)
},
}
}
fn next_back(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
match self.slice
.iter()
.enumerate()
.rposition(|(idx, bit)| (self.pred)(idx, bit))
{
None => self.finish(),
Some(idx) => unsafe {
let out = self.slice.get_unchecked(idx + 1 ..);
self.slice = self.slice.get_unchecked(.. idx);
Some(out)
},
}
}
});
pub struct SplitMut<'a, O, T, P>
where
O: BitOrder,
T: BitStore,
P: FnMut(usize, &bool) -> bool,
{
slice: &'a mut BitSlice<O, T::Alias>,
pred: P,
done: bool,
}
split!(SplitMut => &'a mut BitSlice<O, T::Alias> {
fn next(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
let idx_opt = {
let pred = &mut self.pred;
self.slice
.iter()
.enumerate()
.position(|(idx, bit)| (pred)(idx, bit))
};
match idx_opt
{
None => self.finish(),
Some(idx) => unsafe {
let slice = mem::take(&mut self.slice);
let (out, rest) = slice.split_at_unchecked_mut_noalias(idx);
self.slice = rest.get_unchecked_mut(1 ..);
Some(out)
},
}
}
fn next_back(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
let idx_opt = {
let pred = &mut self.pred;
self.slice
.iter()
.enumerate()
.rposition(|(idx, bit)| (pred)(idx, bit))
};
match idx_opt
{
None => self.finish(),
Some(idx) => unsafe {
let slice = mem::take(&mut self.slice);
let (rest, out) = slice.split_at_unchecked_mut_noalias(idx);
self.slice = rest;
Some(out.get_unchecked_mut(1 ..))
},
}
}
});
#[derive(Clone)]
pub struct RSplit<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
slice: &'a BitSlice<O, T>,
pred: P,
done: bool,
}
split!(RSplit => &'a BitSlice<O, T> {
fn next(&mut self) -> Option<Self::Item> {
let mut split = Split::<'a, O, T, &mut P> {
slice: mem::take(&mut self.slice),
pred: &mut self.pred,
done: self.done,
};
let out = split.next_back();
self.slice = mem::take(&mut split.slice);
self.done = split.done;
out
}
fn next_back(&mut self) -> Option<Self::Item> {
let mut split = Split::<'a, O, T, &mut P> {
slice: mem::take(&mut self.slice),
pred: &mut self.pred,
done: self.done,
};
let out = split.next();
self.slice = mem::take(&mut split.slice);
self.done = split.done;
out
}
});
pub struct RSplitMut<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
slice: &'a mut BitSlice<O, T::Alias>,
pred: P,
done: bool,
}
split!(RSplitMut => &'a mut BitSlice<O, T::Alias> {
fn next(&mut self) -> Option<Self::Item> {
let mut split = SplitMut::<'a, O, T, &mut P> {
slice: mem::take(&mut self.slice),
pred: &mut self.pred,
done: self.done,
};
let out = split.next_back();
self.slice = mem::take(&mut split.slice);
self.done = split.done;
out
}
fn next_back(&mut self) -> Option<Self::Item> {
let mut split = SplitMut::<'a, O, T, &mut P> {
slice: mem::take(&mut self.slice),
pred: &mut self.pred,
done: self.done,
};
let out = split.next();
self.slice = mem::take(&mut split.slice);
self.done = split.done;
out
}
});
#[doc(hidden)]
trait SplitIter: DoubleEndedIterator {
fn finish(&mut self) -> Option<Self::Item>;
}
pub struct SplitN<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
inner: Split<'a, O, T, P>,
count: usize,
}
pub struct SplitNMut<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
inner: SplitMut<'a, O, T, P>,
count: usize,
}
pub struct RSplitN<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
inner: RSplit<'a, O, T, P>,
count: usize,
}
pub struct RSplitNMut<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
inner: RSplitMut<'a, O, T, P>,
count: usize,
}
macro_rules! split_n {
($outer:ident => $inner:ident => $item:ty $( where $alias:ident )?) => {
impl<'a, O, T, P> $outer<'a, O, T, P>
where
O: BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
{
pub(super) fn new(
slice: $item,
pred: P,
count: usize,
) -> Self
{Self{
inner: <$inner<'a, O, T, P>>::new(slice, pred),
count,
}}
}
impl<O, T, P> Debug for $outer<'_, O, T, P>
where
O: BitOrder,
T: BitStore,
P: FnMut(usize, &bool) -> bool
{
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
fmt.debug_struct(stringify!($outer))
.field("slice", &self.inner.slice)
.field("count", &self.count)
.finish()
}
}
impl<'a, O, T, P> Iterator for $outer<'a, O, T, P>
where
O: 'a + BitOrder,
T: 'a + BitStore,
P: FnMut(usize, &bool) -> bool,
$( T::$alias: radium::Radium<<<T as BitStore>::Alias as BitStore>::Mem>, )?
{
type Item = <$inner <'a, O, T, P> as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
match self.count {
0 => None,
1 => {
self.count -= 1;
self.inner.finish()
},
_ => {
self.count -= 1;
self.inner.next()
},
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (low, hi) = self.inner.size_hint();
(low, hi.map(|h| cmp::min(self.count, h)))
}
}
impl<O, T, P> core::iter::FusedIterator for $outer<'_, O, T, P>
where
O: BitOrder,
T: BitStore,
P: FnMut(usize, &bool) -> bool,
$( T::$alias: radium::Radium<<<T as BitStore>::Alias as BitStore>::Mem>, )?
{
}
};
}
split_n!(SplitN => Split => &'a BitSlice<O, T>);
split_n!(SplitNMut => SplitMut => &'a mut BitSlice<O, T::Alias> );
split_n!(RSplitN => RSplit => &'a BitSlice<O, T>);
split_n!(RSplitNMut => RSplitMut => &'a mut BitSlice<O, T::Alias> );
#[cfg(test)]
mod tests {
use crate::prelude::*;
#[test]
fn iter() {
let data = 0b0110_1001u8;
let bits = data.view_bits::<Msb0>();
let mut iter = bits.iter();
assert_eq!(iter.as_bitslice(), bits);
assert_eq!(iter.next(), Some(&false));
assert_eq!(iter.as_bitslice(), &bits[1 ..]);
assert_eq!(iter.next(), Some(&true));
assert_eq!(iter.as_bitslice(), &bits[2 ..]);
assert_eq!(iter.next_back(), Some(&true));
assert_eq!(iter.as_bitslice(), &bits[2 .. 7]);
assert_eq!(iter.next_back(), Some(&false));
assert_eq!(iter.as_bitslice(), &bits[2 .. 6]);
assert_eq!(iter.next(), Some(&true));
assert_eq!(iter.as_bitslice(), &bits[3 .. 6]);
assert_eq!(iter.next(), Some(&false));
assert_eq!(iter.as_bitslice(), &bits[4 .. 6]);
assert_eq!(iter.next_back(), Some(&false));
assert_eq!(iter.as_bitslice(), &bits[4 .. 5]);
assert_eq!(iter.next_back(), Some(&true));
assert!(iter.as_bitslice().is_empty());
assert!(iter.next().is_none());
assert!(iter.next_back().is_none());
}
#[test]
fn iter_mut() {
let mut data = 0b0110_1001u8;
let bits = data.view_bits_mut::<Msb0>();
let mut iter = bits.iter_mut();
*iter.next().unwrap() = true;
*iter.nth_back(1).unwrap() = true;
*iter.nth(2).unwrap() = true;
*iter.next_back().unwrap() = true;
assert_eq!(iter.into_bitslice().bitptr(), bits[4 .. 5].bitptr());
}
#[test]
fn windows() {
let data = 0u8;
let bits = data.view_bits::<LocalBits>();
let mut windows = bits.windows(5);
assert_eq!(windows.next().unwrap().bitptr(), bits[.. 5].bitptr());
assert_eq!(windows.next_back().unwrap().bitptr(), bits[3 ..].bitptr());
let mut windows = bits.windows(3);
assert_eq!(windows.nth(2).unwrap().bitptr(), bits[2 .. 5].bitptr());
assert_eq!(windows.nth_back(2).unwrap().bitptr(), bits[3 .. 6].bitptr());
assert!(windows.next().is_none());
assert!(windows.next_back().is_none());
assert!(windows.nth(1).is_none());
assert!(windows.nth_back(1).is_none());
}
#[test]
fn chunks() {
let data = 0u16;
let bits = data.view_bits::<LocalBits>();
let mut chunks = bits.chunks(5);
assert_eq!(chunks.next().unwrap().bitptr(), bits[.. 5].bitptr());
assert_eq!(chunks.next_back().unwrap().bitptr(), bits[15 ..].bitptr());
let mut chunks = bits.chunks(3);
assert_eq!(chunks.nth(2).unwrap().bitptr(), bits[6 .. 9].bitptr());
assert_eq!(chunks.nth_back(2).unwrap().bitptr(), bits[9 .. 12].bitptr());
}
#[test]
fn chunks_mut() {
let mut data = 0u16;
let bits = data.view_bits_mut::<LocalBits>();
let (one, two, three, four) = (
bits[.. 5].bitptr(),
bits[15 ..].bitptr(),
bits[6 .. 9].bitptr(),
bits[9 .. 12].bitptr(),
);
let mut chunks = bits.chunks_mut(5);
assert_eq!(chunks.next().unwrap().bitptr(), one);
assert_eq!(chunks.next_back().unwrap().bitptr(), two);
let mut chunks = bits.chunks_mut(3);
assert_eq!(chunks.nth(2).unwrap().bitptr(), three);
assert_eq!(chunks.nth_back(2).unwrap().bitptr(), four);
}
#[test]
fn chunks_exact() {
let data = 0u32;
let bits = data.view_bits::<LocalBits>();
let mut chunks = bits.chunks_exact(5);
assert_eq!(chunks.remainder().bitptr(), bits[30 ..].bitptr());
assert_eq!(chunks.next().unwrap().bitptr(), bits[.. 5].bitptr());
assert_eq!(
chunks.next_back().unwrap().bitptr(),
bits[25 .. 30].bitptr(),
);
assert_eq!(chunks.nth(1).unwrap().bitptr(), bits[10 .. 15].bitptr());
assert_eq!(
chunks.nth_back(1).unwrap().bitptr(),
bits[15 .. 20].bitptr(),
);
assert!(chunks.next().is_none());
assert!(chunks.next_back().is_none());
assert!(chunks.nth(1).is_none());
assert!(chunks.nth_back(1).is_none());
}
#[test]
fn chunks_exact_mut() {
let mut data = 0u32;
let bits = data.view_bits_mut::<LocalBits>();
let (one, two, three, four, rest) = (
bits[.. 5].bitptr(),
bits[10 .. 15].bitptr(),
bits[15 .. 20].bitptr(),
bits[25 .. 30].bitptr(),
bits[30 ..].bitptr(),
);
let mut chunks = bits.chunks_exact_mut(5);
assert_eq!(chunks.next().unwrap().bitptr(), one);
assert_eq!(chunks.next_back().unwrap().bitptr(), four);
assert_eq!(chunks.nth(1).unwrap().bitptr(), two);
assert_eq!(chunks.nth_back(1).unwrap().bitptr(), three);
assert!(chunks.next().is_none());
assert!(chunks.next_back().is_none());
assert!(chunks.nth(1).is_none());
assert!(chunks.nth_back(1).is_none());
assert_eq!(chunks.into_remainder().bitptr(), rest);
}
#[test]
fn rchunks() {
let data = 0u16;
let bits = data.view_bits::<LocalBits>();
let mut rchunks = bits.rchunks(5);
assert_eq!(rchunks.next().unwrap().bitptr(), bits[11 ..].bitptr());
assert_eq!(rchunks.next_back().unwrap().bitptr(), bits[.. 1].bitptr());
let mut rchunks = bits.rchunks(3);
assert_eq!(rchunks.nth(2).unwrap().bitptr(), bits[7 .. 10].bitptr());
assert_eq!(rchunks.nth_back(2).unwrap().bitptr(), bits[4 .. 7].bitptr());
}
#[test]
fn rchunks_mut() {
let mut data = 0u16;
let bits = data.view_bits_mut::<LocalBits>();
let (one, two, three, four) = (
bits[11 ..].bitptr(),
bits[.. 1].bitptr(),
bits[7 .. 10].bitptr(),
bits[4 .. 7].bitptr(),
);
let mut rchunks = bits.rchunks_mut(5);
assert_eq!(rchunks.next().unwrap().bitptr(), one);
assert_eq!(rchunks.next_back().unwrap().bitptr(), two);
let mut rchunks = bits.rchunks_mut(3);
assert_eq!(rchunks.nth(2).unwrap().bitptr(), three);
assert_eq!(rchunks.nth_back(2).unwrap().bitptr(), four);
}
#[test]
fn rchunks_exact() {
let data = 0u32;
let bits = data.view_bits::<LocalBits>();
let mut rchunks = bits.rchunks_exact(5);
assert_eq!(rchunks.remainder().bitptr(), bits[.. 2].bitptr());
assert_eq!(rchunks.next().unwrap().bitptr(), bits[27 ..].bitptr());
assert_eq!(rchunks.next_back().unwrap().bitptr(), bits[2 .. 7].bitptr(),);
assert_eq!(rchunks.nth(1).unwrap().bitptr(), bits[17 .. 22].bitptr());
assert_eq!(
rchunks.nth_back(1).unwrap().bitptr(),
bits[12 .. 17].bitptr(),
);
assert!(rchunks.next().is_none());
assert!(rchunks.next_back().is_none());
assert!(rchunks.nth(1).is_none());
assert!(rchunks.nth_back(1).is_none());
}
#[test]
fn rchunks_exact_mut() {
let mut data = 0u32;
let bits = data.view_bits_mut::<LocalBits>();
let (rest, one, two, three, four) = (
bits[.. 2].bitptr(),
bits[2 .. 7].bitptr(),
bits[12 .. 17].bitptr(),
bits[17 .. 22].bitptr(),
bits[27 ..].bitptr(),
);
let mut rchunks = bits.rchunks_exact_mut(5);
assert_eq!(rchunks.next().unwrap().bitptr(), four);
assert_eq!(rchunks.next_back().unwrap().bitptr(), one);
assert_eq!(rchunks.nth(1).unwrap().bitptr(), three);
assert_eq!(rchunks.nth_back(1).unwrap().bitptr(), two);
assert!(rchunks.next().is_none());
assert!(rchunks.next_back().is_none());
assert!(rchunks.nth(1).is_none());
assert!(rchunks.nth_back(1).is_none());
assert_eq!(rchunks.into_remainder().bitptr(), rest);
}
}