fastbit 0.11.1

use std::{
    marker::PhantomData,
    ops::{BitAndAssign, BitOrAssign, BitXorAssign},
    ptr::NonNull,
};

use crate::{
    BitRead, Iter,
    traits::{BitWord, BitWrite},
    util::{
        bitset_all, bitset_any, bitset_clear, bitset_count_ones, bitset_fill, bitset_flip,
        bitset_reset, bitset_set, bitset_test, bitset_test_and_set,
    },
};

/// A read-only view into a bit set stored in memory.
///
/// `BitView` provides a safe interface for accessing bits in an existing memory region
/// without taking ownership of the underlying data. It's similar to a slice (`&[T]`) but
/// operates at the bit level rather than the element level.
///
/// The view is parameterized by:
/// - A lifetime `'a` that ties it to the lifetime of the referenced data
/// - A word type `T` that implements the `BitWord` trait, which defines the storage unit
///
/// # Safety
///
/// This type uses raw pointers internally and relies on the caller to ensure:
/// - The pointer is valid for the entire lifetime `'a`
/// - The pointer points to a properly aligned instance of `T`
/// - The memory region contains at least enough bits to cover the specified length
/// - The memory is not mutated through other references while this view exists
///
/// # Examples
///
/// ```
/// use fastbit::BitView;
/// use fastbit::BitRead;
///
/// // Create a bit pattern in a byte array
/// let data: [u8; 2] = [0b10101010, 0b01010101];
///
/// // Create a BitView over the data (unsafe because we're working with raw pointers)
/// let view = unsafe { BitView::from_raw_parts(data.as_ptr(), 16) };
///
/// // Now we can safely read bits
/// assert!(!view.test(0));
/// assert!(view.test(1));
/// assert_eq!(view.count_ones(), 8);
/// ```
pub struct BitView<'a, T: BitWord> {
    ptr: NonNull<T>,
    len: usize,
    _marker: PhantomData<&'a T>,
}

/// A mutable view into a bit set stored in memory.
///
/// `BitViewMut` provides a safe interface for accessing and modifying bits in an existing memory region
/// without taking ownership of the underlying data. It's similar to a mutable slice (`&mut [T]`) but
/// operates at the bit level rather than the element level.
///
/// The view is parameterized by:
/// - A lifetime `'a` that ties it to the lifetime of the referenced data
/// - A word type `T` that implements the `BitWord` trait, which defines the storage unit
///
/// # Safety
///
/// This type uses raw pointers internally and relies on the caller to ensure:
/// - The pointer is valid for the entire lifetime `'a`
/// - The pointer points to a properly aligned instance of `T`
/// - The memory region contains at least enough bits to cover the specified length
/// - The memory is not mutated through other references while this view exists
/// - The caller has exclusive access to the memory region for the duration of the view
///
/// # Examples
///
/// ```
/// use fastbit::{BitViewMut, BitRead, BitWrite};
///
/// // Create a mutable bit pattern in a byte array
/// let mut data: [u8; 2] = [0b10101010, 0b01010101];
///
/// // Create a BitViewMut over the data (unsafe because we're working with raw pointers)
/// let mut view = unsafe { BitViewMut::from_raw_parts(data.as_mut_ptr(), 16) };
///
/// // Now we can safely read and modify bits
/// assert!(!view.test(0));
/// view.set(0);
/// assert!(view.test(0));
/// view.clear();
/// assert_eq!(view.count_ones(), 0);
/// ```
pub struct BitViewMut<'a, T: BitWord> {
    ptr: NonNull<T>,
    len: usize,
    _marker: PhantomData<&'a mut T>,
}

impl<'a, T: BitWord> BitViewMut<'a, T> {
    /// Creates a new `BitViewMut` from a non-null pointer and length.
    ///
    /// This is a crate-internal constructor used by other data structures.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A non-null pointer to the start of the bit storage
    /// * `len` - The number of bits in the view
    #[inline]
    pub(crate) fn new(ptr: NonNull<T>, len: usize) -> Self {
        Self {
            ptr,
            len,
            _marker: PhantomData,
        }
    }

