8 #ifndef INCLUDED_SDSL_BP_SUPPORT_GG
9 #define INCLUDED_SDSL_BP_SUPPORT_GG
54 template <
class t_nnd = nearest_neighbour_dictionary<30>,
55 class t_rank = rank_support_v5<>,
56 class t_select = select_support_mcl<>,
60 static_assert(t_bs > 2,
"bp_support_gg: block size must be greater than 2.");
77 std::unique_ptr<bp_support_type> m_pioneer_bp_support =
nullptr;
91 , m_size(bp == nullptr ? 0 : bp->
size())
92 , m_blocks((m_size + t_bs - 1) / t_bs)
101 util::init_support(m_rank_bp, bp);
102 util::init_support(m_select_bp, bp);
109 m_pioneer_bp.
resize(m_nnd.ones());
110 if (m_nnd.ones() > 0 and m_nnd.ones() == m_bp->
size())
112 throw std::logic_error(util::demangle(
typeid(
this).name()) +
113 ": recursion in the construction does not terminate!");
116 for (
size_type i = 1; i <= m_nnd.ones(); ++i) { m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)]; }
118 if (m_bp->
size() > 0)
120 m_pioneer_bp_support = std::unique_ptr<bp_support_type>(
new bp_support_type(&m_pioneer_bp));
126 : m_rank_bp(v.m_rank_bp)
127 , m_select_bp(v.m_select_bp)
129 , m_pioneer_bp(v.m_pioneer_bp)
131 , m_blocks(v.m_blocks)
134 m_rank_bp.set_vector(m_bp);
135 m_select_bp.set_vector(m_bp);
137 m_pioneer_bp_support.reset(
nullptr);
138 if (v.m_pioneer_bp_support !=
nullptr)
140 m_pioneer_bp_support.reset(
new bp_support_type(*(v.m_pioneer_bp_support)));
141 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
157 *
this = std::move(tmp);
165 if (
this != &bp_support)
167 m_bp = bp_support.m_bp;
168 bp_support.m_bp =
nullptr;
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_size = bp_support.m_size;
178 m_blocks = bp_support.m_blocks;
180 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
182 m_pioneer_bp_support.reset(
nullptr);
183 if (bp_support.m_pioneer_bp_support !=
nullptr)
185 std::swap(m_pioneer_bp_support, bp_support.m_pioneer_bp_support);
186 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
195 m_rank_bp.set_vector(bp);
196 m_select_bp.set_vector(bp);
232 const size_type i_ = m_nnd.rank(i + 1) - 1;
233 assert(m_pioneer_bp[i_] == 1);
234 size_type mi_ = m_pioneer_bp_support->find_close(i_);
235 assert(m_pioneer_bp[mi_] == 0);
236 mi = m_nnd.select(mi_ + 1);
237 assert((*m_bp)[mi] == 0);
238 mi = (mi / t_bs) * t_bs;
265 assert(m_pioneer_bp[i_] == 0);
266 const size_type mi_ = m_pioneer_bp_support->find_open(i_);
267 assert(m_pioneer_bp[mi_] == 1);
268 mi = m_nnd.select(mi_ + 1);
269 assert((*m_bp)[mi] == 1);
270 mi = (mi / t_bs) * t_bs + t_bs - 1;
275 return near_find_opening(*m_bp, mi, epb2 - ei + 1 - 2 * ((*m_bp)[mi + 1]), t_bs);
301 ei_ = m_pioneer_bp_support->enclose(i_);
302 assert(m_pioneer_bp[ei_] == 1);
303 ei = m_nnd.select(ei_ + 1);
304 assert((*m_bp)[ei] == 1);
305 ei = (ei / t_bs) * t_bs + t_bs - 1;
309 return near_find_opening(*m_bp, ei, epb2 - exi + 1 + 2 * ((*m_bp)[ei + 1] == 0), t_bs);
328 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
330 if (mip1 >= j)
return size();
344 if (l >= r)
return size();
347 if (l / t_bs == r / t_bs) { min_ex_pos =
near_rmq_open(*m_bp, l, r); }
358 size_type min_ex_pos_ = m_pioneer_bp_support->rmq_open(l_, r_);
359 if (min_ex_pos_ < r_)
361 k = m_nnd.select(min_ex_pos_ + 1);
371 assert(
excess(k) < min_ex);
378 if (k < (l / t_bs + 1) * t_bs and (ex =
excess(k)) < min_ex)
401 assert(j > i and j < m_size);
402 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
404 assert(mi > i and mi < j);
407 if (k == m_size or k < i)
413 }
while (k != m_size and k > mi);
432 assert(0 == (*m_bp)[m - 1]);
446 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
464 assert(m_select_bp(ones) < i);
465 return i - m_select_bp(ones) - 1;
487 written_bytes +=
write_member(m_size, out, child,
"size");
488 written_bytes +=
write_member(m_blocks, out, child,
"block_cnt");
490 written_bytes += m_rank_bp.serialize(out, child,
"bp_rank");
491 written_bytes += m_select_bp.serialize(out, child,
"bp_select");
492 written_bytes += m_nnd.serialize(out, child,
"nearest_neighbour_dictionary");
494 written_bytes += m_pioneer_bp.
serialize(out, child,
"pioneer_bp");
495 if (m_bp !=
nullptr and m_bp->
size() > 0)
496 written_bytes += m_pioneer_bp_support->serialize(out, child,
"pioneer_bp_support");
498 return written_bytes;
512 m_rank_bp.load(in, m_bp);
513 m_select_bp.load(in, m_bp);
516 m_pioneer_bp.
load(in);
517 m_pioneer_bp_support.reset(
nullptr);
518 if (m_bp !=
nullptr and m_bp->
size() > 0)
521 m_pioneer_bp_support->load(in, &m_pioneer_bp);
525 template <
typename archive_t>
537 template <
typename archive_t>
547 if (m_pioneer_bp_support !=
nullptr) { m_pioneer_bp_support->set_vector(&m_pioneer_bp); }
553 return (m_size == other.m_size) && (m_blocks == other.m_blocks) && (m_rank_bp == other.m_rank_bp) &&
554 (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd) && (m_pioneer_bp == other.m_pioneer_bp) &&
555 ((m_pioneer_bp_support == other.m_pioneer_bp_support) ||
556 (*m_pioneer_bp_support == *other.m_pioneer_bp_support));
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 rr_enclose(const size_type i, const size_type j) const
Range restricted enclose operation.
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which procede position i in the balanced parentheses sequence.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_gg to a stream.
const select_type & bp_select
size_type size() const
The size of the supported balanced parentheses 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.
void set_vector(const bit_vector *bp)
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis.
size_type rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
bp_support_gg< nnd_type, rank_type, select_support_scan<>, t_bs > bp_support_type
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 .
bp_support_gg & operator=(const bp_support_gg &v)
Assignment operator.
const rank_type & bp_rank
size_type excess(size_type i) const
Calculates the excess value at index i.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_gg for a bit_vector v.
bp_support_gg & operator=(bp_support_gg &&bp_support)
Assignment Move operator.
bp_support_gg(const bit_vector *bp)
Constructor.
bool operator==(bp_support_gg const &other) const noexcept
Equality operator.
bit_vector::size_type size_type
bool operator!=(bp_support_gg const &other) const noexcept
Inequality operator.
bp_support_gg(bp_support_gg &&bp_support)
Move constructor.
size_type enclose(size_type i) const
Calculate enclose.
~bp_support_gg()=default
Destructor.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
bp_support_gg(const bp_support_gg &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_find_closing(const bit_vector &bp, uint64_t i, uint64_t closings, const uint64_t block_size)
uint64_t near_rmq_open(const bit_vector &bp, const uint64_t begin, const uint64_t end)
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
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_find_opening(const bit_vector &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
bit_vector calculate_pioneers_bitmap_succinct(const bit_vector &bp, uint64_t block_size)
Space-efficient version of calculate_pioneers_bitmap.
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...
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.