32template <u
int8_t t_w
idth>
61template <
class t_coder = coder::elias_delta<>, u
int32_t t_dens = 128, u
int8_t t_w
idth = 0>
65 static_assert(t_dens > 1,
"enc_vector: sample density must be larger than `1`");
93 m_sample_vals_and_pointer.
resize(0);
107 template <
class Container>
114 template <u
int8_t
int_w
idth>
153 return m_size && v.m_size &&
m_z == v.
m_z && m_sample_vals_and_pointer == v.m_sample_vals_and_pointer;
158 return !(*
this == v);
173 void load(std::istream & in);
175 template <
typename archive_t>
178 template <
typename archive_t>
199 if (i * t_dens + t_dens - 1 <
size())
201 t_coder::template decode<true, true>(
m_z.
data(), m_sample_vals_and_pointer[(i << 1) + 1], t_dens - 1, it);
205 assert(i * t_dens <
size());
206 t_coder::template decode<true, true>(
m_z.
data(),
207 m_sample_vals_and_pointer[(i << 1) + 1],
208 size() - i * t_dens - 1,
214template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
221 return m_sample_vals_and_pointer[idx << 1]
222 + t_coder::decode_prefix_sum(m_z.data(), m_sample_vals_and_pointer[(idx << 1) + 1], i - t_dens * idx);
225template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
229 assert(i * get_sample_dens() + 1 != 0);
230 assert(i * get_sample_dens() < m_size);
231 return m_sample_vals_and_pointer[i << 1];
234template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
235template <
class Container>
243 typename Container::const_iterator it = c.begin(), end = c.end();
244 typename Container::value_type v1 = *it, v2, max_sample_value = 0, x;
248 for (
size_type i = 0, no_sample = 0; it != end; ++it, ++i, --no_sample)
253 no_sample = get_sample_dens();
254 if (max_sample_value < v2)
255 max_sample_value = v2;
260 z_size += t_coder::encoding_length(v2 - v1);
266 if (max_sample_value > z_size + 1)
267 m_sample_vals_and_pointer.width(
bits::hi(max_sample_value) + 1);
269 m_sample_vals_and_pointer.width(
bits::hi(z_size + 1) + 1);
270 m_sample_vals_and_pointer.resize(2 * samples + 2);
275 for (it = c.begin(); it != end; ++it, --no_sample)
280 no_sample = get_sample_dens();
289 z_size += t_coder::encoding_length(x);
299 uint64_t * z_data = t_coder::raw_data(m_z);
302 for (it = c.begin(); it != end; ++it, --no_sample)
307 no_sample = get_sample_dens();
311 t_coder::encode(v2 - v1, z_data, offset);
319template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
320template <u
int8_t
int_w
idth>
328 value_type v1 = 0, v2 = 0, max_sample_value = 0;
332 for (
size_type i = 0, no_sample = 0; i < n; ++i, --no_sample)
338 if (max_sample_value < v2)
339 max_sample_value = v2;
344 z_size += t_coder::encoding_length(v2 - v1);
351 if (max_sample_value > z_size + 1)
352 m_sample_vals_and_pointer.width(
bits::hi(max_sample_value) + 1);
354 m_sample_vals_and_pointer.width(
bits::hi(z_size + 1) + 1);
355 m_sample_vals_and_pointer.resize(2 * samples + 2);
360 uint64_t * z_data = t_coder::raw_data(m_z);
365 for (
size_type i = 0, j = 0, no_sample = 0; i < n; ++i, --no_sample)
371 m_sample_vals_and_pointer[j++] = v2;
372 m_sample_vals_and_pointer[j++] = z_size;
376 z_size += t_coder::encoding_length(v2 - v1);
377 t_coder::encode(v2 - v1, z_data, offset);
384template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
390 written_bytes +=
write_member(m_size, out, child,
"size");
391 written_bytes += m_z.serialize(out, child,
"encoded deltas");
392 written_bytes += m_sample_vals_and_pointer.serialize(out, child,
"samples_and_pointers");
394 return written_bytes;
397template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
402 m_sample_vals_and_pointer.load(in);
405template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
406template <
typename archive_t>
414template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
415template <
typename archive_t>
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
A generic immutable space-saving vector class for unsigned integers.
enc_vector(enc_vector const &)=default
enc_vector & operator=(enc_vector &&)=default
const value_type const_reference
uint32_t get_sample_dens() const
const const_iterator begin() const
Iterator that points to the first element of the enc_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize the enc_vector to a stream.
void load(std::istream &in)
Load the enc_vector from a stream.
static size_type max_size()
Return the largest size that this container can ever have.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
enc_vector_trait< t_width >::int_vector_type int_vector_type
value_type operator[](size_type i) const
operator[]
value_type sample(const size_type i) const
Returns the i-th sample of enc_vector.
ptrdiff_t difference_type
const value_type reference
void get_inter_sampled_values(const size_type i, uint64_t *it) const
const const_iterator end() const
Iterator that points to the position after the last element of the enc_vector.
value_type const * const_pointer
~enc_vector()
Default Destructor.
static const uint32_t sample_dens
random_access_const_iterator< enc_vector > iterator
bool operator==(enc_vector const &v) const
size_type size() const
The number of elements in the enc_vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
enc_vector & operator=(enc_vector const &)=default
int_vector ::size_type size_type
bool operator!=(enc_vector const &v) const
enc_vector(enc_vector &&)=default
bool empty() const
Returns if the enc_vector is empty.
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
int_vector_size_type size_type
static size_type max_size() noexcept
Maximum size of the int_vector.
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.
Generic iterator for a random access container.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
coder_elias_delta.hpp contains the class sdsl::coder::elias_delta
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Namespace for the succinct data structure library.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
Contains declarations and definitions of data structure concepts.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
int_vector< 32 > int_vector_type
int_vector< 64 > int_vector_type
int_vector< 0 > int_vector_type
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.