// (1) Be careful, most things can overflow here because the amount of bits in
//     memory can overflow `usize`.
// (2) Make sure that the underlying vector has no excess length:
//     E. g. `nbits == 16`, `storage.len() == 2` would be excess length,
//     because the last word isn't used at all. This is important because some
//     methods rely on it (for *CORRECTNESS*).
// (3) Make sure that the unused bits in the last word are zeroed out, again
//     other methods rely on it for *CORRECTNESS*.
// (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in
// `BitVec` will need to be reflected in `BitSet`.

    /// Exposes the raw block storage of this `BitVec`.
    ///
    /// # Safety
    ///
    /// Can probably cause unsafety. Only really intended for `BitSet`.
    #[inline]
    pub unsafe fn storage_mut(&mut self) -> &mut Vec<B> {
        &mut self.storage
    }

    /// Retrieves the value at index `i`, without doing bounds checking.
    ///
    /// For a safe alternative, see `get`.
    ///
    /// # Safety
    ///
    /// Calling this method with an out-of-bounds index is undefined behavior
    /// even if the resulting reference is not used.
    ///
    /// # Examples
    ///
    /// ```
    /// use bit_vec::BitVec;
    ///
    /// let bv = BitVec::from_bytes(&[0b01100000]);
    /// unsafe {
    ///     assert_eq!(bv.get_unchecked(0), false);
    ///     assert_eq!(bv.get_unchecked(1), true);
    /// }
    /// ```
    #[inline]
    pub unsafe fn get_unchecked(&self, i: usize) -> bool {
        self.ensure_invariant();
        let w = i / B::bits();
        let b = i % B::bits();
        let block = *self.storage.get_unchecked(w);
        block & (B::one() << b) != B::zero()
    }

    /// Retrieves a smart pointer to the value at index `i`, without doing bounds checking.
    ///
    /// # Safety
    ///
    /// Calling this method with out-of-bounds `index` may cause undefined behavior even when
    /// the result is not used.
    ///
    /// # Examples
    ///
    /// ```
    /// use bit_vec::BitVec;
    ///
    /// let mut bv = BitVec::from_bytes(&[0b01100000]);
    /// unsafe {
    ///     *bv.get_unchecked_mut(0) = true;
    ///     *bv.get_unchecked_mut(1) = false;
    /// }
    /// assert_eq!(bv, BitVec::from_bytes(&[0b10100000]));
    /// ```
    #[inline]
    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> MutBorrowedBit<B> {
        let value = self.get_unchecked(index);
        MutBorrowedBit {
            #[cfg(debug_assertions)]
            old_value: value,
            new_value: value,
            vec: Rc::new(RefCell::new(self)),
            index,
        }
    }

    /// Sets the number of bits that this `BitVec` considers initialized.
    ///
    /// # Safety
    ///
    /// Almost certainly can cause bad stuff. Only really intended for `BitSet`.
    #[inline]
    pub unsafe fn set_len(&mut self, len: usize) {
        self.nbits = len;
    }

    pub fn insert(&mut self, at: usize, bit: bool) {
        assert!(
            at <= self.nbits,
            "insertion index (is {at}) should be <= nbits (is {nbits})",
            nbits = self.nbits
        );

        let last_block_bits = self.nbits % B::bits();
        let block_at = at / B::bits(); // needed block
        let bit_at = at % B::bits(); // index within the block

        if last_block_bits == 0 {
            self.storage.push(B::zero());
        }

        self.nbits += 1;

        let mut carry = self.storage[block_at] >> (B::bits() - 1);
        let lsbits_mask = (B::one() << bit_at) - B::one();
        let set_bit = if bit { B::one() } else { B::zero() } << bit_at;
        self.storage[block_at] = (self.storage[block_at] & lsbits_mask)
            | ((self.storage[block_at] & !lsbits_mask) << 1)
            | set_bit;

        for block_ref in &mut self.storage[block_at + 1..] {
            let curr_carry = *block_ref >> (B::bits() - 1);
            *block_ref = *block_ref << 1 | carry;
            carry = curr_carry;
        }
    }

#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(
    feature = "borsh",
    derive(borsh::BorshDeserialize, borsh::BorshSerialize)
)]
#[cfg_attr(
    feature = "miniserde",
    derive(miniserde::Deserialize, miniserde::Serialize)
)]
#[cfg_attr(
    feature = "nanoserde",
    derive(DeBin, DeJson, DeRon, SerBin, SerJson, SerRon)
)]
pub struct BitVec<B = u32> {
    /// Internal representation of the bit vector
    storage: Vec<B>,
    /// The number of valid bits in the internal representation
    nbits: usize,
}

    /// Clears all bits in this vector.
    #[inline]
    pub fn clear(&mut self) {
        self.ensure_invariant();
        for w in &mut self.storage {
            *w = B::zero();
        }
    }

    pub fn from_bytes(bytes: &[u8]) -> Self {
        let len = bytes
            .len()
            .checked_mul(u8::bits())
            .expect("capacity overflow");
        let mut bit_vec = BitVec::with_capacity(len);
        let complete_words = bytes.len() / B::bytes();
        let extra_bytes = bytes.len() % B::bytes();

        bit_vec.nbits = len;

        for i in 0..complete_words {
            let mut accumulator = B::zero();
            for idx in 0..B::bytes() {
                accumulator |= B::from_byte(reverse_bits(bytes[i * B::bytes() + idx])) << (idx * 8)
            }
            bit_vec.storage.push(accumulator);
        }

        if extra_bytes > 0 {
            let mut last_word = B::zero();
            for (i, &byte) in bytes[complete_words * B::bytes()..].iter().enumerate() {
                last_word |= B::from_byte(reverse_bits(byte)) << (i * 8);
            }
            bit_vec.storage.push(last_word);
        }

        bit_vec
    }