fastbit 0.11.1

//! A two-dimensional bit grid implementation.
//!
//! `BitGrid` provides a memory-efficient way to represent a 2D grid of bits, where each bit can be
//! individually set or tested. It's particularly useful for representing binary relationships between
//! elements, adjacency matrices, or any other 2D binary data.
//!
//! The implementation uses a single [`BitVec`] as the underlying storage, mapping 2D coordinates to
//! a 1D index.
//!
//! # Examples
//!
//! ```
//! use fastbit::BitGrid;
//!
//! // Create a 3x4 grid
//! let mut grid = BitGrid::new(3, 4);
//!
//! // Set some bits
//! grid.set(0, 1);
//! grid.set(1, 2);
//! grid.set(2, 3);
//!
//! // Test bits
//! assert!(grid.test(0, 1));
//! assert!(!grid.test(0, 2));
//!
//! // Get grid dimensions
//! assert_eq!(grid.len(), (3, 4));
//! ```

use crate::{BitRead, BitSpan, BitSpanMut, BitVec, traits::BitWrite};

/// A two-dimensional bit grid.
///
/// `BitGrid` represents a 2D grid of bits, where each bit can be individually set or tested.
/// It's implemented using a single [`BitVec`] as the underlying storage, with row-major ordering
/// (i.e., elements in the same row are stored contiguously).
///
/// This structure is useful for representing:
/// - Adjacency matrices for graphs
/// - Binary relationships between elements
/// - Game boards or grids
/// - Any other 2D binary data
pub struct BitGrid {
    /// The underlying bit vector storage
    v: BitVec<usize>,
    /// Number of columns in the grid
    width: usize,
}

impl BitGrid {
    /// Creates a new bit grid with the specified number of rows and columns.
    ///
    /// All bits in the newly created grid are initially set to 0.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// // Create a 5x10 grid
    /// let grid = BitGrid::new(5, 10);
    /// assert_eq!(grid.len(), (5, 10));
    /// ```
    pub fn new(line: usize, column: usize) -> Self {
        Self {
            v: BitVec::<usize>::new(line * column),
            width: column,
        }
    }

    /// Sets the bit at the specified row and column position.
    ///
    /// # Panics
    ///
    /// Panics if the row or column is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let mut grid = BitGrid::new(3, 3);
    /// grid.set(1, 2);
    /// assert!(grid.test(1, 2));
    /// ```
    #[inline]
    pub fn set(&mut self, line: usize, column: usize) {
        self.v.set(self.width * line + column);
    }

    /// Tests if the bit at the specified row and column position is set.
    ///
    /// # Panics
    ///
    /// Panics if the row or column is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let mut grid = BitGrid::new(3, 3);
    /// assert!(!grid.test(1, 2));
    /// grid.set(1, 2);
    /// assert!(grid.test(1, 2));
    /// ```
    #[inline]
    pub fn test(&self, line: usize, column: usize) -> bool {
        self.v.test(self.width * line + column)
    }

    /// Returns the dimensions of the grid as a tuple of (rows, columns).
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let grid = BitGrid::new(5, 10);
    /// assert_eq!(grid.len(), (5, 10));
    /// ```
    pub fn len(&self) -> (usize, usize) {
        (self.v.len() / self.width, self.width)
    }

    /// Returns a view of a specific row in the grid.
    ///
    /// # Panics
    ///
    /// Panics if the row is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::{BitGrid, BitRead};
    ///
    /// let mut grid = BitGrid::new(3, 4);
    /// grid.set(1, 0);
    /// grid.set(1, 2);
    ///
    /// let row = grid.line(1);
    /// assert!(row.test(0));
    /// assert!(!row.test(1));
    /// assert!(row.test(2));
    /// assert!(!row.test(3));
    /// ```
    pub fn line(&self, line: usize) -> BitSpan<'_, usize> {
        self.v.slice(self.width * line, self.width)
    }

    pub fn line_mut(&mut self, line: usize) -> BitSpanMut<'_, usize> {
        self.v.slice_mut(self.width * line, self.width)
    }

    pub fn line_and(&mut self, i: usize, j: usize) {
        if i != j {
            for k in 0..self.width {
                if self.test(j, k) {
                    self.set(i, k);
                }
            }
        }
    }

    pub fn line_or(&mut self, i: usize, j: usize) {
        if i != j {
            for k in 0..self.width {
                if self.test(j, k) {
                    self.set(i, k);
                }
            }
        }
    }

    pub fn line_xor(&mut self, i: usize, j: usize) {
        if i != j {
            for k in 0..self.width {
                if self.test(i, k) != self.test(j, k) {
                    self.set(i, k);
                }
            }
        }
    }

    /// Returns true if the grid is symmetric.
    ///
    /// A grid is symmetric if for all positions (i, j), the bit at (i, j) is the same as the bit at (j, i).
    /// This method only returns true for square grids (equal number of rows and columns).
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let mut grid = BitGrid::new(3, 3);
    /// grid.set(0, 1);
    /// grid.set(1, 0);
    /// grid.set(0, 2);
    /// grid.set(2, 0);
    /// assert!(grid.is_symmetric());
    ///
    /// grid.set(1, 2);
    /// assert!(!grid.is_symmetric());
    /// ```
    pub fn is_symmetric(&self) -> bool {
        let (rows, cols) = self.len();
        if rows != cols {
            return false;
        }

        for i in 0..rows {
            for j in 0..i {
                if self.test(i, j) != self.test(j, i) {
                    return false;
                }
            }
        }
        true
    }

    /// Makes the grid symmetric by setting (j, i) if (i, j) is set.
    ///
    /// After calling this method, for all positions (i, j), if the bit at (i, j) is set,
    /// the bit at (j, i) will also be set, and vice versa.
    ///
    /// # Panics
    ///
    /// Panics if the grid is not square (equal number of rows and columns).
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let mut grid = BitGrid::new(3, 3);
    /// grid.set(0, 1);
    /// grid.set(1, 2);
    /// assert!(!grid.is_symmetric());
    ///
    /// grid.make_symmetric();
    /// assert!(grid.is_symmetric());
    /// assert!(grid.test(1, 0));
    /// assert!(grid.test(2, 1));
    /// ```
    pub fn make_symmetric(&mut self) {
        let (rows, cols) = self.len();
        assert_eq!(rows, cols, "Cannot make non-square grid symmetric");

        for i in 0..rows {
            for j in 0..i {
                if self.test(i, j) {
                    self.set(j, i);
                }
                if self.test(j, i) {
                    self.set(i, j);
                }
            }
        }
    }

    /// Computes the transitive closure of the grid, interpreting it as an adjacency matrix.
    ///
    /// If there is a path from i to j through k (i.e., if (i,k) and (k,j) are both set),
    /// then (i,j) will be set in the result.
    ///
    /// # Panics
    ///
    /// Panics if the grid is not square (equal number of rows and columns).
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let mut grid = BitGrid::new(4, 4);
    /// // Set up a path: 0 -> 1 -> 2 -> 3
    /// grid.set(0, 1);
    /// grid.set(1, 2);
    /// grid.set(2, 3);
    ///
    /// grid.transitive_closure();
    ///
    /// // Now we should have direct connections from 0 to all others
    /// assert!(grid.test(0, 1));
    /// assert!(grid.test(0, 2));
    /// assert!(grid.test(0, 3));
    /// ```
    pub fn transitive_closure(&mut self) {
        let (line, column) = self.len();
        assert_eq!(
            line, column,
            "square matrix expected, ({line}x{column}) found"
        );
        for i in 0..line {
            for j in 0..column {
                if self.test(j, i) {
                    for k in 0..self.width {
                        if self.test(i, k) {
                            self.set(j, k);
                        }
                    }
                }
            }
        }
    }

    /// Computes the reflexive transitive closure of the grid.
    ///
    /// This is the same as the transitive closure, but with all diagonal elements (i,i) set.
    /// The reflexive transitive closure represents "can reach in zero or more steps" in a graph.
    ///
    /// # Panics
    ///
    /// Panics if the grid is not square (equal number of rows and columns).
    ///
    /// # Examples
    ///
    /// ```
    /// use fastbit::BitGrid;
    ///
    /// let mut grid = BitGrid::new(4, 4);
    /// // Set up a path: 0 -> 1 -> 2 -> 3
    /// grid.set(0, 1);
    /// grid.set(1, 2);
    /// grid.set(2, 3);
    ///
    /// grid.reflexive_transitive_closure();
    ///
    /// // Now we should have direct connections from 0 to all others
    /// // and all nodes should connect to themselves
    /// assert!(grid.test(0, 0));
    /// assert!(grid.test(0, 1));
    /// assert!(grid.test(0, 2));
    /// assert!(grid.test(0, 3));
    /// assert!(grid.test(1, 1));
    /// assert!(grid.test(2, 2));
    /// assert!(grid.test(3, 3));
    /// ```
    pub fn reflexive_transitive_closure(&mut self) {
        self.transitive_closure();
        let n = self.width;
        for i in 0..n {
            self.set(i, i);
        }
    }

    /// Prints a visual representation of the grid to stderr.
    ///
    /// This method is useful for debugging and visualization purposes.
    /// The output format is a text-based matrix with row and column indices.
    ///
    /// # Examples
    ///
    /// For a 3x3 grid with bits set at (0,1), (1,1), and (2,2), the output would look like:
    ///
    /// ```text
    ///     012
    ///   .---.
    ///  0| 1 |
    ///  1| 1 |
    ///  2|  1|
    ///   `---'
    /// ```
    ///
    /// # Note
    ///
    /// This method prints to stderr, not stdout.
    pub fn print_matrix(&self) {
        eprint!("   ");
        let (line, column) = self.len();

        /* Column numbers. */
        for i in 0..column {
            if i / 10 == 0 {
                eprint!(" ");
            } else {
                // TODO: fix for case over 100
                eprint!("{}", (b'0' + i as u8 / 10) as char);
            }
        }
        eprint!("\n");
        eprint!("   ");
        for i in 0..column {
            eprint!("{}", i % 10);
        }
        eprint!("\n");

        /* Bar. */
        eprint!("  .{}.\n", "-".repeat(column));

        /* Contents. */
        for i in 0..line {
            eprint!("{:2}|", i);
            for j in 0..column {
                eprint!("{}", if self.test(i, j) { "1" } else { " " });
            }
            eprint!("|\n");
        }

        /* Bar. */
        eprint!("  `{}'\n", "-".repeat(column));
    }
}

