Functions
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::root () const
	Return the root of the suffix tree.
bool	sdsl::cst_sct< Csa, Lcp, Bp_support >::is_leaf (const node_type &v) const
	Decide if a node is a leaf in the suffix tree.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::ith_leaf (size_type i) const
	Return the i-th leaf (1-based from left to right) of the suffix tree.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::leaves_in_the_subtree (const node_type &v) const
	Calculate the number of leaves in the subtree rooted at node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::leftmost_leaf_in_the_subtree (const node_type &v) const
	Calculates the leftmost leaf in the subtree rooted at node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::rightmost_leaf_in_the_subtree (const node_type &v) const
	Calculates the rightmost leaf in the subtree rooted at node v.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::lb (const node_type &v) const
	Calculates the index of the leftmost leaf in the corresponding suffix array.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::rb (const node_type &v) const
	Calculates the index of the rightmost leaf in the corresponding suffix array.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::parent (const node_type &v) const
	Calculate the parent node of a node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::ith_child (const node_type &v, size_type i) const
	Get the ith child of a node v.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::degree (const node_type &v) const
	Get the number of children of a node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::sibling (const node_type &v) const
	Returns the next sibling of node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::sibling_naive (const node_type &v) const
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::child_linear (const node_type &v, unsigned char c, size_type &char_pos) const
	Get the child w of v which edge label (v,w) starts with character c.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::child (const node_type &v, const unsigned char c, size_type &char_pos) const
	Get the child w of node v which edge label (v,w) starts with character c.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::child (const node_type &v, const unsigned char c)
	Get the child w of node v which edge label (v,w) starts with character c.
unsigned char	sdsl::cst_sct< Csa, Lcp, Bp_support >::edge (const node_type &v, size_type d) const
	Returns the d-th character (1-based indexing) of the edge-label pointing to v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::lca (node_type v, node_type w) const
	Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::depth (const node_type &v) const
	Returns the string depth of node v.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::node_depth (node_type v) const
	Returns the node depth of node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::sl (const node_type &v) const
	Compute the suffix link of node v.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::wl (const node_type &v, const unsigned char c) const
	Compute the Weiner link of node v and character c.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::sn (const node_type &v) const
	Compute the suffix number of a leaf node v.
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::id (const node_type &v) const
	Computes a unique identification number for a node of the suffx tree in the range [0..2*size()-1].
size_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::nodes () const
	Get the number of nodes of the suffix tree.
node_type	sdsl::cst_sct< Csa, Lcp, Bp_support >::node (size_type lb, size_type rb, size_type l=0) const
	Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
void	sdsl::cst_sct< Csa, Lcp, Bp_support >::print_info () const
	Print some infos about the size of the compressed suffix tree.

Function Documentation

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::child	(	const node_type &	v,
		const unsigned char	c,
		size_type &	char_pos
	)		const `[inline]`

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

   \param v A valid tree node of the cst.

Parameters:

c	First character of the edge label from v to the desired child.
char_pos	Reference which will hold the position (0-based) of the matching char c in the sorted text/suffix array.

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

Time complexity: $\Order{(\lcpaccess+\saaccess+\isaaccess) \cdot \log\sigma}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::child_linear	(	const node_type &	v,
		unsigned char	c,
		size_type &	char_pos
	)		const `[inline]`

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

   \param v A valid tree node of the cst.

Parameters:

c	First character of the edge label from v to the desired child.
char_pos	Reference which will hold the position (0-based) of the matching char c in the sorted text/suffix array.

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

Time complexity: $\Order{ \sigma \cdot (\saaccess+\isaaccess+\lcpaccess) }$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::degree ( const node_type & v ) const [inline]

Get the number of children of a node v.

Parameters:

v	A valid node v of a cst_sct.

Returns:: The number of children of node v.

Time complexity: $\Order{\lcpaccess \cdot \log\sigma}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::depth ( const node_type & v ) const [inline]

Returns the string depth of node v.

Parameters:

v	A valid node of a cst_sct.

Returns:: The string depth of node v.

Time complexity: $\Order{1}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

unsigned char sdsl::cst_sct< Csa, Lcp, Bp_support >::edge	(	const node_type &	v,
		size_type	d
	)		const `[inline]`

Returns the d-th character (1-based indexing) of the edge-label pointing to v.

Parameters:

v	The node at which the edge path ends.
d	The position (1-based indexing) of the requested character on the edge path from the root to v. $d > 0 \wedge d < depth(v)$

