Struct ldpc::SparseBinMat

pub struct SparseBinMat { /* fields omitted */ }

A sparse binary matrix optimized for row operations.

Implementations

impl SparseBinMat

pub fn new(
    number_of_columns: usize,
    rows: Vec<Vec<usize, Global>, Global>
) -> SparseBinMat

Creates a new matrix with the given number of columns and list of rows .

A row is a list of the positions where the elements have value 1. All rows are sorted during insertion.

Example

let matrix = SparseBinMat::new(4, vec![vec![0, 1, 2], vec![0, 2, 3]]);

assert_eq!(matrix.number_of_rows(), 2);
assert_eq!(matrix.number_of_columns(), 4);
assert_eq!(matrix.number_of_elements(), 8);

Panic

Panics if a position in a row is greater or equal the number of columns, a row is unsorted or a row contains duplicate.

pub fn try_new(
    number_of_columns: usize,
    rows: Vec<Vec<usize, Global>, Global>
) -> Result<SparseBinMat, InvalidPositions>

Creates a new matrix with the given number of columns and list of rows or returns an error if a position in a row is greater or equal the number of columns, a row is unsorted or a row contains duplicate.

A row is a list of the positions where the elements have value 1. All rows are sorted during insertion.

Example

let first_matrix = SparseBinMat::try_new(4, vec![vec![0, 1, 2], vec![0, 2, 3]]);
let second_matrix = SparseBinMat::new(4, vec![vec![0, 1, 2], vec![0, 2, 3]]);
assert_eq!(first_matrix, Ok(second_matrix));

pub fn identity(length: usize) -> SparseBinMat

Creates an identity matrix of the given length.

Example

let matrix = SparseBinMat::identity(5);

let identity_rows = (0..5).map(|x| vec![x]).collect();
let identity_matrix = SparseBinMat::new(5, identity_rows);

assert_eq!(matrix, identity_matrix);

pub fn zeros(number_of_rows: usize, number_of_columns: usize) -> SparseBinMat

Creates a matrix fill with zeros of the given dimensions.

Example

let matrix = SparseBinMat::zeros(2, 3);

assert_eq!(matrix.number_of_rows(), 2);
assert_eq!(matrix.number_of_columns(), 3);
assert_eq!(matrix.number_of_zeros(), 6);
assert_eq!(matrix.number_of_ones(), 0);

pub fn empty() -> SparseBinMat

Creates an empty matrix.

This allocate minimally, so it is a good placeholder.

Example

let matrix = SparseBinMat::empty();

assert_eq!(matrix.number_of_rows(), 0);
assert_eq!(matrix.number_of_columns(), 0); assert_eq!(matrix.number_of_elements(), 0);
// Note that these are not equal since new preallocate some space
// to store the data.
assert_ne!(SparseBinMat::new(0, Vec::new()), SparseBinMat::empty());

// To test for emptyness, you should prefer the following.
assert!(matrix.is_empty());

pub fn number_of_columns(&self) -> usize

Returns the number of columns in the matrix.

pub fn number_of_rows(&self) -> usize

Returns the number of rows in the matrix

pub fn dimension(&self) -> (usize, usize)

Returns the number of rows and columns in the matrix.

pub fn number_of_elements(&self) -> usize

Returns the number of elements in the matrix.

pub fn number_of_zeros(&self) -> usize

Returns the number of elements with value 0 in the matrix.

pub fn number_of_ones(&self) -> usize

Returns the number of elements with value 1 in the matrix.

pub fn is_empty(&self) -> bool

Returns true if the number of elements in the matrix is 0.

pub fn is_zero(&self) -> bool

Returns true if the all elements of the matrix are 0.

pub fn get(&self, row: usize, column: usize) -> Option<u8>

Returns the value at the given row and column or None if one of the index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.get(0, 0), Some(1));
assert_eq!(matrix.get(1, 0), Some(0));
assert_eq!(matrix.get(2, 0), None);

