SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::coder::comma< t_width > Class Template Reference

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

#include <coder_comma.hpp>

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. More...
 
static void encode (uint64_t x, uint64_t *&z, uint8_t &offset)
 Encode one positive integer x to an int_vector. More...
 
template<class int_vector >
static bool encode (const int_vector &v, int_vector &z)
 Encode integers contained in vector v into vector z. 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 comma encoded values beginning at start_idx. More...
 
static uint64_t decode_prefix_sum (const uint64_t *data, const size_type start_idx, size_type n)
 Decode n comma gamma encoded integers. More...
 
static uint64_t decode_prefix_sum (const uint64_t *data, const size_type start_idx, const size_type end_idx, size_type n)
 Decode n comma gamma encoded integers. More...
 
template<class int_vector >
static bool decode (const int_vector &z, int_vector &v)
 Decode vector z containing comma encoded integers. More...
 
template<class int_vector >
static uint64_t * raw_data (int_vector &v)
 

Static Public Attributes

static const uint8_t min_codeword_length = t_width
 

Detailed Description

template<uint8_t t_width = 2>
class sdsl::coder::comma< t_width >

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

Author
Uwe Baier

Comma coding works as the following: First of all, comma coding needs a parameter t_width which indicates how big a encoded digit will be (in bits), let's say t_width = 2. By use of t_width one can calculate a base for encoding, in detail this means base = 2^t_width - 1 now, given any number it is encoded as the follows: The number gets displayed in the calculated base, and each digit of the number is saved with t_width bits. To indicate the end of the number, a termination digit is used (namely this is the value base). Example: t_width = 2 => base = 2^2 - 1 = 3 Value to be encoded: 15 15 (base 10) = 120 (base 3) Encoded value: 120 (plus termination digit) = 01 10 00 11 in binary (last digit is termination digit)

Template Parameters
t_widthWidth of one digit used in comma code

Definition at line 47 of file coder_comma.hpp.

Member Typedef Documentation

◆ size_type

template<uint8_t t_width = 2>
typedef uint64_t sdsl::coder::comma< t_width >::size_type

Definition at line 85 of file coder_comma.hpp.

Member Function Documentation

◆ decode() [1/2]

template<uint8_t t_width>
template<class int_vector >
bool sdsl::coder::comma< t_width >::decode ( const int_vector z,
int_vector v 
)
static

Decode vector z containing comma encoded integers.

Parameters
zvector that contains encoded integers.
vvector to store the decoded integers

Definition at line 285 of file coder_comma.hpp.

◆ decode() [2/2]

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

Decode n comma encoded values beginning at start_idx.

Definition at line 244 of file coder_comma.hpp.

◆ decode_prefix_sum() [1/2]

template<uint8_t t_width = 2>
static uint64_t sdsl::coder::comma< t_width >::decode_prefix_sum ( const uint64_t *  data,
const size_type  start_idx,
const size_type  end_idx,
size_type  n 
)
static

Decode n comma gamma encoded integers.

Parameters
dataPointer to the beginning of the comma encoded bitstring.
start_idxIndex of the first bit to encode the values from.
end_idxIndex of the last 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.

◆ decode_prefix_sum() [2/2]

template<uint8_t t_width>
uint64_t sdsl::coder::comma< t_width >::decode_prefix_sum ( const uint64_t *  data,
const size_type  start_idx,
size_type  n 
)
static

Decode n comma gamma encoded integers.

Parameters
dataPointer to the beginning of the comma 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 266 of file coder_comma.hpp.

◆ encode() [1/2]

template<uint8_t t_width>
template<class int_vector >
bool sdsl::coder::comma< t_width >::encode ( const int_vector v,
int_vector z 
)
static

Encode integers contained in vector v into vector z.

Definition at line 215 of file coder_comma.hpp.

◆ encode() [2/2]

template<uint8_t t_width>
void sdsl::coder::comma< t_width >::encode ( uint64_t  x,
uint64_t *&  z,
uint8_t &  offset 
)
inlinestatic

Encode one positive integer x to an int_vector.

Definition at line 205 of file coder_comma.hpp.

◆ encoding_length()

template<uint8_t t_width>
uint8_t sdsl::coder::comma< t_width >::encoding_length ( uint64_t  w)
inlinestatic

Get the number of bits that are necessary to encode.

Parameters
w64bit int to get the length of its comma encoding.

Definition at line 181 of file coder_comma.hpp.

◆ raw_data()

template<uint8_t t_width = 2>
template<class int_vector >
static uint64_t * sdsl::coder::comma< t_width >::raw_data ( int_vector v)
inlinestatic

Definition at line 165 of file coder_comma.hpp.

Member Data Documentation

◆ min_codeword_length

template<uint8_t t_width = 2>
const uint8_t sdsl::coder::comma< t_width >::min_codeword_length = t_width
static

Definition at line 86 of file coder_comma.hpp.


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