    /// Creates a new `BitViewMut` from raw parts.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A pointer to the start of the bit storage
    /// * `len` - The number of bits in the view
    ///
    /// # Safety
    ///
    /// The caller must ensure:
    /// - The pointer is valid for reads and writes for the entire lifetime `'a`
    /// - The pointer points to a properly aligned instance of `T`
    /// - The memory region contains at least enough bits to cover the specified length
    /// - The caller has exclusive access to the memory region for the duration of the view
    #[inline]
    pub unsafe fn from_raw_parts(ptr: *const T, len: usize) -> Self {
        Self {
            ptr: NonNull::new(ptr as *mut T).unwrap(),
            len,
            _marker: PhantomData,
        }
    }
}

impl<'a, T: BitWord> BitView<'a, T> {
    /// Creates a new `BitView` from a non-null pointer and length.
    ///
    /// This is a crate-internal constructor used by other data structures.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A non-null pointer to the start of the bit storage
    /// * `len` - The number of bits in the view
    #[inline]
    pub(crate) fn new(ptr: NonNull<T>, len: usize) -> Self {
        Self {
            ptr,
            len,
            _marker: PhantomData,
        }
    }

    /// Creates a new `BitView` from raw parts.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A pointer to the start of the bit storage
    /// * `len` - The number of bits in the view
    ///
    /// # Safety
    ///
    /// The caller must ensure:
    /// - The pointer is valid for reads for the entire lifetime `'a`
    /// - The pointer points to a properly aligned instance of `T`
    /// - The memory region contains at least enough bits to cover the specified length
    /// - The memory is not mutated through other references while this view exists
    #[inline]
    pub unsafe fn from_raw_parts(ptr: *const T, len: usize) -> Self {
        Self {
            ptr: NonNull::new(ptr as *mut T).unwrap(),
            len,
            _marker: PhantomData,
        }
    }
}

impl<'a, W: BitWord> BitRead for BitView<'a, W> {
    /// The iterator type returned by the `iter` method.
    ///
    /// This iterator yields the indices of all set bits (1s) in the bit view.
    type Iter<'b>
        = Iter<'b, W>
    where
        Self: 'b;

    /// Returns the number of bits in this bit view.
    #[inline]
    fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if this bit view contains no bits.
    #[inline]
    fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Tests if the bit at the specified index is set (1).
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len()`).
    #[inline]
    fn test(&self, idx: usize) -> bool {
        unsafe { bitset_test(self.ptr, self.len, idx) }
    }

    /// Counts the number of set bits (1s) in this bit view.
    #[inline]
    fn count_ones(&self) -> usize {
        unsafe { bitset_count_ones(self.ptr, self.len) }
    }

    /// Returns `true` if all bits in this view are set (1).
    ///
    /// Returns `true` for empty bit views.
    #[inline]
    fn all(&self) -> bool {
        unsafe { bitset_all(self.ptr, self.len) }
    }

    /// Returns `true` if any bit in this view is set (1).
    ///
    /// Returns `false` for empty bit views.
    #[inline]
    fn any(&self) -> bool {
        unsafe { bitset_any(self.ptr, self.len) }
    }

    /// Returns an iterator over the indices of all set bits (1s) in this bit view.
    ///
    /// The iterator yields the indices in ascending order.
    #[inline]
    fn iter(&self) -> Self::Iter<'_> {
        Iter::from_raw_parts(self.ptr.as_ptr(), self.len)
    }
}

impl<'a, T: BitWord> BitRead for BitViewMut<'a, T> {
    /// The iterator type returned by the `iter` method.
    ///
    /// This iterator yields the indices of all set bits (1s) in the bit view.
    type Iter<'b>
        = Iter<'b, T>
    where
        Self: 'b;

    /// Returns the number of bits in this bit view.
    #[inline]
    fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if this bit view contains no bits.
    #[inline]
    fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Tests if the bit at the specified index is set (1).
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len()`).
    #[inline]
    fn test(&self, idx: usize) -> bool {
        unsafe { bitset_test(self.ptr, self.len, idx) }
    }

    /// Counts the number of set bits (1s) in this bit view.
    #[inline]
    fn count_ones(&self) -> usize {
        unsafe { bitset_count_ones(self.ptr, self.len) }
    }

    /// Returns `true` if all bits in this view are set (1).
    ///
    /// Returns `true` for empty bit views.
    #[inline]
    fn all(&self) -> bool {
        unsafe { bitset_all(self.ptr, self.len) }
    }

    /// Returns `true` if any bit in this view is set (1).
    ///
    /// Returns `false` for empty bit views.
    #[inline]
    fn any(&self) -> bool {
        unsafe { bitset_any(self.ptr, self.len) }
    }

    /// Returns an iterator over the indices of all set bits (1s) in this bit view.
    ///
    /// The iterator yields the indices in ascending order.
    #[inline]
    fn iter(&self) -> Self::Iter<'_> {
        Iter::from_raw_parts(self.ptr.as_ptr(), self.len)
    }
}

