SDSL 3.0.1
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
12#include <sdsl/int_vector.hpp>
13#include <sdsl/iterators.hpp>
14
16namespace sdsl
17{
18
19template <uint8_t t_width>
21{
23};
24
25template <>
27{
29};
30
32
38template <class t_coder = coder::elias_delta<>, uint32_t t_dens = 128, uint8_t t_width = 0>
40{
41 private:
42 static_assert(t_dens > 1, "vlc_vector: Sampling density must be larger than 1");
43
44 public:
45 typedef uint64_t value_type;
48 typedef const value_type reference;
50 typedef const value_type * const_pointer;
51 typedef ptrdiff_t difference_type;
53 typedef t_coder coder;
56
57 static const uint32_t sample_dens = t_dens;
58 bit_vector m_z; // compressed bit stream
59 private:
60 int_vector_type m_sample_pointer;
61 size_type m_size = 0; // number of elements
62 uint32_t m_sample_dens = t_dens;
63
64 void clear()
65 {
66 m_z.resize(0);
68 m_size = 0;
69 m_sample_pointer.resize(0);
70 m_sample_pointer.shrink_to_fit();
71 }
72
73 public:
74 vlc_vector() = default;
75 vlc_vector(const vlc_vector &) = default;
76 vlc_vector(vlc_vector &&) = default;
77 vlc_vector & operator=(const vlc_vector &) = default;
79
81
84 template <class Container>
85 vlc_vector(const Container & c);
86
88 template <uint8_t int_width>
90
92 size_type size() const { return m_size; }
94 static size_type max_size() { return int_vector<>::max_size() / 2; }
95
97 bool empty() const { return 0 == m_size; }
98
100 const const_iterator begin() const { return const_iterator(this, 0); }
101
103 const const_iterator end() const { return const_iterator(this, this->m_size); }
104
105 bool operator==(const vlc_vector & v) const
106 {
107 return m_size && v.m_size && m_z == v.m_z && m_sample_pointer == v.m_sample_pointer;
108 }
109
110 bool operator!=(const vlc_vector & v) const { return !(*this == v); }
111
114
116 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
117
119 void load(std::istream & in);
120
122 template <typename archive_t>
123 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
124
126 template <typename archive_t>
127 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
128
131
132 uint32_t get_sample_dens() const;
133 void set_sample_dens(const uint32_t sdens);
134};
135
136template <class t_coder, uint32_t t_dens, uint8_t t_width>
138{
139 if (t_dens == 0)
140 return m_sample_dens;
141 else
142 return t_dens;
143}
144
145template <class t_coder, uint32_t t_dens, uint8_t t_width>
147{
148 m_sample_dens = sdens;
149}
150
151template <class t_coder, uint32_t t_dens, uint8_t t_width>
153 const size_type i) const
154{
155 assert(i + 1 != 0);
156 assert(i < m_size);
157 size_type idx = i / get_sample_dens();
158 return (t_coder::template decode<false, false, int *>(m_z.data(), m_sample_pointer[idx], i - t_dens * idx + 1)) - 1;
159}
160
161template <class t_coder, uint32_t t_dens, uint8_t t_width>
162template <class Container>
164{
165 clear(); // clear bit_vectors
166
167 if (c.empty()) // if c is empty there is nothing to do...
168 return;
169 size_type samples = 0, z_size = 0;
170 // (1) Calculate size of z
171 for (size_type i = 0; i < c.size(); ++i)
172 {
173 if (c[i] + 1 < 1) { throw std::logic_error("vlc_vector cannot decode values smaller than 1!"); }
174 z_size += t_coder::encoding_length(c[i] + 1);
175 }
176 samples = (c.size() + get_sample_dens() - 1) / get_sample_dens();
177 // (2) Write z
178 m_sample_pointer = int_vector<>(samples + 1, 0, bits::hi(z_size + 1) + 1);
179
180 m_z.bit_resize(z_size);
181 z_size = 0;
182 uint64_t * z_data = t_coder::raw_data(m_z);
183 uint8_t offset = 0;
184 size_type no_sample = 0;
185 for (size_type i = 0, sample_cnt = 0; i < c.size(); ++i, --no_sample)
186 {
187 if (!no_sample)
188 { // add a sample pointer
189 no_sample = get_sample_dens();
190 m_sample_pointer[sample_cnt++] = z_size;
191 }
192 t_coder::encode(c[i] + 1, z_data, offset);
193 z_size += t_coder::encoding_length(c[i] + 1);
194 }
195 m_size = c.size();
196}
197
198template <class t_coder, uint32_t t_dens, uint8_t t_width>
199template <uint8_t int_width>
201{
202 clear(); // clear bit_vectors
203 size_type n = v_buf.size();
204 if (n == 0) // if c is empty there is nothing to do...
205 return;
206 size_type samples = 0, z_size = 0;
207 // (1) Calculate size of z
208 for (size_type i = 0; i < n; ++i)
209 {
210 size_type x = v_buf[i] + 1;
211 if (x < 1) { throw std::logic_error("vlc_vector cannot decode values smaller than 1!"); }
212 z_size += t_coder::encoding_length(x);
213 }
214 samples = (n + get_sample_dens() - 1) / get_sample_dens();
215 // (2) Write z
216
217 m_sample_pointer = int_vector<>(samples + 1, 0, bits::hi(z_size + 1) + 1); // add 1 for last entry
218
219 // (b) Initilize bit_vector for encoded data
220 m_z.bit_resize(z_size);
221 z_size = 0;
222 uint64_t * z_data = t_coder::raw_data(m_z);
223 uint8_t offset = 0;
224
225 // (c) Write sample values and deltas
226 size_type no_sample = 0;
227 for (size_type i = 0, sample_cnt = 0; i < n; ++i, --no_sample)
228 {
229 if (!no_sample)
230 { // add a sample pointer
231 no_sample = get_sample_dens();
232 m_sample_pointer[sample_cnt++] = z_size;
233 }
234 size_type x = v_buf[i] + 1;
235 t_coder::encode(x, z_data, offset); // write encoded values
236 z_size += t_coder::encoding_length(x);
237 }
238 m_size = n;
239}
240
241template <class t_coder, uint32_t t_dens, uint8_t t_width>
244 std::string name) const
245{
246 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
247 size_type written_bytes = 0;
248 written_bytes += write_member(m_size, out, child, "m_size");
249 written_bytes += m_z.serialize(out, child, "m_z");
250 written_bytes += m_sample_pointer.serialize(out, child, "m_sample_pointer");
251 structure_tree::add_size(child, written_bytes);
252 return written_bytes;
253}
254
255template <class t_coder, uint32_t t_dens, uint8_t t_width>
257{
258 read_member(m_size, in);
259 m_z.load(in);
260 m_sample_pointer.load(in);
261}
262
263template <class t_coder, uint32_t t_dens, uint8_t t_width>
264template <typename archive_t>
266{
267 ar(CEREAL_NVP(m_size));
268 ar(CEREAL_NVP(m_z));
269 ar(CEREAL_NVP(m_sample_pointer));
270}
271
272template <class t_coder, uint32_t t_dens, uint8_t t_width>
273template <typename archive_t>
275{
276 ar(CEREAL_NVP(m_size));
277 ar(CEREAL_NVP(m_z));
278 ar(CEREAL_NVP(m_sample_pointer));
279}
280
281} // end namespace sdsl
282#endif
#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 .
Definition: int_vector.hpp:216
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:506
static size_type max_size() noexcept
Maximum size of the int_vector.
Definition: int_vector.hpp:542
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:521
Generic iterator for a random access container.
Definition: iterators.hpp:24
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)
A generic immutable space-saving vector class for unsigned integers.
Definition: vlc_vector.hpp:40
static const uint32_t sample_dens
Definition: vlc_vector.hpp:57
const const_iterator end() const
Iterator that points to the position after the last element of the vlc_vector.
Definition: vlc_vector.hpp:103
vlc_vector & operator=(vlc_vector &&)=default
random_access_const_iterator< vlc_vector > iterator
Definition: vlc_vector.hpp:46
bit_vector m_z
Definition: vlc_vector.hpp:58
const const_iterator begin() const
Iterator that points to the first element of the vlc_vector.
Definition: vlc_vector.hpp:100
vlc_vector(vlc_vector &&)=default
vlc_vector(const vlc_vector &)=default
bool operator!=(const vlc_vector &v) const
Definition: vlc_vector.hpp:110
vlc_vector_trait< t_width >::int_vector_type int_vector_type
Definition: vlc_vector.hpp:55
bool operator==(const vlc_vector &v) const
Definition: vlc_vector.hpp:105
size_type size() const
The number of elements in the vlc_vector.
Definition: vlc_vector.hpp:92
ptrdiff_t difference_type
Definition: vlc_vector.hpp:51
vlc_vector()=default
void load(std::istream &in)
Load the vlc_vector from a stream.
Definition: vlc_vector.hpp:256
value_type sample(const size_type i) const
Returns the ith sample of vlc_vector.
uint32_t get_sample_dens() const
Definition: vlc_vector.hpp:137
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
Definition: vlc_vector.hpp:274
const value_type * const_pointer
Definition: vlc_vector.hpp:50
void set_sample_dens(const uint32_t sdens)
Definition: vlc_vector.hpp:146
const value_type reference
Definition: vlc_vector.hpp:48
iterator const_iterator
Definition: vlc_vector.hpp:47
const value_type const_reference
Definition: vlc_vector.hpp:49
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the vlc_vector to a stream.
Definition: vlc_vector.hpp:242
int_vector ::size_type size_type
Definition: vlc_vector.hpp:52
bool empty() const
Returns if the vlc_vector is empty.
Definition: vlc_vector.hpp:97
vlc_vector & operator=(const vlc_vector &)=default
iv_tag index_category
Definition: vlc_vector.hpp:54
uint64_t value_type
Definition: vlc_vector.hpp:45
static size_type max_size()
Return the largest size that this container can ever have.
Definition: vlc_vector.hpp:94
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: vlc_vector.hpp:265
value_type operator[](size_type i) const
[]-operator
Definition: vlc_vector.hpp:152
coder_elias_delta.hpp contains the class sdsl::coder::elias_delta
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
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="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
int_vector< 32 > int_vector_type
Definition: vlc_vector.hpp:28
int_vector< 0 > int_vector_type
Definition: vlc_vector.hpp:22