SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero > Class Template Reference

A wavelet tree class for integer sequences. More...

#include <wt_int.hpp>

Classes

struct  node_type
 Represents a node in the wavelet tree. More...
 

Public Types

enum  { lex_ordered = 1 }
 
typedef int_vector ::size_type size_type
 
typedef int_vector ::value_type value_type
 
typedef t_bitvector::difference_type difference_type
 
typedef random_access_const_iterator< wt_intconst_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 int_alphabet_tag alphabet_category
 
typedef std::pair< value_type, size_typepoint_type
 
typedef std::vector< point_typepoint_vec_type
 
typedef std::pair< size_type, point_vec_typer2d_res_type
 

Public Member Functions

 wt_int ()=default
 Default constructor. More...
 
template<typename t_it >
 wt_int (t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
 Construct the wavelet tree from a sequence defined by two interators. More...
 
 wt_int (const wt_int &wt)
 Copy constructor. More...
 
 wt_int (wt_int &&wt)
 Move constructor. More...
 
wt_intoperator= (const wt_int &wt)
 Assignment operator. More...
 
wt_intoperator= (wt_int &&wt)
 Assignment move 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] of the supported vector. More...
 
std::pair< size_type, value_typeinverse_select (size_type i) const
 Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence. More...
 
size_type select (size_type i, value_type c) const
 Calculates the i-th 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>>
t_ret_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>>
t_ret_type lex_smaller_count (size_type i, value_type c) const
 How many symbols are lexicographic smaller than c in [0..i-1]. More...
 
std::pair< size_type, std::vector< std::pair< value_type, size_type > > > range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, bool report=true) const
 range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb]. More...
 
void _range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, size_type level, size_type ilb, size_type node_size, std::vector< size_type > &offsets, std::vector< size_type > &ones_before_os, size_type path, point_vec_type &point_vec, bool report, size_type &cnt_answers) const
 
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...
 
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)
 
bool operator== (wt_int const &other) const noexcept
 Equality operator. More...
 
bool operator!= (wt_int const &other) const noexcept
 Inequality operator. 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
 Returns the symbol of leaf node v. More...
 
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 empty (const node_type &v) const
 Indicates if node v is empty. More...
 
auto size (const node_type &v) const -> decltype(v.size)
 Return the size of node v. More...
 
node_type root () const
 Return 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< node_type, 2 > expand (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...
 

Public Attributes

const size_typesigma = m_sigma
 Effective alphabet size of the wavelet tree. More...
 
const bit_vector_typetree = m_tree
 A concatenation of all bit vectors of the wavelet tree. More...
 
const uint32_t & max_level = m_max_level
 Maximal level of the wavelet tree. More...
 

Protected Attributes

size_type m_size = 0
 
size_type m_sigma = 0
 
bit_vector_type m_tree
 
rank_1_type m_tree_rank
 
select_1_type m_tree_select1
 
select_0_type m_tree_select0
 
uint32_t m_max_level = 0
 

Detailed Description

template<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 sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >

A wavelet tree class for integer sequences.

Space complexity
$\Order{n\log|\Sigma|}$ bits, where $n$ is the size of the vector the wavelet tree was build for.
Template Parameters
t_bitvectorType of the bitvector used for representing the wavelet tree.
t_rankType of the support structure for rank on pattern 1.
t_selectType of the support structure for select on pattern 1.
t_select_zeroType of the support structure for select on pattern 0.

Definition at line 48 of file wt_int.hpp.

Member Typedef Documentation

◆ alphabet_category

template<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>
typedef int_alphabet_tag sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::alphabet_category

Definition at line 61 of file wt_int.hpp.

◆ bit_vector_type

template<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>
typedef t_bitvector sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vector_type

Definition at line 56 of file wt_int.hpp.

◆ const_iterator

template<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>
typedef random_access_const_iterator<wt_int> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::const_iterator

Definition at line 54 of file wt_int.hpp.

◆ difference_type

template<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>
typedef t_bitvector::difference_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::difference_type

Definition at line 53 of file wt_int.hpp.

◆ index_category

template<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>
typedef wt_tag sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::index_category

Definition at line 60 of file wt_int.hpp.

◆ iterator

template<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>
typedef const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::iterator

Definition at line 55 of file wt_int.hpp.

◆ point_type

template<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>
typedef std::pair<value_type, size_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::point_type

Definition at line 67 of file wt_int.hpp.

◆ point_vec_type

template<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>
typedef std::vector<point_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::point_vec_type

Definition at line 68 of file wt_int.hpp.

◆ r2d_res_type

template<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>
typedef std::pair<size_type, point_vec_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::r2d_res_type

Definition at line 69 of file wt_int.hpp.

◆ rank_1_type

template<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>
typedef t_rank sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::rank_1_type

Definition at line 57 of file wt_int.hpp.

◆ select_0_type

template<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>
typedef t_select_zero sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select_0_type

Definition at line 59 of file wt_int.hpp.

◆ select_1_type

template<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>
typedef t_select sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select_1_type

Definition at line 58 of file wt_int.hpp.

◆ size_type

template<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>
typedef int_vector ::size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size_type

Definition at line 51 of file wt_int.hpp.

◆ value_type

template<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>
typedef int_vector ::value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::value_type

Definition at line 52 of file wt_int.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<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>
anonymous enum
Enumerator
lex_ordered 

Definition at line 62 of file wt_int.hpp.

Constructor & Destructor Documentation

◆ wt_int() [1/4]

template<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>
sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( )
default

Default constructor.

◆ wt_int() [2/4]

template<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>
template<typename t_it >
sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( t_it  begin,
t_it  end,
std::string  tmp_dir = ram_file_name("") 
)
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.
tmp_dirTemporary directory for intermediate results.
Time complexity
$ \Order{n\log|\Sigma|}$, where $n=size$ I.e. we need \Order{n\log n} if rac is a permutation of 0..n-1.

Definition at line 156 of file wt_int.hpp.

◆ wt_int() [3/4]

template<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>
sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( const wt_int< t_bitvector, t_rank, t_select, t_select_zero > &  wt)
inline

Copy constructor.

Definition at line 244 of file wt_int.hpp.

◆ wt_int() [4/4]

template<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>
sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > &&  wt)
inline

