fastbit 0.11.1

use crate::iter::Iter;
use crate::traits::{BitWord, BitWrite};
use crate::util::{
    bitset_all, bitset_any, bitset_clear, bitset_count_ones, bitset_fill, bitset_flip, bitset_free,
    bitset_is_empty, bitset_new, bitset_new_uninit, bitset_reset, bitset_resize, bitset_set,
    bitset_test, bitset_test_and_set,
};
use crate::{BitRead, BitSpan, BitSpanMut, BitView, BitViewMut};
use std::fmt::Debug;
use std::ptr::NonNull;

/// A growable, heap-allocated bit vector.
///
/// `BitVec` provides a contiguous growable array of bits, similar to `Vec<bool>`, but much more efficient.
/// The underlying storage is a raw pointer to a bitset, and the length and capacity are tracked in bits.
pub struct BitVec<W: BitWord> {
    ptr: NonNull<W>,
    len: usize,
    cap: usize, // number of bits allocated
}

/// Implements the `Debug` trait for `BitFixed`.
///
/// This provides a human-readable representation of the bitset for debugging.
impl<T: Debug + BitWord> std::fmt::Debug for BitVec<T> {
    /// Formats the bitset for debugging.
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let store = unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.cap / T::BITS) };
        f.debug_struct("BitFixed")
            .field("len", &self.len)
            .field("cap", &self.cap)
            .field("store", &store)
            .finish()
    }
}

impl<W: BitWord> BitVec<W> {
    /// Creates a new, uninitialized bit vector with the given number of bits.
    ///
    /// # Arguments
    ///
    /// * `bit_len` - The number of bits to allocate.
    ///
    /// # Safety
    ///
    /// The bits are uninitialized and may contain garbage values.
    pub fn new_uninit(bit_len: usize) -> Self {
        let (ptr, cap) = unsafe { bitset_new_uninit(bit_len) };
        Self {
            ptr,
            len: bit_len,
            cap,
        }
    }

    /// Creates a new, zero-initialized bit vector with the given number of bits.
    ///
    /// # Arguments
    ///
    /// * `bit_len` - The number of bits to allocate.
    pub fn new(bit_len: usize) -> Self {
        let (ptr, cap) = unsafe { bitset_new(bit_len) };
        Self {
            ptr,
            len: bit_len,
            cap,
        }
    }

    /// Resizes the bit vector to the new length in bits.
    ///
    /// If the new length is greater than the current length, new bits are zero-initialized.
    /// If the new length is less, excess bits are dropped.
    ///
    /// # Arguments
    ///
    /// * `new_bit_len` - The new length in bits.
    pub fn resize(&mut self, new_bit_len: usize) {
        let (ptr, cap) = unsafe { bitset_resize(self.ptr, self.len, new_bit_len) };
        self.ptr = ptr;
        self.cap = cap;
        self.len = new_bit_len;
    }

    /// Returns an iterator over the bits of the vector.
    #[inline]
    pub fn iter(&self) -> Iter<W> {
        Iter::new(self.ptr, self.len)
    }

    /// Returns a read-only view of the bit vector.
    #[inline]
    pub fn as_view(&self) -> BitView<'_, W> {
        BitView::new(self.ptr, self.len)
    }

    /// Returns a mutable view of the bit vector.
    #[inline]
    pub fn as_view_mut(&self) -> BitViewMut<'_, W> {
        BitViewMut::new(self.ptr, self.len)
    }

    /// Returns a slice of the bit vector as a `BitSpan`.
    ///
    /// # Arguments
    ///
    /// * `offset` - The starting bit index.
    /// * `len` - The number of bits in the slice.
    #[inline]
    pub fn slice(&self, offset: usize, len: usize) -> BitSpan<W> {
        BitSpan::new(self.ptr, offset, len)
    }

    #[inline]
    pub fn slice_mut(&self, offset: usize, len: usize) -> BitSpanMut<W> {
        BitSpanMut::new(self.ptr, offset, len)
    }
}

impl<W: BitWord> Drop for BitVec<W> {
    fn drop(&mut self) {
        unsafe { bitset_free(self.ptr, self.len) };
    }
}

crate::macros::impl_bitset_traits!(BitVec);
crate::macros::impl_bitsetmut_traits!(BitVec);

#[cfg(feature = "serde_support")]
impl<W: BitWord + serde::Serialize> serde::Serialize for BitVec<W> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        use serde::ser::SerializeStruct;

        // Create a struct with two fields: data and length
        let mut state = serializer.serialize_struct("BitVec", 2)?;

        // Serialize the data as a slice of words
        let word_len = (self.len + W::BITS - 1) / W::BITS;
        let data_slice = unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), word_len) };
        state.serialize_field("data", data_slice)?;

        // Serialize the length in bits
        state.serialize_field("len", &self.len)?;

        state.end()
    }
}

