A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al. More...

#include <cst_fully.hpp>

Public Types
typedef cst_dfs_const_forward_iterator< cst_fully >	const_iterator

typedef t_csa::size_type	size_type

typedef t_csa	csa_type

typedef lcp_fully< cst_fully >	lcp_type

typedef t_csa::char_type	char_type

typedef std::pair< size_type, size_type >	node_type

typedef size_type	leaf_type

typedef size_type	sampled_node_type

typedef t_s_support	s_support_type

typedef t_b	b_type

typedef t_b::select_0_type	b_select_0_type

typedef t_b::select_1_type	b_select_1_type

typedef t_depth	depth_type

typedef t_csa::alphabet_category	alphabet_category

typedef cst_tag	index_category

Public Member Functions
	cst_fully ()=default
	Default constructor.

	cst_fully (cst_fully const &cst)
	Copy constructor.

	cst_fully (cst_fully &&cst)
	Move constructor.

	cst_fully (cache_config &config)
	Construct CST from file_map.

size_type	size () const

bool	empty () const

const_iterator	begin () const

const_iterator	end () const

cst_fully &	operator= (cst_fully const &cst)
	Copy Assignment Operator.

cst_fully &	operator= (cst_fully &&cst)
	Move Assignment Operator.

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
	Serialize to a stream.

void	load (std::istream &in)
	Load from a stream.

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== (cst_fully const &other) const noexcept
	Equality operator.

bool	operator!= (cst_fully const &other) const noexcept
	Inequality operator.

node_type	root () const
	Returns the root of the suffix tree.

sampled_node_type	sampled_root () const
	Returns the root of the sampled tree.

bool	is_leaf (node_type v) const
	Returns true iff node v is a leaf.

node_type	select_leaf (size_type i) const
	Return the i-th leaf (1-based from left to right) of the suffix tree.

node_type	node (size_type lb, size_type rb) const
	Get the node in the suffix tree which corresponds to the sa-interval [lb..rb].

leaf_type	lb (node_type v) const
	Returns the leftmost leaf (left boundary) of a node.

leaf_type	rb (node_type v) const
	Returns the rightmost leaf (right boundary) of a node.

size_type	size (node_type const &v) const
	Calculate the number of leaves in the subtree rooted at node v.

node_type	leftmost_leaf (const node_type v) const
	Calculates the leftmost leaf in the subtree rooted at node v.

node_type	rightmost_leaf (const node_type v) const
	Calculates the rightmost leaf in the subtree rooted at node v.

bool	ancestor (node_type v, node_type w) const
	Returns true iff v is an ancestor of w.

sampled_node_type	pred (leaf_type v) const
	Returns the index of the last bracket in S before the leaf with index l.

sampled_node_type	lsa_leaf (leaf_type l) const
	Returns the LSA (lowest sampled ancestor) for a leaf with index l.

node_type	sampled_node (sampled_node_type u) const
	Returns the node in the suffix tree corresponding to the node u in the sampled tree.

sampled_node_type	sampled_lca (sampled_node_type u, sampled_node_type q) const
	Returns the LCA of two nodes in the sampled tree.

size_type	depth (sampled_node_type u) const
	Returns the depth of a sampled node u.

size_type	depth (node_type v) const
	Returns the depth of a node v.

node_type	lca (node_type v, node_type w) const
	Calculate the LCA of two nodes v and w.

node_type	lca (leaf_type l, leaf_type r) const
	Calculate the LCA of two leaves l and r.

size_type	depth_lca (leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u, std::vector< char_type > &res_label) const
	Calculate the depth of the LCA of two leaves l and r.