Move constructor.

Definition at line 259 of file wt_int.hpp.

Member Function Documentation

◆ _range_search_2d()

template<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>
void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::_range_search_2d ( size_type  lb,
size_type  rb,
value_type  vlb,
value_type  vrb,
size_type  level,
size_type  ilb,
size_type  node_size,
std::vector< size_type > &  offsets,
std::vector< size_type > &  ones_before_os,
size_type  path,
point_vec_type point_vec,
bool  report,
size_type cnt_answers 
) const
inline

Definition at line 652 of file wt_int.hpp.

◆ begin()

template<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>
const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::begin ( ) const
inline

Returns a const_iterator to the first element.

Definition at line 749 of file wt_int.hpp.

◆ bit_vec()

template<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>
auto sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vec ( const node_type v) const -> node_bv_container<t_bitvector>
inline

Random access container to bitvector of node v.

Definition at line 865 of file wt_int.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<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>
template<typename archive_t >
void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 795 of file wt_int.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<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>
template<typename archive_t >
void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 783 of file wt_int.hpp.

◆ empty() [1/2]

template<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>
bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 307 of file wt_int.hpp.

◆ empty() [2/2]

template<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>
bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::empty ( const node_type v) const
inline

Indicates if node v is empty.

Definition at line 890 of file wt_int.hpp.

◆ end()

template<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>
const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Definition at line 752 of file wt_int.hpp.

◆ expand() [1/5]

template<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>
std::array< node_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 an array of nodes (left child, right child).
Precondition
!is_leaf(v)

Definition at line 903 of file wt_int.hpp.

◆ expand() [2/5]

template<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>
std::array< range_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 989 of file wt_int.hpp.

◆ expand() [3/5]

template<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>
std::array< range_vec_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 943 of file wt_int.hpp.

◆ expand() [4/5]

template<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>
std::array< range_vec_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 959 of file wt_int.hpp.

◆ expand() [5/5]

template<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>
std::array< node_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::expand ( node_type &&  v) const
inline

Returns the two child nodes of an inner node.

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

Definition at line 914 of file wt_int.hpp.

◆ interval_symbols()

template<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>
void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 ascending order.
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 505 of file wt_int.hpp.

◆ inverse_select()

template<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>
std::pair< size_type, value_type > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::inverse_select ( size_type  i) const
inline

Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.

Parameters
iThe index of the symbol.
Returns
Pair (rank(wt[i],i),wt[i])
Precondition
$ i < size() $

Definition at line 393 of file wt_int.hpp.

◆ is_leaf()

template<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>
bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::is_leaf ( const node_type v) const
inline

Checks if the node is a leaf node.

Definition at line 859 of file wt_int.hpp.

◆ lex_count()

template<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>
template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
t_ret_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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() $

Definition at line 542 of file wt_int.hpp.

◆ lex_smaller_count()

template<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>
template<class t_ret_type = std::tuple<size_type, size_type>>
t_ret_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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() $

Definition at line 592 of file wt_int.hpp.

◆ load()

template<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>
void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 771 of file wt_int.hpp.

◆ operator!=()

