Struct SparseVec

pub struct SparseVec<T> { /* private fields */ }

A SparseVec efficiently encodes a two-dimensional matrix of integers. The input matrix must be encoded as a one-dimensional vector of integers with a row-length. Given an “empty” value, the SparseVec uses row displacement to compress that value as described in “Storing a sparse table” by Robert Endre Tarjan and Andrew Chi-Chih Yao. Afterwards it encodes the result further using a PackedVec.

Example

extern crate sparsevec;
use sparsevec::SparseVec;

fn main() {
    let v:Vec<usize> = vec![1,0,0,0,
                            0,0,7,8,
                            9,0,0,3];
    let sv = SparseVec::from(&v, 0, 4);
    assert_eq!(sv.get(0,0).unwrap(), 1);
    assert_eq!(sv.get(1,2).unwrap(), 7);
    assert_eq!(sv.get(2,3).unwrap(), 3);
}

How it works

Let’s take as an example the two-dimensional vector

1 0 0
2 0 0
3 0 0
0 0 4

represented as a one dimensional vector v = [1,0,0,2,0,0,3,0,0,0,0,4] with row-length 3. Storing this vector in memory is wasteful as the majority of its elements is 0. We can compress this vector using row displacement, which merges all rows into a vector such that non-zero entries are never mapped to the same position. For the above example, this would result in the compressed vector c = [1,2,3,0,4]:

1 0 0
  2 0 0
    3 0 0
    0 0 4
---------
1 2 3 0 4

To retrieve values from the compressed vector, we need a displacement vector, which describes how much each row was shifted during the compression. For the above example, the displacement vector would be d = [0, 1, 2, 2]. In order to retrieve the value at position (2, 0), we can calculate its compressed position with pos = d[row] + col:

pos = d[2] + 0 // =2
value = c[pos] // =3

Implementations

impl<T> SparseVec<T>

where T: AsPrimitive<u64> + FromPrimitive + Ord + PrimInt + ToPrimitive + Unsigned + Clone + Copy + PartialEq, u64: AsPrimitive<T>,

pub fn from(v: &[T], empty_val: T, row_length: usize) -> SparseVec<T>

Constructs a new SparseVec from a Vec of unsigned integers where empty_val describes the values to be compressed and row_length the element size per row in the original two-dimensional vector.

Examples

use sparsevec::SparseVec;
let v:Vec<usize> = vec![1,2,3,4,5,6,7,8];
let sv = SparseVec::from(&v, 0, 4);
assert_eq!(sv.get(1,2).unwrap(), 7);

pub fn get(&self, r: usize, c: usize) -> Option<T>

Returns the value of the element at position (r,c), where r is a row and c is a column. Returns None if out of bounds.

Examples

use sparsevec::SparseVec;
let v:Vec<usize> = vec![1,2,3,4,5,6,7,8];
let sv = SparseVec::from(&v, 0, 4);
assert_eq!(sv.get(1,2).unwrap(), 7);

pub fn len(&self) -> usize

Returns the number of elements of the original input vector.

Examples

use sparsevec::SparseVec;
let v = vec![1,2,3,4];
let sv = SparseVec::from(&v, 0 as usize, 2);
assert_eq!(sv.len(), 4);

pub fn is_empty(&self) -> bool

Returns true if the SparseVec has no elements or false otherwise.

Examples

use sparsevec::SparseVec;
let v = Vec::new();
let sv = SparseVec::from(&v, 0 as usize, 0);
assert_eq!(sv.is_empty(), true);

Trait Implementations

impl<T: Debug> Debug for SparseVec<T>

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

Formats the value using the given formatter.