commonware_utils/bitmap/
mod.rs

1//! Bitmap implementation
2//!
3//! The bitmap is a compact representation of a sequence of bits, using chunks of bytes for a
4//! more-efficient memory layout than doing [`Vec<bool>`].
5
6#[cfg(not(feature = "std"))]
7use alloc::{collections::VecDeque, vec::Vec};
8use bytes::{Buf, BufMut};
9use commonware_codec::{util::at_least, EncodeSize, Error as CodecError, Read, ReadExt, Write};
10use core::{
11    fmt::{self, Formatter, Write as _},
12    ops::{BitAnd, BitOr, BitXor, Index},
13};
14#[cfg(feature = "std")]
15use std::collections::VecDeque;
16
17mod prunable;
18pub use prunable::Prunable;
19
20pub mod historical;
21
22/// The default [BitMap] chunk size in bytes.
23pub const DEFAULT_CHUNK_SIZE: usize = 8;
24
25/// A bitmap that stores data in chunks of N bytes.
26///
27/// # Panics
28///
29/// Operations panic if `bit / CHUNK_SIZE_BITS > usize::MAX`. On 32-bit systems
30/// with N=32, this occurs at bit >= 1,099,511,627,776.
31#[derive(Clone, PartialEq, Eq, Hash)]
32pub struct BitMap<const N: usize = DEFAULT_CHUNK_SIZE> {
33    /// The bitmap itself, in chunks of size N bytes. Within each byte, lowest order bits are
34    /// treated as coming before higher order bits in the bit ordering.
35    ///
36    /// Invariant: `chunks.len() == len.div_ceil(CHUNK_SIZE_BITS)`
37    /// Invariant: All bits at index `i` where `i >= len` must be 0.
38    chunks: VecDeque<[u8; N]>,
39
40    /// The total number of bits stored in the bitmap.
41    len: u64,
42}
43
44impl<const N: usize> BitMap<N> {
45    const _CHUNK_SIZE_NON_ZERO_ASSERT: () = assert!(N > 0, "chunk size must be > 0");
46
47    /// The size of a chunk in bits.
48    pub const CHUNK_SIZE_BITS: u64 = (N * 8) as u64;
49
50    /// A chunk of all 0s.
51    const EMPTY_CHUNK: [u8; N] = [0u8; N];
52
53    /// A chunk of all 1s.
54    const FULL_CHUNK: [u8; N] = [u8::MAX; N];
55
56    /* Constructors */
57
58    /// Create a new empty bitmap.
59    pub fn new() -> Self {
60        #[allow(path_statements)]
61        Self::_CHUNK_SIZE_NON_ZERO_ASSERT; // Prevent compilation for N == 0
62
63        Self {
64            chunks: VecDeque::new(),
65            len: 0,
66        }
67    }
68
69    // Create a new empty bitmap with the capacity to hold `size` bits without reallocating.
70    pub fn with_capacity(size: u64) -> Self {
71        #[allow(path_statements)]
72        Self::_CHUNK_SIZE_NON_ZERO_ASSERT; // Prevent compilation for N == 0
73
74        Self {
75            chunks: VecDeque::with_capacity(size.div_ceil(Self::CHUNK_SIZE_BITS) as usize),
76            len: 0,
77        }
78    }
79
80    /// Create a new bitmap with `size` bits, with all bits set to 0.
81    pub fn zeroes(size: u64) -> Self {
82        #[allow(path_statements)]
83        Self::_CHUNK_SIZE_NON_ZERO_ASSERT; // Prevent compilation for N == 0
84
85        let num_chunks = size.div_ceil(Self::CHUNK_SIZE_BITS) as usize;
86        let mut chunks = VecDeque::with_capacity(num_chunks);
87        for _ in 0..num_chunks {
88            chunks.push_back(Self::EMPTY_CHUNK);
89        }
90        Self { chunks, len: size }
91    }
92
93    /// Create a new bitmap with `size` bits, with all bits set to 1.
94    pub fn ones(size: u64) -> Self {
95        #[allow(path_statements)]
96        Self::_CHUNK_SIZE_NON_ZERO_ASSERT; // Prevent compilation for N == 0
97
98        let num_chunks = size.div_ceil(Self::CHUNK_SIZE_BITS) as usize;
99        let mut chunks = VecDeque::with_capacity(num_chunks);
100        for _ in 0..num_chunks {
101            chunks.push_back(Self::FULL_CHUNK);
102        }
103        let mut result = Self { chunks, len: size };
104        // Clear trailing bits to maintain invariant
105        result.clear_trailing_bits();
106        result
107    }
108
109    /* Length */
110
111    /// Return the number of bits currently stored in the bitmap.
112    #[inline]
113    pub fn len(&self) -> u64 {
114        self.len
115    }
116
117    /// Returns true if the bitmap is empty.
118    #[inline]
119    pub fn is_empty(&self) -> bool {
120        self.len() == 0
121    }
122
123    /// Returns true if the bitmap length is aligned to a chunk boundary.
124    #[inline]
125    pub fn is_chunk_aligned(&self) -> bool {
126        self.len.is_multiple_of(Self::CHUNK_SIZE_BITS)
127    }
128
129    // Get the number of chunks currently in the bitmap.
130    fn chunks_len(&self) -> usize {
131        self.chunks.len()
132    }
133
134    /* Getters */
135
136    /// Get the value of the bit at the given index.
137    ///
138    /// # Warning
139    ///
140    /// Panics if the bit doesn't exist.
141    #[inline]
142    pub fn get(&self, bit: u64) -> bool {
143        let chunk = self.get_chunk_containing(bit);
144        Self::get_from_chunk(chunk, bit)
145    }
146
147    /// Returns the bitmap chunk containing the given bit.
148    ///
149    /// # Warning
150    ///
151    /// Panics if the bit doesn't exist.
152    #[inline]
153    fn get_chunk_containing(&self, bit: u64) -> &[u8; N] {
154        assert!(
155            bit < self.len(),
156            "bit {} out of bounds (len: {})",
157            bit,
158            self.len()
159        );
160        &self.chunks[Self::chunk(bit)]
161    }
162
163    /// Get a reference to a chunk by its index in the current bitmap.
164    /// Note this is an index into the chunks, not a bit.
165    #[inline]
166    pub(super) fn get_chunk(&self, chunk: usize) -> &[u8; N] {
167        assert!(
168            chunk < self.chunks.len(),
169            "chunk {} out of bounds (chunks: {})",
170            chunk,
171            self.chunks.len()
172        );
173        &self.chunks[chunk]
174    }
175
176    /// Get the value at the given `bit` from the `chunk`.
177    /// `bit` is an index into the entire bitmap, not just the chunk.
178    #[inline]
179    fn get_from_chunk(chunk: &[u8; N], bit: u64) -> bool {
180        let byte = Self::chunk_byte_offset(bit);
181        let byte = chunk[byte];
182        let mask = Self::chunk_byte_bitmask(bit);
183        (byte & mask) != 0
184    }
185
186    /// Return the last chunk of the bitmap and its size in bits.
187    ///
188    /// # Panics
189    ///
190    /// Panics if bitmap is empty.
191    #[inline]
192    fn last_chunk(&self) -> (&[u8; N], u64) {
193        let rem = self.len % Self::CHUNK_SIZE_BITS;
194        let bits_in_last_chunk = if rem == 0 { Self::CHUNK_SIZE_BITS } else { rem };
195        (self.chunks.back().unwrap(), bits_in_last_chunk)
196    }
197
198    /* Setters */
199
200    /// Add a single bit to the bitmap.
201    pub fn push(&mut self, bit: bool) {
202        // Check if we need a new chunk
203        if self.is_chunk_aligned() {
204            self.chunks.push_back(Self::EMPTY_CHUNK);
205        }
206
207        // Append to the last chunk
208        if bit {
209            let last_chunk = self.chunks.back_mut().unwrap();
210            let chunk_byte = Self::chunk_byte_offset(self.len);
211            last_chunk[chunk_byte] |= Self::chunk_byte_bitmask(self.len);
212        }
213        // If bit is false, just advance len -- the bit is already 0
214        self.len += 1;
215    }
216
217    /// Remove and return the last bit from the bitmap.
218    ///
219    /// # Warning
220    ///
221    /// Panics if the bitmap is empty.
222    pub fn pop(&mut self) -> bool {
223        assert!(!self.is_empty(), "Cannot pop from empty bitmap");
224
225        // Get the bit value at the last position
226        let last_bit_pos = self.len - 1;
227        let bit = Self::get_from_chunk(self.chunks.back().unwrap(), last_bit_pos);
228
229        // Decrement length
230        self.len -= 1;
231
232        // Clear the bit we just popped to maintain invariant (if it was 1)
233        if bit {
234            let pos_in_chunk = last_bit_pos % Self::CHUNK_SIZE_BITS;
235            let chunk_byte = (pos_in_chunk / 8) as usize;
236            let mask = Self::chunk_byte_bitmask(last_bit_pos);
237            self.chunks.back_mut().unwrap()[chunk_byte] &= !mask;
238        }
239
240        // Remove the last chunk if it's now empty
241        if self.is_chunk_aligned() {
242            self.chunks.pop_back();
243        }
244
245        bit
246    }
247
248    /// Remove and return the last complete chunk from the bitmap.
249    ///
250    /// # Warning
251    ///
252    /// Panics if the bitmap has fewer than `CHUNK_SIZE_BITS` bits or if not chunk-aligned.
253    pub(super) fn pop_chunk(&mut self) -> [u8; N] {
254        assert!(
255            self.len() >= Self::CHUNK_SIZE_BITS,
256            "cannot pop chunk: bitmap has fewer than CHUNK_SIZE_BITS bits"
257        );
258        assert!(
259            self.is_chunk_aligned(),
260            "cannot pop chunk when not chunk aligned"
261        );
262
263        // Remove and return the last data chunk
264        let chunk = self.chunks.pop_back().expect("chunk must exist");
265        self.len -= Self::CHUNK_SIZE_BITS;
266        chunk
267    }
268
269    /// Flips the given bit.
270    ///
271    /// # Panics
272    ///
273    /// Panics if `bit` is out of bounds.
274    #[inline]
275    pub fn flip(&mut self, bit: u64) {
276        self.assert_bit(bit);
277        let chunk = Self::chunk(bit);
278        let byte = Self::chunk_byte_offset(bit);
279        let mask = Self::chunk_byte_bitmask(bit);
280        self.chunks[chunk][byte] ^= mask;
281    }
282
283    /// Flips all bits (1s become 0s and vice versa).
284    pub fn flip_all(&mut self) {
285        for chunk in &mut self.chunks {
286            for byte in chunk {
287                *byte = !*byte;
288            }
289        }
290        // Clear trailing bits to maintain invariant
291        self.clear_trailing_bits();
292    }
293
294    /// Set the value of the referenced bit.
295    ///
296    /// # Warning
297    ///
298    /// Panics if the bit doesn't exist.
299    pub fn set(&mut self, bit: u64, value: bool) {
300        assert!(
301            bit < self.len(),
302            "bit {} out of bounds (len: {})",
303            bit,
304            self.len()
305        );
306
307        let chunk = &mut self.chunks[Self::chunk(bit)];
308        let byte = Self::chunk_byte_offset(bit);
309        let mask = Self::chunk_byte_bitmask(bit);
310        if value {
311            chunk[byte] |= mask;
312        } else {
313            chunk[byte] &= !mask;
314        }
315    }
316
317    /// Sets all bits to the specified value.
318    #[inline]
319    pub fn set_all(&mut self, bit: bool) {
320        let value = if bit { u8::MAX } else { 0 };
321        for chunk in &mut self.chunks {
322            chunk.fill(value);
323        }
324        // Clear trailing bits to maintain invariant
325        if bit {
326            self.clear_trailing_bits();
327        }
328    }
329
330    // Add a byte's worth of bits to the bitmap.
331    //
332    // # Warning
333    //
334    // Panics if self.len is not byte aligned.
335    fn push_byte(&mut self, byte: u8) {
336        assert!(
337            self.len.is_multiple_of(8),
338            "cannot add byte when not byte aligned"
339        );
340
341        // Check if we need a new chunk
342        if self.is_chunk_aligned() {
343            self.chunks.push_back(Self::EMPTY_CHUNK);
344        }
345
346        let chunk_byte = Self::chunk_byte_offset(self.len);
347        self.chunks.back_mut().unwrap()[chunk_byte] = byte;
348        self.len += 8;
349    }
350
351    /// Add a chunk of bits to the bitmap.
352    ///
353    /// # Warning
354    ///
355    /// Panics if self.len is not chunk aligned.
356    pub fn push_chunk(&mut self, chunk: &[u8; N]) {
357        assert!(
358            self.is_chunk_aligned(),
359            "cannot add chunk when not chunk aligned"
360        );
361        self.chunks.push_back(*chunk);
362        self.len += Self::CHUNK_SIZE_BITS;
363    }
364
365    /* Invariant Maintenance */
366
367    /// Clear all bits in the last chunk that are >= self.len to maintain the invariant.
368    /// Returns true if any bits were flipped from 1 to 0.
369    fn clear_trailing_bits(&mut self) -> bool {
370        if self.chunks.is_empty() {
371            return false;
372        }
373
374        let pos_in_chunk = self.len % Self::CHUNK_SIZE_BITS;
375        if pos_in_chunk == 0 {
376            // Chunk is full -- there are no trailing bits to clear.
377            return false;
378        }
379
380        let mut flipped_any = false;
381        let last_chunk = self.chunks.back_mut().unwrap();
382
383        // Clear whole bytes after the last valid bit
384        let last_byte_index = ((pos_in_chunk - 1) / 8) as usize;
385        for byte in last_chunk.iter_mut().skip(last_byte_index + 1) {
386            if *byte != 0 {
387                flipped_any = true;
388                *byte = 0;
389            }
390        }
391
392        // Clear the trailing bits in the last partial byte
393        let bits_in_last_byte = pos_in_chunk % 8;
394        if bits_in_last_byte != 0 {
395            let mask = (1u8 << bits_in_last_byte) - 1;
396            let old_byte = last_chunk[last_byte_index];
397            let new_byte = old_byte & mask;
398            if old_byte != new_byte {
399                flipped_any = true;
400                last_chunk[last_byte_index] = new_byte;
401            }
402        }
403
404        flipped_any
405    }
406
407    /* Pruning */
408
409    /// Remove the first `chunks` chunks from the bitmap.
410    ///
411    /// # Warning
412    ///
413    /// Panics if trying to prune more chunks than exist.
414    fn prune_chunks(&mut self, chunks: usize) {
415        assert!(
416            chunks <= self.chunks.len(),
417            "cannot prune {chunks} chunks, only {} available",
418            self.chunks.len()
419        );
420        self.chunks.drain(..chunks);
421        // Update len to reflect the removed chunks
422        let bits_removed = (chunks as u64) * Self::CHUNK_SIZE_BITS;
423        self.len = self.len.saturating_sub(bits_removed);
424    }
425
426    /// Prepend a chunk to the beginning of the bitmap.
427    pub(super) fn prepend_chunk(&mut self, chunk: &[u8; N]) {
428        self.chunks.push_front(*chunk);
429        self.len += Self::CHUNK_SIZE_BITS;
430    }
431
432    /// Overwrite a chunk's data at the given index.
433    ///
434    /// Replaces the entire chunk data, including any bits beyond `len()` in the last chunk.
435    /// The caller is responsible for ensuring `chunk_data` has the correct bit pattern
436    /// (e.g., zeros beyond the valid length if this is a partial last chunk).
437    ///
438    /// # Panics
439    ///
440    /// Panics if chunk_index is out of bounds.
441    pub(super) fn set_chunk_by_index(&mut self, chunk_index: usize, chunk_data: &[u8; N]) {
442        assert!(
443            chunk_index < self.chunks.len(),
444            "chunk index {chunk_index} out of bounds (chunks_len: {})",
445            self.chunks.len()
446        );
447        self.chunks[chunk_index].copy_from_slice(chunk_data);
448    }
449
450    /* Counting */
451
452    /// Returns the number of bits set to 1.
453    #[inline]
454    pub fn count_ones(&self) -> u64 {
455        // Thanks to the invariant that trailing bits are always 0,
456        // we can simply count all set bits in all chunks
457        self.chunks
458            .iter()
459            .flat_map(|chunk| chunk.iter())
460            .map(|byte| byte.count_ones() as u64)
461            .sum()
462    }
463
464    /// Returns the number of bits set to 0.
465    #[inline]
466    pub fn count_zeros(&self) -> u64 {
467        self.len() - self.count_ones()
468    }
469
470    /* Indexing Helpers */
471
472    /// Convert a bit offset into a bitmask for the byte containing that bit.
473    #[inline]
474    pub(super) fn chunk_byte_bitmask(bit: u64) -> u8 {
475        1 << (bit % 8)
476    }
477
478    /// Convert a bit into the index of the byte within a chunk containing the bit.
479    #[inline]
480    pub(super) fn chunk_byte_offset(bit: u64) -> usize {
481        ((bit / 8) % N as u64) as usize
482    }
483
484    /// Convert a bit into the index of the chunk it belongs to.
485    ///
486    /// # Panics
487    ///
488    /// Panics if the chunk index overflows `usize`.
489    #[inline]
490    pub(super) fn chunk(bit: u64) -> usize {
491        let chunk = bit / Self::CHUNK_SIZE_BITS;
492        assert!(
493            chunk <= usize::MAX as u64,
494            "chunk overflow: {chunk} exceeds usize::MAX",
495        );
496        chunk as usize
497    }
498
499    /* Iterator */
500
501    /// Creates an iterator over the bits.
502    pub fn iter(&self) -> Iterator<'_, N> {
503        Iterator {
504            bitmap: self,
505            pos: 0,
506        }
507    }
508
509    /* Bitwise Operations */
510
511    /// Helper for binary operations
512    #[inline]
513    fn binary_op<F: Fn(u8, u8) -> u8>(&mut self, other: &BitMap<N>, op: F) {
514        self.assert_eq_len(other);
515        for (a_chunk, b_chunk) in self.chunks.iter_mut().zip(other.chunks.iter()) {
516            for (a_byte, b_byte) in a_chunk.iter_mut().zip(b_chunk.iter()) {
517                *a_byte = op(*a_byte, *b_byte);
518            }
519        }
520        // Clear trailing bits to maintain invariant
521        self.clear_trailing_bits();
522    }
523
524    /// Performs a bitwise AND with another BitMap.
525    ///
526    /// # Panics
527    ///
528    /// Panics if the lengths don't match.
529    pub fn and(&mut self, other: &BitMap<N>) {
530        self.binary_op(other, |a, b| a & b);
531    }
532
533    /// Performs a bitwise OR with another BitMap.
534    ///
535    /// # Panics
536    ///
537    /// Panics if the lengths don't match.
538    pub fn or(&mut self, other: &BitMap<N>) {
539        self.binary_op(other, |a, b| a | b);
540    }
541
542    /// Performs a bitwise XOR with another BitMap.
543    ///
544    /// # Panics
545    ///
546    /// Panics if the lengths don't match.
547    pub fn xor(&mut self, other: &BitMap<N>) {
548        self.binary_op(other, |a, b| a ^ b);
549    }
550
551    /* Assertions */
552
553    /// Asserts that the bit is within bounds.
554    #[inline(always)]
555    fn assert_bit(&self, bit: u64) {
556        assert!(
557            bit < self.len(),
558            "bit {} out of bounds (len: {})",
559            bit,
560            self.len()
561        );
562    }
563
564    /// Asserts that the lengths of two [BitMap]s match.
565    #[inline(always)]
566    fn assert_eq_len(&self, other: &BitMap<N>) {
567        assert_eq!(
568            self.len(),
569            other.len(),
570            "BitMap lengths don't match: {} vs {}",
571            self.len(),
572            other.len()
573        );
574    }
575}
576
577impl<const N: usize> Default for BitMap<N> {
578    fn default() -> Self {
579        Self::new()
580    }
581}
582
583impl<T: AsRef<[bool]>, const N: usize> From<T> for BitMap<N> {
584    fn from(t: T) -> Self {
585        let bools = t.as_ref();
586        let mut bv = Self::new();
587        for &b in bools {
588            bv.push(b);
589        }
590        bv
591    }
592}
593
594impl<const N: usize> From<BitMap<N>> for Vec<bool> {
595    fn from(bv: BitMap<N>) -> Self {
596        bv.iter().collect()
597    }
598}
599
600impl<const N: usize> fmt::Debug for BitMap<N> {
601    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
602        // For very large BitMaps, only show a preview
603        const MAX_DISPLAY: u64 = 64;
604        const HALF_DISPLAY: u64 = MAX_DISPLAY / 2;
605
606        // Closure for writing a bit
607        let write_bit = |formatter: &mut Formatter<'_>, bit: u64| -> core::fmt::Result {
608            formatter.write_char(if self.get(bit) { '1' } else { '0' })
609        };
610
611        f.write_str("BitMap[")?;
612        let len = self.len();
613        if len <= MAX_DISPLAY {
614            // Show all bits
615            for i in 0..len {
616                write_bit(f, i)?;
617            }
618        } else {
619            // Show first and last bits with ellipsis
620            for i in 0..HALF_DISPLAY {
621                write_bit(f, i)?;
622            }
623
624            f.write_str("...")?;
625
626            for i in (len - HALF_DISPLAY)..len {
627                write_bit(f, i)?;
628            }
629        }
630        f.write_str("]")
631    }
632}
633
634impl<const N: usize> Index<u64> for BitMap<N> {
635    type Output = bool;
636
637    /// Allows accessing bits using the `[]` operator.
638    ///
639    /// Panics if out of bounds.
640    #[inline]
641    fn index(&self, bit: u64) -> &Self::Output {
642        self.assert_bit(bit);
643        let value = self.get(bit);
644        if value {
645            &true
646        } else {
647            &false
648        }
649    }
650}
651
652impl<const N: usize> BitAnd for &BitMap<N> {
653    type Output = BitMap<N>;
654
655    fn bitand(self, rhs: Self) -> Self::Output {
656        self.assert_eq_len(rhs);
657        let mut result = self.clone();
658        result.and(rhs);
659        result
660    }
661}
662
663impl<const N: usize> BitOr for &BitMap<N> {
664    type Output = BitMap<N>;
665
666    fn bitor(self, rhs: Self) -> Self::Output {
667        self.assert_eq_len(rhs);
668        let mut result = self.clone();
669        result.or(rhs);
670        result
671    }
672}
673
674impl<const N: usize> BitXor for &BitMap<N> {
675    type Output = BitMap<N>;
676
677    fn bitxor(self, rhs: Self) -> Self::Output {
678        self.assert_eq_len(rhs);
679        let mut result = self.clone();
680        result.xor(rhs);
681        result
682    }
683}
684
685impl<const N: usize> Write for BitMap<N> {
686    fn write(&self, buf: &mut impl BufMut) {
687        // Prefix with the number of bits
688        self.len().write(buf);
689
690        // Write all chunks
691        for chunk in &self.chunks {
692            for &byte in chunk {
693                byte.write(buf);
694            }
695        }
696    }
697}
698
699impl<const N: usize> Read for BitMap<N> {
700    type Cfg = u64; // Max bitmap length
701
702    fn read_cfg(buf: &mut impl Buf, max_len: &Self::Cfg) -> Result<Self, CodecError> {
703        // Parse length in bits
704        let len = u64::read(buf)?;
705        if len > *max_len {
706            return Err(CodecError::InvalidLength(len as usize));
707        }
708
709        // Calculate how many chunks we need to read
710        let num_chunks = len.div_ceil(Self::CHUNK_SIZE_BITS) as usize;
711
712        // Parse chunks
713        let mut chunks = VecDeque::with_capacity(num_chunks);
714        for _ in 0..num_chunks {
715            at_least(buf, N)?;
716            let mut chunk = [0u8; N];
717            buf.copy_to_slice(&mut chunk);
718            chunks.push_back(chunk);
719        }
720
721        let mut result = BitMap { chunks, len };
722
723        // Verify trailing bits are zero (maintain invariant)
724        if result.clear_trailing_bits() {
725            return Err(CodecError::Invalid(
726                "BitMap",
727                "Invalid trailing bits in encoded data",
728            ));
729        }
730
731        Ok(result)
732    }
733}
734
735impl<const N: usize> EncodeSize for BitMap<N> {
736    fn encode_size(&self) -> usize {
737        // Size of length prefix + all chunks
738        self.len().encode_size() + (self.chunks.len() * N)
739    }
740}
741
742/// Iterator over bits in a [BitMap].
743pub struct Iterator<'a, const N: usize> {
744    /// Reference to the BitMap being iterated over
745    bitmap: &'a BitMap<N>,
746
747    /// Current index in the BitMap
748    pos: u64,
749}
750
751impl<const N: usize> core::iter::Iterator for Iterator<'_, N> {
752    type Item = bool;
753
754    fn next(&mut self) -> Option<Self::Item> {
755        if self.pos >= self.bitmap.len() {
756            return None;
757        }
758
759        let bit = self.bitmap.get(self.pos);
760        self.pos += 1;
761        Some(bit)
762    }
763
764    fn size_hint(&self) -> (usize, Option<usize>) {
765        let remaining = self.bitmap.len().saturating_sub(self.pos);
766        let capped = remaining.min(usize::MAX as u64) as usize;
767        (capped, Some(capped))
768    }
769}
770
771impl<const N: usize> ExactSizeIterator for Iterator<'_, N> {}
772
773#[cfg(test)]
774mod tests {
775    use super::*;
776    use crate::hex;
777    use bytes::BytesMut;
778    use commonware_codec::{Decode, Encode};
779
780    #[test]
781    fn test_constructors() {
782        // Test new()
783        let bv: BitMap<4> = BitMap::new();
784        assert_eq!(bv.len(), 0);
785        assert!(bv.is_empty());
786
787        // Test default()
788        let bv: BitMap<4> = Default::default();
789        assert_eq!(bv.len(), 0);
790        assert!(bv.is_empty());
791
792        // Test with_capacity()
793        let bv: BitMap<4> = BitMap::with_capacity(0);
794        assert_eq!(bv.len(), 0);
795        assert!(bv.is_empty());
796
797        let bv: BitMap<4> = BitMap::with_capacity(10);
798        assert_eq!(bv.len(), 0);
799        assert!(bv.is_empty());
800    }
801
802    #[test]
803    fn test_zeroes() {
804        let bv: BitMap<1> = BitMap::zeroes(0);
805        assert_eq!(bv.len(), 0);
806        assert!(bv.is_empty());
807        assert_eq!(bv.count_ones(), 0);
808        assert_eq!(bv.count_zeros(), 0);
809
810        let bv: BitMap<1> = BitMap::zeroes(1);
811        assert_eq!(bv.len(), 1);
812        assert!(!bv.is_empty());
813        assert_eq!(bv.len(), 1);
814        assert!(!bv.get(0));
815        assert_eq!(bv.count_ones(), 0);
816        assert_eq!(bv.count_zeros(), 1);
817
818        let bv: BitMap<1> = BitMap::zeroes(10);
819        assert_eq!(bv.len(), 10);
820        assert!(!bv.is_empty());
821        assert_eq!(bv.len(), 10);
822        for i in 0..10 {
823            assert!(!bv.get(i as u64));
824        }
825        assert_eq!(bv.count_ones(), 0);
826        assert_eq!(bv.count_zeros(), 10);
827    }
828
829    #[test]
830    fn test_ones() {
831        let bv: BitMap<1> = BitMap::ones(0);
832        assert_eq!(bv.len(), 0);
833        assert!(bv.is_empty());
834        assert_eq!(bv.count_ones(), 0);
835        assert_eq!(bv.count_zeros(), 0);
836
837        let bv: BitMap<1> = BitMap::ones(1);
838        assert_eq!(bv.len(), 1);
839        assert!(!bv.is_empty());
840        assert_eq!(bv.len(), 1);
841        assert!(bv.get(0));
842        assert_eq!(bv.count_ones(), 1);
843        assert_eq!(bv.count_zeros(), 0);
844
845        let bv: BitMap<1> = BitMap::ones(10);
846        assert_eq!(bv.len(), 10);
847        assert!(!bv.is_empty());
848        assert_eq!(bv.len(), 10);
849        for i in 0..10 {
850            assert!(bv.get(i as u64));
851        }
852        assert_eq!(bv.count_ones(), 10);
853        assert_eq!(bv.count_zeros(), 0);
854    }
855
856    #[test]
857    fn test_invariant_trailing_bits_are_zero() {
858        // Helper function to check the invariant
859        fn check_trailing_bits_zero<const N: usize>(bitmap: &BitMap<N>) {
860            let (last_chunk, next_bit) = bitmap.last_chunk();
861
862            // Check that all bits >= next_bit in the last chunk are 0
863            for bit_idx in next_bit..((N * 8) as u64) {
864                let byte_idx = (bit_idx / 8) as usize;
865                let bit_in_byte = bit_idx % 8;
866                let mask = 1u8 << bit_in_byte;
867                assert_eq!(last_chunk[byte_idx] & mask, 0);
868            }
869        }
870
871        // Test ones() constructor
872        let bv: BitMap<4> = BitMap::ones(15);
873        check_trailing_bits_zero(&bv);
874
875        let bv: BitMap<4> = BitMap::ones(33);
876        check_trailing_bits_zero(&bv);
877
878        // Test after push operations
879        let mut bv: BitMap<4> = BitMap::new();
880        for i in 0..37 {
881            bv.push(i % 2 == 0);
882            check_trailing_bits_zero(&bv);
883        }
884
885        // Test after pop operations
886        let mut bv: BitMap<4> = BitMap::ones(40);
887        check_trailing_bits_zero(&bv);
888        for _ in 0..15 {
889            bv.pop();
890            check_trailing_bits_zero(&bv);
891        }
892
893        // Test after flip_all
894        let mut bv: BitMap<4> = BitMap::ones(25);
895        bv.flip_all();
896        check_trailing_bits_zero(&bv);
897
898        // Test after binary operations
899        let bv1: BitMap<4> = BitMap::ones(20);
900        let bv2: BitMap<4> = BitMap::zeroes(20);
901
902        let mut bv_and = bv1.clone();
903        bv_and.and(&bv2);
904        check_trailing_bits_zero(&bv_and);
905
906        let mut bv_or = bv1.clone();
907        bv_or.or(&bv2);
908        check_trailing_bits_zero(&bv_or);
909
910        let mut bv_xor = bv1.clone();
911        bv_xor.xor(&bv2);
912        check_trailing_bits_zero(&bv_xor);
913
914        // Test after deserialization
915        let original: BitMap<4> = BitMap::ones(27);
916        let encoded = original.encode();
917        let decoded: BitMap<4> =
918            BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
919        check_trailing_bits_zero(&decoded);
920
921        // Test clear_trailing_bits return value
922        let mut bv_clean: BitMap<4> = BitMap::ones(20);
923        // Should return false since ones() already clears trailing bits
924        assert!(!bv_clean.clear_trailing_bits());
925
926        // Create a bitmap with invalid trailing bits by manually setting them
927        let mut bv_dirty: BitMap<4> = BitMap::ones(20);
928        // Manually corrupt the last chunk to have trailing bits set
929        let last_chunk = bv_dirty.chunks.back_mut().unwrap();
930        last_chunk[3] |= 0xF0; // Set some high bits in the last byte
931                               // Should return true since we had invalid trailing bits
932        assert!(bv_dirty.clear_trailing_bits());
933        // After clearing, should return false
934        assert!(!bv_dirty.clear_trailing_bits());
935        check_trailing_bits_zero(&bv_dirty);
936    }
937
938    #[test]
939    fn test_get_set() {
940        let mut bv: BitMap<4> = BitMap::new();
941
942        // Test initial state
943        assert_eq!(bv.len(), 0);
944        assert!(bv.is_empty());
945
946        // Test push
947        bv.push(true);
948        bv.push(false);
949        bv.push(true);
950        assert_eq!(bv.len(), 3);
951        assert!(!bv.is_empty());
952
953        // Test get
954        assert!(bv.get(0));
955        assert!(!bv.get(1));
956        assert!(bv.get(2));
957
958        bv.set(1, true);
959        assert!(bv.get(1));
960        bv.set(2, false);
961        assert!(!bv.get(2));
962
963        // Test flip
964        bv.flip(0); // true -> false
965        assert!(!bv.get(0));
966        bv.flip(0); // false -> true
967        assert!(bv.get(0));
968    }
969
970    #[test]
971    fn test_chunk_operations() {
972        let mut bv: BitMap<4> = BitMap::new();
973        let test_chunk = hex!("0xABCDEF12");
974
975        // Test push_chunk
976        bv.push_chunk(&test_chunk);
977        assert_eq!(bv.len(), 32); // 4 bytes * 8 bits
978
979        // Test get_chunk
980        let chunk = bv.get_chunk(0);
981        assert_eq!(chunk, &test_chunk);
982
983        // Test get_chunk_containing
984        let chunk = bv.get_chunk_containing(0);
985        assert_eq!(chunk, &test_chunk);
986
987        // Test last_chunk
988        let (last_chunk, next_bit) = bv.last_chunk();
989        assert_eq!(next_bit, BitMap::<4>::CHUNK_SIZE_BITS); // Should be at chunk boundary
990        assert_eq!(last_chunk, &test_chunk); // The chunk we just pushed
991    }
992
993    #[test]
994    fn test_pop() {
995        let mut bv: BitMap<3> = BitMap::new();
996        bv.push(true);
997        assert!(bv.pop());
998        assert_eq!(bv.len(), 0);
999
1000        bv.push(false);
1001        assert!(!bv.pop());
1002        assert_eq!(bv.len(), 0);
1003
1004        bv.push(true);
1005        bv.push(false);
1006        bv.push(true);
1007        assert!(bv.pop());
1008        assert_eq!(bv.len(), 2);
1009        assert!(!bv.pop());
1010        assert_eq!(bv.len(), 1);
1011        assert!(bv.pop());
1012        assert_eq!(bv.len(), 0);
1013
1014        for i in 0..100 {
1015            bv.push(i % 2 == 0);
1016        }
1017        assert_eq!(bv.len(), 100);
1018        for i in (0..100).rev() {
1019            assert_eq!(bv.pop(), i % 2 == 0);
1020        }
1021        assert_eq!(bv.len(), 0);
1022        assert!(bv.is_empty());
1023    }
1024
1025    #[test]
1026    fn test_pop_chunk() {
1027        let mut bv: BitMap<3> = BitMap::new();
1028        const CHUNK_SIZE: u64 = BitMap::<3>::CHUNK_SIZE_BITS;
1029
1030        // Test 1: Pop a single chunk and verify it returns the correct data
1031        let chunk1 = hex!("0xAABBCC");
1032        bv.push_chunk(&chunk1);
1033        assert_eq!(bv.len(), CHUNK_SIZE);
1034        let popped = bv.pop_chunk();
1035        assert_eq!(popped, chunk1);
1036        assert_eq!(bv.len(), 0);
1037        assert!(bv.is_empty());
1038
1039        // Test 2: Pop multiple chunks in reverse order
1040        let chunk2 = hex!("0x112233");
1041        let chunk3 = hex!("0x445566");
1042        let chunk4 = hex!("0x778899");
1043
1044        bv.push_chunk(&chunk2);
1045        bv.push_chunk(&chunk3);
1046        bv.push_chunk(&chunk4);
1047        assert_eq!(bv.len(), CHUNK_SIZE * 3);
1048
1049        assert_eq!(bv.pop_chunk(), chunk4);
1050        assert_eq!(bv.len(), CHUNK_SIZE * 2);
1051
1052        assert_eq!(bv.pop_chunk(), chunk3);
1053        assert_eq!(bv.len(), CHUNK_SIZE);
1054
1055        assert_eq!(bv.pop_chunk(), chunk2);
1056        assert_eq!(bv.len(), 0);
1057
1058        // Test 3: Verify data integrity when popping chunks
1059        let first_chunk = hex!("0xAABBCC");
1060        let second_chunk = hex!("0x112233");
1061        bv.push_chunk(&first_chunk);
1062        bv.push_chunk(&second_chunk);
1063
1064        // Pop the second chunk, verify it and that first chunk is intact
1065        assert_eq!(bv.pop_chunk(), second_chunk);
1066        assert_eq!(bv.len(), CHUNK_SIZE);
1067
1068        for i in 0..CHUNK_SIZE {
1069            let byte_idx = (i / 8) as usize;
1070            let bit_idx = i % 8;
1071            let expected = (first_chunk[byte_idx] >> bit_idx) & 1 == 1;
1072            assert_eq!(bv.get(i), expected);
1073        }
1074
1075        assert_eq!(bv.pop_chunk(), first_chunk);
1076        assert_eq!(bv.len(), 0);
1077    }
1078
1079    #[test]
1080    #[should_panic(expected = "cannot pop chunk when not chunk aligned")]
1081    fn test_pop_chunk_not_aligned() {
1082        let mut bv: BitMap<3> = BitMap::new();
1083
1084        // Push a full chunk plus one bit
1085        bv.push_chunk(&[0xFF; 3]);
1086        bv.push(true);
1087
1088        // Should panic because not chunk-aligned
1089        bv.pop_chunk();
1090    }
1091
1092    #[test]
1093    #[should_panic(expected = "cannot pop chunk: bitmap has fewer than CHUNK_SIZE_BITS bits")]
1094    fn test_pop_chunk_insufficient_bits() {
1095        let mut bv: BitMap<3> = BitMap::new();
1096
1097        // Push only a few bits (less than a full chunk)
1098        bv.push(true);
1099        bv.push(false);
1100
1101        // Should panic because we don't have a full chunk to pop
1102        bv.pop_chunk();
1103    }
1104
1105    #[test]
1106    fn test_byte_operations() {
1107        let mut bv: BitMap<4> = BitMap::new();
1108
1109        // Test push_byte
1110        bv.push_byte(0xFF);
1111        assert_eq!(bv.len(), 8);
1112
1113        // All bits in the byte should be set
1114        for i in 0..8 {
1115            assert!(bv.get(i as u64));
1116        }
1117
1118        bv.push_byte(0x00);
1119        assert_eq!(bv.len(), 16);
1120
1121        // All bits in the second byte should be clear
1122        for i in 8..16 {
1123            assert!(!bv.get(i as u64));
1124        }
1125    }
1126
1127    #[test]
1128    fn test_count_operations() {
1129        let mut bv: BitMap<4> = BitMap::new();
1130
1131        // Empty bitmap
1132        assert_eq!(bv.count_ones(), 0);
1133        assert_eq!(bv.count_zeros(), 0);
1134
1135        // Add some bits
1136        bv.push(true);
1137        bv.push(false);
1138        bv.push(true);
1139        bv.push(true);
1140        bv.push(false);
1141
1142        assert_eq!(bv.count_ones(), 3);
1143        assert_eq!(bv.count_zeros(), 2);
1144        assert_eq!(bv.len(), 5);
1145
1146        // Test with full bytes
1147        let mut bv2: BitMap<4> = BitMap::new();
1148        bv2.push_byte(0xFF); // 8 ones
1149        bv2.push_byte(0x00); // 8 zeros
1150        bv2.push_byte(0xAA); // 4 ones, 4 zeros (10101010)
1151
1152        assert_eq!(bv2.count_ones(), 12);
1153        assert_eq!(bv2.count_zeros(), 12);
1154        assert_eq!(bv2.len(), 24);
1155    }
1156
1157    #[test]
1158    fn test_set_all() {
1159        let mut bv: BitMap<1> = BitMap::new();
1160
1161        // Add some bits
1162        bv.push(true);
1163        bv.push(false);
1164        bv.push(true);
1165        bv.push(false);
1166        bv.push(true);
1167        bv.push(false);
1168        bv.push(true);
1169        bv.push(false);
1170        bv.push(true);
1171        bv.push(false);
1172
1173        assert_eq!(bv.len(), 10);
1174        assert_eq!(bv.count_ones(), 5);
1175        assert_eq!(bv.count_zeros(), 5);
1176
1177        // Test set_all(true)
1178        bv.set_all(true);
1179        assert_eq!(bv.len(), 10);
1180        assert_eq!(bv.count_ones(), 10);
1181        assert_eq!(bv.count_zeros(), 0);
1182
1183        // Test set_all(false)
1184        bv.set_all(false);
1185        assert_eq!(bv.len(), 10);
1186        assert_eq!(bv.count_ones(), 0);
1187        assert_eq!(bv.count_zeros(), 10);
1188    }
1189
1190    #[test]
1191    fn test_flip_all() {
1192        let mut bv: BitMap<4> = BitMap::new();
1193
1194        bv.push(true);
1195        bv.push(false);
1196        bv.push(true);
1197        bv.push(false);
1198        bv.push(true);
1199
1200        let original_ones = bv.count_ones();
1201        let original_zeros = bv.count_zeros();
1202        let original_len = bv.len();
1203
1204        bv.flip_all();
1205
1206        // Length should not change
1207        assert_eq!(bv.len(), original_len);
1208
1209        // Ones and zeros should be swapped
1210        assert_eq!(bv.count_ones(), original_zeros);
1211        assert_eq!(bv.count_zeros(), original_ones);
1212
1213        // Check bits
1214        assert!(!bv.get(0));
1215        assert!(bv.get(1));
1216        assert!(!bv.get(2));
1217        assert!(bv.get(3));
1218        assert!(!bv.get(4));
1219    }
1220
1221    #[test]
1222    fn test_bitwise_and() {
1223        let mut bv1: BitMap<4> = BitMap::new();
1224        let mut bv2: BitMap<4> = BitMap::new();
1225
1226        // Create test patterns: 10110 & 11010 = 10010
1227        let pattern1 = [true, false, true, true, false];
1228        let pattern2 = [true, true, false, true, false];
1229        let expected = [true, false, false, true, false];
1230
1231        for &bit in &pattern1 {
1232            bv1.push(bit);
1233        }
1234        for &bit in &pattern2 {
1235            bv2.push(bit);
1236        }
1237
1238        bv1.and(&bv2);
1239
1240        assert_eq!(bv1.len(), 5);
1241        for (i, &expected_bit) in expected.iter().enumerate() {
1242            assert_eq!(bv1.get(i as u64), expected_bit);
1243        }
1244    }
1245
1246    #[test]
1247    fn test_bitwise_or() {
1248        let mut bv1: BitMap<4> = BitMap::new();
1249        let mut bv2: BitMap<4> = BitMap::new();
1250
1251        // Create test patterns: 10110 | 11010 = 11110
1252        let pattern1 = [true, false, true, true, false];
1253        let pattern2 = [true, true, false, true, false];
1254        let expected = [true, true, true, true, false];
1255
1256        for &bit in &pattern1 {
1257            bv1.push(bit);
1258        }
1259        for &bit in &pattern2 {
1260            bv2.push(bit);
1261        }
1262
1263        bv1.or(&bv2);
1264
1265        assert_eq!(bv1.len(), 5);
1266        for (i, &expected_bit) in expected.iter().enumerate() {
1267            assert_eq!(bv1.get(i as u64), expected_bit);
1268        }
1269    }
1270
1271    #[test]
1272    fn test_bitwise_xor() {
1273        let mut bv1: BitMap<4> = BitMap::new();
1274        let mut bv2: BitMap<4> = BitMap::new();
1275
1276        // Create test patterns: 10110 ^ 11010 = 01100
1277        let pattern1 = [true, false, true, true, false];
1278        let pattern2 = [true, true, false, true, false];
1279        let expected = [false, true, true, false, false];
1280
1281        for &bit in &pattern1 {
1282            bv1.push(bit);
1283        }
1284        for &bit in &pattern2 {
1285            bv2.push(bit);
1286        }
1287
1288        bv1.xor(&bv2);
1289
1290        assert_eq!(bv1.len(), 5);
1291        for (i, &expected_bit) in expected.iter().enumerate() {
1292            assert_eq!(bv1.get(i as u64), expected_bit);
1293        }
1294    }
1295
1296    #[test]
1297    fn test_multi_chunk_operations() {
1298        let mut bv1: BitMap<4> = BitMap::new();
1299        let mut bv2: BitMap<4> = BitMap::new();
1300
1301        // Fill multiple chunks
1302        let chunk1 = hex!("0xAABBCCDD"); // 10101010 10111011 11001100 11011101
1303        let chunk2 = hex!("0x55667788"); // 01010101 01100110 01110111 10001000
1304
1305        bv1.push_chunk(&chunk1);
1306        bv1.push_chunk(&chunk1);
1307        bv2.push_chunk(&chunk2);
1308        bv2.push_chunk(&chunk2);
1309
1310        assert_eq!(bv1.len(), 64);
1311        assert_eq!(bv2.len(), 64);
1312
1313        // Test AND operation
1314        let mut bv_and = bv1.clone();
1315        bv_and.and(&bv2);
1316
1317        // Test OR operation
1318        let mut bv_or = bv1.clone();
1319        bv_or.or(&bv2);
1320
1321        // Test XOR operation
1322        let mut bv_xor = bv1.clone();
1323        bv_xor.xor(&bv2);
1324
1325        // Verify results make sense
1326        assert_eq!(bv_and.len(), 64);
1327        assert_eq!(bv_or.len(), 64);
1328        assert_eq!(bv_xor.len(), 64);
1329
1330        // AND should have fewer or equal ones than either operand
1331        assert!(bv_and.count_ones() <= bv1.count_ones());
1332        assert!(bv_and.count_ones() <= bv2.count_ones());
1333
1334        // OR should have more or equal ones than either operand
1335        assert!(bv_or.count_ones() >= bv1.count_ones());
1336        assert!(bv_or.count_ones() >= bv2.count_ones());
1337    }
1338
1339    #[test]
1340    fn test_partial_chunk_operations() {
1341        let mut bv1: BitMap<4> = BitMap::new();
1342        let mut bv2: BitMap<4> = BitMap::new();
1343
1344        // Add partial chunks (not aligned to chunk boundaries)
1345        for i in 0..35 {
1346            // 35 bits = 4 bytes + 3 bits
1347            bv1.push(i % 2 == 0);
1348            bv2.push(i % 3 == 0);
1349        }
1350
1351        assert_eq!(bv1.len(), 35);
1352        assert_eq!(bv2.len(), 35);
1353
1354        // Test operations with partial chunks
1355        let mut bv_and = bv1.clone();
1356        bv_and.and(&bv2);
1357
1358        let mut bv_or = bv1.clone();
1359        bv_or.or(&bv2);
1360
1361        let mut bv_xor = bv1.clone();
1362        bv_xor.xor(&bv2);
1363
1364        // All should maintain the same length
1365        assert_eq!(bv_and.len(), 35);
1366        assert_eq!(bv_or.len(), 35);
1367        assert_eq!(bv_xor.len(), 35);
1368
1369        // Test flip_all with partial chunk
1370        let mut bv_inv = bv1.clone();
1371        let original_ones = bv_inv.count_ones();
1372        let original_zeros = bv_inv.count_zeros();
1373        bv_inv.flip_all();
1374        assert_eq!(bv_inv.count_ones(), original_zeros);
1375        assert_eq!(bv_inv.count_zeros(), original_ones);
1376    }
1377
1378    #[test]
1379    #[should_panic(expected = "bit 1 out of bounds (len: 1)")]
1380    fn test_flip_out_of_bounds() {
1381        let mut bv: BitMap<4> = BitMap::new();
1382        bv.push(true);
1383        bv.flip(1); // Only bit 0 exists
1384    }
1385
1386    #[test]
1387    #[should_panic(expected = "BitMap lengths don't match: 2 vs 1")]
1388    fn test_and_length_mismatch() {
1389        let mut bv1: BitMap<4> = BitMap::new();
1390        let mut bv2: BitMap<4> = BitMap::new();
1391
1392        bv1.push(true);
1393        bv1.push(false);
1394        bv2.push(true); // Different length
1395
1396        bv1.and(&bv2);
1397    }
1398
1399    #[test]
1400    #[should_panic(expected = "BitMap lengths don't match: 1 vs 2")]
1401    fn test_or_length_mismatch() {
1402        let mut bv1: BitMap<4> = BitMap::new();
1403        let mut bv2: BitMap<4> = BitMap::new();
1404
1405        bv1.push(true);
1406        bv2.push(true);
1407        bv2.push(false); // Different length
1408
1409        bv1.or(&bv2);
1410    }
1411
1412    #[test]
1413    #[should_panic(expected = "BitMap lengths don't match: 3 vs 2")]
1414    fn test_xor_length_mismatch() {
1415        let mut bv1: BitMap<4> = BitMap::new();
1416        let mut bv2: BitMap<4> = BitMap::new();
1417
1418        bv1.push(true);
1419        bv1.push(false);
1420        bv1.push(true);
1421        bv2.push(true);
1422        bv2.push(false); // Different length
1423
1424        bv1.xor(&bv2);
1425    }
1426
1427    #[test]
1428    fn test_equality() {
1429        // Test empty bitmaps
1430        assert_eq!(BitMap::<4>::new(), BitMap::<4>::new());
1431        assert_eq!(BitMap::<8>::new(), BitMap::<8>::new());
1432
1433        // Test non-empty bitmaps from constructors
1434        let pattern = [true, false, true, true, false, false, true, false, true];
1435        let bv4: BitMap<4> = pattern.as_ref().into();
1436        assert_eq!(bv4, BitMap::<4>::from(pattern.as_ref()));
1437        let bv8: BitMap<8> = pattern.as_ref().into();
1438        assert_eq!(bv8, BitMap::<8>::from(pattern.as_ref()));
1439
1440        // Test non-empty bitmaps from push operations
1441        let mut bv1: BitMap<4> = BitMap::new();
1442        let mut bv2: BitMap<4> = BitMap::new();
1443        for i in 0..33 {
1444            let bit = i % 3 == 0;
1445            bv1.push(bit);
1446            bv2.push(bit);
1447        }
1448        assert_eq!(bv1, bv2);
1449
1450        // Test inequality: different lengths
1451        bv1.push(true);
1452        assert_ne!(bv1, bv2);
1453        bv1.pop(); // Restore equality
1454        assert_eq!(bv1, bv2);
1455
1456        // Test inequality: different content
1457        bv1.flip(15);
1458        assert_ne!(bv1, bv2);
1459        bv1.flip(15); // Restore equality
1460        assert_eq!(bv1, bv2);
1461
1462        // Test equality after operations
1463        let mut bv_ops1 = BitMap::<16>::ones(25);
1464        let mut bv_ops2 = BitMap::<16>::ones(25);
1465        bv_ops1.flip_all();
1466        bv_ops2.flip_all();
1467        assert_eq!(bv_ops1, bv_ops2);
1468
1469        let mask_bits: Vec<bool> = (0..33).map(|i| i % 3 == 0).collect();
1470        let mask = BitMap::<4>::from(mask_bits);
1471        bv1.and(&mask);
1472        bv2.and(&mask);
1473        assert_eq!(bv1, bv2);
1474    }
1475
1476    #[test]
1477    fn test_different_chunk_sizes() {
1478        // Test with different chunk sizes
1479        let mut bv8: BitMap<8> = BitMap::new();
1480        let mut bv16: BitMap<16> = BitMap::new();
1481        let mut bv32: BitMap<32> = BitMap::new();
1482
1483        // Test chunk operations first (must be chunk-aligned)
1484        let chunk8 = [0xFF; 8];
1485        let chunk16 = [0xAA; 16];
1486        let chunk32 = [0x55; 32];
1487
1488        bv8.push_chunk(&chunk8);
1489        bv16.push_chunk(&chunk16);
1490        bv32.push_chunk(&chunk32);
1491
1492        // Test basic operations work with different sizes
1493        bv8.push(true);
1494        bv8.push(false);
1495        assert_eq!(bv8.len(), 64 + 2);
1496        assert_eq!(bv8.count_ones(), 64 + 1); // chunk8 is all 0xFF + 1 true bit
1497        assert_eq!(bv8.count_zeros(), 1);
1498
1499        bv16.push(true);
1500        bv16.push(false);
1501        assert_eq!(bv16.len(), 128 + 2);
1502        assert_eq!(bv16.count_ones(), 64 + 1); // chunk16 is 0xAA pattern + 1 true bit
1503        assert_eq!(bv16.count_zeros(), 64 + 1);
1504
1505        bv32.push(true);
1506        bv32.push(false);
1507        assert_eq!(bv32.len(), 256 + 2);
1508        assert_eq!(bv32.count_ones(), 128 + 1); // chunk32 is 0x55 pattern + 1 true bit
1509        assert_eq!(bv32.count_zeros(), 128 + 1);
1510    }
1511
1512    #[test]
1513    fn test_iterator() {
1514        // Test empty iterator
1515        let bv: BitMap<4> = BitMap::new();
1516        let mut iter = bv.iter();
1517        assert_eq!(iter.next(), None);
1518        assert_eq!(iter.size_hint(), (0, Some(0)));
1519
1520        // Test iterator with some bits
1521        let pattern = [true, false, true, false, true];
1522        let bv: BitMap<4> = pattern.as_ref().into();
1523
1524        // Collect all bits via iterator
1525        let collected: Vec<bool> = bv.iter().collect();
1526        assert_eq!(collected, pattern);
1527
1528        // Test size_hint
1529        let mut iter = bv.iter();
1530        assert_eq!(iter.size_hint(), (5, Some(5)));
1531
1532        // Consume one element and check size_hint again
1533        assert_eq!(iter.next(), Some(true));
1534        assert_eq!(iter.size_hint(), (4, Some(4)));
1535
1536        // Test ExactSizeIterator
1537        let iter = bv.iter();
1538        assert_eq!(iter.len(), 5);
1539
1540        // Test iterator with larger bitmap
1541        let mut large_bv: BitMap<8> = BitMap::new();
1542        for i in 0..100 {
1543            large_bv.push(i % 3 == 0);
1544        }
1545
1546        let collected: Vec<bool> = large_bv.iter().collect();
1547        assert_eq!(collected.len(), 100);
1548        for (i, &bit) in collected.iter().enumerate() {
1549            assert_eq!(bit, i % 3 == 0);
1550        }
1551    }
1552
1553    #[test]
1554    fn test_iterator_edge_cases() {
1555        // Test iterator with single bit
1556        let mut bv: BitMap<4> = BitMap::new();
1557        bv.push(true);
1558
1559        let collected: Vec<bool> = bv.iter().collect();
1560        assert_eq!(collected, vec![true]);
1561
1562        // Test iterator across chunk boundaries
1563        let mut bv: BitMap<4> = BitMap::new();
1564        // Fill exactly one chunk (32 bits)
1565        for i in 0..32 {
1566            bv.push(i % 2 == 0);
1567        }
1568        // Add a few more bits in the next chunk
1569        bv.push(true);
1570        bv.push(false);
1571        bv.push(true);
1572
1573        let collected: Vec<bool> = bv.iter().collect();
1574        assert_eq!(collected.len(), 35);
1575
1576        // Verify the pattern
1577        for (i, &bit) in collected.iter().enumerate().take(32) {
1578            assert_eq!(bit, i % 2 == 0);
1579        }
1580        assert!(collected[32]);
1581        assert!(!collected[33]);
1582        assert!(collected[34]);
1583    }
1584
1585    #[test]
1586    fn test_codec_roundtrip() {
1587        // Test empty bitmap
1588        let original: BitMap<4> = BitMap::new();
1589        let encoded = original.encode();
1590        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1591        assert_eq!(original, decoded);
1592
1593        // Test small bitmap
1594        let pattern = [true, false, true, false, true];
1595        let original: BitMap<4> = pattern.as_ref().into();
1596        let encoded = original.encode();
1597        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1598        assert_eq!(original, decoded);
1599
1600        // Verify the decoded bitmap has the same bits
1601        for (i, &expected) in pattern.iter().enumerate() {
1602            assert_eq!(decoded.get(i as u64), expected);
1603        }
1604
1605        // Test larger bitmap across multiple chunks
1606        let mut large_original: BitMap<8> = BitMap::new();
1607        for i in 0..100 {
1608            large_original.push(i % 7 == 0);
1609        }
1610
1611        let encoded = large_original.encode();
1612        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1613        assert_eq!(large_original, decoded);
1614
1615        // Verify all bits match
1616        assert_eq!(decoded.len(), 100);
1617        for i in 0..100 {
1618            assert_eq!(decoded.get(i as u64), i % 7 == 0);
1619        }
1620    }
1621
1622    #[test]
1623    fn test_codec_different_chunk_sizes() {
1624        let pattern = [true, false, true, true, false, false, true];
1625
1626        // Test with different chunk sizes
1627        let bv4: BitMap<4> = pattern.as_ref().into();
1628        let bv8: BitMap<8> = pattern.as_ref().into();
1629        let bv16: BitMap<16> = pattern.as_ref().into();
1630
1631        // Encode and decode each
1632        let encoded4 = bv4.encode();
1633        let decoded4 = BitMap::decode_cfg(&mut encoded4.as_ref(), &(usize::MAX as u64)).unwrap();
1634        assert_eq!(bv4, decoded4);
1635
1636        let encoded8 = bv8.encode();
1637        let decoded8 = BitMap::decode_cfg(&mut encoded8.as_ref(), &(usize::MAX as u64)).unwrap();
1638        assert_eq!(bv8, decoded8);
1639
1640        let encoded16 = bv16.encode();
1641        let decoded16 = BitMap::decode_cfg(&mut encoded16.as_ref(), &(usize::MAX as u64)).unwrap();
1642        assert_eq!(bv16, decoded16);
1643
1644        // All should have the same logical content
1645        for (i, &expected) in pattern.iter().enumerate() {
1646            let i = i as u64;
1647            assert_eq!(decoded4.get(i), expected);
1648            assert_eq!(decoded8.get(i), expected);
1649            assert_eq!(decoded16.get(i), expected);
1650        }
1651    }
1652
1653    #[test]
1654    fn test_codec_edge_cases() {
1655        // Test bitmap with exactly one chunk filled
1656        let mut bv: BitMap<4> = BitMap::new();
1657        for i in 0..32 {
1658            bv.push(i % 2 == 0);
1659        }
1660
1661        let encoded = bv.encode();
1662        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1663        assert_eq!(bv, decoded);
1664        assert_eq!(decoded.len(), 32);
1665
1666        // Test bitmap with partial chunk
1667        let mut bv2: BitMap<4> = BitMap::new();
1668        for i in 0..35 {
1669            // 32 + 3 bits
1670            bv2.push(i % 3 == 0);
1671        }
1672
1673        let encoded2 = bv2.encode();
1674        let decoded2 = BitMap::decode_cfg(&mut encoded2.as_ref(), &(usize::MAX as u64)).unwrap();
1675        assert_eq!(bv2, decoded2);
1676        assert_eq!(decoded2.len(), 35);
1677    }
1678
1679    #[test]
1680    fn test_encode_size() {
1681        // Test encode size calculation
1682        let bv: BitMap<4> = BitMap::new();
1683        let encoded = bv.encode();
1684        assert_eq!(bv.encode_size(), encoded.len());
1685
1686        // Test with some data
1687        let pattern = [true, false, true, false, true];
1688        let bv: BitMap<4> = pattern.as_ref().into();
1689        let encoded = bv.encode();
1690        assert_eq!(bv.encode_size(), encoded.len());
1691
1692        // Test with larger data
1693        let mut large_bv: BitMap<8> = BitMap::new();
1694        for i in 0..100 {
1695            large_bv.push(i % 2 == 0);
1696        }
1697        let encoded = large_bv.encode();
1698        assert_eq!(large_bv.encode_size(), encoded.len());
1699    }
1700
1701    #[test]
1702    fn test_codec_empty_chunk_optimization() {
1703        // Test that empty last chunks are not serialized
1704
1705        // Case 1: Empty bitmap (omits the only empty chunk)
1706        let bv_empty: BitMap<4> = BitMap::new();
1707        let encoded_empty = bv_empty.encode();
1708        let decoded_empty: BitMap<4> =
1709            BitMap::decode_cfg(&mut encoded_empty.as_ref(), &(usize::MAX as u64)).unwrap();
1710        assert_eq!(bv_empty, decoded_empty);
1711        assert_eq!(bv_empty.len(), decoded_empty.len());
1712        // Should only encode the length, no chunks
1713        assert_eq!(encoded_empty.len(), bv_empty.len().encode_size());
1714
1715        // Case 2: Bitmap ending exactly at chunk boundary (omits empty last chunk)
1716        let mut bv_exact: BitMap<4> = BitMap::new();
1717        for _ in 0..32 {
1718            bv_exact.push(true);
1719        }
1720        let encoded_exact = bv_exact.encode();
1721        let decoded_exact: BitMap<4> =
1722            BitMap::decode_cfg(&mut encoded_exact.as_ref(), &(usize::MAX as u64)).unwrap();
1723        assert_eq!(bv_exact, decoded_exact);
1724
1725        // Case 3: Bitmap with partial last chunk (includes last chunk)
1726        let mut bv_partial: BitMap<4> = BitMap::new();
1727        for _ in 0..35 {
1728            bv_partial.push(true);
1729        }
1730        let encoded_partial = bv_partial.encode();
1731        let decoded_partial: BitMap<4> =
1732            BitMap::decode_cfg(&mut encoded_partial.as_ref(), &(usize::MAX as u64)).unwrap();
1733        assert_eq!(bv_partial, decoded_partial);
1734        assert_eq!(bv_partial.len(), decoded_partial.len());
1735
1736        // Verify optimization works correctly
1737        assert!(encoded_exact.len() < encoded_partial.len());
1738        assert_eq!(encoded_exact.len(), bv_exact.len().encode_size() + 4); // length + 1 chunk
1739        assert_eq!(encoded_partial.len(), bv_partial.len().encode_size() + 8); // length + 2 chunks
1740    }
1741
1742    #[test]
1743    fn test_codec_error_cases() {
1744        // Test invalid length with range check
1745        let mut buf = BytesMut::new();
1746        100u64.write(&mut buf); // bits length
1747
1748        // 100 bits requires 4 chunks (3 full + partially filled)
1749        for _ in 0..4 {
1750            [0u8; 4].write(&mut buf);
1751        }
1752
1753        // Test with a restricted range that excludes 100
1754        let result = BitMap::<4>::decode_cfg(&mut buf, &99);
1755        assert!(matches!(result, Err(CodecError::InvalidLength(100))));
1756
1757        // Test truncated buffer (not enough chunks)
1758        let mut buf = BytesMut::new();
1759        100u64.write(&mut buf); // bits length requiring 4 chunks (3 full + partially filled)
1760                                // Only write 3 chunks
1761        [0u8; 4].write(&mut buf);
1762        [0u8; 4].write(&mut buf);
1763        [0u8; 4].write(&mut buf);
1764
1765        let result = BitMap::<4>::decode_cfg(&mut buf, &(usize::MAX as u64));
1766        // Should fail when trying to read missing chunks
1767        assert!(result.is_err());
1768
1769        // Test invalid trailing bits
1770
1771        // Create a valid bitmap and encode it
1772        let original: BitMap<4> = BitMap::ones(20);
1773        let mut buf = BytesMut::new();
1774        original.write(&mut buf);
1775
1776        // Manually corrupt the encoded data by setting trailing bits
1777        let corrupted_data = buf.freeze();
1778        let mut corrupted_bytes = corrupted_data.to_vec();
1779
1780        // The last byte should have some trailing bits set to 1
1781        // For 20 bits with 4-byte chunks: 20 bits = 2.5 bytes, so last byte should have 4 valid bits
1782        // Set the high 4 bits of the last byte to 1 (these should be 0)
1783        let last_byte_idx = corrupted_bytes.len() - 1;
1784        corrupted_bytes[last_byte_idx] |= 0xF0;
1785
1786        // Read should fail
1787        let result = BitMap::<4>::read_cfg(&mut corrupted_bytes.as_slice(), &(usize::MAX as u64));
1788        assert!(matches!(
1789            result,
1790            Err(CodecError::Invalid(
1791                "BitMap",
1792                "Invalid trailing bits in encoded data"
1793            ))
1794        ));
1795    }
1796
1797    #[test]
1798    fn test_codec_range_config() {
1799        // Test RangeCfg validation in read_cfg
1800
1801        // Create a bitmap with 100 bits
1802        let mut original: BitMap<4> = BitMap::new();
1803        for i in 0..100 {
1804            original.push(i % 3 == 0);
1805        }
1806
1807        // Write to a buffer
1808        let mut buf = BytesMut::new();
1809        original.write(&mut buf);
1810
1811        // Test with max length < actual size (should fail)
1812        let result = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &50);
1813        assert!(matches!(result, Err(CodecError::InvalidLength(100))));
1814
1815        // Test with max length == actual size (should succeed)
1816        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &100).unwrap();
1817        assert_eq!(decoded.len(), 100);
1818        assert_eq!(decoded, original);
1819
1820        // Test with max length > actual size (should succeed)
1821        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &101).unwrap();
1822        assert_eq!(decoded.len(), 100);
1823        assert_eq!(decoded, original);
1824
1825        // Test empty bitmap
1826        let empty = BitMap::<4>::new();
1827        let mut buf = BytesMut::new();
1828        empty.write(&mut buf);
1829
1830        // Empty bitmap should work with max length 0
1831        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &0).unwrap();
1832        assert_eq!(decoded.len(), 0);
1833        assert!(decoded.is_empty());
1834
1835        // Empty bitmap should work with max length > 0
1836        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &1).unwrap();
1837        assert_eq!(decoded.len(), 0);
1838        assert!(decoded.is_empty());
1839    }
1840
1841    #[test]
1842    fn test_from() {
1843        // Test From trait with different input types
1844
1845        // Test with Vec<bool>
1846        let vec_bool = vec![true, false, true, false, true];
1847        let bv: BitMap<4> = vec_bool.into();
1848        assert_eq!(bv.len(), 5);
1849        assert_eq!(bv.count_ones(), 3);
1850        assert_eq!(bv.count_zeros(), 2);
1851        for (i, &expected) in [true, false, true, false, true].iter().enumerate() {
1852            assert_eq!(bv.get(i as u64), expected);
1853        }
1854
1855        // Test with array slice
1856        let array = [false, true, true, false];
1857        let bv: BitMap<4> = (&array).into();
1858        assert_eq!(bv.len(), 4);
1859        assert_eq!(bv.count_ones(), 2);
1860        assert_eq!(bv.count_zeros(), 2);
1861        for (i, &expected) in array.iter().enumerate() {
1862            assert_eq!(bv.get(i as u64), expected);
1863        }
1864
1865        // Test with empty slice
1866        let empty: Vec<bool> = vec![];
1867        let bv: BitMap<4> = empty.into();
1868        assert_eq!(bv.len(), 0);
1869        assert!(bv.is_empty());
1870
1871        // Test with large slice
1872        let large: Vec<bool> = (0..100).map(|i| i % 3 == 0).collect();
1873        let bv: BitMap<8> = large.clone().into();
1874        assert_eq!(bv.len(), 100);
1875        for (i, &expected) in large.iter().enumerate() {
1876            assert_eq!(bv.get(i as u64), expected);
1877        }
1878    }
1879
1880    #[test]
1881    fn test_debug_formatting() {
1882        // Test Debug formatting for different sizes
1883
1884        // Test empty bitmap
1885        let bv: BitMap<4> = BitMap::new();
1886        let debug_str = format!("{bv:?}");
1887        assert_eq!(debug_str, "BitMap[]");
1888
1889        // Test small bitmap (should show all bits)
1890        let bv: BitMap<4> = [true, false, true, false, true].as_ref().into();
1891        let debug_str = format!("{bv:?}");
1892        assert_eq!(debug_str, "BitMap[10101]");
1893
1894        // Test bitmap at the display limit (64 bits)
1895        let pattern: Vec<bool> = (0..64).map(|i| i % 2 == 0).collect();
1896        let bv: BitMap<8> = pattern.into();
1897        let debug_str = format!("{bv:?}");
1898        let expected_pattern = "1010".repeat(16); // 64 bits alternating
1899        assert_eq!(debug_str, format!("BitMap[{expected_pattern}]"));
1900
1901        // Test large bitmap (should show ellipsis)
1902        let large_pattern: Vec<bool> = (0..100).map(|i| i % 2 == 0).collect();
1903        let bv: BitMap<16> = large_pattern.into();
1904        let debug_str = format!("{bv:?}");
1905
1906        // Should show first 32 bits + "..." + last 32 bits
1907        let first_32 = "10".repeat(16); // First 32 bits: 1010...
1908        let last_32 = "10".repeat(16); // Last 32 bits: ...1010
1909        let expected = format!("BitMap[{first_32}...{last_32}]");
1910        assert_eq!(debug_str, expected);
1911
1912        // Test single bit
1913        let bv: BitMap<4> = [true].as_ref().into();
1914        assert_eq!(format!("{bv:?}"), "BitMap[1]");
1915
1916        let bv: BitMap<4> = [false].as_ref().into();
1917        assert_eq!(format!("{bv:?}"), "BitMap[0]");
1918
1919        // Test exactly at boundary (65 bits - should show ellipsis)
1920        let pattern: Vec<bool> = (0..65).map(|i| i == 0 || i == 64).collect(); // First and last bits are true
1921        let bv: BitMap<16> = pattern.into();
1922        let debug_str = format!("{bv:?}");
1923
1924        // Should show first 32 bits (100000...) + "..." + last 32 bits (...000001)
1925        let first_32 = "1".to_string() + &"0".repeat(31);
1926        let last_32 = "0".repeat(31) + "1";
1927        let expected = format!("BitMap[{first_32}...{last_32}]");
1928        assert_eq!(debug_str, expected);
1929    }
1930
1931    #[test]
1932    fn test_from_different_chunk_sizes() {
1933        // Test From trait works with different chunk sizes
1934        let pattern = [true, false, true, true, false, false, true];
1935
1936        let bv4: BitMap<4> = pattern.as_ref().into();
1937        let bv8: BitMap<8> = pattern.as_ref().into();
1938        let bv16: BitMap<16> = pattern.as_ref().into();
1939
1940        // All should have the same content regardless of chunk size
1941        // Test each bitmap separately since they have different types
1942        for bv in [&bv4] {
1943            assert_eq!(bv.len(), 7);
1944            assert_eq!(bv.count_ones(), 4);
1945            assert_eq!(bv.count_zeros(), 3);
1946            for (i, &expected) in pattern.iter().enumerate() {
1947                assert_eq!(bv.get(i as u64), expected);
1948            }
1949        }
1950
1951        assert_eq!(bv8.len(), 7);
1952        assert_eq!(bv8.count_ones(), 4);
1953        assert_eq!(bv8.count_zeros(), 3);
1954        for (i, &expected) in pattern.iter().enumerate() {
1955            assert_eq!(bv8.get(i as u64), expected);
1956        }
1957
1958        assert_eq!(bv16.len(), 7);
1959        assert_eq!(bv16.count_ones(), 4);
1960        assert_eq!(bv16.count_zeros(), 3);
1961        for (i, &expected) in pattern.iter().enumerate() {
1962            assert_eq!(bv16.get(i as u64), expected);
1963        }
1964    }
1965
1966    #[test]
1967    fn test_prune_chunks() {
1968        let mut bv: BitMap<4> = BitMap::new();
1969        bv.push_chunk(&[1, 2, 3, 4]);
1970        bv.push_chunk(&[5, 6, 7, 8]);
1971        bv.push_chunk(&[9, 10, 11, 12]);
1972
1973        assert_eq!(bv.len(), 96);
1974        assert_eq!(bv.get_chunk(0), &[1, 2, 3, 4]);
1975
1976        // Prune first chunk
1977        bv.prune_chunks(1);
1978        assert_eq!(bv.len(), 64);
1979        assert_eq!(bv.get_chunk(0), &[5, 6, 7, 8]);
1980        assert_eq!(bv.get_chunk(1), &[9, 10, 11, 12]);
1981
1982        // Prune another chunk
1983        bv.prune_chunks(1);
1984        assert_eq!(bv.len(), 32);
1985        assert_eq!(bv.get_chunk(0), &[9, 10, 11, 12]);
1986    }
1987
1988    #[test]
1989    #[should_panic(expected = "cannot prune")]
1990    fn test_prune_too_many_chunks() {
1991        let mut bv: BitMap<4> = BitMap::new();
1992        bv.push_chunk(&[1, 2, 3, 4]);
1993        bv.push_chunk(&[5, 6, 7, 8]);
1994        bv.push(true);
1995
1996        // Try to prune 4 chunks when only 3 are available
1997        bv.prune_chunks(4);
1998    }
1999
2000    #[test]
2001    fn test_prune_with_partial_last_chunk() {
2002        let mut bv: BitMap<4> = BitMap::new();
2003        bv.push_chunk(&[1, 2, 3, 4]);
2004        bv.push_chunk(&[5, 6, 7, 8]);
2005        bv.push(true);
2006        bv.push(false);
2007
2008        assert_eq!(bv.len(), 66);
2009
2010        // Can prune first chunk
2011        bv.prune_chunks(1);
2012        assert_eq!(bv.len(), 34);
2013        assert_eq!(bv.get_chunk(0), &[5, 6, 7, 8]);
2014
2015        // Last partial chunk still has the appended bits
2016        assert!(bv.get(32));
2017        assert!(!bv.get(33));
2018    }
2019
2020    #[test]
2021    fn test_prune_all_chunks_resets_next_bit() {
2022        let mut bv: BitMap<4> = BitMap::new();
2023        bv.push_chunk(&[1, 2, 3, 4]);
2024        bv.push_chunk(&[5, 6, 7, 8]);
2025        bv.push(true);
2026        bv.push(false);
2027        bv.push(true);
2028
2029        // Bitmap has 2 full chunks + 3 bits in partial chunk
2030        assert_eq!(bv.len(), 67);
2031
2032        // Prune all chunks (this leaves chunks empty, triggering the reset path)
2033        bv.prune_chunks(3);
2034
2035        // Regression test: len() should be 0, not the old next_bit value (3)
2036        assert_eq!(bv.len(), 0);
2037        assert!(bv.is_empty());
2038
2039        // Bitmap should behave as freshly created
2040        bv.push(true);
2041        assert_eq!(bv.len(), 1);
2042        assert!(bv.get(0));
2043    }
2044
2045    #[test]
2046    fn test_is_chunk_aligned() {
2047        // Empty bitmap is chunk aligned
2048        let bv: BitMap<4> = BitMap::new();
2049        assert!(bv.is_chunk_aligned());
2050
2051        // Test with various chunk sizes
2052        let mut bv4: BitMap<4> = BitMap::new();
2053        assert!(bv4.is_chunk_aligned());
2054
2055        // Add bits one at a time and check alignment
2056        for i in 1..=32 {
2057            bv4.push(i % 2 == 0);
2058            if i == 32 {
2059                assert!(bv4.is_chunk_aligned()); // Exactly one chunk
2060            } else {
2061                assert!(!bv4.is_chunk_aligned()); // Partial chunk
2062            }
2063        }
2064
2065        // Add more bits
2066        for i in 33..=64 {
2067            bv4.push(i % 2 == 0);
2068            if i == 64 {
2069                assert!(bv4.is_chunk_aligned()); // Exactly two chunks
2070            } else {
2071                assert!(!bv4.is_chunk_aligned()); // Partial chunk
2072            }
2073        }
2074
2075        // Test with push_chunk
2076        let mut bv: BitMap<8> = BitMap::new();
2077        assert!(bv.is_chunk_aligned());
2078        bv.push_chunk(&[0xFF; 8]);
2079        assert!(bv.is_chunk_aligned()); // 64 bits = 1 chunk for N=8
2080        bv.push_chunk(&[0xAA; 8]);
2081        assert!(bv.is_chunk_aligned()); // 128 bits = 2 chunks
2082        bv.push(true);
2083        assert!(!bv.is_chunk_aligned()); // 129 bits = partial chunk
2084
2085        // Test with push_byte
2086        let mut bv: BitMap<4> = BitMap::new();
2087        for _ in 0..4 {
2088            bv.push_byte(0xFF);
2089        }
2090        assert!(bv.is_chunk_aligned()); // 32 bits = 1 chunk for N=4
2091
2092        // Test after pop
2093        bv.pop();
2094        assert!(!bv.is_chunk_aligned()); // 31 bits = partial chunk
2095
2096        // Test with zeroes and ones constructors
2097        let bv_zeroes: BitMap<4> = BitMap::zeroes(64);
2098        assert!(bv_zeroes.is_chunk_aligned());
2099
2100        let bv_ones: BitMap<4> = BitMap::ones(96);
2101        assert!(bv_ones.is_chunk_aligned());
2102
2103        let bv_partial: BitMap<4> = BitMap::zeroes(65);
2104        assert!(!bv_partial.is_chunk_aligned());
2105    }
2106
2107    #[test]
2108    fn test_unprune_restores_length() {
2109        let mut prunable: Prunable<4> = Prunable::new_with_pruned_chunks(1).unwrap();
2110        assert_eq!(prunable.len(), Prunable::<4>::CHUNK_SIZE_BITS);
2111        assert_eq!(prunable.pruned_chunks(), 1);
2112        let chunk = [0xDE, 0xAD, 0xBE, 0xEF];
2113
2114        prunable.unprune_chunks(&[chunk]);
2115
2116        assert_eq!(prunable.pruned_chunks(), 0);
2117        assert_eq!(prunable.len(), Prunable::<4>::CHUNK_SIZE_BITS);
2118        assert_eq!(prunable.get_chunk_containing(0), &chunk);
2119    }
2120}
commonware_utils/bitmap/mod.rs

commonware_utils/bitmap/
mod.rs