pub fn is_zero_at(&self, row: usize, column: usize) -> Option<bool>

Returns true if the value at the given row and column is 0 or None if one of the index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.is_zero_at(0, 0), Some(false));
assert_eq!(matrix.is_zero_at(1, 0), Some(true));
assert_eq!(matrix.is_zero_at(2, 0), None);

pub fn is_one_at(&self, row: usize, column: usize) -> Option<bool>

Returns true if the value at the given row and column is 1 or None if one of the index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.is_one_at(0, 0), Some(true));
assert_eq!(matrix.is_one_at(1, 0), Some(false));
assert_eq!(matrix.is_one_at(2, 0), None);

pub fn row(&self, row: usize) -> Option<SparseBinVecBase<&[usize]>>

Returns a reference to the given row of the matrix or None if the row index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows.clone());

assert_eq!(matrix.row(0), Some(SparseBinSlice::new(3, &rows[0])));
assert_eq!(matrix.row(1), Some(SparseBinSlice::new(3, &rows[1])));
assert_eq!(matrix.row(2), None);

pub fn rows(&self) -> Rows<'_>

Returns an iterator yielding the rows of the matrix as slice of non zero positions.

Example

let rows = vec![vec![0, 1, 2, 5], vec![1, 3, 4], vec![2, 4, 5], vec![0, 5]];
let matrix = SparseBinMat::new(7, rows.clone());

let mut iter = matrix.rows();

assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[0])));
assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[1])));
assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[2])));
assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[3])));
assert_eq!(iter.next(), None);

pub fn non_trivial_elements(&self) -> NonTrivialElements<'_>

Returns an iterator yielding the positions of the non trivial elements.

Example

let rows = vec![vec![0, 2], vec![1], vec![0, 2], vec![1]];
let matrix = SparseBinMat::new(3, rows);

let mut iter = matrix.non_trivial_elements();

assert_eq!(iter.next(), Some((0, 0)));
assert_eq!(iter.next(), Some((0, 2)));
assert_eq!(iter.next(), Some((1, 1)));
assert_eq!(iter.next(), Some((2, 0)));
assert_eq!(iter.next(), Some((2, 2)));
assert_eq!(iter.next(), Some((3, 1)));
assert_eq!(iter.next(), None);

