SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
bp_support_algorithm.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_ALGORITHM
9#define INCLUDED_SDSL_BP_SUPPORT_ALGORITHM
10
11#include <algorithm>
12#include <assert.h>
13#include <cstdint>
14#include <map> // for calculate_pioneers_bitmap method
15#include <stack> // for calculate_pioneers_bitmap method
16#include <utility>
17
18#include <sdsl/bits.hpp>
19#include <sdsl/int_vector.hpp> // for bit_vector
21
22namespace sdsl
23{
24
25// This structure contains lookup tables
26template <typename T = void>
27struct excess
28{
29 struct impl
30 {
31 // Given an excess value x in [-8,8] and a 8-bit
32 // word w interpreted as parentheses sequence.
33 // near_fwd_pos[(x+8)<<8 | w] contains the minimal position
34 // p in [0..7] where the excess value x is reached, or 8
35 // if x is not reached in w.
36 uint8_t near_fwd_pos[(8 - (-8)) * 256];
37
38 // Given an excess value of x in [-8,8] and a 8-bit
39 // word w interpreted as parentheses sequence.
40 // near_bwd_pos[(x+8)<<8 | w] contains the maximal position
41 // p in [0..7] where the excess value x is reached, or 8
42 // if x is not reached in w.
43 uint8_t near_bwd_pos[(8 - (-8)) * 256];
44
45 // Given a 8-bit word w. word_sum[w] contains the
46 // excess value of w.
47 int8_t word_sum[256];
48
49 // Given a 8-bit word w. min[w] contains the
50 // minimal excess value in w.
51 int8_t min[256];
52
53 // Given a 8-bit word w. min_pos_max[w] contains
54 // the maximal position p in w, where min[w] is
55 // reached
56 int8_t min_pos_max[256];
57
58 // Given an excess value x in [1,8] and a 8-bit
59 // word w interpreted as parentheses sequence.
60 // min_match_pos_packed[w]:[(x-1)*4,x*4] contains
61 // the minimal position, where excess value
62 // -x is reached and 9, if there is no such position.
63 uint32_t min_match_pos_packed[256];
64
65 // Given an excess value x in [1,8] and a 8-bit
66 // word w interpreted as parentheses sequence.
67 // max_match_pos_packed[w]:[(x-1)*4,x*4] contains
68 // the maximal position, where excess value
69 // -x is reached and 9, if there is no such position.
70 uint32_t max_match_pos_packed[256];
71
72 // Given a 8-bit word w. x=min_and_info[w] contains
73 // the following information.
74 // * [0..7] the minimum excess value in w + 8 of an opening parenthesis
75 // * [8..11] the maximal position of the minimal excess value
76 // * [12..15] the number of ones in the word
77 // if w != 0, and 17 for w=0.
78 uint16_t min_open_excess_info[256];
79
81 {
82 for (int32_t x = -8; x < 8; ++x)
83 {
84 for (uint16_t w = 0; w < 256; ++w)
85 {
86 uint16_t i = (x + 8) << 8 | w;
87 near_fwd_pos[i] = 8;
88 int8_t p = 0;
89 int8_t excess = 0;
90 do
91 {
92 excess += 1 - 2 * ((w & (1 << p)) == 0);
93 if (excess == x)
94 {
95 near_fwd_pos[i] = p;
96 break;
97 }
98 ++p;
99 }
100 while (p < 8);
101
102 near_bwd_pos[i] = 8;
103 p = 7;
104 excess = 0;
105 do
106 {
107 excess += 1 - 2 * ((w & (1 << p)) > 0);
108 if (excess == x)
109 {
110 near_bwd_pos[i] = p;
111 break;
112 }
113 --p;
114 }
115 while (p > -1);
116 }
117 }
118 int_vector<> packed_mins(1, 0, 32);
119 int_vector<> packed_maxs(1, 0, 32);
120 for (uint16_t w = 0; w < 256; ++w)
121 {
122 int8_t excess = 0;
123 int8_t rev_excess = 0;
124 int32_t min_excess_of_open = 17;
125 int32_t min_excess_of_open_pos = 0;
126 uint32_t ones = 0;
127 min[w] = 8;
128 packed_mins[0] = 0x99999999U;
129 packed_maxs[0] = 0x99999999U;
130 packed_mins.width(4);
131 packed_maxs.width(4);
132 for (uint16_t p = 0; p < 8; ++p)
133 {
134 ones += (w & (1 << p)) != 0;
135 excess += 1 - 2 * ((w & (1 << p)) == 0);
136 if (excess <= min[w])
137 {
138 min[w] = excess;
139 min_pos_max[w] = p;
140 }
141 if (excess < 0 and packed_mins[-excess - 1] == 9)
142 {
143 packed_mins[-excess - 1] = p;
144 }
145 if (w & (1 << p) and excess + 8 <= min_excess_of_open)
146 {
147 min_excess_of_open = excess + 8;
148 min_excess_of_open_pos = p;
149 }
150 rev_excess += 1 - 2 * ((w & (1 << (7 - p))) > 0);
151 if (rev_excess < 0 and packed_maxs[-rev_excess - 1] == 9)
152 {
153 packed_maxs[-rev_excess - 1] = 7 - p;
154 }
155 }
156 word_sum[w] = excess;
157 packed_mins.width(32);
158 min_match_pos_packed[w] = packed_mins[0];
159 packed_maxs.width(32);
160 max_match_pos_packed[w] = packed_maxs[0];
161 min_open_excess_info[w] = (min_excess_of_open) | (min_excess_of_open_pos << 8) | (ones << 12);
162 }
163 }
164 };
165 static impl data;
166};
167
168template <typename T>
170
172
181{
182 bit_vector pioneer_bitmap(bp.size(), 0);
183
184 std::stack<uint64_t> opening_parenthesis;
185 uint64_t blocks = (bp.size() + block_size - 1) / block_size;
186 // calculate positions of findclose and findopen pioneers
187 for (uint64_t block_nr = 0; block_nr < blocks; ++block_nr)
188 {
189 std::map<uint64_t, uint64_t> block_and_position; // for find_open and find_close
190 std::map<uint64_t, uint64_t> matching_position; // for find_open and find_close
191 for (uint64_t i = 0, j = block_nr * block_size; i < block_size and j < bp.size(); ++i, ++j)
192 {
193 if (bp[j])
194 { // opening parenthesis
195 opening_parenthesis.push(j);
196 }
197 else
198 { // closing parenthesis
199 uint64_t position = opening_parenthesis.top();
200 uint64_t blockpos = position / block_size;
201 opening_parenthesis.pop();
202 block_and_position[blockpos] = position;
203 matching_position[blockpos] = j; // greatest j is pioneer
204 }
205 }
206 for (std::map<uint64_t, uint64_t>::const_iterator it = block_and_position.begin(),
207 end = block_and_position.end(),
208 mit = matching_position.begin();
209 it != end and it->first != block_nr;
210 ++it, ++mit)
211 {
212 // opening and closing pioneers are symmetric
213 pioneer_bitmap[it->second] = 1;
214 pioneer_bitmap[mit->second] = 1;
215 }
216 }
217 // assert that the sequence is balanced
218 assert(opening_parenthesis.empty());
219 return pioneer_bitmap;
220}
221
223
234{
235 bit_vector pioneer_bitmap(bp.size(), 0);
236
237 sorted_stack_support opening_parenthesis(bp.size());
238 uint64_t cur_pioneer_block = 0, last_start = 0, last_j = 0, cur_block = 0, first_index_in_block = 0;
239 // calculate positions of findclose and findopen pioneers
240 for (uint64_t j = 0, new_block = block_size; j < bp.size(); ++j, --new_block)
241 {
242 if (!(new_block))
243 {
244 cur_pioneer_block = j / block_size;
245 ++cur_block;
246 first_index_in_block = j;
247 new_block = block_size;
248 }
249
250 if (bp[j])
251 { // opening parenthesis
252 if (/*j < bp.size() is not necessary as the last parenthesis is always a closing one*/
253 new_block > 1 and !bp[j + 1])
254 {
255 ++j;
256 --new_block;
257 continue;
258 }
259 opening_parenthesis.push(j);
260 }
261 else
262 {
263 assert(!opening_parenthesis.empty());
264 uint64_t start = opening_parenthesis.top();
265 opening_parenthesis.pop();
266 if (start < first_index_in_block)
267 {
268 if ((start / block_size) == cur_pioneer_block)
269 {
270 pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0; // override false pioneer
271 }
272 pioneer_bitmap[start] = pioneer_bitmap[j] = 1;
273 cur_pioneer_block = start / block_size;
274 last_start = start;
275 last_j = j;
276 }
277 }
278 }
279 // assert that the sequence is balanced
280 assert(opening_parenthesis.empty());
281 return pioneer_bitmap;
282}
283
285
293template <class int_vector>
294void calculate_matches(bit_vector const & bp, int_vector & matches)
295{
296 matches = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
297 std::stack<uint64_t> opening_parenthesis;
298 for (uint64_t i = 0; i < bp.size(); ++i)
299 {
300 if (bp[i])
301 { // opening parenthesis
302 opening_parenthesis.push(i);
303 }
304 else
305 { // closing parenthesis
306 assert(!opening_parenthesis.empty());
307 uint64_t position = opening_parenthesis.top();
308 opening_parenthesis.pop();
309 matches[i] = position;
310 assert(matches[i] == position);
311 matches[position] = i;
312 assert(matches[position] == i);
313 }
314 }
315 // assert that the sequence is balanced
316 assert(opening_parenthesis.empty());
317}
318
320
328template <class int_vector>
329void calculate_enclose(bit_vector const & bp, int_vector & enclose)
330{
331 enclose = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
332 std::stack<uint64_t> opening_parenthesis;
333 for (uint64_t i = 0; i < bp.size(); ++i)
334 {
335 if (bp[i])
336 { // opening parenthesis
337 if (!opening_parenthesis.empty())
338 {
339 uint64_t position = opening_parenthesis.top();
340 enclose[i] = position;
341 assert(enclose[i] == position);
342 }
343 else
344 enclose[i] = bp.size();
345 opening_parenthesis.push(i);
346 }
347 else
348 { // closing parenthesis
349 uint64_t position = opening_parenthesis.top();
350 enclose[i] = position; // find open answer if i is a closing parenthesis
351 opening_parenthesis.pop();
352 }
353 }
354 // assert that the sequence is balanced
355 assert(opening_parenthesis.empty());
356}
357
358inline uint64_t near_find_close(bit_vector const & bp, const uint64_t i, const uint64_t block_size)
359{
360 typedef bit_vector::difference_type difference_type;
361 difference_type excess_v = 1;
362
363 const uint64_t end = ((i + 1) / block_size + 1) * block_size;
364 const uint64_t l = (((i + 1) + 7) / 8) * 8;
365 const uint64_t r = (end / 8) * 8;
366 for (uint64_t j = i + 1; j < std::min(end, l); ++j)
367 {
368 if (bp[j])
369 ++excess_v;
370 else
371 {
372 --excess_v;
373 if (excess_v == 0)
374 {
375 return j;
376 }
377 }
378 }
379 uint64_t const * b = bp.data();
380 for (uint64_t j = l; j < r; j += 8)
381 {
382 if (excess_v <= 8)
383 {
384 assert(excess_v > 0);
385 uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
386 uint8_t p = (x >> ((excess_v - 1) << 2)) & 0xF;
387 if (p < 9)
388 {
389 return j + p;
390 }
391 }
392 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
393 }
394 for (uint64_t j = std::max(l, r); j < end; ++j)
395 {
396 if (bp[j])
397 ++excess_v;
398 else
399 {
400 --excess_v;
401 if (excess_v == 0)
402 {
403 return j;
404 }
405 }
406 }
407 return i;
408}
409
410inline uint64_t near_find_closing(bit_vector const & bp, uint64_t i, uint64_t closings, const uint64_t block_size)
411{
412 typedef bit_vector::difference_type difference_type;
413 difference_type excess_v = 0;
414 difference_type succ_excess = -closings;
415
416 const uint64_t end = (i / block_size + 1) * block_size;
417 const uint64_t l = (((i) + 7) / 8) * 8;
418 const uint64_t r = (end / 8) * 8;
419 for (uint64_t j = i; j < std::min(end, l); ++j)
420 {
421 if (bp[j])
422 ++excess_v;
423 else
424 {
425 --excess_v;
426 if (excess_v == succ_excess)
427 {
428 return j;
429 }
430 }
431 }
432 uint64_t const * b = bp.data();
433 for (uint64_t j = l; j < r; j += 8)
434 {
435 if (excess_v - succ_excess <= 8)
436 {
437 uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
438 uint8_t p = (x >> (((excess_v - succ_excess) - 1) << 2)) & 0xF;
439 if (p < 9)
440 {
441 return j + p;
442 }
443 }
444 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
445 }
446 for (uint64_t j = std::max(l, r); j < end; ++j)
447 {
448 if (bp[j])
449 ++excess_v;
450 else
451 {
452 --excess_v;
453 if (excess_v == succ_excess)
454 {
455 return j;
456 }
457 }
458 }
459 return i - 1;
460}
461
462inline uint64_t
463near_fwd_excess(bit_vector const & bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
464{
465 typedef bit_vector::difference_type difference_type;
466 difference_type excess_v = rel;
467
468 const uint64_t end = (i / block_size + 1) * block_size;
469 const uint64_t l = (((i) + 7) / 8) * 8;
470 const uint64_t r = (end / 8) * 8;
471 for (uint64_t j = i; j < std::min(end, l); ++j)
472 {
473 excess_v += 1 - 2 * bp[j];
474 if (!excess_v)
475 {
476 return j;
477 }
478 }
479 excess_v += 8;
480 uint64_t const * b = bp.data();
481 for (uint64_t j = l; j < r; j += 8)
482 {
483 if (excess_v >= 0 and excess_v <= 16)
484 {
485 uint32_t x = excess<>::data.near_fwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
486 if (x < 8)
487 {
488 return j + x;
489 }
490 }
491 excess_v -= excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
492 }
493 excess_v -= 8;
494 for (uint64_t j = std::max(l, r); j < end; ++j)
495 {
496 excess_v += 1 - 2 * bp[j];
497 if (!excess_v)
498 {
499 return j;
500 }
501 }
502 return i - 1;
503}
504
506
511inline uint64_t near_rmq(bit_vector const & bp, uint64_t l, uint64_t r, bit_vector::difference_type & min_rel_ex)
512{
513 typedef bit_vector::difference_type difference_type;
514 const uint64_t l8 = (((l + 1) + 7) / 8) * 8;
515 const uint64_t r8 = (r / 8) * 8;
516 difference_type excess_v = 0;
517 difference_type min_pos = l;
518 min_rel_ex = 0;
519 for (uint64_t j = l + 1; j < std::min(l8, r + 1); ++j)
520 {
521 if (bp[j])
522 ++excess_v;
523 else
524 {
525 --excess_v;
526 if (excess_v <= min_rel_ex)
527 {
528 min_rel_ex = excess_v;
529 min_pos = j;
530 }
531 }
532 }
533
534 uint64_t const * b = bp.data();
535 for (uint64_t j = l8; j < r8; j += 8)
536 {
537 int8_t x = excess<>::data.min[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
538 if ((excess_v + x) <= min_rel_ex)
539 {
540 min_rel_ex = excess_v + x;
541 min_pos = j + excess<>::data.min_pos_max[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
542 }
543 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
544 }
545 for (uint64_t j = std::max(l8, r8); j < r + 1; ++j)
546 {
547 if (bp[j])
548 ++excess_v;
549 else
550 {
551 --excess_v;
552 if (excess_v <= min_rel_ex)
553 {
554 min_rel_ex = excess_v;
555 min_pos = j;
556 }
557 }
558 }
559 return min_pos;
560}
561
563/* This method searches the maximal parenthesis j, with \f$ j\leq i \f$,
564 * such that \f$ excess(j) = excess(i+1)+rel \f$ and i < bp.size()-1
565 */
566inline uint64_t
567near_bwd_excess(bit_vector const & bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
568{
569 typedef bit_vector::difference_type difference_type;
570 difference_type excess_v = rel;
571 const difference_type begin = ((difference_type)(i) / block_size) * block_size;
572 const difference_type r = ((difference_type)(i) / 8) * 8;
573 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
574 for (difference_type j = i + 1; j >= /*begin*/ std::max(r, begin); --j)
575 {
576 if (bp[j])
577 ++excess_v;
578 else
579 --excess_v;
580 if (!excess_v)
581 return j - 1;
582 }
583
584 excess_v += 8;
585 uint64_t const * b = bp.data();
586 for (difference_type j = r - 8; j >= l; j -= 8)
587 {
588 if (excess_v >= 0 and excess_v <= 16)
589 {
590 uint32_t x = excess<>::data.near_bwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
591 if (x < 8)
592 {
593 return j + x - 1;
594 }
595 }
596 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
597 }
598 excess_v -= 8;
599 for (difference_type j = std::min(l, r); j > begin; --j)
600 {
601 if (bp[j])
602 ++excess_v;
603 else
604 --excess_v;
605 if (!excess_v)
606 return j - 1;
607 }
608 if (0 == begin and -1 == rel)
609 {
610 return -1;
611 }
612 return i + 1;
613}
614
615inline uint64_t near_find_open(bit_vector const & bp, uint64_t i, const uint64_t block_size)
616{
617 typedef bit_vector::difference_type difference_type;
618 difference_type excess_v = -1;
619 const difference_type begin = ((difference_type)(i - 1) / block_size) * block_size;
620 const difference_type r = ((difference_type)(i - 1) / 8) * 8;
621 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
622 for (difference_type j = i - 1; j >= std::max(r, begin); --j)
623 {
624 if (bp[j])
625 {
626 if (++excess_v == 0)
627 {
628 return j;
629 }
630 }
631 else
632 --excess_v;
633 }
634 uint64_t const * b = bp.data();
635 for (difference_type j = r - 8; j >= l; j -= 8)
636 {
637 if (excess_v >= -8)
638 {
639 assert(excess_v < 0);
640 uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
641 uint8_t p = (x >> ((-excess_v - 1) << 2)) & 0xF;
642 if (p < 9)
643 {
644 return j + p;
645 }
646 }
647 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
648 }
649 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
650 {
651 if (bp[j])
652 {
653 if (++excess_v == 0)
654 {
655 return j;
656 }
657 }
658 else
659 --excess_v;
660 }
661 return i;
662}
663
664inline uint64_t near_find_opening(bit_vector const & bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
665{
666 typedef bit_vector::difference_type difference_type;
667 difference_type excess_v = 0;
668 difference_type succ_excess = openings;
669
670 const difference_type begin = ((difference_type)(i) / block_size) * block_size;
671 const difference_type r = ((difference_type)(i) / 8) * 8;
672 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
673 for (difference_type j = i; j >= std::max(r, begin); --j)
674 {
675 if (bp[j])
676 {
677 if (++excess_v == succ_excess)
678 {
679 return j;
680 }
681 }
682 else
683 --excess_v;
684 }
685 uint64_t const * b = bp.data();
686 for (difference_type j = r - 8; j >= l; j -= 8)
687 {
688 if (succ_excess - excess_v <= 8)
689 {
690 assert(succ_excess - excess_v > 0);
691 uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
692 uint8_t p = (x >> ((succ_excess - excess_v - 1) << 2)) & 0xF;
693 if (p < 9)
694 {
695 return j + p;
696 }
697 }
698 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
699 }
700 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
701 {
702 if (bp[j])
703 {
704 if (++excess_v == succ_excess)
705 {
706 return j;
707 }
708 }
709 else
710 --excess_v;
711 }
712 return i + 1;
713}
714
716
723// TODO: implement a fast version using lookup-tables of size 8
724inline uint64_t near_enclose(bit_vector const & bp, uint64_t i, const uint64_t block_size)
725{
726 uint64_t opening_parentheses = 1;
727 for (uint64_t j = i; j + block_size - 1 > i and j > 0; --j)
728 {
729 if (bp[j - 1])
730 {
731 ++opening_parentheses;
732 if (opening_parentheses == 2)
733 {
734 return j - 1;
735 }
736 }
737 else
738 --opening_parentheses;
739 }
740 return i;
741}
742
743inline uint64_t near_rmq_open(bit_vector const & bp, const uint64_t begin, const uint64_t end)
744{
745 typedef bit_vector::difference_type difference_type;
746 difference_type min_excess = end - begin + 1, ex = 0;
747 uint64_t result = end;
748
749 const uint64_t l = ((begin + 7) / 8) * 8;
750 const uint64_t r = (end / 8) * 8;
751
752 for (uint64_t k = begin; k < std::min(end, l); ++k)
753 {
754 if (bp[k])
755 {
756 ++ex;
757 if (ex <= min_excess)
758 {
759 result = k;
760 min_excess = ex;
761 }
762 }
763 else
764 {
765 --ex;
766 }
767 }
768 uint64_t const * b = bp.data();
769 for (uint64_t k = l; k < r; k += 8)
770 {
771 uint16_t x = excess<>::data.min_open_excess_info[((*(b + (k >> 6))) >> (k & 0x3F)) & 0xFF];
772 int8_t ones = (x >> 12);
773 if (ones)
774 {
775 int8_t min_ex = (x & 0xFF) - 8;
776 if (ex + min_ex <= min_excess)
777 {
778 result = k + ((x >> 8) & 0xF);
779 min_excess = ex + min_ex;
780 }
781 }
782 ex += ((ones << 1) - 8);
783 }
784 for (uint64_t k = std::max(r, l); k < end; ++k)
785 {
786 if (bp[k])
787 {
788 ++ex;
789 if (ex <= min_excess)
790 {
791 result = k;
792 min_excess = ex;
793 }
794 }
795 else
796 {
797 --ex;
798 }
799 }
800 if (min_excess <= ex)
801 return result;
802 return end;
803}
804
805} // end namespace sdsl
806
807#endif
bits.hpp contains the sdsl::bits class.
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
size_type size() const noexcept
The number of elements in the int_vector.
A stack which contains strictly increasing numbers in the range from to .
size_type top() const
Returns the topmost index on the stack.
void pop()
Pop the topmost index of the stack.
bool empty() const
Returns if the stack is empty.
void push(size_type x)
Push the index x of vector vec onto the stack.
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
bit_vector calculate_pioneers_bitmap_succinct(bit_vector const &bp, uint64_t block_size)
Space-efficient version of calculate_pioneers_bitmap.
size_t block_size(void *ptr)
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_fwd_excess(bit_vector const &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
uint64_t near_find_closing(bit_vector const &bp, uint64_t i, uint64_t closings, 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.
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.
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].
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)
uint64_t near_find_opening(bit_vector const &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
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.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:652
uint8_t near_bwd_pos[(8 -(-8)) *256]
uint8_t near_fwd_pos[(8 -(-8)) *256]
uint32_t max_match_pos_packed[256]
uint16_t min_open_excess_info[256]
uint32_t min_match_pos_packed[256]