SDSL 3.0.1
Succinct Data Structure Library
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 <map>
13#include <set>
14#include <stack>
15#include <stdexcept>
16#include <utility>
17
19#include <sdsl/fast_cache.hpp>
20#include <sdsl/int_vector.hpp>
21#include <sdsl/rank_support.hpp>
23#ifndef NDEBUG
24#include <algorithm>
25#endif
26#include <iostream>
27
28namespace sdsl
29{
30
32
59template <uint32_t t_sml_blk = 256,
60 uint32_t t_med_deg = 32,
61 class t_rank = rank_support_v5<>,
62 class t_select = select_support_mcl<>>
64{
65 public:
70 typedef t_rank rank_type;
71 typedef t_select select_type;
72
73 private:
74 static_assert(0 < t_sml_blk, "bp_support_sada: t_sml_blk should be greater than 0!");
75 const bit_vector * m_bp = nullptr; // the supported balanced parentheses sequence as bit_vector
76 rank_type m_bp_rank; // RS for the BP sequence => see excess() and rank()
77 select_type m_bp_select; // SS for the BP sequence => see select()
78
79 sml_block_array_type m_sml_block_min_max;
80 med_block_array_type m_med_block_min_max;
81
82 size_type m_size = 0; // number of supported parentheses
83 size_type m_sml_blocks = 0; // number of small sized blocks
84 size_type m_med_blocks = 0; // number of medium sized blocks
85 size_type m_med_inner_blocks = 0; // number of inner nodes in the min max tree of the medium sized blocks
86//#define USE_CACHE
87#ifdef USE_CACHE
88 mutable fast_cache find_close_cache;
89 mutable fast_cache find_open_cache;
90 mutable fast_cache select_cache;
91#endif
92
93 inline static size_type sml_block_idx(size_type i) { return i / t_sml_blk; }
94
95 inline static size_type med_block_idx(size_type i) { return i / (t_sml_blk * t_med_deg); }
96
97 inline static bool is_root(size_type v) { return v == 0; }
98
99 inline static bool is_left_child(size_type v)
100 {
101 assert(!is_root(v));
102 return v % 2;
103 }
104
105 inline static bool is_right_child(size_type v)
106 {
107 assert(!is_root(v));
108 return !(v % 2);
109 }
110
111 inline static size_type parent(size_type v)
112 {
113 assert(!is_root(v));
114 return (v - 1) / 2;
115 }
116
117 inline static size_type left_child(size_type v) { return 2 * v + 1; }
118
119 inline static size_type right_child(size_type v) { return 2 * v + 2; }
120
121 inline bool node_exists(size_type v) const { return v < (m_med_inner_blocks + m_med_blocks); }
122
123 inline static size_type right_sibling(size_type v) { return ++v; }
124
125 inline static size_type left_sibling(size_type v) { return --v; }
126
127 inline bool is_leaf(size_type v) const { return v >= m_med_inner_blocks; }
128
129 inline difference_type min_value(size_type v) const
130 {
131 return m_size - ((difference_type)m_med_block_min_max[2 * v]);
132 }
133
134 inline difference_type max_value(size_type v) const { return m_med_block_min_max[2 * v + 1] - m_size; }
135
136 inline difference_type sml_min_value(size_type sml_block) const
137 {
138 return (1 - ((difference_type)m_sml_block_min_max[sml_block << 1]));
139 }
140
141 inline difference_type sml_max_value(size_type sml_block) const
142 {
143 return (difference_type)m_sml_block_min_max[(sml_block << 1) + 1] - 1;
144 }
145
146 void print_node(size_type v) const
147 {
148 std::cout << "v = " << v << " (" << min_value(v) << ", " << max_value(v) << ")";
149 if (is_leaf(v))
150 {
151 std::cout << " range: [" << (v - m_med_inner_blocks) * t_med_deg * t_sml_blk << ","
152 << (v - m_med_inner_blocks + 1) * t_med_deg * t_sml_blk - 1 << "]";
153 }
154 std::cout << std::endl;
155 }
156
158
164 size_type fwd_excess(size_type i, difference_type rel) const
165 {
166 size_type j;
167 // (1) search the small block for the answer
168 if ((j = near_fwd_excess(*m_bp, i + 1, rel, t_sml_blk)) > i) { return j; }
169 difference_type desired_excess = excess(i) + rel;
170 // (2) scan the small blocks of the current median block for an answer
171 if ((j = fwd_excess_in_med_block(sml_block_idx(i) + 1, desired_excess)) != size()) { return j; }
172 // (3) search the min-max tree of the medium blocks for the right med block
173 if (med_block_idx(i) == m_med_blocks) // if we are already in the last medium block => we are done
174 return size();
175 size_type v = m_med_inner_blocks + med_block_idx(i);
176 // (3 a) go up the tree
177 while (!is_root(v))
178 {
179 if (is_left_child(v))
180 { // if the node is a left child
181 v = right_sibling(v); // choose right sibling
182 if (min_value(v) <= desired_excess and desired_excess <= max_value(v)) // found solution
183 break;
184 }
185 v = parent(v); // choose parent
186 }
187 // (3 b) go down the tree
188 if (!is_root(v))
189 { // found solution for the query
190 while (!is_leaf(v))
191 {
192 v = left_child(v); // choose left child
193 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
194 {
195 v = right_sibling(v); // choose right child == right sibling of the left child
196 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
197 }
198 }
199 return fwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg, desired_excess);
200 }
201 // no solution found
202 return size();
203 }
204
206
211 size_type bwd_excess(size_type i, difference_type rel) const
212 {
213 size_type j;
214 if (i == 0) { return rel == 0 ? -1 : size(); }
215 // (1) search the small block for the answer
216 if ((j = near_bwd_excess(*m_bp, i - 1, rel, t_sml_blk)) < i or j == (size_type)-1) { return j; }
217 difference_type desired_excess = excess(i) + rel;
218 // (2) scan the small blocks of the current median block for an answer
219 if ((j = bwd_excess_in_med_block(sml_block_idx(i) - 1, desired_excess)) != size()) { return j; }
220 // (3) search the min-max tree of the medium blocks for the right med block
221 if (med_block_idx(i) == 0)
222 { // if we are already in the first medium block => we are done
223 if (desired_excess == 0) return -1;
224 return size();
225 }
226 size_type v = m_med_inner_blocks + med_block_idx(i);
227 // (3 a) go up the tree
228 while (!is_root(v))
229 {
230 if (is_right_child(v))
231 { // if the node is a right child
232 v = left_sibling(v); // choose left sibling
233 if (min_value(v) <= desired_excess and desired_excess <= max_value(v)) // found solution
234 break;
235 }
236 v = parent(v); // choose parent
237 }
238 // (3 b) go down the tree
239 if (!is_root(v))
240 { // found solution for the query
241 while (!is_leaf(v))
242 {
243 v = right_child(v); // choose child
244 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
245 {
246 v = left_sibling(v); // choose left child == left sibling of the right child
247 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
248 }
249 }
250 return bwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg + (t_med_deg - 1), desired_excess);
251 }
252 else if (desired_excess == 0)
253 {
254 return -1;
255 }
256 // no solution found
257 return size();
258 }
259
262 size_type bwd_excess_in_med_block(size_type sml_block_idx, difference_type desired_excess) const
263 {
264 // get the first small block in the medium block right to the current med block
265 size_type first_sml_block_in_med_block = (med_block_idx(sml_block_idx * t_sml_blk)) * t_med_deg;
266
267 while ((sml_block_idx + 1) and sml_block_idx >= first_sml_block_in_med_block)
268 {
269 difference_type ex = (sml_block_idx == 0) ? 0 : excess(sml_block_idx * t_sml_blk - 1);
270 difference_type min_ex = ex + (1 - ((difference_type)m_sml_block_min_max[2 * sml_block_idx]));
271 difference_type max_ex = ex + (m_sml_block_min_max[2 * sml_block_idx + 1] - 1);
272
273 if (min_ex <= desired_excess and desired_excess <= max_ex)
274 {
275 size_type j = near_bwd_excess(*m_bp,
276 (sml_block_idx + 1) * t_sml_blk - 1,
277 desired_excess - excess((sml_block_idx + 1) * t_sml_blk),
278 t_sml_blk);
279 return j;
280 }
281 --sml_block_idx;
282 }
283 if (sml_block_idx == 0 and desired_excess == 0) return -1;
284 return size();
285 }
286
289 size_type fwd_excess_in_med_block(size_type sml_block_idx, difference_type desired_excess) const
290 {
291 // get the first small block in the medium block right to the current med block
292 size_type first_sml_block_nr_in_next_med_block = (med_block_idx(sml_block_idx * t_sml_blk) + 1) * t_med_deg;
293 if (first_sml_block_nr_in_next_med_block > m_sml_blocks) first_sml_block_nr_in_next_med_block = m_sml_blocks;
294
295 assert(sml_block_idx > 0);
296 while (sml_block_idx < first_sml_block_nr_in_next_med_block)
297 {
298 difference_type ex = excess(sml_block_idx * t_sml_blk - 1);
299 difference_type min_ex = ex + (1 - ((difference_type)m_sml_block_min_max[2 * sml_block_idx]));
300 difference_type max_ex = ex + m_sml_block_min_max[2 * sml_block_idx + 1] - 1;
301 if (min_ex <= desired_excess and desired_excess <= max_ex)
302 {
303 size_type j = near_fwd_excess(*m_bp, sml_block_idx * t_sml_blk, desired_excess - ex, t_sml_blk);
304 return j;
305 }
306 ++sml_block_idx;
307 }
308 return size();
309 }
310
311 public:
312 const rank_type & bp_rank = m_bp_rank;
313 const select_type & bp_select = m_bp_select;
314 const sml_block_array_type & sml_block_min_max = m_sml_block_min_max;
316 const med_block_array_type & med_block_min_max = m_med_block_min_max;
318
320
323 : m_bp(v.m_bp)
324 , m_bp_rank(v.m_bp_rank)
325 , m_bp_select(v.m_bp_select)
326 , m_sml_block_min_max(v.m_sml_block_min_max)
327 , m_med_block_min_max(v.m_med_block_min_max)
328 , m_size(v.m_size)
329 , m_sml_blocks(v.m_sml_blocks)
330 , m_med_blocks(v.m_med_blocks)
331 , m_med_inner_blocks(v.m_med_inner_blocks)
332 {
333 m_bp_rank.set_vector(m_bp);
334 m_bp_select.set_vector(m_bp);
335 }
336
338 bp_support_sada(bp_support_sada && bp_support) { *this = std::move(bp_support); }
339
342 {
343 if (this != &bp_support)
344 {
345 m_bp = std::move(bp_support.m_bp);
346 m_bp_rank = std::move(bp_support.m_bp_rank);
347 m_bp_rank.set_vector(m_bp);
348 m_bp_select = std::move(bp_support.m_bp_select);
349 m_bp_select.set_vector(m_bp);
350
351 m_sml_block_min_max = std::move(bp_support.m_sml_block_min_max);
352 m_med_block_min_max = std::move(bp_support.m_med_block_min_max);
353
354 m_size = std::move(bp_support.m_size);
355 m_sml_blocks = std::move(bp_support.m_sml_blocks);
356 m_med_blocks = std::move(bp_support.m_med_blocks);
357 m_med_inner_blocks = std::move(bp_support.m_med_inner_blocks);
358 }
359 return *this;
360 }
361
364 {
365 if (this != &v)
366 {
367 bp_support_sada tmp(v);
368 *this = std::move(tmp);
369 }
370 return *this;
371 }
372
374 explicit bp_support_sada(const bit_vector * bp)
375 : m_bp(bp)
376 , m_size(bp == nullptr ? 0 : bp->size())
377 , m_sml_blocks((m_size + t_sml_blk - 1) / t_sml_blk)
378 , m_med_blocks((m_size + t_sml_blk * t_med_deg - 1) / (t_sml_blk * t_med_deg))
379 , m_med_inner_blocks(0)
380 {
381 if (bp == nullptr or bp->size() == 0) return;
382 // initialize rank and select
383 util::init_support(m_bp_rank, bp);
384 util::init_support(m_bp_select, bp);
385
386 m_med_inner_blocks = 1;
387 // m_med_inner_blocks = (next power of 2 greater than or equal to m_med_blocks)-1
388 while (m_med_inner_blocks < m_med_blocks)
389 {
390 m_med_inner_blocks <<= 1;
391 assert(m_med_inner_blocks != 0);
392 }
393 --m_med_inner_blocks;
394 assert((m_med_inner_blocks == 0) or (m_med_inner_blocks % 2 == 1));
395
396 m_sml_block_min_max = int_vector<>(2 * m_sml_blocks, 0, bits::hi(t_sml_blk + 2) + 1);
397 m_med_block_min_max = int_vector<>(2 * (m_med_blocks + m_med_inner_blocks), 0, bits::hi(2 * m_size + 2) + 1);
398
399 // calculate min/max excess values of the small blocks and medium blocks
400 difference_type min_ex = 1, max_ex = -1, curr_rel_ex = 0, curr_abs_ex = 0;
401 for (size_type i = 0; i < m_size; ++i)
402 {
403 if ((*bp)[i])
404 ++curr_rel_ex;
405 else
406 --curr_rel_ex;
407 if (curr_rel_ex > max_ex) max_ex = curr_rel_ex;
408 if (curr_rel_ex < min_ex) min_ex = curr_rel_ex;
409 if ((i + 1) % t_sml_blk == 0 or i + 1 == m_size)
410 {
411 size_type sidx = i / t_sml_blk;
412 m_sml_block_min_max[2 * sidx] = -(min_ex - 1);
413 m_sml_block_min_max[2 * sidx + 1] = max_ex + 1;
414
415 size_type v = m_med_inner_blocks + sidx / t_med_deg;
416
417 if ((difference_type)(-(curr_abs_ex + min_ex) + m_size) > ((difference_type)m_med_block_min_max[2 * v]))
418 {
419 assert(curr_abs_ex + min_ex <= min_value(v));
420 m_med_block_min_max[2 * v] = -(curr_abs_ex + min_ex) + m_size;
421 }
422
423 if ((difference_type)(curr_abs_ex + max_ex + m_size) > (difference_type)m_med_block_min_max[2 * v + 1])
424 m_med_block_min_max[2 * v + 1] = curr_abs_ex + max_ex + m_size;
425
426 curr_abs_ex += curr_rel_ex;
427 min_ex = 1;
428 max_ex = -1;
429 curr_rel_ex = 0;
430 }
431 }
432
433 for (size_type v = m_med_block_min_max.size() / 2 - 1; !is_root(v); --v)
434 {
435 size_type p = parent(v);
436 if (min_value(v) < min_value(p)) // update minimum
437 m_med_block_min_max[2 * p] = m_med_block_min_max[2 * v];
438 if (max_value(v) > max_value(p)) // update maximum
439 m_med_block_min_max[2 * p + 1] = m_med_block_min_max[2 * v + 1];
440 }
441 }
442
443 void set_vector(const bit_vector * bp)
444 {
445 m_bp = bp;
446 m_bp_rank.set_vector(bp);
447 m_bp_select.set_vector(bp);
448 }
449
453 inline difference_type excess(size_type i) const { return (m_bp_rank(i + 1) << 1) - i - 1; }
454
458 size_type rank(size_type i) const { return m_bp_rank(i + 1); }
459
466 {
467#ifdef USE_CACHE
468 size_type a = 0;
469 if (select_cache.exists(i, a)) { return a; }
470 else
471 {
472 a = m_bp_select(i);
473 select_cache.write(i, a);
474 return a;
475 }
476#endif
477 return m_bp_select(i);
478 }
479
487 {
488 assert(i < m_size);
489 if (!(*m_bp)[i])
490 { // if there is a closing parenthesis at index i return i
491 return i;
492 }
493#ifdef USE_CACHE
494 size_type a = 0;
495 if (find_close_cache.exists(i, a)) { return a; }
496 else
497 {
498 a = fwd_excess(i, -1);
499 find_close_cache.write(i, a);
500 return a;
501 }
502#endif
503 return fwd_excess(i, -1);
504 }
505
507
513 {
514 assert(i < m_size);
515 if ((*m_bp)[i])
516 { // if there is a opening parenthesis at index i return i
517 return i;
518 }
519#ifdef USE_CACHE
520 size_type a = 0;
521 if (find_open_cache.exists(i, a)) { return a; }
522 else
523 {
524 size_type bwd_ex = bwd_excess(i, 0);
525 if (bwd_ex == size())
526 a = size();
527 else
528 a = bwd_ex + 1;
529 find_open_cache.write(i, a);
530 return a;
531 }
532#endif
533 size_type bwd_ex = bwd_excess(i, 0);
534 if (bwd_ex == size())
535 return size();
536 else
537 return bwd_ex + 1;
538 }
539
542
547 {
548 assert(i < m_size);
549 if (!(*m_bp)[i])
550 { // if there is closing parenthesis at position i
551 return find_open(i);
552 }
553 size_type bwd_ex = bwd_excess(i, -2);
554 if (bwd_ex == size())
555 return size();
556 else
557 return bwd_ex + 1;
558 }
559
561
568 size_type rr_enclose(const size_type i, const size_type j) const
569 {
570 assert(j < m_size);
571 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
572 const size_type mip1 = find_close(i) + 1;
573 if (mip1 >= j) return size();
574 return rmq_open(mip1, j);
575 }
576
585 size_type rmq_open(const size_type l, const size_type r) const
586 {
587 assert(r < m_bp->size());
588 if (l >= r) return size();
589 size_type res = rmq(l, r - 1);
590 assert(res >= l and res <= r - 1);
591 if ((*m_bp)[res] == 1)
592 { // The parenthesis with minimal excess is opening
593 assert(find_close(res) >= r);
594 return res;
595 }
596 else
597 {
598 res = res + 1; // go to the next parenthesis to the right
599 if (res < r)
600 { // The parenthesis with minimal excess if closing and the next opening parenthesis is less than r
601 assert((*m_bp)[res] == 1);
602 size_type ec = enclose(res);
603 if (ec < l or ec == size())
604 {
605 assert(find_close(res) >= r);
606 return res;
607 }
608 else
609 {
610 assert(find_close(ec) >= r);
611 return ec;
612 }
613 }
614 else if (res == r)
615 {
616 size_type ec = enclose(res); // if m_bp[res]==0 => find_open(res), if m_bp[res]==1 => enclose(res)
617 if (ec >= l)
618 {
619 assert(ec == size() or excess(ec) == excess(res - 1));
620 return ec;
621 }
622 }
623 }
624 return size();
625 }
626
628 {
629 assert(l_sblock <= r_sblock + 1);
630 size_type pos_min_block = (size_type)-1;
631 difference_type e = 0;
632 if (l_sblock == 0)
633 {
634 if (sml_min_value(0) <= min_ex)
635 {
636 pos_min_block = 0;
637 min_ex = sml_min_value(0);
638 }
639 l_sblock = 1;
640 }
641 for (size_type i = l_sblock; i <= r_sblock; ++i)
642 {
643 if ((e = (excess(i * t_sml_blk - 1) + sml_min_value(i))) <= min_ex)
644 {
645 pos_min_block = i;
646 min_ex = e;
647 }
648 }
649 return pos_min_block;
650 }
651
653
657 {
658 assert(l <= r);
659 size_type sbl = sml_block_idx(l);
660 size_type sbr = sml_block_idx(r);
661 difference_type min_rel_ex = 0;
662 if (sbl == sbr)
663 { // if l and r are in the same small block
664 return near_rmq(*m_bp, l, r, min_rel_ex);
665 }
666 else
667 {
668 difference_type min_ex = 0; // current minimal excess value
669 size_type min_pos = 0; // current min pos
670 enum min_pos_type
671 {
672 POS,
673 SMALL_BLOCK_POS,
674 MEDIUM_BLOCK_POS
675 };
676 enum min_pos_type pos_type = POS; // current
677 min_pos = near_rmq(*m_bp, l, (sbl + 1) * t_sml_blk - 1, min_rel_ex); // scan the leftmost small block of l
678 assert(min_pos >= l);
679 min_ex = excess(l) + min_rel_ex;
680
681 size_type mbl = med_block_idx(l);
682 size_type mbr = med_block_idx(r);
683 assert(mbl <= mbr);
684
685 size_type temp = median_block_rmq(sbl + 1,
686 std::min((mbl + 1) * t_med_deg - 1, sbr - 1),
687 min_ex); // scan the medium block of l
688 if (temp != (size_type)-1)
689 {
690 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
691 min_pos = temp;
692 assert(min_pos < m_sml_blocks);
693 pos_type = SMALL_BLOCK_POS;
694 }
695#if 0
696 // sequential scan the medium blocks
697 for (size_type v=mbl+1+m_med_inner_blocks; v < mbr + m_med_inner_blocks; ++v) {
698 assert(is_leaf(v));
699 if (min_value(v) <= min_ex) {
700 min_ex = min_value(v);
701 min_pos = v;
702 assert(min_pos-m_med_inner_blocks >= 0 and min_pos < m_med_blocks-m_med_inner_blocks);
703 pos_type = MEDIUM_BLOCK_POS;
704 }
705 }
706#else
707 // tree search in the min max tree of the medium blocks
708 if (mbr - mbl > 1)
709 {
710 size_type v = mbl + 1 + m_med_inner_blocks;
711 size_type rcb = mbl + 1; // rightmost covered block
712 size_type h = 0; // subtree height
713 while (rcb < mbr - 1)
714 { // go up the tree until the rightmost covered block >= mbr-1
715 if (min_value(v) <= min_ex)
716 {
717 min_ex = min_value(v);
718 min_pos = v;
719 pos_type = MEDIUM_BLOCK_POS;
720 }
721 if (is_right_child(v))
722 { // v is a right child
723 h += 1;
724 rcb += (1ULL << h);
725 v = right_sibling(parent(v));
726 }
727 else
728 { // it is a left child
729 rcb += (1ULL << h);
730 h += 1;
731 v = parent(v);
732 }
733 }
734 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
735 {
736 min_ex = min_value(v);
737 min_pos = v;
738 pos_type = MEDIUM_BLOCK_POS;
739 }
740 assert(node_exists(v));
741 assert(rcb >= mbr - 1);
742
743 while (rcb != mbr - 1)
744 { // go down the tree until the rightmost covered block = mbr-1
745 assert(h != (size_type)-1);
746 if (rcb > mbr - 1)
747 {
748 h = h - 1;
749 rcb = rcb - (1ULL << h);
750 v = left_child(v);
751 }
752 else
753 { // rcb < mbr-1
754 h = h - 1;
755 rcb = rcb + (1ULL << h);
756 v = right_sibling(right_child(v));
757 }
758 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
759 {
760 min_ex = min_value(v);
761 min_pos = v;
762 pos_type = MEDIUM_BLOCK_POS;
763 }
764 }
765 if (pos_type == MEDIUM_BLOCK_POS)
766 {
767 while (!is_leaf(min_pos))
768 {
769 min_pos = right_child(min_pos);
770 if (!node_exists(min_pos) or min_value(min_pos) > min_ex) min_pos = left_sibling(min_pos);
771 }
772 }
773 }
774#endif
775
776 // search in the medium block of r
777 temp = median_block_rmq(std::max(mbr * t_med_deg, sbl + 1), sbr - 1, min_ex); // scan the medium block of r
778 if (temp != (size_type)-1)
779 {
780 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
781 min_pos = temp;
782 pos_type = SMALL_BLOCK_POS;
783 }
784 // search in the small block of r
785 temp = near_rmq(*m_bp, sbr * t_sml_blk, r, min_rel_ex); // scan the small block of r
786 if ((excess(sbr * t_sml_blk) + min_rel_ex) <= min_ex)
787 { // if it contains the minimum return its position
788 assert(temp >= l and temp <= r);
789 return temp;
790 }
791 // if the found minimum lies in a medium block => find its small block
792 if (pos_type == MEDIUM_BLOCK_POS)
793 {
794 min_pos = min_pos - m_med_inner_blocks;
795 temp = median_block_rmq(min_pos * t_med_deg, (min_pos + 1) * t_med_deg - 1, min_ex);
796 assert(temp != (size_type)-1); // assert that we find a solution
797 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
798 min_pos = temp;
799 pos_type = SMALL_BLOCK_POS;
800 }
801 if (pos_type == SMALL_BLOCK_POS)
802 {
803 min_pos = near_rmq(*m_bp, min_pos * t_sml_blk, (min_pos + 1) * t_sml_blk - 1, min_rel_ex);
804 assert(min_pos >= l and min_pos <= r);
805 }
806 return min_pos;
807 }
808 }
809
811
819 {
820 assert(j > i and j < m_size);
821 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
822 size_type mi = find_close(i); // matching parenthesis to i
823 assert(mi > i and mi < j);
824 assert(find_close(j) > j);
825 size_type k = enclose(j);
826 if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
827 return m_size;
828 size_type kk;
829 do {
830 kk = k;
831 k = enclose(k);
832 } while (k != m_size and k > mi);
833 return kk;
834 }
835
837
843 {
844 assert(j > i);
845 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
846 size_type k = rr_enclose(i, j);
847 if (k == size())
848 return enclose(j);
849 else
850 return enclose(k);
851 }
852
854
857 {
858 assert(i < m_size);
859 if (!i) return 0;
860 size_type ones = m_bp_rank(i);
861 if (ones)
862 { // ones > 0
863 assert(m_bp_select(ones) < i);
864 return i - m_bp_select(ones) - 1;
865 }
866 else
867 {
868 return i;
869 }
870 }
871
873
878 {
879 assert(i < m_size);
880 size_type bwd_ex = bwd_excess(i, -d - 1);
881 if (bwd_ex == size())
882 return size();
883 else
884 return bwd_ex + 1;
885 }
886
890 size_type size() const { return m_size; }
891
893
897 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
898 {
899 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
900 size_type written_bytes = 0;
901 written_bytes += write_member(m_size, out, child, "size");
902 written_bytes += write_member(m_sml_blocks, out, child, "sml_block_cnt");
903 written_bytes += write_member(m_med_blocks, out, child, "med_block_cnt");
904 written_bytes += write_member(m_med_inner_blocks, out, child, "med_inner_blocks");
905
906 written_bytes += m_bp_rank.serialize(out, child, "bp_rank");
907 written_bytes += m_bp_select.serialize(out, child, "bp_select");
908
909 written_bytes += m_sml_block_min_max.serialize(out, child, "sml_blocks");
910 written_bytes += m_med_block_min_max.serialize(out, child, "med_blocks");
911
912 structure_tree::add_size(child, written_bytes);
913 return written_bytes;
914 }
915
917
921 void load(std::istream & in, const bit_vector * bp)
922 {
923 m_bp = bp;
924 read_member(m_size, in);
925 assert(m_size == bp->size());
926 read_member(m_sml_blocks, in);
927 read_member(m_med_blocks, in);
928 read_member(m_med_inner_blocks, in);
929
930 m_bp_rank.load(in, m_bp);
931 m_bp_select.load(in, m_bp);
932
933 m_sml_block_min_max.load(in);
934 m_med_block_min_max.load(in);
935 }
936
937 template <typename archive_t>
938 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
939 {
940 ar(CEREAL_NVP(m_size));
941 ar(CEREAL_NVP(m_sml_blocks));
942 ar(CEREAL_NVP(m_med_blocks));
943 ar(CEREAL_NVP(m_med_inner_blocks));
944 ar(CEREAL_NVP(m_bp_rank));
945 ar(CEREAL_NVP(m_bp_select));
946 ar(CEREAL_NVP(m_sml_block_min_max));
947 ar(CEREAL_NVP(m_med_block_min_max));
948 }
949
950 template <typename archive_t>
951 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
952 {
953 ar(CEREAL_NVP(m_size));
954 ar(CEREAL_NVP(m_sml_blocks));
955 ar(CEREAL_NVP(m_med_blocks));
956 ar(CEREAL_NVP(m_med_inner_blocks));
957 ar(CEREAL_NVP(m_bp_rank));
958 ar(CEREAL_NVP(m_bp_select));
959 ar(CEREAL_NVP(m_sml_block_min_max));
960 ar(CEREAL_NVP(m_med_block_min_max));
961 }
962
964 bool operator==(bp_support_sada const & other) const noexcept
965 {
966 return (m_bp_rank == other.m_bp_rank) && (m_bp_select == other.m_bp_select) &&
967 (m_sml_block_min_max == other.m_sml_block_min_max) &&
968 (m_med_block_min_max == other.m_med_block_min_max) && (m_size == other.m_size) &&
969 (m_sml_blocks == other.m_sml_blocks) && (m_med_blocks == other.m_med_blocks) &&
970 (m_med_inner_blocks == other.m_med_inner_blocks);
971 }
972
974 bool operator!=(bp_support_sada const & other) const noexcept { return !(*this == other); }
975};
976
977} // namespace sdsl
978
979#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.
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.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_sada for a bit_vector v.
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.
const select_type & bp_select
SS for the underlying BP sequence.
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.
bp_support_sada(const bit_vector *bp)
Constructor.
bp_support_sada(const bp_support_sada &v)
Copy constructor.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
bp_support_sada & operator=(const bp_support_sada &v)
Assignment operator.
void set_vector(const bit_vector *bp)
bp_support_sada(bp_support_sada &&bp_support)
Move constructor.
bool operator==(bp_support_sada const &other) const noexcept
Equality operator.
bit_vector::size_type size_type
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
const rank_type & bp_rank
RS for the underlying BP sequence.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
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 .
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.
const med_block_array_type & med_block_min_max
Array containing the min max tree of the medium blocks.
const sml_block_array_type & sml_block_min_max
Small blocks array.
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
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.
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(const bit_vector &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].
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
uint64_t near_fwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
uint64_t near_bwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
Near backward excess.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
void write(size_type i, size_type x)
Definition: fast_cache.hpp:36
bool exists(size_type i, size_type &x)
Definition: fast_cache.hpp:25