8#ifndef INCLUDED_SDSL_BP_SUPPORT_GG
9#define INCLUDED_SDSL_BP_SUPPORT_GG
60template <
class t_nnd = nearest_neighbour_dictionary<30>,
61 class t_rank = rank_support_v5<>,
62 class t_select = select_support_mcl<>,
66 static_assert(t_bs > 2,
"bp_support_gg: block size must be greater than 2.");
83 std::unique_ptr<bp_support_type> m_pioneer_bp_support =
nullptr;
97 m_size(bp == nullptr ? 0 : bp->
size()),
98 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);
115 m_pioneer_bp.
resize(m_nnd.ones());
116 if (m_nnd.ones() > 0 and m_nnd.ones() == m_bp->
size())
118 throw std::logic_error(util::demangle(
typeid(
this).name())
119 +
": recursion in the construction does not terminate!");
122 for (
size_type i = 1; i <= m_nnd.ones(); ++i)
124 m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
127 if (m_bp->
size() > 0)
129 m_pioneer_bp_support = std::unique_ptr<bp_support_type>(
new bp_support_type(&m_pioneer_bp));
135 m_rank_bp(v.m_rank_bp),
136 m_select_bp(v.m_select_bp),
138 m_pioneer_bp(v.m_pioneer_bp),
143 m_rank_bp.set_vector(m_bp);
144 m_select_bp.set_vector(m_bp);
146 m_pioneer_bp_support.reset(
nullptr);
147 if (v.m_pioneer_bp_support !=
nullptr)
149 m_pioneer_bp_support.reset(
new bp_support_type(*(v.m_pioneer_bp_support)));
150 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
157 *
this = std::move(bp_support);
169 *
this = std::move(tmp);
177 if (
this != &bp_support)
179 m_bp = bp_support.m_bp;
180 bp_support.m_bp =
nullptr;
182 m_rank_bp = std::move(bp_support.m_rank_bp);
183 m_rank_bp.set_vector(m_bp);
184 m_select_bp = std::move(bp_support.m_select_bp);
185 m_select_bp.set_vector(m_bp);
187 m_nnd = std::move(bp_support.m_nnd);
189 m_size = bp_support.m_size;
190 m_blocks = bp_support.m_blocks;
192 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
194 m_pioneer_bp_support.reset(
nullptr);
195 if (bp_support.m_pioneer_bp_support !=
nullptr)
197 std::swap(m_pioneer_bp_support, bp_support.m_pioneer_bp_support);
198 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
207 m_rank_bp.set_vector(bp);
208 m_select_bp.set_vector(bp);
216 return (m_rank_bp(i + 1) << 1) - i - 1;
224 return m_rank_bp(i + 1);
234 return m_select_bp(i);
253 const size_type i_ = m_nnd.rank(i + 1) - 1;
254 assert(m_pioneer_bp[i_] == 1);
255 size_type mi_ = m_pioneer_bp_support->find_close(i_);
256 assert(m_pioneer_bp[mi_] == 0);
257 mi = m_nnd.select(mi_ + 1);
258 assert((*m_bp)[mi] == 0);
259 mi = (mi / t_bs) * t_bs;
286 assert(m_pioneer_bp[i_] == 0);
287 const size_type mi_ = m_pioneer_bp_support->find_open(i_);
288 assert(m_pioneer_bp[mi_] == 1);
289 mi = m_nnd.select(mi_ + 1);
290 assert((*m_bp)[mi] == 1);
291 mi = (mi / t_bs) * t_bs + t_bs - 1;
296 return near_find_opening(*m_bp, mi, epb2 - ei + 1 - 2 * ((*m_bp)[mi + 1]), t_bs);
322 ei_ = m_pioneer_bp_support->enclose(i_);
323 assert(m_pioneer_bp[ei_] == 1);
324 ei = m_nnd.select(ei_ + 1);
325 assert((*m_bp)[ei] == 1);
326 ei = (ei / t_bs) * t_bs + t_bs - 1;
330 return near_find_opening(*m_bp, ei, epb2 - exi + 1 + 2 * ((*m_bp)[ei + 1] == 0), t_bs);
349 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
370 if (l / t_bs == r / t_bs)
384 size_type min_ex_pos_ = m_pioneer_bp_support->rmq_open(l_, r_);
385 if (min_ex_pos_ < r_)
387 k = m_nnd.select(min_ex_pos_ + 1);
397 assert(
excess(k) < min_ex);
404 if (k < (l / t_bs + 1) * t_bs and (ex =
excess(k)) < min_ex)
427 assert(j > i and j < m_size);
428 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
430 assert(mi > i and mi < j);
433 if (k == m_size or k < i)
441 while (k != m_size and k > mi);
460 assert(0 == (*m_bp)[m - 1]);
474 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
493 assert(m_select_bp(ones) < i);
494 return i - m_select_bp(ones) - 1;
519 written_bytes +=
write_member(m_size, out, child,
"size");
520 written_bytes +=
write_member(m_blocks, out, child,
"block_cnt");
522 written_bytes += m_rank_bp.serialize(out, child,
"bp_rank");
523 written_bytes += m_select_bp.serialize(out, child,
"bp_select");
524 written_bytes += m_nnd.serialize(out, child,
"nearest_neighbour_dictionary");
526 written_bytes += m_pioneer_bp.
serialize(out, child,
"pioneer_bp");
527 if (m_bp !=
nullptr and m_bp->
size() > 0)
528 written_bytes += m_pioneer_bp_support->serialize(out, child,
"pioneer_bp_support");
530 return written_bytes;
544 m_rank_bp.load(in, m_bp);
545 m_select_bp.load(in, m_bp);
548 m_pioneer_bp.
load(in);
549 m_pioneer_bp_support.reset(
nullptr);
550 if (m_bp !=
nullptr and m_bp->
size() > 0)
553 m_pioneer_bp_support->load(in, &m_pioneer_bp);
557 template <
typename archive_t>
569 template <
typename archive_t>
579 if (m_pioneer_bp_support !=
nullptr)
581 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
588 return (m_size == other.m_size) && (m_blocks == other.m_blocks) && (m_rank_bp == other.m_rank_bp)
589 && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd) && (m_pioneer_bp == other.m_pioneer_bp)
590 && ((m_pioneer_bp_support == other.m_pioneer_bp_support)
591 || (*m_pioneer_bp_support == *other.m_pioneer_bp_support));
597 return !(*
this == other);
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
cereal.hpp offers cereal support
A class that provides support for bit_vectors that represent a BP sequence.
bp_support_gg & operator=(bp_support_gg const &v)
Assignment operator.
size_type rr_enclose(const size_type i, const size_type j) const
Range restricted enclose operation.
void set_vector(bit_vector const *bp)
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.
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.
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.
rank_type const & bp_rank
bp_support_gg & operator=(bp_support_gg &&bp_support)
Assignment Move operator.
void load(std::istream &in, bit_vector const *bp)
Load the bp_support_gg for a bit_vector v.
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
select_type const & bp_select
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.
bp_support_gg(bp_support_gg const &v)
Copy 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(bit_vector const *bp)
Constructor.
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.
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.
void resize(const size_type size)
Resize the int_vector in terms of elements.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
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_succinct(bit_vector const &bp, uint64_t block_size)
Space-efficient version of calculate_pioneers_bitmap.
uint64_t near_find_closing(bit_vector const &bp, uint64_t i, uint64_t closings, const uint64_t block_size)
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
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)
uint64_t near_find_opening(bit_vector const &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support_v5.hpp contains rank_support_v5.5
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
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.