Skip to main content

fixedbitset/
lib.rs

1//! `FixedBitSet` is a simple fixed size set of bits.
2//!
3//! ### Crate features
4//!
5//! - `std` (default feature)
6//!   Disabling this feature disables using std and instead uses crate alloc.
7//!
8//! ### SIMD Acceleration
9//! `fixedbitset` is written with SIMD in mind. The backing store and set operations will use aligned SIMD data types and instructions when compiling
10//! for compatible target platforms. The use of SIMD generally enables better performance in many set and batch operations (i.e. intersection/union/inserting a range).
11//!
12//!  When SIMD is not available on the target, the crate will gracefully fallback to a default implementation.  It is intended to add support for other SIMD architectures
13//! once they appear in stable Rust.
14//!
15//! Currently only SSE2/AVX/AVX2 on x86/x86_64 and wasm32 SIMD are supported as this is what stable Rust supports.
16#![no_std]
17// TODO: Remove once MSRV supports undocumented_unsafe_blocks
18#![allow(unknown_lints)]
19#![deny(clippy::undocumented_unsafe_blocks)]
20// TODO our MSRV supports older versions of Cargo that do not know the following are unsafe:
21// - Vec::from_raw_parts
22// - get_unchecked_mut
23#![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        // SAFETY: A Vec's internal pointer is always non-null.
64        unsafe { NonNull::new_unchecked(vec.as_mut_ptr()) },
65        vec.capacity(),
66        vec.len(),
67    )
68}
69
70/// `FixedBitSet` is a simple fixed size set of bits that each can
71/// be enabled (1 / **true**) or disabled (0 / **false**).
72///
73/// The bit set has a fixed capacity in terms of enabling bits (and the
74/// capacity can grow using the `grow` method).
75///
76/// Derived traits depend on both the zeros and ones, so [0,1] is not equal to
77/// [0,1,0].
78#[derive(Debug, Eq)]
79pub struct FixedBitSet {
80    pub(crate) data: NonNull<MaybeUninit<SimdBlock>>,
81    capacity: usize,
82    /// length in bits
83    pub(crate) length: usize,
84}
85
86// SAFETY: FixedBitset contains no thread-local state and can be safely sent between threads
87unsafe impl Send for FixedBitSet {}
88// SAFETY: FixedBitset does not provide simultaneous unsynchronized mutable access to the
89// underlying buffer.
90unsafe impl Sync for FixedBitSet {}
91
92impl FixedBitSet {
93    /// Create a new empty **FixedBitSet**.
94    pub const fn new() -> Self {
95        FixedBitSet {
96            data: NonNull::dangling(),
97            capacity: 0,
98            length: 0,
99        }
100    }
101
102    /// Create a new **FixedBitSet** with a specific number of bits,
103    /// all initially clear.
104    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    /// Create a new **FixedBitSet** with a specific number of bits,
121    /// initialized from provided blocks.
122    ///
123    /// If the blocks are not the exact size needed for the capacity
124    /// they will be padded with zeros (if shorter) or truncated to
125    /// the capacity (if longer).
126    ///
127    /// For example:
128    /// ```
129    /// let data = vec![4];
130    /// let bs = fixedbitset::FixedBitSet::with_capacity_and_blocks(4, data);
131    /// assert_eq!(format!("{:b}", bs), "0010");
132    /// ```
133    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    /// Grow capacity to **bits**, all new bits initialized to zero
142    #[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            // SAFETY: The provided fill is initialized to NONE.
149            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    /// # Safety
158    /// If `fill` is uninitialized, the memory must not be accessed and must be immediately
159    /// written over
160    #[inline(always)]
161    unsafe fn grow_inner(&mut self, bits: usize, fill: MaybeUninit<SimdBlock>) {
162        // SAFETY: The data pointer and capacity were created from a Vec initially. The block
163        // len is identical to that of the original.
164        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        // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
208        // is called with a read-only borrow so no other write can happen as long as the returned borrow lives.
209        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        // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
215        // is called with a mutable borrow so no other read or write can happen as long as the returned borrow lives.
216        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        // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
222        // is called with a read-only borrow so no other write can happen as long as the returned borrow lives.
223        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        // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
229        // is called with a mutable borrow so no other read or write can happen as long as the returned borrow lives.
230        unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr(), self.simd_block_len()) }
231    }
232
233    /// Grows the internal size of the bitset before inserting a bit
234    ///
235    /// Unlike `insert`, this grows the bitset if the bit is outside of the existing buffer's range.
236    ///
237    /// This is faster than calling `grow` then `insert` in succession.
238    ///
239    /// # Panics
240    ///
241    /// Panics if `bits` is `usize::MAX`, because the required length cannot be represented.
242    #[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        // SAFETY: The above grow ensures that the block is inside the Vec's allocation.
248        unsafe {
249            *self.get_unchecked_mut(blocks) |= 1 << rem;
250        }
251    }
252
253    /// The length of the [`FixedBitSet`] in bits.
254    ///
255    /// Note: `len` includes both set and unset bits.
256    /// ```
257    /// # use fixedbitset::FixedBitSet;
258    /// let bitset = FixedBitSet::with_capacity(10);
259    /// // there are 0 set bits, but 10 unset bits
260    /// assert_eq!(bitset.len(), 10);
261    /// ```
262    /// `len` does not return the count of set bits. For that, use
263    /// [`bitset.count_ones(..)`](FixedBitSet::count_ones) instead.
264    #[inline]
265    pub fn len(&self) -> usize {
266        self.length
267    }
268
269    /// `true` if the [`FixedBitSet`] is empty.
270    ///
271    /// Note that an "empty" `FixedBitSet` is a `FixedBitSet` with
272    /// no bits (meaning: it's length is zero). If you want to check
273    /// if all bits are unset, use [`FixedBitSet::is_clear`].
274    ///
275    /// ```
276    /// # use fixedbitset::FixedBitSet;
277    /// let bitset = FixedBitSet::with_capacity(10);
278    /// assert!(!bitset.is_empty());
279    ///
280    /// let bitset = FixedBitSet::with_capacity(0);
281    /// assert!(bitset.is_empty());
282    /// ```
283    #[inline]
284    pub fn is_empty(&self) -> bool {
285        self.len() == 0
286    }
287
288    /// `true` if all bits in the [`FixedBitSet`] are unset.
289    ///
290    /// As opposed to [`FixedBitSet::is_empty`], which is `true` only for
291    /// sets without any bits, set or unset.
292    ///
293    /// ```
294    /// # use fixedbitset::FixedBitSet;
295    /// let mut bitset = FixedBitSet::with_capacity(10);
296    /// assert!(bitset.is_clear());
297    ///
298    /// bitset.insert(2);
299    /// assert!(!bitset.is_clear());
300    /// ```
301    ///
302    /// This is equivalent to [`bitset.count_ones(..) == 0`](FixedBitSet::count_ones).
303    #[inline]
304    pub fn is_clear(&self) -> bool {
305        self.as_simd_slice().iter().all(|block| block.is_empty())
306    }
307
308    /// Finds the lowest set bit in the bitset.
309    ///
310    /// Returns `None` if there aren't any set bits.
311    ///
312    /// ```
313    /// # use fixedbitset::FixedBitSet;
314    /// let mut bitset = FixedBitSet::with_capacity(10);
315    /// assert_eq!(bitset.minimum(), None);
316    ///
317    /// bitset.insert(2);
318    /// assert_eq!(bitset.minimum(), Some(2));
319    /// bitset.insert(8);
320    /// assert_eq!(bitset.minimum(), Some(2));
321    /// ```
322    #[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    /// Finds the highest set bit in the bitset.
343    ///
344    /// Returns `None` if there aren't any set bits.
345    ///
346    /// ```
347    /// # use fixedbitset::FixedBitSet;
348    /// let mut bitset = FixedBitSet::with_capacity(10);
349    /// assert_eq!(bitset.maximum(), None);
350    ///
351    /// bitset.insert(8);
352    /// assert_eq!(bitset.maximum(), Some(8));
353    /// bitset.insert(2);
354    /// assert_eq!(bitset.maximum(), Some(8));
355    /// ```
356    #[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    /// `true` if all bits in the [`FixedBitSet`] are set.
379    ///
380    /// ```
381    /// # use fixedbitset::FixedBitSet;
382    /// let mut bitset = FixedBitSet::with_capacity(10);
383    /// assert!(!bitset.is_full());
384    ///
385    /// bitset.insert_range(..);
386    /// assert!(bitset.is_full());
387    /// ```
388    ///
389    /// This is equivalent to [`bitset.count_ones(..) == bitset.len()`](FixedBitSet::count_ones).
390    #[inline]
391    pub fn is_full(&self) -> bool {
392        self.contains_all_in_range(..)
393    }
394
395    /// Return **true** if the bit is enabled in the **FixedBitSet**,
396    /// **false** otherwise.
397    ///
398    /// Note: bits outside the capacity are always disabled.
399    ///
400    /// Note: Also available with index syntax: `bitset[bit]`.
401    #[inline]
402    pub fn contains(&self, bit: usize) -> bool {
403        if bit < self.length {
404            // SAFETY: The above check ensures that the block and bit are within bounds.
405            unsafe { self.contains_unchecked(bit) }
406        } else {
407            false
408        }
409    }
410
411    /// Return **true** if the bit is enabled in the **FixedBitSet**,
412    /// **false** otherwise.
413    ///
414    /// Note: unlike `contains`, calling this with an invalid `bit`
415    /// is undefined behavior.
416    ///
417    /// # Safety
418    /// `bit` must be less than `self.len()`
419    #[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    /// Clear all bits.
426    #[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    /// Enable `bit`.
434    ///
435    /// **Panics** if **bit** is out of bounds.
436    #[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        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
445        unsafe {
446            self.insert_unchecked(bit);
447        }
448    }
449
450    /// Enable `bit` without any length checks.
451    ///
452    /// # Safety
453    /// `bit` must be less than `self.len()`
454    #[inline]
455    pub unsafe fn insert_unchecked(&mut self, bit: usize) {
456        let (block, i) = div_rem(bit, BITS);
457        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
458        unsafe {
459            *self.get_unchecked_mut(block) |= 1 << i;
460        }
461    }
462
463    /// Disable `bit`.
464    ///
465    /// **Panics** if **bit** is out of bounds.
466    #[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        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
475        unsafe {
476            self.remove_unchecked(bit);
477        }
478    }
479
480    /// Disable `bit` without any bounds checking.
481    ///
482    /// # Safety
483    /// `bit` must be less than `self.len()`
484    #[inline]
485    pub unsafe fn remove_unchecked(&mut self, bit: usize) {
486        let (block, i) = div_rem(bit, BITS);
487        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
488        unsafe {
489            *self.get_unchecked_mut(block) &= !(1 << i);
490        }
491    }
492
493    /// Enable `bit`, and return its previous value.
494    ///
495    /// **Panics** if **bit** is out of bounds.
496    #[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        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
505        unsafe { self.put_unchecked(bit) }
506    }
507
508    /// Enable `bit`, and return its previous value without doing any bounds checking.
509    ///
510    /// # Safety
511    /// `bit` must be less than `self.len()`
512    #[inline]
513    pub unsafe fn put_unchecked(&mut self, bit: usize) -> bool {
514        let (block, i) = div_rem(bit, BITS);
515        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
516        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    /// Toggle `bit` (inverting its state).
525    ///
526    /// ***Panics*** if **bit** is out of bounds
527    #[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        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
536        unsafe {
537            self.toggle_unchecked(bit);
538        }
539    }
540
541    /// Toggle `bit` (inverting its state) without any bounds checking.
542    ///
543    /// # Safety
544    /// `bit` must be less than `self.len()`
545    #[inline]
546    pub unsafe fn toggle_unchecked(&mut self, bit: usize) {
547        let (block, i) = div_rem(bit, BITS);
548        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
549        unsafe {
550            *self.get_unchecked_mut(block) ^= 1 << i;
551        }
552    }
553
554    /// Sets a bit to the provided `enabled` value.
555    ///
556    /// **Panics** if **bit** is out of bounds.
557    #[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        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
566        unsafe {
567            self.set_unchecked(bit, enabled);
568        }
569    }
570
571    /// Sets a bit to the provided `enabled` value without doing any bounds checking.
572    ///
573    /// # Safety
574    /// `bit` must be less than `self.len()`
575    #[inline]
576    pub unsafe fn set_unchecked(&mut self, bit: usize, enabled: bool) {
577        let (block, i) = div_rem(bit, BITS);
578        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
579        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    /// Copies boolean value from specified bit to the specified bit.
588    ///
589    /// If `from` is out-of-bounds, `to` will be unset.
590    ///
591    /// **Panics** if **to** is out of bounds.
592    #[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        // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
602        unsafe { self.set_unchecked(to, enabled) };
603    }
604
605    /// Copies boolean value from specified bit to the specified bit.
606    ///
607    /// Note: unlike `copy_bit`, calling this with an invalid `from`
608    /// is undefined behavior.
609    ///
610    /// # Safety
611    /// `to` must both be less than `self.len()`
612    #[inline]
613    pub unsafe fn copy_bit_unchecked(&mut self, from: usize, to: usize) {
614        // SAFETY: Caller must ensure that `from` is within bounds.
615        let enabled = self.contains_unchecked(from);
616        // SAFETY: Caller must ensure that `to` is within bounds.
617        self.set_unchecked(to, enabled);
618    }
619
620    /// Count the number of set bits in the given bit range.
621    ///
622    /// This function is potentially much faster than using `ones(other).count()`.
623    /// Use `..` to count the whole content of the bitset.
624    ///
625    /// **Panics** if the range extends past the end of the bitset.
626    #[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            // SAFETY: Masks cannot return a block index that is out of range.
630            unsafe { *self.get_unchecked(block) & mask }
631        }))
632    }
633
634    /// Count the number of unset bits in the given bit range.
635    ///
636    /// This function is potentially much faster than using `zeroes(other).count()`.
637    /// Use `..` to count the whole content of the bitset.
638    ///
639    /// **Panics** if the range extends past the end of the bitset.
640    #[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            // SAFETY: Masks cannot return a block index that is out of range.
644            unsafe { !*self.get_unchecked(block) & mask }
645        }))
646    }
647
648    /// Sets every bit in the given range to the given state (`enabled`)
649    ///
650    /// Use `..` to set the whole bitset.
651    ///
652    /// **Panics** if the range extends past the end of the bitset.
653    #[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    /// Enables every bit in the given range.
663    ///
664    /// Use `..` to make the whole bitset ones.
665    ///
666    /// **Panics** if the range extends past the end of the bitset.
667    #[inline]
668    pub fn insert_range<T: IndexRange>(&mut self, range: T) {
669        for (block, mask) in Masks::new(range, self.length) {
670            // SAFETY: Masks cannot return a block index that is out of range.
671            let block = unsafe { self.get_unchecked_mut(block) };
672            *block |= mask;
673        }
674    }
675
676    /// Disables every bit in the given range.
677    ///
678    /// Use `..` to make the whole bitset ones.
679    ///
680    /// **Panics** if the range extends past the end of the bitset.
681    #[inline]
682    pub fn remove_range<T: IndexRange>(&mut self, range: T) {
683        for (block, mask) in Masks::new(range, self.length) {
684            // SAFETY: Masks cannot return a block index that is out of range.
685            let block = unsafe { self.get_unchecked_mut(block) };
686            *block &= !mask;
687        }
688    }
689
690    /// Toggles (inverts) every bit in the given range.
691    ///
692    /// Use `..` to toggle the whole bitset.
693    ///
694    /// **Panics** if the range extends past the end of the bitset.
695    #[inline]
696    pub fn toggle_range<T: IndexRange>(&mut self, range: T) {
697        for (block, mask) in Masks::new(range, self.length) {
698            // SAFETY: Masks cannot return a block index that is out of range.
699            let block = unsafe { self.get_unchecked_mut(block) };
700            *block ^= mask;
701        }
702    }
703
704    /// Checks if the bitset contains every bit in the given range.
705    ///
706    /// **Panics** if the range extends past the end of the bitset.
707    #[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            // SAFETY: Masks cannot return a block index that is out of range.
711            let block = unsafe { self.get_unchecked(block) };
712            if block & mask != mask {
713                return false;
714            }
715        }
716        true
717    }
718
719    /// Checks if the bitset contains at least one set bit in the given range.
720    ///
721    /// **Panics** if the range extends past the end of the bitset.
722    #[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            // SAFETY: Masks cannot return a block index that is out of range.
726            let block = unsafe { self.get_unchecked(block) };
727            if block & mask != 0 {
728                return true;
729            }
730        }
731        false
732    }
733
734    /// View the bitset as a slice of `Block` blocks
735    #[inline]
736    pub fn as_slice(&self) -> &[Block] {
737        // SAFETY: The bits from both usize and Block are required to be reinterprettable, and
738        // neither have any padding or alignment issues. The slice constructed is within bounds
739        // of the underlying allocation. This function is called with a read-only  borrow so
740        // no other write can happen as long as the returned borrow lives.
741        unsafe {
742            let ptr = self.data.as_ptr().cast::<Block>();
743            core::slice::from_raw_parts(ptr, self.usize_len())
744        }
745    }
746
747    /// View the bitset as a mutable slice of `Block` blocks. Writing past the bitlength in the last
748    /// will cause `contains` to return potentially incorrect results for bits past the bitlength.
749    #[inline]
750    pub fn as_mut_slice(&mut self) -> &mut [Block] {
751        // SAFETY: The bits from both usize and Block are required to be reinterprettable, and
752        // neither have any padding or alignment issues. The slice constructed is within bounds
753        // of the underlying allocation. This function is called with a mutable borrow so
754        // no other read or write can happen as long as the returned borrow lives.
755        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    /// Iterates over all enabled bits.
762    ///
763    /// Iterator element is the index of the `1` bit, type `usize`.
764    #[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    /// Iterates over all enabled bits.
788    ///
789    /// Iterator element is the index of the `1` bit, type `usize`.
790    /// Unlike `ones`, this function consumes the `FixedBitset`.
791    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        // SAFETY:
795        // - ptr comes from self.data, so it is valid;
796        // - self.data is valid for self.data.len() SimdBlocks,
797        //   which is exactly self.data.len() * SimdBlock::USIZE_COUNT usizes;
798        // - we will keep this slice around only as long as self.data is,
799        //   so it won't become dangling.
800        let slice = unsafe { core::slice::from_raw_parts(ptr, len) };
801        // SAFETY: The data pointer and capacity were created from a Vec initially. The block
802        // len is identical to that of the original.
803        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    /// Iterates over all disabled bits.
825    ///
826    /// Iterator element is the index of the `0` bit, type `usize`.
827    #[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    /// Returns a lazy iterator over the intersection of two `FixedBitSet`s
846    pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a> {
847        Intersection {
848            iter: self.ones(),
849            other,
850        }
851    }
852
853    /// Returns a lazy iterator over the union of two `FixedBitSet`s.
854    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    /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a`
861    /// and `b` is the elements of `a` which are not in `b`.
862    pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a> {
863        Difference {
864            iter: self.ones(),
865            other,
866        }
867    }
868
869    /// Returns a lazy iterator over the symmetric difference of two `FixedBitSet`s.
870    /// The symmetric difference of `a` and `b` is the elements of one, but not both, sets.
871    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    /// In-place union of two `FixedBitSet`s.
878    ///
879    /// On calling this method, `self`'s capacity may be increased to match `other`'s.
880    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    /// In-place intersection of two `FixedBitSet`s.
891    ///
892    /// On calling this method, `self`'s capacity will remain the same as before.
893    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    /// In-place difference of two `FixedBitSet`s.
906    ///
907    /// On calling this method, `self`'s capacity will remain the same as before.
908    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        // There's no need to grow self or do any other adjustments.
917        //
918        // * If self is longer than other, the bits at the end of self won't be affected since other
919        //   has them implicitly set to 0.
920        // * If other is longer than self, the bits at the end of other are irrelevant since self
921        //   has them set to 0 anyway.
922    }
923
924    /// In-place symmetric difference of two `FixedBitSet`s.
925    ///
926    /// On calling this method, `self`'s capacity may be increased to match `other`'s.
927    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    /// Computes how many bits would be set in the union between two bitsets.
940    ///
941    /// This is potentially much faster than using `union(other).count()`. Unlike
942    /// other methods like using [`union_with`] followed by [`count_ones`], this
943    /// does not mutate in place or require separate allocations.
944    #[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    /// Computes how many bits would be set in the intersection between two bitsets.
957    ///
958    /// This is potentially much faster than using `intersection(other).count()`. Unlike
959    /// other methods like using [`intersect_with`] followed by [`count_ones`], this
960    /// does not mutate in place or require separate allocations.
961    #[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    /// Computes how many bits would be set in the difference between two bitsets.
972    ///
973    /// This is potentially much faster than using `difference(other).count()`. Unlike
974    /// other methods like using [`difference_with`] followed by [`count_ones`], this
975    /// does not mutate in place or require separate allocations.
976    #[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    /// Computes how many bits would be set in the symmetric difference between two bitsets.
987    ///
988    /// This is potentially much faster than using `symmetric_difference(other).count()`. Unlike
989    /// other methods like using [`symmetric_difference_with`] followed by [`count_ones`], this
990    /// does not mutate in place or require separate allocations.
991    #[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    /// Returns `true` if `self` has no elements in common with `other`. This
1004    /// is equivalent to checking for an empty intersection.
1005    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    /// Returns `true` if the set is a subset of another, i.e. `other` contains
1013    /// at least all the values in `self`.
1014    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    /// Returns `true` if the set is a superset of another, i.e. `self` contains
1024    /// at least all the values in `other`.
1025    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        // SAFETY: The data pointer and capacity were created from a Vec initially. The block
1066        // len is identical to that of the original.
1067        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
1097/// An iterator producing elements in the difference of two sets.
1098///
1099/// This struct is created by the [`FixedBitSet::difference`] method.
1100pub 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
1128// Difference will continue to return None once it first returns None.
1129impl<'a> FusedIterator for Difference<'a> {}
1130
1131/// An iterator producing elements in the symmetric difference of two sets.
1132///
1133/// This struct is created by the [`FixedBitSet::symmetric_difference`] method.
1134pub 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
1158// SymmetricDifference will continue to return None once it first returns None.
1159impl<'a> FusedIterator for SymmetricDifference<'a> {}
1160
1161/// An iterator producing elements in the intersection of two sets.
1162///
1163/// This struct is created by the [`FixedBitSet::intersection`] method.
1164pub struct Intersection<'a> {
1165    iter: Ones<'a>,
1166    other: &'a FixedBitSet,
1167}
1168
1169impl<'a> Iterator for Intersection<'a> {
1170    type Item = usize; // the bit position of the '1'
1171
1172    #[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
1192// Intersection will continue to return None once it first returns None.
1193impl<'a> FusedIterator for Intersection<'a> {}
1194
1195/// An iterator producing elements in the union of two sets.
1196///
1197/// This struct is created by the [`FixedBitSet::union`] method.
1198pub 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
1222// Union will continue to return None once it first returns None.
1223impl<'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            // this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0.
1254        }
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
1290// Masks will continue to return None once it first returns None.
1291impl FusedIterator for Masks {}
1292
1293// Masks's size_hint implementation is exact. It never returns an
1294// unbounded value and always returns an exact number of values.
1295impl ExactSizeIterator for Masks {}
1296
1297/// An  iterator producing the indices of the set bit in a set.
1298///
1299/// This struct is created by the [`FixedBitSet::ones`] method.
1300#[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    /// Clears the least significant set bit and returns its index.
1311    ///
1312    /// If `n` is zero, returns the number of bits in a block and leaves it unchanged.
1313    #[inline]
1314    pub fn last_positive_bit_and_unset(n: &mut usize) -> usize {
1315        // Find the last set bit using x & -x
1316        let last_bit = *n & n.wrapping_neg();
1317
1318        // Find the position of the last set bit
1319        let position = last_bit.trailing_zeros();
1320
1321        // Unset the last set bit
1322        *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        /* Identify the first non zero bit */
1330        let bit_idx = n.leading_zeros();
1331
1332        /* set that bit to zero */
1333        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; // the bit position of the '1'
1373
1374    #[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                        // not needed for iteration, but for size_hint
1385                        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
1411// Ones will continue to return None once it first returns None.
1412impl<'a> FusedIterator for Ones<'a> {}
1413
1414/// An  iterator producing the indices of the unset bit in a set.
1415///
1416/// This struct is created by the [`FixedBitSet::zeroes`] method.
1417pub 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; // the bit position of the '1'
1426
1427    #[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        // The remaining zeroes beyond the length of the bitset must be excluded.
1438        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
1451// Zeroes will stop returning Some when exhausted.
1452impl<'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            // SAFETY: `fill` is uninitialized, but is immediately initialized from `source`.
1464            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            // The grow_inner above ensures that self is at least as large as source.
1476            // so this branch is unreachable.
1477            Ordering::Less => {}
1478        }
1479        self.length = source.length;
1480    }
1481}
1482
1483/// Return **true** if the bit is enabled in the bitset,
1484/// or **false** otherwise.
1485///
1486/// Note: bits outside the capacity are always disabled, and thus
1487/// indexing a FixedBitSet will not panic.
1488impl 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
1501/// Sets the bit at index **i** to **true** for each item **i** in the input **src**.
1502impl 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
1514/// Return a FixedBitSet containing bits set to **true** for every bit index in
1515/// the iterator, other bits are set to **false**.
1516impl 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    // Keep buf along so that `remaining_blocks` remains valid.
1531    _buf: Vec<SimdBlock>,
1532}
1533
1534impl IntoOnes {
1535    /// Clears the least significant set bit and returns its index.
1536    ///
1537    /// If `n` is zero, returns the number of bits in a block and leaves it unchanged.
1538    #[inline]
1539    pub fn last_positive_bit_and_unset(n: &mut Block) -> usize {
1540        // Find the last set bit using x & -x
1541        let last_bit = *n & n.wrapping_neg();
1542
1543        // Find the position of the last set bit
1544        let position = last_bit.trailing_zeros();
1545
1546        // Unset the last set bit
1547        *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        /* Identify the first non zero bit */
1555        let bit_idx = n.leading_zeros();
1556
1557        /* set that bit to zero */
1558        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; // the bit position of the '1'
1598
1599    #[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                        // not needed for iteration, but for size_hint
1610                        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
1636// Ones will continue to return None once it first returns None.
1637impl 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}