8#ifndef SDSL_CODER_COMMA_INCLUDED
9#define SDSL_CODER_COMMA_INCLUDED
47template <u
int8_t t_w
idth = 2>
51 static_assert(t_width > 1 && t_width <= 32,
"comma coder: Width must be in interval [2,32]");
53 static constexpr size_t base_fits_in_64(uint32_t base, uint64_t product,
size_t res)
55 return product == 0 ? res : base_fits_in_64(base, product / base, res + 1);
59 static const uint32_t base = (1 << t_width) - 1;
64 static constexpr size_t codelentbllen = base_fits_in_64(base, 0xFFFFFFFFFFFFFFFFULL, 0);
68 std::array<uint64_t, codelentbllen> codelentbl;
73 for (
size_t i = 0; i < codelentbllen; i++)
76 n = (n << t_width) - n;
83 static void encode_in_base(uint64_t x, uint64_t *& z, uint8_t & offset);
103 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
109 template <
class int_vector>
121 template <
bool t_sumup,
bool t_inc,
class t_iter>
122 static uint64_t
decode(uint64_t
const * data,
const size_type start_idx,
size_type n, t_iter it = (t_iter)
nullptr);
159 template <
class int_vector>
163 template <
class int_vector>
176template <u
int8_t t_w
idth>
177typename comma<t_width>::impl comma<t_width>::data;
179template <u
int8_t t_w
idth>
184 uint8_t numdigits = std::upper_bound(data.codelentbl.begin(), data.codelentbl.end(), w) - data.codelentbl.begin();
187 return (numdigits + 1) * t_width;
190template <u
int8_t t_w
idth>
195 uint32_t digit = x % base;
197 encode_in_base(x / base, z, offset);
203template <u
int8_t t_w
idth>
207 encode_in_base(x, z, offset);
212template <u
int8_t t_w
idth>
213template <
class int_vector>
221 z_bit_size += encoding_length(*it);
226 z.bit_resize(z_bit_size);
230 uint64_t * z_data = z.m_data;
234 encode(*it, z_data, offset);
241template <u
int8_t t_w
idth>
242template <
bool t_sumup,
bool t_inc,
class t_iter>
245 data += (start_idx >> 6);
246 uint8_t offset = start_idx & 0x3F;
254 v = (v << t_width) - v + digit,
258 value = (t_sumup) ? value + v : v;
265template <u
int8_t t_w
idth>
269 return decode<true, false, int *>(data, start_idx, n);
273template <u
int8_t t_w
idth>
275 const size_type start_idx,
280 return decode_prefix_sum(data, start_idx, n);
283template <u
int8_t t_w
idth>
284template <
class int_vector>
292 uint64_t numOfDigits = z.
bit_size() / t_width;
294 uint64_t
const * z_data = z.
data();
295 uint8_t z_offset = 0;
297 uint32_t digit = base;
302 while (numOfDigits--)
319 decode<false, true>(z.
data(), 0, n, v.
begin());
bits.hpp contains the sdsl::bits class.
A class to encode and decode between comma code and binary code.
static uint64_t * raw_data(int_vector &v)
static uint8_t encoding_length(uint64_t w)
Get the number of bits that are necessary to encode.
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 void encode(uint64_t x, uint64_t *&z, uint8_t &offset)
Encode one positive integer x to an int_vector.
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.
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 const uint8_t min_codeword_length
A generic vector class for integers of width .
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
int_vector_size_type size_type
void shrink_to_fit()
Free unused allocated memory.
void resize(const size_type size)
Resize the int_vector in terms of elements.
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
size_type bit_size() const noexcept
The number of bits in the int_vector.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Namespace for the succinct data structure library.
static constexpr void write_int_and_move(uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
Writes value x to an bit position in an array and moves the bit-pointer.
static constexpr uint64_t read_int_and_move(uint64_t const *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.