9 #ifndef INCLUDED_NN_DICT_DYNAMIC
10 #define INCLUDED_NN_DICT_DYNAMIC
20 class nn_dict_dynamic;
41 uint64_t m_v_begin_leaves;
65 m_v_begin_leaves = (1ULL << (m_depth * 6)) / 63;
73 tmp = (tmp + 63) / 64;
75 m_offset[level + 1] = (1ULL << (6 * level)) - tmp;
81 for (level = 1; level <= m_depth; ++level) { m_offset[level] += m_offset[level - 1]; }
90 , m_v_begin_leaves(nn.m_v_begin_leaves)
92 , m_offset(nn.m_offset)
101 *
this = std::move(nn);
110 *
this = std::move(tmp);
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);
128 nn.m_v_begin_leaves = 0;
140 uint64_t node = m_tree[(m_v_begin_leaves + (idx >> 6)) - m_offset[m_depth]];
141 return (node >> (idx & 0x3F)) & 1;
154 uint64_t v_node_position;
156 uint64_t dep = m_depth;
159 v_node_position = m_v_begin_leaves + (idx >> 6);
160 uint8_t off = idx & 0x3F;
163 node = m_tree[v_node_position - m_offset[dep]] >> off;
164 while (!node or off == 64)
171 off = (v_node_position & 0x3F) + 1;
172 v_node_position >>= 6;
173 node = m_tree[v_node_position - m_offset[dep]] >> off;
184 while (v_node_position < m_v_begin_leaves)
187 v_node_position = (v_node_position << 6) + 1 + position;
188 node = m_tree[v_node_position - m_offset[dep]];
193 return ((v_node_position - m_v_begin_leaves) << 6) + position;
204 uint64_t v_node_position;
206 uint64_t dep = m_depth;
209 v_node_position = m_v_begin_leaves + (idx >> 6);
210 uint8_t off = idx & 0x3F;
213 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
214 while (!node or off == (uint8_t)-1)
223 off = ((uint8_t)(v_node_position & 0x3F)) - 1;
224 v_node_position >>= 6;
226 node = m_tree[v_node_position - m_offset[dep]] << (63 - off);
234 position =
bits::hi(node) - (63 - off);
237 while (v_node_position < m_v_begin_leaves)
240 v_node_position = (v_node_position << 6) + 1 + position;
241 node = m_tree[v_node_position - m_offset[dep]];
246 return ((v_node_position - m_v_begin_leaves) << 6) + position;
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");
270 return written_bytes;
274 template <
typename archive_t>
285 template <
typename archive_t>
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);
319 uint64_t v_node_position;
320 uint64_t r_node_position;
321 uint64_t dep = m_pbv->m_depth;
323 v_node_position = m_pbv->m_v_begin_leaves + (m_idx >> 6);
324 uint8_t offset = m_idx & 0x3F;
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)
337 m_pbv->m_tree[r_node_position] |= (1ULL << offset);
342 offset = v_node_position & 0x3F;
343 v_node_position >>= 6;
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))
364 m_pbv->m_tree[r_node_position] &= (~(1ULL << offset));
365 if (!m_pbv->m_tree[r_node_position] and dep)
369 offset = v_node_position & 0x3F;
370 v_node_position >>= 6;
385 operator bool()
const
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;
A generic vector class for integers of width .
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.
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.
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.
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="")
void read_member(T &t, std::istream &in)
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.
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.