SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 (std::vector< pc_node > const &temp_nodes, uint64_t &bv_size, t_wt const *)
 
template<typename t_rank_type >
void init_node_ranks (t_rank_type const &rank)
 
 _int_tree (_int_tree const &bt)=default
 
 _int_tree (_int_tree &&bt)=default
 
_int_treeoperator= (_int_tree const &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.
 
void load (std::istream &in)
 Loads the data structure from the given istream.
 
bool operator== (_int_tree const &other) const noexcept
 Equality operator.
 
bool operator!= (_int_tree const &other) const noexcept
 Inequality operator.
 
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.
 
uint64_t size () const
 Return the number of nodes in the tree.
 
node_type parent (node_type v) const
 Return the parent node of v.
 
node_type child (node_type v, uint8_t i) const
 Return left (i=0) or right (i=1) child node of v.
 
bool is_leaf (node_type v) const
 Return if v is a leaf node.
 
uint64_t size (node_type v) const
 Return size of an inner node.
 
uint64_t bit_path (value_type c) const
 Return the path as left/right bit sequence in a uint64_t.
 
uint64_t bv_pos (node_type v) const
 Return the start of the node in the WT's bit vector.
 
uint64_t bv_pos_rank (node_type v) const
 Returns for node v the rank of 1's up to bv_pos(v)
 
bool is_valid (node_type v) const
 Return if the node is a valid node.
 
std::pair< bool, value_typesymbol_gte (value_type c) const
 Return symbol c or the next larger symbol in the wt.
 
std::pair< bool, value_typesymbol_lte (value_type c) const
 Return symbol c or the next smaller symbol in the wt.
 

Static Public Member Functions

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

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 522 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 524 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 527 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 526 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 525 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 528 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 532 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 ( std::vector< pc_node > const & temp_nodes,
uint64_t & bv_size,
t_wt const *  )
inline

Definition at line 547 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 ( _int_tree< t_dfs_shape, t_wt > const & 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 773 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 783 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 789 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 729 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 721 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 713 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 754 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 ( t_rank_type const & rank)
inline

Definition at line 650 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 760 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 795 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 684 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 707 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= ( _int_tree< t_dfs_shape, t_wt > const & 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 701 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 749 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 737 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 666 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 743 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 766 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 801 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 818 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 538 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 537 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 541 of file wt_helper.hpp.


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