SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
Functions | Variables
sdsl::algorithm Namespace Reference

A helper class containing algorithms for succinct data structures. More...

Functions

double H_0 (const unsigned char *c)
 Calculate the zero-order entropy for a text T.
double H_0s (const unsigned char *c)
template<class RandomAccessContainer1 , class RandomAccessContainer2 >
void calculate_psv (const RandomAccessContainer1 &a, RandomAccessContainer2 &psv)
 Calculate the previous smaller value (psv) array for a random access container a.
void 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 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 calculate_pioneers_bitmap_succinct2 (const bit_vector &bp, size_type block_size, bit_vector &pioneer_bitmap)
template<class int_vector >
void 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 calculate_matches_for_pioneers (const bit_vector &bp, const bit_vector &pioneer_bitmap, int_vector &matches)
template<class int_vector >
void calculate_enclose (const bit_vector &bp, int_vector &enclose)
 Calculates enclose answers for a balanced parentheses sequence.
template<class bp_support >
bool check_bp_support (const bit_vector &bp, bp_support bp_s)
bit_vector::size_type 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 near_find_close (const bit_vector &bp, const bit_vector::size_type i, const bit_vector::size_type block_size)
bit_vector::size_type 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 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 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 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 $ j\leq i $, such that $ excess(j) = excess(i+1)+rel $ and.
bit_vector::size_type 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 near_find_open (const bit_vector &bp, bit_vector::size_type i, const bit_vector::size_type block_size)
bit_vector::size_type 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 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 near_rmq_open (const bit_vector &bp, const bit_vector::size_type begin, const bit_vector::size_type end)
bit_vector::size_type near_rmq_open_naive (const bit_vector &bp, const bit_vector::size_type begin, const bit_vector::size_type end)
template<class Csa >
void set_text (const unsigned char *str, typename Csa::size_type len, int_vector< 64 > &C, int_vector< 8 > &char2comp, int_vector< 8 > &comp2char, uint16_t &sigma)
template<class Csa , class size_type_class >
void set_text (int_vector_file_buffer< 8, size_type_class > &str_buf, typename Csa::size_type len, int_vector< 64 > &C, int_vector< 8 > &char2comp, int_vector< 8 > &comp2char, uint16_t &sigma)
template<class Csa >
bool char_occures_in_text_of_csa (const Csa &csa, typename Csa::char_type c)
 Calculates if a character c occures in the text of the compressed suffix array c.
template<class Csa , uint8_t int_width, class size_type_class >
void set_sa_and_isa_samples (int_vector_file_buffer< int_width, size_type_class > &sa_buf, typename Csa::sa_sample_type &sa_sample, typename Csa::isa_sample_type &isa_sample)
template<class Csa >
const unsigned char get_ith_character_of_the_first_row (const typename Csa::size_type i, const Csa &csa)
template<class RandomAccessContainer >
void construct_supercartesian_tree_bp (const RandomAccessContainer &vec, bit_vector &bp, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).
template<class RandomAccessContainer >
void construct_supercartesian_tree_bp_succinct (const RandomAccessContainer &vec, bit_vector &bp, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).
template<uint8_t fixedIntWidth, class size_type_class >
void construct_supercartesian_tree_bp_succinct (int_vector_file_buffer< fixedIntWidth, size_type_class > &lcp_buf, bit_vector &bp, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).
template<uint8_t fixedIntWidth, class size_type_class >
size_type_class construct_supercartesian_tree_bp_succinct_and_first_child (int_vector_file_buffer< fixedIntWidth, size_type_class > &lcp_buf, bit_vector &bp, bit_vector &bp_fc, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009) and the first_child bit_vector.
template<uint8_t fixedIntWidth, class size_type_class >
size_type_class construct_first_child_lcp (int_vector_file_buffer< fixedIntWidth, size_type_class > &lcp_buf, int_vector< fixedIntWidth, size_type_class > &fc_lcp, size_type_class first_child_size=0)
template<uint32_t SampleDens, uint8_t fixedIntWidth, class size_type_class >
size_type_class construct_first_child_and_lf_lcp (int_vector_file_buffer< fixedIntWidth, size_type_class > &lcp_buf, int_vector_file_buffer< 8, size_type_class > &bwt_buf, std::string small_lcp_file_name, std::string big_lcp_file_name, int_vector<> &big_lcp, size_type_class first_child_size=0)
template<class RandomAccessContainer >
void construct_supercartesian_tree_bp_succinct2 (const RandomAccessContainer &vec, bit_vector &bp, const bool minimum=true)
template<class RandomAccessContainer >
RandomAccessContainer::size_type construct_first_p_index (const RandomAccessContainer &vec, bit_vector &bp, const bool minimum=true)
template<uint8_t fixedIntWidth, class size_type_class >
bit_vector::size_type construct_first_p_index (int_vector_file_buffer< fixedIntWidth, size_type_class > &lcp_buf, bit_vector &bp, const bool minimum=true)
template<class Cst >
Cst::cst_size_type forward_search (const Cst &cst, typename Cst::node_type &v, const typename Cst::size_type d, const typename Cst::char_type c, typename Cst::size_type &char_pos)
 Forward search for a character c on the path on depth $d$ to node $v$.
template<class Cst >
Cst::cst_size_type forward_search (const Cst &cst, typename Cst::node_type &v, typename Cst::size_type d, typename Cst::pattern_type pat, typename Cst::size_type len, typename Cst::size_type &char_pos)
 Forward search for a pattern pat on the path on depth $d$ to node $v$.
template<class Cst >
Cst::cst_size_type count (const Cst &cst, typename Cst::pattern_type pat, typename Cst::size_type len)
 Calculates the count method for a (compressed) suffix tree of type Cst.
template<class Cst , class RandomAccessContainer >
Cst::cst_size_type locate (const Cst &cst, typename Cst::pattern_type pat, typename Cst::size_type len, RandomAccessContainer &occ)
 Calculates the locate method for a (compressed) suffix tree of type Cst.
template<class Cst >
void extract (const Cst &cst, const typename Cst::node_type &v, unsigned char *text)
 Calculate the concatenation of edge labels from the root to the node v of the (compressed) suffix tree of type Cst.
template<class Cst >
std::string extract (const Cst &cst, const typename Cst::node_type &v)
 Calculate the concatenation of edge labels from the root to the node v of the (compressed) suffix tree of type Cst.

Variables

const uint32_t near_find_close_8bits_lookup [256]
const uint32_t near_find_open_8bits_lookup [256]
const int8_t excess_8bits_lookup [256]
const unsigned char near_fwd_excess_8bits_lookup [4352]
const int8_t near_rmq_8bits_val_lookup [256]
const int8_t near_rightmost_rmq_8bits_pos_lookup [256]
const unsigned char near_bwd_excess_8bits_lookup [4352]
const uint16_t min_excess_info_8bits_lookup [256]

Detailed Description

A helper class containing algorithms for succinct data structures.

Author:
Simon Gog

Function Documentation

template<class int_vector >
void sdsl::algorithm::calculate_enclose ( const bit_vector &  bp,
int_vector &  enclose 
)

Calculates enclose answers for a balanced parentheses sequence.

Parameters:
bpA bit_vector representing a balanced parentheses sequence.
encloseReference to the result.
Precondition:
bp represents a balanced parentheses sequence.
Time complexity
$ \Order{n} $, where $ n=$bp.size()
Space complexity
$ \Order{n + 2n\log n } $
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)

Parameters:
bpA bit_vector representing a balanced parentheses sequence.
matchesReference to the result.
Precondition:
bp represents a balanced parentheses sequence.
Time complexity
$ \Order{n} $, where $ n=$bp.size()
Space complexity
$ \Order{n + 2n\log n } $
void sdsl::algorithm::calculate_pioneers_bitmap ( const bit_vector &  bp,
bit_vector::size_type  block_size,
bit_vector &  pioneer_bitmap 
) [inline]

Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)

Parameters:
bpThe balanced parentheses sequence for that the pioneers should be calculated.
block_sizeSize of the blocks for which the pioneers should be calculated.
pioneer_bitmapReference to the resulting bit_vector.
Time complexity
$ \Order{n \log n} $, where $ n=$bp.size()
Space complexity
$ \Order{2n + min(block\_size, \frac{n}{block\_size} )\cdot \log n } $
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.

Parameters:
bpThe balanced parentheses sequence for that the pioneers should be calculated.
block_sizeSize of the blocks for which the pioneers should be calculated.
pioneer_bitmapReference to the resulting bit_vector.
Time complexity
$ \Order{n} $, where $ n=$bp.size()
Space complexity
$ \Order{2n + n} $ bits: $n$ bits for input, $n$ bits for output, and $n$ bits for a succinct stack.
Precondition:
The parentheses sequence represented by bp has to be balanced.
template<class RandomAccessContainer1 , class RandomAccessContainer2 >
void sdsl::algorithm::calculate_psv ( const RandomAccessContainer1 &  a,
RandomAccessContainer2 &  psv 
)