size_type	depth_lca (leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

node_type	sl (node_type v) const
	Compute the suffix link of a node v.

node_type	wl (node_type v, const char_type c) const
	Compute the Weiner link of node v and character c.

size_type	sn (node_type v) const
	Compute the suffix number of a leaf node v.

node_type	parent (node_type v) const
	Calculate the parent node of a node v.

node_type	child (node_type v, char_type c) const
	Get the child w of node v which edge label (v,w) starts with character c.

node_type	child (node_type v, char_type c, size_type d) const

Static Public Member Functions
static size_type	max_size ()

Public Attributes
size_type const &	delta = m_delta

csa_type const &	csa = m_csa

bit_vector const &	s = m_s

s_support_type const &	s_support = m_s_support

b_type const &	b = m_b

b_select_0_type const &	b_select_0 = m_b_select0

b_select_1_type const &	b_select_1 = m_b_select1

depth_type const &	depth_sampling = m_depth

lcp_type const &	lcp = m_lcp

Detailed Description

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
class sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >

A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al.

Template Parameters

t_csa	Type of a CSA (member of this type is accessible via member `csa`, default class is sdsl::wt).
t_delta	Value of the sampling parameter. Larger values result in lower space consumption while requiring more time. For `t_delta` = 0, delta = log n log log n is used.
t_s_support	Type of a BPS structure (member accessible via member `s_support`, default class is sdsl::bp_support_sada),
t_b	Type of a bit vector for the leaf mapping (member accessible via member `b`, default class is sdsl::sd_vector),
t_depth	Type of an integer vector for the depth of the sampled nodes (member accessible via member `depth_sampling`, default class is sdsl::dac_vector),
t_sample_leaves	Boolean value indicating whether leaves are to be sampled. This is helpful for debugging purposes.

It also contains a sdsl::bit_vector which represents the balanced parentheses sequence of the sampled tree. This bit_vector can be accessed via member s.

A node v of the cst_fully is represented by an integer i which corresponds to the position of the opening parenthesis of the parentheses pair $(i,\mu(i))$ that corresponds to v in s.

Reference: Russo, Lu{\'\i}s and Navarro, Gonzalo and Oliveira, Arlindo L: Fully Compressed Suffix Trees. ACM Transactions on Algorithms (TALG), vol. 7, no. 4, p. 53, 2011

Definition at line 151 of file cst_fully.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_csa::alphabet_category sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::alphabet_category

Definition at line 168 of file cst_fully.hpp.

◆ b_select_0_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_b::select_0_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_0_type

Definition at line 164 of file cst_fully.hpp.

◆ b_select_1_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_b::select_1_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_1_type

Definition at line 165 of file cst_fully.hpp.

◆ b_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_b sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_type

Definition at line 163 of file cst_fully.hpp.

◆ char_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_csa::char_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::char_type

Definition at line 158 of file cst_fully.hpp.

◆ const_iterator

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef cst_dfs_const_forward_iterator<cst_fully> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::const_iterator

Definition at line 154 of file cst_fully.hpp.

◆ csa_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_csa sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa_type

Definition at line 156 of file cst_fully.hpp.

◆ depth_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_depth sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_type

Definition at line 166 of file cst_fully.hpp.

◆ index_category

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef cst_tag sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::index_category

Definition at line 169 of file cst_fully.hpp.

◆ lcp_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef lcp_fully<cst_fully> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp_type

Definition at line 157 of file cst_fully.hpp.

◆ leaf_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::leaf_type

Definition at line 160 of file cst_fully.hpp.

◆ node_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef std::pair<size_type, size_type> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::node_type

Definition at line 159 of file cst_fully.hpp.

◆ s_support_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_s_support sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s_support_type

Definition at line 162 of file cst_fully.hpp.

◆ sampled_node_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_node_type

Definition at line 161 of file cst_fully.hpp.

◆ size_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

typedef t_csa::size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size_type

Definition at line 155 of file cst_fully.hpp.

Constructor & Destructor Documentation

◆ cst_fully() [1/4]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( )

default

Default constructor.

◆ cst_fully() [2/4]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const & cst )

inline

Copy constructor.

Definition at line 198 of file cst_fully.hpp.

◆ cst_fully() [3/4]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > && cst )

inline

Move constructor.

Definition at line 215 of file cst_fully.hpp.

◆ cst_fully() [4/4]

template<class t_csa, uint32_t t_delta, class t_s_support, class t_b, class t_depth, bool t_sample_leaves>

sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( cache_config & config )

Construct CST from file_map.

Definition at line 1000 of file cst_fully.hpp.

