9#ifndef INCLUDED_SDSL_BP_SUPPORT_SADA
10#define INCLUDED_SDSL_BP_SUPPORT_SADA
63template <uint32_t t_sml_blk = 256,
64 uint32_t t_med_deg = 32,
78 static_assert(0 < t_sml_blk,
"bp_support_sada: t_sml_blk should be greater than 0!");
104 return i / (t_sml_blk * t_med_deg);
112 static inline bool is_left_child(
size_type v)
118 static inline bool is_right_child(
size_type v)
140 inline bool node_exists(
size_type v)
const
142 return v < (m_med_inner_blocks + m_med_blocks);
157 return v >= m_med_inner_blocks;
167 return m_med_block_min_max[2 * v + 1] - m_size;
182 std::cout <<
"v = " << v <<
" (" << min_value(v) <<
", " << max_value(v) <<
")";
185 std::cout <<
" range: [" << (v - m_med_inner_blocks) * t_med_deg * t_sml_blk <<
","
186 << (v - m_med_inner_blocks + 1) * t_med_deg * t_sml_blk - 1 <<
"]";
188 std::cout << std::endl;
208 if ((j = fwd_excess_in_med_block(sml_block_idx(i) + 1, desired_excess)) !=
size())
213 if (med_block_idx(i) == m_med_blocks)
215 size_type v = m_med_inner_blocks + med_block_idx(i);
219 if (is_left_child(v))
221 v = right_sibling(v);
222 if (min_value(v) <= desired_excess and desired_excess <= max_value(v))
233 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
235 v = right_sibling(v);
236 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
239 return fwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg, desired_excess);
256 return rel == 0 ? -1 :
size();
265 if ((j = bwd_excess_in_med_block(sml_block_idx(i) - 1, desired_excess)) !=
size())
270 if (med_block_idx(i) == 0)
272 if (desired_excess == 0)
276 size_type v = m_med_inner_blocks + med_block_idx(i);
280 if (is_right_child(v))
283 if (min_value(v) <= desired_excess and desired_excess <= max_value(v))
294 if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
297 assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
300 return bwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg + (t_med_deg - 1), desired_excess);
302 else if (desired_excess == 0)
315 size_type first_sml_block_in_med_block = (med_block_idx(sml_block_idx * t_sml_blk)) * t_med_deg;
317 while ((sml_block_idx + 1) and sml_block_idx >= first_sml_block_in_med_block)
321 difference_type max_ex = ex + (m_sml_block_min_max[2 * sml_block_idx + 1] - 1);
323 if (min_ex <= desired_excess and desired_excess <= max_ex)
326 (sml_block_idx + 1) * t_sml_blk - 1,
327 desired_excess -
excess((sml_block_idx + 1) * t_sml_blk),
333 if (sml_block_idx == 0 and desired_excess == 0)
343 size_type first_sml_block_nr_in_next_med_block = (med_block_idx(sml_block_idx * t_sml_blk) + 1) * t_med_deg;
344 if (first_sml_block_nr_in_next_med_block > m_sml_blocks)
345 first_sml_block_nr_in_next_med_block = m_sml_blocks;
347 assert(sml_block_idx > 0);
348 while (sml_block_idx < first_sml_block_nr_in_next_med_block)
352 difference_type max_ex = ex + m_sml_block_min_max[2 * sml_block_idx + 1] - 1;
353 if (min_ex <= desired_excess and desired_excess <= max_ex)
377 m_bp_rank(v.m_bp_rank),
378 m_bp_select(v.m_bp_select),
379 m_sml_block_min_max(v.m_sml_block_min_max),
380 m_med_block_min_max(v.m_med_block_min_max),
382 m_sml_blocks(v.m_sml_blocks),
383 m_med_blocks(v.m_med_blocks),
384 m_med_inner_blocks(v.m_med_inner_blocks)
386 m_bp_rank.set_vector(m_bp);
387 m_bp_select.set_vector(m_bp);
393 *
this = std::move(bp_support);
399 if (
this != &bp_support)
401 m_bp = std::move(bp_support.m_bp);
402 m_bp_rank = std::move(bp_support.m_bp_rank);
403 m_bp_rank.set_vector(m_bp);
404 m_bp_select = std::move(bp_support.m_bp_select);
405 m_bp_select.set_vector(m_bp);
407 m_sml_block_min_max = std::move(bp_support.m_sml_block_min_max);
408 m_med_block_min_max = std::move(bp_support.m_med_block_min_max);
410 m_size = std::move(bp_support.m_size);
411 m_sml_blocks = std::move(bp_support.m_sml_blocks);
412 m_med_blocks = std::move(bp_support.m_med_blocks);
413 m_med_inner_blocks = std::move(bp_support.m_med_inner_blocks);
424 *
this = std::move(tmp);
432 m_size(bp == nullptr ? 0 : bp->
size()),
433 m_sml_blocks((m_size + t_sml_blk - 1) / t_sml_blk),
434 m_med_blocks((m_size + t_sml_blk * t_med_deg - 1) / (t_sml_blk * t_med_deg)),
435 m_med_inner_blocks(0)
437 if (bp ==
nullptr or bp->
size() == 0)
440 util::init_support(m_bp_rank, bp);
441 util::init_support(m_bp_select, bp);
443 m_med_inner_blocks = 1;
445 while (m_med_inner_blocks < m_med_blocks)
447 m_med_inner_blocks <<= 1;
448 assert(m_med_inner_blocks != 0);
450 --m_med_inner_blocks;
451 assert((m_med_inner_blocks == 0) or (m_med_inner_blocks % 2 == 1));
454 m_med_block_min_max =
int_vector<>(2 * (m_med_blocks + m_med_inner_blocks), 0,
bits::hi(2 * m_size + 2) + 1);
457 difference_type min_ex = 1, max_ex = -1, curr_rel_ex = 0, curr_abs_ex = 0;
464 if (curr_rel_ex > max_ex)
465 max_ex = curr_rel_ex;
466 if (curr_rel_ex < min_ex)
467 min_ex = curr_rel_ex;
468 if ((i + 1) % t_sml_blk == 0 or i + 1 == m_size)
471 m_sml_block_min_max[2 * sidx] = -(min_ex - 1);
472 m_sml_block_min_max[2 * sidx + 1] = max_ex + 1;
474 size_type v = m_med_inner_blocks + sidx / t_med_deg;
478 assert(curr_abs_ex + min_ex <= min_value(v));
479 m_med_block_min_max[2 * v] = -(curr_abs_ex + min_ex) + m_size;
483 m_med_block_min_max[2 * v + 1] = curr_abs_ex + max_ex + m_size;
485 curr_abs_ex += curr_rel_ex;
492 for (
size_type v = m_med_block_min_max.size() / 2 - 1; !is_root(v); --v)
495 if (min_value(v) < min_value(p))
496 m_med_block_min_max[2 * p] = m_med_block_min_max[2 * v];
497 if (max_value(v) > max_value(p))
498 m_med_block_min_max[2 * p + 1] = m_med_block_min_max[2 * v + 1];
505 m_bp_rank.set_vector(bp);
506 m_bp_select.set_vector(bp);
514 return (m_bp_rank(i + 1) << 1) - i - 1;
522 return m_bp_rank(i + 1);
534 if (select_cache.
exists(i, a))
541 select_cache.
write(i, a);
545 return m_bp_select(i);
563 if (find_close_cache.
exists(i, a))
569 a = fwd_excess(i, -1);
570 find_close_cache.
write(i, a);
574 return fwd_excess(i, -1);
592 if (find_open_cache.
exists(i, a))
599 if (bwd_ex ==
size())
603 find_open_cache.
write(i, a);
608 if (bwd_ex ==
size())
628 if (bwd_ex ==
size())
645 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
662 assert(r < m_bp->
size());
666 assert(res >= l and res <= r - 1);
667 if ((*m_bp)[res] == 1)
677 assert((*m_bp)[res] == 1);
679 if (ec < l or ec ==
size())
705 assert(l_sblock <= r_sblock + 1);
710 if (sml_min_value(0) <= min_ex)
713 min_ex = sml_min_value(0);
717 for (
size_type i = l_sblock; i <= r_sblock; ++i)
719 if ((e = (
excess(i * t_sml_blk - 1) + sml_min_value(i))) <= min_ex)
725 return pos_min_block;
740 return near_rmq(*m_bp, l, r, min_rel_ex);
752 enum min_pos_type pos_type = POS;
753 min_pos =
near_rmq(*m_bp, l, (sbl + 1) * t_sml_blk - 1, min_rel_ex);
754 assert(min_pos >= l);
755 min_ex =
excess(l) + min_rel_ex;
762 std::min((mbl + 1) * t_med_deg - 1, sbr - 1),
766 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
768 assert(min_pos < m_sml_blocks);
769 pos_type = SMALL_BLOCK_POS;
773 for (
size_type v=mbl+1+m_med_inner_blocks; v < mbr + m_med_inner_blocks; ++v) {
775 if (min_value(v) <= min_ex) {
776 min_ex = min_value(v);
778 assert(min_pos-m_med_inner_blocks >= 0 and min_pos < m_med_blocks-m_med_inner_blocks);
779 pos_type = MEDIUM_BLOCK_POS;
786 size_type v = mbl + 1 + m_med_inner_blocks;
789 while (rcb < mbr - 1)
791 if (min_value(v) <= min_ex)
793 min_ex = min_value(v);
795 pos_type = MEDIUM_BLOCK_POS;
797 if (is_right_child(v))
801 v = right_sibling(parent(v));
810 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
812 min_ex = min_value(v);
814 pos_type = MEDIUM_BLOCK_POS;
816 assert(node_exists(v));
817 assert(rcb >= mbr - 1);
819 while (rcb != mbr - 1)
825 rcb = rcb - (1ULL << h);
831 rcb = rcb + (1ULL << h);
832 v = right_sibling(right_child(v));
834 if (rcb <= mbr - 1 and min_value(v) <= min_ex)
836 min_ex = min_value(v);
838 pos_type = MEDIUM_BLOCK_POS;
841 if (pos_type == MEDIUM_BLOCK_POS)
843 while (!is_leaf(min_pos))
845 min_pos = right_child(min_pos);
846 if (!node_exists(min_pos) or min_value(min_pos) > min_ex)
847 min_pos = left_sibling(min_pos);
854 temp =
median_block_rmq(std::max(mbr * t_med_deg, sbl + 1), sbr - 1, min_ex);
857 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
859 pos_type = SMALL_BLOCK_POS;
862 temp =
near_rmq(*m_bp, sbr * t_sml_blk, r, min_rel_ex);
863 if ((
excess(sbr * t_sml_blk) + min_rel_ex) <= min_ex)
865 assert(temp >= l and temp <= r);
869 if (pos_type == MEDIUM_BLOCK_POS)
871 min_pos = min_pos - m_med_inner_blocks;
872 temp =
median_block_rmq(min_pos * t_med_deg, (min_pos + 1) * t_med_deg - 1, min_ex);
874 assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
876 pos_type = SMALL_BLOCK_POS;
878 if (pos_type == SMALL_BLOCK_POS)
880 min_pos =
near_rmq(*m_bp, min_pos * t_sml_blk, (min_pos + 1) * t_sml_blk - 1, min_rel_ex);
881 assert(min_pos >= l and min_pos <= r);
897 assert(j > i and j < m_size);
898 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
900 assert(mi > i and mi < j);
903 if (k == m_size or k < i)
911 while (k != m_size and k > mi);
924 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
943 assert(m_bp_select(ones) < i);
944 return i - m_bp_select(ones) - 1;
960 size_type bwd_ex = bwd_excess(i, -d - 1);
961 if (bwd_ex ==
size())
984 written_bytes +=
write_member(m_size, out, child,
"size");
985 written_bytes +=
write_member(m_sml_blocks, out, child,
"sml_block_cnt");
986 written_bytes +=
write_member(m_med_blocks, out, child,
"med_block_cnt");
987 written_bytes +=
write_member(m_med_inner_blocks, out, child,
"med_inner_blocks");
989 written_bytes += m_bp_rank.serialize(out, child,
"bp_rank");
990 written_bytes += m_bp_select.serialize(out, child,
"bp_select");
992 written_bytes += m_sml_block_min_max.serialize(out, child,
"sml_blocks");
993 written_bytes += m_med_block_min_max.serialize(out, child,
"med_blocks");
996 return written_bytes;
1008 assert(m_size == bp->
size());
1013 m_bp_rank.load(in, m_bp);
1014 m_bp_select.load(in, m_bp);
1016 m_sml_block_min_max.load(in);
1017 m_med_block_min_max.load(in);
1020 template <
typename archive_t>
1033 template <
typename archive_t>
1049 return (m_bp_rank == other.m_bp_rank) && (m_bp_select == other.m_bp_select)
1050 && (m_sml_block_min_max == other.m_sml_block_min_max) && (m_med_block_min_max == other.m_med_block_min_max)
1051 && (m_size == other.m_size) && (m_sml_blocks == other.m_sml_blocks) && (m_med_blocks == other.m_med_blocks)
1052 && (m_med_inner_blocks == other.m_med_inner_blocks);
1058 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
cereal.hpp offers cereal support
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.
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.
sml_block_array_type const & sml_block_min_max
Small blocks array.
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.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
bp_support_sada(bp_support_sada &&bp_support)
Move constructor.
bool operator==(bp_support_sada const &other) const noexcept
Equality operator.
select_type const & bp_select
SS for the underlying BP sequence.
bit_vector::size_type size_type
bp_support_sada(bp_support_sada const &v)
Copy constructor.
med_block_array_type const & med_block_min_max
Array containing the min max tree of the medium blocks.
bp_support_sada & operator=(bp_support_sada const &v)
Assignment operator.
bp_support_sada & operator=(bp_support_sada &&bp_support)
Assignment operator.
size_type size() const
The size of the supported balanced parentheses sequence.
bit_vector::difference_type difference_type
int_vector sml_block_array_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
void load(std::istream &in, bit_vector const *bp)
Load the bp_support_sada for a bit_vector v.
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 .
void set_vector(bit_vector const *bp)
bp_support_sada(bit_vector const *bp)
Constructor.
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.
rank_type const & bp_rank
RS for the underlying BP sequence.
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
size_type size() const noexcept
The number of elements in the int_vector.
A class supporting rank queries in constant time.
A class supporting constant time select queries.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
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_bwd_excess(bit_vector const &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
Near backward excess.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
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].
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
rank_support_v5.hpp contains rank_support_v5.5
rank_support_v.hpp contains rank_support_v.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
static 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)
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.