fastbit 0.11.1

//! A module providing non-owning views into bit arrays.
//!
//! This module contains types that provide read-only and mutable views into
//! existing bit arrays. These views can represent a subset of bits from the
//! original array, allowing for efficient operations on specific ranges of bits
//! without copying or allocating new memory.
//!
//! # Safety
//!
//! `BitSpan` and `BitSpanMut` use raw pointers internally for efficiency. Users
//! must ensure that:
//!
//! - The referenced memory remains valid for the lifetime of the span
//! - For `BitSpanMut`, the memory is not accessed through other mutable references
//!   during the span's lifetime (to avoid aliasing violations)
//! - The offset and length parameters don't cause out-of-bounds access
//!
//! # Examples
//!
//! ```
//! # use fastbit::{BitSpan, BitRead, BitWrite, BitSpanMut};
//! # use std::ptr::NonNull;
//! // Create a buffer to hold our bits
//! let mut data = [0u64; 2];
//!
//! // Create a read-only view of the first 10 bits
//! let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 10);
//! assert_eq!(span.count_ones(), 0);
//!
//! // Create a mutable view of the same bits
//! let mut span_mut = BitSpanMut::from_raw_parts_mut(data.as_mut_ptr(), 0, 10);
//! span_mut.set(3); // Set the 4th bit
//! span_mut.set(7); // Set the 8th bit
//!
//! // Create a read-only view again to check our changes
//! let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 10);
//! assert_eq!(span.count_ones(), 2);
//! assert!(span.test(3));
//! assert!(span.test(7));
//! ```

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

use crate::{
    BitRead, Iter,
    traits::{BitWord, BitWrite},
};

/// A non-owning read-only view into a bit array.
///
/// `BitSpan` provides a view into a sequence of bits stored in memory, allowing
/// read-only access to individual bits or ranges of bits. It can be used to
/// efficiently operate on a subset of bits without copying or allocating memory.
///
/// The span is defined by:
/// - A pointer to the start of the word array
/// - A bit offset from the start of the first word
/// - A length in bits
///
/// # Safety
///
/// This type uses raw pointers internally. The caller must ensure that:
/// - The referenced memory remains valid for the lifetime of the span
/// - The offset and length parameters don't cause out-of-bounds access
pub struct BitSpan<'a, T: BitWord> {
    ptr: NonNull<T>,
    offset: usize,
    len: usize,
    _marker: PhantomData<&'a T>,
}

/// A non-owning mutable view into a bit array.
///
/// `BitSpanMut` provides a view into a sequence of bits stored in memory, allowing
/// both reading and writing of individual bits or ranges of bits. It can be used to
/// efficiently operate on a subset of bits without copying or allocating memory.
///
/// The span is defined by:
/// - A pointer to the start of the word array
/// - A bit offset from the start of the first word
/// - A length in bits
///
/// # Safety
///
/// This type uses raw pointers internally. The caller must ensure that:
/// - The referenced memory remains valid for the lifetime of the span
/// - No other references (mutable or immutable) to the same memory are used
///   during the lifetime of the span to avoid aliasing violations
/// - The offset and length parameters don't cause out-of-bounds access
pub struct BitSpanMut<'a, T: BitWord> {
    ptr: NonNull<T>,
    offset: usize,
    len: usize,
    _marker: PhantomData<&'a mut T>,
}

impl<'a, T: BitWord> BitSpan<'a, T> {
    /// Creates a new `BitSpan` from the given parameters.
    ///
    /// This is a crate-internal constructor used by other data structures
    /// to create spans into their storage.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A non-null pointer to the word array
    /// * `offset` - The bit offset from the start of the first word
    /// * `len` - The number of bits in the span
    pub(crate) fn new(ptr: NonNull<T>, offset: usize, len: usize) -> Self {
        Self {
            ptr,
            offset,
            len,
            _marker: PhantomData,
        }
    }

