datazoo 0.7.0

//! A bit matrix similar to [`BitMatrix`](super::BitMatrix),
//! but with columns of variable length like [`JaggedVec`](super::JaggedVec).

use std::{fmt, iter, mem};

use sorted_iter::{assume::AssumeSortedByItemExt, sorted_iterator::SortedByItem};

use crate::{div_ceil, Bitset, PackedIntArray};

/// A bit matrix similar to [`BitMatrix`](super::BitMatrix),
/// but with columns of variable length like [`JaggedVec`](super::JaggedVec).
///
/// Use [`jagged_bitset::Builder`](`Builder`) to create a [`JaggedBitset`].
///
/// # Example
///
/// ```rust
/// use datazoo::jagged_bitset;
///
/// let jagged = jagged_bitset::Builder::with_capacity(7)
///     .with_row([0, 2, 4, 8])
///     .with_row([63, 12, 2, 3])
///     .with_row([1, 3, 5, 7, 9, 11])
///     .with_row([])
///     .with_row([])
///     .with_row([])
///     .with_row([1, 3])
///     .build();
///
/// let row_1: Vec<_> = jagged.row(1).collect();
/// assert_eq!(&row_1, &[2, 3, 12, 63]);
///
/// let row_3: Vec<_> = jagged.row(3).collect();
/// assert_eq!(&row_3, &[]);
///
/// let row_6: Vec<_> = jagged.row(6).collect();
/// assert_eq!(&row_6, &[1, 3]);
/// ```
#[derive(Debug, Default, Clone)]
pub struct JaggedBitset {
    ends: PackedIntArray<usize, u32>,
    bits: Bitset<Box<[u32]>>,
}
impl JaggedBitset {
    /// True if bits at column `x` and row `y` is enabled. False if not, or
    /// if `(x, y)` is not within the array.
    #[inline]
    #[must_use]
    pub fn bit(&self, x: usize, y: usize) -> bool {
        if y >= self.capacity() {
            return false;
        }
        let start = y.checked_sub(1).map_or(Some(0), |i| self.ends.get(&i));
        let end = self.ends.get(&y);
        let (Some(start), Some(end)) = (start, end) else {
            return false;
        };
        let (start, end) = (start as usize, end as usize);

        if x >= (end - start) {
            return false;
        }
        self.bits.bit(start + x)
    }
    /// Return the width of the longest row.
    ///
    /// `0` if `height == 0`.
    #[inline]
    #[must_use]
    pub fn max_width(&self) -> u32 {
        let max = (0..self.capacity()).filter_map(|i| self.get_width(i)).max();
        max.unwrap_or(0)
    }
    /// How many rows there are in this bitset matrix.
    #[must_use]
    pub fn height(&self) -> usize {
        let first_occupied = self.ends.rev_iter().next();
        first_occupied.map_or(0, |(k, _)| k)
    }
    /// Return an upper bound of how many rows this jagged bitset has.
    #[inline]
    #[must_use]
    pub fn capacity(&self) -> usize {
        self.ends.capacity()
    }
    /// Return the column count of `index` row.
    ///
    /// # Panics
    /// If `index` is greater or equal to the [`height`](Self::height).
    #[inline]
    #[must_use]
    pub fn width(&self, index: usize) -> u32 {
        self.get_width(index).unwrap()
    }
    /// Return the column count of `index` row.
    /// `None` if `index` is greater or equal to the [`height`](Self::height).
    #[inline]
    #[must_use]
    pub fn get_width(&self, index: usize) -> Option<u32> {
        let start = index
            .checked_sub(1)
            .map_or(Some(0), |i| self.ends.get(&i))?;
        let end = self.ends.get(&index)?;

        Some(end - start)
    }
    /// Iterate over all enabled bits in given `index` row.
    ///
    /// # Panics
    /// If `index` is greater or equal to the [`height`](Self::height).
    pub fn row(&self, index: usize) -> impl Iterator<Item = u32> + SortedByItem + '_ {
        self.get_row(index).unwrap()
    }
    /// Iterate over all enabled bits in given `index` row.
    ///
    /// Returns `None` if the row is out of bound.
    #[must_use]
    pub fn get_row(&self, index: usize) -> Option<impl Iterator<Item = u32> + SortedByItem + '_> {
        let start = index
            .checked_sub(1)
            .map_or(Some(0), |i| self.ends.get(&i))?;
        let end = self.ends.get(&index)?;

        let range = start as usize..end as usize;
        let bits = self.bits.ones_in_range(range).map(move |i| i - start);
        let bits = bits.assume_sorted_by_item();

        let is_not_empty = start != end;
        Some(is_not_empty.then_some(bits).into_iter().flatten())
    }

    /// Like [`JaggedBitset::braille_display`], but with rows and columns
    /// transposed (ie: rotated 90º clockwise and mirrored).
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_assertions::assert_eq;
    /// use datazoo::jagged_bitset;
    ///
    /// let jagged = jagged_bitset::Builder::with_capacity(10)
    ///     .with_row([                     7, 8, 9, 10, 11, 12, 13                ])
    ///     .with_row([0,                         9, 10, 11, 12, 13, 14, 15, 16, 17])
    ///     .with_row([0, 1, 2,    4, 5, 6,                      13, 14            ])
    ///     .with_row([            4, 5,    7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17])
    ///     .with_row([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17])
    ///     .with_row([0, 1,    3, 4,       7, 8, 9, 10, 11,             15, 16, 17])
    ///     .with_row([0,    2,    4,    6,    8,    10,     12,     14,     16, 17])
    ///     .with_row([   1,    3,    5,    7,    9,     11,     13,     15, 16    ])
    ///     .with_row([                                                            ])
    ///     .with_row([                                  11,                       ])
    ///     .build();
    /// let shown = jagged.braille_trans_display().to_string();
    /// let expected = "🭴⠈⠇⣟⢕⠀🭰\n🭴⡀⢟⣏⢕⠀🭰\n🭴⣷⢸⣿⢕⢀🭰\n🭴⢻⢾⣇⢕⠀🭰\n🭴⠘⠘⠛⠋⠀🭰";
    /// assert_eq!(expected, &shown);
    /// ```
    #[must_use]
    pub const fn braille_trans_display(&self) -> BrailleTransposedDisplay {
        BrailleTransposedDisplay { bitset: self }
    }
    /// Return a struct that, when printed with [`fmt::Display`] or [`fmt::Debug`],
    /// displays the jagged bitset using unicode braille characters([wikipedia]).
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_assertions::assert_eq;
    /// use datazoo::jagged_bitset;
    ///
    /// let jagged = jagged_bitset::Builder::with_capacity(10)
    ///     .with_row([                     7, 8, 9, 10, 11, 12, 13                ])
    ///     .with_row([0,                         9, 10, 11, 12, 13, 14, 15, 16, 17])
    ///     .with_row([0, 1, 2,    4, 5, 6,                      13, 14            ])
    ///     .with_row([            4, 5,    7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17])
    ///     .build();
    /// let shown = jagged.braille_display().to_string();
    /// let expected = "🭴⠦⠄⣤⢌⣙⣛⣻⣖⣒🭰";
    /// assert_eq!(expected, &shown);
    /// ```
    ///
    /// [wikipedia]: https://en.wikipedia.org/wiki/Braille_Patterns
    #[must_use]
    pub const fn braille_display(&self) -> BrailleDisplay {
        BrailleDisplay { bitset: self }
    }
}
/// Helps create [`JaggedBitset`] with [`Builder::build`].
///
/// [`JaggedBitset`] is immutable with a fixed capacity, so it is necessary
/// to pass through a builder ot create one.
#[derive(Debug, Clone, Default)]
pub struct Builder {
    ends: Vec<u32>,
    bits: Bitset<Vec<u32>>,
}
impl Builder {
    /// Initialize a [`Builder`].
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }
    /// Initialize a [`Builder`] with capacity rows.
    #[must_use]
    pub fn with_capacity(cap: usize) -> Self {
        Builder {
            ends: Vec::with_capacity(cap),
            bits: Bitset(Vec::new()),
        }
    }
    /// Create the immutable [`JaggedBitset`], consuming this constructor.
    #[must_use]
    pub fn build(&mut self) -> JaggedBitset {
        JaggedBitset {
            ends: self.ends.drain(..).enumerate().collect(),
            bits: Bitset(std::mem::take(&mut self.bits.0).into_boxed_slice()),
        }
    }
    /// Add a single row to this [`Builder`], returning it.
    ///
    /// # Example
    ///
    /// ```rust
    /// use datazoo::{jagged_bitset, JaggedBitset};
    ///
    /// let jagged: JaggedBitset = jagged_bitset::Builder::with_capacity(7)
    ///     .with_row([0, 2, 4, 8])
    ///     .with_row([63, 12, 2, 3])
    ///     .with_row([1, 3, 5, 7, 9, 11])
    ///     .with_row([])
    ///     .with_row([])
    ///     .with_row([])
    ///     .with_row([1, 3])
    ///     .build();
    /// ```
    pub fn with_row(&mut self, row: impl IntoIterator<Item = u32>) -> &mut Self {
        let start = self.ends.last().map_or(0, |i| *i);

        let mut row_len = 0;
        for bit in row {
            let bit_len = self.bits.bit_len();
            let bit_in_array = (bit + start) as usize;

            if bit_len <= bit_in_array {
                let extra_blocks = (bit_in_array - bit_len) / mem::size_of::<u32>() + 1;
                self.bits.0.extend(iter::repeat(0).take(extra_blocks));
            }
            self.bits.enable_bit(bit_in_array);
            row_len = row_len.max(bit + 1);
        }
        self.ends.push(start + row_len);
        self
    }
}

