17045413678

Committed 18 Aug 2025 03:43PM UTC coverage: 86.065% (-1.8%) from 87.913%

Build # 17045413678

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 2657b4c8e into cb2220961

Pull Request Pull Request #4215: Ji/vectors

Run Details

136 of 1803 new or added lines in 42 files covered. (7.54%)

127 existing lines in 26 files now uncovered.

56918 of 66134 relevant lines covered (86.06%)

612050.14 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/vortex-vector/src/bits/view.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::fmt::{Debug, Formatter};

use bitvec::prelude::*;
use vortex_error::{VortexError, vortex_err};

use crate::SC;

/// A borrowed fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
///
/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
/// it up for use within Vortex.
#[derive(Clone, Copy)]
pub struct BitView<'a> {
    bits: &'a BitArray<[u64; SC / 64], Lsb0>,
    true_count: usize,
}

impl Debug for BitView<'_> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("BitView")
            .field("true_count", &self.true_count)
            .field("bits", &self.as_raw())
            .finish()
    }
}

impl BitView<'static> {
    pub fn all_true() -> Self {
        static ALL_TRUE: [u64; SC / 64] = [u64::MAX; SC / 64];
        unsafe {
            BitView::new_unchecked(
                std::mem::transmute::<&[u64; SC / 64], &BitArray<[u64; SC / 64], Lsb0>>(&ALL_TRUE),
                SC,
            )
        }
    }

    pub fn all_false() -> Self {
        static ALL_FALSE: [u64; SC / 64] = [0; SC / 64];
        unsafe {
            BitView::new_unchecked(
                std::mem::transmute::<&[u64; SC / 64], &BitArray<[u64; SC / 64], Lsb0>>(&ALL_FALSE),
                0,
            )
        }
    }
}

impl<'a> BitView<'a> {
    pub fn new(bits: &[u64; SC / 64]) -> Self {
        let true_count = bits.iter().map(|&word| word.count_ones() as usize).sum();
        let bits: &BitArray<[u64; SC / 64], Lsb0> = unsafe {
            std::mem::transmute::<&[u64; SC / 64], &BitArray<[u64; SC / 64], Lsb0>>(bits)
        };
        BitView { bits, true_count }
    }

    pub(crate) unsafe fn new_unchecked(
        bits: &'a BitArray<[u64; SC / 64], Lsb0>,
        true_count: usize,
    ) -> Self {
        BitView { bits, true_count }
    }

    /// Returns the number of `true` bits in the view.
    pub fn true_count(&self) -> usize {
        self.true_count
    }

    /// Runs the provided function `f` for each index of a `true` bit in the view.
    pub fn iter_ones<F>(&self, mut f: F)
    where
        F: FnMut(usize),
    {
        match self.true_count {
            0 => {}
            SC => (0..SC).for_each(&mut f),
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    while raw != 0 {
                        let bit_pos = raw.trailing_zeros();
                        f(bit_idx + bit_pos as usize);
                        raw &= raw - 1; // Clear the bit at `bit_pos`
                    }
                    bit_idx += 64;
                }
            }
        }
    }

    /// Runs the provided function `f` for each index of a `true` bit in the view.
    pub fn iter_zeros<F>(&self, mut f: F)
    where
        F: FnMut(usize),
    {
        match self.true_count {
            0 => (0..SC).for_each(&mut f),
            SC => {}
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    while raw != u64::MAX {
                        let bit_pos = raw.trailing_ones();
                        f(bit_idx + bit_pos as usize);
                        raw |= 1u64 << bit_pos; // Set the zero bit to 1
                    }
                    bit_idx += 64;
                }
            }
        }
    }

    /// Runs the provided function `f` for each range of `true` bits in the view.
    ///
    /// The function `f` receives a tuple `(start, len)` where `start` is the index of the first
    /// `true` bit and `len` is the number of consecutive `true` bits.
    pub fn iter_slices<F>(&self, mut f: F)
    where
        F: FnMut((usize, usize)),
    {
        match self.true_count {
            0 => {}
            SC => f((0, SC)),
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    let mut offset = 0;
                    while raw != 0 {
                        // Skip leading zeros first
                        let zeros = raw.leading_zeros();
                        offset += zeros;
                        raw <<= zeros;

                        if offset >= 64 {
                            break;
                        }

                        // Count leading ones
                        let ones = raw.leading_ones();
                        if ones > 0 {
                            f((bit_idx + offset as usize, ones as usize));
                            offset += ones;
                            raw <<= ones;
                        }
                    }
                    bit_idx += 64; // Move to next word
                }
            }
        }
    }

    pub fn as_raw(&self) -> &[u64; SC / 64] {
        // It's actually remarkably hard to get a reference to the underlying array!
        let raw = self.bits.as_raw_slice();
        unsafe { &*(raw.as_ptr() as *const [u64; SC / 64]) }
    }
}

