SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
bp_support_g.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_BP_SUPPORT_G
9#define INCLUDED_SDSL_BP_SUPPORT_G
10
11#include <map>
12#include <set>
13#include <stack>
14#include <stdexcept>
15#include <utility>
16
18#include <sdsl/int_vector.hpp>
20#include <sdsl/rank_support.hpp>
21#include <sdsl/rmq_support.hpp>
23#include <sdsl/util.hpp>
24
25namespace sdsl
26{
27
29
52template <class t_nnd = nearest_neighbour_dictionary<30>,
53 class t_rank = rank_support_v5<>,
54 class t_select = select_support_mcl<>,
55 class t_rmq = range_maximum_support_sparse_table<>,
56 uint32_t t_bs = 840>
58{
59 static_assert(t_bs > 2, "bp_support_g: block size must be greater than 2.");
60
61 public:
63 typedef t_nnd nnd_type;
64 typedef t_rank rank_type;
65 typedef t_select select_type;
66 typedef t_rmq rmq_type;
67
68 private:
69 const bit_vector * m_bp; // the supported BP sequence as bit_vector
70 rank_type m_rank_bp; // rank support for the BP sequence => see excess() and rank()
71 select_type m_select_bp; // select support for the BP sequence => see select()
72
73 nnd_type m_nnd; // nearest neighbour dictionary for pioneers bit_vector
74
75 bit_vector m_pioneer_bp; // first level of recursion: BP sequence of the pioneers
76 rank_type m_rank_pioneer_bp; // rank for the BP sequence of the pioneers
77 nnd_type m_nnd2; // nearest neighbour dictionary for pioneers of pioneers bit_vector
78 int_vector<> m_match; //
79 int_vector<> m_enclose; //
80 rmq_type m_range_max_match; // range maximum support for m_match
81
82 size_type m_size;
83 size_type m_blocks; // number of blocks
84
88 inline size_type excess_pioneer(size_type i) const { return (m_rank_pioneer_bp(i + 1) << 1) - i - 1; }
89
90 public:
91 const rank_type & bp_rank = m_rank_bp;
92 const select_type & bp_select = m_select_bp;
93
95 explicit bp_support_g(const bit_vector * bp = nullptr)
96 : m_bp(bp)
97 , m_size(bp == nullptr ? 0 : bp->size())
98 , m_blocks((m_size + t_bs - 1) / t_bs)
99 {
100 if (bp == nullptr) return;
101 util::init_support(m_rank_bp, bp);
102 util::init_support(m_select_bp, bp);
103 bit_vector pioneer = calculate_pioneers_bitmap(*m_bp, t_bs);
104 m_nnd = nnd_type(pioneer);
105 m_pioneer_bp.resize(m_nnd.ones());
106 for (size_type i = 1; i <= m_nnd.ones(); ++i) m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
107 util::init_support(m_rank_pioneer_bp, &m_pioneer_bp);
108 pioneer = calculate_pioneers_bitmap(m_pioneer_bp, t_bs);
109 m_nnd2 = nnd_type(pioneer);
110
111 bit_vector pioneer_bp2 = bit_vector(m_nnd2.ones());
112 for (size_type i = 1; i <= m_nnd2.ones(); ++i) pioneer_bp2[i - 1] = m_pioneer_bp[m_nnd2.select(i)];
113 calculate_matches(pioneer_bp2, m_match);
114 calculate_enclose(pioneer_bp2, m_enclose);
115 m_range_max_match = rmq_type(&m_match);
116 }
117
120 : m_bp(v.m_bp)
121 , m_rank_bp(v.m_rank_bp)
122 , m_select_bp(v.m_select_bp)
123 , m_nnd(v.m_nnd)
124 , m_pioneer_bp(v.m_pioneer_bp)
125 , m_rank_pioneer_bp(v.m_rank_pioneer_bp)
126 , m_nnd2(v.m_nnd2)
127 , m_match(v.m_match)
128 , m_enclose(v.m_enclose)
129 , m_range_max_match(v.m_range_max_match)
130 , m_size(v.m_size)
131 , m_blocks(v.m_blocks)
132 {
133 m_rank_bp.set_vector(m_bp);
134 m_select_bp.set_vector(m_bp);
135 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
136 m_range_max_match.set_vector(&m_match);
137 }
138
140 bp_support_g(bp_support_g && bp_support) { *this = std::move(bp_support); }
141
143 bp_support_g & operator=(const bp_support_g & bp_support)
144 {
145 if (this != &bp_support)
146 {
147 bp_support_g tmp(bp_support);
148 *this = std::move(tmp);
149 }
150 return *this;
151 }
152
155 {
156 if (this != &bp_support)
157 {
158 m_bp = std::move(bp_support.m_bp);
159 m_rank_bp = std::move(bp_support.m_rank_bp);
160 m_rank_bp.set_vector(m_bp);
161 m_select_bp = std::move(bp_support.m_select_bp);
162 m_select_bp.set_vector(m_bp);
163
164 m_nnd = std::move(bp_support.m_nnd);
165
166 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
167 m_rank_pioneer_bp = std::move(bp_support.m_rank_pioneer_bp);
168 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
169 m_nnd2 = std::move(bp_support.m_nnd2);
170 m_match = std::move(bp_support.m_match);
171 m_enclose = std::move(bp_support.m_enclose);
172 m_range_max_match = std::move(bp_support.m_range_max_match);
173 m_range_max_match.set_vector(&m_match);
174
175 m_size = std::move(bp_support.m_size);
176 m_blocks = std::move(bp_support.m_blocks);
177 }
178 return *this;
179 }
180
181 void set_vector(const bit_vector * bp)
182 {
183 m_bp = bp;
184 m_rank_bp.set_vector(bp);
185 m_select_bp.set_vector(bp);
186 }
187
191 inline size_type excess(size_type i) const { return (m_rank_bp(i + 1) << 1) - i - 1; }
192
196 size_type rank(size_type i) const { return m_rank_bp(i + 1); }
197
203 size_type select(size_type i) const { return m_select_bp(i); }
204
212 {
213 assert(i < m_size);
214 if (!(*m_bp)[i])
215 { // if there is a closing parenthesis at index i return i
216 return i;
217 }
218 size_type mi = 0; // match for i
219 if ((mi = near_find_close(*m_bp, i, t_bs)) == i)
220 {
221 const size_type i2 = m_nnd.rank(i + 1) - 1; // lemma that this gives us an opening pioneer
222 assert(m_pioneer_bp[i2] == 1); // assert that i2 is an opening parenthesis
223 size_type mi2 = 0; // match for i2
224 if ((mi2 = near_find_close(m_pioneer_bp, i2, t_bs)) == i2)
225 {
226 const size_type i3 = m_nnd2.rank(i2 + 1) - 1;
227 const size_type mi3 = m_match[i3];
228 assert(mi3 > i3); // assert that i3 is an opening parenthesis
229 mi2 = m_nnd2.select(mi3 + 1); // matching pioneer position in pioneer_bp
230 mi2 = (mi2 / t_bs) * t_bs;
231 size_type epb = excess_pioneer(mi2); // excess of first parenthesis in the pioneer block
232 const size_type ei = excess_pioneer(i2); // excess of pioneer
233 /* invariant: epb >= ei-1 */ assert(epb + 1 >= ei);
234 while (epb + 1 != ei)
235 {
236 assert(mi2 < m_pioneer_bp.size());
237 if (m_pioneer_bp[++mi2])
238 ++epb;
239 else
240 --epb;
241 }
242 }
243 mi = m_nnd.select(mi2 + 1); /* matching pioneer position in bp */
244 assert((*m_bp)[mi] == 0);
245 mi = (mi / t_bs) * t_bs;
246 size_type epb = excess(mi); // excess of first parenthesis in the pioneer block
247 const size_type ei = excess(i); // excess at position i
248 /* invariant: epb >= ei-1 */ assert(epb + 1 >= ei);
249 while (epb + 1 != ei)
250 {
251 assert(mi < m_size);
252 if ((*m_bp)[++mi])
253 ++epb;
254 else
255 --epb;
256 }
257 }
258 return mi;
259 }
260
262
268 {
269 assert(i < m_size);
270 if ((*m_bp)[i])
271 { // if there is a opening parenthesis at index i return i
272 return i;
273 }
274 size_type mi = 0; // match for i
275 if ((mi = near_find_open(*m_bp, i, t_bs)) == i)
276 {
277 const size_type i2 = m_nnd.rank(i); // lemma that this gives us an closing pioneer
278 assert(m_pioneer_bp[i2] == 0); // assert that i2 is an opening parenthesis
279 const size_type mi2 = find_open_in_pioneers(i2);
280 assert(m_pioneer_bp[mi2] == 1);
281 mi = m_nnd.select(mi2 + 1); /* matching pioneer position in bp */
282 assert((*m_bp)[mi] == 1);
283 mi = (mi / t_bs) * t_bs + t_bs - 1;
284 assert(mi < i);
285 size_type epb = excess(mi); // excess of last parenthesis in the pioneer block
286 const size_type ei = excess(i); // excess at position i
287 /*invariant: epb >= ei+1*/ assert(epb >= ei + 1);
288 while (epb != ei)
289 {
290 assert(mi < m_size);
291 if ((*m_bp)[mi--])
292 --epb;
293 else
294 ++epb;
295 }
296 ++mi;
297 }
298 return mi;
299 }
300
302 {
303 size_type mi = 0; // match for i
304 if ((mi = near_find_open(m_pioneer_bp, i, t_bs)) == i)
305 {
306 const size_type i3 = m_nnd2.rank(i);
307 const size_type mi3 = m_match[i3];
308 assert(mi3 < i3); // assert that i3 is an closing parenthesis
309 mi = m_nnd2.select(mi3 + 1); // matching pioneer position in pioneer_bp
310 mi = (mi / t_bs) * t_bs + t_bs - 1;
311 size_type epb2 = excess_pioneer(mi); // excess of last parenthesis in the pioneer block
312 const size_type ei = excess_pioneer(i); // excess of pioneer
313 /* invariant: epb2 >= ei+1 */ assert(epb2 >= ei + 1);
314 while (epb2 != ei)
315 {
316 assert(mi < m_pioneer_bp.size());
317 if (m_pioneer_bp[mi--])
318 --epb2;
319 else
320 ++epb2;
321 }
322 ++mi;
323 }
324 return mi;
325 }
326
329
334 {
335 assert(i < m_size);
336 if (!(*m_bp)[i])
337 { // if there is closing parenthesis at position i
338 return find_open(i);
339 }
340 const size_type exi = excess(i);
341 if (exi == 1) // if i is not enclosed by a parentheses pair..
342 return size();
343 size_type ei; // enclose for i
344 if ((ei = near_enclose(*m_bp, i, t_bs)) == i)
345 {
346 const size_type i2 = m_nnd.rank(i); // next parenthesis in the pioneer bitmap
347 size_type ei2; // enclose for i2
348 if (m_pioneer_bp[i2])
349 { // search enclose in the pioneer bp
350 if ((ei2 = near_enclose(m_pioneer_bp, i2, t_bs)) == i2)
351 {
352 const size_type i3 = m_nnd2.rank(i2); // next parenthesis in the pioneer2 bitmap
353 const size_type ei3 = m_enclose[i3];
354 assert(ei3 < i3); // assert that enclose answer is valid
355 ei2 = m_nnd2.select(ei3 + 1);
356 assert(m_pioneer_bp[ei2] == 1);
357 ei2 = (ei2 / t_bs) * t_bs + t_bs - 1;
358 assert(ei2 < i2);
359 size_type epb2 = excess_pioneer(ei2); // excess of the last parenthesis in the pioneer block
360 const size_type exi2 = excess_pioneer(i2); // excess
361 /* invariant epb2+1 >= exi2 */ assert(epb2 + 1 >= exi2);
362 while (epb2 + 2 != exi2)
363 {
364 if (m_pioneer_bp[ei2--])
365 --epb2;
366 else
367 ++epb2;
368 }
369 ++ei2;
370 }
371 }
372 else
373 {
374 // if the next parenthesis in the pioneer bitmap is an closing parenthesis findopen on m_pioneer_bp
375 ei2 = find_open_in_pioneers(i2);
376 }
377 assert(m_pioneer_bp[ei2] == 1);
378 ei = m_nnd.select(ei2 + 1);
379 assert((*m_bp)[ei] == 1);
380 ei = (ei / t_bs) * t_bs + t_bs - 1;
381 assert(ei < i);
382 size_type epb = excess(ei); // excess of the last parenthesis in the pioneer block
383 /* invariant epb+1 >= exi */ assert(epb + 1 >= exi);
384 while (epb + 2 != exi)
385 {
386 if ((*m_bp)[ei--])
387 --epb;
388 else
389 ++epb;
390 }
391 ++ei;
392 }
393 return ei;
394 }
395
397
404 size_type rr_enclose(const size_type i, const size_type j) const
405 {
406 assert(j > i and j < m_size);
407 const size_type mip1 = find_close(i) + 1;
408 if (mip1 >= j) return size();
409 return rmq_open(mip1, j);
410 }
411
425 size_type rmq_open(const size_type l, const size_type r) const
426 {
427 if (l >= r) return size();
428 size_type min_ex_pos = r;
429
430 if (l / t_bs == r / t_bs) { min_ex_pos = near_rmq_open(*m_bp, l, r); }
431 else
432 { // parentheses pair does not start in the same block
433 // assert( l>1 ); // mi is at greater or equal than 1
434 // note: mi and r are not in the same block
435 size_type k, ex; // helper variables
436 size_type min_ex = excess(r); // + 2*((*m_bp[r])==0); // minimal excess
437 const size_type bl = (l / t_bs + 1) *
438 t_bs; // leftmost position of the leftmost block between the blocks of l and r
439 const size_type br = (r / t_bs) * t_bs; // leftmost position of the block of r
440
441 // 1.2
442 size_type l_ = m_nnd.rank(l); // l_ inclusive
443 size_type r_ = m_nnd.rank(r); // r_ exclusive
444
445 if (r_ > l_)
446 {
447 size_type min_ex_pos_ = r_;
448 if (l_ / t_bs == r_ / t_bs) { min_ex_pos_ = near_rmq_open(m_pioneer_bp, l_, r_); }
449 else if (r_ < m_pioneer_bp.size())
450 {
451 size_type min_ex_ = excess_pioneer(r_) + 2 * (m_pioneer_bp[r_] == 0);
452 const size_type bl_ = (l_ / t_bs + 1) * t_bs;
453 const size_type br_ = (r_ / t_bs) * t_bs;
454
455 // 2.2
456 size_type l__ = m_nnd2.rank(l_); // l__ inclusive
457 size_type r__ = m_nnd2.rank(r_); // r__ exclusive
458 if (r__ > l__)
459 {
460 size_type max_match = 0;
461 k = m_range_max_match(l__, r__ - 1);
462 max_match = m_match[k];
463 if (max_match >= r__)
464 {
465 k = m_nnd2.select(k + 1);
466 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
467 {
468 min_ex_ = ex;
469 min_ex_pos_ = k;
470 }
471 }
472 }
473 if (min_ex_pos_ == r_)
474 {
475 // 2.1
476 k = near_rmq_open(m_pioneer_bp, br_, r_);
477 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
478 {
479 min_ex_ = ex;
480 min_ex_pos_ = k;
481 }
482 }
483 // 2.3
484 k = near_rmq_open(m_pioneer_bp, l_, bl_);
485 if (k < bl_ and (ex = excess_pioneer(k)) < min_ex_)
486 {
487 min_ex_ = ex;
488 min_ex_pos_ = k;
489 }
490 }
491 // 2.4
492 if (min_ex_pos_ < r_)
493 {
494 k = m_nnd.select(min_ex_pos_ + 1);
495 if ((ex = excess(k)) < min_ex)
496 {
497 min_ex = ex;
498 min_ex_pos = k;
499 }
500 }
501 }
502 if (min_ex_pos == r)
503 {
504 // 1.1
505 k = near_rmq_open(*m_bp, br, r);
506 if (k < r and (ex = excess(k)) < min_ex)
507 {
508 min_ex = ex;
509 min_ex_pos = k;
510 }
511 }
512 // 1.3
513 k = near_rmq_open(*m_bp, l, bl);
514 if (k < bl and (ex = excess(k)) < min_ex)
515 {
516 min_ex = ex;
517 min_ex_pos = k;
518 }
519 }
520 // 1.4
521 if (min_ex_pos < r)
522 return min_ex_pos;
523 else
524 return size();
525 }
526
528
534 {
535 assert(j > i and j < m_size);
536 size_type mi = find_close(i); // matching parenthesis to i
537 assert(mi > i and mi < j);
538 assert(find_close(j) > j);
539 size_type k = enclose(j);
540 if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
541 return m_size;
542 size_type kk;
543 do {
544 kk = k;
545 k = enclose(k);
546 } while (k != m_size and k > mi);
547 return kk;
548 }
549
551
555 {
556 assert(l <= r);
557 size_type m = rmq_open(l, r + 1);
558 if (m == l)
559 return l;
560 else
561 { // m>l and m<=r
562 assert(0 == (*m_bp)[m - 1]);
563 size_type prev_open = m_rank_bp(m);
564 if (prev_open == 0 or m_select_bp(prev_open) < l)
565 { // if there exists no opening parenthesis to the left of m which is greater or equal than l
566 return l;
567 }
568 else
569 {
570 return m - 1;
571 }
572 }
573 }
574
576
582 {
583 assert(j > i);
584 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
585 size_type k = rr_enclose(i, j);
586 if (k == size())
587 return enclose(j);
588 else
589 return enclose(k);
590 }
591
593
596 {
597 assert(i < m_size);
598 if (!i) return 0;
599 size_type ones = m_rank_bp(i);
600 if (ones)
601 { // ones > 0
602 assert(m_select_bp(ones) < i);
603 return i - m_select_bp(ones) - 1;
604 }
605 else
606 {
607 return i;
608 }
609 }
610
614 size_type size() const { return m_size; }
615
617
621 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
622 {
623 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
624 size_type written_bytes = 0;
625 written_bytes += m_rank_bp.serialize(out, child, "bp_rank");
626 written_bytes += m_select_bp.serialize(out, child, "bp_select");
627 written_bytes += m_nnd.serialize(out, child, "nearest_neighbor_dictionary");
628
629 written_bytes += m_pioneer_bp.serialize(out, child, "pioneer_bp");
630 written_bytes += m_rank_pioneer_bp.serialize(out, child, "pioneer_bp_rank");
631 written_bytes += m_nnd2.serialize(out, child, "nearest_neighbor_dictionary2");
632 written_bytes += m_match.serialize(out, child, "match_answers");
633 written_bytes += m_enclose.serialize(out, child, "enclose_answers");
634 written_bytes += m_range_max_match.serialize(out, child, "rmq_answers");
635
636 written_bytes += write_member(m_size, out, child, "size");
637 written_bytes += write_member(m_blocks, out, child, "block_cnt");
638 structure_tree::add_size(child, written_bytes);
639 return written_bytes;
640 }
641
643
647 void load(std::istream & in, const bit_vector * bp)
648 {
649 m_bp = bp;
650 m_rank_bp.load(in, m_bp);
651 m_select_bp.load(in, m_bp);
652 m_nnd.load(in);
653
654 m_pioneer_bp.load(in);
655 m_rank_pioneer_bp.load(in, &m_pioneer_bp);
656 m_nnd2.load(in);
657 m_match.load(in);
658 m_enclose.load(in);
659 m_range_max_match.load(in, &m_match);
660 read_member(m_size, in);
661 assert(m_size == bp->size());
662 read_member(m_blocks, in);
663 }
664
665 template <typename archive_t>
666 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
667 {
668 ar(CEREAL_NVP(m_rank_bp));
669 ar(CEREAL_NVP(m_select_bp));
670 ar(CEREAL_NVP(m_nnd));
671 ar(CEREAL_NVP(m_pioneer_bp));
672 ar(CEREAL_NVP(m_rank_pioneer_bp));
673 ar(CEREAL_NVP(m_nnd2));
674 ar(CEREAL_NVP(m_match));
675 ar(CEREAL_NVP(m_enclose));
676 ar(CEREAL_NVP(m_range_max_match));
677 ar(CEREAL_NVP(m_size));
678 ar(CEREAL_NVP(m_blocks));
679 }
680
681 template <typename archive_t>
682 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
683 {
684 ar(CEREAL_NVP(m_rank_bp));
685 ar(CEREAL_NVP(m_select_bp));
686 ar(CEREAL_NVP(m_nnd));
687 ar(CEREAL_NVP(m_pioneer_bp));
688 ar(CEREAL_NVP(m_rank_pioneer_bp));
689 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
690 ar(CEREAL_NVP(m_nnd2));
691 ar(CEREAL_NVP(m_match));
692 ar(CEREAL_NVP(m_enclose));
693 ar(CEREAL_NVP(m_range_max_match));
694 m_range_max_match.set_vector(&m_match);
695 ar(CEREAL_NVP(m_size));
696 ar(CEREAL_NVP(m_blocks));
697 }
698
700 bool operator==(bp_support_g const & other) const noexcept
701 {
702 return (m_rank_bp == other.m_rank_bp) && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd) &&
703 (m_pioneer_bp == other.m_pioneer_bp) && (m_rank_pioneer_bp == other.m_rank_pioneer_bp) &&
704 (m_nnd2 == other.m_nnd2) && (m_match == other.m_match) && (m_enclose == other.m_enclose) &&
705 (m_range_max_match == other.m_range_max_match) && (m_size == other.m_size) &&
706 (m_blocks == other.m_blocks);
707 }
708
710 bool operator!=(bp_support_g const & other) const noexcept { return !(*this == other); }
711};
712
713} // namespace sdsl
714
715#endif
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
A class that provides support for bit_vectors that represent a BP sequence.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type rmq_open(const size_type l, const size_type r) const
Search the interval [l,r-1] for an opening parenthesis, say i, such that find_close(i) >= r.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
size_type rmq(size_type l, size_type r) const
The range minimum query (rmq) returns the index of the parenthesis with minimal excess in the range .
size_type excess(size_type i) const
Calculates the excess value at index i.
size_type rr_enclose(const size_type i, const size_type j) const
The range restricted enclose operation.
void set_vector(const bit_vector *bp)
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
const rank_type & bp_rank
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_g to a stream.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
const select_type & bp_select
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which procede position i in the balanced parentheses sequence.
bp_support_g(bp_support_g &&bp_support)
Move constructor.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_g for a bit_vector v.
size_type size() const
The size of the supported balanced parentheses sequence.
bp_support_g & operator=(bp_support_g &&bp_support)
Assignment operator.
bp_support_g & operator=(const bp_support_g &bp_support)
Assignment operator.
bit_vector::size_type size_type
bp_support_g(const bit_vector *bp=nullptr)
Constructor.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
size_type find_open_in_pioneers(size_type i) const
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
bool operator!=(bp_support_g const &other) const noexcept
Inequality operator.
size_type enclose(size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair...
bool operator==(bp_support_g const &other) const noexcept
Equality operator.
size_type rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
bp_support_g(const bp_support_g &v)
Copy constructor.
int_vector_size_type size_type
Definition: int_vector.hpp:229
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:521
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)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
uint64_t near_rmq_open(const bit_vector &bp, const uint64_t begin, const uint64_t end)
void calculate_matches(const bit_vector &bp, int_vector &matches)
find_open/find_close for closing/opening parentheses.
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
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:53
bit_vector calculate_pioneers_bitmap(const bit_vector &bp, uint64_t block_size)
Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)
uint64_t near_find_open(const bit_vector &bp, uint64_t i, const uint64_t block_size)
uint64_t near_find_close(const bit_vector &bp, const uint64_t i, const uint64_t block_size)
void calculate_enclose(const bit_vector &bp, int_vector &enclose)
Calculates enclose answers for a balanced parentheses sequence.
uint64_t near_enclose(const bit_vector &bp, uint64_t i, const uint64_t block_size)
Find the opening parenthesis of the enclosing pair if this parenthesis is near.
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
rmq_support.hpp contains different range minimum support data structures.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.