SDSL 3.0.1
Succinct Data Structure Library
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 <algorithm>
12#include <cassert>
13#include <cstring> // for strlen
14#include <iomanip>
15#include <iostream>
16#include <iterator>
17#include <ostream>
18#include <stack> // for the calculation of the balanced parentheses sequence
19#include <type_traits>
20
21#include <sdsl/bp_support.hpp>
22#include <sdsl/construct.hpp>
23#include <sdsl/csa_wt.hpp> // for std initialization of cst_sct3
25#include <sdsl/int_vector.hpp>
26#include <sdsl/iterators.hpp>
27#include <sdsl/lcp.hpp>
28#include <sdsl/rank_support.hpp>
33#include <sdsl/util.hpp>
34
35namespace sdsl
36{
37
38// Declaration of the CST's node type
40struct bp_interval;
41
43
76template <class t_csa = csa_wt<>,
77 class t_lcp = lcp_dac<>,
78 class t_bp_support = bp_support_sada<>,
79 class t_bv = bit_vector,
80 class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value,
81 rank_support_v5<>,
82 typename t_bv::rank_1_type>::type,
83 class
84 t_sel = typename std::conditional<std::is_same<t_bv,
85 bit_vector>::value and std::is_same<typename t_csa::alphabet_category,
86 byte_alphabet_tag>::value,
87 select_support_scan<>,
88 typename t_bv::select_1_type>::type>
90{
91 static_assert(std::is_same<typename index_tag<t_csa>::type, csa_tag>::value,
92 "First template argument has to be a compressed suffix array.");
93
94 public:
97 typedef typename t_csa::size_type size_type;
98 typedef ptrdiff_t difference_type;
99 typedef t_csa csa_type;
100 typedef typename t_lcp::template type<cst_sct3> lcp_type;
101 typedef t_bp_support bp_support_type;
102 typedef typename t_csa::char_type char_type;
103 typedef typename t_csa::string_type string_type;
105 typedef t_bv bv_type;
106 typedef t_rank rank_type;
107 typedef t_sel sel_type;
108
109 typedef typename t_csa::alphabet_type::comp_char_type comp_char_type;
110 typedef typename t_csa::alphabet_type::sigma_type sigma_type;
111
112 typedef typename t_csa::alphabet_category alphabet_category;
114
115 private:
116 csa_type m_csa;
117 lcp_type m_lcp;
118 bit_vector m_bp;
119 bp_support_type m_bp_support;
120 bv_type m_first_child;
121 rank_type m_first_child_rank;
122 sel_type m_first_child_select;
123 size_type m_nodes;
124
125 // Get the first l index of a [i,j] interval.
126 /* I.e. given an interval [i,j], the function returns the position of
127 * the smallest entry lcp[k] with \f$ i<k\leq j \f$
128 * \par Time complexity
129 * \f$ \Order{1} \f$
130 */
131 inline size_type first_l_index(const node_type & node, size_type & kpos, size_type & ckpos) const
132 {
133 if (node.cipos > node.jp1pos)
134 { // corresponds to m_lcp[i] <= m_lcp[j+1]
135 ckpos = node.jp1pos - 1;
136 }
137 else
138 { // corresponds to m_lcp[i] > m_lcp[j+1]
139 ckpos = node.cipos - 1;
140 }
141 assert(m_bp[ckpos] == 0);
142 kpos = m_bp_support.find_open(ckpos);
143 return m_bp_support.rank(kpos) - 1;
144 }
145
146 // Get the i-th l-index of a node
147 // if there exists no ith l-index return node.j+1
148 /* \param v Node
149 * \param i l-index in [1..degree()]
150 * \paran
151 */
152 size_type select_l_index(const node_type & v, size_type i, size_type & kpos, size_type & ckpos) const
153 {
154 assert(i > 0);
155 if (v.cipos > v.jp1pos)
156 { // corresponds to m_lcp[i] <= m_lcp[j+1]
157 ckpos = v.jp1pos - 1;
158 }
159 else
160 { // corresponds to m_lcp[i] > m_lcp[j+1]
161 ckpos = v.cipos - 1;
162 }
163 assert(m_bp[ckpos] == 0); // at least the first l-index should be present, i.e. node is not leaf
164 if (1 == i)
165 {
166 kpos = m_bp_support.find_open(ckpos);
167 return m_bp_support.rank(kpos) - 1;
168 }
169 else
170 { // i > 1
171 // numbers of closing parentheses - 1 = index of first child in m_first_child
172 size_type r = ckpos - m_bp_support.rank(ckpos);
173 if (r + 1 >= i)
174 { // if there exist more than i l-indices
175 // check if m_first_child[r-i+1..r-1] consists of zeros
176 if (i < degree(v))
177 { // there exists an i-th l-index
178 ckpos -= (i - 1);
179 assert(m_bp[ckpos] == 0);
180 kpos = m_bp_support.find_open(ckpos);
181 return m_bp_support.rank(kpos) - 1;
182 }
183 }
184 // if i >= degree(node)
185 kpos = v.jp1pos;
186 if (kpos < m_bp.size())
187 ckpos = m_bp_support.find_close(kpos);
188 else
189 ckpos = m_bp.size();
190 return v.j + 1;
191 }
192 }
193
194 // Position of the first l-index of a l-[i,j] interval in the BP.
195 /* \par Time complexity
196 * \f$ \Order{1} \f$
197 */
198 inline size_type closing_pos_of_first_l_index(const node_type & node) const
199 {
200 if (node.cipos > node.jp1pos)
201 { // corresponds to m_lcp[i] <= m_lcp[j+1]
202 return node.jp1pos - 1;
203 }
204 else
205 { // corresponds to m_lcp[i] > m_lcp[j+1]
206 return node.cipos - 1;
207 }
208 }
209
210 // Get the next smaller value.
211 /*
212 * \param i Position in the original vector.
213 * \param ipos Position of the corresponding opening parenthesis in BP.
214 * \return Position of the next smaller value in [i+1..n-1], and n when
215 * no such value exists.
216 * \par Time complexity
217 * \f$ \Order{1} \f$
218 */
219 // possible optimization: calculate also position of nsv,
220 // i.e. next ( following position cipos
221 inline size_type nsv(SDSL_UNUSED size_type i, size_type ipos) const
222 {
223 size_type cipos = m_bp_support.find_close(ipos);
224 size_type result = m_bp_support.rank(cipos);
225 return result;
226 }
227
228 // Get the previous smaller value.
229 /*
230 * \param i Position in the original vector.
231 * \param ipos Corresponding opening parenthesis in m_bp
232 * \param cipos Corresponding closing parenthesis to ipos
233 * \par Time complexity
234 * \f$ \Order{\frac{\sigma}{w}} \f$, where w=64 is the word size,
235 * can be implemented in \f$\Order{1}\f$ with rank and select.
236 */
237 inline size_type psv(SDSL_UNUSED size_type i,
238 size_type ipos,
239 size_type cipos,
240 size_type & psvpos,
241 size_type & psvcpos) const
242 {
243 // if lcp[i]==0 => psv is the 0-th index by definition
244 if ((cipos + (size_type)m_csa.sigma) >= m_bp.size())
245 {
246 psvpos = 0;
247 psvcpos = m_bp.size() - 1;
248 return 0;
249 }
250 if (m_bp[cipos + 1])
251 {
252 psvpos = m_bp_support.enclose(ipos);
253 psvcpos = m_bp_support.find_close(psvpos);
254 return m_bp_support.rank(psvpos) - 1;
255 }
256 // r0 = index of clothing parenthesis in m_first_child
257 size_type r0 = cipos - m_bp_support.rank(cipos);
258 size_type next_first_child = 0;
259 const uint64_t * p = m_first_child.data() + (r0 >> 6);
260 uint64_t w = (*p) >> (r0 & 0x3F);
261 if (w)
262 { // if w!=0
263 next_first_child = cipos + bits::lo(w);
264 if (cipos == next_first_child and m_bp[next_first_child + 1])
265 {
266 psvpos = m_bp_support.enclose(ipos);
267 psvcpos = m_bp_support.find_close(psvpos);
268 return m_bp_support.rank(psvpos) - 1;
269 }
270 }
271 else
272 {
273 size_type delta = 63 - (r0 & 0x3F);
274 ++p;
275 int steps = 4;
276 while (!(w = *p) and steps-- > 0)
277 { // while w==0
278 ++p;
279 delta += 64;
280 }
281 if (w != 0) { delta += bits::lo(w) + 1; }
282 else
283 {
284 auto pos = m_first_child_select(m_first_child_rank(r0 + 1) + 1);
285 delta = pos - r0;
286 }
287 next_first_child = cipos + delta;
288 }
289 if (!m_bp[next_first_child + 1])
290 { // if next parenthesis is a closing one
291 psvcpos = next_first_child + 1;
292 psvpos = m_bp_support.find_open(psvcpos);
293 return m_bp_support.rank(psvpos) - 1;
294 }
295 else
296 {
297 psvpos = m_bp_support.enclose(m_bp_support.find_open(next_first_child));
298 psvcpos = m_bp_support.find_close(psvpos);
299 return m_bp_support.rank(psvpos) - 1;
300 }
301 }
302
303 // Range minimum query based on the rr_enclose method.
304 /* \par Time complexity
305 * \f$ \Order{\rrenclose} \f$
306 */
307 inline size_type rmq(size_type l, size_type r) const
308 {
309 size_type i = m_bp_support.select(l + 1);
310 size_type j = m_bp_support.select(r + 1);
311 size_type fc_i = m_bp_support.find_close(i);
312 if (j < fc_i)
313 { // i < j < find_close(j) < find_close(i)
314 return l;
315 }
316 else
317 { // i < find_close(i) < j < find_close(j)
318 size_type ec = m_bp_support.rr_enclose(i, j);
319 if (ec == m_bp_support.size())
320 { // no restricted enclosing pair found
321 return r;
322 }
323 else
324 { // found range restricted enclosing pair
325 return m_bp_support.rank(ec) - 1; // subtract 1, as the index is 0 based
326 }
327 }
328 }
329
330 public:
331 const csa_type & csa = m_csa;
332 const lcp_type & lcp = m_lcp;
333 const bit_vector & bp = m_bp;
334 const bp_support_type & bp_support = m_bp_support;
335
336 const bv_type & first_child_bv = m_first_child;
337 const rank_type & first_child_rank = m_first_child_rank;
338 const sel_type & first_child_select = m_first_child_select;
339
341 /* @{ */
342
344 cst_sct3() = default;
345
347 cst_sct3(cache_config & cache, bool build_only_bps = false);
348
350
355 cst_sct3(const cst_sct3 & cst)
356 : m_csa(cst.m_csa)
357 , m_bp(cst.m_bp)
358 , m_bp_support(cst.m_bp_support)
359 , m_first_child(cst.m_first_child)
360 , m_first_child_rank(cst.m_first_child_rank)
361 , m_first_child_select(cst.m_first_child_select)
362 , m_nodes(cst.m_nodes)
363 {
364 copy_lcp(m_lcp, cst.m_lcp, *this);
365 m_bp_support.set_vector(&m_bp);
366 m_first_child_rank.set_vector(&m_first_child);
367 m_first_child_select.set_vector(&m_first_child);
368 }
369
371
375 : m_csa(std::move(cst.m_csa))
376 , m_bp(std::move(cst.m_bp))
377 , m_bp_support(std::move(cst.m_bp_support))
378 , m_first_child(std::move(cst.m_first_child))
379 , m_first_child_rank(std::move(cst.m_first_child_rank))
380 , m_first_child_select(std::move(cst.m_first_child_select))
381 , m_nodes(cst.m_nodes)
382 {
383 move_lcp(m_lcp, cst.m_lcp, *this);
384 m_bp_support.set_vector(&m_bp);
385 m_first_child_rank.set_vector(&m_first_child);
386 m_first_child_select.set_vector(&m_first_child);
387 }
388
389 /* @} */
390
392
395 size_type size() const { return m_bp.size() >> 1; }
396
398
401 static size_type max_size() { return t_csa::max_size(); }
402
404
407 bool empty() const { return m_csa.empty(); }
408
410
414 {
415 if (0 == m_bp.size()) // special case: tree is uninitialized
416 return end();
417 return const_iterator(this, root(), false, true);
418 };
419
422 {
423 if (0 == m_bp.size() and root() == v) return end();
424 return const_iterator(this, v, false, true);
425 }
426
428
431 const_iterator end() const { return const_iterator(this, root(), true, false); }
432
434 const_iterator end(const node_type & v) const
435 {
436 if (root() == v) return end();
437 return ++const_iterator(this, v, true, true);
438 }
439
442 {
443 if (0 == m_bp.size()) // special case: tree is uninitialized
444 return end_bottom_up();
446 }
447
450
452
456 {
457 if (this != &cst)
458 {
459 cst_sct3 tmp(cst);
460 *this = std::move(tmp);
461 }
462 return *this;
463 }
464
466
470 {
471 if (this != &cst)
472 {
473 m_csa = std::move(cst.m_csa);
474 move_lcp(m_lcp, cst.m_lcp, *this);
475 m_bp = std::move(cst.m_bp);
476 m_bp_support = std::move(cst.m_bp_support);
477 m_bp_support.set_vector(&m_bp);
478 m_first_child = std::move(cst.m_first_child);
479 m_first_child_rank = std::move(cst.m_first_child_rank);
480 m_first_child_rank.set_vector(&m_first_child);
481 m_first_child_select = std::move(cst.m_first_child_select);
482 m_first_child_select.set_vector(&m_first_child);
483 m_nodes = std::move(cst.m_nodes);
484 }
485 return *this;
486 }
487
489
492 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
493
495
497 void load(std::istream & in);
498
500 template <typename archive_t>
501 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
502
504 template <typename archive_t>
505 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
506
508 bool operator==(cst_sct3 const & other) const noexcept
509 {
510 return (m_csa == other.m_csa) && (m_lcp == other.m_lcp) && (m_bp == other.m_bp) &&
511 (m_bp_support == other.m_bp_support) && (m_first_child == other.m_first_child) &&
512 (m_first_child_rank == other.m_first_child_rank) &&
513 (m_first_child_select == other.m_first_child_select) /*&& (m_nodes == other.m_nodes)*/;
514 }
515
517 bool operator!=(cst_sct3 const & other) const noexcept { return !(*this == other); }
518
520 /* @{ */
521
523
527 node_type root() const { return node_type(0, size() - 1, 0, m_bp.size() - 1, m_bp.size()); }
528
530
536 bool is_leaf(const node_type & v) const { return v.i == v.j; }
537
539
547 {
548 assert(i > 0 and i <= size());
549 size_type ipos = m_bp_support.select(i);
550 size_type jp1pos;
551 if (i == size())
552 jp1pos = m_bp.size();
553 else if (m_bp[ipos + 1])
554 jp1pos = ipos + 1;
555 else
556 jp1pos = m_bp_support.select(i + 1);
557 return node_type(i - 1, i - 1, ipos, m_bp_support.find_close(ipos), jp1pos);
558 }
559
561
566 size_type size(const node_type & v) const { return v.j - v.i + 1; }
567
569
574 node_type leftmost_leaf(const node_type & v) const { return select_leaf(v.i + 1); }
575
577
582 node_type rightmost_leaf(const node_type & v) const { return select_leaf(v.j + 1); }
583
585
592 size_type lb(const node_type & v) const { return v.i; }
593
595
602 size_type rb(const node_type & v) const { return v.j; }
603
605
610 node_type parent(const node_type & v) const
611 {
612 if (v.cipos > v.jp1pos)
613 { // LCP[i] <= LCP[j+1]
614 size_type psv_pos, psv_cpos, psv_v, nsv_v, nsv_p1pos;
615 psv_v = psv(v.j + 1, v.jp1pos, m_bp_support.find_close(v.jp1pos), psv_pos, psv_cpos);
616 nsv_v = nsv(v.j + 1, v.jp1pos) - 1;
617 if (nsv_v == size() - 1) { nsv_p1pos = m_bp.size(); }
618 else
619 { // nsv_v < size()-1
620 nsv_p1pos = m_bp_support.select(nsv_v + 2);
621 }
622 return node_type(psv_v, nsv_v, psv_pos, psv_cpos, nsv_p1pos);
623 }
624 else
625 { // LCP[i] > LCP[j+1]
626 size_type psv_pos, psv_cpos, psv_v;
627 psv_v = psv(v.i, v.ipos, v.cipos, psv_pos, psv_cpos);
628 return node_type(psv_v, v.j, psv_pos, psv_cpos, v.jp1pos);
629 }
630 }
631
633
639 {
640 return cst_node_child_proxy<cst_sct3>(this, v);
641 }
642
644
650 node_type sibling(const node_type & v) const
651 {
652 // Procedure:(1) Determine, if v has a right sibling.
653 if (v.cipos < v.jp1pos)
654 { // LCP[i] > LCP[j+1] => v has the same right border as parent(v) => no right sibling
655 return root();
656 }
657 // (2) There exists a right sibling, LCP[j+1] >= LCP[i] and j>i
658 // Now it holds: v.cipos > v.jp1pos
659 size_type cjp1posm1 = m_bp_support.find_close(v.jp1pos) - 1; // v.cipos-2 ???
660 // m_bp[cjp1posm1] equals 1 => v is the last child
661 bool last_child = m_bp[cjp1posm1];
662 // otherwise if m_bp[cjp1posm1] equals 0 => we don't know if it is the last child
663 if (!last_child)
664 {
665 size_type first_child_idx = cjp1posm1 - m_bp_support.rank(cjp1posm1);
666 last_child = m_first_child[first_child_idx]; // if first_child indicator is true => the new sibling is the
667 // rightmost sibling
668 }
669 if (last_child)
670 {
671 size_type nsv_v = nsv(v.j + 1, v.jp1pos) - 1, nsv_p1pos;
672 if (nsv_v == size() - 1) { nsv_p1pos = m_bp.size(); }
673 else
674 {
675 nsv_p1pos = m_bp_support.select(nsv_v + 2);
676 }
677 return node_type(v.j + 1, nsv_v, v.jp1pos, m_bp_support.find_close(v.jp1pos), nsv_p1pos);
678 }
679 else
680 {
681 size_type new_j = m_bp_support.rank(m_bp_support.find_open(cjp1posm1)) - 2;
682 return node_type(v.j + 1,
683 new_j,
684 v.jp1pos,
685 m_bp_support.find_close(v.jp1pos),
686 m_bp_support.select(new_j + 2));
687 }
688 }
689
691
702 {
703 assert(i > 0);
704 if (is_leaf(v)) // if v is a leave, v has no child
705 return root();
706 if (1 == i)
707 {
708 size_type k = 0, kpos = 0, k_find_close = 0;
709 // v is not a leave: v has at least two children
710 k = select_l_index(v, 1, kpos, k_find_close); // get first l-index k and the position of k
711 return node_type(v.i, k - 1, v.ipos, v.cipos, kpos);
712 }
713 else
714 { // i > 1
715 size_type k1, kpos1, k_find_close1;
716 k1 = select_l_index(v, i - 1, kpos1, k_find_close1);
717 if (k1 == v.j + 1) return root();
718 size_type k2, kpos2, k_find_close2;
719 k2 = select_l_index(v, i, kpos2, k_find_close2);
720 return node_type(k1, k2 - 1, kpos1, k_find_close1, kpos2);
721 }
722 }
723
725
732 size_type degree(const node_type & v) const
733 {
734 if (is_leaf(v)) // if v is a leave, v has no child
735 return 0;
736 // v is not a leave: v has at least two children
737 size_type r = closing_pos_of_first_l_index(v);
738 size_type r0 = r - m_bp_support.rank(r);
739 const uint64_t * p = m_first_child.data() + (r0 >> 6);
740 uint8_t offset = r0 & 0x3F;
741
742 uint64_t w = (*p) & bits::lo_set[offset];
743 if (w)
744 { // if there is a bit set in the current word
745 return offset - bits::hi(w) + 1;
746 }
747 else if (m_first_child.data() == p)
748 { // no bit set and we are in the first word
749 return offset + 2; // since would have to be bits::hi(w)=-1, child marked in previous word
750 }
751 else
752 {
753 size_type res = offset + 2;
754 int steps = 4;
755 // search in previous four words for result
756 while (p > m_first_child.data() and steps-- > 0)
757 {
758 w = *(--p);
759 if (0 == w)
760 res += 64;
761 else
762 {
763 return res + (63 - bits::hi(w));
764 }
765 }
766 // if not found: use rank + select to answer query
767 auto goal_rank = m_first_child_rank(r0);
768 if (goal_rank == 0) { return r0 + 2; }
769 else
770 {
771 return r0 - m_first_child_select(goal_rank) + 1;
772 }
773 }
774 }
775
777
787 node_type child(const node_type & v, const char_type c, size_type & char_pos) const
788 {
789 if (is_leaf(v)) // if v is a leaf = (), v has no child
790 return root();
791 // else v = ( ( ))
792 comp_char_type cc = m_csa.char2comp[c];
793 if (cc == 0 and c != 0) // TODO: change char2comp so that we don't need this special case
794 return root();
795 size_type char_ex_max_pos = m_csa.C[((size_type)1) + cc], char_inc_min_pos = m_csa.C[cc];
796
797 size_type d = depth(v);
798
799 // (1) check the first child
800 char_pos = get_char_pos(v.i, d, m_csa);
801 if (char_pos >= char_ex_max_pos)
802 { // the first character of the first child interval is lex. greater than c
803 // => all other first characters of the child intervals are also greater than c => no solution
804 return root();
805 }
806 else if (char_pos >= char_inc_min_pos)
807 { // i.e. char_pos < char_ex_max_pos and char_pos >= char_inc_min_pos
808 return select_child(v, 1);
809 }
810
811 size_type child_cnt = degree(v);
812
813 // (2) check the last child
814 char_pos = get_char_pos(v.j, d, m_csa);
815 if (char_pos < char_inc_min_pos)
816 { // the first character of the last child interval is lex. smaller than c
817 // => all other first characters of the child intervals are also smaller than c => no solution
818 return root();
819 }
820 else if (char_pos < char_ex_max_pos)
821 { // i.e. char_pos < char_ex_max_pos and char_pos >= char_inc_min_pos
822 return select_child(v, child_cnt);
823 }
824
825 // (3) binary search for c in the children [2..children)
826 size_type l_bound = 2, r_bound = child_cnt, mid, kpos, ckpos, l_index;
827 while (l_bound < r_bound)
828 {
829 mid = (l_bound + r_bound) >> 1;
830
831 l_index = select_l_index(v, mid - 1, kpos, ckpos);
832 char_pos = get_char_pos(l_index, d, m_csa);
833
834 if (char_inc_min_pos > char_pos) { l_bound = mid + 1; }
835 else if (char_ex_max_pos <= char_pos)
836 {
837 r_bound = mid;
838 }
839 else
840 { // char_inc_min_pos <= char_pos < char_ex_max_pos => found child
841 // we know that the child is not the last child, see (2)
842 // find next l_index: we know that a new l_index exists: i.e. assert( 0 == m_bp[ckpos-1]);
843 size_type lp1_index = m_bp_support.rank(m_bp_support.find_open(ckpos - 1)) - 1;
844 size_type jp1pos = m_bp.size();
845 if (lp1_index - 1 < size() - 1) { jp1pos = m_bp_support.select(lp1_index + 1); }
846 return node_type(l_index, lp1_index - 1, kpos, ckpos, jp1pos);
847 }
848 }
849 return root();
850 }
851
853 // \sa child(node_type v, const char_type c, size_type &char_pos)
854 node_type child(const node_type & v, const char_type c) const
855 {
856 size_type char_pos;
857 return child(v, c, char_pos);
858 }
859
861
869 char_type edge(const node_type & v, size_type d) const
870 {
871 assert(1 <= d);
872 assert(d <= depth(v));
873 size_type order = get_char_pos(v.i, d - 1, m_csa);
874 size_type c_begin = 1, c_end = ((size_type)m_csa.sigma) + 1, mid;
875 while (c_begin < c_end)
876 {
877 mid = (c_begin + c_end) >> 1;
878 if (m_csa.C[mid] <= order) { c_begin = mid + 1; }
879 else
880 {
881 c_end = mid;
882 }
883 }
884 return m_csa.comp2char[c_begin - 1];
885 }
886
888
897 {
898 if (v.i > w.i or (v.i == w.i and v.j < w.j)) { std::swap(v, w); }
899 if (v.j >= w.j)
900 { // v encloses w or v==w
901 return v;
902 }
903 else
904 { // v.i < v.j < w.i < w.j
905 size_type min_index = rmq(v.i + 1, w.j);
906 size_type min_index_pos = m_bp_support.select(min_index + 1);
907 size_type min_index_cpos = m_bp_support.find_close(min_index_pos);
908
909 if (min_index_cpos >= (m_bp.size() - m_csa.sigma))
910 { // if lcp[min_index]==0 => return root
911 return root();
912 }
913 size_type new_j = nsv(min_index, min_index_pos) - 1;
914 size_type new_ipos, new_icpos;
915 size_type new_i = psv(min_index, min_index_pos, min_index_cpos, new_ipos, new_icpos);
916 size_type jp1pos = m_bp.size();
917 if (new_j < size() - 1) { jp1pos = m_bp_support.select(new_j + 2); }
918 return node_type(new_i, new_j, new_ipos, new_icpos, jp1pos);
919 }
920 }
921
923
929 size_type depth(const node_type & v) const
930 {
931 if (v == root()) { return 0; }
932 else if (v.i == v.j)
933 {
934 return size() - m_csa[v.i];
935 }
936 else
937 {
938 size_type kpos, ckpos;
939 size_type l = select_l_index(v, 1, kpos, ckpos);
940 return m_lcp[l];
941 }
942 }
943
945
957 {
958 size_type d = 0;
959 while (v != root())
960 {
961 ++d;
962 v = parent(v);
963 }
964 return d;
965 }
966
968
974 node_type sl(const node_type & v) const
975 {
976 if (v == root()) return root();
977 // get interval with first char deleted
978 size_type i = m_csa.psi[v.i];
979 if (is_leaf(v))
980 {
981 if (v.i == 0 and v.j == 0) // if( v.l==1 )
982 return root();
983 else
984 return select_leaf(i + 1);
985 }
986 size_type j = m_csa.psi[v.j];
987 assert(i < j);
988 size_type min_index = rmq(i + 1, j); // rmq
989 size_type min_index_pos = m_bp_support.select(min_index + 1);
990 size_type min_index_cpos = m_bp_support.find_close(min_index_pos);
991 if (min_index_cpos >= (m_bp.size() - m_csa.sigma))
992 { // if lcp[min_index]==0 => return root
993 return root();
994 }
995 size_type new_j = nsv(min_index, min_index_pos) - 1;
996 size_type new_ipos, new_icpos;
997 size_type new_i = psv(min_index, min_index_pos, min_index_cpos, new_ipos, new_icpos);
998 size_type jp1pos = m_bp.size();
999 if (new_j < size() - 1) { jp1pos = m_bp_support.select(new_j + 2); }
1000 return node_type(new_i, new_j, new_ipos, new_icpos, jp1pos);
1001 }
1002
1004
1012 node_type wl(const node_type & v, const char_type c) const
1013 {
1014 size_type c_left = m_csa.bwt.rank(v.i, c);
1015 size_type c_right = m_csa.bwt.rank(v.j + 1, c);
1016 if (c_left == c_right) // there exists no Weiner link
1017 return root();
1018 if (c_left + 1 == c_right)
1019 return select_leaf(m_csa.C[m_csa.char2comp[c]] + c_left + 1);
1020 else
1021 {
1022 size_type left = m_csa.C[m_csa.char2comp[c]] + c_left;
1023 size_type right = m_csa.C[m_csa.char2comp[c]] + c_right - 1;
1024 assert(left < right);
1025
1026 size_type ipos = m_bp_support.select(left + 1);
1027 size_type jp1pos = m_bp.size();
1028 if (right < size() - 1) { jp1pos = m_bp_support.select(right + 2); }
1029 return node_type(left, right, ipos, m_bp_support.find_close(ipos), jp1pos);
1030 }
1031 }
1032
1034
1039 size_type sn(const node_type & v) const
1040 {
1041 assert(is_leaf(v));
1042 return m_csa[v.i];
1043 }
1044
1046
1052 size_type id(const node_type & v) const
1053 {
1054 if (is_leaf(v))
1055 { // return id in the range from 0..csa.size()-1
1056 return v.i;
1057 }
1058 size_type ckpos; // closing parentheses of the l-index
1059 if (v.cipos > v.jp1pos)
1060 { // corresponds to m_lcp[i] <= m_lcp[j+1]
1061 ckpos = v.jp1pos - 1;
1062 }
1063 else
1064 { // corresponds to m_lcp[i] > m_lcp[j+1]
1065 ckpos = v.cipos - 1;
1066 }
1067 assert(m_bp[ckpos] == 0);
1068 size_type r0ckpos = ckpos - m_bp_support.rank(ckpos); // determine the rank of the closing parenthesis
1069 return size() + m_first_child_rank(r0ckpos);
1070 }
1071
1073
1081 {
1082 if (id < size())
1083 { // the corresponding node is a leaf
1084 return select_leaf(id + 1);
1085 }
1086 else
1087 { // the corresponding node is a inner node
1088 // (1) get index of the closing parenthesis in m_first_child
1089 size_type r0ckpos = 0;
1090 {
1091 // binary search for the position of the (id-size()+1)-th set bit in
1092 id = id - size() + 1;
1093 size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
1094 // invariant: arg(lb) < id, arg(rb) >= id
1095 while (rb - lb > 1)
1096 {
1097 size_type mid = lb + (rb - lb) / 2;
1098 size_type arg = m_first_child_rank(mid); // ones in the prefix [0..mid-1]
1099 if (arg < id) { lb = mid; }
1100 else
1101 { // arg >= id
1102 rb = mid;
1103 }
1104 }
1105 r0ckpos = lb;
1106 }
1107 // (2) determine position clpos of the r0clpos-th closing parentheses in the parentheses sequence
1108 size_type ckpos = 0;
1109 {
1110 // binary search for the position of the (r0ckpos+1)-th closing parenthesis
1111 size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
1112 // invariant: arg(lb) < r0ckpos+1, arg(rb) >= r0ckpos+1
1113 while (rb - lb > 1)
1114 {
1115 size_type mid = lb + (rb - lb) / 2;
1116 size_type arg = mid - m_bp_support.rank(mid - 1); // zeros in the prefix [0..mid-1]
1117 if (arg < r0ckpos + 1) { lb = mid; }
1118 else
1119 { // arg >= x
1120 rb = mid;
1121 }
1122 }
1123 ckpos = lb;
1124 }
1125 if (ckpos == m_bp.size() - 1) { return root(); }
1126 if (m_bp[ckpos + 1])
1127 { // jp1pos < cipos
1128 size_type jp1pos = ckpos + 1;
1129 size_type j = m_bp_support.rank(jp1pos - 1) - 1;
1130 size_type kpos = m_bp_support.find_open(ckpos);
1131 size_type ipos = m_bp_support.enclose(kpos);
1132 size_type cipos = m_bp_support.find_close(ipos);
1133 size_type i = m_bp_support.rank(ipos - 1);
1134 return node_type(i, j, ipos, cipos, jp1pos);
1135 }
1136 else
1137 { //
1138 size_type cipos = ckpos + 1;
1139 size_type ipos = m_bp_support.find_open(cipos);
1140 size_type i = m_bp_support.rank(ipos - 1);
1141 size_type j = nsv(i, ipos) - 1;
1142 size_type jp1pos = m_bp.size();
1143 if (j != size() - 1) { jp1pos = m_bp_support.select(j + 2); }
1144 return node_type(i, j, ipos, cipos, jp1pos);
1145 }
1146 }
1147 }
1148
1150 size_type nodes() const { return m_nodes; }
1151
1153 /* \param lb Left bound of the lcp-interval [lb..rb] (inclusive).
1154 * \param rb Right bound of the lcp-interval [lb..rb] (inclusive).
1155 * \return The node in the suffix tree corresponding lcp-interval [lb..rb]
1156 * \par Time complexity
1157 * \f$ \Order{1} \f$
1158 */
1160 {
1161 size_type ipos = m_bp_support.select(lb + 1);
1162 size_type jp1pos;
1163 if (rb == size() - 1) { jp1pos = m_bp.size(); }
1164 else
1165 {
1166 jp1pos = m_bp_support.select(rb + 2);
1167 }
1168 return node_type(lb, rb, ipos, m_bp_support.find_close(ipos), jp1pos);
1169 }
1170
1172
1177 {
1178 size_type ipos = m_bp_support.select(i + 1);
1179 size_type cipos = m_bp_support.find_close(ipos);
1180 return m_first_child_rank.rank(((ipos + cipos - 1) >> 1) - i);
1181 }
1182 /* @} */
1183};
1184
1185// == template functions ==
1186
1187template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1189{
1190 {
1191 auto event = memory_monitor::event("bps-sct");
1193 m_nodes = construct_supercartesian_tree_bp_succinct_and_first_child(lcp_buf, m_bp, m_first_child);
1194 m_nodes += m_bp.size() / 2;
1195 if (m_bp.size() == 2)
1196 { // handle special case, when the tree consists only of the root node
1197 m_nodes = 1;
1198 }
1199 }
1200 {
1201 auto event = memory_monitor::event("bpss-sct");
1202 util::init_support(m_bp_support, &m_bp);
1203 util::init_support(m_first_child_rank, &m_first_child);
1204 util::init_support(m_first_child_select, &m_first_child);
1205 }
1206 if (!build_only_bps)
1207 {
1208 auto event = memory_monitor::event("clcp");
1209 cache_config tmp_config(false, config.dir, config.id, config.file_map);
1210 construct_lcp(m_lcp, *this, tmp_config);
1211 config.file_map = tmp_config.file_map;
1212 }
1213 if (!build_only_bps)
1214 {
1215 auto event = memory_monitor::event("load csa");
1216 load_from_cache(m_csa, std::string(conf::KEY_CSA) + "_" + util::class_to_hash(m_csa), config);
1217 }
1218}
1219
1220template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1223 std::string name) const -> size_type
1224{
1225 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1226 size_type written_bytes = 0;
1227 written_bytes += m_csa.serialize(out, child, "csa");
1228 written_bytes += m_lcp.serialize(out, child, "lcp");
1229 written_bytes += m_bp.serialize(out, child, "bp");
1230 written_bytes += m_bp_support.serialize(out, child, "bp_support");
1231 written_bytes += m_first_child.serialize(out, child, "mark_child");
1232 written_bytes += m_first_child_rank.serialize(out, child, "mark_child_rank");
1233 written_bytes += m_first_child_select.serialize(out, child, "mark_child_select");
1234 written_bytes += write_member(m_nodes, out, child, "node_cnt");
1235 structure_tree::add_size(child, written_bytes);
1236 return written_bytes;
1237}
1238
1239template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1241{
1242 m_csa.load(in);
1243 load_lcp(m_lcp, in, *this);
1244 m_bp.load(in);
1245 m_bp_support.load(in, &m_bp);
1246 m_first_child.load(in);
1247 m_first_child_rank.load(in, &m_first_child);
1248 m_first_child_select.load(in, &m_first_child);
1249 read_member(m_nodes, in);
1250}
1251
1252template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1253template <typename archive_t>
1255{
1256 ar(CEREAL_NVP(m_csa));
1257 ar(CEREAL_NVP(m_lcp));
1258 ar(CEREAL_NVP(m_bp));
1259 ar(CEREAL_NVP(m_bp_support));
1260 ar(CEREAL_NVP(m_first_child));
1261 ar(CEREAL_NVP(m_first_child_rank));
1262 ar(CEREAL_NVP(m_first_child_select));
1263 ar(CEREAL_NVP(m_nodes));
1264}
1265
1266template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1267template <typename archive_t>
1269{
1270 ar(CEREAL_NVP(m_csa));
1271 ar(CEREAL_NVP(m_lcp));
1272 set_lcp_pointer(m_lcp, *this);
1273 ar(CEREAL_NVP(m_bp));
1274 ar(CEREAL_NVP(m_bp_support));
1275 m_bp_support.set_vector(&m_bp);
1276 ar(CEREAL_NVP(m_first_child));
1277 ar(CEREAL_NVP(m_first_child_rank));
1278 m_first_child_rank.set_vector(&m_first_child);
1279 ar(CEREAL_NVP(m_first_child_select));
1280 m_first_child_select.set_vector(&m_first_child);
1281 ar(CEREAL_NVP(m_nodes));
1282}
1283
1284template <class t_int>
1286{
1287 t_int i;
1288 t_int j;
1289 t_int ipos; // position of the i+1th opening parenthesis in the balanced parentheses sequence
1290 t_int cipos; // position of the matching closing parenthesis of the i+1th opening parenthesis in the balanced
1291 // parentheses sequence
1292 t_int jp1pos; // position of the j+2th opening parenthesis in the balanced parentheses sequence
1293
1295 bp_interval(t_int i = 0, t_int j = 0, t_int ipos = 0, t_int cipos = 0, t_int jp1pos = 0)
1296 : i(i)
1297 , j(j)
1298 , ipos(ipos)
1299 , cipos(cipos)
1300 , jp1pos(jp1pos){};
1301
1303 bp_interval(const bp_interval & iv) = default;
1305 bp_interval(bp_interval && iv) = default;
1306
1307 bool operator<(const bp_interval & interval) const
1308 {
1309 if (i != interval.i) return i < interval.i;
1310 return j < interval.j;
1311 }
1312
1314
1316 bool operator==(const bp_interval & interval) const { return i == interval.i and j == interval.j; }
1317
1319
1322 bool operator!=(const bp_interval & interval) const { return !(*this == interval); }
1323
1325 bp_interval & operator=(const bp_interval & interval) = default;
1327 bp_interval & operator=(bp_interval && interval) = default;
1328};
1329
1330template <class t_int>
1331inline std::ostream & operator<<(std::ostream & os, const bp_interval<t_int> & interval)
1332{
1333 os << "-[" << interval.i << "," << interval.j << "](" << interval.ipos << "," << interval.cipos << ","
1334 << interval.jp1pos << ")";
1335 return os;
1336}
1337
1338} // end namespace sdsl
1339#endif
bp_support.hpp contains several classed which support find_open, find_close, enclose and rr-enclose q...
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
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:90
t_csa::alphabet_type::sigma_type sigma_type
Definition: cst_sct3.hpp:110
size_type id(const node_type &v) const
Computes a unique identification number for a node of the suffx tree in the range [0....
Definition: cst_sct3.hpp:1052
node_type parent(const node_type &v) const
Calculate the parent node of a node v.
Definition: cst_sct3.hpp:610
node_type lca(node_type v, node_type w) const
Calculate the LCA of two nodes v and w
Definition: cst_sct3.hpp:896
const_iterator begin() const
Returns a const_iterator to the first element of a depth first traversal of the tree.
Definition: cst_sct3.hpp:413
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:449
node_type rightmost_leaf(const node_type &v) const
Calculates the rightmost leaf in the subtree rooted at node v.
Definition: cst_sct3.hpp:582
size_type size(const node_type &v) const
Calculate the number of leaves in the subtree rooted at node v.
Definition: cst_sct3.hpp:566
node_type wl(const node_type &v, const char_type c) const
Compute the Weiner link of node v and character c.
Definition: cst_sct3.hpp:1012
const sel_type & first_child_select
Definition: cst_sct3.hpp:338
t_bp_support bp_support_type
Definition: cst_sct3.hpp:101
const lcp_type & lcp
Definition: cst_sct3.hpp:332
static size_type max_size()
Returns the largest size that cst_sct3 can ever have.
Definition: cst_sct3.hpp:401
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
Definition: cst_sct3.hpp:1268
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right).
Definition: cst_sct3.hpp:546
t_csa csa_type
Definition: cst_sct3.hpp:99
node_type root() const
Return the root of the suffix tree.
Definition: cst_sct3.hpp:527
node_type inv_id(size_type id)
Computes the node for such that id(v)=id.
Definition: cst_sct3.hpp:1080
size_type node_depth(node_type v) const
Returns the node depth of node v.
Definition: cst_sct3.hpp:956
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:441
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition: cst_sct3.hpp:1221
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_sct3.hpp:1159
size_type nodes() const
Get the number of nodes of the suffix tree.
Definition: cst_sct3.hpp:1150
cst_bottom_up_const_forward_iterator< cst_sct3 > const_bottom_up_iterator
Definition: cst_sct3.hpp:96
const_iterator begin(const node_type &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:421
t_csa::string_type string_type
Definition: cst_sct3.hpp:103
const bv_type & first_child_bv
Definition: cst_sct3.hpp:336
const bit_vector & bp
Definition: cst_sct3.hpp:333
bool empty() const
Returns if the data structure is empty.
Definition: cst_sct3.hpp:407
cst_sct3(cst_sct3 &&cst)
Move constructor.
Definition: cst_sct3.hpp:374
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: cst_sct3.hpp:1254
t_csa::char_type char_type
Definition: cst_sct3.hpp:102
bool operator==(cst_sct3 const &other) const noexcept
Equality operator.
Definition: cst_sct3.hpp:508
bool operator!=(cst_sct3 const &other) const noexcept
Inequality operator.
Definition: cst_sct3.hpp:517
size_type size() const
Number of leaves of the suffix tree.
Definition: cst_sct3.hpp:395
cst_tag index_category
Definition: cst_sct3.hpp:113
node_type child(const 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_sct3.hpp:854
const rank_type & first_child_rank
Definition: cst_sct3.hpp:337
const bp_support_type & bp_support
Definition: cst_sct3.hpp:334
char_type edge(const node_type &v, size_type d) const
Returns the d-th character (1-based indexing) of the edge-label pointing to v.
Definition: cst_sct3.hpp:869
node_type sl(const node_type &v) const
Compute the suffix link of node v.
Definition: cst_sct3.hpp:974
node_type child(const 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_sct3.hpp:787
bool is_leaf(const node_type &v) const
Decide if a node is a leaf.
Definition: cst_sct3.hpp:536
const_iterator end(const node_type &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:434
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:431
cst_dfs_const_forward_iterator< cst_sct3 > const_iterator
Definition: cst_sct3.hpp:95
t_csa::size_type size_type
Definition: cst_sct3.hpp:97
bp_interval< size_type > node_type
Type for the nodes in the tree.
Definition: cst_sct3.hpp:104
node_type sibling(const node_type &v) const
Returns the next sibling of node v.
Definition: cst_sct3.hpp:650
node_type leftmost_leaf(const node_type &v) const
Calculates the leftmost leaf in the subtree rooted at node v.
Definition: cst_sct3.hpp:574
size_type depth(const node_type &v) const
Returns the string depth of node v.
Definition: cst_sct3.hpp:929
cst_sct3 & operator=(const cst_sct3 &cst)
Assignment Operator.
Definition: cst_sct3.hpp:455
cst_sct3 & operator=(cst_sct3 &&cst)
Assignment Move Operator.
Definition: cst_sct3.hpp:469
t_lcp::template type< cst_sct3 > lcp_type
Definition: cst_sct3.hpp:100
ptrdiff_t difference_type
Definition: cst_sct3.hpp:98
cst_node_child_proxy< cst_sct3 > children(const node_type &v) const
Return a proxy object which allows iterating over the children of a node.
Definition: cst_sct3.hpp:638
size_type sn(const node_type &v) const
Computes the suffix number of a leaf node v.
Definition: cst_sct3.hpp:1039
size_type rb(const node_type &v) const
Calculates the index of the rightmost leaf in the corresponding suffix array.
Definition: cst_sct3.hpp:602
cst_sct3(const cst_sct3 &cst)
Copy constructor.
Definition: cst_sct3.hpp:355
t_csa::alphabet_category alphabet_category
Definition: cst_sct3.hpp:112
t_csa::alphabet_type::comp_char_type comp_char_type
Definition: cst_sct3.hpp:109
void load(std::istream &in)
Load from a stream.
Definition: cst_sct3.hpp:1240
node_type select_child(const node_type &v, size_type i) const
Get the i-th child of a node v.
Definition: cst_sct3.hpp:701
t_rank rank_type
Definition: cst_sct3.hpp:106
size_type lb(const node_type &v) const
Calculates the index of the leftmost leaf in the corresponding suffix array.
Definition: cst_sct3.hpp:592
const csa_type & csa
Definition: cst_sct3.hpp:331
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_sct3.hpp:1176
size_type degree(const node_type &v) const
Get the number of children of a node v.
Definition: cst_sct3.hpp:732
cst_sct3()=default
Default constructor.
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(const std::string &name)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
#define SDSL_UNUSED
Definition: config.hpp:13
construct.hpp contains methods to construct indexes (compressed suffix arrays and trees).
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.
iterators.hpp contains an generic iterator for random access containers.
lcp.hpp contains classes for lcp information.
constexpr char KEY_CSA[]
Definition: config.hpp:38
constexpr char KEY_LCP[]
Definition: config.hpp:44
int_vector ::size_type size_type
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
Definition: io.hpp:630
t_csa::size_type get_char_pos(typename t_csa::size_type idx, typename t_csa::size_type d, const t_csa &csa)
bool load_from_cache(T &v, const std::string &key, const cache_config &config, bool add_type_hash=false)
Definition: io.hpp:711
void move_lcp(t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &cst)
Definition: lcp.hpp:92
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:946
void copy_lcp(t_lcp &lcp, const t_lcp &lcp_c, const t_cst &cst)
Definition: lcp.hpp:57
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, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
void construct_lcp(t_lcp &lcp, const t_cst &cst, cache_config &config)
Definition: lcp.hpp:25
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
void set_lcp_pointer(t_lcp &lcp, const t_cst &cst)
Definition: lcp.hpp:159
void load_lcp(t_lcp &lcp, std::istream &in, const t_cst &cst)
Definition: lcp.hpp:127
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1331
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
Contains declarations and definitions of data structure concepts.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
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:686
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
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:187
t_int i
The left border of the lcp-interval .
Definition: cst_sct3.hpp:1287
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.
Definition: cst_sct3.hpp:1295
bp_interval(const bp_interval &iv)=default
Copy constructor.
t_int j
The right border of the lcp-interval .
Definition: cst_sct3.hpp:1288
bool operator!=(const bp_interval &interval) const
Inequality operator.
Definition: cst_sct3.hpp:1322
bool operator==(const bp_interval &interval) const
Equality operator.
Definition: cst_sct3.hpp:1316
bp_interval & operator=(const bp_interval &interval)=default
Assignment operator.
bool operator<(const bp_interval &interval) const
Definition: cst_sct3.hpp:1307
bp_interval(bp_interval &&iv)=default
Move copy constructor.
Helper class for construction process.
Definition: config.hpp:67
std::string id
Definition: config.hpp:72
std::string dir
Definition: config.hpp:71
suffix_tree_algorithm.hpp contains algorithms on CSTs
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.