sdsl::coder::fibonacci Class Reference

A class to encode and decode between Fibonacci and binary code. More...

#include <fibonacci_coder.hpp>

List of all members.

Public Types
typedef uint64_t	size_type
Static Public Member Functions
static uint8_t	encoding_length (uint64_t w)
	Get the number of bits that are necessary to encode the value w in fibonacci code.
template<bool sumup, bool increment, class Iterator >
static uint64_t	decode (const uint64_t *data, const size_type start_idx, size_type n, Iterator it=(Iterator) NULL)
	Decode n Fibonacci encoded bits beginning at start_idx in the bitstring "data".
template<bool sumup, bool increment, class Iterator >
static uint64_t	decode1 (const uint64_t *data, const size_type start_idx, size_type n, Iterator it=(Iterator) NULL)
static uint64_t	decode_prefix_sum (const uint64_t *data, const size_type start_idx, size_type n)
	Decode n Fibonacci encoded integers beginning at start_idx in the bitstring "data" and return the sum of these values.
static uint64_t	decode_prefix_sum (const uint64_t *data, const size_type start_idx, const size_type end_idx, size_type n)
	Deocde n Fibonacci encoded integers beginning at start_idx and ending at end_idx (exclusive) in the bitstring "data" and return the sum of these values.
template<class int_vector1 , class int_vector2 >
static bool	encode (const int_vector1 &v, int_vector2 &z)
template<class int_vector >
static uint64_t *	raw_data (int_vector &v)
static void	encode (uint64_t x, uint64_t *&z, uint8_t &offset)
	Encode one positive integer x to an int_vector at bit position start_idx.
template<class int_vector1 , class int_vector2 >
static bool	decode (const int_vector1 &z, int_vector2 &v)
Static Public Attributes
static const uint64_t	Fib2bin_0_95 [(1<< 12)*8]
	Array contains precomputed values for the decoding of a number in the fibonacci system.
static const uint8_t	Fib2binShift [(1<< 13)]
	Array contains precomputed values for the decoding of a number in the fibonacci system.
static const uint16_t	Fib2bin_0_16_greedy [1<< 16]
	Array contains precomputed values for the deconding of a prefix sum of fibonacci encoded integers.
static const uint8_t	min_codeword_length = 2

---

Detailed Description

A class to encode and decode between Fibonacci and binary code.

---

Member Function Documentation

static uint64_t sdsl::coder::fibonacci::decode_prefix_sum	(	const uint64_t *	data,
		const size_type	start_idx,
		size_type	n
	)		[static]

Decode n Fibonacci encoded integers beginning at start_idx in the bitstring "data" and return the sum of these values.

Parameters:

data	Pointer to the beginning of the Fibonacci encoded bitstring.
start_idx	Index of the first bit to endcode the values from.
n	Number of values to decode from the bitstring. Attention: There have to be at least n encoded values in the bitstring.

static uint64_t sdsl::coder::fibonacci::decode_prefix_sum	(	const uint64_t *	data,
		const size_type	start_idx,
		const size_type	end_idx,
		size_type	n
	)		[static]

Deocde n Fibonacci encoded integers beginning at start_idx and ending at end_idx (exclusive) in the bitstring "data" and return the sum of these values.

See also:

decode_prefix_sum

void sdsl::coder::fibonacci::encode	(	uint64_t	x,
		uint64_t *&	z,
		uint8_t &	offset
	)		[inline, static]

Encode one positive integer x to an int_vector at bit position start_idx.

Parameters:

x	Positive integer to encode.
z	Raw data of vector to write the encoded form of x.
offset	Start offset to write the encoded form of x in z. .

uint8_t sdsl::coder::fibonacci::encoding_length

(

uint64_t

w

)

[inline, static]

Get the number of bits that are necessary to encode the value w in fibonacci code.

Parameters:

w	64bit integer to get the length of its fibonacci encoding. Inclusive the terminating 1 of the code.

---

Member Data Documentation

const uint16_t sdsl::coder::fibonacci::Fib2bin_0_16_greedy[1<< 16] [static]

Array contains precomputed values for the deconding of a prefix sum of fibonacci encoded integers.

The 5 most significant bits contain information about how far to shift to get to the next encoded integer. If this 5 bits equal zero, there is no whole fibonacci number encoded in the 16 bits...

const uint8_t sdsl::coder::fibonacci::Fib2binShift[(1<< 13)] [static]

Array contains precomputed values for the decoding of a number in the fibonacci system.

Entry x equals 0 if no 11 substring is in the binary representation of x otherwise Fib2binShift[x] contains the position (1..13) of the left 1 in the rightmost 11 substring in x. E.g. Fib2binShift[3] = 2 and Fib2binShift[6] = 3.

---

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

• sdsl/include/sdsl/fibonacci_coder.hpp