1use std::convert::Infallible;
5use std::fmt::Display;
6use std::fmt::Formatter;
7use std::fmt::Result as FmtResult;
8use std::ops::BitAnd;
9use std::ops::BitOr;
10use std::ops::BitXor;
11use std::ops::Not;
12use std::ops::RangeBounds;
13
14use crate::Alignment;
15use crate::BitBufferMeta;
16use crate::BitBufferMut;
17use crate::Buffer;
18use crate::BufferAllocatorRef;
19use crate::BufferMut;
20use crate::ByteBuffer;
21use crate::bit::BitChunks;
22use crate::bit::BitIndexIterator;
23use crate::bit::BitIterator;
24use crate::bit::BitSliceIterator;
25use crate::bit::UnalignedBitChunk;
26use crate::bit::collect_bool_word;
27use crate::bit::count_ones::count_ones;
28use crate::bit::get_bit_unchecked;
29use crate::bit::ops::bitwise_binary_op;
30use crate::bit::ops::bitwise_binary_op_lhs_owned;
31use crate::bit::ops::bitwise_unary_op;
32use crate::bit::ops::bitwise_unary_op_copy;
33use crate::bit::select::bit_select;
34use crate::bit::select::bit_select_unset;
35
36#[derive(Debug, Clone, Eq)]
38#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
39pub struct BitBuffer {
40 buffer: ByteBuffer,
41 offset: usize,
45 len: usize,
46}
47
48const LIMIT_LEN: usize = 16;
49impl Display for BitBuffer {
50 fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
51 let limit = f.precision().unwrap_or(LIMIT_LEN);
52 let buf: Vec<bool> = self.into_iter().take(limit).collect();
53 f.debug_struct("BitBuffer")
54 .field("len", &self.len)
55 .field("buffer", &buf)
56 .finish()
57 }
58}
59
60impl PartialEq for BitBuffer {
61 fn eq(&self, other: &Self) -> bool {
62 if self.len != other.len {
63 return false;
64 }
65
66 if self.len == 0 {
67 return true;
68 }
69
70 if self.offset == 0 && other.offset == 0 {
72 let full_bytes = self.len / 8;
73 let self_bytes = &self.buffer.as_slice()[..full_bytes];
74 let other_bytes = &other.buffer.as_slice()[..full_bytes];
75 if self_bytes != other_bytes {
76 return false;
77 }
78 let rem = self.len % 8;
80 if rem != 0 {
81 let mask = (1u8 << rem) - 1;
82 let a = self.buffer.as_slice()[full_bytes] & mask;
83 let b = other.buffer.as_slice()[full_bytes] & mask;
84 return a == b;
85 }
86 return true;
87 }
88
89 self.chunks()
90 .iter_padded()
91 .zip(other.chunks().iter_padded())
92 .all(|(a, b)| a == b)
93 }
94}
95
96impl BitBuffer {
97 #[inline]
101 pub fn new(buffer: ByteBuffer, len: usize) -> Self {
102 assert!(
103 buffer.len() * 8 >= len,
104 "provided ByteBuffer not large enough to back BoolBuffer with len {len}"
105 );
106
107 let buffer = buffer.aligned(Alignment::none());
109
110 Self {
111 buffer,
112 len,
113 offset: 0,
114 }
115 }
116
117 #[inline]
122 pub fn new_with_offset(buffer: ByteBuffer, len: usize, offset: usize) -> Self {
123 assert!(
124 len.saturating_add(offset) <= buffer.len().saturating_mul(8),
125 "provided ByteBuffer (len={}) not large enough to back BoolBuffer with offset {offset} len {len}",
126 buffer.len()
127 );
128
129 let buffer = buffer.aligned(Alignment::none());
131
132 let byte_offset = offset / 8;
134 let offset = offset % 8;
135 let buffer = if byte_offset != 0 {
136 buffer.slice(byte_offset..)
137 } else {
138 buffer
139 };
140
141 Self {
142 buffer,
143 offset,
144 len,
145 }
146 }
147
148 #[inline]
150 pub fn new_set(len: usize) -> Self {
151 Self::new_set_in(len, BufferAllocatorRef::statically_allocated())
152 }
153
154 #[inline]
156 pub fn new_set_in(len: usize, allocator: BufferAllocatorRef) -> Self {
157 let words = len.div_ceil(8);
158 let buffer = Buffer::full_in(0xFF, words, allocator);
159
160 Self {
161 buffer,
162 len,
163 offset: 0,
164 }
165 }
166
167 #[inline]
169 pub fn new_unset(len: usize) -> Self {
170 Self::new_unset_in(len, BufferAllocatorRef::statically_allocated())
171 }
172
173 #[inline]
175 pub fn new_unset_in(len: usize, allocator: BufferAllocatorRef) -> Self {
176 let words = len.div_ceil(8);
177 let buffer = Buffer::zeroed_in(words, allocator);
178
179 Self {
180 buffer,
181 len,
182 offset: 0,
183 }
184 }
185
186 pub fn from_indices(len: usize, indices: impl IntoIterator<Item = usize>) -> BitBuffer {
188 BitBufferMut::from_indices(len, indices).freeze()
189 }
190
191 #[inline]
193 pub fn empty() -> Self {
194 Self::new_set(0)
195 }
196
197 #[inline]
199 pub fn full(value: bool, len: usize) -> Self {
200 Self::full_in(value, len, BufferAllocatorRef::statically_allocated())
201 }
202
203 #[inline]
205 pub fn full_in(value: bool, len: usize, allocator: BufferAllocatorRef) -> Self {
206 if value {
207 Self::new_set_in(len, allocator)
208 } else {
209 Self::new_unset_in(len, allocator)
210 }
211 }
212
213 #[inline]
239 pub fn collect_bool<F: FnMut(usize) -> bool>(len: usize, f: F) -> Self {
240 BitBufferMut::collect_bool(len, f).freeze()
241 }
242
243 #[inline]
245 pub fn collect_bool_in<F: FnMut(usize) -> bool>(
246 len: usize,
247 f: F,
248 allocator: BufferAllocatorRef,
249 ) -> Self {
250 BitBufferMut::collect_bool_in(len, f, allocator).freeze()
251 }
252
253 #[inline]
264 pub fn collect_bool_multiversioned<F: FnMut(usize) -> bool>(len: usize, f: F) -> Self {
265 Self::collect_bool_multiversioned_in(len, f, BufferAllocatorRef::statically_allocated())
266 }
267
268 #[inline]
270 pub fn collect_bool_multiversioned_in<F: FnMut(usize) -> bool>(
271 len: usize,
272 f: F,
273 allocator: BufferAllocatorRef,
274 ) -> Self {
275 BitBufferMut::collect_bool_multiversioned_in(len, f, allocator).freeze()
276 }
277
278 pub fn map_cmp<F>(&self, mut f: F) -> Self
283 where
284 F: FnMut(usize, bool) -> bool,
285 {
286 let len = self.len;
287 let mut buffer: BufferMut<u64> = BufferMut::with_capacity(len.div_ceil(64));
288
289 let chunks_count = len / 64;
290 let remainder = len % 64;
291 let chunks = self.chunks();
292
293 for (chunk_idx, src_chunk) in chunks.iter().enumerate() {
294 let packed = collect_bool_word(64, |bit_idx| {
295 let i = bit_idx + chunk_idx * 64;
296 let bit_value = (src_chunk >> bit_idx) & 1 == 1;
297 f(i, bit_value)
298 });
299
300 unsafe { buffer.push_unchecked(packed) }
302 }
303
304 if remainder != 0 {
305 let src_chunk = chunks.remainder_bits();
306 let packed = collect_bool_word(remainder, |bit_idx| {
307 let i = bit_idx + chunks_count * 64;
308 let bit_value = (src_chunk >> bit_idx) & 1 == 1;
309 f(i, bit_value)
310 });
311
312 unsafe { buffer.push_unchecked(packed) }
314 }
315
316 let mut bytes = buffer.into_byte_buffer();
317 bytes.truncate(len.div_ceil(8));
318
319 Self {
320 buffer: bytes.freeze(),
321 offset: 0,
322 len,
323 }
324 }
325
326 #[inline]
328 pub fn clear(&mut self) {
329 self.buffer.clear();
330 self.len = 0;
331 self.offset = 0;
332 }
333
334 #[inline]
339 pub fn len(&self) -> usize {
340 self.len
341 }
342
343 #[inline]
345 pub fn is_empty(&self) -> bool {
346 self.len() == 0
347 }
348
349 #[allow(clippy::inline_always)]
351 #[inline(always)]
352 pub fn offset(&self) -> usize {
353 self.offset
354 }
355
356 #[allow(clippy::inline_always)]
358 #[inline(always)]
359 pub fn inner(&self) -> &ByteBuffer {
360 &self.buffer
361 }
362
363 #[inline]
369 pub fn byte_aligned_bytes(&self) -> Option<&[u8]> {
370 if !self.offset.is_multiple_of(8) {
371 return None;
372 }
373
374 let n_bytes = self.len.div_ceil(8);
375 let start = self.offset / 8;
376 let end = start + n_bytes;
377 Some(&self.buffer.as_slice()[start..end])
378 }
379
380 #[inline]
386 pub fn value(&self, index: usize) -> bool {
387 assert!(index < self.len);
388 unsafe { self.value_unchecked(index) }
389 }
390
391 #[inline]
396 pub unsafe fn value_unchecked(&self, index: usize) -> bool {
397 unsafe { get_bit_unchecked(self.buffer.as_ptr(), index + self.offset) }
398 }
399
400 #[inline]
405 pub fn slice(&self, range: impl RangeBounds<usize>) -> Self {
406 let (byte_offset, meta) = BitBufferMeta::new(self.offset, self.len).slice(range);
407
408 let buffer = if byte_offset != 0 {
411 self.buffer.slice_unaligned(byte_offset..)
412 } else {
413 self.buffer.clone().aligned(Alignment::none())
414 };
415
416 Self {
417 buffer,
418 offset: meta.offset(),
419 len: meta.len(),
420 }
421 }
422
423 pub fn shrink_offset(self) -> Self {
425 let word_start = self.offset / 8;
426 let word_end = (self.offset + self.len).div_ceil(8);
427
428 let buffer = self.buffer.slice(word_start..word_end);
429
430 let bit_offset = self.offset % 8;
431 let len = self.len;
432 BitBuffer::new_with_offset(buffer, len, bit_offset)
433 }
434
435 #[inline]
437 pub fn unaligned_chunks(&self) -> UnalignedBitChunk<'_> {
438 UnalignedBitChunk::new(self.buffer.as_slice(), self.offset, self.len)
439 }
440
441 #[inline]
445 pub fn chunks(&self) -> BitChunks<'_> {
446 BitChunks::new(self.buffer.as_slice(), self.offset, self.len)
447 }
448
449 #[inline]
451 pub fn true_count(&self) -> usize {
452 count_ones(self.buffer.as_slice(), self.offset, self.len)
453 }
454
455 #[inline]
463 pub fn count_range(&self, start: usize, end: usize) -> usize {
464 assert!(start <= end, "start {start} exceeds end {end}");
465 assert!(end <= self.len, "end {end} exceeds len {}", self.len);
466 count_ones(self.buffer.as_slice(), self.offset + start, end - start)
467 }
468
469 #[inline]
476 pub fn select(&self, nth: usize) -> Option<usize> {
477 bit_select(self.buffer.as_slice(), self.offset, self.len, nth)
478 }
479
480 #[inline]
487 pub fn select_unset(&self, nth: usize) -> Option<usize> {
488 bit_select_unset(self.buffer.as_slice(), self.offset, self.len, nth)
489 }
490
491 #[inline]
496 pub fn last_set_index(&self) -> Option<usize> {
497 let chunks = self.unaligned_chunks();
498 let lead = chunks.lead_padding();
499 let prefix_words = usize::from(chunks.prefix().is_some());
500
501 if let Some(word) = chunks.suffix()
502 && word != 0
503 {
504 let word_index = prefix_words + chunks.chunks().len();
505 return Some(word_index * 64 + 63 - word.leading_zeros() as usize - lead);
506 }
507
508 for (index, &word) in chunks.chunks().iter().enumerate().rev() {
509 if word != 0 {
510 let word_index = prefix_words + index;
511 return Some(word_index * 64 + 63 - word.leading_zeros() as usize - lead);
512 }
513 }
514
515 chunks.prefix().filter(|word| *word != 0).map(|word| {
516 debug_assert!(word.trailing_zeros() as usize >= lead);
517 63 - word.leading_zeros() as usize - lead
518 })
519 }
520
521 #[inline]
523 pub fn false_count(&self) -> usize {
524 self.len - self.true_count()
525 }
526
527 #[inline]
529 pub fn iter(&self) -> BitIterator<'_> {
530 BitIterator::new(self.buffer.as_slice(), self.offset, self.len)
531 }
532
533 #[inline]
535 pub fn set_indices(&self) -> BitIndexIterator<'_> {
536 BitIndexIterator::new(self.buffer.as_slice(), self.offset, self.len)
537 }
538
539 #[inline]
541 pub fn set_slices(&self) -> BitSliceIterator<'_> {
542 BitSliceIterator::new(self.buffer.as_slice(), self.offset, self.len)
543 }
544
545 #[inline]
554 pub fn for_each_set_index<F: FnMut(usize)>(&self, mut f: F) {
555 let Ok(()) = self.try_for_each_set_index(|index| {
556 f(index);
557 Ok::<_, Infallible>(())
558 });
559 }
560
561 #[inline]
565 pub fn try_for_each_set_index<E, F>(&self, f: F) -> Result<(), E>
566 where
567 F: FnMut(usize) -> Result<(), E>,
568 {
569 self.try_for_each_index::<false, E, F>(f)
570 }
571
572 #[inline]
577 pub fn for_each_unset_index<F: FnMut(usize)>(&self, mut f: F) {
578 let Ok(()) = self.try_for_each_index::<true, _, _>(|index| {
579 f(index);
580 Ok::<_, Infallible>(())
581 });
582 }
583
584 #[inline]
587 fn try_for_each_index<const UNSET: bool, E, F>(&self, mut f: F) -> Result<(), E>
588 where
589 F: FnMut(usize) -> Result<(), E>,
590 {
591 let mut base = 0usize;
592 for word in self.chunks().iter_padded() {
593 let word = if UNSET {
594 let held = self.len - base;
597 let padding = if held < 64 { u64::MAX << held } else { 0 };
598 !(word | padding)
599 } else {
600 word
601 };
602 if word == u64::MAX {
603 for k in 0..64 {
604 f(base + k)?;
605 }
606 } else {
607 let mut w = word;
608 while w != 0 {
609 f(base + w.trailing_zeros() as usize)?;
610 w &= w - 1;
611 }
612 }
613 base += 64;
614 }
615
616 Ok(())
617 }
618
619 pub fn sliced(&self) -> Self {
621 if self.offset.is_multiple_of(8) {
622 return Self::new(
623 self.buffer
624 .slice(self.offset / 8..(self.offset + self.len).div_ceil(8)),
625 self.len,
626 );
627 }
628
629 bitwise_unary_op_copy(self, |a| a)
631 }
632}
633
634impl BitBuffer {
637 #[inline]
639 pub fn into_inner(self) -> (usize, usize, ByteBuffer) {
640 (self.offset, self.len, self.buffer)
641 }
642
643 #[inline]
645 pub fn try_into_mut(self) -> Result<BitBufferMut, Self> {
646 match self.buffer.try_into_mut() {
647 Ok(buffer) => Ok(BitBufferMut::from_buffer(buffer, self.offset, self.len)),
648 Err(buffer) => Err(BitBuffer::new_with_offset(buffer, self.len, self.offset)),
649 }
650 }
651}
652
653impl From<&[bool]> for BitBuffer {
654 fn from(value: &[bool]) -> Self {
655 BitBufferMut::from(value).freeze()
656 }
657}
658
659impl From<Vec<bool>> for BitBuffer {
660 fn from(value: Vec<bool>) -> Self {
661 BitBufferMut::from(value).freeze()
662 }
663}
664
665impl FromIterator<bool> for BitBuffer {
666 #[inline]
667 fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
668 BitBufferMut::from_iter(iter).freeze()
669 }
670}
671
672impl BitOr for BitBuffer {
673 type Output = Self;
674
675 #[inline]
676 fn bitor(self, rhs: Self) -> Self::Output {
677 bitwise_binary_op_lhs_owned(self, &rhs, |a, b| a | b)
678 }
679}
680
681impl BitOr for &BitBuffer {
682 type Output = BitBuffer;
683
684 #[inline]
685 fn bitor(self, rhs: Self) -> Self::Output {
686 bitwise_binary_op(self, rhs, |a, b| a | b)
687 }
688}
689
690impl BitOr<&BitBuffer> for BitBuffer {
691 type Output = BitBuffer;
692
693 #[inline]
694 fn bitor(self, rhs: &BitBuffer) -> Self::Output {
695 bitwise_binary_op_lhs_owned(self, rhs, |a, b| a | b)
696 }
697}
698
699impl BitAnd for &BitBuffer {
700 type Output = BitBuffer;
701
702 #[inline]
703 fn bitand(self, rhs: Self) -> Self::Output {
704 bitwise_binary_op(self, rhs, |a, b| a & b)
705 }
706}
707
708impl BitAnd<BitBuffer> for &BitBuffer {
709 type Output = BitBuffer;
710
711 #[inline]
712 fn bitand(self, rhs: BitBuffer) -> Self::Output {
713 self.bitand(&rhs)
714 }
715}
716
717impl BitAnd<&BitBuffer> for BitBuffer {
718 type Output = BitBuffer;
719
720 #[inline]
721 fn bitand(self, rhs: &BitBuffer) -> Self::Output {
722 bitwise_binary_op_lhs_owned(self, rhs, |a, b| a & b)
723 }
724}
725
726impl BitAnd<BitBuffer> for BitBuffer {
727 type Output = BitBuffer;
728
729 #[inline]
730 fn bitand(self, rhs: BitBuffer) -> Self::Output {
731 bitwise_binary_op_lhs_owned(self, &rhs, |a, b| a & b)
732 }
733}
734
735impl Not for &BitBuffer {
736 type Output = BitBuffer;
737
738 #[inline]
739 fn not(self) -> Self::Output {
740 bitwise_unary_op_copy(self, |a| !a)
743 }
744}
745
746impl Not for BitBuffer {
747 type Output = BitBuffer;
748
749 #[inline]
750 fn not(self) -> Self::Output {
751 bitwise_unary_op(self, |a| !a)
752 }
753}
754
755impl BitXor for &BitBuffer {
756 type Output = BitBuffer;
757
758 #[inline]
759 fn bitxor(self, rhs: Self) -> Self::Output {
760 bitwise_binary_op(self, rhs, |a, b| a ^ b)
761 }
762}
763
764impl BitXor<&BitBuffer> for BitBuffer {
765 type Output = BitBuffer;
766
767 #[inline]
768 fn bitxor(self, rhs: &BitBuffer) -> Self::Output {
769 bitwise_binary_op_lhs_owned(self, rhs, |a, b| a ^ b)
770 }
771}
772
773impl BitBuffer {
774 pub fn bitand_not(&self, rhs: &BitBuffer) -> BitBuffer {
779 bitwise_binary_op(self, rhs, |a, b| a & !b)
780 }
781
782 pub fn into_bitand_not(self, rhs: &BitBuffer) -> BitBuffer {
784 bitwise_binary_op_lhs_owned(self, rhs, |a, b| a & !b)
785 }
786
787 #[inline]
797 pub fn iter_bits<F>(&self, mut f: F)
798 where
799 F: FnMut(usize, bool),
800 {
801 let total_bits = self.len;
802 if total_bits == 0 {
803 return;
804 }
805
806 let chunks = self.chunks();
808 let chunks_count = total_bits / 64;
809 let remainder = total_bits % 64;
810
811 for (chunk_idx, chunk) in chunks.iter().enumerate() {
812 let base = chunk_idx * 64;
813 for bit_idx in 0..64 {
814 f(base + bit_idx, (chunk >> bit_idx) & 1 == 1);
815 }
816 }
817
818 if remainder != 0 {
819 let rem_chunk = chunks.remainder_bits();
820 let base = chunks_count * 64;
821 for bit_idx in 0..remainder {
822 f(base + bit_idx, (rem_chunk >> bit_idx) & 1 == 1);
823 }
824 }
825 }
826}
827
828impl<'a> IntoIterator for &'a BitBuffer {
829 type Item = bool;
830 type IntoIter = BitIterator<'a>;
831
832 fn into_iter(self) -> Self::IntoIter {
833 self.iter()
834 }
835}
836
837#[cfg(test)]
838mod tests {
839 use rand::RngExt;
840 use rand::SeedableRng;
841 use rand::rngs::StdRng;
842 use rstest::rstest;
843 use vortex_error::VortexResult;
844
845 use crate::ByteBuffer;
846 use crate::bit::BitBuffer;
847 use crate::buffer;
848
849 #[test]
850 fn test_bool() {
851 let buffer: ByteBuffer = buffer![1 << 7; 1024];
853 let bools = BitBuffer::new(buffer, 1024 * 8);
854
855 assert_eq!(bools.len(), 1024 * 8);
857 assert!(!bools.is_empty());
858 assert_eq!(bools.true_count(), 1024);
859 assert_eq!(bools.false_count(), 1024 * 7);
860
861 for word in 0..1024 {
863 for bit in 0..8 {
864 if bit == 7 {
865 assert!(bools.value(word * 8 + bit));
866 } else {
867 assert!(!bools.value(word * 8 + bit));
868 }
869 }
870 }
871
872 let sliced = bools.slice(64..72);
874
875 assert_eq!(sliced.len(), 8);
877 assert!(!sliced.is_empty());
878 assert_eq!(sliced.true_count(), 1);
879 assert_eq!(sliced.false_count(), 7);
880
881 for bit in 0..8 {
883 if bit == 7 {
884 assert!(sliced.value(bit));
885 } else {
886 assert!(!sliced.value(bit));
887 }
888 }
889 }
890
891 #[test]
892 fn test_padded_equaltiy() {
893 let buf1 = BitBuffer::new_set(64); let buf2 = BitBuffer::collect_bool(64, |x| x < 32); for i in 0..32 {
897 assert_eq!(buf1.value(i), buf2.value(i), "Bit {} should be the same", i);
898 }
899
900 for i in 32..64 {
901 assert_ne!(buf1.value(i), buf2.value(i), "Bit {} should differ", i);
902 }
903
904 assert_eq!(
905 buf1.slice(0..32),
906 buf2.slice(0..32),
907 "Buffer slices with same bits should be equal (`PartialEq` needs `iter_padded()`)"
908 );
909 assert_ne!(
910 buf1.slice(32..64),
911 buf2.slice(32..64),
912 "Buffer slices with different bits should not be equal (`PartialEq` needs `iter_padded()`)"
913 );
914 }
915
916 #[test]
917 fn test_slice_offset_calculation() {
918 let buf = BitBuffer::collect_bool(16, |_| true);
919 let sliced = buf.slice(10..16);
920 assert_eq!(sliced.len(), 6);
921 assert_eq!(sliced.offset(), 2);
923 }
924
925 #[test]
926 fn test_byte_aligned_bytes() {
927 let bytes: ByteBuffer = buffer![0b1010_0101u8, 0b0000_0011];
928 let buf = BitBuffer::new(bytes.clone(), 10);
929 assert_eq!(buf.byte_aligned_bytes(), Some(bytes.as_slice()));
930
931 let byte_sliced = buf.slice(8..10);
932 assert_eq!(byte_sliced.byte_aligned_bytes(), Some(&[0b0000_0011][..]));
933
934 let bit_sliced = buf.slice(1..9);
935 assert!(bit_sliced.byte_aligned_bytes().is_none());
936 }
937
938 #[test]
939 fn test_from_indices_dense_crosses_words() {
940 let len = 130;
941 let indices = (0..len).filter(|idx| idx % 3 != 1);
942 let buf = BitBuffer::from_indices(len, indices);
943
944 assert_eq!(buf.len(), len);
945 for idx in 0..len {
946 assert_eq!(buf.value(idx), idx % 3 != 1, "mismatch at {idx}");
947 }
948 }
949
950 #[test]
951 #[should_panic(expected = "index 5 exceeds len 5")]
952 fn test_from_indices_out_of_bounds() {
953 BitBuffer::from_indices(5, [0, 5]);
954 }
955
956 #[rstest]
957 #[case(0, 0, None)]
958 #[case(3, 7, None)]
959 #[case(0, 1, Some(0))]
960 #[case(8, 64, Some(63))]
961 #[case(13, 65, Some(0))]
962 #[case(13, 65, Some(64))]
963 #[case(67, 151, Some(97))]
964 #[case(67, 151, Some(150))]
965 fn last_set_index_handles_offsets_and_padding(
966 #[case] offset: usize,
967 #[case] len: usize,
968 #[case] expected: Option<usize>,
969 ) {
970 let backing = BitBuffer::from_iter(
971 std::iter::repeat_n(true, offset)
972 .chain((0..len).map(|index| Some(index) == expected))
973 .chain(std::iter::repeat_n(true, 7)),
974 );
975 let buffer = BitBuffer::new_with_offset(backing.inner().clone(), len, offset);
976
977 assert_eq!(buffer.last_set_index(), expected);
978 }
979
980 #[rstest]
981 #[case(5)]
982 #[case(8)]
983 #[case(10)]
984 #[case(13)]
985 #[case(16)]
986 #[case(23)]
987 #[case(100)]
988 fn test_iter_bits(#[case] len: usize) {
989 let buf = BitBuffer::collect_bool(len, |i| i % 2 == 0);
990
991 let mut collected = Vec::new();
992 buf.iter_bits(|idx, is_set| {
993 collected.push((idx, is_set));
994 });
995
996 let expected: Vec<_> = (0..len).map(|idx| (idx, idx % 2 == 0)).collect();
997 assert_eq!(collected, expected);
998 }
999
1000 #[rstest]
1001 #[case(3, 5)]
1002 #[case(3, 8)]
1003 #[case(5, 10)]
1004 #[case(2, 16)]
1005 #[case(8, 16)]
1006 #[case(9, 16)]
1007 #[case(17, 16)]
1008 fn test_iter_bits_with_offset(#[case] offset: usize, #[case] len: usize) {
1009 let total_bits = offset + len;
1010 let buf = BitBuffer::collect_bool(total_bits, |i| i % 2 == 0);
1011 let buf_with_offset = BitBuffer::new_with_offset(buf.inner().clone(), len, offset);
1012
1013 let mut collected = Vec::new();
1014 buf_with_offset.iter_bits(|idx, is_set| {
1015 collected.push((idx, is_set));
1016 });
1017
1018 let expected: Vec<_> = (0..len)
1019 .map(|idx| (idx, (offset + idx).is_multiple_of(2)))
1020 .collect();
1021 assert_eq!(collected, expected);
1022 }
1023
1024 #[rstest]
1025 #[case(8, 10)]
1026 #[case(9, 7)]
1027 #[case(16, 8)]
1028 #[case(17, 10)]
1029 fn test_iter_bits_catches_wrong_byte_offset(#[case] offset: usize, #[case] len: usize) {
1030 let total_bits = offset + len;
1031 let buf = BitBuffer::collect_bool(total_bits, |i| (i / 8) % 2 == 0);
1033
1034 let buf_with_offset = BitBuffer::new_with_offset(buf.inner().clone(), len, offset);
1035
1036 let mut collected = Vec::new();
1037 buf_with_offset.iter_bits(|idx, is_set| {
1038 collected.push((idx, is_set));
1039 });
1040
1041 let expected: Vec<_> = (0..len)
1042 .map(|idx| (idx, ((offset + idx) / 8).is_multiple_of(2)))
1043 .collect();
1044 assert_eq!(collected, expected);
1045 }
1046
1047 #[rstest]
1048 #[case(5)]
1049 #[case(8)]
1050 #[case(10)]
1051 #[case(64)]
1052 #[case(65)]
1053 #[case(100)]
1054 #[case(128)]
1055 fn test_map_cmp_identity(#[case] len: usize) {
1056 let buf = BitBuffer::collect_bool(len, |i| i % 3 == 0);
1058 let mapped = buf.map_cmp(|_idx, bit| bit);
1059
1060 assert_eq!(buf.len(), mapped.len());
1061 for i in 0..len {
1062 assert_eq!(buf.value(i), mapped.value(i), "Mismatch at index {}", i);
1063 }
1064 }
1065
1066 #[rstest]
1067 #[case(5)]
1068 #[case(8)]
1069 #[case(64)]
1070 #[case(65)]
1071 #[case(100)]
1072 fn test_map_cmp_negate(#[case] len: usize) {
1073 let buf = BitBuffer::collect_bool(len, |i| i % 2 == 0);
1075 let mapped = buf.map_cmp(|_idx, bit| !bit);
1076
1077 assert_eq!(buf.len(), mapped.len());
1078 for i in 0..len {
1079 assert_eq!(!buf.value(i), mapped.value(i), "Mismatch at index {}", i);
1080 }
1081 }
1082
1083 #[rstest]
1084 #[case(0, 0)]
1085 #[case(0, 64)]
1086 #[case(5, 70)]
1087 #[case(64, 130)]
1088 #[case(0, 200)]
1089 fn test_count_range(#[case] start: usize, #[case] end: usize) {
1090 let len = 200;
1091 let buf = BitBuffer::collect_bool(len, |i| i % 3 == 0);
1092 let expected = (start..end).filter(|i| i % 3 == 0).count();
1093 assert_eq!(buf.count_range(start, end), expected);
1094 assert_eq!(
1096 buf.count_range(start, end),
1097 buf.slice(start..end).true_count()
1098 );
1099 }
1100
1101 #[rstest]
1102 #[case(3)]
1103 #[case(7)]
1104 fn test_count_range_with_offset(#[case] offset: usize) {
1105 let len = 150;
1106 let buf = BitBuffer::collect_bool(offset + len, |i| i % 2 == 0);
1107 let view = BitBuffer::new_with_offset(buf.inner().clone(), len, offset);
1108 for (start, end) in [(0, len), (10, 100), (1, 2), (63, 129)] {
1109 let expected = (offset + start..offset + end)
1110 .filter(|i| i % 2 == 0)
1111 .count();
1112 assert_eq!(view.count_range(start, end), expected, "[{start}, {end})");
1113 }
1114 }
1115
1116 #[rstest]
1117 #[case(0)]
1118 #[case(1)]
1119 #[case(63)]
1120 #[case(64)]
1121 #[case(65)]
1122 #[case(200)]
1123 #[case(1000)]
1124 fn test_set_index_visitors_match_set_indices(#[case] len: usize) {
1125 let buf = BitBuffer::collect_bool(len, |i| i % 5 == 0 || i % 7 == 0);
1126 let expected: Vec<usize> = buf.set_indices().collect();
1127
1128 let mut got = Vec::new();
1129 buf.for_each_set_index(|i| got.push(i));
1130 assert_eq!(got, expected);
1131
1132 let mut fallible_got = Vec::new();
1133 let result = buf.try_for_each_set_index(|i| {
1134 fallible_got.push(i);
1135 Ok::<(), ()>(())
1136 });
1137 assert_eq!(result, Ok(()));
1138 assert_eq!(fallible_got, expected);
1139 }
1140
1141 #[rstest]
1142 #[case(3, 200)]
1143 #[case(7, 130)]
1144 fn test_for_each_set_index_with_offset(#[case] offset: usize, #[case] len: usize) {
1145 let base = BitBuffer::collect_bool(offset + len, |i| i % 3 == 0);
1146 let view = BitBuffer::new_with_offset(base.inner().clone(), len, offset);
1147 let expected: Vec<usize> = view.set_indices().collect();
1148 let mut got = Vec::new();
1149 view.for_each_set_index(|i| got.push(i));
1150 assert_eq!(got, expected);
1151 }
1152
1153 #[test]
1154 fn test_for_each_set_index_all_set() {
1155 let buf = BitBuffer::new_set(130);
1156 let mut got = Vec::new();
1157 buf.for_each_set_index(|i| got.push(i));
1158 assert_eq!(got, (0..130).collect::<Vec<_>>());
1159 }
1160
1161 #[test]
1162 fn test_try_for_each_set_index_stops_on_error() {
1163 for (buffer, stop) in [
1164 (BitBuffer::new_set(130), 65),
1165 (BitBuffer::collect_bool(130, |i| i % 3 == 0), 66),
1166 ] {
1167 let mut visited = Vec::new();
1168 let result = buffer.try_for_each_set_index(|index| {
1169 visited.push(index);
1170 if index == stop {
1171 return Err(index);
1172 }
1173
1174 Ok(())
1175 });
1176
1177 assert_eq!(result, Err(stop));
1178 assert_eq!(
1179 visited,
1180 buffer
1181 .set_indices()
1182 .take_while(|&i| i <= stop)
1183 .collect::<Vec<_>>()
1184 );
1185 }
1186 }
1187
1188 #[rstest]
1189 #[case(0)]
1190 #[case(1)]
1191 #[case(63)]
1192 #[case(64)]
1193 #[case(65)]
1194 #[case(128)]
1195 #[case(200)]
1196 fn test_for_each_unset_index_agrees_with_naive(#[case] len: usize) -> VortexResult<()> {
1197 let mut rng = StdRng::seed_from_u64(u64::try_from(len)?);
1198 let random: BitBuffer = (0..len).map(|_| rng.random_bool(0.5)).collect();
1199 let offset: BitBuffer = (0..len + 3).map(|_| rng.random_bool(0.5)).collect();
1201 for bits in [
1202 random,
1203 offset.slice(3..),
1204 BitBuffer::new_set(len),
1205 BitBuffer::new_unset(len),
1206 ] {
1207 let expected: Vec<usize> = bits
1208 .iter()
1209 .enumerate()
1210 .filter_map(|(index, set)| (!set).then_some(index))
1211 .collect();
1212 let mut found = Vec::new();
1213 bits.for_each_unset_index(|index| found.push(index));
1214 assert_eq!(found, expected);
1215 }
1216 Ok(())
1217 }
1218
1219 #[test]
1220 fn test_map_cmp_conditional() {
1221 let len = 100;
1223 let buf = BitBuffer::collect_bool(len, |i| i % 2 == 0);
1224
1225 let mapped = buf.map_cmp(|idx, bit| bit && idx % 4 == 0);
1227
1228 for i in 0..len {
1229 let expected = (i % 2 == 0) && (i % 4 == 0);
1230 assert_eq!(mapped.value(i), expected, "Mismatch at index {}", i);
1231 }
1232 }
1233
1234 #[rstest]
1235 #[case(0, 200)]
1236 #[case(3, 197)]
1237 #[case(13, 600)]
1238 fn test_select_unset_sliced(#[case] start: usize, #[case] len: usize) {
1239 let buf = BitBuffer::collect_bool(start + len, |i| i % 3 == 0 || i % 7 == 0);
1240 let sliced = buf.slice(start..start + len);
1241 let expected: Vec<usize> = sliced
1242 .iter()
1243 .enumerate()
1244 .filter_map(|(index, set)| (!set).then_some(index))
1245 .collect();
1246
1247 for (nth, &index) in expected.iter().enumerate() {
1248 assert_eq!(
1249 sliced.select_unset(nth),
1250 Some(index),
1251 "start={start} nth={nth}"
1252 );
1253 }
1254 assert_eq!(sliced.select_unset(expected.len()), None);
1255 }
1256}