A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Kunihiko Sadakane in the paper "The Ultimate Balanced Parentheses" (Technical Report 2008). 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
Public Member Functions
	bp_support_sada (const bit_vector *bp)
	Constructor.
	bp_support_sada (const bp_support_sada &bp_support)
	Copy constructor.
	~bp_support_sada ()
	Destructor.
void	swap (bp_support_sada &bp_support)
	Swap method.
bp_support_sada &	operator= (const bp_support_sada &bp_support)
	Assignment operator.
void	set_vector (const bit_vector *bp)
difference_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 (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
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 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_sada to a stream.
void	load (std::istream &in, const bit_vector *bp)
	Load the bp_support_sada for a bit_vector v.
std::string	get_info () const
Public Attributes
const RankSupport &	bp_rank
	The rank support for the supported balanced parentheses sequence.
const SelectSupport &	bp_select
	The select support for the supported balanced parentheses sequence.
const sml_block_array_type &	sml_block_min_max
	The array which contains the entries of the small blocks. I.e. the relative maximum and minimum for the small blocks.
const med_block_array_type &	med_block_min_max
	The array which contains the min max tree of the medium blocks.

Detailed Description

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>
class sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >

A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Kunihiko Sadakane in the paper "The Ultimate Balanced Parentheses" (Technical Report 2008).

This data structure supports the following methods on a bit_vector b that represents a balanced parentheses sequence:

rank
select
excess
find_open
find_close
enclose
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.

This class could be parametrized by four parameters:

SmlBlkSize is the size of the small blocks. Denoted as "s" in Sadakane's paper.
MedBlkDeg is the number of small blocks that a medium block contains. Denoted as "l" in Sadakane's paper.
RankSupport is a class which support the rank operation on bit_vectors.
SelectSupport is a class which support the select operation on bit_vectors.

Member Function Documentation

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::double_enclose	(	size_type	i,
		size_type	j
	)		const `[inline]`

The double enclose operation.

Parameters:

i	Index of an opening parenthesis.
j	Index 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().

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::enclose ( size_type i ) const [inline]

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<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

difference_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::excess ( size_type i ) const [inline]

Calculates the excess value at index i.

Parameters:

i	The index of which the excess value should be calculated.

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::find_close ( size_type i ) const [inline]

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<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::find_open ( size_type i ) const [inline]

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<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

void sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::load	(	std::istream &	in,
		const bit_vector *	bp
	)		`[inline]`

Load the bp_support_sada 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<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::preceding_closing_parentheses ( size_type i ) const [inline]

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

Parameters:

i	Index of an parenthesis.

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::rank ( size_type i ) const [inline]

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

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

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::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:

l	The left border of the interval ( $l\leq r$ ).
r	The right border of the interval ( $l \leq r$ ).

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::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:

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.

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}$

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::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:

i	First opening parenthesis.
j	Second 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}$

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::rr_enclose_naive	(	size_type	i,
		size_type	j
	)		const `[inline]`

The range restricted enclose operation.

Parameters:

i	Index of an opening parenthesis.
j	Index of an opening parenthesis $i<j \wedge findclose(i) < j$ .

Returns:: The minimal opening parenthesis, say k, such that 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.

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::select ( size_type i ) const [inline]

Returns the index of the i-th opening parenthesis.

Parameters:

i	Number of the parenthesis to select.

Precondition:: { $1\leq i < rank(size())$ }

Postcondition:: { $0\leq select(i) < size()$ }

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = `NULL`,
		std::string	name = `""`
	)		const `[inline]`

Serializes the bp_support_sada to a stream.

Parameters:

out	The outstream to which the data structure is written.

Returns:: The number of bytes written to out.

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

size_type sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::size ( ) const [inline]

The size of the supported balanced parentheses sequence.

Returns:: the size of the supported balanced parentheses sequence.

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>

void sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >::swap ( bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport > & bp_support ) [inline]

Swap method.

Swaps the content of the two data structure. You have to use set_vector to adjust the supported bit_vector.

Parameters:

bp_support Object which is swapped.

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

sdsl/include/sdsl/bp_support_sada.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>> class sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >

Member Function Documentation

template<uint32_t SmlBlkSize = 256, uint32_t MedBlkDeg = 32, class RankSupport = rank_support_v<>, class SelectSupport = select_support_mcl<>>
class sdsl::bp_support_sada< SmlBlkSize, MedBlkDeg, RankSupport, SelectSupport >