SDSL 3.0.2
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 <assert.h>
12#include <iosfwd>
13#include <stdint.h>
14#include <string>
15
17#include <sdsl/cereal.hpp>
18#include <sdsl/int_vector.hpp>
19#include <sdsl/io.hpp>
25#include <sdsl/util.hpp>
26
27namespace sdsl
28{
29
31
54template <class t_nnd = nearest_neighbour_dictionary<30>,
55 class t_rank = rank_support_v5<>,
56 class t_select = select_support_mcl<>,
57 class t_rmq = range_maximum_support_sparse_table<>,
58 uint32_t t_bs = 840>
60{
61 static_assert(t_bs > 2, "bp_support_g: block size must be greater than 2.");
62
63public:
65 typedef t_nnd nnd_type;
66 typedef t_rank rank_type;
67 typedef t_select select_type;
68 typedef t_rmq rmq_type;
69
70private:
71 bit_vector const * m_bp; // the supported BP sequence as bit_vector
72 rank_type m_rank_bp; // rank support for the BP sequence => see excess() and rank()
73 select_type m_select_bp; // select support for the BP sequence => see select()
74
75 nnd_type m_nnd; // nearest neighbour dictionary for pioneers bit_vector
76
77 bit_vector m_pioneer_bp; // first level of recursion: BP sequence of the pioneers
78 rank_type m_rank_pioneer_bp; // rank for the BP sequence of the pioneers
79 nnd_type m_nnd2; // nearest neighbour dictionary for pioneers of pioneers bit_vector
80 int_vector<> m_match; //
81 int_vector<> m_enclose; //
82 rmq_type m_range_max_match; // range maximum support for m_match
83
84 size_type m_size;
85 size_type m_blocks; // number of blocks
86
90 inline size_type excess_pioneer(size_type i) const
91 {
92 return (m_rank_pioneer_bp(i + 1) << 1) - i - 1;
93 }
94
95public:
96 rank_type const & bp_rank = m_rank_bp;
97 select_type const & bp_select = m_select_bp;
98
100 explicit bp_support_g(bit_vector const * bp = nullptr) :
101 m_bp(bp),
102 m_size(bp == nullptr ? 0 : bp->size()),
103 m_blocks((m_size + t_bs - 1) / t_bs)
104 {
105 if (bp == nullptr)
106 return;
107 util::init_support(m_rank_bp, bp);
108 util::init_support(m_select_bp, bp);
109 bit_vector pioneer = calculate_pioneers_bitmap(*m_bp, t_bs);
110 m_nnd = nnd_type(pioneer);
111 m_pioneer_bp.resize(m_nnd.ones());
112 for (size_type i = 1; i <= m_nnd.ones(); ++i)
113 m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
114 util::init_support(m_rank_pioneer_bp, &m_pioneer_bp);
115 pioneer = calculate_pioneers_bitmap(m_pioneer_bp, t_bs);
116 m_nnd2 = nnd_type(pioneer);
117
118 bit_vector pioneer_bp2 = bit_vector(m_nnd2.ones());
119 for (size_type i = 1; i <= m_nnd2.ones(); ++i)
120 pioneer_bp2[i - 1] = m_pioneer_bp[m_nnd2.select(i)];
121 calculate_matches(pioneer_bp2, m_match);
122 calculate_enclose(pioneer_bp2, m_enclose);
123 m_range_max_match = rmq_type(&m_match);
124 }
125
128 m_bp(v.m_bp),
129 m_rank_bp(v.m_rank_bp),
130 m_select_bp(v.m_select_bp),
131 m_nnd(v.m_nnd),
132 m_pioneer_bp(v.m_pioneer_bp),
133 m_rank_pioneer_bp(v.m_rank_pioneer_bp),
134 m_nnd2(v.m_nnd2),
135 m_match(v.m_match),
136 m_enclose(v.m_enclose),
137 m_range_max_match(v.m_range_max_match),
138 m_size(v.m_size),
139 m_blocks(v.m_blocks)
140 {
141 m_rank_bp.set_vector(m_bp);
142 m_select_bp.set_vector(m_bp);
143 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
144 m_range_max_match.set_vector(&m_match);
145 }
146
149 {
150 *this = std::move(bp_support);
151 }
152
154 bp_support_g & operator=(bp_support_g const & bp_support)
155 {
156 if (this != &bp_support)
157 {
158 bp_support_g tmp(bp_support);
159 *this = std::move(tmp);
160 }
161 return *this;
162 }
163
166 {
167 if (this != &bp_support)
168 {
169 m_bp = std::move(bp_support.m_bp);
170 m_rank_bp = std::move(bp_support.m_rank_bp);
171 m_rank_bp.set_vector(m_bp);
172 m_select_bp = std::move(bp_support.m_select_bp);
173 m_select_bp.set_vector(m_bp);
174
175 m_nnd = std::move(bp_support.m_nnd);
176
177 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
178 m_rank_pioneer_bp = std::move(bp_support.m_rank_pioneer_bp);
179 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
180 m_nnd2 = std::move(bp_support.m_nnd2);
181 m_match = std::move(bp_support.m_match);
182 m_enclose = std::move(bp_support.m_enclose);
183 m_range_max_match = std::move(bp_support.m_range_max_match);
184 m_range_max_match.set_vector(&m_match);
185
186 m_size = std::move(bp_support.m_size);
187 m_blocks = std::move(bp_support.m_blocks);
188 }
189 return *this;
190 }
191
192 void set_vector(bit_vector const * bp)
193 {
194 m_bp = bp;
195 m_rank_bp.set_vector(bp);
196 m_select_bp.set_vector(bp);
197 }
198
202 inline size_type excess(size_type i) const
203 {
204 return (m_rank_bp(i + 1) << 1) - i - 1;
205 }
206
211 {
212 return m_rank_bp(i + 1);
213 }
214
221 {
222 return m_select_bp(i);
223 }
224
232 {
233 assert(i < m_size);
234 if (!(*m_bp)[i])
235 { // if there is a closing parenthesis at index i return i
236 return i;
237 }
238 size_type mi = 0; // match for i
239 if ((mi = near_find_close(*m_bp, i, t_bs)) == i)
240 {
241 const size_type i2 = m_nnd.rank(i + 1) - 1; // lemma that this gives us an opening pioneer
242 assert(m_pioneer_bp[i2] == 1); // assert that i2 is an opening parenthesis
243 size_type mi2 = 0; // match for i2
244 if ((mi2 = near_find_close(m_pioneer_bp, i2, t_bs)) == i2)
245 {
246 const size_type i3 = m_nnd2.rank(i2 + 1) - 1;
247 const size_type mi3 = m_match[i3];
248 assert(mi3 > i3); // assert that i3 is an opening parenthesis
249 mi2 = m_nnd2.select(mi3 + 1); // matching pioneer position in pioneer_bp
250 mi2 = (mi2 / t_bs) * t_bs;
251 size_type epb = excess_pioneer(mi2); // excess of first parenthesis in the pioneer block
252 const size_type ei = excess_pioneer(i2); // excess of pioneer
253 /* invariant: epb >= ei-1 */ assert(epb + 1 >= ei);
254 while (epb + 1 != ei)
255 {
256 assert(mi2 < m_pioneer_bp.size());
257 if (m_pioneer_bp[++mi2])
258 ++epb;
259 else
260 --epb;
261 }
262 }
263 mi = m_nnd.select(mi2 + 1); /* matching pioneer position in bp */
264 assert((*m_bp)[mi] == 0);
265 mi = (mi / t_bs) * t_bs;
266 size_type epb = excess(mi); // excess of first parenthesis in the pioneer block
267 const size_type ei = excess(i); // excess at position i
268 /* invariant: epb >= ei-1 */ assert(epb + 1 >= ei);
269 while (epb + 1 != ei)
270 {
271 assert(mi < m_size);
272 if ((*m_bp)[++mi])
273 ++epb;
274 else
275 --epb;
276 }
277 }
278 return mi;
279 }
280
282
288 {
289 assert(i < m_size);
290 if ((*m_bp)[i])
291 { // if there is a opening parenthesis at index i return i
292 return i;
293 }
294 size_type mi = 0; // match for i
295 if ((mi = near_find_open(*m_bp, i, t_bs)) == i)
296 {
297 const size_type i2 = m_nnd.rank(i); // lemma that this gives us an closing pioneer
298 assert(m_pioneer_bp[i2] == 0); // assert that i2 is an opening parenthesis
299 const size_type mi2 = find_open_in_pioneers(i2);
300 assert(m_pioneer_bp[mi2] == 1);
301 mi = m_nnd.select(mi2 + 1); /* matching pioneer position in bp */
302 assert((*m_bp)[mi] == 1);
303 mi = (mi / t_bs) * t_bs + t_bs - 1;
304 assert(mi < i);
305 size_type epb = excess(mi); // excess of last parenthesis in the pioneer block
306 const size_type ei = excess(i); // excess at position i
307 /*invariant: epb >= ei+1*/ assert(epb >= ei + 1);
308 while (epb != ei)
309 {
310 assert(mi < m_size);
311 if ((*m_bp)[mi--])
312 --epb;
313 else
314 ++epb;
315 }
316 ++mi;
317 }
318 return mi;
319 }
320
322 {
323 size_type mi = 0; // match for i
324 if ((mi = near_find_open(m_pioneer_bp, i, t_bs)) == i)
325 {
326 const size_type i3 = m_nnd2.rank(i);
327 const size_type mi3 = m_match[i3];
328 assert(mi3 < i3); // assert that i3 is an closing parenthesis
329 mi = m_nnd2.select(mi3 + 1); // matching pioneer position in pioneer_bp
330 mi = (mi / t_bs) * t_bs + t_bs - 1;
331 size_type epb2 = excess_pioneer(mi); // excess of last parenthesis in the pioneer block
332 const size_type ei = excess_pioneer(i); // excess of pioneer
333 /* invariant: epb2 >= ei+1 */ assert(epb2 >= ei + 1);
334 while (epb2 != ei)
335 {
336 assert(mi < m_pioneer_bp.size());
337 if (m_pioneer_bp[mi--])
338 --epb2;
339 else
340 ++epb2;
341 }
342 ++mi;
343 }
344 return mi;
345 }
346
349
354 {
355 assert(i < m_size);
356 if (!(*m_bp)[i])
357 { // if there is closing parenthesis at position i
358 return find_open(i);
359 }
360 const size_type exi = excess(i);
361 if (exi == 1) // if i is not enclosed by a parentheses pair..
362 return size();
363 size_type ei; // enclose for i
364 if ((ei = near_enclose(*m_bp, i, t_bs)) == i)
365 {
366 const size_type i2 = m_nnd.rank(i); // next parenthesis in the pioneer bitmap
367 size_type ei2; // enclose for i2
368 if (m_pioneer_bp[i2])
369 { // search enclose in the pioneer bp
370 if ((ei2 = near_enclose(m_pioneer_bp, i2, t_bs)) == i2)
371 {
372 const size_type i3 = m_nnd2.rank(i2); // next parenthesis in the pioneer2 bitmap
373 const size_type ei3 = m_enclose[i3];
374 assert(ei3 < i3); // assert that enclose answer is valid
375 ei2 = m_nnd2.select(ei3 + 1);
376 assert(m_pioneer_bp[ei2] == 1);
377 ei2 = (ei2 / t_bs) * t_bs + t_bs - 1;
378 assert(ei2 < i2);
379 size_type epb2 = excess_pioneer(ei2); // excess of the last parenthesis in the pioneer block
380 const size_type exi2 = excess_pioneer(i2); // excess
381 /* invariant epb2+1 >= exi2 */ assert(epb2 + 1 >= exi2);
382 while (epb2 + 2 != exi2)
383 {
384 if (m_pioneer_bp[ei2--])
385 --epb2;
386 else
387 ++epb2;
388 }
389 ++ei2;
390 }
391 }
392 else
393 {
394 // if the next parenthesis in the pioneer bitmap is an closing parenthesis findopen on m_pioneer_bp
395 ei2 = find_open_in_pioneers(i2);
396 }
397 assert(m_pioneer_bp[ei2] == 1);
398 ei = m_nnd.select(ei2 + 1);
399 assert((*m_bp)[ei] == 1);
400 ei = (ei / t_bs) * t_bs + t_bs - 1;
401 assert(ei < i);
402 size_type epb = excess(ei); // excess of the last parenthesis in the pioneer block
403 /* invariant epb+1 >= exi */ assert(epb + 1 >= exi);
404 while (epb + 2 != exi)
405 {
406 if ((*m_bp)[ei--])
407 --epb;
408 else
409 ++epb;
410 }
411 ++ei;
412 }
413 return ei;
414 }
415
417
424 size_type rr_enclose(const size_type i, const size_type j) const
425 {
426 assert(j > i and j < m_size);
427 const size_type mip1 = find_close(i) + 1;
428 if (mip1 >= j)
429 return size();
430 return rmq_open(mip1, j);
431 }
432
446 size_type rmq_open(const size_type l, const size_type r) const
447 {
448 if (l >= r)
449 return size();
450 size_type min_ex_pos = r;
451
452 if (l / t_bs == r / t_bs)
453 {
454 min_ex_pos = near_rmq_open(*m_bp, l, r);
455 }
456 else
457 { // parentheses pair does not start in the same block
458 // assert( l>1 ); // mi is at greater or equal than 1
459 // note: mi and r are not in the same block
460 size_type k, ex; // helper variables
461 size_type min_ex = excess(r); // + 2*((*m_bp[r])==0); // minimal excess
462 const size_type bl =
463 (l / t_bs + 1) * t_bs; // leftmost position of the leftmost block between the blocks of l and r
464 const size_type br = (r / t_bs) * t_bs; // leftmost position of the block of r
465
466 // 1.2
467 size_type l_ = m_nnd.rank(l); // l_ inclusive
468 size_type r_ = m_nnd.rank(r); // r_ exclusive
469
470 if (r_ > l_)
471 {
472 size_type min_ex_pos_ = r_;
473 if (l_ / t_bs == r_ / t_bs)
474 {
475 min_ex_pos_ = near_rmq_open(m_pioneer_bp, l_, r_);
476 }
477 else if (r_ < m_pioneer_bp.size())
478 {
479 size_type min_ex_ = excess_pioneer(r_) + 2 * (m_pioneer_bp[r_] == 0);
480 const size_type bl_ = (l_ / t_bs + 1) * t_bs;
481 const size_type br_ = (r_ / t_bs) * t_bs;
482
483 // 2.2
484 size_type l__ = m_nnd2.rank(l_); // l__ inclusive
485 size_type r__ = m_nnd2.rank(r_); // r__ exclusive
486 if (r__ > l__)
487 {
488 size_type max_match = 0;
489 k = m_range_max_match(l__, r__ - 1);
490 max_match = m_match[k];
491 if (max_match >= r__)
492 {
493 k = m_nnd2.select(k + 1);
494 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
495 {
496 min_ex_ = ex;
497 min_ex_pos_ = k;
498 }
499 }
500 }
501 if (min_ex_pos_ == r_)
502 {
503 // 2.1
504 k = near_rmq_open(m_pioneer_bp, br_, r_);
505 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
506 {
507 min_ex_ = ex;
508 min_ex_pos_ = k;
509 }
510 }
511 // 2.3
512 k = near_rmq_open(m_pioneer_bp, l_, bl_);
513 if (k < bl_ and (ex = excess_pioneer(k)) < min_ex_)
514 {
515 min_ex_ = ex;
516 min_ex_pos_ = k;
517 }
518 }
519 // 2.4
520 if (min_ex_pos_ < r_)
521 {
522 k = m_nnd.select(min_ex_pos_ + 1);
523 if ((ex = excess(k)) < min_ex)
524 {
525 min_ex = ex;
526 min_ex_pos = k;
527 }
528 }
529 }
530 if (min_ex_pos == r)
531 {
532 // 1.1
533 k = near_rmq_open(*m_bp, br, r);
534 if (k < r and (ex = excess(k)) < min_ex)
535 {
536 min_ex = ex;
537 min_ex_pos = k;
538 }
539 }
540 // 1.3
541 k = near_rmq_open(*m_bp, l, bl);
542 if (k < bl and (ex = excess(k)) < min_ex)
543 {
544 min_ex = ex;
545 min_ex_pos = k;
546 }
547 }
548 // 1.4
549 if (min_ex_pos < r)
550 return min_ex_pos;
551 else
552 return size();
553 }
554
556
562 {
563 assert(j > i and j < m_size);
564 size_type mi = find_close(i); // matching parenthesis to i
565 assert(mi > i and mi < j);
566 assert(find_close(j) > j);
567 size_type k = enclose(j);
568 if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
569 return m_size;
570 size_type kk;
571 do
572 {
573 kk = k;
574 k = enclose(k);
575 }
576 while (k != m_size and k > mi);
577 return kk;
578 }
579
581
585 {
586 assert(l <= r);
587 size_type m = rmq_open(l, r + 1);
588 if (m == l)
589 return l;
590 else
591 { // m>l and m<=r
592 assert(0 == (*m_bp)[m - 1]);
593 size_type prev_open = m_rank_bp(m);
594 if (prev_open == 0 or m_select_bp(prev_open) < l)
595 { // if there exists no opening parenthesis to the left of m which is greater or equal than l
596 return l;
597 }
598 else
599 {
600 return m - 1;
601 }
602 }
603 }
604
606
612 {
613 assert(j > i);
614 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
615 size_type k = rr_enclose(i, j);
616 if (k == size())
617 return enclose(j);
618 else
619 return enclose(k);
620 }
621
623
626 {
627 assert(i < m_size);
628 if (!i)
629 return 0;
630 size_type ones = m_rank_bp(i);
631 if (ones)
632 { // ones > 0
633 assert(m_select_bp(ones) < i);
634 return i - m_select_bp(ones) - 1;
635 }
636 else
637 {
638 return i;
639 }
640 }
641
646 {
647 return m_size;
648 }
649
651
655 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
656 {
657 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
658 size_type written_bytes = 0;
659 written_bytes += m_rank_bp.serialize(out, child, "bp_rank");
660 written_bytes += m_select_bp.serialize(out, child, "bp_select");
661 written_bytes += m_nnd.serialize(out, child, "nearest_neighbor_dictionary");
662
663 written_bytes += m_pioneer_bp.serialize(out, child, "pioneer_bp");
664 written_bytes += m_rank_pioneer_bp.serialize(out, child, "pioneer_bp_rank");
665 written_bytes += m_nnd2.serialize(out, child, "nearest_neighbor_dictionary2");
666 written_bytes += m_match.serialize(out, child, "match_answers");
667 written_bytes += m_enclose.serialize(out, child, "enclose_answers");
668 written_bytes += m_range_max_match.serialize(out, child, "rmq_answers");
669
670 written_bytes += write_member(m_size, out, child, "size");
671 written_bytes += write_member(m_blocks, out, child, "block_cnt");
672 structure_tree::add_size(child, written_bytes);
673 return written_bytes;
674 }
675
677
681 void load(std::istream & in, bit_vector const * bp)
682 {
683 m_bp = bp;
684 m_rank_bp.load(in, m_bp);
685 m_select_bp.load(in, m_bp);
686 m_nnd.load(in);
687
688 m_pioneer_bp.load(in);
689 m_rank_pioneer_bp.load(in, &m_pioneer_bp);
690 m_nnd2.load(in);
691 m_match.load(in);
692 m_enclose.load(in);
693 m_range_max_match.load(in, &m_match);
694 read_member(m_size, in);
695 assert(m_size == bp->size());
696 read_member(m_blocks, in);
697 }
698
699 template <typename archive_t>
700 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
701 {
702 ar(CEREAL_NVP(m_rank_bp));
703 ar(CEREAL_NVP(m_select_bp));
704 ar(CEREAL_NVP(m_nnd));
705 ar(CEREAL_NVP(m_pioneer_bp));
706 ar(CEREAL_NVP(m_rank_pioneer_bp));
707 ar(CEREAL_NVP(m_nnd2));
708 ar(CEREAL_NVP(m_match));
709 ar(CEREAL_NVP(m_enclose));
710 ar(CEREAL_NVP(m_range_max_match));
711 ar(CEREAL_NVP(m_size));
712 ar(CEREAL_NVP(m_blocks));
713 }
714
715 template <typename archive_t>
716 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
717 {
718 ar(CEREAL_NVP(m_rank_bp));
719 ar(CEREAL_NVP(m_select_bp));
720 ar(CEREAL_NVP(m_nnd));
721 ar(CEREAL_NVP(m_pioneer_bp));
722 ar(CEREAL_NVP(m_rank_pioneer_bp));
723 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
724 ar(CEREAL_NVP(m_nnd2));
725 ar(CEREAL_NVP(m_match));
726 ar(CEREAL_NVP(m_enclose));
727 ar(CEREAL_NVP(m_range_max_match));
728 m_range_max_match.set_vector(&m_match);
729 ar(CEREAL_NVP(m_size));
730 ar(CEREAL_NVP(m_blocks));
731 }
732
734 bool operator==(bp_support_g const & other) const noexcept
735 {
736 return (m_rank_bp == other.m_rank_bp) && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd)
737 && (m_pioneer_bp == other.m_pioneer_bp) && (m_rank_pioneer_bp == other.m_rank_pioneer_bp)
738 && (m_nnd2 == other.m_nnd2) && (m_match == other.m_match) && (m_enclose == other.m_enclose)
739 && (m_range_max_match == other.m_range_max_match) && (m_size == other.m_size)
740 && (m_blocks == other.m_blocks);
741 }
742
744 bool operator!=(bp_support_g const & other) const noexcept
745 {
746 return !(*this == other);
747 }
748};
749
750} // namespace sdsl
751
752#endif
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
cereal.hpp offers cereal support
#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)
bp_support_g(bp_support_g const &v)
Copy constructor.
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 .
rank_type const & bp_rank
void load(std::istream &in, bit_vector const *bp)
Load the bp_support_g for a bit_vector v.
bp_support_g & operator=(bp_support_g const &bp_support)
Assignment operator.
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.
bp_support_g(bit_vector const *bp=nullptr)
Constructor.
select_type const & bp_select
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_g to a stream.
void set_vector(bit_vector const *bp)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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.
size_type size() const
The size of the supported balanced parentheses sequence.
bp_support_g & operator=(bp_support_g &&bp_support)
Assignment operator.
bit_vector::size_type size_type
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.
int_vector_size_type size_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
static 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)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
bit_vector calculate_pioneers_bitmap(bit_vector const &bp, uint64_t block_size)
Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)
uint64_t near_find_open(bit_vector const &bp, uint64_t i, const uint64_t block_size)
void calculate_enclose(bit_vector const &bp, int_vector &enclose)
Calculates enclose answers for a balanced parentheses sequence.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
uint64_t near_enclose(bit_vector const &bp, uint64_t i, const uint64_t block_size)
Find the opening parenthesis of the enclosing pair if this parenthesis is near.
uint64_t near_rmq_open(bit_vector const &bp, const uint64_t begin, const uint64_t end)
void read_member(T &t, std::istream &in)
Definition io.hpp:119
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
uint64_t near_find_close(bit_vector const &bp, const uint64_t i, const uint64_t block_size)
void calculate_matches(bit_vector const &bp, int_vector &matches)
find_open/find_close for closing/opening parentheses.
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support_v5.hpp contains rank_support_v5.5
rmq_support_sparse_table.hpp contains the class rmq_support_sparse_table.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
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.