8#ifndef INCLUDED_SDSL_CST_FULLY
9#define INCLUDED_SDSL_CST_FULLY
26template <
typename t_cst>
62 if (0 == i) {
return 0; }
65 using leaf_type =
typename t_cst::leaf_type;
66 using sampled_node_type =
typename t_cst::sampled_node_type;
67 leaf_type v_l = i - 1;
72 return m_cst->depth_lca(v_l, v_r, i, u);
116template <
class t_csa = csa_wt<>,
117 u
int32_t t_delta = 0,
118 class t_s_support = bp_support_sada<>,
119 class t_b = sd_vector<>,
120 class t_depth = dac_vector<>,
121 bool t_sample_leaves = false>
170 : m_delta(cst.m_delta)
171 , m_nodes(cst.m_nodes)
174 , m_s_support(cst.m_s_support)
176 , m_b_select0(cst.m_b_select0)
177 , m_b_select1(cst.m_b_select1)
178 , m_depth(cst.m_depth)
180 m_s_support.set_vector(&m_s);
181 m_b_select0.set_vector(&m_b);
182 m_b_select1.set_vector(&m_b);
195 bool empty()
const {
return m_csa.empty(); }
199 if (m_b.size() == 0) {
return end(); }
211 *
this = std::move(tmp);
221 m_delta = cst.m_delta;
222 m_nodes = cst.m_nodes;
223 m_csa = std::move(cst.m_csa);
224 m_s = std::move(cst.m_s);
225 m_s_support = std::move(cst.m_s_support);
226 m_s_support.set_vector(&m_s);
227 m_b = std::move(cst.m_b);
228 m_b_select0 = std::move(cst.m_b_select0);
229 m_b_select0.set_vector(&m_b);
230 m_b_select1 = std::move(cst.m_b_select1);
231 m_b_select1.set_vector(&m_b);
232 m_depth = std::move(cst.m_depth);
247 written_bytes += m_csa.serialize(out,
child,
"csa");
249 written_bytes += m_s_support.serialize(out,
child,
"s_support");
250 written_bytes += m_b.serialize(out,
child,
"b");
251 written_bytes += m_b_select0.serialize(out,
child,
"b_select0");
252 written_bytes += m_b_select1.serialize(out,
child,
"b_select1");
253 written_bytes += m_depth.serialize(out,
child,
"depth");
255 return written_bytes;
267 m_s_support.load(in, &m_s);
269 m_b_select0.load(in, &m_b);
270 m_b_select1.load(in, &m_b);
274 template <
typename archive_t>
288 template <
typename archive_t>
296 m_s_support.set_vector(&m_s);
299 m_b_select0.set_vector(&m_b);
301 m_b_select1.set_vector(&m_b);
308 return (m_delta == other.m_delta) && (m_nodes == other.m_nodes) && (m_csa == other.m_csa) &&
309 (m_s == other.m_s) && (m_s_support == other.m_s_support) && (m_b == other.m_b) &&
310 (m_b_select0 == other.m_b_select0) && (m_b_select1 == other.m_b_select1) && (m_depth == other.m_depth);
335 assert(i > 0 and i <= m_csa.size());
392 if (m_s[p]) {
return p; }
395 return m_s_support.enclose(m_s_support.find_open(p));
409 size_type u_end = m_s_support.find_close(u);
410 size_type b_left = m_b_select1.select(u + 1);
411 size_type b_right = m_b_select1.select(u_end + 1);
413 return node_type(b_left - u, b_right - u_end - 1);
426 assert(m_s[u] == 1 and m_s[q] == 1);
433 if (m_s_support.find_close(u) > q) {
return u; }
435 return m_s_support.double_enclose(u, q);
450 return m_depth[idx] * (m_delta / 2);
467 return m_csa.size() - m_csa[v.first];
472 return depth_lca(v.first, v.second, i, u);
485 leaf_type l = std::min(v.first, w.first);
486 leaf_type r = std::max(v.second, w.second);
509 std::vector<char_type> c(
delta, 0);
537 std::vector<char_type> & res_label)
const
562 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1]) {
break; }
599 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1]) {
break; }
623 size_t leaf = m_csa.psi[v.first];
627 return lca(m_csa.psi[v.first], m_csa.psi[v.second]);
655 return m_csa[v.first];
673 if (l > 0) { left_parent =
lca(l - 1, r); }
674 if (r < m_csa.size() - 1) { right_parent =
lca(l, r + 1); }
675 return ancestor(right_parent, left_parent) ? left_parent : right_parent;
691 return child(v, c, d);
708 if (sample < c) {
begin = sample_pos + 1; }
727 if (sample <= c) {
begin = sample_pos + 1; }
737 if (lower == upper) {
return root(); }
758 if (res.second >= v.second) {
return root(); }
760 c = m_csa.F[char_pos];
761 res =
child(v, c, d);
783 while (v_i.second < v.second)
787 c = m_csa.F[char_pos];
788 v_i =
child(v, c, d);
798 cst_node_child_proxy<cst_fully> children(
const node_type & v)
const
800 return cst_node_child_proxy<cst_fully>(
this, v);
811 if (v.second >= p.second) {
return root(); }
815 return child(p, c, d);
820 assert(d >= 1 and d <=
depth(v));
822 return m_csa.F[char_pos];
842 size_type nodes()
const {
return m_nodes; }
853template <
class t_csa, u
int32_t t_delta,
class t_s_support,
class t_b,
class t_depth,
bool t_sample_leaves>
858 m_nodes = cst.
nodes();
860 if (t_delta > 0) { m_delta = t_delta; }
865 if (m_delta < 2) { m_delta = 2; }
871 is_sampled[cst.
id(cst.
root())] =
true;
882 if (d + delta_half <= cst.
size() and d % delta_half == 0)
888 is_sampled[
id] =
true;
892 leaf_idx = cst.
csa.lf[leaf_idx];
899 for (
auto it = cst.
begin(); it != cst.
end(); ++it)
901 if (it.visit() == 1 and cst.
is_leaf(*it) ==
false)
903 const auto node = *it;
905 if (d % delta_half == 0)
907 auto v = cst.
sl(node, delta_half);
911 is_sampled[
id] =
true;
919 m_s.
resize(2 * sample_count);
924 tmp_depth.
resize(sample_count);
934 for (
auto it = cst.
begin(); it != cst.
end(); ++it)
937 if (it.visit() == 1 && is_sampled[cst.
id(node)])
941 tmp_depth[sample_idx++] = cst.
depth(node) / delta_half;
943 if (cst.
is_leaf(node)) { b_idx++; }
944 if ((cst.
is_leaf(node) || it.visit() == 2) && is_sampled[cst.
id(node)])
954 m_csa = std::move(cst.
csa);
955 util::init_support(m_s_support, &m_s);
957 util::init_support(m_b_select0, &m_b);
958 util::init_support(m_b_select1, &m_b);
bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations.
bp_support.hpp contains several classed which support find_open, find_close, enclose and rr-enclose q...
An forward iterator for (compressed) suffix trees.
A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al.
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.
const b_select_1_type & b_select_1
node_type leftmost_leaf(const node_type v) const
Calculates the leftmost leaf in the subtree rooted at node v.
const s_support_type & s_support
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 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.
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.
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...
cst_fully(const cst_fully &cst)
Copy constructor.
const depth_type & depth_sampling
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()
const b_select_0_type & b_select_0
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
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.
size_type size(const node_type &v) const
Calculate the number of leaves in the subtree rooted at node v.
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.
cst_fully & operator=(const cst_fully &cst)
Copy Assignment Operator.
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 load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
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(const t_cst *cst)
lcp_fully & operator=(lcp_fully &&)=default
t_cst::size_type size_type
lcp_fully(const lcp_fully &)=default
const_iterator end() const
Returns a const_iterator to the element after the last element.
lcp_fully & operator=(const lcp_fully &)=default
const_iterator begin() const
Returns a const_iterator to the first element.
lcp_fully(lcp_fully &&)=default
static mm_event_proxy event(const std::string &name)
Generic iterator for a random access container.
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
construct.hpp contains methods to construct indexes (compressed suffix arrays and trees).
cst_iterators.hpp contains iterator classes for traversing (compressed) suffix arrays.
cst_sada.hpp contains an implementation of Sadakane's CST.
int_vector ::size_type size_type
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, const t_csa &csa)
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
t_csa::size_type backward_search(const t_csa &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.
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.
suffix_arrays.hpp contains generic classes for different suffix array classes.
suffix_tree_algorithm.hpp contains algorithms on CSTs
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.