sdsl/include/sdsl/algorithms_for_balanced_parentheses.hpp File Reference

algorithms.hpp contains algorithms for balanced parentheses sequences. More...

#include "int_vector.hpp"
#include <stack>
#include <map>
#include "sorted_stack_support.hpp"

Go to the source code of this file.

Namespaces
namespace	sdsl
	Namespace for the succinct data structure library.
namespace	sdsl::algorithm
	A helper class containing algorithms for succinct data structures.
Functions
void	sdsl::algorithm::calculate_pioneers_bitmap (const bit_vector &bp, bit_vector::size_type block_size, bit_vector &pioneer_bitmap)
	Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)
template<class size_type >
void	sdsl::algorithm::calculate_pioneers_bitmap_succinct (const bit_vector &bp, size_type block_size, bit_vector &pioneer_bitmap)
	Calculate pioneers as defined in the paper of Geary et al. (CPM 2004) with few extra space.
template<class size_type >
void	sdsl::algorithm::calculate_pioneers_bitmap_succinct2 (const bit_vector &bp, size_type block_size, bit_vector &pioneer_bitmap)
template<class int_vector >
void	sdsl::algorithm::calculate_matches (const bit_vector &bp, int_vector &matches)
	Calculates matches (i.e. find_open for a closing parenthesis and find_close for an opening parenthesis)
template<class int_vector >
void	sdsl::algorithm::calculate_matches_for_pioneers (const bit_vector &bp, const bit_vector &pioneer_bitmap, int_vector &matches)
template<class int_vector >
void	sdsl::algorithm::calculate_enclose (const bit_vector &bp, int_vector &enclose)
	Calculates enclose answers for a balanced parentheses sequence.
template<class bp_support >
bool	sdsl::algorithm::check_bp_support (const bit_vector &bp, bp_support bp_s)
bit_vector::size_type	sdsl::algorithm::near_find_close_naive (const bit_vector &bp, bit_vector::size_type i, const bit_vector::size_type block_size)
	Find the near closing parenthesis if it exists.
bit_vector::size_type	sdsl::algorithm::near_find_close (const bit_vector &bp, const bit_vector::size_type i, const bit_vector::size_type block_size)
bit_vector::size_type	sdsl::algorithm::near_find_closing (const bit_vector &bp, bit_vector::size_type i, bit_vector::size_type closings, const bit_vector::size_type block_size)
bit_vector::size_type	sdsl::algorithm::near_fwd_excess (const bit_vector &bp, bit_vector::size_type i, bit_vector::difference_type rel, const bit_vector::size_type block_size)
	This method searches the minimal parenthesis j, with j>=i, such that excess(j) = excess(i-1)+rel.
bit_vector::size_type	sdsl::algorithm::near_rmq (const bit_vector &bp, bit_vector::size_type l, bit_vector::size_type r, bit_vector::difference_type &min_rel_ex)
	Calculate the position with minimal excess value in the interval [l..r].
bit_vector::size_type	sdsl::algorithm::near_bwd_excess (const bit_vector &bp, bit_vector::size_type i, bit_vector::difference_type rel, const bit_vector::size_type block_size)
	This method searches the maximal parenthesis j, with , such that and.
bit_vector::size_type	sdsl::algorithm::near_find_open_naive (const bit_vector &bp, bit_vector::size_type i, const bit_vector::size_type block_size)
	Find the near opening parenthesis if it exists.
bit_vector::size_type	sdsl::algorithm::near_find_open (const bit_vector &bp, bit_vector::size_type i, const bit_vector::size_type block_size)
bit_vector::size_type	sdsl::algorithm::near_find_opening (const bit_vector &bp, bit_vector::size_type i, const bit_vector::size_type openings, const bit_vector::size_type block_size)
bit_vector::size_type	sdsl::algorithm::near_enclose (const bit_vector &bp, bit_vector::size_type i, const bit_vector::size_type block_size)
	Find the opening parenthesis of the enclosing pair if this parenthesis is near.
bit_vector::size_type	sdsl::algorithm::near_rmq_open (const bit_vector &bp, const bit_vector::size_type begin, const bit_vector::size_type end)
bit_vector::size_type	sdsl::algorithm::near_rmq_open_naive (const bit_vector &bp, const bit_vector::size_type begin, const bit_vector::size_type end)
Variables
const uint32_t	sdsl::algorithm::near_find_close_8bits_lookup [256]
const uint32_t	sdsl::algorithm::near_find_open_8bits_lookup [256]
const int8_t	sdsl::algorithm::excess_8bits_lookup [256]
const unsigned char	sdsl::algorithm::near_fwd_excess_8bits_lookup [4352]
const int8_t	sdsl::algorithm::near_rmq_8bits_val_lookup [256]
const int8_t	sdsl::algorithm::near_rightmost_rmq_8bits_pos_lookup [256]
const unsigned char	sdsl::algorithm::near_bwd_excess_8bits_lookup [4352]
const uint16_t	sdsl::algorithm::min_excess_info_8bits_lookup [256]

---

Detailed Description

algorithms.hpp contains algorithms for balanced parentheses sequences.

Author:

Simon Gog