8 #ifndef INCLUDED_SDSL_BP_SUPPORT_ALGORITHM
9 #define INCLUDED_SDSL_BP_SUPPORT_ALGORITHM
21 template <
typename T =
void>
77 for (int32_t x = -8; x < 8; ++x)
79 for (uint16_t w = 0; w < 256; ++w)
81 uint16_t i = (x + 8) << 8 | w;
86 excess += 1 - 2 * ((w & (1 << p)) == 0);
99 excess += 1 - 2 * ((w & (1 << p)) > 0);
111 for (uint16_t w = 0; w < 256; ++w)
114 int8_t rev_excess = 0;
115 int32_t min_excess_of_open = 17;
116 int32_t min_excess_of_open_pos = 0;
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)
125 ones += (w & (1 << p)) != 0;
126 excess += 1 - 2 * ((w & (1 << p)) == 0);
133 if (w & (1 << p) and
excess + 8 <= min_excess_of_open)
135 min_excess_of_open =
excess + 8;
136 min_excess_of_open_pos = p;
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; }
142 packed_mins.
width(32);
144 packed_maxs.
width(32);
153 template <
typename T>
169 std::stack<uint64_t> opening_parenthesis;
172 for (uint64_t block_nr = 0; block_nr < blocks; ++block_nr)
174 std::map<uint64_t, uint64_t> block_and_position;
175 std::map<uint64_t, uint64_t> matching_position;
180 opening_parenthesis.push(j);
184 uint64_t position = opening_parenthesis.top();
186 opening_parenthesis.pop();
187 block_and_position[blockpos] = position;
188 matching_position[blockpos] = j;
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;
198 pioneer_bitmap[it->second] = 1;
199 pioneer_bitmap[mit->second] = 1;
203 assert(opening_parenthesis.empty());
204 return pioneer_bitmap;
223 uint64_t cur_pioneer_block = 0, last_start = 0, last_j = 0, cur_block = 0, first_index_in_block = 0;
225 for (uint64_t j = 0, new_block =
block_size; j < bp.
size(); ++j, --new_block)
231 first_index_in_block = j;
238 new_block > 1 and !bp[j + 1])
244 opening_parenthesis.
push(j);
248 assert(!opening_parenthesis.
empty());
249 uint64_t start = opening_parenthesis.
top();
250 opening_parenthesis.
pop();
251 if (start < first_index_in_block)
253 if ((start /
block_size) == cur_pioneer_block)
255 pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0;
257 pioneer_bitmap[start] = pioneer_bitmap[j] = 1;
265 assert(opening_parenthesis.
empty());
266 return pioneer_bitmap;
278 template <
class int_vector>
282 std::stack<uint64_t> opening_parenthesis;
283 for (uint64_t i = 0; i < bp.
size(); ++i)
287 opening_parenthesis.push(i);
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);
301 assert(opening_parenthesis.empty());
313 template <
class int_vector>
317 std::stack<uint64_t> opening_parenthesis;
318 for (uint64_t i = 0; i < bp.
size(); ++i)
322 if (!opening_parenthesis.empty())
324 uint64_t position = opening_parenthesis.top();
325 enclose[i] = position;
326 assert(enclose[i] == position);
329 enclose[i] = bp.
size();
330 opening_parenthesis.push(i);
334 uint64_t position = opening_parenthesis.top();
335 enclose[i] = position;
336 opening_parenthesis.pop();
340 assert(opening_parenthesis.empty());
346 difference_type excess_v = 1;
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)
358 if (excess_v == 0) {
return j; }
361 const uint64_t * b = bp.
data();
362 for (uint64_t j = l; j < r; j += 8)
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; }
371 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
373 for (uint64_t j = std::max(l, r); j < end; ++j)
380 if (excess_v == 0) {
return j; }
389 difference_type excess_v = 0;
390 difference_type succ_excess = -closings;
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)
402 if (excess_v == succ_excess) {
return j; }
405 const uint64_t * b = bp.
data();
406 for (uint64_t j = l; j < r; j += 8)
408 if (excess_v - succ_excess <= 8)
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; }
414 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
416 for (uint64_t j = std::max(l, r); j < end; ++j)
423 if (excess_v == succ_excess) {
return j; }
435 difference_type excess_v = rel;
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)
442 excess_v += 1 - 2 * bp[j];
443 if (!excess_v) {
return j; }
446 const uint64_t * b = bp.
data();
447 for (uint64_t j = l; j < r; j += 8)
449 if (excess_v >= 0 and excess_v <= 16)
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; }
454 excess_v -=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
457 for (uint64_t j = std::max(l, r); j < end; ++j)
459 excess_v += 1 - 2 * bp[j];
460 if (!excess_v) {
return j; }
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;
479 for (uint64_t j = l + 1; j < std::min(l8, r + 1); ++j)
486 if (excess_v <= min_rel_ex)
488 min_rel_ex = excess_v;
494 const uint64_t * b = bp.
data();
495 for (uint64_t j = l8; j < r8; j += 8)
497 int8_t x =
excess<>::data.min[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
498 if ((excess_v + x) <= min_rel_ex)
500 min_rel_ex = excess_v + x;
501 min_pos = j +
excess<>::data.min_pos_max[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
503 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
505 for (uint64_t j = std::max(l8, r8); j < r + 1; ++j)
512 if (excess_v <= min_rel_ex)
514 min_rel_ex = excess_v;
532 difference_type excess_v = rel;
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 >= std::max(r, begin); --j)
542 if (!excess_v)
return j - 1;
546 const uint64_t * b = bp.
data();
547 for (difference_type j = r - 8; j >= l; j -= 8)
549 if (excess_v >= 0 and excess_v <= 16)
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; }
554 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
557 for (difference_type j = std::min(l, r); j > begin; --j)
563 if (!excess_v)
return j - 1;
565 if (0 == begin and -1 == rel) {
return -1; }
572 difference_type excess_v = -1;
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)
580 if (++excess_v == 0) {
return j; }
585 const uint64_t * b = bp.
data();
586 for (difference_type j = r - 8; j >= l; j -= 8)
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; }
595 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
597 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
601 if (++excess_v == 0) {
return j; }
612 difference_type excess_v = 0;
613 difference_type succ_excess = openings;
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)
622 if (++excess_v == succ_excess) {
return j; }
627 const uint64_t * b = bp.
data();
628 for (difference_type j = r - 8; j >= l; j -= 8)
630 if (succ_excess - excess_v <= 8)
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; }
637 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
639 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
643 if (++excess_v == succ_excess) {
return j; }
662 uint64_t opening_parentheses = 1;
663 for (uint64_t j = i; j +
block_size - 1 > i and j > 0; --j)
667 ++opening_parentheses;
668 if (opening_parentheses == 2) {
return j - 1; }
671 --opening_parentheses;
679 difference_type min_excess = end - begin + 1, ex = 0;
680 uint64_t result = end;
682 const uint64_t l = ((begin + 7) / 8) * 8;
683 const uint64_t r = (end / 8) * 8;
685 for (uint64_t k = begin; k < std::min(end, l); ++k)
690 if (ex <= min_excess)
701 const uint64_t * b = bp.
data();
702 for (uint64_t k = l; k < r; k += 8)
704 uint16_t x =
excess<>::data.min_open_excess_info[((*(b + (k >> 6))) >> (k & 0x3F)) & 0xFF];
705 int8_t ones = (x >> 12);
708 int8_t min_ex = (x & 0xFF) - 8;
709 if (ex + min_ex <= min_excess)
711 result = k + ((x >> 8) & 0xF);
712 min_excess = ex + min_ex;
715 ex += ((ones << 1) - 8);
717 for (uint64_t k = std::max(r, l); k < end; ++k)
722 if (ex <= min_excess)
733 if (min_excess <= ex)
return result;
ptrdiff_t difference_type
const uint64_t * 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.
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 SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
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]