Skip to main content

arrow_buffer/buffer/
boolean.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use crate::bit_chunk_iterator::{BitChunks, UnalignedBitChunk};
6use crate::bit_iterator::{BitIndexIterator, BitIndexU32Iterator, BitIterator, BitSliceIterator};
7use crate::bit_util::read_u64;
8use crate::{
9    BooleanBufferBuilder, Buffer, MutableBuffer, bit_util, buffer_bin_and, buffer_bin_or,
10    buffer_bin_xor,
11};
12
13use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
14
15/// A slice-able [`Buffer`] containing bit-packed booleans
16///
17/// This structure represents a sequence of boolean values packed into a
18/// byte-aligned [`Buffer`]. Both the offset and length are represented in bits.
19///
20/// # Layout
21///
22/// The values are represented as little endian bit-packed values, where the
23/// least significant bit of each byte represents the first boolean value and
24/// then proceeding to the most significant bit.
25///
26/// For example, the 10 bit bitmask `0b0111001101` has length 10, and is
27/// represented using 2 bytes with offset 0 like this:
28///
29/// ```text
30///        ┌─────────────────────────────────┐    ┌─────────────────────────────────┐
31///        │┌───┬───┬───┬───┬───┬───┬───┬───┐│    │┌───┬───┬───┬───┬───┬───┬───┬───┐│
32///        ││ 1 │ 0 │ 1 │ 1 │ 0 │ 0 │ 1 │ 1 ││    ││ 1 │ 0 │ ? │ ? │ ? │ ? │ ? │ ? ││
33///        │└───┴───┴───┴───┴───┴───┴───┴───┘│    │└───┴───┴───┴───┴───┴───┴───┴───┘│
34/// bit    └─────────────────────────────────┘    └─────────────────────────────────┘
35/// offset  0             Byte 0             7    0              Byte 1            7
36///
37///         length = 10 bits, offset = 0
38/// ```
39///
40/// The same bitmask with length 10 and offset 3 would be represented using 2
41/// bytes like this:
42///
43/// ```text
44///       ┌─────────────────────────────────┐    ┌─────────────────────────────────┐
45///       │┌───┬───┬───┬───┬───┬───┬───┬───┐│    │┌───┬───┬───┬───┬───┬───┬───┬───┐│
46///       ││ ? │ ? │ ? │ 1 │ 0 │ 1 │ 1 │ 0 ││    ││ 0 │ 1 │ 1 │ 1 │ 0 │ ? │ ? │ ? ││
47///       │└───┴───┴───┴───┴───┴───┴───┴───┘│    │└───┴───┴───┴───┴───┴───┴───┴───┘│
48/// bit   └─────────────────────────────────┘    └─────────────────────────────────┘
49/// offset 0             Byte 0             7    0              Byte 1            7
50///
51///        length = 10 bits, offset = 3
52/// ```
53///
54/// Note that the bits marked `?` are not logically part of the mask and may
55/// contain either `0` or `1`
56///
57/// # Bitwise Operations
58///
59/// `BooleanBuffer` implements the standard bitwise traits for creating a new
60/// buffer ([`BitAnd`], [`BitOr`], [`BitXor`], [`Not`]) as well as the assign variants
61/// for updating an existing buffer in place when possible ([`BitAndAssign`],
62/// [`BitOrAssign`], [`BitXorAssign`]).
63///
64/// ```
65/// # use arrow_buffer::BooleanBuffer;
66/// let mut left = BooleanBuffer::from(&[true, false, true, true] as &[bool]);
67/// let right = BooleanBuffer::from(&[true, true, false, true] as &[bool]);
68///
69/// // Create a new buffer by applying bitwise AND
70/// let anded = &left & &right;
71/// assert_eq!(anded, BooleanBuffer::from(&[true, false, false, true] as &[bool]));
72///
73/// // Update `left` in place by applying bitwise AND in place
74/// left &= &right;
75/// assert_eq!(left, BooleanBuffer::from(&[true, false, false, true] as &[bool]));
76/// ```
77///
78/// # See Also
79/// * [`BooleanBufferBuilder`] for building [`BooleanBuffer`] instances
80/// * [`NullBuffer`] for representing null values in Arrow arrays
81///
82/// [`NullBuffer`]: crate::NullBuffer
83#[derive(Debug, Clone, Eq)]
84pub struct BooleanBuffer {
85    /// Underlying buffer (byte aligned)
86    buffer: Buffer,
87    /// Offset in bits (not bytes)
88    bit_offset: usize,
89    /// Length in bits (not bytes)
90    bit_len: usize,
91}
92
93impl PartialEq for BooleanBuffer {
94    fn eq(&self, other: &Self) -> bool {
95        if self.bit_len != other.bit_len {
96            return false;
97        }
98
99        let lhs = self.bit_chunks().iter_padded();
100        let rhs = other.bit_chunks().iter_padded();
101        lhs.zip(rhs).all(|(a, b)| a == b)
102    }
103}
104
105impl BooleanBuffer {
106    /// Create a new [`BooleanBuffer`] from a [`Buffer`], `bit_offset` offset and `bit_len` length
107    ///
108    /// # Panics
109    ///
110    /// This method will panic if `buffer` is not large enough
111    pub fn new(buffer: Buffer, bit_offset: usize, bit_len: usize) -> Self {
112        let total_len = bit_offset.saturating_add(bit_len);
113        let buffer_len = buffer.len();
114        let buffer_bit_len = buffer_len.saturating_mul(8);
115        assert!(
116            total_len <= buffer_bit_len,
117            "buffer not large enough (bit_offset: {bit_offset}, bit_len: {bit_len}, buffer_len: {buffer_len})"
118        );
119        Self {
120            buffer,
121            bit_offset,
122            bit_len,
123        }
124    }
125
126    /// Create a new [`BooleanBuffer`] of `length` bits (not bytes) where all values are `true`
127    pub fn new_set(length: usize) -> Self {
128        let mut builder = BooleanBufferBuilder::new(length);
129        builder.append_n(length, true);
130        builder.finish()
131    }
132
133    /// Create a new [`BooleanBuffer`] of `length` bits (not bytes) where all values are `false`
134    pub fn new_unset(length: usize) -> Self {
135        let buffer = MutableBuffer::new_null(length).into_buffer();
136        Self {
137            buffer,
138            bit_offset: 0,
139            bit_len: length,
140        }
141    }
142
143    /// Invokes `f` with indexes `0..len` collecting the boolean results into a new `BooleanBuffer`
144    pub fn collect_bool<F: FnMut(usize) -> bool>(len: usize, f: F) -> Self {
145        let buffer = MutableBuffer::collect_bool(len, f);
146        Self::new(buffer.into(), 0, len)
147    }
148
149    /// Create a new [`BooleanBuffer`] by copying the relevant bits from an
150    /// input buffer.
151    ///
152    /// # Notes:
153    /// * The new `BooleanBuffer` may have non zero offset
154    ///   and/or padding bits outside the logical range.
155    ///
156    /// # Example: Create a new [`BooleanBuffer`] copying a bit slice from in input slice
157    /// ```
158    /// # use arrow_buffer::BooleanBuffer;
159    /// let input = [0b11001100u8, 0b10111010u8];
160    /// // // Copy bits 4..16 from input
161    /// let result = BooleanBuffer::from_bits(&input, 4, 12);
162    /// // output is 12 bits long starting from bit offset 4
163    /// assert_eq!(result.len(), 12);
164    /// assert_eq!(result.offset(), 4);
165    /// // the expected 12 bits are 0b101110101100 (bits 4..16 of the input)
166    /// let expected_bits = [false, false, true, true, false, true, false, true, true, true, false, true];
167    /// for (i, v) in expected_bits.into_iter().enumerate() {
168    ///    assert_eq!(result.value(i), v);
169    /// }
170    /// // However, underlying buffer has (ignored) bits set outside the requested range
171    /// assert_eq!(result.values(), &[0b11001100u8, 0b10111010, 0, 0, 0, 0, 0, 0]);
172    /// ```
173    pub fn from_bits(src: impl AsRef<[u8]>, offset_in_bits: usize, len_in_bits: usize) -> Self {
174        Self::from_bitwise_unary_op(src, offset_in_bits, len_in_bits, |a| a)
175    }
176
177    /// Create a new [`BooleanBuffer`] by applying the bitwise operation to `op`
178    /// to an input buffer.
179    ///
180    /// This function is faster than applying the operation bit by bit as
181    /// it processes input buffers in chunks of 64 bits (8 bytes) at a time
182    ///
183    /// # Notes:
184    /// * `op` takes a single `u64` inputs and produces one `u64` output.
185    /// * `op` must only apply bitwise operations
186    ///   on the relevant bits; the input `u64` may contain irrelevant bits
187    ///   and may be processed differently on different endian architectures.
188    /// * `op` may be called with input bits outside the requested range
189    /// * Returned `BooleanBuffer` may have non zero offset
190    /// * Returned `BooleanBuffer` may have bits set outside the requested range
191    ///
192    /// # See Also
193    /// - [`BooleanBuffer::from_bitwise_binary_op`] to create a new buffer from a binary operation
194    /// - [`apply_bitwise_unary_op`](bit_util::apply_bitwise_unary_op) for in-place unary bitwise operations
195    ///
196    /// # Example: Create new [`BooleanBuffer`] from bitwise `NOT`
197    /// ```
198    /// # use arrow_buffer::BooleanBuffer;
199    /// let input = [0b11001100u8, 0b10111010u8]; // 2 bytes = 16 bits
200    /// // NOT of bits 4..16
201    /// let result = BooleanBuffer::from_bitwise_unary_op(
202    ///  &input, 4, 12, |a| !a
203    /// );
204    /// // output is 12 bits long starting from bit offset 4
205    /// assert_eq!(result.len(), 12);
206    /// assert_eq!(result.offset(), 4);
207    /// // the expected 12 bits are 0b001100110101, (NOT of the requested bits)
208    /// let expected_bits = [true, true, false, false, true, false, true, false, false, false, true, false];
209    /// for (i, v) in expected_bits.into_iter().enumerate() {
210    ///     assert_eq!(result.value(i), v);
211    /// }
212    /// // However, underlying buffer has (ignored) bits set outside the requested range
213    /// let expected = [0b00110011u8, 0b01000101u8, 255, 255, 255, 255, 255, 255];
214    /// assert_eq!(result.values(), &expected);
215    /// ```
216    pub fn from_bitwise_unary_op<F>(
217        src: impl AsRef<[u8]>,
218        offset_in_bits: usize,
219        len_in_bits: usize,
220        mut op: F,
221    ) -> Self
222    where
223        F: FnMut(u64) -> u64,
224    {
225        let end = offset_in_bits + len_in_bits;
226        // Align start and end to 64 bit (8 byte) boundaries if possible to allow using the
227        // optimized code path as much as possible.
228        let aligned_offset = offset_in_bits & !63;
229        let aligned_end_bytes = bit_util::ceil(end, 64) * 8;
230        let src_len = src.as_ref().len();
231        let slice_end = aligned_end_bytes.min(src_len);
232
233        let aligned_start = &src.as_ref()[aligned_offset / 8..slice_end];
234
235        let (prefix, aligned_u64s, suffix) = unsafe { aligned_start.as_ref().align_to::<u64>() };
236        match (prefix, suffix) {
237            ([], []) => {
238                // the buffer is word (64 bit) aligned, so use optimized Vec code.
239                let result_u64s: Vec<u64> = aligned_u64s.iter().map(|l| op(*l)).collect();
240                return BooleanBuffer::new(result_u64s.into(), offset_in_bits % 64, len_in_bits);
241            }
242            ([], suffix) => {
243                let suffix = read_u64(suffix);
244                let result_u64s: Vec<u64> = aligned_u64s
245                    .iter()
246                    .copied()
247                    .chain(std::iter::once(suffix))
248                    .map(&mut op)
249                    .collect();
250                return BooleanBuffer::new(result_u64s.into(), offset_in_bits % 64, len_in_bits);
251            }
252            _ => {}
253        }
254
255        // align to byte boundaries
256        // Use unaligned code path, handle remainder bytes
257        let (chunks, remainder) = aligned_start.as_chunks::<8>();
258        let iter = chunks.iter().map(|c| u64::from_le_bytes(*c));
259        let vec_u64s: Vec<u64> = if remainder.is_empty() {
260            iter.map(&mut op).collect()
261        } else {
262            iter.chain(Some(read_u64(remainder))).map(&mut op).collect()
263        };
264
265        BooleanBuffer::new(vec_u64s.into(), offset_in_bits % 64, len_in_bits)
266    }
267
268    /// Create a new [`BooleanBuffer`] by applying the bitwise operation `op` to
269    /// the relevant bits from two input buffers.
270    ///
271    /// This function is faster than applying the operation bit by bit as
272    /// it processes input buffers in chunks of 64 bits (8 bytes) at a time
273    ///
274    /// # Notes:
275    /// * `op` takes two `u64` inputs and produces one `u64` output.
276    /// * `op` must only apply bitwise operations
277    ///   on the relevant bits; the input `u64` values may contain irrelevant bits
278    ///   and may be processed differently on different endian architectures.
279    /// * `op` may be called with input bits outside the requested range.
280    /// * Returned `BooleanBuffer` may have non zero offset
281    /// * Returned `BooleanBuffer` may have bits set outside the requested range
282    ///
283    /// # See Also
284    /// - [`BooleanBuffer::from_bitwise_unary_op`] for unary operations on a single input buffer.
285    /// - [`apply_bitwise_binary_op`](bit_util::apply_bitwise_binary_op) for in-place binary bitwise operations
286    ///
287    /// # Example: Create new [`BooleanBuffer`] from bitwise `AND` of two [`Buffer`]s
288    /// ```
289    /// # use arrow_buffer::{Buffer, BooleanBuffer};
290    /// let left = Buffer::from(vec![0b11001100u8, 0b10111010u8]); // 2 bytes = 16 bits
291    /// let right = Buffer::from(vec![0b10101010u8, 0b11011100u8, 0b11110000u8]); // 3 bytes = 24 bits
292    /// // AND of the first 12 bits
293    /// let result = BooleanBuffer::from_bitwise_binary_op(
294    ///   &left, 0, &right, 0, 12, |a, b| a & b
295    /// );
296    /// assert_eq!(result.len(), 12);
297    /// for i in 0..12 {
298    ///     assert_eq!(result.value(i), left.as_slice()[i / 8] >> (i % 8) & 1 == 1
299    ///         && right.as_slice()[i / 8] >> (i % 8) & 1 == 1);
300    /// }
301    /// ```
302    ///
303    /// # Example: Create new [`BooleanBuffer`] from bitwise `OR` of two byte slices
304    /// ```
305    /// # use arrow_buffer::{BooleanBuffer, bit_util};
306    /// let left = [0b11001100u8, 0b10111010u8];
307    /// let right = [0b10101010u8, 0b11011100u8];
308    /// // OR of bits 4..16 from left and bits 0..12 from right
309    /// let result = BooleanBuffer::from_bitwise_binary_op(
310    ///  &left, 4, &right, 0, 12, |a, b| a | b
311    /// );
312    /// assert_eq!(result.len(), 12);
313    /// for i in 0..12 {
314    ///     let l = bit_util::get_bit(&left, 4 + i);
315    ///     let r = bit_util::get_bit(&right, i);
316    ///     assert_eq!(result.value(i), l | r);
317    /// }
318    /// ```
319    pub fn from_bitwise_binary_op<F>(
320        left: impl AsRef<[u8]>,
321        left_offset_in_bits: usize,
322        right: impl AsRef<[u8]>,
323        right_offset_in_bits: usize,
324        len_in_bits: usize,
325        mut op: F,
326    ) -> Self
327    where
328        F: FnMut(u64, u64) -> u64,
329    {
330        let left = left.as_ref();
331        let right = right.as_ref();
332
333        // When both offsets share the same sub-64-bit alignment, we can
334        // align both to 64-bit boundaries and zip u64s directly,
335        // avoiding BitChunks bit-shifting entirely.
336        if left_offset_in_bits % 64 == right_offset_in_bits % 64 {
337            let bit_offset = left_offset_in_bits % 64;
338            let left_end = left_offset_in_bits + len_in_bits;
339            let right_end = right_offset_in_bits + len_in_bits;
340
341            let left_aligned = left_offset_in_bits & !63;
342            let right_aligned = right_offset_in_bits & !63;
343
344            let left_end_bytes = (bit_util::ceil(left_end, 64) * 8).min(left.len());
345            let right_end_bytes = (bit_util::ceil(right_end, 64) * 8).min(right.len());
346
347            let left_slice = &left[left_aligned / 8..left_end_bytes];
348            let right_slice = &right[right_aligned / 8..right_end_bytes];
349
350            let (lp, left_u64s, ls) = unsafe { left_slice.align_to::<u64>() };
351            let (rp, right_u64s, rs) = unsafe { right_slice.align_to::<u64>() };
352
353            match (lp, ls, rp, rs) {
354                ([], [], [], []) => {
355                    let result_u64s: Vec<u64> = left_u64s
356                        .iter()
357                        .zip(right_u64s.iter())
358                        .map(|(l, r)| op(*l, *r))
359                        .collect();
360                    return BooleanBuffer::new(result_u64s.into(), bit_offset, len_in_bits);
361                }
362                ([], left_suf, [], right_suf) => {
363                    let left_iter = left_u64s
364                        .iter()
365                        .copied()
366                        .chain((!left_suf.is_empty()).then(|| read_u64(left_suf)));
367                    let right_iter = right_u64s
368                        .iter()
369                        .copied()
370                        .chain((!right_suf.is_empty()).then(|| read_u64(right_suf)));
371                    let result_u64s: Vec<u64> =
372                        left_iter.zip(right_iter).map(|(l, r)| op(l, r)).collect();
373                    return BooleanBuffer::new(result_u64s.into(), bit_offset, len_in_bits);
374                }
375                _ => {}
376            }
377
378            // Memory not u64-aligned, use chunks_exact fallback
379            let (left_chunks, left_rem) = left_slice.as_chunks::<8>();
380            let (right_chunks, right_rem) = right_slice.as_chunks::<8>();
381
382            let left_iter = left_chunks.iter().map(|c| u64::from_le_bytes(*c));
383            let right_iter = right_chunks.iter().map(|c| u64::from_le_bytes(*c));
384
385            let result_u64s: Vec<u64> = if left_rem.is_empty() && right_rem.is_empty() {
386                left_iter.zip(right_iter).map(|(l, r)| op(l, r)).collect()
387            } else {
388                left_iter
389                    .chain(Some(read_u64(left_rem)))
390                    .zip(right_iter.chain(Some(read_u64(right_rem))))
391                    .map(|(l, r)| op(l, r))
392                    .collect()
393            };
394            return BooleanBuffer::new(result_u64s.into(), bit_offset, len_in_bits);
395        }
396
397        // Different sub-64-bit alignments: bit-shifting unavoidable
398        let left_chunks = BitChunks::new(left, left_offset_in_bits, len_in_bits);
399        let right_chunks = BitChunks::new(right, right_offset_in_bits, len_in_bits);
400
401        let chunks = left_chunks
402            .iter()
403            .zip(right_chunks.iter())
404            .map(|(left, right)| op(left, right));
405        // Soundness: `BitChunks` is a `BitChunks` trusted length iterator which
406        // correctly reports its upper bound
407        let mut buffer = unsafe { MutableBuffer::from_trusted_len_iter(chunks) };
408
409        let remainder_bytes = bit_util::ceil(left_chunks.remainder_len(), 8);
410        let rem = op(left_chunks.remainder_bits(), right_chunks.remainder_bits());
411        // we are counting its starting from the least significant bit, to to_le_bytes should be correct
412        let rem = &rem.to_le_bytes()[0..remainder_bytes];
413        buffer.extend_from_slice(rem);
414
415        BooleanBuffer {
416            buffer: Buffer::from(buffer),
417            bit_offset: 0,
418            bit_len: len_in_bits,
419        }
420    }
421
422    /// Returns the number of set bits in this buffer
423    pub fn count_set_bits(&self) -> usize {
424        self.buffer
425            .count_set_bits_offset(self.bit_offset, self.bit_len)
426    }
427
428    /// Finds the position of the n-th set bit (1-based) starting from `start` index.
429    /// If fewer than `n` set bits are found, returns the length of the buffer.
430    pub fn find_nth_set_bit_position(&self, start: usize, n: usize) -> usize {
431        if n == 0 {
432            return start;
433        }
434
435        self.slice(start, self.bit_len - start)
436            .set_indices()
437            .nth(n - 1)
438            .map(|idx| start + idx + 1)
439            .unwrap_or(self.bit_len)
440    }
441
442    /// Returns a [`BitChunks`] instance which can be used to iterate over
443    /// this buffer's bits in `u64` chunks
444    #[inline]
445    pub fn bit_chunks(&self) -> BitChunks<'_> {
446        BitChunks::new(self.values(), self.bit_offset, self.bit_len)
447    }
448
449    /// Returns the offset of this [`BooleanBuffer`] in bits (not bytes)
450    #[inline]
451    pub fn offset(&self) -> usize {
452        self.bit_offset
453    }
454
455    /// Returns the length of this [`BooleanBuffer`] in bits (not bytes)
456    #[inline]
457    pub fn len(&self) -> usize {
458        self.bit_len
459    }
460
461    /// Returns true if this [`BooleanBuffer`] is empty
462    #[inline]
463    pub fn is_empty(&self) -> bool {
464        self.bit_len == 0
465    }
466
467    /// Free up unused memory.
468    pub fn shrink_to_fit(&mut self) {
469        // TODO(emilk): we could shrink even more in the case where we are a small sub-slice of the full buffer
470        self.buffer.shrink_to_fit();
471    }
472
473    /// Returns the boolean value at index `i`.
474    ///
475    /// # Panics
476    ///
477    /// Panics if `i >= self.len()`
478    #[inline]
479    pub fn value(&self, idx: usize) -> bool {
480        assert!(idx < self.bit_len);
481        unsafe { self.value_unchecked(idx) }
482    }
483
484    /// Returns the boolean value at index `i`.
485    ///
486    /// # Safety
487    /// This doesn't check bounds, the caller must ensure that index < self.len()
488    #[inline]
489    pub unsafe fn value_unchecked(&self, i: usize) -> bool {
490        unsafe { bit_util::get_bit_raw(self.buffer.as_ptr(), i + self.bit_offset) }
491    }
492
493    /// Returns the packed values of this [`BooleanBuffer`] not including any offset
494    #[inline]
495    pub fn values(&self) -> &[u8] {
496        &self.buffer
497    }
498
499    /// Slices this [`BooleanBuffer`] by the provided `offset` and `length`
500    ///
501    /// # Panics
502    ///
503    /// Panics if `offset + len > self.len()`
504    pub fn slice(&self, offset: usize, len: usize) -> Self {
505        assert!(
506            offset.saturating_add(len) <= self.bit_len,
507            "the length + offset of the sliced BooleanBuffer cannot exceed the existing length"
508        );
509        Self {
510            buffer: self.buffer.clone(),
511            bit_offset: self.bit_offset + offset,
512            bit_len: len,
513        }
514    }
515
516    /// Returns a new [`Buffer`] containing the sliced contents of this [`BooleanBuffer`]
517    ///
518    /// Equivalent to `self.buffer.bit_slice(self.offset, self.len)`
519    pub fn sliced(&self) -> Buffer {
520        self.buffer.bit_slice(self.bit_offset, self.bit_len)
521    }
522
523    /// Returns true if this [`BooleanBuffer`] is equal to `other`, using pointer comparisons
524    /// to determine buffer equality. This is cheaper than `PartialEq::eq` but may
525    /// return false when the arrays are logically equal
526    pub fn ptr_eq(&self, other: &Self) -> bool {
527        self.buffer.as_ptr() == other.buffer.as_ptr()
528            && self.bit_offset == other.bit_offset
529            && self.bit_len == other.bit_len
530    }
531
532    /// Returns the inner [`Buffer`]
533    ///
534    /// Note: this does not account for offset and length of this [`BooleanBuffer`]
535    #[inline]
536    pub fn inner(&self) -> &Buffer {
537        &self.buffer
538    }
539
540    /// Returns the inner [`Buffer`], consuming self
541    ///
542    /// Note: this does not account for offset and length of this [`BooleanBuffer`]
543    pub fn into_inner(self) -> Buffer {
544        self.buffer
545    }
546
547    /// Claim memory used by this buffer in the provided memory pool.
548    ///
549    /// See [`Buffer::claim`] for details.
550    #[cfg(feature = "pool")]
551    pub fn claim(&self, pool: &dyn crate::MemoryPool) {
552        self.buffer.claim(pool);
553    }
554
555    /// Apply a bitwise binary operation to `self`.
556    ///
557    /// If the underlying buffer is uniquely owned, reuses the allocation
558    /// and updates the bytes in place. If the underlying buffer is shared,
559    /// returns a newly allocated buffer.
560    ///
561    /// # API Notes
562    ///
563    /// If the buffer is reused, the result preserves the existing offset, which
564    /// may be non-zero.
565    fn bitwise_bin_op_assign<F>(&mut self, rhs: &BooleanBuffer, op: F)
566    where
567        F: FnMut(u64, u64) -> u64,
568    {
569        assert_eq!(self.bit_len, rhs.bit_len);
570        // Try to mutate in place if the buffer is uniquely owned
571        let buffer = std::mem::take(&mut self.buffer);
572        match buffer.into_mutable() {
573            Ok(mut buf) => {
574                bit_util::apply_bitwise_binary_op(
575                    &mut buf,
576                    self.bit_offset,
577                    &rhs.buffer,
578                    rhs.bit_offset,
579                    self.bit_len,
580                    op,
581                );
582                self.buffer = buf.into();
583            }
584            Err(buf) => {
585                self.buffer = buf;
586                *self = BooleanBuffer::from_bitwise_binary_op(
587                    self.values(),
588                    self.bit_offset,
589                    rhs.values(),
590                    rhs.bit_offset,
591                    self.bit_len,
592                    op,
593                );
594            }
595        }
596    }
597
598    /// Returns an iterator over the bits in this [`BooleanBuffer`]
599    pub fn iter(&self) -> BitIterator<'_> {
600        self.into_iter()
601    }
602
603    /// Returns an [`UnalignedBitChunk`] over this buffer's values.
604    fn unaligned_bit_chunks(&self) -> UnalignedBitChunk<'_> {
605        UnalignedBitChunk::new(self.values(), self.offset(), self.len())
606    }
607
608    /// Returns an iterator over the set bit positions in this [`BooleanBuffer`]
609    pub fn set_indices(&self) -> BitIndexIterator<'_> {
610        BitIndexIterator::new(self.values(), self.bit_offset, self.bit_len)
611    }
612
613    /// Returns a `u32` iterator over set bit positions without any usize->u32 conversion
614    pub fn set_indices_u32(&self) -> BitIndexU32Iterator<'_> {
615        BitIndexU32Iterator::new(self.values(), self.bit_offset, self.bit_len)
616    }
617
618    /// Returns a [`BitSliceIterator`] yielding contiguous ranges of set bits
619    pub fn set_slices(&self) -> BitSliceIterator<'_> {
620        BitSliceIterator::new(self.values(), self.bit_offset, self.bit_len)
621    }
622
623    /// Block size for chunked fold operations in [`Self::has_true`] and [`Self::has_false`].
624    /// Using `chunks_exact` with this size lets the compiler fully unroll the inner
625    /// fold (no inner branch/loop), enabling short-circuit exits every N chunks.
626    const CHUNK_FOLD_BLOCK_SIZE: usize = 16;
627
628    /// Returns whether there is at least one `true` value in this buffer.
629    ///
630    /// This is more efficient than `count_set_bits() > 0` because it can short-circuit
631    /// as soon as a `true` value is found, without counting all set bits.
632    ///
633    /// Returns `false` for empty buffer.
634    pub fn has_true(&self) -> bool {
635        let bit_chunks = self.unaligned_bit_chunks();
636        let chunks = bit_chunks.chunks();
637        let (exact, remainder) = chunks.as_chunks::<{ Self::CHUNK_FOLD_BLOCK_SIZE }>();
638        let found = bit_chunks.prefix().unwrap_or(0) != 0
639            || exact
640                .iter()
641                .any(|block| block.iter().fold(0u64, |acc, &c| acc | c) != 0);
642        found || remainder.iter().any(|&c| c != 0) || bit_chunks.suffix().unwrap_or(0) != 0
643    }
644
645    /// Returns whether there is at least one `false` value in this buffer.
646    ///
647    /// This is more efficient than `len() > count_set_bits()` because it can short-circuit
648    /// as soon as a `false` value is found, without counting all set bits.
649    ///
650    /// Returns `false` for empty buffer.
651    pub fn has_false(&self) -> bool {
652        let bit_chunks = self.unaligned_bit_chunks();
653        // UnalignedBitChunk zeros padding bits; fill them with 1s so
654        // they don't appear as false values.
655        let lead_mask = !((1u64 << bit_chunks.lead_padding()) - 1);
656        let trail_mask = if bit_chunks.trailing_padding() == 0 {
657            u64::MAX
658        } else {
659            (1u64 << (64 - bit_chunks.trailing_padding())) - 1
660        };
661        let (prefix_fill, suffix_fill) = match (bit_chunks.prefix(), bit_chunks.suffix()) {
662            (Some(_), Some(_)) => (!lead_mask, !trail_mask),
663            (Some(_), None) => (!lead_mask | !trail_mask, 0),
664            (None, Some(_)) => (0, !trail_mask),
665            (None, None) => (0, 0),
666        };
667        let chunks = bit_chunks.chunks();
668        let (exact, remainder) = chunks.as_chunks::<{ Self::CHUNK_FOLD_BLOCK_SIZE }>();
669        let found = bit_chunks
670            .prefix()
671            .is_some_and(|v| (v | prefix_fill) != u64::MAX)
672            || exact
673                .iter()
674                .any(|block| block.iter().fold(u64::MAX, |acc, &c| acc & c) != u64::MAX);
675        found
676            || remainder.iter().any(|&c| c != u64::MAX)
677            || bit_chunks
678                .suffix()
679                .is_some_and(|v| (v | suffix_fill) != u64::MAX)
680    }
681}
682
683impl Not for &BooleanBuffer {
684    type Output = BooleanBuffer;
685
686    fn not(self) -> Self::Output {
687        BooleanBuffer::from_bitwise_unary_op(&self.buffer, self.bit_offset, self.bit_len, |a| !a)
688    }
689}
690
691impl BitAnd<&BooleanBuffer> for &BooleanBuffer {
692    type Output = BooleanBuffer;
693
694    fn bitand(self, rhs: &BooleanBuffer) -> Self::Output {
695        assert_eq!(self.bit_len, rhs.bit_len);
696        BooleanBuffer {
697            buffer: buffer_bin_and(
698                &self.buffer,
699                self.bit_offset,
700                &rhs.buffer,
701                rhs.bit_offset,
702                self.bit_len,
703            ),
704            bit_offset: 0,
705            bit_len: self.bit_len,
706        }
707    }
708}
709
710impl BitOr<&BooleanBuffer> for &BooleanBuffer {
711    type Output = BooleanBuffer;
712
713    fn bitor(self, rhs: &BooleanBuffer) -> Self::Output {
714        assert_eq!(self.bit_len, rhs.bit_len);
715        BooleanBuffer {
716            buffer: buffer_bin_or(
717                &self.buffer,
718                self.bit_offset,
719                &rhs.buffer,
720                rhs.bit_offset,
721                self.bit_len,
722            ),
723            bit_offset: 0,
724            bit_len: self.bit_len,
725        }
726    }
727}
728
729impl BitXor<&BooleanBuffer> for &BooleanBuffer {
730    type Output = BooleanBuffer;
731
732    fn bitxor(self, rhs: &BooleanBuffer) -> Self::Output {
733        assert_eq!(self.bit_len, rhs.bit_len);
734        BooleanBuffer {
735            buffer: buffer_bin_xor(
736                &self.buffer,
737                self.bit_offset,
738                &rhs.buffer,
739                rhs.bit_offset,
740                self.bit_len,
741            ),
742            bit_offset: 0,
743            bit_len: self.bit_len,
744        }
745    }
746}
747
748impl BitAndAssign<&BooleanBuffer> for BooleanBuffer {
749    fn bitand_assign(&mut self, rhs: &BooleanBuffer) {
750        self.bitwise_bin_op_assign(rhs, |a, b| a & b);
751    }
752}
753
754impl BitOrAssign<&BooleanBuffer> for BooleanBuffer {
755    fn bitor_assign(&mut self, rhs: &BooleanBuffer) {
756        self.bitwise_bin_op_assign(rhs, |a, b| a | b);
757    }
758}
759
760impl BitXorAssign<&BooleanBuffer> for BooleanBuffer {
761    fn bitxor_assign(&mut self, rhs: &BooleanBuffer) {
762        self.bitwise_bin_op_assign(rhs, |a, b| a ^ b);
763    }
764}
765
766impl<'a> IntoIterator for &'a BooleanBuffer {
767    type Item = bool;
768    type IntoIter = BitIterator<'a>;
769
770    fn into_iter(self) -> Self::IntoIter {
771        BitIterator::new(self.values(), self.bit_offset, self.bit_len)
772    }
773}
774
775impl From<&[bool]> for BooleanBuffer {
776    fn from(value: &[bool]) -> Self {
777        let mut builder = BooleanBufferBuilder::new(value.len());
778        builder.append_slice(value);
779        builder.finish()
780    }
781}
782
783impl From<Vec<bool>> for BooleanBuffer {
784    fn from(value: Vec<bool>) -> Self {
785        value.as_slice().into()
786    }
787}
788
789impl FromIterator<bool> for BooleanBuffer {
790    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
791        let iter = iter.into_iter();
792        let (hint, _) = iter.size_hint();
793        let mut builder = BooleanBufferBuilder::new(hint);
794        iter.for_each(|b| builder.append(b));
795        builder.finish()
796    }
797}
798
799#[cfg(test)]
800mod tests {
801    use super::*;
802
803    #[test]
804    fn test_boolean_new() {
805        let bytes = &[0, 1, 2, 3, 4];
806        let buf = Buffer::from(bytes);
807        let offset = 0;
808        let len = 24;
809
810        let boolean_buf = BooleanBuffer::new(buf.clone(), offset, len);
811        assert_eq!(bytes, boolean_buf.values());
812        assert_eq!(offset, boolean_buf.offset());
813        assert_eq!(len, boolean_buf.len());
814
815        assert_eq!(2, boolean_buf.count_set_bits());
816        assert_eq!(&buf, boolean_buf.inner());
817        assert_eq!(buf, boolean_buf.clone().into_inner());
818
819        assert!(!boolean_buf.is_empty())
820    }
821
822    #[test]
823    fn test_boolean_data_equality() {
824        let boolean_buf1 = BooleanBuffer::new(Buffer::from(&[0, 1, 4, 3, 5]), 0, 32);
825        let boolean_buf2 = BooleanBuffer::new(Buffer::from(&[0, 1, 4, 3, 5]), 0, 32);
826        assert_eq!(boolean_buf1, boolean_buf2);
827
828        // slice with same offset and same length should still preserve equality
829        let boolean_buf3 = boolean_buf1.slice(8, 16);
830        assert_ne!(boolean_buf1, boolean_buf3);
831        let boolean_buf4 = boolean_buf1.slice(0, 32);
832        assert_eq!(boolean_buf1, boolean_buf4);
833
834        // unequal because of different elements
835        let boolean_buf2 = BooleanBuffer::new(Buffer::from(&[0, 0, 2, 3, 4]), 0, 32);
836        assert_ne!(boolean_buf1, boolean_buf2);
837
838        // unequal because of different length
839        let boolean_buf2 = BooleanBuffer::new(Buffer::from(&[0, 1, 4, 3, 5]), 0, 24);
840        assert_ne!(boolean_buf1, boolean_buf2);
841
842        // ptr_eq
843        assert!(boolean_buf1.ptr_eq(&boolean_buf1));
844        assert!(boolean_buf2.ptr_eq(&boolean_buf2));
845        assert!(!boolean_buf1.ptr_eq(&boolean_buf2));
846    }
847
848    #[test]
849    fn test_boolean_slice() {
850        let bytes = &[0, 3, 2, 6, 2];
851        let boolean_buf1 = BooleanBuffer::new(Buffer::from(bytes), 0, 32);
852        let boolean_buf2 = BooleanBuffer::new(Buffer::from(bytes), 0, 32);
853
854        let boolean_slice1 = boolean_buf1.slice(16, 16);
855        let boolean_slice2 = boolean_buf2.slice(0, 16);
856        assert_eq!(boolean_slice1.values(), boolean_slice2.values());
857
858        assert_eq!(bytes, boolean_slice1.values());
859        assert_eq!(16, boolean_slice1.bit_offset);
860        assert_eq!(16, boolean_slice1.bit_len);
861
862        assert_eq!(bytes, boolean_slice2.values());
863        assert_eq!(0, boolean_slice2.bit_offset);
864        assert_eq!(16, boolean_slice2.bit_len);
865    }
866
867    #[test]
868    fn test_boolean_bitand() {
869        let offset = 0;
870        let len = 40;
871
872        let buf1 = Buffer::from(&[0, 1, 1, 0, 0]);
873        let boolean_buf1 = &BooleanBuffer::new(buf1, offset, len);
874
875        let buf2 = Buffer::from(&[0, 1, 1, 1, 0]);
876        let boolean_buf2 = &BooleanBuffer::new(buf2, offset, len);
877
878        let expected = BooleanBuffer::new(Buffer::from(&[0, 1, 1, 0, 0]), offset, len);
879        assert_eq!(boolean_buf1 & boolean_buf2, expected);
880    }
881
882    #[test]
883    fn test_boolean_bitor() {
884        let offset = 0;
885        let len = 40;
886
887        let buf1 = Buffer::from(&[0, 1, 1, 0, 0]);
888        let boolean_buf1 = &BooleanBuffer::new(buf1, offset, len);
889
890        let buf2 = Buffer::from(&[0, 1, 1, 1, 0]);
891        let boolean_buf2 = &BooleanBuffer::new(buf2, offset, len);
892
893        let expected = BooleanBuffer::new(Buffer::from(&[0, 1, 1, 1, 0]), offset, len);
894        assert_eq!(boolean_buf1 | boolean_buf2, expected);
895    }
896
897    #[test]
898    fn test_boolean_bitxor() {
899        let offset = 0;
900        let len = 40;
901
902        let buf1 = Buffer::from(&[0, 1, 1, 0, 0]);
903        let boolean_buf1 = &BooleanBuffer::new(buf1, offset, len);
904
905        let buf2 = Buffer::from(&[0, 1, 1, 1, 0]);
906        let boolean_buf2 = &BooleanBuffer::new(buf2, offset, len);
907
908        let expected = BooleanBuffer::new(Buffer::from(&[0, 0, 0, 1, 0]), offset, len);
909        assert_eq!(boolean_buf1 ^ boolean_buf2, expected);
910    }
911
912    #[test]
913    fn test_boolean_bitand_assign_shared_and_unshared() {
914        let rhs = BooleanBuffer::from(&[true, true, false, true, false, true][..]);
915        let original = BooleanBuffer::from(&[true, false, true, true, true, false][..]);
916
917        let mut unshared = BooleanBuffer::from(&[true, false, true, true, true, false][..]);
918        unshared &= &rhs;
919
920        let mut shared = original.clone();
921        let _shared_owner = shared.clone();
922        shared &= &rhs;
923
924        let expected = &original & &rhs;
925        assert_eq!(unshared, expected);
926        assert_eq!(shared, expected);
927    }
928
929    #[test]
930    fn test_boolean_bitor_assign() {
931        let rhs = BooleanBuffer::from(&[true, true, false, true, false, true][..]);
932        let original = BooleanBuffer::from(&[true, false, true, true, true, false][..]);
933
934        let mut actual = original.clone();
935        actual |= &rhs;
936
937        let expected = &original | &rhs;
938        assert_eq!(actual, expected);
939    }
940
941    #[test]
942    fn test_boolean_bitxor_assign() {
943        let rhs = BooleanBuffer::from(&[true, true, false, true, false, true][..]);
944        let original = BooleanBuffer::from(&[true, false, true, true, true, false][..]);
945
946        let mut actual = original.clone();
947        actual ^= &rhs;
948
949        let expected = &original ^ &rhs;
950        assert_eq!(actual, expected);
951    }
952
953    #[test]
954    fn test_boolean_not() {
955        let offset = 0;
956        let len = 40;
957
958        let buf = Buffer::from(&[0, 1, 1, 0, 0]);
959        let boolean_buf = &BooleanBuffer::new(buf, offset, len);
960
961        let expected = BooleanBuffer::new(Buffer::from(&[255, 254, 254, 255, 255]), offset, len);
962        assert_eq!(!boolean_buf, expected);
963
964        // Demonstrate that Non-zero offsets are preserved
965        let sliced = boolean_buf.slice(3, 20);
966        let result = !&sliced;
967        assert_eq!(result.offset(), 3);
968        assert_eq!(result.len(), sliced.len());
969        for i in 0..sliced.len() {
970            assert_eq!(result.value(i), !sliced.value(i));
971        }
972    }
973
974    #[test]
975    fn test_boolean_from_slice_bool() {
976        let v = [true, false, false];
977        let buf = BooleanBuffer::from(&v[..]);
978        assert_eq!(buf.offset(), 0);
979        assert_eq!(buf.len(), 3);
980        assert_eq!(buf.values().len(), 1);
981        assert!(buf.value(0));
982    }
983
984    #[test]
985    fn test_from_bitwise_unary_op() {
986        // Use 1024 boolean values so that at least some of the tests cover multiple u64 chunks and
987        // perfect alignment
988        let input_bools = (0..1024)
989            .map(|_| rand::random::<bool>())
990            .collect::<Vec<bool>>();
991        let input_buffer = BooleanBuffer::from(&input_bools[..]);
992
993        // Note ensure we test offsets over 100 to cover multiple u64 chunks
994        for offset in 0..1024 {
995            let result = BooleanBuffer::from_bitwise_unary_op(
996                input_buffer.values(),
997                offset,
998                input_buffer.len() - offset,
999                |a| !a,
1000            );
1001            let expected = input_bools[offset..]
1002                .iter()
1003                .map(|b| !*b)
1004                .collect::<BooleanBuffer>();
1005            assert_eq!(result, expected);
1006        }
1007
1008        // Also test when the input doesn't cover the entire buffer
1009        for offset in 0..512 {
1010            let len = 512 - offset; // fixed length less than total
1011            let result =
1012                BooleanBuffer::from_bitwise_unary_op(input_buffer.values(), offset, len, |a| !a);
1013            let expected = input_bools[offset..]
1014                .iter()
1015                .take(len)
1016                .map(|b| !*b)
1017                .collect::<BooleanBuffer>();
1018            assert_eq!(result, expected);
1019        }
1020    }
1021
1022    #[test]
1023    fn test_from_bitwise_unary_op_unaligned_fallback() {
1024        // Deterministic affine sequence over u8: b[i] = 37*i + 11 (mod 256).
1025        // This yields a non-trivial mix of bits (prefix: 11, 48, 85, 122, 159, 196, 233, 14, ...)
1026        // so unary bit operations are exercised on varied input patterns.
1027        let bytes = (0..80)
1028            .map(|i| (i as u8).wrapping_mul(37).wrapping_add(11))
1029            .collect::<Vec<_>>();
1030        let base = bytes.as_ptr() as usize;
1031        let shift = (0..8).find(|s| !(base + s).is_multiple_of(8)).unwrap();
1032        let misaligned = &bytes[shift..];
1033
1034        // Case 1: fallback path with `remainder.is_empty() == true`
1035        let src = &misaligned[..24];
1036        let offset = 7;
1037        let len = 96;
1038        let result = BooleanBuffer::from_bitwise_unary_op(src, offset, len, |a| !a);
1039        let expected = (0..len)
1040            .map(|i| !bit_util::get_bit(src, offset + i))
1041            .collect::<BooleanBuffer>();
1042        assert_eq!(result, expected);
1043        assert_eq!(result.offset(), offset % 64);
1044
1045        // Case 2: fallback path with `remainder.is_empty() == false`
1046        let src = &misaligned[..13];
1047        let offset = 3;
1048        let len = 100;
1049        let result = BooleanBuffer::from_bitwise_unary_op(src, offset, len, |a| !a);
1050        let expected = (0..len)
1051            .map(|i| !bit_util::get_bit(src, offset + i))
1052            .collect::<BooleanBuffer>();
1053        assert_eq!(result, expected);
1054        assert_eq!(result.offset(), offset % 64);
1055    }
1056
1057    #[test]
1058    fn test_from_bitwise_binary_op() {
1059        // pick random boolean inputs
1060        let input_bools_left = (0..1024)
1061            .map(|_| rand::random::<bool>())
1062            .collect::<Vec<bool>>();
1063        let input_bools_right = (0..1024)
1064            .map(|_| rand::random::<bool>())
1065            .collect::<Vec<bool>>();
1066        let input_buffer_left = BooleanBuffer::from(&input_bools_left[..]);
1067        let input_buffer_right = BooleanBuffer::from(&input_bools_right[..]);
1068
1069        #[cfg(miri)] // Takes too long otherwise
1070        let left_offsets = [0, 1, 7, 8, 63, 64, 65];
1071        #[cfg(not(miri))]
1072        let left_offsets = 0..200;
1073
1074        for left_offset in left_offsets {
1075            for right_offset in [0, 4, 5, 17, 33, 24, 45, 64, 65, 100, 200] {
1076                for len_offset in [0, 1, 44, 100, 256, 300, 512] {
1077                    let len = 1024 - len_offset - left_offset.max(right_offset); // ensure we don't go out of bounds
1078                    // compute with AND
1079                    let result = BooleanBuffer::from_bitwise_binary_op(
1080                        input_buffer_left.values(),
1081                        left_offset,
1082                        input_buffer_right.values(),
1083                        right_offset,
1084                        len,
1085                        |a, b| a & b,
1086                    );
1087                    // compute directly from bools
1088                    let expected = input_bools_left[left_offset..]
1089                        .iter()
1090                        .zip(&input_bools_right[right_offset..])
1091                        .take(len)
1092                        .map(|(a, b)| *a & *b)
1093                        .collect::<BooleanBuffer>();
1094                    assert_eq!(result, expected);
1095                }
1096            }
1097        }
1098    }
1099
1100    #[test]
1101    fn test_from_bitwise_binary_op_same_mod_64_unaligned_fallback() {
1102        // Exercise the shared-alignment fast path when both inputs are misaligned in memory,
1103        // forcing the chunks_exact fallback instead of align_to::<u64>().
1104        let left_bytes = [
1105            0,           // dropped so `&left_bytes[1..]` is not u64-aligned in memory
1106            0b1101_0010, // logical left bits start at bit 3 of this byte
1107            0b0110_1101,
1108            0b1010_0111,
1109            0b0001_1110,
1110            0b1110_0001,
1111            0b0101_1010,
1112            0b1001_0110,
1113            0b0011_1100,
1114            0b1011_0001,
1115            0b0100_1110,
1116            0b1100_0011,
1117            0b0111_1000,
1118        ];
1119        let right_bytes = [
1120            0,           // dropped so `&right_bytes[1..]` is not u64-aligned in memory
1121            0b1010_1100, // logical right bits start at bit 67 == bit 3 of the second 64-bit block
1122            0b0101_0011,
1123            0b1111_0000,
1124            0b0011_1010,
1125            0b1000_1111,
1126            0b0110_0101,
1127            0b1101_1000,
1128            0b0001_0111,
1129            0b1110_0100,
1130            0b0010_1101,
1131            0b1001_1010,
1132            0b0111_0001,
1133        ];
1134
1135        let left = &left_bytes[1..];
1136        let right = &right_bytes[1..];
1137
1138        let left_offset = 3;
1139        let right_offset = 67; // same mod 64 as left_offset, so this takes the shared-alignment path
1140        let len = 24; // leaves a partial trailing chunk, so this covers the non-empty remainder branch
1141
1142        let result = BooleanBuffer::from_bitwise_binary_op(
1143            left,
1144            left_offset,
1145            right,
1146            right_offset,
1147            len,
1148            |a, b| a & b,
1149        );
1150        let expected = (0..len)
1151            .map(|i| {
1152                bit_util::get_bit(left, left_offset + i)
1153                    & bit_util::get_bit(right, right_offset + i)
1154            })
1155            .collect::<BooleanBuffer>();
1156
1157        assert_eq!(result, expected);
1158        assert_eq!(result.offset(), left_offset % 64);
1159    }
1160
1161    #[test]
1162    fn test_from_bitwise_binary_op_same_mod_64_unaligned_fallback_no_remainder() {
1163        // Force the chunks_exact fallback with an exact 8-byte chunk so both remainders are empty.
1164        let left_bytes = [
1165            0,           // dropped so `&left_bytes[1..]` is not u64-aligned in memory
1166            0b1010_1100, // logical left bits start at bit 3 of this byte
1167            0b0110_1001,
1168            0b1101_0011,
1169            0b0001_1110,
1170            0b1110_0101,
1171            0b0101_1000,
1172            0b1001_0111,
1173            0b0011_1101,
1174        ];
1175        let right_bytes = [
1176            0,           // dropped so `&right_bytes[1..]` is not u64-aligned in memory
1177            0b0111_0010, // logical right bits start at bit 67 == bit 3 of the second 64-bit block
1178            0b1010_1001,
1179            0b0101_1110,
1180            0b1100_0011,
1181            0b0011_1011,
1182            0b1000_1110,
1183            0b1111_0001,
1184            0b0100_1101,
1185            0b1011_0110,
1186            0b0001_1011,
1187            0b1101_0100,
1188            0b0110_0011,
1189            0b1001_1110,
1190            0b0010_1001,
1191            0b1110_0110,
1192            0b0101_0001,
1193        ];
1194
1195        let left = &left_bytes[1..];
1196        let right = &right_bytes[1..];
1197
1198        let left_offset = 3;
1199        let right_offset = 67; // same mod 64 as left_offset, so this takes the shared-alignment path
1200        let len = 61; // 3 + 61 = 64, so the aligned slices are exactly one 8-byte chunk with empty remainders
1201
1202        let result = BooleanBuffer::from_bitwise_binary_op(
1203            left,
1204            left_offset,
1205            right,
1206            right_offset,
1207            len,
1208            |a, b| a | b,
1209        );
1210        let expected = (0..len)
1211            .map(|i| {
1212                bit_util::get_bit(left, left_offset + i)
1213                    | bit_util::get_bit(right, right_offset + i)
1214            })
1215            .collect::<BooleanBuffer>();
1216
1217        assert_eq!(result, expected);
1218        assert_eq!(result.offset(), left_offset % 64);
1219    }
1220
1221    #[test]
1222    fn test_extend_trusted_len_sets_byte_len() {
1223        // Ensures extend_trusted_len keeps the underlying byte length in sync with bit length.
1224        let mut builder = BooleanBufferBuilder::new(0);
1225        let bools: Vec<_> = (0..10).map(|i| i % 2 == 0).collect();
1226        unsafe { builder.extend_trusted_len(bools.into_iter()) };
1227        assert_eq!(builder.as_slice().len(), bit_util::ceil(builder.len(), 8));
1228    }
1229
1230    #[test]
1231    fn test_extend_trusted_len_then_append() {
1232        // Exercises append after extend_trusted_len to validate byte length and values.
1233        let mut builder = BooleanBufferBuilder::new(0);
1234        let bools: Vec<_> = (0..9).map(|i| i % 3 == 0).collect();
1235        unsafe { builder.extend_trusted_len(bools.clone().into_iter()) };
1236        builder.append(true);
1237        assert_eq!(builder.as_slice().len(), bit_util::ceil(builder.len(), 8));
1238        let finished = builder.finish();
1239        for (i, v) in bools.into_iter().chain(std::iter::once(true)).enumerate() {
1240            assert_eq!(finished.value(i), v, "at index {i}");
1241        }
1242    }
1243
1244    #[test]
1245    fn test_find_nth_set_bit_position() {
1246        let bools = vec![true, false, true, true, false, true];
1247        let buffer = BooleanBuffer::from(bools);
1248
1249        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 1), 1);
1250        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 2), 3);
1251        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 3), 4);
1252        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 4), 6);
1253        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 5), 6);
1254
1255        assert_eq!(buffer.clone().find_nth_set_bit_position(1, 1), 3);
1256        assert_eq!(buffer.clone().find_nth_set_bit_position(3, 1), 4);
1257        assert_eq!(buffer.clone().find_nth_set_bit_position(3, 2), 6);
1258    }
1259
1260    #[test]
1261    fn test_find_nth_set_bit_position_large() {
1262        let mut bools = vec![false; 1000];
1263        bools[100] = true;
1264        bools[500] = true;
1265        bools[999] = true;
1266        let buffer = BooleanBuffer::from(bools);
1267
1268        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 1), 101);
1269        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 2), 501);
1270        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 3), 1000);
1271        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 4), 1000);
1272
1273        assert_eq!(buffer.clone().find_nth_set_bit_position(101, 1), 501);
1274    }
1275
1276    #[test]
1277    fn test_find_nth_set_bit_position_sliced() {
1278        let bools = vec![false, true, false, true, true, false, true]; // [F, T, F, T, T, F, T]
1279        let buffer = BooleanBuffer::from(bools);
1280        let slice = buffer.slice(1, 6); // [T, F, T, T, F, T]
1281
1282        assert_eq!(slice.len(), 6);
1283        // Logical indices: 0, 1, 2, 3, 4, 5
1284        // Logical values: T, F, T, T, F, T
1285
1286        assert_eq!(slice.clone().find_nth_set_bit_position(0, 1), 1);
1287        assert_eq!(slice.clone().find_nth_set_bit_position(0, 2), 3);
1288        assert_eq!(slice.clone().find_nth_set_bit_position(0, 3), 4);
1289        assert_eq!(slice.clone().find_nth_set_bit_position(0, 4), 6);
1290    }
1291
1292    #[test]
1293    fn test_find_nth_set_bit_position_all_set() {
1294        let buffer = BooleanBuffer::new_set(100);
1295        for i in 1..=100 {
1296            assert_eq!(buffer.clone().find_nth_set_bit_position(0, i), i);
1297        }
1298        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 101), 100);
1299    }
1300
1301    #[test]
1302    fn test_find_nth_set_bit_position_none_set() {
1303        let buffer = BooleanBuffer::new_unset(100);
1304        assert_eq!(buffer.clone().find_nth_set_bit_position(0, 1), 100);
1305    }
1306
1307    #[test]
1308    fn test_has_true_has_false_all_true() {
1309        let arr = BooleanBuffer::from(vec![true, true, true]);
1310        assert!(arr.has_true());
1311        assert!(!arr.has_false());
1312    }
1313
1314    #[test]
1315    fn test_has_true_has_false_all_false() {
1316        let arr = BooleanBuffer::from(vec![false, false, false]);
1317        assert!(!arr.has_true());
1318        assert!(arr.has_false());
1319    }
1320
1321    #[test]
1322    fn test_has_true_has_false_mixed() {
1323        let arr = BooleanBuffer::from(vec![true, false, true]);
1324        assert!(arr.has_true());
1325        assert!(arr.has_false());
1326    }
1327
1328    #[test]
1329    fn test_has_true_has_false_empty() {
1330        let arr = BooleanBuffer::from(Vec::<bool>::new());
1331        assert!(!arr.has_true());
1332        assert!(!arr.has_false());
1333    }
1334
1335    #[test]
1336    fn test_has_false_aligned_suffix_all_true() {
1337        let arr = BooleanBuffer::from(vec![true; 129]);
1338        assert!(arr.has_true());
1339        assert!(!arr.has_false());
1340    }
1341
1342    #[test]
1343    fn test_has_false_non_aligned_all_true() {
1344        // 65 elements: exercises the remainder path in has_false
1345        let arr = BooleanBuffer::from(vec![true; 65]);
1346        assert!(arr.has_true());
1347        assert!(!arr.has_false());
1348    }
1349
1350    #[test]
1351    fn test_has_false_non_aligned_last_false() {
1352        // 64 trues + 1 false: remainder path should find the false
1353        let mut values = vec![true; 64];
1354        values.push(false);
1355        let arr = BooleanBuffer::from(values);
1356        assert!(arr.has_true());
1357        assert!(arr.has_false());
1358    }
1359
1360    #[test]
1361    fn test_has_false_exact_64_all_true() {
1362        // Exactly 64 elements, no remainder
1363        let arr = BooleanBuffer::from(vec![true; 64]);
1364        assert!(arr.has_true());
1365        assert!(!arr.has_false());
1366    }
1367
1368    #[test]
1369    fn test_has_true_has_false_unaligned_slices() {
1370        let cases = [
1371            (1, 129, true, false),
1372            (3, 130, true, false),
1373            (5, 65, true, false),
1374            (7, 64, true, false),
1375        ];
1376
1377        let base = BooleanBuffer::from(vec![true; 300]);
1378
1379        for (offset, len, expected_has_true, expected_has_false) in cases {
1380            let arr = base.slice(offset, len);
1381            assert_eq!(
1382                arr.has_true(),
1383                expected_has_true,
1384                "offset={offset} len={len}"
1385            );
1386            assert_eq!(
1387                arr.has_false(),
1388                expected_has_false,
1389                "offset={offset} len={len}"
1390            );
1391        }
1392    }
1393
1394    #[test]
1395    fn test_has_true_has_false_exact_multiples_of_64() {
1396        let cases = [
1397            (64, true, false),
1398            (128, true, false),
1399            (192, true, false),
1400            (256, true, false),
1401        ];
1402
1403        for (len, expected_has_true, expected_has_false) in cases {
1404            let arr = BooleanBuffer::from(vec![true; len]);
1405            assert_eq!(arr.has_true(), expected_has_true, "len={len}");
1406            assert_eq!(arr.has_false(), expected_has_false, "len={len}");
1407        }
1408    }
1409}