    /// Creates a new `BitSpan` from raw parts.
    ///
    /// This function allows creating a span directly from a raw pointer,
    /// which is useful for interfacing with external memory or creating
    /// views into existing bit arrays.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A pointer to the word array (will be converted to non-null)
    /// * `offset` - The bit offset from the start of the first word
    /// * `len` - The number of bits in the span
    ///
    /// # Safety
    ///
    /// The caller must ensure that:
    /// - The pointer is valid for reads of `len` bits starting at `offset`
    /// - The memory remains valid for the lifetime of the returned span
    ///
    /// If `ptr` is null, a dangling pointer will be used. This is safe as long
    /// as `len` is 0, but will lead to undefined behavior otherwise.
    pub fn from_raw_parts(ptr: *const T, offset: usize, len: usize) -> Self {
        Self {
            ptr: NonNull::new(ptr as *mut T).unwrap_or(NonNull::dangling()),
            offset,
            len,
            _marker: PhantomData,
        }
    }
}

/// An iterator over the set bits in a `BitSpan` or `BitSpanMut`.
///
/// This iterator yields the indices of all bits that are set to 1
/// within the span, in ascending order.
pub struct BitSpanIter<'a, T: BitWord> {
    /// The starting bit offset of the span
    ///
    /// This is added to each index returned by the underlying iterator
    /// to convert from span-relative to absolute bit indices.
    offset: usize,

    /// The underlying iterator over the word array
    iter: Iter<'a, T>,
}

impl<'a, T: BitWord> Iterator for BitSpanIter<'a, T> {
    /// The type of items yielded by this iterator.
    type Item = usize;

    /// Advances the iterator and returns the next bit index.
    ///
    /// # Returns
    ///
    /// The index of the next set bit, or `None` if there are no more set bits.
    ///
    /// # Implementation Details
    ///
    /// This method delegates to the underlying `Iter` and adds the span's
    /// offset to each returned index to convert from span-relative to
    /// absolute bit indices.
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|i| self.offset + i)
    }
}

impl<'a, T: BitWord> BitSpan<'a, T> {
    /// Calculates the pointer and bit mask for a given bit index.
    ///
    /// This is an internal helper method used by the bit manipulation methods.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit within the span
    ///
    /// # Returns
    ///
    /// A tuple containing:
    /// - A pointer to the word containing the bit
    /// - A mask with only the target bit set
    ///
    /// # Safety
    ///
    /// This method performs pointer arithmetic and assumes that `idx` is within bounds.
    /// The caller must ensure that `idx < self.len`.
    #[inline(always)]
    fn ptr_and_mask(&self, idx: usize) -> (*const T, T) {
        let bit_idx = self.offset + idx;
        let word_idx = bit_idx / usize::BITS as usize;
        let bit_in_word = bit_idx % usize::BITS as usize;
        let ptr = unsafe { self.ptr.as_ptr().add(word_idx) };
        let mask = T::from(1) << bit_in_word;
        (ptr, mask)
    }
}

impl<'a, T: BitWord> BitRead for BitSpan<'a, T> {
    /// The iterator type returned by the `iter` method.
    type Iter<'b>
        = BitSpanIter<'b, T>
    where
        Self: 'b;

    /// Returns the number of bits in the span.
    fn len(&self) -> usize {
        self.len
    }

    /// Returns true if the span is empty or contains no set bits.
    ///
    /// This implementation considers a span empty if either:
    /// - It has zero length
    /// - It has no bits set to 1
    fn is_empty(&self) -> bool {
        self.len == 0 || self.count_ones() == 0
    }

    /// Tests if the bit at the given index is set.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Returns
    ///
    /// `true` if the bit is set, `false` otherwise
    ///
    /// # Panics
    ///
    /// Panics if `idx` is out of bounds (>= `self.len`).
    fn test(&self, idx: usize) -> bool {
        assert!(idx < self.len, "index out of bounds");
        let (ptr, mask) = self.ptr_and_mask(idx);
        unsafe { (*ptr & mask) != T::from(0) }
    }

    /// Counts the number of bits set to 1 in the span.
    ///
    /// # Returns
    ///
    /// The number of bits set to 1
    fn count_ones(&self) -> usize {
        let mut count = 0;
        for i in 0..self.len {
            if self.test(i) {
                count += 1;
            }
        }
        count
    }

    /// Returns true if all bits in the span are set to 1.
    ///
    /// # Returns
    ///
    /// `true` if the span is non-empty and all bits are set to 1,
    /// `false` otherwise
    fn all(&self) -> bool {
        self.len > 0 && self.count_ones() == self.len
    }

