Struct qwt::quadwt::QWaveletTree
source · pub struct QWaveletTree<T, RS, const WITH_PREFETCH_SUPPORT: bool = false> { /* private fields */ }
Expand description
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 extra informationa are needed only for sequences such that data
about superblocks and blocks do not fit in L3 cache.
Implementations§
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
sourcepub fn new(sequence: &mut [T]) -> Self
pub fn new(sequence: &mut [T]) -> Self
Builds the wavelet tree of the sequence
of unsigned integers.
The input `sequence`` will be 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 mut data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];
let qwt = QWT256::new(&mut data);
assert_eq!(qwt.len(), 8);
sourcepub fn len(&self) -> usize
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);
sourcepub fn sigma(&self) -> Option<T>
pub fn sigma(&self) -> Option<T>
Returns the largest value in the sequence, or None
if the sequence is empty.
Note: that for us sigma is the largest value and not the largest value plus 1 as common because the latter may overflow.
§Examples
use qwt::QWT256;
let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];
let qwt = QWT256::from(data);
assert_eq!(qwt.sigma(), Some(5));
sourcepub fn is_empty(&self) -> bool
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);
sourcepub fn n_levels(&self) -> usize
pub fn n_levels(&self) -> usize
Returns the number of levels in the wavelet tree.
The number of levels represents the depth of the wavelet tree.
§Examples
use qwt::QWT256;
let data = vec![1u8, 0, 1, 0, 255, 4, 5, 3];
let qwt = QWT256::from(data);
assert_eq!(qwt.n_levels(), 4);
sourcepub fn iter(
&self,
) -> QWTIterator<T, RS, &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>, WITH_PREFETCH_SUPPORT> ⓘ
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.clone());
assert_eq!(qwt.iter().collect::<Vec<_>>(), data);
assert_eq!(qwt.iter().rev().collect::<Vec<_>>(), data.into_iter().rev().collect::<Vec<_>>());
sourcepub fn rank_prefetch(&self, symbol: T, i: usize) -> Option<usize>
pub fn rank_prefetch(&self, symbol: T, i: usize) -> Option<usize>
Returns the 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 the rank
function, rank_prefetch
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
function 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
sourcepub unsafe fn rank_prefetch_unchecked(&self, symbol: T, i: usize) -> usize
pub unsafe fn rank_prefetch_unchecked(&self, symbol: T, i: usize) -> usize
Returns the rank of symbol
up to position i
excluded.
Differently from the rank_unchecked
function, rank_prefetch
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
function 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§
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> AccessUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> AccessUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn get(&self, i: usize) -> Option<Self::Item>
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);
source§unsafe fn get_unchecked(&self, i: usize) -> Self::Item
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.
Users must ensure that the index i
is within the bounds of the sequence.
§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
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> AsRef<QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> AsRef<QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn as_ref(&self) -> &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
fn as_ref(&self) -> &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§impl<T: Clone, RS: Clone, const WITH_PREFETCH_SUPPORT: bool> Clone for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T: Clone, RS: Clone, const WITH_PREFETCH_SUPPORT: bool> Clone for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn clone(&self) -> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
fn clone(&self) -> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<T: Debug, RS: Debug, const WITH_PREFETCH_SUPPORT: bool> Debug for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T: Debug, RS: Debug, const WITH_PREFETCH_SUPPORT: bool> Debug for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§impl<T: Default, RS: Default, const WITH_PREFETCH_SUPPORT: bool> Default for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T: Default, RS: Default, const WITH_PREFETCH_SUPPORT: bool> Default for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn default() -> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
fn default() -> QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§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>,
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>,
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, RS, const WITH_PREFETCH_SUPPORT: bool> From<Vec<T>> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> From<Vec<T>> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> FromIterator<T> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> FromIterator<T> for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
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, T, RS, const WITH_PREFETCH_SUPPORT: bool> IntoIterator for &'a QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<'a, T, RS, const WITH_PREFETCH_SUPPORT: bool> IntoIterator for &'a QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> IntoIterator for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> IntoIterator for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§impl<T: PartialEq, RS: PartialEq, const WITH_PREFETCH_SUPPORT: bool> PartialEq for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T: PartialEq, RS: PartialEq, const WITH_PREFETCH_SUPPORT: bool> PartialEq for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn eq(&self, other: &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>) -> bool
fn eq(&self, other: &QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>) -> bool
self
and other
values to be equal, and is used
by ==
.source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> RankUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> RankUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn rank(&self, symbol: Self::Item, i: usize) -> Option<usize>
fn rank(&self, symbol: Self::Item, i: usize) -> Option<usize>
Returns the 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
source§unsafe fn rank_unchecked(&self, symbol: Self::Item, i: usize) -> usize
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
or with an invalid symbol is undefined behavior.
Users must ensure that the position i
is within the bounds of the sequence
and that the symbol is valid.
§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);
}
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> SelectUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> SelectUnsigned for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn select(&self, symbol: Self::Item, i: usize) -> Option<usize>
fn select(&self, symbol: Self::Item, i: usize) -> Option<usize>
Returns the position of the i+1
-th occurrence of symbol symbol
.
None
is returned if the is no (i+1)th 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(2));
assert_eq!(qwt.select(0, 1), Some(3));
assert_eq!(qwt.select(0, 2), None);
assert_eq!(qwt.select(1, 0), Some(0));
assert_eq!(qwt.select(5, 0), Some(6));
assert_eq!(qwt.select(6, 1), None);
source§unsafe fn select_unchecked(&self, symbol: Self::Item, i: usize) -> usize
unsafe fn select_unchecked(&self, symbol: Self::Item, i: usize) -> usize
Returns the position of the i+1
-th occurrence of symbol symbol
.
§Safety
Calling this method with a value of i
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 efficiency reason to prefer this
unsafe select
over the safe one.
source§impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Serialize for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Serialize for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§impl<T, RS: SpaceUsage, const WITH_PREFETCH_SUPPORT: bool> SpaceUsage for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS: SpaceUsage, const WITH_PREFETCH_SUPPORT: bool> SpaceUsage for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
source§fn space_usage_byte(&self) -> usize
fn space_usage_byte(&self) -> usize
Gives the space usage in bytes of the struct.
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
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> StructuralPartialEq for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
Auto Trait Implementations§
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Freeze for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>where
T: Freeze,
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> RefUnwindSafe for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>where
T: RefUnwindSafe,
RS: RefUnwindSafe,
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Send for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Sync for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> Unpin for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>
impl<T, RS, const WITH_PREFETCH_SUPPORT: bool> UnwindSafe for QWaveletTree<T, RS, WITH_PREFETCH_SUPPORT>where
T: UnwindSafe,
RS: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)