1#![no_std]
17#![allow(unknown_lints)]
19#![deny(clippy::undocumented_unsafe_blocks)]
20#![allow(unused_unsafe)]
24
25extern crate alloc;
26use alloc::{vec, vec::Vec};
27
28mod block;
29mod range;
30
31#[cfg(feature = "serde")]
32extern crate serde;
33#[cfg(feature = "serde")]
34mod serde_impl;
35
36use core::fmt::Write;
37use core::fmt::{Binary, Display, Error, Formatter};
38
39use core::cmp::Ordering;
40use core::hash::Hash;
41use core::iter::{Chain, FusedIterator};
42use core::mem::ManuallyDrop;
43use core::mem::MaybeUninit;
44use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Index};
45use core::ptr::NonNull;
46pub use range::IndexRange;
47
48pub(crate) const BITS: usize = core::mem::size_of::<Block>() * 8;
49#[cfg(feature = "serde")]
50pub(crate) const BYTES: usize = core::mem::size_of::<Block>();
51
52use block::Block as SimdBlock;
53pub type Block = usize;
54
55#[inline]
56fn div_rem(x: usize, denominator: usize) -> (usize, usize) {
57 (x / denominator, x % denominator)
58}
59
60fn vec_into_parts<T>(vec: Vec<T>) -> (NonNull<T>, usize, usize) {
61 let mut vec = ManuallyDrop::new(vec);
62 (
63 unsafe { NonNull::new_unchecked(vec.as_mut_ptr()) },
65 vec.capacity(),
66 vec.len(),
67 )
68}
69
70#[derive(Debug, Eq)]
79pub struct FixedBitSet {
80 pub(crate) data: NonNull<MaybeUninit<SimdBlock>>,
81 capacity: usize,
82 pub(crate) length: usize,
84}
85
86unsafe impl Send for FixedBitSet {}
88unsafe impl Sync for FixedBitSet {}
91
92impl FixedBitSet {
93 pub const fn new() -> Self {
95 FixedBitSet {
96 data: NonNull::dangling(),
97 capacity: 0,
98 length: 0,
99 }
100 }
101
102 pub fn with_capacity(bits: usize) -> Self {
105 let (mut blocks, rem) = div_rem(bits, SimdBlock::BITS);
106 blocks += (rem > 0) as usize;
107 Self::from_blocks_and_len(vec![SimdBlock::NONE; blocks], bits)
108 }
109
110 #[inline]
111 fn from_blocks_and_len(data: Vec<SimdBlock>, length: usize) -> Self {
112 let (data, capacity, _) = vec_into_parts(data);
113 FixedBitSet {
114 data: data.cast(),
115 capacity,
116 length,
117 }
118 }
119
120 pub fn with_capacity_and_blocks<I: IntoIterator<Item = Block>>(bits: usize, blocks: I) -> Self {
134 let mut bitset = Self::with_capacity(bits);
135 for (subblock, value) in bitset.as_mut_slice().iter_mut().zip(blocks) {
136 *subblock = value;
137 }
138 bitset
139 }
140
141 #[inline]
143 pub fn grow(&mut self, bits: usize) {
144 #[cold]
145 #[track_caller]
146 #[inline(never)]
147 fn do_grow(slf: &mut FixedBitSet, bits: usize) {
148 unsafe { slf.grow_inner(bits, MaybeUninit::new(SimdBlock::NONE)) };
150 }
151
152 if bits > self.length {
153 do_grow(self, bits);
154 }
155 }
156
157 #[inline(always)]
161 unsafe fn grow_inner(&mut self, bits: usize, fill: MaybeUninit<SimdBlock>) {
162 let mut data = unsafe {
165 Vec::from_raw_parts(self.data.as_ptr(), self.simd_block_len(), self.capacity)
166 };
167 let (mut blocks, rem) = div_rem(bits, SimdBlock::BITS);
168 blocks += (rem > 0) as usize;
169 data.resize(blocks, fill);
170 let (data, capacity, _) = vec_into_parts(data);
171 self.data = data;
172 self.capacity = capacity;
173 self.length = bits;
174 }
175
176 #[inline]
177 unsafe fn get_unchecked(&self, subblock: usize) -> &Block {
178 &*self.data.as_ptr().cast::<Block>().add(subblock)
179 }
180
181 #[inline]
182 unsafe fn get_unchecked_mut(&mut self, subblock: usize) -> &mut Block {
183 &mut *self.data.as_ptr().cast::<Block>().add(subblock)
184 }
185
186 #[inline]
187 fn usize_len(&self) -> usize {
188 let (mut blocks, rem) = div_rem(self.length, BITS);
189 blocks += (rem > 0) as usize;
190 blocks
191 }
192
193 #[inline]
194 fn simd_block_len(&self) -> usize {
195 let (mut blocks, rem) = div_rem(self.length, SimdBlock::BITS);
196 blocks += (rem > 0) as usize;
197 blocks
198 }
199
200 #[inline]
201 fn batch_count_ones(blocks: impl IntoIterator<Item = Block>) -> usize {
202 blocks.into_iter().map(|x| x.count_ones() as usize).sum()
203 }
204
205 #[inline]
206 fn as_simd_slice(&self) -> &[SimdBlock] {
207 unsafe { core::slice::from_raw_parts(self.data.as_ptr().cast(), self.simd_block_len()) }
210 }
211
212 #[inline]
213 fn as_mut_simd_slice(&mut self) -> &mut [SimdBlock] {
214 unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr().cast(), self.simd_block_len()) }
217 }
218
219 #[inline]
220 fn as_simd_slice_uninit(&self) -> &[MaybeUninit<SimdBlock>] {
221 unsafe { core::slice::from_raw_parts(self.data.as_ptr(), self.simd_block_len()) }
224 }
225
226 #[inline]
227 fn as_mut_simd_slice_uninit(&mut self) -> &mut [MaybeUninit<SimdBlock>] {
228 unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr(), self.simd_block_len()) }
231 }
232
233 #[inline]
243 pub fn grow_and_insert(&mut self, bits: usize) {
244 self.grow(bits.checked_add(1).expect("bitset capacity overflow"));
245
246 let (blocks, rem) = div_rem(bits, BITS);
247 unsafe {
249 *self.get_unchecked_mut(blocks) |= 1 << rem;
250 }
251 }
252
253 #[inline]
265 pub fn len(&self) -> usize {
266 self.length
267 }
268
269 #[inline]
284 pub fn is_empty(&self) -> bool {
285 self.len() == 0
286 }
287
288 #[inline]
304 pub fn is_clear(&self) -> bool {
305 self.as_simd_slice().iter().all(|block| block.is_empty())
306 }
307
308 #[inline]
323 pub fn minimum(&self) -> Option<usize> {
324 let (block_idx, block) = self
325 .as_simd_slice()
326 .iter()
327 .enumerate()
328 .find(|&(_, block)| !block.is_empty())?;
329 let mut inner = 0;
330 let mut trailing = 0;
331 for subblock in block.into_usize_array() {
332 if subblock != 0 {
333 trailing = subblock.trailing_zeros() as usize;
334 break;
335 } else {
336 inner += BITS;
337 }
338 }
339 Some(block_idx * SimdBlock::BITS + inner + trailing)
340 }
341
342 #[inline]
357 pub fn maximum(&self) -> Option<usize> {
358 let (block_idx, block) = self
359 .as_simd_slice()
360 .iter()
361 .rev()
362 .enumerate()
363 .find(|&(_, block)| !block.is_empty())?;
364 let mut inner = 0;
365 let mut leading = 0;
366 for subblock in block.into_usize_array().iter().rev() {
367 if *subblock != 0 {
368 leading = subblock.leading_zeros() as usize;
369 break;
370 } else {
371 inner += BITS;
372 }
373 }
374 let max = self.simd_block_len() * SimdBlock::BITS;
375 Some(max - block_idx * SimdBlock::BITS - inner - leading - 1)
376 }
377
378 #[inline]
391 pub fn is_full(&self) -> bool {
392 self.contains_all_in_range(..)
393 }
394
395 #[inline]
402 pub fn contains(&self, bit: usize) -> bool {
403 if bit < self.length {
404 unsafe { self.contains_unchecked(bit) }
406 } else {
407 false
408 }
409 }
410
411 #[inline]
420 pub unsafe fn contains_unchecked(&self, bit: usize) -> bool {
421 let (block, i) = div_rem(bit, BITS);
422 (self.get_unchecked(block) & (1 << i)) != 0
423 }
424
425 #[inline]
427 pub fn clear(&mut self) {
428 for elt in self.as_mut_simd_slice().iter_mut() {
429 *elt = SimdBlock::NONE
430 }
431 }
432
433 #[inline]
437 pub fn insert(&mut self, bit: usize) {
438 assert!(
439 bit < self.length,
440 "insert at index {} exceeds fixedbitset size {}",
441 bit,
442 self.length
443 );
444 unsafe {
446 self.insert_unchecked(bit);
447 }
448 }
449
450 #[inline]
455 pub unsafe fn insert_unchecked(&mut self, bit: usize) {
456 let (block, i) = div_rem(bit, BITS);
457 unsafe {
459 *self.get_unchecked_mut(block) |= 1 << i;
460 }
461 }
462
463 #[inline]
467 pub fn remove(&mut self, bit: usize) {
468 assert!(
469 bit < self.length,
470 "remove at index {} exceeds fixedbitset size {}",
471 bit,
472 self.length
473 );
474 unsafe {
476 self.remove_unchecked(bit);
477 }
478 }
479
480 #[inline]
485 pub unsafe fn remove_unchecked(&mut self, bit: usize) {
486 let (block, i) = div_rem(bit, BITS);
487 unsafe {
489 *self.get_unchecked_mut(block) &= !(1 << i);
490 }
491 }
492
493 #[inline]
497 pub fn put(&mut self, bit: usize) -> bool {
498 assert!(
499 bit < self.length,
500 "put at index {} exceeds fixedbitset size {}",
501 bit,
502 self.length
503 );
504 unsafe { self.put_unchecked(bit) }
506 }
507
508 #[inline]
513 pub unsafe fn put_unchecked(&mut self, bit: usize) -> bool {
514 let (block, i) = div_rem(bit, BITS);
515 unsafe {
517 let word = self.get_unchecked_mut(block);
518 let prev = *word & (1 << i) != 0;
519 *word |= 1 << i;
520 prev
521 }
522 }
523
524 #[inline]
528 pub fn toggle(&mut self, bit: usize) {
529 assert!(
530 bit < self.length,
531 "toggle at index {} exceeds fixedbitset size {}",
532 bit,
533 self.length
534 );
535 unsafe {
537 self.toggle_unchecked(bit);
538 }
539 }
540
541 #[inline]
546 pub unsafe fn toggle_unchecked(&mut self, bit: usize) {
547 let (block, i) = div_rem(bit, BITS);
548 unsafe {
550 *self.get_unchecked_mut(block) ^= 1 << i;
551 }
552 }
553
554 #[inline]
558 pub fn set(&mut self, bit: usize, enabled: bool) {
559 assert!(
560 bit < self.length,
561 "set at index {} exceeds fixedbitset size {}",
562 bit,
563 self.length
564 );
565 unsafe {
567 self.set_unchecked(bit, enabled);
568 }
569 }
570
571 #[inline]
576 pub unsafe fn set_unchecked(&mut self, bit: usize, enabled: bool) {
577 let (block, i) = div_rem(bit, BITS);
578 let elt = unsafe { self.get_unchecked_mut(block) };
580 if enabled {
581 *elt |= 1 << i;
582 } else {
583 *elt &= !(1 << i);
584 }
585 }
586
587 #[inline]
593 pub fn copy_bit(&mut self, from: usize, to: usize) {
594 assert!(
595 to < self.length,
596 "copy to index {} exceeds fixedbitset size {}",
597 to,
598 self.length
599 );
600 let enabled = self.contains(from);
601 unsafe { self.set_unchecked(to, enabled) };
603 }
604
605 #[inline]
613 pub unsafe fn copy_bit_unchecked(&mut self, from: usize, to: usize) {
614 let enabled = self.contains_unchecked(from);
616 self.set_unchecked(to, enabled);
618 }
619
620 #[inline]
627 pub fn count_ones<T: IndexRange>(&self, range: T) -> usize {
628 Self::batch_count_ones(Masks::new(range, self.length).map(|(block, mask)| {
629 unsafe { *self.get_unchecked(block) & mask }
631 }))
632 }
633
634 #[inline]
641 pub fn count_zeroes<T: IndexRange>(&self, range: T) -> usize {
642 Self::batch_count_ones(Masks::new(range, self.length).map(|(block, mask)| {
643 unsafe { !*self.get_unchecked(block) & mask }
645 }))
646 }
647
648 #[inline]
654 pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool) {
655 if enabled {
656 self.insert_range(range);
657 } else {
658 self.remove_range(range);
659 }
660 }
661
662 #[inline]
668 pub fn insert_range<T: IndexRange>(&mut self, range: T) {
669 for (block, mask) in Masks::new(range, self.length) {
670 let block = unsafe { self.get_unchecked_mut(block) };
672 *block |= mask;
673 }
674 }
675
676 #[inline]
682 pub fn remove_range<T: IndexRange>(&mut self, range: T) {
683 for (block, mask) in Masks::new(range, self.length) {
684 let block = unsafe { self.get_unchecked_mut(block) };
686 *block &= !mask;
687 }
688 }
689
690 #[inline]
696 pub fn toggle_range<T: IndexRange>(&mut self, range: T) {
697 for (block, mask) in Masks::new(range, self.length) {
698 let block = unsafe { self.get_unchecked_mut(block) };
700 *block ^= mask;
701 }
702 }
703
704 #[inline]
708 pub fn contains_all_in_range<T: IndexRange>(&self, range: T) -> bool {
709 for (block, mask) in Masks::new(range, self.length) {
710 let block = unsafe { self.get_unchecked(block) };
712 if block & mask != mask {
713 return false;
714 }
715 }
716 true
717 }
718
719 #[inline]
723 pub fn contains_any_in_range<T: IndexRange>(&self, range: T) -> bool {
724 for (block, mask) in Masks::new(range, self.length) {
725 let block = unsafe { self.get_unchecked(block) };
727 if block & mask != 0 {
728 return true;
729 }
730 }
731 false
732 }
733
734 #[inline]
736 pub fn as_slice(&self) -> &[Block] {
737 unsafe {
742 let ptr = self.data.as_ptr().cast::<Block>();
743 core::slice::from_raw_parts(ptr, self.usize_len())
744 }
745 }
746
747 #[inline]
750 pub fn as_mut_slice(&mut self) -> &mut [Block] {
751 unsafe {
756 let ptr = self.data.as_ptr().cast::<Block>();
757 core::slice::from_raw_parts_mut(ptr, self.usize_len())
758 }
759 }
760
761 #[inline]
765 pub fn ones(&self) -> Ones<'_> {
766 match self.as_slice().split_first() {
767 Some((&first_block, rem)) => {
768 let (&last_block, rem) = rem.split_last().unwrap_or((&0, rem));
769 Ones {
770 bitset_front: first_block,
771 bitset_back: last_block,
772 block_idx_front: 0,
773 block_idx_back: (1 + rem.len()) * BITS,
774 remaining_blocks: rem.iter(),
775 }
776 }
777 None => Ones {
778 bitset_front: 0,
779 bitset_back: 0,
780 block_idx_front: 0,
781 block_idx_back: 0,
782 remaining_blocks: [].iter(),
783 },
784 }
785 }
786
787 pub fn into_ones(self) -> IntoOnes {
792 let ptr = self.data.as_ptr().cast();
793 let len = self.simd_block_len() * SimdBlock::USIZE_COUNT;
794 let slice = unsafe { core::slice::from_raw_parts(ptr, len) };
801 let data: Vec<SimdBlock> = unsafe {
804 Vec::from_raw_parts(
805 self.data.as_ptr().cast(),
806 self.simd_block_len(),
807 self.capacity,
808 )
809 };
810 let mut iter = slice.iter().copied();
811
812 core::mem::forget(self);
813
814 IntoOnes {
815 bitset_front: iter.next().unwrap_or(0),
816 bitset_back: iter.next_back().unwrap_or(0),
817 block_idx_front: 0,
818 block_idx_back: len.saturating_sub(1) * BITS,
819 remaining_blocks: iter,
820 _buf: data,
821 }
822 }
823
824 #[inline]
828 pub fn zeroes(&self) -> Zeroes<'_> {
829 match self.as_slice().split_first() {
830 Some((&block, rem)) => Zeroes {
831 bitset: !block,
832 block_idx: 0,
833 len: self.len(),
834 remaining_blocks: rem.iter(),
835 },
836 None => Zeroes {
837 bitset: !0,
838 block_idx: 0,
839 len: self.len(),
840 remaining_blocks: [].iter(),
841 },
842 }
843 }
844
845 pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a> {
847 Intersection {
848 iter: self.ones(),
849 other,
850 }
851 }
852
853 pub fn union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a> {
855 Union {
856 iter: self.ones().chain(other.difference(self)),
857 }
858 }
859
860 pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a> {
863 Difference {
864 iter: self.ones(),
865 other,
866 }
867 }
868
869 pub fn symmetric_difference<'a>(&'a self, other: &'a FixedBitSet) -> SymmetricDifference<'a> {
872 SymmetricDifference {
873 iter: self.difference(other).chain(other.difference(self)),
874 }
875 }
876
877 pub fn union_with(&mut self, other: &FixedBitSet) {
881 if other.len() >= self.len() {
882 self.grow(other.len());
883 }
884 self.as_mut_simd_slice()
885 .iter_mut()
886 .zip(other.as_simd_slice().iter())
887 .for_each(|(x, y)| *x |= *y);
888 }
889
890 pub fn intersect_with(&mut self, other: &FixedBitSet) {
894 let me = self.as_mut_simd_slice();
895 let other = other.as_simd_slice();
896 me.iter_mut().zip(other.iter()).for_each(|(x, y)| {
897 *x &= *y;
898 });
899 let mn = core::cmp::min(me.len(), other.len());
900 for wd in &mut me[mn..] {
901 *wd = SimdBlock::NONE;
902 }
903 }
904
905 pub fn difference_with(&mut self, other: &FixedBitSet) {
909 self.as_mut_simd_slice()
910 .iter_mut()
911 .zip(other.as_simd_slice().iter())
912 .for_each(|(x, y)| {
913 *x &= !*y;
914 });
915
916 }
923
924 pub fn symmetric_difference_with(&mut self, other: &FixedBitSet) {
928 if other.len() >= self.len() {
929 self.grow(other.len());
930 }
931 self.as_mut_simd_slice()
932 .iter_mut()
933 .zip(other.as_simd_slice().iter())
934 .for_each(|(x, y)| {
935 *x ^= *y;
936 });
937 }
938
939 #[inline]
945 pub fn union_count(&self, other: &FixedBitSet) -> usize {
946 let me = self.as_slice();
947 let other = other.as_slice();
948 let count = Self::batch_count_ones(me.iter().zip(other.iter()).map(|(x, y)| *x | *y));
949 match other.len().cmp(&me.len()) {
950 Ordering::Greater => count + Self::batch_count_ones(other[me.len()..].iter().copied()),
951 Ordering::Less => count + Self::batch_count_ones(me[other.len()..].iter().copied()),
952 Ordering::Equal => count,
953 }
954 }
955
956 #[inline]
962 pub fn intersection_count(&self, other: &FixedBitSet) -> usize {
963 Self::batch_count_ones(
964 self.as_slice()
965 .iter()
966 .zip(other.as_slice())
967 .map(|(x, y)| *x & *y),
968 )
969 }
970
971 #[inline]
977 pub fn difference_count(&self, other: &FixedBitSet) -> usize {
978 Self::batch_count_ones(
979 self.as_slice()
980 .iter()
981 .zip(other.as_slice().iter())
982 .map(|(x, y)| *x & !*y),
983 ) + Self::batch_count_ones(self.as_slice().iter().skip(other.as_slice().len()).copied())
984 }
985
986 #[inline]
992 pub fn symmetric_difference_count(&self, other: &FixedBitSet) -> usize {
993 let me = self.as_slice();
994 let other = other.as_slice();
995 let count = Self::batch_count_ones(me.iter().zip(other.iter()).map(|(x, y)| *x ^ *y));
996 match other.len().cmp(&me.len()) {
997 Ordering::Greater => count + Self::batch_count_ones(other[me.len()..].iter().copied()),
998 Ordering::Less => count + Self::batch_count_ones(me[other.len()..].iter().copied()),
999 Ordering::Equal => count,
1000 }
1001 }
1002
1003 pub fn is_disjoint(&self, other: &FixedBitSet) -> bool {
1006 self.as_simd_slice()
1007 .iter()
1008 .zip(other.as_simd_slice())
1009 .all(|(x, y)| (*x & *y).is_empty())
1010 }
1011
1012 pub fn is_subset(&self, other: &FixedBitSet) -> bool {
1015 let me = self.as_simd_slice();
1016 let other = other.as_simd_slice();
1017 me.iter()
1018 .zip(other.iter())
1019 .all(|(x, y)| x.andnot(*y).is_empty())
1020 && me.iter().skip(other.len()).all(|x| x.is_empty())
1021 }
1022
1023 pub fn is_superset(&self, other: &FixedBitSet) -> bool {
1026 other.is_subset(self)
1027 }
1028}
1029
1030impl Hash for FixedBitSet {
1031 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
1032 self.length.hash(state);
1033 self.as_simd_slice().hash(state);
1034 }
1035}
1036
1037impl PartialEq for FixedBitSet {
1038 fn eq(&self, other: &Self) -> bool {
1039 self.length == other.length && self.as_simd_slice().eq(other.as_simd_slice())
1040 }
1041}
1042
1043impl PartialOrd for FixedBitSet {
1044 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1045 Some(self.cmp(other))
1046 }
1047}
1048
1049impl Ord for FixedBitSet {
1050 fn cmp(&self, other: &Self) -> Ordering {
1051 self.length
1052 .cmp(&other.length)
1053 .then_with(|| self.as_simd_slice().cmp(other.as_simd_slice()))
1054 }
1055}
1056
1057impl Default for FixedBitSet {
1058 fn default() -> Self {
1059 Self::new()
1060 }
1061}
1062
1063impl Drop for FixedBitSet {
1064 fn drop(&mut self) {
1065 drop(unsafe {
1068 Vec::from_raw_parts(self.data.as_ptr(), self.simd_block_len(), self.capacity)
1069 });
1070 }
1071}
1072
1073impl Binary for FixedBitSet {
1074 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
1075 if f.alternate() {
1076 f.write_str("0b")?;
1077 }
1078
1079 for i in 0..self.length {
1080 if self[i] {
1081 f.write_char('1')?;
1082 } else {
1083 f.write_char('0')?;
1084 }
1085 }
1086
1087 Ok(())
1088 }
1089}
1090
1091impl Display for FixedBitSet {
1092 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
1093 Binary::fmt(&self, f)
1094 }
1095}
1096
1097pub struct Difference<'a> {
1101 iter: Ones<'a>,
1102 other: &'a FixedBitSet,
1103}
1104
1105impl<'a> Iterator for Difference<'a> {
1106 type Item = usize;
1107
1108 #[inline]
1109 fn next(&mut self) -> Option<Self::Item> {
1110 self.iter.by_ref().find(|&nxt| !self.other.contains(nxt))
1111 }
1112
1113 #[inline]
1114 fn size_hint(&self) -> (usize, Option<usize>) {
1115 self.iter.size_hint()
1116 }
1117}
1118
1119impl<'a> DoubleEndedIterator for Difference<'a> {
1120 fn next_back(&mut self) -> Option<Self::Item> {
1121 self.iter
1122 .by_ref()
1123 .rev()
1124 .find(|&nxt| !self.other.contains(nxt))
1125 }
1126}
1127
1128impl<'a> FusedIterator for Difference<'a> {}
1130
1131pub struct SymmetricDifference<'a> {
1135 iter: Chain<Difference<'a>, Difference<'a>>,
1136}
1137
1138impl<'a> Iterator for SymmetricDifference<'a> {
1139 type Item = usize;
1140
1141 #[inline]
1142 fn next(&mut self) -> Option<Self::Item> {
1143 self.iter.next()
1144 }
1145
1146 #[inline]
1147 fn size_hint(&self) -> (usize, Option<usize>) {
1148 self.iter.size_hint()
1149 }
1150}
1151
1152impl<'a> DoubleEndedIterator for SymmetricDifference<'a> {
1153 fn next_back(&mut self) -> Option<Self::Item> {
1154 self.iter.next_back()
1155 }
1156}
1157
1158impl<'a> FusedIterator for SymmetricDifference<'a> {}
1160
1161pub struct Intersection<'a> {
1165 iter: Ones<'a>,
1166 other: &'a FixedBitSet,
1167}
1168
1169impl<'a> Iterator for Intersection<'a> {
1170 type Item = usize; #[inline]
1173 fn next(&mut self) -> Option<Self::Item> {
1174 self.iter.by_ref().find(|&nxt| self.other.contains(nxt))
1175 }
1176
1177 #[inline]
1178 fn size_hint(&self) -> (usize, Option<usize>) {
1179 self.iter.size_hint()
1180 }
1181}
1182
1183impl<'a> DoubleEndedIterator for Intersection<'a> {
1184 fn next_back(&mut self) -> Option<Self::Item> {
1185 self.iter
1186 .by_ref()
1187 .rev()
1188 .find(|&nxt| self.other.contains(nxt))
1189 }
1190}
1191
1192impl<'a> FusedIterator for Intersection<'a> {}
1194
1195pub struct Union<'a> {
1199 iter: Chain<Ones<'a>, Difference<'a>>,
1200}
1201
1202impl<'a> Iterator for Union<'a> {
1203 type Item = usize;
1204
1205 #[inline]
1206 fn next(&mut self) -> Option<Self::Item> {
1207 self.iter.next()
1208 }
1209
1210 #[inline]
1211 fn size_hint(&self) -> (usize, Option<usize>) {
1212 self.iter.size_hint()
1213 }
1214}
1215
1216impl<'a> DoubleEndedIterator for Union<'a> {
1217 fn next_back(&mut self) -> Option<Self::Item> {
1218 self.iter.next_back()
1219 }
1220}
1221
1222impl<'a> FusedIterator for Union<'a> {}
1224
1225struct Masks {
1226 first_block: usize,
1227 first_mask: usize,
1228 last_block: usize,
1229 last_mask: usize,
1230}
1231
1232impl Masks {
1233 #[inline]
1234 fn new<T: IndexRange>(range: T, length: usize) -> Masks {
1235 let start = range.start().unwrap_or(0);
1236 let end = range.end().unwrap_or(length);
1237 assert!(
1238 start <= end && end <= length,
1239 "invalid range {}..{} for a fixedbitset of size {}",
1240 start,
1241 end,
1242 length
1243 );
1244
1245 let (first_block, first_rem) = div_rem(start, BITS);
1246 let (last_block, last_rem) = div_rem(end, BITS);
1247
1248 Masks {
1249 first_block,
1250 first_mask: usize::MAX << first_rem,
1251 last_block,
1252 last_mask: (usize::MAX >> 1) >> (BITS - last_rem - 1),
1253 }
1255 }
1256}
1257
1258impl Iterator for Masks {
1259 type Item = (usize, usize);
1260
1261 #[inline]
1262 fn next(&mut self) -> Option<Self::Item> {
1263 match self.first_block.cmp(&self.last_block) {
1264 Ordering::Less => {
1265 let res = (self.first_block, self.first_mask);
1266 self.first_block += 1;
1267 self.first_mask = !0;
1268 Some(res)
1269 }
1270 Ordering::Equal => {
1271 let mask = self.first_mask & self.last_mask;
1272 let res = if mask == 0 {
1273 None
1274 } else {
1275 Some((self.first_block, mask))
1276 };
1277 self.first_block += 1;
1278 res
1279 }
1280 Ordering::Greater => None,
1281 }
1282 }
1283
1284 #[inline]
1285 fn size_hint(&self) -> (usize, Option<usize>) {
1286 (self.first_block..=self.last_block).size_hint()
1287 }
1288}
1289
1290impl FusedIterator for Masks {}
1292
1293impl ExactSizeIterator for Masks {}
1296
1297#[derive(Clone)]
1301pub struct Ones<'a> {
1302 bitset_front: usize,
1303 bitset_back: usize,
1304 block_idx_front: usize,
1305 block_idx_back: usize,
1306 remaining_blocks: core::slice::Iter<'a, usize>,
1307}
1308
1309impl<'a> Ones<'a> {
1310 #[inline]
1314 pub fn last_positive_bit_and_unset(n: &mut usize) -> usize {
1315 let last_bit = *n & n.wrapping_neg();
1317
1318 let position = last_bit.trailing_zeros();
1320
1321 *n &= n.wrapping_sub(1);
1323
1324 position as usize
1325 }
1326
1327 #[inline]
1328 fn first_positive_bit_and_unset(n: &mut usize) -> usize {
1329 let bit_idx = n.leading_zeros();
1331
1332 let mask = !((1_usize) << (BITS as u32 - bit_idx - 1));
1334 n.bitand_assign(mask);
1335
1336 bit_idx as usize
1337 }
1338}
1339
1340impl<'a> DoubleEndedIterator for Ones<'a> {
1341 fn next_back(&mut self) -> Option<Self::Item> {
1342 while self.bitset_back == 0 {
1343 match self.remaining_blocks.next_back() {
1344 None => {
1345 if self.bitset_front != 0 {
1346 self.bitset_back = 0;
1347 self.block_idx_back = self.block_idx_front;
1348 return Some(
1349 self.block_idx_front + BITS
1350 - Self::first_positive_bit_and_unset(&mut self.bitset_front)
1351 - 1,
1352 );
1353 } else {
1354 return None;
1355 }
1356 }
1357 Some(next_block) => {
1358 self.bitset_back = *next_block;
1359 self.block_idx_back -= BITS;
1360 }
1361 };
1362 }
1363
1364 Some(
1365 self.block_idx_back - Self::first_positive_bit_and_unset(&mut self.bitset_back) + BITS
1366 - 1,
1367 )
1368 }
1369}
1370
1371impl<'a> Iterator for Ones<'a> {
1372 type Item = usize; #[inline]
1375 fn next(&mut self) -> Option<Self::Item> {
1376 while self.bitset_front == 0 {
1377 match self.remaining_blocks.next() {
1378 Some(next_block) => {
1379 self.bitset_front = *next_block;
1380 self.block_idx_front += BITS;
1381 }
1382 None => {
1383 if self.bitset_back != 0 {
1384 self.block_idx_front = self.block_idx_back;
1386 self.bitset_front = 0;
1387
1388 return Some(
1389 self.block_idx_back
1390 + Self::last_positive_bit_and_unset(&mut self.bitset_back),
1391 );
1392 } else {
1393 return None;
1394 }
1395 }
1396 };
1397 }
1398
1399 Some(self.block_idx_front + Self::last_positive_bit_and_unset(&mut self.bitset_front))
1400 }
1401
1402 #[inline]
1403 fn size_hint(&self) -> (usize, Option<usize>) {
1404 (
1405 0,
1406 (Some(self.block_idx_back - self.block_idx_front + 2 * BITS)),
1407 )
1408 }
1409}
1410
1411impl<'a> FusedIterator for Ones<'a> {}
1413
1414pub struct Zeroes<'a> {
1418 bitset: usize,
1419 block_idx: usize,
1420 len: usize,
1421 remaining_blocks: core::slice::Iter<'a, usize>,
1422}
1423
1424impl<'a> Iterator for Zeroes<'a> {
1425 type Item = usize; #[inline]
1428 fn next(&mut self) -> Option<Self::Item> {
1429 while self.bitset == 0 {
1430 self.bitset = !*self.remaining_blocks.next()?;
1431 self.block_idx += BITS;
1432 }
1433 let t = self.bitset & (0_usize).wrapping_sub(self.bitset);
1434 let r = self.bitset.trailing_zeros() as usize;
1435 self.bitset ^= t;
1436 let bit = self.block_idx + r;
1437 if bit < self.len {
1439 Some(bit)
1440 } else {
1441 None
1442 }
1443 }
1444
1445 #[inline]
1446 fn size_hint(&self) -> (usize, Option<usize>) {
1447 (0, Some(self.len))
1448 }
1449}
1450
1451impl<'a> FusedIterator for Zeroes<'a> {}
1453
1454impl Clone for FixedBitSet {
1455 #[inline]
1456 fn clone(&self) -> Self {
1457 Self::from_blocks_and_len(Vec::from(self.as_simd_slice()), self.length)
1458 }
1459
1460 #[inline]
1461 fn clone_from(&mut self, source: &Self) {
1462 if self.length < source.length {
1463 unsafe { self.grow_inner(source.length, MaybeUninit::uninit()) };
1465 }
1466 let me = self.as_mut_simd_slice_uninit();
1467 let them = source.as_simd_slice_uninit();
1468 match me.len().cmp(&them.len()) {
1469 Ordering::Greater => {
1470 let (head, tail) = me.split_at_mut(them.len());
1471 head.copy_from_slice(them);
1472 tail.fill(MaybeUninit::new(SimdBlock::NONE));
1473 }
1474 Ordering::Equal => me.copy_from_slice(them),
1475 Ordering::Less => {}
1478 }
1479 self.length = source.length;
1480 }
1481}
1482
1483impl Index<usize> for FixedBitSet {
1489 type Output = bool;
1490
1491 #[inline]
1492 fn index(&self, bit: usize) -> &bool {
1493 if self.contains(bit) {
1494 &true
1495 } else {
1496 &false
1497 }
1498 }
1499}
1500
1501impl Extend<usize> for FixedBitSet {
1503 fn extend<I: IntoIterator<Item = usize>>(&mut self, src: I) {
1504 let iter = src.into_iter();
1505 for i in iter {
1506 if i >= self.len() {
1507 self.grow(i + 1);
1508 }
1509 self.put(i);
1510 }
1511 }
1512}
1513
1514impl FromIterator<usize> for FixedBitSet {
1517 fn from_iter<I: IntoIterator<Item = usize>>(src: I) -> Self {
1518 let mut fbs = FixedBitSet::with_capacity(0);
1519 fbs.extend(src);
1520 fbs
1521 }
1522}
1523
1524pub struct IntoOnes {
1525 bitset_front: Block,
1526 bitset_back: Block,
1527 block_idx_front: usize,
1528 block_idx_back: usize,
1529 remaining_blocks: core::iter::Copied<core::slice::Iter<'static, usize>>,
1530 _buf: Vec<SimdBlock>,
1532}
1533
1534impl IntoOnes {
1535 #[inline]
1539 pub fn last_positive_bit_and_unset(n: &mut Block) -> usize {
1540 let last_bit = *n & n.wrapping_neg();
1542
1543 let position = last_bit.trailing_zeros();
1545
1546 *n &= n.wrapping_sub(1);
1548
1549 position as usize
1550 }
1551
1552 #[inline]
1553 fn first_positive_bit_and_unset(n: &mut Block) -> usize {
1554 let bit_idx = n.leading_zeros();
1556
1557 let mask = !((1_usize) << (BITS as u32 - bit_idx - 1));
1559 n.bitand_assign(mask);
1560
1561 bit_idx as usize
1562 }
1563}
1564
1565impl DoubleEndedIterator for IntoOnes {
1566 fn next_back(&mut self) -> Option<Self::Item> {
1567 while self.bitset_back == 0 {
1568 match self.remaining_blocks.next_back() {
1569 None => {
1570 if self.bitset_front != 0 {
1571 self.bitset_back = 0;
1572 self.block_idx_back = self.block_idx_front;
1573 return Some(
1574 self.block_idx_front + BITS
1575 - Self::first_positive_bit_and_unset(&mut self.bitset_front)
1576 - 1,
1577 );
1578 } else {
1579 return None;
1580 }
1581 }
1582 Some(next_block) => {
1583 self.bitset_back = next_block;
1584 self.block_idx_back -= BITS;
1585 }
1586 };
1587 }
1588
1589 Some(
1590 self.block_idx_back - Self::first_positive_bit_and_unset(&mut self.bitset_back) + BITS
1591 - 1,
1592 )
1593 }
1594}
1595
1596impl Iterator for IntoOnes {
1597 type Item = usize; #[inline]
1600 fn next(&mut self) -> Option<Self::Item> {
1601 while self.bitset_front == 0 {
1602 match self.remaining_blocks.next() {
1603 Some(next_block) => {
1604 self.bitset_front = next_block;
1605 self.block_idx_front += BITS;
1606 }
1607 None => {
1608 if self.bitset_back != 0 {
1609 self.block_idx_front = self.block_idx_back;
1611 self.bitset_front = 0;
1612
1613 return Some(
1614 self.block_idx_back
1615 + Self::last_positive_bit_and_unset(&mut self.bitset_back),
1616 );
1617 } else {
1618 return None;
1619 }
1620 }
1621 };
1622 }
1623
1624 Some(self.block_idx_front + Self::last_positive_bit_and_unset(&mut self.bitset_front))
1625 }
1626
1627 #[inline]
1628 fn size_hint(&self) -> (usize, Option<usize>) {
1629 (
1630 0,
1631 (Some(self.block_idx_back - self.block_idx_front + 2 * BITS)),
1632 )
1633 }
1634}
1635
1636impl FusedIterator for IntoOnes {}
1638
1639impl BitAnd for &FixedBitSet {
1640 type Output = FixedBitSet;
1641 fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
1642 let (short, long) = {
1643 if self.len() <= other.len() {
1644 (self.as_simd_slice(), other.as_simd_slice())
1645 } else {
1646 (other.as_simd_slice(), self.as_simd_slice())
1647 }
1648 };
1649 let mut data = Vec::from(short);
1650 for (data, block) in data.iter_mut().zip(long.iter()) {
1651 *data &= *block;
1652 }
1653 let len = core::cmp::min(self.len(), other.len());
1654 FixedBitSet::from_blocks_and_len(data, len)
1655 }
1656}
1657
1658impl BitAndAssign for FixedBitSet {
1659 fn bitand_assign(&mut self, other: Self) {
1660 self.intersect_with(&other);
1661 }
1662}
1663
1664impl BitAndAssign<&Self> for FixedBitSet {
1665 fn bitand_assign(&mut self, other: &Self) {
1666 self.intersect_with(other);
1667 }
1668}
1669
1670impl BitOr for &FixedBitSet {
1671 type Output = FixedBitSet;
1672 fn bitor(self, other: &FixedBitSet) -> FixedBitSet {
1673 let (short, long) = {
1674 if self.len() <= other.len() {
1675 (self.as_simd_slice(), other.as_simd_slice())
1676 } else {
1677 (other.as_simd_slice(), self.as_simd_slice())
1678 }
1679 };
1680 let mut data = Vec::from(long);
1681 for (data, block) in data.iter_mut().zip(short.iter()) {
1682 *data |= *block;
1683 }
1684 let len = core::cmp::max(self.len(), other.len());
1685 FixedBitSet::from_blocks_and_len(data, len)
1686 }
1687}
1688
1689impl BitOrAssign for FixedBitSet {
1690 fn bitor_assign(&mut self, other: Self) {
1691 self.union_with(&other);
1692 }
1693}
1694
1695impl BitOrAssign<&Self> for FixedBitSet {
1696 fn bitor_assign(&mut self, other: &Self) {
1697 self.union_with(other);
1698 }
1699}
1700
1701impl BitXor for &FixedBitSet {
1702 type Output = FixedBitSet;
1703 fn bitxor(self, other: &FixedBitSet) -> FixedBitSet {
1704 let (short, long) = {
1705 if self.len() <= other.len() {
1706 (self.as_simd_slice(), other.as_simd_slice())
1707 } else {
1708 (other.as_simd_slice(), self.as_simd_slice())
1709 }
1710 };
1711 let mut data = Vec::from(long);
1712 for (data, block) in data.iter_mut().zip(short.iter()) {
1713 *data ^= *block;
1714 }
1715 let len = core::cmp::max(self.len(), other.len());
1716 FixedBitSet::from_blocks_and_len(data, len)
1717 }
1718}
1719
1720impl BitXorAssign for FixedBitSet {
1721 fn bitxor_assign(&mut self, other: Self) {
1722 self.symmetric_difference_with(&other);
1723 }
1724}
1725
1726impl BitXorAssign<&Self> for FixedBitSet {
1727 fn bitxor_assign(&mut self, other: &Self) {
1728 self.symmetric_difference_with(other);
1729 }
1730}