SDSL  3.0.0
Succinct Data Structure Library
sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > Class Template Reference

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

#include <bp_support_g.hpp>

Public Types

typedef bit_vector::size_type size_type
 
typedef t_nnd nnd_type
 
typedef t_rank rank_type
 
typedef t_select select_type
 
typedef t_rmq rmq_type
 

Public Member Functions

 bp_support_g (const bit_vector *bp=nullptr)
 Constructor. More...
 
 bp_support_g (const bp_support_g &v)
 Copy constructor. More...
 
 bp_support_g (bp_support_g &&bp_support)
 Move constructor. More...
 
bp_support_goperator= (const bp_support_g &bp_support)
 Assignment operator. More...
 
bp_support_goperator= (bp_support_g &&bp_support)
 Assignment operator. More...
 
void set_vector (const bit_vector *bp)
 
size_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 find_open_in_pioneers (size_type i) const
 
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. More...
 
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 rr_enclose_naive (size_type i, size_type j) const
 The range restricted enclose operation. More...
 
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]$. 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 procede position i in the balanced parentheses sequence. 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_g to a stream. More...
 
void load (std::istream &in, const bit_vector *bp)
 Load the bp_support_g 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_g const &other) const noexcept
 Equality operator. More...
 
bool operator!= (bp_support_g const &other) const noexcept
 Inequality operator. More...
 

Public Attributes

const rank_typebp_rank = m_rank_bp
 
const select_typebp_select = m_select_bp
 

Detailed Description

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
class sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >

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_nndType which supports rank and select with little space on sparse populated bit_vectors.
t_rankType of rank support structure.
t_selectType of select support structure.
t_rmqType which supports range maximum queries on a int_vector<>.
Reference
Richard F. Geary, Naila Rahman, Rajeev Raman, Venkatesh Raman: A Simple Optimal Representation for Balanced Parentheses. CPM 2004: 159-172

Definition at line 57 of file bp_support_g.hpp.

Member Typedef Documentation

◆ nnd_type

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
typedef t_nnd sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::nnd_type

Definition at line 63 of file bp_support_g.hpp.

◆ rank_type

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
typedef t_rank sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::rank_type

Definition at line 64 of file bp_support_g.hpp.

◆ rmq_type

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
typedef t_rmq sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::rmq_type

Definition at line 66 of file bp_support_g.hpp.

◆ select_type

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
typedef t_select sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::select_type

Definition at line 65 of file bp_support_g.hpp.

◆ size_type

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
typedef bit_vector::size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::size_type

Definition at line 62 of file bp_support_g.hpp.

Constructor & Destructor Documentation

◆ bp_support_g() [1/3]

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::bp_support_g ( const bit_vector bp = nullptr)
inlineexplicit

Constructor.

Definition at line 95 of file bp_support_g.hpp.

◆ bp_support_g() [2/3]

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::bp_support_g ( const bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > &  v)
inline

Copy constructor.

Definition at line 119 of file bp_support_g.hpp.

◆ bp_support_g() [3/3]

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::bp_support_g ( bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > &&  bp_support)
inline

Move constructor.

Definition at line 140 of file bp_support_g.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
template<typename archive_t >
void sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 682 of file bp_support_g.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
template<typename archive_t >
void sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 666 of file bp_support_g.hpp.

◆ double_enclose()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 581 of file bp_support_g.hpp.

◆ enclose()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 333 of file bp_support_g.hpp.

◆ excess()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 191 of file bp_support_g.hpp.

◆ find_close()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 211 of file bp_support_g.hpp.

◆ find_open()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 267 of file bp_support_g.hpp.

◆ find_open_in_pioneers()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::find_open_in_pioneers ( size_type  i) const
inline

Definition at line 301 of file bp_support_g.hpp.

◆ load()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
void sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::load ( std::istream &  in,
const bit_vector bp 
)
inline

Load the bp_support_g 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 647 of file bp_support_g.hpp.

◆ operator!=()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
bool sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::operator!= ( bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 710 of file bp_support_g.hpp.

◆ operator=() [1/2]

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
bp_support_g& sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::operator= ( bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > &&  bp_support)
inline

Assignment operator.

Definition at line 154 of file bp_support_g.hpp.

◆ operator=() [2/2]

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
bp_support_g& sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::operator= ( const bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > &  bp_support)
inline

Assignment operator.

Definition at line 143 of file bp_support_g.hpp.

◆ operator==()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
bool sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::operator== ( bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 700 of file bp_support_g.hpp.

◆ preceding_closing_parentheses()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::preceding_closing_parentheses ( size_type  i) const
inline

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

Parameters
iIndex of an parenthesis.

Definition at line 595 of file bp_support_g.hpp.

◆ rank()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 196 of file bp_support_g.hpp.

◆ rmq()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 554 of file bp_support_g.hpp.

◆ rmq_open()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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. The algorithm consists of 4 steps:
  1. scan back from position r to the begin of that block
  2. recursively scan back the pioneers of the blocks which lie in between the blocks of l and r
  3. scan from position l to the end of the block, which contains l
  4. check if there exists a valid solution and return
Time complexity
$ \Order{block\_size} $

Definition at line 425 of file bp_support_g.hpp.

◆ rr_enclose()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::rr_enclose ( const size_type  i,
const 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 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 404 of file bp_support_g.hpp.

◆ rr_enclose_naive()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 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().

Definition at line 533 of file bp_support_g.hpp.

◆ select()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::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 203 of file bp_support_g.hpp.

◆ serialize()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Serializes the bp_support_g to a stream.

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

Definition at line 621 of file bp_support_g.hpp.

◆ set_vector()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
void sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::set_vector ( const bit_vector bp)
inline

Definition at line 181 of file bp_support_g.hpp.

◆ size()

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
size_type sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::size ( ) const
inline

The size of the supported balanced parentheses sequence.

Returns
the size of the supported balanced parentheses sequence.

Definition at line 614 of file bp_support_g.hpp.

Member Data Documentation

◆ bp_rank

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
const rank_type& sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::bp_rank = m_rank_bp

Definition at line 91 of file bp_support_g.hpp.

◆ bp_select

template<class t_nnd = nearest_neighbour_dictionary<30>, class t_rank = rank_support_v5<>, class t_select = select_support_mcl<>, class t_rmq = range_maximum_support_sparse_table<>, uint32_t t_bs = 840>
const select_type& sdsl::bp_support_g< t_nnd, t_rank, t_select, t_rmq, t_bs >::bp_select = m_select_bp

Definition at line 92 of file bp_support_g.hpp.


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