SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > Class Template Reference

A prefix code-shaped wavelet. More...

#include <wt_pc.hpp>

Public Types

enum  { lex_ordered = shape_type::lex_ordered }
typedef t_tree_strat::template type< wt_pctree_strat_type
typedef int_vector ::size_type size_type
typedef tree_strat_type::value_type value_type
typedef t_bitvector::difference_type difference_type
typedef random_access_const_iterator< wt_pcconst_iterator
typedef const_iterator iterator
typedef t_bitvector bit_vector_type
typedef t_rank rank_1_type
typedef t_select select_1_type
typedef t_select_zero select_0_type
typedef wt_tag index_category
typedef tree_strat_type::alphabet_category alphabet_category
typedef t_shape::template type< wt_pcshape_type
using node_type = typename tree_strat_type::node_type

Public Member Functions

 wt_pc ()
template<typename t_it>
 wt_pc (t_it begin, t_it end)
 Construct the wavelet tree from a sequence defined by two interators.
template<typename t_it>
 wt_pc (t_it begin, t_it end, std::string)
 wt_pc (wt_pc const &wt)
 Copy constructor.
 wt_pc (wt_pc &&wt)
wt_pcoperator= (wt_pc const &wt)
 Assignment operator.
wt_pcoperator= (wt_pc &&wt)
 Move assignment operator.
size_type size () const
 Returns the size of the original vector.
bool empty () const
 Returns whether the wavelet tree contains no data.
value_type operator[] (size_type i) const
 Recovers the i-th symbol of the original vector.
size_type rank (size_type i, value_type c) const
 Calculates how many symbols c are in the prefix [0..i-1].
std::pair< size_type, value_typeinverse_select (size_type i) const
 Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].
size_type select (size_type i, value_type c) const
 Calculates the ith occurrence of the symbol c in the supported vector.
void interval_symbols (size_type i, size_type j, size_type &k, std::vector< value_type > &cs, std::vector< size_type > &rank_c_i, std::vector< size_type > &rank_c_j) const
 For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).
template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
std::enable_if< shape_type::lex_ordered, t_ret_type >::type lex_count (size_type i, size_type j, value_type c) const
 How many symbols are lexicographic smaller/greater than c in [i..j-1].
template<class t_ret_type = std::tuple<size_type, size_type>>
std::enable_if< shape_type::lex_ordered, t_ret_type >::type lex_smaller_count (size_type i, value_type c) const
 How many symbols are lexicographic smaller than c in [0..i-1].
const_iterator begin () const
 Returns a const_iterator to the first element.
const_iterator end () const
 Returns a const_iterator to the element after the last element.
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream.
void load (std::istream &in)
 Loads the data structure from the given istream.
bool operator== (wt_pc const &other) const noexcept
 Equality operator.
bool operator!= (wt_pc const &other) const noexcept
 Inequality operator.
template<typename archive_t>
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
template<typename archive_t>
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
auto bit_vec (node_type const &v) const -> node_bv_container< t_bitvector >
 Random access container to bitvector of node v.
auto seq (node_type const &v) const -> random_access_container< std::function< value_type(size_type)> >
 Random access container to sequence of node v.
bool is_leaf (node_type const &v) const
 Checks if the node is a leaf node.
value_type sym (node_type const &v) const
 Symbol for a leaf.
bool empty (node_type const &v) const
 Indicates if node v is empty.
auto size (node_type const &v) const -> decltype(m_tree.size(v))
 Return the size of node v.
node_type root () const
 Returns the root node.
std::array< node_type, 2 > expand (node_type const &v) const
 Returns the two child nodes of an inner node.
std::array< range_vec_type, 2 > expand (node_type const &v, range_vec_type const &ranges) const
 Returns for each range its left and right child ranges.
std::array< range_vec_type, 2 > expand (node_type const &v, range_vec_type &&ranges) const
 Returns for each range its left and right child ranges.
std::array< range_type, 2 > expand (node_type const &v, range_type const &r) const
 Returns for a range its left and right child ranges.
std::pair< uint64_t, uint64_t > path (value_type c) const
 return the path to the leaf for a given symbol
std::pair< bool, value_typesymbol_gte (value_type c) const
 Returns for a symbol c the next larger or equal symbol in the WT.
