Struct qwt::qvector::rs_qvector::RSQVector
source · pub struct RSQVector<S> { /* private fields */ }
Expand description
The generic S
is the data structure used to provide rank/select
support at the level of blocks.
Implementations§
source§impl<S: RSSupport> RSQVector<S>
impl<S: RSSupport> RSQVector<S>
sourcepub fn new<T>(v: &[T]) -> Self
pub fn new<T>(v: &[T]) -> Self
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 RSQVector
s,
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
Trait Implementations§
source§impl<S> AccessQuad for RSQVector<S>
impl<S> AccessQuad for RSQVector<S>
source§unsafe fn get_unchecked(&self, i: usize) -> u8
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);
source§fn get(&self, i: usize) -> Option<u8>
fn get(&self, i: usize) -> Option<u8>
Accesses the i
th 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);
source§impl<'de, S> Deserialize<'de> for RSQVector<S>where
S: Deserialize<'de>,
impl<'de, S> Deserialize<'de> for RSQVector<S>where
S: Deserialize<'de>,
source§fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
source§impl<T, S: RSSupport> FromIterator<T> for RSQVector<S>
impl<T, S: RSSupport> FromIterator<T> for RSQVector<S>
source§fn from_iter<I>(iter: I) -> Selfwhere
I: IntoIterator<Item = T>,
fn from_iter<I>(iter: I) -> Selfwhere
I: IntoIterator<Item = T>,
source§impl<'a, S> IntoIterator for &'a RSQVector<S>
impl<'a, S> IntoIterator for &'a RSQVector<S>
source§impl<S> IntoIterator for RSQVector<S>
impl<S> IntoIterator for RSQVector<S>
source§impl<S: PartialEq> PartialEq for RSQVector<S>
impl<S: PartialEq> PartialEq for RSQVector<S>
source§impl<S: RSSupport> RankQuad for RSQVector<S>
impl<S: RSSupport> RankQuad for RSQVector<S>
source§fn rank(&self, symbol: u8, i: usize) -> Option<usize>
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);
source§impl<S: RSSupport> SelectQuad for RSQVector<S>
impl<S: RSSupport> SelectQuad for RSQVector<S>
source§fn select(&self, symbol: u8, i: usize) -> Option<usize>
fn select(&self, symbol: u8, i: usize) -> Option<usize>
Returns the position of the i
th 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);
source§unsafe fn select_unchecked(&self, symbol: u8, i: usize) -> usize
unsafe fn select_unchecked(&self, symbol: u8, i: usize) -> usize
Returns the position of the i
th 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.
source§impl<S: SpaceUsage> SpaceUsage for RSQVector<S>
impl<S: SpaceUsage> SpaceUsage for RSQVector<S>
source§fn space_usage_byte(&self) -> usize
fn space_usage_byte(&self) -> usize
Gives the space usage in bytes of the data structure.
source§fn space_usage_KiB(&self) -> f64
fn space_usage_KiB(&self) -> f64
source§fn space_usage_MiB(&self) -> f64
fn space_usage_MiB(&self) -> f64
source§fn space_usage_GiB(&self) -> f64
fn space_usage_GiB(&self) -> f64
source§impl<S: RSSupport> WTSupport for RSQVector<S>
impl<S: RSSupport> WTSupport for RSQVector<S>
source§fn occs(&self, symbol: u8) -> Option<usize>
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].
source§unsafe fn occs_unchecked(&self, symbol: u8) -> usize
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.
source§fn occs_smaller(&self, symbol: u8) -> Option<usize>
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].
source§unsafe fn occs_smaller_unchecked(&self, symbol: u8) -> usize
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.
source§unsafe fn rank_block_unchecked(&self, symbol: u8, i: usize) -> usize
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.
source§fn prefetch_info(&self, pos: usize)
fn prefetch_info(&self, pos: usize)
Prefetches counters of the superblock and blocks containing the position pos
.
source§fn prefetch_data(&self, pos: usize)
fn prefetch_data(&self, pos: usize)
Prefetches data containing the position pos
.