#[cfg(feature = "serde_support")]
impl<'de, W: BitWord + serde::Serialize + serde::Deserialize<'de>> serde::Deserialize<'de>
    for BitVec<W>
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        use serde::de::{self, MapAccess, SeqAccess, Visitor};
        use std::fmt;
        use std::marker::PhantomData;

        struct BitVecVisitor<W> {
            marker: PhantomData<W>,
        }

        impl<'de, W: BitWord + serde::Serialize + serde::Deserialize<'de>> Visitor<'de>
            for BitVecVisitor<W>
        {
            type Value = BitVec<W>;

            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
                formatter.write_str("a BitVec struct")
            }

            fn visit_map<V>(self, mut map: V) -> Result<BitVec<W>, V::Error>
            where
                V: MapAccess<'de>,
            {
                let mut data: Option<Vec<W>> = None;
                let mut len: Option<usize> = None;

                while let Some(key) = map.next_key::<String>()? {
                    match key.as_str() {
                        "data" => {
                            if data.is_some() {
                                return Err(de::Error::duplicate_field("data"));
                            }
                            data = Some(map.next_value()?);
                        }
                        "len" => {
                            if len.is_some() {
                                return Err(de::Error::duplicate_field("len"));
                            }
                            len = Some(map.next_value()?);
                        }
                        _ => {
                            return Err(de::Error::unknown_field(&key, &["data", "len"]));
                        }
                    }
                }

                let data = data.ok_or_else(|| de::Error::missing_field("data"))?;
                let len = len.ok_or_else(|| de::Error::missing_field("len"))?;

                // Create a new BitVec and copy the data
                let mut bv = BitVec::new(len);
                let word_len = (len + W::BITS - 1) / W::BITS;

                if data.len() < word_len {
                    return Err(de::Error::custom(
                        "data length is too short for the specified bit length",
                    ));
                }

                unsafe {
                    std::ptr::copy_nonoverlapping(data.as_ptr(), bv.ptr.as_ptr(), word_len);
                }

                Ok(bv)
            }
        }

        deserializer.deserialize_map(BitVecVisitor {
            marker: PhantomData,
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_debug() {
        let mut bv: BitVec<u16> = BitVec::new(60);
        bv.set(1);
        bv.set(17);
        bv.set(27);
        bv.set(47);
        assert_eq!(
            format!("{bv:?}"),
            "BitFixed { len: 60, cap: 64, store: [2, 2050, 32768, 0] }"
        );
    }

    #[test]
    fn test_new_and_len() {
        let bv: BitVec<u8> = BitVec::new(10);
        assert_eq!(bv.len(), 10);
        assert!(bv.is_empty());
        let bv0: BitVec<u16> = BitVec::new(0);
        assert_eq!(bv0.len(), 0);
        assert!(bv0.is_empty());
        let mut iter = bv.iter();
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_set_and_test() {
        let mut bv: BitVec<u32> = BitVec::new(8);
        for i in 0..8 {
            assert!(!bv.test(i));
            bv.set(i);
            assert!(bv.test(i));
        }
    }

    #[test]
    fn test_reset() {
        let mut bv: BitVec<u64> = BitVec::new(8);
        for i in 0..8 {
            bv.set(i);
        }
        for i in 0..8 {
            bv.reset(i);
            assert!(!bv.test(i));
        }
    }

    #[test]
    fn test_test_and_set() {
        let mut bv: BitVec<usize> = BitVec::new(4);
        assert!(!bv.test_and_set(2));
        assert!(bv.test_and_set(2));
        assert!(bv.test(2));
    }

    #[test]
    fn test_fill_and_clear() {
        let mut bv: BitVec<u8> = BitVec::new(10);
        bv.fill();
        for i in 0..10 {
            assert!(bv.test(i));
        }
        bv.clear();
        for i in 0..10 {
            assert!(!bv.test(i));
        }
    }

    #[test]
    fn test_count_ones() {
        let mut bv: BitVec<u16> = BitVec::new(16);
        assert_eq!(bv.count_ones(), 0);
        bv.set(0);
        bv.set(3);
        bv.set(15);
        assert_eq!(bv.count_ones(), 3);
        bv.fill();
        assert_eq!(bv.count_ones(), 16);
        bv.clear();
        assert_eq!(bv.count_ones(), 0);
    }

    #[test]
    fn test_all_and_any() {
        let mut bv: BitVec<u32> = BitVec::new(5);
        assert!(!bv.all());
        assert!(!bv.any());
        bv.set(0);
        assert!(!bv.all());
        assert!(bv.any());
        bv.fill();
        assert!(bv.all());
        bv.reset(2);
        assert!(!bv.all());
        assert!(bv.any());
        bv.clear();
        assert!(!bv.any());
    }

    #[test]
    fn test_resize_grow_and_shrink() {
        let mut bv: BitVec<u64> = BitVec::new(4);
        bv.set(1);
        bv.resize(8);
        assert!(bv.test(1));
        bv.set(7);
        assert!(bv.test(7));
        bv.resize(2);
        assert_eq!(bv.len(), 2);
        assert!(bv.test(1));
    }

    #[test]
    fn test_zero_len() {
        let mut bv: BitVec<usize> = BitVec::new(0);
        assert_eq!(bv.len(), 0);
        assert!(bv.is_empty());
        bv.resize(0);
        assert_eq!(bv.len(), 0);
    }
}