Calculate the previous smaller value (psv) array for a random access container a.

Parameters:
aContainer to calculate the psv array.
psvContainer that contains the result after the calculation.
Precondition:
The array a contains only non negative values and a.size() == psv.size().
Postcondition:

\[ psv[i] = \begin{array}{rl} a.size() &\mbox{ if} \min\{ a[j] \mid j<i \} \geq a[i] \\ max\{j\mid a[j] < a[i] \wedge j<i\} &\mbox{ otherwise.}\end{array} \]

template<class Csa >
bool sdsl::algorithm::char_occures_in_text_of_csa ( const Csa &  csa,
typename Csa::char_type  c 
)

Calculates if a character c occures in the text of the compressed suffix array c.

Parameters:
csaThe csa in which we search for the occurence of c.
cThe character c for which we search in the text of the compressed suffix array.
Returns:
True, if c occures in the text of the compressed suffix array and False otherwise.
Precondition:
$ csa.size()>0 $
template<class RandomAccessContainer >
void sdsl::algorithm::construct_supercartesian_tree_bp ( const RandomAccessContainer &  vec,
bit_vector &  bp,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).

Parameters:
vecRandom access container for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
bpReference to the balanced parentheses sequence which represents the Super-Cartesian tree.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$ \Order{n \cdot \log n } $ bits.
template<class RandomAccessContainer >
void sdsl::algorithm::construct_supercartesian_tree_bp_succinct ( const RandomAccessContainer &  vec,
bit_vector &  bp,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).

Parameters:
vecRandom access container for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
bpReference to the balanced parentheses sequence which represents the Super-Cartesian tree.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$\Order{n}$ bits, by the stack_support described in the paper "Optimal Succinctness For Range Minimum Queries" of Johannes Fischer.
template<uint8_t fixedIntWidth, class size_type_class >
void sdsl::algorithm::construct_supercartesian_tree_bp_succinct ( int_vector_file_buffer< fixedIntWidth, size_type_class > &  lcp_buf,
bit_vector &  bp,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).

Parameters:
lcp_bufint_vector_file_buffer of the LCP Array for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
bpReference to the balanced parentheses sequence which represents the Super-Cartesian tree.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$\Order{2n}$ bits, by the multi_stack_support
template<uint8_t fixedIntWidth, class size_type_class >
size_type_class sdsl::algorithm::construct_supercartesian_tree_bp_succinct_and_first_child ( int_vector_file_buffer< fixedIntWidth, size_type_class > &  lcp_buf,
bit_vector &  bp,
bit_vector &  bp_fc,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009) and the first_child bit_vector.

Parameters:
lcp_bufint_vector_file_buffer for the lcp array for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
bpReference to the balanced parentheses sequence which represents the Super-Cartesian tree.
bp_fcReference to the first child bit_vector of bp.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$\Order{2n}$ bits, by the multi_stack_support
template<class Cst >
Cst::cst_size_type sdsl::algorithm::count ( const Cst &  cst,
typename Cst::pattern_type  pat,
typename Cst::size_type  len 
)

Calculates the count method for a (compressed) suffix tree of type Cst.

Parameters:
cstA const reference to the (compressed) suffix tree.
patThe pattern we seach the number of occurences.
lenThe length of the pattern.
Returns:
Number of occurences of the pattern in the text of the (compressed) suffix tree.
template<class Cst >
void sdsl::algorithm::extract ( const Cst &  cst,
const typename Cst::node_type &  v,
unsigned char *  text 
)

Calculate the concatenation of edge labels from the root to the node v of the (compressed) suffix tree of type Cst. 

 \param cst A const reference to the compressed suffix tree.
 \param v The node where the concatenation of the edge labels ends.
 \param text A pointer in which the string representing the concatenation of edge labels form the root to the node v will be stored.
Precondition:
text has to be initialized with enough memory ( $ cst.depth(v)+1$ bytes) to hold the extracted text.
template<class Cst >
std::string sdsl::algorithm::extract ( const Cst &  cst,
const typename Cst::node_type &  v 
)

Calculate the concatenation of edge labels from the root to the node v of the (compressed) suffix tree of type Cst.

Parameters:
cstA const reference to the compressed suffix tree.
vThe node where the concatenation of the edge labels ends.
Returns:
The string of the concatenated edge labels from the root to the node v.
template<class Cst >
Cst::cst_size_type sdsl::algorithm::forward_search ( const Cst &  cst,
typename Cst::node_type &  v,
const typename Cst::size_type  d,
const typename Cst::char_type  c,
typename Cst::size_type &  char_pos 
)

Forward search for a character c on the path on depth $d$ to node $v$. 

   \param cst              The compressed suffix tree.
   \param v                The node at the endpoint of the current edge.
   \param d                The current depth of the path. 0 = first character on each edge of the root node.
   \param c                The character c which should be matched at the path on depth \form#45 to node \form#46.
   \param char_pos One position in the text, which corresponds to the text that is already matched. If v=cst.root() and d=0 => char_pos=0.

   \par Time complexity

$ \Order{ t_{\Psi} } $ or $ \Order{t_{cst.child}} $

template<class Cst >
Cst::cst_size_type sdsl::algorithm::forward_search ( const Cst &  cst,
typename Cst::node_type &  v,
typename Cst::size_type  d,
typename Cst::pattern_type  pat,
typename Cst::size_type  len,
typename Cst::size_type &  char_pos 
)

Forward search for a pattern pat on the path on depth $d$ to node $v$. 

   \param cst              The compressed suffix tree.
   \param v                The node at the endpoint of the current edge.
   \param d                The current depth of the path. 0 = first character on each edge of the root node.
   \param pat      The character c which should be matched at the path on depth \form#45 to node \form#46.
   \param len              The length of the pattern.
   \param char_pos One position in the text, which corresponds to the text that is already matched. If v=cst.root() and d=0 => char_pos=0.

   \par Time complexity

$ \Order{ t_{\Psi} } $ or $ \Order{t_{cst.child}} $

double sdsl::algorithm::H_0 ( const unsigned char *  c)

Calculate the zero-order entropy for a text T.

Parameters:
cPointer to a 0-terminated string.
Returns:
The zero-order entropy of the text.
template<class Cst , class RandomAccessContainer >
Cst::cst_size_type sdsl::algorithm::locate ( const Cst &  cst,
typename Cst::pattern_type  pat,
typename Cst::size_type  len,
RandomAccessContainer &  occ 
)

Calculates the locate method for a (compressed) suffix tree of type Cst.

Parameters:
cstA const reference to the (compressed) suffix tree.
patThe pattern for which we seach the occurences for.
lenThe length of the pattern.
occA reference to a random access container in which we store the occurences of pattern in the text of the (compressed suffix array).
Returns:
Number of occurences of the pattern in the text of the (compressed) suffix tree.
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 
) [inline]

This method searches the maximal parenthesis j, with $ j\leq i $, such that $ excess(j) = excess(i+1)+rel $ and.

i < bp.size()-1

bit_vector::size_type sdsl::algorithm::near_enclose ( const bit_vector &  bp,
bit_vector::size_type  i,
const bit_vector::size_type  block_size 
) [inline]

Find the opening parenthesis of the enclosing pair if this parenthesis is near.

Parameters:
bpbit_vector containing the representation of the balanced parentheses sequence.
iPosition of the opening parenthesis for which we search the position of the opening parenthesis of the enclosing parentheses pair.
block_sizeNumber of entries to search for the corresponding opening parenthesis of the enclosing parentheses pair.
Returns:
If no near enclose exists return i, otherwise the position of the opening parenthesis of the enclosing pair.
Precondition:
We assert that $ bp[i]=1 $
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 
) [inline]

Find the near closing parenthesis if it exists.

Parameters:
bpbit_vector containing the representation of the balanced parentheses sequence.
iPosition of the opening parenthesis we for which search the corresponding closing parenthesis.
block_sizeNumber of entries to search for the corresponding closing parenthesis.
Returns:
i if there is no near find_close answer, otherwise the position of the near closing parenthesis.
Precondition:
We assert that $ bp[i]=1 $ holds, i.e. there is an opening parenthesis at position i.
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 
) [inline]

Find the near opening parenthesis if it exists.

Parameters:
bpbit_vector containing the representation of the balanced parentheses sequence.
iPosition of the closing parenthesis for which we search the corresponding opening parenthesis.
block_sizeNumber of entries to search for the corresponding opening parenthesis.
Returns:
i if there is no near opening parenthesis, otherwise the position of the near opening parenthesis.
Precondition:
We assert that $ bp[i]=0 $ holds, i.e. there is an closing parenthesis at position i.
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 
) [inline]

This method searches the minimal parenthesis j, with j>=i, such that excess(j) = excess(i-1)+rel.

i>0

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 
) [inline]

Calculate the position with minimal excess value in the interval [l..r].

