Struct WaveletMatrix 

pub struct WaveletMatrix { /* private fields */ }

An immutable integer vector supporting rank/select-type queries.

Each item consists of the lowest 1 to 64 bits of a u64 value, as specified by the width of the vector. The vector is represented using WMCore. There is also an IntVector storing the starting position of each possible item value after the reordering done by the core. Hence a WaveletMatrix should only be used when most values in 0..(1 << width) are in use. The maximum length of the vector is approximately usize::MAX items.

A WaveletMatrix can be built from a Vec of unsigned integers using the From trait. The construction requires several passes over the input and uses the input vector as working space. Using smaller integer types helps reducing the space overhead during construction.

WaveletMatrix implements the following simple_sds traits:

• Basic functionality: Vector, Access
• Queries and operations: VectorIndex
• Serialization: Serialize

Overridden default implementations:

• VectorIndex::contains has a simple constant-time implementation.
• VectorIndex::inverse_select is effectively the same as Access::get.

Examples

use simple_sds_sbwt::ops::{Vector, Access, VectorIndex};
use simple_sds_sbwt::wavelet_matrix::WaveletMatrix;

// Construction
let source: Vec<u64> = vec![1, 0, 3, 1, 1, 2, 4, 5, 1, 2, 1, 7, 0, 1];
let wm = WaveletMatrix::from(source.clone());

// Access
assert_eq!(wm.len(), source.len());
assert_eq!(wm.width(), 3);
for i in 0..wm.len() {
    assert_eq!(wm.get(i), source[i]);
}
assert!(wm.iter().eq(source.iter().cloned()));

// Rank
assert_eq!(wm.rank(5, 3), 1);
assert_eq!(wm.rank(10, 2), 2);

// Select
assert_eq!(wm.select(2, 1), Some(4));
assert!(wm.select(1, 7).is_none());
assert_eq!(wm.select_iter(1, 2).next(), Some((1, 9)));

// Inverse select
let index = 7;
let inverse = wm.inverse_select(index).unwrap();
assert_eq!(inverse, (0, 5));
assert_eq!(wm.select(inverse.0, inverse.1), Some(index));

// Predecessor / successor
assert!(wm.predecessor(1, 3).next().is_none());
assert_eq!(wm.predecessor(2, 3).next(), Some((0, 2)));
assert_eq!(wm.successor(12, 0).next(), Some((1, 12)));
assert!(wm.successor(13, 0).next().is_none());

Notes

• WaveletMatrix never panics from I/O errors.

Trait Implementations

impl<'a> Access<'a> for WaveletMatrix

type Iter = AccessIter<'a, WaveletMatrix>

Iterator over the items in the vector.

fn get(&self, index: usize) -> <Self as Vector>::Item

Returns an item from the vector.

fn iter(&'a self) -> Self::Iter

Returns an iterator over the items in the vector.

fn get_or( &self, index: usize, value: <Self as Vector>::Item, ) -> <Self as Vector>::Item

Returns an item from the vector or the provided value if index is invalid.

fn is_mutable(&self) -> bool

Returns true if the underlying data is mutable.

fn set(&mut self, _: usize, _: <Self as Vector>::Item)

Sets an item in the vector.

impl Clone for WaveletMatrix

fn clone(&self) -> WaveletMatrix

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for WaveletMatrix

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

Formats the value using the given formatter.

impl From<Vec<u16>> for WaveletMatrix

fn from(source: Vec<u16>) -> Self

Converts to this type from the input type.

impl From<Vec<u32>> for WaveletMatrix

fn from(source: Vec<u32>) -> Self

Converts to this type from the input type.

impl From<Vec<u64>> for WaveletMatrix

fn from(source: Vec<u64>) -> Self

Converts to this type from the input type.

impl From<Vec<u8>> for WaveletMatrix

fn from(source: Vec<u8>) -> Self

Converts to this type from the input type.

impl From<Vec<usize>> for WaveletMatrix

fn from(source: Vec<usize>) -> Self

Converts to this type from the input type.

impl IntoIterator for WaveletMatrix

type Item = <WaveletMatrix as Vector>::Item

The type of the elements being iterated over.

type IntoIter = IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl PartialEq for WaveletMatrix

fn eq(&self, other: &WaveletMatrix) -> 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 Serialize for WaveletMatrix

fn serialize_header<T: Write>(&self, writer: &mut T) -> Result<()>

Serializes the header to the writer.

fn serialize_body<T: Write>(&self, writer: &mut T) -> Result<()>

Serializes the body to the writer.

fn load<T: Read>(reader: &mut T) -> Result<Self>

Loads the struct from the reader.

fn size_in_elements(&self) -> usize

Returns the size of the serialized struct in u64 elements.

fn serialize<T: Write>(&self, writer: &mut T) -> Result<()>

Serializes the struct to the writer.

fn size_in_bytes(&self) -> usize

Returns the size of the serialized struct in bytes.

impl Vector for WaveletMatrix

type Item = u64

The type of the items in the vector.

fn len(&self) -> usize

Returns the number of items in the vector.

fn width(&self) -> usize

Returns the width of of an item in bits.

fn max_len(&self) -> usize

Returns the maximum length of the vector.

fn is_empty(&self) -> bool

Returns true if the vector is empty.

impl<'a> VectorIndex<'a> for WaveletMatrix

type ValueIter = ValueIter<'a>

Iterator type over the occurrences of a specific item.

fn contains(&self, value: <Self as Vector>::Item) -> bool

Returns true if the vector contains an item with the given value.

fn rank(&self, index: usize, value: <Self as Vector>::Item) -> usize

Returns the number of indexes i < index in vector such that self.get(i) == value.

fn inverse_select( &self, index: usize, ) -> Option<(usize, <Self as Vector>::Item)>

Computes the inverse of VectorIndex::select, or returns None if index is invalid.

fn value_iter(&'a self, value: <Self as Vector>::Item) -> Self::ValueIter

Returns an iterator over the occurrences of item value.

fn value_of(iter: &Self::ValueIter) -> <Self as Vector>::Item

Returns the value of the items iterated over by the iterator.

fn select(&self, rank: usize, value: <Self as Vector>::Item) -> Option<usize>

Returns the index of the vector that contains the occurrence of item value of rank rank.

fn select_iter( &'a self, rank: usize, value: <Self as Vector>::Item, ) -> Self::ValueIter

Returns an iterator at the occurrence of item value of rank rank.

fn predecessor( &'a self, index: usize, value: <Self as Vector>::Item, ) -> Self::ValueIter

Returns an iterator at the last occurrence i <= index of item value.

fn successor( &'a self, index: usize, value: <Self as Vector>::Item, ) -> Self::ValueIter

Returns an iterator at the first occurrence i >= index of item value.

impl Eq for WaveletMatrix

impl StructuralPartialEq for WaveletMatrix