fastbit 0.11.1

use crate::traits::{BitRead, BitResize, BitStack, BitWrite};
use std::fmt::Debug;

/// A sparse bit set implementation that efficiently stores indices of set bits.
///
/// `BitList` provides a space-efficient representation for sparse bit sets by only storing
/// the indices where bits are set to 1. This makes it particularly efficient for cases where
/// relatively few bits are set in a large bit space.
///
/// The implementation maintains a sorted vector of indices, enabling efficient operations like
/// testing, setting, and resetting bits through binary search. This approach trades off some
/// performance on dense bit sets for significant memory savings on sparse ones.
///
/// # Examples
///
/// ```
/// use fastbit::BitList;
/// use fastbit::{BitRead, BitWrite};
///
/// // Create a bit list with a logical length of 100 bits
/// let mut bits = BitList::new(100);
///
/// // Set some bits
/// bits.set(5);
/// bits.set(42);
/// bits.set(99);
///
/// // Test if bits are set
/// assert!(bits.test(5));
/// assert!(bits.test(42));
/// assert!(!bits.test(10));
///
/// // Count set bits
/// assert_eq!(bits.count_ones(), 3);
///
/// // Reset a bit
/// bits.reset(5);
/// assert!(!bits.test(5));
/// ```
#[derive(Debug, Hash, PartialEq, Eq)]
pub struct BitList {
    store: Vec<usize>,
    len: usize,
}

impl BitList {
    /// Creates a new empty `BitList` with the specified logical length.
    ///
    /// The logical length represents the valid range of bit indices (0 to len-1).
    /// Initially, all bits are set to 0 (unset).
    ///
    /// # Arguments
    ///
    /// * `len` - The logical length of the bit list in bits
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::BitRead;
    ///
    /// let bits = BitList::new(64);
    /// assert_eq!(bits.len(), 64);
    /// assert!(bits.none());  // All bits are initially 0
    /// ```
    #[inline]
    pub fn new(len: usize) -> Self {
        Self {
            store: Vec::new(),
            len,
        }
    }

    /// Creates a new empty `BitList` with the specified capacity for storing indices.
    ///
    /// This pre-allocates memory for storing up to `capacity` indices of set bits,
    /// which can improve performance when you know in advance approximately how many
    /// bits will be set.
    ///
    /// # Arguments
    ///
    /// * `capacity` - The number of indices to pre-allocate space for
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::BitWrite;
    ///
    /// // Pre-allocate space for 10 set bits
    /// let mut bits = BitList::with_capacity(10);
    ///
    /// // Setting bits won't cause reallocations until more than 10 are set
    /// for i in 0..10 {
    ///     bits.set(i * 10);  // Set bits at positions 0, 10, 20, ...
    /// }
    /// ```
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            store: Vec::with_capacity(capacity),
            len: 0,
        }
    }

    /// Returns an iterator over the indices of set bits in the list.
    ///
    /// The iterator yields the indices where bits are set to 1, in ascending order.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::BitWrite;
    ///
    /// let mut bits = BitList::new(100);
    /// bits.set(5);
    /// bits.set(42);
    /// bits.set(99);
    ///
    /// let indices: Vec<usize> = bits.iter().collect();
    /// assert_eq!(indices, vec![5, 42, 99]);
    /// ```
    #[inline]
    pub fn iter(&self) -> Iter<'_> {
        Iter(self.store.iter())
    }

    /// Returns the first (lowest) index where a bit is set, or None if no bits are set.
    ///
    /// # Returns
    ///
    /// The lowest index where a bit is set to 1, or None if all bits are 0.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::BitWrite;
    ///
    /// let mut bits = BitList::new(100);
    /// assert_eq!(bits.first(), None);
    ///
    /// bits.set(42);
    /// bits.set(5);
    /// assert_eq!(bits.first(), Some(5));  // 5 is the lowest set bit
    /// ```
    #[inline]
    pub fn first(&self) -> Option<usize> {
        self.store.first().map(|&index| index)
    }

    /// Returns the last (highest) index where a bit is set, or None if no bits are set.
    ///
    /// # Returns
    ///
    /// The highest index where a bit is set to 1, or None if all bits are 0.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::BitWrite;
    ///
    /// let mut bits = BitList::new(100);
    /// assert_eq!(bits.last(), None);
    ///
    /// bits.set(5);
    /// bits.set(42);
    /// assert_eq!(bits.last(), Some(42));  // 42 is the highest set bit
    /// ```
    #[inline]
    pub fn last(&self) -> Option<usize> {
        self.store.last().map(|&index| index)
    }

    /// Returns the capacity of the internal store in terms of how many indices it can hold
    /// without reallocation.
    ///
    /// This is not the same as the logical length of the bit list. It represents how many
    /// set bits (1s) can be stored before the internal vector needs to reallocate.
    ///
    /// # Returns
    ///
    /// The current capacity of the internal store.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    ///
    /// let bits = BitList::with_capacity(10);
    /// assert!(bits.capacity() >= 10);  // Capacity is at least 10
    /// ```
    pub fn capacity(&self) -> usize {
        self.store.capacity()
    }
}