    /// Returns true if any bit in the span is set to 1.
    ///
    /// # Returns
    ///
    /// `true` if at least one bit is set to 1, `false` otherwise
    fn any(&self) -> bool {
        self.count_ones() > 0
    }

    /// Returns an iterator over the indices of bits set to 1.
    ///
    /// # Returns
    ///
    /// An iterator that yields the indices of all bits set to 1
    /// in ascending order
    fn iter(&self) -> Self::Iter<'_> {
        BitSpanIter {
            offset: self.offset,
            iter: Iter::from_raw_parts(self.ptr.as_ptr(), self.len),
        }
    }
}

impl<'a, T: BitWord> BitSpanMut<'a, T> {
    /// Creates a new `BitSpanMut` from the given parameters.
    ///
    /// This is a crate-internal constructor used by other data structures
    /// to create mutable spans into their storage.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A non-null pointer to the word array
    /// * `offset` - The bit offset from the start of the first word
    /// * `len` - The number of bits in the span
    pub(crate) fn new(ptr: NonNull<T>, offset: usize, len: usize) -> Self {
        Self {
            ptr,
            offset,
            len,
            _marker: PhantomData,
        }
    }

    /// Creates a new `BitSpanMut` from raw parts.
    ///
    /// This function allows creating a mutable span directly from a raw pointer,
    /// which is useful for interfacing with external memory or creating
    /// mutable views into existing bit arrays.
    ///
    /// # Arguments
    ///
    /// * `ptr` - A mutable pointer to the word array (will be converted to non-null)
    /// * `offset` - The bit offset from the start of the first word
    /// * `len` - The number of bits in the span
    ///
    /// # Safety
    ///
    /// The caller must ensure that:
    /// - The pointer is valid for reads and writes of `len` bits starting at `offset`
    /// - The memory remains valid for the lifetime of the returned span
    /// - No other references to the same memory are used during the lifetime of the span
    ///
    /// If `ptr` is null, a dangling pointer will be used. This is safe as long
    /// as `len` is 0, but will lead to undefined behavior otherwise.
    pub fn from_raw_parts_mut(ptr: *mut T, offset: usize, len: usize) -> Self {
        Self {
            ptr: NonNull::new(ptr).unwrap_or(NonNull::dangling()),
            offset,
            len,
            _marker: PhantomData,
        }
    }

    /// Calculates the pointer and bit mask for a given bit index.
    ///
    /// This is an internal helper method used by the bit manipulation methods.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit within the span
    ///
    /// # Returns
    ///
    /// A tuple containing:
    /// - A mutable pointer to the word containing the bit
    /// - A mask with only the target bit set
    ///
    /// # Safety
    ///
    /// This method performs pointer arithmetic and assumes that `idx` is within bounds.
    /// The caller must ensure that `idx < self.len`.
    #[inline(always)]
    fn ptr_and_mask(&self, idx: usize) -> (*mut T, T) {
        let bit_idx = self.offset + idx;
        let word_idx = bit_idx / usize::BITS as usize;
        let bit_in_word = bit_idx % usize::BITS as usize;
        let ptr = unsafe { self.ptr.as_ptr().add(word_idx) };
        let mask = T::from(1) << bit_in_word;
        (ptr, mask)
    }
}

impl<'a, T: BitWord> BitRead for BitSpanMut<'a, T> {
    /// The iterator type returned by the `iter` method.
    type Iter<'b>
        = BitSpanIter<'b, T>
    where
        Self: 'b;

    /// Returns the number of bits in the span.
    fn len(&self) -> usize {
        self.len
    }

    /// Returns true if the span is empty or contains no set bits.
    ///
    /// This implementation considers a span empty if either:
    /// - It has zero length
    /// - It has no bits set to 1
    fn is_empty(&self) -> bool {
        self.len == 0 || self.count_ones() == 0
    }

    /// Tests if the bit at the given index is set.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Returns
    ///
    /// `true` if the bit is set, `false` otherwise
    ///
    /// # Panics
    ///
    /// Debug builds will assert if `idx` is out of bounds (>= `self.len`).
    fn test(&self, idx: usize) -> bool {
        debug_assert!(idx < self.len, "index out of bounds");
        let (ptr, mask) = self.ptr_and_mask(idx);
        unsafe { (*ptr & mask) != T::from(0) }
    }

