8 #ifndef SDSL_CODER_COMMA_INCLUDED
9 #define SDSL_CODER_COMMA_INCLUDED
46 template <u
int8_t t_w
idth = 2>
50 static_assert(t_width > 1 && t_width <= 32,
"comma coder: Width must be in interval [2,32]");
52 static constexpr
size_t base_fits_in_64(uint32_t base, uint64_t product,
size_t res)
54 return product == 0 ? res : base_fits_in_64(base, product / base, res + 1);
58 static const uint32_t base = (1 << t_width) - 1;
63 static constexpr
size_t codelentbllen = base_fits_in_64(base, 0xFFFFFFFFFFFFFFFFULL, 0);
67 std::array<uint64_t, codelentbllen> codelentbl;
72 for (
size_t i = 0; i < codelentbllen; i++)
75 n = (n << t_width) - n;
82 static void encode_in_base(uint64_t x, uint64_t *& z, uint8_t & offset);
102 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
108 template <
class int_vector>
120 template <
bool t_sumup,
bool t_inc,
class t_iter>
121 static uint64_t
decode(
const uint64_t * data,
const size_type start_idx,
size_type n, t_iter it = (t_iter)
nullptr);
160 template <
class int_vector>
164 template <
class int_vector>
177 template <u
int8_t t_w
idth>
178 typename comma<t_width>::impl comma<t_width>::data;
180 template <u
int8_t t_w
idth>
185 uint8_t numdigits = std::upper_bound(data.codelentbl.begin(), data.codelentbl.end(), w) - data.codelentbl.begin();
188 return (numdigits + 1) * t_width;
191 template <u
int8_t t_w
idth>
196 uint32_t digit = x % base;
198 encode_in_base(x / base, z, offset);
204 template <u
int8_t t_w
idth>
208 encode_in_base(x, z, offset);
213 template <u
int8_t t_w
idth>
214 template <
class int_vector>
222 z_bit_size += encoding_length(*it);
227 z.bit_resize(z_bit_size);
231 uint64_t * z_data = z.m_data;
235 encode(*it, z_data, offset);
242 template <u
int8_t t_w
idth>
243 template <
bool t_sumup,
bool t_inc,
class t_iter>
246 data += (start_idx >> 6);
247 uint8_t offset = start_idx & 0x3F;
255 v = (v << t_width) - v + digit,
259 value = (t_sumup) ? value + v : v;
260 if (t_inc) *(it++) = value;
265 template <u
int8_t t_w
idth>
269 return decode<true, false, int *>(data, start_idx, n);
273 template <u
int8_t t_w
idth>
280 return decode_prefix_sum(data, start_idx, n);
283 template <u
int8_t t_w
idth>
284 template <
class int_vector>
288 if (z.
bit_size() % t_width != 0)
return false;
291 uint64_t numOfDigits = z.
bit_size() / t_width;
293 const uint64_t * z_data = z.
data();
294 uint8_t z_offset = 0;
296 uint32_t digit = base;
301 while (numOfDigits--)
304 if (digit == base) n++;
308 if (digit != base)
return false;
316 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 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.
static uint8_t encoding_length(uint64_t w)
Get the number of bits that are necessary to encode.
static uint64_t decode_prefix_sum(const uint64_t *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 const uint8_t min_codeword_length
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.
static uint64_t * raw_data(int_vector &v)
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
size_type bit_size() const noexcept
The number of bits in the int_vector.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
void shrink_to_fit()
Free unused allocated memory.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
void resize(const size_type size)
Resize the int_vector in terms of elements.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
static SDSL_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 SDSL_CONSTEXPR uint64_t read_int_and_move(const uint64_t *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.