SDSL  3.0.0
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 
15 namespace sdsl
16 {
17 
18 // possible TODO: resize(size_type size)
19 
20 class nn_dict_dynamic;
21 
22 namespace util
23 {
24 
25 inline 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 
305  class reference
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 
397 namespace 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:30
A generic vector class for integers of width .
Definition: int_vector.hpp:253
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.
reference & operator=(const reference &x)
reference & operator=(bool x)
Assignment operator for the proxy class.
bool operator==(const reference &x) const
bool operator<(const reference &x) const
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
nn_dict_dynamic & operator=(const nn_dict_dynamic &nn)
Assignment operator.
void load(std::istream &in)
Load the data structure.
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 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)
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:566
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 lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition: bits.hpp:696
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
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.