fastbit 0.11.1

//! Provides set operations (union, intersection, symmetric difference, and difference)
//! for bit sets that implement the `BitRead` trait.
//!
//! These operations allow for combining bit sets in various ways without modifying
//! the original bit sets. Each operation returns a new adapter that implements the
//! `BitRead` trait, allowing for further operations or iteration over the result.
//!
//! # Examples
//!
//! ```
//! use fastbit::{BitVec, BitRead, BitWrite};
//! use fastbit::BitSetUnion;
//!
//! let mut bv1 = BitVec::<u32>::new(64);
//! let mut bv2 = BitVec::<u32>::new(64);
//!
//! // Set even bits in bv1
//! for i in 0..64 {
//!     if i % 2 == 0 {
//!         bv1.set(i);
//!     }
//! }
//!
//! // Set bits divisible by 3 in bv2
//! for i in 0..64 {
//!     if i % 3 == 0 {
//!         bv2.set(i);
//!     }
//! }
//!
//! // Create a union of the two bit sets
//! let union = BitSetUnion::new(&bv1, &bv2);
//!
//! // Iterate over the set bits in the union
//! for idx in union.iter() {
//!     println!("Bit {} is set in the union", idx);
//! }
//! ```

use std::iter::Peekable;

use crate::BitRead;

/// Adapter for the union of two bit sets.
///
/// This struct provides a view of the union of two bit sets without modifying
/// the original bit sets. A bit is set in the union if it is set in either of
/// the original bit sets.
///
/// # Examples
///
/// ```
/// use fastbit::{BitVec, BitRead, BitWrite};
/// use fastbit::BitSetUnion;
///
/// let mut bv1 = BitVec::<u32>::new(64);
/// let mut bv2 = BitVec::<u32>::new(64);
///
/// bv1.set(1);
/// bv1.set(3);
/// bv2.set(2);
/// bv2.set(3);
///
/// let union = BitSetUnion::new(&bv1, &bv2);
///
/// assert!(union.test(1)); // From bv1
/// assert!(union.test(2)); // From bv2
/// assert!(union.test(3)); // From both
/// assert!(!union.test(0)); // Not set in either
/// ```
pub struct BitSetUnion<'a, A: BitRead, B: BitRead> {
    a: &'a A,
    b: &'a B,
}

impl<'a, A: BitRead, B: BitRead> BitSetUnion<'a, A, B> {
    pub fn new(a: &'a A, b: &'a B) -> Self {
        Self { a, b }
    }
}

impl<'a, A: BitRead, B: BitRead> BitRead for BitSetUnion<'a, A, B> {
    type Iter<'b>
        = BitSetUnionIter<'b, A, B>
    where
        Self: 'b;

    fn len(&self) -> usize {
        self.a.len()
    }

    fn test(&self, idx: usize) -> bool {
        self.a.test(idx) || self.b.test(idx)
    }

    fn iter(&self) -> Self::Iter<'_> {
        BitSetUnionIter {
            a: self.a.iter().peekable(),
            b: self.b.iter().peekable(),
        }
    }
}

/// Iterator over the set bits in a `BitSetUnion`.
///
/// This iterator yields the indices of all bits that are set in either of the
/// original bit sets, in ascending order and without duplicates.
pub struct BitSetUnionIter<'a, A: BitRead + 'a, B: BitRead + 'a> {
    a: Peekable<<A as BitRead>::Iter<'a>>,
    b: Peekable<<B as BitRead>::Iter<'a>>,
}

impl<'a, A: BitRead, B: BitRead> Iterator for BitSetUnionIter<'a, A, B> {
    type Item = usize;

    /// Returns the next set bit in the union.
    ///
    /// The bits are returned in ascending order, without duplicates.
    fn next(&mut self) -> Option<Self::Item> {
        match (self.a.peek(), self.b.peek()) {
            (None, None) => None,
            (None, Some(_)) => self.b.next(),
            (Some(_), None) => self.a.next(),
            (Some(a), Some(b)) => {
                if a < b {
                    self.a.next()
                } else if a > b {
                    self.b.next()
                } else {
                    // Equal values, advance both iterators but return only one value
                    let result = self.a.next();
                    let _ = self.b.next();
                    result
                }
            }
        }
    }
}

