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 |
typedef NearestNeighbourDictionary | nnd_type |
typedef RankSupport | rank_support_type |
typedef SelectSupport | select_support_type |
typedef bp_support_gg
< nnd_type, RankSupport,
select_support_bs< RankSupport > > | bp_support_type |
Public Member Functions |
| bp_support_gg (const bit_vector *bp, uint32_t used_block_size=840) |
| Constructor.
|
| bp_support_gg (const bp_support_gg &bp_support) |
| Copy constructor.
|
| ~bp_support_gg () |
| Destructor.
|
void | swap (bp_support_gg &bp_support) |
| Swap operator.
|
bp_support_gg & | operator= (const bp_support_gg &bp_support) |
| Assignment operator.
|
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 | 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 for parentheses pairs and .
|
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_gg to a stream.
|
void | load (std::istream &in, const bit_vector *bp) |
| Load the bp_support_gg 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 sdsl::bp_support_gg< NearestNeighbourDictionary, RankSupport, SelectSupport >
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:
- rank
- select
- 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.
template<class NearestNeighbourDictionary = nearest_neighbour_dictionary<30>, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>
size_type sdsl::bp_support_gg< NearestNeighbourDictionary, RankSupport, SelectSupport >::rmq |
( |
size_type |
l, |
|
|
size_type |
r |
|
) |
| const [inline] |
The range minimum query (rmq) returns the index of the parenthesis with minimal excess in the range .
\param l The left border of the interval \form#68 ( \form#69).
\param r The right border of the interval \form#68 ( \form#70).
TODO: bisher liefert rmq nicht immer das am weitesen rechts liegende minimum
template<class NearestNeighbourDictionary = nearest_neighbour_dictionary<30>, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>
size_type sdsl::bp_support_gg< NearestNeighbourDictionary, RankSupport, SelectSupport >::rmq_open |
( |
const size_type |
l, |
|
|
const size_type |
r |
|
) |
| const [inline] |