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 const 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 const fn len(&self) -> u64 {
114        self.len
115    }
116
117    /// Returns true if the bitmap is empty.
118    #[inline]
119    pub const 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 const 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    const 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) const 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) const 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 const 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: &Self, 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: &Self) {
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: &Self) {
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: &Self) {
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: &Self) {
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::with_capacity(bools.len() as u64);
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 = Self { 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(feature = "arbitrary")]
774impl<const N: usize> arbitrary::Arbitrary<'_> for BitMap<N> {
775    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
776        let size = u.int_in_range(0..=1024)?;
777        let mut bits = Self::with_capacity(size);
778        for _ in 0..size {
779            bits.push(u.arbitrary::<bool>()?);
780        }
781        Ok(bits)
782    }
783}
784
785#[cfg(test)]
786mod tests {
787    use super::*;
788    use crate::hex;
789    use bytes::BytesMut;
790    use commonware_codec::{Decode, Encode};
791
792    #[test]
793    fn test_constructors() {
794        // Test new()
795        let bv: BitMap<4> = BitMap::new();
796        assert_eq!(bv.len(), 0);
797        assert!(bv.is_empty());
798
799        // Test default()
800        let bv: BitMap<4> = Default::default();
801        assert_eq!(bv.len(), 0);
802        assert!(bv.is_empty());
803
804        // Test with_capacity()
805        let bv: BitMap<4> = BitMap::with_capacity(0);
806        assert_eq!(bv.len(), 0);
807        assert!(bv.is_empty());
808
809        let bv: BitMap<4> = BitMap::with_capacity(10);
810        assert_eq!(bv.len(), 0);
811        assert!(bv.is_empty());
812    }
813
814    #[test]
815    fn test_zeroes() {
816        let bv: BitMap<1> = BitMap::zeroes(0);
817        assert_eq!(bv.len(), 0);
818        assert!(bv.is_empty());
819        assert_eq!(bv.count_ones(), 0);
820        assert_eq!(bv.count_zeros(), 0);
821
822        let bv: BitMap<1> = BitMap::zeroes(1);
823        assert_eq!(bv.len(), 1);
824        assert!(!bv.is_empty());
825        assert_eq!(bv.len(), 1);
826        assert!(!bv.get(0));
827        assert_eq!(bv.count_ones(), 0);
828        assert_eq!(bv.count_zeros(), 1);
829
830        let bv: BitMap<1> = BitMap::zeroes(10);
831        assert_eq!(bv.len(), 10);
832        assert!(!bv.is_empty());
833        assert_eq!(bv.len(), 10);
834        for i in 0..10 {
835            assert!(!bv.get(i as u64));
836        }
837        assert_eq!(bv.count_ones(), 0);
838        assert_eq!(bv.count_zeros(), 10);
839    }
840
841    #[test]
842    fn test_ones() {
843        let bv: BitMap<1> = BitMap::ones(0);
844        assert_eq!(bv.len(), 0);
845        assert!(bv.is_empty());
846        assert_eq!(bv.count_ones(), 0);
847        assert_eq!(bv.count_zeros(), 0);
848
849        let bv: BitMap<1> = BitMap::ones(1);
850        assert_eq!(bv.len(), 1);
851        assert!(!bv.is_empty());
852        assert_eq!(bv.len(), 1);
853        assert!(bv.get(0));
854        assert_eq!(bv.count_ones(), 1);
855        assert_eq!(bv.count_zeros(), 0);
856
857        let bv: BitMap<1> = BitMap::ones(10);
858        assert_eq!(bv.len(), 10);
859        assert!(!bv.is_empty());
860        assert_eq!(bv.len(), 10);
861        for i in 0..10 {
862            assert!(bv.get(i as u64));
863        }
864        assert_eq!(bv.count_ones(), 10);
865        assert_eq!(bv.count_zeros(), 0);
866    }
867
868    #[test]
869    fn test_invariant_trailing_bits_are_zero() {
870        // Helper function to check the invariant
871        fn check_trailing_bits_zero<const N: usize>(bitmap: &BitMap<N>) {
872            let (last_chunk, next_bit) = bitmap.last_chunk();
873
874            // Check that all bits >= next_bit in the last chunk are 0
875            for bit_idx in next_bit..((N * 8) as u64) {
876                let byte_idx = (bit_idx / 8) as usize;
877                let bit_in_byte = bit_idx % 8;
878                let mask = 1u8 << bit_in_byte;
879                assert_eq!(last_chunk[byte_idx] & mask, 0);
880            }
881        }
882
883        // Test ones() constructor
884        let bv: BitMap<4> = BitMap::ones(15);
885        check_trailing_bits_zero(&bv);
886
887        let bv: BitMap<4> = BitMap::ones(33);
888        check_trailing_bits_zero(&bv);
889
890        // Test after push operations
891        let mut bv: BitMap<4> = BitMap::new();
892        for i in 0..37 {
893            bv.push(i % 2 == 0);
894            check_trailing_bits_zero(&bv);
895        }
896
897        // Test after pop operations
898        let mut bv: BitMap<4> = BitMap::ones(40);
899        check_trailing_bits_zero(&bv);
900        for _ in 0..15 {
901            bv.pop();
902            check_trailing_bits_zero(&bv);
903        }
904
905        // Test after flip_all
906        let mut bv: BitMap<4> = BitMap::ones(25);
907        bv.flip_all();
908        check_trailing_bits_zero(&bv);
909
910        // Test after binary operations
911        let bv1: BitMap<4> = BitMap::ones(20);
912        let bv2: BitMap<4> = BitMap::zeroes(20);
913
914        let mut bv_and = bv1.clone();
915        bv_and.and(&bv2);
916        check_trailing_bits_zero(&bv_and);
917
918        let mut bv_or = bv1.clone();
919        bv_or.or(&bv2);
920        check_trailing_bits_zero(&bv_or);
921
922        let mut bv_xor = bv1;
923        bv_xor.xor(&bv2);
924        check_trailing_bits_zero(&bv_xor);
925
926        // Test after deserialization
927        let original: BitMap<4> = BitMap::ones(27);
928        let encoded = original.encode();
929        let decoded: BitMap<4> =
930            BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
931        check_trailing_bits_zero(&decoded);
932
933        // Test clear_trailing_bits return value
934        let mut bv_clean: BitMap<4> = BitMap::ones(20);
935        // Should return false since ones() already clears trailing bits
936        assert!(!bv_clean.clear_trailing_bits());
937
938        // Create a bitmap with invalid trailing bits by manually setting them
939        let mut bv_dirty: BitMap<4> = BitMap::ones(20);
940        // Manually corrupt the last chunk to have trailing bits set
941        let last_chunk = bv_dirty.chunks.back_mut().unwrap();
942        last_chunk[3] |= 0xF0; // Set some high bits in the last byte
943                               // Should return true since we had invalid trailing bits
944        assert!(bv_dirty.clear_trailing_bits());
945        // After clearing, should return false
946        assert!(!bv_dirty.clear_trailing_bits());
947        check_trailing_bits_zero(&bv_dirty);
948    }
949
950    #[test]
951    fn test_get_set() {
952        let mut bv: BitMap<4> = BitMap::new();
953
954        // Test initial state
955        assert_eq!(bv.len(), 0);
956        assert!(bv.is_empty());
957
958        // Test push
959        bv.push(true);
960        bv.push(false);
961        bv.push(true);
962        assert_eq!(bv.len(), 3);
963        assert!(!bv.is_empty());
964
965        // Test get
966        assert!(bv.get(0));
967        assert!(!bv.get(1));
968        assert!(bv.get(2));
969
970        bv.set(1, true);
971        assert!(bv.get(1));
972        bv.set(2, false);
973        assert!(!bv.get(2));
974
975        // Test flip
976        bv.flip(0); // true -> false
977        assert!(!bv.get(0));
978        bv.flip(0); // false -> true
979        assert!(bv.get(0));
980    }
981
982    #[test]
983    fn test_chunk_operations() {
984        let mut bv: BitMap<4> = BitMap::new();
985        let test_chunk = hex!("0xABCDEF12");
986
987        // Test push_chunk
988        bv.push_chunk(&test_chunk);
989        assert_eq!(bv.len(), 32); // 4 bytes * 8 bits
990
991        // Test get_chunk
992        let chunk = bv.get_chunk(0);
993        assert_eq!(chunk, &test_chunk);
994
995        // Test get_chunk_containing
996        let chunk = bv.get_chunk_containing(0);
997        assert_eq!(chunk, &test_chunk);
998
999        // Test last_chunk
1000        let (last_chunk, next_bit) = bv.last_chunk();
1001        assert_eq!(next_bit, BitMap::<4>::CHUNK_SIZE_BITS); // Should be at chunk boundary
1002        assert_eq!(last_chunk, &test_chunk); // The chunk we just pushed
1003    }
1004
1005    #[test]
1006    fn test_pop() {
1007        let mut bv: BitMap<3> = BitMap::new();
1008        bv.push(true);
1009        assert!(bv.pop());
1010        assert_eq!(bv.len(), 0);
1011
1012        bv.push(false);
1013        assert!(!bv.pop());
1014        assert_eq!(bv.len(), 0);
1015
1016        bv.push(true);
1017        bv.push(false);
1018        bv.push(true);
1019        assert!(bv.pop());
1020        assert_eq!(bv.len(), 2);
1021        assert!(!bv.pop());
1022        assert_eq!(bv.len(), 1);
1023        assert!(bv.pop());
1024        assert_eq!(bv.len(), 0);
1025
1026        for i in 0..100 {
1027            bv.push(i % 2 == 0);
1028        }
1029        assert_eq!(bv.len(), 100);
1030        for i in (0..100).rev() {
1031            assert_eq!(bv.pop(), i % 2 == 0);
1032        }
1033        assert_eq!(bv.len(), 0);
1034        assert!(bv.is_empty());
1035    }
1036
1037    #[test]
1038    fn test_pop_chunk() {
1039        let mut bv: BitMap<3> = BitMap::new();
1040        const CHUNK_SIZE: u64 = BitMap::<3>::CHUNK_SIZE_BITS;
1041
1042        // Test 1: Pop a single chunk and verify it returns the correct data
1043        let chunk1 = hex!("0xAABBCC");
1044        bv.push_chunk(&chunk1);
1045        assert_eq!(bv.len(), CHUNK_SIZE);
1046        let popped = bv.pop_chunk();
1047        assert_eq!(popped, chunk1);
1048        assert_eq!(bv.len(), 0);
1049        assert!(bv.is_empty());
1050
1051        // Test 2: Pop multiple chunks in reverse order
1052        let chunk2 = hex!("0x112233");
1053        let chunk3 = hex!("0x445566");
1054        let chunk4 = hex!("0x778899");
1055
1056        bv.push_chunk(&chunk2);
1057        bv.push_chunk(&chunk3);
1058        bv.push_chunk(&chunk4);
1059        assert_eq!(bv.len(), CHUNK_SIZE * 3);
1060
1061        assert_eq!(bv.pop_chunk(), chunk4);
1062        assert_eq!(bv.len(), CHUNK_SIZE * 2);
1063
1064        assert_eq!(bv.pop_chunk(), chunk3);
1065        assert_eq!(bv.len(), CHUNK_SIZE);
1066
1067        assert_eq!(bv.pop_chunk(), chunk2);
1068        assert_eq!(bv.len(), 0);
1069
1070        // Test 3: Verify data integrity when popping chunks
1071        let first_chunk = hex!("0xAABBCC");
1072        let second_chunk = hex!("0x112233");
1073        bv.push_chunk(&first_chunk);
1074        bv.push_chunk(&second_chunk);
1075
1076        // Pop the second chunk, verify it and that first chunk is intact
1077        assert_eq!(bv.pop_chunk(), second_chunk);
1078        assert_eq!(bv.len(), CHUNK_SIZE);
1079
1080        for i in 0..CHUNK_SIZE {
1081            let byte_idx = (i / 8) as usize;
1082            let bit_idx = i % 8;
1083            let expected = (first_chunk[byte_idx] >> bit_idx) & 1 == 1;
1084            assert_eq!(bv.get(i), expected);
1085        }
1086
1087        assert_eq!(bv.pop_chunk(), first_chunk);
1088        assert_eq!(bv.len(), 0);
1089    }
1090
1091    #[test]
1092    #[should_panic(expected = "cannot pop chunk when not chunk aligned")]
1093    fn test_pop_chunk_not_aligned() {
1094        let mut bv: BitMap<3> = BitMap::new();
1095
1096        // Push a full chunk plus one bit
1097        bv.push_chunk(&[0xFF; 3]);
1098        bv.push(true);
1099
1100        // Should panic because not chunk-aligned
1101        bv.pop_chunk();
1102    }
1103
1104    #[test]
1105    #[should_panic(expected = "cannot pop chunk: bitmap has fewer than CHUNK_SIZE_BITS bits")]
1106    fn test_pop_chunk_insufficient_bits() {
1107        let mut bv: BitMap<3> = BitMap::new();
1108
1109        // Push only a few bits (less than a full chunk)
1110        bv.push(true);
1111        bv.push(false);
1112
1113        // Should panic because we don't have a full chunk to pop
1114        bv.pop_chunk();
1115    }
1116
1117    #[test]
1118    fn test_byte_operations() {
1119        let mut bv: BitMap<4> = BitMap::new();
1120
1121        // Test push_byte
1122        bv.push_byte(0xFF);
1123        assert_eq!(bv.len(), 8);
1124
1125        // All bits in the byte should be set
1126        for i in 0..8 {
1127            assert!(bv.get(i as u64));
1128        }
1129
1130        bv.push_byte(0x00);
1131        assert_eq!(bv.len(), 16);
1132
1133        // All bits in the second byte should be clear
1134        for i in 8..16 {
1135            assert!(!bv.get(i as u64));
1136        }
1137    }
1138
1139    #[test]
1140    fn test_count_operations() {
1141        let mut bv: BitMap<4> = BitMap::new();
1142
1143        // Empty bitmap
1144        assert_eq!(bv.count_ones(), 0);
1145        assert_eq!(bv.count_zeros(), 0);
1146
1147        // Add some bits
1148        bv.push(true);
1149        bv.push(false);
1150        bv.push(true);
1151        bv.push(true);
1152        bv.push(false);
1153
1154        assert_eq!(bv.count_ones(), 3);
1155        assert_eq!(bv.count_zeros(), 2);
1156        assert_eq!(bv.len(), 5);
1157
1158        // Test with full bytes
1159        let mut bv2: BitMap<4> = BitMap::new();
1160        bv2.push_byte(0xFF); // 8 ones
1161        bv2.push_byte(0x00); // 8 zeros
1162        bv2.push_byte(0xAA); // 4 ones, 4 zeros (10101010)
1163
1164        assert_eq!(bv2.count_ones(), 12);
1165        assert_eq!(bv2.count_zeros(), 12);
1166        assert_eq!(bv2.len(), 24);
1167    }
1168
1169    #[test]
1170    fn test_set_all() {
1171        let mut bv: BitMap<1> = BitMap::new();
1172
1173        // Add some bits
1174        bv.push(true);
1175        bv.push(false);
1176        bv.push(true);
1177        bv.push(false);
1178        bv.push(true);
1179        bv.push(false);
1180        bv.push(true);
1181        bv.push(false);
1182        bv.push(true);
1183        bv.push(false);
1184
1185        assert_eq!(bv.len(), 10);
1186        assert_eq!(bv.count_ones(), 5);
1187        assert_eq!(bv.count_zeros(), 5);
1188
1189        // Test set_all(true)
1190        bv.set_all(true);
1191        assert_eq!(bv.len(), 10);
1192        assert_eq!(bv.count_ones(), 10);
1193        assert_eq!(bv.count_zeros(), 0);
1194
1195        // Test set_all(false)
1196        bv.set_all(false);
1197        assert_eq!(bv.len(), 10);
1198        assert_eq!(bv.count_ones(), 0);
1199        assert_eq!(bv.count_zeros(), 10);
1200    }
1201
1202    #[test]
1203    fn test_flip_all() {
1204        let mut bv: BitMap<4> = BitMap::new();
1205
1206        bv.push(true);
1207        bv.push(false);
1208        bv.push(true);
1209        bv.push(false);
1210        bv.push(true);
1211
1212        let original_ones = bv.count_ones();
1213        let original_zeros = bv.count_zeros();
1214        let original_len = bv.len();
1215
1216        bv.flip_all();
1217
1218        // Length should not change
1219        assert_eq!(bv.len(), original_len);
1220
1221        // Ones and zeros should be swapped
1222        assert_eq!(bv.count_ones(), original_zeros);
1223        assert_eq!(bv.count_zeros(), original_ones);
1224
1225        // Check bits
1226        assert!(!bv.get(0));
1227        assert!(bv.get(1));
1228        assert!(!bv.get(2));
1229        assert!(bv.get(3));
1230        assert!(!bv.get(4));
1231    }
1232
1233    #[test]
1234    fn test_bitwise_and() {
1235        let mut bv1: BitMap<4> = BitMap::new();
1236        let mut bv2: BitMap<4> = BitMap::new();
1237
1238        // Create test patterns: 10110 & 11010 = 10010
1239        let pattern1 = [true, false, true, true, false];
1240        let pattern2 = [true, true, false, true, false];
1241        let expected = [true, false, false, true, false];
1242
1243        for &bit in &pattern1 {
1244            bv1.push(bit);
1245        }
1246        for &bit in &pattern2 {
1247            bv2.push(bit);
1248        }
1249
1250        bv1.and(&bv2);
1251
1252        assert_eq!(bv1.len(), 5);
1253        for (i, &expected_bit) in expected.iter().enumerate() {
1254            assert_eq!(bv1.get(i as u64), expected_bit);
1255        }
1256    }
1257
1258    #[test]
1259    fn test_bitwise_or() {
1260        let mut bv1: BitMap<4> = BitMap::new();
1261        let mut bv2: BitMap<4> = BitMap::new();
1262
1263        // Create test patterns: 10110 | 11010 = 11110
1264        let pattern1 = [true, false, true, true, false];
1265        let pattern2 = [true, true, false, true, false];
1266        let expected = [true, true, true, true, false];
1267
1268        for &bit in &pattern1 {
1269            bv1.push(bit);
1270        }
1271        for &bit in &pattern2 {
1272            bv2.push(bit);
1273        }
1274
1275        bv1.or(&bv2);
1276
1277        assert_eq!(bv1.len(), 5);
1278        for (i, &expected_bit) in expected.iter().enumerate() {
1279            assert_eq!(bv1.get(i as u64), expected_bit);
1280        }
1281    }
1282
1283    #[test]
1284    fn test_bitwise_xor() {
1285        let mut bv1: BitMap<4> = BitMap::new();
1286        let mut bv2: BitMap<4> = BitMap::new();
1287
1288        // Create test patterns: 10110 ^ 11010 = 01100
1289        let pattern1 = [true, false, true, true, false];
1290        let pattern2 = [true, true, false, true, false];
1291        let expected = [false, true, true, false, false];
1292
1293        for &bit in &pattern1 {
1294            bv1.push(bit);
1295        }
1296        for &bit in &pattern2 {
1297            bv2.push(bit);
1298        }
1299
1300        bv1.xor(&bv2);
1301
1302        assert_eq!(bv1.len(), 5);
1303        for (i, &expected_bit) in expected.iter().enumerate() {
1304            assert_eq!(bv1.get(i as u64), expected_bit);
1305        }
1306    }
1307
1308    #[test]
1309    fn test_multi_chunk_operations() {
1310        let mut bv1: BitMap<4> = BitMap::new();
1311        let mut bv2: BitMap<4> = BitMap::new();
1312
1313        // Fill multiple chunks
1314        let chunk1 = hex!("0xAABBCCDD"); // 10101010 10111011 11001100 11011101
1315        let chunk2 = hex!("0x55667788"); // 01010101 01100110 01110111 10001000
1316
1317        bv1.push_chunk(&chunk1);
1318        bv1.push_chunk(&chunk1);
1319        bv2.push_chunk(&chunk2);
1320        bv2.push_chunk(&chunk2);
1321
1322        assert_eq!(bv1.len(), 64);
1323        assert_eq!(bv2.len(), 64);
1324
1325        // Test AND operation
1326        let mut bv_and = bv1.clone();
1327        bv_and.and(&bv2);
1328
1329        // Test OR operation
1330        let mut bv_or = bv1.clone();
1331        bv_or.or(&bv2);
1332
1333        // Test XOR operation
1334        let mut bv_xor = bv1.clone();
1335        bv_xor.xor(&bv2);
1336
1337        // Verify results make sense
1338        assert_eq!(bv_and.len(), 64);
1339        assert_eq!(bv_or.len(), 64);
1340        assert_eq!(bv_xor.len(), 64);
1341
1342        // AND should have fewer or equal ones than either operand
1343        assert!(bv_and.count_ones() <= bv1.count_ones());
1344        assert!(bv_and.count_ones() <= bv2.count_ones());
1345
1346        // OR should have more or equal ones than either operand
1347        assert!(bv_or.count_ones() >= bv1.count_ones());
1348        assert!(bv_or.count_ones() >= bv2.count_ones());
1349    }
1350
1351    #[test]
1352    fn test_partial_chunk_operations() {
1353        let mut bv1: BitMap<4> = BitMap::new();
1354        let mut bv2: BitMap<4> = BitMap::new();
1355
1356        // Add partial chunks (not aligned to chunk boundaries)
1357        for i in 0..35 {
1358            // 35 bits = 4 bytes + 3 bits
1359            bv1.push(i % 2 == 0);
1360            bv2.push(i % 3 == 0);
1361        }
1362
1363        assert_eq!(bv1.len(), 35);
1364        assert_eq!(bv2.len(), 35);
1365
1366        // Test operations with partial chunks
1367        let mut bv_and = bv1.clone();
1368        bv_and.and(&bv2);
1369
1370        let mut bv_or = bv1.clone();
1371        bv_or.or(&bv2);
1372
1373        let mut bv_xor = bv1.clone();
1374        bv_xor.xor(&bv2);
1375
1376        // All should maintain the same length
1377        assert_eq!(bv_and.len(), 35);
1378        assert_eq!(bv_or.len(), 35);
1379        assert_eq!(bv_xor.len(), 35);
1380
1381        // Test flip_all with partial chunk
1382        let mut bv_inv = bv1.clone();
1383        let original_ones = bv_inv.count_ones();
1384        let original_zeros = bv_inv.count_zeros();
1385        bv_inv.flip_all();
1386        assert_eq!(bv_inv.count_ones(), original_zeros);
1387        assert_eq!(bv_inv.count_zeros(), original_ones);
1388    }
1389
1390    #[test]
1391    #[should_panic(expected = "bit 1 out of bounds (len: 1)")]
1392    fn test_flip_out_of_bounds() {
1393        let mut bv: BitMap<4> = BitMap::new();
1394        bv.push(true);
1395        bv.flip(1); // Only bit 0 exists
1396    }
1397
1398    #[test]
1399    #[should_panic(expected = "BitMap lengths don't match: 2 vs 1")]
1400    fn test_and_length_mismatch() {
1401        let mut bv1: BitMap<4> = BitMap::new();
1402        let mut bv2: BitMap<4> = BitMap::new();
1403
1404        bv1.push(true);
1405        bv1.push(false);
1406        bv2.push(true); // Different length
1407
1408        bv1.and(&bv2);
1409    }
1410
1411    #[test]
1412    #[should_panic(expected = "BitMap lengths don't match: 1 vs 2")]
1413    fn test_or_length_mismatch() {
1414        let mut bv1: BitMap<4> = BitMap::new();
1415        let mut bv2: BitMap<4> = BitMap::new();
1416
1417        bv1.push(true);
1418        bv2.push(true);
1419        bv2.push(false); // Different length
1420
1421        bv1.or(&bv2);
1422    }
1423
1424    #[test]
1425    #[should_panic(expected = "BitMap lengths don't match: 3 vs 2")]
1426    fn test_xor_length_mismatch() {
1427        let mut bv1: BitMap<4> = BitMap::new();
1428        let mut bv2: BitMap<4> = BitMap::new();
1429
1430        bv1.push(true);
1431        bv1.push(false);
1432        bv1.push(true);
1433        bv2.push(true);
1434        bv2.push(false); // Different length
1435
1436        bv1.xor(&bv2);
1437    }
1438
1439    #[test]
1440    fn test_equality() {
1441        // Test empty bitmaps
1442        assert_eq!(BitMap::<4>::new(), BitMap::<4>::new());
1443        assert_eq!(BitMap::<8>::new(), BitMap::<8>::new());
1444
1445        // Test non-empty bitmaps from constructors
1446        let pattern = [true, false, true, true, false, false, true, false, true];
1447        let bv4: BitMap<4> = pattern.as_ref().into();
1448        assert_eq!(bv4, BitMap::<4>::from(pattern.as_ref()));
1449        let bv8: BitMap<8> = pattern.as_ref().into();
1450        assert_eq!(bv8, BitMap::<8>::from(pattern.as_ref()));
1451
1452        // Test non-empty bitmaps from push operations
1453        let mut bv1: BitMap<4> = BitMap::new();
1454        let mut bv2: BitMap<4> = BitMap::new();
1455        for i in 0..33 {
1456            let bit = i % 3 == 0;
1457            bv1.push(bit);
1458            bv2.push(bit);
1459        }
1460        assert_eq!(bv1, bv2);
1461
1462        // Test inequality: different lengths
1463        bv1.push(true);
1464        assert_ne!(bv1, bv2);
1465        bv1.pop(); // Restore equality
1466        assert_eq!(bv1, bv2);
1467
1468        // Test inequality: different content
1469        bv1.flip(15);
1470        assert_ne!(bv1, bv2);
1471        bv1.flip(15); // Restore equality
1472        assert_eq!(bv1, bv2);
1473
1474        // Test equality after operations
1475        let mut bv_ops1 = BitMap::<16>::ones(25);
1476        let mut bv_ops2 = BitMap::<16>::ones(25);
1477        bv_ops1.flip_all();
1478        bv_ops2.flip_all();
1479        assert_eq!(bv_ops1, bv_ops2);
1480
1481        let mask_bits: Vec<bool> = (0..33).map(|i| i % 3 == 0).collect();
1482        let mask = BitMap::<4>::from(mask_bits);
1483        bv1.and(&mask);
1484        bv2.and(&mask);
1485        assert_eq!(bv1, bv2);
1486    }
1487
1488    #[test]
1489    fn test_different_chunk_sizes() {
1490        // Test with different chunk sizes
1491        let mut bv8: BitMap<8> = BitMap::new();
1492        let mut bv16: BitMap<16> = BitMap::new();
1493        let mut bv32: BitMap<32> = BitMap::new();
1494
1495        // Test chunk operations first (must be chunk-aligned)
1496        let chunk8 = [0xFF; 8];
1497        let chunk16 = [0xAA; 16];
1498        let chunk32 = [0x55; 32];
1499
1500        bv8.push_chunk(&chunk8);
1501        bv16.push_chunk(&chunk16);
1502        bv32.push_chunk(&chunk32);
1503
1504        // Test basic operations work with different sizes
1505        bv8.push(true);
1506        bv8.push(false);
1507        assert_eq!(bv8.len(), 64 + 2);
1508        assert_eq!(bv8.count_ones(), 64 + 1); // chunk8 is all 0xFF + 1 true bit
1509        assert_eq!(bv8.count_zeros(), 1);
1510
1511        bv16.push(true);
1512        bv16.push(false);
1513        assert_eq!(bv16.len(), 128 + 2);
1514        assert_eq!(bv16.count_ones(), 64 + 1); // chunk16 is 0xAA pattern + 1 true bit
1515        assert_eq!(bv16.count_zeros(), 64 + 1);
1516
1517        bv32.push(true);
1518        bv32.push(false);
1519        assert_eq!(bv32.len(), 256 + 2);
1520        assert_eq!(bv32.count_ones(), 128 + 1); // chunk32 is 0x55 pattern + 1 true bit
1521        assert_eq!(bv32.count_zeros(), 128 + 1);
1522    }
1523
1524    #[test]
1525    fn test_iterator() {
1526        // Test empty iterator
1527        let bv: BitMap<4> = BitMap::new();
1528        let mut iter = bv.iter();
1529        assert_eq!(iter.next(), None);
1530        assert_eq!(iter.size_hint(), (0, Some(0)));
1531
1532        // Test iterator with some bits
1533        let pattern = [true, false, true, false, true];
1534        let bv: BitMap<4> = pattern.as_ref().into();
1535
1536        // Collect all bits via iterator
1537        let collected: Vec<bool> = bv.iter().collect();
1538        assert_eq!(collected, pattern);
1539
1540        // Test size_hint
1541        let mut iter = bv.iter();
1542        assert_eq!(iter.size_hint(), (5, Some(5)));
1543
1544        // Consume one element and check size_hint again
1545        assert_eq!(iter.next(), Some(true));
1546        assert_eq!(iter.size_hint(), (4, Some(4)));
1547
1548        // Test ExactSizeIterator
1549        let iter = bv.iter();
1550        assert_eq!(iter.len(), 5);
1551
1552        // Test iterator with larger bitmap
1553        let mut large_bv: BitMap<8> = BitMap::new();
1554        for i in 0..100 {
1555            large_bv.push(i % 3 == 0);
1556        }
1557
1558        let collected: Vec<bool> = large_bv.iter().collect();
1559        assert_eq!(collected.len(), 100);
1560        for (i, &bit) in collected.iter().enumerate() {
1561            assert_eq!(bit, i % 3 == 0);
1562        }
1563    }
1564
1565    #[test]
1566    fn test_iterator_edge_cases() {
1567        // Test iterator with single bit
1568        let mut bv: BitMap<4> = BitMap::new();
1569        bv.push(true);
1570
1571        let collected: Vec<bool> = bv.iter().collect();
1572        assert_eq!(collected, vec![true]);
1573
1574        // Test iterator across chunk boundaries
1575        let mut bv: BitMap<4> = BitMap::new();
1576        // Fill exactly one chunk (32 bits)
1577        for i in 0..32 {
1578            bv.push(i % 2 == 0);
1579        }
1580        // Add a few more bits in the next chunk
1581        bv.push(true);
1582        bv.push(false);
1583        bv.push(true);
1584
1585        let collected: Vec<bool> = bv.iter().collect();
1586        assert_eq!(collected.len(), 35);
1587
1588        // Verify the pattern
1589        for (i, &bit) in collected.iter().enumerate().take(32) {
1590            assert_eq!(bit, i % 2 == 0);
1591        }
1592        assert!(collected[32]);
1593        assert!(!collected[33]);
1594        assert!(collected[34]);
1595    }
1596
1597    #[test]
1598    fn test_codec_roundtrip() {
1599        // Test empty bitmap
1600        let original: BitMap<4> = BitMap::new();
1601        let encoded = original.encode();
1602        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1603        assert_eq!(original, decoded);
1604
1605        // Test small bitmap
1606        let pattern = [true, false, true, false, true];
1607        let original: BitMap<4> = pattern.as_ref().into();
1608        let encoded = original.encode();
1609        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1610        assert_eq!(original, decoded);
1611
1612        // Verify the decoded bitmap has the same bits
1613        for (i, &expected) in pattern.iter().enumerate() {
1614            assert_eq!(decoded.get(i as u64), expected);
1615        }
1616
1617        // Test larger bitmap across multiple chunks
1618        let mut large_original: BitMap<8> = BitMap::new();
1619        for i in 0..100 {
1620            large_original.push(i % 7 == 0);
1621        }
1622
1623        let encoded = large_original.encode();
1624        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1625        assert_eq!(large_original, decoded);
1626
1627        // Verify all bits match
1628        assert_eq!(decoded.len(), 100);
1629        for i in 0..100 {
1630            assert_eq!(decoded.get(i as u64), i % 7 == 0);
1631        }
1632    }
1633
1634    #[test]
1635    fn test_codec_different_chunk_sizes() {
1636        let pattern = [true, false, true, true, false, false, true];
1637
1638        // Test with different chunk sizes
1639        let bv4: BitMap<4> = pattern.as_ref().into();
1640        let bv8: BitMap<8> = pattern.as_ref().into();
1641        let bv16: BitMap<16> = pattern.as_ref().into();
1642
1643        // Encode and decode each
1644        let encoded4 = bv4.encode();
1645        let decoded4 = BitMap::decode_cfg(&mut encoded4.as_ref(), &(usize::MAX as u64)).unwrap();
1646        assert_eq!(bv4, decoded4);
1647
1648        let encoded8 = bv8.encode();
1649        let decoded8 = BitMap::decode_cfg(&mut encoded8.as_ref(), &(usize::MAX as u64)).unwrap();
1650        assert_eq!(bv8, decoded8);
1651
1652        let encoded16 = bv16.encode();
1653        let decoded16 = BitMap::decode_cfg(&mut encoded16.as_ref(), &(usize::MAX as u64)).unwrap();
1654        assert_eq!(bv16, decoded16);
1655
1656        // All should have the same logical content
1657        for (i, &expected) in pattern.iter().enumerate() {
1658            let i = i as u64;
1659            assert_eq!(decoded4.get(i), expected);
1660            assert_eq!(decoded8.get(i), expected);
1661            assert_eq!(decoded16.get(i), expected);
1662        }
1663    }
1664
1665    #[test]
1666    fn test_codec_edge_cases() {
1667        // Test bitmap with exactly one chunk filled
1668        let mut bv: BitMap<4> = BitMap::new();
1669        for i in 0..32 {
1670            bv.push(i % 2 == 0);
1671        }
1672
1673        let encoded = bv.encode();
1674        let decoded = BitMap::decode_cfg(&mut encoded.as_ref(), &(usize::MAX as u64)).unwrap();
1675        assert_eq!(bv, decoded);
1676        assert_eq!(decoded.len(), 32);
1677
1678        // Test bitmap with partial chunk
1679        let mut bv2: BitMap<4> = BitMap::new();
1680        for i in 0..35 {
1681            // 32 + 3 bits
1682            bv2.push(i % 3 == 0);
1683        }
1684
1685        let encoded2 = bv2.encode();
1686        let decoded2 = BitMap::decode_cfg(&mut encoded2.as_ref(), &(usize::MAX as u64)).unwrap();
1687        assert_eq!(bv2, decoded2);
1688        assert_eq!(decoded2.len(), 35);
1689    }
1690
1691    #[test]
1692    fn test_encode_size() {
1693        // Test encode size calculation
1694        let bv: BitMap<4> = BitMap::new();
1695        let encoded = bv.encode();
1696        assert_eq!(bv.encode_size(), encoded.len());
1697
1698        // Test with some data
1699        let pattern = [true, false, true, false, true];
1700        let bv: BitMap<4> = pattern.as_ref().into();
1701        let encoded = bv.encode();
1702        assert_eq!(bv.encode_size(), encoded.len());
1703
1704        // Test with larger data
1705        let mut large_bv: BitMap<8> = BitMap::new();
1706        for i in 0..100 {
1707            large_bv.push(i % 2 == 0);
1708        }
1709        let encoded = large_bv.encode();
1710        assert_eq!(large_bv.encode_size(), encoded.len());
1711    }
1712
1713    #[test]
1714    fn test_codec_empty_chunk_optimization() {
1715        // Test that empty last chunks are not serialized
1716
1717        // Case 1: Empty bitmap (omits the only empty chunk)
1718        let bv_empty: BitMap<4> = BitMap::new();
1719        let encoded_empty = bv_empty.encode();
1720        let decoded_empty: BitMap<4> =
1721            BitMap::decode_cfg(&mut encoded_empty.as_ref(), &(usize::MAX as u64)).unwrap();
1722        assert_eq!(bv_empty, decoded_empty);
1723        assert_eq!(bv_empty.len(), decoded_empty.len());
1724        // Should only encode the length, no chunks
1725        assert_eq!(encoded_empty.len(), bv_empty.len().encode_size());
1726
1727        // Case 2: Bitmap ending exactly at chunk boundary (omits empty last chunk)
1728        let mut bv_exact: BitMap<4> = BitMap::new();
1729        for _ in 0..32 {
1730            bv_exact.push(true);
1731        }
1732        let encoded_exact = bv_exact.encode();
1733        let decoded_exact: BitMap<4> =
1734            BitMap::decode_cfg(&mut encoded_exact.as_ref(), &(usize::MAX as u64)).unwrap();
1735        assert_eq!(bv_exact, decoded_exact);
1736
1737        // Case 3: Bitmap with partial last chunk (includes last chunk)
1738        let mut bv_partial: BitMap<4> = BitMap::new();
1739        for _ in 0..35 {
1740            bv_partial.push(true);
1741        }
1742        let encoded_partial = bv_partial.encode();
1743        let decoded_partial: BitMap<4> =
1744            BitMap::decode_cfg(&mut encoded_partial.as_ref(), &(usize::MAX as u64)).unwrap();
1745        assert_eq!(bv_partial, decoded_partial);
1746        assert_eq!(bv_partial.len(), decoded_partial.len());
1747
1748        // Verify optimization works correctly
1749        assert!(encoded_exact.len() < encoded_partial.len());
1750        assert_eq!(encoded_exact.len(), bv_exact.len().encode_size() + 4); // length + 1 chunk
1751        assert_eq!(encoded_partial.len(), bv_partial.len().encode_size() + 8); // length + 2 chunks
1752    }
1753
1754    #[test]
1755    fn test_codec_error_cases() {
1756        // Test invalid length with range check
1757        let mut buf = BytesMut::new();
1758        100u64.write(&mut buf); // bits length
1759
1760        // 100 bits requires 4 chunks (3 full + partially filled)
1761        for _ in 0..4 {
1762            [0u8; 4].write(&mut buf);
1763        }
1764
1765        // Test with a restricted range that excludes 100
1766        let result = BitMap::<4>::decode_cfg(&mut buf, &99);
1767        assert!(matches!(result, Err(CodecError::InvalidLength(100))));
1768
1769        // Test truncated buffer (not enough chunks)
1770        let mut buf = BytesMut::new();
1771        100u64.write(&mut buf); // bits length requiring 4 chunks (3 full + partially filled)
1772                                // Only write 3 chunks
1773        [0u8; 4].write(&mut buf);
1774        [0u8; 4].write(&mut buf);
1775        [0u8; 4].write(&mut buf);
1776
1777        let result = BitMap::<4>::decode_cfg(&mut buf, &(usize::MAX as u64));
1778        // Should fail when trying to read missing chunks
1779        assert!(result.is_err());
1780
1781        // Test invalid trailing bits
1782
1783        // Create a valid bitmap and encode it
1784        let original: BitMap<4> = BitMap::ones(20);
1785        let mut buf = BytesMut::new();
1786        original.write(&mut buf);
1787
1788        // Manually corrupt the encoded data by setting trailing bits
1789        let corrupted_data = buf.freeze();
1790        let mut corrupted_bytes = corrupted_data.to_vec();
1791
1792        // The last byte should have some trailing bits set to 1
1793        // For 20 bits with 4-byte chunks: 20 bits = 2.5 bytes, so last byte should have 4 valid bits
1794        // Set the high 4 bits of the last byte to 1 (these should be 0)
1795        let last_byte_idx = corrupted_bytes.len() - 1;
1796        corrupted_bytes[last_byte_idx] |= 0xF0;
1797
1798        // Read should fail
1799        let result = BitMap::<4>::read_cfg(&mut corrupted_bytes.as_slice(), &(usize::MAX as u64));
1800        assert!(matches!(
1801            result,
1802            Err(CodecError::Invalid(
1803                "BitMap",
1804                "Invalid trailing bits in encoded data"
1805            ))
1806        ));
1807    }
1808
1809    #[test]
1810    fn test_codec_range_config() {
1811        // Test RangeCfg validation in read_cfg
1812
1813        // Create a bitmap with 100 bits
1814        let mut original: BitMap<4> = BitMap::new();
1815        for i in 0..100 {
1816            original.push(i % 3 == 0);
1817        }
1818
1819        // Write to a buffer
1820        let mut buf = BytesMut::new();
1821        original.write(&mut buf);
1822
1823        // Test with max length < actual size (should fail)
1824        let result = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &50);
1825        assert!(matches!(result, Err(CodecError::InvalidLength(100))));
1826
1827        // Test with max length == actual size (should succeed)
1828        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &100).unwrap();
1829        assert_eq!(decoded.len(), 100);
1830        assert_eq!(decoded, original);
1831
1832        // Test with max length > actual size (should succeed)
1833        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &101).unwrap();
1834        assert_eq!(decoded.len(), 100);
1835        assert_eq!(decoded, original);
1836
1837        // Test empty bitmap
1838        let empty = BitMap::<4>::new();
1839        let mut buf = BytesMut::new();
1840        empty.write(&mut buf);
1841
1842        // Empty bitmap should work with max length 0
1843        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &0).unwrap();
1844        assert_eq!(decoded.len(), 0);
1845        assert!(decoded.is_empty());
1846
1847        // Empty bitmap should work with max length > 0
1848        let decoded = BitMap::<4>::decode_cfg(&mut buf.as_ref(), &1).unwrap();
1849        assert_eq!(decoded.len(), 0);
1850        assert!(decoded.is_empty());
1851    }
1852
1853    #[test]
1854    fn test_from() {
1855        // Test From trait with different input types
1856
1857        // Test with Vec<bool>
1858        let vec_bool = vec![true, false, true, false, true];
1859        let bv: BitMap<4> = vec_bool.into();
1860        assert_eq!(bv.len(), 5);
1861        assert_eq!(bv.count_ones(), 3);
1862        assert_eq!(bv.count_zeros(), 2);
1863        for (i, &expected) in [true, false, true, false, true].iter().enumerate() {
1864            assert_eq!(bv.get(i as u64), expected);
1865        }
1866
1867        // Test with array slice
1868        let array = [false, true, true, false];
1869        let bv: BitMap<4> = (&array).into();
1870        assert_eq!(bv.len(), 4);
1871        assert_eq!(bv.count_ones(), 2);
1872        assert_eq!(bv.count_zeros(), 2);
1873        for (i, &expected) in array.iter().enumerate() {
1874            assert_eq!(bv.get(i as u64), expected);
1875        }
1876
1877        // Test with empty slice
1878        let empty: Vec<bool> = vec![];
1879        let bv: BitMap<4> = empty.into();
1880        assert_eq!(bv.len(), 0);
1881        assert!(bv.is_empty());
1882
1883        // Test with large slice
1884        let large: Vec<bool> = (0..100).map(|i| i % 3 == 0).collect();
1885        let bv: BitMap<8> = large.clone().into();
1886        assert_eq!(bv.len(), 100);
1887        for (i, &expected) in large.iter().enumerate() {
1888            assert_eq!(bv.get(i as u64), expected);
1889        }
1890    }
1891
1892    #[test]
1893    fn test_debug_formatting() {
1894        // Test Debug formatting for different sizes
1895
1896        // Test empty bitmap
1897        let bv: BitMap<4> = BitMap::new();
1898        let debug_str = format!("{bv:?}");
1899        assert_eq!(debug_str, "BitMap[]");
1900
1901        // Test small bitmap (should show all bits)
1902        let bv: BitMap<4> = [true, false, true, false, true].as_ref().into();
1903        let debug_str = format!("{bv:?}");
1904        assert_eq!(debug_str, "BitMap[10101]");
1905
1906        // Test bitmap at the display limit (64 bits)
1907        let pattern: Vec<bool> = (0..64).map(|i| i % 2 == 0).collect();
1908        let bv: BitMap<8> = pattern.into();
1909        let debug_str = format!("{bv:?}");
1910        let expected_pattern = "1010".repeat(16); // 64 bits alternating
1911        assert_eq!(debug_str, format!("BitMap[{expected_pattern}]"));
1912
1913        // Test large bitmap (should show ellipsis)
1914        let large_pattern: Vec<bool> = (0..100).map(|i| i % 2 == 0).collect();
1915        let bv: BitMap<16> = large_pattern.into();
1916        let debug_str = format!("{bv:?}");
1917
1918        // Should show first 32 bits + "..." + last 32 bits
1919        let first_32 = "10".repeat(16); // First 32 bits: 1010...
1920        let last_32 = "10".repeat(16); // Last 32 bits: ...1010
1921        let expected = format!("BitMap[{first_32}...{last_32}]");
1922        assert_eq!(debug_str, expected);
1923
1924        // Test single bit
1925        let bv: BitMap<4> = [true].as_ref().into();
1926        assert_eq!(format!("{bv:?}"), "BitMap[1]");
1927
1928        let bv: BitMap<4> = [false].as_ref().into();
1929        assert_eq!(format!("{bv:?}"), "BitMap[0]");
1930
1931        // Test exactly at boundary (65 bits - should show ellipsis)
1932        let pattern: Vec<bool> = (0..65).map(|i| i == 0 || i == 64).collect(); // First and last bits are true
1933        let bv: BitMap<16> = pattern.into();
1934        let debug_str = format!("{bv:?}");
1935
1936        // Should show first 32 bits (100000...) + "..." + last 32 bits (...000001)
1937        let first_32 = "1".to_string() + &"0".repeat(31);
1938        let last_32 = "0".repeat(31) + "1";
1939        let expected = format!("BitMap[{first_32}...{last_32}]");
1940        assert_eq!(debug_str, expected);
1941    }
1942
1943    #[test]
1944    fn test_from_different_chunk_sizes() {
1945        // Test From trait works with different chunk sizes
1946        let pattern = [true, false, true, true, false, false, true];
1947
1948        let bv4: BitMap<4> = pattern.as_ref().into();
1949        let bv8: BitMap<8> = pattern.as_ref().into();
1950        let bv16: BitMap<16> = pattern.as_ref().into();
1951
1952        // All should have the same content regardless of chunk size
1953        // Test each bitmap separately since they have different types
1954        for bv in [&bv4] {
1955            assert_eq!(bv.len(), 7);
1956            assert_eq!(bv.count_ones(), 4);
1957            assert_eq!(bv.count_zeros(), 3);
1958            for (i, &expected) in pattern.iter().enumerate() {
1959                assert_eq!(bv.get(i as u64), expected);
1960            }
1961        }
1962
1963        assert_eq!(bv8.len(), 7);
1964        assert_eq!(bv8.count_ones(), 4);
1965        assert_eq!(bv8.count_zeros(), 3);
1966        for (i, &expected) in pattern.iter().enumerate() {
1967            assert_eq!(bv8.get(i as u64), expected);
1968        }
1969
1970        assert_eq!(bv16.len(), 7);
1971        assert_eq!(bv16.count_ones(), 4);
1972        assert_eq!(bv16.count_zeros(), 3);
1973        for (i, &expected) in pattern.iter().enumerate() {
1974            assert_eq!(bv16.get(i as u64), expected);
1975        }
1976    }
1977
1978    #[test]
1979    fn test_prune_chunks() {
1980        let mut bv: BitMap<4> = BitMap::new();
1981        bv.push_chunk(&[1, 2, 3, 4]);
1982        bv.push_chunk(&[5, 6, 7, 8]);
1983        bv.push_chunk(&[9, 10, 11, 12]);
1984
1985        assert_eq!(bv.len(), 96);
1986        assert_eq!(bv.get_chunk(0), &[1, 2, 3, 4]);
1987
1988        // Prune first chunk
1989        bv.prune_chunks(1);
1990        assert_eq!(bv.len(), 64);
1991        assert_eq!(bv.get_chunk(0), &[5, 6, 7, 8]);
1992        assert_eq!(bv.get_chunk(1), &[9, 10, 11, 12]);
1993
1994        // Prune another chunk
1995        bv.prune_chunks(1);
1996        assert_eq!(bv.len(), 32);
1997        assert_eq!(bv.get_chunk(0), &[9, 10, 11, 12]);
1998    }
1999
2000    #[test]
2001    #[should_panic(expected = "cannot prune")]
2002    fn test_prune_too_many_chunks() {
2003        let mut bv: BitMap<4> = BitMap::new();
2004        bv.push_chunk(&[1, 2, 3, 4]);
2005        bv.push_chunk(&[5, 6, 7, 8]);
2006        bv.push(true);
2007
2008        // Try to prune 4 chunks when only 3 are available
2009        bv.prune_chunks(4);
2010    }
2011
2012    #[test]
2013    fn test_prune_with_partial_last_chunk() {
2014        let mut bv: BitMap<4> = BitMap::new();
2015        bv.push_chunk(&[1, 2, 3, 4]);
2016        bv.push_chunk(&[5, 6, 7, 8]);
2017        bv.push(true);
2018        bv.push(false);
2019
2020        assert_eq!(bv.len(), 66);
2021
2022        // Can prune first chunk
2023        bv.prune_chunks(1);
2024        assert_eq!(bv.len(), 34);
2025        assert_eq!(bv.get_chunk(0), &[5, 6, 7, 8]);
2026
2027        // Last partial chunk still has the appended bits
2028        assert!(bv.get(32));
2029        assert!(!bv.get(33));
2030    }
2031
2032    #[test]
2033    fn test_prune_all_chunks_resets_next_bit() {
2034        let mut bv: BitMap<4> = BitMap::new();
2035        bv.push_chunk(&[1, 2, 3, 4]);
2036        bv.push_chunk(&[5, 6, 7, 8]);
2037        bv.push(true);
2038        bv.push(false);
2039        bv.push(true);
2040
2041        // Bitmap has 2 full chunks + 3 bits in partial chunk
2042        assert_eq!(bv.len(), 67);
2043
2044        // Prune all chunks (this leaves chunks empty, triggering the reset path)
2045        bv.prune_chunks(3);
2046
2047        // Regression test: len() should be 0, not the old next_bit value (3)
2048        assert_eq!(bv.len(), 0);
2049        assert!(bv.is_empty());
2050
2051        // Bitmap should behave as freshly created
2052        bv.push(true);
2053        assert_eq!(bv.len(), 1);
2054        assert!(bv.get(0));
2055    }
2056
2057    #[test]
2058    fn test_is_chunk_aligned() {
2059        // Empty bitmap is chunk aligned
2060        let bv: BitMap<4> = BitMap::new();
2061        assert!(bv.is_chunk_aligned());
2062
2063        // Test with various chunk sizes
2064        let mut bv4: BitMap<4> = BitMap::new();
2065        assert!(bv4.is_chunk_aligned());
2066
2067        // Add bits one at a time and check alignment
2068        for i in 1..=32 {
2069            bv4.push(i % 2 == 0);
2070            if i == 32 {
2071                assert!(bv4.is_chunk_aligned()); // Exactly one chunk
2072            } else {
2073                assert!(!bv4.is_chunk_aligned()); // Partial chunk
2074            }
2075        }
2076
2077        // Add more bits
2078        for i in 33..=64 {
2079            bv4.push(i % 2 == 0);
2080            if i == 64 {
2081                assert!(bv4.is_chunk_aligned()); // Exactly two chunks
2082            } else {
2083                assert!(!bv4.is_chunk_aligned()); // Partial chunk
2084            }
2085        }
2086
2087        // Test with push_chunk
2088        let mut bv: BitMap<8> = BitMap::new();
2089        assert!(bv.is_chunk_aligned());
2090        bv.push_chunk(&[0xFF; 8]);
2091        assert!(bv.is_chunk_aligned()); // 64 bits = 1 chunk for N=8
2092        bv.push_chunk(&[0xAA; 8]);
2093        assert!(bv.is_chunk_aligned()); // 128 bits = 2 chunks
2094        bv.push(true);
2095        assert!(!bv.is_chunk_aligned()); // 129 bits = partial chunk
2096
2097        // Test with push_byte
2098        let mut bv: BitMap<4> = BitMap::new();
2099        for _ in 0..4 {
2100            bv.push_byte(0xFF);
2101        }
2102        assert!(bv.is_chunk_aligned()); // 32 bits = 1 chunk for N=4
2103
2104        // Test after pop
2105        bv.pop();
2106        assert!(!bv.is_chunk_aligned()); // 31 bits = partial chunk
2107
2108        // Test with zeroes and ones constructors
2109        let bv_zeroes: BitMap<4> = BitMap::zeroes(64);
2110        assert!(bv_zeroes.is_chunk_aligned());
2111
2112        let bv_ones: BitMap<4> = BitMap::ones(96);
2113        assert!(bv_ones.is_chunk_aligned());
2114
2115        let bv_partial: BitMap<4> = BitMap::zeroes(65);
2116        assert!(!bv_partial.is_chunk_aligned());
2117    }
2118
2119    #[test]
2120    fn test_unprune_restores_length() {
2121        let mut prunable: Prunable<4> = Prunable::new_with_pruned_chunks(1).unwrap();
2122        assert_eq!(prunable.len(), Prunable::<4>::CHUNK_SIZE_BITS);
2123        assert_eq!(prunable.pruned_chunks(), 1);
2124        let chunk = [0xDE, 0xAD, 0xBE, 0xEF];
2125
2126        prunable.unprune_chunks(&[chunk]);
2127
2128        assert_eq!(prunable.pruned_chunks(), 0);
2129        assert_eq!(prunable.len(), Prunable::<4>::CHUNK_SIZE_BITS);
2130        assert_eq!(prunable.get_chunk_containing(0), &chunk);
2131    }
2132
2133    #[cfg(feature = "arbitrary")]
2134    mod conformance {
2135        use super::*;
2136        use commonware_codec::conformance::CodecConformance;
2137
2138        commonware_conformance::conformance_tests! {
2139            CodecConformance<BitMap>
2140        }
2141    }
2142}
commonware_utils/bitmap/mod.rs

commonware_utils/bitmap/
mod.rs