/// Implementation of the `BitRead` trait for `BitList`.
///
/// This provides methods for reading bit values and iterating over the bit list.
/// The implementation uses binary search to efficiently check if bits are set.
impl BitRead for BitList {
    type Iter<'a>
        = Iter<'a>
    where
        Self: 'a;

    /// Returns the logical length of the bit list.
    ///
    /// This is the valid range of bit indices (0 to len-1) that can be accessed.
    fn len(&self) -> usize {
        self.len
    }

    /// Tests if the bit at the specified index is set (1).
    ///
    /// Uses binary search to efficiently check if the index exists in the store.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Returns
    ///
    /// `true` if the bit is set, `false` otherwise
    fn test(&self, idx: usize) -> bool {
        self.store.binary_search(&idx).is_ok()
    }

    /// Returns an iterator over the indices of set bits.
    ///
    /// The iterator yields the indices where bits are set to 1, in ascending order.
    fn iter(&self) -> Self::Iter<'_> {
        Iter(self.store.iter())
    }
}

/// Implementation of the `BitWrite` trait for `BitList`.
///
/// This provides methods for modifying bit values in the bit list.
/// The implementation maintains a sorted list of indices where bits are set to 1.
impl BitWrite for BitList {
    /// Sets the bit at the specified index to 1.
    ///
    /// If the bit is already set, this operation has no effect.
    /// Uses binary search to find the correct position to insert the index.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the bit to set
    fn set(&mut self, index: usize) {
        match self.store.binary_search(&index) {
            Ok(_) => {}
            Err(pos) => self.store.insert(pos, index),
        }
    }

    /// Resets the bit at the specified index to 0.
    ///
    /// If the bit is already reset, this operation has no effect.
    /// Uses binary search to find and remove the index if it exists.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the bit to reset
    fn reset(&mut self, index: usize) {
        match self.store.binary_search(&index) {
            Ok(pos) => {
                self.store.remove(pos);
            }
            Err(_) => {}
        }
    }

    /// Flips the bit at the specified index (0 becomes 1, 1 becomes 0).
    ///
    /// Uses binary search to efficiently find and modify the bit.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the bit to flip
    fn flip(&mut self, index: usize) {
        match self.store.binary_search(&index) {
            Ok(pos) => {
                self.store.remove(pos);
            }
            Err(pos) => self.store.insert(pos, index),
        }
    }

    /// Tests the bit at the specified index and sets it to 1.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the bit to test and set
    ///
    /// # Returns
    ///
    /// `true` if the bit was already set, `false` if it was reset
    fn test_and_set(&mut self, index: usize) -> bool {
        match self.store.binary_search(&index) {
            Ok(_) => true,
            Err(pos) => {
                self.store.insert(pos, index);
                false
            }
        }
    }

    /// Sets all bits in the bit list to 1.
    ///
    /// This populates the internal store with all indices from 0 to len-1.
    fn fill(&mut self) {
        for i in 0..self.len {
            if i < self.store.len() {
                self.store[i] = i;
            } else {
                self.store.push(i);
            }
        }
    }

    /// Resets all bits in the bit list to 0.
    ///
    /// This clears the internal store, effectively setting all bits to 0.
    fn clear(&mut self) {
        self.store.clear();
    }
}