template<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>
bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator!= ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 818 of file wt_int.hpp.

◆ operator=() [1/2]

template<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>
wt_int & sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator= ( const wt_int< t_bitvector, t_rank, t_select, t_select_zero > &  wt)
inline

Assignment operator.

Definition at line 274 of file wt_int.hpp.

◆ operator=() [2/2]

template<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>
wt_int & sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator= ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > &&  wt)
inline

Assignment move operator.

Definition at line 285 of file wt_int.hpp.

◆ operator==()

template<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>
bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator== ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 810 of file wt_int.hpp.

◆ operator[]()

template<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>
value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator[] ( size_type  i) const
inline

Recovers the i-th symbol of the original vector.

Parameters
iThe index of the symbol in the original vector.
Returns
The i-th symbol of the original vector.
Precondition
$ i < size() $

Definition at line 315 of file wt_int.hpp.

◆ path()

template<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>
std::pair< uint64_t, uint64_t > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::path ( value_type  c) const
inline

return the path to the leaf for a given symbol

Definition at line 1003 of file wt_int.hpp.

◆ range_search_2d()

template<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>
std::pair< size_type, std::vector< std::pair< value_type, size_type > > > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::range_search_2d ( size_type  lb,
size_type  rb,
value_type  vlb,
value_type  vrb,
bool  report = true 
) const
inline

range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb].

Parameters
lbLeft bound of index interval (inclusive)
rbRight bound of index interval (inclusive)
vlbLeft bound of value interval (inclusive)
vrbRight bound of value interval (inclusive)
reportShould the matching points be returned?
Returns
Pair (#of found points, vector of points), the vector is empty when report = false.

Definition at line 635 of file wt_int.hpp.

◆ rank()

template<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>
size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::rank ( size_type  i,
value_type  c 
) const
inline

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

Parameters
iThe exclusive index of the prefix range [0..i-1], so $i\in[0..size()]$.
cThe symbol to count the occurrences in the prefix.
Returns
The number of occurrences of symbol c in the prefix [0..i-1] of the supported vector.
Time complexity
$ \Order{\log |\Sigma|} $
Precondition
$ i \leq size() $

Definition at line 354 of file wt_int.hpp.

◆ root()

template<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>
node_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::root ( ) const
inline

Return the root node.

Definition at line 896 of file wt_int.hpp.

◆ select()

template<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>
size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select ( size_type  i,
value_type  c 
) const
inline

Calculates the i-th occurrence of the symbol c in the supported vector.

Parameters
iThe i-th occurrence.
cThe symbol c.
Time complexity
$ \Order{\log |\Sigma|} $
Precondition
$ 1 \leq i \leq rank(size(), c) $

Definition at line 431 of file wt_int.hpp.

◆ seq()

template<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>
auto sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 871 of file wt_int.hpp.

◆ serialize()

template<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>
size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::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 755 of file wt_int.hpp.

◆ size() [1/2]

template<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>
size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 304 of file wt_int.hpp.

◆ size() [2/2]

template<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>
auto sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size ( const node_type v) const -> decltype(v.size)
inline

Return the size of node v.

Definition at line 893 of file wt_int.hpp.

◆ sym()

template<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>
value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::sym ( const node_type v) const
inline

Returns the symbol of leaf node v.

Definition at line 862 of file wt_int.hpp.

Member Data Documentation

◆ m_max_level

template<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>
uint32_t sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_max_level = 0
protected

Definition at line 78 of file wt_int.hpp.

◆ m_sigma

template<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>
size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_sigma = 0
protected

Definition at line 73 of file wt_int.hpp.

◆ m_size

template<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>
size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_size = 0
protected

Definition at line 72 of file wt_int.hpp.

◆ m_tree

template<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>
bit_vector_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree
protected

Definition at line 74 of file wt_int.hpp.

◆ m_tree_rank

template<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>
rank_1_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_rank
protected

Definition at line 75 of file wt_int.hpp.

◆ m_tree_select0

template<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>
select_0_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_select0
protected

Definition at line 77 of file wt_int.hpp.

◆ m_tree_select1

template<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>
select_1_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_select1
protected

Definition at line 76 of file wt_int.hpp.

◆ max_level

template<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>
const uint32_t& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::max_level = m_max_level

Maximal level of the wavelet tree.

Definition at line 141 of file wt_int.hpp.

◆ sigma

template<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>
const size_type& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::sigma = m_sigma

Effective alphabet size of the wavelet tree.

Definition at line 139 of file wt_int.hpp.

◆ tree

template<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>
const bit_vector_type& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::tree = m_tree

A concatenation of all bit vectors of the wavelet tree.

Definition at line 140 of file wt_int.hpp.


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