1use 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#[derive(Debug, Clone, Eq)]
84pub struct BooleanBuffer {
85 buffer: Buffer,
87 bit_offset: usize,
89 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 pub fn count_set_bits(&self) -> usize {
424 self.buffer
425 .count_set_bits_offset(self.bit_offset, self.bit_len)
426 }
427
428 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 #[inline]
445 pub fn bit_chunks(&self) -> BitChunks<'_> {
446 BitChunks::new(self.values(), self.bit_offset, self.bit_len)
447 }
448
449 #[inline]
451 pub fn offset(&self) -> usize {
452 self.bit_offset
453 }
454
455 #[inline]
457 pub fn len(&self) -> usize {
458 self.bit_len
459 }
460
461 #[inline]
463 pub fn is_empty(&self) -> bool {
464 self.bit_len == 0
465 }
466
467 pub fn shrink_to_fit(&mut self) {
469 self.buffer.shrink_to_fit();
471 }
472
473 #[inline]
479 pub fn value(&self, idx: usize) -> bool {
480 assert!(idx < self.bit_len);
481 unsafe { self.value_unchecked(idx) }
482 }
483
484 #[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 #[inline]
495 pub fn values(&self) -> &[u8] {
496 &self.buffer
497 }
498
499 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 pub fn sliced(&self) -> Buffer {
520 self.buffer.bit_slice(self.bit_offset, self.bit_len)
521 }
522
523 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 #[inline]
536 pub fn inner(&self) -> &Buffer {
537 &self.buffer
538 }
539
540 pub fn into_inner(self) -> Buffer {
544 self.buffer
545 }
546
547 #[cfg(feature = "pool")]
551 pub fn claim(&self, pool: &dyn crate::MemoryPool) {
552 self.buffer.claim(pool);
553 }
554
555 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 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 pub fn iter(&self) -> BitIterator<'_> {
600 self.into_iter()
601 }
602
603 fn unaligned_bit_chunks(&self) -> UnalignedBitChunk<'_> {
605 UnalignedBitChunk::new(self.values(), self.offset(), self.len())
606 }
607
608 pub fn set_indices(&self) -> BitIndexIterator<'_> {
610 BitIndexIterator::new(self.values(), self.bit_offset, self.bit_len)
611 }
612
613 pub fn set_indices_u32(&self) -> BitIndexU32Iterator<'_> {
615 BitIndexU32Iterator::new(self.values(), self.bit_offset, self.bit_len)
616 }
617
618 pub fn set_slices(&self) -> BitSliceIterator<'_> {
620 BitSliceIterator::new(self.values(), self.bit_offset, self.bit_len)
621 }
622
623 const CHUNK_FOLD_BLOCK_SIZE: usize = 16;
627
628 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 pub fn has_false(&self) -> bool {
652 let bit_chunks = self.unaligned_bit_chunks();
653 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 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 let boolean_buf2 = BooleanBuffer::new(Buffer::from(&[0, 0, 2, 3, 4]), 0, 32);
836 assert_ne!(boolean_buf1, boolean_buf2);
837
838 let boolean_buf2 = BooleanBuffer::new(Buffer::from(&[0, 1, 4, 3, 5]), 0, 24);
840 assert_ne!(boolean_buf1, boolean_buf2);
841
842 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 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 let input_bools = (0..1024)
989 .map(|_| rand::random::<bool>())
990 .collect::<Vec<bool>>();
991 let input_buffer = BooleanBuffer::from(&input_bools[..]);
992
993 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 for offset in 0..512 {
1010 let len = 512 - offset; 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 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 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 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 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)] 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); 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 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 let left_bytes = [
1105 0, 0b1101_0010, 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, 0b1010_1100, 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; let len = 24; 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 let left_bytes = [
1165 0, 0b1010_1100, 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, 0b0111_0010, 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; let len = 61; 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 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 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]; let buffer = BooleanBuffer::from(bools);
1280 let slice = buffer.slice(1, 6); assert_eq!(slice.len(), 6);
1283 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 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 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 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}