    /// Counts the number of bits set to 1 in the span.
    ///
    /// # Returns
    ///
    /// The number of bits set to 1
    fn count_ones(&self) -> usize {
        let mut count = 0;
        for i in 0..self.len {
            if self.test(i) {
                count += 1;
            }
        }
        count
    }

    /// Returns true if all bits in the span are set to 1.
    ///
    /// # Returns
    ///
    /// `true` if the span is non-empty and all bits are set to 1,
    /// `false` otherwise
    fn all(&self) -> bool {
        self.len > 0 && self.count_ones() == self.len
    }

    /// Returns true if any bit in the span is set to 1.
    ///
    /// # Returns
    ///
    /// `true` if at least one bit is set to 1, `false` otherwise
    fn any(&self) -> bool {
        self.count_ones() > 0
    }

    /// Returns an iterator over the indices of bits set to 1.
    ///
    /// # Returns
    ///
    /// An iterator that yields the indices of all bits set to 1
    /// in ascending order
    fn iter(&self) -> Self::Iter<'_> {
        BitSpanIter {
            offset: self.offset,
            iter: Iter::from_raw_parts(self.ptr.as_ptr(), self.len),
        }
    }
}

impl<'a, T: BitWord> BitWrite for BitSpanMut<'a, T> {
    /// Sets the bit at the given index to 1.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to set
    ///
    /// # Panics
    ///
    /// Debug builds will assert if `idx` is out of bounds (>= `self.len`).
    fn set(&mut self, idx: usize) {
        debug_assert!(idx < self.len, "index out of bounds");
        let (ptr, mask) = self.ptr_and_mask(idx);
        unsafe {
            *ptr |= mask;
        }
    }

    /// Sets the bit at the given index to 0.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to clear
    ///
    /// # Panics
    ///
    /// Debug builds will assert if `idx` is out of bounds (>= `self.len`).
    fn reset(&mut self, idx: usize) {
        debug_assert!(idx < self.len, "index out of bounds");
        let (ptr, mask) = self.ptr_and_mask(idx);
        unsafe {
            *ptr &= !mask;
        }
    }

    /// Flips the bit at the given 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`).
    fn flip(&mut self, idx: usize) {
        assert!(idx < self.len);
        let (ptr, mask) = self.ptr_and_mask(idx);
        unsafe {
            *ptr ^= mask;
        }
    }

    /// Sets the bit at the given index to 1 and returns the previous value.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to set
    ///
    /// # Returns
    ///
    /// `true` if the bit was already set, `false` otherwise
    ///
    /// # Panics
    ///
    /// Debug builds will assert if `idx` is out of bounds (>= `self.len`).
    fn test_and_set(&mut self, idx: usize) -> bool {
        debug_assert!(idx < self.len, "index out of bounds");
        let (ptr, mask) = self.ptr_and_mask(idx);
        unsafe {
            let old = *ptr & mask;
            *ptr |= mask;
            old != T::from(0)
        }
    }

    /// Sets all bits in the span to 1.
    ///
    /// This method efficiently sets all bits within the span's range to 1,
    /// taking care to only modify bits that are part of the span.
    fn fill(&mut self) {
        if self.len == 0 {
            return;
        }
        let start_bit = self.offset;
        let end_bit = self.offset + self.len;
        let start_word = start_bit / usize::BITS as usize;
        let end_word = (end_bit + usize::BITS as usize - 1) / usize::BITS as usize;
        let first_bit = start_bit % usize::BITS as usize;
        let last_bit = (end_bit - 1) % usize::BITS as usize;

        for word_idx in start_word..end_word {
            let ptr = unsafe { self.ptr.as_ptr().add(word_idx) as *mut usize };
            let mut mask = usize::MAX;
            if word_idx == start_word {
                mask &= usize::MAX << first_bit;
            }
            if word_idx == end_word - 1 {
                mask &= usize::MAX >> (usize::BITS as usize - 1 - last_bit);
            }
            unsafe {
                *ptr |= mask;
            }
        }
    }