/// Adapter for the intersection of two bit sets.
///
/// This struct provides a view of the intersection of two bit sets without modifying
/// the original bit sets. A bit is set in the intersection if it is set in both of
/// the original bit sets.
///
/// # Examples
///
/// ```
/// use fastbit::{BitVec, BitRead, BitWrite};
/// use fastbit::BitSetIntersection;
///
/// let mut bv1 = BitVec::<u32>::new(64);
/// let mut bv2 = BitVec::<u32>::new(64);
///
/// bv1.set(1);
/// bv1.set(3);
/// bv2.set(2);
/// bv2.set(3);
///
/// let intersection = BitSetIntersection::new(&bv1, &bv2);
///
/// assert!(!intersection.test(1)); // Only in bv1
/// assert!(!intersection.test(2)); // Only in bv2
/// assert!(intersection.test(3));  // In both
/// assert!(!intersection.test(0)); // Not set in either
/// ```
pub struct BitSetIntersection<'a, A: BitRead, B: BitRead> {
    a: &'a A,
    b: &'a B,
}

impl<'a, A: BitRead, B: BitRead> BitSetIntersection<'a, A, B> {
    /// Creates a new `BitSetIntersection` from two bit sets.
    ///
    /// # Arguments
    ///
    /// * `a` - The first bit set
    /// * `b` - The second bit set
    ///
    /// # Returns
    ///
    /// A new `BitSetIntersection` that represents the intersection of the two bit sets.
    pub fn new(a: &'a A, b: &'a B) -> Self {
        Self { a, b }
    }
}

impl<'a, A: BitRead, B: BitRead> BitRead for BitSetIntersection<'a, A, B> {
    type Iter<'b>
        = BitSetIntersectionIter<'b, A, B>
    where
        Self: 'b;

    /// Returns the length of the bit set.
    ///
    /// The length is determined by the length of the first bit set.
    fn len(&self) -> usize {
        self.a.len()
    }

    /// Tests if the bit at the given index is set.
    ///
    /// A bit is set in the intersection if it is set in both of the original bit sets.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Returns
    ///
    /// `true` if the bit is set in both of the original bit sets, `false` otherwise.
    fn test(&self, idx: usize) -> bool {
        self.a.test(idx) && self.b.test(idx)
    }

    /// Returns an iterator over the set bits in the intersection.
    fn iter(&self) -> Self::Iter<'_> {
        BitSetIntersectionIter {
            a: self.a.iter().peekable(),
            b: self.b.iter().peekable(),
        }
    }
}

/// Iterator over the set bits in a `BitSetIntersection`.
///
/// This iterator yields the indices of all bits that are set in both of the
/// original bit sets, in ascending order.
pub struct BitSetIntersectionIter<'a, A: BitRead + 'a, B: BitRead + 'a> {
    a: Peekable<<A as BitRead>::Iter<'a>>,
    b: Peekable<<B as BitRead>::Iter<'a>>,
}

impl<'a, A: BitRead, B: BitRead> Iterator for BitSetIntersectionIter<'a, A, B> {
    type Item = usize;

    /// Returns the next set bit in the intersection.
    ///
    /// The bits are returned in ascending order.
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match (self.a.peek(), self.b.peek()) {
                (Some(a), Some(b)) => {
                    if a < b {
                        // Skip a and continue
                        let _ = self.a.next();
                    } else if a > b {
                        // Skip b and continue
                        let _ = self.b.next();
                    } else {
                        // Equal values, return one and advance both
                        let result = self.a.next();
                        let _ = self.b.next();
                        return result;
                    }
                }
                // If either iterator is exhausted, there can be no more intersections
                _ => return None,
            }
        }
    }
}

/// Adapter for the symmetric difference (XOR) of two bit sets.
///
/// This struct provides a view of the symmetric difference of two bit sets without modifying
/// the original bit sets. A bit is set in the symmetric difference if it is set in exactly
/// one of the original bit sets (not in both).
///
/// # Examples
///
/// ```
/// use fastbit::{BitVec, BitRead, BitWrite};
/// use fastbit::BitSetSymmetricDifference;
///
/// let mut bv1 = BitVec::<u32>::new(64);
/// let mut bv2 = BitVec::<u32>::new(64);
///
/// bv1.set(1);
/// bv1.set(3);
/// bv2.set(2);
/// bv2.set(3);
///
/// let sym_diff = BitSetSymmetricDifference::new(&bv1, &bv2);
///
/// assert!(sym_diff.test(1));  // Only in bv1
/// assert!(sym_diff.test(2));  // Only in bv2
/// assert!(!sym_diff.test(3)); // In both, so not in symmetric difference
/// assert!(!sym_diff.test(0)); // Not set in either
/// ```
pub struct BitSetSymmetricDifference<'a, A: BitRead, B: BitRead> {
    a: &'a A,
    b: &'a B,
}

