SDSL 3.0.1
Succinct Data Structure Library
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 <map> // for calculate_pioneers_bitmap method
12#include <stack> // for calculate_pioneers_bitmap method
13
14#include <sdsl/int_vector.hpp> // for bit_vector
16
17namespace sdsl
18{
19
20// This structure contains lookup tables
21template <typename T = void>
22struct excess
23{
24 struct impl
25 {
26 // Given an excess value x in [-8,8] and a 8-bit
27 // word w interpreted as parentheses sequence.
28 // near_fwd_pos[(x+8)<<8 | w] contains the minimal position
29 // p in [0..7] where the excess value x is reached, or 8
30 // if x is not reached in w.
31 uint8_t near_fwd_pos[(8 - (-8)) * 256];
32
33 // Given an excess value of x in [-8,8] and a 8-bit
34 // word w interpreted as parentheses sequence.
35 // near_bwd_pos[(x+8)<<8 | w] contains the maximal position
36 // p in [0..7] where the excess value x is reached, or 8
37 // if x is not reached in w.
38 uint8_t near_bwd_pos[(8 - (-8)) * 256];
39
40 // Given a 8-bit word w. word_sum[w] contains the
41 // excess value of w.
42 int8_t word_sum[256];
43
44 // Given a 8-bit word w. min[w] contains the
45 // minimal excess value in w.
46 int8_t min[256];
47
48 // Given a 8-bit word w. min_pos_max[w] contains
49 // the maximal position p in w, where min[w] is
50 // reached
51 int8_t min_pos_max[256];
52
53 // Given an excess value x in [1,8] and a 8-bit
54 // word w interpreted as parentheses sequence.
55 // min_match_pos_packed[w]:[(x-1)*4,x*4] contains
56 // the minimal position, where excess value
57 // -x is reached and 9, if there is no such position.
58 uint32_t min_match_pos_packed[256];
59
60 // Given an excess value x in [1,8] and a 8-bit
61 // word w interpreted as parentheses sequence.
62 // max_match_pos_packed[w]:[(x-1)*4,x*4] contains
63 // the maximal position, where excess value
64 // -x is reached and 9, if there is no such position.
65 uint32_t max_match_pos_packed[256];
66
67 // Given a 8-bit word w. x=min_and_info[w] contains
68 // the following information.
69 // * [0..7] the minimum excess value in w + 8 of an opening parenthesis
70 // * [8..11] the maximal position of the minimal excess value
71 // * [12..15] the number of ones in the word
72 // if w != 0, and 17 for w=0.
73 uint16_t min_open_excess_info[256];
74
76 {
77 for (int32_t x = -8; x < 8; ++x)
78 {
79 for (uint16_t w = 0; w < 256; ++w)
80 {
81 uint16_t i = (x + 8) << 8 | w;
82 near_fwd_pos[i] = 8;
83 int8_t p = 0;
84 int8_t excess = 0;
85 do {
86 excess += 1 - 2 * ((w & (1 << p)) == 0);
87 if (excess == x)
88 {
89 near_fwd_pos[i] = p;
90 break;
91 }
92 ++p;
93 } while (p < 8);
94
95 near_bwd_pos[i] = 8;
96 p = 7;
97 excess = 0;
98 do {
99 excess += 1 - 2 * ((w & (1 << p)) > 0);
100 if (excess == x)
101 {
102 near_bwd_pos[i] = p;
103 break;
104 }
105 --p;
106 } while (p > -1);
107 }
108 }
109 int_vector<> packed_mins(1, 0, 32);
110 int_vector<> packed_maxs(1, 0, 32);
111 for (uint16_t w = 0; w < 256; ++w)
112 {
113 int8_t excess = 0;
114 int8_t rev_excess = 0;
115 int32_t min_excess_of_open = 17;
116 int32_t min_excess_of_open_pos = 0;
117 uint32_t ones = 0;
118 min[w] = 8;
119 packed_mins[0] = 0x99999999U;
120 packed_maxs[0] = 0x99999999U;
121 packed_mins.width(4);
122 packed_maxs.width(4);
123 for (uint16_t p = 0; p < 8; ++p)
124 {
125 ones += (w & (1 << p)) != 0;
126 excess += 1 - 2 * ((w & (1 << p)) == 0);
127 if (excess <= min[w])
128 {
129 min[w] = excess;
130 min_pos_max[w] = p;
131 }
132 if (excess < 0 and packed_mins[-excess - 1] == 9) { packed_mins[-excess - 1] = p; }
133 if (w & (1 << p) and excess + 8 <= min_excess_of_open)
134 {
135 min_excess_of_open = excess + 8;
136 min_excess_of_open_pos = p;
137 }
138 rev_excess += 1 - 2 * ((w & (1 << (7 - p))) > 0);
139 if (rev_excess < 0 and packed_maxs[-rev_excess - 1] == 9) { packed_maxs[-rev_excess - 1] = 7 - p; }
140 }
141 word_sum[w] = excess;
142 packed_mins.width(32);
143 min_match_pos_packed[w] = packed_mins[0];
144 packed_maxs.width(32);
145 max_match_pos_packed[w] = packed_maxs[0];
146 min_open_excess_info[w] = (min_excess_of_open) | (min_excess_of_open_pos << 8) | (ones << 12);
147 }
148 }
149 };
150 static impl data;
151};
152
153template <typename T>
155
157
166{
167 bit_vector pioneer_bitmap(bp.size(), 0);
168
169 std::stack<uint64_t> opening_parenthesis;
170 uint64_t blocks = (bp.size() + block_size - 1) / block_size;
171 // calculate positions of findclose and findopen pioneers
172 for (uint64_t block_nr = 0; block_nr < blocks; ++block_nr)
173 {
174 std::map<uint64_t, uint64_t> block_and_position; // for find_open and find_close
175 std::map<uint64_t, uint64_t> matching_position; // for find_open and find_close
176 for (uint64_t i = 0, j = block_nr * block_size; i < block_size and j < bp.size(); ++i, ++j)
177 {
178 if (bp[j])
179 { // opening parenthesis
180 opening_parenthesis.push(j);
181 }
182 else
183 { // closing parenthesis
184 uint64_t position = opening_parenthesis.top();
185 uint64_t blockpos = position / block_size;
186 opening_parenthesis.pop();
187 block_and_position[blockpos] = position;
188 matching_position[blockpos] = j; // greatest j is pioneer
189 }
190 }
191 for (std::map<uint64_t, uint64_t>::const_iterator it = block_and_position.begin(),
192 end = block_and_position.end(),
193 mit = matching_position.begin();
194 it != end and it->first != block_nr;
195 ++it, ++mit)
196 {
197 // opening and closing pioneers are symmetric
198 pioneer_bitmap[it->second] = 1;
199 pioneer_bitmap[mit->second] = 1;
200 }
201 }
202 // assert that the sequence is balanced
203 assert(opening_parenthesis.empty());
204 return pioneer_bitmap;
205}
206
208
219{
220 bit_vector pioneer_bitmap(bp.size(), 0);
221
222 sorted_stack_support opening_parenthesis(bp.size());
223 uint64_t cur_pioneer_block = 0, last_start = 0, last_j = 0, cur_block = 0, first_index_in_block = 0;
224 // calculate positions of findclose and findopen pioneers
225 for (uint64_t j = 0, new_block = block_size; j < bp.size(); ++j, --new_block)
226 {
227 if (!(new_block))
228 {
229 cur_pioneer_block = j / block_size;
230 ++cur_block;
231 first_index_in_block = j;
232 new_block = block_size;
233 }
234
235 if (bp[j])
236 { // opening parenthesis
237 if (/*j < bp.size() is not necessary as the last parenthesis is always a closing one*/
238 new_block > 1 and !bp[j + 1])
239 {
240 ++j;
241 --new_block;
242 continue;
243 }
244 opening_parenthesis.push(j);
245 }
246 else
247 {
248 assert(!opening_parenthesis.empty());
249 uint64_t start = opening_parenthesis.top();
250 opening_parenthesis.pop();
251 if (start < first_index_in_block)
252 {
253 if ((start / block_size) == cur_pioneer_block)
254 {
255 pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0; // override false pioneer
256 }
257 pioneer_bitmap[start] = pioneer_bitmap[j] = 1;
258 cur_pioneer_block = start / block_size;
259 last_start = start;
260 last_j = j;
261 }
262 }
263 }
264 // assert that the sequence is balanced
265 assert(opening_parenthesis.empty());
266 return pioneer_bitmap;
267}
268
270
278template <class int_vector>
279void calculate_matches(const bit_vector & bp, int_vector & matches)
280{
281 matches = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
282 std::stack<uint64_t> opening_parenthesis;
283 for (uint64_t i = 0; i < bp.size(); ++i)
284 {
285 if (bp[i])
286 { // opening parenthesis
287 opening_parenthesis.push(i);
288 }
289 else
290 { // closing parenthesis
291 assert(!opening_parenthesis.empty());
292 uint64_t position = opening_parenthesis.top();
293 opening_parenthesis.pop();
294 matches[i] = position;
295 assert(matches[i] == position);
296 matches[position] = i;
297 assert(matches[position] == i);
298 }
299 }
300 // assert that the sequence is balanced
301 assert(opening_parenthesis.empty());
302}
303
305
313template <class int_vector>
314void calculate_enclose(const bit_vector & bp, int_vector & enclose)
315{
316 enclose = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
317 std::stack<uint64_t> opening_parenthesis;
318 for (uint64_t i = 0; i < bp.size(); ++i)
319 {
320 if (bp[i])
321 { // opening parenthesis
322 if (!opening_parenthesis.empty())
323 {
324 uint64_t position = opening_parenthesis.top();
325 enclose[i] = position;
326 assert(enclose[i] == position);
327 }
328 else
329 enclose[i] = bp.size();
330 opening_parenthesis.push(i);
331 }
332 else
333 { // closing parenthesis
334 uint64_t position = opening_parenthesis.top();
335 enclose[i] = position; // find open answer if i is a closing parenthesis
336 opening_parenthesis.pop();
337 }
338 }
339 // assert that the sequence is balanced
340 assert(opening_parenthesis.empty());
341}
342
343inline uint64_t near_find_close(const bit_vector & bp, const uint64_t i, const uint64_t block_size)
344{
345 typedef bit_vector::difference_type difference_type;
346 difference_type excess_v = 1;
347
348 const uint64_t end = ((i + 1) / block_size + 1) * block_size;
349 const uint64_t l = (((i + 1) + 7) / 8) * 8;
350 const uint64_t r = (end / 8) * 8;
351 for (uint64_t j = i + 1; j < std::min(end, l); ++j)
352 {
353 if (bp[j])
354 ++excess_v;
355 else
356 {
357 --excess_v;
358 if (excess_v == 0) { return j; }
359 }
360 }
361 const uint64_t * b = bp.data();
362 for (uint64_t j = l; j < r; j += 8)
363 {
364 if (excess_v <= 8)
365 {
366 assert(excess_v > 0);
367 uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
368 uint8_t p = (x >> ((excess_v - 1) << 2)) & 0xF;
369 if (p < 9) { return j + p; }
370 }
371 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
372 }
373 for (uint64_t j = std::max(l, r); j < end; ++j)
374 {
375 if (bp[j])
376 ++excess_v;
377 else
378 {
379 --excess_v;
380 if (excess_v == 0) { return j; }
381 }
382 }
383 return i;
384}
385
386inline uint64_t near_find_closing(const bit_vector & bp, uint64_t i, uint64_t closings, const uint64_t block_size)
387{
388 typedef bit_vector::difference_type difference_type;
389 difference_type excess_v = 0;
390 difference_type succ_excess = -closings;
391
392 const uint64_t end = (i / block_size + 1) * block_size;
393 const uint64_t l = (((i) + 7) / 8) * 8;
394 const uint64_t r = (end / 8) * 8;
395 for (uint64_t j = i; j < std::min(end, l); ++j)
396 {
397 if (bp[j])
398 ++excess_v;
399 else
400 {
401 --excess_v;
402 if (excess_v == succ_excess) { return j; }
403 }
404 }
405 const uint64_t * b = bp.data();
406 for (uint64_t j = l; j < r; j += 8)
407 {
408 if (excess_v - succ_excess <= 8)
409 {
410 uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
411 uint8_t p = (x >> (((excess_v - succ_excess) - 1) << 2)) & 0xF;
412 if (p < 9) { return j + p; }
413 }
414 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
415 }
416 for (uint64_t j = std::max(l, r); j < end; ++j)
417 {
418 if (bp[j])
419 ++excess_v;
420 else
421 {
422 --excess_v;
423 if (excess_v == succ_excess) { return j; }
424 }
425 }
426 return i - 1;
427}
428
429inline uint64_t near_fwd_excess(const bit_vector & bp,
430 uint64_t i,
432 const uint64_t block_size)
433{
434 typedef bit_vector::difference_type difference_type;
435 difference_type excess_v = rel;
436
437 const uint64_t end = (i / block_size + 1) * block_size;
438 const uint64_t l = (((i) + 7) / 8) * 8;
439 const uint64_t r = (end / 8) * 8;
440 for (uint64_t j = i; j < std::min(end, l); ++j)
441 {
442 excess_v += 1 - 2 * bp[j];
443 if (!excess_v) { return j; }
444 }
445 excess_v += 8;
446 const uint64_t * b = bp.data();
447 for (uint64_t j = l; j < r; j += 8)
448 {
449 if (excess_v >= 0 and excess_v <= 16)
450 {
451 uint32_t x = excess<>::data.near_fwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
452 if (x < 8) { return j + x; }
453 }
454 excess_v -= excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
455 }
456 excess_v -= 8;
457 for (uint64_t j = std::max(l, r); j < end; ++j)
458 {
459 excess_v += 1 - 2 * bp[j];
460 if (!excess_v) { return j; }
461 }
462 return i - 1;
463}
464
466
471inline uint64_t near_rmq(const bit_vector & bp, uint64_t l, uint64_t r, bit_vector::difference_type & min_rel_ex)
472{
473 typedef bit_vector::difference_type difference_type;
474 const uint64_t l8 = (((l + 1) + 7) / 8) * 8;
475 const uint64_t r8 = (r / 8) * 8;
476 difference_type excess_v = 0;
477 difference_type min_pos = l;
478 min_rel_ex = 0;
479 for (uint64_t j = l + 1; j < std::min(l8, r + 1); ++j)
480 {
481 if (bp[j])
482 ++excess_v;
483 else
484 {
485 --excess_v;
486 if (excess_v <= min_rel_ex)
487 {
488 min_rel_ex = excess_v;
489 min_pos = j;
490 }
491 }
492 }
493
494 const uint64_t * b = bp.data();
495 for (uint64_t j = l8; j < r8; j += 8)
496 {
497 int8_t x = excess<>::data.min[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
498 if ((excess_v + x) <= min_rel_ex)
499 {
500 min_rel_ex = excess_v + x;
501 min_pos = j + excess<>::data.min_pos_max[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
502 }
503 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
504 }
505 for (uint64_t j = std::max(l8, r8); j < r + 1; ++j)
506 {
507 if (bp[j])
508 ++excess_v;
509 else
510 {
511 --excess_v;
512 if (excess_v <= min_rel_ex)
513 {
514 min_rel_ex = excess_v;
515 min_pos = j;
516 }
517 }
518 }
519 return min_pos;
520}
521
523/* This method searches the maximal parenthesis j, with \f$ j\leq i \f$,
524 * such that \f$ excess(j) = excess(i+1)+rel \f$ and i < bp.size()-1
525 */
526inline uint64_t near_bwd_excess(const bit_vector & bp,
527 uint64_t i,
529 const uint64_t block_size)
530{
531 typedef bit_vector::difference_type difference_type;
532 difference_type excess_v = rel;
533 const difference_type begin = ((difference_type)(i) / block_size) * block_size;
534 const difference_type r = ((difference_type)(i) / 8) * 8;
535 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
536 for (difference_type j = i + 1; j >= /*begin*/ std::max(r, begin); --j)
537 {
538 if (bp[j])
539 ++excess_v;
540 else
541 --excess_v;
542 if (!excess_v) return j - 1;
543 }
544
545 excess_v += 8;
546 const uint64_t * b = bp.data();
547 for (difference_type j = r - 8; j >= l; j -= 8)
548 {
549 if (excess_v >= 0 and excess_v <= 16)
550 {
551 uint32_t x = excess<>::data.near_bwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
552 if (x < 8) { return j + x - 1; }
553 }
554 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
555 }
556 excess_v -= 8;
557 for (difference_type j = std::min(l, r); j > begin; --j)
558 {
559 if (bp[j])
560 ++excess_v;
561 else
562 --excess_v;
563 if (!excess_v) return j - 1;
564 }
565 if (0 == begin and -1 == rel) { return -1; }
566 return i + 1;
567}
568
569inline uint64_t near_find_open(const bit_vector & bp, uint64_t i, const uint64_t block_size)
570{
571 typedef bit_vector::difference_type difference_type;
572 difference_type excess_v = -1;
573 const difference_type begin = ((difference_type)(i - 1) / block_size) * block_size;
574 const difference_type r = ((difference_type)(i - 1) / 8) * 8;
575 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
576 for (difference_type j = i - 1; j >= std::max(r, begin); --j)
577 {
578 if (bp[j])
579 {
580 if (++excess_v == 0) { return j; }
581 }
582 else
583 --excess_v;
584 }
585 const uint64_t * b = bp.data();
586 for (difference_type j = r - 8; j >= l; j -= 8)
587 {
588 if (excess_v >= -8)
589 {
590 assert(excess_v < 0);
591 uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
592 uint8_t p = (x >> ((-excess_v - 1) << 2)) & 0xF;
593 if (p < 9) { return j + p; }
594 }
595 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
596 }
597 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
598 {
599 if (bp[j])
600 {
601 if (++excess_v == 0) { return j; }
602 }
603 else
604 --excess_v;
605 }
606 return i;
607}
608
609inline uint64_t near_find_opening(const bit_vector & bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
610{
611 typedef bit_vector::difference_type difference_type;
612 difference_type excess_v = 0;
613 difference_type succ_excess = openings;
614
615 const difference_type begin = ((difference_type)(i) / block_size) * block_size;
616 const difference_type r = ((difference_type)(i) / 8) * 8;
617 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
618 for (difference_type j = i; j >= std::max(r, begin); --j)
619 {
620 if (bp[j])
621 {
622 if (++excess_v == succ_excess) { return j; }
623 }
624 else
625 --excess_v;
626 }
627 const uint64_t * b = bp.data();
628 for (difference_type j = r - 8; j >= l; j -= 8)
629 {
630 if (succ_excess - excess_v <= 8)
631 {
632 assert(succ_excess - excess_v > 0);
633 uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
634 uint8_t p = (x >> ((succ_excess - excess_v - 1) << 2)) & 0xF;
635 if (p < 9) { return j + p; }
636 }
637 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
638 }
639 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
640 {
641 if (bp[j])
642 {
643 if (++excess_v == succ_excess) { return j; }
644 }
645 else
646 --excess_v;
647 }
648 return i + 1;
649}
650
652
659// TODO: implement a fast version using lookup-tables of size 8
660inline uint64_t near_enclose(const bit_vector & bp, uint64_t i, const uint64_t block_size)
661{
662 uint64_t opening_parentheses = 1;
663 for (uint64_t j = i; j + block_size - 1 > i and j > 0; --j)
664 {
665 if (bp[j - 1])
666 {
667 ++opening_parentheses;
668 if (opening_parentheses == 2) { return j - 1; }
669 }
670 else
671 --opening_parentheses;
672 }
673 return i;
674}
675
676inline uint64_t near_rmq_open(const bit_vector & bp, const uint64_t begin, const uint64_t end)
677{
678 typedef bit_vector::difference_type difference_type;
679 difference_type min_excess = end - begin + 1, ex = 0;
680 uint64_t result = end;
681
682 const uint64_t l = ((begin + 7) / 8) * 8;
683 const uint64_t r = (end / 8) * 8;
684
685 for (uint64_t k = begin; k < std::min(end, l); ++k)
686 {
687 if (bp[k])
688 {
689 ++ex;
690 if (ex <= min_excess)
691 {
692 result = k;
693 min_excess = ex;
694 }
695 }
696 else
697 {
698 --ex;
699 }
700 }
701 const uint64_t * b = bp.data();
702 for (uint64_t k = l; k < r; k += 8)
703 {
704 uint16_t x = excess<>::data.min_open_excess_info[((*(b + (k >> 6))) >> (k & 0x3F)) & 0xFF];
705 int8_t ones = (x >> 12);
706 if (ones)
707 {
708 int8_t min_ex = (x & 0xFF) - 8;
709 if (ex + min_ex <= min_excess)
710 {
711 result = k + ((x >> 8) & 0xF);
712 min_excess = ex + min_ex;
713 }
714 }
715 ex += ((ones << 1) - 8);
716 }
717 for (uint64_t k = std::max(r, l); k < end; ++k)
718 {
719 if (bp[k])
720 {
721 ++ex;
722 if (ex <= min_excess)
723 {
724 result = k;
725 min_excess = ex;
726 }
727 }
728 else
729 {
730 --ex;
731 }
732 }
733 if (min_excess <= ex) return result;
734 return end;
735}
736
737} // end namespace sdsl
738
739#endif
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:595
size_type size() const noexcept
The number of elements in the int_vector.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:566
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.
uint64_t near_find_closing(const bit_vector &bp, uint64_t i, uint64_t closings, const uint64_t block_size)
size_t block_size(void *ptr)
uint64_t near_rmq_open(const bit_vector &bp, const uint64_t begin, const uint64_t end)
void calculate_matches(const bit_vector &bp, int_vector &matches)
find_open/find_close for closing/opening parentheses.
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].
uint64_t near_find_opening(const bit_vector &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
bit_vector calculate_pioneers_bitmap(const bit_vector &bp, uint64_t block_size)
Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)
uint64_t near_find_open(const bit_vector &bp, uint64_t i, const uint64_t block_size)
uint64_t near_find_close(const bit_vector &bp, const uint64_t i, const uint64_t block_size)
bit_vector calculate_pioneers_bitmap_succinct(const bit_vector &bp, uint64_t block_size)
Space-efficient version of calculate_pioneers_bitmap.
uint64_t near_fwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
void calculate_enclose(const bit_vector &bp, int_vector &enclose)
Calculates enclose answers for a balanced parentheses sequence.
uint64_t near_bwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
Near backward excess.
uint64_t near_enclose(const bit_vector &bp, uint64_t i, const uint64_t block_size)
Find the opening parenthesis of the enclosing pair if this parenthesis is near.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
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]