impl<'a> From<&'a [u64; SC / 64]> for BitView<'a> {
    fn from(value: &'a [u64; SC / 64]) -> Self {
        Self::new(value)
    }
}

impl<'a> From<&'a BitArray<[u64; SC / 64], Lsb0>> for BitView<'a> {
    fn from(bits: &'a BitArray<[u64; SC / 64], Lsb0>) -> Self {
        BitView::new(unsafe { std::mem::transmute::<&BitArray<[u64; 16]>, &[u64; 16]>(bits) })
    }
}

impl<'a> TryFrom<&'a BitSlice<u64, Lsb0>> for BitView<'a> {
    type Error = VortexError;

    fn try_from(value: &'a BitSlice<u64, Lsb0>) -> Result<Self, Self::Error> {
        let bits: &BitArray<[u64; SC / 64], Lsb0> = value
            .try_into()
            .map_err(|e| vortex_err!("Failed to convert BitSlice to BitArray: {}", e))?;
        Ok(BitView::new(unsafe {
            std::mem::transmute::<&BitArray<[u64; 16]>, &[u64; 16]>(bits)
        }))
    }
}

#[cfg(test)]
mod tests {
    use vortex_mask::Mask;

    use super::*;
    use crate::bits::BitVector;

    #[test]
    fn test_iter_ones_empty() {
        let bits = [0u64; SC / 64];
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, Vec::<usize>::new());
        assert_eq!(view.true_count(), 0);
    }

    #[test]
    fn test_iter_ones_all_set() {
        let view = BitView::all_true();

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones.len(), SC);
        assert_eq!(ones, (0..SC).collect::<Vec<_>>());
        assert_eq!(view.true_count(), SC);
    }

    #[test]
    fn test_iter_zeros_empty() {
        let bits = [0u64; SC / 64];
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros.len(), SC);
        assert_eq!(zeros, (0..SC).collect::<Vec<_>>());
    }

    #[test]
    fn test_iter_zeros_all_set() {
        let view = BitView::all_true();

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, Vec::<usize>::new());
    }

    #[test]
    fn test_iter_ones_single_bit() {
        let mut bits = [0u64; SC / 64];
        bits[0] = 1; // Set bit 0 (LSB)
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![0]);
        assert_eq!(view.true_count(), 1);
    }

    #[test]
    fn test_iter_zeros_single_bit_unset() {
        let mut bits = [u64::MAX; SC / 64];
        bits[0] = u64::MAX ^ 1; // Clear bit 0 (LSB)
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, vec![0]);
    }

    #[test]
    fn test_iter_ones_multiple_bits_first_word() {
        let mut bits = [0u64; SC / 64];
        bits[0] = 0b1010101; // Set bits 0, 2, 4, 6
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![0, 2, 4, 6]);
        assert_eq!(view.true_count(), 4);
    }

    #[test]
    fn test_iter_zeros_multiple_bits_first_word() {
        let mut bits = [u64::MAX; SC / 64];
        bits[0] = !0b1010101; // Clear bits 0, 2, 4, 6
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, vec![0, 2, 4, 6]);
    }

    #[test]
    fn test_iter_ones_across_words() {
        let mut bits = [0u64; SC / 64];
        bits[0] = 1 << 63; // Set bit 63 of first word
        bits[1] = 1; // Set bit 0 of second word (bit 64 overall)
        bits[2] = 1 << 31; // Set bit 31 of third word (bit 159 overall)
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![63, 64, 159]);
        assert_eq!(view.true_count(), 3);
    }

    #[test]
    fn test_iter_zeros_across_words() {
        let mut bits = [u64::MAX; SC / 64];
        bits[0] = !(1 << 63); // Clear bit 63 of first word
        bits[1] = !1; // Clear bit 0 of second word (bit 64 overall)
        bits[2] = !(1 << 31); // Clear bit 31 of third word (bit 159 overall)
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, vec![63, 64, 159]);
    }

    #[test]
    fn test_lsb_bit_ordering() {
        let mut bits = [0u64; SC / 64];
        bits[0] = 0b11111111; // Set bits 0-7 (LSB ordering)
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![0, 1, 2, 3, 4, 5, 6, 7]);
        assert_eq!(view.true_count(), 8);
    }

    #[test]
    fn test_iter_ones_and_zeros_complement() {
        let mut bits = [0u64; SC / 64];
        bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating pattern
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        let mut zeros = Vec::new();
        view.iter_ones(|idx| ones.push(idx));
        view.iter_zeros(|idx| zeros.push(idx));

        // Check that ones and zeros together cover all indices
        let mut all_indices = ones.clone();
        all_indices.extend(&zeros);
        all_indices.sort_unstable();

        assert_eq!(all_indices, (0..SC).collect::<Vec<_>>());

        // Check they don't overlap
        for one_idx in &ones {
            assert!(!zeros.contains(one_idx));
        }
    }

    #[test]
    fn test_all_false_static() {
        let view = BitView::all_false();

        let mut ones = Vec::new();
        let mut zeros = Vec::new();
        view.iter_ones(|idx| ones.push(idx));
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(ones, Vec::<usize>::new());
        assert_eq!(zeros, (0..SC).collect::<Vec<_>>());
        assert_eq!(view.true_count(), 0);
    }

    #[test]
    fn test_compatibility_with_mask_all_true() {
        // Create a Mask with all bits set
        let mask = Mask::new_true(SC);

        // Create corresponding BitView
        let view = BitView::all_true();

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Get indices from Mask (all indices for all_true mask)
        let expected_indices: Vec<usize> = (0..SC).collect();

        assert_eq!(bitview_ones, expected_indices);
        assert_eq!(view.true_count(), SC);
    }

    #[test]
    fn test_compatibility_with_mask_all_false() {
        // Create a Mask with no bits set
        let mask = Mask::new_false(SC);

        // Create corresponding BitView
        let view = BitView::all_false();

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Collect zeros from BitView
        let mut bitview_zeros = Vec::new();
        view.iter_zeros(|idx| bitview_zeros.push(idx));

        assert_eq!(bitview_ones, Vec::<usize>::new());
        assert_eq!(bitview_zeros, (0..SC).collect::<Vec<_>>());
        assert_eq!(view.true_count(), 0);
    }

    #[test]
    fn test_compatibility_with_mask_from_indices() {
        // Create a Mask from specific indices
        let indices = vec![0, 10, 20, 63, 64, 100, 500, 1023];
        let mask = Mask::from_indices(SC, indices.clone());

        // Create corresponding BitView
        let mut bits = [0u64; SC / 64];
        for idx in &indices {
            let word_idx = idx / 64;
            let bit_idx = idx % 64;
            bits[word_idx] |= 1u64 << bit_idx;
        }
        let view = BitView::new(&bits);

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        assert_eq!(bitview_ones, indices);
        assert_eq!(view.true_count(), indices.len());
    }

    #[test]
    fn test_compatibility_with_mask_slices() {
        // Create a Mask from slices (ranges)
        let slices = vec![(0, 10), (100, 110), (500, 510)];
        let mask = Mask::from_slices(SC, slices.clone());

        // Create corresponding BitView
        let mut bits = [0u64; SC / 64];
        for (start, end) in &slices {
            for idx in *start..*end {
                let word_idx = idx / 64;
                let bit_idx = idx % 64;
                bits[word_idx] |= 1u64 << bit_idx;
            }
        }
        let view = BitView::new(&bits);

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Expected indices from slices
        let mut expected_indices = Vec::new();
        for (start, end) in &slices {
            expected_indices.extend(*start..*end);
        }

        assert_eq!(bitview_ones, expected_indices);
        assert_eq!(view.true_count(), expected_indices.len());
    }

    #[test]
    fn test_mask_and_bitview_iter_match() {
        // Create a pattern with alternating bits in first word
        let mut bits = [0u64; SC / 64];
        bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating 1s and 0s
        bits[1] = 0xFF00FF00FF00FF00; // Alternating bytes

        let view = BitView::new(&bits);

        // Collect indices from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Create Mask from the same indices
        let mask = Mask::from_indices(SC, bitview_ones.clone());

        // Verify the mask returns the same indices
        mask.iter_bools(|iter| {
            let mask_bools: Vec<bool> = iter.collect();

            // Check each bit matches
            for i in 0..SC {
                let expected = bitview_ones.contains(&i);
                assert_eq!(mask_bools[i], expected, "Mismatch at index {}", i);
            }
        });
    }

    #[test]
    fn test_mask_and_bitview_all_true() {
        let mask = Mask::AllTrue(5);

        let vector = BitVector::true_until(5);

        let view = vector.as_view();

        // Collect indices from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Collect indices from BitView
        let mask_ones = mask.iter_bools(|iter| {
            iter.enumerate()
                .filter(|(_, b)| *b)
                .map(|(i, _)| i)
                .collect::<Vec<_>>()
        });

        assert_eq!(bitview_ones, mask_ones);
    }

    #[test]
    fn test_bitview_zeros_complement_mask() {
        // Create a pattern
        let mut bits = [0u64; SC / 64];
        bits[0] = 0b11110000111100001111000011110000;

        let view = BitView::new(&bits);

        // Collect ones and zeros from BitView
        let mut bitview_ones = Vec::new();
        let mut bitview_zeros = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));
        view.iter_zeros(|idx| bitview_zeros.push(idx));

        // Create masks for ones and zeros
        let ones_mask = Mask::from_indices(SC, bitview_ones);
        let zeros_mask = Mask::from_indices(SC, bitview_zeros);

        // Verify they are complements
        ones_mask.iter_bools(|ones_iter| {
            zeros_mask.iter_bools(|zeros_iter| {
                let ones_bools: Vec<bool> = ones_iter.collect();
                let zeros_bools: Vec<bool> = zeros_iter.collect();

                for i in 0..SC {
                    // Each index should be either in ones or zeros, but not both
                    assert_ne!(
                        ones_bools[i], zeros_bools[i],
                        "Index {} should be in exactly one set",
                        i
                    );
                }
            });
        });
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::fmt::{Debug, Formatter};
5
6	use bitvec::prelude::*;
7	use vortex_error::{VortexError, vortex_err};
8
9	use crate::SC;
10
11	/// A borrowed fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
12	///
13	/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
14	/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
15	/// it up for use within Vortex.
16	#[derive(Clone, Copy)]
17	pub struct BitView<'a> {
18	bits: &'a BitArray<[u64; SC / 64], Lsb0>,
19	true_count: usize,
20	}
21
22	impl Debug for BitView<'_> {
NEW 23	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
NEW 24	f.debug_struct("BitView")	×
NEW 25	.field("true_count", &self.true_count)	×
NEW 26	.field("bits", &self.as_raw())	×
NEW 27	.finish()	×
NEW 28	}	×
29	}
30
31	impl BitView<'static> {
NEW 32	pub fn all_true() -> Self {	×
33	static ALL_TRUE: [u64; SC / 64] = [u64::MAX; SC / 64];
34	unsafe {
NEW 35	BitView::new_unchecked(	×
NEW 36	std::mem::transmute::<&[u64; SC / 64], &BitArray<[u64; SC / 64], Lsb0>>(&ALL_TRUE),	×
37	SC,
38	)
39	}
NEW 40	}	×
41
NEW 42	pub fn all_false() -> Self {	×
43	static ALL_FALSE: [u64; SC / 64] = [0; SC / 64];
44	unsafe {
NEW 45	BitView::new_unchecked(	×
NEW 46	std::mem::transmute::<&[u64; SC / 64], &BitArray<[u64; SC / 64], Lsb0>>(&ALL_FALSE),	×
47	0,
48	)
49	}
NEW 50	}	×
51	}
52
53	impl<'a> BitView<'a> {
NEW 54	pub fn new(bits: &[u64; SC / 64]) -> Self {	×
NEW 55	let true_count = bits.iter().map(\|&word\| word.count_ones() as usize).sum();	×
NEW 56	let bits: &BitArray<[u64; SC / 64], Lsb0> = unsafe {	×
NEW 57	std::mem::transmute::<&[u64; SC / 64], &BitArray<[u64; SC / 64], Lsb0>>(bits)	×
58	};
NEW 59	BitView { bits, true_count }	×
NEW 60	}	×
61
NEW 62	pub(crate) unsafe fn new_unchecked(	×
NEW 63	bits: &'a BitArray<[u64; SC / 64], Lsb0>,	×
NEW 64	true_count: usize,	×
NEW 65	) -> Self {	×
NEW 66	BitView { bits, true_count }	×
NEW 67	}	×
68
69	/// Returns the number of `true` bits in the view.
NEW 70	pub fn true_count(&self) -> usize {	×
NEW 71	self.true_count	×
NEW 72	}	×
73
74	/// Runs the provided function `f` for each index of a `true` bit in the view.
NEW 75	pub fn iter_ones<F>(&self, mut f: F)	×
NEW 76	where	×
NEW 77	F: FnMut(usize),	×
78	{
NEW 79	match self.true_count {	×
NEW 80	0 => {}	×
NEW 81	SC => (0..SC).for_each(&mut f),	×
82	_ => {
NEW 83	let mut bit_idx = 0;	×
NEW 84	for mut raw in self.bits.into_inner() {	×
NEW 85	while raw != 0 {	×
NEW 86	let bit_pos = raw.trailing_zeros();	×
NEW 87	f(bit_idx + bit_pos as usize);	×
NEW 88	raw &= raw - 1; // Clear the bit at `bit_pos`	×
NEW 89	}	×
NEW 90	bit_idx += 64;	×
91	}
92	}
93	}
NEW 94	}	×
95
96	/// Runs the provided function `f` for each index of a `true` bit in the view.
NEW 97	pub fn iter_zeros<F>(&self, mut f: F)	×
NEW 98	where	×
NEW 99	F: FnMut(usize),	×
100	{
NEW 101	match self.true_count {	×
NEW 102	0 => (0..SC).for_each(&mut f),	×
NEW 103	SC => {}	×
104	_ => {
NEW 105	let mut bit_idx = 0;	×
NEW 106	for mut raw in self.bits.into_inner() {	×
NEW 107	while raw != u64::MAX {	×
NEW 108	let bit_pos = raw.trailing_ones();	×
NEW 109	f(bit_idx + bit_pos as usize);	×
NEW 110	raw \|= 1u64 << bit_pos; // Set the zero bit to 1	×
NEW 111	}	×
NEW 112	bit_idx += 64;	×
113	}
114	}
115	}
NEW 116	}	×
117
118	/// Runs the provided function `f` for each range of `true` bits in the view.
119	///
120	/// The function `f` receives a tuple `(start, len)` where `start` is the index of the first
121	/// `true` bit and `len` is the number of consecutive `true` bits.
NEW 122	pub fn iter_slices<F>(&self, mut f: F)	×
NEW 123	where	×
NEW 124	F: FnMut((usize, usize)),	×
125	{
NEW 126	match self.true_count {	×
NEW 127	0 => {}	×
NEW 128	SC => f((0, SC)),	×
129	_ => {
NEW 130	let mut bit_idx = 0;	×
NEW 131	for mut raw in self.bits.into_inner() {	×
NEW 132	let mut offset = 0;	×
NEW 133	while raw != 0 {	×
134	// Skip leading zeros first
NEW 135	let zeros = raw.leading_zeros();	×
NEW 136	offset += zeros;	×
NEW 137	raw <<= zeros;	×
138
NEW 139	if offset >= 64 {	×
NEW 140	break;	×
NEW 141	}	×
142
143	// Count leading ones
NEW 144	let ones = raw.leading_ones();	×
NEW 145	if ones > 0 {	×
NEW 146	f((bit_idx + offset as usize, ones as usize));	×
NEW 147	offset += ones;	×
NEW 148	raw <<= ones;	×
NEW 149	}	×
150	}
NEW 151	bit_idx += 64; // Move to next word	×
152	}
153	}
154	}
NEW 155	}	×
156
NEW 157	pub fn as_raw(&self) -> &[u64; SC / 64] {	×
158	// It's actually remarkably hard to get a reference to the underlying array!
NEW 159	let raw = self.bits.as_raw_slice();	×
NEW 160	unsafe { &(raw.as_ptr() as const [u64; SC / 64]) }	×
NEW 161	}	×
162	}
163
164	impl<'a> From<&'a [u64; SC / 64]> for BitView<'a> {
NEW 165	fn from(value: &'a [u64; SC / 64]) -> Self {	×
NEW 166	Self::new(value)	×
NEW 167	}	×
168	}
169
170	impl<'a> From<&'a BitArray<[u64; SC / 64], Lsb0>> for BitView<'a> {
NEW 171	fn from(bits: &'a BitArray<[u64; SC / 64], Lsb0>) -> Self {	×
NEW 172	BitView::new(unsafe { std::mem::transmute::<&BitArray<[u64; 16]>, &[u64; 16]>(bits) })	×
NEW 173	}	×
174	}
175
176	impl<'a> TryFrom<&'a BitSlice<u64, Lsb0>> for BitView<'a> {
177	type Error = VortexError;
178
NEW 179	fn try_from(value: &'a BitSlice<u64, Lsb0>) -> Result<Self, Self::Error> {	×
NEW 180	let bits: &BitArray<[u64; SC / 64], Lsb0> = value	×
NEW 181	.try_into()	×
NEW 182	.map_err(\|e\| vortex_err!("Failed to convert BitSlice to BitArray: {}", e))?;	×
NEW 183	Ok(BitView::new(unsafe {	×
NEW 184	std::mem::transmute::<&BitArray<[u64; 16]>, &[u64; 16]>(bits)	×
NEW 185	}))	×
NEW 186	}	×
187	}
188
189	#[cfg(test)]
190	mod tests {
191	use vortex_mask::Mask;
192
193	use super::*;
194	use crate::bits::BitVector;
195
196	#[test]
197	fn test_iter_ones_empty() {
198	let bits = [0u64; SC / 64];
199	let view = BitView::new(&bits);
200
201	let mut ones = Vec::new();
202	view.iter_ones(\|idx\| ones.push(idx));
203
204	assert_eq!(ones, Vec::<usize>::new());
205	assert_eq!(view.true_count(), 0);
206	}
207
208	#[test]
209	fn test_iter_ones_all_set() {
210	let view = BitView::all_true();
211
212	let mut ones = Vec::new();
213	view.iter_ones(\|idx\| ones.push(idx));
214
215	assert_eq!(ones.len(), SC);
216	assert_eq!(ones, (0..SC).collect::<Vec<_>>());
217	assert_eq!(view.true_count(), SC);
218	}
219
220	#[test]
221	fn test_iter_zeros_empty() {
222	let bits = [0u64; SC / 64];
223	let view = BitView::new(&bits);
224
225	let mut zeros = Vec::new();
226	view.iter_zeros(\|idx\| zeros.push(idx));
227
228	assert_eq!(zeros.len(), SC);
229	assert_eq!(zeros, (0..SC).collect::<Vec<_>>());
230	}
231
232	#[test]
233	fn test_iter_zeros_all_set() {
234	let view = BitView::all_true();
235
236	let mut zeros = Vec::new();
237	view.iter_zeros(\|idx\| zeros.push(idx));
238
239	assert_eq!(zeros, Vec::<usize>::new());
240	}
241
242	#[test]
243	fn test_iter_ones_single_bit() {
244	let mut bits = [0u64; SC / 64];
245	bits[0] = 1; // Set bit 0 (LSB)
246	let view = BitView::new(&bits);
247
248	let mut ones = Vec::new();
249	view.iter_ones(\|idx\| ones.push(idx));
250
251	assert_eq!(ones, vec![0]);
252	assert_eq!(view.true_count(), 1);
253	}
254
255	#[test]
256	fn test_iter_zeros_single_bit_unset() {
257	let mut bits = [u64::MAX; SC / 64];
258	bits[0] = u64::MAX ^ 1; // Clear bit 0 (LSB)
259	let view = BitView::new(&bits);
260
261	let mut zeros = Vec::new();
262	view.iter_zeros(\|idx\| zeros.push(idx));
263
264	assert_eq!(zeros, vec![0]);
265	}
266
267	#[test]
268	fn test_iter_ones_multiple_bits_first_word() {
269	let mut bits = [0u64; SC / 64];
270	bits[0] = 0b1010101; // Set bits 0, 2, 4, 6
271	let view = BitView::new(&bits);
272
273	let mut ones = Vec::new();
274	view.iter_ones(\|idx\| ones.push(idx));
275
276	assert_eq!(ones, vec![0, 2, 4, 6]);
277	assert_eq!(view.true_count(), 4);
278	}
279
280	#[test]
281	fn test_iter_zeros_multiple_bits_first_word() {
282	let mut bits = [u64::MAX; SC / 64];
283	bits[0] = !0b1010101; // Clear bits 0, 2, 4, 6
284	let view = BitView::new(&bits);
285
286	let mut zeros = Vec::new();
287	view.iter_zeros(\|idx\| zeros.push(idx));
288
289	assert_eq!(zeros, vec![0, 2, 4, 6]);
290	}
291
292	#[test]
293	fn test_iter_ones_across_words() {
294	let mut bits = [0u64; SC / 64];
295	bits[0] = 1 << 63; // Set bit 63 of first word
296	bits[1] = 1; // Set bit 0 of second word (bit 64 overall)
297	bits[2] = 1 << 31; // Set bit 31 of third word (bit 159 overall)
298	let view = BitView::new(&bits);
299
300	let mut ones = Vec::new();
301	view.iter_ones(\|idx\| ones.push(idx));
302
303	assert_eq!(ones, vec![63, 64, 159]);
304	assert_eq!(view.true_count(), 3);
305	}
306
307	#[test]
308	fn test_iter_zeros_across_words() {
309	let mut bits = [u64::MAX; SC / 64];
310	bits[0] = !(1 << 63); // Clear bit 63 of first word
311	bits[1] = !1; // Clear bit 0 of second word (bit 64 overall)
312	bits[2] = !(1 << 31); // Clear bit 31 of third word (bit 159 overall)
313	let view = BitView::new(&bits);
314
315	let mut zeros = Vec::new();
316	view.iter_zeros(\|idx\| zeros.push(idx));
317
318	assert_eq!(zeros, vec![63, 64, 159]);
319	}
320
321	#[test]
322	fn test_lsb_bit_ordering() {
323	let mut bits = [0u64; SC / 64];
324	bits[0] = 0b11111111; // Set bits 0-7 (LSB ordering)
325	let view = BitView::new(&bits);
326
327	let mut ones = Vec::new();
328	view.iter_ones(\|idx\| ones.push(idx));
329
330	assert_eq!(ones, vec![0, 1, 2, 3, 4, 5, 6, 7]);
331	assert_eq!(view.true_count(), 8);
332	}
333
334	#[test]
335	fn test_iter_ones_and_zeros_complement() {
336	let mut bits = [0u64; SC / 64];
337	bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating pattern
338	let view = BitView::new(&bits);
339
340	let mut ones = Vec::new();
341	let mut zeros = Vec::new();
342	view.iter_ones(\|idx\| ones.push(idx));
343	view.iter_zeros(\|idx\| zeros.push(idx));
344
345	// Check that ones and zeros together cover all indices
346	let mut all_indices = ones.clone();
347	all_indices.extend(&zeros);
348	all_indices.sort_unstable();
349
350	assert_eq!(all_indices, (0..SC).collect::<Vec<_>>());
351
352	// Check they don't overlap
353	for one_idx in &ones {
354	assert!(!zeros.contains(one_idx));
355	}
356	}
357
358	#[test]
359	fn test_all_false_static() {
360	let view = BitView::all_false();
361
362	let mut ones = Vec::new();
363	let mut zeros = Vec::new();
364	view.iter_ones(\|idx\| ones.push(idx));
365	view.iter_zeros(\|idx\| zeros.push(idx));
366
367	assert_eq!(ones, Vec::<usize>::new());
368	assert_eq!(zeros, (0..SC).collect::<Vec<_>>());
369	assert_eq!(view.true_count(), 0);
370	}
371
372	#[test]
373	fn test_compatibility_with_mask_all_true() {
374	// Create a Mask with all bits set
375	let mask = Mask::new_true(SC);
376
377	// Create corresponding BitView
378	let view = BitView::all_true();
379
380	// Collect ones from BitView
381	let mut bitview_ones = Vec::new();
382	view.iter_ones(\|idx\| bitview_ones.push(idx));
383
384	// Get indices from Mask (all indices for all_true mask)
385	let expected_indices: Vec<usize> = (0..SC).collect();
386
387	assert_eq!(bitview_ones, expected_indices);
388	assert_eq!(view.true_count(), SC);
389	}
390
391	#[test]
392	fn test_compatibility_with_mask_all_false() {
393	// Create a Mask with no bits set
394	let mask = Mask::new_false(SC);
395
396	// Create corresponding BitView
397	let view = BitView::all_false();
398
399	// Collect ones from BitView
400	let mut bitview_ones = Vec::new();
401	view.iter_ones(\|idx\| bitview_ones.push(idx));
402
403	// Collect zeros from BitView
404	let mut bitview_zeros = Vec::new();
405	view.iter_zeros(\|idx\| bitview_zeros.push(idx));
406
407	assert_eq!(bitview_ones, Vec::<usize>::new());
408	assert_eq!(bitview_zeros, (0..SC).collect::<Vec<_>>());
409	assert_eq!(view.true_count(), 0);
410	}
411
412	#[test]
413	fn test_compatibility_with_mask_from_indices() {
414	// Create a Mask from specific indices
415	let indices = vec![0, 10, 20, 63, 64, 100, 500, 1023];
416	let mask = Mask::from_indices(SC, indices.clone());
417
418	// Create corresponding BitView
419	let mut bits = [0u64; SC / 64];
420	for idx in &indices {
421	let word_idx = idx / 64;
422	let bit_idx = idx % 64;
423	bits[word_idx] \|= 1u64 << bit_idx;
424	}
425	let view = BitView::new(&bits);
426
427	// Collect ones from BitView
428	let mut bitview_ones = Vec::new();
429	view.iter_ones(\|idx\| bitview_ones.push(idx));
430
431	assert_eq!(bitview_ones, indices);
432	assert_eq!(view.true_count(), indices.len());
433	}
434
435	#[test]
436	fn test_compatibility_with_mask_slices() {
437	// Create a Mask from slices (ranges)
438	let slices = vec![(0, 10), (100, 110), (500, 510)];
439	let mask = Mask::from_slices(SC, slices.clone());
440
441	// Create corresponding BitView
442	let mut bits = [0u64; SC / 64];
443	for (start, end) in &slices {
444	for idx in start..end {
445	let word_idx = idx / 64;
446	let bit_idx = idx % 64;
447	bits[word_idx] \|= 1u64 << bit_idx;
448	}
449	}
450	let view = BitView::new(&bits);
451
452	// Collect ones from BitView
453	let mut bitview_ones = Vec::new();
454	view.iter_ones(\|idx\| bitview_ones.push(idx));
455
456	// Expected indices from slices
457	let mut expected_indices = Vec::new();
458	for (start, end) in &slices {
459	expected_indices.extend(start..end);
460	}
461
462	assert_eq!(bitview_ones, expected_indices);
463	assert_eq!(view.true_count(), expected_indices.len());
464	}
465
466	#[test]
467	fn test_mask_and_bitview_iter_match() {
468	// Create a pattern with alternating bits in first word
469	let mut bits = [0u64; SC / 64];
470	bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating 1s and 0s
471	bits[1] = 0xFF00FF00FF00FF00; // Alternating bytes
472
473	let view = BitView::new(&bits);
474
475	// Collect indices from BitView
476	let mut bitview_ones = Vec::new();
477	view.iter_ones(\|idx\| bitview_ones.push(idx));
478
479	// Create Mask from the same indices
480	let mask = Mask::from_indices(SC, bitview_ones.clone());
481
482	// Verify the mask returns the same indices
483	mask.iter_bools(\|iter\| {
484	let mask_bools: Vec<bool> = iter.collect();
485
486	// Check each bit matches
487	for i in 0..SC {
488	let expected = bitview_ones.contains(&i);
489	assert_eq!(mask_bools[i], expected, "Mismatch at index {}", i);
490	}
491	});
492	}
493
494	#[test]
495	fn test_mask_and_bitview_all_true() {
496	let mask = Mask::AllTrue(5);
497
498	let vector = BitVector::true_until(5);
499
500	let view = vector.as_view();
501
502	// Collect indices from BitView
503	let mut bitview_ones = Vec::new();
504	view.iter_ones(\|idx\| bitview_ones.push(idx));
505
506	// Collect indices from BitView
507	let mask_ones = mask.iter_bools(\|iter\| {
508	iter.enumerate()
509	.filter(\|(_, b)\| *b)
510	.map(\|(i, _)\| i)
511	.collect::<Vec<_>>()
512	});
513
514	assert_eq!(bitview_ones, mask_ones);
515	}
516
517	#[test]
518	fn test_bitview_zeros_complement_mask() {
519	// Create a pattern
520	let mut bits = [0u64; SC / 64];
521	bits[0] = 0b11110000111100001111000011110000;
522
523	let view = BitView::new(&bits);
524
525	// Collect ones and zeros from BitView
526	let mut bitview_ones = Vec::new();
527	let mut bitview_zeros = Vec::new();
528	view.iter_ones(\|idx\| bitview_ones.push(idx));
529	view.iter_zeros(\|idx\| bitview_zeros.push(idx));
530
531	// Create masks for ones and zeros
532	let ones_mask = Mask::from_indices(SC, bitview_ones);
533	let zeros_mask = Mask::from_indices(SC, bitview_zeros);
534
535	// Verify they are complements
536	ones_mask.iter_bools(\|ones_iter\| {
537	zeros_mask.iter_bools(\|zeros_iter\| {
538	let ones_bools: Vec<bool> = ones_iter.collect();
539	let zeros_bools: Vec<bool> = zeros_iter.collect();
540
541	for i in 0..SC {
542	// Each index should be either in ones or zeros, but not both
543	assert_ne!(
544	ones_bools[i], zeros_bools[i],
545	"Index {} should be in exactly one set",
546	i
547	);
548	}
549	});
550	});
551	}
552	}

vortex-data / vortex / 17045413678

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous