datazoo/

bitmatrix.rs

//! A [bitset](Bitset) with fixed-size rows.

use std::{fmt, mem};

use crate::{div_ceil, Bitset};

/// A [bitset](Bitset) with fixed-size rows.
///
/// Note that only the total size is tracked in `BitMatrix` and you must provide
/// the `width` value when calling methods on `BitMatrix`.
#[derive(Debug, Clone)]
pub struct BitMatrix(Bitset<Box<[u32]>>);
impl BitMatrix {
    /// The height this matrix would have if it had given `width`.
    ///
    /// Note that this might be greater than the `height` given to [`Self::new_with_size`]
    /// due to `BitMatrix` discarding information about actual size.
    ///
    /// # Panics
    /// If `Self` is not empty **and** `width` equals `0` (division by zero)
    #[inline]
    #[must_use]
    pub fn height(&self, width: usize) -> usize {
        match self.0.bit_len() {
            0 => 0,
            total => total / width,
        }
    }
    /// Iterate over active bits in given `column`.
    ///
    /// # Panics
    ///
    /// When `width = 0` (this would otherwise mean there is an infinite
    /// amount of columns)
    #[inline]
    #[must_use]
    pub fn active_rows_in_column(&self, width: usize, x: usize) -> Column {
        assert_ne!(width, 0);
        Column { data: &self.0 .0, width, current_cell: x }
    }
    /// Iterate over the enabled bits of a single row at `y` of this `Bitmatrix`.
    ///
    /// Assuming the `Bitmatrix` has the provided `width`.
    pub fn row(&self, width: usize, y: usize) -> impl Iterator<Item = usize> + '_ {
        let start = y * width;
        let end = (y + 1) * width;

        self.0
            .ones_in_range(start..end)
            .map(move |i| (i as usize) - start)
    }
    /// Enables bit at position `bit`.
    ///
    /// Returns `None` and does nothing if `bit` is out of range.
    ///
    /// When [`Bitset::bit(bit)`] will be called next, it will be `true`
    /// if this returned `Some`.
    #[inline]
    pub fn enable_bit(&mut self, width: usize, x: usize, y: usize) -> Option<()> {
        if width == 0 {
            return Some(());
        }
        self.0.enable_bit(width * y + x)
    }
    /// Create a [`BitMatrix`] with given proportions.
    ///
    /// Note that the total size is the lowest multiple of 32 higher or equal to `width * height`.
    #[must_use]
    pub fn new_with_size(width: usize, height: usize) -> Self {
        let bit_size = width * height;
        let u32_size = div_ceil(bit_size, mem::size_of::<u32>());
        BitMatrix(Bitset(vec![0; u32_size].into_boxed_slice()))
    }

    /// `true` if bit at position `x, y` in matrix is enabled.
    ///
    /// `false` otherwise, included if `x, y` is outside of the matrix.
    #[must_use]
    pub fn bit(&self, width: usize, x: usize, y: usize) -> bool {
        x < width && self.0.bit(x + y * width)
    }

    /// Return a struct that, when printed with [`fmt::Display`] or [`fmt::Debug`],
    /// displays the matrix using unicode sextant characters([pdf]).
    ///
    /// [pdf]: https://unicode.org/charts/PDF/U1FB00.pdf
    #[must_use]
    pub const fn sextant_display(&self, width: usize, height: usize) -> SextantDisplay {
        SextantDisplay { matrix: self, width, height }
    }
}

/// Iterator over a single column of a [`BitMatrix`],
/// see [`BitMatrix::active_rows_in_column`] documentation for details.
pub struct Column<'a> {
    width: usize,
    current_cell: usize,
    data: &'a [u32],
}
impl Iterator for Column<'_> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let bit = self.current_cell;
            let row = self.current_cell / self.width;
            self.current_cell += self.width;

            let block = bit / u32::BITS as usize;
            let offset = bit % u32::BITS as usize;

            let is_active = |block: u32| block & (1 << offset) != 0;
            match self.data.get(block) {
                Some(block) if is_active(*block) => return Some(row),
                Some(_) => continue,
                None => return None,
            }
        }
    }
    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let upper = self.data.len().saturating_sub(self.current_cell) / self.width;
        (0, Some(upper))
    }
    #[inline]
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        self.current_cell = self.current_cell.saturating_add(n * self.width);
        self.next()
    }
}

/// Nice printing for [`BitMatrix`], see [`BitMatrix::sextant_display`] for details.
#[derive(Copy, Clone)]
pub struct SextantDisplay<'a> {
    matrix: &'a BitMatrix,
    width: usize,
    height: usize,
}
impl<'a> fmt::Debug for SextantDisplay<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}
impl<'a> fmt::Display for SextantDisplay<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.height == 0 {
            write!(f, "\u{1fb74}\u{1fb70}")?;
        }
        for y in 0..div_ceil(self.height, 3) {
            if y != 0 {
                writeln!(f)?;
            }
            write!(f, "\u{1fb74}")?;
            for x in 0..div_ceil(self.width, 2) {
                let get_bit = |offset_x, offset_y| {
                    let (x, y) = (x * 2 + offset_x, y * 3 + offset_y);
                    u32::from(self.matrix.bit(self.width, x, y))
                };
                let offset = get_bit(0, 0)
                    | get_bit(1, 0) << 1
                    | get_bit(0, 1) << 2
                    | get_bit(1, 1) << 3
                    | get_bit(0, 2) << 4
                    | get_bit(1, 2) << 5;
                let character = match offset {
                    0b11_1111 => '\u{2588}',
                    0b00_0000 => ' ',
                    offset => char::from_u32(0x1fb00 + offset - 1).unwrap(),
                };
                write!(f, "{character}")?;
            }
            write!(f, "\u{1fb70}")?;
        }
        Ok(())
    }
}