half_matrix

[Done] Triangular Matrix Library for Rust.
git clone https://git.jojolepro.com/half_matrix.git
Log | Files | Refs | README | LICENSE

commit 8528996e721ec3c2f14ea41d5eb100b4f56c0954
parent 5c496b26f7dc52b4845d64f93f4abcef6a808420
Author: Joël Lupien (Jojolepro) <jojolepromain@gmail.com>
Date:   Tue, 18 Dec 2018 15:29:33 -0500

Initial

Diffstat:
A.gitignore | 3+++
ACargo.toml | 18++++++++++++++++++
MREADME.md | 44+++++++++++++++++++++++++++++++++++++++++++-
Asrc/lib.rs | 155+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 219 insertions(+), 1 deletion(-)

diff --git a/.gitignore b/.gitignore @@ -0,0 +1,3 @@ +/target +**/*.rs.bk +Cargo.lock diff --git a/Cargo.toml b/Cargo.toml @@ -0,0 +1,18 @@ +[package] +name = "half_matrix" +version = "0.1.0" +authors = ["Joël Lupien (Jojolepro) <jojolepromain@gmail.com>"] +edition = "2018" +description = """ +A clean way to define function as a set of subfunctions where each has +defined start and end bounds. +""" + +keywords = ["half", "matrix", "groups"] +documentation = "https://docs.rs/half_matrix" +repository = "https://github.com/jojolepro/half-matrix" +license = "Apache-2.0" +exclude = ["doc"] + +[dependencies] +hibitset = "0.5" diff --git a/README.md b/README.md @@ -1,2 +1,44 @@ -# half-matrix +# Half Matrix A Half Matrix implementation. Like a normal matrix, but you only store half of it. Also it only contains bools. + +### Half Matrix: Storage +The matrix is row major. +Here's how it looks like: + +``` + ABCD +A- +B-- +C--- +D---- +``` + +In memory representation: +``` +-|--|---|---- +``` + + +Indexing starts at 0. +``` +ABCD +0123 +``` + +Row Major means that the first parameter of the methods is the Y axis in the matrix, and the second is the X axis. + +As shown by the matrix, the row value is required to be bigger or equal to the column value. + +### Example +Parameters: (3, 0) = (D, A) +``` + ABCD +A- +B-- +C--- +DX--- +``` + +### Contributing + +If you see a missing method or a bug, open a pull request and I'll be more than happy to merge it! diff --git a/src/lib.rs b/src/lib.rs @@ -0,0 +1,155 @@ +//! Half matrix storage, Row major +//! ```ignore +//! ABCD +//! A- +//! B-- +//! C--- +//! D---- +//! ``` +//! +//! In memory representation: +//! ```ignore +//! -|--|---|---- +//! ``` +//! +//! Indexing starts at 0. +//! ```ignore +//! ABCD +//! 0123 +//! ``` +//! +//! Row Major means that the first parameter of the methods is the Y axis in the matrix, and the second is the X axis. +//! +//! As shown by the matrix, the row value is required to be bigger or equal to the column value. +//! +//! ### Example +//! Parameters: (3, 0) = (D, A) +//! +//! ```ignore +//! ABCD +//! A- +//! B-- +//! C--- +//! DX--- +//! ``` +//! + +use hibitset::BitSet; + +/// A matrix where only half of it is stored. See the lib documentation for more details. +#[derive(Debug, Clone)] +pub struct HalfMatrix { + size: u32, + collision_matrix: BitSet, +} + +impl HalfMatrix { + /// Creates a new half matrix of the given size. + /// This value represents the maximum number of indices you can have for both sides. + /// ABCD size = 4. + pub fn new(size: u32) -> Self { + if size > 16777216 { + panic!("Size of HalfMatrix too big! Maximum size is 5792 and requested size is {}.", size); + } + let size = (size * (size + 1)) / 2; + HalfMatrix { + size, + collision_matrix: BitSet::with_capacity(size), + } + } + + /// Enables the boolean for the position (row, column). + /// Row is required to be bigger or equal to column. + pub fn enable(&mut self, row: u32, column: u32) { + self.collision_matrix.add(self.index_of(row, column)); + } + + /// Disables the boolean for the position (row, column). + /// Row is required to be bigger or equal to column. + pub fn disable(&mut self, row: u32, column: u32) { + self.collision_matrix.remove(self.index_of(row, column)); + } + + /// Returns the boolean for the position (row, column). + /// Row is required to be bigger or equal to column. + pub fn contains(&self, row: u32, column: u32) -> bool { + self.collision_matrix.contains(self.index_of(row, column)) + } + + /// Gives the internal memory index of the bitset for the given (row, column) values. + /// The internal indexing starts at 0. This means that index_of(0,0) = 0. That is the position of (A, A). + /// Row is required to be bigger or equal to column. + pub(crate) fn index_of(&self, row: u32, column: u32) -> u32 { + debug_assert!(row >= column); + let row_sum = (row * (row + 1)) / 2; + let idx = row_sum + column; + idx + } +} + +#[cfg(test)] +mod tests { + use crate::*; + + #[test] + fn index_calculation() { + // 4x4 + // C,C (2,2) + // Expected: 5 + let m = HalfMatrix::new(4); + assert_eq!(m.index_of(2,2), 5); + } + + #[test] + fn index_calculation2() { + // 4x4 + // D,C (3,2) + // Expected: 9 + let m = HalfMatrix::new(4); + assert_eq!(m.index_of(3,2), 8); + } + + #[test] + fn max_size_okay() { + let size = 5792; + HalfMatrix::new(size); + } + + #[test] + #[should_panic] + fn max_size_too_big() { + let size = 5793; + HalfMatrix::new(size); + } + + #[test] + fn enable() { + // 3x3 + // + // 012 + // + // 2 oxo + // 1 xx + // 0 o + + let mut m = HalfMatrix::new(3); + m.enable(2, 0); + m.enable(2, 2); + m.enable(0, 0); + + assert!(m.contains(2,0)); + assert!(m.contains(2,2)); + assert!(m.contains(0,0)); + + assert!(!m.contains(1,0)); + assert!(!m.contains(1,1)); + assert!(!m.contains(2,1)); + } + + #[test] + #[should_panic] + fn out_of_range() { + let m = HalfMatrix::new(3); + m.contains(0,1); + } +}