|
| bp_support_g (const bit_vector *bp=nullptr) |
| Constructor. More...
|
|
| bp_support_g (const bp_support_g &v) |
| Copy constructor. More...
|
|
| bp_support_g (bp_support_g &&bp_support) |
| Move constructor. More...
|
|
bp_support_g & | operator= (const bp_support_g &bp_support) |
| Assignment operator. More...
|
|
bp_support_g & | operator= (bp_support_g &&bp_support) |
| Assignment operator. More...
|
|
void | set_vector (const bit_vector *bp) |
|
size_type | excess (size_type i) const |
| Calculates the excess value at index i. More...
|
|
size_type | rank (size_type i) const |
| Returns the number of opening parentheses up to and including index i. More...
|
|
size_type | select (size_type i) const |
| Returns the index of the i-th opening parenthesis. More...
|
|
size_type | find_close (size_type i) const |
| Calculate the index of the matching closing parenthesis to the parenthesis at index i. More...
|
|
size_type | find_open (size_type i) const |
| Calculate the matching opening parenthesis to the closing parenthesis at position i. More...
|
|
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. More...
|
|
size_type | rr_enclose (const size_type i, const size_type j) const |
| The range restricted enclose operation. More...
|
|
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. More...
|
|
size_type | rr_enclose_naive (size_type i, size_type j) const |
| The range restricted enclose operation. More...
|
|
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 . More...
|
|
size_type | double_enclose (size_type i, size_type j) const |
| The double enclose operation. More...
|
|
size_type | preceding_closing_parentheses (size_type i) const |
| Return the number of zeros which procede position i in the balanced parentheses sequence. More...
|
|
size_type | size () const |
| The size of the supported balanced parentheses sequence. More...
|
|
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const |
| Serializes the bp_support_g to a stream. More...
|
|
void | load (std::istream &in, const bit_vector *bp) |
| Load the bp_support_g for a bit_vector v. More...
|
|
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. More...
|
|
bool | operator!= (bp_support_g const &other) const noexcept |
| Inequality operator. More...
|
|
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 57 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 581 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 333 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 191 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 211 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 267 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 647 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 595 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
- {
}
Definition at line 196 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 425 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 404 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 533 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
- {
}
- Postcondition
- {
}
Definition at line 203 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 614 of file bp_support_g.hpp.