Struct qwt::quadwt::QWaveletTree

pub struct QWaveletTree<T, RS, const WITH_PREFETCH_SUPPORT: bool = false> { /* private fields */ }

The generic RS is the data structure we use to index a quaternary sequence to support access, rank, and select` queries.

The const generic PREFETCH_DATA specifies if the wavelet tree is augmented with extra data to support a deeper level of prefetching. This is needed only for sequences such that data about superblocks and blocks do not fit in L3 cache.

Implementations

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

pub fn new(sequence: &mut [T]) -> Self

Builds the wavelet tree of the sequence of unsigned integers. The input sequence is destroyed.

The alphabet size sigma is the largest value in the sequence. Both space usage and query time of a QWaveletTree depend on $$\lfloor\log_2 (\sigma-1)\rfloor + 1$$ (i.e., the length of the binary representation of values in the sequence). For this reason, it may be convenient for both space usage and query time to remap the alphabet to form a consecutive range [0, d], where d is the number of distinct values in sequence.

## Panics Panics if the sequence is longer than the largest possible length. The largest possible length is 2^{43} symbols.

Examples

use qwt::QWT256;

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.len(), 8);

pub fn len(&self) -> usize

Returns the length of the indexed sequence.

Examples

use qwt::QWT256;

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.len(), 8);

pub fn sigma(&self) -> T

Returns the largest value in the sequence. Note: it is not +1 because it may overflow.

pub fn is_empty(&self) -> bool

Checks if the indexed sequence is empty.

Examples

use qwt::QWT256;

let qwt = QWT256::<u8>::default();

assert_eq!(qwt.is_empty(), true);

pub fn n_levels(&self) -> usize

Returns the number of levels in the wavelet tree.

pub fn iter( &self ) -> QWTIterator<T, RS, &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>, WITH_PREFETCH_SUPPORT>

Returns an iterator over the values in the wavelet tree.

Examples

use qwt::QWT256;

let data: Vec<u8> = (0..10u8).into_iter().cycle().take(100).collect();

let qwt = QWT256::from(data);

for (i, v) in qwt.iter().enumerate() {
   assert_eq!((i%10) as u8, v);
}

pub fn rank_prefetch(&self, symbol: T, i: usize) -> Option<usize>

Returns rank of symbol up to position i excluded. None, is returned if i is out of bound or if symbol is not valid (i.e., it is greater than or equal to the alphabet size).

Differently from rank function, it runs a first phase in which it estimates the positions in the wavelet tree needed by rank queries and prefetches these data. It is faster than the original rank whenever the superblock/block counters fit in L3 cache but the sequence is larger.

Examples

use qwt::{QWT256, RankUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.rank_prefetch(1, 2), Some(1));
assert_eq!(qwt.rank_prefetch(3, 8), Some(1));
assert_eq!(qwt.rank_prefetch(1, 0), Some(0));
assert_eq!(qwt.rank_prefetch(1, 9), None);     // too large position
assert_eq!(qwt.rank_prefetch(6, 1), None);     // too large symbol

pub unsafe fn rank_prefetch_unchecked(&self, symbol: T, i: usize) -> usize

Returns rank of symbol up to position i excluded. Differently from rank_unchecked, it runs a first phase in which it estimates the positions in the wavelet tree needed by rank queries and prefetches these data. It is faster than the original rank whenever the superblock/block counters fit in L3 cache but the sequence is larger.

Safety

Calling this method with a position i larger than the size of the sequence of with invalid symbol is undefined behavior.

Examples

use qwt::{QWT256, RankUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

unsafe {
    assert_eq!(qwt.rank_prefetch_unchecked(1, 2), 1);
}

Trait Implementations

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> AccessUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

fn get(&self, i: usize) -> Option<Self::Item>

Returns the i-th symbol of the indexed sequence, None is returned if i is out of bound.

Examples

use qwt::{QWT256, AccessUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.get(2), Some(1));
assert_eq!(qwt.get(3), Some(0));
assert_eq!(qwt.get(8), None);

use qwt::{QWT256, AccessUnsigned, RankUnsigned, SelectUnsigned};

let data = vec![1u32, 0, 1, 0, 2, 1000000, 5, 3];
let qwt = QWT256::from(data);

assert_eq!(qwt.get(2), Some(1));
assert_eq!(qwt.get(5), Some(1000000));
assert_eq!(qwt.get(8), None);

unsafe fn get_unchecked(&self, i: usize) -> Self::Item

Returns the i-th symbol of the indexed sequence.

Safety

Calling this method with an out-of-bounds index is undefined behavior.

Examples

use qwt::{QWT256, AccessUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

unsafe {
    assert_eq!(qwt.get_unchecked(2), 1);
    assert_eq!(qwt.get_unchecked(3), 0);
}

type Item = T

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> AsRef<QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

fn as_ref(&self) -> &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

Converts this type into a shared reference of the (usually inferred) input type.

impl<T: Clone, RS: Clone, const WITH_PREFETCH_SUPPORT: bool> Clone for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

fn clone(&self) -> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, RS: Debug, const WITH_PREFETCH_SUPPORT: bool> Debug for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

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

Formats the value using the given formatter.

impl<T: Default, RS: Default, const WITH_PREFETCH_SUPPORT: bool> Default for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

fn default() -> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

Returns the “default value” for a type.

impl<'de, T, RS, const WITH_PREFETCH_SUPPORT: bool> Deserialize<'de> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: Deserialize<'de>, RS: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> From<Vec<T>> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

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

Converts to this type from the input type.

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> FromIterator<T> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<'a, T, RS, const WITH_PREFETCH_SUPPORT: bool> IntoIterator for &'a QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

type IntoIter = QWTIterator<T, RS, &'a QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>, WITH_PREFETCH_SUPPORT>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> IntoIterator for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

type IntoIter = QWTIterator<T, RS, QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>, WITH_PREFETCH_SUPPORT>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq, RS: PartialEq, const WITH_PREFETCH_SUPPORT: bool> PartialEq for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

fn eq(&self, other: &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> RankUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

fn rank(&self, symbol: Self::Item, i: usize) -> Option<usize>

Returns rank of symbol up to position i excluded. None, is returned if i is out of bound or if symbol is not valid (i.e., it is greater than or equal to the alphabet size).

Examples

use qwt::{QWT256, RankUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.rank(1, 2), Some(1));
assert_eq!(qwt.rank(3, 8), Some(1));
assert_eq!(qwt.rank(1, 0), Some(0));
assert_eq!(qwt.rank(1, 9), None);     // too large position
assert_eq!(qwt.rank(6, 1), None);     // too large symbol

unsafe fn rank_unchecked(&self, symbol: Self::Item, i: usize) -> usize

Returns rank of symbol up to position i excluded.

Safety

Calling this method with a position i larger than the size of the sequence of with invalid symbol is undefined behavior.

Examples

use qwt::{QWT256, RankUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

unsafe {
    assert_eq!(qwt.rank_unchecked(1, 2), 1);
}

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> SelectUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: WTIndexable, u8: AsPrimitive<T>, RS: RSforWT,

fn select(&self, symbol: Self::Item, i: usize) -> Option<usize>

Returns the position of the i-th occurrence of symbol symbol, None is returned if i is 0 or if there is no such occurrence for the symbol or if symbol is not valid (i.e., it is greater than or equal to the alphabet size).

Examples

use qwt::{QWT256, SelectUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.select(1, 1), Some(0));
assert_eq!(qwt.select(0, 2), Some(3));
assert_eq!(qwt.select(1, 0), None);
assert_eq!(qwt.select(6, 1), None);

unsafe fn select_unchecked(&self, symbol: Self::Item, i: usize) -> usize

Returns the position of the i-th occurrence of symbol symbol.

Safety

Calling this method with a value of i which is larger than the number of occurrences of the symbol or if the symbol is not valid is undefined behavior.

In the current implementation there is no reason to prefer this unsafe select over the safe one.

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Serialize for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

where T: Serialize, RS: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<T, RS: SpaceUsage, const WITH_PREFETCH_SUPPORT: bool> SpaceUsage for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>

fn space_usage_byte(&self) -> usize

Gives the space usage in bytes of the struct.

fn space_usage_KiB(&self) -> f64

Gives the space usage of the data structure in KiB.

fn space_usage_MiB(&self) -> f64

Gives the space usage of the data structure in MiB.

fn space_usage_GiB(&self) -> f64

Gives the space usage of the data structure in GiB.

impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> StructuralPartialEq for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>