1use std::fmt;
45use std::sync::atomic::{AtomicI64, Ordering};
46
47use crate::buffer::Buffer;
48use crate::buffer::aligned::AlignedBuf;
49use crate::error::{DataError, Result};
50
51const UNKNOWN_COUNT: i64 = -1;
53
54#[inline]
68#[must_use]
69pub fn get_bit(data: &[u8], index: usize) -> bool {
70 match data.get(index / 8) {
71 Some(byte) => (byte >> (index % 8)) & 1 == 1,
72 None => false,
73 }
74}
75
76#[inline]
90pub fn set_bit(data: &mut [u8], index: usize, value: bool) {
91 if let Some(byte) = data.get_mut(index / 8) {
92 let mask = 1u8 << (index % 8);
93 if value {
94 *byte |= mask;
95 } else {
96 *byte &= !mask;
97 }
98 }
99}
100
101#[must_use]
115pub fn count_set_bits(data: &[u8], offset: usize, len: usize) -> usize {
116 let available = data.len().saturating_mul(8);
117 if len == 0 || offset >= available {
118 return 0;
119 }
120 let len = len.min(available - offset);
121 let end = offset + len;
122
123 let first_byte = offset / 8;
124 let last_byte = end.div_ceil(8);
125 let Some(bytes) = data.get(first_byte..last_byte) else {
126 return 0;
127 };
128 let Some((&head, rest)) = bytes.split_first() else {
129 return 0;
130 };
131
132 let lead = offset % 8;
133 let trail = (8 - end % 8) % 8;
134 let head_mask = 0xffu8 << lead;
135
136 let Some((&tail, middle)) = rest.split_last() else {
137 return usize::try_from((head & head_mask & (0xffu8 >> trail)).count_ones()).unwrap_or(0);
139 };
140
141 let mut count = (head & head_mask).count_ones();
142 let (words, remainder) = middle.as_chunks::<8>();
145 for word in words {
146 count += u64::from_le_bytes(*word).count_ones();
147 }
148 for byte in remainder {
149 count += byte.count_ones();
150 }
151 count += (tail & (0xffu8 >> trail)).count_ones();
152 usize::try_from(count).unwrap_or(0)
153}
154
155pub struct Bitmap {
164 buffer: Buffer,
166 offset: usize,
168 len: usize,
170 set_count: AtomicI64,
172}
173
174impl Bitmap {
175 pub fn try_new(buffer: Buffer, offset: usize, len: usize) -> Result<Self> {
192 let required = offset.saturating_add(len).div_ceil(8);
193 if required > buffer.len() {
194 return Err(DataError::BufferTooSmall {
195 required,
196 actual: buffer.len(),
197 });
198 }
199 Ok(Self {
200 buffer,
201 offset,
202 len,
203 set_count: AtomicI64::new(UNKNOWN_COUNT),
204 })
205 }
206
207 #[must_use]
215 pub fn from_buffer(buffer: Buffer) -> Self {
216 let len = buffer.len() * 8;
217 Self {
218 buffer,
219 offset: 0,
220 len,
221 set_count: AtomicI64::new(UNKNOWN_COUNT),
222 }
223 }
224
225 #[must_use]
227 pub fn new_set(len: usize) -> Self {
228 let mut buf = AlignedBuf::with_capacity(len.div_ceil(8));
229 buf.resize(len.div_ceil(8), 0xff);
230 Self {
231 buffer: Buffer::from(buf),
232 offset: 0,
233 len,
234 set_count: AtomicI64::new(i64::try_from(len).unwrap_or(UNKNOWN_COUNT)),
235 }
236 }
237
238 #[must_use]
240 pub fn new_unset(len: usize) -> Self {
241 Self {
242 buffer: Buffer::zeroed(len.div_ceil(8)),
243 offset: 0,
244 len,
245 set_count: AtomicI64::new(0),
246 }
247 }
248
249 #[inline]
251 #[must_use]
252 pub const fn len(&self) -> usize {
253 self.len
254 }
255
256 #[inline]
258 #[must_use]
259 pub const fn is_empty(&self) -> bool {
260 self.len == 0
261 }
262
263 #[inline]
265 #[must_use]
266 pub const fn bit_offset(&self) -> usize {
267 self.offset
268 }
269
270 #[inline]
272 #[must_use]
273 pub const fn buffer(&self) -> &Buffer {
274 &self.buffer
275 }
276
277 #[inline]
279 #[must_use]
280 pub fn get(&self, index: usize) -> Option<bool> {
281 if index >= self.len {
282 return None;
283 }
284 Some(get_bit(self.buffer.as_slice(), self.offset + index))
285 }
286
287 #[inline]
291 #[must_use]
292 pub fn value(&self, index: usize) -> bool {
293 index < self.len && get_bit(self.buffer.as_slice(), self.offset + index)
294 }
295
296 #[must_use]
306 pub fn count_set(&self) -> usize {
307 let cached = self.set_count.load(Ordering::Relaxed);
308 if cached >= 0 {
309 return usize::try_from(cached).unwrap_or(self.len);
310 }
311 let counted = count_set_bits(self.buffer.as_slice(), self.offset, self.len);
312 self.set_count.store(
315 i64::try_from(counted).unwrap_or(UNKNOWN_COUNT),
316 Ordering::Relaxed,
317 );
318 counted
319 }
320
321 #[inline]
323 #[must_use]
324 pub fn count_unset(&self) -> usize {
325 self.len - self.count_set()
326 }
327
328 #[inline]
330 #[must_use]
331 pub fn all_set(&self) -> bool {
332 self.count_set() == self.len
333 }
334
335 #[inline]
337 #[must_use]
338 pub fn none_set(&self) -> bool {
339 self.count_set() == 0
340 }
341
342 #[must_use]
354 pub fn slice(&self, offset: usize, len: usize) -> Self {
355 let offset = offset.min(self.len);
356 let len = len.min(self.len - offset);
357 let full = offset == 0 && len == self.len;
358 Self {
359 buffer: self.buffer.clone(),
360 offset: self.offset + offset,
361 len,
362 set_count: AtomicI64::new(if full {
363 self.set_count.load(Ordering::Relaxed)
364 } else {
365 UNKNOWN_COUNT
366 }),
367 }
368 }
369
370 pub fn try_slice(&self, offset: usize, len: usize) -> Result<Self> {
372 if offset.saturating_add(len) > self.len {
373 return Err(DataError::SliceOutOfBounds {
374 offset,
375 len,
376 available: self.len,
377 });
378 }
379 Ok(self.slice(offset, len))
380 }
381
382 #[inline]
384 #[must_use]
385 pub fn iter(&self) -> BitmapIter<'_> {
386 BitmapIter {
387 bitmap: self,
388 front: 0,
389 back: self.len,
390 }
391 }
392
393 pub fn set_indices(&self) -> impl Iterator<Item = usize> + '_ {
402 self.iter()
403 .enumerate()
404 .filter_map(|(i, bit)| bit.then_some(i))
405 }
406
407 pub fn unset_indices(&self) -> impl Iterator<Item = usize> + '_ {
409 self.iter()
410 .enumerate()
411 .filter_map(|(i, bit)| (!bit).then_some(i))
412 }
413
414 #[inline]
420 #[must_use]
421 fn byte_at(&self, start: usize) -> u8 {
422 if start >= self.len {
423 return 0;
424 }
425 let data = self.buffer.as_slice();
426 let bit = self.offset + start;
427 let index = bit / 8;
428 let shift = bit % 8;
429 let mut byte = data.get(index).copied().unwrap_or(0) >> shift;
430 if shift != 0 {
431 let next = data.get(index + 1).copied().unwrap_or(0);
432 byte |= next << (8 - shift);
433 }
434 let remaining = self.len - start;
435 if remaining < 8 {
436 byte &= 0xffu8 >> (8 - remaining);
437 }
438 byte
439 }
440
441 #[must_use]
456 pub fn to_canonical(&self) -> Self {
457 if self.offset == 0 && self.buffer.len() == self.len.div_ceil(8) {
458 return self.clone();
459 }
460 let byte_len = self.len.div_ceil(8);
461 let mut buf = AlignedBuf::with_capacity(byte_len);
462 for index in 0..byte_len {
463 buf.push(self.byte_at(index * 8));
464 }
465 Self {
466 buffer: Buffer::from(buf),
467 offset: 0,
468 len: self.len,
469 set_count: AtomicI64::new(self.set_count.load(Ordering::Relaxed)),
470 }
471 }
472
473 pub fn and(&self, other: &Self) -> Result<Self> {
491 self.binary_op(other, |a, b| a & b)
492 }
493
494 pub fn or(&self, other: &Self) -> Result<Self> {
500 self.binary_op(other, |a, b| a | b)
501 }
502
503 pub fn xor(&self, other: &Self) -> Result<Self> {
509 self.binary_op(other, |a, b| a ^ b)
510 }
511
512 #[must_use]
521 pub fn not(&self) -> Self {
522 self.map_bytes(|byte| !byte)
523 }
524
525 fn map_bytes(&self, op: impl Fn(u8) -> u8) -> Self {
527 let byte_len = self.len.div_ceil(8);
528 let mut buf = AlignedBuf::with_capacity(byte_len);
529 for index in 0..byte_len {
530 buf.push(op(self.byte_at(index * 8)));
531 }
532 mask_tail(&mut buf, self.len);
533 Self {
534 buffer: Buffer::from(buf),
535 offset: 0,
536 len: self.len,
537 set_count: AtomicI64::new(UNKNOWN_COUNT),
538 }
539 }
540
541 fn binary_op(&self, other: &Self, op: impl Fn(u8, u8) -> u8) -> Result<Self> {
544 if self.len != other.len {
545 return Err(DataError::BitmapLengthMismatch {
546 left: self.len,
547 right: other.len,
548 });
549 }
550 let byte_len = self.len.div_ceil(8);
551 let mut buf = AlignedBuf::with_capacity(byte_len);
552 for index in 0..byte_len {
553 let start = index * 8;
554 buf.push(op(self.byte_at(start), other.byte_at(start)));
555 }
556 mask_tail(&mut buf, self.len);
557 Ok(Self {
558 buffer: Buffer::from(buf),
559 offset: 0,
560 len: self.len,
561 set_count: AtomicI64::new(UNKNOWN_COUNT),
562 })
563 }
564
565 pub fn intersect(left: Option<&Self>, right: Option<&Self>) -> Result<Option<Self>> {
584 match (left, right) {
585 (None, None) => Ok(None),
586 (Some(only), None) | (None, Some(only)) => Ok(Some(only.clone())),
587 (Some(a), Some(b)) => a.and(b).map(Some),
588 }
589 }
590
591 #[must_use]
604 pub fn repeat_each(&self, factor: usize) -> Self {
605 let mut builder = BitmapBuilder::with_capacity(self.len.saturating_mul(factor));
606 for bit in self.iter() {
607 builder.append_n(factor, bit);
608 }
609 builder.finish()
610 }
611}
612
613fn mask_tail(buf: &mut AlignedBuf, len: usize) {
616 let trailing = len % 8;
617 if trailing == 0 {
618 return;
619 }
620 let last = len / 8;
621 if let Some(byte) = buf.as_mut_slice().get_mut(last) {
622 *byte &= 0xffu8 >> (8 - trailing);
623 }
624}
625
626impl Clone for Bitmap {
627 fn clone(&self) -> Self {
628 Self {
629 buffer: self.buffer.clone(),
630 offset: self.offset,
631 len: self.len,
632 set_count: AtomicI64::new(self.set_count.load(Ordering::Relaxed)),
633 }
634 }
635}
636
637impl PartialEq for Bitmap {
638 fn eq(&self, other: &Self) -> bool {
641 if self.len != other.len {
642 return false;
643 }
644 (0..self.len.div_ceil(8)).all(|index| {
645 let start = index * 8;
646 self.byte_at(start) == other.byte_at(start)
647 })
648 }
649}
650
651impl Eq for Bitmap {}
652
653impl std::hash::Hash for Bitmap {
654 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
655 self.len.hash(state);
656 for index in 0..self.len.div_ceil(8) {
657 self.byte_at(index * 8).hash(state);
658 }
659 }
660}
661
662impl fmt::Debug for Bitmap {
663 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
664 const PREVIEW: usize = 64;
665 let mut bits = String::with_capacity(self.len.min(PREVIEW) + 1);
666 for bit in self.iter().take(PREVIEW) {
667 bits.push(if bit { '1' } else { '0' });
668 }
669 if self.len > PREVIEW {
670 bits.push('…');
671 }
672 f.debug_struct("Bitmap")
673 .field("len", &self.len)
674 .field("offset", &self.offset)
675 .field("set", &self.count_set())
676 .field("bits", &bits)
677 .finish()
678 }
679}
680
681impl FromIterator<bool> for Bitmap {
682 fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
683 let iter = iter.into_iter();
684 let (lower, _) = iter.size_hint();
685 let mut builder = BitmapBuilder::with_capacity(lower);
686 for bit in iter {
687 builder.append(bit);
688 }
689 builder.finish()
690 }
691}
692
693impl<'a> IntoIterator for &'a Bitmap {
694 type Item = bool;
695 type IntoIter = BitmapIter<'a>;
696
697 fn into_iter(self) -> BitmapIter<'a> {
698 self.iter()
699 }
700}
701
702#[derive(Debug, Clone)]
704pub struct BitmapIter<'a> {
705 bitmap: &'a Bitmap,
707 front: usize,
709 back: usize,
711}
712
713impl Iterator for BitmapIter<'_> {
714 type Item = bool;
715
716 #[inline]
717 fn next(&mut self) -> Option<bool> {
718 if self.front >= self.back {
719 return None;
720 }
721 let bit = self.bitmap.value(self.front);
722 self.front += 1;
723 Some(bit)
724 }
725
726 #[inline]
727 fn size_hint(&self) -> (usize, Option<usize>) {
728 let remaining = self.back - self.front;
729 (remaining, Some(remaining))
730 }
731}
732
733impl DoubleEndedIterator for BitmapIter<'_> {
734 #[inline]
735 fn next_back(&mut self) -> Option<bool> {
736 if self.front >= self.back {
737 return None;
738 }
739 self.back -= 1;
740 Some(self.bitmap.value(self.back))
741 }
742}
743
744impl ExactSizeIterator for BitmapIter<'_> {}
745
746impl std::iter::FusedIterator for BitmapIter<'_> {}
747
748#[derive(Debug, Default)]
762pub struct BitmapBuilder {
763 buf: AlignedBuf,
765 len: usize,
767 set_count: usize,
769}
770
771impl BitmapBuilder {
772 #[must_use]
774 pub fn new() -> Self {
775 Self::default()
776 }
777
778 #[must_use]
780 pub fn with_capacity(capacity: usize) -> Self {
781 Self {
782 buf: AlignedBuf::with_capacity(capacity.div_ceil(8)),
783 len: 0,
784 set_count: 0,
785 }
786 }
787
788 #[inline]
790 #[must_use]
791 pub const fn len(&self) -> usize {
792 self.len
793 }
794
795 #[inline]
797 #[must_use]
798 pub const fn is_empty(&self) -> bool {
799 self.len == 0
800 }
801
802 #[inline]
804 #[must_use]
805 pub const fn count_set(&self) -> usize {
806 self.set_count
807 }
808
809 #[inline]
811 pub fn append(&mut self, value: bool) {
812 if self.len.is_multiple_of(8) {
813 self.buf.push(0);
814 }
815 if value {
816 set_bit(self.buf.as_mut_slice(), self.len, true);
817 self.set_count += 1;
818 }
819 self.len += 1;
820 }
821
822 pub fn append_n(&mut self, count: usize, value: bool) {
824 if count == 0 {
825 return;
826 }
827 self.buf
828 .reserve((self.len + count).div_ceil(8) - self.buf.len());
829 let head = (8 - self.len % 8) % 8;
831 let head = head.min(count);
832 for _ in 0..head {
833 self.append(value);
834 }
835 let remaining = count - head;
836 if remaining == 0 {
837 return;
838 }
839 let whole_bytes = remaining / 8;
840 if whole_bytes > 0 {
841 self.buf
842 .resize(self.buf.len() + whole_bytes, u8::from(value) * 0xff);
843 self.len += whole_bytes * 8;
844 if value {
845 self.set_count += whole_bytes * 8;
846 }
847 }
848 for _ in 0..remaining % 8 {
849 self.append(value);
850 }
851 }
852
853 pub fn append_slice(&mut self, values: &[bool]) {
855 self.buf.reserve(
856 (self.len + values.len())
857 .div_ceil(8)
858 .saturating_sub(self.buf.len()),
859 );
860 for value in values {
861 self.append(*value);
862 }
863 }
864
865 pub fn append_bitmap(&mut self, bitmap: &Bitmap) {
867 self.buf.reserve(
868 (self.len + bitmap.len())
869 .div_ceil(8)
870 .saturating_sub(self.buf.len()),
871 );
872 for bit in bitmap.iter() {
873 self.append(bit);
874 }
875 }
876
877 pub fn set(&mut self, index: usize, value: bool) {
879 if index >= self.len {
880 return;
881 }
882 let previous = get_bit(self.buf.as_slice(), index);
883 if previous == value {
884 return;
885 }
886 set_bit(self.buf.as_mut_slice(), index, value);
887 if value {
888 self.set_count += 1;
889 } else {
890 self.set_count -= 1;
891 }
892 }
893
894 #[must_use]
896 pub fn get(&self, index: usize) -> Option<bool> {
897 (index < self.len).then(|| get_bit(self.buf.as_slice(), index))
898 }
899
900 pub fn clear(&mut self) {
902 self.buf.clear();
903 self.len = 0;
904 self.set_count = 0;
905 }
906
907 #[must_use]
909 pub fn finish(&mut self) -> Bitmap {
910 let buf = std::mem::take(&mut self.buf);
911 let len = std::mem::take(&mut self.len);
912 let set_count = std::mem::take(&mut self.set_count);
913 Bitmap {
914 buffer: Buffer::from(buf),
915 offset: 0,
916 len,
917 set_count: AtomicI64::new(i64::try_from(set_count).unwrap_or(UNKNOWN_COUNT)),
918 }
919 }
920
921 #[must_use]
923 pub fn finish_cloned(&self) -> Bitmap {
924 Bitmap {
925 buffer: Buffer::from(self.buf.clone()),
926 offset: 0,
927 len: self.len,
928 set_count: AtomicI64::new(i64::try_from(self.set_count).unwrap_or(UNKNOWN_COUNT)),
929 }
930 }
931}
932
933impl Extend<bool> for BitmapBuilder {
934 fn extend<I: IntoIterator<Item = bool>>(&mut self, iter: I) {
935 for bit in iter {
936 self.append(bit);
937 }
938 }
939}
940
941impl FromIterator<bool> for BitmapBuilder {
942 fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
943 let mut builder = Self::new();
944 builder.extend(iter);
945 builder
946 }
947}
948
949#[cfg(test)]
950mod tests {
951 #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
952
953 use super::*;
954
955 const fn assert_send_sync<T: Send + Sync>() {}
956
957 fn bitmap_of(bits: &[bool]) -> Bitmap {
958 bits.iter().copied().collect()
959 }
960
961 #[test]
962 fn bitmap_is_send_and_sync() {
963 assert_send_sync::<Bitmap>();
964 assert_send_sync::<BitmapBuilder>();
965 }
966
967 #[test]
968 fn lsb_numbering_matches_the_arrow_spec() {
969 let bits = Bitmap::from_buffer(Buffer::from_slice(&[0b0000_0101, 0b1000_0000]));
970 assert!(bits.value(0));
971 assert!(!bits.value(1));
972 assert!(bits.value(2));
973 assert!(!bits.value(8));
974 assert!(bits.value(15));
975 assert_eq!(bits.count_set(), 3);
976 }
977
978 #[test]
979 fn empty_bitmap() {
980 let bits = bitmap_of(&[]);
981 assert!(bits.is_empty());
982 assert_eq!(bits.len(), 0);
983 assert_eq!(bits.count_set(), 0);
984 assert_eq!(bits.count_unset(), 0);
985 assert!(bits.all_set(), "vacuously true");
986 assert!(bits.none_set());
987 assert_eq!(bits.get(0), None);
988 assert!(!bits.value(0));
989 assert_eq!(bits.iter().count(), 0);
990 }
991
992 #[test]
993 fn all_set_and_all_unset_constructors() {
994 let set = Bitmap::new_set(13);
995 assert_eq!(set.len(), 13);
996 assert_eq!(set.count_set(), 13);
997 assert!(set.all_set());
998 assert!(set.iter().all(|b| b));
999
1000 let unset = Bitmap::new_unset(13);
1001 assert_eq!(unset.count_set(), 0);
1002 assert!(unset.none_set());
1003 assert!(unset.iter().all(|b| !b));
1004 }
1005
1006 #[test]
1007 fn try_new_validates_coverage() {
1008 let buffer = Buffer::from_slice(&[0xff, 0xff]);
1009 assert!(Bitmap::try_new(buffer.clone(), 0, 16).is_ok());
1010 assert!(Bitmap::try_new(buffer.clone(), 9, 7).is_ok());
1011 assert_eq!(
1012 Bitmap::try_new(buffer.clone(), 0, 17).unwrap_err(),
1013 DataError::BufferTooSmall {
1014 required: 3,
1015 actual: 2
1016 }
1017 );
1018 assert!(Bitmap::try_new(buffer, usize::MAX, 1).is_err());
1019 }
1020
1021 #[test]
1022 fn slicing_is_zero_copy_and_offset_aware() {
1023 let source: Vec<bool> = (0..40).map(|i| i % 3 == 0).collect();
1024 let bits = bitmap_of(&source);
1025 for offset in 0..20 {
1026 for len in 0..=(40 - offset) {
1027 let window = bits.slice(offset, len);
1028 assert_eq!(window.len(), len);
1029 let expected: Vec<bool> = source[offset..offset + len].to_vec();
1030 assert_eq!(window.iter().collect::<Vec<_>>(), expected);
1031 assert_eq!(window.count_set(), expected.iter().filter(|b| **b).count());
1032 }
1033 }
1034 }
1035
1036 #[test]
1037 fn slices_clamp_and_try_slice_reports() {
1038 let bits = bitmap_of(&[true; 10]);
1039 assert_eq!(bits.slice(8, 99).len(), 2);
1040 assert_eq!(bits.slice(99, 99).len(), 0);
1041 assert_eq!(
1042 bits.try_slice(8, 5).unwrap_err(),
1043 DataError::SliceOutOfBounds {
1044 offset: 8,
1045 len: 5,
1046 available: 10
1047 }
1048 );
1049 assert_eq!(bits.try_slice(8, 2).unwrap().len(), 2);
1050 }
1051
1052 #[test]
1053 fn nested_slices_compose() {
1054 let source: Vec<bool> = (0..64).map(|i| i % 5 == 0).collect();
1055 let bits = bitmap_of(&source);
1056 let a = bits.slice(7, 40);
1057 let b = a.slice(11, 10);
1058 let expected: Vec<bool> = source[18..28].to_vec();
1059 assert_eq!(b.iter().collect::<Vec<_>>(), expected);
1060 assert_eq!(b.bit_offset(), 18);
1061 }
1062
1063 #[test]
1064 fn full_slice_reuses_the_cached_count() {
1065 let bits = bitmap_of(&[true, false, true]);
1066 assert_eq!(bits.count_set(), 2);
1067 let full = bits.slice(0, 3);
1068 assert_eq!(full.count_set(), 2);
1069 }
1070
1071 #[test]
1072 fn count_set_bits_handles_offsets_and_ragged_ends() {
1073 let data = vec![0xffu8; 9];
1074 assert_eq!(count_set_bits(&data, 0, 72), 72);
1075 assert_eq!(count_set_bits(&data, 3, 5), 5);
1076 assert_eq!(count_set_bits(&data, 3, 60), 60);
1077 assert_eq!(count_set_bits(&data, 70, 2), 2);
1078 assert_eq!(count_set_bits(&data, 0, 0), 0);
1079 assert_eq!(count_set_bits(&data, 72, 8), 0, "past the end");
1080 assert_eq!(count_set_bits(&data, 60, 100), 12, "clamped");
1081 assert_eq!(count_set_bits(&[], 0, 8), 0);
1082
1083 let sparse = [0b0000_0001u8, 0b1000_0000];
1084 assert_eq!(count_set_bits(&sparse, 0, 16), 2);
1085 assert_eq!(count_set_bits(&sparse, 1, 14), 0);
1086 assert_eq!(count_set_bits(&sparse, 1, 15), 1);
1087 }
1088
1089 #[test]
1090 fn count_set_bits_spans_many_words() {
1091 let data = vec![0b0101_0101u8; 100];
1092 assert_eq!(count_set_bits(&data, 0, 800), 400);
1093 assert_eq!(count_set_bits(&data, 1, 798), 399);
1094 assert_eq!(count_set_bits(&data, 5, 790), 395);
1095 }
1096
1097 #[test]
1098 fn binary_ops_respect_differing_offsets() {
1099 let left_src: Vec<bool> = (0..37).map(|i| i % 2 == 0).collect();
1100 let right_src: Vec<bool> = (0..37).map(|i| i % 3 == 0).collect();
1101 let padded_left: Vec<bool> = std::iter::repeat_n(false, 5)
1103 .chain(left_src.iter().copied())
1104 .collect();
1105 let padded_right: Vec<bool> = std::iter::repeat_n(true, 11)
1106 .chain(right_src.iter().copied())
1107 .collect();
1108 let left = bitmap_of(&padded_left).slice(5, 37);
1109 let right = bitmap_of(&padded_right).slice(11, 37);
1110
1111 let and = left.and(&right).unwrap();
1112 let or = left.or(&right).unwrap();
1113 let xor = left.xor(&right).unwrap();
1114 for i in 0..37 {
1115 assert_eq!(and.value(i), left_src[i] && right_src[i], "and at {i}");
1116 assert_eq!(or.value(i), left_src[i] || right_src[i], "or at {i}");
1117 assert_eq!(xor.value(i), left_src[i] ^ right_src[i], "xor at {i}");
1118 }
1119 assert_eq!(and.bit_offset(), 0, "results are canonicalised");
1120 }
1121
1122 #[test]
1123 fn binary_ops_reject_length_mismatch() {
1124 let a = bitmap_of(&[true, false]);
1125 let b = bitmap_of(&[true]);
1126 assert_eq!(
1127 a.and(&b).unwrap_err(),
1128 DataError::BitmapLengthMismatch { left: 2, right: 1 }
1129 );
1130 assert!(a.or(&b).is_err());
1131 assert!(a.xor(&b).is_err());
1132 }
1133
1134 #[test]
1135 fn not_masks_the_tail() {
1136 let bits = bitmap_of(&[true, false, true]);
1137 let inverted = bits.not();
1138 assert_eq!(inverted.len(), 3);
1139 assert_eq!(
1140 inverted.iter().collect::<Vec<_>>(),
1141 vec![false, true, false]
1142 );
1143 assert_eq!(
1144 inverted.count_set(),
1145 1,
1146 "tail bits must not leak into the count"
1147 );
1148 assert_eq!(inverted.buffer().as_slice(), &[0b0000_0010]);
1149 }
1150
1151 #[test]
1152 fn intersect_treats_none_as_all_valid() {
1153 let a = bitmap_of(&[true, false, true]);
1154 let b = bitmap_of(&[true, true, false]);
1155 assert_eq!(Bitmap::intersect(None, None).unwrap(), None);
1156 assert_eq!(Bitmap::intersect(Some(&a), None).unwrap(), Some(a.clone()));
1157 assert_eq!(Bitmap::intersect(None, Some(&b)).unwrap(), Some(b.clone()));
1158 assert_eq!(
1159 Bitmap::intersect(Some(&a), Some(&b)).unwrap(),
1160 Some(bitmap_of(&[true, false, false]))
1161 );
1162 let short = bitmap_of(&[true]);
1163 assert!(Bitmap::intersect(Some(&a), Some(&short)).is_err());
1164 }
1165
1166 #[test]
1167 fn repeat_each_expands_parent_validity() {
1168 let parent = bitmap_of(&[true, false, true]);
1169 let child = parent.repeat_each(2);
1170 assert_eq!(
1171 child.iter().collect::<Vec<_>>(),
1172 vec![true, true, false, false, true, true]
1173 );
1174 assert_eq!(parent.repeat_each(0).len(), 0);
1175 assert_eq!(parent.repeat_each(1), parent);
1176 }
1177
1178 #[test]
1179 fn to_canonical_repacks_offsets() {
1180 let source: Vec<bool> = (0..50).map(|i| i % 7 < 3).collect();
1181 let bits = bitmap_of(&source);
1182 let window = bits.slice(11, 21);
1183 let packed = window.to_canonical();
1184 assert_eq!(packed.bit_offset(), 0);
1185 assert_eq!(packed.len(), 21);
1186 assert_eq!(packed.iter().collect::<Vec<_>>(), source[11..32].to_vec());
1187 assert_eq!(packed.buffer().len(), 3);
1188 assert_eq!(packed, window);
1189 let again = packed.to_canonical();
1191 assert_eq!(again.buffer().as_ptr(), packed.buffer().as_ptr());
1192 }
1193
1194 #[test]
1195 fn equality_is_logical_not_physical() {
1196 let source: Vec<bool> = (0..30).map(|i| i % 4 == 1).collect();
1197 let direct = bitmap_of(&source[3..17]);
1198 let padded: Vec<bool> = std::iter::repeat_n(true, 3)
1199 .chain(source[3..17].iter().copied())
1200 .collect();
1201 let windowed = bitmap_of(&padded).slice(3, 14);
1202 assert_eq!(direct, windowed);
1203 assert_ne!(direct, bitmap_of(&source[3..16]));
1204
1205 use std::collections::hash_map::DefaultHasher;
1206 use std::hash::{Hash, Hasher};
1207 let hash = |b: &Bitmap| {
1208 let mut h = DefaultHasher::new();
1209 b.hash(&mut h);
1210 h.finish()
1211 };
1212 assert_eq!(hash(&direct), hash(&windowed));
1213 }
1214
1215 #[test]
1216 fn iterator_is_double_ended_and_exact() {
1217 let bits = bitmap_of(&[true, false, true, true]);
1218 let mut iter = bits.iter();
1219 assert_eq!(iter.len(), 4);
1220 assert_eq!(iter.next(), Some(true));
1221 assert_eq!(iter.next_back(), Some(true));
1222 assert_eq!(iter.len(), 2);
1223 assert_eq!(iter.collect::<Vec<_>>(), vec![false, true]);
1224
1225 let reversed: Vec<bool> = bits.iter().rev().collect();
1226 assert_eq!(reversed, vec![true, true, false, true]);
1227 assert_eq!((&bits).into_iter().count(), 4);
1228 }
1229
1230 #[test]
1231 fn index_iterators() {
1232 let bits = bitmap_of(&[false, true, false, true, true]);
1233 assert_eq!(bits.set_indices().collect::<Vec<_>>(), vec![1, 3, 4]);
1234 assert_eq!(bits.unset_indices().collect::<Vec<_>>(), vec![0, 2]);
1235 }
1236
1237 #[test]
1238 fn builder_round_trips() {
1239 let mut builder = BitmapBuilder::new();
1240 assert!(builder.is_empty());
1241 for i in 0..100 {
1242 builder.append(i % 3 == 0);
1243 }
1244 assert_eq!(builder.len(), 100);
1245 assert_eq!(builder.count_set(), 34);
1246 let bits = builder.finish();
1247 assert_eq!(bits.len(), 100);
1248 assert_eq!(bits.count_set(), 34);
1249 for i in 0..100 {
1250 assert_eq!(bits.value(i), i % 3 == 0);
1251 }
1252 assert!(builder.is_empty(), "finish resets the builder");
1253 }
1254
1255 #[test]
1256 fn builder_append_n_crosses_byte_boundaries() {
1257 for start in 0..16usize {
1258 for run in 0..40usize {
1259 let mut builder = BitmapBuilder::new();
1260 builder.append_n(start, false);
1261 builder.append_n(run, true);
1262 builder.append_n(3, false);
1263 let bits = builder.finish();
1264 assert_eq!(bits.len(), start + run + 3);
1265 assert_eq!(bits.count_set(), run, "start {start} run {run}");
1266 for i in 0..start {
1267 assert!(!bits.value(i));
1268 }
1269 for i in start..start + run {
1270 assert!(bits.value(i), "start {start} run {run} index {i}");
1271 }
1272 for i in start + run..start + run + 3 {
1273 assert!(!bits.value(i));
1274 }
1275 }
1276 }
1277 }
1278
1279 #[test]
1280 fn builder_append_slice_and_bitmap() {
1281 let mut builder = BitmapBuilder::with_capacity(16);
1282 builder.append_slice(&[true, false, true]);
1283 builder.append_bitmap(&bitmap_of(&[false, true]));
1284 let bits = builder.finish();
1285 assert_eq!(
1286 bits.iter().collect::<Vec<_>>(),
1287 vec![true, false, true, false, true]
1288 );
1289 }
1290
1291 #[test]
1292 fn builder_set_updates_the_running_count() {
1293 let mut builder = BitmapBuilder::new();
1294 builder.append_slice(&[true, false, true]);
1295 assert_eq!(builder.count_set(), 2);
1296 builder.set(1, true);
1297 assert_eq!(builder.count_set(), 3);
1298 builder.set(1, true);
1299 assert_eq!(builder.count_set(), 3, "idempotent");
1300 builder.set(0, false);
1301 assert_eq!(builder.count_set(), 2);
1302 builder.set(99, true);
1303 assert_eq!(builder.count_set(), 2, "out-of-range writes are ignored");
1304 assert_eq!(builder.get(1), Some(true));
1305 assert_eq!(builder.get(9), None);
1306 let bits = builder.finish();
1307 assert_eq!(bits.count_set(), 2);
1308 }
1309
1310 #[test]
1311 fn builder_clear_and_finish_cloned() {
1312 let mut builder: BitmapBuilder = [true, true, false].into_iter().collect();
1313 let snapshot = builder.finish_cloned();
1314 assert_eq!(snapshot.len(), 3);
1315 assert_eq!(builder.len(), 3, "finish_cloned keeps the builder");
1316 builder.clear();
1317 assert!(builder.is_empty());
1318 assert_eq!(builder.finish().len(), 0);
1319 assert_eq!(snapshot.count_set(), 2);
1320 }
1321
1322 #[test]
1323 fn builder_extend() {
1324 let mut builder = BitmapBuilder::new();
1325 builder.extend([true, false]);
1326 builder.extend(vec![true]);
1327 assert_eq!(builder.finish().count_set(), 2);
1328 }
1329
1330 #[test]
1331 fn debug_renders_bits() {
1332 let bits = bitmap_of(&[true, false, true]);
1333 let rendered = format!("{bits:?}");
1334 assert!(rendered.contains("101"), "{rendered}");
1335 assert!(rendered.contains("set: 2"), "{rendered}");
1336
1337 let long = Bitmap::new_set(200);
1338 assert!(format!("{long:?}").contains('…'));
1339 }
1340
1341 #[test]
1342 fn free_helpers_are_total() {
1343 let mut data = [0u8; 2];
1344 set_bit(&mut data, 0, true);
1345 set_bit(&mut data, 15, true);
1346 set_bit(&mut data, 99, true);
1347 assert_eq!(data, [0b0000_0001, 0b1000_0000]);
1348 assert!(get_bit(&data, 0));
1349 assert!(get_bit(&data, 15));
1350 assert!(!get_bit(&data, 16));
1351 set_bit(&mut data, 0, false);
1352 assert!(!get_bit(&data, 0));
1353 }
1354
1355 #[test]
1356 fn cached_count_survives_cloning() {
1357 let bits = bitmap_of(&[true, false, true, true]);
1358 assert_eq!(bits.count_set(), 3);
1359 let copy = bits.clone();
1360 assert_eq!(copy.count_set(), 3);
1361 assert_eq!(copy, bits);
1362 }
1363
1364 #[test]
1365 fn from_buffer_uses_every_bit() {
1366 let bits = Bitmap::from_buffer(Buffer::from_slice(&[0b0000_1111, 0]));
1367 assert_eq!(bits.len(), 16);
1368 assert_eq!(bits.count_set(), 4);
1369 assert_eq!(bits.buffer().len(), 2);
1370 }
1371}