Struct qwt::qvector::rs_qvector::RSQVector

pub struct RSQVector<S> { /* private fields */ }

The generic S is the data structure used to provide rank/select support at the level of blocks.

Implementations

impl<S> RSQVector<S>

pub fn iter(&self) -> QVectorIterator<&QVector>

Returns an iterator over the values in the quad vector.

Examples

use qwt::RSQVector256;

let rsqv: RSQVector256 = (0..10_u64).into_iter().map(|x| x % 4).collect();

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

impl<S: RSSupport> RSQVector<S>

pub fn new<T>(v: &[T]) -> Self

where T: Unsigned + Copy, QVector: FromIterator<T>,

Creates a quad vector with support for RankQuad and SelectQuad queries for a sequence of integers in the range [0, 3].

Panics

Panics if the vector is longer than the largest possible length 2^{43}-1 symbols. If you need longer vectors, consider using a vector of RSQVectors, each of length smaller than 2^{43} symbols. This limit is due to two different reasons: - The number of occurrences of a symbol up to the beginning of its superblock is stored in 44 bits. - A select sample stores a superblock id. The size of a superblock is at least 2048 symbols, thus a superblock id for a sequence of length 2^{43}-1 fits in 32 bits.

Examples

use qwt::RSQVector256;

let v: Vec<u64> = (0..10).into_iter().map(|x| x % 4).collect();
let rsqv = RSQVector256::new(&v);

assert_eq!(rsqv.is_empty(), false);
assert_eq!(rsqv.len(), 10);

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

Checks if the vector is empty.

Trait Implementations

impl<S> AccessQuad for RSQVector<S>

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

Accesses the i-th value in the quad vector. The caller must guarantee that the position i is valid.

Safety

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

Examples

use qwt::{RSQVector256, AccessQuad};

let rsqv: RSQVector256 = (0..10_u64).into_iter().map(|x| x % 4).collect();

assert_eq!(unsafe { rsqv.get_unchecked(0) }, 0);
assert_eq!(unsafe { rsqv.get_unchecked(1) }, 1);

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

Accesses the ith value in the quad vector or None if out of bounds.

Examples

use qwt::{RSQVector256, AccessQuad};

let rsqv: RSQVector256 = (0..10_u64).into_iter().map(|x| x % 4).collect();

assert_eq!(rsqv.get(0), Some(0));
assert_eq!(rsqv.get(1), Some(1));
assert_eq!(rsqv.get(10), None);

impl<S> AsRef<RSQVector<S>> for RSQVector<S>

fn as_ref(&self) -> &RSQVector<S>

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

impl<S: Clone> Clone for RSQVector<S>

fn clone(&self) -> RSQVector<S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<S: Debug> Debug for RSQVector<S>

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

Formats the value using the given formatter.

impl<S: Default> Default for RSQVector<S>

fn default() -> RSQVector<S>

Returns the “default value” for a type.

impl<'de, S> Deserialize<'de> for RSQVector<S>

where S: Deserialize<'de>,

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<S: RSSupport> From<QVector> for RSQVector<S>

fn from(qv: QVector) -> Self

Converts a given quad vector qv into a RSQVector with support for rank and select queries.

Examples

use qwt::RSQVector256;

let rsqv: RSQVector256 = (0..10_u64).into_iter().map(|x| x % 4).collect();

assert_eq!(rsqv.is_empty(), false);
assert_eq!(rsqv.len(), 10);

impl<T, S: RSSupport> FromIterator<T> for RSQVector<S>

where T: PrimInt + AsPrimitive<u8>,

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

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<'a, S> IntoIterator for &'a RSQVector<S>

type IntoIter = QVectorIterator<&'a QVector>

Which kind of iterator are we turning this into?

type Item = u8

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<S> IntoIterator for RSQVector<S>

type IntoIter = QVectorIterator<QVector>

Which kind of iterator are we turning this into?

type Item = u8

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<S: PartialEq> PartialEq for RSQVector<S>

fn eq(&self, other: &RSQVector<S>) -> 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<S: RSSupport> RankQuad for RSQVector<S>

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

Returns rank of symbol up to position i excluded. Returns None if out of bounds.

Examples

use qwt::{RSQVector256, RankQuad};

let rsqv: RSQVector256 = (0..10_u64).into_iter().map(|x| x % 4).collect();

assert_eq!(rsqv.rank(0, 0), Some(0));
assert_eq!(rsqv.rank(0, 1), Some(1));
assert_eq!(rsqv.rank(0, 2), Some(1));
assert_eq!(rsqv.rank(0, 10), Some(3));
assert_eq!(rsqv.rank(0, 11), None);

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

Returns rank of symbol up to position i excluded.

Safety

Calling this method with a position i larger than the length of the vector is undefined behavior.

impl<S: RSSupport> SelectQuad for RSQVector<S>

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

Returns the position of the ith occurrence of symbol. Returns None if i is not valid, i.e., if i == 0 or i is larger than the number of occurrences of symbol, or if symbol is not in [0..3].

Examples

use qwt::{RSQVector256, SelectQuad};

let rsqv: RSQVector256 = (0..10_u64).into_iter().map(|x| x % 4).collect();

assert_eq!(rsqv.select(0, 1), Some(0));
assert_eq!(rsqv.select(0, 2), Some(4));
assert_eq!(rsqv.select(0, 3), Some(8));
assert_eq!(rsqv.select(0, 0), None);
assert_eq!(rsqv.select(0, 4), None);

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

Returns the position of the ith occurrence of symbol.

Safety

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

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

impl<S> Serialize for RSQVector<S>

where S: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<S: SpaceUsage> SpaceUsage for RSQVector<S>

fn space_usage_byte(&self) -> usize

Gives the space usage in bytes of the data structure.

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<S: RSSupport> WTSupport for RSQVector<S>

fn occs(&self, symbol: u8) -> Option<usize>

Returns the number of occurrences of symbol in the indexed sequence, None if symbol is not in [0..3].

unsafe fn occs_unchecked(&self, symbol: u8) -> usize

Returns the number of occurrences of symbol in the indexed sequence.

Safety

Calling this method if the symbol is not in [0..3] is undefined behavior.

fn occs_smaller(&self, symbol: u8) -> Option<usize>

Returns the number of occurrences of all the symbols smaller than the input symbol, None if symbol is not in [0..3].

unsafe fn occs_smaller_unchecked(&self, symbol: u8) -> usize

Returns the number of occurrences of all the symbols smaller than the input symbol in the indexed sequence.

Safety

Calling this method if the symbol is not in [0..3] is undefined behavior.

unsafe fn rank_block_unchecked(&self, symbol: u8, i: usize) -> usize

Returns the rank of symbol up to the block that contains the position i.

Safety

Calling this method if the symbol is larger than 3 of if the position i is out of bound is undefined behavior.

fn prefetch_info(&self, pos: usize)

Prefetches counters of the superblock and blocks containing the position pos.

fn prefetch_data(&self, pos: usize)

Prefetches data containing the position pos.

impl<S> StructuralPartialEq for RSQVector<S>