std::pair< bool, value_typesymbol_lte (value_type c) const
 Returns for a symbol c the previous smaller or equal symbol in the WT.

Public Attributes

size_type const & sigma = m_sigma
bit_vector_type const & bv = m_bv

Detailed Description

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
class sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >

A prefix code-shaped wavelet.

Template Parameters
t_shapeShape of the tree ().
t_bitvectorUnderlying bitvector structure.
t_rankRank support for pattern 1 on the bitvector.
t_selectSelect support for pattern 1 on the bitvector.
t_select_zeroSelect support for pattern 0 on the bitvector.
t_tree_stratTree strategy determines alphabet and the tree class used to navigate the WT.

Definition at line 59 of file wt_pc.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef tree_strat_type::alphabet_category sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::alphabet_category

Definition at line 73 of file wt_pc.hpp.

◆ bit_vector_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_bitvector sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bit_vector_type

Definition at line 68 of file wt_pc.hpp.

◆ const_iterator

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef random_access_const_iterator<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::const_iterator

Definition at line 66 of file wt_pc.hpp.

◆ difference_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_bitvector::difference_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::difference_type

Definition at line 65 of file wt_pc.hpp.

◆ index_category

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef wt_tag sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::index_category

Definition at line 72 of file wt_pc.hpp.

◆ iterator

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::iterator

Definition at line 67 of file wt_pc.hpp.

◆ node_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::node_type = typename tree_strat_type::node_type

Definition at line 79 of file wt_pc.hpp.

◆ rank_1_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_rank sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::rank_1_type

Definition at line 69 of file wt_pc.hpp.

◆ select_0_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_select_zero sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select_0_type

Definition at line 71 of file wt_pc.hpp.

◆ select_1_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_select sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select_1_type

Definition at line 70 of file wt_pc.hpp.

◆ shape_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_shape::template type<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::shape_type

Definition at line 74 of file wt_pc.hpp.

◆ size_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef int_vector ::size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size_type

Definition at line 63 of file wt_pc.hpp.

◆ tree_strat_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef t_tree_strat::template type<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::tree_strat_type

Definition at line 62 of file wt_pc.hpp.

◆ value_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
typedef tree_strat_type::value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::value_type

Definition at line 64 of file wt_pc.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
anonymous enum
Enumerator
lex_ordered 

Definition at line 75 of file wt_pc.hpp.

Constructor & Destructor Documentation

◆ wt_pc() [1/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( )
inline

Definition at line 184 of file wt_pc.hpp.

◆ wt_pc() [2/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
template<typename t_it>
sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( t_it begin,
t_it end )
inline

Construct the wavelet tree from a sequence defined by two interators.

Parameters
beginIterator to the start of the input.
endIterator one past the end of the input.
Time complexity
$ \Order{n\log|\Sigma|}$, where $n=size$

Definition at line 194 of file wt_pc.hpp.

◆ wt_pc() [3/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
template<typename t_it>
sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( t_it begin,
t_it end,
std::string  )
inline

Definition at line 251 of file wt_pc.hpp.

◆ wt_pc() [4/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & wt)
inline

Copy constructor.

Definition at line 255 of file wt_pc.hpp.

◆ wt_pc() [5/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > && wt)
inline

Definition at line 269 of file wt_pc.hpp.

Member Function Documentation

◆ begin()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::begin ( ) const
inline

Returns a const_iterator to the first element.

Definition at line 701 of file wt_pc.hpp.

◆ bit_vec()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
auto sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bit_vec ( node_type const & v) const -> node_bv_container<t_bitvector>
inline

Random access container to bitvector of node v.

Definition at line 782 of file wt_pc.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
template<typename archive_t>
void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Definition at line 767 of file wt_pc.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
template<typename archive_t>
void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Definition at line 755 of file wt_pc.hpp.

◆ empty() [1/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 320 of file wt_pc.hpp.

◆ empty() [2/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::empty ( node_type const & v) const
inline

Indicates if node v is empty.

Definition at line 820 of file wt_pc.hpp.

◆ end()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Definition at line 707 of file wt_pc.hpp.

◆ expand() [1/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::array< node_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand ( node_type const & v) const
inline

Returns the two child nodes of an inner node.

Parameters
vAn inner node of a wavelet tree.
Returns
Return a pair of nodes (left child, right child).
Precondition
!is_leaf(v)

Definition at line 859 of file wt_pc.hpp.

◆ expand() [2/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::array< range_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand ( node_type const & v,
range_type const & r ) const
inline

Returns for a range its left and right child ranges.

Parameters
vAn inner node of an wavelet tree.
rA ranges [s,e], such that [s,e] is contained in v=[v_s,v_e].
Returns
A range pair. The first element of the range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.
Precondition
!is_leaf(v) and s>=v_s and e<=v_e

Definition at line 920 of file wt_pc.hpp.

◆ expand() [3/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::array< range_vec_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand ( node_type const & v,
range_vec_type && ranges ) const
inline

Returns for each range its left and right child ranges.

Parameters
vAn inner node of an wavelet tree.
rangesA vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e].
Returns
A vector a range pairs. The first element of each range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.
Precondition
!is_leaf(v) and s>=v_s and e<=v_e

Definition at line 890 of file wt_pc.hpp.

◆ expand() [4/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::array< range_vec_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand ( node_type const & v,
range_vec_type const & ranges ) const
inline

Returns for each range its left and right child ranges.

Parameters
vAn inner node of an wavelet tree.
rangesA vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e].
Returns
A vector a range pairs. The first element of each range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.
Precondition
!is_leaf(v) and s>=v_s and e<=v_e

Definition at line 874 of file wt_pc.hpp.

◆ interval_symbols()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::interval_symbols ( size_type i,
size_type j,
size_type & k,
std::vector< value_type > & cs,
std::vector< size_type > & rank_c_i,
std::vector< size_type > & rank_c_j ) const
inline

For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

Parameters
iThe start index (inclusive) of the interval.
jThe end index (exclusive) of the interval.
kReference for number of different symbols in [i..j-1].
csReference to a vector that will contain in cs[0..k-1] all symbols that occur in [i..j-1] in arbitrary order (if lex_ordered = false) and ascending order (if lex_ordered = true).
rank_c_iReference to a vector which equals rank_c_i[p] = rank(i,cs[p]), for $ 0 \leq p < k $.
rank_c_jReference to a vector which equals rank_c_j[p] = rank(j,cs[p]), for $ 0 \leq p < k $.
Time complexity
$ \Order{\min{\sigma, k \log \sigma}} $
Precondition
$ i \leq j \leq size() $ $ cs.size() \geq \sigma $ $ rank_{c_i}.size() \geq \sigma $ $ rank_{c_j}.size() \geq \sigma $

Definition at line 498 of file wt_pc.hpp.

◆ inverse_select()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::pair< size_type, value_type > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::inverse_select ( size_type i) const
inline

Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].

Parameters
iThe index of the symbol.
Returns
Pair (rank(wt[i],i),wt[i])
Time complexity
$ \Order{H_0} $
Precondition
$ i < size() $

Definition at line 411 of file wt_pc.hpp.

◆ is_leaf()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::is_leaf ( node_type const & v) const
inline

Checks if the node is a leaf node.

Definition at line 808 of file wt_pc.hpp.

◆ lex_count()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
std::enable_if< shape_type::lex_ordered, t_ret_type >::type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::lex_count ( size_type i,
size_type j,
value_type c ) const
inline

How many symbols are lexicographic smaller/greater than c in [i..j-1].

Parameters
iStart index (inclusive) of the interval.
jEnd index (exclusive) of the interval.
cSymbol c.
Returns
A triple containing:
  • rank(i,c)
  • #symbols smaller than c in [i..j-1]
  • #symbols greater than c in [i..j-1]
Precondition
$ i \leq j \leq size() $
Note
This method is only available if lex_ordered = true

Definition at line 575 of file wt_pc.hpp.

◆ lex_smaller_count()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
template<class t_ret_type = std::tuple<size_type, size_type>>
std::enable_if< shape_type::lex_ordered, t_ret_type >::type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::lex_smaller_count ( size_type i,
value_type c ) const
inline

How many symbols are lexicographic smaller than c in [0..i-1].

Parameters
iExclusive right bound of the range.
cSymbol c.
Returns
A tuple containing:
  • rank(i,c)
  • #symbols smaller than c in [0..i-1]
Precondition
$ i \leq size() $
Note
This method is only available if lex_ordered = true

Definition at line 647 of file wt_pc.hpp.

◆ load()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::load ( std::istream & in)
inline

Loads the data structure from the given istream.

Definition at line 729 of file wt_pc.hpp.

◆ operator!=()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator!= ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & other) const
inlinenoexcept

Inequality operator.

Definition at line 749 of file wt_pc.hpp.

◆ operator=() [1/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
wt_pc & sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator= ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > && wt)
inline

Move assignment operator.

Definition at line 295 of file wt_pc.hpp.

◆ operator=() [2/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
wt_pc & sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator= ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & wt)
inline

Assignment operator.

Definition at line 284 of file wt_pc.hpp.

◆ operator==()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator== ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & other) const
inlinenoexcept

Equality operator.

Definition at line 741 of file wt_pc.hpp.

◆ operator[]()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator[] ( size_type i) const
inline

Recovers the i-th symbol of the original vector.

Parameters
iIndex in the original vector.
Returns
The i-th symbol of the original vector.
Time complexity
$ \Order{H_0} $ on average, where $ H_0 $ is the zero order entropy of the sequence
Precondition
$ i < size() $

Definition at line 336 of file wt_pc.hpp.

◆ path()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::pair< uint64_t, uint64_t > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::path ( value_type c) const
inline

return the path to the leaf for a given symbol

Definition at line 934 of file wt_pc.hpp.

◆ rank()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::rank ( size_type i,
value_type c ) const
inline

Calculates how many symbols c are in the prefix [0..i-1].

Parameters
iExclusive right bound of the range.
cSymbol c.
Returns
Number of occurrences of symbol c in the prefix [0..i-1].
Time complexity
$ \Order{H_0} $ on average, where $ H_0 $ is the zero order entropy of the sequence
Precondition
$ i \leq size() $

Definition at line 371 of file wt_pc.hpp.

◆ root()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
node_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::root ( ) const
inline

Returns the root node.

Definition at line 849 of file wt_pc.hpp.

◆ select()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select ( size_type i,
value_type c ) const
inline

Calculates the ith occurrence of the symbol c in the supported vector.

Parameters
iThe ith occurrence.
cThe symbol c.
Time complexity
$ \Order{H_0} $ on average, where $ H_0 $ is the zero order entropy of the sequence
Precondition
$ 1 \leq i \leq rank(size(), c) $

Definition at line 443 of file wt_pc.hpp.

◆ seq()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
auto sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::seq ( node_type const & v) const -> random_access_container<std::function<value_type(size_type)>>
inline

Random access container to sequence of node v.

Definition at line 788 of file wt_pc.hpp.

◆ serialize()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
std::string name = "" ) const
inline

Serializes the data structure into the given ostream.

Definition at line 713 of file wt_pc.hpp.

◆ size() [1/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 314 of file wt_pc.hpp.

◆ size() [2/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
auto sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size ( node_type const & v) const -> decltype(m_tree.size(v))
inline

Return the size of node v.

Definition at line 826 of file wt_pc.hpp.

◆ sym()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::sym ( node_type const & v) const
inline

Symbol for a leaf.

Definition at line 814 of file wt_pc.hpp.

◆ symbol_gte()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::pair< bool, value_type > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::symbol_gte ( value_type c) const
inline

Returns for a symbol c the next larger or equal symbol in the WT.

Parameters
cthe symbol
Returns
A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 950 of file wt_pc.hpp.

◆ symbol_lte()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
std::pair< bool, value_type > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::symbol_lte ( value_type c) const
inline

Returns for a symbol c the previous smaller or equal symbol in the WT.

Parameters
cthe symbol
Returns
A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 961 of file wt_pc.hpp.

Member Data Documentation

◆ bv

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
bit_vector_type const& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bv = m_bv

Definition at line 181 of file wt_pc.hpp.

◆ sigma

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
size_type const& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::sigma = m_sigma

Definition at line 180 of file wt_pc.hpp.


The documentation for this class was generated from the following file:
  • /builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/wt_pc.hpp