SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
vlc_vector.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef SDSL_VLC_VECTOR
9#define SDSL_VLC_VECTOR
10
11#include <assert.h>
12#include <iosfwd>
13#include <stddef.h>
14#include <stdexcept>
15#include <stdint.h>
16#include <string>
17
18#include <sdsl/bits.hpp>
19#include <sdsl/cereal.hpp>
21#include <sdsl/int_vector.hpp>
23#include <sdsl/io.hpp>
24#include <sdsl/iterators.hpp>
27#include <sdsl/util.hpp>
28
30namespace sdsl
31{
32
33template <uint8_t t_width>
38
39template <>
44
46
52template <class t_coder = coder::elias_delta<>, uint32_t t_dens = 128, uint8_t t_width = 0>
54{
55private:
56 static_assert(t_dens > 1, "vlc_vector: Sampling density must be larger than 1");
57
58public:
59 typedef uint64_t value_type;
62 typedef const value_type reference;
64 typedef value_type const * const_pointer;
65 typedef ptrdiff_t difference_type;
67 typedef t_coder coder;
70
71 static const uint32_t sample_dens = t_dens;
72 bit_vector m_z; // compressed bit stream
73
74private:
75 int_vector_type m_sample_pointer;
76 size_type m_size = 0; // number of elements
77 uint32_t m_sample_dens = t_dens;
78
79 void clear()
80 {
81 m_z.resize(0);
83 m_size = 0;
84 m_sample_pointer.resize(0);
85 m_sample_pointer.shrink_to_fit();
86 }
87
88public:
89 vlc_vector() = default;
90 vlc_vector(vlc_vector const &) = default;
91 vlc_vector(vlc_vector &&) = default;
92 vlc_vector & operator=(vlc_vector const &) = default;
94
96
99 template <class Container>
100 vlc_vector(Container const & c);
101
103 template <uint8_t int_width>
105
108 {
109 return m_size;
110 }
113 {
114 return int_vector<>::max_size() / 2;
115 }
116
118 bool empty() const
119 {
120 return 0 == m_size;
121 }
122
124 const const_iterator begin() const
125 {
126 return const_iterator(this, 0);
127 }
128
130 const const_iterator end() const
131 {
132 return const_iterator(this, this->m_size);
133 }
134
135 bool operator==(vlc_vector const & v) const
136 {
137 return m_size && v.m_size && m_z == v.m_z && m_sample_pointer == v.m_sample_pointer;
138 }
139
140 bool operator!=(vlc_vector const & v) const
141 {
142 return !(*this == v);
143 }
144
147
149 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
150
152 void load(std::istream & in);
153
155 template <typename archive_t>
156 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
157
159 template <typename archive_t>
160 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
161
164
165 uint32_t get_sample_dens() const;
166 void set_sample_dens(const uint32_t sdens);
167};
168
169template <class t_coder, uint32_t t_dens, uint8_t t_width>
171{
172 if (t_dens == 0)
173 return m_sample_dens;
174 else
175 return t_dens;
176}
177
178template <class t_coder, uint32_t t_dens, uint8_t t_width>
180{
181 m_sample_dens = sdens;
182}
183
184template <class t_coder, uint32_t t_dens, uint8_t t_width>
187{
188 assert(i + 1 != 0);
189 assert(i < m_size);
190 size_type idx = i / get_sample_dens();
191 return (t_coder::template decode<false, false, int *>(m_z.data(), m_sample_pointer[idx], i - t_dens * idx + 1)) - 1;
192}
193
194template <class t_coder, uint32_t t_dens, uint8_t t_width>
195template <class Container>
197{
198 clear(); // clear bit_vectors
199
200 if (c.empty()) // if c is empty there is nothing to do...
201 return;
202 size_type samples = 0, z_size = 0;
203 // (1) Calculate size of z
204 for (size_type i = 0; i < c.size(); ++i)
205 {
206 if (c[i] + 1 < 1)
207 {
208 throw std::logic_error("vlc_vector cannot decode values smaller than 1!");
209 }
210 z_size += t_coder::encoding_length(c[i] + 1);
211 }
212 samples = (c.size() + get_sample_dens() - 1) / get_sample_dens();
213 // (2) Write z
214 m_sample_pointer = int_vector<>(samples + 1, 0, bits::hi(z_size + 1) + 1);
215
216 m_z.bit_resize(z_size);
217 z_size = 0;
218 uint64_t * z_data = t_coder::raw_data(m_z);
219 uint8_t offset = 0;
220 size_type no_sample = 0;
221 for (size_type i = 0, sample_cnt = 0; i < c.size(); ++i, --no_sample)
222 {
223 if (!no_sample)
224 { // add a sample pointer
225 no_sample = get_sample_dens();
226 m_sample_pointer[sample_cnt++] = z_size;
227 }
228 t_coder::encode(c[i] + 1, z_data, offset);
229 z_size += t_coder::encoding_length(c[i] + 1);
230 }
231 m_size = c.size();
232}
233
234template <class t_coder, uint32_t t_dens, uint8_t t_width>
235template <uint8_t int_width>
237{
238 clear(); // clear bit_vectors
239 size_type n = v_buf.size();
240 if (n == 0) // if c is empty there is nothing to do...
241 return;
242 size_type samples = 0, z_size = 0;
243 // (1) Calculate size of z
244 for (size_type i = 0; i < n; ++i)
245 {
246 size_type x = v_buf[i] + 1;
247 if (x < 1)
248 {
249 throw std::logic_error("vlc_vector cannot decode values smaller than 1!");
250 }
251 z_size += t_coder::encoding_length(x);
252 }
253 samples = (n + get_sample_dens() - 1) / get_sample_dens();
254 // (2) Write z
255
256 m_sample_pointer = int_vector<>(samples + 1, 0, bits::hi(z_size + 1) + 1); // add 1 for last entry
257
258 // (b) Initilize bit_vector for encoded data
259 m_z.bit_resize(z_size);
260 z_size = 0;
261 uint64_t * z_data = t_coder::raw_data(m_z);
262 uint8_t offset = 0;
263
264 // (c) Write sample values and deltas
265 size_type no_sample = 0;
266 for (size_type i = 0, sample_cnt = 0; i < n; ++i, --no_sample)
267 {
268 if (!no_sample)
269 { // add a sample pointer
270 no_sample = get_sample_dens();
271 m_sample_pointer[sample_cnt++] = z_size;
272 }
273 size_type x = v_buf[i] + 1;
274 t_coder::encode(x, z_data, offset); // write encoded values
275 z_size += t_coder::encoding_length(x);
276 }
277 m_size = n;
278}
279
280template <class t_coder, uint32_t t_dens, uint8_t t_width>
282vlc_vector<t_coder, t_dens, t_width>::serialize(std::ostream & out, structure_tree_node * v, std::string name) const
283{
284 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
285 size_type written_bytes = 0;
286 written_bytes += write_member(m_size, out, child, "m_size");
287 written_bytes += m_z.serialize(out, child, "m_z");
288 written_bytes += m_sample_pointer.serialize(out, child, "m_sample_pointer");
289 structure_tree::add_size(child, written_bytes);
290 return written_bytes;
291}
292
293template <class t_coder, uint32_t t_dens, uint8_t t_width>
295{
296 read_member(m_size, in);
297 m_z.load(in);
298 m_sample_pointer.load(in);
299}
300
301template <class t_coder, uint32_t t_dens, uint8_t t_width>
302template <typename archive_t>
304{
305 ar(CEREAL_NVP(m_size));
306 ar(CEREAL_NVP(m_z));
307 ar(CEREAL_NVP(m_sample_pointer));
308}
309
310template <class t_coder, uint32_t t_dens, uint8_t t_width>
311template <typename archive_t>
313{
314 ar(CEREAL_NVP(m_size));
315 ar(CEREAL_NVP(m_z));
316 ar(CEREAL_NVP(m_sample_pointer));
317}
318
319} // end namespace sdsl
320#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
#define CEREAL_LOAD_FUNCTION_NAME
Definition cereal.hpp:34
#define CEREAL_SAVE_FUNCTION_NAME
Definition cereal.hpp:35
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
void shrink_to_fit()
Free unused allocated memory.
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.
Definition iterators.hpp:24
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)
A generic immutable space-saving vector class for unsigned integers.
static const uint32_t sample_dens
const const_iterator end() const
Iterator that points to the position after the last element of the vlc_vector.
vlc_vector & operator=(vlc_vector &&)=default
random_access_const_iterator< vlc_vector > iterator
const const_iterator begin() const
Iterator that points to the first element of the vlc_vector.
vlc_vector(vlc_vector &&)=default
bool operator==(vlc_vector const &v) const
vlc_vector_trait< t_width >::int_vector_type int_vector_type
vlc_vector & operator=(vlc_vector const &)=default
size_type size() const
The number of elements in the vlc_vector.
ptrdiff_t difference_type
vlc_vector()=default
void load(std::istream &in)
Load the vlc_vector from a stream.
value_type sample(const size_type i) const
Returns the ith sample of vlc_vector.
uint32_t get_sample_dens() const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
void set_sample_dens(const uint32_t sdens)
const value_type reference
iterator const_iterator
const value_type const_reference
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the vlc_vector to a stream.
int_vector ::size_type size_type
bool operator!=(vlc_vector const &v) const
bool empty() const
Returns if the vlc_vector is empty.
vlc_vector(vlc_vector const &)=default
value_type const * const_pointer
uint64_t value_type
static size_type max_size()
Return the largest size that this container can ever have.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
value_type operator[](size_type i) const
[]-operator
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.
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="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
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.
Definition bits.hpp:653
int_vector< 32 > 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.