SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::wt_ap< t_wt_byte, t_wt_int > Class Template Reference

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

#include <wt_ap.hpp>

Public Types

enum  { lex_ordered = 0 }
 
typedef int_vector ::size_type size_type
 
typedef int_vector ::value_type value_type
 
typedef int_vector ::difference_type difference_type
 
typedef random_access_const_iterator< wt_apconst_iterator
 
typedef const_iterator iterator
 
typedef t_wt_byte wt_byte_type
 
typedef t_wt_int wt_int_type
 
typedef wt_tag index_category
 
typedef int_alphabet_tag alphabet_category
 

Public Member Functions

 wt_ap ()
 Default constructor.
 
template<typename t_it >
 wt_ap (t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
 Construct the wavelet tree from a sequence defined by two interators.
 
 wt_ap (wt_ap const &wt)
 Copy constructor.
 
 wt_ap (wt_ap &&wt)
 Move copy constructor.
 
wt_apoperator= (wt_ap const &wt)
 Assignment operator.
 
wt_apoperator= (wt_ap &&wt)
 Assignment move 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] of the supported vector.
 
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.
 
size_type select (size_type i, value_type c) const
 Calculates the i-th occurrence of the symbol c in the supported vector.
 
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.
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal.
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Load via cereal.
 
iterator begin ()
 
const_iterator end ()
 
iterator begin () const
 
const_iterator end () const
 
bool operator== (wt_ap const &other) const noexcept
 Equality operator.
 
bool operator!= (wt_ap const &other) const noexcept
 Inequality operator.
 

Public Attributes

size_type const & sigma = m_sigma
 

Protected Attributes

size_type m_size = 0
 
value_type m_sigma = 0
 
value_type m_singleton_class_cnt = 0
 
value_type m_class_cnt = 0
 
wt_byte_type m_char2class
 
wt_byte_type m_class
 
std::vector< wt_int_typem_offset
 

Detailed Description

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
class sdsl::wt_ap< t_wt_byte, t_wt_int >

A wavelet tree class for integer sequences.

Space complexity
$\order{n} (H_0 + 1)$ bits, where $n$ is the size of the vector the wavelet tree was build for.1
Template Parameters
t_wt_byteType of the wavelet tree used for class representation.
t_wt_intType of the wavelet tree used for class offset representation.
References
[1] J. Barbay, F. Claude, T. Gagie, G. Navarro and Y. Nekrich: ,,Efficient Fully-Compressed Sequence Representations''

Definition at line 58 of file wt_ap.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef int_alphabet_tag sdsl::wt_ap< t_wt_byte, t_wt_int >::alphabet_category

Definition at line 74 of file wt_ap.hpp.

◆ const_iterator

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef random_access_const_iterator<wt_ap> sdsl::wt_ap< t_wt_byte, t_wt_int >::const_iterator

Definition at line 69 of file wt_ap.hpp.

◆ difference_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef int_vector ::difference_type sdsl::wt_ap< t_wt_byte, t_wt_int >::difference_type

Definition at line 68 of file wt_ap.hpp.

◆ index_category

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef wt_tag sdsl::wt_ap< t_wt_byte, t_wt_int >::index_category

Definition at line 73 of file wt_ap.hpp.

◆ iterator

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef const_iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::iterator

Definition at line 70 of file wt_ap.hpp.

◆ size_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef int_vector ::size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::size_type

Definition at line 66 of file wt_ap.hpp.

◆ value_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef int_vector ::value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::value_type

Definition at line 67 of file wt_ap.hpp.

◆ wt_byte_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef t_wt_byte sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_byte_type

Definition at line 71 of file wt_ap.hpp.

◆ wt_int_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
typedef t_wt_int sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_int_type

Definition at line 72 of file wt_ap.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
anonymous enum
Enumerator
lex_ordered 

Definition at line 75 of file wt_ap.hpp.

Constructor & Destructor Documentation

