light_bitmap/bitmap.rs
1use core::array::from_fn;
2use core::fmt::{Debug, Formatter};
3use core::iter::{FusedIterator, Iterator};
4use core::ops::{
5 BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Range, Shl, ShlAssign,
6 Shr, ShrAssign,
7};
8
9/// Computes the number of buckets needed to store `bit_count` bits.
10///
11/// It's recommended to inline this call as a const expression into the type
12/// annotation generics to avoid unnecessary panics.
13///
14/// # Examples
15/// ```
16/// use light_bitmap::bucket_count;
17///
18/// assert_eq!(bucket_count(9), 2);
19/// assert_eq!(bucket_count(16), 2);
20/// assert_eq!(bucket_count(17), 3);
21/// ```
22pub const fn bucket_count(bit_count: usize) -> usize {
23 bit_count.div_ceil(8)
24}
25
26#[allow(clippy::no_effect)]
27#[allow(clippy::unnecessary_operation)]
28pub(crate) const fn compile_assert_const_params(bit_count: usize, buckets: usize) {
29 // This will cause a compile-time error if bit_count == 0
30 ["BIT_COUNT must be greater than zero."][(bit_count == 0) as usize];
31 // This will cause a compile-time error if buckets != bucket_count(bit_count)
32 ["BUCKET_COUNT must match bucket_count(BIT_COUNT)."]
33 [(bucket_count(bit_count) != buckets) as usize];
34}
35
36pub(crate) fn runtime_assert_const_params(bit_count: usize, buckets: usize) {
37 assert_ne!(bit_count, 0, "BIT_COUNT must be greater than zero.");
38 assert_eq!(
39 bucket_count(bit_count),
40 buckets,
41 "BUCKET_COUNT must match bucket_count(BIT_COUNT)."
42 );
43}
44
45pub(crate) const fn ones_mask(start_bit: usize, width: usize) -> u8 {
46 if width >= 8 {
47 // shift would be undefined / panic on u8
48 !0u8
49 } else {
50 // if `1u8 << shift_amount` == 0 wrap around
51 (1u8 << width).wrapping_sub(1) << start_bit
52 }
53}
54
55/// The main type that stores the information.
56///
57/// `BIT_COUNT` is the number of usable bits.
58/// `BUCKET_COUNT` is the number of internal buckets needed and should only be
59/// set via const expression with [`bucket_count`] to avoid unnecessary panics
60/// (see [`new`]).
61///
62/// Internally stores bits in an array of `u8`.
63///
64/// [`new`]: BitMap::new
65#[derive(PartialEq, Eq, Hash, Clone, Copy)]
66pub struct BitMap<const BIT_COUNT: usize, const BUCKET_COUNT: usize>(pub(crate) [u8; BUCKET_COUNT]);
67
68impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitMap<BIT_COUNT, BUCKET_COUNT> {
69 /// Creates a new bitmap with all bits unset.
70 ///
71 /// # Panics
72 /// Panics if `BIT_COUNT == 0` or `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
73 ///
74 /// # Examples
75 /// ```
76 /// use light_bitmap::{BitMap, bucket_count};
77 ///
78 /// let bitmap = BitMap::<16, { bucket_count(16) }>::new();
79 /// assert_eq!(bitmap.popcount(), 0);
80 /// ```
81 pub fn new() -> Self {
82 runtime_assert_const_params(BIT_COUNT, BUCKET_COUNT);
83 Self([0u8; BUCKET_COUNT])
84 }
85
86 /// Creates a new `const` bitmap with all bits unset.
87 ///
88 /// Equivalent to [`new`], but callable in compile-time contexts such as
89 /// const initialization.
90 ///
91 /// # Compiler Errors
92 /// Prevents compilation if either `BIT_COUNT == 0` or `BUCKET_COUNT !=
93 /// bucket_count(bit_count)` with an unintuitive message like `evaluation of
94 /// constant value failed` and `index out of bounds: the length is 1 but the
95 /// index is 1`.
96 ///
97 /// # Examples
98 /// ```
99 /// use light_bitmap::{BitMap, bucket_count};
100 ///
101 /// const EMPTY: BitMap<8, { bucket_count(8) }> = BitMap::const_empty();
102 /// assert_eq!(EMPTY.popcount(), 0);
103 /// ```
104 ///
105 /// [`new`]: BitMap::new
106 pub const fn const_empty() -> Self {
107 compile_assert_const_params(BIT_COUNT, BUCKET_COUNT);
108 Self([0u8; BUCKET_COUNT])
109 }
110
111 /// Creates a new bitmap with all bits set.
112 ///
113 /// # Panics
114 /// Panics if `BIT_COUNT == 0` or `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
115 ///
116 /// # Examples
117 /// ```
118 /// use light_bitmap::{BitMap, bucket_count};
119 ///
120 /// let bitmap = BitMap::<10, { bucket_count(10) }>::with_all_set();
121 /// assert_eq!(bitmap.popcount(), 10);
122 /// ```
123 #[inline]
124 pub fn with_all_set() -> Self {
125 runtime_assert_const_params(BIT_COUNT, BUCKET_COUNT);
126 let mut bm = Self([!0u8; BUCKET_COUNT]);
127 bm.clean_unused_bits();
128 bm
129 }
130
131 /// Creates a new `const` bitmap with all bits set.
132 ///
133 /// Equivalent to [`with_all_set`], but callable in compile-time contexts
134 /// such as const initialization.
135 ///
136 /// # Compiler Errors
137 /// Prevents compilation if either `BIT_COUNT == 0` or `BUCKET_COUNT !=
138 /// bucket_count(bit_count)` with an unintuitive message like `evaluation of
139 /// constant value failed` and `index out of bounds: the length is 1 but the
140 /// index is 1`.
141 ///
142 /// # Examples
143 /// ```
144 /// use light_bitmap::{BitMap, bucket_count};
145 ///
146 /// const FULL: BitMap<10, { bucket_count(10) }> = BitMap::const_full();
147 /// assert_eq!(FULL.popcount(), 10);
148 /// ```
149 ///
150 /// [`with_all_set`]: BitMap::with_all_set
151 pub const fn const_full() -> Self {
152 compile_assert_const_params(BIT_COUNT, BUCKET_COUNT);
153 let mut bm = Self([!0u8; BUCKET_COUNT]);
154 bm.clean_unused_bits();
155 bm
156 }
157
158 /// Constructs a bitmap from a boolean slice, where `true` means set.
159 ///
160 /// # Panics
161 /// Panics if the slice length doesn't match `BIT_COUNT`, if `BIT_COUNT == 0`
162 /// or if `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
163 ///
164 /// # Examples
165 /// ```
166 /// use light_bitmap::{BitMap, bucket_count};
167 ///
168 /// let bitmap = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
169 /// assert_eq!(bitmap.popcount(), 2);
170 /// ```
171 #[inline]
172 pub fn from_slice(bits: &[bool]) -> Self {
173 runtime_assert_const_params(BIT_COUNT, BUCKET_COUNT);
174 assert_eq!(bits.len(), BIT_COUNT);
175 let mut bm = Self([0u8; BUCKET_COUNT]);
176 for (idx, bit) in bits.iter().enumerate() {
177 if *bit {
178 bm.set(idx)
179 }
180 }
181 bm
182 }
183
184 /// Constructs a bitmap by setting only the indices provided in the iterator.
185 ///
186 /// All unspecified indices are left unset.
187 ///
188 /// # Panics
189 /// Panics if any index is out of bounds (i.e., `>= BIT_COUNT`), if
190 /// `BIT_COUNT == 0` or if `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
191 ///
192 /// # Examples
193 /// ```
194 /// use light_bitmap::{BitMap, bucket_count};
195 ///
196 /// let bitmap = BitMap::<5, { bucket_count(5) }>::from_ones_iter([0, 2, 4]);
197 /// assert!(bitmap.is_set(0));
198 /// assert!(!bitmap.is_set(1));
199 /// assert_eq!(bitmap.popcount(), 3);
200 /// ```
201 pub fn from_ones_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
202 runtime_assert_const_params(BIT_COUNT, BUCKET_COUNT);
203 let mut bitmap = Self::new();
204 for idx in iter {
205 assert!(idx < BIT_COUNT, "Bit index {idx} out of bounds");
206 bitmap.set(idx);
207 }
208 bitmap
209 }
210
211 /// Sets the bit at the given index.
212 ///
213 /// # Panics
214 /// Panics if the index is out of bounds (i.e., `>= BIT_COUNT`).
215 ///
216 /// # Examples
217 /// ```
218 /// use light_bitmap::{BitMap, bucket_count};
219 ///
220 /// let mut bm = BitMap::<8, { bucket_count(8) }>::new();
221 /// assert!(!bm.is_set(3));
222 /// bm.set(3);
223 /// assert!(bm.is_set(3));
224 /// ```
225 #[inline]
226 pub fn set(&mut self, idx: usize) {
227 assert!(idx < BIT_COUNT, "Bit index {idx} out of bounds");
228 let (group_idx, item_idx) = Self::idxs(idx);
229 self.0[group_idx] |= 1 << item_idx;
230 }
231
232 /// Sets all bits in the given range.
233 ///
234 /// # Panics
235 /// Panics if `range.start >= BIT_COUNT` or `range.end > BIT_COUNT`.
236 ///
237 /// # Examples
238 /// ```
239 /// use light_bitmap::{BitMap, bucket_count};
240 ///
241 /// let mut bm = BitMap::<8, { bucket_count(8) }>::new();
242 /// bm.set_range(2..6);
243 /// assert!(bm.is_set(2));
244 /// assert!(bm.is_set(5));
245 /// assert!(!bm.is_set(6));
246 /// ```
247 pub fn set_range(&mut self, range: Range<usize>) {
248 assert!(
249 range.start < BIT_COUNT,
250 "Range start {} out of bounds",
251 range.start
252 );
253 assert!(
254 range.end <= BIT_COUNT,
255 "Range end {} out of bounds",
256 range.end
257 );
258
259 if range.start >= range.end {
260 return;
261 }
262
263 let (start_byte, start_bit) = Self::idxs(range.start);
264 let (end_byte, end_bit) = Self::idxs(range.end - 1);
265
266 // all within one byte
267 if start_byte == end_byte {
268 let width = end_bit - start_bit + 1;
269 let mask = ones_mask(start_bit, width);
270 self.0[start_byte] |= mask;
271 return;
272 }
273
274 // set bits in first byte
275 let first_mask = !0u8 << start_bit;
276 self.0[start_byte] |= first_mask;
277
278 // set full bytes in between
279 for byte in &mut self.0[start_byte + 1..end_byte] {
280 *byte = !0;
281 }
282
283 // set bits in last byte
284 let width = end_bit + 1;
285 let last_mask = ones_mask(0, width);
286 self.0[end_byte] |= last_mask;
287 }
288
289 /// Unsets the bit at the given index.
290 ///
291 /// # Panics
292 /// Panics if `idx >= BIT_COUNT`.
293 ///
294 /// # Examples
295 /// ```
296 /// use light_bitmap::{BitMap, bucket_count};
297 ///
298 /// let mut bm = BitMap::<8, { bucket_count(8) }>::with_all_set();
299 /// assert!(bm.is_set(3));
300 /// bm.unset(3);
301 /// assert!(!bm.is_set(3));
302 /// ```
303 #[inline]
304 pub fn unset(&mut self, idx: usize) {
305 assert!(idx < BIT_COUNT, "Bit index {idx} out of bounds");
306 let (group_idx, item_idx) = Self::idxs(idx);
307 self.0[group_idx] &= !(1 << item_idx);
308 }
309
310 /// Unsets all bits in the given range.
311 ///
312 /// # Panics
313 /// Panics if `range.start >= BIT_COUNT` or `range.end > BIT_COUNT`.
314 ///
315 /// # Examples
316 /// ```
317 /// use light_bitmap::{BitMap, bucket_count};
318 ///
319 /// let mut bm = BitMap::<8, { bucket_count(8) }>::with_all_set();
320 /// bm.unset_range(2..6);
321 /// assert!(!bm.is_set(2));
322 /// assert!(!bm.is_set(5));
323 /// assert!(bm.is_set(6));
324 /// ```
325 pub fn unset_range(&mut self, range: Range<usize>) {
326 assert!(
327 range.start < BIT_COUNT,
328 "Range start {} out of bounds",
329 range.start
330 );
331 assert!(
332 range.end <= BIT_COUNT,
333 "Range end {} out of bounds",
334 range.end
335 );
336
337 if range.start >= range.end {
338 return;
339 }
340
341 let (start_byte, start_bit) = Self::idxs(range.start);
342 let (end_byte, end_bit) = Self::idxs(range.end - 1);
343
344 // all within one byte
345 if start_byte == end_byte {
346 let width = end_bit - start_bit + 1;
347 let mask = !ones_mask(start_bit, width);
348 self.0[start_byte] &= mask;
349 return;
350 }
351
352 // unset bits in first byte
353 let first_mask = (1u8 << start_bit) - 1;
354 self.0[start_byte] &= first_mask;
355
356 // unset full bytes in between
357 for byte in &mut self.0[start_byte + 1..end_byte] {
358 *byte = 0;
359 }
360
361 // unset bits in last byte
362 let width = end_bit + 1;
363 let last_mask = !ones_mask(0, width);
364 self.0[end_byte] &= last_mask;
365 }
366
367 /// Toggles the bit at the given index.
368 ///
369 /// Returns the previous value of the bit (before the toggle).
370 ///
371 /// # Panics
372 /// Panics if `idx >= BIT_COUNT`.
373 ///
374 /// # Examples
375 /// ```
376 /// use light_bitmap::{BitMap, bucket_count};
377 ///
378 /// let mut bm = BitMap::<8, { bucket_count(8) }>::new();
379 /// assert_eq!(bm.toggle(4), false); // flipped from false to true
380 /// assert_eq!(bm.toggle(4), true); // flipped from true to false
381 /// ```
382 #[inline]
383 pub fn toggle(&mut self, idx: usize) -> bool {
384 assert!(idx < BIT_COUNT, "Bit index {idx} out of bounds");
385 let (group_idx, item_idx) = Self::idxs(idx);
386 let bit = self.0[group_idx] & 1 << item_idx != 0;
387 self.0[group_idx] ^= 1 << item_idx;
388 bit
389 }
390
391 /// Returns `true` if the bit at the given index is set.
392 ///
393 /// # Panics
394 /// Panics if `idx >= BIT_COUNT`.
395 ///
396 /// # Examples
397 /// ```
398 /// use light_bitmap::{BitMap, bucket_count};
399 ///
400 /// let mut bm = BitMap::<8, { bucket_count(8) }>::new();
401 /// bm.set(1);
402 /// assert!(bm.is_set(1));
403 /// assert!(!bm.is_set(0));
404 /// ```
405 #[inline]
406 pub fn is_set(&self, idx: usize) -> bool {
407 assert!(idx < BIT_COUNT, "Bit index {idx} out of bounds");
408 let (group_idx, item_idx) = Self::idxs(idx);
409 self.0[group_idx] & 1 << item_idx != 0
410 }
411
412 #[inline]
413 fn idxs(idx: usize) -> (usize, usize) {
414 (idx / 8, idx % 8)
415 }
416
417 /// Returns an iterator over all bits as `bool`, from least to most significant.
418 ///
419 /// The iterator yields exactly `BIT_COUNT` items in order.
420 ///
421 /// # Examples
422 /// ```
423 /// use light_bitmap::{BitMap, bucket_count};
424 /// use core::array::from_fn;
425 ///
426 ///
427 /// let bm = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
428 /// let mut bm_iter = bm.iter();
429 /// assert_eq!(from_fn(|_| bm_iter.next().unwrap()), [true, false, true, false]);
430 /// ```
431 #[inline]
432 pub fn iter(&self) -> BitMapIter<BIT_COUNT, BUCKET_COUNT> {
433 BitMapIter {
434 bytes: &self.0,
435 group_idx: 0,
436 item_idx: 0,
437 }
438 }
439
440 /// Returns an iterator over the indices of all set bits, in ascending
441 /// order.
442 ///
443 /// The iterator yields up to `BIT_COUNT` indices and is guaranteed to
444 /// terminate. Iterating through the entire iterator runs in is O(max(k, b))
445 /// where k is the number of set bits and b is the number of buckets.
446 ///
447 /// # Examples
448 /// ```
449 /// use light_bitmap::{BitMap, bucket_count};
450 /// use core::array::from_fn;
451 ///
452 /// let bm = BitMap::<5, { bucket_count(5) }>::from_slice(&[true, false, true, false, true]);
453 /// let mut ones_iter = bm.iter_ones();
454 /// let ones = from_fn(|i| ones_iter.next().unwrap_or(999));
455 /// assert_eq!(ones, [0, 2, 4, 999, 999]);
456 /// ```
457 #[inline]
458 pub fn iter_ones(&self) -> IterOnes<BIT_COUNT, BUCKET_COUNT> {
459 IterOnes {
460 bytes: &self.0,
461 byte_idx: 0,
462 current: self.0[0],
463 base_bit_idx: 0,
464 }
465 }
466
467 /// Returns an iterator over the indices of all unset bits, in ascending
468 /// order.
469 ///
470 /// The iterator yields up to `BIT_COUNT` indices and is guaranteed to
471 /// terminate. Iterating through the entire iterator runs in is O(max(k, b))
472 /// where k is the number of unset bits and b is the number of buckets.
473 ///
474 /// # Examples
475 /// ```
476 /// use light_bitmap::{BitMap, bucket_count};
477 /// use core::array::from_fn;
478 ///
479 /// let bm = BitMap::<5, { bucket_count(5) }>::from_slice(&[true, false, true, false, true]);
480 /// let mut zeros_iter = bm.iter_zeros();
481 /// let zeros = from_fn(|i| zeros_iter.next().unwrap_or(999));
482 /// assert_eq!(zeros, [1, 3, 999, 999, 999]);
483 /// ```
484 #[inline]
485 pub fn iter_zeros(&self) -> IterZeros<BIT_COUNT, BUCKET_COUNT> {
486 IterZeros {
487 bytes: &self.0,
488 byte_idx: 0,
489 current: !self.0[0],
490 base_bit_idx: 0,
491 }
492 }
493
494 /// Returns a new bitmap representing the bitwise OR of `self` and `other`.
495 ///
496 /// Each bit in the result is set if it is set in either operand.
497 ///
498 /// # Examples
499 /// ```
500 /// use light_bitmap::{BitMap, bucket_count};
501 ///
502 /// let a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
503 /// let b = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, true, false]);
504 /// let c = a.bit_or(&b);
505 /// assert_eq!(c, BitMap::<4, { bucket_count(4) }>::from_slice(&[true, true, true, false]));
506 /// ```
507 #[inline]
508 pub fn bit_or(&self, other: &Self) -> Self {
509 Self(from_fn(|i| self.0[i] | other.0[i]))
510 }
511
512 /// Performs an in-place bitwise OR with another bitmap.
513 ///
514 /// Each bit in `self` is updated to the result of `self | other`.
515 ///
516 /// # Examples
517 /// ```
518 /// use light_bitmap::{BitMap, bucket_count};
519 ///
520 /// let mut a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
521 /// let b = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, true, false]);
522 /// a.in_place_bit_or(&b);
523 /// assert_eq!(a, BitMap::<4, { bucket_count(4) }>::from_slice(&[true, true, true, false]));
524 /// ```
525 #[inline]
526 pub fn in_place_bit_or(&mut self, other: &Self) {
527 for (self_byte, other_byte) in self.0.iter_mut().zip(other.0.iter()) {
528 *self_byte |= other_byte
529 }
530 }
531
532 /// Returns a new bitmap representing the bitwise AND of `self` and `other`.
533 ///
534 /// Each bit in the result is set only if it is set in both operands.
535 ///
536 /// # Examples
537 /// ```
538 /// use light_bitmap::{BitMap, bucket_count};
539 ///
540 /// let a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
541 /// let b = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, true, false]);
542 /// let c = a.bit_and(&b);
543 /// assert_eq!(c, BitMap::<4, { bucket_count(4) }>::from_slice(&[false, false, true, false]));
544 /// ```
545 #[inline]
546 pub fn bit_and(&self, other: &Self) -> Self {
547 Self(from_fn(|i| self.0[i] & other.0[i]))
548 }
549
550 /// Performs an in-place bitwise AND with another bitmap.
551 ///
552 /// Each bit in `self` is updated to the result of `self & other`.
553 ///
554 /// # Examples
555 /// ```
556 /// use light_bitmap::{BitMap, bucket_count};
557 ///
558 /// let mut a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
559 /// let b = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, true, false]);
560 /// a.in_place_bit_and(&b);
561 /// assert_eq!(a, BitMap::<4, { bucket_count(4) }>::from_slice(&[false, false, true, false]));
562 /// ```
563 #[inline]
564 pub fn in_place_bit_and(&mut self, other: &Self) {
565 for (self_byte, other_byte) in self.0.iter_mut().zip(other.0.iter()) {
566 *self_byte &= other_byte
567 }
568 }
569
570 /// Returns a new bitmap representing the bitwise XOR of `self` and `other`.
571 ///
572 /// Each bit in the result is set if it differs between the operands.
573 ///
574 /// # Examples
575 /// ```
576 /// use light_bitmap::{BitMap, bucket_count};
577 ///
578 /// let a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
579 /// let b = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, true, false]);
580 /// let c = a.bit_xor(&b);
581 /// assert_eq!(c, BitMap::<4, { bucket_count(4) }>::from_slice(&[true, true, false, false]));
582 /// ```
583 #[inline]
584 pub fn bit_xor(&self, other: &Self) -> Self {
585 Self(from_fn(|i| self.0[i] ^ other.0[i]))
586 }
587
588 /// Performs an in-place bitwise XOR with another bitmap.
589 ///
590 /// Each bit in `self` is updated to the result of `self ^ other`.
591 ///
592 /// # Examples
593 /// ```
594 /// use light_bitmap::{BitMap, bucket_count};
595 ///
596 /// let mut a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
597 /// let b = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, true, false]);
598 /// a.in_place_bit_xor(&b);
599 /// assert_eq!(a, BitMap::<4, { bucket_count(4) }>::from_slice(&[true, true, false, false]));
600 /// ```
601 #[inline]
602 pub fn in_place_bit_xor(&mut self, other: &Self) {
603 for (self_byte, other_byte) in self.0.iter_mut().zip(other.0.iter()) {
604 *self_byte ^= other_byte
605 }
606 }
607
608 /// Returns a new bitmap with each bit inverted (bitwise NOT).
609 ///
610 /// Each bit in the result is the inverse of the corresponding bit in self.
611 ///
612 /// # Examples
613 /// ```
614 /// use light_bitmap::{BitMap, bucket_count};
615 ///
616 /// let a = BitMap::<4, { bucket_count(4) }>::from_slice(&[false, false, true, false]);
617 /// let b = a.bit_not();
618 /// assert_eq!(b, BitMap::<4, { bucket_count(4) }>::from_slice(&[true, true, false, true]));
619 /// ```
620 #[inline]
621 pub fn bit_not(&self) -> Self {
622 let mut result = Self(from_fn(|i| !self.0[i]));
623 result.clean_unused_bits();
624 result
625 }
626
627 /// Inverts each bit of the bitmap in-place (bitwise NOT).
628 ///
629 /// Each bit in `self` is updated to the inverse of the corresponding bit in
630 /// self.
631 ///
632 /// # Examples
633 /// ```
634 /// use light_bitmap::{BitMap, bucket_count};
635 ///
636 /// let mut a = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
637 /// a.in_place_bit_not();
638 /// assert_eq!(a, BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, false, true]));
639 /// ```
640 #[inline]
641 pub fn in_place_bit_not(&mut self) {
642 for byte in &mut self.0 {
643 *byte = !*byte;
644 }
645 self.clean_unused_bits();
646 }
647
648 /// Returns the number of set bits in the bitmap.
649 ///
650 /// # Examples
651 /// ```
652 /// use light_bitmap::{BitMap, bucket_count};
653 ///
654 /// let bm = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
655 /// assert_eq!(bm.popcount(), 2);
656 /// ```
657 #[inline]
658 pub fn popcount(&self) -> usize {
659 self.0.iter().map(|b| b.count_ones() as usize).sum()
660 }
661
662 /// Returns the index of the first set bit or `None` if all bits are unset.
663 ///
664 /// Bits are checked in ascending order from least to most significant.
665 /// Returns `None` if all bits are unset. Runs in O(b) where b is the bucket
666 /// count.
667 ///
668 /// # Examples
669 /// ```
670 /// use light_bitmap::{BitMap, bucket_count};
671 ///
672 /// let empty = BitMap::<4, { bucket_count(4) }>::new();
673 /// assert_eq!(empty.first_set_bit(), None);
674 ///
675 /// let mut bm = BitMap::<4, { bucket_count(4) }>::new();
676 /// bm.set(2);
677 /// assert_eq!(bm.first_set_bit(), Some(2));
678 /// ```
679 pub fn first_set_bit(&self) -> Option<usize> {
680 for (i, byte) in self.0.iter().enumerate() {
681 if *byte != 0 {
682 let bit = byte.trailing_zeros() as usize;
683 return Some(i * 8 + bit);
684 }
685 }
686 None
687 }
688
689 #[inline]
690 const fn clean_unused_bits(&mut self) {
691 let bits_in_last = BIT_COUNT % 8;
692 if bits_in_last != 0 {
693 let mask = (1 << bits_in_last) - 1;
694 self.0[BUCKET_COUNT - 1] &= mask;
695 }
696 }
697
698 /// Does a left shift by `n` positions, filling with unset bits. This means
699 /// bits are shifted towards higher bit indices.
700 ///
701 /// Bits that are shifted beyond `BIT_COUNT` are lost.
702 /// If `n >= BIT_COUNT`, the bitmap is cleared.
703 ///
704 /// # Examples
705 /// ```
706 /// use light_bitmap::{BitMap, bucket_count};
707 ///
708 /// let mut bm = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
709 /// bm.shift_left(1);
710 /// assert_eq!(bm, BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, false, true]));
711 /// ```
712 pub fn shift_left(&mut self, n: usize) {
713 if n >= BIT_COUNT {
714 self.0.fill(0);
715 return;
716 }
717 let (byte_shift, bit_shift) = Self::idxs(n);
718
719 if byte_shift > 0 {
720 for i in (byte_shift..BUCKET_COUNT).rev() {
721 self.0[i] = self.0[i - byte_shift];
722 }
723 for i in 0..byte_shift {
724 self.0[i] = 0;
725 }
726 }
727
728 if bit_shift > 0 {
729 for i in (0..BUCKET_COUNT).rev() {
730 let high = *self.0.get(i.wrapping_sub(1)).unwrap_or(&0);
731 self.0[i] <<= bit_shift;
732 self.0[i] |= high >> (8 - bit_shift);
733 }
734 }
735
736 self.clean_unused_bits();
737 }
738
739 /// Does a right shift by `n` positions, filling with unset bits. This means
740 /// bits are shifted towards lower bit indices.
741 ///
742 /// Bits that are shifted beyond index 0 are lost.
743 /// If `n >= BIT_COUNT`, the bitmap is cleared.
744 ///
745 /// # Examples
746 /// ```
747 /// use light_bitmap::{BitMap, bucket_count};
748 ///
749 /// let mut bm = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, true, false]);
750 /// bm.shift_right(1);
751 /// assert_eq!(bm, BitMap::<4, { bucket_count(4) }>::from_slice(&[false, true, false, false]));
752 /// ```
753 pub fn shift_right(&mut self, n: usize) {
754 if n >= BIT_COUNT {
755 self.0.fill(0);
756 return;
757 }
758 self.clean_unused_bits();
759
760 let byte_shift = n / 8;
761 let bit_shift = n % 8;
762
763 if byte_shift > 0 {
764 for i in 0..BUCKET_COUNT - byte_shift {
765 self.0[i] = self.0[i + byte_shift];
766 }
767 for i in byte_shift..BUCKET_COUNT {
768 self.0[i] = 0;
769 }
770 }
771
772 if bit_shift > 0 {
773 for i in 0..BUCKET_COUNT {
774 let low = *self.0.get(i.wrapping_add(1)).unwrap_or(&0);
775 self.0[i] >>= bit_shift;
776 self.0[i] |= low << (8 - bit_shift);
777 }
778 }
779 }
780
781 /// Rotates all bits in direction of higher bit indices by `n` positions.
782 /// Bits shifted out are reinserted on the other side.
783 ///
784 /// # Panics
785 /// Panics if `BIT_COUNT == 0` or `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
786 ///
787 /// # Examples
788 /// ```
789 /// use light_bitmap::{BitMap, bucket_count};
790 ///
791 /// let mut bm = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, false, true]);
792 /// bm.rotate_left(1);
793 /// assert_eq!(bm, BitMap::<4, { bucket_count(4) }>::from_slice(&[true, true, false, false]));
794 /// ```
795 pub fn rotate_left(&mut self, n: usize) {
796 // avoid division by zero
797 runtime_assert_const_params(BIT_COUNT, BUCKET_COUNT);
798 if n % BIT_COUNT == 0 {
799 return;
800 }
801 let n = n % BIT_COUNT;
802 let mut prev = self.is_set((BIT_COUNT - n) % BIT_COUNT);
803 let mut bit_idx = 0;
804 let mut start_idx = 0;
805 for _ in 0..BIT_COUNT {
806 let temp = self.is_set(bit_idx);
807 if prev {
808 self.set(bit_idx)
809 } else {
810 self.unset(bit_idx);
811 }
812 prev = temp;
813 bit_idx = (bit_idx + n) % BIT_COUNT;
814 if bit_idx == start_idx {
815 start_idx += 1;
816 bit_idx += 1;
817 prev = self.is_set((bit_idx + BIT_COUNT - n) % BIT_COUNT)
818 }
819 }
820 }
821
822 /// Rotates all bits in direction of lower bit indices by `n` positions.
823 /// Bits shifted out are reinserted on the other side.
824 ///
825 /// # Panics
826 /// Panics if `BIT_COUNT == 0` or `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
827 ///
828 /// # Examples
829 /// ```
830 /// use light_bitmap::{BitMap, bucket_count};
831 ///
832 /// let mut bm = BitMap::<4, { bucket_count(4) }>::from_slice(&[true, false, false, true]);
833 /// bm.rotate_right(1);
834 /// assert_eq!(bm, BitMap::<4, { bucket_count(4) }>::from_slice(&[false, false, true, true]));
835 /// ```
836 pub fn rotate_right(&mut self, n: usize) {
837 self.rotate_left(BIT_COUNT - n % BIT_COUNT);
838 }
839}
840
841impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Default
842 for BitMap<BIT_COUNT, BUCKET_COUNT>
843{
844 fn default() -> Self {
845 Self::new()
846 }
847}
848
849impl<'bitmap, const BIT_COUNT: usize, const BUCKET_COUNT: usize> IntoIterator
850 for &'bitmap BitMap<BIT_COUNT, BUCKET_COUNT>
851{
852 type Item = bool;
853 type IntoIter = BitMapIter<'bitmap, BIT_COUNT, BUCKET_COUNT>;
854
855 fn into_iter(self) -> Self::IntoIter {
856 self.iter()
857 }
858}
859
860impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Debug for BitMap<BIT_COUNT, BUCKET_COUNT> {
861 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
862 write!(f, "LSB -> ")?;
863 for (i, bit) in self.iter().enumerate() {
864 if i % 8 == 0 {
865 write!(f, "{i}: ")?;
866 }
867 write!(f, "{}", if bit { '1' } else { '0' })?;
868 if i % 8 == 7 && i < BUCKET_COUNT * 8 - 1 {
869 write!(f, " ")?;
870 }
871 }
872 write!(f, " <- MSB")?;
873 Ok(())
874 }
875}
876
877/// Constructs a bitmap from an iterator over `bool`s.
878///
879/// # Panics
880/// Panics if the iterator yields more or fewer than `BIT_COUNT` elements, if
881/// `BIT_COUNT == 0` or if `BUCKET_COUNT != bucket_count(BIT_COUNT)`.
882impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> FromIterator<bool>
883 for BitMap<BIT_COUNT, BUCKET_COUNT>
884{
885 fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
886 runtime_assert_const_params(BIT_COUNT, BUCKET_COUNT);
887 let mut bm = Self::new();
888 let mut idx = 0;
889
890 for bit in iter {
891 if idx >= BIT_COUNT {
892 panic!("Iterator yielded more than {BIT_COUNT} elements");
893 }
894 if bit {
895 bm.set(idx);
896 }
897 idx += 1;
898 }
899
900 if idx != BIT_COUNT {
901 panic!("Iterator yielded fewer than {BIT_COUNT} elements");
902 }
903
904 bm
905 }
906}
907
908impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitAnd for BitMap<BIT_COUNT, BUCKET_COUNT> {
909 type Output = Self;
910
911 fn bitand(self, rhs: Self) -> Self::Output {
912 self.bit_and(&rhs)
913 }
914}
915
916impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitAndAssign
917 for BitMap<BIT_COUNT, BUCKET_COUNT>
918{
919 fn bitand_assign(&mut self, rhs: Self) {
920 self.in_place_bit_and(&rhs)
921 }
922}
923
924impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitOr for BitMap<BIT_COUNT, BUCKET_COUNT> {
925 type Output = Self;
926
927 fn bitor(self, rhs: Self) -> Self::Output {
928 self.bit_or(&rhs)
929 }
930}
931
932impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitOrAssign
933 for BitMap<BIT_COUNT, BUCKET_COUNT>
934{
935 fn bitor_assign(&mut self, rhs: Self) {
936 self.in_place_bit_or(&rhs)
937 }
938}
939
940impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitXor for BitMap<BIT_COUNT, BUCKET_COUNT> {
941 type Output = Self;
942
943 fn bitxor(self, rhs: Self) -> Self::Output {
944 self.bit_xor(&rhs)
945 }
946}
947
948impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> BitXorAssign
949 for BitMap<BIT_COUNT, BUCKET_COUNT>
950{
951 fn bitxor_assign(&mut self, rhs: Self) {
952 self.in_place_bit_xor(&rhs)
953 }
954}
955
956impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Not for BitMap<BIT_COUNT, BUCKET_COUNT> {
957 type Output = Self;
958
959 fn not(self) -> Self::Output {
960 self.bit_not()
961 }
962}
963
964impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Shl<usize>
965 for BitMap<BIT_COUNT, BUCKET_COUNT>
966{
967 type Output = Self;
968
969 fn shl(mut self, rhs: usize) -> Self::Output {
970 self.shift_left(rhs);
971 self
972 }
973}
974
975impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> ShlAssign<usize>
976 for BitMap<BIT_COUNT, BUCKET_COUNT>
977{
978 fn shl_assign(&mut self, rhs: usize) {
979 self.shift_left(rhs);
980 }
981}
982
983impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Shr<usize>
984 for BitMap<BIT_COUNT, BUCKET_COUNT>
985{
986 type Output = Self;
987
988 fn shr(mut self, rhs: usize) -> Self::Output {
989 self.shift_right(rhs);
990 self
991 }
992}
993
994impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> ShrAssign<usize>
995 for BitMap<BIT_COUNT, BUCKET_COUNT>
996{
997 fn shr_assign(&mut self, rhs: usize) {
998 self.shift_right(rhs);
999 }
1000}
1001
1002/// Iterator over all bits in the bitmap as `bool` values.
1003///
1004/// Yields `true` for set bits and `false` for unset bits, starting from index 0.
1005///
1006/// Returned by [`BitMap::iter()`].
1007#[derive(Clone, Copy)]
1008pub struct BitMapIter<'bitmap, const BIT_COUNT: usize, const BUCKET_COUNT: usize> {
1009 bytes: &'bitmap [u8; BUCKET_COUNT],
1010 group_idx: usize,
1011 item_idx: usize,
1012}
1013
1014impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Iterator
1015 for BitMapIter<'_, BIT_COUNT, BUCKET_COUNT>
1016{
1017 type Item = bool;
1018
1019 fn next(&mut self) -> Option<Self::Item> {
1020 let absolute_idx = self.group_idx * 8 + self.item_idx;
1021 if absolute_idx >= BIT_COUNT {
1022 return None;
1023 }
1024 let bit = self.bytes[self.group_idx] & 1 << self.item_idx;
1025 self.item_idx += 1;
1026 if self.item_idx == 8 {
1027 self.item_idx = 0;
1028 self.group_idx += 1;
1029 }
1030 Some(bit != 0)
1031 }
1032}
1033
1034impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> FusedIterator
1035 for BitMapIter<'_, BIT_COUNT, BUCKET_COUNT>
1036{
1037}
1038
1039/// Iterator over the indices of set bits in the bitmap.
1040///
1041/// Yields the positions of all bits that are set, in ascending order.
1042///
1043/// Returned by [`BitMap::iter_ones()`].
1044#[derive(Clone, Copy)]
1045pub struct IterOnes<'bitmap, const BIT_COUNT: usize, const BUCKET_COUNT: usize> {
1046 bytes: &'bitmap [u8; BUCKET_COUNT],
1047 byte_idx: usize,
1048 current: u8,
1049 base_bit_idx: usize,
1050}
1051
1052impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Iterator
1053 for IterOnes<'_, BIT_COUNT, BUCKET_COUNT>
1054{
1055 type Item = usize;
1056
1057 fn next(&mut self) -> Option<Self::Item> {
1058 while self.byte_idx < BUCKET_COUNT {
1059 if self.current != 0 {
1060 let tz = self.current.trailing_zeros() as usize;
1061 let idx = self.base_bit_idx + tz;
1062 if idx >= BIT_COUNT {
1063 return None;
1064 }
1065 self.current &= self.current - 1; // unset LSB
1066 return Some(idx);
1067 }
1068
1069 self.byte_idx += 1;
1070 self.base_bit_idx += 8;
1071 self.current = *self.bytes.get(self.byte_idx).unwrap_or(&0);
1072 }
1073 None
1074 }
1075}
1076
1077impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> FusedIterator
1078 for IterOnes<'_, BIT_COUNT, BUCKET_COUNT>
1079{
1080}
1081
1082/// Iterator over the indices of unset bits in the bitmap.
1083///
1084/// Yields the positions of all bits that are unset, in ascending order.
1085///
1086/// Returned by [`BitMap::iter_zeros()`].
1087#[derive(Clone, Copy)]
1088pub struct IterZeros<'bitmap, const BIT_COUNT: usize, const BUCKET_COUNT: usize> {
1089 bytes: &'bitmap [u8; BUCKET_COUNT],
1090 byte_idx: usize,
1091 current: u8,
1092 base_bit_idx: usize,
1093}
1094
1095impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> Iterator
1096 for IterZeros<'_, BIT_COUNT, BUCKET_COUNT>
1097{
1098 type Item = usize;
1099
1100 fn next(&mut self) -> Option<Self::Item> {
1101 while self.byte_idx < BUCKET_COUNT {
1102 if self.current != 0 {
1103 let tz = self.current.trailing_zeros() as usize;
1104 let idx = self.base_bit_idx + tz;
1105 if idx >= BIT_COUNT {
1106 self.current = 0; // avoid entering if block once exhausted
1107 return None;
1108 }
1109 self.current &= self.current - 1; // unset LSB
1110 return Some(idx);
1111 }
1112
1113 self.byte_idx += 1;
1114 self.base_bit_idx += 8;
1115 self.current = !*self.bytes.get(self.byte_idx).unwrap_or(&0);
1116 }
1117 None
1118 }
1119}
1120
1121impl<const BIT_COUNT: usize, const BUCKET_COUNT: usize> FusedIterator
1122 for IterZeros<'_, BIT_COUNT, BUCKET_COUNT>
1123{
1124}