SDSL 3.0.1
Succinct Data Structure Library
sdsl::_byte_tree< t_dfs_shape, t_wt > Struct Template Reference

#include <wt_helper.hpp>

Public Types

enum  : uint16_t { undef = 0xFFFF }
 
enum  : uint32_t { fixed_sigma = 256 }
 
enum  : uint8_t { int_width = 8 }
 
using alphabet_category = byte_alphabet_tag
 
using value_type = uint8_t
 
using node_type = uint16_t
 
using data_node = _node< _byte_tree >
 

Public Member Functions

 _byte_tree ()
 
 _byte_tree (const std::vector< pc_node > &temp_nodes, uint64_t &bv_size, const t_wt *)
 
template<typename t_rank_type >
void init_node_ranks (const t_rank_type &rank)
 
 _byte_tree (const _byte_tree &bt)
 
_byte_treeoperator= (const _byte_tree &bt)
 
_byte_treeoperator= (_byte_tree &&bt)
 
uint64_t 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== (_byte_tree const &other) const noexcept
 Equality operator. More...
 
bool operator!= (_byte_tree const &other) const noexcept
 Inequality operator. More...
 
node_type c_to_leaf (value_type c) const
 Get corresponding leaf for symbol c. More...
 
uint64_t size () const
 Return the number of nodes in the tree. More...
 
node_type parent (node_type v) const
 Return the parent node of v. More...
 
node_type child (node_type v, uint8_t i) const
 Return left (i=0) or right (i=1) child node of v. More...
 
bool is_leaf (node_type v) const
 Return if v is a leaf node. More...
 
uint64_t size (node_type v) const
 Return size of an inner node. More...
 
uint64_t bit_path (value_type c) const
 Return the path as left/right bit sequence in a uint64_t. More...
 
uint64_t bv_pos (node_type v) const
 Return the start of the node in the WT's bit vector. More...
 
uint64_t bv_pos_rank (node_type v) const
 Returns for node v the rank of 1's up to bv_pos(v) More...
 
bool is_valid (node_type v) const
 Return if the node is a valid node. More...
 
std::pair< bool, value_typesymbol_gte (value_type c) const
 Return symbol c or the next larger symbol in the wt. More...
 
std::pair< bool, value_typesymbol_lte (value_type c) const
 Return symbol c or the next smaller symbol in the wt. More...
 

Static Public Member Functions

static node_type root ()
 Return the root node of the tree. More...
 

Public Attributes

std::vector< data_nodem_nodes
 
node_type m_c_to_leaf [fixed_sigma]
 
uint64_t m_path [fixed_sigma]
 

Detailed Description

template<bool t_dfs_shape, typename t_wt>
struct sdsl::_byte_tree< t_dfs_shape, t_wt >

Definition at line 182 of file wt_helper.hpp.

Member Typedef Documentation

◆ alphabet_category

template<bool t_dfs_shape, typename t_wt >
using sdsl::_byte_tree< t_dfs_shape, t_wt >::alphabet_category = byte_alphabet_tag

Definition at line 184 of file wt_helper.hpp.

◆ data_node

template<bool t_dfs_shape, typename t_wt >
using sdsl::_byte_tree< t_dfs_shape, t_wt >::data_node = _node<_byte_tree>

Definition at line 187 of file wt_helper.hpp.

◆ node_type

template<bool t_dfs_shape, typename t_wt >
using sdsl::_byte_tree< t_dfs_shape, t_wt >::node_type = uint16_t

Definition at line 186 of file wt_helper.hpp.

◆ value_type

template<bool t_dfs_shape, typename t_wt >
using sdsl::_byte_tree< t_dfs_shape, t_wt >::value_type = uint8_t

Definition at line 185 of file wt_helper.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<bool t_dfs_shape, typename t_wt >
anonymous enum : uint16_t
Enumerator
undef 

Definition at line 188 of file wt_helper.hpp.

◆ anonymous enum

template<bool t_dfs_shape, typename t_wt >
anonymous enum : uint32_t
Enumerator
fixed_sigma 

Definition at line 192 of file wt_helper.hpp.

◆ anonymous enum

template<bool t_dfs_shape, typename t_wt >
anonymous enum : uint8_t
Enumerator
int_width 

Definition at line 196 of file wt_helper.hpp.

Constructor & Destructor Documentation

◆ _byte_tree() [1/3]

template<bool t_dfs_shape, typename t_wt >
sdsl::_byte_tree< t_dfs_shape, t_wt >::_byte_tree ( )
inline

Definition at line 209 of file wt_helper.hpp.

◆ _byte_tree() [2/3]

template<bool t_dfs_shape, typename t_wt >
sdsl::_byte_tree< t_dfs_shape, t_wt >::_byte_tree ( const std::vector< pc_node > &  temp_nodes,
uint64_t &  bv_size,
const t_wt *   
)
inline

Definition at line 211 of file wt_helper.hpp.

◆ _byte_tree() [3/3]

template<bool t_dfs_shape, typename t_wt >
sdsl::_byte_tree< t_dfs_shape, t_wt >::_byte_tree ( const _byte_tree< t_dfs_shape, t_wt > &  bt)
inline

Definition at line 307 of file wt_helper.hpp.

Member Function Documentation

◆ bit_path()

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::bit_path ( value_type  c) const
inline

Return the path as left/right bit sequence in a uint64_t.

Definition at line 413 of file wt_helper.hpp.

◆ bv_pos()

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::bv_pos ( node_type  v) const
inline

Return the start of the node in the WT's bit vector.

Definition at line 416 of file wt_helper.hpp.

◆ bv_pos_rank()

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::bv_pos_rank ( node_type  v) const
inline

Returns for node v the rank of 1's up to bv_pos(v)

Definition at line 419 of file wt_helper.hpp.

◆ c_to_leaf()

template<bool t_dfs_shape, typename t_wt >
node_type sdsl::_byte_tree< t_dfs_shape, t_wt >::c_to_leaf ( value_type  c) const
inline

Get corresponding leaf for symbol c.

Definition at line 390 of file wt_helper.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<bool t_dfs_shape, typename t_wt >
template<typename archive_t >
void sdsl::_byte_tree< t_dfs_shape, t_wt >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 372 of file wt_helper.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<bool t_dfs_shape, typename t_wt >
template<typename archive_t >
void sdsl::_byte_tree< t_dfs_shape, t_wt >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 364 of file wt_helper.hpp.

◆ child()

template<bool t_dfs_shape, typename t_wt >
node_type sdsl::_byte_tree< t_dfs_shape, t_wt >::child ( node_type  v,
uint8_t  i 
) const
inline

Return left (i=0) or right (i=1) child node of v.

Definition at line 400 of file wt_helper.hpp.

◆ init_node_ranks()

template<bool t_dfs_shape, typename t_wt >
template<typename t_rank_type >
void sdsl::_byte_tree< t_dfs_shape, t_wt >::init_node_ranks ( const t_rank_type &  rank)
inline

Definition at line 298 of file wt_helper.hpp.

◆ is_leaf()

template<bool t_dfs_shape, typename t_wt >
bool sdsl::_byte_tree< t_dfs_shape, t_wt >::is_leaf ( node_type  v) const
inline

Return if v is a leaf node.

Definition at line 403 of file wt_helper.hpp.

◆ is_valid()

template<bool t_dfs_shape, typename t_wt >
bool sdsl::_byte_tree< t_dfs_shape, t_wt >::is_valid ( node_type  v) const
inline

Return if the node is a valid node.

Definition at line 422 of file wt_helper.hpp.

◆ load()

template<bool t_dfs_shape, typename t_wt >
void sdsl::_byte_tree< t_dfs_shape, t_wt >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 353 of file wt_helper.hpp.

◆ operator!=()

template<bool t_dfs_shape, typename t_wt >
bool sdsl::_byte_tree< t_dfs_shape, t_wt >::operator!= ( _byte_tree< t_dfs_shape, t_wt > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 387 of file wt_helper.hpp.

◆ operator=() [1/2]

template<bool t_dfs_shape, typename t_wt >
_byte_tree & sdsl::_byte_tree< t_dfs_shape, t_wt >::operator= ( _byte_tree< t_dfs_shape, t_wt > &&  bt)
inline

Definition at line 325 of file wt_helper.hpp.

◆ operator=() [2/2]

template<bool t_dfs_shape, typename t_wt >
_byte_tree & sdsl::_byte_tree< t_dfs_shape, t_wt >::operator= ( const _byte_tree< t_dfs_shape, t_wt > &  bt)
inline

Definition at line 315 of file wt_helper.hpp.

◆ operator==()

template<bool t_dfs_shape, typename t_wt >
bool sdsl::_byte_tree< t_dfs_shape, t_wt >::operator== ( _byte_tree< t_dfs_shape, t_wt > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 380 of file wt_helper.hpp.

◆ parent()

template<bool t_dfs_shape, typename t_wt >
node_type sdsl::_byte_tree< t_dfs_shape, t_wt >::parent ( node_type  v) const
inline

Return the parent node of v.

Definition at line 398 of file wt_helper.hpp.

◆ root()

template<bool t_dfs_shape, typename t_wt >
static node_type sdsl::_byte_tree< t_dfs_shape, t_wt >::root ( )
inlinestatic

Return the root node of the tree.

Definition at line 392 of file wt_helper.hpp.

◆ serialize()

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::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 337 of file wt_helper.hpp.

◆ size() [1/2]

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::size ( ) const
inline

Return the number of nodes in the tree.

Definition at line 395 of file wt_helper.hpp.

◆ size() [2/2]

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::size ( node_type  v) const
inline

Return size of an inner node.

Definition at line 406 of file wt_helper.hpp.

◆ symbol_gte()

template<bool t_dfs_shape, typename t_wt >
std::pair< bool, value_type > sdsl::_byte_tree< t_dfs_shape, t_wt >::symbol_gte ( value_type  c) const
inline

Return symbol c or the next larger symbol in the wt.

Definition at line 425 of file wt_helper.hpp.

◆ symbol_lte()

template<bool t_dfs_shape, typename t_wt >
std::pair< bool, value_type > sdsl::_byte_tree< t_dfs_shape, t_wt >::symbol_lte ( value_type  c) const
inline

Return symbol c or the next smaller symbol in the wt.

Definition at line 435 of file wt_helper.hpp.

Member Data Documentation

◆ m_c_to_leaf

template<bool t_dfs_shape, typename t_wt >
node_type sdsl::_byte_tree< t_dfs_shape, t_wt >::m_c_to_leaf[fixed_sigma]

Definition at line 202 of file wt_helper.hpp.

◆ m_nodes

template<bool t_dfs_shape, typename t_wt >
std::vector<data_node> sdsl::_byte_tree< t_dfs_shape, t_wt >::m_nodes

Definition at line 201 of file wt_helper.hpp.

◆ m_path

template<bool t_dfs_shape, typename t_wt >
uint64_t sdsl::_byte_tree< t_dfs_shape, t_wt >::m_path[fixed_sigma]

Definition at line 205 of file wt_helper.hpp.


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