SDSL  3.0.0
Succinct Data Structure Library
sdsl::_int_tree< t_dfs_shape, t_wt > Struct Template Reference

#include <wt_helper.hpp>

Public Types

enum  : uint64_t { undef = 0xFFFFFFFFFFFFFFFFULL }
 
enum  : uint8_t { int_width = 0 }
 
using alphabet_category = int_alphabet_tag
 
using value_type = uint64_t
 
using node_type = uint64_t
 
using data_node = _node< _int_tree >
 

Public Member Functions

 _int_tree ()=default
 
 _int_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)
 
 _int_tree (const _int_tree &bt)=default
 
 _int_tree (_int_tree &&bt)=default
 
_int_treeoperator= (const _int_tree &bt)=default
 
_int_treeoperator= (_int_tree &&bt)=default
 
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...
 
bool operator== (_int_tree const &other) const noexcept
 Equality operator. More...
 
bool operator!= (_int_tree 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)
 
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
 
std::vector< node_typem_c_to_leaf
 
std::vector< uint64_t > m_path
 

Detailed Description

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

Definition at line 456 of file wt_helper.hpp.

Member Typedef Documentation

◆ alphabet_category

template<bool t_dfs_shape, typename t_wt >
using sdsl::_int_tree< t_dfs_shape, t_wt >::alphabet_category = int_alphabet_tag

Definition at line 458 of file wt_helper.hpp.

◆ data_node

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

Definition at line 461 of file wt_helper.hpp.

◆ node_type

template<bool t_dfs_shape, typename t_wt >
using sdsl::_int_tree< t_dfs_shape, t_wt >::node_type = uint64_t

Definition at line 460 of file wt_helper.hpp.

◆ value_type

template<bool t_dfs_shape, typename t_wt >
using sdsl::_int_tree< t_dfs_shape, t_wt >::value_type = uint64_t

Definition at line 459 of file wt_helper.hpp.

Member Enumeration Documentation

◆ anonymous enum

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

Definition at line 462 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 466 of file wt_helper.hpp.

Constructor & Destructor Documentation

◆ _int_tree() [1/4]

template<bool t_dfs_shape, typename t_wt >
sdsl::_int_tree< t_dfs_shape, t_wt >::_int_tree ( )
default

◆ _int_tree() [2/4]

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

Definition at line 481 of file wt_helper.hpp.

◆ _int_tree() [3/4]

template<bool t_dfs_shape, typename t_wt >
sdsl::_int_tree< t_dfs_shape, t_wt >::_int_tree ( const _int_tree< t_dfs_shape, t_wt > &  bt)
default

◆ _int_tree() [4/4]

template<bool t_dfs_shape, typename t_wt >
sdsl::_int_tree< t_dfs_shape, t_wt >::_int_tree ( _int_tree< t_dfs_shape, t_wt > &&  bt)
default

Member Function Documentation

◆ bit_path()

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

◆ bv_pos()

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

◆ bv_pos_rank()

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

◆ c_to_leaf()

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

Get corresponding leaf for symbol c.

Definition at line 656 of file wt_helper.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

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

Definition at line 648 of file wt_helper.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

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

Definition at line 640 of file wt_helper.hpp.

◆ child()

template<bool t_dfs_shape, typename t_wt >
node_type sdsl::_int_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 672 of file wt_helper.hpp.

◆ init_node_ranks()

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

Definition at line 580 of file wt_helper.hpp.

◆ is_leaf()

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

Return if v is a leaf node.

Definition at line 675 of file wt_helper.hpp.

◆ is_valid()

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

Return if the node is a valid node.

Definition at line 698 of file wt_helper.hpp.

◆ load()

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

Loads the data structure from the given istream.

Definition at line 614 of file wt_helper.hpp.

◆ operator!=()

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

Inequality operator.

Definition at line 637 of file wt_helper.hpp.

◆ operator=() [1/2]

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

◆ operator=() [2/2]

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

◆ operator==()

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

Equality operator.

Definition at line 631 of file wt_helper.hpp.

◆ parent()

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

Return the parent node of v.

Definition at line 670 of file wt_helper.hpp.

◆ root()

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

Return the root node of the tree.

Definition at line 664 of file wt_helper.hpp.

◆ serialize()

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

◆ size() [1/2]

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

Return the number of nodes in the tree.

Definition at line 667 of file wt_helper.hpp.

◆ size() [2/2]

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

Return size of an inner node.

Definition at line 678 of file wt_helper.hpp.

◆ symbol_gte()

template<bool t_dfs_shape, typename t_wt >
std::pair<bool, value_type> sdsl::_int_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 701 of file wt_helper.hpp.

◆ symbol_lte()

template<bool t_dfs_shape, typename t_wt >
std::pair<bool, value_type> sdsl::_int_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 712 of file wt_helper.hpp.

Member Data Documentation

◆ m_c_to_leaf

template<bool t_dfs_shape, typename t_wt >
std::vector<node_type> sdsl::_int_tree< t_dfs_shape, t_wt >::m_c_to_leaf

Definition at line 472 of file wt_helper.hpp.

◆ m_nodes

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

Definition at line 471 of file wt_helper.hpp.

◆ m_path

template<bool t_dfs_shape, typename t_wt >
std::vector<uint64_t> sdsl::_int_tree< t_dfs_shape, t_wt >::m_path

Definition at line 475 of file wt_helper.hpp.


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