A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Geary et al. (CPM 2004) and extended by Ohlebusch and Gog (SPIRE 2009).
More...
Public Types |
typedef bit_vector::size_type | size_type |
Public Member Functions |
| bp_support_g (const bit_vector *bp=NULL, uint32_t used_block_size=840) |
| Constructor.
|
| bp_support_g (const bp_support_g &bp_support) |
| Copy constructor.
|
bp_support_g & | operator= (const bp_support_g &bp_support) |
| Assignment operator.
|
void | swap (bp_support_g &bp_support) |
void | set_vector (const bit_vector *bp) |
size_type | excess (size_type i) const |
size_type | rank (size_type i) const |
size_type | select (size_type i) const |
size_type | find_close (size_type i) const |
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 |
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 |
size_type | serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const |
| Serializes the bp_support_g to a stream.
|
void | load (std::istream &in, const bit_vector *bp) |
| Load the bp_support_g for a bit_vector v.
|
std::string | get_info () const |
Public Attributes |
const RankSupport & | bp_rank |
const SelectSupport & | bp_select |
template<class NearestNeighbourDictionary = nearest_neighbour_dictionary<30>, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>, class RangeMaxSupport = range_maximum_support_sparse_table<int_vector<> >::type>
class sdsl::bp_support_g< NearestNeighbourDictionary, RankSupport, SelectSupport, RangeMaxSupport >
A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Geary et al. (CPM 2004) and extended by Ohlebusch and Gog (SPIRE 2009).
This data structure supports the following methods on a bit_vector b that represents a balanced parentheses sequence:
- excess
- find_open
- find_close
- enclose
- 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.
This class could be parametrized by four parameters:
- NearestNeighbourDictionary is a class which supports rank and select with little space on sparse populated bit_vectors.
- RankSupport is a class which support the rank operation on bit_vectors.
- SelectSupport is a class which support the select operation on bit_vectors.
- RangeMaxType is a class which supports range maximum queries on a int_vector<>.
template<class NearestNeighbourDictionary = nearest_neighbour_dictionary<30>, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>, class RangeMaxSupport = range_maximum_support_sparse_table<int_vector<> >::type>
size_type sdsl::bp_support_g< NearestNeighbourDictionary, RankSupport, SelectSupport, RangeMaxSupport >::rmq_open |
( |
const size_type |
l, |
|
|
const size_type |
r |
|
) |
| const [inline] |