SDSL  3.0.0
Succinct Data Structure Library
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. More...
 
template<typename t_it >
 wt_pc (t_it begin, t_it end, std::string)
 
 wt_pc (const wt_pc &wt)
 Copy constructor. More...
 
 wt_pc (wt_pc &&wt)
 
wt_pcoperator= (const wt_pc &wt)
 Assignment operator. More...
 
wt_pcoperator= (wt_pc &&wt)
 Move assignment operator. More...
 
size_type size () const
 Returns the size of the original vector. More...
 
bool empty () const
 Returns whether the wavelet tree contains no data. More...
 
value_type operator[] (size_type i) const
 Recovers the i-th symbol of the original vector. More...
 
size_type rank (size_type i, value_type c) const
 Calculates how many symbols c are in the prefix [0..i-1]. More...
 
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]. More...
 
size_type select (size_type i, value_type c) const
 Calculates the ith occurrence of the symbol c in the supported vector. More...
 
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). More...
 
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]. More...
 
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]. More...
 
const_iterator begin () const
 Returns a const_iterator to the first element. More...
 
const_iterator end () const
 Returns a const_iterator to the element after the last element. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream. More...
 
void load (std::istream &in)
 Loads the data structure from the given istream. More...
 
bool operator== (wt_pc const &other) const noexcept
 Equality operator. More...
 
bool operator!= (wt_pc const &other) const noexcept
 Inequality operator. More...
 
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 (const node_type &v) const -> node_bv_container< t_bitvector >
 Random access container to bitvector of node v. More...
 
auto seq (const node_type &v) const -> random_access_container< std::function< value_type(size_type)>>
 Random access container to sequence of node v. More...
 
bool is_leaf (const node_type &v) const
 Checks if the node is a leaf node. More...
 
value_type sym (const node_type &v) const
 Symbol for a leaf. More...
 
bool empty (const node_type &v) const
 Indicates if node v is empty. More...
 
auto size (const node_type &v) const -> decltype(m_tree.size(v))
 Return the size of node v. More...
 
node_type root () const
 Returns the root node. More...
 
std::array< node_type, 2 > expand (const node_type &v) const
 Returns the two child nodes of an inner node. More...
 
std::array< range_vec_type, 2 > expand (const node_type &v, const range_vec_type &ranges) const
 Returns for each range its left and right child ranges. More...
 
std::array< range_vec_type, 2 > expand (const node_type &v, range_vec_type &&ranges) const
 Returns for each range its left and right child ranges. More...
 
std::array< range_type, 2 > expand (const node_type &v, const range_type &r) const
 Returns for a range its left and right child ranges. More...
 
std::pair< uint64_t, uint64_t > path (value_type c) const
 return the path to the leaf for a given symbol More...
 
std::pair< bool, value_typesymbol_gte (value_type c) const
 Returns for a symbol c the next larger or equal symbol in the WT. More...
 
std::pair< bool, value_typesymbol_lte (value_type c) const
 Returns for a symbol c the previous smaller or equal symbol in the WT. More...
 

Public Attributes

const size_typesigma = m_sigma
 
const bit_vector_typebv = 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 43 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 57 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 52 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 50 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 49 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 56 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 51 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 63 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 53 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 55 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 54 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 58 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 47 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 46 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 48 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 59 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 159 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 169 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 220 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 ( const wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > &  wt)
inline

Copy constructor.

Definition at line 225 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 239 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 654 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 ( const node_type v) const -> node_bv_container<t_bitvector>
inline

Random access container to bitvector of node v.

Definition at line 726 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 711 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 699 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 287 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 ( const node_type v) const
inline

Indicates if node v is empty.

Definition at line 757 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 657 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 ( const node_type 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 790 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 ( const node_type v,
const range_type 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 851 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 ( const node_type v,
const 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 805 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 ( const node_type 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 821 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 456 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 372 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 ( const node_type v) const
inline

Checks if the node is a leaf node.

Definition at line 751 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 529 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 600 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 676 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 696 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= ( const wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > &  wt)
inline

Assignment operator.

Definition at line 254 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 > &&  wt)
inline

Move assignment operator.

Definition at line 265 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 688 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 300 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 865 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 335 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 783 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 404 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 ( const node_type v) const -> random_access_container<std::function<value_type(size_type)>>
inline

Random access container to sequence of node v.

Definition at line 732 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 660 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 284 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 ( const node_type v) const -> decltype(m_tree.size(v))
inline

Return the size of node v.

Definition at line 760 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 ( const node_type v) const
inline

Symbol for a leaf.

Definition at line 754 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 881 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 889 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<>>
const bit_vector_type& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bv = m_bv

Definition at line 156 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<>>
const size_type& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::sigma = m_sigma

Definition at line 155 of file wt_pc.hpp.


The documentation for this class was generated from the following file: