boolvec/
lib.rs

1//! This crate provides the `BoolVec` structure. This is basically a wrapper around a `Vec<u8>`
2//! where each byte is interpreted as 8 `bool`.
3//! 
4//! # Example
5//! ```rust
6//! // Create a new `BoolVec`
7//! use boolvec::BoolVec;
8//! 
9//! let mut vec = BoolVec::new();
10//! 
11//! // You can push data onto it
12//! vec.push(true);
13//! vec.push(false);
14//! 
15//! // ... retreve it
16//! assert_eq!(vec.get(0), Some(true));
17//! assert_eq!(vec.get(3), None);
18//! 
19//! // ... update it
20//! vec.set(0, false);
21//! assert_eq!(vec.get(0), Some(false));
22//! 
23//! // You can get a reference to an unaligned boolean
24//! let mut boolean = vec.get_mut(1).unwrap();
25//! assert_eq!(boolean.get(), false);
26//! 
27//! boolean.set(true);
28//! assert_eq!(vec.get(1), Some(true));
29//! 
30//! // You can also iterate over this data (mutably or not).
31//! let mut iter = vec.iter_mut();
32//! 
33//! iter.next().unwrap().set(true);
34//! iter.next().unwrap().set(false);
35//! 
36//! let mut iter = vec.iter();
37//! 
38//! assert_eq!(iter.next(), Some(true));
39//! assert_eq!(iter.next(), Some(false));
40//! assert_eq!(iter.next(), None);
41//! ```
42
43use std::ptr::NonNull;
44use std::marker::PhantomData;
45use std::cmp::Ord;
46use std::iter::Iterator;
47use std::iter::ExactSizeIterator;
48use std::iter::DoubleEndedIterator;
49use std::iter::FromIterator;
50use std::iter::FusedIterator;
51use std::ops::{
52    BitAnd, BitAndAssign,
53    BitOr, BitOrAssign,
54    BitXor, BitXorAssign,
55};
56
57mod bool_ref;
58use bool_ref::*;
59
60pub use bool_ref::RefBool;
61pub use bool_ref::RefBoolMut;
62
63mod mask;
64use mask::*;
65
66pub(crate) fn count_ones(mut value: u8) -> u8 {
67    let mut result = 0;
68    while value != 0 {
69        result += value & 1;
70        value >>= 1;
71    }
72    result
73}
74
75/// Deconstructs `nth` into a *index* and a *bit mask*
76const fn deconstruct_nth(nth: usize) -> (usize, Mask) {
77    (nth / 8, Mask::VALUES[nth % 8])
78}
79
80/// A vector of boolean values.
81#[derive(Clone)]
82pub struct BoolVec {
83    /// The data allocated for this `BoolVec`.
84    vec: Vec<u8>,
85
86    /// The bit mask that locates the last boolean that have been pushed
87    /// onto the `BoolVec`.
88    bit_mask: Mask,
89}
90
91impl BoolVec {
92    
93    /// Creates a new, empty `BoolVec`. The `BoolVec` will not allocate until elements
94    /// are pushed onto it.
95    #[inline(always)]
96    pub const fn new() -> Self {
97        Self {
98            vec: Vec::new(),
99            bit_mask: Mask::VALUES[7],
100        }
101    }
102    
103    /// Constructs a new, empty `BoolVec` with the specified capacity.
104    /// The `BoolVec` will be able to hold exactly `capacity * 8` booleans without
105    /// reallocating. If `capacity` is 0, the `BoolVec` will not allocate.
106    #[inline(always)]
107    pub fn with_capacity(capacity: usize) -> Self {
108        Self {
109            vec: Vec::with_capacity(capacity),
110            bit_mask: Mask::VALUES[7],
111        }
112    }
113
114    /// Creates a new `BoolVec` containing `count` booleans set to `value`.
115    pub fn filled_with(count: usize, value: bool) -> Self {
116        // The number of bytes we need to allocate.
117        let value = if value { 255 } else { 0 };
118        
119        let (bytes, bit_mask) = if count == 0 {
120            (Vec::new(), Mask::VALUES[7])
121        }
122        else {
123            // The bits that are not part of the vector should be set to 0.
124            let mut bytes = vec![value; count / 8];
125            bytes.push(
126                value << (7 - ((count - 1) % 8))
127            );
128            (bytes, Mask::VALUES[(count - 1) % 8])
129        };
130
131        Self {
132            vec: bytes,
133            bit_mask,
134        }
135    }
136
137    /// Creates a `BitVec` from a vector of bytes.
138    pub fn from_vec(vec: Vec<u8>) -> Self {
139        Self {
140            vec,
141            bit_mask: Mask::VALUES[7],
142        }
143    }
144
145    /// Returns the number of booleans that are stored inside of this `BoolVec`.
146    #[inline]
147    pub fn count(&self) -> usize {
148        if self.vec.len() == 0 {
149            0
150        }
151        else {
152            self.vec.len() * 8 - 7 + self.bit_mask.offset()
153        }
154    }
155
156    /// Is this `BoolVec` empty ?
157    #[inline]
158    pub fn is_empty(&self) -> bool {
159        self.count() == 0
160    }
161
162    /// Returns the capacity of this `BoolVec`, in bytes.
163    #[inline(always)]
164    pub fn capacity(&self) -> usize {
165        self.vec.capacity()
166    }
167
168    /// Identical to `Vec::reserve`.
169    /// 
170    /// `additional_capacity` is in bytes.
171    #[inline(always)]
172    pub fn reserve(&mut self, additional_capacity: usize) {
173        self.vec.reserve(additional_capacity);
174    }
175
176    /// Identical to `Vec::reserve_exact`.
177    /// 
178    /// `additional_capacity` is in bytes.
179    #[inline(always)]
180    pub fn reserve_exact(&mut self, additional_capacity: usize) {
181        self.vec.reserve_exact(additional_capacity);
182    }
183
184    /// Identical to `Vec::shrink_to_fit`.
185    #[inline(always)]
186    pub fn shrink_to_fit(&mut self) {
187        self.vec.shrink_to_fit();
188    }
189
190    /// Shortens the `BoolVec`, keeping the first `count` boolean values and
191    /// dropping the rest.
192    /// 
193    /// If `count` is greater or equal to `self.count()`, this will have
194    /// no effect.
195    pub fn truncate(&mut self, count: usize) {
196        if count >= self.count() {
197            return;
198        }
199        
200        let (kept_length, new_bit_mask) = if count == 0 {
201            (0, Mask::VALUES[7])
202        }
203        else {
204            (count / 8 + 1, Mask::VALUES[(count - 1) % 8])
205        };
206
207        self.vec.truncate(kept_length);
208        self.bit_mask = new_bit_mask;
209    }
210
211    /// Gets a reference to the `nth` boolean stored inside of this `BoolVec`.
212    /// 
213    /// # Safety
214    /// No bound checks are made.
215    #[inline]
216    pub unsafe fn get_unchecked_ref(&self, nth: usize) -> RefBool {
217        let (index, bit_mask) = deconstruct_nth(nth);
218        
219        RefBool::new(
220            self.vec.get_unchecked(index),
221            bit_mask
222        )
223    }
224
225    /// Gets the `nth` boolean stored inside of this `BoolVec`.
226    /// 
227    /// # Safety
228    /// The value of `nth` must be less than `self.count()`.
229    #[inline(always)]
230    pub unsafe fn get_unchecked(&self, nth: usize) -> bool {
231        self.get_unchecked_ref(nth).get()
232    }
233
234    /// Gets a reference to the `nth` boolean stored inside of this `BoolVec`
235    /// or `None` if `nth` is out of bounds.
236    #[inline]
237    pub fn get_ref(&self, nth: usize) -> Option<RefBool> {
238        if nth >= self.count() {
239            None
240        }
241        else { unsafe {
242            Some(self.get_unchecked_ref(nth))
243        } }
244    }
245
246    /// Gets the the `nth` boolean stored inside of this `BoolVec` or `None` if
247    /// `nth` is out of bounds.
248    #[inline]
249    pub fn get(&self, nth: usize) -> Option<bool> {
250        if nth >= self.count() {
251            None
252        }
253        else { unsafe {
254            Some(self.get_unchecked(nth))
255        } }
256    }
257
258    /// Gets a mutable reference to the `nth` boolean stored inside of
259    /// this `BoolVec`.
260    /// 
261    /// # Safety
262    /// The value of `nth` must be less than `self.count()`.
263    #[inline]
264    pub unsafe fn get_unchecked_mut(&mut self, nth: usize) -> RefBoolMut {
265        let (index, bit_mask) = deconstruct_nth(nth);
266
267        RefBoolMut::new(
268            self.vec.get_unchecked_mut(index),
269            bit_mask,
270        )
271    }
272
273    /// Gets a mutable reference to the `nth` boolean stored inside of
274    /// this `BoolVec` or `None` if `nth` is out of bounds.
275    #[inline]
276    pub fn get_mut(&mut self, nth: usize) -> Option<RefBoolMut> {
277        if nth >= self.count() {
278            None
279        }
280        else { unsafe {
281            Some(self.get_unchecked_mut(nth))
282        } }
283    }
284
285    /// Sets the value of the `nth` boolean stored inside of this `BoolVec`.
286    /// 
287    /// # Safety
288    /// The value of `nth` must be less than `self.count()`
289    #[inline(always)]
290    pub unsafe fn set_unchecked(&mut self, nth: usize, value: bool) {
291        self.get_unchecked_mut(nth).set(value);
292    }
293
294    /// Sets the value of the `nth` boolean stored inside of this `BoolVec`.
295    /// 
296    /// # Panics
297    /// This function panics if `nth` is greater or equal to `self.count()`.
298    #[inline]
299    pub fn set(&mut self, nth: usize, value: bool) {
300        if nth >= self.count() {
301            panic!("nth was {} but the count was {}.", nth, self.count());
302        }
303        else { unsafe { 
304            self.set_unchecked(nth, value)
305        } }
306    }
307
308    /// Pushes a new boolean value into this `BoolVec`.
309    /// 
310    /// # Panics
311    /// The function panics if the number of bytes allocated overflows `usize`.
312    pub fn push(&mut self, value: bool) {
313        self.bit_mask >>= 1;
314
315        if self.bit_mask == Mask::VALUES[0] {
316            self.vec.push(0)
317        }
318
319        unsafe {
320            // Safety: `self.count() - 1 < self.count()`
321            self.set_unchecked(self.count() - 1, value);
322        }
323    }
324
325    /// Removes the last boolean value from this `BoolVec` and returns it.
326    pub fn pop(&mut self) -> Option<bool> {
327        if self.count() == 0 {
328            None
329        }
330        else {
331            let result = unsafe { self.get_unchecked(self.count() - 1) };
332
333            self.bit_mask <<= 1;
334
335            if self.bit_mask == Mask::VALUES[7] {
336                self.vec.pop();
337            }
338
339            Some(result)
340        }
341    }
342
343    /// Gets a reference to the last boolean stored in this `BoolVec` or `None`
344    /// if the `BoolVec` is empty.
345    pub fn last_ref(&self) -> Option<RefBool> {
346        let count = self.count();
347        
348        if count == 0 {
349            None
350        }
351        else { unsafe {
352            Some(self.get_unchecked_ref(count - 1))
353        } }
354    }
355
356    /// Gets a mutable reference to the last boolean stored in this `BoolVec`
357    /// or `None` if the `BoolVec` is empty.
358    pub fn last_mut(&mut self) -> Option<RefBoolMut> {
359        let count = self.count();
360
361        if count == 0 {
362            None
363        }
364        else { unsafe { 
365            Some(self.get_unchecked_mut(count - 1))
366        } }
367    }
368
369    /// Gets the last boolean stored in this `BoolVec` or `None` if the vetor
370    /// is empty.
371    pub fn last(&self) -> Option<bool> {
372        let count = self.count();
373
374        if count == 0 {
375            None
376        }
377        else { unsafe {
378            Some(self.get_unchecked(count - 1))
379        }}
380    }
381
382    /// Clears this `BoolVec`.1
383    pub fn clear(&mut self) {
384        self.vec.clear();
385        self.bit_mask = Mask::VALUES[7];
386    }
387
388    /// Creates an unsafe iterator over the values of this `BoolVec`.
389    unsafe fn unsafe_iter(&self) -> UnsafeIter {
390        UnsafeIter {
391            start: UnsafeBoolRef::new(
392                // This cast if valid because this pointer will be used inside
393                // an `Iter` that will never write.
394                NonNull::new(self.vec.as_ptr() as *mut u8).unwrap(),
395                Mask::VALUES[0],
396            ),
397
398            end: UnsafeBoolRef::new(
399                // Safty : The data id valid between `self.vec.as_ptr` and
400                // `self.vec.as_ptr + self.vec.len` (not included).
401                NonNull::new(self.vec.as_ptr().add({
402                    if self.count() == 0 {
403                        0
404                    }
405                    else {
406                        self.vec.len() - 1
407                    }
408                }) as *mut u8).unwrap(),
409                self.bit_mask,
410            ).next_bit()
411        }
412    }
413
414    /// Creates a new iterator that iterates over the values of this `BoolVec`.
415    pub fn iter(&self) -> Iter {
416        Iter {
417            inner: unsafe { self.unsafe_iter() },
418            _marker: PhantomData,
419        }
420    }
421
422    /// Creates a new iterator that iterates over mutable references of the
423    /// values of this `BoolVec`.
424    pub fn iter_mut(&mut self) -> IterMut {
425        IterMut {
426            inner: unsafe { self.unsafe_iter() },
427            _marker: PhantomData,
428        }
429    }
430
431    /// Returns an iterator over the bytes of this `BoolVec`.
432    pub fn bytes(&self) -> impl Iterator<Item=&u8> {
433        self.vec.iter()
434    }
435
436    /// Returns an iterator over the bytes of this `BoolVec`.
437    pub fn bytes_mut(&mut self) -> impl Iterator<Item=&mut u8> {
438        self.vec.iter_mut()
439    }
440
441    /// Returns the number of bits that are set to `1` within this vector.
442    pub fn count_ones(&self) -> usize {
443        self.bytes()
444            .map(|&b| count_ones(b) as usize)
445            .sum::<usize>()
446    }
447}
448
449impl<'s> BitAnd<&'s BoolVec> for &'s BoolVec {
450    type Output = BoolVec;
451
452    fn bitand(self: &'s BoolVec, other: &'s BoolVec) -> BoolVec {
453        let mut result = BoolVec::with_capacity(
454            Ord::min(self.vec.len(), other.vec.len())
455        );
456
457        // Safety : We don't care if the bytes are not initialized.
458        for (&a, &b) in self.bytes().zip(other.bytes()) {
459            result.vec.push(a & b);
460        }
461
462        result.bit_mask = Ord::min(self.bit_mask, other.bit_mask);
463
464        result
465    }
466}
467
468impl<'s> BitAndAssign<&'s BoolVec> for BoolVec {
469    fn bitand_assign(&mut self, other: &'s BoolVec) {
470        for (byte, &o_byte) in self.bytes_mut().zip(other.bytes()) {
471            *byte &= o_byte;
472        }
473    }
474}
475
476impl<'s> BitOr<&'s BoolVec> for &'s BoolVec {
477    type Output = BoolVec;
478
479    fn bitor(self: &'s BoolVec, other: &'s BoolVec) -> BoolVec {
480        let mut result = BoolVec::with_capacity(
481            Ord::min(self.vec.len(), other.vec.len())
482        );
483
484        for (&a, &b) in self.bytes().zip(other.bytes()) {
485            result.vec.push(a | b);
486        }
487
488        result.bit_mask = Ord::max(self.bit_mask, other.bit_mask);
489
490        result
491    }
492}
493
494impl<'s> BitOrAssign<&'s BoolVec> for BoolVec {
495    fn bitor_assign(&mut self, other: &'s BoolVec) {
496        for (byte, &o_byte) in self.bytes_mut().zip(other.bytes()) {
497            *byte |= o_byte;
498        }
499    }
500}
501
502impl<'s> BitXor<&'s BoolVec> for &'s BoolVec {
503    type Output = BoolVec;
504
505    fn bitxor(self: &'s BoolVec, other: &'s BoolVec) -> BoolVec {
506        let mut result = BoolVec::with_capacity(
507            Ord::min(self.vec.len(), other.vec.len())
508        );
509
510        for (&a, &b) in self.bytes().zip(other.bytes()) {
511            result.vec.push(a ^ b);
512        }
513
514        result.bit_mask = Ord::max(self.bit_mask, other.bit_mask);
515
516        result
517    }
518}
519
520impl<'s> BitXorAssign<&'s BoolVec> for BoolVec {
521    fn bitxor_assign(&mut self, other: &'s BoolVec) {
522        for (byte, &o_byte) in self.bytes_mut().zip(other.bytes()) {
523            *byte ^= o_byte;
524        }
525    }
526}
527
528impl FromIterator<bool> for BoolVec {
529    fn from_iter<S: IntoIterator<Item=bool>>(iter: S) -> Self {
530        let iter = iter.into_iter();
531        let mut result = Self::with_capacity(iter.size_hint().0);
532
533        for bit in iter {
534            result.push(bit);
535        }
536
537        result
538    }
539}
540
541impl FromIterator<u8> for BoolVec {
542    fn from_iter<S: IntoIterator<Item=u8>>(iter: S) -> Self {
543        let iter = iter.into_iter();
544        let mut result = Vec::with_capacity(iter.size_hint().0);
545
546        for byte in iter {
547            result.push(byte)
548        }
549
550        Self::from_vec(result)
551    }
552}
553
554/// An unsafe interface for iterators.
555#[derive(Clone)]
556struct UnsafeIter {
557    start: UnsafeBoolRef,
558    end: UnsafeBoolRef,
559}
560
561impl Iterator for UnsafeIter {
562    type Item = UnsafeBoolRef;
563
564    fn next(&mut self) -> Option<UnsafeBoolRef> {
565        if self.start >= self.end {
566            None
567        }
568        else {
569            let temp = self.start.clone();
570            // Safety: The `UnsafeIter` must have been created with valid values.
571            unsafe { self.start = self.start.next_bit() }
572            Some(temp)
573        }
574    }
575
576    #[inline(always)]
577    fn size_hint(&self) -> (usize, Option<usize>) {
578        let len = self.len();
579        (len, Some(len))
580    }
581}
582
583impl ExactSizeIterator for UnsafeIter {
584    fn len(&self) -> usize {
585        let start = self.start.byte.as_ptr() as usize;
586        let end = self.end.byte.as_ptr() as usize;
587        let start_bit = self.start.bit_mask.offset();
588        let end_bit = self.end.bit_mask.offset();
589
590        (end - start) * 8 + (end_bit - start_bit)
591    }
592}
593
594impl DoubleEndedIterator for UnsafeIter {
595    fn next_back(&mut self) -> Option<UnsafeBoolRef> {
596        if self.start >= self.end {
597            None
598        }
599        else {
600            unsafe { self.end = self.end.prev_bit() }
601            Some(self.end.clone())
602        }
603    }
604}
605
606impl FusedIterator for UnsafeIter { }
607
608#[derive(Clone)]
609pub struct Iter<'s> {
610    inner: UnsafeIter,
611    _marker: PhantomData<&'s [u8]>,
612}
613
614impl<'s> Iterator for Iter<'s> {
615    type Item = bool;
616
617    #[inline]
618    fn next(&mut self) -> Option<bool> {
619        match self.inner.next() {
620            // Safety: The inner iterator has to be valid.
621            Some(val) => unsafe { Some(val.get()) },
622            None => None,
623        }
624    }
625
626    #[inline(always)]
627    fn size_hint(&self) -> (usize, Option<usize>) {
628        self.inner.size_hint()
629    }
630}
631
632impl<'s> ExactSizeIterator for Iter<'s> {
633    #[inline(always)]
634    fn len(&self) -> usize { self.inner.len() }
635}
636
637impl<'s> DoubleEndedIterator for Iter<'s> {
638    #[inline]
639    fn next_back(&mut self) -> Option<bool> {
640        match self.inner.next_back() {
641            // Safety: The inner iterator has to be valid.
642            Some(val) => unsafe { Some(val.get()) },
643            None => None,
644        }
645    }
646}
647
648impl<'s> FusedIterator for Iter<'s> { }
649
650#[derive(Clone)]
651pub struct IterMut<'s> {
652    inner: UnsafeIter,
653    _marker: PhantomData<&'s mut [u8]>,
654}
655
656impl<'s> Iterator for IterMut<'s> {
657    type Item = RefBoolMut<'s>;
658
659    #[inline]
660    fn next(&mut self) -> Option<RefBoolMut<'s>> {
661        match self.inner.next() {
662            // Safety: The inner iterator has to be valid.
663            Some(val) => Some(RefBoolMut::from_inner(val)),
664            None => None,
665        }
666    }
667
668    #[inline(always)]
669    fn size_hint(&self) -> (usize, Option<usize>) {
670        self.inner.size_hint()
671    }
672}
673
674impl<'s> ExactSizeIterator for IterMut<'s> {
675    #[inline(always)]
676    fn len(&self) -> usize { self.inner.len() }
677}
678
679impl<'s> DoubleEndedIterator for IterMut<'s> {
680    #[inline]
681    fn next_back(&mut self) -> Option<RefBoolMut<'s>> {
682        match self.inner.next_back() {
683            // Safety: The inner iterator has to be valid.
684            Some(val) => Some(RefBoolMut::from_inner(val)),
685            None => None,
686        }
687    }
688}
689
690impl<'s> FusedIterator for IterMut<'s> { }
691
692#[cfg(test)]
693mod vec_tests {
694    use super::*;
695
696    #[test]
697    fn create_vector() {
698        let vec = BoolVec::new();
699        assert_eq!(vec.capacity(), 0);
700        assert_eq!(vec.count(), 0);
701        assert!(vec.is_empty());
702        
703        let vec = BoolVec::with_capacity(0);
704        assert_eq!(vec.capacity(), 0);
705        assert_eq!(vec.count(), 0);
706        assert!(vec.is_empty());
707        
708        let vec = BoolVec::with_capacity(10);
709        assert_eq!(vec.capacity(), 10);
710        assert_eq!(vec.count(), 0);
711        assert!(vec.is_empty());
712        
713        let vec = BoolVec::filled_with(4, true);
714        assert_eq!(vec.capacity(), 1);
715        assert_eq!(vec.count(), 4);
716        assert_eq!(vec.vec.len(), 1);
717        assert_eq!(vec.vec[0], 0b1111_0000);
718        assert!(!vec.is_empty());
719        
720        let vec = BoolVec::filled_with(9, false);
721        assert_eq!(vec.capacity(), 2);
722        assert_eq!(vec.count(), 9);
723        assert_eq!(vec.vec.len(), 2);
724        assert!(!vec.is_empty());
725        assert_eq!(vec.vec[0], 0);
726        assert_eq!(vec.vec[1], 0);
727    }
728
729    #[test]
730    fn truncate() {
731        let mut vec = BoolVec::new();
732
733        vec.push(true);
734        vec.push(false);
735        vec.push(false);
736        vec.push(true);
737
738        assert_eq!(vec.count(), 4);
739        
740        vec.truncate(2);
741
742        assert_eq!(vec.count(), 2);
743
744        assert_eq!(vec.get(0), Some(true));
745        assert_eq!(vec.get(1), Some(false));
746        assert_eq!(vec.get(2), None);
747        assert_eq!(vec.get(3), None);
748    }
749
750    #[test]
751    fn pop() {
752        let mut vec = BoolVec::new();
753
754        vec.push(true);
755        vec.push(false);
756        vec.push(true);
757        vec.push(true);
758        vec.push(false);
759        vec.push(false);
760
761        assert_eq!(vec.pop(), Some(false));
762        assert_eq!(vec.pop(), Some(false));
763        assert_eq!(vec.pop(), Some(true));
764        assert_eq!(vec.pop(), Some(true));
765        assert_eq!(vec.pop(), Some(false));
766        assert_eq!(vec.pop(), Some(true));
767        assert_eq!(vec.pop(), None);
768        assert_eq!(vec.pop(), None);
769
770        assert_eq!(vec.last(), None);
771    }
772
773    #[test]
774    fn pushes() {
775        let mut vec = BoolVec::new();
776
777        assert_eq!(vec.vec.len(), 0);
778        assert_eq!(vec.count(), 0);
779
780        vec.push(false);
781        vec.push(true);
782        vec.push(true);
783        vec.push(false);
784
785        println!("{:#b}", vec.vec[0]);
786
787        assert_eq!(vec.count(), 4);
788        assert_eq!(vec.vec.len(), 1);
789
790        assert_eq!(vec.get(0), Some(false));
791        assert_eq!(vec.get(1), Some(true));
792        assert_eq!(vec.get(2), Some(true));
793        assert_eq!(vec.get(3), Some(false));
794        assert_eq!(vec.get(4), None);
795
796        assert_eq!(vec.last(), Some(false));
797
798        vec.set(0, true);
799        vec.set(1, false);
800        vec.set(2, false);
801        vec.set(3, true);
802
803        assert_eq!(vec.get(0), Some(true));
804        assert_eq!(vec.get(1), Some(false));
805        assert_eq!(vec.get(2), Some(false));
806        assert_eq!(vec.get(3), Some(true));
807        assert_eq!(vec.get(4), None);
808
809        assert_eq!(vec.last(), Some(true));
810    }
811
812
813    #[test]
814    fn iterators() {
815        let mut vec = BoolVec::new();
816
817        vec.push(true);
818        vec.push(false);
819        vec.push(false);
820        vec.push(false);
821        vec.push(true);
822        vec.push(true);
823        vec.push(false);
824        vec.push(true);
825        vec.push(false);
826        vec.push(false);
827        vec.push(true);
828        vec.push(false);
829
830        let mut iter = vec.iter();
831
832        assert_eq!(iter.len(), 12);
833
834        assert_eq!(iter.next(), Some(true));
835        assert_eq!(iter.next_back(), Some(false));
836        assert_eq!(iter.len(), 10);
837        assert_eq!(iter.next(), Some(false));
838        assert_eq!(iter.next_back(), Some(true));
839        assert_eq!(iter.next(), Some(false));
840        assert_eq!(iter.next_back(), Some(false));
841        assert_eq!(iter.next(), Some(false));
842        assert_eq!(iter.next_back(), Some(false));
843        assert_eq!(iter.next(), Some(true));
844        assert_eq!(iter.next_back(), Some(true));
845        assert_eq!(iter.next(), Some(true));
846        assert_eq!(iter.next_back(), Some(false));
847        assert_eq!(iter.len(), 0);
848        assert_eq!(iter.next(), None);
849        assert_eq!(iter.next(), None);
850        assert_eq!(iter.next_back(), None);
851        assert_eq!(iter.next_back(), None);
852
853        let mut iter = vec.iter_mut();
854
855        assert_eq!(iter.next().unwrap().get(), true);
856        assert_eq!(iter.next_back().unwrap().get(), false);
857        assert_eq!(iter.len(), 10);
858        assert_eq!(iter.next().unwrap().get(), false);
859        assert_eq!(iter.next_back().unwrap().get(), true);
860        assert_eq!(iter.next().unwrap().get(), false);
861        assert_eq!(iter.next_back().unwrap().get(), false);
862        assert_eq!(iter.next().unwrap().get(), false);
863        assert_eq!(iter.next_back().unwrap().get(),false);
864        assert_eq!(iter.next().unwrap().get(), true);
865        assert_eq!(iter.next_back().unwrap().get(), true);
866        assert_eq!(iter.next().unwrap().get(), true);
867        assert_eq!(iter.next_back().unwrap().get(), false);
868        assert_eq!(iter.len(), 0);
869        assert_eq!(iter.next(), None);
870        assert_eq!(iter.next(), None);
871        assert_eq!(iter.next_back(), None);
872        assert_eq!(iter.next_back(), None);
873    }
874
875    #[test]
876    fn operations() {
877        let mut vec_a = BoolVec::new();
878
879        vec_a.push(true);
880        vec_a.push(true);
881        vec_a.push(true);
882        vec_a.push(true);
883        vec_a.push(false);
884        vec_a.push(false);
885        vec_a.push(false);
886        vec_a.push(false);
887        vec_a.push(true);
888        vec_a.push(false);
889        vec_a.push(false);
890        vec_a.push(true);
891
892        let mut vec_b = BoolVec::new();
893
894        vec_b.push(true);
895        vec_b.push(true);
896        vec_b.push(false);
897        vec_b.push(false);
898        vec_b.push(true);
899        vec_b.push(true);
900        vec_b.push(false);
901        vec_b.push(false);
902        vec_b.push(true);
903        vec_b.push(true);
904        vec_b.push(true);
905        vec_b.push(true);
906
907        let and = &vec_a & &vec_b;
908        let or = &vec_a | &vec_b;
909        let xor = &vec_a ^ &vec_b;
910
911        let and_i = and.iter();
912        let or_i = or.iter();
913        let xor_i = xor.iter();
914
915        let mut and_a = vec_a.clone();
916        let mut or_a = vec_a.clone();
917        let mut xor_a = vec_a.clone();
918
919        and_a &= &vec_b;
920        or_a  |= &vec_b;
921        xor_a ^= &vec_b;
922
923        let and_a = and_a.iter();
924        let or_a = or_a.iter();
925        let xor_a = xor_a.iter();
926
927        for (and, or, xor)
928        in [ (and_i, or_i, xor_i), (and_a, or_a, xor_a) ].iter_mut () {
929            assert_eq!(and.next(), Some(true));
930            assert_eq!(and.next(), Some(true));
931            assert_eq!(and.next(), Some(false));
932            assert_eq!(and.next(), Some(false));
933            assert_eq!(and.next(), Some(false));
934            assert_eq!(and.next(), Some(false));
935            assert_eq!(and.next(), Some(false));
936            assert_eq!(and.next(), Some(false));
937            assert_eq!(and.next(), Some(true));
938            assert_eq!(and.next(), Some(false));
939            assert_eq!(and.next(), Some(false));
940            assert_eq!(and.next(), Some(true));
941    
942            assert_eq!(or.next(), Some(true));
943            assert_eq!(or.next(), Some(true));
944            assert_eq!(or.next(), Some(true));
945            assert_eq!(or.next(), Some(true));
946            assert_eq!(or.next(), Some(true));
947            assert_eq!(or.next(), Some(true));
948            assert_eq!(or.next(), Some(false));
949            assert_eq!(or.next(), Some(false));
950            assert_eq!(or.next(), Some(true));
951            assert_eq!(or.next(), Some(true));
952            assert_eq!(or.next(), Some(true));
953            assert_eq!(or.next(), Some(true));
954    
955            assert_eq!(xor.next(), Some(false));
956            assert_eq!(xor.next(), Some(false));
957            assert_eq!(xor.next(), Some(true));
958            assert_eq!(xor.next(), Some(true));
959            assert_eq!(xor.next(), Some(true));
960            assert_eq!(xor.next(), Some(true));
961            assert_eq!(xor.next(), Some(false));
962            assert_eq!(xor.next(), Some(false));
963            assert_eq!(xor.next(), Some(false));
964            assert_eq!(xor.next(), Some(true));
965            assert_eq!(xor.next(), Some(true));
966            assert_eq!(xor.next(), Some(false));
967        }
968    }
969
970    #[test]
971    fn count_ones() {
972        assert_eq!(super::count_ones(0b1111_0000), 4);
973        assert_eq!(super::count_ones(0b0001_0000), 1);
974        assert_eq!(super::count_ones(0b0001_1111), 5);
975        assert_eq!(super::count_ones(0b1010_1010), 4);
976
977        assert_eq!(BoolVec::new().count_ones(), 0);
978        assert_eq!(BoolVec::with_capacity(10).count_ones(), 0);
979        assert_eq!(BoolVec::filled_with(100, false).count_ones(), 0);
980        assert_eq!(BoolVec::filled_with(100, true).count_ones(), 100);
981
982        let mut vec = BoolVec::new();
983        vec.push(true);
984        vec.push(true);
985        vec.push(false);
986        vec.push(true);
987        vec.push(true);
988        vec.push(false);
989        vec.push(false);
990        vec.push(true);
991        vec.push(false);
992        vec.push(false);
993        vec.push(false);
994        vec.push(true);
995        vec.push(true);
996        vec.push(true);
997        vec.push(true);
998        vec.push(false);
999
1000        assert_eq!(vec.count_ones(), 9);
1001
1002        let vec = [true, true, false].iter().cloned().cycle().take(60).collect::<BoolVec>();
1003        assert_eq!(vec.count_ones(), 40);
1004    }
1005
1006    #[test]
1007    fn from_iter() {
1008        let bits = [true, true, false].iter().cloned().cycle().take(100);
1009
1010        let vec = bits.collect::<BoolVec>();
1011
1012        assert_eq!(vec.count(), 100);
1013
1014        for i in 0..100 {
1015            assert_eq!(vec.get(i).unwrap(), match i % 3 {
1016                0 => true,
1017                1 => true,
1018                2 => false,
1019                _ => unreachable!(),
1020            });
1021        }
1022
1023        let bytes = std::iter::repeat(0b1010_1010).take(10);
1024
1025        let vec = bytes.collect::<BoolVec>();
1026
1027        for i in 0..80 {
1028            assert_eq!(vec.get(i).unwrap(), if i % 2 == 0 { true } else { false });
1029        }
1030    }
1031}
boolvec/lib.rs

boolvec/
lib.rs
