SDSL 3.0.1
Succinct Data Structure Library
cst_fully.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_CST_FULLY
9#define INCLUDED_SDSL_CST_FULLY
10
11#include <sdsl/bit_vectors.hpp>
12#include <sdsl/bp_support.hpp>
13#include <sdsl/construct.hpp>
15#include <sdsl/cst_sada.hpp>
20#include <sdsl/util.hpp>
21#include <sdsl/vectors.hpp>
22
23namespace sdsl
24{
25
26template <typename t_cst>
28{
29 public:
30 typedef typename t_cst::size_type size_type;
34
36
37 enum
38 {
41 sa_order = 0
42 };
43
44 private:
45 const t_cst * m_cst;
46
47 public:
48 lcp_fully() = default;
49 lcp_fully(const t_cst * cst)
50 : m_cst(cst){};
51
52 lcp_fully(const lcp_fully &) = default;
53 lcp_fully(lcp_fully &&) = default;
54 lcp_fully & operator=(const lcp_fully &) = default;
55 lcp_fully & operator=(lcp_fully &&) = default;
56 ~lcp_fully() = default;
57
58 size_type size() const { return m_cst->size(); }
59
61 {
62 if (0 == i) { return 0; }
63 else
64 {
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;
68 leaf_type v_r = i;
69
70 size_type i;
71 sampled_node_type u;
72 return m_cst->depth_lca(v_l, v_r, i, u);
73 }
74 }
75
77 const_iterator begin() const { return const_iterator(this, 0); }
78
80 const_iterator end() const { return const_iterator(this, size()); }
81};
82
84
116template <class t_csa = csa_wt<>,
117 uint32_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>
123{
124 public:
126 typedef typename t_csa::size_type size_type;
127 typedef t_csa csa_type;
129 typedef typename t_csa::char_type char_type;
130 typedef std::pair<size_type, size_type> node_type; // Nodes are represented by their interval over the CSA
131 typedef size_type leaf_type; // Index of a leaf
132 typedef size_type sampled_node_type; // Node in the sampled tree represented by its index in s
133 typedef t_s_support s_support_type;
134 typedef t_b b_type;
135 typedef typename t_b::select_0_type b_select_0_type;
136 typedef typename t_b::select_1_type b_select_1_type;
137 typedef t_depth depth_type;
138
139 typedef typename t_csa::alphabet_category alphabet_category;
141
142 private:
143 size_type m_delta;
144 size_type m_nodes;
145 csa_type m_csa;
146 bit_vector m_s;
147 s_support_type m_s_support;
148 b_type m_b;
149 b_select_0_type m_b_select0;
150 b_select_1_type m_b_select1;
151 depth_type m_depth;
152 lcp_type m_lcp = lcp_type(this);
153
154 public:
155 const size_type & delta = m_delta;
156 const csa_type & csa = m_csa;
157 const bit_vector & s = m_s;
158 const s_support_type & s_support = m_s_support;
159 const b_type & b = m_b;
160 const b_select_0_type & b_select_0 = m_b_select0;
161 const b_select_1_type & b_select_1 = m_b_select1;
162 const depth_type & depth_sampling = m_depth;
163 const lcp_type & lcp = m_lcp;
164
166 cst_fully() = default;
167
169 cst_fully(const cst_fully & cst)
170 : m_delta(cst.m_delta)
171 , m_nodes(cst.m_nodes)
172 , m_csa(cst.m_csa)
173 , m_s(cst.m_s)
174 , m_s_support(cst.m_s_support)
175 , m_b(cst.m_b)
176 , m_b_select0(cst.m_b_select0)
177 , m_b_select1(cst.m_b_select1)
178 , m_depth(cst.m_depth)
179 {
180 m_s_support.set_vector(&m_s);
181 m_b_select0.set_vector(&m_b);
182 m_b_select1.set_vector(&m_b);
183 }
184
186 cst_fully(cst_fully && cst) { *this = std::move(cst); }
187
189 cst_fully(cache_config & config);
190
191 size_type size() const { return m_csa.size(); }
192
193 static size_type max_size() { return t_csa::max_size(); }
194
195 bool empty() const { return m_csa.empty(); }
196
198 {
199 if (m_b.size() == 0) { return end(); }
200 return const_iterator(this, root(), false, true);
201 }
202
203 const_iterator end() const { return const_iterator(this, root(), true, false); }
204
207 {
208 if (this != &cst)
209 {
210 cst_fully tmp(cst);
211 *this = std::move(tmp);
212 }
213 return *this;
214 }
215
218 {
219 if (this != &cst)
220 {
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);
233 }
234 return *this;
235 }
236
238
241 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
242 {
243 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
244 size_type written_bytes = 0;
245 written_bytes += write_member(m_delta, out, child, "m_delta");
246 written_bytes += write_member(m_nodes, out, child, "m_nodes");
247 written_bytes += m_csa.serialize(out, child, "csa");
248 written_bytes += m_s.serialize(out, child, "s");
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");
254 structure_tree::add_size(child, written_bytes);
255 return written_bytes;
256 }
257
259
261 void load(std::istream & in)
262 {
263 read_member(m_delta, in);
264 read_member(m_nodes, in);
265 m_csa.load(in);
266 m_s.load(in);
267 m_s_support.load(in, &m_s);
268 m_b.load(in);
269 m_b_select0.load(in, &m_b);
270 m_b_select1.load(in, &m_b);
271 m_depth.load(in);
272 }
273
274 template <typename archive_t>
275 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
276 {
277 ar(CEREAL_NVP(m_delta));
278 ar(CEREAL_NVP(m_nodes));
279 ar(CEREAL_NVP(m_csa));
280 ar(CEREAL_NVP(m_s));
281 ar(CEREAL_NVP(m_s_support));
282 ar(CEREAL_NVP(m_b));
283 ar(CEREAL_NVP(m_b_select0));
284 ar(CEREAL_NVP(m_b_select1));
285 ar(CEREAL_NVP(m_depth));
286 }
287
288 template <typename archive_t>
289 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
290 {
291 ar(CEREAL_NVP(m_delta));
292 ar(CEREAL_NVP(m_nodes));
293 ar(CEREAL_NVP(m_csa));
294 ar(CEREAL_NVP(m_s));
295 ar(CEREAL_NVP(m_s_support));
296 m_s_support.set_vector(&m_s);
297 ar(CEREAL_NVP(m_b));
298 ar(CEREAL_NVP(m_b_select0));
299 m_b_select0.set_vector(&m_b);
300 ar(CEREAL_NVP(m_b_select1));
301 m_b_select1.set_vector(&m_b);
302 ar(CEREAL_NVP(m_depth));
303 }
304
306 bool operator==(cst_fully const & other) const noexcept
307 {
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);
311 }
312
314 bool operator!=(cst_fully const & other) const noexcept { return !(*this == other); }
315
317 node_type root() const { return node_type(0, m_csa.size() - 1); }
318
320 sampled_node_type sampled_root() const { return 0; }
321
323 bool is_leaf(node_type v) const { return v.first == v.second; }
324
326
334 {
335 assert(i > 0 and i <= m_csa.size());
336 return node_type(i - 1, i - 1);
337 }
338
341
343 leaf_type lb(node_type v) const { return v.first; }
344
346 leaf_type rb(node_type v) const { return v.second; }
347
349
354 size_type size(const node_type & v) const { return v.second - v.first + 1; }
355
357
362 node_type leftmost_leaf(const node_type v) const { return node_type(v.first, v.first); }
363
365
370 node_type rightmost_leaf(const node_type v) const { return node_type(v.second, v.second); }
371
373 bool ancestor(node_type v, node_type w) const { return v.first <= w.first && v.second >= w.second; }
374
376
380 sampled_node_type pred(leaf_type v) const { return m_b_select0.select(v + 1) - v - 1; }
381
383
390 {
391 sampled_node_type p = pred(l);
392 if (m_s[p]) { return p; }
393 else
394 {
395 return m_s_support.enclose(m_s_support.find_open(p));
396 }
397 }
398
400
407 {
408 assert(m_s[u] == 1);
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);
412
413 return node_type(b_left - u, b_right - u_end - 1);
414 }
415
417
425 {
426 assert(m_s[u] == 1 and m_s[q] == 1);
427 if (u > q) { std::swap(u, q); }
428 else if (u == q)
429 {
430 return u;
431 }
432 if (u == sampled_root()) { return sampled_root(); }
433 if (m_s_support.find_close(u) > q) { return u; }
434
435 return m_s_support.double_enclose(u, q);
436 }
437
439
446 {
447 assert(m_s[u] == 1);
448
449 size_type idx = m_s_support.rank(u) - 1;
450 return m_depth[idx] * (m_delta / 2);
451 }
452
454
462 {
463 if (v == root()) // if v is the root
464 return 0;
465 else if (is_leaf(v))
466 {
467 return m_csa.size() - m_csa[v.first];
468 }
469
470 size_type i;
472 return depth_lca(v.first, v.second, i, u);
473 }
474
476
484 {
485 leaf_type l = std::min(v.first, w.first);
486 leaf_type r = std::max(v.second, w.second);
487
488 if (l == r) { return node_type(l, r); }
489 else
490 {
491 return lca(l, r);
492 }
493 }
494
496
504 {
505 assert(l < r);
506
507 size_type i;
509 std::vector<char_type> c(delta, 0);
510 depth_lca(l, r, i, u, c);
511
512 node_type v = sampled_node(u);
513 leaf_type lb = v.first;
514 leaf_type rb = v.second;
515
516 for (size_type k = 0; k < i; k++) { backward_search(m_csa, lb, rb, c[i - k - 1], lb, rb); }
517
518 return node_type(lb, rb);
519 }
520
522
532 // TODO: return by reference really necessary?
534 leaf_type r,
535 size_type & res_i,
536 sampled_node_type & res_u,
537 std::vector<char_type> & res_label) const
538 {
539 assert(l < r);
540
541 size_type max_d = 0;
542 size_type max_d_i = 0;
543 sampled_node_type max_d_node = 0;
544
545 for (size_type i = 0; i < m_delta; i++)
546 {
548 size_type d = i + depth(node);
549
550 if (d > max_d)
551 {
552 max_d = d;
553 max_d_i = i;
554 max_d_node = node;
555 }
556
557 char_type c = m_csa.F[l];
558 char_type comp = csa.char2comp[c];
559 res_label[i] = c;
560
561 // break if LCA of lb and rb is root
562 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1]) { break; }
563
564 l = m_csa.psi[l];
565 r = m_csa.psi[r];
566 }
567
568 res_i = max_d_i;
569 res_u = max_d_node;
570
571 return max_d;
572 }
573
576 {
577 assert(l < r);
578
579 size_type max_d = 0;
580 size_type max_d_i = 0;
581 sampled_node_type max_d_node = 0;
582
583 for (size_type i = 0; i < m_delta; i++)
584 {
586 size_type d = i + depth(node);
587
588 if (d > max_d)
589 {
590 max_d = d;
591 max_d_i = i;
592 max_d_node = node;
593 }
594
595 char_type c = m_csa.F[l];
596 char_type comp = csa.char2comp[c];
597
598 // break if LCA of lb and rb is root
599 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1]) { break; }
600
601 l = m_csa.psi[l];
602 r = m_csa.psi[r];
603 }
604
605 res_i = max_d_i;
606 res_u = max_d_node;
607
608 return max_d;
609 }
610
612
619 {
620 if (v == root()) { return root(); }
621 else if (is_leaf(v))
622 {
623 size_t leaf = m_csa.psi[v.first];
624 return node_type(leaf, leaf);
625 }
626
627 return lca(m_csa.psi[v.first], m_csa.psi[v.second]);
628 }
629
631 /*
632 * \param v A valid node of a cst_fully.
633 * \param c The character which should be prepended to the string of the current node.
634 * \return root() if the Weiner link of (v, c) does not exist, otherwise the Weiner link is returned.
635 * \par Time complexity
636 * \f$ \Order{ t_{rank\_bwt} + t_{lca}}\f$
637 */
638 node_type wl(node_type v, const char_type c) const
639 {
640 size_type l, r;
641 std::tie(l, r) = v;
642 backward_search(m_csa, l, r, c, l, r);
643 return node_type(l, r);
644 }
645
647
653 {
654 assert(is_leaf(v));
655 return m_csa[v.first];
656 }
657
659
666 {
667 const leaf_type l = v.first;
668 const leaf_type r = v.second;
669
670 node_type left_parent = root();
671 node_type right_parent = root();
672
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;
676 }
677
679
688 {
689 if (is_leaf(v)) { return root(); }
690 size_type d = depth(v);
691 return child(v, c, d);
692 }
693
695 {
696 leaf_type lower;
697 leaf_type upper;
698
699 {
700 leaf_type begin = v.first;
701 leaf_type end = v.second + 1;
702
703 while (begin < end)
704 {
705 leaf_type sample_pos = (begin + end) / 2;
706 size_type char_pos = get_char_pos(sample_pos, d, m_csa);
707 char_type sample = m_csa.F[char_pos];
708 if (sample < c) { begin = sample_pos + 1; }
709 else
710 {
711 end = sample_pos;
712 }
713 }
714
715 lower = begin;
716 }
717
718 {
719 leaf_type begin = v.first;
720 leaf_type end = v.second + 1;
721
722 while (begin < end)
723 {
724 leaf_type sample_pos = (begin + end) / 2;
725 size_type char_pos = get_char_pos(sample_pos, d, m_csa);
726 char_type sample = m_csa.F[char_pos];
727 if (sample <= c) { begin = sample_pos + 1; }
728 else
729 {
730 end = sample_pos;
731 }
732 }
733
734 upper = begin;
735 }
736
737 if (lower == upper) { return root(); }
738
739 return node_type(lower, upper - 1);
740 }
741
743
748 node_type select_child(node_type v, size_type i) const
749 {
750 if (is_leaf(v)) { return root(); }
751
752 size_type d = depth(v);
753 size_type char_pos = get_char_pos(v.first, d, m_csa);
754 char_type c = m_csa.F[char_pos];
755 node_type res = child(v, c, d);
756 while (i > 1)
757 {
758 if (res.second >= v.second) { return root(); }
759 char_pos = get_char_pos(res.second + 1, d, m_csa);
760 c = m_csa.F[char_pos];
761 res = child(v, c, d);
762 i--;
763 }
764
765 return res;
766 }
767
769
773 size_type degree(const node_type & v) const
774 {
775 if (is_leaf(v)) { return 0; }
776 else
777 {
778 size_type res = 1;
779 size_type d = depth(v);
780 size_type char_pos = get_char_pos(v.first, d, m_csa);
781 char_type c = m_csa.F[char_pos];
782 node_type v_i = child(v, c, d);
783 while (v_i.second < v.second)
784 {
785 ++res;
786 char_pos = get_char_pos(v_i.second + 1, d, m_csa);
787 c = m_csa.F[char_pos];
788 v_i = child(v, c, d);
789 }
790 return res;
791 }
792 }
793
795
798 cst_node_child_proxy<cst_fully> children(const node_type & v) const
799 {
800 return cst_node_child_proxy<cst_fully>(this, v);
801 }
802
804
808 node_type sibling(node_type v) const
809 {
810 node_type p = parent(v);
811 if (v.second >= p.second) { return root(); }
812 size_type d = depth(p);
813 size_type char_pos = get_char_pos(v.second + 1, d, m_csa);
814 char_type c = m_csa.F[char_pos];
815 return child(p, c, d);
816 }
817
818 char_type edge(node_type v, size_type d) const
819 {
820 assert(d >= 1 and d <= depth(v));
821 size_type char_pos = get_char_pos(v.first, d - 1, m_csa);
822 return m_csa.F[char_pos];
823 }
824
826
830 size_type node_depth(node_type v) const
831 {
832 size_type d = 0;
833 while (v != root())
834 {
835 ++d;
836 v = parent(v);
837 }
838 return d;
839 }
840
842 size_type nodes() const { return m_nodes; }
843
845
850 size_type sampled_nodes() const { return m_s.size() / 2; }
851};
852
853template <class t_csa, uint32_t t_delta, class t_s_support, class t_b, class t_depth, bool t_sample_leaves>
855{
856 // 1. Construct CST
857 cst_sada<csa_type, lcp_dac<>> cst(config);
858 m_nodes = cst.nodes();
859
860 if (t_delta > 0) { m_delta = t_delta; }
861 else
862 {
863 const size_type n = cst.size();
864 m_delta = (bits::hi(n - 1) + 1) * (bits::hi(bits::hi(n - 1)) + 1);
865 if (m_delta < 2) { m_delta = 2; }
866 }
867
868 size_type delta_half = m_delta / 2;
869
870 bit_vector is_sampled(cst.nodes(), false);
871 is_sampled[cst.id(cst.root())] = true; // always sample root
872 size_type sample_count = 1;
873
874 // 2a. Scan and mark leaves to be sampled
875 if (t_sample_leaves)
876 {
877 auto event = memory_monitor::event("scan-leaves");
878 size_type leaf_idx = 0;
879 for (size_type i = 0; i < cst.size(); i++)
880 {
881 const size_type d = i + 1;
882 if (d + delta_half <= cst.size() and d % delta_half == 0)
883 {
884 const auto node = cst.select_leaf(leaf_idx + 1);
885 const size_type id = cst.id(node);
886 if (!is_sampled[id])
887 {
888 is_sampled[id] = true;
889 sample_count++;
890 }
891 }
892 leaf_idx = cst.csa.lf[leaf_idx];
893 }
894 }
895
896 // 2b. Scan and mark inner nodes to be sampled
897 {
898 auto event = memory_monitor::event("scan-nodes");
899 for (auto it = cst.begin(); it != cst.end(); ++it)
900 {
901 if (it.visit() == 1 and cst.is_leaf(*it) == false)
902 {
903 const auto node = *it;
904 const size_type d = cst.depth(node);
905 if (d % delta_half == 0)
906 {
907 auto v = cst.sl(node, delta_half);
908 const size_type id = cst.id(v);
909 if (!is_sampled[id])
910 {
911 is_sampled[id] = true;
912 sample_count++;
913 }
914 }
915 }
916 }
917 }
918
919 m_s.resize(2 * sample_count);
920 util::set_to_value(m_s, 0);
921 // increase size of tmp_b resp. m_b by two if text is empty
922 bit_vector tmp_b(2 * sample_count + cst.size() + 2 * (cst.size() == 1), 0);
923 int_vector<64> tmp_depth;
924 tmp_depth.resize(sample_count);
925
926 // 3. Create sampled tree data structures
927 {
928 auto event = memory_monitor::event("node-sampling");
929
930 size_type s_idx = 0;
931 size_type b_idx = 0;
932 size_type sample_idx = 0;
933
934 for (auto it = cst.begin(); it != cst.end(); ++it)
935 {
936 auto node = *it;
937 if (it.visit() == 1 && is_sampled[cst.id(node)])
938 {
939 m_s[s_idx++] = 1;
940 tmp_b[b_idx++] = 1;
941 tmp_depth[sample_idx++] = cst.depth(node) / delta_half;
942 }
943 if (cst.is_leaf(node)) { b_idx++; }
944 if ((cst.is_leaf(node) || it.visit() == 2) && is_sampled[cst.id(node)])
945 {
946 s_idx++;
947 tmp_b[b_idx++] = 1;
948 }
949 }
950 }
951
952 {
953 auto event = memory_monitor::event("ss-depth");
954 m_csa = std::move(cst.csa);
955 util::init_support(m_s_support, &m_s);
956 m_b = b_type(tmp_b);
957 util::init_support(m_b_select0, &m_b);
958 util::init_support(m_b_select1, &m_b);
959 m_depth = depth_type(tmp_depth);
960 }
961}
962
963} // end namespace sdsl
964
965#endif // INCLUDED_SDSL_CST_FULLY
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...
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
An forward iterator for (compressed) suffix trees.
A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al.
Definition: cst_fully.hpp:123
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition: cst_fully.hpp:241
cst_fully & operator=(cst_fully &&cst)
Move Assignment Operator.
Definition: cst_fully.hpp:217
cst_dfs_const_forward_iterator< cst_fully > const_iterator
Definition: cst_fully.hpp:125
const bit_vector & s
Definition: cst_fully.hpp:157
bool ancestor(node_type v, node_type w) const
Returns true iff v is an ancestor of w.
Definition: cst_fully.hpp:373
node_type parent(node_type v) const
Calculate the parent node of a node v.
Definition: cst_fully.hpp:665
node_type wl(node_type v, const char_type c) const
Compute the Weiner link of node v and character c.
Definition: cst_fully.hpp:638
const b_select_1_type & b_select_1
Definition: cst_fully.hpp:161
node_type leftmost_leaf(const node_type v) const
Calculates the leftmost leaf in the subtree rooted at node v.
Definition: cst_fully.hpp:362
const s_support_type & s_support
Definition: cst_fully.hpp:158
bool is_leaf(node_type v) const
Returns true iff node v is a leaf.
Definition: cst_fully.hpp:323
leaf_type rb(node_type v) const
Returns the rightmost leaf (right boundary) of a node.
Definition: cst_fully.hpp:346
bool operator==(cst_fully const &other) const noexcept
Equality operator.
Definition: cst_fully.hpp:306
cst_tag index_category
Definition: cst_fully.hpp:140
t_csa::alphabet_category alphabet_category
Definition: cst_fully.hpp:139
const_iterator end() const
Definition: cst_fully.hpp:203
cst_fully()=default
Default constructor.
t_s_support s_support_type
Definition: cst_fully.hpp:133
t_b::select_1_type b_select_1_type
Definition: cst_fully.hpp:136
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.
Definition: cst_fully.hpp:533
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.
Definition: cst_fully.hpp:687
void load(std::istream &in)
Load from a stream.
Definition: cst_fully.hpp:261
leaf_type lb(node_type v) const
Returns the leftmost leaf (left boundary) of a node.
Definition: cst_fully.hpp:343
size_type sn(node_type v) const
Compute the suffix number of a leaf node v.
Definition: cst_fully.hpp:652
t_csa::size_type size_type
Definition: cst_fully.hpp:126
node_type sl(node_type v) const
Compute the suffix link of a node v.
Definition: cst_fully.hpp:618
size_type sampled_node_type
Definition: cst_fully.hpp:132
const lcp_type & lcp
Definition: cst_fully.hpp:163
const b_type & b
Definition: cst_fully.hpp:159
size_type size() const
Definition: cst_fully.hpp:191
size_type depth(node_type v) const
Returns the depth of a node v.
Definition: cst_fully.hpp:461
node_type lca(node_type v, node_type w) const
Calculate the LCA of two nodes v and w.
Definition: cst_fully.hpp:483
sampled_node_type sampled_root() const
Returns the root of the sampled tree.
Definition: cst_fully.hpp:320
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
Definition: cst_fully.hpp:333
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition: cst_fully.hpp:275
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...
Definition: cst_fully.hpp:575
const size_type & delta
Definition: cst_fully.hpp:155
cst_fully(const cst_fully &cst)
Copy constructor.
Definition: cst_fully.hpp:169
const depth_type & depth_sampling
Definition: cst_fully.hpp:162
sampled_node_type lsa_leaf(leaf_type l) const
Returns the LSA (lowest sampled ancestor) for a leaf with index l.
Definition: cst_fully.hpp:389
static size_type max_size()
Definition: cst_fully.hpp:193
const b_select_0_type & b_select_0
Definition: cst_fully.hpp:160
size_type depth(sampled_node_type u) const
Returns the depth of a sampled node u.
Definition: cst_fully.hpp:445
const csa_type & csa
Definition: cst_fully.hpp:156
sampled_node_type sampled_lca(sampled_node_type u, sampled_node_type q) const
Returns the LCA of two nodes in the sampled tree.
Definition: cst_fully.hpp:424
std::pair< size_type, size_type > node_type
Definition: cst_fully.hpp:130
bool empty() const
Definition: cst_fully.hpp:195
t_csa::char_type char_type
Definition: cst_fully.hpp:129
bool operator!=(cst_fully const &other) const noexcept
Inequality operator.
Definition: cst_fully.hpp:314
node_type child(node_type v, char_type c, size_type d) const
Definition: cst_fully.hpp:694
node_type lca(leaf_type l, leaf_type r) const
Calculate the LCA of two leaves l and r.
Definition: cst_fully.hpp:503
t_b::select_0_type b_select_0_type
Definition: cst_fully.hpp:135
node_type root() const
Returns the root of the suffix tree.
Definition: cst_fully.hpp:317
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.
Definition: cst_fully.hpp:406
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].
Definition: cst_fully.hpp:340
cst_fully(cst_fully &&cst)
Move constructor.
Definition: cst_fully.hpp:186
size_type leaf_type
Definition: cst_fully.hpp:131
size_type size(const node_type &v) const
Calculate the number of leaves in the subtree rooted at node v.
Definition: cst_fully.hpp:354
sampled_node_type pred(leaf_type v) const
Returns the index of the last bracket in S before the leaf with index l.
Definition: cst_fully.hpp:380
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition: cst_fully.hpp:289
lcp_fully< cst_fully > lcp_type
Definition: cst_fully.hpp:128
node_type rightmost_leaf(const node_type v) const
Calculates the rightmost leaf in the subtree rooted at node v.
Definition: cst_fully.hpp:370
t_depth depth_type
Definition: cst_fully.hpp:137
cst_fully & operator=(const cst_fully &cst)
Copy Assignment Operator.
Definition: cst_fully.hpp:206
const_iterator begin() const
Definition: cst_fully.hpp:197
A class for the Compressed Suffix Tree (CST) proposed by Sadakane.
Definition: cst_sada.hpp:73
size_type id(node_type v) const
Computes a unique identification number for a node of the suffix tree in the range [0....
Definition: cst_sada.hpp:805
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
Definition: cst_sada.hpp:443
const t_csa & csa
Definition: cst_sada.hpp:111
node_type sl(node_type v) const
Compute the suffix link of node v.
Definition: cst_sada.hpp:716
const_iterator begin() const
Returns a const_iterator to the first element.
Definition: cst_sada.hpp:270
size_type size() const
Number of leaves in the suffix tree.
Definition: cst_sada.hpp:252
bool is_leaf(node_type v) const
Decide if a node is a leaf in the suffix tree.
Definition: cst_sada.hpp:428
size_type nodes() const
Get the number of nodes of the suffix tree.
Definition: cst_sada.hpp:866
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition: cst_sada.hpp:288
node_type root() const
Return the root of the suffix tree.
Definition: cst_sada.hpp:419
size_type depth(node_type v) const
Returns the depth of node v.
Definition: cst_sada.hpp:457
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.
Definition: int_vector.hpp:521
lcp_fully()=default
value_type operator[](size_type i) const
Definition: cst_fully.hpp:60
random_access_const_iterator< lcp_fully > const_iterator
Definition: cst_fully.hpp:32
lcp_fully(const t_cst *cst)
Definition: cst_fully.hpp:49
lcp_fully & operator=(lcp_fully &&)=default
t_cst::size_type size_type
Definition: cst_fully.hpp:30
size_type size() const
Definition: cst_fully.hpp:58
lcp_fully(const lcp_fully &)=default
lcp_tag lcp_category
Definition: cst_fully.hpp:35
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition: cst_fully.hpp:80
const_iterator iterator
Definition: cst_fully.hpp:33
lcp_fully & operator=(const lcp_fully &)=default
size_type value_type
Definition: cst_fully.hpp:31
const_iterator begin() const
Returns a const_iterator to the first element.
Definition: cst_fully.hpp:77
lcp_fully(lcp_fully &&)=default
~lcp_fully()=default
static mm_event_proxy event(const std::string &name)
Generic iterator for a random access container.
Definition: iterators.hpp:24
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
uint64_t id()
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:563
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
Definition: int_vector.hpp:946
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
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.
Definition: bits.hpp:651
Helper class for construction process.
Definition: config.hpp:67
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.