sdsl::rrr_helper< n > Class Template Reference

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

#include <rrr_helper.hpp>

List of all members.

Public Types
typedef binomial_coefficients< n >	binomial
	The class containing the binomial coefficients.
typedef binomial::impl::number_type	number_type
	The used number type, e.g. uint64_t, uint128_t,...
typedef binomial::impl::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 .
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 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>
class 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 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.

---

Member Function Documentation

template<uint16_t n>

static uint16_t sdsl::rrr_helper< n >::decode_select	(	uint16_t	k,
		number_type &	nr,
		uint16_t	sel
	)		[inline, static]

Precondition:

k >= sel, sel>0

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

Precondition:

k >= sel, sel>0

---

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

• sdsl/include/sdsl/rrr_helper.hpp