Skip to main content

arrow_buffer/util/
bit_iterator.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
5//! Types for iterating over packed bitmasks
6
7use crate::bit_chunk_iterator::{UnalignedBitChunk, UnalignedBitChunkIterator};
8use crate::bit_util::{ceil, get_bit_raw};
9
10/// Iterator over the bits within a packed bitmask
11///
12/// To efficiently iterate over just the set bits see [`BitIndexIterator`] and [`BitSliceIterator`]
13#[derive(Clone)]
14pub struct BitIterator<'a> {
15    buffer: &'a [u8],
16    current_offset: usize,
17    end_offset: usize,
18}
19
20impl<'a> BitIterator<'a> {
21    /// Create a new [`BitIterator`] from the provided `buffer`,
22    /// and `offset` and `len` in bits
23    ///
24    /// # Panics
25    ///
26    /// Panics if `buffer` is too short for the provided offset and length
27    pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
28        let end_offset = offset.checked_add(len).unwrap();
29        let required_len = ceil(end_offset, 8);
30        assert!(
31            buffer.len() >= required_len,
32            "BitIterator buffer too small, expected {required_len} got {}",
33            buffer.len()
34        );
35
36        Self {
37            buffer,
38            current_offset: offset,
39            end_offset,
40        }
41    }
42}
43
44impl Iterator for BitIterator<'_> {
45    type Item = bool;
46
47    #[inline]
48    fn next(&mut self) -> Option<Self::Item> {
49        if self.current_offset == self.end_offset {
50            return None;
51        }
52        // Safety:
53        // offsets in bounds
54        let v = unsafe { get_bit_raw(self.buffer.as_ptr(), self.current_offset) };
55        self.current_offset += 1;
56        Some(v)
57    }
58
59    fn size_hint(&self) -> (usize, Option<usize>) {
60        let remaining_bits = self.end_offset - self.current_offset;
61        (remaining_bits, Some(remaining_bits))
62    }
63
64    fn count(self) -> usize
65    where
66        Self: Sized,
67    {
68        self.len()
69    }
70
71    #[inline]
72    fn nth(&mut self, n: usize) -> Option<Self::Item> {
73        // Check if we can advance to the desired offset.
74        // When n is 0 it means we want the next() value
75        // and when n is 1 we want the next().next() value
76        // so adding n to the current offset and not n - 1
77        match self.current_offset.checked_add(n) {
78            // Yes, and still within bounds
79            Some(new_offset) if new_offset < self.end_offset => {
80                self.current_offset = new_offset;
81            }
82
83            // Either overflow or would exceed end_offset
84            _ => {
85                self.current_offset = self.end_offset;
86                return None;
87            }
88        }
89
90        self.next()
91    }
92
93    fn last(mut self) -> Option<Self::Item> {
94        // If already at the end, return None
95        if self.current_offset == self.end_offset {
96            return None;
97        }
98
99        // Go to the one before the last bit
100        self.current_offset = self.end_offset - 1;
101
102        // Return the last bit
103        self.next()
104    }
105
106    fn max(self) -> Option<Self::Item>
107    where
108        Self: Sized,
109        Self::Item: Ord,
110    {
111        if self.current_offset == self.end_offset {
112            return None;
113        }
114
115        // true is greater than false so we only need to check if there's any true bit
116        let mut bit_index_iter = BitIndexIterator::new(
117            self.buffer,
118            self.current_offset,
119            self.end_offset - self.current_offset,
120        );
121
122        if bit_index_iter.next().is_some() {
123            return Some(true);
124        }
125
126        // We know the iterator is not empty and there are no set bits so false is the max
127        Some(false)
128    }
129}
130
131impl ExactSizeIterator for BitIterator<'_> {}
132
133impl DoubleEndedIterator for BitIterator<'_> {
134    fn next_back(&mut self) -> Option<Self::Item> {
135        if self.current_offset == self.end_offset {
136            return None;
137        }
138        self.end_offset -= 1;
139        // Safety:
140        // offsets in bounds
141        let v = unsafe { get_bit_raw(self.buffer.as_ptr(), self.end_offset) };
142        Some(v)
143    }
144
145    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
146        // Check if we can advance to the desired offset.
147        // When n is 0 it means we want the next_back() value
148        // and when n is 1 we want the next_back().next_back() value
149        // so subtracting n to the current offset and not n - 1
150        match self.end_offset.checked_sub(n) {
151            // Yes, and still within bounds
152            Some(new_offset) if self.current_offset < new_offset => {
153                self.end_offset = new_offset;
154            }
155
156            // Either underflow or would exceed current_offset
157            _ => {
158                self.current_offset = self.end_offset;
159                return None;
160            }
161        }
162
163        self.next_back()
164    }
165}
166
167/// Iterator of contiguous ranges of set bits within a provided packed bitmask
168///
169/// Returns `(usize, usize)` each representing an interval where the corresponding
170/// bits in the provides mask are set
171///
172/// the first value is the start of the range (inclusive) and the second value is the end of the range (exclusive)
173///
174#[derive(Debug)]
175pub struct BitSliceIterator<'a> {
176    iter: UnalignedBitChunkIterator<'a>,
177    len: usize,
178    current_offset: i64,
179    current_chunk: u64,
180}
181
182impl<'a> BitSliceIterator<'a> {
183    /// Create a new [`BitSliceIterator`] from the provided `buffer`,
184    /// and `offset` and `len` in bits
185    #[inline]
186    pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
187        let chunk = UnalignedBitChunk::new(buffer, offset, len);
188        let mut iter = chunk.iter();
189
190        let current_offset = -(chunk.lead_padding() as i64);
191        let current_chunk = iter.next().unwrap_or(0);
192
193        Self {
194            iter,
195            len,
196            current_offset,
197            current_chunk,
198        }
199    }
200
201    /// Returns `Some((chunk_offset, bit_offset))` for the next chunk that has at
202    /// least one bit set, or None if there is no such chunk.
203    ///
204    /// Where `chunk_offset` is the bit offset to the current `u64` chunk
205    /// and `bit_offset` is the offset of the first `1` bit in that chunk
206    #[inline]
207    fn advance_to_set_bit(&mut self) -> Option<(i64, u32)> {
208        loop {
209            if self.current_chunk != 0 {
210                // Find the index of the first 1
211                let bit_pos = self.current_chunk.trailing_zeros();
212                return Some((self.current_offset, bit_pos));
213            }
214
215            self.current_chunk = self.iter.next()?;
216            self.current_offset += 64;
217        }
218    }
219}
220
221impl Iterator for BitSliceIterator<'_> {
222    type Item = (usize, usize);
223
224    #[inline]
225    fn next(&mut self) -> Option<Self::Item> {
226        // Used as termination condition
227        if self.len == 0 {
228            return None;
229        }
230
231        let (start_chunk, start_bit) = self.advance_to_set_bit()?;
232
233        // Set bits up to start
234        self.current_chunk |= (1 << start_bit) - 1;
235
236        loop {
237            if self.current_chunk != u64::MAX {
238                // Find the index of the first 0
239                let end_bit = self.current_chunk.trailing_ones();
240
241                // Zero out up to end_bit
242                self.current_chunk &= !((1 << end_bit) - 1);
243
244                return Some((
245                    (start_chunk + start_bit as i64) as usize,
246                    (self.current_offset + end_bit as i64) as usize,
247                ));
248            }
249
250            match self.iter.next() {
251                Some(next) => {
252                    self.current_chunk = next;
253                    self.current_offset += 64;
254                }
255                None => {
256                    return Some((
257                        (start_chunk + start_bit as i64) as usize,
258                        std::mem::replace(&mut self.len, 0),
259                    ));
260                }
261            }
262        }
263    }
264}
265
266/// An iterator of `usize` whose index in a provided bitmask is true
267///
268/// This provides the best performance on most masks, apart from those which contain
269/// large runs and therefore favour [`BitSliceIterator`]
270#[derive(Debug)]
271pub struct BitIndexIterator<'a> {
272    current_chunk: u64,
273    chunk_offset: i64,
274    iter: UnalignedBitChunkIterator<'a>,
275}
276
277impl<'a> BitIndexIterator<'a> {
278    /// Create a new [`BitIndexIterator`] from the provide `buffer`,
279    /// and `offset` and `len` in bits
280    pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
281        let chunks = UnalignedBitChunk::new(buffer, offset, len);
282        let mut iter = chunks.iter();
283
284        let current_chunk = iter.next().unwrap_or(0);
285        let chunk_offset = -(chunks.lead_padding() as i64);
286
287        Self {
288            current_chunk,
289            chunk_offset,
290            iter,
291        }
292    }
293}
294
295impl Iterator for BitIndexIterator<'_> {
296    type Item = usize;
297
298    #[inline(always)]
299    fn next(&mut self) -> Option<Self::Item> {
300        loop {
301            if self.current_chunk != 0 {
302                let bit_pos = self.current_chunk.trailing_zeros();
303                self.current_chunk &= self.current_chunk - 1;
304                return Some((self.chunk_offset + bit_pos as i64) as usize);
305            }
306
307            self.current_chunk = self.iter.next()?;
308            self.chunk_offset += 64;
309        }
310    }
311}
312
313/// An iterator of u32 whose index in a provided bitmask is true
314/// Respects arbitrary offsets and slice lead/trail padding exactly like BitIndexIterator
315#[derive(Debug)]
316pub struct BitIndexU32Iterator<'a> {
317    curr: u64,
318    chunk_offset: i64,
319    iter: UnalignedBitChunkIterator<'a>,
320}
321
322impl<'a> BitIndexU32Iterator<'a> {
323    /// Create a new [BitIndexU32Iterator] from the provided buffer,
324    /// offset and len in bits.
325    pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
326        // Build the aligned chunks (including prefix/suffix masked)
327        let chunks = UnalignedBitChunk::new(buffer, offset, len);
328        let mut iter = chunks.iter();
329
330        // First 64-bit word (masked for lead padding), or 0 if empty
331        let curr = iter.next().unwrap_or(0);
332        // Negative lead padding ensures the first bit in curr maps to index 0
333        let chunk_offset = -(chunks.lead_padding() as i64);
334
335        Self {
336            curr,
337            chunk_offset,
338            iter,
339        }
340    }
341}
342
343impl Iterator for BitIndexU32Iterator<'_> {
344    type Item = u32;
345
346    #[inline(always)]
347    fn next(&mut self) -> Option<u32> {
348        loop {
349            if self.curr != 0 {
350                // Position of least-significant set bit
351                let tz = self.curr.trailing_zeros();
352                // Clear that bit
353                self.curr &= self.curr - 1;
354                // Return global index = chunk_offset + tz
355                return Some((self.chunk_offset + tz as i64) as u32);
356            }
357            // Advance to next 64-bit chunk
358            let next_chunk = self.iter.next()?;
359            // Move offset forward by 64 bits
360            self.chunk_offset += 64;
361            self.curr = next_chunk;
362        }
363    }
364}
365
366/// Calls the provided closure for each index in the provided null mask that is set,
367/// using an adaptive strategy based on the null count
368///
369/// Ideally this would be encapsulated in an [`Iterator`] that would determine the optimal
370/// strategy up front, and then yield indexes based on this.
371///
372/// Unfortunately, external iteration based on the resulting [`Iterator`] would match the strategy
373/// variant on each call to [`Iterator::next`], and LLVM generally cannot eliminate this.
374///
375/// One solution to this might be internal iteration, e.g. [`Iterator::try_fold`], however,
376/// it is currently [not possible] to override this for custom iterators in stable Rust.
377///
378/// As such this is the next best option
379///
380/// [not possible]: https://github.com/rust-lang/rust/issues/69595
381#[inline]
382pub fn try_for_each_valid_idx<E, F: FnMut(usize) -> Result<(), E>>(
383    len: usize,
384    offset: usize,
385    null_count: usize,
386    nulls: Option<&[u8]>,
387    f: F,
388) -> Result<(), E> {
389    let valid_count = len - null_count;
390
391    if valid_count == len {
392        (0..len).try_for_each(f)
393    } else if null_count != len {
394        BitIndexIterator::new(nulls.unwrap(), offset, len).try_for_each(f)
395    } else {
396        Ok(())
397    }
398}
399
400// Note: further tests located in arrow_select::filter module
401
402#[cfg(test)]
403mod tests {
404    use super::*;
405    use crate::BooleanBuffer;
406    use rand::rngs::StdRng;
407    use rand::{RngExt, SeedableRng};
408    use std::fmt::Debug;
409    use std::iter::Copied;
410    use std::slice::Iter;
411
412    #[test]
413    fn test_bit_iterator_size_hint() {
414        let mut b = BitIterator::new(&[0b00000011], 0, 2);
415        assert_eq!(
416            b.size_hint(),
417            (2, Some(2)),
418            "Expected size_hint to be (2, Some(2))"
419        );
420
421        b.next();
422        assert_eq!(
423            b.size_hint(),
424            (1, Some(1)),
425            "Expected size_hint to be (1, Some(1)) after one bit consumed"
426        );
427
428        b.next();
429        assert_eq!(
430            b.size_hint(),
431            (0, Some(0)),
432            "Expected size_hint to be (0, Some(0)) after all bits consumed"
433        );
434    }
435
436    #[test]
437    fn test_bit_iterator() {
438        let mask = &[0b00010010, 0b00100011, 0b00000101, 0b00010001, 0b10010011];
439        let actual: Vec<_> = BitIterator::new(mask, 0, 5).collect();
440        assert_eq!(actual, &[false, true, false, false, true]);
441
442        let actual: Vec<_> = BitIterator::new(mask, 4, 5).collect();
443        assert_eq!(actual, &[true, false, false, false, true]);
444
445        let actual: Vec<_> = BitIterator::new(mask, 12, 14).collect();
446        assert_eq!(
447            actual,
448            &[
449                false, true, false, false, true, false, true, false, false, false, false, false,
450                true, false
451            ]
452        );
453
454        assert_eq!(BitIterator::new(mask, 0, 0).count(), 0);
455        assert_eq!(BitIterator::new(mask, 40, 0).count(), 0);
456    }
457
458    #[test]
459    #[should_panic(expected = "BitIterator buffer too small, expected 3 got 2")]
460    fn test_bit_iterator_bounds() {
461        let mask = &[223, 23];
462        BitIterator::new(mask, 17, 0);
463    }
464
465    #[test]
466    fn test_bit_index_u32_iterator_basic() {
467        let mask = &[0b00010010, 0b00100011];
468
469        let result: Vec<u32> = BitIndexU32Iterator::new(mask, 0, 16).collect();
470        let expected: Vec<u32> = BitIndexIterator::new(mask, 0, 16)
471            .map(|i| i as u32)
472            .collect();
473        assert_eq!(result, expected);
474
475        let result: Vec<u32> = BitIndexU32Iterator::new(mask, 4, 8).collect();
476        let expected: Vec<u32> = BitIndexIterator::new(mask, 4, 8)
477            .map(|i| i as u32)
478            .collect();
479        assert_eq!(result, expected);
480
481        let result: Vec<u32> = BitIndexU32Iterator::new(mask, 10, 4).collect();
482        let expected: Vec<u32> = BitIndexIterator::new(mask, 10, 4)
483            .map(|i| i as u32)
484            .collect();
485        assert_eq!(result, expected);
486
487        let result: Vec<u32> = BitIndexU32Iterator::new(mask, 0, 0).collect();
488        let expected: Vec<u32> = BitIndexIterator::new(mask, 0, 0)
489            .map(|i| i as u32)
490            .collect();
491        assert_eq!(result, expected);
492    }
493
494    #[test]
495    fn test_bit_index_u32_iterator_all_set() {
496        let mask = &[0xFF, 0xFF];
497        let result: Vec<u32> = BitIndexU32Iterator::new(mask, 0, 16).collect();
498        let expected: Vec<u32> = BitIndexIterator::new(mask, 0, 16)
499            .map(|i| i as u32)
500            .collect();
501        assert_eq!(result, expected);
502    }
503
504    #[test]
505    fn test_bit_index_u32_iterator_none_set() {
506        let mask = &[0x00, 0x00];
507        let result: Vec<u32> = BitIndexU32Iterator::new(mask, 0, 16).collect();
508        let expected: Vec<u32> = BitIndexIterator::new(mask, 0, 16)
509            .map(|i| i as u32)
510            .collect();
511        assert_eq!(result, expected);
512    }
513
514    #[test]
515    fn test_bit_index_u32_cross_chunk() {
516        let mut buf = vec![0u8; 16];
517        for bit in 60..68 {
518            let byte = (bit / 8) as usize;
519            let bit_in_byte = bit % 8;
520            buf[byte] |= 1 << bit_in_byte;
521        }
522        let offset = 58;
523        let len = 10;
524
525        let result: Vec<u32> = BitIndexU32Iterator::new(&buf, offset, len).collect();
526        let expected: Vec<u32> = BitIndexIterator::new(&buf, offset, len)
527            .map(|i| i as u32)
528            .collect();
529        assert_eq!(result, expected);
530    }
531
532    #[test]
533    fn test_bit_index_u32_unaligned_offset() {
534        let mask = &[0b0110_1100, 0b1010_0000];
535        let offset = 2;
536        let len = 12;
537
538        let result: Vec<u32> = BitIndexU32Iterator::new(mask, offset, len).collect();
539        let expected: Vec<u32> = BitIndexIterator::new(mask, offset, len)
540            .map(|i| i as u32)
541            .collect();
542        assert_eq!(result, expected);
543    }
544
545    #[test]
546    fn test_bit_index_u32_long_all_set() {
547        let len = 200;
548        let num_bytes = len / 8 + usize::from(len % 8 != 0);
549        let bytes = vec![0xFFu8; num_bytes];
550
551        let result: Vec<u32> = BitIndexU32Iterator::new(&bytes, 0, len).collect();
552        let expected: Vec<u32> = BitIndexIterator::new(&bytes, 0, len)
553            .map(|i| i as u32)
554            .collect();
555        assert_eq!(result, expected);
556    }
557
558    #[test]
559    fn test_bit_index_u32_none_set() {
560        let len = 50;
561        let num_bytes = len / 8 + usize::from(len % 8 != 0);
562        let bytes = vec![0u8; num_bytes];
563
564        let result: Vec<u32> = BitIndexU32Iterator::new(&bytes, 0, len).collect();
565        let expected: Vec<u32> = BitIndexIterator::new(&bytes, 0, len)
566            .map(|i| i as u32)
567            .collect();
568        assert_eq!(result, expected);
569    }
570
571    trait SharedBetweenBitIteratorAndSliceIter:
572        ExactSizeIterator<Item = bool> + DoubleEndedIterator<Item = bool>
573    {
574    }
575    impl<T: ?Sized + ExactSizeIterator<Item = bool> + DoubleEndedIterator<Item = bool>>
576        SharedBetweenBitIteratorAndSliceIter for T
577    {
578    }
579
580    fn get_bit_iterator_cases() -> impl Iterator<Item = (BooleanBuffer, Vec<bool>)> {
581        let mut rng = StdRng::seed_from_u64(42);
582
583        [0, 1, 6, 8, 100, 164]
584            .map(|len| {
585                let source = (0..len).map(|_| rng.random_bool(0.5)).collect::<Vec<_>>();
586
587                (BooleanBuffer::from(source.as_slice()), source)
588            })
589            .into_iter()
590    }
591
592    fn setup_and_assert(
593        setup_iters: impl Fn(&mut dyn SharedBetweenBitIteratorAndSliceIter),
594        assert_fn: impl Fn(BitIterator, Copied<Iter<bool>>),
595    ) {
596        for (boolean_buffer, source) in get_bit_iterator_cases() {
597            // Not using `boolean_buffer.iter()` in case the implementation change to not call BitIterator internally
598            // in which case the test would not test what it intends to test
599            let mut actual = BitIterator::new(boolean_buffer.values(), 0, boolean_buffer.len());
600            let mut expected = source.iter().copied();
601
602            setup_iters(&mut actual);
603            setup_iters(&mut expected);
604
605            assert_fn(actual, expected);
606        }
607    }
608
609    /// Trait representing an operation on a BitIterator
610    /// that can be compared against a slice iterator
611    trait BitIteratorOp {
612        /// What the operation returns (e.g. Option<bool> for last/max, usize for count, etc)
613        type Output: PartialEq + Debug;
614
615        /// The name of the operation, used for error messages
616        const NAME: &'static str;
617
618        /// Get the value of the operation for the provided iterator
619        /// This will be either a BitIterator or a slice iterator to make sure they produce the same result
620        fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(iter: T) -> Self::Output;
621    }
622
623    /// Helper function that will assert that the provided operation
624    /// produces the same result for both BitIterator and slice iterator
625    /// under various consumption patterns (e.g. some calls to next/next_back/consume_all/etc)
626    fn assert_bit_iterator_cases<O: BitIteratorOp>() {
627        setup_and_assert(
628            |_iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {},
629            |actual, expected| {
630                let current_iterator_values: Vec<bool> = expected.clone().collect();
631                assert_eq!(
632                    O::get_value(actual),
633                    O::get_value(expected),
634                    "Failed on op {} for new iter (left actual, right expected) ({current_iterator_values:?})",
635                    O::NAME
636                );
637            },
638        );
639
640        setup_and_assert(
641            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
642                iter.next();
643            },
644            |actual, expected| {
645                let current_iterator_values: Vec<bool> = expected.clone().collect();
646
647                assert_eq!(
648                    O::get_value(actual),
649                    O::get_value(expected),
650                    "Failed on op {} for new iter after consuming 1 element from the start (left actual, right expected) ({current_iterator_values:?})",
651                    O::NAME
652                );
653            },
654        );
655
656        setup_and_assert(
657            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
658                iter.next_back();
659            },
660            |actual, expected| {
661                let current_iterator_values: Vec<bool> = expected.clone().collect();
662
663                assert_eq!(
664                    O::get_value(actual),
665                    O::get_value(expected),
666                    "Failed on op {} for new iter after consuming 1 element from the end (left actual, right expected) ({current_iterator_values:?})",
667                    O::NAME
668                );
669            },
670        );
671
672        setup_and_assert(
673            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
674                iter.next();
675                iter.next_back();
676            },
677            |actual, expected| {
678                let current_iterator_values: Vec<bool> = expected.clone().collect();
679
680                assert_eq!(
681                    O::get_value(actual),
682                    O::get_value(expected),
683                    "Failed on op {} for new iter after consuming 1 element from start and end (left actual, right expected) ({current_iterator_values:?})",
684                    O::NAME
685                );
686            },
687        );
688
689        setup_and_assert(
690            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
691                while iter.len() > 1 {
692                    iter.next();
693                }
694            },
695            |actual, expected| {
696                let current_iterator_values: Vec<bool> = expected.clone().collect();
697
698                assert_eq!(
699                    O::get_value(actual),
700                    O::get_value(expected),
701                    "Failed on op {} for new iter after consuming all from the start but 1 (left actual, right expected) ({current_iterator_values:?})",
702                    O::NAME
703                );
704            },
705        );
706
707        setup_and_assert(
708            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
709                while iter.len() > 1 {
710                    iter.next_back();
711                }
712            },
713            |actual, expected| {
714                let current_iterator_values: Vec<bool> = expected.clone().collect();
715
716                assert_eq!(
717                    O::get_value(actual),
718                    O::get_value(expected),
719                    "Failed on op {} for new iter after consuming all from the end but 1 (left actual, right expected) ({current_iterator_values:?})",
720                    O::NAME
721                );
722            },
723        );
724
725        setup_and_assert(
726            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
727                while iter.next().is_some() {}
728            },
729            |actual, expected| {
730                let current_iterator_values: Vec<bool> = expected.clone().collect();
731
732                assert_eq!(
733                    O::get_value(actual),
734                    O::get_value(expected),
735                    "Failed on op {} for new iter after consuming all from the start (left actual, right expected) ({current_iterator_values:?})",
736                    O::NAME
737                );
738            },
739        );
740
741        setup_and_assert(
742            |iter: &mut dyn SharedBetweenBitIteratorAndSliceIter| {
743                while iter.next_back().is_some() {}
744            },
745            |actual, expected| {
746                let current_iterator_values: Vec<bool> = expected.clone().collect();
747
748                assert_eq!(
749                    O::get_value(actual),
750                    O::get_value(expected),
751                    "Failed on op {} for new iter after consuming all from the end (left actual, right expected) ({current_iterator_values:?})",
752                    O::NAME
753                );
754            },
755        );
756    }
757
758    #[test]
759    fn assert_bit_iterator_count() {
760        struct CountOp;
761
762        impl BitIteratorOp for CountOp {
763            type Output = usize;
764            const NAME: &'static str = "count";
765
766            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(iter: T) -> Self::Output {
767                iter.count()
768            }
769        }
770
771        assert_bit_iterator_cases::<CountOp>()
772    }
773
774    #[test]
775    fn assert_bit_iterator_last() {
776        struct LastOp;
777
778        impl BitIteratorOp for LastOp {
779            type Output = Option<bool>;
780            const NAME: &'static str = "last";
781
782            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(iter: T) -> Self::Output {
783                iter.last()
784            }
785        }
786
787        assert_bit_iterator_cases::<LastOp>()
788    }
789
790    #[test]
791    fn assert_bit_iterator_max() {
792        struct MaxOp;
793
794        impl BitIteratorOp for MaxOp {
795            type Output = Option<bool>;
796            const NAME: &'static str = "max";
797
798            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(iter: T) -> Self::Output {
799                iter.max()
800            }
801        }
802
803        assert_bit_iterator_cases::<MaxOp>()
804    }
805
806    #[test]
807    fn assert_bit_iterator_nth_0() {
808        struct NthOp<const BACK: bool>;
809
810        impl<const BACK: bool> BitIteratorOp for NthOp<BACK> {
811            type Output = Option<bool>;
812            const NAME: &'static str = if BACK { "nth_back(0)" } else { "nth(0)" };
813
814            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(mut iter: T) -> Self::Output {
815                if BACK { iter.nth_back(0) } else { iter.nth(0) }
816            }
817        }
818
819        assert_bit_iterator_cases::<NthOp<false>>();
820        assert_bit_iterator_cases::<NthOp<true>>();
821    }
822
823    #[test]
824    fn assert_bit_iterator_nth_1() {
825        struct NthOp<const BACK: bool>;
826
827        impl<const BACK: bool> BitIteratorOp for NthOp<BACK> {
828            type Output = Option<bool>;
829            const NAME: &'static str = if BACK { "nth_back(1)" } else { "nth(1)" };
830
831            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(mut iter: T) -> Self::Output {
832                if BACK { iter.nth_back(1) } else { iter.nth(1) }
833            }
834        }
835
836        assert_bit_iterator_cases::<NthOp<false>>();
837        assert_bit_iterator_cases::<NthOp<true>>();
838    }
839
840    #[test]
841    fn assert_bit_iterator_nth_after_end() {
842        struct NthOp<const BACK: bool>;
843
844        impl<const BACK: bool> BitIteratorOp for NthOp<BACK> {
845            type Output = Option<bool>;
846            const NAME: &'static str = if BACK {
847                "nth_back(iter.len() + 1)"
848            } else {
849                "nth(iter.len() + 1)"
850            };
851
852            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(mut iter: T) -> Self::Output {
853                if BACK {
854                    iter.nth_back(iter.len() + 1)
855                } else {
856                    iter.nth(iter.len() + 1)
857                }
858            }
859        }
860
861        assert_bit_iterator_cases::<NthOp<false>>();
862        assert_bit_iterator_cases::<NthOp<true>>();
863    }
864
865    #[test]
866    fn assert_bit_iterator_nth_len() {
867        struct NthOp<const BACK: bool>;
868
869        impl<const BACK: bool> BitIteratorOp for NthOp<BACK> {
870            type Output = Option<bool>;
871            const NAME: &'static str = if BACK {
872                "nth_back(iter.len())"
873            } else {
874                "nth(iter.len())"
875            };
876
877            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(mut iter: T) -> Self::Output {
878                if BACK {
879                    iter.nth_back(iter.len())
880                } else {
881                    iter.nth(iter.len())
882                }
883            }
884        }
885
886        assert_bit_iterator_cases::<NthOp<false>>();
887        assert_bit_iterator_cases::<NthOp<true>>();
888    }
889
890    #[test]
891    fn assert_bit_iterator_nth_last() {
892        struct NthOp<const BACK: bool>;
893
894        impl<const BACK: bool> BitIteratorOp for NthOp<BACK> {
895            type Output = Option<bool>;
896            const NAME: &'static str = if BACK {
897                "nth_back(iter.len().saturating_sub(1))"
898            } else {
899                "nth(iter.len().saturating_sub(1))"
900            };
901
902            fn get_value<T: SharedBetweenBitIteratorAndSliceIter>(mut iter: T) -> Self::Output {
903                if BACK {
904                    iter.nth_back(iter.len().saturating_sub(1))
905                } else {
906                    iter.nth(iter.len().saturating_sub(1))
907                }
908            }
909        }
910
911        assert_bit_iterator_cases::<NthOp<false>>();
912        assert_bit_iterator_cases::<NthOp<true>>();
913    }
914
915    #[test]
916    fn assert_bit_iterator_nth_and_reuse() {
917        setup_and_assert(
918            |_| {},
919            |actual, expected| {
920                {
921                    let mut actual = actual.clone();
922                    let mut expected = expected.clone();
923                    for _ in 0..expected.len() {
924                        #[expect(clippy::iter_nth_zero)]
925                        let actual_val = actual.nth(0);
926                        #[expect(clippy::iter_nth_zero)]
927                        let expected_val = expected.nth(0);
928                        assert_eq!(actual_val, expected_val, "Failed on nth(0)");
929                    }
930                }
931
932                {
933                    let mut actual = actual.clone();
934                    let mut expected = expected.clone();
935                    for _ in 0..expected.len() {
936                        let actual_val = actual.nth(1);
937                        let expected_val = expected.nth(1);
938                        assert_eq!(actual_val, expected_val, "Failed on nth(1)");
939                    }
940                }
941
942                {
943                    let mut actual = actual.clone();
944                    let mut expected = expected.clone();
945                    for _ in 0..expected.len() {
946                        let actual_val = actual.nth(2);
947                        let expected_val = expected.nth(2);
948                        assert_eq!(actual_val, expected_val, "Failed on nth(2)");
949                    }
950                }
951            },
952        );
953    }
954
955    #[test]
956    fn assert_bit_iterator_nth_back_and_reuse() {
957        setup_and_assert(
958            |_| {},
959            |actual, expected| {
960                {
961                    let mut actual = actual.clone();
962                    let mut expected = expected.clone();
963                    for _ in 0..expected.len() {
964                        let actual_val = actual.nth_back(0);
965                        let expected_val = expected.nth_back(0);
966                        assert_eq!(actual_val, expected_val, "Failed on nth_back(0)");
967                    }
968                }
969
970                {
971                    let mut actual = actual.clone();
972                    let mut expected = expected.clone();
973                    for _ in 0..expected.len() {
974                        let actual_val = actual.nth_back(1);
975                        let expected_val = expected.nth_back(1);
976                        assert_eq!(actual_val, expected_val, "Failed on nth_back(1)");
977                    }
978                }
979
980                {
981                    let mut actual = actual.clone();
982                    let mut expected = expected.clone();
983                    for _ in 0..expected.len() {
984                        let actual_val = actual.nth_back(2);
985                        let expected_val = expected.nth_back(2);
986                        assert_eq!(actual_val, expected_val, "Failed on nth_back(2)");
987                    }
988                }
989            },
990        );
991    }
992}