8#ifndef INCLUDED_SDSL_CST_FULLY
9#define INCLUDED_SDSL_CST_FULLY
44template <
typename t_cst>
88 using leaf_type =
typename t_cst::leaf_type;
89 using sampled_node_type =
typename t_cst::sampled_node_type;
90 leaf_type v_l = i - 1;
95 return m_cst->depth_lca(v_l, v_r, i, u);
145template <
class t_csa = csa_wt<>,
146 u
int32_t t_delta = 0,
147 class t_s_support = bp_support_sada<>,
148 class t_b = sd_vector<>,
149 class t_depth = dac_vector<>,
150 bool t_sample_leaves = false>
199 m_delta(cst.m_delta),
200 m_nodes(cst.m_nodes),
203 m_s_support(cst.m_s_support),
205 m_b_select0(cst.m_b_select0),
206 m_b_select1(cst.m_b_select1),
209 m_s_support.set_vector(&m_s);
210 m_b_select0.set_vector(&m_b);
211 m_b_select1.set_vector(&m_b);
217 *
this = std::move(cst);
230 return t_csa::max_size();
235 return m_csa.empty();
258 *
this = std::move(tmp);
268 m_delta = cst.m_delta;
269 m_nodes = cst.m_nodes;
270 m_csa = std::move(cst.m_csa);
271 m_s = std::move(cst.m_s);
272 m_s_support = std::move(cst.m_s_support);
273 m_s_support.set_vector(&m_s);
274 m_b = std::move(cst.m_b);
275 m_b_select0 = std::move(cst.m_b_select0);
276 m_b_select0.set_vector(&m_b);
277 m_b_select1 = std::move(cst.m_b_select1);
278 m_b_select1.set_vector(&m_b);
279 m_depth = std::move(cst.m_depth);
294 written_bytes += m_csa.serialize(out,
child,
"csa");
295 written_bytes += m_s.serialize(out,
child,
"s");
296 written_bytes += m_s_support.serialize(out,
child,
"s_support");
297 written_bytes += m_b.serialize(out,
child,
"b");
298 written_bytes += m_b_select0.serialize(out,
child,
"b_select0");
299 written_bytes += m_b_select1.serialize(out,
child,
"b_select1");
300 written_bytes += m_depth.serialize(out,
child,
"depth");
302 return written_bytes;
314 m_s_support.load(in, &m_s);
316 m_b_select0.load(in, &m_b);
317 m_b_select1.load(in, &m_b);
321 template <
typename archive_t>
335 template <
typename archive_t>
343 m_s_support.set_vector(&m_s);
346 m_b_select0.set_vector(&m_b);
348 m_b_select1.set_vector(&m_b);
355 return (m_delta == other.m_delta) && (m_nodes == other.m_nodes) && (m_csa == other.m_csa) && (m_s == other.m_s)
356 && (m_s_support == other.m_s_support) && (m_b == other.m_b) && (m_b_select0 == other.m_b_select0)
357 && (m_b_select1 == other.m_b_select1) && (m_depth == other.m_depth);
363 return !(*
this == other);
381 return v.first == v.second;
394 assert(i > 0 and i <= m_csa.size());
424 return v.second - v.first + 1;
452 return v.first <= w.first && v.second >= w.second;
462 return m_b_select0.select(v + 1) - v - 1;
481 return m_s_support.enclose(m_s_support.find_open(p));
495 size_type u_end = m_s_support.find_close(u);
496 size_type b_left = m_b_select1.select(u + 1);
497 size_type b_right = m_b_select1.select(u_end + 1);
499 return node_type(b_left - u, b_right - u_end - 1);
512 assert(m_s[u] == 1 and m_s[q] == 1);
525 if (m_s_support.find_close(u) > q)
530 return m_s_support.double_enclose(u, q);
545 return m_depth[idx] * (m_delta / 2);
562 return m_csa.size() - m_csa[v.first];
567 return depth_lca(v.first, v.second, i, u);
580 leaf_type l = std::min(v.first, w.first);
581 leaf_type r = std::max(v.second, w.second);
607 std::vector<char_type> c(
delta, 0);
638 std::vector<char_type> & res_label)
const
663 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1])
703 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1])
733 size_t leaf = m_csa.psi[v.first];
737 return lca(m_csa.psi[v.first], m_csa.psi[v.second]);
765 return m_csa[v.first];
785 left_parent =
lca(l - 1, r);
787 if (r < m_csa.size() - 1)
789 right_parent =
lca(l, r + 1);
791 return ancestor(right_parent, left_parent) ? left_parent : right_parent;
810 return child(v, c, d);
829 begin = sample_pos + 1;
851 begin = sample_pos + 1;
889 if (res.second >= v.second)
894 c = m_csa.F[char_pos];
895 res =
child(v, c, d);
920 while (v_i.second < v.second)
924 c = m_csa.F[char_pos];
925 v_i =
child(v, c, d);
935 cst_node_child_proxy<cst_fully> children(
node_type const & v)
const
937 return cst_node_child_proxy<cst_fully>(
this, v);
948 if (v.second >= p.second)
955 return child(p, c, d);
960 assert(d >= 1 and d <=
depth(v));
962 return m_csa.F[char_pos];
995 return m_s.size() / 2;
999template <
class t_csa, u
int32_t t_delta,
class t_s_support,
class t_b,
class t_depth,
bool t_sample_leaves>
1004 m_nodes = cst.
nodes();
1023 is_sampled[cst.
id(cst.
root())] =
true;
1027 if (t_sample_leaves)
1034 if (d + delta_half <= cst.
size() and d % delta_half == 0)
1038 if (!is_sampled[
id])
1040 is_sampled[id] =
true;
1044 leaf_idx = cst.
csa.lf[leaf_idx];
1051 for (
auto it = cst.
begin(); it != cst.
end(); ++it)
1053 if (it.visit() == 1 and cst.
is_leaf(*it) ==
false)
1055 auto const node = *it;
1057 if (d % delta_half == 0)
1059 auto v = cst.
sl(
node, delta_half);
1061 if (!is_sampled[
id])
1063 is_sampled[id] =
true;
1071 m_s.resize(2 * sample_count);
1076 tmp_depth.
resize(sample_count);
1086 for (
auto it = cst.
begin(); it != cst.
end(); ++it)
1089 if (it.visit() == 1 && is_sampled[cst.
id(
node)])
1093 tmp_depth[sample_idx++] = cst.
depth(
node) / delta_half;
1109 m_csa = std::move(cst.
csa);
1110 util::init_support(m_s_support, &m_s);
1112 util::init_support(m_b_select0, &m_b);
1113 util::init_support(m_b_select1, &m_b);
bits.hpp contains the sdsl::bits class.
bp_support_sada.hpp contains an implementation of a balanced parentheses support structure proposed b...
cereal.hpp offers cereal support
An forward iterator for (compressed) suffix trees.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
cst_fully & operator=(cst_fully &&cst)
Move Assignment Operator.
cst_dfs_const_forward_iterator< cst_fully > const_iterator
bool ancestor(node_type v, node_type w) const
Returns true iff v is an ancestor of w.
node_type parent(node_type v) const
Calculate the parent node 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.
node_type leftmost_leaf(const node_type v) const
Calculates the leftmost leaf in the subtree rooted at node v.
bool is_leaf(node_type v) const
Returns true iff node v is a leaf.
leaf_type rb(node_type v) const
Returns the rightmost leaf (right boundary) of a node.
bool operator==(cst_fully const &other) const noexcept
Equality operator.
t_csa::alphabet_category alphabet_category
const_iterator end() const
cst_fully()=default
Default constructor.
t_s_support s_support_type
t_b::select_1_type b_select_1_type
size_type size(node_type const &v) const
Calculate the number of leaves in the subtree rooted at node v.
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.
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.
cst_fully(cst_fully const &cst)
Copy constructor.
b_select_0_type const & b_select_0
void load(std::istream &in)
Load from a stream.
leaf_type lb(node_type v) const
Returns the leftmost leaf (left boundary) of a node.
size_type sn(node_type v) const
Compute the suffix number of a leaf node v.
t_csa::size_type size_type
node_type sl(node_type v) const
Compute the suffix link of a node v.
b_select_1_type const & b_select_1
size_type sampled_node_type
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.
sampled_node_type sampled_root() const
Returns the root of the sampled tree.
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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 o...
s_support_type const & s_support
sampled_node_type lsa_leaf(leaf_type l) const
Returns the LSA (lowest sampled ancestor) for a leaf with index l.
static size_type max_size()
size_type depth(sampled_node_type u) const
Returns the depth of a sampled node u.
sampled_node_type sampled_lca(sampled_node_type u, sampled_node_type q) const
Returns the LCA of two nodes in the sampled tree.
std::pair< size_type, size_type > node_type
cst_fully & operator=(cst_fully const &cst)
Copy Assignment Operator.
t_csa::char_type char_type
bool operator!=(cst_fully const &other) const noexcept
Inequality operator.
node_type child(node_type v, char_type c, size_type d) const
node_type lca(leaf_type l, leaf_type r) const
Calculate the LCA of two leaves l and r.
t_b::select_0_type b_select_0_type
node_type root() const
Returns the root of the suffix tree.
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.
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].
cst_fully(cst_fully &&cst)
Move constructor.
depth_type const & depth_sampling
sampled_node_type pred(leaf_type v) const
Returns the index of the last bracket in S before the leaf with index l.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
lcp_fully< cst_fully > lcp_type
node_type rightmost_leaf(const node_type v) const
Calculates the rightmost leaf in the subtree rooted at node v.
const_iterator begin() const
A class for the Compressed Suffix Tree (CST) proposed by Sadakane.
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 select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
node_type sl(node_type v) const
Compute the suffix link of node v.
const_iterator begin() const
Returns a const_iterator to the first element.
size_type size() const
Number of leaves in the suffix tree.
bool is_leaf(node_type v) const
Decide if a node is a leaf in the suffix tree.
size_type nodes() const
Get the number of nodes of the suffix tree.
const_iterator end() const
Returns a const_iterator to the element after the last element.
node_type root() const
Return the root of the suffix tree.
size_type depth(node_type v) const
Returns the depth of node v.
void resize(const size_type size)
Resize the int_vector in terms of elements.
value_type operator[](size_type i) const
random_access_const_iterator< lcp_fully > const_iterator
lcp_fully(lcp_fully const &)=default
lcp_fully & operator=(lcp_fully &&)=default
t_cst::size_type size_type
lcp_fully(t_cst const *cst)
const_iterator end() const
Returns a const_iterator to the element after the last element.
lcp_fully & operator=(lcp_fully const &)=default
const_iterator begin() const
Returns a const_iterator to the first element.
lcp_fully(lcp_fully &&)=default
static mm_event_proxy event(std::string const &name)
Generic iterator for a random access container.
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_wt.hpp contains an implementation of the compressed suffix array based on a wavelet tree.
cst_iterators.hpp contains iterator classes for traversing (compressed) suffix arrays.
cst_sada.hpp contains an implementation of Sadakane's CST.
dac_vector.hpp contains a vector which stores the values with variable length codes.
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
lcp_dac.hpp contains an implementation of a (compressed) LCP array.
memory_tracking.hpp contains two function for allocating and deallocating memory
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
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)
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
t_csa::size_type backward_search(t_csa const &csa, typename t_csa::size_type l, typename t_csa::size_type r, typename t_csa::char_type c, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
Backward search for a character c in an -interval in the CSA.
sd_vector.hpp contains the sdsl::sd_vector class, and classes which support rank and select for sd_ve...
Contains declarations and definitions of data structure concepts.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Helper class for construction process.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
suffix_array_algorithm.hpp contains algorithms on CSAs
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.
wt_pc.hpp contains a class for the wavelet tree of byte sequences.