/// Implementation of the `BitResize` trait for `BitList`.
///
/// This provides methods for resizing the bit list, adjusting its logical length
/// and ensuring that no indices beyond the new length remain in the store.
impl BitResize for BitList {
    /// Resizes the bit list to the specified new length.
    ///
    /// When growing the list, the new bits are initialized to 0.
    /// When shrinking the list, any indices beyond the new length are removed from the store.
    ///
    /// # Arguments
    ///
    /// * `new_len` - The new logical length for the bit list
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::{BitRead, BitWrite, BitResize};
    ///
    /// let mut bits = BitList::new(10);
    /// bits.set(8);
    ///
    /// // Grow the list
    /// bits.resize(20);
    /// assert_eq!(bits.len(), 20);
    /// assert!(bits.test(8));  // Existing bits remain set
    ///
    /// // Shrink the list
    /// bits.resize(5);
    /// assert_eq!(bits.len(), 5);
    /// assert!(!bits.test(8));  // Bits beyond new length are removed
    /// ```
    fn resize(&mut self, new_len: usize) {
        match self.len.cmp(&new_len) {
            std::cmp::Ordering::Less => self.len = new_len,
            std::cmp::Ordering::Equal => {}
            std::cmp::Ordering::Greater => {
                while let Some(&index) = self.store.last() {
                    if index > new_len {
                        self.store.pop();
                    } else {
                        break;
                    }
                }
                self.len = new_len;
            }
        }
    }
}

/// Implementation of the `BitStack` trait for `BitList`.
///
/// This provides stack-like operations (push/pop) for the bit list,
/// treating it as a stack of boolean values.
impl BitStack for BitList {
    /// Pushes a boolean value onto the end of the bit list.
    ///
    /// This increases the length of the bit list by 1 and sets the
    /// new bit according to the provided value.
    ///
    /// # Arguments
    ///
    /// * `value` - The boolean value to push (true for 1, false for 0)
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::{BitRead, BitStack};
    ///
    /// let mut bits = BitList::new(0);
    /// bits.push(true);   // Push a 1
    /// bits.push(false);  // Push a 0
    /// bits.push(true);   // Push a 1
    ///
    /// assert_eq!(bits.len(), 3);
    /// assert!(bits.test(0));
    /// assert!(!bits.test(1));
    /// assert!(bits.test(2));
    /// ```
    fn push(&mut self, value: bool) {
        if value {
            self.store.push(self.len);
        }
        self.len += 1;
    }

    /// Pops a boolean value from the end of the bit list.
    ///
    /// This decreases the length of the bit list by 1 and returns the
    /// value of the removed bit.
    ///
    /// # Returns
    ///
    /// The boolean value of the popped bit (true for 1, false for 0),
    /// or None if the bit list is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitList;
    /// use fastbit::BitStack;
    ///
    /// let mut bits = BitList::new(0);
    /// bits.push(true);
    /// bits.push(false);
    ///
    /// assert_eq!(bits.pop(), Some(false));
    /// assert_eq!(bits.pop(), Some(true));
    /// assert_eq!(bits.pop(), None);  // Empty list
    /// ```
    fn pop(&mut self) -> Option<bool> {
        if let Some(&index) = self.store.last() {
            self.len -= 1;
            if index == self.len {
                self.store.pop();
                return Some(true);
            } else {
                return Some(false);
            }
        }
        None
    }
}

/// An iterator over the indices of set bits in a `BitList`.
///
/// This iterator yields the indices where bits are set to 1, in ascending order.
pub struct Iter<'a>(std::slice::Iter<'a, usize>);

