Skip to main content

bit_vec/
lib.rs

1// Copyright 2012-2023 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11// FIXME(Gankro): BitVec and BitSet are very tightly coupled. Ideally (for
12// maintenance), they should be in separate files/modules, with BitSet only
13// using BitVec's public API. This will be hard for performance though, because
14// `BitVec` will not want to leak its internal representation while its internal
15// representation as `u32`s must be assumed for best performance.
16
17// (1) Be careful, most things can overflow here because the amount of bits in
18//     memory can overflow `usize`.
19// (2) Make sure that the underlying vector has no excess length:
20//     E. g. `nbits == 16`, `storage.len() == 2` would be excess length,
21//     because the last word isn't used at all. This is important because some
22//     methods rely on it (for *CORRECTNESS*).
23// (3) Make sure that the unused bits in the last word are zeroed out, again
24//     other methods rely on it for *CORRECTNESS*.
25// (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in
26// `BitVec` will need to be reflected in `BitSet`.
27
28//! # Description
29//!
30//! Dynamic collections implemented with compact bit vectors.
31//!
32//! # Examples
33//!
34//! This is a simple example of the [Sieve of Eratosthenes][sieve]
35//! which calculates prime numbers up to a given limit.
36//!
37//! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
38//!
39//! ```
40//! use bit_vec::BitVec;
41//!
42//! let max_prime = 10000;
43//!
44//! // Store the primes as a BitVec
45//! let primes = {
46//!     // Assume all numbers are prime to begin, and then we
47//!     // cross off non-primes progressively
48//!     let mut bv = BitVec::from_elem(max_prime, true);
49//!
50//!     // Neither 0 nor 1 are prime
51//!     bv.set(0, false);
52//!     bv.set(1, false);
53//!
54//!     for i in 2.. 1 + (max_prime as f64).sqrt() as usize {
55//!         // if i is a prime
56//!         if bv[i] {
57//!             // Mark all multiples of i as non-prime (any multiples below i * i
58//!             // will have been marked as non-prime previously)
59//!             for j in i.. {
60//!                 if i * j >= max_prime {
61//!                     break;
62//!                 }
63//!                 bv.set(i * j, false)
64//!             }
65//!         }
66//!     }
67//!     bv
68//! };
69//!
70//! // Simple primality tests below our max bound
71//! let print_primes = 20;
72//! print!("The primes below {} are: ", print_primes);
73//! for x in 0..print_primes {
74//!     if primes.get(x).unwrap_or(false) {
75//!         print!("{} ", x);
76//!     }
77//! }
78//! println!();
79//!
80//! let num_primes = primes.iter().filter(|x| *x).count();
81//! println!("There are {} primes below {}", num_primes, max_prime);
82//! assert_eq!(num_primes, 1_229);
83//! ```
84
85#![doc(html_root_url = "https://docs.rs/bit-vec/0.9.0/bit_vec/")]
86#![no_std]
87#![deny(clippy::shadow_reuse)]
88#![deny(clippy::shadow_same)]
89#![deny(clippy::shadow_unrelated)]
90#![warn(clippy::multiple_inherent_impl)]
91#![warn(clippy::multiple_crate_versions)]
92#![warn(clippy::single_match)]
93#![warn(clippy::missing_safety_doc)]
94
95#[cfg(any(test, feature = "std"))]
96#[macro_use]
97extern crate std;
98
99#[cfg(all(feature = "std", feature = "borsh"))]
100use std::borrow::ToOwned;
101#[cfg(all(feature = "std", feature = "miniserde"))]
102use std::boxed::Box;
103#[cfg(feature = "std")]
104use std::rc::Rc;
105#[cfg(feature = "std")]
106use std::string::String;
107#[cfg(feature = "std")]
108use std::vec::Vec;
109
110#[cfg(not(feature = "std"))]
111#[macro_use]
112extern crate alloc;
113#[cfg(all(not(feature = "std"), feature = "borsh"))]
114use alloc::borrow::ToOwned;
115#[cfg(all(not(feature = "std"), feature = "miniserde"))]
116use alloc::boxed::Box;
117#[cfg(not(feature = "std"))]
118use alloc::rc::Rc;
119#[cfg(not(feature = "std"))]
120use alloc::string::String;
121#[cfg(not(feature = "std"))]
122use alloc::vec::Vec;
123
124use core::error::Error;
125
126#[cfg(feature = "borsh")]
127extern crate borsh;
128#[cfg(feature = "miniserde")]
129extern crate miniserde;
130#[cfg(feature = "serde")]
131extern crate serde;
132
133mod util;
134
135use core::cell::RefCell;
136use core::cmp::Ordering;
137use core::fmt::Write;
138use core::iter::FromIterator;
139use core::ops::*;
140use core::{cmp, fmt, hash, iter, mem, slice};
141
142/// Abstracts over a pile of bits (basically unsigned primitives)
143pub trait BitBlock:
144    Copy
145    + Add<Self, Output = Self>
146    + Sub<Self, Output = Self>
147    + Shl<usize, Output = Self>
148    + Shr<usize, Output = Self>
149    + Not<Output = Self>
150    + BitAnd<Self, Output = Self>
151    + BitOr<Self, Output = Self>
152    + BitXor<Self, Output = Self>
153    + Rem<Self, Output = Self>
154    + BitOrAssign<Self>
155    + Eq
156    + Ord
157    + hash::Hash
158{
159    /// How many bits it has
160    fn bits() -> usize;
161    /// How many bytes it has
162    #[inline]
163    fn bytes() -> usize {
164        Self::bits() / 8
165    }
166    /// Convert a byte into this type (lowest-order bits set)
167    fn from_byte(byte: u8) -> Self;
168    /// Count the number of 1's in the bitwise repr
169    fn count_ones(self) -> usize;
170    /// Count the number of 0's in the bitwise repr
171    fn count_zeros(self) -> usize {
172        Self::bits() - self.count_ones()
173    }
174    /// Get `0`
175    fn zero() -> Self;
176    /// Get `1`
177    fn one() -> Self;
178}
179
180macro_rules! bit_block_impl {
181    ($(($t: ident, $size: expr)),*) => ($(
182        impl BitBlock for $t {
183            #[inline]
184            fn bits() -> usize { $size }
185            #[inline]
186            fn from_byte(byte: u8) -> Self { $t::from(byte) }
187            #[inline]
188            fn count_ones(self) -> usize { self.count_ones() as usize }
189            #[inline]
190            fn count_zeros(self) -> usize { self.count_zeros() as usize }
191            #[inline]
192            fn one() -> Self { 1 }
193            #[inline]
194            fn zero() -> Self { 0 }
195        }
196    )*)
197}
198
199bit_block_impl! {
200    (u8, 8),
201    (u16, 16),
202    (u32, 32),
203    (u64, 64),
204    (usize, core::mem::size_of::<usize>() * 8)
205}
206
207/// The bitvector type.
208///
209/// # Examples
210///
211/// ```
212/// use bit_vec::BitVec;
213///
214/// let mut bv = BitVec::from_elem(10, false);
215///
216/// // insert all primes less than 10
217/// bv.set(2, true);
218/// bv.set(3, true);
219/// bv.set(5, true);
220/// bv.set(7, true);
221/// println!("{:?}", bv);
222/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
223///
224/// // flip all values in bitvector, producing non-primes less than 10
225/// bv.negate();
226/// println!("{:?}", bv);
227/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
228///
229/// // reset bitvector to empty
230/// bv.fill(false);
231/// println!("{:?}", bv);
232/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
233/// ```
234#[cfg_attr(feature = "serde", derive(serde::Serialize))]
235#[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize))]
236#[cfg_attr(feature = "miniserde", derive(miniserde::Serialize))]
237pub struct BitVec<B = u32> {
238    /// Internal representation of the bit vector
239    storage: Vec<B>,
240    /// The number of valid bits in the internal representation
241    nbits: usize,
242}
243
244#[cfg(any(feature = "serde", feature = "borsh", feature = "miniserde"))]
245#[cfg_attr(feature = "serde", derive(serde::Deserialize))]
246#[cfg_attr(feature = "borsh", derive(borsh::BorshDeserialize))]
247#[cfg_attr(feature = "miniserde", derive(miniserde::Deserialize))]
248struct UncheckedBitVec<B = u32> {
249    storage: Vec<B>,
250    nbits: usize,
251}
252
253#[cfg(feature = "serde")]
254impl<'de, B: BitBlock> serde::Deserialize<'de> for BitVec<B>
255where
256    B: serde::Deserialize<'de>,
257{
258    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
259    where
260        D: serde::Deserializer<'de>,
261    {
262        use serde::de::Error;
263        UncheckedBitVec::<B>::deserialize(deserializer).and_then(|unchecked| {
264            let result = BitVec {
265                storage: unchecked.storage,
266                nbits: unchecked.nbits,
267            };
268            if !result.storage_len_matches_nbits() {
269                Err(D::Error::custom(DeserializeError::StorageLenMismatch))
270            } else if !result.is_last_block_fixed() {
271                Err(D::Error::custom(DeserializeError::TrailingBits))
272            } else {
273                Ok(result)
274            }
275        })
276    }
277}
278
279#[cfg(feature = "borsh")]
280impl<B: BitBlock> borsh::BorshDeserialize for BitVec<B>
281where
282    B: borsh::BorshDeserialize,
283{
284    fn deserialize_reader<R: borsh::io::Read>(reader: &mut R) -> borsh::io::Result<Self> {
285        UncheckedBitVec::<B>::deserialize_reader(reader).and_then(|unchecked| {
286            let result = BitVec {
287                storage: unchecked.storage,
288                nbits: unchecked.nbits,
289            };
290            if !result.storage_len_matches_nbits() {
291                Err(borsh::io::Error::other(
292                    DeserializeError::StorageLenMismatch,
293                ))
294            } else if !result.is_last_block_fixed() {
295                Err(borsh::io::Error::other(DeserializeError::TrailingBits))
296            } else {
297                Ok(result)
298            }
299        })
300    }
301}
302
303#[cfg(feature = "miniserde")]
304miniserde::make_place!(Place);
305
306#[cfg(feature = "miniserde")]
307struct BitVecBuilder<'a, B> {
308    storage: Option<Vec<B>>,
309    nbits: Option<usize>,
310    out: &'a mut Option<BitVec<B>>,
311}
312
313#[cfg(feature = "miniserde")]
314impl<B: BitBlock> miniserde::de::Visitor for Place<BitVec<B>>
315where
316    B: miniserde::Deserialize,
317{
318    fn map(&mut self) -> miniserde::Result<Box<dyn miniserde::de::Map + '_>> {
319        Ok(Box::new(BitVecBuilder {
320            storage: None,
321            nbits: None,
322            out: &mut self.out,
323        }))
324    }
325}
326
327#[cfg(feature = "miniserde")]
328impl<B: BitBlock> miniserde::de::Map for BitVecBuilder<'_, B>
329where
330    B: miniserde::Deserialize,
331{
332    fn key(&mut self, k: &str) -> miniserde::Result<&mut dyn miniserde::de::Visitor> {
333        match k {
334            "storage" => Ok(miniserde::Deserialize::begin(&mut self.storage)),
335            "nbits" => Ok(miniserde::Deserialize::begin(&mut self.nbits)),
336            _ => Ok(<dyn miniserde::de::Visitor>::ignore()),
337        }
338    }
339
340    fn finish(&mut self) -> miniserde::Result<()> {
341        let storage = self.storage.take().ok_or(miniserde::Error)?;
342        let nbits = self.nbits.take().ok_or(miniserde::Error)?;
343        let result = BitVec { storage, nbits };
344        if !result.storage_len_matches_nbits() || !result.is_last_block_fixed() {
345            Err(miniserde::Error)
346        } else {
347            *self.out = Some(result);
348            Ok(())
349        }
350    }
351}
352
353#[cfg(feature = "miniserde")]
354impl<B: BitBlock> miniserde::Deserialize for BitVec<B>
355where
356    B: miniserde::Deserialize,
357{
358    fn begin(out: &mut Option<Self>) -> &mut dyn miniserde::de::Visitor {
359        Place::new(out)
360    }
361}
362
363#[derive(Debug)]
364pub enum DeserializeError {
365    StorageLenMismatch,
366    TrailingBits,
367}
368
369impl core::fmt::Display for DeserializeError {
370    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
371        f.write_str(self.simple_description())
372    }
373}
374
375#[cfg(feature = "borsh")]
376impl From<DeserializeError> for String {
377    fn from(value: DeserializeError) -> Self {
378        value.simple_description().to_owned()
379    }
380}
381
382impl Error for DeserializeError {}
383
384impl DeserializeError {
385    fn simple_description(&self) -> &str {
386        match self {
387            DeserializeError::TrailingBits => "some out of bounds trailing bits are set",
388            DeserializeError::StorageLenMismatch => "nbits and storage length isnt same",
389        }
390    }
391}
392
393// FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
394impl<B: BitBlock> Index<usize> for BitVec<B> {
395    type Output = bool;
396
397    #[inline]
398    fn index(&self, i: usize) -> &bool {
399        if self.get(i).expect("index out of bounds") {
400            &true
401        } else {
402            &false
403        }
404    }
405}
406
407/// Computes how many blocks are needed to store that many bits
408fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
409    // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
410    // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
411    // one too many. So we need to check if that's the case. We can do that by computing if
412    // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
413    // superior modulo operator on a power of two to this.
414    //
415    // Note that we can technically avoid this branch with the expression
416    // `(nbits + U32_BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
417    if bits % B::bits() == 0 {
418        bits / B::bits()
419    } else {
420        bits / B::bits() + 1
421    }
422}
423
424/// Computes the bitmask for the final word of the vector
425fn mask_for_bits<B: BitBlock>(bits: usize) -> B {
426    // Note especially that a perfect multiple of U32_BITS should mask all 1s.
427    (!B::zero()) >> ((B::bits() - bits % B::bits()) % B::bits())
428}
429
430impl BitVec<u32> {
431    /// Creates an empty `BitVec`.
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// use bit_vec::BitVec;
437    /// let mut bv = BitVec::new();
438    /// ```
439    #[inline]
440    pub fn new() -> Self {
441        Default::default()
442    }
443
444    /// Creates a `BitVec` that holds `nbits` elements, setting each element
445    /// to `bit`.
446    ///
447    /// # Examples
448    ///
449    /// ```
450    /// use bit_vec::BitVec;
451    ///
452    /// let mut bv = BitVec::from_elem(10, false);
453    /// assert_eq!(bv.len(), 10);
454    /// for x in bv.iter() {
455    ///     assert_eq!(x, false);
456    /// }
457    /// ```
458    #[inline]
459    pub fn from_elem(len: usize, bit: bool) -> Self {
460        BitVec::<u32>::from_elem_general(len, bit)
461    }
462
463    /// Constructs a new, empty `BitVec` with the specified capacity.
464    ///
465    /// The bitvector will be able to hold at least `capacity` bits without
466    /// reallocating. If `capacity` is 0, it will not allocate.
467    ///
468    /// It is important to note that this function does not specify the
469    /// *length* of the returned bitvector, but only the *capacity*.
470    #[inline]
471    pub fn with_capacity(capacity: usize) -> Self {
472        BitVec::<u32>::with_capacity_general(capacity)
473    }
474
475    /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits,
476    /// with the most significant bits of each byte coming first. Each
477    /// bit becomes `true` if equal to 1 or `false` if equal to 0.
478    ///
479    /// # Examples
480    ///
481    /// ```
482    /// use bit_vec::BitVec;
483    ///
484    /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]);
485    /// assert!(bv.eq_vec(&[true, false, true, false,
486    ///                     false, false, false, false,
487    ///                     false, false, false, true,
488    ///                     false, false, true, false]));
489    /// ```
490    pub fn from_bytes(bytes: &[u8]) -> Self {
491        BitVec::<u32>::from_bytes_general(bytes)
492    }
493
494    /// Creates a `BitVec` of the specified length where the value at each index
495    /// is `f(index)`.
496    ///
497    /// # Examples
498    ///
499    /// ```
500    /// use bit_vec::BitVec;
501    ///
502    /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 });
503    /// assert!(bv.eq_vec(&[true, false, true, false, true]));
504    /// ```
505    #[inline]
506    pub fn from_fn<F>(len: usize, f: F) -> Self
507    where
508        F: FnMut(usize) -> bool,
509    {
510        BitVec::<u32>::from_fn_general(len, f)
511    }
512}
513
514impl<B: BitBlock> BitVec<B> {
515    /// Creates an empty `BitVec`.
516    ///
517    /// # Examples
518    ///
519    /// ```
520    /// use bit_vec::BitVec;
521    /// let mut bv = BitVec::<usize>::new_general();
522    /// ```
523    #[inline]
524    pub fn new_general() -> Self {
525        Default::default()
526    }
527
528    /// Creates a `BitVec` that holds `nbits` elements, setting each element
529    /// to `bit`.
530    ///
531    /// # Examples
532    ///
533    /// ```
534    /// use bit_vec::BitVec;
535    ///
536    /// let mut bv = BitVec::<usize>::from_elem_general(10, false);
537    /// assert_eq!(bv.len(), 10);
538    /// for x in bv.iter() {
539    ///     assert_eq!(x, false);
540    /// }
541    /// ```
542    #[inline]
543    pub fn from_elem_general(len: usize, bit: bool) -> Self {
544        let nblocks = blocks_for_bits::<B>(len);
545        let mut bit_vec = BitVec {
546            storage: vec![if bit { !B::zero() } else { B::zero() }; nblocks],
547            nbits: len,
548        };
549        bit_vec.fix_last_block();
550        bit_vec
551    }
552
553    /// Constructs a new, empty `BitVec` with the specified capacity.
554    ///
555    /// The bitvector will be able to hold at least `capacity` bits without
556    /// reallocating. If `capacity` is 0, it will not allocate.
557    ///
558    /// It is important to note that this function does not specify the
559    /// *length* of the returned bitvector, but only the *capacity*.
560    #[inline]
561    pub fn with_capacity_general(capacity: usize) -> Self {
562        BitVec {
563            storage: Vec::with_capacity(blocks_for_bits::<B>(capacity)),
564            nbits: 0,
565        }
566    }
567
568    /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits,
569    /// with the most significant bits of each byte coming first. Each
570    /// bit becomes `true` if equal to 1 or `false` if equal to 0.
571    ///
572    /// # Examples
573    ///
574    /// ```
575    /// use bit_vec::BitVec;
576    ///
577    /// let bv = BitVec::<usize>::from_bytes_general(&[0b10100000, 0b00010010]);
578    /// assert!(bv.eq_vec(&[true, false, true, false,
579    ///                     false, false, false, false,
580    ///                     false, false, false, true,
581    ///                     false, false, true, false]));
582    /// ```
583    pub fn from_bytes_general(bytes: &[u8]) -> Self {
584        let len = bytes
585            .len()
586            .checked_mul(u8::bits())
587            .expect("capacity overflow");
588        let mut bit_vec = BitVec::with_capacity_general(len);
589        let complete_words = bytes.len() / B::bytes();
590        let extra_bytes = bytes.len() % B::bytes();
591
592        bit_vec.nbits = len;
593
594        for i in 0..complete_words {
595            let mut accumulator = B::zero();
596            for idx in 0..B::bytes() {
597                accumulator |=
598                    B::from_byte(util::reverse_bits(bytes[i * B::bytes() + idx])) << (idx * 8)
599            }
600            bit_vec.storage.push(accumulator);
601        }
602
603        if extra_bytes > 0 {
604            let mut last_word = B::zero();
605            for (i, &byte) in bytes[complete_words * B::bytes()..].iter().enumerate() {
606                last_word |= B::from_byte(util::reverse_bits(byte)) << (i * 8);
607            }
608            bit_vec.storage.push(last_word);
609        }
610
611        bit_vec
612    }
613
614    /// Creates a `BitVec` of the specified length where the value at each index
615    /// is `f(index)`.
616    ///
617    /// # Examples
618    ///
619    /// ```
620    /// use bit_vec::BitVec;
621    ///
622    /// let bv = BitVec::<usize>::from_fn_general(5, |i| { i % 2 == 0 });
623    /// assert!(bv.eq_vec(&[true, false, true, false, true]));
624    /// ```
625    #[inline]
626    pub fn from_fn_general<F>(len: usize, mut f: F) -> Self
627    where
628        F: FnMut(usize) -> bool,
629    {
630        let mut bit_vec = BitVec::from_elem_general(len, false);
631        for i in 0..len {
632            bit_vec.set(i, f(i));
633        }
634        bit_vec
635    }
636
637    /// Applies the given operation to the blocks of self and other, and sets
638    /// self to be the result. This relies on the caller not to corrupt the
639    /// last word.
640    #[inline]
641    fn process<F>(&mut self, that: &BitVec<B>, mut op: F, tail: bool) -> bool
642    where
643        F: FnMut(B, B) -> B,
644    {
645        assert_eq!(self.len(), that.len());
646        debug_assert_eq!(self.storage.len(), that.storage.len());
647        let mut changed_bits = B::zero();
648        let extra_bits = self.nbits % B::bits();
649        let desired_tail_len = if tail && extra_bits != 0 { 1 } else { 0 };
650        let full_blocks = self.storage.len().saturating_sub(desired_tail_len);
651        let (a_head, a_tail) = self.storage.split_at_mut(full_blocks);
652        let (b_head, b_tail) = that.storage.split_at(full_blocks);
653        for (a, b) in a_head.iter_mut().zip(b_head.iter()) {
654            let w = op(*a, *b);
655            changed_bits |= *a ^ w;
656            *a = w;
657        }
658        if a_tail.len() == 1 {
659            let mask = (B::one() << extra_bits) - B::one();
660            let w = op(a_tail[0], b_tail[0]) & mask;
661            changed_bits |= a_tail[0] ^ w;
662            a_tail[0] = w;
663        }
664        changed_bits != B::zero()
665    }
666
667    /// Iterator over the underlying blocks of data
668    #[inline]
669    pub fn blocks(&self) -> Blocks<'_, B> {
670        // (2)
671        Blocks {
672            iter: self.storage.iter(),
673        }
674    }
675
676    /// Exposes the raw block storage of this `BitVec`.
677    ///
678    /// Only really intended for `BitSet`.
679    #[inline]
680    pub fn storage(&self) -> &[B] {
681        &self.storage
682    }
683
684    /// Exposes the raw block storage of this `BitVec`.
685    ///
686    /// # Safety
687    ///
688    /// Can break the structure's invariants despite not
689    /// giving real memory unsafety. Only really intended for `BitSet`.
690    #[inline]
691    pub unsafe fn storage_mut(&mut self) -> &mut Vec<B> {
692        &mut self.storage
693    }
694
695    /// Helper for procedures involving spare space in the last block.
696    #[inline]
697    fn last_block_with_mask(&self) -> Option<(B, B)> {
698        let extra_bits = self.len() % B::bits();
699        if extra_bits > 0 {
700            let mask = (B::one() << extra_bits) - B::one();
701            let storage_len = self.storage.len();
702            Some((self.storage[storage_len - 1], mask))
703        } else {
704            None
705        }
706    }
707
708    /// Helper for procedures involving spare space in the last block.
709    #[inline]
710    fn last_block_mut_with_mask(&mut self) -> Option<(&mut B, B)> {
711        let extra_bits = self.len() % B::bits();
712        if extra_bits > 0 {
713            let mask = (B::one() << extra_bits) - B::one();
714            let storage_len = self.storage.len();
715            Some((&mut self.storage[storage_len - 1], mask))
716        } else {
717            None
718        }
719    }
720
721    /// An operation might screw up the unused bits in the last block of the
722    /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up.
723    fn fix_last_block(&mut self) {
724        if let Some((last_block, used_bits)) = self.last_block_mut_with_mask() {
725            *last_block = *last_block & used_bits;
726        }
727    }
728
729    /// Check whether last block's invariant is fine.
730    fn is_last_block_fixed(&self) -> bool {
731        if let Some((last_block, used_bits)) = self.last_block_with_mask() {
732            last_block & !used_bits == B::zero()
733        } else {
734            true
735        }
736    }
737
738    /// Checks whether our `nbits` fits within our storage.
739    fn storage_len_matches_nbits(&self) -> bool {
740        self.storage.len() == blocks_for_bits::<B>(self.nbits)
741    }
742
743    /// Ensure the invariant for the last block.
744    ///
745    /// An operation might screw up the unused bits in the last block of the
746    /// `BitVec`.
747    ///
748    /// This method fails in case the last block is not fixed. The check
749    /// is skipped outside testing.
750    #[inline]
751    fn ensure_invariant(&self) {
752        if cfg!(test) {
753            debug_assert!(self.storage_len_matches_nbits());
754            debug_assert!(self.is_last_block_fixed());
755        }
756    }
757
758    /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
759    ///
760    /// # Examples
761    ///
762    /// ```
763    /// use bit_vec::BitVec;
764    ///
765    /// let bv = BitVec::from_bytes(&[0b01100000]);
766    /// assert_eq!(bv.get(0), Some(false));
767    /// assert_eq!(bv.get(1), Some(true));
768    /// assert_eq!(bv.get(100), None);
769    ///
770    /// // Can also use array indexing
771    /// assert_eq!(bv[1], true);
772    /// ```
773    #[inline]
774    pub fn get(&self, i: usize) -> Option<bool> {
775        self.ensure_invariant();
776        if i >= self.nbits {
777            return None;
778        }
779        let w = i / B::bits();
780        let b = i % B::bits();
781        self.storage
782            .get(w)
783            .map(|&block| (block & (B::one() << b)) != B::zero())
784    }
785
786    /// Retrieves the value at index `i`, without doing bounds checking.
787    ///
788    /// For a safe alternative, see `get`.
789    ///
790    /// # Safety
791    ///
792    /// Calling this method with an out-of-bounds index is undefined behavior
793    /// even if the resulting reference is not used.
794    ///
795    /// # Examples
796    ///
797    /// ```
798    /// use bit_vec::BitVec;
799    ///
800    /// let bv = BitVec::from_bytes(&[0b01100000]);
801    /// // Safety:
802    /// // We access the structure with in-bounds indices (those smaller
803    /// // than 32).
804    /// unsafe {
805    ///     assert_eq!(bv.get_unchecked(0), false);
806    ///     assert_eq!(bv.get_unchecked(1), true);
807    /// }
808    /// ```
809    #[inline]
810    pub unsafe fn get_unchecked(&self, i: usize) -> bool {
811        self.ensure_invariant();
812        let w = i / B::bits();
813        let b = i % B::bits();
814        let block = *self.storage.get_unchecked(w);
815        block & (B::one() << b) != B::zero()
816    }
817
818    /// Retrieves a smart pointer to the value at index `i`, or `None` if the index is out of bounds.
819    ///
820    /// # Examples
821    ///
822    /// ```
823    /// use bit_vec::BitVec;
824    ///
825    /// let mut bv = BitVec::from_bytes(&[0b01100000]);
826    /// *bv.get_mut(0).unwrap() = true;
827    /// *bv.get_mut(1).unwrap() = false;
828    /// assert!(bv.get_mut(100).is_none());
829    /// assert_eq!(bv, BitVec::from_bytes(&[0b10100000]));
830    /// ```
831    #[inline]
832    pub fn get_mut(&mut self, index: usize) -> Option<MutBorrowedBit<'_, B>> {
833        self.get(index).map(move |value| MutBorrowedBit {
834            vec: Rc::new(RefCell::new(self)),
835            index,
836            #[cfg(debug_assertions)]
837            old_value: value,
838            new_value: value,
839        })
840    }
841
842    /// Retrieves a smart pointer to the value at index `i`, without doing bounds checking.
843    ///
844    /// # Safety
845    ///
846    /// Calling this method with out-of-bounds `index` may cause undefined behavior even when
847    /// the result is not used.
848    ///
849    /// # Examples
850    ///
851    /// ```
852    /// use bit_vec::BitVec;
853    ///
854    /// let mut bv = BitVec::from_bytes(&[0b01100000]);
855    /// unsafe {
856    ///     *bv.get_unchecked_mut(0) = true;
857    ///     *bv.get_unchecked_mut(1) = false;
858    /// }
859    /// assert_eq!(bv, BitVec::from_bytes(&[0b10100000]));
860    /// ```
861    #[inline]
862    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> MutBorrowedBit<'_, B> {
863        let value = self.get_unchecked(index);
864        MutBorrowedBit {
865            #[cfg(debug_assertions)]
866            old_value: value,
867            new_value: value,
868            vec: Rc::new(RefCell::new(self)),
869            index,
870        }
871    }
872
873    /// Sets the value of a bit at an index `i`.
874    ///
875    /// # Panics
876    ///
877    /// Panics if `i` is out of bounds.
878    ///
879    /// # Examples
880    ///
881    /// ```
882    /// use bit_vec::BitVec;
883    ///
884    /// let mut bv = BitVec::from_elem(5, false);
885    /// bv.set(3, true);
886    /// assert_eq!(bv[3], true);
887    /// ```
888    #[inline]
889    pub fn set(&mut self, i: usize, x: bool) {
890        self.ensure_invariant();
891        assert!(
892            i < self.nbits,
893            "index out of bounds: {:?} >= {:?}",
894            i,
895            self.nbits
896        );
897        let w = i / B::bits();
898        let b = i % B::bits();
899        let flag = B::one() << b;
900        let val = if x {
901            self.storage[w] | flag
902        } else {
903            self.storage[w] & !flag
904        };
905        self.storage[w] = val;
906    }
907
908    /// Sets all bits to 1.
909    ///
910    /// # Examples
911    ///
912    /// ```
913    /// use bit_vec::BitVec;
914    ///
915    /// let before = 0b01100000;
916    /// let after  = 0b11111111;
917    ///
918    /// let mut bv = BitVec::from_bytes(&[before]);
919    /// bv.set_all();
920    /// assert_eq!(bv, BitVec::from_bytes(&[after]));
921    /// ```
922    #[inline]
923    #[deprecated(since = "0.9.0", note = "please use `.fill(true)` instead")]
924    pub fn set_all(&mut self) {
925        self.ensure_invariant();
926        for w in &mut self.storage {
927            *w = !B::zero();
928        }
929        self.fix_last_block();
930    }
931
932    /// Flips all bits.
933    ///
934    /// # Examples
935    ///
936    /// ```
937    /// use bit_vec::BitVec;
938    ///
939    /// let before = 0b01100000;
940    /// let after  = 0b10011111;
941    ///
942    /// let mut bv = BitVec::from_bytes(&[before]);
943    /// bv.negate();
944    /// assert_eq!(bv, BitVec::from_bytes(&[after]));
945    /// ```
946    #[inline]
947    pub fn negate(&mut self) {
948        self.ensure_invariant();
949        for w in &mut self.storage {
950            *w = !*w;
951        }
952        self.fix_last_block();
953    }
954
955    /// Calculates the union of two bitvectors. This acts like the bitwise `or`
956    /// function.
957    ///
958    /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
959    /// the same length. Returns `true` if `self` changed.
960    ///
961    /// # Panics
962    ///
963    /// Panics if the bitvectors are of different lengths.
964    ///
965    /// # Examples
966    ///
967    /// ```
968    /// use bit_vec::BitVec;
969    ///
970    /// let a   = 0b01100100;
971    /// let b   = 0b01011010;
972    /// let res = 0b01111110;
973    ///
974    /// let mut a = BitVec::from_bytes(&[a]);
975    /// let b = BitVec::from_bytes(&[b]);
976    ///
977    /// assert!(a.union(&b));
978    /// assert_eq!(a, BitVec::from_bytes(&[res]));
979    /// ```
980    #[deprecated(since = "0.7.0", note = "Please use the 'or' function instead")]
981    #[inline]
982    pub fn union(&mut self, other: &Self) -> bool {
983        self.or(other)
984    }
985
986    /// Calculates the intersection of two bitvectors. This acts like the
987    /// bitwise `and` function.
988    ///
989    /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
990    /// must be the same length. Returns `true` if `self` changed.
991    ///
992    /// # Panics
993    ///
994    /// Panics if the bitvectors are of different lengths.
995    ///
996    /// # Examples
997    ///
998    /// ```
999    /// use bit_vec::BitVec;
1000    ///
1001    /// let a   = 0b01100100;
1002    /// let b   = 0b01011010;
1003    /// let res = 0b01000000;
1004    ///
1005    /// let mut a = BitVec::from_bytes(&[a]);
1006    /// let b = BitVec::from_bytes(&[b]);
1007    ///
1008    /// assert!(a.intersect(&b));
1009    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1010    /// ```
1011    #[deprecated(since = "0.7.0", note = "Please use the 'and' function instead")]
1012    #[inline]
1013    pub fn intersect(&mut self, other: &Self) -> bool {
1014        self.and(other)
1015    }
1016
1017    /// Calculates the bitwise `or` of two bitvectors.
1018    ///
1019    /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
1020    /// the same length. Returns `true` if `self` changed.
1021    ///
1022    /// # Panics
1023    ///
1024    /// Panics if the bitvectors are of different lengths.
1025    ///
1026    /// # Examples
1027    ///
1028    /// ```
1029    /// use bit_vec::BitVec;
1030    ///
1031    /// let a   = 0b01100100;
1032    /// let b   = 0b01011010;
1033    /// let res = 0b01111110;
1034    ///
1035    /// let mut a = BitVec::from_bytes(&[a]);
1036    /// let b = BitVec::from_bytes(&[b]);
1037    ///
1038    /// assert!(a.or(&b));
1039    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1040    /// ```
1041    #[inline]
1042    pub fn or(&mut self, other: &Self) -> bool {
1043        self.ensure_invariant();
1044        debug_assert!(other.is_last_block_fixed());
1045        let result = self.process(other, |w1, w2| w1 | w2, false);
1046        debug_assert!(self.is_last_block_fixed());
1047        result
1048    }
1049
1050    /// Calculates the bitwise `and` of two bitvectors.
1051    ///
1052    /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
1053    /// must be the same length. Returns `true` if `self` changed.
1054    ///
1055    /// # Panics
1056    ///
1057    /// Panics if the bitvectors are of different lengths.
1058    ///
1059    /// # Examples
1060    ///
1061    /// ```
1062    /// use bit_vec::BitVec;
1063    ///
1064    /// let a   = 0b01100100;
1065    /// let b   = 0b01011010;
1066    /// let res = 0b01000000;
1067    ///
1068    /// let mut a = BitVec::from_bytes(&[a]);
1069    /// let b = BitVec::from_bytes(&[b]);
1070    ///
1071    /// assert!(a.and(&b));
1072    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1073    /// ```
1074    #[inline]
1075    pub fn and(&mut self, other: &Self) -> bool {
1076        self.ensure_invariant();
1077        debug_assert!(other.is_last_block_fixed());
1078        self.process(other, |w1, w2| w1 & w2, false)
1079    }
1080
1081    /// Calculates the difference between two bitvectors.
1082    ///
1083    /// Sets each element of `self` to the value of that element minus the
1084    /// element of `other` at the same index. Both bitvectors must be the same
1085    /// length. Returns `true` if `self` changed.
1086    ///
1087    /// # Panics
1088    ///
1089    /// Panics if the bitvectors are of different length.
1090    ///
1091    /// # Examples
1092    ///
1093    /// ```
1094    /// use bit_vec::BitVec;
1095    ///
1096    /// let a   = 0b01100100;
1097    /// let b   = 0b01011010;
1098    /// let a_b = 0b00100100; // a - b
1099    /// let b_a = 0b00011010; // b - a
1100    ///
1101    /// let mut bva = BitVec::from_bytes(&[a]);
1102    /// let bvb = BitVec::from_bytes(&[b]);
1103    ///
1104    /// assert!(bva.difference(&bvb));
1105    /// assert_eq!(bva, BitVec::from_bytes(&[a_b]));
1106    ///
1107    /// let bva = BitVec::from_bytes(&[a]);
1108    /// let mut bvb = BitVec::from_bytes(&[b]);
1109    ///
1110    /// assert!(bvb.difference(&bva));
1111    /// assert_eq!(bvb, BitVec::from_bytes(&[b_a]));
1112    /// ```
1113    #[inline]
1114    pub fn difference(&mut self, other: &Self) -> bool {
1115        self.ensure_invariant();
1116        debug_assert!(other.is_last_block_fixed());
1117        self.process(other, |w1, w2| w1 & !w2, false)
1118    }
1119
1120    /// Calculates the xor of two bitvectors.
1121    ///
1122    /// Sets `self` to the xor of `self` and `other`. Both bitvectors must be
1123    /// the same length. Returns `true` if `self` changed.
1124    ///
1125    /// # Panics
1126    ///
1127    /// Panics if the bitvectors are of different length.
1128    ///
1129    /// # Examples
1130    ///
1131    /// ```
1132    /// use bit_vec::BitVec;
1133    ///
1134    /// let a   = 0b01100110;
1135    /// let b   = 0b01010100;
1136    /// let res = 0b00110010;
1137    ///
1138    /// let mut a = BitVec::from_bytes(&[a]);
1139    /// let b = BitVec::from_bytes(&[b]);
1140    ///
1141    /// assert!(a.xor(&b));
1142    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1143    /// ```
1144    #[inline]
1145    pub fn xor(&mut self, other: &Self) -> bool {
1146        self.ensure_invariant();
1147        debug_assert!(other.is_last_block_fixed());
1148        let result = self.process(other, |w1, w2| w1 ^ w2, false);
1149        debug_assert!(self.is_last_block_fixed());
1150        result
1151    }
1152
1153    /// Calculates the nand of two bitvectors.
1154    ///
1155    /// Sets `self` to the nand of `self` and `other`. Both bitvectors must be
1156    /// the same length. Returns `true` if `self` changed.
1157    ///
1158    /// # Panics
1159    ///
1160    /// Panics if the bitvectors are of different length.
1161    ///
1162    /// # Examples
1163    ///
1164    /// ```
1165    /// use bit_vec::BitVec;
1166    ///
1167    /// let a   = 0b01100110;
1168    /// let b   = 0b01010100;
1169    /// let res = 0b10111011;
1170    ///
1171    /// let mut a = BitVec::from_bytes(&[a]);
1172    /// let b = BitVec::from_bytes(&[b]);
1173    ///
1174    /// assert!(a.nand(&b));
1175    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1176    /// ```
1177    #[inline]
1178    pub fn nand(&mut self, other: &Self) -> bool {
1179        self.ensure_invariant();
1180        debug_assert!(other.is_last_block_fixed());
1181        let result = self.process(other, |w1, w2| !(w1 & w2), true);
1182        debug_assert!(self.is_last_block_fixed());
1183        result
1184    }
1185
1186    /// Calculates the nor of two bitvectors.
1187    ///
1188    /// Sets `self` to the nor of `self` and `other`. Both bitvectors must be
1189    /// the same length. Returns `true` if `self` changed.
1190    ///
1191    /// # Panics
1192    ///
1193    /// Panics if the bitvectors are of different length.
1194    ///
1195    /// # Examples
1196    ///
1197    /// ```
1198    /// use bit_vec::BitVec;
1199    ///
1200    /// let a   = 0b01100110;
1201    /// let b   = 0b01010100;
1202    /// let res = 0b10001001;
1203    ///
1204    /// let mut a = BitVec::from_bytes(&[a]);
1205    /// let b = BitVec::from_bytes(&[b]);
1206    ///
1207    /// assert!(a.nor(&b));
1208    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1209    /// ```
1210    #[inline]
1211    pub fn nor(&mut self, other: &Self) -> bool {
1212        self.ensure_invariant();
1213        debug_assert!(other.is_last_block_fixed());
1214        let result = self.process(other, |w1, w2| !(w1 | w2), true);
1215        debug_assert!(self.is_last_block_fixed());
1216        result
1217    }
1218
1219    /// Calculates the xnor of two bitvectors.
1220    ///
1221    /// Sets `self` to the xnor of `self` and `other`. Both bitvectors must be
1222    /// the same length. Returns `true` if `self` changed.
1223    ///
1224    /// # Panics
1225    ///
1226    /// Panics if the bitvectors are of different length.
1227    ///
1228    /// # Examples
1229    ///
1230    /// ```
1231    /// use bit_vec::BitVec;
1232    ///
1233    /// let a   = 0b01100110;
1234    /// let b   = 0b01010100;
1235    /// let res = 0b11001101;
1236    ///
1237    /// let mut a = BitVec::from_bytes(&[a]);
1238    /// let b = BitVec::from_bytes(&[b]);
1239    ///
1240    /// assert!(a.xnor(&b));
1241    /// assert_eq!(a, BitVec::from_bytes(&[res]));
1242    /// ```
1243    #[inline]
1244    pub fn xnor(&mut self, other: &Self) -> bool {
1245        self.ensure_invariant();
1246        debug_assert!(other.is_last_block_fixed());
1247        let result = self.process(other, |w1, w2| !(w1 ^ w2), true);
1248        debug_assert!(self.is_last_block_fixed());
1249        result
1250    }
1251
1252    /// Returns `true` if all bits are 1.
1253    ///
1254    /// # Examples
1255    ///
1256    /// ```
1257    /// use bit_vec::BitVec;
1258    ///
1259    /// let mut bv = BitVec::from_elem(5, true);
1260    /// assert_eq!(bv.all(), true);
1261    ///
1262    /// bv.set(1, false);
1263    /// assert_eq!(bv.all(), false);
1264    /// ```
1265    #[inline]
1266    pub fn all(&self) -> bool {
1267        self.ensure_invariant();
1268        let mut last_word = !B::zero();
1269        // Check that every block but the last is all-ones...
1270        self.blocks().all(|elem| {
1271            let tmp = last_word;
1272            last_word = elem;
1273            tmp == !B::zero()
1274            // and then check the last one has enough ones
1275        }) && (last_word == mask_for_bits(self.nbits))
1276    }
1277
1278    /// Returns the number of ones in the binary representation.
1279    ///
1280    /// Also known as the
1281    /// [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight).
1282    ///
1283    /// # Examples
1284    ///
1285    /// ```
1286    /// use bit_vec::BitVec;
1287    ///
1288    /// let mut bv = BitVec::from_elem(100, true);
1289    /// assert_eq!(bv.count_ones(), 100);
1290    ///
1291    /// bv.set(50, false);
1292    /// assert_eq!(bv.count_ones(), 99);
1293    /// ```
1294    #[inline]
1295    pub fn count_ones(&self) -> u64 {
1296        self.ensure_invariant();
1297        // Add the number of ones of each block.
1298        self.blocks().map(|elem| elem.count_ones() as u64).sum()
1299    }
1300
1301    /// Returns the number of zeros in the binary representation.
1302    ///
1303    /// Also known as the opposite of
1304    /// [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight).
1305    ///
1306    /// # Examples
1307    ///
1308    /// ```
1309    /// use bit_vec::BitVec;
1310    ///
1311    /// let mut bv = BitVec::from_elem(100, false);
1312    /// assert_eq!(bv.count_zeros(), 100);
1313    ///
1314    /// bv.set(50, true);
1315    /// assert_eq!(bv.count_zeros(), 99);
1316    /// ```
1317    #[inline]
1318    pub fn count_zeros(&self) -> u64 {
1319        self.ensure_invariant();
1320        // Add the number of zeros of each block.
1321        let extra_zeros = (B::bits() - (self.len() % B::bits())) % B::bits();
1322        self.blocks()
1323            .map(|elem| elem.count_zeros() as u64)
1324            .sum::<u64>()
1325            - extra_zeros as u64
1326    }
1327
1328    /// Returns an iterator over the elements of the vector in order.
1329    ///
1330    /// # Examples
1331    ///
1332    /// ```
1333    /// use bit_vec::BitVec;
1334    ///
1335    /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]);
1336    /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
1337    /// ```
1338    #[inline]
1339    pub fn iter(&self) -> Iter<'_, B> {
1340        self.ensure_invariant();
1341        Iter {
1342            bit_vec: self,
1343            range: 0..self.nbits,
1344        }
1345    }
1346
1347    /// Returns an iterator over mutable smart pointers to the elements of the vector in order.
1348    ///
1349    /// # Examples
1350    ///
1351    /// ```
1352    /// use bit_vec::BitVec;
1353    ///
1354    /// let mut a = BitVec::from_elem(8, false);
1355    /// a.iter_mut().enumerate().for_each(|(index, mut bit)| {
1356    ///     *bit = if index % 2 == 1 { true } else { false };
1357    /// });
1358    /// assert!(a.eq_vec(&[
1359    ///    false, true, false, true, false, true, false, true
1360    /// ]));
1361    /// ```
1362    #[inline]
1363    pub fn iter_mut(&mut self) -> IterMut<'_, B> {
1364        self.ensure_invariant();
1365        let nbits = self.nbits;
1366        IterMut {
1367            vec: Rc::new(RefCell::new(self)),
1368            range: 0..nbits,
1369        }
1370    }
1371
1372    /// Moves all bits from `other` into `Self`, leaving `other` empty.
1373    ///
1374    /// # Examples
1375    ///
1376    /// ```
1377    /// use bit_vec::BitVec;
1378    ///
1379    /// let mut a = BitVec::from_bytes(&[0b10000000]);
1380    /// let mut b = BitVec::from_bytes(&[0b01100001]);
1381    ///
1382    /// a.append(&mut b);
1383    ///
1384    /// assert_eq!(a.len(), 16);
1385    /// assert_eq!(b.len(), 0);
1386    /// assert!(a.eq_vec(&[true, false, false, false, false, false, false, false,
1387    ///                    false, true, true, false, false, false, false, true]));
1388    /// ```
1389    pub fn append(&mut self, other: &mut Self) {
1390        self.ensure_invariant();
1391        debug_assert!(other.is_last_block_fixed());
1392
1393        let b = self.len() % B::bits();
1394        let o = other.len() % B::bits();
1395        let will_overflow = (b + o > B::bits()) || (o == 0 && b != 0);
1396
1397        self.nbits += other.len();
1398        other.nbits = 0;
1399
1400        if b == 0 {
1401            self.storage.append(&mut other.storage);
1402        } else {
1403            self.storage.reserve(other.storage.len());
1404
1405            for block in other.storage.drain(..) {
1406                {
1407                    let last = self.storage.last_mut().unwrap();
1408                    *last |= block << b;
1409                }
1410                self.storage.push(block >> (B::bits() - b));
1411            }
1412
1413            // Remove additional block if the last shift did not overflow
1414            if !will_overflow {
1415                self.storage.pop();
1416            }
1417        }
1418    }
1419
1420    /// Splits the `BitVec` into two at the given bit,
1421    /// retaining the first half in-place and returning the second one.
1422    ///
1423    /// # Panics
1424    ///
1425    /// Panics if `at` is out of bounds.
1426    ///
1427    /// # Examples
1428    ///
1429    /// ```
1430    /// use bit_vec::BitVec;
1431    /// let mut a = BitVec::new();
1432    /// a.push(true);
1433    /// a.push(false);
1434    /// a.push(false);
1435    /// a.push(true);
1436    ///
1437    /// let b = a.split_off(2);
1438    ///
1439    /// assert_eq!(a.len(), 2);
1440    /// assert_eq!(b.len(), 2);
1441    /// assert!(a.eq_vec(&[true, false]));
1442    /// assert!(b.eq_vec(&[false, true]));
1443    /// ```
1444    pub fn split_off(&mut self, at: usize) -> Self {
1445        self.ensure_invariant();
1446        assert!(at <= self.len(), "`at` out of bounds");
1447
1448        let mut other = BitVec::<B>::default();
1449
1450        if at == 0 {
1451            mem::swap(self, &mut other);
1452            return other;
1453        } else if at == self.len() {
1454            return other;
1455        }
1456
1457        let w = at / B::bits();
1458        let b = at % B::bits();
1459        other.nbits = self.nbits - at;
1460        self.nbits = at;
1461        if b == 0 {
1462            // Split at block boundary
1463            other.storage = self.storage.split_off(w);
1464        } else {
1465            let original_storage_len = self.storage.len();
1466            other.storage.reserve(original_storage_len - w);
1467
1468            {
1469                let mut iter = self.storage[w..].iter();
1470                let mut last = *iter.next().unwrap();
1471                for &cur in iter {
1472                    other.storage.push((last >> b) | (cur << (B::bits() - b)));
1473                    last = cur;
1474                }
1475                // An unaligned read can span one more block than the result needs.
1476                if original_storage_len - w <= blocks_for_bits::<B>(other.nbits) {
1477                    other.storage.push(last >> b);
1478                }
1479            }
1480
1481            self.storage.truncate(w + 1);
1482            self.fix_last_block();
1483        }
1484
1485        other
1486    }
1487
1488    /// Returns `true` if all bits are 0.
1489    ///
1490    /// # Examples
1491    ///
1492    /// ```
1493    /// use bit_vec::BitVec;
1494    ///
1495    /// let mut bv = BitVec::from_elem(10, false);
1496    /// assert_eq!(bv.none(), true);
1497    ///
1498    /// bv.set(3, true);
1499    /// assert_eq!(bv.none(), false);
1500    /// ```
1501    #[inline]
1502    pub fn none(&self) -> bool {
1503        self.blocks().all(|w| w == B::zero())
1504    }
1505
1506    /// Returns `true` if any bit is 1.
1507    ///
1508    /// # Examples
1509    ///
1510    /// ```
1511    /// use bit_vec::BitVec;
1512    ///
1513    /// let mut bv = BitVec::from_elem(10, false);
1514    /// assert_eq!(bv.any(), false);
1515    ///
1516    /// bv.set(3, true);
1517    /// assert_eq!(bv.any(), true);
1518    /// ```
1519    #[inline]
1520    pub fn any(&self) -> bool {
1521        !self.none()
1522    }
1523
1524    /// Organises the bits into bytes, such that the first bit in the
1525    /// `BitVec` becomes the high-order bit of the first byte. If the
1526    /// size of the `BitVec` is not a multiple of eight then trailing bits
1527    /// will be filled-in with `false`.
1528    ///
1529    /// # Examples
1530    ///
1531    /// ```
1532    /// use bit_vec::BitVec;
1533    ///
1534    /// let mut bv = BitVec::from_elem(3, true);
1535    /// bv.set(1, false);
1536    ///
1537    /// assert_eq!(bv.to_bytes(), [0b10100000]);
1538    ///
1539    /// let mut bv = BitVec::from_elem(9, false);
1540    /// bv.set(2, true);
1541    /// bv.set(8, true);
1542    ///
1543    /// assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
1544    /// ```
1545    pub fn to_bytes(&self) -> Vec<u8> {
1546        self.ensure_invariant();
1547
1548        let len = self.nbits / 8 + if self.nbits % 8 == 0 { 0 } else { 1 };
1549        let mut result = Vec::with_capacity(len);
1550
1551        for byte_idx in 0..len {
1552            let mut byte = 0u8;
1553            for bit_idx in 0..8 {
1554                let offset = byte_idx * 8 + bit_idx;
1555                if offset < self.nbits && self[offset] {
1556                    byte |= 1 << bit_idx;
1557                }
1558            }
1559            result.push(util::reverse_bits(byte));
1560        }
1561
1562        result
1563    }
1564
1565    /// Compares a `BitVec` to a slice of `bool`s.
1566    /// Both the `BitVec` and slice must have the same length.
1567    ///
1568    /// # Panics
1569    ///
1570    /// Panics if the `BitVec` and slice are of different length.
1571    ///
1572    /// # Examples
1573    ///
1574    /// ```
1575    /// use bit_vec::BitVec;
1576    ///
1577    /// let bv = BitVec::from_bytes(&[0b10100000]);
1578    ///
1579    /// assert!(bv.eq_vec(&[true, false, true, false,
1580    ///                     false, false, false, false]));
1581    /// ```
1582    #[inline]
1583    pub fn eq_vec(&self, v: &[bool]) -> bool {
1584        assert_eq!(self.nbits, v.len());
1585        self.iter().zip(v.iter().cloned()).all(|(b1, b2)| b1 == b2)
1586    }
1587
1588    /// Shortens a `BitVec`, dropping excess elements.
1589    ///
1590    /// If `len` is greater than the vector's current length, this has no
1591    /// effect.
1592    ///
1593    /// # Examples
1594    ///
1595    /// ```
1596    /// use bit_vec::BitVec;
1597    ///
1598    /// let mut bv = BitVec::from_bytes(&[0b01001011]);
1599    /// bv.truncate(2);
1600    /// assert!(bv.eq_vec(&[false, true]));
1601    /// ```
1602    #[inline]
1603    pub fn truncate(&mut self, len: usize) {
1604        self.ensure_invariant();
1605        if len < self.len() {
1606            self.nbits = len;
1607            // This fixes (2).
1608            self.storage.truncate(blocks_for_bits::<B>(len));
1609            self.fix_last_block();
1610        }
1611    }
1612
1613    /// Reserves capacity for at least `additional` more bits to be inserted in the given
1614    /// `BitVec`. The collection may reserve more space to avoid frequent reallocations.
1615    ///
1616    /// # Panics
1617    ///
1618    /// Panics if the new capacity overflows `usize`.
1619    ///
1620    /// # Examples
1621    ///
1622    /// ```
1623    /// use bit_vec::BitVec;
1624    ///
1625    /// let mut bv = BitVec::from_elem(3, false);
1626    /// bv.reserve(10);
1627    /// assert_eq!(bv.len(), 3);
1628    /// assert!(bv.capacity() >= 13);
1629    /// ```
1630    #[inline]
1631    pub fn reserve(&mut self, additional: usize) {
1632        let desired_cap = self
1633            .len()
1634            .checked_add(additional)
1635            .expect("capacity overflow");
1636        let storage_len = self.storage.len();
1637        if desired_cap > self.capacity() {
1638            self.storage
1639                .reserve(blocks_for_bits::<B>(desired_cap) - storage_len);
1640        }
1641    }
1642
1643    /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
1644    /// given `BitVec`. Does nothing if the capacity is already sufficient.
1645    ///
1646    /// Note that the allocator may give the collection more space than it requests. Therefore
1647    /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
1648    /// insertions are expected.
1649    ///
1650    /// # Panics
1651    ///
1652    /// Panics if the new capacity overflows `usize`.
1653    ///
1654    /// # Examples
1655    ///
1656    /// ```
1657    /// use bit_vec::BitVec;
1658    ///
1659    /// let mut bv = BitVec::from_elem(3, false);
1660    /// bv.reserve(10);
1661    /// assert_eq!(bv.len(), 3);
1662    /// assert!(bv.capacity() >= 13);
1663    /// ```
1664    #[inline]
1665    pub fn reserve_exact(&mut self, additional: usize) {
1666        let desired_cap = self
1667            .len()
1668            .checked_add(additional)
1669            .expect("capacity overflow");
1670        let storage_len = self.storage.len();
1671        if desired_cap > self.capacity() {
1672            self.storage
1673                .reserve_exact(blocks_for_bits::<B>(desired_cap) - storage_len);
1674        }
1675    }
1676
1677    /// Returns the capacity in bits for this bit vector. Inserting any
1678    /// element less than this amount will not trigger a resizing.
1679    ///
1680    /// # Examples
1681    ///
1682    /// ```
1683    /// use bit_vec::BitVec;
1684    ///
1685    /// let mut bv = BitVec::new();
1686    /// bv.reserve(10);
1687    /// assert!(bv.capacity() >= 10);
1688    /// ```
1689    #[inline]
1690    pub fn capacity(&self) -> usize {
1691        self.storage.capacity().saturating_mul(B::bits())
1692    }
1693
1694    /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`.
1695    ///
1696    /// # Panics
1697    ///
1698    /// Panics if the new len overflows a `usize`.
1699    ///
1700    /// # Examples
1701    ///
1702    /// ```
1703    /// use bit_vec::BitVec;
1704    ///
1705    /// let mut bv = BitVec::from_bytes(&[0b01001011]);
1706    /// bv.grow(2, true);
1707    /// assert_eq!(bv.len(), 10);
1708    /// assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]);
1709    /// ```
1710    pub fn grow(&mut self, n: usize, value: bool) {
1711        self.ensure_invariant();
1712
1713        // Note: we just bulk set all the bits in the last word in this fn in multiple places
1714        // which is technically wrong if not all of these bits are to be used. However, at the end
1715        // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
1716
1717        let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
1718        let new_nblocks = blocks_for_bits::<B>(new_nbits);
1719        let full_value = if value { !B::zero() } else { B::zero() };
1720
1721        // Correct the old tail word, setting or clearing formerly unused bits
1722        let num_cur_blocks = blocks_for_bits::<B>(self.nbits);
1723        if self.nbits % B::bits() > 0 {
1724            let mask = mask_for_bits::<B>(self.nbits);
1725            if value {
1726                let block = &mut self.storage[num_cur_blocks - 1];
1727                *block |= !mask;
1728            } else {
1729                // Extra bits are already zero by invariant.
1730            }
1731        }
1732
1733        // Fill in words after the old tail word
1734        let stop_idx = cmp::min(self.storage.len(), new_nblocks);
1735        for idx in num_cur_blocks..stop_idx {
1736            self.storage[idx] = full_value;
1737        }
1738
1739        // Allocate new words, if needed
1740        if new_nblocks > self.storage.len() {
1741            let to_add = new_nblocks - self.storage.len();
1742            self.storage.extend(iter::repeat_n(full_value, to_add));
1743        }
1744
1745        // Adjust internal bit count
1746        self.nbits = new_nbits;
1747
1748        self.fix_last_block();
1749    }
1750
1751    /// Removes the last bit from the `BitVec`, and returns it. Returns `None` if the `BitVec` is empty.
1752    ///
1753    /// # Examples
1754    ///
1755    /// ```
1756    /// use bit_vec::BitVec;
1757    ///
1758    /// let mut bv = BitVec::from_bytes(&[0b01001001]);
1759    /// assert_eq!(bv.pop(), Some(true));
1760    /// assert_eq!(bv.pop(), Some(false));
1761    /// assert_eq!(bv.len(), 6);
1762    /// ```
1763    #[inline]
1764    pub fn pop(&mut self) -> Option<bool> {
1765        self.ensure_invariant();
1766
1767        if self.is_empty() {
1768            None
1769        } else {
1770            let i = self.nbits - 1;
1771            let ret = self[i];
1772            // (3)
1773            self.set(i, false);
1774            self.nbits = i;
1775            if self.nbits % B::bits() == 0 {
1776                // (2)
1777                self.storage.pop();
1778            }
1779            Some(ret)
1780        }
1781    }
1782
1783    /// Pushes a `bool` onto the end.
1784    ///
1785    /// # Examples
1786    ///
1787    /// ```
1788    /// use bit_vec::BitVec;
1789    ///
1790    /// let mut bv = BitVec::new();
1791    /// bv.push(true);
1792    /// bv.push(false);
1793    /// assert!(bv.eq_vec(&[true, false]));
1794    /// ```
1795    #[inline]
1796    pub fn push(&mut self, elem: bool) {
1797        if self.nbits % B::bits() == 0 {
1798            self.storage.push(B::zero());
1799        }
1800        let insert_pos = self.nbits;
1801        self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
1802        self.set(insert_pos, elem);
1803    }
1804
1805    /// Returns the total number of bits in this vector
1806    #[inline]
1807    pub fn len(&self) -> usize {
1808        self.nbits
1809    }
1810
1811    /// Sets the number of bits that this `BitVec` considers initialized.
1812    ///
1813    /// # Safety
1814    ///
1815    /// Almost certainly can cause bad stuff. Only really intended for `BitSet`.
1816    #[inline]
1817    pub unsafe fn set_len(&mut self, len: usize) {
1818        self.nbits = len;
1819    }
1820
1821    /// Returns true if there are no bits in this vector
1822    #[inline]
1823    pub fn is_empty(&self) -> bool {
1824        self.len() == 0
1825    }
1826
1827    /// Clears all bits in this vector.
1828    #[inline]
1829    #[deprecated(since = "0.9.0", note = "please use `.fill(false)` instead")]
1830    pub fn clear(&mut self) {
1831        self.ensure_invariant();
1832        for w in &mut self.storage {
1833            *w = B::zero();
1834        }
1835    }
1836
1837    /// Assigns all bits in this vector to the given boolean value.
1838    ///
1839    /// # Invariants
1840    ///
1841    /// - After a call to `.fill(true)`, the result of [`all`] is `true`.
1842    /// - After a call to `.fill(false)`, the result of [`none`] is `true`.
1843    ///
1844    /// [`all`]: Self::all
1845    /// [`none`]: Self::none
1846    #[inline]
1847    pub fn fill(&mut self, bit: bool) {
1848        self.ensure_invariant();
1849        let block = if bit { !B::zero() } else { B::zero() };
1850        for w in &mut self.storage {
1851            *w = block;
1852        }
1853        if bit {
1854            self.fix_last_block();
1855        }
1856    }
1857
1858    /// Shrinks the capacity of the underlying storage as much as
1859    /// possible.
1860    ///
1861    /// It will drop down as close as possible to the length but the
1862    /// allocator may still inform the underlying storage that there
1863    /// is space for a few more elements/bits.
1864    pub fn shrink_to_fit(&mut self) {
1865        self.storage.shrink_to_fit();
1866    }
1867
1868    /// Inserts a given bit at index `at`, shifting all bits after by one
1869    ///
1870    /// # Panics
1871    /// Panics if `at` is out of bounds for `BitVec`'s length (that is, if `at > BitVec::len()`)
1872    ///
1873    /// # Examples
1874    ///```
1875    /// use bit_vec::BitVec;
1876    ///
1877    /// let mut b = BitVec::new();
1878    ///
1879    /// b.push(true);
1880    /// b.push(true);
1881    /// b.insert(1, false);
1882    ///
1883    /// assert!(b.eq_vec(&[true, false, true]));
1884    ///```
1885    ///
1886    /// # Time complexity
1887    /// Takes O([`len`]) time. All items after the insertion index must be
1888    /// shifted to the right. In the worst case, all elements are shifted when
1889    /// the insertion index is 0.
1890    ///
1891    /// [`len`]: Self::len
1892    pub fn insert(&mut self, at: usize, bit: bool) {
1893        assert!(
1894            at <= self.nbits,
1895            "insertion index (is {at}) should be <= len (is {nbits})",
1896            nbits = self.nbits
1897        );
1898        self.ensure_invariant();
1899
1900        let last_block_bits = self.nbits % B::bits();
1901        let block_at = at / B::bits(); // needed block
1902        let bit_at = at % B::bits(); // index within the block
1903
1904        if last_block_bits == 0 {
1905            self.storage.push(B::zero());
1906        }
1907
1908        self.nbits += 1;
1909
1910        let mut carry = self.storage[block_at] >> (B::bits() - 1);
1911        let lsbits_mask = (B::one() << bit_at) - B::one();
1912        let set_bit = if bit { B::one() } else { B::zero() } << bit_at;
1913        self.storage[block_at] = (self.storage[block_at] & lsbits_mask)
1914            | ((self.storage[block_at] & !lsbits_mask) << 1)
1915            | set_bit;
1916
1917        for block_ref in &mut self.storage[block_at + 1..] {
1918            let curr_carry = *block_ref >> (B::bits() - 1);
1919            *block_ref = *block_ref << 1 | carry;
1920            carry = curr_carry;
1921        }
1922    }
1923
1924    /// Remove a bit at index `at`, shifting all bits after by one.
1925    ///
1926    /// # Panics
1927    /// Panics if `at` is out of bounds for `BitVec`'s length (that is, if `at >= BitVec::len()`)
1928    ///
1929    /// # Examples
1930    ///```
1931    /// use bit_vec::BitVec;
1932    ///
1933    /// let mut b = BitVec::new();
1934    ///
1935    /// b.push(true);
1936    /// b.push(false);
1937    /// b.push(false);
1938    /// b.push(true);
1939    /// assert!(!b.remove(1));
1940    ///
1941    /// assert!(b.eq_vec(&[true, false, true]));
1942    ///```
1943    ///
1944    /// # Time complexity
1945    /// Takes O([`len`]) time. All items after the removal index must be
1946    /// shifted to the left. In the worst case, all elements are shifted when
1947    /// the removal index is 0.
1948    ///
1949    /// [`len`]: Self::len
1950    pub fn remove(&mut self, at: usize) -> bool {
1951        assert!(
1952            at < self.nbits,
1953            "removal index (is {at}) should be < len (is {nbits})",
1954            nbits = self.nbits
1955        );
1956        self.ensure_invariant();
1957
1958        self.nbits -= 1;
1959
1960        let last_block_bits = self.nbits % B::bits();
1961        let block_at = at / B::bits(); // needed block
1962        let bit_at = at % B::bits(); // index within the block
1963
1964        let lsbits_mask = (B::one() << bit_at) - B::one();
1965
1966        let mut carry = B::zero();
1967
1968        for block_ref in self.storage[block_at + 1..].iter_mut().rev() {
1969            let curr_carry = *block_ref & B::one();
1970            *block_ref = *block_ref >> 1 | (carry << (B::bits() - 1));
1971            carry = curr_carry;
1972        }
1973
1974        let result = (self.storage[block_at] >> bit_at) & B::one() == B::one();
1975
1976        self.storage[block_at] = (self.storage[block_at] & lsbits_mask)
1977            | ((self.storage[block_at] & (!lsbits_mask << 1)) >> 1)
1978            | carry << (B::bits() - 1);
1979
1980        if last_block_bits == 0 {
1981            self.storage.pop();
1982        }
1983
1984        result
1985    }
1986
1987    /// Removes all bits in this vector.
1988    ///
1989    /// Note: this method is not named [`clear`] to avoid confusion whenever [`.fill(false)`]
1990    /// is needed.
1991    ///
1992    /// [`clear`]: Self::clear
1993    /// [`.fill(false)`]: Self::fill
1994    pub fn remove_all(&mut self) {
1995        self.storage.clear();
1996        self.nbits = 0;
1997    }
1998
1999    /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
2000    /// with the element.
2001    ///
2002    /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
2003    /// The caller should use [`reserve`] to ensure that there is enough capacity.
2004    ///
2005    /// [`push`]: Self::push
2006    /// [`reserve`]: Self::reserve
2007    ///
2008    /// # Examples
2009    /// ```
2010    /// use bit_vec::BitVec;
2011    ///
2012    /// let initial_capacity = 64;
2013    /// let mut bitvec = BitVec::with_capacity(64);
2014    ///
2015    /// for _ in 0..initial_capacity - 1 {
2016    ///     bitvec.push(false);
2017    /// }
2018    ///
2019    /// assert_eq!(bitvec.len(), initial_capacity - 1); // there is space for only 1 bit
2020    ///
2021    /// assert_eq!(bitvec.push_within_capacity(true), Ok(())); // Successfully push a bit
2022    /// assert_eq!(bitvec.len(), initial_capacity); // So we can't push within capacity anymore
2023    ///
2024    /// assert_eq!(bitvec.push_within_capacity(true), Err(true));
2025    /// assert_eq!(bitvec.len(), initial_capacity);
2026    /// assert_eq!(bitvec.capacity(), initial_capacity);
2027    /// ```
2028    ///
2029    /// # Time Complexity
2030    /// Takes *O(1)* time.
2031    pub fn push_within_capacity(&mut self, bit: bool) -> Result<(), bool> {
2032        let len = self.len();
2033
2034        if len == self.capacity() {
2035            return Err(bit);
2036        }
2037
2038        let bits = B::bits();
2039
2040        if len % bits == 0 {
2041            self.storage.push(B::zero());
2042        }
2043
2044        let block_at = len / bits;
2045        let bit_at = len % bits;
2046        let flag = if bit { B::one() << bit_at } else { B::zero() };
2047
2048        self.nbits += 1;
2049
2050        self.storage[block_at] |= flag; // set the bit
2051
2052        self.ensure_invariant();
2053
2054        Ok(())
2055    }
2056}
2057
2058impl<B: BitBlock> Default for BitVec<B> {
2059    #[inline]
2060    fn default() -> Self {
2061        BitVec {
2062            storage: Vec::new(),
2063            nbits: 0,
2064        }
2065    }
2066}
2067
2068impl<B: BitBlock> FromIterator<bool> for BitVec<B> {
2069    #[inline]
2070    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
2071        let mut ret: Self = Default::default();
2072        ret.extend(iter);
2073        ret
2074    }
2075}
2076
2077impl<B: BitBlock> Extend<bool> for BitVec<B> {
2078    #[inline]
2079    fn extend<I: IntoIterator<Item = bool>>(&mut self, iterable: I) {
2080        self.ensure_invariant();
2081        let iterator = iterable.into_iter();
2082        let (min, _) = iterator.size_hint();
2083        self.reserve(min);
2084        for element in iterator {
2085            self.push(element)
2086        }
2087    }
2088}
2089
2090impl<B: BitBlock> Clone for BitVec<B> {
2091    #[inline]
2092    fn clone(&self) -> Self {
2093        self.ensure_invariant();
2094        BitVec {
2095            storage: self.storage.clone(),
2096            nbits: self.nbits,
2097        }
2098    }
2099
2100    #[inline]
2101    fn clone_from(&mut self, source: &Self) {
2102        debug_assert!(source.is_last_block_fixed());
2103        self.nbits = source.nbits;
2104        self.storage.clone_from(&source.storage);
2105    }
2106}
2107
2108impl<B: BitBlock> PartialOrd for BitVec<B> {
2109    #[inline]
2110    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2111        Some(self.cmp(other))
2112    }
2113}
2114
2115impl<B: BitBlock> Ord for BitVec<B> {
2116    #[inline]
2117    fn cmp(&self, other: &Self) -> Ordering {
2118        self.ensure_invariant();
2119        debug_assert!(other.is_last_block_fixed());
2120        let mut a = self.iter();
2121        let mut b = other.iter();
2122        loop {
2123            match (a.next(), b.next()) {
2124                (Some(x), Some(y)) => match x.cmp(&y) {
2125                    Ordering::Equal => {}
2126                    otherwise => return otherwise,
2127                },
2128                (None, None) => return Ordering::Equal,
2129                (None, _) => return Ordering::Less,
2130                (_, None) => return Ordering::Greater,
2131            }
2132        }
2133    }
2134}
2135
2136impl<B: BitBlock> fmt::Display for BitVec<B> {
2137    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
2138        self.ensure_invariant();
2139        for bit in self {
2140            fmt.write_char(if bit { '1' } else { '0' })?;
2141        }
2142        Ok(())
2143    }
2144}
2145
2146impl<B: BitBlock> fmt::Debug for BitVec<B> {
2147    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
2148        self.ensure_invariant();
2149        let mut storage = String::with_capacity(self.len() + self.len() / B::bits());
2150        for (i, bit) in self.iter().enumerate() {
2151            if i != 0 && i % B::bits() == 0 {
2152                storage.push(' ');
2153            }
2154            storage.push(if bit { '1' } else { '0' });
2155        }
2156        fmt.debug_struct("BitVec")
2157            .field("storage", &storage)
2158            .field("nbits", &self.nbits)
2159            .finish()
2160    }
2161}
2162
2163impl<B: BitBlock> hash::Hash for BitVec<B> {
2164    #[inline]
2165    fn hash<H: hash::Hasher>(&self, state: &mut H) {
2166        self.ensure_invariant();
2167        self.nbits.hash(state);
2168        for elem in self.blocks() {
2169            elem.hash(state);
2170        }
2171    }
2172}
2173
2174impl<B: BitBlock> cmp::PartialEq for BitVec<B> {
2175    #[inline]
2176    fn eq(&self, other: &Self) -> bool {
2177        if self.nbits != other.nbits {
2178            self.ensure_invariant();
2179            other.ensure_invariant();
2180            return false;
2181        }
2182        self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
2183    }
2184}
2185
2186impl<B: BitBlock> cmp::Eq for BitVec<B> {}
2187
2188/// An iterator for `BitVec`.
2189#[derive(Clone)]
2190pub struct Iter<'a, B: 'a = u32> {
2191    bit_vec: &'a BitVec<B>,
2192    range: Range<usize>,
2193}
2194
2195#[derive(Debug)]
2196pub struct MutBorrowedBit<'a, B: 'a + BitBlock> {
2197    vec: Rc<RefCell<&'a mut BitVec<B>>>,
2198    index: usize,
2199    #[cfg(debug_assertions)]
2200    old_value: bool,
2201    new_value: bool,
2202}
2203
2204/// An iterator for mutable references to the bits in a `BitVec`.
2205pub struct IterMut<'a, B: 'a + BitBlock = u32> {
2206    vec: Rc<RefCell<&'a mut BitVec<B>>>,
2207    range: Range<usize>,
2208}
2209
2210impl<'a, B: 'a + BitBlock> IterMut<'a, B> {
2211    fn get(&mut self, index: Option<usize>) -> Option<MutBorrowedBit<'a, B>> {
2212        let value = (*self.vec).borrow().get(index?)?;
2213        Some(MutBorrowedBit {
2214            vec: self.vec.clone(),
2215            index: index?,
2216            #[cfg(debug_assertions)]
2217            old_value: value,
2218            new_value: value,
2219        })
2220    }
2221}
2222
2223impl<B: BitBlock> Deref for MutBorrowedBit<'_, B> {
2224    type Target = bool;
2225
2226    fn deref(&self) -> &Self::Target {
2227        &self.new_value
2228    }
2229}
2230
2231impl<B: BitBlock> DerefMut for MutBorrowedBit<'_, B> {
2232    fn deref_mut(&mut self) -> &mut Self::Target {
2233        &mut self.new_value
2234    }
2235}
2236
2237impl<B: BitBlock> Drop for MutBorrowedBit<'_, B> {
2238    fn drop(&mut self) {
2239        let mut vec = (*self.vec).borrow_mut();
2240        #[cfg(debug_assertions)]
2241        debug_assert_eq!(
2242            Some(self.old_value),
2243            vec.get(self.index),
2244            "Mutably-borrowed bit was modified externally!"
2245        );
2246        vec.set(self.index, self.new_value);
2247    }
2248}
2249
2250impl<B: BitBlock> Iterator for Iter<'_, B> {
2251    type Item = bool;
2252
2253    #[inline]
2254    fn next(&mut self) -> Option<bool> {
2255        // NB: indexing is slow for extern crates when it has to go through &TRUE or &FALSE
2256        // variables.  get is more direct, and unwrap is fine since we're sure of the range.
2257        self.range.next().map(|i| self.bit_vec.get(i).unwrap())
2258    }
2259
2260    fn nth(&mut self, n: usize) -> Option<Self::Item> {
2261        // This override is used by the compiler to optimize Iterator::skip.
2262        // Without this, the default implementation of Iterator::nth is used, which walks over
2263        // the whole iterator up to n.
2264        self.range.nth(n).and_then(|i| self.bit_vec.get(i))
2265    }
2266
2267    fn size_hint(&self) -> (usize, Option<usize>) {
2268        self.range.size_hint()
2269    }
2270}
2271
2272impl<'a, B: BitBlock> Iterator for IterMut<'a, B> {
2273    type Item = MutBorrowedBit<'a, B>;
2274
2275    #[inline]
2276    fn next(&mut self) -> Option<Self::Item> {
2277        let index = self.range.next();
2278        self.get(index)
2279    }
2280
2281    fn size_hint(&self) -> (usize, Option<usize>) {
2282        self.range.size_hint()
2283    }
2284}
2285
2286impl<B: BitBlock> DoubleEndedIterator for Iter<'_, B> {
2287    #[inline]
2288    fn next_back(&mut self) -> Option<bool> {
2289        self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
2290    }
2291}
2292
2293impl<B: BitBlock> DoubleEndedIterator for IterMut<'_, B> {
2294    #[inline]
2295    fn next_back(&mut self) -> Option<Self::Item> {
2296        let index = self.range.next_back();
2297        self.get(index)
2298    }
2299}
2300
2301impl<B: BitBlock> ExactSizeIterator for Iter<'_, B> {}
2302
2303impl<B: BitBlock> ExactSizeIterator for IterMut<'_, B> {}
2304
2305impl<'a, B: BitBlock> IntoIterator for &'a BitVec<B> {
2306    type Item = bool;
2307    type IntoIter = Iter<'a, B>;
2308
2309    #[inline]
2310    fn into_iter(self) -> Iter<'a, B> {
2311        self.iter()
2312    }
2313}
2314
2315pub struct IntoIter<B = u32> {
2316    bit_vec: BitVec<B>,
2317    range: Range<usize>,
2318}
2319
2320impl<B: BitBlock> Iterator for IntoIter<B> {
2321    type Item = bool;
2322
2323    #[inline]
2324    fn next(&mut self) -> Option<bool> {
2325        self.range.next().map(|i| self.bit_vec.get(i).unwrap())
2326    }
2327}
2328
2329impl<B: BitBlock> DoubleEndedIterator for IntoIter<B> {
2330    #[inline]
2331    fn next_back(&mut self) -> Option<bool> {
2332        self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
2333    }
2334}
2335
2336impl<B: BitBlock> ExactSizeIterator for IntoIter<B> {}
2337
2338impl<B: BitBlock> IntoIterator for BitVec<B> {
2339    type Item = bool;
2340    type IntoIter = IntoIter<B>;
2341
2342    #[inline]
2343    fn into_iter(self) -> IntoIter<B> {
2344        let nbits = self.nbits;
2345        IntoIter {
2346            bit_vec: self,
2347            range: 0..nbits,
2348        }
2349    }
2350}
2351
2352/// An iterator over the blocks of a `BitVec`.
2353#[derive(Clone)]
2354pub struct Blocks<'a, B: 'a> {
2355    iter: slice::Iter<'a, B>,
2356}
2357
2358impl<B: BitBlock> Iterator for Blocks<'_, B> {
2359    type Item = B;
2360
2361    #[inline]
2362    fn next(&mut self) -> Option<B> {
2363        self.iter.next().cloned()
2364    }
2365
2366    #[inline]
2367    fn size_hint(&self) -> (usize, Option<usize>) {
2368        self.iter.size_hint()
2369    }
2370}
2371
2372impl<B: BitBlock> DoubleEndedIterator for Blocks<'_, B> {
2373    #[inline]
2374    fn next_back(&mut self) -> Option<B> {
2375        self.iter.next_back().cloned()
2376    }
2377}
2378
2379impl<B: BitBlock> ExactSizeIterator for Blocks<'_, B> {}
2380
2381#[cfg(test)]
2382mod tests {
2383    #![allow(clippy::shadow_reuse)]
2384    #![allow(clippy::shadow_same)]
2385    #![allow(clippy::shadow_unrelated)]
2386
2387    use super::{BitVec, Iter, Vec};
2388
2389    // This is stupid, but I want to differentiate from a "random" 32
2390    const U32_BITS: usize = 32;
2391
2392    #[test]
2393    fn test_display_output() {
2394        assert_eq!(format!("{}", BitVec::new()), "");
2395        assert_eq!(format!("{}", BitVec::from_elem(1, true)), "1");
2396        assert_eq!(format!("{}", BitVec::from_elem(8, false)), "00000000")
2397    }
2398
2399    #[test]
2400    fn test_debug_output() {
2401        assert_eq!(
2402            format!("{:?}", BitVec::new()),
2403            "BitVec { storage: \"\", nbits: 0 }"
2404        );
2405        assert_eq!(
2406            format!("{:?}", BitVec::from_elem(1, true)),
2407            "BitVec { storage: \"1\", nbits: 1 }"
2408        );
2409        assert_eq!(
2410            format!("{:?}", BitVec::from_elem(8, false)),
2411            "BitVec { storage: \"00000000\", nbits: 8 }"
2412        );
2413        assert_eq!(
2414            format!("{:?}", BitVec::from_elem(33, true)),
2415            "BitVec { storage: \"11111111111111111111111111111111 1\", nbits: 33 }"
2416        );
2417        assert_eq!(
2418            format!(
2419                "{:?}",
2420                BitVec::from_bytes(&[0b111, 0b000, 0b1110, 0b0001, 0b11111111, 0b00000000])
2421            ),
2422            "BitVec { storage: \"00000111000000000000111000000001 1111111100000000\", nbits: 48 }"
2423        )
2424    }
2425
2426    #[test]
2427    fn test_0_elements() {
2428        let act = BitVec::new();
2429        let exp = Vec::new();
2430        assert!(act.eq_vec(&exp));
2431        assert!(act.none() && act.all());
2432    }
2433
2434    #[test]
2435    fn test_1_element() {
2436        let mut act = BitVec::from_elem(1, false);
2437        assert!(act.eq_vec(&[false]));
2438        assert!(act.none() && !act.all());
2439        act = BitVec::from_elem(1, true);
2440        assert!(act.eq_vec(&[true]));
2441        assert!(!act.none() && act.all());
2442    }
2443
2444    #[test]
2445    fn test_2_elements() {
2446        let mut b = BitVec::from_elem(2, false);
2447        b.set(0, true);
2448        b.set(1, false);
2449        assert_eq!(format!("{}", b), "10");
2450        assert!(!b.none() && !b.all());
2451    }
2452
2453    #[test]
2454    fn test_10_elements() {
2455        // all 0
2456
2457        let mut act = BitVec::from_elem(10, false);
2458        assert!(
2459            (act.eq_vec(&[false, false, false, false, false, false, false, false, false, false]))
2460        );
2461        assert!(act.none() && !act.all());
2462        // all 1
2463
2464        act = BitVec::from_elem(10, true);
2465        assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
2466        assert!(!act.none() && act.all());
2467        // mixed
2468
2469        act = BitVec::from_elem(10, false);
2470        act.set(0, true);
2471        act.set(1, true);
2472        act.set(2, true);
2473        act.set(3, true);
2474        act.set(4, true);
2475        assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
2476        assert!(!act.none() && !act.all());
2477        // mixed
2478
2479        act = BitVec::from_elem(10, false);
2480        act.set(5, true);
2481        act.set(6, true);
2482        act.set(7, true);
2483        act.set(8, true);
2484        act.set(9, true);
2485        assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
2486        assert!(!act.none() && !act.all());
2487        // mixed
2488
2489        act = BitVec::from_elem(10, false);
2490        act.set(0, true);
2491        act.set(3, true);
2492        act.set(6, true);
2493        act.set(9, true);
2494        assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
2495        assert!(!act.none() && !act.all());
2496    }
2497
2498    #[test]
2499    fn test_31_elements() {
2500        // all 0
2501
2502        let mut act = BitVec::from_elem(31, false);
2503        assert!(act.eq_vec(&[
2504            false, false, false, false, false, false, false, false, false, false, false, false,
2505            false, false, false, false, false, false, false, false, false, false, false, false,
2506            false, false, false, false, false, false, false
2507        ]));
2508        assert!(act.none() && !act.all());
2509        // all 1
2510
2511        act = BitVec::from_elem(31, true);
2512        assert!(act.eq_vec(&[
2513            true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2514            true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2515            true, true, true
2516        ]));
2517        assert!(!act.none() && act.all());
2518        // mixed
2519
2520        act = BitVec::from_elem(31, false);
2521        act.set(0, true);
2522        act.set(1, true);
2523        act.set(2, true);
2524        act.set(3, true);
2525        act.set(4, true);
2526        act.set(5, true);
2527        act.set(6, true);
2528        act.set(7, true);
2529        assert!(act.eq_vec(&[
2530            true, true, true, true, true, true, true, true, false, false, false, false, false,
2531            false, false, false, false, false, false, false, false, false, false, false, false,
2532            false, false, false, false, false, false
2533        ]));
2534        assert!(!act.none() && !act.all());
2535        // mixed
2536
2537        act = BitVec::from_elem(31, false);
2538        act.set(16, true);
2539        act.set(17, true);
2540        act.set(18, true);
2541        act.set(19, true);
2542        act.set(20, true);
2543        act.set(21, true);
2544        act.set(22, true);
2545        act.set(23, true);
2546        assert!(act.eq_vec(&[
2547            false, false, false, false, false, false, false, false, false, false, false, false,
2548            false, false, false, false, true, true, true, true, true, true, true, true, false,
2549            false, false, false, false, false, false
2550        ]));
2551        assert!(!act.none() && !act.all());
2552        // mixed
2553
2554        act = BitVec::from_elem(31, false);
2555        act.set(24, true);
2556        act.set(25, true);
2557        act.set(26, true);
2558        act.set(27, true);
2559        act.set(28, true);
2560        act.set(29, true);
2561        act.set(30, true);
2562        assert!(act.eq_vec(&[
2563            false, false, false, false, false, false, false, false, false, false, false, false,
2564            false, false, false, false, false, false, false, false, false, false, false, false,
2565            true, true, true, true, true, true, true
2566        ]));
2567        assert!(!act.none() && !act.all());
2568        // mixed
2569
2570        act = BitVec::from_elem(31, false);
2571        act.set(3, true);
2572        act.set(17, true);
2573        act.set(30, true);
2574        assert!(act.eq_vec(&[
2575            false, false, false, true, false, false, false, false, false, false, false, false,
2576            false, false, false, false, false, true, false, false, false, false, false, false,
2577            false, false, false, false, false, false, true
2578        ]));
2579        assert!(!act.none() && !act.all());
2580    }
2581
2582    #[test]
2583    fn test_32_elements() {
2584        // all 0
2585
2586        let mut act = BitVec::from_elem(32, false);
2587        assert!(act.eq_vec(&[
2588            false, false, false, false, false, false, false, false, false, false, false, false,
2589            false, false, false, false, false, false, false, false, false, false, false, false,
2590            false, false, false, false, false, false, false, false
2591        ]));
2592        assert!(act.none() && !act.all());
2593        // all 1
2594
2595        act = BitVec::from_elem(32, true);
2596        assert!(act.eq_vec(&[
2597            true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2598            true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2599            true, true, true, true
2600        ]));
2601        assert!(!act.none() && act.all());
2602        // mixed
2603
2604        act = BitVec::from_elem(32, false);
2605        act.set(0, true);
2606        act.set(1, true);
2607        act.set(2, true);
2608        act.set(3, true);
2609        act.set(4, true);
2610        act.set(5, true);
2611        act.set(6, true);
2612        act.set(7, true);
2613        assert!(act.eq_vec(&[
2614            true, true, true, true, true, true, true, true, false, false, false, false, false,
2615            false, false, false, false, false, false, false, false, false, false, false, false,
2616            false, false, false, false, false, false, false
2617        ]));
2618        assert!(!act.none() && !act.all());
2619        // mixed
2620
2621        act = BitVec::from_elem(32, false);
2622        act.set(16, true);
2623        act.set(17, true);
2624        act.set(18, true);
2625        act.set(19, true);
2626        act.set(20, true);
2627        act.set(21, true);
2628        act.set(22, true);
2629        act.set(23, true);
2630        assert!(act.eq_vec(&[
2631            false, false, false, false, false, false, false, false, false, false, false, false,
2632            false, false, false, false, true, true, true, true, true, true, true, true, false,
2633            false, false, false, false, false, false, false
2634        ]));
2635        assert!(!act.none() && !act.all());
2636        // mixed
2637
2638        act = BitVec::from_elem(32, false);
2639        act.set(24, true);
2640        act.set(25, true);
2641        act.set(26, true);
2642        act.set(27, true);
2643        act.set(28, true);
2644        act.set(29, true);
2645        act.set(30, true);
2646        act.set(31, true);
2647        assert!(act.eq_vec(&[
2648            false, false, false, false, false, false, false, false, false, false, false, false,
2649            false, false, false, false, false, false, false, false, false, false, false, false,
2650            true, true, true, true, true, true, true, true
2651        ]));
2652        assert!(!act.none() && !act.all());
2653        // mixed
2654
2655        act = BitVec::from_elem(32, false);
2656        act.set(3, true);
2657        act.set(17, true);
2658        act.set(30, true);
2659        act.set(31, true);
2660        assert!(act.eq_vec(&[
2661            false, false, false, true, false, false, false, false, false, false, false, false,
2662            false, false, false, false, false, true, false, false, false, false, false, false,
2663            false, false, false, false, false, false, true, true
2664        ]));
2665        assert!(!act.none() && !act.all());
2666    }
2667
2668    #[test]
2669    fn test_33_elements() {
2670        // all 0
2671
2672        let mut act = BitVec::from_elem(33, false);
2673        assert!(act.eq_vec(&[
2674            false, false, false, false, false, false, false, false, false, false, false, false,
2675            false, false, false, false, false, false, false, false, false, false, false, false,
2676            false, false, false, false, false, false, false, false, false
2677        ]));
2678        assert!(act.none() && !act.all());
2679        // all 1
2680
2681        act = BitVec::from_elem(33, true);
2682        assert!(act.eq_vec(&[
2683            true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2684            true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2685            true, true, true, true, true
2686        ]));
2687        assert!(!act.none() && act.all());
2688        // mixed
2689
2690        act = BitVec::from_elem(33, false);
2691        act.set(0, true);
2692        act.set(1, true);
2693        act.set(2, true);
2694        act.set(3, true);
2695        act.set(4, true);
2696        act.set(5, true);
2697        act.set(6, true);
2698        act.set(7, true);
2699        assert!(act.eq_vec(&[
2700            true, true, true, true, true, true, true, true, false, false, false, false, false,
2701            false, false, false, false, false, false, false, false, false, false, false, false,
2702            false, false, false, false, false, false, false, false
2703        ]));
2704        assert!(!act.none() && !act.all());
2705        // mixed
2706
2707        act = BitVec::from_elem(33, false);
2708        act.set(16, true);
2709        act.set(17, true);
2710        act.set(18, true);
2711        act.set(19, true);
2712        act.set(20, true);
2713        act.set(21, true);
2714        act.set(22, true);
2715        act.set(23, true);
2716        assert!(act.eq_vec(&[
2717            false, false, false, false, false, false, false, false, false, false, false, false,
2718            false, false, false, false, true, true, true, true, true, true, true, true, false,
2719            false, false, false, false, false, false, false, false
2720        ]));
2721        assert!(!act.none() && !act.all());
2722        // mixed
2723
2724        act = BitVec::from_elem(33, false);
2725        act.set(24, true);
2726        act.set(25, true);
2727        act.set(26, true);
2728        act.set(27, true);
2729        act.set(28, true);
2730        act.set(29, true);
2731        act.set(30, true);
2732        act.set(31, true);
2733        assert!(act.eq_vec(&[
2734            false, false, false, false, false, false, false, false, false, false, false, false,
2735            false, false, false, false, false, false, false, false, false, false, false, false,
2736            true, true, true, true, true, true, true, true, false
2737        ]));
2738        assert!(!act.none() && !act.all());
2739        // mixed
2740
2741        act = BitVec::from_elem(33, false);
2742        act.set(3, true);
2743        act.set(17, true);
2744        act.set(30, true);
2745        act.set(31, true);
2746        act.set(32, true);
2747        assert!(act.eq_vec(&[
2748            false, false, false, true, false, false, false, false, false, false, false, false,
2749            false, false, false, false, false, true, false, false, false, false, false, false,
2750            false, false, false, false, false, false, true, true, true
2751        ]));
2752        assert!(!act.none() && !act.all());
2753    }
2754
2755    #[test]
2756    fn test_equal_differing_sizes() {
2757        let v0 = BitVec::from_elem(10, false);
2758        let v1 = BitVec::from_elem(11, false);
2759        assert_ne!(v0, v1);
2760    }
2761
2762    #[test]
2763    fn test_equal_greatly_differing_sizes() {
2764        let v0 = BitVec::from_elem(10, false);
2765        let v1 = BitVec::from_elem(110, false);
2766        assert_ne!(v0, v1);
2767    }
2768
2769    #[test]
2770    fn test_equal_sneaky_small() {
2771        let mut a = BitVec::from_elem(1, false);
2772        a.set(0, true);
2773
2774        let mut b = BitVec::from_elem(1, true);
2775        b.set(0, true);
2776
2777        assert_eq!(a, b);
2778    }
2779
2780    #[test]
2781    fn test_equal_sneaky_big() {
2782        let mut a = BitVec::from_elem(100, false);
2783        for i in 0..100 {
2784            a.set(i, true);
2785        }
2786
2787        let mut b = BitVec::from_elem(100, true);
2788        for i in 0..100 {
2789            b.set(i, true);
2790        }
2791
2792        assert_eq!(a, b);
2793    }
2794
2795    #[test]
2796    fn test_from_bytes() {
2797        let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2798        let str = concat!("10110110", "00000000", "11111111");
2799        assert_eq!(format!("{}", bit_vec), str);
2800    }
2801
2802    #[test]
2803    fn test_to_bytes() {
2804        let mut bv = BitVec::from_elem(3, true);
2805        bv.set(1, false);
2806        assert_eq!(bv.to_bytes(), [0b10100000]);
2807
2808        let mut bv = BitVec::from_elem(9, false);
2809        bv.set(2, true);
2810        bv.set(8, true);
2811        assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
2812    }
2813
2814    #[test]
2815    fn test_from_bools() {
2816        let bools = [true, false, true, true];
2817        let bit_vec: BitVec = bools.iter().copied().collect();
2818        assert_eq!(format!("{}", bit_vec), "1011");
2819    }
2820
2821    #[test]
2822    fn test_to_bools() {
2823        let bools = vec![false, false, true, false, false, true, true, false];
2824        assert_eq!(
2825            BitVec::from_bytes(&[0b00100110])
2826                .iter()
2827                .collect::<Vec<bool>>(),
2828            bools
2829        );
2830    }
2831
2832    #[test]
2833    fn test_bit_vec_iterator() {
2834        let bools = vec![true, false, true, true];
2835        let bit_vec: BitVec = bools.iter().copied().collect();
2836
2837        assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools);
2838
2839        let long: Vec<_> = (0..10000).map(|i| i % 2 == 0).collect();
2840        let bit_vec: BitVec = long.iter().copied().collect();
2841        assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long)
2842    }
2843
2844    #[test]
2845    fn test_small_difference() {
2846        let mut b1 = BitVec::from_elem(3, false);
2847        let mut b2 = BitVec::from_elem(3, false);
2848        b1.set(0, true);
2849        b1.set(1, true);
2850        b2.set(1, true);
2851        b2.set(2, true);
2852        assert!(b1.difference(&b2));
2853        assert!(b1[0]);
2854        assert!(!b1[1]);
2855        assert!(!b1[2]);
2856    }
2857
2858    #[test]
2859    fn test_big_difference() {
2860        let mut b1 = BitVec::from_elem(100, false);
2861        let mut b2 = BitVec::from_elem(100, false);
2862        b1.set(0, true);
2863        b1.set(40, true);
2864        b2.set(40, true);
2865        b2.set(80, true);
2866        assert!(b1.difference(&b2));
2867        assert!(b1[0]);
2868        assert!(!b1[40]);
2869        assert!(!b1[80]);
2870    }
2871
2872    #[test]
2873    fn test_small_xor() {
2874        let mut a = BitVec::from_bytes(&[0b0011]);
2875        let b = BitVec::from_bytes(&[0b0101]);
2876        let c = BitVec::from_bytes(&[0b0110]);
2877        assert!(a.xor(&b));
2878        assert_eq!(a, c);
2879    }
2880
2881    #[test]
2882    fn test_small_xnor() {
2883        let mut a = BitVec::from_bytes(&[0b0011]);
2884        let b = BitVec::from_bytes(&[0b1111_0101]);
2885        let c = BitVec::from_bytes(&[0b1001]);
2886        assert!(a.xnor(&b));
2887        assert_eq!(a, c);
2888    }
2889
2890    #[test]
2891    fn test_small_nand() {
2892        let mut a = BitVec::from_bytes(&[0b1111_0011]);
2893        let b = BitVec::from_bytes(&[0b1111_0101]);
2894        let c = BitVec::from_bytes(&[0b1110]);
2895        assert!(a.nand(&b));
2896        assert_eq!(a, c);
2897    }
2898
2899    #[test]
2900    fn test_small_nor() {
2901        let mut a = BitVec::from_bytes(&[0b0011]);
2902        let b = BitVec::from_bytes(&[0b1111_0101]);
2903        let c = BitVec::from_bytes(&[0b1000]);
2904        assert!(a.nor(&b));
2905        assert_eq!(a, c);
2906    }
2907
2908    #[test]
2909    fn test_big_xor() {
2910        let mut a = BitVec::from_bytes(&[
2911            // 88 bits
2912            0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0,
2913        ]);
2914        let b = BitVec::from_bytes(&[
2915            // 88 bits
2916            0, 0, 0b00010100, 0, 0, 0, 0, 0, 0, 0, 0b00110100,
2917        ]);
2918        let c = BitVec::from_bytes(&[
2919            // 88 bits
2920            0, 0, 0, 0, 0, 0, 0, 0b00110100, 0, 0, 0b00110100,
2921        ]);
2922        assert!(a.xor(&b));
2923        assert_eq!(a, c);
2924    }
2925
2926    #[test]
2927    fn test_big_xnor() {
2928        let mut a = BitVec::from_bytes(&[
2929            // 88 bits
2930            0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0,
2931        ]);
2932        let b = BitVec::from_bytes(&[
2933            // 88 bits
2934            0, 0, 0b00010100, 0, 0, 0, 0, 0, 0, 0, 0b00110100,
2935        ]);
2936        let c = BitVec::from_bytes(&[
2937            // 88 bits
2938            !0,
2939            !0,
2940            !0,
2941            !0,
2942            !0,
2943            !0,
2944            !0,
2945            !0b00110100,
2946            !0,
2947            !0,
2948            !0b00110100,
2949        ]);
2950        assert!(a.xnor(&b));
2951        assert_eq!(a, c);
2952    }
2953
2954    #[test]
2955    fn test_small_fill() {
2956        let mut b = BitVec::from_elem(14, true);
2957        assert!(!b.none() && b.all());
2958        b.fill(false);
2959        assert!(b.none() && !b.all());
2960        b.fill(true);
2961        assert!(!b.none() && b.all());
2962    }
2963
2964    #[test]
2965    fn test_big_fill() {
2966        let mut b = BitVec::from_elem(140, true);
2967        assert!(!b.none() && b.all());
2968        b.fill(false);
2969        assert!(b.none() && !b.all());
2970        b.fill(true);
2971        assert!(!b.none() && b.all());
2972    }
2973
2974    #[test]
2975    fn test_bit_vec_lt() {
2976        let mut a = BitVec::from_elem(5, false);
2977        let mut b = BitVec::from_elem(5, false);
2978
2979        assert!(a >= b && b >= a);
2980        b.set(2, true);
2981        assert!(a < b);
2982        a.set(3, true);
2983        assert!(a < b);
2984        a.set(2, true);
2985        assert!(a >= b && b < a);
2986        b.set(0, true);
2987        assert!(a < b);
2988    }
2989
2990    #[test]
2991    fn test_ord() {
2992        let mut a = BitVec::from_elem(5, false);
2993        let mut b = BitVec::from_elem(5, false);
2994
2995        assert!(a == b);
2996        a.set(1, true);
2997        assert!(a > b && a >= b);
2998        assert!(b < a && b <= a);
2999        b.set(1, true);
3000        b.set(2, true);
3001        assert!(b > a && b >= a);
3002        assert!(a < b && a <= b);
3003    }
3004
3005    #[test]
3006    fn test_small_bit_vec_tests() {
3007        let v = BitVec::from_bytes(&[0]);
3008        assert!(!v.all());
3009        assert!(!v.any());
3010        assert!(v.none());
3011
3012        let v = BitVec::from_bytes(&[0b00010100]);
3013        assert!(!v.all());
3014        assert!(v.any());
3015        assert!(!v.none());
3016
3017        let v = BitVec::from_bytes(&[0xFF]);
3018        assert!(v.all());
3019        assert!(v.any());
3020        assert!(!v.none());
3021    }
3022
3023    #[test]
3024    fn test_big_bit_vec_tests() {
3025        let v = BitVec::from_bytes(&[
3026            // 88 bits
3027            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3028        ]);
3029        assert!(!v.all());
3030        assert!(!v.any());
3031        assert!(v.none());
3032
3033        let v = BitVec::from_bytes(&[
3034            // 88 bits
3035            0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0,
3036        ]);
3037        assert!(!v.all());
3038        assert!(v.any());
3039        assert!(!v.none());
3040
3041        let v = BitVec::from_bytes(&[
3042            // 88 bits
3043            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
3044        ]);
3045        assert!(v.all());
3046        assert!(v.any());
3047        assert!(!v.none());
3048    }
3049
3050    #[test]
3051    fn test_bit_vec_push_pop() {
3052        let mut s = BitVec::from_elem(5 * U32_BITS - 2, false);
3053        assert_eq!(s.len(), 5 * U32_BITS - 2);
3054        assert!(!s[5 * U32_BITS - 3]);
3055        s.push(true);
3056        s.push(true);
3057        assert!(s[5 * U32_BITS - 2]);
3058        assert!(s[5 * U32_BITS - 1]);
3059        // Here the internal vector will need to be extended
3060        s.push(false);
3061        assert!(!s[5 * U32_BITS]);
3062        s.push(false);
3063        assert!(!s[5 * U32_BITS + 1]);
3064        assert_eq!(s.len(), 5 * U32_BITS + 2);
3065        // Pop it all off
3066        assert_eq!(s.pop(), Some(false));
3067        assert_eq!(s.pop(), Some(false));
3068        assert_eq!(s.pop(), Some(true));
3069        assert_eq!(s.pop(), Some(true));
3070        assert_eq!(s.len(), 5 * U32_BITS - 2);
3071    }
3072
3073    #[test]
3074    fn test_bit_vec_truncate() {
3075        let mut s = BitVec::from_elem(5 * U32_BITS, true);
3076
3077        assert_eq!(s, BitVec::from_elem(5 * U32_BITS, true));
3078        assert_eq!(s.len(), 5 * U32_BITS);
3079        s.truncate(4 * U32_BITS);
3080        assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
3081        assert_eq!(s.len(), 4 * U32_BITS);
3082        // Truncating to a size > s.len() should be a noop
3083        s.truncate(5 * U32_BITS);
3084        assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
3085        assert_eq!(s.len(), 4 * U32_BITS);
3086        s.truncate(3 * U32_BITS - 10);
3087        assert_eq!(s, BitVec::from_elem(3 * U32_BITS - 10, true));
3088        assert_eq!(s.len(), 3 * U32_BITS - 10);
3089        s.truncate(0);
3090        assert_eq!(s, BitVec::from_elem(0, true));
3091        assert_eq!(s.len(), 0);
3092    }
3093
3094    #[test]
3095    fn test_bit_vec_reserve() {
3096        let mut s = BitVec::from_elem(5 * U32_BITS, true);
3097        // Check capacity
3098        assert!(s.capacity() >= 5 * U32_BITS);
3099        s.reserve(2 * U32_BITS);
3100        assert!(s.capacity() >= 7 * U32_BITS);
3101        s.reserve(7 * U32_BITS);
3102        assert!(s.capacity() >= 12 * U32_BITS);
3103        s.reserve_exact(7 * U32_BITS);
3104        assert!(s.capacity() >= 12 * U32_BITS);
3105        s.reserve(7 * U32_BITS + 1);
3106        assert!(s.capacity() > 12 * U32_BITS);
3107        // Check that length hasn't changed
3108        assert_eq!(s.len(), 5 * U32_BITS);
3109        s.push(true);
3110        s.push(false);
3111        s.push(true);
3112        assert!(s[5 * U32_BITS - 1]);
3113        assert!(s[5 * U32_BITS]);
3114        assert!(!s[5 * U32_BITS + 1]);
3115        assert!(s[5 * U32_BITS + 2]);
3116    }
3117
3118    #[test]
3119    fn test_bit_vec_grow() {
3120        let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
3121        bit_vec.grow(32, true);
3122        assert_eq!(
3123            bit_vec,
3124            BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF])
3125        );
3126        bit_vec.grow(64, false);
3127        assert_eq!(
3128            bit_vec,
3129            BitVec::from_bytes(&[
3130                0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0
3131            ])
3132        );
3133        bit_vec.grow(16, true);
3134        assert_eq!(
3135            bit_vec,
3136            BitVec::from_bytes(&[
3137                0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0,
3138                0xFF, 0xFF
3139            ])
3140        );
3141    }
3142
3143    #[test]
3144    fn test_bit_vec_extend() {
3145        let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
3146        let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
3147        bit_vec.extend(ext.iter());
3148        assert_eq!(
3149            bit_vec,
3150            BitVec::from_bytes(&[
3151                0b10110110, 0b00000000, 0b11111111, 0b01001001, 0b10010010, 0b10111101
3152            ])
3153        );
3154    }
3155
3156    #[test]
3157    fn test_bit_vec_append() {
3158        // Append to BitVec that holds a multiple of U32_BITS bits
3159        let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011]);
3160        let mut b = BitVec::new();
3161        b.push(false);
3162        b.push(true);
3163        b.push(true);
3164
3165        a.append(&mut b);
3166
3167        assert_eq!(a.len(), 35);
3168        assert_eq!(b.len(), 0);
3169        assert!(b.capacity() >= 3);
3170
3171        assert!(a.eq_vec(&[
3172            true, false, true, false, false, false, false, false, false, false, false, true, false,
3173            false, true, false, true, false, false, true, false, false, true, false, false, false,
3174            true, true, false, false, true, true, false, true, true
3175        ]));
3176
3177        // Append to arbitrary BitVec
3178        let mut a = BitVec::new();
3179        a.push(true);
3180        a.push(false);
3181
3182        let mut b =
3183            BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
3184
3185        a.append(&mut b);
3186
3187        assert_eq!(a.len(), 42);
3188        assert_eq!(b.len(), 0);
3189        assert!(b.capacity() >= 40);
3190
3191        assert!(a.eq_vec(&[
3192            true, false, true, false, true, false, false, false, false, false, false, false, false,
3193            true, false, false, true, false, true, false, false, true, false, false, true, false,
3194            false, false, true, true, false, false, true, true, true, false, false, true, false,
3195            true, false, true
3196        ]));
3197
3198        // Append to empty BitVec
3199        let mut a = BitVec::new();
3200        let mut b =
3201            BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
3202
3203        a.append(&mut b);
3204
3205        assert_eq!(a.len(), 40);
3206        assert_eq!(b.len(), 0);
3207        assert!(b.capacity() >= 40);
3208
3209        assert!(a.eq_vec(&[
3210            true, false, true, false, false, false, false, false, false, false, false, true, false,
3211            false, true, false, true, false, false, true, false, false, true, false, false, false,
3212            true, true, false, false, true, true, true, false, false, true, false, true, false,
3213            true
3214        ]));
3215
3216        // Append empty BitVec
3217        let mut a =
3218            BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
3219        let mut b = BitVec::new();
3220
3221        a.append(&mut b);
3222
3223        assert_eq!(a.len(), 40);
3224        assert_eq!(b.len(), 0);
3225
3226        assert!(a.eq_vec(&[
3227            true, false, true, false, false, false, false, false, false, false, false, true, false,
3228            false, true, false, true, false, false, true, false, false, true, false, false, false,
3229            true, true, false, false, true, true, true, false, false, true, false, true, false,
3230            true
3231        ]));
3232    }
3233
3234    #[test]
3235    fn test_bit_vec_split_off() {
3236        // Split at 0
3237        let mut a = BitVec::new();
3238        a.push(true);
3239        a.push(false);
3240        a.push(false);
3241        a.push(true);
3242
3243        let b = a.split_off(0);
3244
3245        assert_eq!(a.len(), 0);
3246        assert_eq!(b.len(), 4);
3247
3248        assert!(b.eq_vec(&[true, false, false, true]));
3249
3250        // Split at last bit
3251        a.truncate(0);
3252        a.push(true);
3253        a.push(false);
3254        a.push(false);
3255        a.push(true);
3256
3257        let b = a.split_off(4);
3258
3259        assert_eq!(a.len(), 4);
3260        assert_eq!(b.len(), 0);
3261
3262        assert!(a.eq_vec(&[true, false, false, true]));
3263
3264        // Split at block boundary
3265        let mut a =
3266            BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b11110011]);
3267
3268        let b = a.split_off(32);
3269
3270        assert_eq!(a.len(), 32);
3271        assert_eq!(b.len(), 8);
3272
3273        assert!(a.eq_vec(&[
3274            true, false, true, false, false, false, false, false, false, false, false, true, false,
3275            false, true, false, true, false, false, true, false, false, true, false, false, false,
3276            true, true, false, false, true, true
3277        ]));
3278        assert!(b.eq_vec(&[true, true, true, true, false, false, true, true]));
3279
3280        // Don't split at block boundary
3281        let mut a = BitVec::from_bytes(&[
3282            0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b01101011, 0b10101101,
3283        ]);
3284
3285        let b = a.split_off(13);
3286
3287        assert_eq!(a.len(), 13);
3288        assert_eq!(b.len(), 35);
3289
3290        assert!(a.eq_vec(&[
3291            true, false, true, false, false, false, false, false, false, false, false, true, false
3292        ]));
3293        assert!(b.eq_vec(&[
3294            false, true, false, true, false, false, true, false, false, true, false, false, false,
3295            true, true, false, false, true, true, false, true, true, false, true, false, true,
3296            true, true, false, true, false, true, true, false, true
3297        ]));
3298    }
3299
3300    #[test]
3301    fn test_split_off_storage_boundaries() {
3302        for tail_len in [1, 31, 32, 33, 63, 64, 65] {
3303            for at in 0..=64 {
3304                for pattern in 0..3 {
3305                    let bits: Vec<bool> = (0..at + tail_len)
3306                        .map(|i| match pattern {
3307                            0 => false,
3308                            1 => true,
3309                            _ => i % 3 == 0,
3310                        })
3311                        .collect();
3312                    let mut a: BitVec<u32> = bits.iter().copied().collect();
3313                    let b = a.split_off(at);
3314
3315                    assert_eq!(a.storage().len(), (at + 31) / 32);
3316                    assert_eq!(b.storage().len(), (tail_len + 31) / 32);
3317                    assert_eq!(a.iter().collect::<Vec<_>>(), bits[..at]);
3318                    assert_eq!(b.iter().collect::<Vec<_>>(), bits[at..]);
3319                    assert_eq!(b.all(), bits[at..].iter().all(|&bit| bit));
3320                    assert_eq!(
3321                        b.count_zeros(),
3322                        bits[at..].iter().filter(|&&bit| !bit).count() as u64
3323                    );
3324                }
3325            }
3326        }
3327    }
3328
3329    #[test]
3330    fn test_into_iter() {
3331        let bools = [true, false, true, true];
3332        let bit_vec: BitVec = bools.iter().copied().collect();
3333        let mut iter = bit_vec.into_iter();
3334        assert_eq!(Some(true), iter.next());
3335        assert_eq!(Some(false), iter.next());
3336        assert_eq!(Some(true), iter.next());
3337        assert_eq!(Some(true), iter.next());
3338        assert_eq!(None, iter.next());
3339        assert_eq!(None, iter.next());
3340
3341        let bit_vec: BitVec = bools.iter().copied().collect();
3342        let mut iter = bit_vec.into_iter();
3343        assert_eq!(Some(true), iter.next_back());
3344        assert_eq!(Some(true), iter.next_back());
3345        assert_eq!(Some(false), iter.next_back());
3346        assert_eq!(Some(true), iter.next_back());
3347        assert_eq!(None, iter.next_back());
3348        assert_eq!(None, iter.next_back());
3349
3350        let bit_vec: BitVec = bools.iter().copied().collect();
3351        let mut iter = bit_vec.into_iter();
3352        assert_eq!(Some(true), iter.next_back());
3353        assert_eq!(Some(true), iter.next());
3354        assert_eq!(Some(false), iter.next());
3355        assert_eq!(Some(true), iter.next_back());
3356        assert_eq!(None, iter.next());
3357        assert_eq!(None, iter.next_back());
3358    }
3359
3360    #[test]
3361    fn iter() {
3362        let b = BitVec::with_capacity(10);
3363        let _a: Iter = b.iter();
3364    }
3365
3366    #[cfg(feature = "serde")]
3367    #[test]
3368    fn test_serialization() {
3369        let bit_vec: BitVec = BitVec::new();
3370        let serialized = serde_json::to_string(&bit_vec).unwrap();
3371        let unserialized: BitVec = serde_json::from_str(&serialized[..]).unwrap();
3372        assert_eq!(bit_vec, unserialized);
3373
3374        let bools = [true, false, true, true];
3375        let bit_vec: BitVec = bools.iter().copied().collect();
3376        let serialized = serde_json::to_string(&bit_vec).unwrap();
3377        let unserialized = serde_json::from_str(&serialized).unwrap();
3378        assert_eq!(bit_vec, unserialized);
3379    }
3380
3381    #[cfg(feature = "miniserde")]
3382    #[test]
3383    fn test_miniserde_serialization() {
3384        let bit_vec: BitVec = BitVec::new();
3385        let serialized = miniserde::json::to_string(&bit_vec);
3386        let unserialized = miniserde::json::from_str(&serialized[..]).unwrap();
3387        assert_eq!(bit_vec, unserialized);
3388
3389        let bools = [true, false, true, true];
3390        let bit_vec: BitVec = bools.iter().copied().collect();
3391        let serialized = miniserde::json::to_string(&bit_vec);
3392        let unserialized = miniserde::json::from_str(&serialized[..]).unwrap();
3393        assert_eq!(bit_vec, unserialized);
3394    }
3395
3396    #[cfg(feature = "borsh")]
3397    #[test]
3398    fn test_borsh_serialization() {
3399        let bit_vec: BitVec = BitVec::new();
3400        let serialized = borsh::to_vec(&bit_vec).unwrap();
3401        let unserialized = borsh::from_slice(&serialized[..]).unwrap();
3402        assert_eq!(bit_vec, unserialized);
3403
3404        let bools = [true, false, true, true];
3405        let bit_vec: BitVec = bools.iter().copied().collect();
3406        let serialized = borsh::to_vec(&bit_vec).unwrap();
3407        let unserialized = borsh::from_slice(&serialized[..]).unwrap();
3408        assert_eq!(bit_vec, unserialized);
3409    }
3410
3411    #[test]
3412    fn test_bit_vec_unaligned_small_append() {
3413        let mut a = BitVec::from_elem(8, false);
3414        a.set(7, true);
3415
3416        let mut b = BitVec::from_elem(16, false);
3417        b.set(14, true);
3418
3419        let mut c = BitVec::from_elem(8, false);
3420        c.set(6, true);
3421        c.set(7, true);
3422
3423        a.append(&mut b);
3424        a.append(&mut c);
3425
3426        assert_eq!(&[1, 0, 2, 3][..], &*a.to_bytes());
3427    }
3428
3429    #[test]
3430    fn test_bit_vec_unaligned_large_append() {
3431        let mut a = BitVec::from_elem(48, false);
3432        a.set(47, true);
3433
3434        let mut b = BitVec::from_elem(48, false);
3435        b.set(46, true);
3436
3437        let mut c = BitVec::from_elem(48, false);
3438        c.set(46, true);
3439        c.set(47, true);
3440
3441        a.append(&mut b);
3442        a.append(&mut c);
3443
3444        assert_eq!(
3445            &[
3446                0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00,
3447                0x00, 0x00, 0x00, 0x03
3448            ][..],
3449            &*a.to_bytes()
3450        );
3451    }
3452
3453    #[test]
3454    fn test_bit_vec_append_aligned_to_unaligned() {
3455        let mut a = BitVec::from_elem(2, true);
3456        let mut b = BitVec::from_elem(32, false);
3457        let mut c = BitVec::from_elem(8, true);
3458        a.append(&mut b);
3459        a.append(&mut c);
3460        assert_eq!(&[0xc0, 0x00, 0x00, 0x00, 0x3f, 0xc0][..], &*a.to_bytes());
3461    }
3462
3463    #[test]
3464    fn test_count_ones() {
3465        for i in 0..1000 {
3466            let mut t = BitVec::from_elem(i, true);
3467            let mut f = BitVec::from_elem(i, false);
3468            assert_eq!(i as u64, t.count_ones());
3469            assert_eq!(0_u64, f.count_ones());
3470            if i > 20 {
3471                t.set(10, false);
3472                t.set(i - 10, false);
3473                assert_eq!(i - 2, t.count_ones() as usize);
3474                f.set(10, true);
3475                f.set(i - 10, true);
3476                assert_eq!(2, f.count_ones());
3477            }
3478        }
3479    }
3480
3481    #[test]
3482    fn test_count_zeros() {
3483        for i in 0..1000 {
3484            let mut tbits = BitVec::from_elem(i, true);
3485            let mut fbits = BitVec::from_elem(i, false);
3486            assert_eq!(i as u64, fbits.count_zeros());
3487            assert_eq!(0_u64, tbits.count_zeros());
3488            if i > 20 {
3489                fbits.set(10, true);
3490                fbits.set(i - 10, true);
3491                assert_eq!(i - 2, fbits.count_zeros() as usize);
3492                tbits.set(10, false);
3493                tbits.set(i - 10, false);
3494                assert_eq!(2, tbits.count_zeros());
3495            }
3496        }
3497    }
3498
3499    #[test]
3500    fn test_get_mut() {
3501        let mut a = BitVec::from_elem(3, false);
3502        let mut a_bit_1 = a.get_mut(1).unwrap();
3503        assert!(!*a_bit_1);
3504        *a_bit_1 = true;
3505        drop(a_bit_1);
3506        assert!(a.eq_vec(&[false, true, false]));
3507    }
3508    #[test]
3509    fn test_iter_mut() {
3510        let mut a = BitVec::from_elem(8, false);
3511        a.iter_mut().enumerate().for_each(|(index, mut bit)| {
3512            *bit = index % 2 == 1;
3513        });
3514        assert!(a.eq_vec(&[false, true, false, true, false, true, false, true]));
3515    }
3516
3517    #[test]
3518    fn test_insert_at_zero() {
3519        let mut v = BitVec::new();
3520
3521        v.insert(0, false);
3522        v.insert(0, true);
3523        v.insert(0, false);
3524        v.insert(0, true);
3525        v.insert(0, false);
3526        v.insert(0, true);
3527
3528        assert_eq!(v.len(), 6);
3529        assert_eq!(v.storage().len(), 1);
3530        assert!(v.eq_vec(&[true, false, true, false, true, false]));
3531    }
3532
3533    #[test]
3534    fn test_insert_at_end() {
3535        let mut v = BitVec::new();
3536
3537        v.insert(v.len(), true);
3538        v.insert(v.len(), false);
3539        v.insert(v.len(), true);
3540        v.insert(v.len(), false);
3541        v.insert(v.len(), true);
3542        v.insert(v.len(), false);
3543
3544        assert_eq!(v.storage().len(), 1);
3545        assert_eq!(v.len(), 6);
3546        assert!(v.eq_vec(&[true, false, true, false, true, false]));
3547    }
3548
3549    #[test]
3550    fn test_insert_at_block_boundaries() {
3551        let mut v = BitVec::from_elem(32, false);
3552
3553        assert_eq!(v.storage().len(), 1);
3554
3555        v.insert(31, true);
3556
3557        assert_eq!(v.len(), 33);
3558
3559        assert!(matches!(v.get(31), Some(true)));
3560        assert!(v.eq_vec(&[
3561            false, false, false, false, false, false, false, false, false, false, false, false,
3562            false, false, false, false, false, false, false, false, false, false, false, false,
3563            false, false, false, false, false, false, false, true, false
3564        ]));
3565
3566        assert_eq!(v.storage().len(), 2);
3567    }
3568
3569    #[test]
3570    fn test_insert_at_block_boundaries_1() {
3571        let mut v = BitVec::from_elem(64, false);
3572
3573        assert_eq!(v.storage().len(), 2);
3574
3575        v.insert(63, true);
3576
3577        assert_eq!(v.len(), 65);
3578
3579        assert!(matches!(v.get(63), Some(true)));
3580        assert!(v.eq_vec(&[
3581            false, false, false, false, false, false, false, false, false, false, false, false,
3582            false, false, false, false, false, false, false, false, false, false, false, false,
3583            false, false, false, false, false, false, false, false, false, false, false, false,
3584            false, false, false, false, false, false, false, false, false, false, false, false,
3585            false, false, false, false, false, false, false, false, false, false, false, false,
3586            false, false, false, true, false
3587        ]));
3588
3589        assert_eq!(v.storage().len(), 3);
3590    }
3591
3592    #[test]
3593    fn test_push_within_capacity_with_suffice_cap() {
3594        let mut v = BitVec::from_elem(16, true);
3595
3596        assert!(v.push_within_capacity(false).is_ok());
3597
3598        for i in 0..16 {
3599            assert_eq!(v.get(i), Some(true));
3600        }
3601
3602        assert_eq!(v.get(16), Some(false));
3603        assert_eq!(v.len(), 17);
3604    }
3605
3606    #[test]
3607    fn test_push_within_capacity_at_brink() {
3608        let mut v = BitVec::from_elem(31, true);
3609
3610        assert!(v.push_within_capacity(false).is_ok());
3611
3612        assert_eq!(v.get(31), Some(false));
3613        assert_eq!(v.len(), v.capacity());
3614        assert_eq!(v.len(), 32);
3615
3616        assert_eq!(v.push_within_capacity(false), Err(false));
3617        assert_eq!(v.capacity(), 32);
3618
3619        for i in 0..31 {
3620            assert_eq!(v.get(i), Some(true));
3621        }
3622        assert_eq!(v.get(31), Some(false));
3623    }
3624
3625    #[test]
3626    fn test_push_within_capacity_at_brink_with_mul_blocks() {
3627        let mut v = BitVec::from_elem(95, true);
3628
3629        assert!(v.push_within_capacity(false).is_ok());
3630
3631        assert_eq!(v.get(95), Some(false));
3632        assert_eq!(v.len(), v.capacity());
3633        assert_eq!(v.len(), 96);
3634
3635        assert_eq!(v.push_within_capacity(false), Err(false));
3636        assert_eq!(v.capacity(), 96);
3637
3638        for i in 0..95 {
3639            assert_eq!(v.get(i), Some(true));
3640        }
3641        assert_eq!(v.get(95), Some(false));
3642    }
3643
3644    #[test]
3645    fn test_push_within_capacity_storage_push() {
3646        let mut v = BitVec::with_capacity(64);
3647
3648        for _ in 0..32 {
3649            v.push(true);
3650        }
3651
3652        assert_eq!(v.len(), 32);
3653
3654        assert!(v.push_within_capacity(false).is_ok());
3655
3656        assert_eq!(v.len(), 33);
3657
3658        for i in 0..32 {
3659            assert_eq!(v.get(i), Some(true));
3660        }
3661        assert_eq!(v.get(32), Some(false));
3662    }
3663
3664    #[test]
3665    fn test_insert_remove() {
3666        // two primes for no common divisors with 32
3667        let mut v = BitVec::from_fn(1024, |i| i % 11 < 7);
3668        for i in 0..1024 {
3669            let result = v.remove(i);
3670            v.insert(i, result);
3671            assert_eq!(result, i % 11 < 7);
3672        }
3673
3674        for i in 0..1024 {
3675            v.insert(i, false);
3676            v.remove(i);
3677        }
3678
3679        for i in 0..1024 {
3680            v.insert(i, true);
3681            v.remove(i);
3682        }
3683
3684        for (i, result) in v.into_iter().enumerate() {
3685            assert_eq!(result, i % 11 < 7);
3686        }
3687    }
3688
3689    #[test]
3690    fn test_remove_last() {
3691        let mut v = BitVec::from_fn(1025, |i| i % 11 < 7);
3692        assert_eq!(v.len(), 1025);
3693        assert_eq!(v.remove(1024), 1024 % 11 < 7);
3694        assert_eq!(v.len(), 1024);
3695        assert_eq!(v.storage().len(), 1024 / 32);
3696    }
3697
3698    #[test]
3699    fn test_remove_all() {
3700        let v = BitVec::from_elem(1024, false);
3701        for _ in 0..1024 {
3702            let mut v2 = v.clone();
3703            v2.remove_all();
3704            assert_eq!(v2.len(), 0);
3705            assert_eq!(v2.get(0), None);
3706            assert_eq!(v2, BitVec::new());
3707        }
3708    }
3709
3710    #[test]
3711    fn test_bitwise_ops_change() {
3712        for len in 0..256 {
3713            let mut a = BitVec::from_elem(len, false);
3714            let mut b = BitVec::from_elem(len, true);
3715            if len == 0 {
3716                assert!(!a.or(&b));
3717                assert!(!a.nor(&b));
3718                assert!(!a.xor(&b));
3719                assert!(!a.xnor(&b));
3720                assert!(!a.nand(&b));
3721                assert!(!a.and(&b));
3722            } else {
3723                assert!(a.or(&b));
3724                a.fill(false);
3725                assert!(!b.or(&a));
3726                b.fill(true);
3727                assert!(!a.nor(&b));
3728                a.fill(false);
3729                assert!(b.nor(&a));
3730                b.fill(true);
3731                assert!(a.xor(&b));
3732                a.fill(false);
3733                assert!(!b.xor(&a));
3734                b.fill(true);
3735                assert!(!a.xnor(&b));
3736                a.fill(false);
3737                assert!(b.xnor(&a));
3738                b.fill(true);
3739                assert!(a.nand(&b));
3740
3741                let b = BitVec::from_elem(len, false);
3742
3743                let mut a = BitVec::from_elem(len, false);
3744                assert!(a.nor(&b));
3745                assert_eq!(a, BitVec::from_elem(len, true));
3746
3747                let mut a = BitVec::from_elem(len, false);
3748                assert!(a.xnor(&b));
3749                assert_eq!(a, BitVec::from_elem(len, true));
3750            }
3751        }
3752    }
3753}