SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
nn_dict_dynamic.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.
9#ifndef INCLUDED_NN_DICT_DYNAMIC
10#define INCLUDED_NN_DICT_DYNAMIC
11
12#include <iosfwd>
13#include <stdint.h>
14#include <string>
15#include <utility>
16
17#include <sdsl/bits.hpp>
18#include <sdsl/cereal.hpp>
19#include <sdsl/int_vector.hpp>
20#include <sdsl/io.hpp>
22#include <sdsl/util.hpp>
23
24namespace sdsl
25{
26
27// possible TODO: resize(size_type size)
28
29class nn_dict_dynamic;
30
31namespace util
32{
33
34inline void set_zero_bits(nn_dict_dynamic & nn);
35
36}
37
40{
41public:
43 class reference; // forward declaration of inner class
44
45 friend class reference;
47
48private:
49 uint64_t m_depth; // Depth of the tree (1 level corresonds to 0, 2 levels corresponds to 1,...)
50 uint64_t m_v_begin_leaves; // Virtual begin of leaves
51 size_type m_size;
52 int_vector<64> m_offset; // Number of nodes to skip on each level
53 int_vector<64> m_tree; // Tree
54
55public:
56 uint64_t const & depth;
57
59 {
60 return m_size;
61 }
62
64
66 nn_dict_dynamic(const uint64_t n = 0) : depth(m_depth)
67 {
68 m_size = n;
69 if (n == 0)
70 return;
71 uint64_t level; // level indicator
72 uint64_t nodes = 1; // number of nodes (=64 bit integer)
73 uint64_t tmp; // tmp-variable
74
75 /* Calc depth and begin of leaves */
76 m_depth = bits::hi(n) / 6; // if, n>0 calculate \f$ \lfloor log_64(n) \rfloor \f$
77 m_v_begin_leaves = (1ULL << (m_depth * 6)) / 63;
78
79 /* Calc how many nodes to skip on each level */
80 m_offset = int_vector<64>(m_depth + 2, 0);
81 level = m_depth;
82 tmp = n;
83 while (level)
84 {
85 tmp = (tmp + 63) / 64; // get real number of nodes, of the next higher level
86 // <number of nodes in the full tree> - <real number of nodes>
87 m_offset[level + 1] = (1ULL << (6 * level)) - tmp;
88 nodes += tmp;
89 --level;
90 }
91
92 /* Calc how many nodes to skip up to each level*/
93 for (level = 1; level <= m_depth; ++level)
94 {
95 m_offset[level] += m_offset[level - 1];
96 }
97
98 /* Create Tree incl. leaves */
99 m_tree = int_vector<64>(nodes);
100 }
101
104 m_depth(nn.m_depth),
105 m_v_begin_leaves(nn.m_v_begin_leaves),
106 m_size(nn.m_size),
107 m_offset(nn.m_offset),
108 m_tree(nn.m_tree),
109 depth(m_depth)
110 {}
111
114 {
115 *this = std::move(nn);
116 }
117
120 {
121 if (this != &nn)
122 {
123 nn_dict_dynamic tmp(nn);
124 *this = std::move(tmp);
125 }
126 return *this;
127 }
128
131 {
132 if (this != &nn)
133 {
134 m_depth = std::move(nn.m_depth);
135 m_v_begin_leaves = std::move(nn.m_v_begin_leaves);
136 m_size = std::move(nn.m_size);
137 m_offset = std::move(nn.m_offset);
138 m_tree = std::move(nn.m_tree);
139 // set nn to default-constructor state
140 nn.m_size = 0;
141 nn.m_depth = 0;
142 nn.m_v_begin_leaves = 0;
143 }
144 return *this;
145 }
146
148
152 bool operator[](size_type const & idx) const
153 {
154 uint64_t node = m_tree[(m_v_begin_leaves + (idx >> 6)) - m_offset[m_depth]];
155 return (node >> (idx & 0x3F)) & 1;
156 }
157
158 inline reference operator[](size_type const & idx)
159 {
160 return reference(this, idx);
161 }
162
164
169 size_type next(const size_type idx) const
170 {
171 uint64_t v_node_position; // virtual node position
172 uint64_t node; // current node
173 uint64_t dep = m_depth; // current depth of node
174 uint64_t position; // position of the 1-bit
175
176 v_node_position = m_v_begin_leaves + (idx >> 6);
177 uint8_t off = idx & 0x3F; // mod 64
178
179 // Go up until a 1-bit is found
180 node = m_tree[v_node_position - m_offset[dep]] >> off;
181 while (!node or off == 64)
182 {
183 // Not in the root
184 if (v_node_position)
185 {
186 --dep;
187 --v_node_position;
188 off = (v_node_position & 0x3F) + 1;
189 v_node_position >>= 6;
190 node = m_tree[v_node_position - m_offset[dep]] >> off;
191 }
192 else
193 {
194 return size();
195 }
196 }
197 // Calculate the position of the 1-bit
198 position = bits::lo(node) + off;
199
200 // Go down to the leaf
201 while (v_node_position < m_v_begin_leaves)
202 {
203 ++dep;
204 v_node_position = (v_node_position << 6) + 1 + position;
205 node = m_tree[v_node_position - m_offset[dep]];
206
207 // Calculate the position of the 1-bit
208 position = bits::lo(node);
209 }
210 return ((v_node_position - m_v_begin_leaves) << 6) + position;
211 }
212
214
219 size_type prev(const size_type idx) const
220 {
221 uint64_t v_node_position; // virtual node position
222 uint64_t node; // current node
223 uint64_t dep = m_depth; // current depth of node
224 uint64_t position; // position of the 1-bit
225
226 v_node_position = m_v_begin_leaves + (idx >> 6);
227 uint8_t off = idx & 0x3F; // mod 64
228
229 // Go up until a 1-bit is found
230 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
231 while (!node or off == (uint8_t)-1)
232 {
233
234 // Not in the root
235 if (v_node_position)
236 {
237 --dep;
238 --v_node_position;
239
240 off = ((uint8_t)(v_node_position & 0x3F)) - 1;
241 v_node_position >>= 6;
242
243 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
244 }
245 else
246 {
247 return size();
248 }
249 }
250 // Calculate the position of the 1-bit
251 position = bits::hi(node) - (63 - off);
252
253 // Go down to the leaf
254 while (v_node_position < m_v_begin_leaves)
255 {
256 ++dep;
257 v_node_position = (v_node_position << 6) + 1 + position;
258 node = m_tree[v_node_position - m_offset[dep]];
259
260 // Calculate the position of the 1-bit
261 position = bits::hi(node); //-(63-off)
262 }
263 return ((v_node_position - m_v_begin_leaves) << 6) + position;
264 }
265
267 void load(std::istream & in)
268 {
269 read_member(m_depth, in);
270 read_member(m_v_begin_leaves, in);
271 read_member(m_size, in);
272 m_offset.load(in);
273 m_tree.load(in);
274 }
275
277 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
278 {
279 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
280 size_type written_bytes = 0;
281 written_bytes += write_member(m_depth, out, child, "depth");
282 written_bytes += write_member(m_v_begin_leaves, out, child, "v_begin_leaves");
283 written_bytes += write_member(m_size, out, child, "size");
284 written_bytes += m_offset.serialize(out, child, "offset");
285 written_bytes += m_tree.serialize(out, child, "tree");
286 structure_tree::add_size(child, written_bytes);
287 return written_bytes;
288 }
289
291 template <typename archive_t>
292 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
293 {
294 ar(CEREAL_NVP(m_depth));
295 ar(CEREAL_NVP(m_v_begin_leaves));
296 ar(CEREAL_NVP(m_size));
297 ar(CEREAL_NVP(m_offset));
298 ar(CEREAL_NVP(m_tree));
299 }
300
302 template <typename archive_t>
303 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
304 {
305 ar(CEREAL_NVP(m_depth));
306 ar(CEREAL_NVP(m_v_begin_leaves));
307 ar(CEREAL_NVP(m_size));
308 ar(CEREAL_NVP(m_offset));
309 ar(CEREAL_NVP(m_tree));
310 }
311
313 bool operator==(nn_dict_dynamic const & other) const noexcept
314 {
315 return (m_depth == other.m_depth) && (m_v_begin_leaves == other.m_v_begin_leaves) && (m_size == other.m_size)
316 && (m_offset == other.m_offset) && (m_tree == other.m_tree);
317 }
318
320 bool operator!=(nn_dict_dynamic const & other) const noexcept
321 {
322 return !(*this == other);
323 }
324
326 {
327 private:
328 nn_dict_dynamic * m_pbv; // pointer to the bit_vector_nearest_neigbour
329 size_type m_idx; // virtual node position
330
331 public:
333 reference(nn_dict_dynamic * pbv, nn_dict_dynamic::size_type idx) : m_pbv(pbv), m_idx(idx){};
334
337 {
338 uint64_t v_node_position; // virtual node position
339 uint64_t r_node_position; // real node position
340 uint64_t dep = m_pbv->m_depth; // current depth of node
341
342 v_node_position = m_pbv->m_v_begin_leaves + (m_idx >> 6);
343 uint8_t offset = m_idx & 0x3F; // pos mod 64
344 if (x)
345 {
346 while (true)
347 {
348 r_node_position = v_node_position - m_pbv->m_offset[dep];
349 uint64_t w = m_pbv->m_tree[r_node_position];
350 if ((w >> offset) & 1)
351 { // if the bit was already set
352 return *this;
353 }
354 else
355 {
356 m_pbv->m_tree[r_node_position] |= (1ULL << offset); // set bit
357 if (!w and dep)
358 { // go up in the tree
359 --dep;
360 --v_node_position;
361 offset = v_node_position & 0x3F;
362 v_node_position >>= 6;
363 }
364 else
365 {
366 return *this;
367 }
368 }
369 }
370 }
371 else
372 {
373 while (true)
374 {
375 r_node_position = v_node_position - m_pbv->m_offset[dep];
376 uint64_t w = m_pbv->m_tree[r_node_position];
377 if (!((w >> offset) & 1))
378 { // if the bit is already 0
379 return *this;
380 }
381 else
382 {
383 m_pbv->m_tree[r_node_position] &= (~(1ULL << offset)); // unset bit
384 if (!m_pbv->m_tree[r_node_position] and dep)
385 { // go up in the tree
386 --dep;
387 --v_node_position;
388 offset = v_node_position & 0x3F;
389 v_node_position >>= 6;
390 }
391 else
392 {
393 return *this;
394 }
395 }
396 }
397 }
398 return *this;
399 }
400
402 {
403 return *this = bool(x);
404 }
405
406 reference(reference const &) = default;
407
409 operator bool() const
410 {
411 uint64_t node = m_pbv->m_tree[(m_pbv->m_v_begin_leaves + (m_idx >> 6)) - m_pbv->m_offset[m_pbv->m_depth]];
412 return (node >> (m_idx & 0x3F)) & 1;
413 }
414
415 bool operator==(reference const & x) const
416 {
417 return bool(*this) == bool(x);
418 }
419
420 bool operator<(reference const & x) const
421 {
422 return !bool(*this) and bool(x);
423 }
424 };
425};
426
427namespace util
428{
430{
431 util::set_to_value(nn.m_tree, 0);
432}
433} // namespace util
434
435} // namespace sdsl
436
437#endif // end file
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
A generic vector class for integers of width .
Definition io.hpp:36
int_vector_size_type size_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
reference(nn_dict_dynamic *pbv, nn_dict_dynamic::size_type idx)
Constructor.
bool operator<(reference const &x) const
reference(reference const &)=default
bool operator==(reference const &x) const
reference & operator=(reference const &x)
reference & operator=(bool x)
Assignment operator for the proxy class.
A class for a dynamic bit vector which also supports the prev and next operations.
void load(std::istream &in)
Load the data structure.
bool operator[](size_type const &idx) const
Access the bit at index idx.
reference operator[](size_type const &idx)
nn_dict_dynamic(nn_dict_dynamic const &nn)
Copy constructor.
int_vector< 64 >::size_type size_type
bool operator!=(nn_dict_dynamic const &other) const noexcept
Inequality operator.
size_type size() const
nn_dict_dynamic & operator=(nn_dict_dynamic const &nn)
Assignment operator.
nn_dict_dynamic(nn_dict_dynamic &&nn)
move constructor
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize the data structure.
nn_dict_dynamic & operator=(nn_dict_dynamic &&nn)
Assignment move operator.
size_type next(const size_type idx) const
Get the leftmost index where a bit is set.
bool operator==(nn_dict_dynamic const &other) const noexcept
Equality operator.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
size_type prev(const size_type idx) const
Get the rightmost index where a bit is set.
nn_dict_dynamic(const uint64_t n=0)
Constructor.
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)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
void set_zero_bits(nn_dict_dynamic &nn)
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition util.hpp:597
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
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition bits.hpp:689
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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.