SDSL 3.0.3
Succinct Data Structure Library
|
A class that provides support for bit_vectors that represent a BP sequence. More...
#include <bp_support_sada.hpp>
Public Types | |
typedef bit_vector::size_type | size_type |
typedef bit_vector::difference_type | difference_type |
typedef int_vector | sml_block_array_type |
typedef int_vector | med_block_array_type |
typedef t_rank | rank_type |
typedef t_select | select_type |
Public Member Functions | |
bp_support_sada () | |
bp_support_sada (bp_support_sada const &v) | |
Copy constructor. | |
bp_support_sada (bp_support_sada &&bp_support) | |
Move constructor. | |
bp_support_sada & | operator= (bp_support_sada &&bp_support) |
Assignment operator. | |
bp_support_sada & | operator= (bp_support_sada const &v) |
Assignment operator. | |
bp_support_sada (bit_vector const *bp) | |
Constructor. | |
void | set_vector (bit_vector const *bp) |
difference_type | excess (size_type i) const |
Calculates the excess value at index i. | |
size_type | rank (size_type i) const |
Returns the number of opening parentheses up to and including index i. | |
size_type | select (size_type i) const |
Returns the index of the i-th opening parenthesis. | |
size_type | find_close (size_type i) const |
Calculate the index of the matching closing parenthesis to the parenthesis at index i. | |
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 ![]() ![]() | |
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. | |
size_type | median_block_rmq (size_type l_sblock, size_type r_sblock, bit_vector::difference_type &min_ex) const |
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 | rr_enclose_naive (size_type i, size_type j) const |
The range restricted enclose operation. | |
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 proceed position i in the balanced parentheses sequence. | |
size_type | level_anc (size_type i, size_type d) const |
Returns the level ancestor of the node i. | |
size_type | size () const |
The size of the supported balanced parentheses sequence. | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const |
Serializes the bp_support_sada to a stream. | |
void | load (std::istream &in, bit_vector const *bp) |
Load the bp_support_sada for a bit_vector v. | |
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_sada const &other) const noexcept |
Equality operator. | |
bool | operator!= (bp_support_sada const &other) const noexcept |
Inequality operator. | |
Public Attributes | |
rank_type const & | bp_rank = m_bp_rank |
RS for the underlying BP sequence. | |
select_type const & | bp_select = m_bp_select |
SS for the underlying BP sequence. | |
sml_block_array_type const & | sml_block_min_max = m_sml_block_min_max |
Small blocks array. | |
med_block_array_type const & | med_block_min_max = m_med_block_min_max |
Array containing the min max tree of the medium blocks. | |
A class that provides support for bit_vectors that represent a BP sequence.
This data structure supports the following operations:
t_sml_blk | The size of the small blocks. Denoted as s in Sadakane's paper. |
t_med_deg | Number of small blocks that a medium block contains. Denoted as l in Sadakane's paper. |
t_rank | Type of rank support used for the underlying bitvector. |
t_select | Type of select support used for the underlying bitvector. |
Definition at line 67 of file bp_support_sada.hpp.
typedef bit_vector::difference_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::difference_type |
Definition at line 71 of file bp_support_sada.hpp.
typedef int_vector sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::med_block_array_type |
Definition at line 73 of file bp_support_sada.hpp.
typedef t_rank sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::rank_type |
Definition at line 74 of file bp_support_sada.hpp.
typedef t_select sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::select_type |
Definition at line 75 of file bp_support_sada.hpp.
typedef bit_vector::size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::size_type |
Definition at line 70 of file bp_support_sada.hpp.
typedef int_vector sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::sml_block_array_type |
Definition at line 72 of file bp_support_sada.hpp.
|
inline |
Definition at line 371 of file bp_support_sada.hpp.
|
inline |
Copy constructor.
Definition at line 375 of file bp_support_sada.hpp.
|
inline |
Move constructor.
Definition at line 391 of file bp_support_sada.hpp.
|
inlineexplicit |
Constructor.
Definition at line 430 of file bp_support_sada.hpp.
|
inline |
Definition at line 1034 of file bp_support_sada.hpp.
|
inline |
Definition at line 1021 of file bp_support_sada.hpp.
|
inline |
The double enclose operation.
i | Index of an opening parenthesis. |
j | Index of an opening parenthesis ![]() |
Definition at line 921 of file bp_support_sada.hpp.
|
inline |
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair enclosing i.
i | Index of an opening parenthesis. |
Definition at line 620 of file bp_support_sada.hpp.
|
inline |
Calculates the excess value at index i.
i | The index of which the excess value should be calculated. |
Definition at line 512 of file bp_support_sada.hpp.
|
inline |
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
i | Index of an parenthesis. 0 <= i < size(). |
Definition at line 554 of file bp_support_sada.hpp.
|
inline |
Calculate the matching opening parenthesis to the closing parenthesis at position i.
i | Index of a closing parenthesis. |
Definition at line 583 of file bp_support_sada.hpp.
|
inline |
Returns the level ancestor of the node i.
i | The index of a parenthesis (i.e., a node). |
d | The level, i.e., which node to select on the path from the node i up to the root. The level d = 0 will return the node itself, d = 1 will return its parent, and so on. |
Definition at line 957 of file bp_support_sada.hpp.
|
inline |
Load the bp_support_sada for a bit_vector v.
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 1004 of file bp_support_sada.hpp.
|
inline |
Definition at line 703 of file bp_support_sada.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 1056 of file bp_support_sada.hpp.
|
inline |
Assignment operator.
Definition at line 397 of file bp_support_sada.hpp.
|
inline |
Assignment operator.
Definition at line 419 of file bp_support_sada.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 1047 of file bp_support_sada.hpp.
|
inline |
Return the number of zeros which proceed position i in the balanced parentheses sequence.
i | Index of an parenthesis. |
Definition at line 935 of file bp_support_sada.hpp.
|
inline |
Returns the number of opening parentheses up to and including index i.
Definition at line 520 of file bp_support_sada.hpp.
|
inline |
The range minimum query (rmq) returns the index of the parenthesis with minimal excess in the range
l | The left border of the interval ![]() ![]() |
r | The right border of the interval ![]() ![]() |
Definition at line 732 of file bp_support_sada.hpp.
|
inline |
Search the interval [l,r-1] for an opening parenthesis, say i, such that find_close(i) >= r.
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. |
Definition at line 660 of file bp_support_sada.hpp.
|
inline |
The range restricted enclose operation for parentheses pairs
i | First opening parenthesis. |
j | Second opening parenthesis ![]() |
Definition at line 642 of file bp_support_sada.hpp.
|
inline |
The range restricted enclose operation.
i | Index of an opening parenthesis. |
j | Index of an opening parenthesis ![]() |
Definition at line 895 of file bp_support_sada.hpp.
|
inline |
Returns the index of the i-th opening parenthesis.
i | Number of the parenthesis to select. |
Definition at line 530 of file bp_support_sada.hpp.
|
inline |
Serializes the bp_support_sada to a stream.
out | The outstream to which the data structure is written. |
Definition at line 980 of file bp_support_sada.hpp.
|
inline |
Definition at line 502 of file bp_support_sada.hpp.
|
inline |
The size of the supported balanced parentheses sequence.
Definition at line 970 of file bp_support_sada.hpp.
rank_type const& sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::bp_rank = m_bp_rank |
RS for the underlying BP sequence.
Definition at line 364 of file bp_support_sada.hpp.
select_type const& sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::bp_select = m_bp_select |
SS for the underlying BP sequence.
Definition at line 365 of file bp_support_sada.hpp.
med_block_array_type const& sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::med_block_min_max = m_med_block_min_max |
Array containing the min max tree of the medium blocks.
Definition at line 368 of file bp_support_sada.hpp.
sml_block_array_type const& sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::sml_block_min_max = m_sml_block_min_max |
Small blocks array.
Rel. min/max for the small blocks.
Definition at line 366 of file bp_support_sada.hpp.