9#ifndef INCLUDED_NN_DICT_DYNAMIC
10#define INCLUDED_NN_DICT_DYNAMIC
50 uint64_t m_v_begin_leaves;
77 m_v_begin_leaves = (1ULL << (m_depth * 6)) / 63;
85 tmp = (tmp + 63) / 64;
87 m_offset[level + 1] = (1ULL << (6 * level)) - tmp;
93 for (level = 1; level <= m_depth; ++level)
95 m_offset[level] += m_offset[level - 1];
105 m_v_begin_leaves(nn.m_v_begin_leaves),
107 m_offset(nn.m_offset),
115 *
this = std::move(nn);
124 *
this = std::move(tmp);
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);
142 nn.m_v_begin_leaves = 0;
154 uint64_t node = m_tree[(m_v_begin_leaves + (idx >> 6)) - m_offset[m_depth]];
155 return (node >> (idx & 0x3F)) & 1;
171 uint64_t v_node_position;
173 uint64_t dep = m_depth;
176 v_node_position = m_v_begin_leaves + (idx >> 6);
177 uint8_t off = idx & 0x3F;
180 node = m_tree[v_node_position - m_offset[dep]] >> off;
181 while (!node or off == 64)
188 off = (v_node_position & 0x3F) + 1;
189 v_node_position >>= 6;
190 node = m_tree[v_node_position - m_offset[dep]] >> off;
201 while (v_node_position < m_v_begin_leaves)
204 v_node_position = (v_node_position << 6) + 1 + position;
205 node = m_tree[v_node_position - m_offset[dep]];
210 return ((v_node_position - m_v_begin_leaves) << 6) + position;
221 uint64_t v_node_position;
223 uint64_t dep = m_depth;
226 v_node_position = m_v_begin_leaves + (idx >> 6);
227 uint8_t off = idx & 0x3F;
230 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
231 while (!node or off == (uint8_t)-1)
240 off = ((uint8_t)(v_node_position & 0x3F)) - 1;
241 v_node_position >>= 6;
243 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
251 position =
bits::hi(node) - (63 - off);
254 while (v_node_position < m_v_begin_leaves)
257 v_node_position = (v_node_position << 6) + 1 + position;
258 node = m_tree[v_node_position - m_offset[dep]];
263 return ((v_node_position - m_v_begin_leaves) << 6) + position;
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");
287 return written_bytes;
291 template <
typename archive_t>
302 template <
typename archive_t>
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);
322 return !(*
this == other);
338 uint64_t v_node_position;
339 uint64_t r_node_position;
340 uint64_t dep = m_pbv->m_depth;
342 v_node_position = m_pbv->m_v_begin_leaves + (m_idx >> 6);
343 uint8_t offset = m_idx & 0x3F;
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)
356 m_pbv->m_tree[r_node_position] |= (1ULL << offset);
361 offset = v_node_position & 0x3F;
362 v_node_position >>= 6;
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))
383 m_pbv->m_tree[r_node_position] &= (~(1ULL << offset));
384 if (!m_pbv->m_tree[r_node_position] and dep)
388 offset = v_node_position & 0x3F;
389 v_node_position >>= 6;
403 return *
this = bool(x);
409 operator bool()
const
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;
417 return bool(*
this) == bool(x);
422 return !bool(*
this) and bool(x);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
A generic vector class for integers of width .
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.
int_vector< 64 >::size_type size_type
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.
bool operator!=(nn_dict_dynamic const &other) const noexcept
Inequality operator.
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.
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="")
void read_member(T &t, std::istream &in)
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
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.