19template <u
int8_t t_w
idth>
48template <
class t_coder = coder::elias_delta<>, u
int32_t t_dens = 128, u
int8_t t_w
idth = 0>
52 static_assert(t_dens > 1,
"enc_vector: sample density must be larger than `1`");
79 m_sample_vals_and_pointer.
resize(0);
93 template <
class Container>
100 template <u
int8_t
int_w
idth>
113 bool empty()
const {
return 0 == m_size; }
123 return m_size && v.m_size &&
m_z == v.
m_z && m_sample_vals_and_pointer == v.m_sample_vals_and_pointer;
140 void load(std::istream & in);
142 template <
typename archive_t>
145 template <
typename archive_t>
163 if (i * t_dens + t_dens - 1 <
size())
165 t_coder::template decode<true, true>(
m_z.
data(), m_sample_vals_and_pointer[(i << 1) + 1], t_dens - 1, it);
169 assert(i * t_dens <
size());
170 t_coder::template decode<true, true>(
m_z.
data(),
171 m_sample_vals_and_pointer[(i << 1) + 1],
172 size() - i * t_dens - 1,
178template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
185 return m_sample_vals_and_pointer[idx << 1] +
186 t_coder::decode_prefix_sum(m_z.data(), m_sample_vals_and_pointer[(idx << 1) + 1], i - t_dens * idx);
189template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
193 assert(i * get_sample_dens() + 1 != 0);
194 assert(i * get_sample_dens() < m_size);
195 return m_sample_vals_and_pointer[i << 1];
198template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
199template <
class Container>
207 typename Container::const_iterator it = c.begin(), end = c.end();
208 typename Container::value_type v1 = *it, v2, max_sample_value = 0, x;
212 for (
size_type i = 0, no_sample = 0; it != end; ++it, ++i, --no_sample)
217 no_sample = get_sample_dens();
218 if (max_sample_value < v2) max_sample_value = v2;
223 z_size += t_coder::encoding_length(v2 - v1);
229 if (max_sample_value > z_size + 1)
230 m_sample_vals_and_pointer.width(
bits::hi(max_sample_value) + 1);
232 m_sample_vals_and_pointer.width(
bits::hi(z_size + 1) + 1);
233 m_sample_vals_and_pointer.resize(2 * samples + 2);
238 for (it = c.begin(); it != end; ++it, --no_sample)
243 no_sample = get_sample_dens();
252 z_size += t_coder::encoding_length(x);
262 uint64_t * z_data = t_coder::raw_data(m_z);
265 for (it = c.begin(); it != end; ++it, --no_sample)
270 no_sample = get_sample_dens();
274 t_coder::encode(v2 - v1, z_data, offset);
282template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
283template <u
int8_t
int_w
idth>
291 value_type v1 = 0, v2 = 0, max_sample_value = 0;
295 for (
size_type i = 0, no_sample = 0; i < n; ++i, --no_sample)
301 if (max_sample_value < v2) max_sample_value = v2;
306 z_size += t_coder::encoding_length(v2 - v1);
313 if (max_sample_value > z_size + 1)
314 m_sample_vals_and_pointer.width(
bits::hi(max_sample_value) + 1);
316 m_sample_vals_and_pointer.width(
bits::hi(z_size + 1) + 1);
317 m_sample_vals_and_pointer.resize(2 * samples + 2);
322 uint64_t * z_data = t_coder::raw_data(m_z);
327 for (
size_type i = 0, j = 0, no_sample = 0; i < n; ++i, --no_sample)
333 m_sample_vals_and_pointer[j++] = v2;
334 m_sample_vals_and_pointer[j++] = z_size;
338 z_size += t_coder::encoding_length(v2 - v1);
339 t_coder::encode(v2 - v1, z_data, offset);
346template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
349 std::string name)
const
353 written_bytes +=
write_member(m_size, out, child,
"size");
354 written_bytes += m_z.serialize(out, child,
"encoded deltas");
355 written_bytes += m_sample_vals_and_pointer.serialize(out, child,
"samples_and_pointers");
357 return written_bytes;
360template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
365 m_sample_vals_and_pointer.load(in);
368template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
369template <
typename archive_t>
377template <
class t_coder, u
int32_t t_dens, u
int8_t t_w
idth>
378template <
typename archive_t>
A generic immutable space-saving vector class for unsigned integers.
enc_vector & operator=(enc_vector &&)=default
enc_vector & operator=(const enc_vector &)=default
const value_type const_reference
uint32_t get_sample_dens() const
const value_type * const_pointer
random_access_const_iterator< enc_vector > iterator
enc_vector_trait< t_width >::int_vector_type int_vector_type
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
bool operator==(const enc_vector &v) const
value_type operator[](size_type i) const
operator[]
const value_type reference
bool operator!=(const enc_vector &v) const
value_type sample(const size_type i) const
Returns the i-th sample of enc_vector.
enc_vector(const enc_vector &)=default
int_vector ::size_type size_type
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.
~enc_vector()
Default Destructor.
static const uint32_t sample_dens
size_type size() const
The number of elements in the enc_vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
ptrdiff_t difference_type
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.
void shrink_to_fit()
Free unused allocated memory.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
static size_type max_size() noexcept
Maximum size of the int_vector.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Generic iterator for a random access container.
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
coder.hpp contains the coder namespace and includes the header files of sdsl::coder::fibonacci,...
int_vector.hpp contains the sdsl::int_vector class.
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(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
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