Parameters:
bpThe bit_vector which represents the parentheses sequence
lThe left border of the interval.
rThe right border of the interval.
min_rel_exReference to the relative minimal excess value with regards to excess(bp[l])

Variable Documentation

const int8_t sdsl::algorithm::excess_8bits_lookup[256]
Initial value:
 {
    -8,-6,-6,-4,-6,-4,-4,-2,-6,-4,-4,-2,-4,-2,-2,0,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2,
    -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2,
    -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4,
    -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4,
    -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2,
    -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4,
    -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4,
    -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6,
    -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4,
    -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6,
    -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6,
    0,2,2,4,2,4,4,6,2,4,4,6,4,6,6,8
}
const uint16_t sdsl::algorithm::min_excess_info_8bits_lookup[256]
Initial value:
 {
    17,4105,4360,8201,4615,8713,8456,12297,4870,8968,8968,12297,8711,12809,12552,16393,
    5125,9223,9223,13321,9223,13321,12552,16393,8966,13064,13064,16393,12807,16905,16648,20489,
    5380,9478,9478,13576,9478,13576,13576,16393,9478,13576,13576,16393,12807,16905,16648,20489,
    9221,13319,13319,17417,13319,17417,16648,20489,13062,17160,17160,20489,16903,21001,20744,24585,
    5635,9733,9733,13831,9733,13831,13831,17929,9733,13831,13831,17929,13831,17929,16648,20489,
    9733,13831,13831,17929,13831,17929,16648,20489,13062,17160,17160,20489,16903,21001,20744,24585,
    9476,13574,13574,17672,13574,17672,17672,20489,13574,17672,17672,20489,16903,21001,20744,24585,
    13317,17415,17415,21513,17415,21513,20744,24585,17158,21256,21256,24585,20999,25097,24840,28681,
    5890,9988,9988,14086,9988,14086,14086,18184,9988,14086,14086,18184,14086,18184,18184,20489,
    9988,14086,14086,18184,14086,18184,18184,20489,14086,18184,18184,20489,16903,21001,20744,24585,
    9988,14086,14086,18184,14086,18184,18184,20489,14086,18184,18184,20489,16903,21001,20744,24585,
    13317,17415,17415,21513,17415,21513,20744,24585,17158,21256,21256,24585,20999,25097,24840,28681,
    9731,13829,13829,17927,13829,17927,17927,22025,13829,17927,17927,22025,17927,22025,20744,24585,
    13829,17927,17927,22025,17927,22025,20744,24585,17158,21256,21256,24585,20999,25097,24840,28681,
    13572,17670,17670,21768,17670,21768,21768,24585,17670,21768,21768,24585,20999,25097,24840,28681,
    17413,21511,21511,25609,21511,25609,24840,28681,21254,25352,25352,28681,25095,29193,28936,32777
}
const int8_t sdsl::algorithm::near_rightmost_rmq_8bits_pos_lookup[256]
Initial value:
 {
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,0,0,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,0,0,
    7,7,7,7,7,7,0,0,2,2,2,2,1,1,0,0,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,0,0,
    7,7,7,7,7,7,0,0,2,2,2,2,1,1,0,0,
    4,4,4,4,4,4,4,4,4,4,4,4,1,1,0,0,
    3,3,3,3,3,3,0,0,2,2,2,2,1,1,0,0,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    6,6,6,6,6,6,6,6,6,6,6,6,1,1,0,0,
    6,6,6,6,6,6,6,6,6,6,6,6,1,1,0,0,
    3,3,3,3,3,3,0,0,2,2,2,2,1,1,0,0,
    5,5,5,5,5,5,5,5,5,5,5,5,5,5,0,0,
    5,5,5,5,5,5,0,0,2,2,2,2,1,1,0,0,
    4,4,4,4,4,4,4,4,4,4,4,4,1,1,0,0,
    3,3,3,3,3,3,0,0,2,2,2,2,1,1,0,0
}
const int8_t sdsl::algorithm::near_rmq_8bits_val_lookup[256]
Initial value:
 {
    -8,-6,-6,-4,-6,-4,-4,-2,-6,-4,-4,-2,-4,-2,-2,0,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1,
    -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1,
    -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -7,-5,-5,-3,-5,-3,-3,-1,-5,-3,-3,-1,-3,-1,-1,1,
    -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1,
    -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1,
    -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1
}
Generated on Mon Aug 13 2012 15:23:29 for SDSL: Succinct Data Structure Library by   doxygen 1.8.0