bp_support_gg ()=default
bp_support_gg (bit_vector const *bp)
Constructor.
bp_support_gg (bp_support_gg const &v)
Copy constructor.
bp_support_gg (bp_support_gg &&bp_support)
Move constructor.
~bp_support_gg ()=default
Destructor.
bp_support_gg & operator= (bp_support_gg const &v)
Assignment operator.
bp_support_gg & operator= (bp_support_gg &&bp_support)
Assignment Move operator.
void set_vector (bit_vector const *bp)
size_type excess (size_type i) const
Calculates the excess value at index i.
size_type rank (size_type i) const
Returns the number of opening parentheses up to and including index i.
size_type select (size_type i) const
Returns the index of the i-th opening parenthesis.
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 (size_type i) const
Calculate the matching opening parenthesis.
size_type enclose (size_type i) const
Calculate enclose.
size_type rr_enclose (const size_type i, const size_type j) const
Range restricted enclose operation.
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 rr_enclose_naive (size_type i, size_type j) const
The range restricted enclose operation.
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 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 procede position i in the balanced parentheses sequence.
size_type size () const
The size of the supported 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.
void load (std::istream &in, bit_vector const *bp)
Load the bp_support_gg for a bit_vector v.
template<typename archive_t>
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
template<typename archive_t>
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
bool operator== (bp_support_gg const &other) const noexcept
Equality operator.
bool operator!= (bp_support_gg const &other) const noexcept
Inequality operator.
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, uint32_t t_bs = 840>
class sdsl::bp_support_gg< t_nnd, t_rank, t_select, t_bs >
A class that provides support for bit_vectors that represent a BP sequence.
This data structure supports the following operations:
find_open
find_close
enclose
double_enclose
rank
select
excess
rr_enclose An opening parenthesis in the balanced parentheses sequence is represented by a 1 in the bit_vector and a closing parenthesis by a 0.
Template Parameters
t_nnd A class which supports rank and select with little space on sparse populated bit_vectors.
t_rank A rank support structure.
t_select A select support structure.
References
Richard F. Geary, Naila Rahman, Rajeev Raman, Venkatesh Raman: A Simple Optimal Representation for Balanced Parentheses. CPM 2004: 159-172
Enno Ohlebusch, Simon Gog: A Compressed Enhanced Suffix Array Supporting Fast String Matching. SPIRE 2009: 51-62
Definition at line 64 of file bp_support_gg.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, uint32_t t_bs = 840>
Search the interval [l,r-1] for an opening parenthesis, say i, such that find_close(i) >= r.
Parameters
l The left end (inclusive) of the interval to search for the result.
r The right end (exclusive) of the interval to search for the result.
Returns the minimal opening parenthesis i with and ; if no such i exists size() is returned.
Time complexity
Definition at line 364 of file bp_support_gg.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, uint32_t t_bs = 840>
Range restricted enclose operation.
Range restricted enclose operation for parentheses pairs and .
Parameters
i First opening parenthesis.
j Second opening parenthesis .
Returns The smallest index, say k, of an opening parenthesis such that find_close(i) < k < j and find_close(j) < find_close(k). If such a k does not exists, restricted_enclose(i,j) returns size() .
Time complexity
Definition at line 346 of file bp_support_gg.hpp .