SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::coder::comma< uint8_t > 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.
 
static void encode (uint64_t x, uint64_t *&z, uint8_t &offset)
 Encode one positive integer x to an int_vector.
 
template<class int_vector >
static bool encode (int_vector const &v, int_vector &z)
 Encode integers contained in vector v into vector z.
 
template<bool t_sumup, bool t_inc, class t_iter >
static uint64_t decode (uint64_t const *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
 Decode n comma encoded values beginning at start_idx.
 
static uint64_t decode_prefix_sum (uint64_t const *data, const size_type start_idx, size_type n)
 Decode n comma gamma encoded integers.
 
static uint64_t decode_prefix_sum (uint64_t const *data, const size_type start_idx, const size_type end_idx, size_type n)
 Decode n comma gamma encoded integers.
 
template<class int_vector >
static bool decode (int_vector const &z, int_vector &v)
 Decode vector z containing comma encoded integers.
 
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>
class sdsl::coder::comma< uint8_t >

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 68 of file int_vector.hpp.

Member Typedef Documentation

◆ size_type

template<uint8_t >
typedef uint64_t sdsl::coder::comma< uint8_t >::size_type

Definition at line 86 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 ( int_vector const & 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 ( uint64_t const * 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 243 of file coder_comma.hpp.

◆ decode_prefix_sum() [1/2]

template<uint8_t >
static uint64_t sdsl::coder::comma< uint8_t >::decode_prefix_sum ( uint64_t const * 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 ( uint64_t const * 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 ( int_vector const & v,
int_vector & z )
static

Encode integers contained in vector v into vector z.

Definition at line 214 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 204 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 180 of file coder_comma.hpp.

◆ raw_data()

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

Definition at line 164 of file coder_comma.hpp.

Member Data Documentation

◆ min_codeword_length

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

Definition at line 87 of file coder_comma.hpp.


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