8#ifndef INCLUDED_SDSL_BP_SUPPORT_ALGORITHM
9#define INCLUDED_SDSL_BP_SUPPORT_ALGORITHM
26template <
typename T =
void>
82 for (int32_t x = -8; x < 8; ++x)
84 for (uint16_t w = 0; w < 256; ++w)
86 uint16_t i = (x + 8) << 8 | w;
92 excess += 1 - 2 * ((w & (1 << p)) == 0);
107 excess += 1 - 2 * ((w & (1 << p)) > 0);
120 for (uint16_t w = 0; w < 256; ++w)
123 int8_t rev_excess = 0;
124 int32_t min_excess_of_open = 17;
125 int32_t min_excess_of_open_pos = 0;
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)
134 ones += (w & (1 << p)) != 0;
135 excess += 1 - 2 * ((w & (1 << p)) == 0);
143 packed_mins[-
excess - 1] = p;
145 if (w & (1 << p) and
excess + 8 <= min_excess_of_open)
147 min_excess_of_open =
excess + 8;
148 min_excess_of_open_pos = p;
150 rev_excess += 1 - 2 * ((w & (1 << (7 - p))) > 0);
151 if (rev_excess < 0 and packed_maxs[-rev_excess - 1] == 9)
153 packed_maxs[-rev_excess - 1] = 7 - p;
157 packed_mins.
width(32);
159 packed_maxs.
width(32);
184 std::stack<uint64_t> opening_parenthesis;
187 for (uint64_t block_nr = 0; block_nr < blocks; ++block_nr)
189 std::map<uint64_t, uint64_t> block_and_position;
190 std::map<uint64_t, uint64_t> matching_position;
195 opening_parenthesis.push(j);
199 uint64_t position = opening_parenthesis.top();
201 opening_parenthesis.pop();
202 block_and_position[blockpos] = position;
203 matching_position[blockpos] = j;
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;
213 pioneer_bitmap[it->second] = 1;
214 pioneer_bitmap[mit->second] = 1;
218 assert(opening_parenthesis.empty());
219 return pioneer_bitmap;
238 uint64_t cur_pioneer_block = 0, last_start = 0, last_j = 0, cur_block = 0, first_index_in_block = 0;
240 for (uint64_t j = 0, new_block =
block_size; j < bp.
size(); ++j, --new_block)
246 first_index_in_block = j;
253 new_block > 1 and !bp[j + 1])
259 opening_parenthesis.
push(j);
263 assert(!opening_parenthesis.
empty());
264 uint64_t start = opening_parenthesis.
top();
265 opening_parenthesis.
pop();
266 if (start < first_index_in_block)
268 if ((start /
block_size) == cur_pioneer_block)
270 pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0;
272 pioneer_bitmap[start] = pioneer_bitmap[j] = 1;
280 assert(opening_parenthesis.
empty());
281 return pioneer_bitmap;
293template <
class int_vector>
297 std::stack<uint64_t> opening_parenthesis;
298 for (uint64_t i = 0; i < bp.
size(); ++i)
302 opening_parenthesis.push(i);
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);
316 assert(opening_parenthesis.empty());
328template <
class int_vector>
332 std::stack<uint64_t> opening_parenthesis;
333 for (uint64_t i = 0; i < bp.
size(); ++i)
337 if (!opening_parenthesis.empty())
339 uint64_t position = opening_parenthesis.top();
340 enclose[i] = position;
341 assert(enclose[i] == position);
344 enclose[i] = bp.
size();
345 opening_parenthesis.push(i);
349 uint64_t position = opening_parenthesis.top();
350 enclose[i] = position;
351 opening_parenthesis.pop();
355 assert(opening_parenthesis.empty());
361 difference_type excess_v = 1;
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)
379 uint64_t
const * b = bp.
data();
380 for (uint64_t j = l; j < r; j += 8)
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;
392 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
394 for (uint64_t j = std::max(l, r); j < end; ++j)
413 difference_type excess_v = 0;
414 difference_type succ_excess = -closings;
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)
426 if (excess_v == succ_excess)
432 uint64_t
const * b = bp.
data();
433 for (uint64_t j = l; j < r; j += 8)
435 if (excess_v - succ_excess <= 8)
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;
444 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
446 for (uint64_t j = std::max(l, r); j < end; ++j)
453 if (excess_v == succ_excess)
466 difference_type excess_v = rel;
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)
473 excess_v += 1 - 2 * bp[j];
480 uint64_t
const * b = bp.
data();
481 for (uint64_t j = l; j < r; j += 8)
483 if (excess_v >= 0 and excess_v <= 16)
485 uint32_t x =
excess<>::data.near_fwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
491 excess_v -=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
494 for (uint64_t j = std::max(l, r); j < end; ++j)
496 excess_v += 1 - 2 * bp[j];
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;
519 for (uint64_t j = l + 1; j < std::min(l8, r + 1); ++j)
526 if (excess_v <= min_rel_ex)
528 min_rel_ex = excess_v;
534 uint64_t
const * b = bp.
data();
535 for (uint64_t j = l8; j < r8; j += 8)
537 int8_t x =
excess<>::data.min[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
538 if ((excess_v + x) <= min_rel_ex)
540 min_rel_ex = excess_v + x;
541 min_pos = j +
excess<>::data.min_pos_max[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
543 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
545 for (uint64_t j = std::max(l8, r8); j < r + 1; ++j)
552 if (excess_v <= min_rel_ex)
554 min_rel_ex = excess_v;
570 difference_type excess_v = rel;
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 >= std::max(r, begin); --j)
585 uint64_t
const * b = bp.
data();
586 for (difference_type j = r - 8; j >= l; j -= 8)
588 if (excess_v >= 0 and excess_v <= 16)
590 uint32_t x =
excess<>::data.near_bwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
596 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
599 for (difference_type j = std::min(l, r); j > begin; --j)
608 if (0 == begin and -1 == rel)
618 difference_type excess_v = -1;
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)
634 uint64_t
const * b = bp.
data();
635 for (difference_type j = r - 8; j >= l; j -= 8)
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;
647 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
649 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
667 difference_type excess_v = 0;
668 difference_type succ_excess = openings;
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)
677 if (++excess_v == succ_excess)
685 uint64_t
const * b = bp.
data();
686 for (difference_type j = r - 8; j >= l; j -= 8)
688 if (succ_excess - excess_v <= 8)
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;
698 excess_v +=
excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
700 for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
704 if (++excess_v == succ_excess)
726 uint64_t opening_parentheses = 1;
727 for (uint64_t j = i; j +
block_size - 1 > i and j > 0; --j)
731 ++opening_parentheses;
732 if (opening_parentheses == 2)
738 --opening_parentheses;
746 difference_type min_excess = end - begin + 1, ex = 0;
747 uint64_t result = end;
749 const uint64_t l = ((begin + 7) / 8) * 8;
750 const uint64_t r = (end / 8) * 8;
752 for (uint64_t k = begin; k < std::min(end, l); ++k)
757 if (ex <= min_excess)
768 uint64_t
const * b = bp.
data();
769 for (uint64_t k = l; k < r; k += 8)
771 uint16_t x =
excess<>::data.min_open_excess_info[((*(b + (k >> 6))) >> (k & 0x3F)) & 0xFF];
772 int8_t ones = (x >> 12);
775 int8_t min_ex = (x & 0xFF) - 8;
776 if (ex + min_ex <= min_excess)
778 result = k + ((x >> 8) & 0xF);
779 min_excess = ex + min_ex;
782 ex += ((ones << 1) - 8);
784 for (uint64_t k = std::max(r, l); k < end; ++k)
789 if (ex <= min_excess)
800 if (min_excess <= ex)
bits.hpp contains the sdsl::bits class.
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
ptrdiff_t difference_type
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.
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]