SDSL  3.0.0
Succinct Data Structure Library
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 
16 namespace sdsl
17 {
18 
19 template <uint8_t t_width>
21 {
23 };
24 
25 template <>
26 struct vlc_vector_trait<32>
27 {
29 };
30 
32 
38 template <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;
49  typedef const value_type const_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;
78  vlc_vector & operator=(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 
130  value_type sample(const size_type i) const;
131 
132  uint32_t get_sample_dens() const;
133  void set_sample_dens(const uint32_t sdens);
134 };
135 
136 template <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 
145 template <class t_coder, uint32_t t_dens, uint8_t t_width>
147 {
148  m_sample_dens = sdens;
149 }
150 
151 template <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 
161 template <class t_coder, uint32_t t_dens, uint8_t t_width>
162 template <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 
198 template <class t_coder, uint32_t t_dens, uint8_t t_width>
199 template <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 
241 template <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 
255 template <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 
263 template <class t_coder, uint32_t t_dens, uint8_t t_width>
264 template <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 
272 template <class t_coder, uint32_t t_dens, uint8_t t_width>
273 template <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:30
uint64_t size() const
Returns the number of elements currently stored.
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:530
static size_type max_size() noexcept
Maximum size of the int_vector.
Definition: int_vector.hpp:566
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
Generic iterator for a random access container.
Definition: iterators.hpp:24
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
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
vlc_vector & operator=(const vlc_vector &)=default
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
iv_tag index_category
Definition: vlc_vector.hpp:54
uint64_t value_type
Definition: vlc_vector.hpp:42
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 SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
int_vector< 32 > int_vector_type
Definition: vlc_vector.hpp:28
int_vector< 0 > int_vector_type
Definition: vlc_vector.hpp:22