Member Function Documentation

◆ ancestor()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::ancestor	(	node_type	v,
		node_type	w ) const

inline

Returns true iff v is an ancestor of w.

Definition at line 450 of file cst_fully.hpp.

◆ begin()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

const_iterator sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::begin ( ) const

inline

Definition at line 238 of file cst_fully.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

template<typename archive_t>

void sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Definition at line 336 of file cst_fully.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

template<typename archive_t>

void sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Definition at line 322 of file cst_fully.hpp.

◆ child() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::child	(	node_type	v,
		char_type	c ) const

inline

Get the child w of node v which edge label (v,w) starts with character c.

Parameters

v	A node v.
c	First character of the edge label from v to the desired child.

Returns: The child node w which edge label (v,w) starts with c or root() if it does not exist.

Time complexity: $\Order{ \log m \cdot (\saaccess+\isaaccess) }$ where is the number of leaves in the subtree rooted at node v.

Definition at line 803 of file cst_fully.hpp.

◆ child() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::child	(	node_type	v,
		char_type	c,
		size_type	d ) const

inline

Definition at line 813 of file cst_fully.hpp.

◆ depth() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth ( node_type v ) const

inline

Returns the depth of a node v.

Parameters

v	The node v.

Returns: The depth of node v.

Time complexity: $\Order( \delta )$ for inner nodes, $\Order( \saaccess )$ for leaves.

Definition at line 556 of file cst_fully.hpp.

◆ depth() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth ( sampled_node_type u ) const

inline

Returns the depth of a sampled node u.

Parameters

u	A sampled node u.

Returns: The depth of sampled node u.

Time complexity: $\Order{1}$

Definition at line 540 of file cst_fully.hpp.

◆ depth_lca() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_lca	(	leaf_type	l,
		leaf_type	r,
		size_type &	res_i,
		sampled_node_type &	res_u ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 679 of file cst_fully.hpp.

◆ depth_lca() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_lca	(	leaf_type	l,
		leaf_type	r,
		size_type &	res_i,
		sampled_node_type &	res_u,
		std::vector< char_type > &	res_label ) const

inline

Calculate the depth of the LCA of two leaves l and r.

Parameters

l	The index of leaf l.
r	The index of leaf r.
res_i	The index i for the ancestor used to determine the depth (return value).
res_u	The ancestor used to determine the depth (return value).
res_label	The label from the found sampled node to the actual LCA.

Returns: The depth of the LCA of l and r.

Time complexity: $\Order( \delta )$

Definition at line 634 of file cst_fully.hpp.

◆ empty()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::empty ( ) const

inline

Definition at line 233 of file cst_fully.hpp.

◆ end()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

const_iterator sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::end ( ) const

inline

Definition at line 247 of file cst_fully.hpp.

◆ is_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::is_leaf ( node_type v ) const

inline

Returns true iff node v is a leaf.

Definition at line 379 of file cst_fully.hpp.

◆ lb()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

leaf_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lb ( node_type v ) const

inline

Returns the leftmost leaf (left boundary) of a node.

Definition at line 405 of file cst_fully.hpp.

◆ lca() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lca	(	leaf_type	l,
		leaf_type	r ) const

inline

Calculate the LCA of two leaves l and r.

Parameters

l	The index of leaf l.
r	The index of leaf r.

Returns: The LCA of l and r.

Time complexity: $\Order( \delta \cdot ( 1 + t_{rank\_bwt} ) )$

Definition at line 601 of file cst_fully.hpp.

◆ lca() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lca	(	node_type	v,
		node_type	w ) const

inline

Calculate the LCA of two nodes v and w.

Parameters

v	The node v.
w	The node w.

Returns: The LCA of v and w.

Time complexity: $\Order( \delta \cdot ( 1 + t_{rank\_bwt} ) )$

Definition at line 578 of file cst_fully.hpp.

◆ leftmost_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::leftmost_leaf ( const node_type v ) const

inline

Calculates the leftmost leaf in the subtree rooted at node v.

Parameters

v	A valid node of the suffix tree.

Returns: The leftmost leaf in the subtree rooted at node v.

Time complexity: $\Order{1}$

Definition at line 433 of file cst_fully.hpp.

◆ load()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

void sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::load ( std::istream & in )

inline

Load from a stream.

Parameters

in	Inputstream to load the data structure from.

Definition at line 308 of file cst_fully.hpp.

◆ lsa_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lsa_leaf ( leaf_type l ) const

inline

Returns the LSA (lowest sampled ancestor) for a leaf with index l.

Parameters

v	The index of leaf l.

Returns: The LSA for the leaf with index l.

Time complexity: $\Order{1}$

Definition at line 472 of file cst_fully.hpp.

◆ max_size()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

static size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::max_size ( )

inlinestatic

Definition at line 228 of file cst_fully.hpp.

◆ node()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::node	(	size_type	lb,
		size_type	rb ) const

inline

Get the node in the suffix tree which corresponds to the sa-interval [lb..rb].

Definition at line 399 of file cst_fully.hpp.

◆ operator!=()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator!= ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const & other ) const

