SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Public Attributes | List of all members
sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > Class Template Reference
Balanced Parentheses Supports (BPS)

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.
 
 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= (const bp_support_sada &v)
 Assignment operator.
 
 bp_support_sada (const bit_vector *bp)
 Constructor.
 
void set_vector (const bit_vector *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 $(i,\mu(i))$ and $(j,\mu(j))$.
 
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 $[l..r]$.
 
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, const bit_vector *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

const rank_type & bp_rank = m_bp_rank
 RS for the underlying BP sequence.
 
const select_type & bp_select = m_bp_select
 SS for the underlying BP sequence.
 
const sml_block_array_type & sml_block_min_max = m_sml_block_min_max
 Small blocks array.
 
const med_block_array_type & med_block_min_max = m_med_block_min_max
 Array containing the min max tree of the medium blocks.
 

Detailed Description

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
class sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >

A class that provides support for bit_vectors that represent a BP sequence.

This data structure supports the following operations:

  • find_open
  • find_close
  • enclose
  • double_enclose
  • rank
  • select
  • excess
  • 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.
Template Parameters
t_sml_blkThe size of the small blocks. Denoted as s in Sadakane's paper.
t_med_degNumber of small blocks that a medium block contains. Denoted as l in Sadakane's paper.
t_rankType of rank support used for the underlying bitvector.
t_selectType of select support used for the underlying bitvector.
References
  • Kunihiko Sadakane: The Ultimate Balanced Parentheses Technical Report 2008.
  • Kunihiko Sadakane, Gonzalo Navarro: Fully-Functional Succinct Trees. SODA 2010: 134-149

Definition at line 63 of file bp_support_sada.hpp.

Member Typedef Documentation

◆ difference_type

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ med_block_array_type

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ rank_type

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ select_type

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ size_type

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ sml_block_array_type

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

Constructor & Destructor Documentation

◆ bp_support_sada() [1/4]

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::bp_support_sada ( )
inline

Definition at line 319 of file bp_support_sada.hpp.

◆ bp_support_sada() [2/4]

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::bp_support_sada ( const bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > &  v)
inline

Copy constructor.

Definition at line 322 of file bp_support_sada.hpp.

◆ bp_support_sada() [3/4]

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::bp_support_sada ( bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > &&  bp_support)
inline

Move constructor.

Definition at line 338 of file bp_support_sada.hpp.

◆ bp_support_sada() [4/4]

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::bp_support_sada ( const bit_vector *  bp)
inlineexplicit

Constructor.

Definition at line 374 of file bp_support_sada.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
template<typename archive_t >
void sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 951 of file bp_support_sada.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
template<typename archive_t >
void sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 938 of file bp_support_sada.hpp.

◆ double_enclose()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::double_enclose ( size_type  i,
size_type  j 
) const
inline

The double enclose operation.

Parameters
iIndex of an opening parenthesis.
jIndex of an opening parenthesis $ i<j \wedge findclose(i) < j $.
Returns
The maximal opening parenthesis, say k, such that $ k<j \wedge k>findclose(j) $. If such a k does not exists, double_enclose(i,j) returns size().

Definition at line 842 of file bp_support_sada.hpp.

◆ enclose()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::enclose ( size_type  i) const
inline

Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair enclosing i.

Parameters
iIndex 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.

Definition at line 546 of file bp_support_sada.hpp.

◆ excess()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
difference_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::excess ( size_type  i) const
inline

Calculates the excess value at index i.

Parameters
iThe index of which the excess value should be calculated.

Definition at line 453 of file bp_support_sada.hpp.

◆ find_close()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::find_close ( size_type  i) const
inline

Calculate the index of the matching closing parenthesis to the parenthesis at index i.

Parameters
iIndex 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.

Definition at line 486 of file bp_support_sada.hpp.

◆ find_open()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::find_open ( size_type  i) const
inline

Calculate the matching opening parenthesis to the closing parenthesis at position i.

Parameters
iIndex 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.

Definition at line 512 of file bp_support_sada.hpp.

◆ level_anc()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::level_anc ( size_type  i,
size_type  d 
) const
inline

Returns the level ancestor of the node i.

Parameters
iThe index of a parenthesis (i.e., a node).
dThe 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.

◆ load()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
void sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::load ( std::istream &  in,
const bit_vector *  bp 
)
inline

Load the bp_support_sada for a bit_vector v.

Parameters
inThe instream from which the data strucutre is read.
bpBit vector representing a balanced parentheses sequence that is supported by this data structure.

Definition at line 921 of file bp_support_sada.hpp.

◆ median_block_rmq()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::median_block_rmq ( size_type  l_sblock,
size_type  r_sblock,
bit_vector::difference_type &  min_ex 
) const
inline

Definition at line 627 of file bp_support_sada.hpp.

◆ operator!=()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
bool sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::operator!= ( bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 974 of file bp_support_sada.hpp.

◆ operator=() [1/2]

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
bp_support_sada & sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::operator= ( bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > &&  bp_support)
inline

Assignment operator.

Definition at line 341 of file bp_support_sada.hpp.

◆ operator=() [2/2]

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
bp_support_sada & sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::operator= ( const bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > &  v)
inline

Assignment operator.

Definition at line 363 of file bp_support_sada.hpp.

◆ operator==()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
bool sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::operator== ( bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 964 of file bp_support_sada.hpp.

◆ preceding_closing_parentheses()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::preceding_closing_parentheses ( size_type  i) const
inline

Return the number of zeros which proceed position i in the balanced parentheses sequence.

Parameters
iIndex of an parenthesis.

Definition at line 856 of file bp_support_sada.hpp.

◆ rank()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::rank ( size_type  i) const
inline

Returns the number of opening parentheses up to and including index i.

Precondition
{ $ 0\leq i < size() $ }

Definition at line 458 of file bp_support_sada.hpp.

◆ rmq()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::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 $[l..r]$.

Parameters
lThe left border of the interval $[l..r]$ ( $l\leq r$).
rThe right border of the interval $[l..r]$ ( $l \leq r$).

Definition at line 656 of file bp_support_sada.hpp.

◆ rmq_open()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::rmq_open ( const size_type  l,
const size_type  r 
) const
inline

Search the interval [l,r-1] for an opening parenthesis, say i, such that find_close(i) >= r.

Parameters
lThe left end (inclusive) of the interval to search for the result.
rThe right end (exclusive) of the interval to search for the result.
Returns
The minimal opening parenthesis i with $ \ell \leq i < r $ and $ find_close(i) \geq r $; if no such i exists size() is returned.
Time complexity
$ \Order{block\_size} $

Definition at line 585 of file bp_support_sada.hpp.

◆ rr_enclose()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::rr_enclose ( const size_type  i,
const size_type  j 
) const
inline

The range restricted enclose operation for parentheses pairs $(i,\mu(i))$ and $(j,\mu(j))$.

Parameters
iFirst opening parenthesis.
jSecond opening parenthesis $ i<j \wedge findclose(i) < j $.
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().
Time complexity
$ \Order{block\_size} $

Definition at line 568 of file bp_support_sada.hpp.

◆ rr_enclose_naive()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::rr_enclose_naive ( size_type  i,
size_type  j 
) const
inline

The range restricted enclose operation.

Parameters
iIndex of an opening parenthesis.
jIndex of an opening parenthesis $ i<j \wedge findclose(i) < j $.
Returns
The minimal opening parenthesis, say k, such that $ findclose(i) < k < j$ and findclose(j) < findclose(k). If such a k does not exists, restricted_enclose(i,j) returns size().
Time complexity
$ \Order{size()}$ in the worst case.

Definition at line 818 of file bp_support_sada.hpp.

◆ select()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::select ( size_type  i) const
inline

Returns the index of the i-th opening parenthesis.

Parameters
iNumber of the parenthesis to select.
Precondition
{ $1\leq i < rank(size())$ }
Postcondition
{ $ 0\leq select(i) < size() $ }

Definition at line 465 of file bp_support_sada.hpp.

◆ serialize()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::serialize ( std::ostream &  out,
structure_tree_node *  v = nullptr,
std::string  name = "" 
) const
inline

Serializes the bp_support_sada to a stream.

Parameters
outThe outstream to which the data structure is written.
Returns
The number of bytes written to out.

Definition at line 897 of file bp_support_sada.hpp.

◆ set_vector()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
void sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::set_vector ( const bit_vector *  bp)
inline

Definition at line 443 of file bp_support_sada.hpp.

◆ size()

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
size_type sdsl::bp_support_sada< t_sml_blk, t_med_deg, t_rank, t_select >::size ( ) const
inline

The size of the supported balanced parentheses sequence.

Returns
the size of the supported balanced parentheses sequence.

Definition at line 890 of file bp_support_sada.hpp.

Member Data Documentation

◆ bp_rank

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ bp_select

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ med_block_min_max

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

◆ sml_block_min_max

template<uint32_t t_sml_blk = 256, uint32_t t_med_deg = 32, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>>
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.

The documentation for this class was generated from the following file: