[−][src]Struct sparsevec::SparseVec
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
Methods
impl<T: Clone + Copy + PartialEq> SparseVec<T> where
T: AsPrimitive<usize> + FromPrimitive + Ord + PrimInt + ToPrimitive + Unsigned,
usize: AsPrimitive<T>,
[src]
T: AsPrimitive<usize> + FromPrimitive + Ord + PrimInt + ToPrimitive + Unsigned,
usize: AsPrimitive<T>,
pub fn from(v: &[T], empty_val: T, row_length: usize) -> SparseVec<T>
[src]
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>
[src]
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
[src]
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
[src]
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);
Auto Trait Implementations
impl<T> Send for SparseVec<T> where
T: Send,
T: Send,
impl<T> Sync for SparseVec<T> where
T: Sync,
T: Sync,
impl<T> Unpin for SparseVec<T> where
T: Unpin,
T: Unpin,
impl<T> UnwindSafe for SparseVec<T> where
T: UnwindSafe,
T: UnwindSafe,
impl<T> RefUnwindSafe for SparseVec<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,