inlinenoexcept

Inequality operator.

Definition at line 361 of file cst_fully.hpp.

◆ operator=() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

cst_fully & sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator= ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > && cst )

inline

Move Assignment Operator.

Definition at line 264 of file cst_fully.hpp.

◆ operator=() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

cst_fully & sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator= ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const & cst )

inline

Copy Assignment Operator.

Definition at line 253 of file cst_fully.hpp.

◆ operator==()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator== ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const & other ) const

inlinenoexcept

Equality operator.

Definition at line 353 of file cst_fully.hpp.

◆ parent()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::parent ( node_type v ) const

inline

Calculate the parent node of a node v.

Parameters

v	The node v.

Returns: The parent node of v or root() if v equals root().

Time complexity: $\Order( \delta \cdot ( 1 + t_{rank\_bwt} ) )$

Definition at line 775 of file cst_fully.hpp.

◆ pred()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::pred ( leaf_type v ) const

inline

Returns the index of the last bracket in S before the leaf with index l.

Parameters

v	The index of leaf l.

Returns: The index of the last bracket in S before the leaf with index l.

Definition at line 460 of file cst_fully.hpp.

◆ rb()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

leaf_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::rb ( node_type v ) const

inline

Returns the rightmost leaf (right boundary) of a node.

Definition at line 411 of file cst_fully.hpp.

◆ rightmost_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::rightmost_leaf ( const node_type v ) const

inline

Calculates the rightmost leaf in the subtree rooted at node v.

Parameters

v	A valid node of the suffix tree.

Returns: The rightmost leaf in the subtree rooted at node v.

Time complexity: $\Order{1}$

Definition at line 444 of file cst_fully.hpp.

◆ root()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::root ( ) const

inline

Returns the root of the suffix tree.

Definition at line 367 of file cst_fully.hpp.

◆ sampled_lca()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_lca	(	sampled_node_type	u,
		sampled_node_type	q ) const

inline

Returns the LCA of two nodes in the sampled tree.

Parameters

u	The sampled node u.
q	The sampled node q.

Returns: The lowest common ancestor of u and q in the sampled tree.

Time complexity: $\Order{\rrenclose}$

Definition at line 510 of file cst_fully.hpp.

◆ sampled_node()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_node ( sampled_node_type u ) const

inline

Returns the node in the suffix tree corresponding to the node u in the sampled tree.

Parameters

v	The node u in the sampled tree.

Returns: The node in the suffix tree corresponding to the node u in the sampled tree.

Time complexity: $\Order{1}$

Definition at line 492 of file cst_fully.hpp.

◆ sampled_root()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_root ( ) const

inline

Returns the root of the sampled tree.

Definition at line 373 of file cst_fully.hpp.

◆ select_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::select_leaf ( size_type i ) const

inline

Return the i-th leaf (1-based from left to right) of the suffix tree.

Parameters

i	1-based position of the leaf. $1\leq i\leq csa.size()$ .

Returns: The i-th leave.

Time complexity: $\Order{1}$

Precondition: $1 \leq i \leq csa.size()$