pub fn row_weights(&'a self) -> impl Iterator<Item = usize> + 'a

Returns an iterator yielding the number of non zero elements in each row of the matrix.

Example

let rows = vec![vec![0, 1, 2, 5], vec![1, 3, 4], vec![2, 4, 5], vec![0, 5]];
let matrix = SparseBinMat::new(7, rows);

assert_eq!(matrix.row_weights().collect::<Vec<usize>>(), vec![4, 3, 3, 2]);

pub fn transposed(&self) -> SparseBinMat

Gets the transposed version of the matrix by swapping the columns with the rows.

Example

let rows = vec![vec![0, 1, 2], vec![1, 3], vec![0, 2, 3]];
let matrix = SparseBinMat::new(4, rows);

let transposed_matrix = matrix.transposed();

let expected_rows = vec![vec![0, 2], vec![0, 1], vec![0, 2], vec![1, 2]];
let expected_matrix = SparseBinMat::new(3, expected_rows);

assert_eq!(transposed_matrix, expected_matrix);

pub fn rank(&self) -> usize

Computes the rank of the matrix. That is, the number of linearly independent rows or columns.

Example

let rows = vec![vec![0, 1], vec![1, 2], vec![0, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.rank(), 2);

pub fn echelon_form(&self) -> SparseBinMat

Returns an echeloned version of the matrix.

A matrix in echelon form as the property that no rows any given row have a 1 in the first non trivial position of that row. Also, all rows are linearly independent.

Example

let matrix = SparseBinMat::new(3, vec![vec![0, 1, 2], vec![0], vec![1, 2], vec![0, 2]]);
let expected = SparseBinMat::new(3, vec![vec![0, 1, 2], vec![1], vec![2]]);
assert_eq!(matrix.echelon_form(), expected);

pub fn nullspace(&self) -> SparseBinMat

Returns a matrix for which the rows are the generators of the nullspace of the original matrix.

The nullspace of a matrix M is the set of vectors N such that Mx = 0 for all x in N. Therefore, if N is the nullspace matrix obtain from this function, we have that M * N^T = 0.

Example

let matrix = SparseBinMat::new(
    6,
    vec![vec![0, 1, 3, 5], vec![2, 3, 4], vec![2, 5], vec![0, 1, 3]],
);

let expected = SparseBinMat::new(6, vec![vec![0, 3, 4,], vec![0, 1]]);
let nullspace = matrix.nullspace();

assert_eq!(nullspace, expected);
assert_eq!(&matrix * &nullspace.transposed(), SparseBinMat::zeros(4, 2));

pub fn horizontal_concat_with(&self, other: &SparseBinMat) -> SparseBinMat

Returns the horizontal concatenation of two matrices.

If the matrix have different number of rows, the smallest one is padded with empty rows.

Example

let left_matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let right_matrix = SparseBinMat::new(4, vec![vec![1, 2, 3], vec![0, 1], vec![2, 3]]);

let concatened = left_matrix.horizontal_concat_with(&right_matrix);

let expected = SparseBinMat::new(7, vec![vec![0, 1, 4, 5, 6], vec![1, 2, 3, 4], vec![5, 6]]);

assert_eq!(concatened, expected);

pub fn vertical_concat_with(
    &self,
    other: &SparseBinMat
) -> Result<SparseBinMat, IncompatibleDimensions<(usize, usize), (usize, usize)>>

Returns the vertical concatenation of two matrices.

If the matrix have different number of columns, the smallest one is padded with empty columns.

Example

let left_matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let right_matrix = SparseBinMat::identity(3);

let concatened = left_matrix.vertical_concat_with(&right_matrix);
let expected = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2], vec![0], vec![1], vec![2]]);

assert_eq!(concatened, Ok(expected));

pub fn dot_with_vector<T>(
    &self,
    vector: &SparseBinVecBase<T>
) -> Result<SparseBinVecBase<Vec<usize, Global>>, IncompatibleDimensions<(usize, usize), usize>> where
    T: Deref<Target = [usize]>, 

Returns the dot product between a matrix and a vector or an error if the number of columns in the matrix is not equal to the length of the vector.

Use the Mul (*) operator for a version that panics instead of returning a Result.

Example

let matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let vector = SparseBinVec::new(3, vec![0, 1]);
let result = SparseBinVec::new(2, vec![1]);

assert_eq!(matrix.dot_with_vector(&vector), Ok(result));

pub fn dot_with_matrix(
    &self,
    other: &SparseBinMat
) -> Result<SparseBinMat, IncompatibleDimensions<(usize, usize), (usize, usize)>>

Returns the dot product between two matrices or an error if the number of columns in the first matrix is not equal to the number of rows in the second matrix.

Use the Mul (*) operator for a version that panics instead of returning a Result.

Example

let matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let other_matrix = SparseBinMat::new(4, vec![vec![1], vec![2], vec![3]]);
let result = SparseBinMat::new(4, vec![vec![1, 2], vec![2, 3]]);

assert_eq!(matrix.dot_with_matrix(&other_matrix), Ok(result));

pub fn bitwise_xor_with(
    &self,
    other: &SparseBinMat
) -> Result<SparseBinMat, IncompatibleDimensions<(usize, usize), (usize, usize)>>

Returns the bitwise xor sum of two matrices or an error if the matrices have different dimensions.

Use the Add (+) operator for a version that panics instead of returning a Result.

Example

let matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let other_matrix = SparseBinMat::new(3, vec![vec![0, 1, 2], vec![0, 1, 2]]);
let result = SparseBinMat::new(3, vec![vec![2], vec![0]]);

