SDSL 3.0.3
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, 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 first_index_in_block = j;
246 new_block = block_size;
247 }
248
249 if (bp[j])
250 { // opening parenthesis
251 if (/*j < bp.size() is not necessary as the last parenthesis is always a closing one*/
252 new_block > 1 and !bp[j + 1])
253 {
254 ++j;
255 --new_block;
256 continue;
257 }
258 opening_parenthesis.push(j);
259 }
260 else
261 {
262 assert(!opening_parenthesis.empty());
263 uint64_t start = opening_parenthesis.top();
264 opening_parenthesis.pop();
265 if (start < first_index_in_block)
266 {
267 if ((start / block_size) == cur_pioneer_block)
268 {
269 pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0; // override false pioneer
270 }
271 pioneer_bitmap[start] = pioneer_bitmap[j] = 1;
272 cur_pioneer_block = start / block_size;
273 last_start = start;
274 last_j = j;
275 }
276 }
277 }
278 // assert that the sequence is balanced
279 assert(opening_parenthesis.empty());
280 return pioneer_bitmap;
281}
282
284
292template <class int_vector>
293void calculate_matches(bit_vector const & bp, int_vector & matches)
294{
295 matches = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
296 std::stack<uint64_t> opening_parenthesis;
297 for (uint64_t i = 0; i < bp.size(); ++i)
298 {
299 if (bp[i])
300 { // opening parenthesis
301 opening_parenthesis.push(i);
302 }
303 else
304 { // closing parenthesis
305 assert(!opening_parenthesis.empty());
306 uint64_t position = opening_parenthesis.top();
307 opening_parenthesis.pop();
308 matches[i] = position;
309 assert(matches[i] == position);
310 matches[position] = i;
311 assert(matches[position] == i);
312 }
313 }
314 // assert that the sequence is balanced
315 assert(opening_parenthesis.empty());
316}
317
319
327template <class int_vector>
328void calculate_enclose(bit_vector const & bp, int_vector & enclose)
329{
330 enclose = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
331 std::stack<uint64_t> opening_parenthesis;
332 for (uint64_t i = 0; i < bp.size(); ++i)
333 {
334 if (bp[i])
335 { // opening parenthesis
336 if (!opening_parenthesis.empty())
337 {
338 uint64_t position = opening_parenthesis.top();
339 enclose[i] = position;
340 assert(enclose[i] == position);
341 }
342 else
343 enclose[i] = bp.size();
344 opening_parenthesis.push(i);
345 }
346 else
347 { // closing parenthesis
348 uint64_t position = opening_parenthesis.top();
349 enclose[i] = position; // find open answer if i is a closing parenthesis
350 opening_parenthesis.pop();
351 }
352 }
353 // assert that the sequence is balanced
354 assert(opening_parenthesis.empty());
355}
356
357inline uint64_t near_find_close(bit_vector const & bp, const uint64_t i, const uint64_t block_size)
358{
360 difference_type excess_v = 1;
361
362 const uint64_t end = ((i + 1) / block_size + 1) * block_size;
363 const uint64_t l = (((i + 1) + 7) / 8) * 8;
364 const uint64_t r = (end / 8) * 8;
365 for (uint64_t j = i + 1; j < std::min(end, l); ++j)
366 {
367 if (bp[j])
368 ++excess_v;
369 else
370 {
371 --excess_v;
372 if (excess_v == 0)
373 {
374 return j;
375 }
376 }
377 }
378 uint64_t const * b = bp.data();
379 for (uint64_t j = l; j < r; j += 8)
380 {
381 if (excess_v <= 8)
382 {
383 assert(excess_v > 0);
384 uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
385 uint8_t p = (x >> ((excess_v - 1) << 2)) & 0xF;
386 if (p < 9)
387 {
388 return j + p;
389 }
390 }
391 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
392 }
393 for (uint64_t j = std::max(l, r); j < end; ++j)
394 {
395 if (bp[j])
396 ++excess_v;
397 else
398 {
399 --excess_v;
400 if (excess_v == 0)
401 {
402 return j;
403 }
404 }
405 }
406 return i;
407}
408
409inline uint64_t near_find_closing(bit_vector const & bp, uint64_t i, uint64_t closings, const uint64_t block_size)
410{
412 difference_type excess_v = 0;
413 difference_type succ_excess = -closings;
414
415 const uint64_t end = (i / block_size + 1) * block_size;
416 const uint64_t l = (((i) + 7) / 8) * 8;
417 const uint64_t r = (end / 8) * 8;
418 for (uint64_t j = i; j < std::min(end, l); ++j)
419 {
420 if (bp[j])
421 ++excess_v;
422 else
423 {
424 --excess_v;
425 if (excess_v == succ_excess)
426 {
427 return j;
428 }
429 }
430 }
431 uint64_t const * b = bp.data();
432 for (uint64_t j = l; j < r; j += 8)
433 {
434 if (excess_v - succ_excess <= 8)
435 {
436 uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
437 uint8_t p = (x >> (((excess_v - succ_excess) - 1) << 2)) & 0xF;
438 if (p < 9)
439 {
440 return j + p;
441 }
442 }
443 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
444 }
445 for (uint64_t j = std::max(l, r); j < end; ++j)
446 {
447 if (bp[j])
448 ++excess_v;
449 else
450 {
451 --excess_v;
452 if (excess_v == succ_excess)
453 {
454 return j;
455 }
456 }
457 }
458 return i - 1;
459}
460
461inline uint64_t
462near_fwd_excess(bit_vector const & bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
463{
465 difference_type excess_v = rel;
466
467 const uint64_t end = (i / block_size + 1) * block_size;
468 const uint64_t l = (((i) + 7) / 8) * 8;
469 const uint64_t r = (end / 8) * 8;
470 for (uint64_t j = i; j < std::min(end, l); ++j)
471 {
472 excess_v += 1 - 2 * bp[j];
473 if (!excess_v)
474 {
475 return j;
476 }
477 }
478 excess_v += 8;
479 uint64_t const * b = bp.data();
480 for (uint64_t j = l; j < r; j += 8)
481 {
482 if (excess_v >= 0 and excess_v <= 16)
483 {
484 uint32_t x = excess<>::data.near_fwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
485 if (x < 8)
486 {
487 return j + x;
488 }
489 }
490 excess_v -= excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
491 }
492 excess_v -= 8;
493 for (uint64_t j = std::max(l, r); j < end; ++j)
494 {
495 excess_v += 1 - 2 * bp[j];
496 if (!excess_v)
497 {
498 return j;
499 }
500 }
501 return i - 1;
502}
503
505
510inline uint64_t near_rmq(bit_vector const & bp, uint64_t l, uint64_t r, bit_vector::difference_type & min_rel_ex)
511{
513 const uint64_t l8 = (((l + 1) + 7) / 8) * 8;
514 const uint64_t r8 = (r / 8) * 8;
515 difference_type excess_v = 0;
516 difference_type min_pos = l;
517 min_rel_ex = 0;
518 for (uint64_t j = l + 1; j < std::min(l8, r + 1); ++j)
519 {
520 if (bp[j])
521 ++excess_v;
522 else
523 {
524 --excess_v;
525 if (excess_v <= min_rel_ex)
526 {
527 min_rel_ex = excess_v;
528 min_pos = j;
529 }
530 }
531 }
532
533 uint64_t const * b = bp.data();
534 for (uint64_t j = l8; j < r8; j += 8)
535 {
536 int8_t x = excess<>::data.min[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
537 if ((excess_v + x) <= min_rel_ex)
538 {
539 min_rel_ex = excess_v + x;
540 min_pos = j + excess<>::data.min_pos_max[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
541 }
542 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
543 }
544 for (uint64_t j = std::max(l8, r8); j < r + 1; ++j)
545 {
546 if (bp[j])
547 ++excess_v;
548 else
549 {
550 --excess_v;
551 if (excess_v <= min_rel_ex)
552 {
553 min_rel_ex = excess_v;
554 min_pos = j;
555 }
556 }
557 }
558 return min_pos;
559}
560
562/* This method searches the maximal parenthesis j, with \f$ j\leq i \f$,
563 * such that \f$ excess(j) = excess(i+1)+rel \f$ and i < bp.size()-1
564 */
565inline uint64_t
566near_bwd_excess(bit_vector const & bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
567{
569 difference_type excess_v = rel;
570 const difference_type begin = ((difference_type)(i) / block_size) * block_size;
571 const difference_type r = ((difference_type)(i) / 8) * 8;
572 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
573 for (difference_type j = i + 1; j >= /*begin*/ std::max(r, begin); --j)
574 {
575 if (bp[j])
576 ++excess_v;
577 else
578 --excess_v;
579 if (!excess_v)
580 return j - 1;
581 }
582
583 excess_v += 8;
584 uint64_t const * b = bp.data();
585 for (difference_type j = r - 8; j >= l; j -= 8)
586 {
587 if (excess_v >= 0 and excess_v <= 16)
588 {
589 uint32_t x = excess<>::data.near_bwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
590 if (x < 8)
591 {
592 return j + x - 1;
593 }
594 }
595 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
596 }
597 excess_v -= 8;
598 for (difference_type j = std::min(l, r); j > begin; --j)
599 {
600 if (bp[j])
601 ++excess_v;
602 else
603 --excess_v;
604 if (!excess_v)
605 return j - 1;
606 }
607 if (0 == begin and -1 == rel)
608 {
609 return -1;
610 }
611 return i + 1;
612}
613
614inline uint64_t near_find_open(bit_vector const & bp, uint64_t i, const uint64_t block_size)
615{
617 difference_type excess_v = -1;
618 const difference_type begin = ((difference_type)(i - 1) / block_size) * block_size;
619 const difference_type r = ((difference_type)(i - 1) / 8) * 8;
620 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
621 for (difference_type j = i - 1; j >= std::max(r, begin); --j)
622 {
623 if (bp[j])
624 {
625 if (++excess_v == 0)
626 {
627 return j;
628 }
629 }
630 else
631 --excess_v;
632 }
633 uint64_t const * b = bp.data();
634 for (difference_type j = r - 8; j >= l; j -= 8)
635 {
636 if (excess_v >= -8)
637 {
638 assert(excess_v < 0);
639 uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
640 uint8_t p = (x >> ((-excess_v - 1) << 2)) & 0xF;
641 if (p < 9)
642 {
643 return j + p;
644 }
645 }
646 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
647 }
648 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
649 {
650 if (bp[j])
651 {
652 if (++excess_v == 0)
653 {
654 return j;
655 }
656 }
657 else
658 --excess_v;
659 }
660 return i;
661}
662
663inline uint64_t near_find_opening(bit_vector const & bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
664{
666 difference_type excess_v = 0;
667 difference_type succ_excess = openings;
668
669 const difference_type begin = ((difference_type)(i) / block_size) * block_size;
670 const difference_type r = ((difference_type)(i) / 8) * 8;
671 const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
672 for (difference_type j = i; j >= std::max(r, begin); --j)
673 {
674 if (bp[j])
675 {
676 if (++excess_v == succ_excess)
677 {
678 return j;
679 }
680 }
681 else
682 --excess_v;
683 }
684 uint64_t const * b = bp.data();
685 for (difference_type j = r - 8; j >= l; j -= 8)
686 {
687 if (succ_excess - excess_v <= 8)
688 {
689 assert(succ_excess - excess_v > 0);
690 uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
691 uint8_t p = (x >> ((succ_excess - excess_v - 1) << 2)) & 0xF;
692 if (p < 9)
693 {
694 return j + p;
695 }
696 }
697 excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
698 }
699 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
700 {
701 if (bp[j])
702 {
703 if (++excess_v == succ_excess)
704 {
705 return j;
706 }
707 }
708 else
709 --excess_v;
710 }
711 return i + 1;
712}
713
715
722// TODO: implement a fast version using lookup-tables of size 8
723inline uint64_t near_enclose(bit_vector const & bp, uint64_t i, const uint64_t block_size)
724{
725 uint64_t opening_parentheses = 1;
726 for (uint64_t j = i; j + block_size - 1 > i and j > 0; --j)
727 {
728 if (bp[j - 1])
729 {
730 ++opening_parentheses;
731 if (opening_parentheses == 2)
732 {
733 return j - 1;
734 }
735 }
736 else
737 --opening_parentheses;
738 }
739 return i;
740}
741
742inline uint64_t near_rmq_open(bit_vector const & bp, const uint64_t begin, const uint64_t end)
743{
745 difference_type min_excess = end - begin + 1, ex = 0;
746 uint64_t result = end;
747
748 const uint64_t l = ((begin + 7) / 8) * 8;
749 const uint64_t r = (end / 8) * 8;
750
751 for (uint64_t k = begin; k < std::min(end, l); ++k)
752 {
753 if (bp[k])
754 {
755 ++ex;
756 if (ex <= min_excess)
757 {
758 result = k;
759 min_excess = ex;
760 }
761 }
762 else
763 {
764 --ex;
765 }
766 }
767 uint64_t const * b = bp.data();
768 for (uint64_t k = l; k < r; k += 8)
769 {
770 uint16_t x = excess<>::data.min_open_excess_info[((*(b + (k >> 6))) >> (k & 0x3F)) & 0xFF];
771 int8_t ones = (x >> 12);
772 if (ones)
773 {
774 int8_t min_ex = (x & 0xFF) - 8;
775 if (ex + min_ex <= min_excess)
776 {
777 result = k + ((x >> 8) & 0xF);
778 min_excess = ex + min_ex;
779 }
780 }
781 ex += ((ones << 1) - 8);
782 }
783 for (uint64_t k = std::max(r, l); k < end; ++k)
784 {
785 if (bp[k])
786 {
787 ++ex;
788 if (ex <= min_excess)
789 {
790 result = k;
791 min_excess = ex;
792 }
793 }
794 else
795 {
796 --ex;
797 }
798 }
799 if (min_excess <= ex)
800 return result;
801 return end;
802}
803
804} // end namespace sdsl
805
806#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)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
uint64_t near_find_close(bit_vector const &bp, const uint64_t i, const uint64_t block_size)
void calculate_matches(bit_vector const &bp, int_vector &matches)
find_open/find_close for closing/opening parentheses.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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]