SDSL 3.0.1
Succinct Data Structure Library
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 <sdsl/int_vector.hpp>
13#include <sdsl/util.hpp>
14
15namespace sdsl
16{
17
18// possible TODO: resize(size_type size)
19
20class nn_dict_dynamic;
21
22namespace util
23{
24
25inline void set_zero_bits(nn_dict_dynamic & nn);
26
27}
28
31{
32 public:
34 class reference; // forward declaration of inner class
35
36 friend class reference;
38
39 private:
40 uint64_t m_depth; // Depth of the tree (1 level corresonds to 0, 2 levels corresponds to 1,...)
41 uint64_t m_v_begin_leaves; // Virtual begin of leaves
42 size_type m_size;
43 int_vector<64> m_offset; // Number of nodes to skip on each level
44 int_vector<64> m_tree; // Tree
45
46 public:
47 const uint64_t & depth;
48
49 size_type size() const { return m_size; }
50
52
54 nn_dict_dynamic(const uint64_t n = 0)
55 : depth(m_depth)
56 {
57 m_size = n;
58 if (n == 0) return;
59 uint64_t level; // level indicator
60 uint64_t nodes = 1; // number of nodes (=64 bit integer)
61 uint64_t tmp; // tmp-variable
62
63 /* Calc depth and begin of leaves */
64 m_depth = bits::hi(n) / 6; // if, n>0 calculate \f$ \lfloor log_64(n) \rfloor \f$
65 m_v_begin_leaves = (1ULL << (m_depth * 6)) / 63;
66
67 /* Calc how many nodes to skip on each level */
68 m_offset = int_vector<64>(m_depth + 2, 0);
69 level = m_depth;
70 tmp = n;
71 while (level)
72 {
73 tmp = (tmp + 63) / 64; // get real number of nodes, of the next higher level
74 // <number of nodes in the full tree> - <real number of nodes>
75 m_offset[level + 1] = (1ULL << (6 * level)) - tmp;
76 nodes += tmp;
77 --level;
78 }
79
80 /* Calc how many nodes to skip up to each level*/
81 for (level = 1; level <= m_depth; ++level) { m_offset[level] += m_offset[level - 1]; }
82
83 /* Create Tree incl. leaves */
84 m_tree = int_vector<64>(nodes);
85 }
86
89 : m_depth(nn.m_depth)
90 , m_v_begin_leaves(nn.m_v_begin_leaves)
91 , m_size(nn.m_size)
92 , m_offset(nn.m_offset)
93 , m_tree(nn.m_tree)
94 , depth(m_depth)
95 {}
96
99 : depth(m_depth)
100 {
101 *this = std::move(nn);
102 }
103
106 {
107 if (this != &nn)
108 {
109 nn_dict_dynamic tmp(nn);
110 *this = std::move(tmp);
111 }
112 return *this;
113 }
114
117 {
118 if (this != &nn)
119 {
120 m_depth = std::move(nn.m_depth);
121 m_v_begin_leaves = std::move(nn.m_v_begin_leaves);
122 m_size = std::move(nn.m_size);
123 m_offset = std::move(nn.m_offset);
124 m_tree = std::move(nn.m_tree);
125 // set nn to default-constructor state
126 nn.m_size = 0;
127 nn.m_depth = 0;
128 nn.m_v_begin_leaves = 0;
129 }
130 return *this;
131 }
132
134
138 bool operator[](const size_type & idx) const
139 {
140 uint64_t node = m_tree[(m_v_begin_leaves + (idx >> 6)) - m_offset[m_depth]];
141 return (node >> (idx & 0x3F)) & 1;
142 }
143
144 inline reference operator[](const size_type & idx) { return reference(this, idx); }
145
147
152 size_type next(const size_type idx) const
153 {
154 uint64_t v_node_position; // virtual node position
155 uint64_t node; // current node
156 uint64_t dep = m_depth; // current depth of node
157 uint64_t position; // position of the 1-bit
158
159 v_node_position = m_v_begin_leaves + (idx >> 6);
160 uint8_t off = idx & 0x3F; // mod 64
161
162 // Go up until a 1-bit is found
163 node = m_tree[v_node_position - m_offset[dep]] >> off;
164 while (!node or off == 64)
165 {
166 // Not in the root
167 if (v_node_position)
168 {
169 --dep;
170 --v_node_position;
171 off = (v_node_position & 0x3F) + 1;
172 v_node_position >>= 6;
173 node = m_tree[v_node_position - m_offset[dep]] >> off;
174 }
175 else
176 {
177 return size();
178 }
179 }
180 // Calculate the position of the 1-bit
181 position = bits::lo(node) + off;
182
183 // Go down to the leaf
184 while (v_node_position < m_v_begin_leaves)
185 {
186 ++dep;
187 v_node_position = (v_node_position << 6) + 1 + position;
188 node = m_tree[v_node_position - m_offset[dep]];
189
190 // Calculate the position of the 1-bit
191 position = bits::lo(node);
192 }
193 return ((v_node_position - m_v_begin_leaves) << 6) + position;
194 }
195
197
202 size_type prev(const size_type idx) const
203 {
204 uint64_t v_node_position; // virtual node position
205 uint64_t node; // current node
206 uint64_t dep = m_depth; // current depth of node
207 uint64_t position; // position of the 1-bit
208
209 v_node_position = m_v_begin_leaves + (idx >> 6);
210 uint8_t off = idx & 0x3F; // mod 64
211
212 // Go up until a 1-bit is found
213 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
214 while (!node or off == (uint8_t)-1)
215 {
216
217 // Not in the root
218 if (v_node_position)
219 {
220 --dep;
221 --v_node_position;
222
223 off = ((uint8_t)(v_node_position & 0x3F)) - 1;
224 v_node_position >>= 6;
225
226 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
227 }
228 else
229 {
230 return size();
231 }
232 }
233 // Calculate the position of the 1-bit
234 position = bits::hi(node) - (63 - off);
235
236 // Go down to the leaf
237 while (v_node_position < m_v_begin_leaves)
238 {
239 ++dep;
240 v_node_position = (v_node_position << 6) + 1 + position;
241 node = m_tree[v_node_position - m_offset[dep]];
242
243 // Calculate the position of the 1-bit
244 position = bits::hi(node); //-(63-off)
245 }
246 return ((v_node_position - m_v_begin_leaves) << 6) + position;
247 }
248
250 void load(std::istream & in)
251 {
252 read_member(m_depth, in);
253 read_member(m_v_begin_leaves, in);
254 read_member(m_size, in);
255 m_offset.load(in);
256 m_tree.load(in);
257 }
258
260 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
261 {
262 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
263 size_type written_bytes = 0;
264 written_bytes += write_member(m_depth, out, child, "depth");
265 written_bytes += write_member(m_v_begin_leaves, out, child, "v_begin_leaves");
266 written_bytes += write_member(m_size, out, child, "size");
267 written_bytes += m_offset.serialize(out, child, "offset");
268 written_bytes += m_tree.serialize(out, child, "tree");
269 structure_tree::add_size(child, written_bytes);
270 return written_bytes;
271 }
272
274 template <typename archive_t>
275 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
276 {
277 ar(CEREAL_NVP(m_depth));
278 ar(CEREAL_NVP(m_v_begin_leaves));
279 ar(CEREAL_NVP(m_size));
280 ar(CEREAL_NVP(m_offset));
281 ar(CEREAL_NVP(m_tree));
282 }
283
285 template <typename archive_t>
286 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
287 {
288 ar(CEREAL_NVP(m_depth));
289 ar(CEREAL_NVP(m_v_begin_leaves));
290 ar(CEREAL_NVP(m_size));
291 ar(CEREAL_NVP(m_offset));
292 ar(CEREAL_NVP(m_tree));
293 }
294
296 bool operator==(nn_dict_dynamic const & other) const noexcept
297 {
298 return (m_depth == other.m_depth) && (m_v_begin_leaves == other.m_v_begin_leaves) && (m_size == other.m_size) &&
299 (m_offset == other.m_offset) && (m_tree == other.m_tree);
300 }
301
303 bool operator!=(nn_dict_dynamic const & other) const noexcept { return !(*this == other); }
304
306 {
307 private:
308 nn_dict_dynamic * m_pbv; // pointer to the bit_vector_nearest_neigbour
309 size_type m_idx; // virtual node position
310 public:
313 : m_pbv(pbv)
314 , m_idx(idx){};
315
318 {
319 uint64_t v_node_position; // virtual node position
320 uint64_t r_node_position; // real node position
321 uint64_t dep = m_pbv->m_depth; // current depth of node
322
323 v_node_position = m_pbv->m_v_begin_leaves + (m_idx >> 6);
324 uint8_t offset = m_idx & 0x3F; // pos mod 64
325 if (x)
326 {
327 while (true)
328 {
329 r_node_position = v_node_position - m_pbv->m_offset[dep];
330 uint64_t w = m_pbv->m_tree[r_node_position];
331 if ((w >> offset) & 1)
332 { // if the bit was already set
333 return *this;
334 }
335 else
336 {
337 m_pbv->m_tree[r_node_position] |= (1ULL << offset); // set bit
338 if (!w and dep)
339 { // go up in the tree
340 --dep;
341 --v_node_position;
342 offset = v_node_position & 0x3F;
343 v_node_position >>= 6;
344 }
345 else
346 {
347 return *this;
348 }
349 }
350 }
351 }
352 else
353 {
354 while (true)
355 {
356 r_node_position = v_node_position - m_pbv->m_offset[dep];
357 uint64_t w = m_pbv->m_tree[r_node_position];
358 if (!((w >> offset) & 1))
359 { // if the bit is already 0
360 return *this;
361 }
362 else
363 {
364 m_pbv->m_tree[r_node_position] &= (~(1ULL << offset)); // unset bit
365 if (!m_pbv->m_tree[r_node_position] and dep)
366 { // go up in the tree
367 --dep;
368 --v_node_position;
369 offset = v_node_position & 0x3F;
370 v_node_position >>= 6;
371 }
372 else
373 {
374 return *this;
375 }
376 }
377 }
378 }
379 return *this;
380 }
381
382 reference & operator=(const reference & x) { return *this = bool(x); }
383
385 operator bool() const
386 {
387 uint64_t node = m_pbv->m_tree[(m_pbv->m_v_begin_leaves + (m_idx >> 6)) - m_pbv->m_offset[m_pbv->m_depth]];
388 return (node >> (m_idx & 0x3F)) & 1;
389 }
390
391 bool operator==(const reference & x) const { return bool(*this) == bool(x); }
392
393 bool operator<(const reference & x) const { return !bool(*this) and bool(x); }
394 };
395};
396
397namespace util
398{
400{
401 util::set_to_value(nn.m_tree, 0);
402}
403} // namespace util
404
405} // namespace sdsl
406
407#endif // end file
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
A generic vector class for integers of width .
Definition: int_vector.hpp:216
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==(const reference &x) const
reference & operator=(const reference &x)
bool operator<(const reference &x) const
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.
const uint64_t & depth
bool operator[](const size_type &idx) const
Access the bit at index idx.
int_vector< 64 >::size_type size_type
void load(std::istream &in)
Load the data structure.
nn_dict_dynamic & operator=(const nn_dict_dynamic &nn)
Assignment operator.
nn_dict_dynamic(const nn_dict_dynamic &nn)
Copy constructor.
bool operator!=(nn_dict_dynamic const &other) const noexcept
Inequality operator.
size_type size() const
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.
reference operator[](const size_type &idx)
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, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
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:563
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 lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition: bits.hpp:686
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.