|
| bp_support_gg ()=default |
|
| bp_support_gg (const bit_vector *bp) |
| Constructor. More...
|
|
| bp_support_gg (const bp_support_gg &v) |
| Copy constructor. More...
|
|
| bp_support_gg (bp_support_gg &&bp_support) |
| Move constructor. More...
|
|
| ~bp_support_gg ()=default |
| Destructor. More...
|
|
bp_support_gg & | operator= (const bp_support_gg &v) |
| Assignment operator. More...
|
|
bp_support_gg & | operator= (bp_support_gg &&bp_support) |
| Assignment Move 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. More...
|
|
size_type | enclose (size_type i) const |
| Calculate enclose. More...
|
|
size_type | rr_enclose (const size_type i, const size_type j) const |
| 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_gg to a stream. More...
|
|
void | load (std::istream &in, const bit_vector *bp) |
| Load the bp_support_gg 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_gg const &other) const noexcept |
| Equality operator. More...
|
|
bool | operator!= (bp_support_gg 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<>, 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 58 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 342 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 325 of file bp_support_gg.hpp.