impl<'a, A: BitRead, B: BitRead> BitSetSymmetricDifference<'a, A, B> {
    /// Creates a new `BitSetSymmetricDifference` from two bit sets.
    ///
    /// # Arguments
    ///
    /// * `a` - The first bit set
    /// * `b` - The second bit set
    ///
    /// # Returns
    ///
    /// A new `BitSetSymmetricDifference` that represents the symmetric difference of the two bit sets.
    pub fn new(a: &'a A, b: &'a B) -> Self {
        Self { a, b }
    }
}

impl<'a, A: BitRead, B: BitRead> BitRead for BitSetSymmetricDifference<'a, A, B> {
    type Iter<'b>
        = BitSetSymmetricDifferenceIter<'b, A, B>
    where
        Self: 'b;

    /// Returns the length of the bit set.
    ///
    /// The length is determined by the length of the first bit set.
    fn len(&self) -> usize {
        self.a.len()
    }

    /// Tests if the bit at the given index is set.
    ///
    /// A bit is set in the symmetric difference if it is set in exactly one of the original bit sets.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Returns
    ///
    /// `true` if the bit is set in exactly one of the original bit sets, `false` otherwise.
    fn test(&self, idx: usize) -> bool {
        self.a.test(idx) != self.b.test(idx)
    }

    /// Returns an iterator over the set bits in the symmetric difference.
    fn iter(&self) -> Self::Iter<'_> {
        BitSetSymmetricDifferenceIter {
            a: self.a.iter().peekable(),
            b: self.b.iter().peekable(),
        }
    }
}

/// Iterator over the set bits in a `BitSetSymmetricDifference`.
///
/// This iterator yields the indices of all bits that are set in exactly one of the
/// original bit sets, in ascending order.
pub struct BitSetSymmetricDifferenceIter<'a, A: BitRead + 'a, B: BitRead + 'a> {
    a: Peekable<<A as BitRead>::Iter<'a>>,
    b: Peekable<<B as BitRead>::Iter<'a>>,
}

impl<'a, A: BitRead, B: BitRead> Iterator for BitSetSymmetricDifferenceIter<'a, A, B> {
    type Item = usize;

    /// Returns the next set bit in the symmetric difference.
    ///
    /// The bits are returned in ascending order.
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match (self.a.peek(), self.b.peek()) {
                (None, None) => return None,
                (None, Some(_)) => return self.b.next(),
                (Some(_), None) => return self.a.next(),
                (Some(a), Some(b)) => {
                    if a < b {
                        // Only in a, include it
                        return self.a.next();
                    } else if a > b {
                        // Only in b, include it
                        return self.b.next();
                    } else {
                        // In both, skip it
                        let _ = self.a.next();
                        let _ = self.b.next();
                    }
                }
            }
        }
    }
}

/// Adapter for the difference of two bit sets (A \ B).
///
/// This struct provides a view of the difference of two bit sets without modifying
/// the original bit sets. A bit is set in the difference if it is set in the first
/// bit set but not in the second bit set.
///
/// # Examples
///
/// ```
/// use fastbit::{BitVec, BitRead, BitWrite};
/// use fastbit::BitSetDifference;
///
/// let mut bv1 = BitVec::<u32>::new(64);
/// let mut bv2 = BitVec::<u32>::new(64);
///
/// bv1.set(1);
/// bv1.set(3);
/// bv2.set(2);
/// bv2.set(3);
///
/// let difference = BitSetDifference::new(&bv1, &bv2);
///
/// assert!(difference.test(1));  // In bv1 but not in bv2
/// assert!(!difference.test(2)); // Not in bv1
/// assert!(!difference.test(3)); // In both, so not in difference
/// assert!(!difference.test(0)); // Not set in either
/// ```
pub struct BitSetDifference<'a, A: BitRead, B: BitRead> {
    a: &'a A,
    b: &'a B,
}

impl<'a, A: BitRead, B: BitRead> BitSetDifference<'a, A, B> {
    /// Creates a new `BitSetDifference` from two bit sets.
    ///
    /// # Arguments
    ///
    /// * `a` - The first bit set
    /// * `b` - The second bit set
    ///
    /// # Returns
    ///
    /// A new `BitSetDifference` that represents the difference of the two bit sets (A \ B).
    pub fn new(a: &'a A, b: &'a B) -> Self {
        Self { a, b }
    }
}

impl<'a, A: BitRead, B: BitRead> BitRead for BitSetDifference<'a, A, B> {
    type Iter<'c>
        = BitSetDifferenceIter<'c, A, B>
    where
        Self: 'c;

    /// Returns the length of the bit set.
    ///
    /// The length is determined by the length of the first bit set.
    fn len(&self) -> usize {
        self.a.len()
    }

    /// Tests if the bit at the given index is set.
    ///
    /// A bit is set in the difference if it is set in the first bit set but not in the second bit set.
    ///
    /// # Arguments
    ///
    /// * `idx` - The index of the bit to test
    ///
    /// # Returns
    ///
    /// `true` if the bit is set in the first bit set but not in the second bit set, `false` otherwise.
    fn test(&self, idx: usize) -> bool {
        self.a.test(idx) && !self.b.test(idx)
    }

    /// Returns an iterator over the set bits in the difference.
    fn iter(&self) -> Self::Iter<'_> {
        BitSetDifferenceIter {
            a: self.a.iter().peekable(),
            b: self.b.iter().peekable(),
        }
    }
}

/// Iterator over the set bits in a `BitSetDifference`.
///
/// This iterator yields the indices of all bits that are set in the first bit set
/// but not in the second bit set, in ascending order.
pub struct BitSetDifferenceIter<'a, A: BitRead + 'a, B: BitRead + 'a> {
    a: Peekable<<A as BitRead>::Iter<'a>>,
    b: Peekable<<B as BitRead>::Iter<'a>>,
}

impl<'a, A: BitRead, B: BitRead> Iterator for BitSetDifferenceIter<'a, A, B> {
    type Item = usize;

    /// Returns the next set bit in the difference.
    ///
    /// The bits are returned in ascending order.
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match (self.a.peek(), self.b.peek()) {
                (None, _) => return None,                // If a is exhausted, we're done
                (Some(_), None) => return self.a.next(), // If b is exhausted, all remaining bits in a are in the difference
                (Some(a), Some(b)) => {
                    if a < b {
                        // a is smaller, so it's not in b, include it
                        return self.a.next();
                    } else if a > b {
                        // a is larger, skip b and continue
                        let _ = self.b.next();
                    } else {
                        // Equal values, skip both and continue
                        let _ = self.a.next();
                        let _ = self.b.next();
                    }
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{BitVec, BitWrite};

    #[test]
    fn test_bitset_union() {
        let mut bv1 = BitVec::<u32>::new(64);
        let mut bv2 = BitVec::<u32>::new(64);

        // Set even bits in bv1
        for i in 0..64 {
            if i % 2 == 0 {
                bv1.set(i);
            }
        }

        // Set bits divisible by 3 in bv2
        for i in 0..64 {
            if i % 3 == 0 {
                bv2.set(i);
            }
        }

        let union = BitSetUnion::new(&bv1, &bv2);

        // Test specific bits
        assert!(union.test(0)); // In both (0 is even and divisible by 3)
        assert!(union.test(2)); // In bv1 only (even)
        assert!(union.test(3)); // In bv2 only (divisible by 3)
        assert!(union.test(6)); // In both (even and divisible by 3)
        assert!(!union.test(1)); // In neither

        // Test iteration
        let union_bits: Vec<usize> = union.iter().collect();

        // Expected bits: all even numbers (0,2,4,...,62) and all multiples of 3 (0,3,6,...,63)
        // without duplicates
        let mut expected_bits = Vec::new();
        for i in 0..64 {
            if i % 2 == 0 || i % 3 == 0 {
                expected_bits.push(i);
            }
        }

        assert_eq!(union_bits, expected_bits);
    }

    #[test]
    fn test_bitset_intersection() {
        let mut bv1 = BitVec::<u32>::new(64);
        let mut bv2 = BitVec::<u32>::new(64);

        // Set even bits in bv1
        for i in 0..64 {
            if i % 2 == 0 {
                bv1.set(i);
            }
        }

        // Set bits divisible by 3 in bv2
        for i in 0..64 {
            if i % 3 == 0 {
                bv2.set(i);
            }
        }

        let intersection = BitSetIntersection::new(&bv1, &bv2);

        // Test specific bits
        assert!(intersection.test(0)); // In both (0 is even and divisible by 3)
        assert!(!intersection.test(2)); // In bv1 only (even)
        assert!(!intersection.test(3)); // In bv2 only (divisible by 3)
        assert!(intersection.test(6)); // In both (even and divisible by 3)
        assert!(!intersection.test(1)); // In neither

        // Test iteration
        let intersection_bits: Vec<usize> = intersection.iter().collect();

        // Expected bits: numbers that are both even and divisible by 3 (0,6,12,...,60)
        let mut expected_bits = Vec::new();
        for i in 0..64 {
            if i % 2 == 0 && i % 3 == 0 {
                expected_bits.push(i);
            }
        }

        assert_eq!(intersection_bits, expected_bits);
    }

    #[test]
    fn test_bitset_symmetric_difference() {
        let mut bv1 = BitVec::<u32>::new(64);
        let mut bv2 = BitVec::<u32>::new(64);

        // Set even bits in bv1
        for i in 0..64 {
            if i % 2 == 0 {
                bv1.set(i);
            }
        }

        // Set bits divisible by 3 in bv2
        for i in 0..64 {
            if i % 3 == 0 {
                bv2.set(i);
            }
        }

        let sym_diff = BitSetSymmetricDifference::new(&bv1, &bv2);

        // Test specific bits
        assert!(!sym_diff.test(0)); // In both (0 is even and divisible by 3)
        assert!(sym_diff.test(2)); // In bv1 only (even)
        assert!(sym_diff.test(3)); // In bv2 only (divisible by 3)
        assert!(!sym_diff.test(6)); // In both (even and divisible by 3)
        assert!(!sym_diff.test(1)); // In neither

        // Test iteration
        let sym_diff_bits: Vec<usize> = sym_diff.iter().collect();

        // Expected bits: numbers that are either even or divisible by 3, but not both
        let mut expected_bits = Vec::new();
        for i in 0..64 {
            if (i % 2 == 0) != (i % 3 == 0) {
                expected_bits.push(i);
            }
        }

        assert_eq!(sym_diff_bits, expected_bits);
    }

    #[test]
    fn test_bitset_difference() {
        let mut bv1 = BitVec::<u32>::new(64);
        let mut bv2 = BitVec::<u32>::new(64);

        // Set even bits in bv1
        for i in 0..64 {
            if i % 2 == 0 {
                bv1.set(i);
            }
        }

        // Set bits divisible by 3 in bv2
        for i in 0..64 {
            if i % 3 == 0 {
                bv2.set(i);
            }
        }

        let difference = BitSetDifference::new(&bv1, &bv2);

        // Test specific bits
        assert!(!difference.test(0)); // In both (0 is even and divisible by 3)
        assert!(difference.test(2)); // In bv1 only (even)
        assert!(!difference.test(3)); // In bv2 only (divisible by 3)
        assert!(!difference.test(6)); // In both (even and divisible by 3)
        assert!(!difference.test(1)); // In neither

        // Test iteration
        let difference_bits: Vec<usize> = difference.iter().collect();

        // Expected bits: numbers that are even but not divisible by 3
        let mut expected_bits = Vec::new();
        for i in 0..64 {
            if i % 2 == 0 && i % 3 != 0 {
                expected_bits.push(i);
            }
        }

        assert_eq!(difference_bits, expected_bits);
    }

    #[test]
    fn test_empty_sets() {
        let empty1 = BitVec::<u32>::new(64);
        let empty2 = BitVec::<u32>::new(64);

        let union = BitSetUnion::new(&empty1, &empty2);
        let intersection = BitSetIntersection::new(&empty1, &empty2);
        let sym_diff = BitSetSymmetricDifference::new(&empty1, &empty2);
        let difference = BitSetDifference::new(&empty1, &empty2);

        // All operations on empty sets should yield empty results
        assert_eq!(union.iter().count(), 0);
        assert_eq!(intersection.iter().count(), 0);
        assert_eq!(sym_diff.iter().count(), 0);
        assert_eq!(difference.iter().count(), 0);
    }

    #[test]
    fn test_with_single_bit() {
        let mut bv1 = BitVec::<u32>::new(64);
        let mut bv2 = BitVec::<u32>::new(64);

        bv1.set(10);
        bv2.set(20);

        // Union should have both bits
        let union = BitSetUnion::new(&bv1, &bv2);
        let union_bits: Vec<usize> = union.iter().collect();
        assert_eq!(union_bits, vec![10, 20]);

        // Intersection should be empty
        let intersection = BitSetIntersection::new(&bv1, &bv2);
        assert_eq!(intersection.iter().count(), 0);

        // Symmetric difference should have both bits
        let sym_diff = BitSetSymmetricDifference::new(&bv1, &bv2);
        let sym_diff_bits: Vec<usize> = sym_diff.iter().collect();
        assert_eq!(sym_diff_bits, vec![10, 20]);

        // Difference A\B should have only the bit from A
        let difference = BitSetDifference::new(&bv1, &bv2);
        let difference_bits: Vec<usize> = difference.iter().collect();
        assert_eq!(difference_bits, vec![10]);

        // Difference B\A should have only the bit from B
        let reverse_difference = BitSetDifference::new(&bv2, &bv1);
        let reverse_difference_bits: Vec<usize> = reverse_difference.iter().collect();
        assert_eq!(reverse_difference_bits, vec![20]);
    }
}