Struct SparseVec 

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

A vector that can be stored in either dense or sparse format.

Useful for compressing repeated values.

Implementations

impl<T> SparseVec<T>

pub fn new() -> Self

Creates a new empty sparse vector in dense format.

Examples

use timsrust_utils::vec::SparseVec;
let sv: SparseVec<u32> = SparseVec::new();
assert_eq!(sv.len(), 0);
assert!(sv.is_dense());

pub fn sparse() -> Self

Creates a new empty sparse vector in sparse format.

Examples

use timsrust_utils::vec::SparseVec;
let sv: SparseVec<u32> = SparseVec::sparse();
assert_eq!(sv.len(), 0);
assert!(sv.is_sparse());

pub fn sparse_from_offsets( vals: Vec<T>, offsets: Vec<usize>, ) -> Result<Self, SparseVecError>

Creates a new sparse vector from values and offsets.

The vals vector contains the unique values, and offsets specifies the start of each run. The length of offsets must be one more than the length of vals, and must be non-decreasing.

Examples

use timsrust_utils::vec::SparseVec;
let vals = vec![1, 2];
let offsets = vec![0, 2, 5];
let sv = SparseVec::sparse_from_offsets(vals, offsets).unwrap();
assert_eq!(sv.iter().collect::<Vec<_>>(), vec![1, 1, 2, 2, 2]);

pub fn get_offsets(&self) -> Option<&[usize]>

Returns the offsets array if the vector is in sparse format, or None if dense.

Examples

use timsrust_utils::vec::SparseVec;
let vals = vec![1, 2];
let offsets = vec![0, 2, 5];
let sv = SparseVec::sparse_from_offsets(vals, offsets.clone()).unwrap();
assert_eq!(sv.get_offsets(), Some(&offsets[..]));

let dv: SparseVec<u32> = SparseVec::dense();
assert_eq!(dv.get_offsets(), None);

pub fn dense() -> Self

Creates a new empty sparse vector in dense format.

Examples

use timsrust_utils::vec::SparseVec;
let sv: SparseVec<u32> = SparseVec::dense();
assert_eq!(sv.len(), 0);
assert!(sv.is_dense());

pub fn len(&self) -> usize

Returns the total number of elements in the vector.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::dense();
sv.push(1);
sv.push(2);
assert_eq!(sv.len(), 2);

pub fn push(&mut self, val: T)

where T: PartialEq,

Appends an element to the vector.

In sparse format, consecutive equal values are compressed.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::sparse();
sv.push(1);
sv.push(1);
sv.push(2);
assert_eq!(sv.len(), 3);

pub fn compress(&mut self)

where T: PartialEq + Copy,

Compresses the vector from dense to sparse format if it saves memory.

Only compresses if the sparse representation uses less memory than the dense one.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::new();
for i in 0..100 {
    sv.push(i / 25);
}
assert_eq!(sv.len(), 100);
assert!(sv.is_dense());
let mut sv2 = sv.clone();
sv2.compress();
assert!(sv2.is_sparse());
assert_eq!(Vec::from(sv), Vec::from(sv2));

pub fn size_of(&self) -> usize

Returns the memory usage in bytes.

Examples

use timsrust_utils::vec::SparseVec;
let mut dv: SparseVec<u32> = SparseVec::dense();
for i in 0..100 {
    dv.push(i / 25);
}
let mut sv = dv.clone();
sv.compress();
assert!(sv.size_of() < dv.size_of());

pub fn iter(&self) -> SparseVecIter<'_, T>

Returns an iterator over all elements in the vector.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::dense();
sv.push(1);
sv.push(2);
let v: Vec<_> = sv.iter().collect();
assert_eq!(v, vec![1, 2]);

pub fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

Examples

use timsrust_utils::vec::SparseVec;
let sv: SparseVec<u32> = SparseVec::sparse();
assert_eq!(sv.len(), 0);

pub fn is_dense(&self) -> bool

Returns true if the vector is in dense format.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv: SparseVec<u32> = SparseVec::dense();
assert!(sv.is_dense());

pub fn is_sparse(&self) -> bool

Returns true if the vector is in sparse format.

Examples

use timsrust_utils::vec::SparseVec;
let sv: SparseVec<u32> = SparseVec::sparse();
assert!(sv.is_sparse());

pub fn argsort(&self) -> Vec<usize>

where T: Ord + Copy,

Returns the indices that would sort the vector.

The returned vector contains the indices of the elements in sorted order.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::dense();
sv.push(3);
sv.push(1);
sv.push(2);
let sorted_indices = sv.argsort();
assert_eq!(sorted_indices, vec![1, 2, 0]);

let mut sv = SparseVec::sparse();
sv.push(2);
sv.push(2);
sv.push(1);
sv.push(1);
sv.push(1);
let sorted_indices = sv.argsort();
assert_eq!(sorted_indices, vec![2, 3, 0, 1, 2]);

Trait Implementations

impl<T: Clone> Clone for SparseVec<T>

fn clone(&self) -> SparseVec<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<T: Default> Default for SparseVec<T>

fn default() -> SparseVec<T>

Returns the “default value” for a type.

impl<T: Eq> Eq for SparseVec<T>

impl<T: Copy> From<&SparseVec<T>> for Vec<T>

fn from(sparse: &SparseVec<T>) -> Self

Converts a SparseVec into a regular Vec, expanding any compressed values.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::sparse();
sv.push(1);
sv.push(1);
sv.push(2);
let v: Vec<_> = Vec::from(sv);
assert_eq!(v, vec![1, 1, 2]);

impl<T: Copy> From<SparseVec<T>> for Vec<T>

fn from(sparse: SparseVec<T>) -> Self

Converts a SparseVec into a regular Vec, expanding any compressed values.

Examples

use timsrust_utils::vec::SparseVec;
let mut sv = SparseVec::sparse();
sv.push(1);
sv.push(1);
sv.push(2);
let v: Vec<_> = Vec::from(sv);
assert_eq!(v, vec![1, 1, 2]);

impl<T: Copy + PartialEq> From<Vec<T>> for SparseVec<T>

fn from(vec: Vec<T>) -> Self

Converts a regular Vec into a compressed SparseVec.

Examples

use timsrust_utils::vec::SparseVec;
let mut v = Vec::new();
for i in 0..100 {
    v.push(i / 25);
}
let sv: SparseVec<_> = v.clone().into();
assert_eq!(sv.iter().collect::<Vec<_>>(), v);

impl<T: Hash> Hash for SparseVec<T>

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

Feeds this value into the given Hasher.

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

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: Ord> Ord for SparseVec<T>

fn cmp(&self, other: &SparseVec<T>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq for SparseVec<T>

fn eq(&self, other: &SparseVec<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialOrd> PartialOrd for SparseVec<T>

fn partial_cmp(&self, other: &SparseVec<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> StructuralPartialEq for SparseVec<T>