SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
cst_sct3.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_SCT3
9#define INCLUDED_SDSL_CST_SCT3
10
11#include <cassert>
12#include <iostream>
13#include <stddef.h>
14#include <stdint.h>
15#include <string>
16
17#include <sdsl/bits.hpp>
19#include <sdsl/cereal.hpp>
20#include <sdsl/config.hpp>
21#include <sdsl/csa_wt.hpp>
23#include <sdsl/int_vector.hpp>
25#include <sdsl/io.hpp>
26#include <sdsl/lcp.hpp>
27#include <sdsl/lcp_dac.hpp>
34#include <sdsl/util.hpp>
35
36namespace sdsl
37{
38
39// Declaration of the CST's node type
40template <class t_int = int_vector<>::size_type>
41struct bp_interval;
42
44
77template <class t_csa = csa_wt<>,
78 class t_lcp = lcp_dac<>,
79 class t_bp_support = bp_support_sada<>,
80 class t_bv = bit_vector,
81 class t_rank = typename std::
82 conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type,
83 class t_sel = typename std::conditional<
84 std::is_same<t_bv, bit_vector>::value
85 and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value,
86 select_support_scan<>,
87 typename t_bv::select_1_type>::type>
89{
90 static_assert(std::is_same<typename index_tag<t_csa>::type, csa_tag>::value,
91 "First template argument has to be a compressed suffix array.");
92
93public:
96 typedef typename t_csa::size_type size_type;
97 typedef ptrdiff_t difference_type;
98 typedef t_csa csa_type;
99 typedef typename t_lcp::template type<cst_sct3> lcp_type;
100 typedef t_bp_support bp_support_type;
101 typedef typename t_csa::char_type char_type;
102 typedef typename t_csa::string_type string_type;
104 typedef t_bv bv_type;
105 typedef t_rank rank_type;
106 typedef t_sel sel_type;
107
108 typedef typename t_csa::alphabet_type::comp_char_type comp_char_type;
109 typedef typename t_csa::alphabet_type::sigma_type sigma_type;
110
111 typedef typename t_csa::alphabet_category alphabet_category;
113
114private:
115 csa_type m_csa;
116 lcp_type m_lcp;
117 bit_vector m_bp;
118 bp_support_type m_bp_support;
119 bv_type m_first_child;
120 rank_type m_first_child_rank;
121 sel_type m_first_child_select;
122 size_type m_nodes;
123
124 // Get the first l index of a [i,j] interval.
125 /* I.e. given an interval [i,j], the function returns the position of
126 * the smallest entry lcp[k] with \f$ i<k\leq j \f$
127 * \par Time complexity
128 * \f$ \Order{1} \f$
129 */
130 inline size_type first_l_index(node_type const & node, size_type & kpos, size_type & ckpos) const
131 {
132 if (node.cipos > node.jp1pos)
133 { // corresponds to m_lcp[i] <= m_lcp[j+1]
134 ckpos = node.jp1pos - 1;
135 }
136 else
137 { // corresponds to m_lcp[i] > m_lcp[j+1]
138 ckpos = node.cipos - 1;
139 }
140 assert(m_bp[ckpos] == 0);
141 kpos = m_bp_support.find_open(ckpos);
142 return m_bp_support.rank(kpos) - 1;
143 }
144
145 // Get the i-th l-index of a node
146 // if there exists no ith l-index return node.j+1
147 /* \param v Node
148 * \param i l-index in [1..degree()]
149 * \paran
150 */
151 size_type select_l_index(node_type const & v, size_type i, size_type & kpos, size_type & ckpos) const
152 {
153 assert(i > 0);
154 if (v.cipos > v.jp1pos)
155 { // corresponds to m_lcp[i] <= m_lcp[j+1]
156 ckpos = v.jp1pos - 1;
157 }
158 else
159 { // corresponds to m_lcp[i] > m_lcp[j+1]
160 ckpos = v.cipos - 1;
161 }
162 assert(m_bp[ckpos] == 0); // at least the first l-index should be present, i.e. node is not leaf
163 if (1 == i)
164 {
165 kpos = m_bp_support.find_open(ckpos);
166 return m_bp_support.rank(kpos) - 1;
167 }
168 else
169 { // i > 1
170 // numbers of closing parentheses - 1 = index of first child in m_first_child
171 size_type r = ckpos - m_bp_support.rank(ckpos);
172 if (r + 1 >= i)
173 { // if there exist more than i l-indices
174 // check if m_first_child[r-i+1..r-1] consists of zeros
175 if (i < degree(v))
176 { // there exists an i-th l-index
177 ckpos -= (i - 1);
178 assert(m_bp[ckpos] == 0);
179 kpos = m_bp_support.find_open(ckpos);
180 return m_bp_support.rank(kpos) - 1;
181 }
182 }
183 // if i >= degree(node)
184 kpos = v.jp1pos;
185 if (kpos < m_bp.size())
186 ckpos = m_bp_support.find_close(kpos);
187 else
188 ckpos = m_bp.size();
189 return v.j + 1;
190 }
191 }
192
193 // Position of the first l-index of a l-[i,j] interval in the BP.
194 /* \par Time complexity
195 * \f$ \Order{1} \f$
196 */
197 inline size_type closing_pos_of_first_l_index(node_type const & node) const
198 {
199 if (node.cipos > node.jp1pos)
200 { // corresponds to m_lcp[i] <= m_lcp[j+1]
201 return node.jp1pos - 1;
202 }
203 else
204 { // corresponds to m_lcp[i] > m_lcp[j+1]
205 return node.cipos - 1;
206 }
207 }
208
209 // Get the next smaller value.
210 /*
211 * \param i Position in the original vector.
212 * \param ipos Position of the corresponding opening parenthesis in BP.
213 * \return Position of the next smaller value in [i+1..n-1], and n when
214 * no such value exists.
215 * \par Time complexity
216 * \f$ \Order{1} \f$
217 */
218 // possible optimization: calculate also position of nsv,
219 // i.e. next ( following position cipos
220 inline size_type nsv(SDSL_UNUSED size_type i, size_type ipos) const
221 {
222 size_type cipos = m_bp_support.find_close(ipos);
223 size_type result = m_bp_support.rank(cipos);
224 return result;
225 }
226
227 // Get the previous smaller value.
228 /*
229 * \param i Position in the original vector.
230 * \param ipos Corresponding opening parenthesis in m_bp
231 * \param cipos Corresponding closing parenthesis to ipos
232 * \par Time complexity
233 * \f$ \Order{\frac{\sigma}{w}} \f$, where w=64 is the word size,
234 * can be implemented in \f$\Order{1}\f$ with rank and select.
235 */
236 inline size_type
237 psv(SDSL_UNUSED size_type i, size_type ipos, size_type cipos, size_type & psvpos, size_type & psvcpos) const
238 {
239 // if lcp[i]==0 => psv is the 0-th index by definition
240 if ((cipos + (size_type)m_csa.sigma) >= m_bp.size())
241 {
242 psvpos = 0;
243 psvcpos = m_bp.size() - 1;
244 return 0;
245 }
246 if (m_bp[cipos + 1])
247 {
248 psvpos = m_bp_support.enclose(ipos);
249 psvcpos = m_bp_support.find_close(psvpos);
250 return m_bp_support.rank(psvpos) - 1;
251 }
252 // r0 = index of clothing parenthesis in m_first_child
253 size_type r0 = cipos - m_bp_support.rank(cipos);
254 size_type next_first_child = 0;
255 uint64_t const * p = m_first_child.data() + (r0 >> 6);
256 uint64_t w = (*p) >> (r0 & 0x3F);
257 if (w)
258 { // if w!=0
259 next_first_child = cipos + bits::lo(w);
260 if (cipos == next_first_child and m_bp[next_first_child + 1])
261 {
262 psvpos = m_bp_support.enclose(ipos);
263 psvcpos = m_bp_support.find_close(psvpos);
264 return m_bp_support.rank(psvpos) - 1;
265 }
266 }
267 else
268 {
269 size_type delta = 63 - (r0 & 0x3F);
270 ++p;
271 int steps = 4;
272 while (!(w = *p) and steps-- > 0)
273 { // while w==0
274 ++p;
275 delta += 64;
276 }
277 if (w != 0)
278 {
279 delta += bits::lo(w) + 1;
280 }
281 else
282 {
283 auto pos = m_first_child_select(m_first_child_rank(r0 + 1) + 1);
284 delta = pos - r0;
285 }
286 next_first_child = cipos + delta;
287 }
288 if (!m_bp[next_first_child + 1])
289 { // if next parenthesis is a closing one
290 psvcpos = next_first_child + 1;
291 psvpos = m_bp_support.find_open(psvcpos);
292 return m_bp_support.rank(psvpos) - 1;
293 }
294 else
295 {
296 psvpos = m_bp_support.enclose(m_bp_support.find_open(next_first_child));
297 psvcpos = m_bp_support.find_close(psvpos);
298 return m_bp_support.rank(psvpos) - 1;
299 }
300 }
301
302 // Range minimum query based on the rr_enclose method.
303 /* \par Time complexity
304 * \f$ \Order{\rrenclose} \f$
305 */
306 inline size_type rmq(size_type l, size_type r) const
307 {
308 size_type i = m_bp_support.select(l + 1);
309 size_type j = m_bp_support.select(r + 1);
310 size_type fc_i = m_bp_support.find_close(i);
311 if (j < fc_i)
312 { // i < j < find_close(j) < find_close(i)
313 return l;
314 }
315 else
316 { // i < find_close(i) < j < find_close(j)
317 size_type ec = m_bp_support.rr_enclose(i, j);
318 if (ec == m_bp_support.size())
319 { // no restricted enclosing pair found
320 return r;
321 }
322 else
323 { // found range restricted enclosing pair
324 return m_bp_support.rank(ec) - 1; // subtract 1, as the index is 0 based
325 }
326 }
327 }
328
329public:
330 csa_type const & csa = m_csa;
331 lcp_type const & lcp = m_lcp;
332 bit_vector const & bp = m_bp;
333 bp_support_type const & bp_support = m_bp_support;
334
335 bv_type const & first_child_bv = m_first_child;
336 rank_type const & first_child_rank = m_first_child_rank;
337 sel_type const & first_child_select = m_first_child_select;
338
340 /* @{ */
341
343 cst_sct3() = default;
344
346 cst_sct3(cache_config & cache, bool build_only_bps = false);
347
349
354 cst_sct3(cst_sct3 const & cst) :
355 m_csa(cst.m_csa),
356 m_bp(cst.m_bp),
357 m_bp_support(cst.m_bp_support),
358 m_first_child(cst.m_first_child),
359 m_first_child_rank(cst.m_first_child_rank),
360 m_first_child_select(cst.m_first_child_select),
361 m_nodes(cst.m_nodes)
362 {
363 copy_lcp(m_lcp, cst.m_lcp, *this);
364 m_bp_support.set_vector(&m_bp);
365 m_first_child_rank.set_vector(&m_first_child);
366 m_first_child_select.set_vector(&m_first_child);
367 }
368
370
374 m_csa(std::move(cst.m_csa)),
375 m_bp(std::move(cst.m_bp)),
376 m_bp_support(std::move(cst.m_bp_support)),
377 m_first_child(std::move(cst.m_first_child)),
378 m_first_child_rank(std::move(cst.m_first_child_rank)),
379 m_first_child_select(std::move(cst.m_first_child_select)),
380 m_nodes(cst.m_nodes)
381 {
382 move_lcp(m_lcp, cst.m_lcp, *this);
383 m_bp_support.set_vector(&m_bp);
384 m_first_child_rank.set_vector(&m_first_child);
385 m_first_child_select.set_vector(&m_first_child);
386 }
387
388 /* @} */
389
391
395 {
396 return m_bp.size() >> 1;
397 }
398
400
404 {
405 return t_csa::max_size();
406 }
407
409
412 bool empty() const
413 {
414 return m_csa.empty();
415 }
416
418
422 {
423 if (0 == m_bp.size()) // special case: tree is uninitialized
424 return end();
425 return const_iterator(this, root(), false, true);
426 };
427
430 {
431 if (0 == m_bp.size() and root() == v)
432 return end();
433 return const_iterator(this, v, false, true);
434 }
435
437
441 {
442 return const_iterator(this, root(), true, false);
443 }
444
446 const_iterator end(node_type const & v) const
447 {
448 if (root() == v)
449 return end();
450 return ++const_iterator(this, v, true, true);
451 }
452
455 {
456 if (0 == m_bp.size()) // special case: tree is uninitialized
457 return end_bottom_up();
459 }
460
463 {
464 return const_bottom_up_iterator(this, root(), false);
465 }
466
468
472 {
473 if (this != &cst)
474 {
475 cst_sct3 tmp(cst);
476 *this = std::move(tmp);
477 }
478 return *this;
479 }
480
482
486 {
487 if (this != &cst)
488 {
489 m_csa = std::move(cst.m_csa);
490 move_lcp(m_lcp, cst.m_lcp, *this);
491 m_bp = std::move(cst.m_bp);
492 m_bp_support = std::move(cst.m_bp_support);
493 m_bp_support.set_vector(&m_bp);
494 m_first_child = std::move(cst.m_first_child);
495 m_first_child_rank = std::move(cst.m_first_child_rank);
496 m_first_child_rank.set_vector(&m_first_child);
497 m_first_child_select = std::move(cst.m_first_child_select);
498 m_first_child_select.set_vector(&m_first_child);
499 m_nodes = std::move(cst.m_nodes);
500 }
501 return *this;
502 }
503
505
508 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
509
511
513 void load(std::istream & in);
514
516 template <typename archive_t>
517 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
518
520 template <typename archive_t>
521 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
522
524 bool operator==(cst_sct3 const & other) const noexcept
525 {
526 return (m_csa == other.m_csa) && (m_lcp == other.m_lcp) && (m_bp == other.m_bp)
527 && (m_bp_support == other.m_bp_support) && (m_first_child == other.m_first_child)
528 && (m_first_child_rank == other.m_first_child_rank)
529 && (m_first_child_select == other.m_first_child_select) /*&& (m_nodes == other.m_nodes)*/;
530 }
531
533 bool operator!=(cst_sct3 const & other) const noexcept
534 {
535 return !(*this == other);
536 }
537
539 /* @{ */
540
542
547 {
548 return node_type(0, size() - 1, 0, m_bp.size() - 1, m_bp.size());
549 }
550
552
558 bool is_leaf(node_type const & v) const
559 {
560 return v.i == v.j;
561 }
562
564
572 {
573 assert(i > 0 and i <= size());
574 size_type ipos = m_bp_support.select(i);
575 size_type jp1pos;
576 if (i == size())
577 jp1pos = m_bp.size();
578 else if (m_bp[ipos + 1])
579 jp1pos = ipos + 1;
580 else
581 jp1pos = m_bp_support.select(i + 1);
582 return node_type(i - 1, i - 1, ipos, m_bp_support.find_close(ipos), jp1pos);
583 }
584
586
591 size_type size(node_type const & v) const
592 {
593 return v.j - v.i + 1;
594 }
595
597
603 {
604 return select_leaf(v.i + 1);
605 }
606
608
614 {
615 return select_leaf(v.j + 1);
616 }
617
619
626 size_type lb(node_type const & v) const
627 {
628 return v.i;
629 }
630
632
639 size_type rb(node_type const & v) const
640 {
641 return v.j;
642 }
643
645
650 node_type parent(node_type const & v) const
651 {
652 if (v.cipos > v.jp1pos)
653 { // LCP[i] <= LCP[j+1]
654 size_type psv_pos, psv_cpos, psv_v, nsv_v, nsv_p1pos;
655 psv_v = psv(v.j + 1, v.jp1pos, m_bp_support.find_close(v.jp1pos), psv_pos, psv_cpos);
656 nsv_v = nsv(v.j + 1, v.jp1pos) - 1;
657 if (nsv_v == size() - 1)
658 {
659 nsv_p1pos = m_bp.size();
660 }
661 else
662 { // nsv_v < size()-1
663 nsv_p1pos = m_bp_support.select(nsv_v + 2);
664 }
665 return node_type(psv_v, nsv_v, psv_pos, psv_cpos, nsv_p1pos);
666 }
667 else
668 { // LCP[i] > LCP[j+1]
669 size_type psv_pos, psv_cpos, psv_v;
670 psv_v = psv(v.i, v.ipos, v.cipos, psv_pos, psv_cpos);
671 return node_type(psv_v, v.j, psv_pos, psv_cpos, v.jp1pos);
672 }
673 }
674
676
682 {
683 return cst_node_child_proxy<cst_sct3>(this, v);
684 }
685
687
693 node_type sibling(node_type const & v) const
694 {
695 // Procedure:(1) Determine, if v has a right sibling.
696 if (v.cipos < v.jp1pos)
697 { // LCP[i] > LCP[j+1] => v has the same right border as parent(v) => no right sibling
698 return root();
699 }
700 // (2) There exists a right sibling, LCP[j+1] >= LCP[i] and j>i
701 // Now it holds: v.cipos > v.jp1pos
702 size_type cjp1posm1 = m_bp_support.find_close(v.jp1pos) - 1; // v.cipos-2 ???
703 // m_bp[cjp1posm1] equals 1 => v is the last child
704 bool last_child = m_bp[cjp1posm1];
705 // otherwise if m_bp[cjp1posm1] equals 0 => we don't know if it is the last child
706 if (!last_child)
707 {
708 size_type first_child_idx = cjp1posm1 - m_bp_support.rank(cjp1posm1);
709 last_child = m_first_child[first_child_idx]; // if first_child indicator is true => the new sibling is the
710 // rightmost sibling
711 }
712 if (last_child)
713 {
714 size_type nsv_v = nsv(v.j + 1, v.jp1pos) - 1, nsv_p1pos;
715 if (nsv_v == size() - 1)
716 {
717 nsv_p1pos = m_bp.size();
718 }
719 else
720 {
721 nsv_p1pos = m_bp_support.select(nsv_v + 2);
722 }
723 return node_type(v.j + 1, nsv_v, v.jp1pos, m_bp_support.find_close(v.jp1pos), nsv_p1pos);
724 }
725 else
726 {
727 size_type new_j = m_bp_support.rank(m_bp_support.find_open(cjp1posm1)) - 2;
728 return node_type(v.j + 1,
729 new_j,
730 v.jp1pos,
731 m_bp_support.find_close(v.jp1pos),
732 m_bp_support.select(new_j + 2));
733 }
734 }
735
737
748 {
749 assert(i > 0);
750 if (is_leaf(v)) // if v is a leave, v has no child
751 return root();
752 if (1 == i)
753 {
754 size_type k = 0, kpos = 0, k_find_close = 0;
755 // v is not a leave: v has at least two children
756 k = select_l_index(v, 1, kpos, k_find_close); // get first l-index k and the position of k
757 return node_type(v.i, k - 1, v.ipos, v.cipos, kpos);
758 }
759 else
760 { // i > 1
761 size_type k1, kpos1, k_find_close1;
762 k1 = select_l_index(v, i - 1, kpos1, k_find_close1);
763 if (k1 == v.j + 1)
764 return root();
765 size_type k2, kpos2, k_find_close2;
766 k2 = select_l_index(v, i, kpos2, k_find_close2);
767 return node_type(k1, k2 - 1, kpos1, k_find_close1, kpos2);
768 }
769 }
770
772
779 size_type degree(node_type const & v) const
780 {
781 if (is_leaf(v)) // if v is a leave, v has no child
782 return 0;
783 // v is not a leave: v has at least two children
784 size_type r = closing_pos_of_first_l_index(v);
785 size_type r0 = r - m_bp_support.rank(r);
786 uint64_t const * p = m_first_child.data() + (r0 >> 6);
787 uint8_t offset = r0 & 0x3F;
788
789 uint64_t w = (*p) & bits::lo_set[offset];
790 if (w)
791 { // if there is a bit set in the current word
792 return offset - bits::hi(w) + 1;
793 }
794 else if (m_first_child.data() == p)
795 { // no bit set and we are in the first word
796 return offset + 2; // since would have to be bits::hi(w)=-1, child marked in previous word
797 }
798 else
799 {
800 size_type res = offset + 2;
801 int steps = 4;
802 // search in previous four words for result
803 while (p > m_first_child.data() and steps-- > 0)
804 {
805 w = *(--p);
806 if (0 == w)
807 res += 64;
808 else
809 {
810 return res + (63 - bits::hi(w));
811 }
812 }
813 // if not found: use rank + select to answer query
814 auto goal_rank = m_first_child_rank(r0);
815 if (goal_rank == 0)
816 {
817 return r0 + 2;
818 }
819 else
820 {
821 return r0 - m_first_child_select(goal_rank) + 1;
822 }
823 }
824 }
825
827
837 node_type child(node_type const & v, const char_type c, size_type & char_pos) const
838 {
839 if (is_leaf(v)) // if v is a leaf = (), v has no child
840 return root();
841 // else v = ( ( ))
842 comp_char_type cc = m_csa.char2comp[c];
843 if (cc == 0 and c != 0) // TODO: change char2comp so that we don't need this special case
844 return root();
845 size_type char_ex_max_pos = m_csa.C[((size_type)1) + cc], char_inc_min_pos = m_csa.C[cc];
846
847 size_type d = depth(v);
848
849 // (1) check the first child
850 char_pos = get_char_pos(v.i, d, m_csa);
851 if (char_pos >= char_ex_max_pos)
852 { // the first character of the first child interval is lex. greater than c
853 // => all other first characters of the child intervals are also greater than c => no solution
854 return root();
855 }
856 else if (char_pos >= char_inc_min_pos)
857 { // i.e. char_pos < char_ex_max_pos and char_pos >= char_inc_min_pos
858 return select_child(v, 1);
859 }
860
861 size_type child_cnt = degree(v);
862
863 // (2) check the last child
864 char_pos = get_char_pos(v.j, d, m_csa);
865 if (char_pos < char_inc_min_pos)
866 { // the first character of the last child interval is lex. smaller than c
867 // => all other first characters of the child intervals are also smaller than c => no solution
868 return root();
869 }
870 else if (char_pos < char_ex_max_pos)
871 { // i.e. char_pos < char_ex_max_pos and char_pos >= char_inc_min_pos
872 return select_child(v, child_cnt);
873 }
874
875 // (3) binary search for c in the children [2..children)
876 size_type l_bound = 2, r_bound = child_cnt, mid, kpos, ckpos, l_index;
877 while (l_bound < r_bound)
878 {
879 mid = (l_bound + r_bound) >> 1;
880
881 l_index = select_l_index(v, mid - 1, kpos, ckpos);
882 char_pos = get_char_pos(l_index, d, m_csa);
883
884 if (char_inc_min_pos > char_pos)
885 {
886 l_bound = mid + 1;
887 }
888 else if (char_ex_max_pos <= char_pos)
889 {
890 r_bound = mid;
891 }
892 else
893 { // char_inc_min_pos <= char_pos < char_ex_max_pos => found child
894 // we know that the child is not the last child, see (2)
895 // find next l_index: we know that a new l_index exists: i.e. assert( 0 == m_bp[ckpos-1]);
896 size_type lp1_index = m_bp_support.rank(m_bp_support.find_open(ckpos - 1)) - 1;
897 size_type jp1pos = m_bp.size();
898 if (lp1_index - 1 < size() - 1)
899 {
900 jp1pos = m_bp_support.select(lp1_index + 1);
901 }
902 return node_type(l_index, lp1_index - 1, kpos, ckpos, jp1pos);
903 }
904 }
905 return root();
906 }
907
909 // \sa child(node_type v, const char_type c, size_type &char_pos)
910 node_type child(node_type const & v, const char_type c) const
911 {
912 size_type char_pos;
913 return child(v, c, char_pos);
914 }
915
917
925 char_type edge(node_type const & v, size_type d) const
926 {
927 assert(1 <= d);
928 assert(d <= depth(v));
929 size_type order = get_char_pos(v.i, d - 1, m_csa);
930 size_type c_begin = 1, c_end = ((size_type)m_csa.sigma) + 1, mid;
931 while (c_begin < c_end)
932 {
933 mid = (c_begin + c_end) >> 1;
934 if (m_csa.C[mid] <= order)
935 {
936 c_begin = mid + 1;
937 }
938 else
939 {
940 c_end = mid;
941 }
942 }
943 return m_csa.comp2char[c_begin - 1];
944 }
945
947
956 {
957 if (v.i > w.i or (v.i == w.i and v.j < w.j))
958 {
959 std::swap(v, w);
960 }
961 if (v.j >= w.j)
962 { // v encloses w or v==w
963 return v;
964 }
965 else
966 { // v.i < v.j < w.i < w.j
967 size_type min_index = rmq(v.i + 1, w.j);
968 size_type min_index_pos = m_bp_support.select(min_index + 1);
969 size_type min_index_cpos = m_bp_support.find_close(min_index_pos);
970
971 if (min_index_cpos >= (m_bp.size() - m_csa.sigma))
972 { // if lcp[min_index]==0 => return root
973 return root();
974 }
975 size_type new_j = nsv(min_index, min_index_pos) - 1;
976 size_type new_ipos, new_icpos;
977 size_type new_i = psv(min_index, min_index_pos, min_index_cpos, new_ipos, new_icpos);
978 size_type jp1pos = m_bp.size();
979 if (new_j < size() - 1)
980 {
981 jp1pos = m_bp_support.select(new_j + 2);
982 }
983 return node_type(new_i, new_j, new_ipos, new_icpos, jp1pos);
984 }
985 }
986
988
994 size_type depth(node_type const & v) const
995 {
996 if (v == root())
997 {
998 return 0;
999 }
1000 else if (v.i == v.j)
1001 {
1002 return size() - m_csa[v.i];
1003 }
1004 else
1005 {
1006 size_type kpos, ckpos;
1007 size_type l = select_l_index(v, 1, kpos, ckpos);
1008 return m_lcp[l];
1009 }
1010 }
1011
1013
1025 {
1026 size_type d = 0;
1027 while (v != root())
1028 {
1029 ++d;
1030 v = parent(v);
1031 }
1032 return d;
1033 }
1034
1036
1042 node_type sl(node_type const & v) const
1043 {
1044 if (v == root())
1045 return root();
1046 // get interval with first char deleted
1047 size_type i = m_csa.psi[v.i];
1048 if (is_leaf(v))
1049 {
1050 if (v.i == 0 and v.j == 0) // if( v.l==1 )
1051 return root();
1052 else
1053 return select_leaf(i + 1);
1054 }
1055 size_type j = m_csa.psi[v.j];
1056 assert(i < j);
1057 size_type min_index = rmq(i + 1, j); // rmq
1058 size_type min_index_pos = m_bp_support.select(min_index + 1);
1059 size_type min_index_cpos = m_bp_support.find_close(min_index_pos);
1060 if (min_index_cpos >= (m_bp.size() - m_csa.sigma))
1061 { // if lcp[min_index]==0 => return root
1062 return root();
1063 }
1064 size_type new_j = nsv(min_index, min_index_pos) - 1;
1065 size_type new_ipos, new_icpos;
1066 size_type new_i = psv(min_index, min_index_pos, min_index_cpos, new_ipos, new_icpos);
1067 size_type jp1pos = m_bp.size();
1068 if (new_j < size() - 1)
1069 {
1070 jp1pos = m_bp_support.select(new_j + 2);
1071 }
1072 return node_type(new_i, new_j, new_ipos, new_icpos, jp1pos);
1073 }
1074
1076
1084 node_type wl(node_type const & v, const char_type c) const
1085 {
1086 size_type c_left = m_csa.bwt.rank(v.i, c);
1087 size_type c_right = m_csa.bwt.rank(v.j + 1, c);
1088 if (c_left == c_right) // there exists no Weiner link
1089 return root();
1090 if (c_left + 1 == c_right)
1091 return select_leaf(m_csa.C[m_csa.char2comp[c]] + c_left + 1);
1092 else
1093 {
1094 size_type left = m_csa.C[m_csa.char2comp[c]] + c_left;
1095 size_type right = m_csa.C[m_csa.char2comp[c]] + c_right - 1;
1096 assert(left < right);
1097
1098 size_type ipos = m_bp_support.select(left + 1);
1099 size_type jp1pos = m_bp.size();
1100 if (right < size() - 1)
1101 {
1102 jp1pos = m_bp_support.select(right + 2);
1103 }
1104 return node_type(left, right, ipos, m_bp_support.find_close(ipos), jp1pos);
1105 }
1106 }
1107
1109
1114 size_type sn(node_type const & v) const
1115 {
1116 assert(is_leaf(v));
1117 return m_csa[v.i];
1118 }
1119
1121
1127 size_type id(node_type const & v) const
1128 {
1129 if (is_leaf(v))
1130 { // return id in the range from 0..csa.size()-1
1131 return v.i;
1132 }
1133 size_type ckpos; // closing parentheses of the l-index
1134 if (v.cipos > v.jp1pos)
1135 { // corresponds to m_lcp[i] <= m_lcp[j+1]
1136 ckpos = v.jp1pos - 1;
1137 }
1138 else
1139 { // corresponds to m_lcp[i] > m_lcp[j+1]
1140 ckpos = v.cipos - 1;
1141 }
1142 assert(m_bp[ckpos] == 0);
1143 size_type r0ckpos = ckpos - m_bp_support.rank(ckpos); // determine the rank of the closing parenthesis
1144 return size() + m_first_child_rank(r0ckpos);
1145 }
1146
1148
1156 {
1157 if (id < size())
1158 { // the corresponding node is a leaf
1159 return select_leaf(id + 1);
1160 }
1161 else
1162 { // the corresponding node is a inner node
1163 // (1) get index of the closing parenthesis in m_first_child
1164 size_type r0ckpos = 0;
1165 {
1166 // binary search for the position of the (id-size()+1)-th set bit in
1167 id = id - size() + 1;
1168 size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
1169 // invariant: arg(lb) < id, arg(rb) >= id
1170 while (rb - lb > 1)
1171 {
1172 size_type mid = lb + (rb - lb) / 2;
1173 size_type arg = m_first_child_rank(mid); // ones in the prefix [0..mid-1]
1174 if (arg < id)
1175 {
1176 lb = mid;
1177 }
1178 else
1179 { // arg >= id
1180 rb = mid;
1181 }
1182 }
1183 r0ckpos = lb;
1184 }
1185 // (2) determine position clpos of the r0clpos-th closing parentheses in the parentheses sequence
1186 size_type ckpos = 0;
1187 {
1188 // binary search for the position of the (r0ckpos+1)-th closing parenthesis
1189 size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
1190 // invariant: arg(lb) < r0ckpos+1, arg(rb) >= r0ckpos+1
1191 while (rb - lb > 1)
1192 {
1193 size_type mid = lb + (rb - lb) / 2;
1194 size_type arg = mid - m_bp_support.rank(mid - 1); // zeros in the prefix [0..mid-1]
1195 if (arg < r0ckpos + 1)
1196 {
1197 lb = mid;
1198 }
1199 else
1200 { // arg >= x
1201 rb = mid;
1202 }
1203 }
1204 ckpos = lb;
1205 }
1206 if (ckpos == m_bp.size() - 1)
1207 {
1208 return root();
1209 }
1210 if (m_bp[ckpos + 1])
1211 { // jp1pos < cipos
1212 size_type jp1pos = ckpos + 1;
1213 size_type j = m_bp_support.rank(jp1pos - 1) - 1;
1214 size_type kpos = m_bp_support.find_open(ckpos);
1215 size_type ipos = m_bp_support.enclose(kpos);
1216 size_type cipos = m_bp_support.find_close(ipos);
1217 size_type i = m_bp_support.rank(ipos - 1);
1218 return node_type(i, j, ipos, cipos, jp1pos);
1219 }
1220 else
1221 { //
1222 size_type cipos = ckpos + 1;
1223 size_type ipos = m_bp_support.find_open(cipos);
1224 size_type i = m_bp_support.rank(ipos - 1);
1225 size_type j = nsv(i, ipos) - 1;
1226 size_type jp1pos = m_bp.size();
1227 if (j != size() - 1)
1228 {
1229 jp1pos = m_bp_support.select(j + 2);
1230 }
1231 return node_type(i, j, ipos, cipos, jp1pos);
1232 }
1233 }
1234 }
1235
1238 {
1239 return m_nodes;
1240 }
1241
1243 /* \param lb Left bound of the lcp-interval [lb..rb] (inclusive).
1244 * \param rb Right bound of the lcp-interval [lb..rb] (inclusive).
1245 * \return The node in the suffix tree corresponding lcp-interval [lb..rb]
1246 * \par Time complexity
1247 * \f$ \Order{1} \f$
1248 */
1250 {
1251 size_type ipos = m_bp_support.select(lb + 1);
1252 size_type jp1pos;
1253 if (rb == size() - 1)
1254 {
1255 jp1pos = m_bp.size();
1256 }
1257 else
1258 {
1259 jp1pos = m_bp_support.select(rb + 2);
1260 }
1261 return node_type(lb, rb, ipos, m_bp_support.find_close(ipos), jp1pos);
1262 }
1263
1265
1270 {
1271 size_type ipos = m_bp_support.select(i + 1);
1272 size_type cipos = m_bp_support.find_close(ipos);
1273 return m_first_child_rank.rank(((ipos + cipos - 1) >> 1) - i);
1274 }
1275 /* @} */
1276};
1277
1278// == template functions ==
1279
1280template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1282{
1283 {
1284 auto event = memory_monitor::event("bps-sct");
1286 m_nodes = construct_supercartesian_tree_bp_succinct_and_first_child(lcp_buf, m_bp, m_first_child);
1287 m_nodes += m_bp.size() / 2;
1288 if (m_bp.size() == 2)
1289 { // handle special case, when the tree consists only of the root node
1290 m_nodes = 1;
1291 }
1292 }
1293 {
1294 auto event = memory_monitor::event("bpss-sct");
1295 util::init_support(m_bp_support, &m_bp);
1296 util::init_support(m_first_child_rank, &m_first_child);
1297 util::init_support(m_first_child_select, &m_first_child);
1298 }
1299 if (!build_only_bps)
1300 {
1301 auto event = memory_monitor::event("clcp");
1302 cache_config tmp_config(false, config.dir, config.id, config.file_map);
1303 construct_lcp(m_lcp, *this, tmp_config);
1304 config.file_map = tmp_config.file_map;
1305 }
1306 if (!build_only_bps)
1307 {
1308 auto event = memory_monitor::event("load csa");
1309 load_from_cache(m_csa, std::string(conf::KEY_CSA) + "_" + util::class_to_hash(m_csa), config);
1310 }
1311}
1312
1313template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1316 std::string name) const -> size_type
1317{
1318 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1319 size_type written_bytes = 0;
1320 written_bytes += m_csa.serialize(out, child, "csa");
1321 written_bytes += m_lcp.serialize(out, child, "lcp");
1322 written_bytes += m_bp.serialize(out, child, "bp");
1323 written_bytes += m_bp_support.serialize(out, child, "bp_support");
1324 written_bytes += m_first_child.serialize(out, child, "mark_child");
1325 written_bytes += m_first_child_rank.serialize(out, child, "mark_child_rank");
1326 written_bytes += m_first_child_select.serialize(out, child, "mark_child_select");
1327 written_bytes += write_member(m_nodes, out, child, "node_cnt");
1328 structure_tree::add_size(child, written_bytes);
1329 return written_bytes;
1330}
1331
1332template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1334{
1335 m_csa.load(in);
1336 load_lcp(m_lcp, in, *this);
1337 m_bp.load(in);
1338 m_bp_support.load(in, &m_bp);
1339 m_first_child.load(in);
1340 m_first_child_rank.load(in, &m_first_child);
1341 m_first_child_select.load(in, &m_first_child);
1342 read_member(m_nodes, in);
1343}
1344
1345template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1346template <typename archive_t>
1348{
1349 ar(CEREAL_NVP(m_csa));
1350 ar(CEREAL_NVP(m_lcp));
1351 ar(CEREAL_NVP(m_bp));
1352 ar(CEREAL_NVP(m_bp_support));
1353 ar(CEREAL_NVP(m_first_child));
1354 ar(CEREAL_NVP(m_first_child_rank));
1355 ar(CEREAL_NVP(m_first_child_select));
1356 ar(CEREAL_NVP(m_nodes));
1357}
1358
1359template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1360template <typename archive_t>
1362{
1363 ar(CEREAL_NVP(m_csa));
1364 ar(CEREAL_NVP(m_lcp));
1365 set_lcp_pointer(m_lcp, *this);
1366 ar(CEREAL_NVP(m_bp));
1367 ar(CEREAL_NVP(m_bp_support));
1368 m_bp_support.set_vector(&m_bp);
1369 ar(CEREAL_NVP(m_first_child));
1370 ar(CEREAL_NVP(m_first_child_rank));
1371 m_first_child_rank.set_vector(&m_first_child);
1372 ar(CEREAL_NVP(m_first_child_select));
1373 m_first_child_select.set_vector(&m_first_child);
1374 ar(CEREAL_NVP(m_nodes));
1375}
1376
1377template <class t_int>
1379{
1380 t_int i;
1381 t_int j;
1382 t_int ipos; // position of the i+1th opening parenthesis in the balanced parentheses sequence
1383 t_int cipos; // position of the matching closing parenthesis of the i+1th opening parenthesis in the balanced
1384 // parentheses sequence
1385 t_int jp1pos; // position of the j+2th opening parenthesis in the balanced parentheses sequence
1386
1388 bp_interval(t_int i = 0, t_int j = 0, t_int ipos = 0, t_int cipos = 0, t_int jp1pos = 0) :
1389 i(i),
1390 j(j),
1391 ipos(ipos),
1392 cipos(cipos),
1393 jp1pos(jp1pos){};
1394
1396 bp_interval(bp_interval const & iv) = default;
1398 bp_interval(bp_interval && iv) = default;
1399
1400 bool operator<(bp_interval const & interval) const
1401 {
1402 if (i != interval.i)
1403 return i < interval.i;
1404 return j < interval.j;
1405 }
1406
1408
1410 bool operator==(bp_interval const & interval) const
1411 {
1412 return i == interval.i and j == interval.j;
1413 }
1414
1416
1419 bool operator!=(bp_interval const & interval) const
1420 {
1421 return !(*this == interval);
1422 }
1423
1425 bp_interval & operator=(bp_interval const & interval) = default;
1427 bp_interval & operator=(bp_interval && interval) = default;
1428};
1429
1430template <class t_int>
1431inline std::ostream & operator<<(std::ostream & os, bp_interval<t_int> const & interval)
1432{
1433 os << "-[" << interval.i << "," << interval.j << "](" << interval.ipos << "," << interval.cipos << ","
1434 << interval.jp1pos << ")";
1435 return os;
1436}
1437
1438} // end namespace sdsl
1439#endif
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
#define CEREAL_LOAD_FUNCTION_NAME
Definition cereal.hpp:34
#define CEREAL_SAVE_FUNCTION_NAME
Definition cereal.hpp:35
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 Ohlebusch and Gog.
Definition cst_sct3.hpp:89
t_csa::alphabet_type::sigma_type sigma_type
Definition cst_sct3.hpp:109
bool is_leaf(node_type const &v) const
Decide if a node is a leaf.
Definition cst_sct3.hpp:558
node_type lca(node_type v, node_type w) const
Calculate the LCA of two nodes v and w
Definition cst_sct3.hpp:955
const_iterator begin() const
Returns a const_iterator to the first element of a depth first traversal of the tree.
Definition cst_sct3.hpp:421
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_sct3.hpp:462
node_type child(node_type const &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_sct3.hpp:837
node_type rightmost_leaf(node_type const &v) const
Calculates the rightmost leaf in the subtree rooted at node v.
Definition cst_sct3.hpp:613
t_bp_support bp_support_type
Definition cst_sct3.hpp:100
static size_type max_size()
Returns the largest size that cst_sct3 can ever have.
Definition cst_sct3.hpp:403
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right).
Definition cst_sct3.hpp:571
size_type lb(node_type const &v) const
Calculates the index of the leftmost leaf in the corresponding suffix array.
Definition cst_sct3.hpp:626
node_type root() const
Return the root of the suffix tree.
Definition cst_sct3.hpp:546
node_type inv_id(size_type id)
Computes the node for such that id(v)=id.
size_type node_depth(node_type v) const
Returns the node depth of node v.
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_sct3.hpp:454
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
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].
size_type nodes() const
Get the number of nodes of the suffix tree.
size_type size(node_type const &v) const
Calculate the number of leaves in the subtree rooted at node v.
Definition cst_sct3.hpp:591
cst_bottom_up_const_forward_iterator< cst_sct3 > const_bottom_up_iterator
Definition cst_sct3.hpp:95
node_type parent(node_type const &v) const
Calculate the parent node of a node v.
Definition cst_sct3.hpp:650
t_csa::string_type string_type
Definition cst_sct3.hpp:102
bv_type const & first_child_bv
Definition cst_sct3.hpp:335
sel_type const & first_child_select
Definition cst_sct3.hpp:337
rank_type const & first_child_rank
Definition cst_sct3.hpp:336
node_type leftmost_leaf(node_type const &v) const
Calculates the leftmost leaf in the subtree rooted at node v.
Definition cst_sct3.hpp:602
bool empty() const
Returns if the data structure is empty.
Definition cst_sct3.hpp:412
cst_sct3(cst_sct3 &&cst)
Move constructor.
Definition cst_sct3.hpp:373
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
node_type sibling(node_type const &v) const
Returns the next sibling of node v.
Definition cst_sct3.hpp:693
t_csa::char_type char_type
Definition cst_sct3.hpp:101
bool operator==(cst_sct3 const &other) const noexcept
Equality operator.
Definition cst_sct3.hpp:524
bool operator!=(cst_sct3 const &other) const noexcept
Inequality operator.
Definition cst_sct3.hpp:533
size_type size() const
Number of leaves of the suffix tree.
Definition cst_sct3.hpp:394
cst_tag index_category
Definition cst_sct3.hpp:112
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_sct3.hpp:446
node_type select_child(node_type const &v, size_type i) const
Get the i-th child of a node v.
Definition cst_sct3.hpp:747
csa_type const & csa
Definition cst_sct3.hpp:330
lcp_type const & lcp
Definition cst_sct3.hpp:331
size_type sn(node_type const &v) const
Computes the suffix number of a leaf node v.
cst_sct3 & operator=(cst_sct3 const &cst)
Assignment Operator.
Definition cst_sct3.hpp:471
cst_sct3(cst_sct3 const &cst)
Copy constructor.
Definition cst_sct3.hpp:354
node_type wl(node_type const &v, const char_type c) const
Compute the Weiner link of node v and character c.
node_type sl(node_type const &v) const
Compute the suffix link of node v.
bit_vector const & bp
Definition cst_sct3.hpp:332
const_iterator end() const
Returns a const_iterator to the element after the last element of a depth first traversal of the tree...
Definition cst_sct3.hpp:440
cst_dfs_const_forward_iterator< cst_sct3 > const_iterator
Definition cst_sct3.hpp:94
size_type id(node_type const &v) const
Computes a unique identification number for a node of the suffx tree in the range [0....
node_type child(node_type const &v, const char_type c) const
Get the child w of node v which edge label (v,w) starts with character c.
Definition cst_sct3.hpp:910
t_csa::size_type size_type
Definition cst_sct3.hpp:96
bp_interval< size_type > node_type
Type for the nodes in the tree.
Definition cst_sct3.hpp:103
size_type depth(node_type const &v) const
Returns the string depth of node v.
Definition cst_sct3.hpp:994
size_type rb(node_type const &v) const
Calculates the index of the rightmost leaf in the corresponding suffix array.
Definition cst_sct3.hpp:639
cst_sct3 & operator=(cst_sct3 &&cst)
Assignment Move Operator.
Definition cst_sct3.hpp:485
t_lcp::template type< cst_sct3 > lcp_type
Definition cst_sct3.hpp:99
ptrdiff_t difference_type
Definition cst_sct3.hpp:97
bp_support_type const & bp_support
Definition cst_sct3.hpp:333
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_sct3.hpp:429
t_csa::alphabet_category alphabet_category
Definition cst_sct3.hpp:111
t_csa::alphabet_type::comp_char_type comp_char_type
Definition cst_sct3.hpp:108
void load(std::istream &in)
Load from a stream.
size_type degree(node_type const &v) const
Get the number of children of a node v.
Definition cst_sct3.hpp:779
size_type tlcp_idx(size_type i) const
Maps an index i to the position in TLCP where LCP[i] can be found.
cst_sct3()=default
Default constructor.
char_type edge(node_type const &v, size_type d) const
Returns the d-th character (1-based indexing) of the edge-label pointing to v.
Definition cst_sct3.hpp:925
cst_node_child_proxy< cst_sct3 > children(node_type const &v) const
Return a proxy object which allows iterating over the children of a node.
Definition cst_sct3.hpp:681
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.
static mm_event_proxy event(std::string const &name)
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)
#define SDSL_UNUSED
Definition config.hpp:12
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.
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_dac.hpp contains an implementation of 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.
std::ostream & operator<<(std::ostream &os, bp_interval< t_int > const &interval)
t_csa::size_type get_char_pos(typename t_csa::size_type idx, typename t_csa::size_type d, t_csa const &csa)
bit_vector::size_type construct_supercartesian_tree_bp_succinct_and_first_child(int_vector_buffer< t_width > &lcp_buf, bit_vector &bp, bit_vector &bp_fc, bool const minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
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
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
void move_lcp(t_lcp &&lcp, t_lcp &&lcp_c, t_cst const &cst)
Definition lcp.hpp:108
void read_member(T &t, std::istream &in)
Definition io.hpp:119
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_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition bits.hpp:689
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition bits.hpp:194
bp_interval & operator=(bp_interval const &interval)=default
Assignment operator.
bp_interval(bp_interval const &iv)=default
Copy constructor.
t_int i
The left border of the lcp-interval .
bp_interval & operator=(bp_interval &&interval)=default
Move assignment.
bp_interval(t_int i=0, t_int j=0, t_int ipos=0, t_int cipos=0, t_int jp1pos=0)
Constructor.
bool operator<(bp_interval const &interval) const
t_int j
The right border of the lcp-interval .
bool operator!=(bp_interval const &interval) const
Inequality operator.
bool operator==(bp_interval const &interval) const
Equality operator.
bp_interval(bp_interval &&iv)=default
Move copy constructor.
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.