assert_eq!(matrix.bitwise_xor_with(&other_matrix), Ok(result));

pub fn keep_only_rows(
    &self,
    rows: &[usize]
) -> Result<SparseBinMat, InvalidPositions>

Returns a new matrix keeping only the given rows or an error if rows are out of bound, unsorted or not unique.

Example

use sparse_bin_mat::SparseBinMat;
let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![0, 2, 4],
]);

assert_eq!(matrix.keep_only_rows(&[0, 2]), Ok(truncated));
assert_eq!(matrix.keep_only_rows(&[0, 2, 3]).unwrap().number_of_rows(), 3);

pub fn without_rows(
    &self,
    rows: &[usize]
) -> Result<SparseBinMat, InvalidPositions>

Returns a truncated matrix where the given rows are removed or an error if rows are out of bound or unsorted.

Example

let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(5, vec![
    vec![2, 3, 4],
    vec![1, 3],
]);

assert_eq!(matrix.without_rows(&[0, 2]), Ok(truncated));
assert_eq!(matrix.without_rows(&[1, 2, 3]).unwrap().number_of_rows(), 1);

pub fn keep_only_columns(
    &self,
    columns: &[usize]
) -> Result<SparseBinMat, InvalidPositions>

Returns a new matrix keeping only the given columns or an error if columns are out of bound, unsorted or not unique.

Columns are relabeled to the fit new number of columns.

Example

use sparse_bin_mat::SparseBinMat;
let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(3, vec![
    vec![0, 1],
    vec![2],
    vec![0, 2],
    vec![1],
]);

assert_eq!(matrix.keep_only_columns(&[0, 1, 4]), Ok(truncated));
assert_eq!(matrix.keep_only_columns(&[1, 2]).unwrap().number_of_columns(), 2);

pub fn without_columns(
    &self,
    columns: &[usize]
) -> Result<SparseBinMat, InvalidPositions>

Returns a truncated matrix where the given columns are removed or an error if columns are out of bound or unsorted.

Columns are relabeled to fit the new number of columns.

Example

let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(3, vec![
    vec![0],
    vec![1, 2],
    vec![2],
    vec![0, 1],
]);

assert_eq!(matrix.without_columns(&[0, 2]), Ok(truncated));

Trait Implementations

impl<'_, '_> Add<&'_ SparseBinMat> for &'_ SparseBinMat

type Output = SparseBinMat

The resulting type after applying the + operator.

pub fn add(self, other: &SparseBinMat) -> SparseBinMat

Performs the + operation.

impl Clone for SparseBinMat

pub fn clone(&self) -> SparseBinMat

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SparseBinMat

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Display for SparseBinMat

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Eq for SparseBinMat

impl Hash for SparseBinMat

pub fn hash<__H>(&self, state: &mut __H) where
    __H: Hasher, 

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<'_, '_> Mul<&'_ SparseBinMat> for &'_ SparseBinMat

type Output = SparseBinMat

The resulting type after applying the * operator.

pub fn mul(self, other: &SparseBinMat) -> SparseBinMat

Performs the * operation.

impl<'_, '_, T> Mul<&'_ SparseBinVecBase<T>> for &'_ SparseBinMat where
    T: Deref<Target = [usize]>, 

type Output = SparseBinVecBase<Vec<usize, Global>>

The resulting type after applying the * operator.

pub fn mul(
    self,
    other: &SparseBinVecBase<T>
) -> SparseBinVecBase<Vec<usize, Global>>

Performs the * operation.

impl PartialEq<SparseBinMat> for SparseBinMat

pub fn eq(&self, other: &SparseBinMat) -> bool

This method tests for self and other values to be equal, and is used by ==.

pub fn ne(&self, other: &SparseBinMat) -> bool

This method tests for !=.

impl StructuralEq for SparseBinMat

impl StructuralPartialEq for SparseBinMat