bp_support_g (bit_vector const *bp=nullptr)
Constructor.
bp_support_g (bp_support_g const &v)
Copy constructor.
bp_support_g (bp_support_g &&bp_support)
Move constructor.
bp_support_g & operator= (bp_support_g const &bp_support)
Assignment operator.
bp_support_g & operator= (bp_support_g &&bp_support)
Assignment 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 to the closing parenthesis at position i.
size_type find_open_in_pioneers (size_type i) const
size_type enclose (size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair enclosing i.
size_type rr_enclose (const size_type i, const size_type j) const
The 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_g to a stream.
void load (std::istream &in, bit_vector const *bp)
Load the bp_support_g 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_g const &other) const noexcept
Equality operator.
bool operator!= (bp_support_g 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<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
class sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, 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 Type which supports rank and select with little space on sparse populated bit_vectors.
t_rank Type of rank support structure.
t_select Type of select support structure.
t_rmq Type which supports range maximum queries on a int_vector<> .
Reference Richard F. Geary, Naila Rahman, Rajeev Raman, Venkatesh Raman: A Simple Optimal Representation for Balanced Parentheses. CPM 2004: 159-172
Definition at line 59 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
template<typename archive_t>
void sdsl::bp_support_g < t_nnd, t_rank, t_select, t_rmq, t_bs >::CEREAL_LOAD_FUNCTION_NAME
(
archive_t & ar )
inline
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
template<typename archive_t>
void sdsl::bp_support_g < t_nnd, t_rank, t_select, t_rmq, t_bs >::CEREAL_SAVE_FUNCTION_NAME
(
archive_t & ar )
const
inline
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
The double enclose operation.
Parameters
i Index of an opening parenthesis.
j Index of an opening parenthesis .
Returns The maximal opening parenthesis, say k, such that . If such a k does not exists, double_enclose(i,j) returns size() .
Definition at line 611 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair enclosing i.
Parameters
i Index of an opening parenthesis.
Returns The index of the opening parenthesis corresponding to the closest matching parenthesis pair enclosing i, or size() if no such pair exists.
Definition at line 353 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Calculates the excess value at index i.
Parameters
i The index of which the excess value should be calculated.
Definition at line 202 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
Parameters
i Index of an parenthesis. 0 <= i < size() .
Returns * i, if the parenthesis at index i is closing,
the position j of the matching closing parenthesis, if a matching parenthesis exists,
size() if no matching closing parenthesis exists.
Definition at line 231 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Calculate the matching opening parenthesis to the closing parenthesis at position i.
Parameters
i Index of a closing parenthesis.
Returns * i, if the parenthesis at index i is closing,
the position j of the matching opening parenthesis, if a matching parenthesis exists,
size() if no matching closing parenthesis exists.
Definition at line 287 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Load the bp_support_g for a bit_vector v.
Parameters
in The instream from which the data strucutre is read.
bp Bit vector representing a balanced parentheses sequence that is supported by this data structure.
Definition at line 681 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Return the number of zeros which procede position i in the balanced parentheses sequence.
Parameters
i Index of an parenthesis.
Definition at line 625 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Returns the number of opening parentheses up to and including index i.
Precondition { \f$ 0\leq i < size() \f$ }
Definition at line 210 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, 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. The algorithm consists of 4 steps:
scan back from position r to the begin of that block
recursively scan back the pioneers of the blocks which lie in between the blocks of l and r
scan from position l to the end of the block, which contains l
check if there exists a valid solution and return
Time complexity
Definition at line 446 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
The range restricted enclose operation.
Parameters
i Index of an opening parenthesis.
j Index of an opening parenthesis/ .
Returns The smallest index, say k, of an opening parenthesis such that findclose(i) < k < j and findclose(j) < findclose(k). If such a k does not exists, restricted_enclose(i,j) returns size() .
Time complexity
Definition at line 424 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
The range restricted enclose operation.
Parameters
i Index of an opening parenthesis.
j Index of an opening parenthesis/ .
Returns The smallest index, say k, of an opening parenthesis such that findclose(i) < k < j and findclose(j) < findclose(k). If such a k does not exists, restricted_enclose(i,j) returns size() .
Definition at line 561 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
Returns the index of the i-th opening parenthesis.
Parameters
i Number of the parenthesis to select.
Precondition { \f$1\leq i < rank(size())\f$ }
Postcondition { \f$ 0\leq select(i) < size() \f$ }
Definition at line 220 of file bp_support_g.hpp .
template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
The size of the supported balanced parentheses sequence.
Returns the size of the supported balanced parentheses sequence.
Definition at line 645 of file bp_support_g.hpp .