SDSL 3.0.1
Succinct Data Structure Library
sdsl::coder::fibonacci< T > Class Template Reference

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

#include <coder_fibonacci.hpp>

Classes

struct  impl
 

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. More...
 
template<bool t_sumup, bool t_inc, class t_iter >
static uint64_t decode (const uint64_t *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
 Decode n Fibonacci encoded bits beginning at start_idx in the bitstring "data". More...
 
template<bool t_sumup, bool t_inc, class t_iter >
static uint64_t decode1 (const uint64_t *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
 
static uint64_t decode_prefix_sum (const uint64_t *d, 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. More...
 
static uint64_t decode_prefix_sum (const uint64_t *d, const size_type start_idx, const size_type end_idx, size_type n)
 Decode 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. More...
 
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. More...
 
template<class int_vector1 , class int_vector2 >
static bool decode (const int_vector1 &z, int_vector2 &v)
 

Static Public Attributes

static struct sdsl::coder::fibonacci::impl data
 
static const uint8_t min_codeword_length = 2
 

Detailed Description

template<typename T = void>
class sdsl::coder::fibonacci< T >

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

Definition at line 21 of file coder_fibonacci.hpp.

Member Typedef Documentation

◆ size_type

template<typename T = void>
typedef uint64_t sdsl::coder::fibonacci< T >::size_type

Definition at line 101 of file coder_fibonacci.hpp.

Member Function Documentation

◆ decode() [1/2]

template<typename T >
template<class int_vector1 , class int_vector2 >
bool sdsl::coder::fibonacci< T >::decode ( const int_vector1 &  z,
int_vector2 &  v 
)
inlinestatic

Definition at line 352 of file coder_fibonacci.hpp.

◆ decode() [2/2]

template<typename T >
template<bool t_sumup, bool t_inc, class t_iter >
uint64_t sdsl::coder::fibonacci< T >::decode ( const uint64_t *  data,
const size_type  start_idx,
size_type  n,
t_iter  it = (t_iter) nullptr 
)
inlinestatic

Decode n Fibonacci encoded bits beginning at start_idx in the bitstring "data".

Definition at line 384 of file coder_fibonacci.hpp.

◆ decode1()

template<typename T >
template<bool t_sumup, bool t_inc, class t_iter >
uint64_t sdsl::coder::fibonacci< T >::decode1 ( const uint64_t *  data,
const size_type  start_idx,
size_type  n,
t_iter  it = (t_iter) nullptr 
)
inlinestatic

Definition at line 432 of file coder_fibonacci.hpp.

◆ decode_prefix_sum() [1/2]

template<typename T = void>
static uint64_t sdsl::coder::fibonacci< T >::decode_prefix_sum ( const uint64_t *  d,
const size_type  start_idx,
const size_type  end_idx,
size_type  n 
)
static

Decode 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

◆ decode_prefix_sum() [2/2]

template<typename T >
uint64_t sdsl::coder::fibonacci< T >::decode_prefix_sum ( const uint64_t *  d,
const size_type  start_idx,
size_type  n 
)
inlinestatic

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

Parameters
dataPointer to the beginning of the Fibonacci encoded bitstring.
start_idxIndex of the first bit to encode the values from.
nNumber of values to decode from the bitstring. Attention: There have to be at least n encoded values in the bitstring.

Definition at line 486 of file coder_fibonacci.hpp.

◆ encode() [1/2]

template<typename T >
template<class int_vector1 , class int_vector2 >
bool sdsl::coder::fibonacci< T >::encode ( const int_vector1 &  v,
int_vector2 &  z 
)
inlinestatic

Definition at line 174 of file coder_fibonacci.hpp.

◆ encode() [2/2]

template<typename T >
void sdsl::coder::fibonacci< T >::encode ( uint64_t  x,
uint64_t *&  z,
uint8_t &  offset 
)
inlinestatic

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

Parameters
xPositive integer to encode.
zRaw data of vector to write the encoded form of x.
offsetStart offset to write the encoded form of x in z. $0\leq offset< 64$.

Definition at line 276 of file coder_fibonacci.hpp.

◆ encoding_length()

template<typename T >
uint8_t sdsl::coder::fibonacci< T >::encoding_length ( uint64_t  w)
inlinestatic

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

Parameters
w64bit integer to get the length of its fibonacci encoding. Inclusive the terminating 1 of the code.

Definition at line 162 of file coder_fibonacci.hpp.

◆ raw_data()

template<typename T = void>
template<class int_vector >
static uint64_t * sdsl::coder::fibonacci< T >::raw_data ( int_vector v)
inlinestatic

Definition at line 145 of file coder_fibonacci.hpp.

Member Data Documentation

◆ data

template<typename T >
fibonacci< T >::impl sdsl::coder::fibonacci< T >::data
static

Definition at line 604 of file coder_fibonacci.hpp.

◆ min_codeword_length

template<typename T = void>
const uint8_t sdsl::coder::fibonacci< T >::min_codeword_length = 2
static

Definition at line 103 of file coder_fibonacci.hpp.


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