fn display_braille(
    f: &mut fmt::Formatter,
    height: usize,
    width: usize,
    get_bit: impl Fn(usize, usize) -> u32,
) -> fmt::Result {
    if width == 0 {
        write!(f, "\u{1fb74}\u{1fb70}")?;
    }
    for y in 0..div_ceil(height, 4) {
        if y != 0 {
            writeln!(f)?;
        }
        write!(f, "\u{1fb74}")?;
        for x in 0..div_ceil(width, 2) {
            let get_bit = |offset_x, offset_y| get_bit(x * 2 + offset_x, y * 4 + offset_y);
            let offset = get_bit(0, 0)
                | get_bit(1, 0) << 3
                | get_bit(0, 1) << 1
                | get_bit(1, 1) << 4
                | get_bit(0, 2) << 2
                | get_bit(1, 2) << 5
                | get_bit(0, 3) << 6
                | get_bit(1, 3) << 7;
            let character = char::from_u32(0x2800 + offset).unwrap();
            write!(f, "{character}")?;
        }
        write!(f, "\u{1fb70}")?;
    }
    Ok(())
}
/// Nice printing for [`JaggedBitset`], see [`JaggedBitset::braille_trans_display`] for details.
#[derive(Clone, Copy)]
pub struct BrailleTransposedDisplay<'a> {
    bitset: &'a JaggedBitset,
}
impl<'a> fmt::Debug for BrailleTransposedDisplay<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}
impl<'a> fmt::Display for BrailleTransposedDisplay<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // Note that since this is transposed, height/width are swapped
        let height = self.bitset.max_width() as usize;
        let width = self.bitset.height();
        display_braille(f, height, width, |x, y| u32::from(self.bitset.bit(y, x)))
    }
}
/// Nice printing for [`JaggedBitset`], see [`JaggedBitset::braille_display`] for details.
#[derive(Clone, Copy)]
pub struct BrailleDisplay<'a> {
    bitset: &'a JaggedBitset,
}
impl<'a> fmt::Debug for BrailleDisplay<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}
impl<'a> fmt::Display for BrailleDisplay<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let width = self.bitset.max_width() as usize;
        let height = self.bitset.height();
        display_braille(f, height, width, |x, y| u32::from(self.bitset.bit(x, y)))
    }
}