SDSL 3.0.1
Succinct Data Structure Library
|
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 ![]() | |
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 ![]() | |
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 ![]() | |
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) |
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:
Definition at line 280 of file rrr_helper.hpp.
typedef binomial_coefficients<n> sdsl::rrr_helper< n >::binomial |
The struct containing the binomial coefficients.
Definition at line 282 of file rrr_helper.hpp.
typedef binomial::number_type sdsl::rrr_helper< n >::number_type |
typedef binomial::trait sdsl::rrr_helper< n >::trait |
The number trait.
Definition at line 284 of file rrr_helper.hpp.
|
inlinestatic |
Definition at line 314 of file rrr_helper.hpp.
|
inlinestatic |
Decode the bit at position
Definition at line 337 of file rrr_helper.hpp.
|
inlinestatic |
Definition at line 290 of file rrr_helper.hpp.
|
inlinestatic |
Decode the len-bit integer starting at position
Definition at line 397 of file rrr_helper.hpp.
|
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.
|
inlinestatic |
Definition at line 504 of file rrr_helper.hpp.
|
inlinestatic |
Definition at line 561 of file rrr_helper.hpp.
|
inlinestatic |
Definition at line 307 of file rrr_helper.hpp.
|
inlinestatic |
Definition at line 298 of file rrr_helper.hpp.
|
inlinestatic |
Returns the space usage in bits of the binary representation of the number
Definition at line 287 of file rrr_helper.hpp.