A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Jacobson (1989) and Geary et al. (CPM 2004).
More...
#include <bp_support_j.hpp>
List of all members.
Public Types |
typedef bit_vector::size_type | size_type |
Public Member Functions |
| bp_support_j (const bit_vector *bp=NULL, uint32_t ignore=0) |
| Constructor.
|
| bp_support_j (const bp_support_j &bp_support) |
| Copy constructor.
|
bp_support_j & | operator= (const bp_support_j &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 (size_type i, size_type j) const |
| The range restricted enclose operation.
|
size_type | rr_enclose_naive (size_type i, size_type j) const |
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_j to a stream.
|
void | load (std::istream &in, const bit_vector *bp) |
| Load the bp_support_j for a bit_vector v.
|
std::string | get_info () const |
Detailed Description
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
class sdsl::bp_support_j< RankSupport, SelectSupport >
A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Jacobson (1989) and Geary et al. (CPM 2004).
An opening parenthesis is represented by a 1 in the bit_vector and a closing parenthesis by a 0. This class could be parametrized by a rank_support and select_support.
Member Function Documentation
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
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().
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
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.
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
Calculates the excess value at index i.
- Parameters:
-
i | The index of which the excess value should be calculated. |
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
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.
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
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.
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
Load the bp_support_j 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. |
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
Return the number of zeros which procede position i in the balanced parentheses sequence.
- Parameters:
-
i | Index of an parenthesis. |
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
Returns the number of opening parentheses up to and including index i.
- Precondition:
- { }
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
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().
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
Returns the index of the i-th opening parenthesis.
- Parameters:
-
i | Number of the parenthesis to select. |
- Precondition:
- { }
- Postcondition:
- { }
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
Serializes the bp_support_j to a stream.
- Parameters:
-
out | The outstream to which the data structure is written. |
- Returns:
- The number of bytes written to out.
template<class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<1>>
The size of the supported balanced parentheses sequence.
- Returns:
- the size of the supported balanced parentheses sequence.
The documentation for this class was generated from the following file: