Struct LcsArray

pub struct LcsArray { /* private fields */ }

An array that stores the lengths of the longest common suffixes of consecutive k-mers in colexicographic order.

Implementations

impl LcsArray

An LCS array implementation using ceil(log(k)) bits per element.

pub fn new(v: IntVector) -> Self

Construct from a pre-built LCS array stored in an IntVector.

pub fn access(&self, i: usize) -> usize

Access the LCS value at position i.

pub fn len(&self) -> usize

Returns the number of elements in the LCS array.

pub fn is_empty(&self) -> bool

Returns true iff the length of the array is zero.

pub fn size_in_bytes(&self) -> usize

Returns the number of bytes used by the LCS array.

pub fn serialize<W: Write>(&self, out: &mut W) -> Result<usize>

Serialize the LCS array to the given writer. The array can then later be loaded with LcsArray::load. Returns number of bytes written.

pub fn load<R: Read>(input: &mut R) -> Result<Self>

Load an LCS array that was previously serialized with LcsArray::serialize.

pub fn from_sbwt<SS: SubsetSeq + Sync>( sbwt: &SbwtIndex<SS>, n_threads: usize, ) -> Self

Build an LCS array using the given SBWT index. This runs an O(nk) time algorithm, where n is the number of k-mers in the padded spectrum encoded in the SBWT, and k is the length of the k-mers. The algorithm works by inverting the SBWT column by column, which takes 2n bytes of extra working space. The algorithm is described in the paper Longest Common Prefix Arrays for Succinct k-spectra.

Trait Implementations

impl Clone for LcsArray

fn clone(&self) -> LcsArray

Returns a copy of the value.

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

Performs copy-assignment from source.

impl ContractLeft for LcsArray

fn contract_left(&self, I: Range<usize>, target_len: usize) -> Range<usize>

Expands the interval by scanning left and right until the LCS value is less than target_len. This has worst case time complexity equal to the length of LCS array, but if used on short intervals, the performance is typically quite good.

impl Debug for LcsArray

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

Formats the value using the given formatter.

impl PartialEq for LcsArray

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

impl StructuralPartialEq for LcsArray