SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <assert.h>
12#include <iosfwd>
13#include <stddef.h>
14#include <stdint.h>
15#include <string>
16#include <tuple>
17#include <utility>
18#include <vector>
19
20#include <sdsl/bits.hpp>
22#include <sdsl/cereal.hpp>
23#include <sdsl/csa_wt.hpp>
25#include <sdsl/cst_sada.hpp>
26#include <sdsl/dac_vector.hpp>
27#include <sdsl/int_vector.hpp>
28#include <sdsl/io.hpp>
29#include <sdsl/iterators.hpp>
30#include <sdsl/lcp_dac.hpp>
32#include <sdsl/sd_vector.hpp>
37#include <sdsl/util.hpp>
38#include <sdsl/wt_pc.hpp>
39
40namespace sdsl
41{
42struct cache_config;
43
44template <typename t_cst>
46{
47public:
48 typedef typename t_cst::size_type size_type;
52
54
55 enum
56 {
59 sa_order = 0
60 };
61
62private:
63 t_cst const * m_cst;
64
65public:
66 lcp_fully() = default;
67 lcp_fully(t_cst const * cst) : m_cst(cst){};
68
69 lcp_fully(lcp_fully const &) = default;
70 lcp_fully(lcp_fully &&) = default;
71 lcp_fully & operator=(lcp_fully const &) = default;
72 lcp_fully & operator=(lcp_fully &&) = default;
73 ~lcp_fully() = default;
74
76 {
77 return m_cst->size();
78 }
79
81 {
82 if (0 == i)
83 {
84 return 0;
85 }
86 else
87 {
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;
91 leaf_type v_r = i;
92
93 size_type i;
94 sampled_node_type u;
95 return m_cst->depth_lca(v_l, v_r, i, u);
96 }
97 }
98
101 {
102 return const_iterator(this, 0);
103 }
104
107 {
108 return const_iterator(this, size());
109 }
110};
111
113
145template <class t_csa = csa_wt<>,
146 uint32_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>
152{
153public:
155 typedef typename t_csa::size_type size_type;
156 typedef t_csa csa_type;
158 typedef typename t_csa::char_type char_type;
159 typedef std::pair<size_type, size_type> node_type; // Nodes are represented by their interval over the CSA
160 typedef size_type leaf_type; // Index of a leaf
161 typedef size_type sampled_node_type; // Node in the sampled tree represented by its index in s
162 typedef t_s_support s_support_type;
163 typedef t_b b_type;
164 typedef typename t_b::select_0_type b_select_0_type;
165 typedef typename t_b::select_1_type b_select_1_type;
166 typedef t_depth depth_type;
167
168 typedef typename t_csa::alphabet_category alphabet_category;
170
171private:
172 size_type m_delta;
173 size_type m_nodes;
174 csa_type m_csa;
175 bit_vector m_s;
176 s_support_type m_s_support;
177 b_type m_b;
178 b_select_0_type m_b_select0;
179 b_select_1_type m_b_select1;
180 depth_type m_depth;
181 lcp_type m_lcp = lcp_type(this);
182
183public:
184 size_type const & delta = m_delta;
185 csa_type const & csa = m_csa;
186 bit_vector const & s = m_s;
187 s_support_type const & s_support = m_s_support;
188 b_type const & b = m_b;
189 b_select_0_type const & b_select_0 = m_b_select0;
190 b_select_1_type const & b_select_1 = m_b_select1;
191 depth_type const & depth_sampling = m_depth;
192 lcp_type const & lcp = m_lcp;
193
195 cst_fully() = default;
196
198 cst_fully(cst_fully const & cst) :
199 m_delta(cst.m_delta),
200 m_nodes(cst.m_nodes),
201 m_csa(cst.m_csa),
202 m_s(cst.m_s),
203 m_s_support(cst.m_s_support),
204 m_b(cst.m_b),
205 m_b_select0(cst.m_b_select0),
206 m_b_select1(cst.m_b_select1),
207 m_depth(cst.m_depth)
208 {
209 m_s_support.set_vector(&m_s);
210 m_b_select0.set_vector(&m_b);
211 m_b_select1.set_vector(&m_b);
212 }
213
216 {
217 *this = std::move(cst);
218 }
219
221 cst_fully(cache_config & config);
222
224 {
225 return m_csa.size();
226 }
227
229 {
230 return t_csa::max_size();
231 }
232
233 bool empty() const
234 {
235 return m_csa.empty();
236 }
237
239 {
240 if (m_b.size() == 0)
241 {
242 return end();
243 }
244 return const_iterator(this, root(), false, true);
245 }
246
248 {
249 return const_iterator(this, root(), true, false);
250 }
251
254 {
255 if (this != &cst)
256 {
257 cst_fully tmp(cst);
258 *this = std::move(tmp);
259 }
260 return *this;
261 }
262
265 {
266 if (this != &cst)
267 {
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);
280 }
281 return *this;
282 }
283
285
288 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
289 {
290 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
291 size_type written_bytes = 0;
292 written_bytes += write_member(m_delta, out, child, "m_delta");
293 written_bytes += write_member(m_nodes, out, child, "m_nodes");
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");
301 structure_tree::add_size(child, written_bytes);
302 return written_bytes;
303 }
304
306
308 void load(std::istream & in)
309 {
310 read_member(m_delta, in);
311 read_member(m_nodes, in);
312 m_csa.load(in);
313 m_s.load(in);
314 m_s_support.load(in, &m_s);
315 m_b.load(in);
316 m_b_select0.load(in, &m_b);
317 m_b_select1.load(in, &m_b);
318 m_depth.load(in);
319 }
320
321 template <typename archive_t>
322 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
323 {
324 ar(CEREAL_NVP(m_delta));
325 ar(CEREAL_NVP(m_nodes));
326 ar(CEREAL_NVP(m_csa));
327 ar(CEREAL_NVP(m_s));
328 ar(CEREAL_NVP(m_s_support));
329 ar(CEREAL_NVP(m_b));
330 ar(CEREAL_NVP(m_b_select0));
331 ar(CEREAL_NVP(m_b_select1));
332 ar(CEREAL_NVP(m_depth));
333 }
334
335 template <typename archive_t>
336 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
337 {
338 ar(CEREAL_NVP(m_delta));
339 ar(CEREAL_NVP(m_nodes));
340 ar(CEREAL_NVP(m_csa));
341 ar(CEREAL_NVP(m_s));
342 ar(CEREAL_NVP(m_s_support));
343 m_s_support.set_vector(&m_s);
344 ar(CEREAL_NVP(m_b));
345 ar(CEREAL_NVP(m_b_select0));
346 m_b_select0.set_vector(&m_b);
347 ar(CEREAL_NVP(m_b_select1));
348 m_b_select1.set_vector(&m_b);
349 ar(CEREAL_NVP(m_depth));
350 }
351
353 bool operator==(cst_fully const & other) const noexcept
354 {
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);
358 }
359
361 bool operator!=(cst_fully const & other) const noexcept
362 {
363 return !(*this == other);
364 }
365
368 {
369 return node_type(0, m_csa.size() - 1);
370 }
371
374 {
375 return 0;
376 }
377
379 bool is_leaf(node_type v) const
380 {
381 return v.first == v.second;
382 }
383
385
393 {
394 assert(i > 0 and i <= m_csa.size());
395 return node_type(i - 1, i - 1);
396 }
397
400 {
401 return node_type(lb, rb);
402 }
403
406 {
407 return v.first;
408 }
409
412 {
413 return v.second;
414 }
415
417
422 size_type size(node_type const & v) const
423 {
424 return v.second - v.first + 1;
425 }
426
428
434 {
435 return node_type(v.first, v.first);
436 }
437
439
445 {
446 return node_type(v.second, v.second);
447 }
448
450 bool ancestor(node_type v, node_type w) const
451 {
452 return v.first <= w.first && v.second >= w.second;
453 }
454
456
461 {
462 return m_b_select0.select(v + 1) - v - 1;
463 }
464
466
473 {
474 sampled_node_type p = pred(l);
475 if (m_s[p])
476 {
477 return p;
478 }
479 else
480 {
481 return m_s_support.enclose(m_s_support.find_open(p));
482 }
483 }
484
486
493 {
494 assert(m_s[u] == 1);
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);
498
499 return node_type(b_left - u, b_right - u_end - 1);
500 }
501
503
511 {
512 assert(m_s[u] == 1 and m_s[q] == 1);
513 if (u > q)
514 {
515 std::swap(u, q);
516 }
517 else if (u == q)
518 {
519 return u;
520 }
521 if (u == sampled_root())
522 {
523 return sampled_root();
524 }
525 if (m_s_support.find_close(u) > q)
526 {
527 return u;
528 }
529
530 return m_s_support.double_enclose(u, q);
531 }
532
534
541 {
542 assert(m_s[u] == 1);
543
544 size_type idx = m_s_support.rank(u) - 1;
545 return m_depth[idx] * (m_delta / 2);
546 }
547
549
557 {
558 if (v == root()) // if v is the root
559 return 0;
560 else if (is_leaf(v))
561 {
562 return m_csa.size() - m_csa[v.first];
563 }
564
565 size_type i;
567 return depth_lca(v.first, v.second, i, u);
568 }
569
571
579 {
580 leaf_type l = std::min(v.first, w.first);
581 leaf_type r = std::max(v.second, w.second);
582
583 if (l == r)
584 {
585 return node_type(l, r);
586 }
587 else
588 {
589 return lca(l, r);
590 }
591 }
592
594
602 {
603 assert(l < r);
604
605 size_type i;
607 std::vector<char_type> c(delta, 0);
608 depth_lca(l, r, i, u, c);
609
610 node_type v = sampled_node(u);
611 leaf_type lb = v.first;
612 leaf_type rb = v.second;
613
614 for (size_type k = 0; k < i; k++)
615 {
616 backward_search(m_csa, lb, rb, c[i - k - 1], lb, rb);
617 }
618
619 return node_type(lb, rb);
620 }
621
623
633 // TODO: return by reference really necessary?
635 leaf_type r,
636 size_type & res_i,
637 sampled_node_type & res_u,
638 std::vector<char_type> & res_label) const
639 {
640 assert(l < r);
641
642 size_type max_d = 0;
643 size_type max_d_i = 0;
644 sampled_node_type max_d_node = 0;
645
646 for (size_type i = 0; i < m_delta; i++)
647 {
649 size_type d = i + depth(node);
650
651 if (d > max_d)
652 {
653 max_d = d;
654 max_d_i = i;
655 max_d_node = node;
656 }
657
658 char_type c = m_csa.F[l];
659 char_type comp = csa.char2comp[c];
660 res_label[i] = c;
661
662 // break if LCA of lb and rb is root
663 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1])
664 {
665 break;
666 }
667
668 l = m_csa.psi[l];
669 r = m_csa.psi[r];
670 }
671
672 res_i = max_d_i;
673 res_u = max_d_node;
674
675 return max_d;
676 }
677
680 {
681 assert(l < r);
682
683 size_type max_d = 0;
684 size_type max_d_i = 0;
685 sampled_node_type max_d_node = 0;
686
687 for (size_type i = 0; i < m_delta; i++)
688 {
690 size_type d = i + depth(node);
691
692 if (d > max_d)
693 {
694 max_d = d;
695 max_d_i = i;
696 max_d_node = node;
697 }
698
699 char_type c = m_csa.F[l];
700 char_type comp = csa.char2comp[c];
701
702 // break if LCA of lb and rb is root
703 if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1])
704 {
705 break;
706 }
707
708 l = m_csa.psi[l];
709 r = m_csa.psi[r];
710 }
711
712 res_i = max_d_i;
713 res_u = max_d_node;
714
715 return max_d;
716 }
717
719
726 {
727 if (v == root())
728 {
729 return root();
730 }
731 else if (is_leaf(v))
732 {
733 size_t leaf = m_csa.psi[v.first];
734 return node_type(leaf, leaf);
735 }
736
737 return lca(m_csa.psi[v.first], m_csa.psi[v.second]);
738 }
739
741 /*
742 * \param v A valid node of a cst_fully.
743 * \param c The character which should be prepended to the string of the current node.
744 * \return root() if the Weiner link of (v, c) does not exist, otherwise the Weiner link is returned.
745 * \par Time complexity
746 * \f$ \Order{ t_{rank\_bwt} + t_{lca}}\f$
747 */
748 node_type wl(node_type v, const char_type c) const
749 {
750 size_type l, r;
751 std::tie(l, r) = v;
752 backward_search(m_csa, l, r, c, l, r);
753 return node_type(l, r);
754 }
755
757
763 {
764 assert(is_leaf(v));
765 return m_csa[v.first];
766 }
767
769
776 {
777 const leaf_type l = v.first;
778 const leaf_type r = v.second;
779
780 node_type left_parent = root();
781 node_type right_parent = root();
782
783 if (l > 0)
784 {
785 left_parent = lca(l - 1, r);
786 }
787 if (r < m_csa.size() - 1)
788 {
789 right_parent = lca(l, r + 1);
790 }
791 return ancestor(right_parent, left_parent) ? left_parent : right_parent;
792 }
793
795
804 {
805 if (is_leaf(v))
806 {
807 return root();
808 }
809 size_type d = depth(v);
810 return child(v, c, d);
811 }
812
814 {
815 leaf_type lower;
816 leaf_type upper;
817
818 {
819 leaf_type begin = v.first;
820 leaf_type end = v.second + 1;
821
822 while (begin < end)
823 {
824 leaf_type sample_pos = (begin + end) / 2;
825 size_type char_pos = get_char_pos(sample_pos, d, m_csa);
826 char_type sample = m_csa.F[char_pos];
827 if (sample < c)
828 {
829 begin = sample_pos + 1;
830 }
831 else
832 {
833 end = sample_pos;
834 }
835 }
836
837 lower = begin;
838 }
839
840 {
841 leaf_type begin = v.first;
842 leaf_type end = v.second + 1;
843
844 while (begin < end)
845 {
846 leaf_type sample_pos = (begin + end) / 2;
847 size_type char_pos = get_char_pos(sample_pos, d, m_csa);
848 char_type sample = m_csa.F[char_pos];
849 if (sample <= c)
850 {
851 begin = sample_pos + 1;
852 }
853 else
854 {
855 end = sample_pos;
856 }
857 }
858
859 upper = begin;
860 }
861
862 if (lower == upper)
863 {
864 return root();
865 }
866
867 return node_type(lower, upper - 1);
868 }
869
871
876 node_type select_child(node_type v, size_type i) const
877 {
878 if (is_leaf(v))
879 {
880 return root();
881 }
882
883 size_type d = depth(v);
884 size_type char_pos = get_char_pos(v.first, d, m_csa);
885 char_type c = m_csa.F[char_pos];
886 node_type res = child(v, c, d);
887 while (i > 1)
888 {
889 if (res.second >= v.second)
890 {
891 return root();
892 }
893 char_pos = get_char_pos(res.second + 1, d, m_csa);
894 c = m_csa.F[char_pos];
895 res = child(v, c, d);
896 i--;
897 }
898
899 return res;
900 }
901
903
907 size_type degree(node_type const & v) const
908 {
909 if (is_leaf(v))
910 {
911 return 0;
912 }
913 else
914 {
915 size_type res = 1;
916 size_type d = depth(v);
917 size_type char_pos = get_char_pos(v.first, d, m_csa);
918 char_type c = m_csa.F[char_pos];
919 node_type v_i = child(v, c, d);
920 while (v_i.second < v.second)
921 {
922 ++res;
923 char_pos = get_char_pos(v_i.second + 1, d, m_csa);
924 c = m_csa.F[char_pos];
925 v_i = child(v, c, d);
926 }
927 return res;
928 }
929 }
930
932
935 cst_node_child_proxy<cst_fully> children(node_type const & v) const
936 {
937 return cst_node_child_proxy<cst_fully>(this, v);
938 }
939
941
945 node_type sibling(node_type v) const
946 {
947 node_type p = parent(v);
948 if (v.second >= p.second)
949 {
950 return root();
951 }
952 size_type d = depth(p);
953 size_type char_pos = get_char_pos(v.second + 1, d, m_csa);
954 char_type c = m_csa.F[char_pos];
955 return child(p, c, d);
956 }
957
958 char_type edge(node_type v, size_type d) const
959 {
960 assert(d >= 1 and d <= depth(v));
961 size_type char_pos = get_char_pos(v.first, d - 1, m_csa);
962 return m_csa.F[char_pos];
963 }
964
966
970 size_type node_depth(node_type v) const
971 {
972 size_type d = 0;
973 while (v != root())
974 {
975 ++d;
976 v = parent(v);
977 }
978 return d;
979 }
980
982 size_type nodes() const
983 {
984 return m_nodes;
985 }
986
988
993 size_type sampled_nodes() const
994 {
995 return m_s.size() / 2;
996 }
997};
998
999template <class t_csa, uint32_t t_delta, class t_s_support, class t_b, class t_depth, bool t_sample_leaves>
1001{
1002 // 1. Construct CST
1003 cst_sada<csa_type, lcp_dac<>> cst(config);
1004 m_nodes = cst.nodes();
1005
1006 if (t_delta > 0)
1007 {
1008 m_delta = t_delta;
1009 }
1010 else
1011 {
1012 const size_type n = cst.size();
1013 m_delta = (bits::hi(n - 1) + 1) * (bits::hi(bits::hi(n - 1)) + 1);
1014 if (m_delta < 2)
1015 {
1016 m_delta = 2;
1017 }
1018 }
1019
1020 size_type delta_half = m_delta / 2;
1021
1022 bit_vector is_sampled(cst.nodes(), false);
1023 is_sampled[cst.id(cst.root())] = true; // always sample root
1024 size_type sample_count = 1;
1025
1026 // 2a. Scan and mark leaves to be sampled
1027 if (t_sample_leaves)
1028 {
1029 auto event = memory_monitor::event("scan-leaves");
1030 size_type leaf_idx = 0;
1031 for (size_type i = 0; i < cst.size(); i++)
1032 {
1033 const size_type d = i + 1;
1034 if (d + delta_half <= cst.size() and d % delta_half == 0)
1035 {
1036 auto const node = cst.select_leaf(leaf_idx + 1);
1037 const size_type id = cst.id(node);
1038 if (!is_sampled[id])
1039 {
1040 is_sampled[id] = true;
1041 sample_count++;
1042 }
1043 }
1044 leaf_idx = cst.csa.lf[leaf_idx];
1045 }
1046 }
1047
1048 // 2b. Scan and mark inner nodes to be sampled
1049 {
1050 auto event = memory_monitor::event("scan-nodes");
1051 for (auto it = cst.begin(); it != cst.end(); ++it)
1052 {
1053 if (it.visit() == 1 and cst.is_leaf(*it) == false)
1054 {
1055 auto const node = *it;
1056 const size_type d = cst.depth(node);
1057 if (d % delta_half == 0)
1058 {
1059 auto v = cst.sl(node, delta_half);
1060 const size_type id = cst.id(v);
1061 if (!is_sampled[id])
1062 {
1063 is_sampled[id] = true;
1064 sample_count++;
1065 }
1066 }
1067 }
1068 }
1069 }
1070
1071 m_s.resize(2 * sample_count);
1072 util::set_to_value(m_s, 0);
1073 // increase size of tmp_b resp. m_b by two if text is empty
1074 bit_vector tmp_b(2 * sample_count + cst.size() + 2 * (cst.size() == 1), 0);
1075 int_vector<64> tmp_depth;
1076 tmp_depth.resize(sample_count);
1077
1078 // 3. Create sampled tree data structures
1079 {
1080 auto event = memory_monitor::event("node-sampling");
1081
1082 size_type s_idx = 0;
1083 size_type b_idx = 0;
1084 size_type sample_idx = 0;
1085
1086 for (auto it = cst.begin(); it != cst.end(); ++it)
1087 {
1088 auto node = *it;
1089 if (it.visit() == 1 && is_sampled[cst.id(node)])
1090 {
1091 m_s[s_idx++] = 1;
1092 tmp_b[b_idx++] = 1;
1093 tmp_depth[sample_idx++] = cst.depth(node) / delta_half;
1094 }
1095 if (cst.is_leaf(node))
1096 {
1097 b_idx++;
1098 }
1099 if ((cst.is_leaf(node) || it.visit() == 2) && is_sampled[cst.id(node)])
1100 {
1101 s_idx++;
1102 tmp_b[b_idx++] = 1;
1103 }
1104 }
1105 }
1106
1107 {
1108 auto event = memory_monitor::event("ss-depth");
1109 m_csa = std::move(cst.csa);
1110 util::init_support(m_s_support, &m_s);
1111 m_b = b_type(tmp_b);
1112 util::init_support(m_b_select0, &m_b);
1113 util::init_support(m_b_select1, &m_b);
1114 m_depth = depth_type(tmp_depth);
1115 }
1116}
1117
1118} // end namespace sdsl
1119
1120#endif // INCLUDED_SDSL_CST_FULLY
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
#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.
csa_type const & csa
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
bit_vector const & s
cst_fully & operator=(cst_fully &&cst)
Move Assignment Operator.
lcp_type const & lcp
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.
cst_tag index_category
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 size() const
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.
b_type const & b
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...
size_type const & delta
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.
bool empty() const
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 leaf_type
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.
Definition cst_sada.hpp:75
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:872
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:482
node_type sl(node_type v) const
Compute the suffix link of node v.
Definition cst_sada.hpp:775
const_iterator begin() const
Returns a const_iterator to the first element.
Definition cst_sada.hpp:295
size_type size() const
Number of leaves in the suffix tree.
Definition cst_sada.hpp:268
bool is_leaf(node_type v) const
Decide if a node is a leaf in the suffix tree.
Definition cst_sada.hpp:467
t_csa const & csa
Definition cst_sada.hpp:116
size_type nodes() const
Get the number of nodes of the suffix tree.
Definition cst_sada.hpp:936
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition cst_sada.hpp:314
node_type root() const
Return the root of the suffix tree.
Definition cst_sada.hpp:455
size_type depth(node_type v) const
Returns the depth of node v.
Definition cst_sada.hpp:496
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.
lcp_fully()=default
value_type operator[](size_type i) const
Definition cst_fully.hpp:80
random_access_const_iterator< lcp_fully > const_iterator
Definition cst_fully.hpp:50
lcp_fully(lcp_fully const &)=default
lcp_fully & operator=(lcp_fully &&)=default
t_cst::size_type size_type
Definition cst_fully.hpp:48
size_type size() const
Definition cst_fully.hpp:75
lcp_tag lcp_category
Definition cst_fully.hpp:53
lcp_fully(t_cst const *cst)
Definition cst_fully.hpp:67
const_iterator end() const
Returns a const_iterator to the element after the last element.
const_iterator iterator
Definition cst_fully.hpp:51
lcp_fully & operator=(lcp_fully const &)=default
size_type value_type
Definition cst_fully.hpp:49
const_iterator begin() const
Returns a const_iterator to the first element.
lcp_fully(lcp_fully &&)=default
~lcp_fully()=default
static mm_event_proxy event(std::string const &name)
Generic iterator for a random access container.
Definition iterators.hpp:24
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.
Definition util.hpp:597
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="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
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.
Definition bits.hpp:652
Helper class for construction process.
Definition config.hpp:66
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.