SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
Public Types | Static Public Member Functions | List of all members
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.
 
typedef binomial::number_type number_type
 The used number type, e.g.
 
typedef binomial::trait trait
 The number trait.
 

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}$.
 
template<class bit_vector_type>
static number_type decode_btnr (bit_vector_type const &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 (bit_vector_type const &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).
 
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).
 
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.
 
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 313 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 315 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 316 of file rrr_helper.hpp.

◆ trait

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

The number trait.

Definition at line 317 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 346 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 369 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 ( bit_vector_type const & bv,
typename bit_vector_type::size_type btnrp,
uint16_t btnrlen )
inlinestatic

Definition at line 327 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 439 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 487 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 559 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 619 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 ( bit_vector_type const & bv,
typename bit_vector_type::size_type pos,
uint16_t block_size )
inlinestatic

Definition at line 341 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 334 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 320 of file rrr_helper.hpp.

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