impl std::fmt::Debug for BitGrid {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (nline, ncol) = self.len();
        let buf = (0..nline)
            .map(|i| {
                (0..ncol)
                    .map(|j| if self.test(i, j) { "1" } else { "0" })
                    .collect::<String>()
            })
            .collect::<Vec<_>>();
        if f.alternate() {
            write!(f, "{:#?}", buf)
        } else {
            write!(f, "{:?}", buf)
        }
    }
}

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

    #[test]
    fn test_grid() {
        let line = 4;
        let column = 7;
        let mut grid = BitGrid::new(line, column);
        assert_eq!(grid.len(), (line, column));
        for (l, c) in [(0, 2), (1, 3), (2, 4), (3, 5)] {
            assert!(!grid.test(l, c));
            grid.set(l, c);
            assert!(grid.test(l, c));
        }
    }

    #[test]
    fn test_transitive_closure() {
        let n = 4;
        let mut grid = BitGrid::new(n, n);
        assert_eq!(grid.len(), (n, n));
        for (l, c) in [(0, 1), (1, 2), (2, 3)] {
            assert!(!grid.test(l, c));
            grid.set(l, c);
            assert!(grid.test(l, c));
        }
        grid.transitive_closure();
        assert!(grid.test(0, 1));
        assert!(grid.test(0, 2));
        assert!(grid.test(0, 3));
    }

    #[test]
    fn test_reflexive_transitive_closure() {
        let n = 4;
        let mut grid = BitGrid::new(n, n);
        assert_eq!(grid.len(), (n, n));
        grid.reflexive_transitive_closure();
        for i in 0..n {
            assert!(grid.test(i, i));
        }
    }

    #[test]
    fn test_print() {
        let line = 12;
        let column = 36;
        let mut grid = BitGrid::new(line, column);
        for i in 0..line {
            for j in 0..column {
                if i > j {
                    grid.set(i, j);
                }
            }
        }
        grid.print_matrix();
    }

    #[test]
    fn test_line_or() {
        let line = 12;
        let column = 36;
        let mut grid = BitGrid::new(line, column);
        grid.set(1, 0);
        grid.line_or(0, 1);
        assert!(grid.test(0, 0));
    }
}