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_t &	cst
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:

• compressors/lz78u/SuffixTree.hpp