8 #ifndef INCLUDED_SDSL_BP_SUPPORT_G
9 #define INCLUDED_SDSL_BP_SUPPORT_G
52 template <
class t_nnd = nearest_neighbour_dictionary<30>,
53 class t_rank = rank_support_v5<>,
54 class t_select = select_support_mcl<>,
55 class t_rmq = range_maximum_support_sparse_table<>,
59 static_assert(t_bs > 2,
"bp_support_g: block size must be greater than 2.");
88 inline size_type excess_pioneer(
size_type i)
const {
return (m_rank_pioneer_bp(i + 1) << 1) - i - 1; }
97 , m_size(bp == nullptr ? 0 : bp->
size())
98 , m_blocks((m_size + t_bs - 1) / t_bs)
100 if (bp ==
nullptr)
return;
101 util::init_support(m_rank_bp, bp);
102 util::init_support(m_select_bp, bp);
105 m_pioneer_bp.
resize(m_nnd.ones());
106 for (
size_type i = 1; i <= m_nnd.ones(); ++i) m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
107 util::init_support(m_rank_pioneer_bp, &m_pioneer_bp);
112 for (
size_type i = 1; i <= m_nnd2.ones(); ++i) pioneer_bp2[i - 1] = m_pioneer_bp[m_nnd2.select(i)];
115 m_range_max_match =
rmq_type(&m_match);
121 , m_rank_bp(v.m_rank_bp)
122 , m_select_bp(v.m_select_bp)
124 , m_pioneer_bp(v.m_pioneer_bp)
125 , m_rank_pioneer_bp(v.m_rank_pioneer_bp)
128 , m_enclose(v.m_enclose)
129 , m_range_max_match(v.m_range_max_match)
131 , m_blocks(v.m_blocks)
133 m_rank_bp.set_vector(m_bp);
134 m_select_bp.set_vector(m_bp);
135 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
136 m_range_max_match.set_vector(&m_match);
145 if (
this != &bp_support)
148 *
this = std::move(tmp);
156 if (
this != &bp_support)
158 m_bp = std::move(bp_support.m_bp);
159 m_rank_bp = std::move(bp_support.m_rank_bp);
160 m_rank_bp.set_vector(m_bp);
161 m_select_bp = std::move(bp_support.m_select_bp);
162 m_select_bp.set_vector(m_bp);
164 m_nnd = std::move(bp_support.m_nnd);
166 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
167 m_rank_pioneer_bp = std::move(bp_support.m_rank_pioneer_bp);
168 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
169 m_nnd2 = std::move(bp_support.m_nnd2);
170 m_match = std::move(bp_support.m_match);
171 m_enclose = std::move(bp_support.m_enclose);
172 m_range_max_match = std::move(bp_support.m_range_max_match);
173 m_range_max_match.set_vector(&m_match);
175 m_size = std::move(bp_support.m_size);
176 m_blocks = std::move(bp_support.m_blocks);
184 m_rank_bp.set_vector(bp);
185 m_select_bp.set_vector(bp);
221 const size_type i2 = m_nnd.rank(i + 1) - 1;
222 assert(m_pioneer_bp[i2] == 1);
226 const size_type i3 = m_nnd2.rank(i2 + 1) - 1;
229 mi2 = m_nnd2.select(mi3 + 1);
230 mi2 = (mi2 / t_bs) * t_bs;
233 assert(epb + 1 >= ei);
234 while (epb + 1 != ei)
236 assert(mi2 < m_pioneer_bp.
size());
237 if (m_pioneer_bp[++mi2])
243 mi = m_nnd.select(mi2 + 1);
244 assert((*m_bp)[mi] == 0);
245 mi = (mi / t_bs) * t_bs;
248 assert(epb + 1 >= ei);
249 while (epb + 1 != ei)
278 assert(m_pioneer_bp[i2] == 0);
280 assert(m_pioneer_bp[mi2] == 1);
281 mi = m_nnd.select(mi2 + 1);
282 assert((*m_bp)[mi] == 1);
283 mi = (mi / t_bs) * t_bs + t_bs - 1;
287 assert(epb >= ei + 1);
309 mi = m_nnd2.select(mi3 + 1);
310 mi = (mi / t_bs) * t_bs + t_bs - 1;
313 assert(epb2 >= ei + 1);
316 assert(mi < m_pioneer_bp.
size());
317 if (m_pioneer_bp[mi--])
348 if (m_pioneer_bp[i2])
355 ei2 = m_nnd2.select(ei3 + 1);
356 assert(m_pioneer_bp[ei2] == 1);
357 ei2 = (ei2 / t_bs) * t_bs + t_bs - 1;
360 const size_type exi2 = excess_pioneer(i2);
361 assert(epb2 + 1 >= exi2);
362 while (epb2 + 2 != exi2)
364 if (m_pioneer_bp[ei2--])
377 assert(m_pioneer_bp[ei2] == 1);
378 ei = m_nnd.select(ei2 + 1);
379 assert((*m_bp)[ei] == 1);
380 ei = (ei / t_bs) * t_bs + t_bs - 1;
383 assert(epb + 1 >= exi);
384 while (epb + 2 != exi)
406 assert(j > i and j < m_size);
408 if (mip1 >= j)
return size();
427 if (l >= r)
return size();
430 if (l / t_bs == r / t_bs) { min_ex_pos =
near_rmq_open(*m_bp, l, r); }
448 if (l_ / t_bs == r_ / t_bs) { min_ex_pos_ =
near_rmq_open(m_pioneer_bp, l_, r_); }
449 else if (r_ < m_pioneer_bp.
size())
451 size_type min_ex_ = excess_pioneer(r_) + 2 * (m_pioneer_bp[r_] == 0);
452 const size_type bl_ = (l_ / t_bs + 1) * t_bs;
453 const size_type br_ = (r_ / t_bs) * t_bs;
461 k = m_range_max_match(l__, r__ - 1);
462 max_match = m_match[k];
463 if (max_match >= r__)
465 k = m_nnd2.select(k + 1);
466 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
473 if (min_ex_pos_ == r_)
477 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
485 if (k < bl_ and (ex = excess_pioneer(k)) < min_ex_)
492 if (min_ex_pos_ < r_)
494 k = m_nnd.select(min_ex_pos_ + 1);
495 if ((ex =
excess(k)) < min_ex)
506 if (k < r and (ex =
excess(k)) < min_ex)
514 if (k < bl and (ex =
excess(k)) < min_ex)
535 assert(j > i and j < m_size);
537 assert(mi > i and mi < j);
540 if (k == m_size or k < i)
546 }
while (k != m_size and k > mi);
562 assert(0 == (*m_bp)[m - 1]);
564 if (prev_open == 0 or m_select_bp(prev_open) < l)
584 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
602 assert(m_select_bp(ones) < i);
603 return i - m_select_bp(ones) - 1;
625 written_bytes += m_rank_bp.serialize(out, child,
"bp_rank");
626 written_bytes += m_select_bp.serialize(out, child,
"bp_select");
627 written_bytes += m_nnd.serialize(out, child,
"nearest_neighbor_dictionary");
629 written_bytes += m_pioneer_bp.
serialize(out, child,
"pioneer_bp");
630 written_bytes += m_rank_pioneer_bp.serialize(out, child,
"pioneer_bp_rank");
631 written_bytes += m_nnd2.serialize(out, child,
"nearest_neighbor_dictionary2");
632 written_bytes += m_match.
serialize(out, child,
"match_answers");
633 written_bytes += m_enclose.
serialize(out, child,
"enclose_answers");
634 written_bytes += m_range_max_match.serialize(out, child,
"rmq_answers");
636 written_bytes +=
write_member(m_size, out, child,
"size");
637 written_bytes +=
write_member(m_blocks, out, child,
"block_cnt");
639 return written_bytes;
650 m_rank_bp.
load(in, m_bp);
651 m_select_bp.load(in, m_bp);
654 m_pioneer_bp.
load(in);
655 m_rank_pioneer_bp.load(in, &m_pioneer_bp);
659 m_range_max_match.load(in, &m_match);
661 assert(m_size == bp->
size());
665 template <
typename archive_t>
681 template <
typename archive_t>
689 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
694 m_range_max_match.set_vector(&m_match);
702 return (m_rank_bp == other.m_rank_bp) && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd) &&
703 (m_pioneer_bp == other.m_pioneer_bp) && (m_rank_pioneer_bp == other.m_rank_pioneer_bp) &&
704 (m_nnd2 == other.m_nnd2) && (m_match == other.m_match) && (m_enclose == other.m_enclose) &&
705 (m_range_max_match == other.m_range_max_match) && (m_size == other.m_size) &&
706 (m_blocks == other.m_blocks);
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
A class that provides support for bit_vectors that represent a BP sequence.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
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 select(size_type i) const
Returns the index of the i-th opening parenthesis.
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 .
size_type excess(size_type i) const
Calculates the excess value at index i.
size_type rr_enclose(const size_type i, const size_type j) const
The range restricted enclose operation.
void set_vector(const bit_vector *bp)
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
const rank_type & bp_rank
bp_support_g & operator=(bp_support_g &&bp_support)
Assignment operator.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_g to a stream.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
const select_type & bp_select
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which procede position i in the balanced parentheses sequence.
bp_support_g & operator=(const bp_support_g &bp_support)
Assignment operator.
bp_support_g(bp_support_g &&bp_support)
Move constructor.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_g for a bit_vector v.
size_type size() const
The size of the supported balanced parentheses sequence.
bit_vector::size_type size_type
bp_support_g(const bit_vector *bp=nullptr)
Constructor.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
size_type find_open_in_pioneers(size_type i) const
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
bool operator!=(bp_support_g const &other) const noexcept
Inequality operator.
size_type enclose(size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair...
bool operator==(bp_support_g const &other) const noexcept
Equality operator.
size_type rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
bp_support_g(const bp_support_g &v)
Copy constructor.
int_vector_size_type size_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.
void resize(const size_type size)
Resize the int_vector in terms of elements.
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_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.
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)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
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)
void calculate_enclose(const bit_vector &bp, int_vector &enclose)
Calculates enclose answers for a balanced parentheses sequence.
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.
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
rmq_support.hpp contains different range minimum support data structures.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.