Returns:: The character at position d on the edge path from the root to v.

Time complexity: $\Order{ \log\sigma + (\saaccess+\isaaccess) }$

Precondition:: $1 \leq d \leq depth(v)$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::id ( const node_type & v ) const [inline]

Computes a unique identification number for a node of the suffx tree in the range [0..2*size()-1].

   \param v A valid node of a cst_sct.

Returns:: A unique identification number for the node v in the range [0..2*size()-1]

Time complexity: $\Order{\lcpaccess}$

Changes in future: This method will someday hopefully return a value in the range [0..nodes()-1]

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

bool sdsl::cst_sct< Csa, Lcp, Bp_support >::is_leaf ( const node_type & v ) const [inline]

Decide if a node is a leaf in the suffix tree.

Parameters:

v	A valid node of a cst_sct.

Returns:: A boolean value indicating if v is a leaf.

Time complexity: $\Order{1}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::ith_child	(	const node_type &	v,
		size_type	i
	)		const `[inline]`

Get the ith child of a node v.

   \param v A valid tree node of the cst.

Parameters:

i	1-based index of the child which should be returned. $i \geq 1$ .

Returns:: The i-th child node of v or root() if v has no i-th child.

Time complexity: $\Order{i \cdot \lcpaccess}$ , $i \leq \sigma$

Precondition:: $1 \leq i \leq degree(v)$

Note:: Could be implemented in time $\Order{\log i \cdot \lcpaccess}$ with binary search.

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::ith_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{\saaccess}$

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

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::lb ( const node_type & v ) const [inline]

Calculates the index of the leftmost leaf in the corresponding suffix array.

Parameters:

v	A valid node of the suffix tree.

Returns:: The index of the leftmost leaf in the corresponding suffix array.

Time complexity: $\Order{1}$

Note: lb is an abbreviation for ,,left bound''

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::lca	(	node_type	v,
		node_type	w
	)		const `[inline]`

Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.

Parameters:

v	The first node for which the lca with the second node should be computed.
w	The second node for which the lca with the first node should be computed.

Returns:: A node that is the lowest common ancestor of v and w in the suffix tree.

Time complexity: $\Order{\rrenclose}\$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::leaves_in_the_subtree ( const node_type & 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}$

This method is used e.g. in the sdsl::algorithm::count<Cst> method.

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::leftmost_leaf_in_the_subtree ( 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{\saaccess}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::node_depth ( node_type v ) const [inline]

Returns the node depth of node v.

Parameters:

v	A valid node of a cst_sct3.

Returns:: The node depth of node v.

Time complexity: $\Order{z}$ , where is the resulting node depth.

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::parent ( const node_type & v ) const [inline]

Calculate the parent node of a node v.

Parameters:

v	A valid node of the suffix tree.

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

Time complexity: $\Order{\lcpaccess \cdot \log\sigma}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::rb ( const node_type & v ) const [inline]

Calculates the index of the rightmost leaf in the corresponding suffix array.

Parameters:

v	A valid node of the suffix tree.

Returns:: The index of the rightmost leaf in the corresponding suffix array.

Time complexity: $\Order{1}$

Note: rb is an abbreviation for ,,right bound''

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::rightmost_leaf_in_the_subtree ( 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{\saaccess}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::root ( ) const [inline]

Return the root of the suffix tree.

Time complexity O(1): $\Order{1}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::sibling ( const node_type & v ) const [inline]

Returns the next sibling of node v.

Parameters:

v	A valid node v of the suffix tree.

Returns:: The next (right) sibling of node v or root() if v has no next (right) sibling.

Time complexity: $\Order{\lcpaccess}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

node_type sdsl::cst_sct< Csa, Lcp, Bp_support >::sl ( const node_type & v ) const [inline]

Compute the suffix link of node v.

Parameters:

v	A valid node of a cst_sct.

Returns:: The suffix link of node v.

Time complexity: $\Order{ \rrenclose + \lcpaccess \cdot \log\sigma}$

template<class Csa = csa_wt<>, class Lcp = lcp_support_sada<Csa>, class Bp_support = bp_support_sada<>>

size_type sdsl::cst_sct< Csa, Lcp, Bp_support >::sn ( const node_type & v ) const [inline]

Compute the suffix number of a leaf node v.

Parameters:

v	A valid leaf node of a cst_sct.

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

Time complexity: $\Order{ \saaccess }$

Functions

Function Documentation