impl<'a> Iterator for Iter<'a> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|&x| x)
    }
}

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

    #[test]
    fn test_debug() {
        let mut bl: BitList = BitList::new(60);
        bl.set(1);
        bl.set(17);
        bl.set(27);
        bl.set(47);
        assert_eq!(
            format!("{bl:?}"),
            "BitList { store: [1, 17, 27, 47], len: 60 }"
        );
    }

    #[test]
    fn test_new_and_len() {
        let bl: BitList = BitList::new(10);
        assert_eq!(bl.len(), 10);
        assert!(bl.none());
        let bl0: BitList = BitList::new(0);
        assert_eq!(bl0.len(), 0);
        assert!(bl0.is_empty());
        let mut iter = bl.iter();
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_set_and_test() {
        let mut bl: BitList = BitList::new(8);
        for i in 0..8 {
            assert!(!bl.test(i));
            bl.set(i);
            assert!(bl.test(i));
        }
    }

    #[test]
    fn test_reset() {
        let mut bl: BitList = BitList::new(8);
        for i in 0..8 {
            bl.set(i);
        }
        for i in 0..8 {
            bl.reset(i);
            assert!(!bl.test(i));
        }
    }

    #[test]
    fn test_test_and_set() {
        let mut bl: BitList = BitList::new(4);
        assert!(!bl.test_and_set(2));
        assert!(bl.test_and_set(2));
        assert!(bl.test(2));
    }

    #[test]
    fn test_fill_and_clear() {
        let mut bl: BitList = BitList::new(10);
        bl.fill();
        for i in 0..10 {
            assert!(bl.test(i));
        }
        bl.clear();
        assert!(bl.none());
    }

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

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

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

    // #[test]
    // fn test_last() {
    //     let mut bl: BitList = BitList::new(0);
    //     assert_eq!(bl.last(), None);

    //     // Use the BitList::push method that takes a usize
    //     bl.set(1);
    //     assert_eq!(bl.last(), Some(1));

    //     bl.set(2);
    //     assert_eq!(bl.last(), Some(2));

    //     // Use the BitList::pop method that returns Option<usize>
    //     assert_eq!(bl.pop(), Some(2));
    //     assert_eq!(bl.last(), Some(1));

    //     assert_eq!(bl.pop(), Some(1));
    //     assert_eq!(bl.last(), None);
    // }

    #[test]
    fn test_first() {
        let mut bl: BitList = BitList::new(0);
        assert_eq!(bl.first(), None);

        // Use the BitList::push method that takes a usize
        bl.set(5);
        assert_eq!(bl.first(), Some(5));

        bl.set(2); // Note: This doesn't maintain sorted order
        assert_eq!(bl.first(), Some(2)); // Still 5 because push doesn't sort

        // Use set to properly maintain sorted order
        let mut bl2: BitList = BitList::new(10);
        bl2.set(5);
        bl2.set(2);
        assert_eq!(bl2.first(), Some(2)); // Now 2 is first because set maintains order
    }

    #[test]
    fn test_flip() {
        let mut bl: BitList = BitList::new(8);

        // Flip unset bits to set
        for i in 0..4 {
            assert!(!bl.test(i));
            bl.flip(i);
            assert!(bl.test(i));
        }

        // Flip set bits to unset
        for i in 0..4 {
            assert!(bl.test(i));
            bl.flip(i);
            assert!(!bl.test(i));
        }
    }

    #[test]
    fn test_bit_stack_trait() {
        // Create a separate test for BitStack trait implementation
        // to avoid method resolution ambiguity
        let mut bit_stack = BitList::new(0);

        // Import the trait
        use crate::traits::BitStack;

        // Test the BitStack trait implementation
        // We need to use the trait methods through the trait itself
        <BitList as BitStack>::push(&mut bit_stack, true);
        <BitList as BitStack>::push(&mut bit_stack, false);
        <BitList as BitStack>::push(&mut bit_stack, true);

        assert_eq!(bit_stack.len(), 3);
        assert!(bit_stack.test(0));
        assert!(!bit_stack.test(1));
        assert!(bit_stack.test(2));

        assert_eq!(<BitList as BitStack>::pop(&mut bit_stack), Some(true));
        assert_eq!(bit_stack.len(), 2);

        assert_eq!(<BitList as BitStack>::pop(&mut bit_stack), Some(false));
        assert_eq!(bit_stack.len(), 1);

        assert_eq!(<BitList as BitStack>::pop(&mut bit_stack), Some(true));
        assert_eq!(bit_stack.len(), 0);

        assert_eq!(<BitList as BitStack>::pop(&mut bit_stack), None);
    }

    #[test]
    fn test_out_of_bounds() {
        let mut bl: BitList = BitList::new(10);

        // Setting bits within bounds works
        bl.set(9);
        assert!(bl.test(9));

        // Setting bits at the boundary
        bl.set(10); // This is at len, which should be allowed
        assert!(bl.test(10));

        // Setting bits beyond len still works but extends the logical range
        bl.set(20);
        assert!(bl.test(20));

        // Resizing down removes out-of-bounds bits
        bl.resize(10);
        assert!(bl.test(9));
    }
}