Struct terminus_store::structure::wavelettree::WaveletTree

pub struct WaveletTree { /* fields omitted */ }

A wavelet tree, encoding a u64 array for fast lookup of number positions.

A wavelet tree consists of a layer of bitarrays (stored as one big bitarray). The amount of layers is the log2 of the alphabet size, rounded up to make it an integer. Since we're encoding u64 values, the number of layers can never be larger than 64.

Implementations

impl WaveletTree

pub fn from_parts(bits: BitIndex, num_layers: u8) -> WaveletTree

Construct a wavelet tree from a bitindex and a layer count.

pub fn len(&self) -> usize

Returns the length of the encoded array.

pub fn num_layers(&self) -> usize

Returns the amount of layers.

pub fn decode(&self) -> impl Iterator<Item = u64>

Decode the wavelet tree to the original u64 sequence. This returns an iterator.

pub fn decode_one(&self, index: usize) -> u64

Decode a single position of the original u64 sequence.

pub fn lookup(&self, entry: u64) -> Option<WaveletLookup>

Lookup the given entry. This returns a WaveletLookup which can then be used to find all positions.

pub fn lookup_one(&self, entry: u64) -> Option<u64>

Lookup the given entry. This returns a single result, even if there's multiple.

Trait Implementations

impl Clone for WaveletTree

fn clone(&self) -> WaveletTree

Returns a copy of the value.

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

Performs copy-assignment from source.