8#ifndef INCLUDED_SDSL_BP_SUPPORT_G
9#define INCLUDED_SDSL_BP_SUPPORT_G
54template <
class t_nnd = nearest_neighbour_dictionary<30>,
55 class t_rank = rank_support_v5<>,
56 class t_select = select_support_mcl<>,
57 class t_rmq = range_maximum_support_sparse_table<>,
61 static_assert(t_bs > 2,
"bp_support_g: block size must be greater than 2.");
92 return (m_rank_pioneer_bp(i + 1) << 1) - i - 1;
102 m_size(bp == nullptr ? 0 : bp->
size()),
103 m_blocks((m_size + t_bs - 1) / t_bs)
107 util::init_support(m_rank_bp, bp);
108 util::init_support(m_select_bp, bp);
111 m_pioneer_bp.resize(m_nnd.ones());
112 for (
size_type i = 1; i <= m_nnd.ones(); ++i)
113 m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
114 util::init_support(m_rank_pioneer_bp, &m_pioneer_bp);
119 for (
size_type i = 1; i <= m_nnd2.ones(); ++i)
120 pioneer_bp2[i - 1] = m_pioneer_bp[m_nnd2.select(i)];
123 m_range_max_match =
rmq_type(&m_match);
129 m_rank_bp(v.m_rank_bp),
130 m_select_bp(v.m_select_bp),
132 m_pioneer_bp(v.m_pioneer_bp),
133 m_rank_pioneer_bp(v.m_rank_pioneer_bp),
136 m_enclose(v.m_enclose),
137 m_range_max_match(v.m_range_max_match),
141 m_rank_bp.set_vector(m_bp);
142 m_select_bp.set_vector(m_bp);
143 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
144 m_range_max_match.set_vector(&m_match);
150 *
this = std::move(bp_support);
156 if (
this != &bp_support)
159 *
this = std::move(tmp);
167 if (
this != &bp_support)
169 m_bp = std::move(bp_support.m_bp);
170 m_rank_bp = std::move(bp_support.m_rank_bp);
171 m_rank_bp.set_vector(m_bp);
172 m_select_bp = std::move(bp_support.m_select_bp);
173 m_select_bp.set_vector(m_bp);
175 m_nnd = std::move(bp_support.m_nnd);
177 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
178 m_rank_pioneer_bp = std::move(bp_support.m_rank_pioneer_bp);
179 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
180 m_nnd2 = std::move(bp_support.m_nnd2);
181 m_match = std::move(bp_support.m_match);
182 m_enclose = std::move(bp_support.m_enclose);
183 m_range_max_match = std::move(bp_support.m_range_max_match);
184 m_range_max_match.set_vector(&m_match);
186 m_size = std::move(bp_support.m_size);
187 m_blocks = std::move(bp_support.m_blocks);
195 m_rank_bp.set_vector(bp);
196 m_select_bp.set_vector(bp);
204 return (m_rank_bp(i + 1) << 1) - i - 1;
212 return m_rank_bp(i + 1);
222 return m_select_bp(i);
241 const size_type i2 = m_nnd.rank(i + 1) - 1;
242 assert(m_pioneer_bp[i2] == 1);
246 const size_type i3 = m_nnd2.rank(i2 + 1) - 1;
249 mi2 = m_nnd2.select(mi3 + 1);
250 mi2 = (mi2 / t_bs) * t_bs;
253 assert(epb + 1 >= ei);
254 while (epb + 1 != ei)
256 assert(mi2 < m_pioneer_bp.size());
257 if (m_pioneer_bp[++mi2])
263 mi = m_nnd.select(mi2 + 1);
264 assert((*m_bp)[mi] == 0);
265 mi = (mi / t_bs) * t_bs;
268 assert(epb + 1 >= ei);
269 while (epb + 1 != ei)
298 assert(m_pioneer_bp[i2] == 0);
300 assert(m_pioneer_bp[mi2] == 1);
301 mi = m_nnd.select(mi2 + 1);
302 assert((*m_bp)[mi] == 1);
303 mi = (mi / t_bs) * t_bs + t_bs - 1;
307 assert(epb >= ei + 1);
329 mi = m_nnd2.select(mi3 + 1);
330 mi = (mi / t_bs) * t_bs + t_bs - 1;
333 assert(epb2 >= ei + 1);
336 assert(mi < m_pioneer_bp.size());
337 if (m_pioneer_bp[mi--])
368 if (m_pioneer_bp[i2])
375 ei2 = m_nnd2.select(ei3 + 1);
376 assert(m_pioneer_bp[ei2] == 1);
377 ei2 = (ei2 / t_bs) * t_bs + t_bs - 1;
380 const size_type exi2 = excess_pioneer(i2);
381 assert(epb2 + 1 >= exi2);
382 while (epb2 + 2 != exi2)
384 if (m_pioneer_bp[ei2--])
397 assert(m_pioneer_bp[ei2] == 1);
398 ei = m_nnd.select(ei2 + 1);
399 assert((*m_bp)[ei] == 1);
400 ei = (ei / t_bs) * t_bs + t_bs - 1;
403 assert(epb + 1 >= exi);
404 while (epb + 2 != exi)
426 assert(j > i and j < m_size);
452 if (l / t_bs == r / t_bs)
463 (l / t_bs + 1) * t_bs;
473 if (l_ / t_bs == r_ / t_bs)
477 else if (r_ < m_pioneer_bp.size())
479 size_type min_ex_ = excess_pioneer(r_) + 2 * (m_pioneer_bp[r_] == 0);
480 const size_type bl_ = (l_ / t_bs + 1) * t_bs;
481 const size_type br_ = (r_ / t_bs) * t_bs;
489 k = m_range_max_match(l__, r__ - 1);
490 max_match = m_match[k];
491 if (max_match >= r__)
493 k = m_nnd2.select(k + 1);
494 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
501 if (min_ex_pos_ == r_)
505 if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
513 if (k < bl_ and (ex = excess_pioneer(k)) < min_ex_)
520 if (min_ex_pos_ < r_)
522 k = m_nnd.select(min_ex_pos_ + 1);
523 if ((ex =
excess(k)) < min_ex)
534 if (k < r and (ex =
excess(k)) < min_ex)
542 if (k < bl and (ex =
excess(k)) < min_ex)
563 assert(j > i and j < m_size);
565 assert(mi > i and mi < j);
568 if (k == m_size or k < i)
576 while (k != m_size and k > mi);
592 assert(0 == (*m_bp)[m - 1]);
594 if (prev_open == 0 or m_select_bp(prev_open) < l)
614 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
633 assert(m_select_bp(ones) < i);
634 return i - m_select_bp(ones) - 1;
659 written_bytes += m_rank_bp.serialize(out, child,
"bp_rank");
660 written_bytes += m_select_bp.serialize(out, child,
"bp_select");
661 written_bytes += m_nnd.serialize(out, child,
"nearest_neighbor_dictionary");
663 written_bytes += m_pioneer_bp.serialize(out, child,
"pioneer_bp");
664 written_bytes += m_rank_pioneer_bp.serialize(out, child,
"pioneer_bp_rank");
665 written_bytes += m_nnd2.serialize(out, child,
"nearest_neighbor_dictionary2");
666 written_bytes += m_match.serialize(out, child,
"match_answers");
667 written_bytes += m_enclose.serialize(out, child,
"enclose_answers");
668 written_bytes += m_range_max_match.serialize(out, child,
"rmq_answers");
670 written_bytes +=
write_member(m_size, out, child,
"size");
671 written_bytes +=
write_member(m_blocks, out, child,
"block_cnt");
673 return written_bytes;
684 m_rank_bp.
load(in, m_bp);
685 m_select_bp.load(in, m_bp);
688 m_pioneer_bp.load(in);
689 m_rank_pioneer_bp.load(in, &m_pioneer_bp);
693 m_range_max_match.load(in, &m_match);
695 assert(m_size == bp->
size());
699 template <
typename archive_t>
715 template <
typename archive_t>
723 m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
728 m_range_max_match.set_vector(&m_match);
736 return (m_rank_bp == other.m_rank_bp) && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd)
737 && (m_pioneer_bp == other.m_pioneer_bp) && (m_rank_pioneer_bp == other.m_rank_pioneer_bp)
738 && (m_nnd2 == other.m_nnd2) && (m_match == other.m_match) && (m_enclose == other.m_enclose)
739 && (m_range_max_match == other.m_range_max_match) && (m_size == other.m_size)
740 && (m_blocks == other.m_blocks);
746 return !(*
this == other);
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
cereal.hpp offers cereal support
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
bp_support_g(bp_support_g const &v)
Copy constructor.
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 .
rank_type const & bp_rank
void load(std::istream &in, bit_vector const *bp)
Load the bp_support_g for a bit_vector v.
bp_support_g & operator=(bp_support_g const &bp_support)
Assignment operator.
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.
bp_support_g(bit_vector const *bp=nullptr)
Constructor.
select_type const & bp_select
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_g to a stream.
void set_vector(bit_vector const *bp)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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(bp_support_g &&bp_support)
Move constructor.
size_type size() const
The size of the supported balanced parentheses sequence.
bp_support_g & operator=(bp_support_g &&bp_support)
Assignment operator.
bit_vector::size_type size_type
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.
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.
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.
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_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.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
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)
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
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.
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support_v5.hpp contains rank_support_v5.5
rmq_support_sparse_table.hpp contains the class rmq_support_sparse_table.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
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.