◆ wt_ap() [1/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( )
inline

Default constructor.

Definition at line 109 of file wt_ap.hpp.

◆ wt_ap() [2/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
template<typename t_it >
sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( 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.

Definition at line 119 of file wt_ap.hpp.

◆ wt_ap() [3/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( wt_ap< t_wt_byte, t_wt_int > const & wt)
inline

Copy constructor.

Definition at line 232 of file wt_ap.hpp.

◆ wt_ap() [4/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( wt_ap< t_wt_byte, t_wt_int > && wt)
inline

Move copy constructor.

Definition at line 243 of file wt_ap.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::begin ( )
inline

Definition at line 443 of file wt_ap.hpp.

◆ begin() [2/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::begin ( ) const
inline

Definition at line 451 of file wt_ap.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
template<typename archive_t >
void sdsl::wt_ap< t_wt_byte, t_wt_int >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Load via cereal.

Definition at line 432 of file wt_ap.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
template<typename archive_t >
void sdsl::wt_ap< t_wt_byte, t_wt_int >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Serialise (save) via cereal.

Definition at line 419 of file wt_ap.hpp.

◆ empty()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
bool sdsl::wt_ap< t_wt_byte, t_wt_int >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 282 of file wt_ap.hpp.

◆ end() [1/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
const_iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::end ( )
inline

Definition at line 447 of file wt_ap.hpp.

◆ end() [2/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
const_iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::end ( ) const
inline

Definition at line 455 of file wt_ap.hpp.

◆ inverse_select()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
std::pair< size_type, value_type > sdsl::wt_ap< t_wt_byte, t_wt_int >::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 340 of file wt_ap.hpp.

◆ load()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
void sdsl::wt_ap< t_wt_byte, t_wt_int >::load ( std::istream & in)
inline

Loads the data structure from the given istream.

Definition at line 401 of file wt_ap.hpp.

◆ operator!=()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
bool sdsl::wt_ap< t_wt_byte, t_wt_int >::operator!= ( wt_ap< t_wt_byte, t_wt_int > const & other) const
inlinenoexcept

Inequality operator.

Definition at line 469 of file wt_ap.hpp.

◆ operator=() [1/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
wt_ap & sdsl::wt_ap< t_wt_byte, t_wt_int >::operator= ( wt_ap< t_wt_byte, t_wt_int > && wt)
inline

Assignment move operator.

Definition at line 260 of file wt_ap.hpp.

◆ operator=() [2/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
wt_ap & sdsl::wt_ap< t_wt_byte, t_wt_int >::operator= ( wt_ap< t_wt_byte, t_wt_int > const & wt)
inline

Assignment operator.

Definition at line 249 of file wt_ap.hpp.

◆ operator==()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
bool sdsl::wt_ap< t_wt_byte, t_wt_int >::operator== ( wt_ap< t_wt_byte, t_wt_int > const & other) const
inlinenoexcept

Equality operator.

Definition at line 461 of file wt_ap.hpp.

◆ operator[]()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::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.
Worst case time complexity
$ \Order{\log \log |\Sigma|} $
Average case time complexity
$ \Order{\log H_0} $
Precondition
$ i < size() $

Definition at line 297 of file wt_ap.hpp.

◆ rank()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::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.
Worst case time complexity
$ \Order{\log \log |\Sigma|} $
Average case time complexity
$ \Order{\log H_0} $
Precondition
$ i \leq size() $

Definition at line 319 of file wt_ap.hpp.

◆ select()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::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.
Worst case time complexity
$ \Order{\log \log |\Sigma|} $
Average case time complexity
$ \Order{\log H_0} $
Precondition
$ 1 \leq i \leq rank(size(), c) $

Definition at line 366 of file wt_ap.hpp.

◆ serialize()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::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 382 of file wt_ap.hpp.

◆ size()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 276 of file wt_ap.hpp.

Member Data Documentation

◆ m_char2class

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
wt_byte_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_char2class
protected

Definition at line 85 of file wt_ap.hpp.

◆ m_class

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
wt_byte_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_class
protected

Definition at line 86 of file wt_ap.hpp.

◆ m_class_cnt

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_class_cnt = 0
protected

Definition at line 84 of file wt_ap.hpp.

◆ m_offset

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
std::vector<wt_int_type> sdsl::wt_ap< t_wt_byte, t_wt_int >::m_offset
protected

Definition at line 87 of file wt_ap.hpp.

◆ m_sigma

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_sigma = 0
protected

Definition at line 82 of file wt_ap.hpp.

◆ m_singleton_class_cnt

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_singleton_class_cnt = 0
protected

Definition at line 83 of file wt_ap.hpp.

◆ m_size

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_size = 0
protected

Definition at line 81 of file wt_ap.hpp.

◆ sigma

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
size_type const& sdsl::wt_ap< t_wt_byte, t_wt_int >::sigma = m_sigma

Definition at line 106 of file wt_ap.hpp.


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