A class for the Compressed Suffix Tree (CST) proposed by Sadakane. More...

#include <cst_sada.hpp>

Public Types
typedef Csa::value_type	value_type
typedef cst_dfs_const_forward_iterator < cst_sada >	const_iterator
typedef cst_bottom_up_const_forward_iterator < cst_sada >	const_bottom_up_iterator
typedef const value_type	const_reference
typedef const_reference	reference
typedef const_reference *	pointer
typedef const pointer	const_pointer
typedef Csa::size_type	size_type
typedef size_type	cst_size_type
typedef ptrdiff_t	difference_type
typedef Csa	csa_type
typedef Lcp::template type < cst_sada >::lcp_type	lcp_type
typedef Csa::pattern_type	pattern_type
typedef Csa::char_type	char_type
typedef size_type	node_type
	Type for the nodes in the tree.
typedef Bp_support	bp_support_type
typedef cst_tag	index_category
Public Member Functions
	cst_sada ()
	Default Constructor.
	~cst_sada ()
	Default Destructor.
	cst_sada (const cst_sada &cst)
	Copy constructor.
template<uint8_t int_width, class size_type_class , uint8_t int_width_1, class size_type_class_1 , uint8_t int_width_2, class size_type_class_2 >
	cst_sada (const std::string &csa_file_name, int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width_1, size_type_class_1 > &sa_buf, int_vector_file_buffer< int_width_2, size_type_class_2 > &isa_buf, std::string dir="./", bool build_ony_bps=false)
	cst_sada (tMSS &file_map, const std::string dir, const std::string id, bool build_only_bps=false)
void	construct (tMSS &file_map, const std::string dir, const std::string id, bool build_only_bps=false)
size_type	size () const
	Number of leaves in the suffix tree.
bool	empty () const
	Returns if the data strucutre is empty.
void	swap (cst_sada &cst)
	Swap method for cst_sada.
const_iterator	begin () const
	Returns a const_iterator to the first element.
const_iterator	end () const
	Returns a const_iterator to the element after the last element.
const_bottom_up_iterator	begin_bottom_up () const
	Returns an iterator to the first element of a bottom-up traversal of the tree.
const_bottom_up_iterator	end_bottom_up () const
	Returns an iterator to the element after the last element of a bottom-up traversal of the tree.
cst_sada &	operator= (const cst_sada &cst)
	Assignment Operator.
bool	operator== (const cst_sada &csa) const
	Equality Operator.
bool	operator!= (const cst_sada &csa) const
	Unequality Operator.
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
	Serialize to a stream.
void	load (std::istream &in)
	Load from a stream.
node_type	root () const
	Return the root of the suffix tree.
bool	is_leaf (node_type v) const
	Decide if a node is a leaf in the suffix tree.
node_type	ith_leaf (size_type i) const
	Return the i-th leaf (1-based from left to right) of the suffix tree.
size_type	depth (node_type v) const
	Returns the depth of node v.
size_type	node_depth (node_type v) const
	Returns the node depth of node v.
size_type	leaves_in_the_subtree (node_type v) const
	Calculate the number of leaves in the subtree rooted at node v.
node_type	leftmost_leaf_in_the_subtree (const node_type &v) const
	Calculates the leftmost leaf in the subtree rooted at node v.
node_type	rightmost_leaf_in_the_subtree (const node_type &v) const
	Calculates the rightmost leaf in the subtree rooted at node v.
size_type	lb (const node_type &v) const
	Calculates the index of the leftmost leaf in the corresponding suffix array.
size_type	rb (const node_type &v) const
	Calculates the index of the rightmost leaf in the corresponding suffix array.
node_type	parent (node_type v) const
	Calculate the parent node of a node v.
node_type	sibling (node_type v) const
	Returns the next sibling of node v.
node_type	child (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	child (node_type v, const unsigned char c)
	Get the child w of node v which edge label (v,w) starts with character c.
node_type	ith_child (node_type v, size_type i) const
	Get the ith child of a node v.
unsigned char	edge (node_type v, size_type d) const
	Returns the d-th character (1-based indexing) of the edge-label pointing to v.
node_type	lca (node_type v, node_type w) const
	Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.
node_type	sl (node_type v) const
	Compute the suffix link of node v.
node_type	wl (node_type v, const unsigned char 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.
size_type	id (node_type v) const
	Computes a unique identification number for a node of the suffix tree in the range [0..nodes()-1].
size_type	inv_id (size_type id)
	Computes the node for such that id(v)=id.
size_type	nodes () const
	Get the number of nodes of the suffix tree.
node_type	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].
size_type	degree (node_type v) const
	Get the number of children of a node v.
size_type	tlcp_idx (size_type i) const
	Maps an index i to the position in TLCP where LCP[i] can be found.
void	print_info () const
	Print some infos about the size of the compressed suffix tree.
Static Public Member Functions
static size_type	max_size ()
	Returns the maximal lenght of text for that a suffix tree can be build.
Public Attributes
const Csa &	csa
	The compressed suffix array the suffix tree is based on.
const lcp_type &	lcp
	The lcp array the suffix tree is based on.
const bit_vector &	bp
	The balanced parentheses sequence of the suffix tree.
const Bp_support &	bp_support
	The balanced parentheses sequence support for member bp.
const Rank_support10 &	bp_rank_10
	The rank support for the bit pattern "01" for member bp.
const Select_support10 &	bp_select_10
	The select support for the bit pattern "01" for member bp.

Detailed Description

template<class Csa = csa_sada<>, class Lcp = lcp_support_sada<>, class Bp_support = bp_support_sada<>, class Rank_support10 = rank_support_v<10,2>, class Select_support10 = select_support_mcl<10,2>>
class sdsl::cst_sada< Csa, Lcp, Bp_support, Rank_support10, Select_support10 >

A class for the Compressed Suffix Tree (CST) proposed by Sadakane.

The CSA is parameterized by

a (compressed) suffix array data structure (accessible via member , default class is sdsl::csa_sada),
a (compressed) longest common prefix data structure (accessible via member , default class is sdsl::lcp_support_sada),
a support data structure for balanced parentheses sequences (accessible via member $bp\_support$ , default class is sdsl::bp_support_sada),
a rank data structure for the 2-bit pattern "10" (accessible via memeber $bp\_rank\_10$ , default class is sdsl::rank_support_v), and
a select data structure for the 2-bit pattern "10" (accessible via member $bp\_select\_10$ , default class is sdsl::select_support_mcl).

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

A node of the csa_sada is represented by an integer which gives the opening parenthesis of the parenthesis pair $(i,\mu(i))$ that corresponds to in .

Size comparison between cst_sct and cst_sada