tudocomp
– The TU Dortmund Compression Framework
tdc::lz78u::SuffixTree Struct Reference

This is a wrapper class around the sdsl-lite library to get a easier translation between the pseudocode in the LZCICS-paper and the C++ code. More...

#include <SuffixTree.hpp>

Public Types

using cst_t = cst_sada<>
 
using node_type = cst_t::node_type
 

Public Member Functions

 SuffixTree (const cst_t &_cst)
 number of internal nodes More...
 
cst_t::node_type parent (const cst_t::node_type &node) const
 
cst_t::node_type level_anc (const cst_t::node_type &node, size_t depth) const
 Returns the level ancestor of node. More...
 
cst_t::node_type select_leaf (const cst_t::size_type &i) const
 Select the i-th leaf in SA-order 0 <= i < n. More...
 
cst_t::node_type smallest_leaf () const
 Return the leaf corresponding to the suffix starting at position 0, i.e., the leaf with the longest string-depth. More...
 
cst_t::node_type next_leaf (const cst_t::node_type &node) const
 
cst_t::node_type next_mth_leaf (const cst_t::node_type &node, cst_t::size_type m) const
 
cst_t::size_type leafrank (const cst_t::node_type &node) const
 
cst_t::size_type str_depth (const cst_t::node_type &node) const
 
cst_t::size_type nid (const cst_t::node_type &node) const
 
cst_t::size_type number_of_leaves (const cst_t::node_type &node) const
 Returns the number of leaves contained in the subtree rooted at 'node'. More...
 

Public Attributes

const cst_tcst
 
const cst_t::node_type root
 sdsl suffix tree More...
 
const rank_support_v5< 1 > m_bp_rank1
 the root node of the suffix tree More...
 
const size_t internal_nodes
 rank the one bits in the BP More...
 

Detailed Description

This is a wrapper class around the sdsl-lite library to get a easier translation between the pseudocode in the LZCICS-paper and the C++ code.

Definition at line 18 of file compressors/lz78u/SuffixTree.hpp.

Member Typedef Documentation

◆ cst_t

using tdc::lz78u::SuffixTree::cst_t = cst_sada<>

Definition at line 19 of file compressors/lz78u/SuffixTree.hpp.

◆ node_type

using tdc::lz78u::SuffixTree::node_type = cst_t::node_type

Definition at line 20 of file compressors/lz78u/SuffixTree.hpp.

Constructor & Destructor Documentation

◆ SuffixTree()

tdc::lz78u::SuffixTree::SuffixTree ( const cst_t _cst)
inline

number of internal nodes

Definition at line 27 of file compressors/lz78u/SuffixTree.hpp.

Member Function Documentation

◆ leafrank()

cst_t::size_type tdc::lz78u::SuffixTree::leafrank ( const cst_t::node_type &  node) const
inline

Definition at line 86 of file compressors/lz78u/SuffixTree.hpp.

◆ level_anc()

cst_t::node_type tdc::lz78u::SuffixTree::level_anc ( const cst_t::node_type &  node,
size_t  depth 
) const
inline

Returns the level ancestor of node.

In the sdsl-implementation, the 0-th ancestor is the node itself. Here, we want that root is the 0-th ancestor.

Definition at line 43 of file compressors/lz78u/SuffixTree.hpp.

◆ next_leaf()

cst_t::node_type tdc::lz78u::SuffixTree::next_leaf ( const cst_t::node_type &  node) const
inline

Definition at line 67 of file compressors/lz78u/SuffixTree.hpp.

◆ next_mth_leaf()

cst_t::node_type tdc::lz78u::SuffixTree::next_mth_leaf ( const cst_t::node_type &  node,
cst_t::size_type  m 
) const
inline

Definition at line 74 of file compressors/lz78u/SuffixTree.hpp.

◆ nid()

cst_t::size_type tdc::lz78u::SuffixTree::nid ( const cst_t::node_type &  node) const
inline

Definition at line 101 of file compressors/lz78u/SuffixTree.hpp.

◆ number_of_leaves()

cst_t::size_type tdc::lz78u::SuffixTree::number_of_leaves ( const cst_t::node_type &  node) const
inline

Returns the number of leaves contained in the subtree rooted at 'node'.

Definition at line 110 of file compressors/lz78u/SuffixTree.hpp.

◆ parent()

cst_t::node_type tdc::lz78u::SuffixTree::parent ( const cst_t::node_type &  node) const
inline

Definition at line 35 of file compressors/lz78u/SuffixTree.hpp.

◆ select_leaf()

cst_t::node_type tdc::lz78u::SuffixTree::select_leaf ( const cst_t::size_type &  i) const
inline

Select the i-th leaf in SA-order 0 <= i < n.

Definition at line 53 of file compressors/lz78u/SuffixTree.hpp.

◆ smallest_leaf()

cst_t::node_type tdc::lz78u::SuffixTree::smallest_leaf ( ) const
inline

Return the leaf corresponding to the suffix starting at position 0, i.e., the leaf with the longest string-depth.

Definition at line 61 of file compressors/lz78u/SuffixTree.hpp.

◆ str_depth()

cst_t::size_type tdc::lz78u::SuffixTree::str_depth ( const cst_t::node_type &  node) const
inline

Definition at line 94 of file compressors/lz78u/SuffixTree.hpp.

Member Data Documentation

◆ cst

const cst_t& tdc::lz78u::SuffixTree::cst

Definition at line 22 of file compressors/lz78u/SuffixTree.hpp.

◆ internal_nodes

const size_t tdc::lz78u::SuffixTree::internal_nodes

rank the one bits in the BP

Definition at line 25 of file compressors/lz78u/SuffixTree.hpp.

◆ m_bp_rank1

const rank_support_v5<1> tdc::lz78u::SuffixTree::m_bp_rank1

the root node of the suffix tree

Definition at line 24 of file compressors/lz78u/SuffixTree.hpp.

◆ root

const cst_t::node_type tdc::lz78u::SuffixTree::root

sdsl suffix tree

Definition at line 23 of file compressors/lz78u/SuffixTree.hpp.


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