SDSL 3.0.1
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 (const bp_support_sada &v) | |
Copy constructor. More... | |
bp_support_sada (bp_support_sada &&bp_support) | |
Move constructor. More... | |
bp_support_sada & | operator= (bp_support_sada &&bp_support) |
Assignment operator. More... | |
bp_support_sada & | operator= (const bp_support_sada &v) |
Assignment operator. More... | |
bp_support_sada (const bit_vector *bp) | |
Constructor. More... | |
void | set_vector (const bit_vector *bp) |
difference_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 to the closing parenthesis at position i. More... | |
size_type | enclose (size_type i) const |
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair enclosing i. More... | |
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. More... | |
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. 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 proceed position i in the balanced parentheses sequence. More... | |
size_type | level_anc (size_type i, size_type d) const |
Returns the level ancestor of the node i. 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_sada to a stream. More... | |
void | load (std::istream &in, const bit_vector *bp) |
Load the bp_support_sada 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_sada const &other) const noexcept |
Equality operator. More... | |
bool | operator!= (bp_support_sada const &other) const noexcept |
Inequality operator. More... | |
Public Attributes | |
const rank_type & | bp_rank = m_bp_rank |
RS for the underlying BP sequence. More... | |
const select_type & | bp_select = m_bp_select |
SS for the underlying BP sequence. More... | |
const sml_block_array_type & | sml_block_min_max = m_sml_block_min_max |
Small blocks array. More... | |
const med_block_array_type & | med_block_min_max = m_med_block_min_max |
Array containing the min max tree of the medium blocks. More... | |
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 63 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 67 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 69 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 70 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 71 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 66 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 68 of file bp_support_sada.hpp.
|
inline |
Definition at line 319 of file bp_support_sada.hpp.
|
inline |
Copy constructor.
Definition at line 322 of file bp_support_sada.hpp.
|
inline |
Move constructor.
Definition at line 338 of file bp_support_sada.hpp.
|
inlineexplicit |
Constructor.
Definition at line 374 of file bp_support_sada.hpp.
|
inline |
Definition at line 951 of file bp_support_sada.hpp.
|
inline |
Definition at line 938 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 842 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 546 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 453 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 486 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 512 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 877 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 921 of file bp_support_sada.hpp.
|
inline |
Definition at line 627 of file bp_support_sada.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 974 of file bp_support_sada.hpp.
|
inline |
Assignment operator.
Definition at line 341 of file bp_support_sada.hpp.
|
inline |
Assignment operator.
Definition at line 363 of file bp_support_sada.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 964 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 856 of file bp_support_sada.hpp.
|
inline |
Returns the number of opening parentheses up to and including index i.
Definition at line 458 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 656 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 585 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 568 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 818 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 465 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 897 of file bp_support_sada.hpp.
|
inline |
Definition at line 443 of file bp_support_sada.hpp.
|
inline |
The size of the supported balanced parentheses sequence.
Definition at line 890 of file bp_support_sada.hpp.
const rank_type& 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 312 of file bp_support_sada.hpp.
const select_type& 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 313 of file bp_support_sada.hpp.
const med_block_array_type& 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 316 of file bp_support_sada.hpp.
const sml_block_array_type& 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 314 of file bp_support_sada.hpp.