use std::ptr::NonNull;
use std::marker::PhantomData;
use std::cmp::Ord;
use std::iter::Iterator;
use std::iter::ExactSizeIterator;
use std::iter::DoubleEndedIterator;
use std::iter::FromIterator;
use std::iter::FusedIterator;
use std::ops::{
BitAnd, BitAndAssign,
BitOr, BitOrAssign,
BitXor, BitXorAssign,
};
mod bool_ref;
use bool_ref::*;
pub use bool_ref::RefBool;
pub use bool_ref::RefBoolMut;
mod mask;
use mask::*;
pub(crate) fn count_ones(mut value: u8) -> u8 {
let mut result = 0;
while value != 0 {
result += value & 1;
value >>= 1;
}
result
}
const fn deconstruct_nth(nth: usize) -> (usize, Mask) {
(nth / 8, Mask::VALUES[nth % 8])
}
#[derive(Clone)]
pub struct BoolVec {
vec: Vec<u8>,
bit_mask: Mask,
}
impl BoolVec {
#[inline(always)]
pub const fn new() -> Self {
Self {
vec: Vec::new(),
bit_mask: Mask::VALUES[7],
}
}
#[inline(always)]
pub fn with_capacity(capacity: usize) -> Self {
Self {
vec: Vec::with_capacity(capacity),
bit_mask: Mask::VALUES[7],
}
}
pub fn filled_with(count: usize, value: bool) -> Self {
let value = if value { 255 } else { 0 };
let (bytes, bit_mask) = if count == 0 {
(Vec::new(), Mask::VALUES[7])
}
else {
let mut bytes = vec![value; count / 8];
bytes.push(
value << (7 - ((count - 1) % 8))
);
(bytes, Mask::VALUES[(count - 1) % 8])
};
Self {
vec: bytes,
bit_mask,
}
}
pub fn from_vec(vec: Vec<u8>) -> Self {
Self {
vec,
bit_mask: Mask::VALUES[7],
}
}
#[inline]
pub fn count(&self) -> usize {
if self.vec.len() == 0 {
0
}
else {
self.vec.len() * 8 - 7 + self.bit_mask.offset()
}
}
#[inline]
pub fn is_empty(&self) -> bool {
self.count() == 0
}
#[inline(always)]
pub fn capacity(&self) -> usize {
self.vec.capacity()
}
#[inline(always)]
pub fn reserve(&mut self, additional_capacity: usize) {
self.vec.reserve(additional_capacity);
}
#[inline(always)]
pub fn reserve_exact(&mut self, additional_capacity: usize) {
self.vec.reserve_exact(additional_capacity);
}
#[inline(always)]
pub fn shrink_to_fit(&mut self) {
self.vec.shrink_to_fit();
}
pub fn truncate(&mut self, count: usize) {
if count >= self.count() {
return;
}
let (kept_length, new_bit_mask) = if count == 0 {
(0, Mask::VALUES[7])
}
else {
(count / 8 + 1, Mask::VALUES[(count - 1) % 8])
};
self.vec.truncate(kept_length);
self.bit_mask = new_bit_mask;
}
#[inline]
pub unsafe fn get_unchecked_ref(&self, nth: usize) -> RefBool {
let (index, bit_mask) = deconstruct_nth(nth);
RefBool::new(
self.vec.get_unchecked(index),
bit_mask
)
}
#[inline(always)]
pub unsafe fn get_unchecked(&self, nth: usize) -> bool {
self.get_unchecked_ref(nth).get()
}
#[inline]
pub fn get_ref(&self, nth: usize) -> Option<RefBool> {
if nth >= self.count() {
None
}
else { unsafe {
Some(self.get_unchecked_ref(nth))
} }
}
#[inline]
pub fn get(&self, nth: usize) -> Option<bool> {
if nth >= self.count() {
None
}
else { unsafe {
Some(self.get_unchecked(nth))
} }
}
#[inline]
pub unsafe fn get_unchecked_mut(&mut self, nth: usize) -> RefBoolMut {
let (index, bit_mask) = deconstruct_nth(nth);
RefBoolMut::new(
self.vec.get_unchecked_mut(index),
bit_mask,
)
}
#[inline]
pub fn get_mut(&mut self, nth: usize) -> Option<RefBoolMut> {
if nth >= self.count() {
None
}
else { unsafe {
Some(self.get_unchecked_mut(nth))
} }
}
#[inline(always)]
pub unsafe fn set_unchecked(&mut self, nth: usize, value: bool) {
self.get_unchecked_mut(nth).set(value);
}
#[inline]
pub fn set(&mut self, nth: usize, value: bool) {
if nth >= self.count() {
panic!("nth was {} but the count was {}.", nth, self.count());
}
else { unsafe {
self.set_unchecked(nth, value)
} }
}
pub fn push(&mut self, value: bool) {
self.bit_mask >>= 1;
if self.bit_mask == Mask::VALUES[0] {
self.vec.push(0)
}
unsafe {
self.set_unchecked(self.count() - 1, value);
}
}
pub fn pop(&mut self) -> Option<bool> {
if self.count() == 0 {
None
}
else {
let result = unsafe { self.get_unchecked(self.count() - 1) };
self.bit_mask <<= 1;
if self.bit_mask == Mask::VALUES[7] {
self.vec.pop();
}
Some(result)
}
}
pub fn last_ref(&self) -> Option<RefBool> {
let count = self.count();
if count == 0 {
None
}
else { unsafe {
Some(self.get_unchecked_ref(count - 1))
} }
}
pub fn last_mut(&mut self) -> Option<RefBoolMut> {
let count = self.count();
if count == 0 {
None
}
else { unsafe {
Some(self.get_unchecked_mut(count - 1))
} }
}
pub fn last(&self) -> Option<bool> {
let count = self.count();
if count == 0 {
None
}
else { unsafe {
Some(self.get_unchecked(count - 1))
}}
}
pub fn clear(&mut self) {
self.vec.clear();
self.bit_mask = Mask::VALUES[7];
}
unsafe fn unsafe_iter(&self) -> UnsafeIter {
UnsafeIter {
start: UnsafeBoolRef::new(
NonNull::new(self.vec.as_ptr() as *mut u8).unwrap(),
Mask::VALUES[0],
),
end: UnsafeBoolRef::new(
NonNull::new(self.vec.as_ptr().add({
if self.count() == 0 {
0
}
else {
self.vec.len() - 1
}
}) as *mut u8).unwrap(),
self.bit_mask,
).next_bit()
}
}
pub fn iter(&self) -> Iter {
Iter {
inner: unsafe { self.unsafe_iter() },
_marker: PhantomData,
}
}
pub fn iter_mut(&mut self) -> IterMut {
IterMut {
inner: unsafe { self.unsafe_iter() },
_marker: PhantomData,
}
}
pub fn bytes(&self) -> impl Iterator<Item=&u8> {
self.vec.iter()
}
pub fn bytes_mut(&mut self) -> impl Iterator<Item=&mut u8> {
self.vec.iter_mut()
}
pub fn count_ones(&self) -> usize {
self.bytes()
.map(|&b| count_ones(b) as usize)
.sum::<usize>()
}
}
impl<'s> BitAnd<&'s BoolVec> for &'s BoolVec {
type Output = BoolVec;
fn bitand(self: &'s BoolVec, other: &'s BoolVec) -> BoolVec {
let mut result = BoolVec::with_capacity(
Ord::min(self.vec.len(), other.vec.len())
);
for (&a, &b) in self.bytes().zip(other.bytes()) {
result.vec.push(a & b);
}
result.bit_mask = Ord::min(self.bit_mask, other.bit_mask);
result
}
}
impl<'s> BitAndAssign<&'s BoolVec> for BoolVec {
fn bitand_assign(&mut self, other: &'s BoolVec) {
for (byte, &o_byte) in self.bytes_mut().zip(other.bytes()) {
*byte &= o_byte;
}
}
}
impl<'s> BitOr<&'s BoolVec> for &'s BoolVec {
type Output = BoolVec;
fn bitor(self: &'s BoolVec, other: &'s BoolVec) -> BoolVec {
let mut result = BoolVec::with_capacity(
Ord::min(self.vec.len(), other.vec.len())
);
for (&a, &b) in self.bytes().zip(other.bytes()) {
result.vec.push(a | b);
}
result.bit_mask = Ord::max(self.bit_mask, other.bit_mask);
result
}
}
impl<'s> BitOrAssign<&'s BoolVec> for BoolVec {
fn bitor_assign(&mut self, other: &'s BoolVec) {
for (byte, &o_byte) in self.bytes_mut().zip(other.bytes()) {
*byte |= o_byte;
}
}
}
impl<'s> BitXor<&'s BoolVec> for &'s BoolVec {
type Output = BoolVec;
fn bitxor(self: &'s BoolVec, other: &'s BoolVec) -> BoolVec {
let mut result = BoolVec::with_capacity(
Ord::min(self.vec.len(), other.vec.len())
);
for (&a, &b) in self.bytes().zip(other.bytes()) {
result.vec.push(a ^ b);
}
result.bit_mask = Ord::max(self.bit_mask, other.bit_mask);
result
}
}
impl<'s> BitXorAssign<&'s BoolVec> for BoolVec {
fn bitxor_assign(&mut self, other: &'s BoolVec) {
for (byte, &o_byte) in self.bytes_mut().zip(other.bytes()) {
*byte ^= o_byte;
}
}
}
impl FromIterator<bool> for BoolVec {
fn from_iter<S: IntoIterator<Item=bool>>(iter: S) -> Self {
let iter = iter.into_iter();
let mut result = Self::with_capacity(iter.size_hint().0);
for bit in iter {
result.push(bit);
}
result
}
}
impl FromIterator<u8> for BoolVec {
fn from_iter<S: IntoIterator<Item=u8>>(iter: S) -> Self {
let iter = iter.into_iter();
let mut result = Vec::with_capacity(iter.size_hint().0);
for byte in iter {
result.push(byte)
}
Self::from_vec(result)
}
}
#[derive(Clone)]
struct UnsafeIter {
start: UnsafeBoolRef,
end: UnsafeBoolRef,
}
impl Iterator for UnsafeIter {
type Item = UnsafeBoolRef;
fn next(&mut self) -> Option<UnsafeBoolRef> {
if self.start >= self.end {
None
}
else {
let temp = self.start.clone();
unsafe { self.start = self.start.next_bit() }
Some(temp)
}
}
#[inline(always)]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl ExactSizeIterator for UnsafeIter {
fn len(&self) -> usize {
let start = self.start.byte.as_ptr() as usize;
let end = self.end.byte.as_ptr() as usize;
let start_bit = self.start.bit_mask.offset();
let end_bit = self.end.bit_mask.offset();
(end - start) * 8 + (end_bit - start_bit)
}
}
impl DoubleEndedIterator for UnsafeIter {
fn next_back(&mut self) -> Option<UnsafeBoolRef> {
if self.start >= self.end {
None
}
else {
unsafe { self.end = self.end.prev_bit() }
Some(self.end.clone())
}
}
}
impl FusedIterator for UnsafeIter { }
#[derive(Clone)]
pub struct Iter<'s> {
inner: UnsafeIter,
_marker: PhantomData<&'s [u8]>,
}
impl<'s> Iterator for Iter<'s> {
type Item = bool;
#[inline]
fn next(&mut self) -> Option<bool> {
match self.inner.next() {
Some(val) => unsafe { Some(val.get()) },
None => None,
}
}
#[inline(always)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<'s> ExactSizeIterator for Iter<'s> {
#[inline(always)]
fn len(&self) -> usize { self.inner.len() }
}
impl<'s> DoubleEndedIterator for Iter<'s> {
#[inline]
fn next_back(&mut self) -> Option<bool> {
match self.inner.next_back() {
Some(val) => unsafe { Some(val.get()) },
None => None,
}
}
}
impl<'s> FusedIterator for Iter<'s> { }
#[derive(Clone)]
pub struct IterMut<'s> {
inner: UnsafeIter,
_marker: PhantomData<&'s mut [u8]>,
}
impl<'s> Iterator for IterMut<'s> {
type Item = RefBoolMut<'s>;
#[inline]
fn next(&mut self) -> Option<RefBoolMut<'s>> {
match self.inner.next() {
Some(val) => Some(RefBoolMut::from_inner(val)),
None => None,
}
}
#[inline(always)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<'s> ExactSizeIterator for IterMut<'s> {
#[inline(always)]
fn len(&self) -> usize { self.inner.len() }
}
impl<'s> DoubleEndedIterator for IterMut<'s> {
#[inline]
fn next_back(&mut self) -> Option<RefBoolMut<'s>> {
match self.inner.next_back() {
Some(val) => Some(RefBoolMut::from_inner(val)),
None => None,
}
}
}
impl<'s> FusedIterator for IterMut<'s> { }
#[cfg(test)]
mod vec_tests {
use super::*;
#[test]
fn create_vector() {
let vec = BoolVec::new();
assert_eq!(vec.capacity(), 0);
assert_eq!(vec.count(), 0);
assert!(vec.is_empty());
let vec = BoolVec::with_capacity(0);
assert_eq!(vec.capacity(), 0);
assert_eq!(vec.count(), 0);
assert!(vec.is_empty());
let vec = BoolVec::with_capacity(10);
assert_eq!(vec.capacity(), 10);
assert_eq!(vec.count(), 0);
assert!(vec.is_empty());
let vec = BoolVec::filled_with(4, true);
assert_eq!(vec.capacity(), 1);
assert_eq!(vec.count(), 4);
assert_eq!(vec.vec.len(), 1);
assert_eq!(vec.vec[0], 0b1111_0000);
assert!(!vec.is_empty());
let vec = BoolVec::filled_with(9, false);
assert_eq!(vec.capacity(), 2);
assert_eq!(vec.count(), 9);
assert_eq!(vec.vec.len(), 2);
assert!(!vec.is_empty());
assert_eq!(vec.vec[0], 0);
assert_eq!(vec.vec[1], 0);
}
#[test]
fn truncate() {
let mut vec = BoolVec::new();
vec.push(true);
vec.push(false);
vec.push(false);
vec.push(true);
assert_eq!(vec.count(), 4);
vec.truncate(2);
assert_eq!(vec.count(), 2);
assert_eq!(vec.get(0), Some(true));
assert_eq!(vec.get(1), Some(false));
assert_eq!(vec.get(2), None);
assert_eq!(vec.get(3), None);
}
#[test]
fn pop() {
let mut vec = BoolVec::new();
vec.push(true);
vec.push(false);
vec.push(true);
vec.push(true);
vec.push(false);
vec.push(false);
assert_eq!(vec.pop(), Some(false));
assert_eq!(vec.pop(), Some(false));
assert_eq!(vec.pop(), Some(true));
assert_eq!(vec.pop(), Some(true));
assert_eq!(vec.pop(), Some(false));
assert_eq!(vec.pop(), Some(true));
assert_eq!(vec.pop(), None);
assert_eq!(vec.pop(), None);
assert_eq!(vec.last(), None);
}
#[test]
fn pushes() {
let mut vec = BoolVec::new();
assert_eq!(vec.vec.len(), 0);
assert_eq!(vec.count(), 0);
vec.push(false);
vec.push(true);
vec.push(true);
vec.push(false);
println!("{:#b}", vec.vec[0]);
assert_eq!(vec.count(), 4);
assert_eq!(vec.vec.len(), 1);
assert_eq!(vec.get(0), Some(false));
assert_eq!(vec.get(1), Some(true));
assert_eq!(vec.get(2), Some(true));
assert_eq!(vec.get(3), Some(false));
assert_eq!(vec.get(4), None);
assert_eq!(vec.last(), Some(false));
vec.set(0, true);
vec.set(1, false);
vec.set(2, false);
vec.set(3, true);
assert_eq!(vec.get(0), Some(true));
assert_eq!(vec.get(1), Some(false));
assert_eq!(vec.get(2), Some(false));
assert_eq!(vec.get(3), Some(true));
assert_eq!(vec.get(4), None);
assert_eq!(vec.last(), Some(true));
}
#[test]
fn iterators() {
let mut vec = BoolVec::new();
vec.push(true);
vec.push(false);
vec.push(false);
vec.push(false);
vec.push(true);
vec.push(true);
vec.push(false);
vec.push(true);
vec.push(false);
vec.push(false);
vec.push(true);
vec.push(false);
let mut iter = vec.iter();
assert_eq!(iter.len(), 12);
assert_eq!(iter.next(), Some(true));
assert_eq!(iter.next_back(), Some(false));
assert_eq!(iter.len(), 10);
assert_eq!(iter.next(), Some(false));
assert_eq!(iter.next_back(), Some(true));
assert_eq!(iter.next(), Some(false));
assert_eq!(iter.next_back(), Some(false));
assert_eq!(iter.next(), Some(false));
assert_eq!(iter.next_back(), Some(false));
assert_eq!(iter.next(), Some(true));
assert_eq!(iter.next_back(), Some(true));
assert_eq!(iter.next(), Some(true));
assert_eq!(iter.next_back(), Some(false));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next(), None);
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next_back(), None);
let mut iter = vec.iter_mut();
assert_eq!(iter.next().unwrap().get(), true);
assert_eq!(iter.next_back().unwrap().get(), false);
assert_eq!(iter.len(), 10);
assert_eq!(iter.next().unwrap().get(), false);
assert_eq!(iter.next_back().unwrap().get(), true);
assert_eq!(iter.next().unwrap().get(), false);
assert_eq!(iter.next_back().unwrap().get(), false);
assert_eq!(iter.next().unwrap().get(), false);
assert_eq!(iter.next_back().unwrap().get(),false);
assert_eq!(iter.next().unwrap().get(), true);
assert_eq!(iter.next_back().unwrap().get(), true);
assert_eq!(iter.next().unwrap().get(), true);
assert_eq!(iter.next_back().unwrap().get(), false);
assert_eq!(iter.len(), 0);
assert_eq!(iter.next(), None);
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn operations() {
let mut vec_a = BoolVec::new();
vec_a.push(true);
vec_a.push(true);
vec_a.push(true);
vec_a.push(true);
vec_a.push(false);
vec_a.push(false);
vec_a.push(false);
vec_a.push(false);
vec_a.push(true);
vec_a.push(false);
vec_a.push(false);
vec_a.push(true);
let mut vec_b = BoolVec::new();
vec_b.push(true);
vec_b.push(true);
vec_b.push(false);
vec_b.push(false);
vec_b.push(true);
vec_b.push(true);
vec_b.push(false);
vec_b.push(false);
vec_b.push(true);
vec_b.push(true);
vec_b.push(true);
vec_b.push(true);
let and = &vec_a & &vec_b;
let or = &vec_a | &vec_b;
let xor = &vec_a ^ &vec_b;
let and_i = and.iter();
let or_i = or.iter();
let xor_i = xor.iter();
let mut and_a = vec_a.clone();
let mut or_a = vec_a.clone();
let mut xor_a = vec_a.clone();
and_a &= &vec_b;
or_a |= &vec_b;
xor_a ^= &vec_b;
let and_a = and_a.iter();
let or_a = or_a.iter();
let xor_a = xor_a.iter();
for (and, or, xor)
in [ (and_i, or_i, xor_i), (and_a, or_a, xor_a) ].iter_mut () {
assert_eq!(and.next(), Some(true));
assert_eq!(and.next(), Some(true));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(true));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(false));
assert_eq!(and.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(false));
assert_eq!(or.next(), Some(false));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(or.next(), Some(true));
assert_eq!(xor.next(), Some(false));
assert_eq!(xor.next(), Some(false));
assert_eq!(xor.next(), Some(true));
assert_eq!(xor.next(), Some(true));
assert_eq!(xor.next(), Some(true));
assert_eq!(xor.next(), Some(true));
assert_eq!(xor.next(), Some(false));
assert_eq!(xor.next(), Some(false));
assert_eq!(xor.next(), Some(false));
assert_eq!(xor.next(), Some(true));
assert_eq!(xor.next(), Some(true));
assert_eq!(xor.next(), Some(false));
}
}
#[test]
fn count_ones() {
assert_eq!(super::count_ones(0b1111_0000), 4);
assert_eq!(super::count_ones(0b0001_0000), 1);
assert_eq!(super::count_ones(0b0001_1111), 5);
assert_eq!(super::count_ones(0b1010_1010), 4);
assert_eq!(BoolVec::new().count_ones(), 0);
assert_eq!(BoolVec::with_capacity(10).count_ones(), 0);
assert_eq!(BoolVec::filled_with(100, false).count_ones(), 0);
assert_eq!(BoolVec::filled_with(100, true).count_ones(), 100);
let mut vec = BoolVec::new();
vec.push(true);
vec.push(true);
vec.push(false);
vec.push(true);
vec.push(true);
vec.push(false);
vec.push(false);
vec.push(true);
vec.push(false);
vec.push(false);
vec.push(false);
vec.push(true);
vec.push(true);
vec.push(true);
vec.push(true);
vec.push(false);
assert_eq!(vec.count_ones(), 9);
let vec = [true, true, false].iter().cloned().cycle().take(60).collect::<BoolVec>();
assert_eq!(vec.count_ones(), 40);
}
#[test]
fn from_iter() {
let bits = [true, true, false].iter().cloned().cycle().take(100);
let vec = bits.collect::<BoolVec>();
assert_eq!(vec.count(), 100);
for i in 0..100 {
assert_eq!(vec.get(i).unwrap(), match i % 3 {
0 => true,
1 => true,
2 => false,
_ => unreachable!(),
});
}
let bytes = std::iter::repeat(0b1010_1010).take(10);
let vec = bytes.collect::<BoolVec>();
for i in 0..80 {
assert_eq!(vec.get(i).unwrap(), if i % 2 == 0 { true } else { false });
}
}
}