SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
cst_sada.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_SADA
9#define INCLUDED_SDSL_CST_SADA
10
11#include <cassert>
12#include <iostream>
13#include <stddef.h>
14#include <string>
15#include <type_traits>
16
18#include <sdsl/cereal.hpp>
19#include <sdsl/config.hpp>
20#include <sdsl/csa_sada.hpp> // for std initialization of cst_sada
22#include <sdsl/int_vector.hpp>
24#include <sdsl/io.hpp>
25#include <sdsl/lcp.hpp>
34#include <sdsl/util.hpp>
35
36namespace sdsl
37{
38
40
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>>
75{
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.");
78
79public:
82 typedef typename t_csa::size_type size_type;
83 typedef ptrdiff_t difference_type;
84 typedef t_csa csa_type;
85 typedef typename t_lcp::template type<cst_sada> lcp_type;
86 typedef typename t_csa::char_type char_type;
87 typedef typename t_csa::string_type string_type;
89 typedef t_bp_support bp_support_type;
90 typedef t_rank_10 rank_10_type;
91 typedef t_select_10 select_10_type;
92
93 typedef typename t_csa::alphabet_type::comp_char_type comp_char_type;
94 typedef typename t_csa::alphabet_type::sigma_type sigma_type;
95
96 typedef typename t_csa::alphabet_category alphabet_category;
98
99private:
100 t_csa m_csa; // suffix array
101 lcp_type m_lcp; // lcp information
102 bit_vector m_bp; // balanced parentheses sequence for suffix tree
103 bp_support_type m_bp_support; // support for the balanced parentheses sequence
104 rank_10_type m_bp_rank10; // rank_support for leaves, i.e. "10" bit pattern
105 select_10_type m_bp_select10; // select_support for leaves, i.e. "10" bit pattern
106
107 /* Get the number of leaves that are in the subtree rooted at the first child of v +
108 * number of leafs in the subtrees rooted at the children of parent(v) which precede v in the tree.
109 */
110 size_type inorder(node_type v) const
111 {
112 return m_bp_rank10(m_bp_support.find_close(v + 1) + 1);
113 }
114
115public:
116 t_csa const & csa = m_csa;
117 lcp_type const & lcp = m_lcp;
118 bit_vector const & bp = m_bp;
119 bp_support_type const & bp_support = m_bp_support;
120 rank_10_type const & bp_rank_10 = m_bp_rank10;
121 select_10_type const & bp_select_10 = m_bp_select10;
122
124 cst_sada() = default;
125
127 cst_sada(cst_sada const & cst) :
128 m_csa(cst.m_csa),
129 m_bp(cst.m_bp),
130 m_bp_support(cst.m_bp_support),
131 m_bp_rank10(cst.m_bp_rank10),
132 m_bp_select10(cst.m_bp_select10)
133 {
134 copy_lcp(m_lcp, cst.m_lcp, *this);
135 m_bp_support.set_vector(&m_bp);
136 m_bp_rank10.set_vector(&m_bp);
137 m_bp_select10.set_vector(&m_bp);
138 }
139
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))
147 {
148 move_lcp(m_lcp, cst.m_lcp, *this);
149 m_bp_support.set_vector(&m_bp);
150 m_bp_rank10.set_vector(&m_bp);
151 m_bp_select10.set_vector(&m_bp);
152 }
153
156 {
157 {
158 auto event = memory_monitor::event("bps-dfs");
160
161 bool const o_par = true;
162 bool const c_par = !o_par;
163
164 // trim bps to maximal size of tree
165 m_bp.resize(4 * lcp.size());
166
167 if (lcp.size() > 0)
168 {
169 // run from back to front of lcp, enumerate intervals and count
170 // opening parentheses per position i
171 sorted_stack_support stack(lcp.size() + 1);
172 stack.push(0); // for lcp[n+1]
173 size_type p = m_bp.size() - 1;
174 for (size_type i = lcp.size() - 1; i > 0; --i)
175 {
176 // compute number of opening parentheses at position i
177 size_type co = 1; // for singleton interval
178 size_type x = lcp[i] + 1; // to indicate start and end of lcp-array
179 while (stack.top() > x)
180 {
181 stack.pop();
182 ++co;
183 }
184 if (stack.top() < x)
185 {
186 stack.push(x);
187 }
188 // encode number of opening parenthesis at i as unary number
189 m_bp[p--] = o_par;
190 while (--co > 0)
191 m_bp[p--] = c_par;
192 }
193 // handle last value lcp[0] separate, since it virtually is a -1, but in real is a 0
194 m_bp[p--] = o_par; // code last number of opening parenthesis
195 while (stack.size() > 1)
196 { // remove all elements except the zero from stack for next run
197 stack.pop();
198 m_bp[p--] = c_par; // move k to first bit before unary number
199 }
200
201 // run from front to back of lcp, enumerate intervals,
202 // write opening parentheses and leave out closing parentheses
203 size_type q = 0;
204 for (size_type i = 1; i < lcp.size(); ++i)
205 {
206 // compute number of opening parentheses at position i-1 using
207 // the unary coding from the last step
208 size_type co = 0;
209 do
210 {
211 ++co;
212 }
213 while (m_bp[++p] == c_par);
214
215 // compute number of closing parentheses at position i-1
216 size_type cc = 1; // for singleton interval
217 size_type x = lcp[i] + 1;
218 while (stack.top() > x)
219 {
220 stack.pop();
221 ++cc;
222 }
223 if (stack.top() < x)
224 {
225 stack.push(x);
226 }
227 // write sequence for position i-1
228 while (co-- > 0)
229 m_bp[q++] = o_par;
230 while (cc-- > 0)
231 m_bp[q++] = c_par;
232 }
233 // handle last value lcp[n+1] separate
234 m_bp[q++] = o_par;
235 while (!stack.empty())
236 {
237 m_bp[q++] = c_par;
238 stack.pop();
239 }
240
241 // trim bps to correct size and stop
242 m_bp.resize(q);
243 }
244 }
245 {
246 auto event = memory_monitor::event("bpss-dfs");
247
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);
251 }
252 {
253 auto event = memory_monitor::event("clcp");
254 cache_config tmp_config(false, config.dir, config.id, config.file_map);
255 construct_lcp(m_lcp, *this, tmp_config);
256 config.file_map = tmp_config.file_map;
257 }
258 {
259 auto event = memory_monitor::event("load csa");
260 load_from_cache(m_csa, std::string(conf::KEY_CSA) + "_" + util::class_to_hash(m_csa), config);
261 }
262 }
263
265
269 {
270 return m_csa.size();
271 }
272
274
278 {
279 return t_csa::max_size();
280 }
281
283
286 bool empty() const
287 {
288 return m_csa.empty();
289 }
290
292
296 {
297 if (0 == m_bp.size()) // special case: tree is uninitialized
298 return end();
299 return const_iterator(this, root(), false, true);
300 }
301
304 {
305 if (0 == m_bp.size() and root() == v)
306 return end();
307 return const_iterator(this, v, false, true);
308 }
309
311
315 {
316 return const_iterator(this, root(), true, false);
317 }
318
320 const_iterator end(node_type const & v) const
321 {
322 if (root() == v)
323 return end();
324 return ++const_iterator(this, v, true, true);
325 }
326
329 {
330 if (0 == m_bp.size()) // special case: tree is uninitialized
331 return end_bottom_up();
333 }
334
337 {
338 return const_bottom_up_iterator(this, root(), false);
339 }
340
342
346 {
347 if (this != &cst)
348 {
349 cst_sada tmp(cst);
350 *this = std::move(tmp);
351 }
352 return *this;
353 }
354
356
360 {
361 if (this != &cst)
362 {
363 m_csa = std::move(cst.m_csa);
364 move_lcp(m_lcp, cst.m_lcp, *this);
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);
372 }
373 return *this;
374 }
375
377 bool operator==(cst_sada const & other) const noexcept
378 {
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);
382 }
383
385 bool operator!=(cst_sada const & other) const noexcept
386 {
387 return !(*this == other);
388 }
389
391
394 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
395 {
396 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
397 size_type written_bytes = 0;
398 written_bytes += m_csa.serialize(out, child, "csa");
399 written_bytes += m_lcp.serialize(out, child, "lcp");
400 written_bytes += m_bp.serialize(out, child, "bp");
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");
404 structure_tree::add_size(child, written_bytes);
405 return written_bytes;
406 }
407
409
411 void load(std::istream & in)
412 {
413 m_csa.load(in);
414 load_lcp(m_lcp, in, *this);
415 m_bp.load(in);
416 m_bp_support.load(in, &m_bp);
417 m_bp_rank10.load(in, &m_bp);
418 m_bp_select10.load(in, &m_bp);
419 }
420
421 template <typename archive_t>
422 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
423 {
424 ar(CEREAL_NVP(m_csa));
425 ar(CEREAL_NVP(m_lcp));
426 ar(CEREAL_NVP(m_bp));
427 ar(CEREAL_NVP(m_bp_support));
428 ar(CEREAL_NVP(m_bp_rank10));
429 ar(CEREAL_NVP(m_bp_select10));
430 }
431
432 template <typename archive_t>
433 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
434 {
435 ar(CEREAL_NVP(m_csa));
436 ar(CEREAL_NVP(m_lcp));
437 set_lcp_pointer(m_lcp, *this);
438 ar(CEREAL_NVP(m_bp));
439 ar(CEREAL_NVP(m_bp_support));
440 m_bp_support.set_vector(&m_bp);
441 ar(CEREAL_NVP(m_bp_rank10));
442 m_bp_rank10.set_vector(&m_bp);
443 ar(CEREAL_NVP(m_bp_select10));
444 m_bp_select10.set_vector(&m_bp);
445 }
446
448 /* @{ */
449
451
456 {
457 return 0;
458 }
459
461
467 bool is_leaf(node_type v) const
468 {
469 assert(m_bp[v] == 1); // assert that v is a valid node of the suffix tree
470 // if there is a closing parenthesis at position v+1, the node is a leaf
471 return !m_bp[v + 1];
472 }
473
475
483 {
484 assert(i > 0 and i <= m_csa.size());
485 // -1 as select(i) returns the postion of the 0 of pattern 10
486 return m_bp_select10.select(i) - 1;
487 }
488
490
497 {
498 if (v == root()) // if v is the root
499 return 0;
500
501 if (is_leaf(v))
502 { // if v is a leave
503 size_type i = m_bp_rank10(v); // get the index in the suffix array
504 return m_csa.size() - m_csa[i];
505 }
506 assert(inorder(v) > 0);
507 return m_lcp[inorder(v)];
508 }
509
511
518 {
519 // -2 as the root() we assign depth=0 to the root
520 return (m_bp_support.rank(v) << 1) - v - 2;
521 }
522
524
532 {
533 size_type r = m_bp_support.find_close(v);
534 return m_bp_rank10(r + 1) - m_bp_rank10(v);
535 }
536
538
544 {
545 return m_bp_select10(m_bp_rank10(v) + 1) - 1;
546 }
547
549
555 {
556 size_type r = m_bp_support.find_close(v);
557 return m_bp_select10(m_bp_rank10(r + 1)) - 1;
558 }
559
561
568 size_type lb(const node_type v) const
569 {
570 return m_bp_rank10(v);
571 }
572
574
581 size_type rb(const node_type v) const
582 {
583 size_type r = m_bp_support.find_close(v);
584 return m_bp_rank10(r + 1) - 1;
585 }
586
588
594 {
595 assert(m_bp[v] == 1); // assert a valid node
596 if (v == root())
597 return root();
598 else
599 {
600 return m_bp_support.enclose(v);
601 }
602 }
603
605
614
616
623 {
624 if (v == root())
625 return root();
626 node_type sib = m_bp_support.find_close(v) + 1;
627 if (m_bp[sib])
628 return sib;
629 else
630 return root();
631 }
632
634 /*
635 * \param v A valid tree node of the cst.
636 * \param c First character of the edge label from v to the desired child.
637 * \param char_pos Reference which will hold the position (0-based) of the matching char c in the sorted text/suffix
638 * array. \return The child node w which edge label (v,w) starts with c or root() if it does not exist. \par Time
639 * complexity \f$ \Order( (\saaccess+\isaaccess) \cdot \sigma + \lcpaccess) \f$ \par Note With range median mimimum
640 * queries (RMMQ) one can code this operation in \f$\log \sigma \f$ time
641 */
642 node_type child(node_type v, const char_type c, size_type & char_pos) const
643 {
644 if (is_leaf(v)) // if v is a leaf = (), v has no child
645 return root();
646 // else v = ( ( ))
647 comp_char_type cc = m_csa.char2comp[c];
648 if (cc == 0 and c != 0) // TODO: aendere char2comp so ab, dass man diesen sonderfall nicht braucht
649 return root();
650 size_type char_ex_max_pos = m_csa.C[cc + 1], char_inc_min_pos = m_csa.C[cc];
651
652 size_type d = depth(v); // time complexity: \lcpaccess
653 size_type res = v + 1;
654 while (true)
655 {
656 if (is_leaf(res))
657 {
658 char_pos = get_char_pos(m_bp_rank10(res), d, m_csa);
659 }
660 else
661 {
662 char_pos = get_char_pos(inorder(res), d, m_csa);
663 }
664 if (char_pos >= char_ex_max_pos) // if the current char is lex. greater than the searched char: exit
665 return root();
666 if (char_pos >= char_inc_min_pos) // if the current char is lex. equal with the
667 return res;
668 res = m_bp_support.find_close(res) + 1;
669 if (!m_bp[res]) // closing parenthesis: there exists no next child
670 return root();
671 }
672 }
673
675 // \sa child(node_type v, const char_type c, size_type &char_pos)
677 {
678 size_type char_pos;
679 return child(v, c, char_pos);
680 }
681
683
692 {
693 if (is_leaf(v)) // if v is a leave, v has no child
694 return root();
695 size_type res = v + 1;
696 while (i > 1)
697 {
698 res = m_bp_support.find_close(res) + 1;
699 if (!m_bp[res])
700 { // closing parenthesis: there exists no next child
701 return root();
702 }
703 --i;
704 }
705 return res;
706 }
707
709
715 {
716 assert(1 <= d);
717 assert(d <= depth(v));
718 size_type i = 0; // index of the first suffix in the subtree of v
719 if (is_leaf(v))
720 { // if v is a leave
721 i = m_bp_rank10(v); // get the index in the suffix array
722 }
723 else
724 {
725 i = inorder(v);
726 }
727 size_type order = get_char_pos(i, d - 1, m_csa);
728 size_type c_begin = 1, c_end = ((size_type)m_csa.sigma) + 1, mid;
729 while (c_begin < c_end)
730 {
731 mid = (c_begin + c_end) >> 1;
732 if (m_csa.C[mid] <= order)
733 {
734 c_begin = mid + 1;
735 }
736 else
737 {
738 c_end = mid;
739 }
740 }
741 return m_csa.comp2char[c_begin - 1];
742 }
743
745
753 {
754 assert(m_bp[v] == 1 and m_bp[w] == 1);
755 if (v > w)
756 {
757 std::swap(v, w);
758 }
759 else if (v == w)
760 {
761 return v;
762 }
763 if (v == root())
764 return root();
765 return m_bp_support.double_enclose(v, w);
766 }
767
769
776 {
777 if (v == root())
778 return root();
779 // get leftmost leaf in the tree rooted at v
780 size_type left = m_bp_rank10(v);
781 if (is_leaf(v))
782 {
783 return select_leaf(m_csa.psi[left] + 1);
784 }
785 // get the rightmost leaf in the tree rooted at v
786 size_type right = m_bp_rank10(m_bp_support.find_close(v)) - 1;
787 assert(left < right);
788 node_type left_leaf = select_leaf(m_csa.psi[left] + 1);
789 node_type right_leaf = select_leaf(m_csa.psi[right] + 1);
790 return lca(left_leaf, right_leaf);
791 }
792
794
801 {
802 if (v == root())
803 return root();
804 // get leftmost leaf in the tree rooted at v
805 size_type left = m_bp_rank10(v);
806 if (is_leaf(v))
807 {
808 return select_leaf(get_char_pos(left, i, m_csa) + 1);
809 }
810 // get the rightmost leaf in the tree rooted at v
811 size_type right = m_bp_rank10(m_bp_support.find_close(v)) - 1;
812 assert(left < right);
813 node_type left_leaf = select_leaf(get_char_pos(left, i, m_csa) + 1);
814 node_type right_leaf = select_leaf(get_char_pos(right, i, m_csa) + 1);
815 return lca(left_leaf, right_leaf);
816 }
817
819 /*
820 * \param v A valid node of a cst_sada.
821 * \param c The character which should be prepended to the string of the current node.
822 * \return root() if the Weiner link of (v, c) does not exist, otherwise the Weiner link is returned.
823 * \par Time complexity
824 * \f$ \Order{ t_{rank\_bwt} + t_{lca}}\f$
825 */
826 node_type wl(node_type v, const char_type c) const
827 {
828 // get leftmost leaf in the tree rooted at v
829 size_type left = m_bp_rank10(v);
830 // get the rightmost leaf in the tree rooted at v
831 size_type right = is_leaf(v) ? left : m_bp_rank10(m_bp_support.find_close(v)) - 1;
832
833 size_type c_left = m_csa.bwt.rank(left, c);
834 size_type c_right = m_csa.bwt.rank(right + 1, c);
835
836 if (c_left == c_right) // there exists no Weiner link
837 return root();
838 if (c_left + 1 == c_right)
839 return select_leaf(m_csa.C[m_csa.char2comp[c]] + c_left + 1);
840 else
841 {
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);
845 node_type left_leaf = select_leaf(left + 1);
846 node_type right_leaf = select_leaf(right + 1);
847 return lca(left_leaf, right_leaf);
848 }
849 }
850
852
858 {
859 assert(is_leaf(v));
860 // count the leaves left to leaf v
861 return m_csa[m_bp_rank10(v)];
862 }
863
865
873 {
874 // v+1 is < m_bp.size(), as v is the position of an open parenthesis
875 if (m_bp[v + 1])
876 { // case (a) inner node
877 return size() + (m_bp_support.rank(v) - 1) - m_bp_rank10(v);
878 }
879 else
880 { // case (b) leaf
881 return m_bp_rank10(v);
882 }
883 }
884
886
894 {
895 if (id < size())
896 { // the corresponding node is a leaf
897 return select_leaf(id + 1);
898 }
899 else
900 { // the corresponding node is a inner node
901 id = id + 1 - size();
902 // solved by binary search; TODO: can be done in constant time by using a select structure on the bitpattern
903 // 11
904 size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
905 // invariant: arg(lb) < id, arg(rb)>= id
906 while (rb - lb > 1)
907 {
908 size_type mid = lb + (rb - lb) / 2; // mid \in [0..m_bp.size()-1]
909 if (m_bp[mid] == 0 and m_bp[mid - 1] == 1)
910 { // if we are ``half on a leaf''
911 ++mid; // we step one to the right to include it
912 }
913 // get the number of open inner nodes before position mid, i.e. arg(mid)
914 size_type mid_id = m_bp_support.rank(mid - 1)
915 - m_bp_rank10(mid); // Note: mid-1 is valid of mid is of type ``size_type'' as us the
916 // parameter of rank
917 if (mid_id < id)
918 {
919 lb = mid;
920 }
921 else
922 { // mid_id >= x
923 rb = mid;
924 }
925 }
926 return lb;
927 }
928 }
929
931 /*
932 * \return The number of nodes of the suffix tree.
933 * \par Time complexity
934 * \f$ \Order{1} \f$
935 */
937 {
938 return m_bp.size() >> 1;
939 }
940
942 /* \param lb Left bound of the lcp-interval [lb..rb] (inclusive).
943 * \param rb Right bound of the lcp-interval [lb..rb] (inclusive).
944 *\ return The node in the suffix tree corresponding lcp-interval [lb..rb]
945 */
947 {
948 return lca(select_leaf(lb + 1), select_leaf(rb + 1));
949 }
950
952
959 {
960 size_type res = 0;
961 v = v + 1;
962 while (m_bp[v])
963 { // found open parentheses
964 ++res;
965 v = m_bp_support.find_close(v) + 1;
966 }
967 return res;
968 }
969
971
976 {
977 size_type ii = 0;
978 if (i > 0)
979 {
980 size_type ipos = m_bp_select10(i) - 1; // -1 as select returns the position of the zero
981 size_type ip1pos = m_bp_select10(i + 1) - 1; // " " " " " " " " "
982 ii = m_bp_support.double_enclose(ipos, ip1pos);
983 }
984 ii = m_bp_support.find_close(ii);
985 // all right, as bp[ii] = 0
986 return ii - m_bp_support.rank(ii) - m_bp_rank10(ii);
987 }
988 /* @} */
989};
990
991} // end namespace sdsl
992#endif
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
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.
Definition cst_sada.hpp:75
t_rank_10 rank_10_type
Definition cst_sada.hpp:90
size_type tlcp_idx(size_type i) const
Maps an index i to the position in TLCP where LCP[i] can be found.
Definition cst_sada.hpp:975
size_type sn(node_type v) const
Compute the suffix number of a leaf node v.
Definition cst_sada.hpp:857
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 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.
Definition cst_sada.hpp:676
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
ptrdiff_t difference_type
Definition cst_sada.hpp:83
node_type sibling(node_type v) const
Returns the next sibling of node v.
Definition cst_sada.hpp:622
cst_sada(cst_sada &&cst)
Move constructor.
Definition cst_sada.hpp:141
cst_sada(cache_config &config)
Construct CST from file_map.
Definition cst_sada.hpp:155
t_select_10 select_10_type
Definition cst_sada.hpp:91
node_type rightmost_leaf(const node_type v) const
Calculates the rightmost leaf in the subtree rooted at node v.
Definition cst_sada.hpp:554
cst_sada()=default
Default constructor.
rank_10_type const & bp_rank_10
Definition cst_sada.hpp:120
size_type node_type
Type for the nodes in the tree.
Definition cst_sada.hpp:88
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...
Definition cst_sada.hpp:303
lcp_type const & lcp
Definition cst_sada.hpp:117
cst_bottom_up_const_forward_iterator< cst_sada > const_bottom_up_iterator
Definition cst_sada.hpp:81
bool operator!=(cst_sada const &other) const noexcept
Inequality operator.
Definition cst_sada.hpp:385
t_csa::char_type char_type
Definition cst_sada.hpp:86
node_type sl(node_type v) const
Compute the suffix link of node v.
Definition cst_sada.hpp:775
t_csa::alphabet_category alphabet_category
Definition cst_sada.hpp:96
size_type lb(const node_type v) const
Calculates the index of the leftmost leaf in the corresponding suffix array.
Definition cst_sada.hpp:568
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.
Definition cst_sada.hpp:336
const_iterator begin() const
Returns a const_iterator to the first element.
Definition cst_sada.hpp:295
node_type leftmost_leaf(const node_type v) const
Calculates the leftmost leaf in the subtree rooted at node v.
Definition cst_sada.hpp:543
size_type size() const
Number of leaves in the suffix tree.
Definition cst_sada.hpp:268
t_csa::alphabet_type::comp_char_type comp_char_type
Definition cst_sada.hpp:93
size_type degree(node_type v) const
Get the number of children of a node v.
Definition cst_sada.hpp:958
bool operator==(cst_sada const &other) const noexcept
Equality operator.
Definition cst_sada.hpp:377
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 serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition cst_sada.hpp:394
select_10_type const & bp_select_10
Definition cst_sada.hpp:121
size_type size(node_type v) const
Calculate the number of leaves in the subtree rooted at node v.
Definition cst_sada.hpp:531
node_type wl(node_type v, const char_type c) const
Compute the Weiner link of node v and character c.
Definition cst_sada.hpp:826
size_type rb(const node_type v) const
Calculates the index of the rightmost leaf in the corresponding suffix array.
Definition cst_sada.hpp:581
t_lcp::template type< cst_sada > lcp_type
Definition cst_sada.hpp:85
cst_sada & operator=(cst_sada &&cst)
Move assignment Operator.
Definition cst_sada.hpp:359
static size_type max_size()
Returns the maximal lenght of text for that a suffix tree can be build.
Definition cst_sada.hpp:277
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...
Definition cst_sada.hpp:320
void load(std::istream &in)
Load from a stream.
Definition cst_sada.hpp:411
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].
Definition cst_sada.hpp:946
size_type node_depth(node_type v) const
Returns the node depth of node v.
Definition cst_sada.hpp:517
bool empty() const
Returns if the data strucutre is empty.
Definition cst_sada.hpp:286
bit_vector const & bp
Definition cst_sada.hpp:118
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition cst_sada.hpp:433
t_bp_support bp_support_type
Definition cst_sada.hpp:89
size_type nodes() const
Get the number of nodes of the suffix tree.
Definition cst_sada.hpp:936
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition cst_sada.hpp:422
cst_tag index_category
Definition cst_sada.hpp:97
bp_support_type const & bp_support
Definition cst_sada.hpp:119
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.
Definition cst_sada.hpp:714
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.
Definition cst_sada.hpp:752
node_type select_child(node_type v, size_type i) const
Get the i-th child of a node v.
Definition cst_sada.hpp:691
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.
Definition cst_sada.hpp:642
const_bottom_up_iterator begin_bottom_up() const
Returns an iterator to the first element of a bottom-up traversal of the tree.
Definition cst_sada.hpp:328
node_type sl(node_type v, size_type i) const
Compute the suffix link of node v applied a number of times consecutively.
Definition cst_sada.hpp:800
cst_sada(cst_sada const &cst)
Copy constructor.
Definition cst_sada.hpp:127
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition cst_sada.hpp:314
cst_sada & operator=(cst_sada const &cst)
Assignment Operator.
Definition cst_sada.hpp:345
t_csa::string_type string_type
Definition cst_sada.hpp:87
node_type root() const
Return the root of the suffix tree.
Definition cst_sada.hpp:455
t_csa::size_type size_type
Definition cst_sada.hpp:82
cst_dfs_const_forward_iterator< cst_sada > const_iterator
Definition cst_sada.hpp:80
cst_node_child_proxy< cst_sada > children(node_type v) const
Return a proxy object which allows iterating over the children of a node.
Definition cst_sada.hpp:610
size_type inv_id(size_type id)
Computes the node for such that id(v)=id.
Definition cst_sada.hpp:893
size_type depth(node_type v) const
Returns the depth of node v.
Definition cst_sada.hpp:496
node_type parent(node_type v) const
Calculate the parent node of a node v.
Definition cst_sada.hpp:593
t_csa::alphabet_type::sigma_type sigma_type
Definition cst_sada.hpp:94
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.
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
constexpr char KEY_CSA[]
Definition config.hpp:37
constexpr char KEY_LCP[]
Definition config.hpp:43
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.
Definition io.hpp:688
void copy_lcp(t_lcp &lcp, t_lcp const &lcp_c, t_cst const &cst)
Definition lcp.hpp:73
void move_lcp(t_lcp &&lcp, t_lcp &&lcp_c, t_cst const &cst)
Definition lcp.hpp:108
bool load_from_cache(T &v, std::string const &key, cache_config const &config, bool add_type_hash=false)
Definition io.hpp:772
void load_lcp(t_lcp &lcp, std::istream &in, t_cst const &cst)
Definition lcp.hpp:143
void set_lcp_pointer(t_lcp &lcp, t_cst const &cst)
Definition lcp.hpp:175
void construct_lcp(t_lcp &lcp, t_cst const &cst, cache_config &config)
Definition lcp.hpp:41
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.
Definition config.hpp:66
std::string id
Definition config.hpp:71
std::string dir
Definition config.hpp:70
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.