SDSL 3.0.1
Succinct Data Structure Library
sdsl::rrr_helper< n > Struct Template Reference

Class to encode and decode binomial coefficients on the fly. More...

#include <rrr_helper.hpp>

Public Types

typedef binomial_coefficients< n > binomial
 The struct containing the binomial coefficients. More...
 
typedef binomial::number_type number_type
 The used number type, e.g. More...
 
typedef binomial::trait trait
 The number trait. More...
 

Static Public Member Functions

static uint16_t space_for_bt (uint16_t i)
 Returns the space usage in bits of the binary representation of the number ${n \choose k}$. More...
 
template<class bit_vector_type >
static number_type decode_btnr (const bit_vector_type &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
 
template<class bit_vector_type >
static void set_bt (bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
 
template<class bit_vector_type >
static uint16_t get_bt (const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
 
static number_type bin_to_nr (number_type bin)
 
static bool decode_bit (uint16_t k, number_type nr, uint16_t off)
 Decode the bit at position $ off $ of the block encoded by the pair (k, nr). More...
 
static uint64_t decode_int (uint16_t k, number_type nr, uint16_t off, uint16_t len)
 Decode the len-bit integer starting at position $ off $ of the block encoded by the pair (k, nr). More...
 
static uint16_t decode_popcount (uint16_t k, number_type nr, uint16_t off)
 Decode the first off bits bits of the block encoded by the pair (k, nr) and return the set bits. More...
 
static uint16_t decode_select (uint16_t k, number_type &nr, uint16_t sel)
 
template<uint8_t pattern, uint8_t len>
static uint16_t decode_select_bitpattern (uint16_t k, number_type &nr, uint16_t sel)
 

Detailed Description

template<uint16_t n>
struct sdsl::rrr_helper< n >

Class to encode and decode binomial coefficients on the fly.

The basic encoding and decoding process is described in Gonzalo Navarro and Eliana Providel: Fast, Small, Simple Rank/Select on Bitmaps, SEA 2012

Implemented optimizations in the decoding process:

  • Constant time handling for uniform blocks (only zeros or ones in the block)
  • Constant time handling for blocks contains only a single one bit.
  • Decode blocks with at most $ k<n\log(n) $ by a binary search for the ones.
  • For operations decode_popcount, decode_select, and decode_bit a block is only decoded as long as the query is not answered yet.

Definition at line 280 of file rrr_helper.hpp.

Member Typedef Documentation

◆ binomial

template<uint16_t n>
typedef binomial_coefficients<n> sdsl::rrr_helper< n >::binomial

The struct containing the binomial coefficients.

Definition at line 282 of file rrr_helper.hpp.

◆ number_type

template<uint16_t n>
typedef binomial::number_type sdsl::rrr_helper< n >::number_type

The used number type, e.g.

uint64_t, uint128_t,...

Definition at line 283 of file rrr_helper.hpp.

◆ trait

template<uint16_t n>
typedef binomial::trait sdsl::rrr_helper< n >::trait

The number trait.

Definition at line 284 of file rrr_helper.hpp.

Member Function Documentation

◆ bin_to_nr()

template<uint16_t n>
static number_type sdsl::rrr_helper< n >::bin_to_nr ( number_type  bin)
inlinestatic

Definition at line 314 of file rrr_helper.hpp.

◆ decode_bit()

template<uint16_t n>
static bool sdsl::rrr_helper< n >::decode_bit ( uint16_t  k,
number_type  nr,
uint16_t  off 
)
inlinestatic

Decode the bit at position $ off $ of the block encoded by the pair (k, nr).

Definition at line 337 of file rrr_helper.hpp.

◆ decode_btnr()

template<uint16_t n>
template<class bit_vector_type >
static number_type sdsl::rrr_helper< n >::decode_btnr ( const bit_vector_type &  bv,
typename bit_vector_type::size_type  btnrp,
uint16_t  btnrlen 
)
inlinestatic

Definition at line 290 of file rrr_helper.hpp.

◆ decode_int()

template<uint16_t n>
static uint64_t sdsl::rrr_helper< n >::decode_int ( uint16_t  k,
number_type  nr,
uint16_t  off,
uint16_t  len 
)
inlinestatic

Decode the len-bit integer starting at position $ off $ of the block encoded by the pair (k, nr).

Definition at line 397 of file rrr_helper.hpp.

◆ decode_popcount()

template<uint16_t n>
static uint16_t sdsl::rrr_helper< n >::decode_popcount ( uint16_t  k,
number_type  nr,
uint16_t  off 
)
inlinestatic

Decode the first off bits bits of the block encoded by the pair (k, nr) and return the set bits.

Definition at line 441 of file rrr_helper.hpp.

◆ decode_select()

template<uint16_t n>
static uint16_t sdsl::rrr_helper< n >::decode_select ( uint16_t  k,
number_type nr,
uint16_t  sel 
)
inlinestatic
Precondition
k >= sel, sel>0

Definition at line 504 of file rrr_helper.hpp.

◆ decode_select_bitpattern()

template<uint16_t n>
template<uint8_t pattern, uint8_t len>
static uint16_t sdsl::rrr_helper< n >::decode_select_bitpattern ( uint16_t  k,
number_type nr,
uint16_t  sel 
)
inlinestatic
Precondition
k >= sel, sel>0

Definition at line 561 of file rrr_helper.hpp.

◆ get_bt()

template<uint16_t n>
template<class bit_vector_type >
static uint16_t sdsl::rrr_helper< n >::get_bt ( const bit_vector_type &  bv,
typename bit_vector_type::size_type  pos,
uint16_t  block_size 
)
inlinestatic

Definition at line 307 of file rrr_helper.hpp.

◆ set_bt()

template<uint16_t n>
template<class bit_vector_type >
static void sdsl::rrr_helper< n >::set_bt ( bit_vector_type &  bv,
typename bit_vector_type::size_type  pos,
number_type  bt,
uint16_t  space_for_bt 
)
inlinestatic

Definition at line 298 of file rrr_helper.hpp.

◆ space_for_bt()

template<uint16_t n>
static uint16_t sdsl::rrr_helper< n >::space_for_bt ( uint16_t  i)
inlinestatic

Returns the space usage in bits of the binary representation of the number ${n \choose k}$.

Definition at line 287 of file rrr_helper.hpp.


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