impl<'a, T: BitWord> BitWrite for BitViewMut<'a, T> {
    /// Sets the bit at the specified index to 1.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to set
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len()`).
    #[inline]
    fn set(&mut self, idx: usize) {
        unsafe { bitset_set(self.ptr, self.len, idx) };
    }

    /// Sets the bit at the specified index to 0.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to reset
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len()`).
    #[inline]
    fn reset(&mut self, idx: usize) {
        unsafe { bitset_reset(self.ptr, self.len, idx) };
    }

    /// Flips the bit at the specified index (0 becomes 1, 1 becomes 0).
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to flip
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len()`).
    #[inline]
    fn flip(&mut self, idx: usize) {
        unsafe { bitset_flip(self.ptr, self.len, idx) };
    }

    /// Tests the bit at the specified index and then sets it to 1.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test and set
    ///
    /// # Returns
    ///
    /// The previous value of the bit (true if it was 1, false if it was 0).
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len()`).
    #[inline]
    fn test_and_set(&mut self, idx: usize) -> bool {
        unsafe { bitset_test_and_set(self.ptr, self.len, idx) }
    }

    /// Sets all bits in this view to 1.
    #[inline]
    fn fill(&mut self) {
        unsafe { bitset_fill(self.ptr, self.len) };
    }

    /// Sets all bits in this view to 0.
    #[inline]
    fn clear(&mut self) {
        unsafe { bitset_clear(self.ptr, self.len) };
    }
}

impl<'a, 'b, T: BitWord> BitAndAssign<&'b BitView<'b, T>> for BitViewMut<'a, T> {
    fn bitand_assign(&mut self, rhs: &'b BitView<'b, T>) {
        for index in self.iter().collect::<Vec<_>>() {
            if !rhs.test(index) {
                self.reset(index);
            }
        }
    }
}

impl<'a, 'b, T: BitWord> BitOrAssign<&'b BitView<'b, T>> for BitViewMut<'a, T> {
    fn bitor_assign(&mut self, rhs: &'b BitView<'b, T>) {
        for index in rhs.iter() {
            self.set(index);
        }
    }
}

