8#ifndef INCLUDED_SDSL_CST_SADA
9#define INCLUDED_SDSL_CST_SADA
69template <
class t_csa = csa_sada<>,
70 class t_lcp = lcp_support_sada<>,
71 class t_bp_support = bp_support_sada<>,
72 class t_rank_10 = rank_support_v5<10, 2>,
73 class t_select_10 = select_support_mcl<10, 2>>
76 static_assert(std::is_same<typename index_tag<t_csa>::type,
csa_tag>::value,
77 "First template argument has to be a compressed suffix array.");
85 typedef typename t_lcp::template type<cst_sada>
lcp_type;
94 typedef typename t_csa::alphabet_type::sigma_type
sigma_type;
112 return m_bp_rank10(m_bp_support.find_close(v + 1) + 1);
116 t_csa
const &
csa = m_csa;
130 m_bp_support(cst.m_bp_support),
131 m_bp_rank10(cst.m_bp_rank10),
132 m_bp_select10(cst.m_bp_select10)
135 m_bp_support.set_vector(&m_bp);
136 m_bp_rank10.set_vector(&m_bp);
137 m_bp_select10.set_vector(&m_bp);
142 m_csa(std::move(cst.m_csa)),
143 m_bp(std::move(cst.m_bp)),
144 m_bp_support(std::move(cst.m_bp_support)),
145 m_bp_rank10(std::move(cst.m_bp_rank10)),
146 m_bp_select10(std::move(cst.m_bp_select10))
149 m_bp_support.set_vector(&m_bp);
150 m_bp_rank10.set_vector(&m_bp);
151 m_bp_select10.set_vector(&m_bp);
161 bool const o_par =
true;
162 bool const c_par = !o_par;
179 while (stack.
top() > x)
195 while (stack.
size() > 1)
213 while (m_bp[++p] == c_par);
218 while (stack.
top() > x)
235 while (!stack.
empty())
248 util::init_support(m_bp_support, &m_bp);
249 util::init_support(m_bp_rank10, &m_bp);
250 util::init_support(m_bp_select10, &m_bp);
279 return t_csa::max_size();
288 return m_csa.empty();
297 if (0 == m_bp.
size())
305 if (0 == m_bp.
size() and
root() == v)
330 if (0 == m_bp.
size())
350 *
this = std::move(tmp);
363 m_csa = std::move(cst.m_csa);
365 m_bp = std::move(cst.m_bp);
366 m_bp_support = std::move(cst.m_bp_support);
367 m_bp_support.set_vector(&m_bp);
368 m_bp_rank10 = std::move(cst.m_bp_rank10);
369 m_bp_rank10.set_vector(&m_bp);
370 m_bp_select10 = std::move(cst.m_bp_select10);
371 m_bp_select10.set_vector(&m_bp);
379 return (m_csa == other.m_csa) && (m_lcp == other.m_lcp) && (m_bp == other.m_bp)
380 && (m_bp_support == other.m_bp_support) && (m_bp_rank10 == other.m_bp_rank10)
381 && (m_bp_select10 == other.m_bp_select10);
387 return !(*
this == other);
398 written_bytes += m_csa.serialize(out,
child,
"csa");
399 written_bytes += m_lcp.serialize(out,
child,
"lcp");
401 written_bytes += m_bp_support.serialize(out,
child,
"bp_support");
402 written_bytes += m_bp_rank10.serialize(out,
child,
"bp_rank_10");
403 written_bytes += m_bp_select10.serialize(out,
child,
"bp_select_10");
405 return written_bytes;
416 m_bp_support.load(in, &m_bp);
417 m_bp_rank10.load(in, &m_bp);
418 m_bp_select10.load(in, &m_bp);
421 template <
typename archive_t>
432 template <
typename archive_t>
440 m_bp_support.set_vector(&m_bp);
442 m_bp_rank10.set_vector(&m_bp);
444 m_bp_select10.set_vector(&m_bp);
469 assert(m_bp[v] == 1);
484 assert(i > 0 and i <= m_csa.size());
486 return m_bp_select10.select(i) - 1;
504 return m_csa.size() - m_csa[i];
506 assert(inorder(v) > 0);
507 return m_lcp[inorder(v)];
520 return (m_bp_support.rank(v) << 1) - v - 2;
533 size_type r = m_bp_support.find_close(v);
534 return m_bp_rank10(r + 1) - m_bp_rank10(v);
545 return m_bp_select10(m_bp_rank10(v) + 1) - 1;
556 size_type r = m_bp_support.find_close(v);
557 return m_bp_select10(m_bp_rank10(r + 1)) - 1;
570 return m_bp_rank10(v);
583 size_type r = m_bp_support.find_close(v);
584 return m_bp_rank10(r + 1) - 1;
595 assert(m_bp[v] == 1);
600 return m_bp_support.enclose(v);
626 node_type sib = m_bp_support.find_close(v) + 1;
648 if (cc == 0 and c != 0)
650 size_type char_ex_max_pos = m_csa.C[cc + 1], char_inc_min_pos = m_csa.C[cc];
664 if (char_pos >= char_ex_max_pos)
666 if (char_pos >= char_inc_min_pos)
668 res = m_bp_support.find_close(res) + 1;
679 return child(v, c, char_pos);
698 res = m_bp_support.find_close(res) + 1;
717 assert(d <=
depth(v));
729 while (c_begin < c_end)
731 mid = (c_begin + c_end) >> 1;
732 if (m_csa.C[mid] <= order)
741 return m_csa.comp2char[c_begin - 1];
754 assert(m_bp[v] == 1 and m_bp[w] == 1);
765 return m_bp_support.double_enclose(v, w);
786 size_type right = m_bp_rank10(m_bp_support.find_close(v)) - 1;
787 assert(left < right);
790 return lca(left_leaf, right_leaf);
811 size_type right = m_bp_rank10(m_bp_support.find_close(v)) - 1;
812 assert(left < right);
815 return lca(left_leaf, right_leaf);
831 size_type right =
is_leaf(v) ? left : m_bp_rank10(m_bp_support.find_close(v)) - 1;
833 size_type c_left = m_csa.bwt.rank(left, c);
834 size_type c_right = m_csa.bwt.rank(right + 1, c);
836 if (c_left == c_right)
838 if (c_left + 1 == c_right)
839 return select_leaf(m_csa.C[m_csa.char2comp[c]] + c_left + 1);
842 size_type left = m_csa.C[m_csa.char2comp[c]] + c_left;
843 size_type right = m_csa.C[m_csa.char2comp[c]] + c_right - 1;
844 assert(left < right);
847 return lca(left_leaf, right_leaf);
861 return m_csa[m_bp_rank10(v)];
877 return size() + (m_bp_support.rank(v) - 1) - m_bp_rank10(v);
881 return m_bp_rank10(v);
901 id =
id + 1 -
size();
909 if (m_bp[mid] == 0 and m_bp[mid - 1] == 1)
914 size_type mid_id = m_bp_support.rank(mid - 1)
938 return m_bp.
size() >> 1;
965 v = m_bp_support.find_close(v) + 1;
981 size_type ip1pos = m_bp_select10(i + 1) - 1;
982 ii = m_bp_support.double_enclose(ipos, ip1pos);
984 ii = m_bp_support.find_close(ii);
986 return ii - m_bp_support.rank(ii) - m_bp_rank10(ii);
bp_support_sada.hpp contains an implementation of a balanced parentheses support structure proposed b...
cereal.hpp offers cereal support
A forward iterator for a bottom up traversal of a suffix tree.
An forward iterator for (compressed) suffix trees.
A class for the Compressed Suffix Tree (CST) proposed by Sadakane.
size_type tlcp_idx(size_type i) const
Maps an index i to the position in TLCP where LCP[i] can be found.
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....
node_type child(node_type v, const char_type c) const
Get the child w of node v which edge label (v,w) starts with character c.
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
ptrdiff_t difference_type
node_type sibling(node_type v) const
Returns the next sibling of node v.
cst_sada(cst_sada &&cst)
Move constructor.
cst_sada(cache_config &config)
Construct CST from file_map.
t_select_10 select_10_type
node_type rightmost_leaf(const node_type v) const
Calculates the rightmost leaf in the subtree rooted at node v.
cst_sada()=default
Default constructor.
rank_10_type const & bp_rank_10
size_type node_type
Type for the nodes in the tree.
const_iterator begin(node_type const &v) const
Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at nod...
cst_bottom_up_const_forward_iterator< cst_sada > const_bottom_up_iterator
bool operator!=(cst_sada const &other) const noexcept
Inequality operator.
t_csa::char_type char_type
node_type sl(node_type v) const
Compute the suffix link of node v.
t_csa::alphabet_category alphabet_category
size_type lb(const node_type v) const
Calculates the index of the leftmost leaf in the corresponding suffix array.
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.
const_iterator begin() const
Returns a const_iterator to the first element.
node_type leftmost_leaf(const node_type v) const
Calculates the leftmost leaf in the subtree rooted at node v.
size_type size() const
Number of leaves in the suffix tree.
t_csa::alphabet_type::comp_char_type comp_char_type
size_type degree(node_type v) const
Get the number of children of a node v.
bool operator==(cst_sada const &other) const noexcept
Equality operator.
bool is_leaf(node_type v) const
Decide if a node is a leaf in the suffix tree.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
select_10_type const & bp_select_10
size_type size(node_type v) const
Calculate the number of leaves in the subtree rooted at 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 rb(const node_type v) const
Calculates the index of the rightmost leaf in the corresponding suffix array.
t_lcp::template type< cst_sada > lcp_type
cst_sada & operator=(cst_sada &&cst)
Move assignment Operator.
static size_type max_size()
Returns the maximal lenght of text for that a suffix tree can be build.
const_iterator end(node_type const &v) const
Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted...
void load(std::istream &in)
Load from a stream.
node_type node(size_type lb, size_type rb) const
Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
size_type node_depth(node_type v) const
Returns the node depth of node v.
bool empty() const
Returns if the data strucutre is empty.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
t_bp_support bp_support_type
size_type nodes() const
Get the number of nodes of the suffix tree.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
bp_support_type const & bp_support
char_type 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 select_child(node_type v, size_type i) const
Get the i-th child of a node v.
node_type child(node_type v, const char_type c, size_type &char_pos) const
Get the child w of node v which edge label (v,w) starts with character c.
const_bottom_up_iterator begin_bottom_up() const
Returns an iterator to the first element of a bottom-up traversal of the tree.
node_type sl(node_type v, size_type i) const
Compute the suffix link of node v applied a number of times consecutively.
cst_sada(cst_sada const &cst)
Copy constructor.
const_iterator end() const
Returns a const_iterator to the element after the last element.
cst_sada & operator=(cst_sada const &cst)
Assignment Operator.
t_csa::string_type string_type
node_type root() const
Return the root of the suffix tree.
t_csa::size_type size_type
cst_dfs_const_forward_iterator< cst_sada > const_iterator
cst_node_child_proxy< cst_sada > children(node_type v) const
Return a proxy object which allows iterating over the children of a node.
size_type inv_id(size_type id)
Computes the node for such that id(v)=id.
size_type depth(node_type v) const
Returns the depth of node v.
node_type parent(node_type v) const
Calculate the parent node of a node v.
t_csa::alphabet_type::sigma_type sigma_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
void resize(const size_type size)
Resize the int_vector in terms of elements.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
static mm_event_proxy event(std::string const &name)
A stack which contains strictly increasing numbers in the range from to .
size_type top() const
Returns the topmost index on the stack.
void pop()
Pop the topmost index of the stack.
bool empty() const
Returns if the stack is empty.
void push(size_type x)
Push the index x of vector vec onto the stack.
size_type size() const
Returns the number of element is the stack.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
csa_sada.hpp contains an implementation of the compressed suffix array.
cst_iterators.hpp contains iterator classes for traversing (compressed) suffix arrays.
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
lcp.hpp contains classes for lcp information.
lcp_support_sada.hpp contains a compressed lcp array.
memory_tracking.hpp contains two function for allocating and deallocating memory
Namespace for the succinct data structure library.
t_csa::size_type get_char_pos(typename t_csa::size_type idx, typename t_csa::size_type d, t_csa const &csa)
std::string cache_file_name(std::string const &key, cache_config const &config)
Returns the file name of the resource.
void copy_lcp(t_lcp &lcp, t_lcp const &lcp_c, t_cst const &cst)
void move_lcp(t_lcp &&lcp, t_lcp &&lcp_c, t_cst const &cst)
bool load_from_cache(T &v, std::string const &key, cache_config const &config, bool add_type_hash=false)
void load_lcp(t_lcp &lcp, std::istream &in, t_cst const &cst)
void set_lcp_pointer(t_lcp &lcp, t_cst const &cst)
void construct_lcp(t_lcp &lcp, t_cst const &cst, cache_config &config)
rank_support_v5.hpp contains rank_support_v5.5
Contains declarations and definitions of data structure concepts.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
Helper class for construction process.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.