Definition at line 392 of file cst_fully.hpp.

◆ serialize()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = nullptr,
		std::string	name = "" ) const

inline

Serialize to a stream.

Parameters

out	Outstream to write the data structure.

Returns: The number of written bytes.

Definition at line 288 of file cst_fully.hpp.

◆ size() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size ( ) const

inline

Definition at line 223 of file cst_fully.hpp.

◆ size() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size ( node_type const & v ) const

inline

Calculate the number of leaves in the subtree rooted at node v.

Parameters

v	A valid node of the suffix tree.

Returns: The number of leaves in the subtree rooted at node v.

Time complexity: $\Order{1}$

Definition at line 422 of file cst_fully.hpp.

◆ sl()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sl ( node_type v ) const

inline

Compute the suffix link of a node v.

Parameters

v	The node v.

Returns: The suffix link of node v or root() if v equals root().

Time complexity: $\Order( \delta \cdot ( 1 + t_{rank\_bwt} ) )$

Definition at line 725 of file cst_fully.hpp.

◆ sn()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sn ( node_type v ) const

inline

Compute the suffix number of a leaf node v.

Parameters

v	A valid leaf node of a cst_sada.

Returns: The suffix array value corresponding to the leaf node v.

Time complexity: $\Order{ \saaccess }$

Definition at line 762 of file cst_fully.hpp.

◆ wl()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::wl	(	node_type	v,
		const char_type	c ) const

inline

Compute the Weiner link of node v and character c.

Definition at line 748 of file cst_fully.hpp.

Member Data Documentation

◆ b

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

b_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b = m_b

Definition at line 188 of file cst_fully.hpp.

◆ b_select_0

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

b_select_0_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_0 = m_b_select0

Definition at line 189 of file cst_fully.hpp.

◆ b_select_1

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

b_select_1_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_1 = m_b_select1

Definition at line 190 of file cst_fully.hpp.

◆ csa

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

csa_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa = m_csa

Definition at line 185 of file cst_fully.hpp.

◆ delta

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

size_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::delta = m_delta

Definition at line 184 of file cst_fully.hpp.

◆ depth_sampling

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

depth_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_sampling = m_depth

Definition at line 191 of file cst_fully.hpp.

◆ lcp

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

lcp_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp = m_lcp

Definition at line 192 of file cst_fully.hpp.

◆ s

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

bit_vector const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s = m_s

Definition at line 186 of file cst_fully.hpp.

◆ s_support

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>

s_support_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s_support = m_s_support

Definition at line 187 of file cst_fully.hpp.

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

/builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/cst_fully.hpp

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ alphabet_category

◆ b_select_0_type

◆ b_select_1_type

◆ b_type

◆ char_type

◆ const_iterator

◆ csa_type

◆ depth_type

◆ index_category

◆ lcp_type

◆ leaf_type

◆ node_type

◆ s_support_type

◆ sampled_node_type

◆ size_type

Constructor & Destructor Documentation

◆ cst_fully() [1/4]

◆ cst_fully() [2/4]

◆ cst_fully() [3/4]

◆ cst_fully() [4/4]

Member Function Documentation

◆ ancestor()

◆ begin()

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ child() [1/2]

◆ child() [2/2]

◆ depth() [1/2]

◆ depth() [2/2]

◆ depth_lca() [1/2]

◆ depth_lca() [2/2]

◆ empty()

◆ end()

◆ is_leaf()

◆ lb()

◆ lca() [1/2]

◆ lca() [2/2]

◆ leftmost_leaf()

◆ load()

◆ lsa_leaf()

◆ max_size()

◆ node()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ parent()

◆ pred()

◆ rb()

◆ rightmost_leaf()

◆ root()

◆ sampled_lca()

◆ sampled_node()

◆ sampled_root()

◆ select_leaf()

◆ serialize()

◆ size() [1/2]

◆ size() [2/2]

◆ sl()

◆ sn()

◆ wl()

Member Data Documentation

◆ b

◆ b_select_0

◆ b_select_1

◆ csa

◆ delta

◆ depth_sampling

◆ lcp

◆ s

◆ s_support