impl<'a, 'b, T: BitWord> BitXorAssign<&'b BitView<'b, T>> for BitViewMut<'a, T> {
    fn bitxor_assign(&mut self, rhs: &'b BitView<'b, T>) {
        for index in self.iter().collect::<Vec<_>>() {
            if rhs.test(index) {
                self.reset(index);
            }
        }
        for index in rhs.iter() {
            if self.test(index) {
                self.reset(index);
            }
        }
    }
}

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

    /// Tests basic functionality of BitView including bit testing, counting ones,
    /// and checking all/any/is_empty methods.
    #[test]
    fn test_bitview_basic() {
        let data: [u8; 2] = [0b10101010, 0b01010101];
        let bv = unsafe { BitView::from_raw_parts(data.as_ptr(), 16) };
        // Test individual bits
        assert_eq!(bv.test(0), false);
        assert_eq!(bv.test(1), true);
        assert_eq!(bv.test(2), false);
        assert_eq!(bv.test(3), true);
        assert_eq!(bv.test(8), true);
        assert_eq!(bv.test(9), false);
        // Test count_ones
        assert_eq!(bv.count_ones(), 8);
        // Test all/any/is_empty
        assert!(!bv.all());
        assert!(bv.any());
        assert!(!bv.is_empty());
    }

    /// Tests that an empty BitView (with length 0) behaves correctly:
    /// - len() returns 0
    /// - is_empty() returns true
    /// - any() returns false
    /// - all() returns true (vacuously true for empty sets)
    /// - count_ones() returns 0
    #[test]
    fn test_bitview_empty() {
        let data: [u8; 1] = [0];
        let bv = BitView {
            ptr: NonNull::new(data.as_ptr() as *const u8 as *mut u8).unwrap(),
            len: 0,
            _marker: PhantomData,
        };
        assert_eq!(bv.len(), 0);
        assert!(bv.is_empty());
        assert!(!bv.any());
        assert!(bv.all());
        assert_eq!(bv.count_ones(), 0);
    }

    /// Tests a BitView where all bits are set to 1:
    /// - all() returns true
    /// - any() returns true
    /// - count_ones() returns the total number of bits
    #[test]
    fn test_bitview_all_ones() {
        let data: [u8; 2] = [0xFF, 0xFF];
        let bv = BitView {
            ptr: NonNull::new(data.as_ptr() as *const u8 as *mut u8).unwrap(),
            len: 16,
            _marker: PhantomData,
        };
        assert!(bv.all());
        assert!(bv.any());
        assert_eq!(bv.count_ones(), 16);
    }

    /// Tests a BitView with a partial last word (not using all bits in the last storage unit).
    /// Ensures that operations correctly handle the bit length rather than the underlying storage size.
    #[test]
    fn test_bitview_partial_last_word() {
        let data: [u8; 2] = [0xFF, 0x0F]; // 0x0F = 00001111
        let bv = BitView {
            ptr: NonNull::new(data.as_ptr() as *const u8 as *mut u8).unwrap(),
            len: 12, // Only 12 bits used
            _marker: PhantomData,
        };
        assert!(bv.all());
        assert!(bv.any());
        assert_eq!(bv.count_ones(), 12);
    }

    /// Tests that the iterator correctly yields the indices of set bits in ascending order.
    #[test]
    fn test_bitview_iter() {
        let data: [u8; 1] = [0b10110010];
        let bv = BitView {
            ptr: NonNull::new(data.as_ptr() as *const u8 as *mut u8).unwrap(),
            len: 8,
            _marker: PhantomData,
        };
        let bits: Vec<_> = bv.iter().collect();
        assert_eq!(bits, vec![1, 4, 5, 7]);
    }

    /// Tests a BitView with only a single bit set, verifying:
    /// - count_ones() returns 1
    /// - test() returns true only for the set bit
    /// - test() returns false for all other bits
    #[test]
    fn test_bitview_single_bit() {
        let data: [u8; 1] = [0b00000010];
        let bv = unsafe { BitView::from_raw_parts(data.as_ptr(), 8) };
        assert_eq!(bv.count_ones(), 1);
        assert!(bv.test(1));
        for i in 0..8 {
            if i != 1 {
                assert!(!bv.test(i));
            }
        }
    }

    /// Tests a BitView with zero length (different from empty, which has storage but no bits).
    /// Verifies the same properties as test_bitview_empty.
    #[test]
    fn test_bitview_zero_bits() {
        let data: [u8; 1] = [0];
        let bv = unsafe { BitView::from_raw_parts(data.as_ptr(), 0) };
        assert_eq!(bv.len(), 0);
        assert!(bv.is_empty());
        assert!(!bv.any());
        assert!(bv.all());
        assert_eq!(bv.count_ones(), 0);
    }

    /// Tests that the iterator for an empty BitView yields no elements.
    #[test]
    fn test_bitview_iter_empty() {
        let data: [u8; 1] = [0];
        let bv = unsafe { BitView::from_raw_parts(data.as_ptr(), 0) };
        let bits: Vec<_> = bv.iter().collect();
        assert!(bits.is_empty());
    }

    /// Tests that the iterator correctly handles a BitView with a partial last word,
    /// yielding only the indices of set bits within the specified length.
    #[test]
    fn test_bitview_iter_partial_word() {
        let data: [u8; 2] = [0b11110000, 0b00001111];
        let bv = unsafe { BitView::from_raw_parts(data.as_ptr(), 12) };
        let bits: Vec<_> = bv.iter().collect();
        assert_eq!(bits, vec![4, 5, 6, 7, 8, 9, 10, 11]);
    }

    /// Tests the mutable operations of BitViewMut:
    /// - set() correctly sets bits
    /// - clear() resets all bits to 0
    #[test]
    fn test_bitview_mut() {
        let mut v = [123, 0, 1, usize::MAX];
        let len = v.len() * usize::BITS as usize - 3;
        let mut r = unsafe { BitViewMut::from_raw_parts(v.as_mut_ptr(), len) };
        r.set(0);
        r.set(1);
        r.set(7);
        assert_eq!(v, [251, 0, 1, usize::MAX]);
        r.clear();
        assert_eq!(v, [0, 0, 0, 0]);
    }
}