    /// Sets all bits in the span to 0.
    ///
    /// This method efficiently clears all bits within the span's range,
    /// taking care to only modify bits that are part of the span.
    fn clear(&mut self) {
        if self.len == 0 {
            return;
        }
        let start_bit = self.offset;
        let end_bit = self.offset + self.len;
        let start_word = start_bit / usize::BITS as usize;
        let end_word = (end_bit + usize::BITS as usize - 1) / usize::BITS as usize;
        let first_bit = start_bit % usize::BITS as usize;
        let last_bit = (end_bit - 1) % usize::BITS as usize;

        for word_idx in start_word..end_word {
            let ptr = unsafe { self.ptr.as_ptr().add(word_idx) as *mut usize };
            let mut mask = usize::MAX;
            if word_idx == start_word {
                mask &= usize::MAX << first_bit;
            }
            if word_idx == end_word - 1 {
                mask &= usize::MAX >> (usize::BITS as usize - 1 - last_bit);
            }
            unsafe {
                *ptr &= !mask;
            }
        }
    }
}

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

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

impl<'a, 'b, T: BitWord> BitXorAssign<&'b BitSpan<'b, T>> for BitSpanMut<'a, T> {
    fn bitxor_assign(&mut self, rhs: &'b BitSpan<'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::*;

    #[test]
    fn test_bitspan_from_raw_parts_and_test() {
        let data = [0b10101010usize, 0b01010101usize];
        let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 128);
        assert_eq!(span.len(), 128);
        assert!(!span.test(0));
        assert!(span.test(1));
        assert!(!span.test(2));
        assert!(span.test(3));
    }

    #[test]
    fn test_bitspan_iter() {
        let data = [0b1011usize];
        let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 4);
        let bits: Vec<_> = span.iter().collect();
        assert_eq!(bits, vec![0, 1, 3]);
    }

    #[test]
    fn test_bitspan_count_ones_and_any_all() {
        let data = [0b1111usize];
        let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 4);
        assert_eq!(span.count_ones(), 4);
        assert!(span.all());
        assert!(span.any());

        let data = [0usize];
        let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 4);
        assert_eq!(span.count_ones(), 0);
        assert!(!span.all());
        assert!(!span.any());
    }

    #[test]
    fn test_bitspanmut_set_reset_test_and_set() {
        let mut data = [0usize];
        let mut span = BitSpanMut::from_raw_parts_mut(data.as_mut_ptr(), 0, 4);

        for i in 0..4 {
            assert!(!span.test(i));
            span.set(i);
            assert!(span.test(i));
            assert!(span.test_and_set(i)); // already set
            span.reset(i);
            assert!(!span.test(i));
            assert!(!span.test_and_set(i)); // was not set
        }
    }

    #[test]
    fn test_bitspanmut_fill_and_clear() {
        let mut data = [0usize; 2];
        let mut span =
            BitSpanMut::from_raw_parts_mut(data.as_mut_ptr(), 0, 2 * usize::BITS as usize);

        span.fill();
        for i in 0..span.len() {
            assert!(span.test(i));
        }
        span.clear();
        for i in 0..span.len() {
            assert!(!span.test(i));
        }
    }

    #[test]
    fn test_bitspanmut_partial_fill_and_clear() {
        let mut data = [0usize; 2];
        let mut span = BitSpanMut::from_raw_parts_mut(data.as_mut_ptr(), 5, 10);
        span.fill();
        for i in 0..span.len() {
            assert!(span.test(i));
        }
        // bits outside the span should remain zero
        for i in 0..5 {
            assert!(!unsafe { (*data.as_ptr() & (1 << i)) != 0 });
        }
        span.clear();
        for i in 0..span.len() {
            assert!(!span.test(i));
        }
    }

    #[test]
    fn test_empty_bitspan() {
        let data = [0usize];
        let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 0);
        assert_eq!(span.len(), 0);
        assert!(span.is_empty());
        assert_eq!(span.count_ones(), 0);
        assert!(!span.any());
        assert!(!span.all());
        assert_eq!(span.iter().count(), 0);
    }

    #[test]
    #[should_panic(expected = "index out of bounds")]
    fn test_bitspan_test_out_of_bounds() {
        let data = [0usize];
        let span = BitSpan::from_raw_parts(data.as_ptr(), 0, 1);
        span.test(1);
    }

    #[test]
    #[should_panic(expected = "index out of bounds")]
    fn test_bitspanmut_set_out_of_bounds() {
        let mut data = [0usize];
        let mut span = BitSpanMut::from_raw_parts_mut(data.as_mut_ptr(), 0, 1);
        span.set(1);
    }
}