9 #ifndef INCLUDED_SDSL_BP_SUPPORT_SADA
10 #define INCLUDED_SDSL_BP_SUPPORT_SADA
59 template <uint32_t t_sml_blk = 256,
60 uint32_t t_med_deg = 32,
61 class t_rank = rank_support_v5<>,
62 class t_select = select_support_mcl<>>
74 static_assert(0 < t_sml_blk,
"bp_support_sada: t_sml_blk should be greater than 0!");
95 inline static size_type med_block_idx(
size_type i) {
return i / (t_sml_blk * t_med_deg); }
97 inline static bool is_root(
size_type v) {
return v == 0; }
99 inline static bool is_left_child(
size_type v)
105 inline static bool is_right_child(
size_type v)
121 inline bool node_exists(
size_type v)
const {
return v < (m_med_inner_blocks + m_med_blocks); }
127 inline bool is_leaf(
size_type v)
const {
return v >= m_med_inner_blocks; }
148 std::cout <<
"v = " << v <<
" (" << min_value(v) <<
", " << max_value(v) <<
")";
151 std::cout <<
" range: [" << (v - m_med_inner_blocks) * t_med_deg * t_sml_blk <<
","
152 << (v - m_med_inner_blocks + 1) * t_med_deg * t_sml_blk - 1 <<
"]";
154 std::cout << std::endl;
168 if ((j =
near_fwd_excess(*m_bp, i + 1, rel, t_sml_blk)) > i) {
return j; }
171 if ((j = fwd_excess_in_med_block(sml_block_idx(i) + 1, desired_excess)) !=
size()) {
return j; }
173 if (med_block_idx(i) == m_med_blocks)
175 size_type v = m_med_inner_blocks + med_block_idx(i);
179 if (is_left_child(v))
181 v = right_sibling(v);
182 if (min_value(v) <= desired_excess and desired_excess <= max_value(v))
193 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
195 v = right_sibling(v);
196 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
199 return fwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg, desired_excess);
214 if (i == 0) {
return rel == 0 ? -1 :
size(); }
219 if ((j = bwd_excess_in_med_block(sml_block_idx(i) - 1, desired_excess)) !=
size()) {
return j; }
221 if (med_block_idx(i) == 0)
223 if (desired_excess == 0)
return -1;
226 size_type v = m_med_inner_blocks + med_block_idx(i);
230 if (is_right_child(v))
233 if (min_value(v) <= desired_excess and desired_excess <= max_value(v))
244 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
247 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
250 return bwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg + (t_med_deg - 1), desired_excess);
252 else if (desired_excess == 0)
265 size_type first_sml_block_in_med_block = (med_block_idx(sml_block_idx * t_sml_blk)) * t_med_deg;
267 while ((sml_block_idx + 1) and sml_block_idx >= first_sml_block_in_med_block)
271 difference_type max_ex = ex + (m_sml_block_min_max[2 * sml_block_idx + 1] - 1);
273 if (min_ex <= desired_excess and desired_excess <= max_ex)
276 (sml_block_idx + 1) * t_sml_blk - 1,
277 desired_excess -
excess((sml_block_idx + 1) * t_sml_blk),
283 if (sml_block_idx == 0 and desired_excess == 0)
return -1;
292 size_type first_sml_block_nr_in_next_med_block = (med_block_idx(sml_block_idx * t_sml_blk) + 1) * t_med_deg;
293 if (first_sml_block_nr_in_next_med_block > m_sml_blocks) first_sml_block_nr_in_next_med_block = m_sml_blocks;
295 assert(sml_block_idx > 0);
296 while (sml_block_idx < first_sml_block_nr_in_next_med_block)
300 difference_type max_ex = ex + m_sml_block_min_max[2 * sml_block_idx + 1] - 1;
301 if (min_ex <= desired_excess and desired_excess <= max_ex)
324 , m_bp_rank(v.m_bp_rank)
325 , m_bp_select(v.m_bp_select)
326 , m_sml_block_min_max(v.m_sml_block_min_max)
327 , m_med_block_min_max(v.m_med_block_min_max)
329 , m_sml_blocks(v.m_sml_blocks)
330 , m_med_blocks(v.m_med_blocks)
331 , m_med_inner_blocks(v.m_med_inner_blocks)
333 m_bp_rank.set_vector(m_bp);
334 m_bp_select.set_vector(m_bp);
343 if (
this != &bp_support)
345 m_bp = std::move(bp_support.m_bp);
346 m_bp_rank = std::move(bp_support.m_bp_rank);
347 m_bp_rank.set_vector(m_bp);
348 m_bp_select = std::move(bp_support.m_bp_select);
349 m_bp_select.set_vector(m_bp);
351 m_sml_block_min_max = std::move(bp_support.m_sml_block_min_max);
352 m_med_block_min_max = std::move(bp_support.m_med_block_min_max);
354 m_size = std::move(bp_support.m_size);
355 m_sml_blocks = std::move(bp_support.m_sml_blocks);
356 m_med_blocks = std::move(bp_support.m_med_blocks);
357 m_med_inner_blocks = std::move(bp_support.m_med_inner_blocks);
368 *
this = std::move(tmp);
376 , m_size(bp == nullptr ? 0 : bp->
size())
377 , m_sml_blocks((m_size + t_sml_blk - 1) / t_sml_blk)
378 , m_med_blocks((m_size + t_sml_blk * t_med_deg - 1) / (t_sml_blk * t_med_deg))
379 , m_med_inner_blocks(0)
381 if (bp ==
nullptr or bp->
size() == 0)
return;
383 util::init_support(m_bp_rank, bp);
384 util::init_support(m_bp_select, bp);
386 m_med_inner_blocks = 1;
388 while (m_med_inner_blocks < m_med_blocks)
390 m_med_inner_blocks <<= 1;
391 assert(m_med_inner_blocks != 0);
393 --m_med_inner_blocks;
394 assert((m_med_inner_blocks == 0) or (m_med_inner_blocks % 2 == 1));
397 m_med_block_min_max =
int_vector<>(2 * (m_med_blocks + m_med_inner_blocks), 0,
bits::hi(2 * m_size + 2) + 1);
400 difference_type min_ex = 1, max_ex = -1, curr_rel_ex = 0, curr_abs_ex = 0;
407 if (curr_rel_ex > max_ex) max_ex = curr_rel_ex;
408 if (curr_rel_ex < min_ex) min_ex = curr_rel_ex;
409 if ((i + 1) % t_sml_blk == 0 or i + 1 == m_size)
412 m_sml_block_min_max[2 * sidx] = -(min_ex - 1);
413 m_sml_block_min_max[2 * sidx + 1] = max_ex + 1;
415 size_type v = m_med_inner_blocks + sidx / t_med_deg;
419 assert(curr_abs_ex + min_ex <= min_value(v));
420 m_med_block_min_max[2 * v] = -(curr_abs_ex + min_ex) + m_size;
424 m_med_block_min_max[2 * v + 1] = curr_abs_ex + max_ex + m_size;
426 curr_abs_ex += curr_rel_ex;
433 for (
size_type v = m_med_block_min_max.
size() / 2 - 1; !is_root(v); --v)
436 if (min_value(v) < min_value(p))
437 m_med_block_min_max[2 * p] = m_med_block_min_max[2 * v];
438 if (max_value(v) > max_value(p))
439 m_med_block_min_max[2 * p + 1] = m_med_block_min_max[2 * v + 1];
446 m_bp_rank.set_vector(bp);
447 m_bp_select.set_vector(bp);
469 if (select_cache.
exists(i, a)) {
return a; }
473 select_cache.
write(i, a);
477 return m_bp_select(i);
495 if (find_close_cache.
exists(i, a)) {
return a; }
498 a = fwd_excess(i, -1);
499 find_close_cache.
write(i, a);
503 return fwd_excess(i, -1);
521 if (find_open_cache.
exists(i, a)) {
return a; }
525 if (bwd_ex ==
size())
529 find_open_cache.
write(i, a);
534 if (bwd_ex ==
size())
554 if (bwd_ex ==
size())
571 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
573 if (mip1 >= j)
return size();
587 assert(r < m_bp->
size());
588 if (l >= r)
return size();
590 assert(res >= l and res <= r - 1);
591 if ((*m_bp)[res] == 1)
601 assert((*m_bp)[res] == 1);
603 if (ec < l or ec ==
size())
629 assert(l_sblock <= r_sblock + 1);
634 if (sml_min_value(0) <= min_ex)
637 min_ex = sml_min_value(0);
641 for (
size_type i = l_sblock; i <= r_sblock; ++i)
643 if ((e = (
excess(i * t_sml_blk - 1) + sml_min_value(i))) <= min_ex)
649 return pos_min_block;
664 return near_rmq(*m_bp, l, r, min_rel_ex);
676 enum min_pos_type pos_type = POS;
677 min_pos =
near_rmq(*m_bp, l, (sbl + 1) * t_sml_blk - 1, min_rel_ex);
678 assert(min_pos >= l);
679 min_ex =
excess(l) + min_rel_ex;
686 std::min((mbl + 1) * t_med_deg - 1, sbr - 1),
690 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
692 assert(min_pos < m_sml_blocks);
693 pos_type = SMALL_BLOCK_POS;
697 for (
size_type v=mbl+1+m_med_inner_blocks; v < mbr + m_med_inner_blocks; ++v) {
699 if (min_value(v) <= min_ex) {
700 min_ex = min_value(v);
702 assert(min_pos-m_med_inner_blocks >= 0 and min_pos < m_med_blocks-m_med_inner_blocks);
703 pos_type = MEDIUM_BLOCK_POS;
710 size_type v = mbl + 1 + m_med_inner_blocks;
713 while (rcb < mbr - 1)
715 if (min_value(v) <= min_ex)
717 min_ex = min_value(v);
719 pos_type = MEDIUM_BLOCK_POS;
721 if (is_right_child(v))
725 v = right_sibling(parent(v));
734 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
736 min_ex = min_value(v);
738 pos_type = MEDIUM_BLOCK_POS;
740 assert(node_exists(v));
741 assert(rcb >= mbr - 1);
743 while (rcb != mbr - 1)
749 rcb = rcb - (1ULL << h);
755 rcb = rcb + (1ULL << h);
756 v = right_sibling(right_child(v));
758 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
760 min_ex = min_value(v);
762 pos_type = MEDIUM_BLOCK_POS;
765 if (pos_type == MEDIUM_BLOCK_POS)
767 while (!is_leaf(min_pos))
769 min_pos = right_child(min_pos);
770 if (!node_exists(min_pos) or min_value(min_pos) > min_ex) min_pos = left_sibling(min_pos);
777 temp =
median_block_rmq(std::max(mbr * t_med_deg, sbl + 1), sbr - 1, min_ex);
780 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
782 pos_type = SMALL_BLOCK_POS;
785 temp =
near_rmq(*m_bp, sbr * t_sml_blk, r, min_rel_ex);
786 if ((
excess(sbr * t_sml_blk) + min_rel_ex) <= min_ex)
788 assert(temp >= l and temp <= r);
792 if (pos_type == MEDIUM_BLOCK_POS)
794 min_pos = min_pos - m_med_inner_blocks;
795 temp =
median_block_rmq(min_pos * t_med_deg, (min_pos + 1) * t_med_deg - 1, min_ex);
797 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
799 pos_type = SMALL_BLOCK_POS;
801 if (pos_type == SMALL_BLOCK_POS)
803 min_pos =
near_rmq(*m_bp, min_pos * t_sml_blk, (min_pos + 1) * t_sml_blk - 1, min_rel_ex);
804 assert(min_pos >= l and min_pos <= r);
820 assert(j > i and j < m_size);
821 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
823 assert(mi > i and mi < j);
826 if (k == m_size or k < i)
832 }
while (k != m_size and k > mi);
845 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
863 assert(m_bp_select(ones) < i);
864 return i - m_bp_select(ones) - 1;
880 size_type bwd_ex = bwd_excess(i, -d - 1);
881 if (bwd_ex ==
size())
901 written_bytes +=
write_member(m_size, out, child,
"size");
902 written_bytes +=
write_member(m_sml_blocks, out, child,
"sml_block_cnt");
903 written_bytes +=
write_member(m_med_blocks, out, child,
"med_block_cnt");
904 written_bytes +=
write_member(m_med_inner_blocks, out, child,
"med_inner_blocks");
906 written_bytes += m_bp_rank.serialize(out, child,
"bp_rank");
907 written_bytes += m_bp_select.serialize(out, child,
"bp_select");
909 written_bytes += m_sml_block_min_max.
serialize(out, child,
"sml_blocks");
910 written_bytes += m_med_block_min_max.
serialize(out, child,
"med_blocks");
913 return written_bytes;
925 assert(m_size == bp->
size());
930 m_bp_rank.load(in, m_bp);
931 m_bp_select.load(in, m_bp);
933 m_sml_block_min_max.
load(in);
934 m_med_block_min_max.
load(in);
937 template <
typename archive_t>
950 template <
typename archive_t>
966 return (m_bp_rank == other.m_bp_rank) && (m_bp_select == other.m_bp_select) &&
967 (m_sml_block_min_max == other.m_sml_block_min_max) &&
968 (m_med_block_min_max == other.m_med_block_min_max) && (m_size == other.m_size) &&
969 (m_sml_blocks == other.m_sml_blocks) && (m_med_blocks == other.m_med_blocks) &&
970 (m_med_inner_blocks == other.m_med_inner_blocks);
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
A class that provides support for bit_vectors that represent a BP sequence.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
size_type enclose(size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair...
size_type median_block_rmq(size_type l_sblock, size_type r_sblock, bit_vector::difference_type &min_ex) const
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which proceed position i in the balanced parentheses sequence.
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_sada for a bit_vector v.
size_type level_anc(size_type i, size_type d) const
Returns the level ancestor of the node i.
size_type rmq_open(const size_type l, const size_type r) const
Search the interval [l,r-1] for an opening parenthesis, say i, such that find_close(i) >= r.
size_type rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
const select_type & bp_select
SS for the underlying BP sequence.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
bool operator!=(bp_support_sada const &other) const noexcept
Inequality operator.
bp_support_sada(const bit_vector *bp)
Constructor.
bp_support_sada(const bp_support_sada &v)
Copy constructor.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
void set_vector(const bit_vector *bp)
bp_support_sada(bp_support_sada &&bp_support)
Move constructor.
bool operator==(bp_support_sada const &other) const noexcept
Equality operator.
bit_vector::size_type size_type
bp_support_sada & operator=(const bp_support_sada &v)
Assignment operator.
size_type size() const
The size of the supported balanced parentheses sequence.
bp_support_sada & operator=(bp_support_sada &&bp_support)
Assignment operator.
bit_vector::difference_type difference_type
int_vector sml_block_array_type
const rank_type & bp_rank
RS for the underlying BP sequence.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type rmq(size_type l, size_type r) const
The range minimum query (rmq) returns the index of the parenthesis with minimal excess in the range .
int_vector med_block_array_type
difference_type excess(size_type i) const
Calculates the excess value at index i.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_sada to a stream.
const med_block_array_type & med_block_min_max
Array containing the min max tree of the medium blocks.
const sml_block_array_type & sml_block_min_max
Small blocks array.
size_type rr_enclose(const size_type i, const size_type j) const
The range restricted enclose operation for parentheses pairs and .
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
int_vector_size_type size_type
ptrdiff_t difference_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
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].
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
uint64_t near_fwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
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.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
void write(size_type i, size_type x)
bool exists(size_type i, size_type &x)