SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
bp_support_sada.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
9#ifndef INCLUDED_SDSL_BP_SUPPORT_SADA
10#define INCLUDED_SDSL_BP_SUPPORT_SADA
11
12#include <assert.h>
13#include <stdint.h>
14
16#include <sdsl/int_vector.hpp>
20#ifndef NDEBUG
21# include <algorithm>
22#endif
23#include <iostream>
24#include <string>
25
26#include <sdsl/bits.hpp>
27#include <sdsl/cereal.hpp>
28#include <sdsl/io.hpp>
30#include <sdsl/util.hpp>
31
32namespace sdsl
33{
34
36
63template <uint32_t t_sml_blk = 256,
64 uint32_t t_med_deg = 32,
65 class t_rank = rank_support_v5<>,
66 class t_select = select_support_mcl<>>
68{
69public:
74 typedef t_rank rank_type;
75 typedef t_select select_type;
76
77private:
78 static_assert(0 < t_sml_blk, "bp_support_sada: t_sml_blk should be greater than 0!");
79 bit_vector const * m_bp = nullptr; // the supported balanced parentheses sequence as bit_vector
80 rank_type m_bp_rank; // RS for the BP sequence => see excess() and rank()
81 select_type m_bp_select; // SS for the BP sequence => see select()
82
83 sml_block_array_type m_sml_block_min_max;
84 med_block_array_type m_med_block_min_max;
85
86 size_type m_size = 0; // number of supported parentheses
87 size_type m_sml_blocks = 0; // number of small sized blocks
88 size_type m_med_blocks = 0; // number of medium sized blocks
89 size_type m_med_inner_blocks = 0; // number of inner nodes in the min max tree of the medium sized blocks
90//#define USE_CACHE
91#ifdef USE_CACHE
92 mutable fast_cache find_close_cache;
93 mutable fast_cache find_open_cache;
94 mutable fast_cache select_cache;
95#endif
96
97 static inline size_type sml_block_idx(size_type i)
98 {
99 return i / t_sml_blk;
100 }
101
102 static inline size_type med_block_idx(size_type i)
103 {
104 return i / (t_sml_blk * t_med_deg);
105 }
106
107 static inline bool is_root(size_type v)
108 {
109 return v == 0;
110 }
111
112 static inline bool is_left_child(size_type v)
113 {
114 assert(!is_root(v));
115 return v % 2;
116 }
117
118 static inline bool is_right_child(size_type v)
119 {
120 assert(!is_root(v));
121 return !(v % 2);
122 }
123
124 static inline size_type parent(size_type v)
125 {
126 assert(!is_root(v));
127 return (v - 1) / 2;
128 }
129
130 static inline size_type left_child(size_type v)
131 {
132 return 2 * v + 1;
133 }
134
135 static inline size_type right_child(size_type v)
136 {
137 return 2 * v + 2;
138 }
139
140 inline bool node_exists(size_type v) const
141 {
142 return v < (m_med_inner_blocks + m_med_blocks);
143 }
144
145 static inline size_type right_sibling(size_type v)
146 {
147 return ++v;
148 }
149
150 static inline size_type left_sibling(size_type v)
151 {
152 return --v;
153 }
154
155 inline bool is_leaf(size_type v) const
156 {
157 return v >= m_med_inner_blocks;
158 }
159
160 inline difference_type min_value(size_type v) const
161 {
162 return m_size - ((difference_type)m_med_block_min_max[2 * v]);
163 }
164
165 inline difference_type max_value(size_type v) const
166 {
167 return m_med_block_min_max[2 * v + 1] - m_size;
168 }
169
170 inline difference_type sml_min_value(size_type sml_block) const
171 {
172 return (1 - ((difference_type)m_sml_block_min_max[sml_block << 1]));
173 }
174
175 inline difference_type sml_max_value(size_type sml_block) const
176 {
177 return (difference_type)m_sml_block_min_max[(sml_block << 1) + 1] - 1;
178 }
179
180 void print_node(size_type v) const
181 {
182 std::cout << "v = " << v << " (" << min_value(v) << ", " << max_value(v) << ")";
183 if (is_leaf(v))
184 {
185 std::cout << " range: [" << (v - m_med_inner_blocks) * t_med_deg * t_sml_blk << ","
186 << (v - m_med_inner_blocks + 1) * t_med_deg * t_sml_blk - 1 << "]";
187 }
188 std::cout << std::endl;
189 }
190
192
198 size_type fwd_excess(size_type i, difference_type rel) const
199 {
200 size_type j;
201 // (1) search the small block for the answer
202 if ((j = near_fwd_excess(*m_bp, i + 1, rel, t_sml_blk)) > i)
203 {
204 return j;
205 }
206 difference_type desired_excess = excess(i) + rel;
207 // (2) scan the small blocks of the current median block for an answer
208 if ((j = fwd_excess_in_med_block(sml_block_idx(i) + 1, desired_excess)) != size())
209 {
210 return j;
211 }
212 // (3) search the min-max tree of the medium blocks for the right med block
213 if (med_block_idx(i) == m_med_blocks) // if we are already in the last medium block => we are done
214 return size();
215 size_type v = m_med_inner_blocks + med_block_idx(i);
216 // (3 a) go up the tree
217 while (!is_root(v))
218 {
219 if (is_left_child(v))
220 { // if the node is a left child
221 v = right_sibling(v); // choose right sibling
222 if (min_value(v) <= desired_excess and desired_excess <= max_value(v)) // found solution
223 break;
224 }
225 v = parent(v); // choose parent
226 }
227 // (3 b) go down the tree
228 if (!is_root(v))
229 { // found solution for the query
230 while (!is_leaf(v))
231 {
232 v = left_child(v); // choose left child
233 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
234 {
235 v = right_sibling(v); // choose right child == right sibling of the left child
236 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
237 }
238 }
239 return fwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg, desired_excess);
240 }
241 // no solution found
242 return size();
243 }
244
246
251 size_type bwd_excess(size_type i, difference_type rel) const
252 {
253 size_type j;
254 if (i == 0)
255 {
256 return rel == 0 ? -1 : size();
257 }
258 // (1) search the small block for the answer
259 if ((j = near_bwd_excess(*m_bp, i - 1, rel, t_sml_blk)) < i or j == (size_type)-1)
260 {
261 return j;
262 }
263 difference_type desired_excess = excess(i) + rel;
264 // (2) scan the small blocks of the current median block for an answer
265 if ((j = bwd_excess_in_med_block(sml_block_idx(i) - 1, desired_excess)) != size())
266 {
267 return j;
268 }
269 // (3) search the min-max tree of the medium blocks for the right med block
270 if (med_block_idx(i) == 0)
271 { // if we are already in the first medium block => we are done
272 if (desired_excess == 0)
273 return -1;
274 return size();
275 }
276 size_type v = m_med_inner_blocks + med_block_idx(i);
277 // (3 a) go up the tree
278 while (!is_root(v))
279 {
280 if (is_right_child(v))
281 { // if the node is a right child
282 v = left_sibling(v); // choose left sibling
283 if (min_value(v) <= desired_excess and desired_excess <= max_value(v)) // found solution
284 break;
285 }
286 v = parent(v); // choose parent
287 }
288 // (3 b) go down the tree
289 if (!is_root(v))
290 { // found solution for the query
291 while (!is_leaf(v))
292 {
293 v = right_child(v); // choose child
294 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
295 {
296 v = left_sibling(v); // choose left child == left sibling of the right child
297 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
298 }
299 }
300 return bwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg + (t_med_deg - 1), desired_excess);
301 }
302 else if (desired_excess == 0)
303 {
304 return -1;
305 }
306 // no solution found
307 return size();
308 }
309
312 size_type bwd_excess_in_med_block(size_type sml_block_idx, difference_type desired_excess) const
313 {
314 // get the first small block in the medium block right to the current med block
315 size_type first_sml_block_in_med_block = (med_block_idx(sml_block_idx * t_sml_blk)) * t_med_deg;
316
317 while ((sml_block_idx + 1) and sml_block_idx >= first_sml_block_in_med_block)
318 {
319 difference_type ex = (sml_block_idx == 0) ? 0 : excess(sml_block_idx * t_sml_blk - 1);
320 difference_type min_ex = ex + (1 - ((difference_type)m_sml_block_min_max[2 * sml_block_idx]));
321 difference_type max_ex = ex + (m_sml_block_min_max[2 * sml_block_idx + 1] - 1);
322
323 if (min_ex <= desired_excess and desired_excess <= max_ex)
324 {
325 size_type j = near_bwd_excess(*m_bp,
326 (sml_block_idx + 1) * t_sml_blk - 1,
327 desired_excess - excess((sml_block_idx + 1) * t_sml_blk),
328 t_sml_blk);
329 return j;
330 }
331 --sml_block_idx;
332 }
333 if (sml_block_idx == 0 and desired_excess == 0)
334 return -1;
335 return size();
336 }
337
340 size_type fwd_excess_in_med_block(size_type sml_block_idx, difference_type desired_excess) const
341 {
342 // get the first small block in the medium block right to the current med block
343 size_type first_sml_block_nr_in_next_med_block = (med_block_idx(sml_block_idx * t_sml_blk) + 1) * t_med_deg;
344 if (first_sml_block_nr_in_next_med_block > m_sml_blocks)
345 first_sml_block_nr_in_next_med_block = m_sml_blocks;
346
347 assert(sml_block_idx > 0);
348 while (sml_block_idx < first_sml_block_nr_in_next_med_block)
349 {
350 difference_type ex = excess(sml_block_idx * t_sml_blk - 1);
351 difference_type min_ex = ex + (1 - ((difference_type)m_sml_block_min_max[2 * sml_block_idx]));
352 difference_type max_ex = ex + m_sml_block_min_max[2 * sml_block_idx + 1] - 1;
353 if (min_ex <= desired_excess and desired_excess <= max_ex)
354 {
355 size_type j = near_fwd_excess(*m_bp, sml_block_idx * t_sml_blk, desired_excess - ex, t_sml_blk);
356 return j;
357 }
358 ++sml_block_idx;
359 }
360 return size();
361 }
362
363public:
364 rank_type const & bp_rank = m_bp_rank;
365 select_type const & bp_select = m_bp_select;
366 sml_block_array_type const & sml_block_min_max = m_sml_block_min_max;
368 med_block_array_type const & med_block_min_max = m_med_block_min_max;
370
373
376 m_bp(v.m_bp),
377 m_bp_rank(v.m_bp_rank),
378 m_bp_select(v.m_bp_select),
379 m_sml_block_min_max(v.m_sml_block_min_max),
380 m_med_block_min_max(v.m_med_block_min_max),
381 m_size(v.m_size),
382 m_sml_blocks(v.m_sml_blocks),
383 m_med_blocks(v.m_med_blocks),
384 m_med_inner_blocks(v.m_med_inner_blocks)
385 {
386 m_bp_rank.set_vector(m_bp);
387 m_bp_select.set_vector(m_bp);
388 }
389
392 {
393 *this = std::move(bp_support);
394 }
395
398 {
399 if (this != &bp_support)
400 {
401 m_bp = std::move(bp_support.m_bp);
402 m_bp_rank = std::move(bp_support.m_bp_rank);
403 m_bp_rank.set_vector(m_bp);
404 m_bp_select = std::move(bp_support.m_bp_select);
405 m_bp_select.set_vector(m_bp);
406
407 m_sml_block_min_max = std::move(bp_support.m_sml_block_min_max);
408 m_med_block_min_max = std::move(bp_support.m_med_block_min_max);
409
410 m_size = std::move(bp_support.m_size);
411 m_sml_blocks = std::move(bp_support.m_sml_blocks);
412 m_med_blocks = std::move(bp_support.m_med_blocks);
413 m_med_inner_blocks = std::move(bp_support.m_med_inner_blocks);
414 }
415 return *this;
416 }
417
420 {
421 if (this != &v)
422 {
423 bp_support_sada tmp(v);
424 *this = std::move(tmp);
425 }
426 return *this;
427 }
428
430 explicit bp_support_sada(bit_vector const * bp) :
431 m_bp(bp),
432 m_size(bp == nullptr ? 0 : bp->size()),
433 m_sml_blocks((m_size + t_sml_blk - 1) / t_sml_blk),
434 m_med_blocks((m_size + t_sml_blk * t_med_deg - 1) / (t_sml_blk * t_med_deg)),
435 m_med_inner_blocks(0)
436 {
437 if (bp == nullptr or bp->size() == 0)
438 return;
439 // initialize rank and select
440 util::init_support(m_bp_rank, bp);
441 util::init_support(m_bp_select, bp);
442
443 m_med_inner_blocks = 1;
444 // m_med_inner_blocks = (next power of 2 greater than or equal to m_med_blocks)-1
445 while (m_med_inner_blocks < m_med_blocks)
446 {
447 m_med_inner_blocks <<= 1;
448 assert(m_med_inner_blocks != 0);
449 }
450 --m_med_inner_blocks;
451 assert((m_med_inner_blocks == 0) or (m_med_inner_blocks % 2 == 1));
452
453 m_sml_block_min_max = int_vector<>(2 * m_sml_blocks, 0, bits::hi(t_sml_blk + 2) + 1);
454 m_med_block_min_max = int_vector<>(2 * (m_med_blocks + m_med_inner_blocks), 0, bits::hi(2 * m_size + 2) + 1);
455
456 // calculate min/max excess values of the small blocks and medium blocks
457 difference_type min_ex = 1, max_ex = -1, curr_rel_ex = 0, curr_abs_ex = 0;
458 for (size_type i = 0; i < m_size; ++i)
459 {
460 if ((*bp)[i])
461 ++curr_rel_ex;
462 else
463 --curr_rel_ex;
464 if (curr_rel_ex > max_ex)
465 max_ex = curr_rel_ex;
466 if (curr_rel_ex < min_ex)
467 min_ex = curr_rel_ex;
468 if ((i + 1) % t_sml_blk == 0 or i + 1 == m_size)
469 {
470 size_type sidx = i / t_sml_blk;
471 m_sml_block_min_max[2 * sidx] = -(min_ex - 1);
472 m_sml_block_min_max[2 * sidx + 1] = max_ex + 1;
473
474 size_type v = m_med_inner_blocks + sidx / t_med_deg;
475
476 if ((difference_type)(-(curr_abs_ex + min_ex) + m_size) > ((difference_type)m_med_block_min_max[2 * v]))
477 {
478 assert(curr_abs_ex + min_ex <= min_value(v));
479 m_med_block_min_max[2 * v] = -(curr_abs_ex + min_ex) + m_size;
480 }
481
482 if ((difference_type)(curr_abs_ex + max_ex + m_size) > (difference_type)m_med_block_min_max[2 * v + 1])
483 m_med_block_min_max[2 * v + 1] = curr_abs_ex + max_ex + m_size;
484
485 curr_abs_ex += curr_rel_ex;
486 min_ex = 1;
487 max_ex = -1;
488 curr_rel_ex = 0;
489 }
490 }
491
492 for (size_type v = m_med_block_min_max.size() / 2 - 1; !is_root(v); --v)
493 {
494 size_type p = parent(v);
495 if (min_value(v) < min_value(p)) // update minimum
496 m_med_block_min_max[2 * p] = m_med_block_min_max[2 * v];
497 if (max_value(v) > max_value(p)) // update maximum
498 m_med_block_min_max[2 * p + 1] = m_med_block_min_max[2 * v + 1];
499 }
500 }
501
502 void set_vector(bit_vector const * bp)
503 {
504 m_bp = bp;
505 m_bp_rank.set_vector(bp);
506 m_bp_select.set_vector(bp);
507 }
508
513 {
514 return (m_bp_rank(i + 1) << 1) - i - 1;
515 }
516
521 {
522 return m_bp_rank(i + 1);
523 }
524
531 {
532#ifdef USE_CACHE
533 size_type a = 0;
534 if (select_cache.exists(i, a))
535 {
536 return a;
537 }
538 else
539 {
540 a = m_bp_select(i);
541 select_cache.write(i, a);
542 return a;
543 }
544#endif
545 return m_bp_select(i);
546 }
547
555 {
556 assert(i < m_size);
557 if (!(*m_bp)[i])
558 { // if there is a closing parenthesis at index i return i
559 return i;
560 }
561#ifdef USE_CACHE
562 size_type a = 0;
563 if (find_close_cache.exists(i, a))
564 {
565 return a;
566 }
567 else
568 {
569 a = fwd_excess(i, -1);
570 find_close_cache.write(i, a);
571 return a;
572 }
573#endif
574 return fwd_excess(i, -1);
575 }
576
578
584 {
585 assert(i < m_size);
586 if ((*m_bp)[i])
587 { // if there is a opening parenthesis at index i return i
588 return i;
589 }
590#ifdef USE_CACHE
591 size_type a = 0;
592 if (find_open_cache.exists(i, a))
593 {
594 return a;
595 }
596 else
597 {
598 size_type bwd_ex = bwd_excess(i, 0);
599 if (bwd_ex == size())
600 a = size();
601 else
602 a = bwd_ex + 1;
603 find_open_cache.write(i, a);
604 return a;
605 }
606#endif
607 size_type bwd_ex = bwd_excess(i, 0);
608 if (bwd_ex == size())
609 return size();
610 else
611 return bwd_ex + 1;
612 }
613
616
621 {
622 assert(i < m_size);
623 if (!(*m_bp)[i])
624 { // if there is closing parenthesis at position i
625 return find_open(i);
626 }
627 size_type bwd_ex = bwd_excess(i, -2);
628 if (bwd_ex == size())
629 return size();
630 else
631 return bwd_ex + 1;
632 }
633
635
642 size_type rr_enclose(const size_type i, const size_type j) const
643 {
644 assert(j < m_size);
645 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
646 const size_type mip1 = find_close(i) + 1;
647 if (mip1 >= j)
648 return size();
649 return rmq_open(mip1, j);
650 }
651
660 size_type rmq_open(const size_type l, const size_type r) const
661 {
662 assert(r < m_bp->size());
663 if (l >= r)
664 return size();
665 size_type res = rmq(l, r - 1);
666 assert(res >= l and res <= r - 1);
667 if ((*m_bp)[res] == 1)
668 { // The parenthesis with minimal excess is opening
669 assert(find_close(res) >= r);
670 return res;
671 }
672 else
673 {
674 res = res + 1; // go to the next parenthesis to the right
675 if (res < r)
676 { // The parenthesis with minimal excess if closing and the next opening parenthesis is less than r
677 assert((*m_bp)[res] == 1);
678 size_type ec = enclose(res);
679 if (ec < l or ec == size())
680 {
681 assert(find_close(res) >= r);
682 return res;
683 }
684 else
685 {
686 assert(find_close(ec) >= r);
687 return ec;
688 }
689 }
690 else if (res == r)
691 {
692 size_type ec = enclose(res); // if m_bp[res]==0 => find_open(res), if m_bp[res]==1 => enclose(res)
693 if (ec >= l)
694 {
695 assert(ec == size() or excess(ec) == excess(res - 1));
696 return ec;
697 }
698 }
699 }
700 return size();
701 }
702
704 {
705 assert(l_sblock <= r_sblock + 1);
706 size_type pos_min_block = (size_type)-1;
707 difference_type e = 0;
708 if (l_sblock == 0)
709 {
710 if (sml_min_value(0) <= min_ex)
711 {
712 pos_min_block = 0;
713 min_ex = sml_min_value(0);
714 }
715 l_sblock = 1;
716 }
717 for (size_type i = l_sblock; i <= r_sblock; ++i)
718 {
719 if ((e = (excess(i * t_sml_blk - 1) + sml_min_value(i))) <= min_ex)
720 {
721 pos_min_block = i;
722 min_ex = e;
723 }
724 }
725 return pos_min_block;
726 }
727
729
733 {
734 assert(l <= r);
735 size_type sbl = sml_block_idx(l);
736 size_type sbr = sml_block_idx(r);
737 difference_type min_rel_ex = 0;
738 if (sbl == sbr)
739 { // if l and r are in the same small block
740 return near_rmq(*m_bp, l, r, min_rel_ex);
741 }
742 else
743 {
744 difference_type min_ex = 0; // current minimal excess value
745 size_type min_pos = 0; // current min pos
746 enum min_pos_type
747 {
748 POS,
749 SMALL_BLOCK_POS,
750 MEDIUM_BLOCK_POS
751 };
752 enum min_pos_type pos_type = POS; // current
753 min_pos = near_rmq(*m_bp, l, (sbl + 1) * t_sml_blk - 1, min_rel_ex); // scan the leftmost small block of l
754 assert(min_pos >= l);
755 min_ex = excess(l) + min_rel_ex;
756
757 size_type mbl = med_block_idx(l);
758 size_type mbr = med_block_idx(r);
759 assert(mbl <= mbr);
760
761 size_type temp = median_block_rmq(sbl + 1,
762 std::min((mbl + 1) * t_med_deg - 1, sbr - 1),
763 min_ex); // scan the medium block of l
764 if (temp != (size_type)-1)
765 {
766 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
767 min_pos = temp;
768 assert(min_pos < m_sml_blocks);
769 pos_type = SMALL_BLOCK_POS;
770 }
771#if 0
772 // sequential scan the medium blocks
773 for (size_type v=mbl+1+m_med_inner_blocks; v < mbr + m_med_inner_blocks; ++v) {
774 assert(is_leaf(v));
775 if (min_value(v) <= min_ex) {
776 min_ex = min_value(v);
777 min_pos = v;
778 assert(min_pos-m_med_inner_blocks >= 0 and min_pos < m_med_blocks-m_med_inner_blocks);
779 pos_type = MEDIUM_BLOCK_POS;
780 }
781 }
782#else
783 // tree search in the min max tree of the medium blocks
784 if (mbr - mbl > 1)
785 {
786 size_type v = mbl + 1 + m_med_inner_blocks;
787 size_type rcb = mbl + 1; // rightmost covered block
788 size_type h = 0; // subtree height
789 while (rcb < mbr - 1)
790 { // go up the tree until the rightmost covered block >= mbr-1
791 if (min_value(v) <= min_ex)
792 {
793 min_ex = min_value(v);
794 min_pos = v;
795 pos_type = MEDIUM_BLOCK_POS;
796 }
797 if (is_right_child(v))
798 { // v is a right child
799 h += 1;
800 rcb += (1ULL << h);
801 v = right_sibling(parent(v));
802 }
803 else
804 { // it is a left child
805 rcb += (1ULL << h);
806 h += 1;
807 v = parent(v);
808 }
809 }
810 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
811 {
812 min_ex = min_value(v);
813 min_pos = v;
814 pos_type = MEDIUM_BLOCK_POS;
815 }
816 assert(node_exists(v));
817 assert(rcb >= mbr - 1);
818
819 while (rcb != mbr - 1)
820 { // go down the tree until the rightmost covered block = mbr-1
821 assert(h != (size_type)-1);
822 if (rcb > mbr - 1)
823 {
824 h = h - 1;
825 rcb = rcb - (1ULL << h);
826 v = left_child(v);
827 }
828 else
829 { // rcb < mbr-1
830 h = h - 1;
831 rcb = rcb + (1ULL << h);
832 v = right_sibling(right_child(v));
833 }
834 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
835 {
836 min_ex = min_value(v);
837 min_pos = v;
838 pos_type = MEDIUM_BLOCK_POS;
839 }
840 }
841 if (pos_type == MEDIUM_BLOCK_POS)
842 {
843 while (!is_leaf(min_pos))
844 {
845 min_pos = right_child(min_pos);
846 if (!node_exists(min_pos) or min_value(min_pos) > min_ex)
847 min_pos = left_sibling(min_pos);
848 }
849 }
850 }
851#endif
852
853 // search in the medium block of r
854 temp = median_block_rmq(std::max(mbr * t_med_deg, sbl + 1), sbr - 1, min_ex); // scan the medium block of r
855 if (temp != (size_type)-1)
856 {
857 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
858 min_pos = temp;
859 pos_type = SMALL_BLOCK_POS;
860 }
861 // search in the small block of r
862 temp = near_rmq(*m_bp, sbr * t_sml_blk, r, min_rel_ex); // scan the small block of r
863 if ((excess(sbr * t_sml_blk) + min_rel_ex) <= min_ex)
864 { // if it contains the minimum return its position
865 assert(temp >= l and temp <= r);
866 return temp;
867 }
868 // if the found minimum lies in a medium block => find its small block
869 if (pos_type == MEDIUM_BLOCK_POS)
870 {
871 min_pos = min_pos - m_med_inner_blocks;
872 temp = median_block_rmq(min_pos * t_med_deg, (min_pos + 1) * t_med_deg - 1, min_ex);
873 assert(temp != (size_type)-1); // assert that we find a solution
874 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
875 min_pos = temp;
876 pos_type = SMALL_BLOCK_POS;
877 }
878 if (pos_type == SMALL_BLOCK_POS)
879 {
880 min_pos = near_rmq(*m_bp, min_pos * t_sml_blk, (min_pos + 1) * t_sml_blk - 1, min_rel_ex);
881 assert(min_pos >= l and min_pos <= r);
882 }
883 return min_pos;
884 }
885 }
886
888
896 {
897 assert(j > i and j < m_size);
898 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
899 size_type mi = find_close(i); // matching parenthesis to i
900 assert(mi > i and mi < j);
901 assert(find_close(j) > j);
902 size_type k = enclose(j);
903 if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
904 return m_size;
905 size_type kk;
906 do
907 {
908 kk = k;
909 k = enclose(k);
910 }
911 while (k != m_size and k > mi);
912 return kk;
913 }
914
916
922 {
923 assert(j > i);
924 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
925 size_type k = rr_enclose(i, j);
926 if (k == size())
927 return enclose(j);
928 else
929 return enclose(k);
930 }
931
933
936 {
937 assert(i < m_size);
938 if (!i)
939 return 0;
940 size_type ones = m_bp_rank(i);
941 if (ones)
942 { // ones > 0
943 assert(m_bp_select(ones) < i);
944 return i - m_bp_select(ones) - 1;
945 }
946 else
947 {
948 return i;
949 }
950 }
951
953
958 {
959 assert(i < m_size);
960 size_type bwd_ex = bwd_excess(i, -d - 1);
961 if (bwd_ex == size())
962 return size();
963 else
964 return bwd_ex + 1;
965 }
966
971 {
972 return m_size;
973 }
974
976
980 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
981 {
982 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
983 size_type written_bytes = 0;
984 written_bytes += write_member(m_size, out, child, "size");
985 written_bytes += write_member(m_sml_blocks, out, child, "sml_block_cnt");
986 written_bytes += write_member(m_med_blocks, out, child, "med_block_cnt");
987 written_bytes += write_member(m_med_inner_blocks, out, child, "med_inner_blocks");
988
989 written_bytes += m_bp_rank.serialize(out, child, "bp_rank");
990 written_bytes += m_bp_select.serialize(out, child, "bp_select");
991
992 written_bytes += m_sml_block_min_max.serialize(out, child, "sml_blocks");
993 written_bytes += m_med_block_min_max.serialize(out, child, "med_blocks");
994
995 structure_tree::add_size(child, written_bytes);
996 return written_bytes;
997 }
998
1000
1004 void load(std::istream & in, bit_vector const * bp)
1005 {
1006 m_bp = bp;
1007 read_member(m_size, in);
1008 assert(m_size == bp->size());
1009 read_member(m_sml_blocks, in);
1010 read_member(m_med_blocks, in);
1011 read_member(m_med_inner_blocks, in);
1012
1013 m_bp_rank.load(in, m_bp);
1014 m_bp_select.load(in, m_bp);
1015
1016 m_sml_block_min_max.load(in);
1017 m_med_block_min_max.load(in);
1018 }
1019
1020 template <typename archive_t>
1021 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
1022 {
1023 ar(CEREAL_NVP(m_size));
1024 ar(CEREAL_NVP(m_sml_blocks));
1025 ar(CEREAL_NVP(m_med_blocks));
1026 ar(CEREAL_NVP(m_med_inner_blocks));
1027 ar(CEREAL_NVP(m_bp_rank));
1028 ar(CEREAL_NVP(m_bp_select));
1029 ar(CEREAL_NVP(m_sml_block_min_max));
1030 ar(CEREAL_NVP(m_med_block_min_max));
1031 }
1032
1033 template <typename archive_t>
1034 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
1035 {
1036 ar(CEREAL_NVP(m_size));
1037 ar(CEREAL_NVP(m_sml_blocks));
1038 ar(CEREAL_NVP(m_med_blocks));
1039 ar(CEREAL_NVP(m_med_inner_blocks));
1040 ar(CEREAL_NVP(m_bp_rank));
1041 ar(CEREAL_NVP(m_bp_select));
1042 ar(CEREAL_NVP(m_sml_block_min_max));
1043 ar(CEREAL_NVP(m_med_block_min_max));
1044 }
1045
1047 bool operator==(bp_support_sada const & other) const noexcept
1048 {
1049 return (m_bp_rank == other.m_bp_rank) && (m_bp_select == other.m_bp_select)
1050 && (m_sml_block_min_max == other.m_sml_block_min_max) && (m_med_block_min_max == other.m_med_block_min_max)
1051 && (m_size == other.m_size) && (m_sml_blocks == other.m_sml_blocks) && (m_med_blocks == other.m_med_blocks)
1052 && (m_med_inner_blocks == other.m_med_inner_blocks);
1053 }
1054
1056 bool operator!=(bp_support_sada const & other) const noexcept
1057 {
1058 return !(*this == other);
1059 }
1060};
1061
1062} // namespace sdsl
1063
1064#endif
bits.hpp contains the sdsl::bits class.
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.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
size_type enclose(size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair...
size_type median_block_rmq(size_type l_sblock, size_type r_sblock, bit_vector::difference_type &min_ex) const
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which proceed position i in the balanced parentheses sequence.
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
size_type level_anc(size_type i, size_type d) const
Returns the level ancestor of the node i.
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 rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
sml_block_array_type const & sml_block_min_max
Small blocks array.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
bool operator!=(bp_support_sada const &other) const noexcept
Inequality operator.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
bp_support_sada(bp_support_sada &&bp_support)
Move constructor.
bool operator==(bp_support_sada const &other) const noexcept
Equality operator.
select_type const & bp_select
SS for the underlying BP sequence.
bit_vector::size_type size_type
bp_support_sada(bp_support_sada const &v)
Copy constructor.
med_block_array_type const & med_block_min_max
Array containing the min max tree of the medium blocks.
bp_support_sada & operator=(bp_support_sada const &v)
Assignment operator.
bp_support_sada & operator=(bp_support_sada &&bp_support)
Assignment operator.
size_type size() const
The size of the supported balanced parentheses sequence.
bit_vector::difference_type difference_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
void load(std::istream &in, bit_vector const *bp)
Load the bp_support_sada for a bit_vector v.
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 .
void set_vector(bit_vector const *bp)
bp_support_sada(bit_vector const *bp)
Constructor.
difference_type excess(size_type i) const
Calculates the excess value at index i.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_sada to a stream.
rank_type const & bp_rank
RS for the underlying BP sequence.
size_type rr_enclose(const size_type i, const size_type j) const
The range restricted enclose operation for parentheses pairs and .
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
A generic vector class for integers of width .
Definition io.hpp:36
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.
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.
uint64_t near_fwd_excess(bit_vector const &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
uint64_t near_bwd_excess(bit_vector const &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
Near backward excess.
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_rmq(bit_vector const &bp, uint64_t l, uint64_t r, bit_vector::difference_type &min_rel_ex)
Calculate the position with minimal excess value in the interval [l..r].
void read_member(T &t, std::istream &in)
Definition io.hpp:119
rank_support_v5.hpp contains rank_support_v5.5
rank_support_v.hpp contains rank_support_v.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
void write(size_type i, size_type x)
bool exists(size_type i, size_type &x)
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.