58template <u
int8_t t_b = 4,
typename t_rank = rank_support_v5<>>
62 static_assert(t_b > 0,
"dac_vector: t_b has to be larger than 0");
63 static_assert(t_b < 64,
"dac_vector: t_b has to be smaller than 64");
90 m_overflow(v.m_overflow),
91 m_overflow_rank(v.m_overflow_rank),
92 m_level_pointer_and_rank(v.m_level_pointer_and_rank),
93 m_max_level(v.m_max_level)
95 m_overflow_rank.set_vector(&m_overflow);
100 *
this = std::move(v);
107 *
this = std::move(tmp);
116 m_data = std::move(v.m_data);
117 m_overflow = std::move(v.m_overflow);
118 m_overflow_rank = std::move(v.m_overflow_rank);
119 m_overflow_rank.set_vector(&m_overflow);
120 m_level_pointer_and_rank = std::move(v.m_level_pointer_and_rank);
121 m_max_level = std::move(v.m_max_level);
130 template <
class Container>
134 template <u
int8_t
int_w
idth>
140 return m_level_pointer_and_rank[2];
151 return 0 == m_level_pointer_and_rank[2];
170 uint8_t offset = t_b;
172 uint64_t
const * p = m_level_pointer_and_rank.data();
173 uint64_t ppi = (*p) + i;
174 while (level < m_max_level and m_overflow[ppi])
177 ppi = *p + (m_overflow_rank(ppi) - *(p - 1));
178 result |= (m_data[ppi] << (offset));
193 m_overflow_rank.load(in, &m_overflow);
194 m_level_pointer_and_rank.load(in);
199 template <
typename archive_t>
202 template <
typename archive_t>
207 return (m_max_level == v.m_max_level) && (m_data == v.m_data) && (m_overflow == v.m_overflow)
208 && (m_overflow_rank == v.m_overflow_rank) && (m_level_pointer_and_rank == v.m_level_pointer_and_rank);
213 return !(*
this == v);
217template <u
int8_t t_b,
typename t_rank>
218template <
class Container>
229 m_level_pointer_and_rank[0] = n;
231 uint8_t level_x_2 = 0;
232 uint8_t max_level_x_2 = 4;
241 ++m_level_pointer_and_rank[level_x_2];
244 max_level_x_2 = std::max(max_level_x_2, level_x_2);
247 m_level_pointer_and_rank.resize(max_level_x_2);
250 size_type sum_blocks = 0, last_block_size = 0;
251 for (
size_type i = 0, t = 0; i < m_level_pointer_and_rank.size(); i += 2)
254 sum_blocks += m_level_pointer_and_rank[i];
255 m_level_pointer_and_rank[i] = t;
259 last_block_size = sum_blocks - t;
262 m_overflow =
bit_vector(sum_blocks - last_block_size, 0);
263 m_data.resize(sum_blocks);
265 assert(last_block_size > 0);
275 m_data[j] = val & mask;
282 j = cnt[level_x_2]++;
283 m_data[j] = val & mask;
291 util::init_support(m_overflow_rank, &m_overflow);
293 2 * i < m_level_pointer_and_rank.size() and m_level_pointer_and_rank[2 * i] < m_overflow.size();
296 m_level_pointer_and_rank[2 * i + 1] = m_overflow_rank(m_level_pointer_and_rank[2 * i]);
300template <u
int8_t t_b,
typename t_rank>
301template <u
int8_t
int_w
idth>
312 m_level_pointer_and_rank[0] = n;
314 uint8_t level_x_2 = 0;
315 uint8_t max_level_x_2 = 4;
324 ++m_level_pointer_and_rank[level_x_2];
327 max_level_x_2 = std::max(max_level_x_2, level_x_2);
330 m_level_pointer_and_rank.resize(max_level_x_2);
333 size_type sum_blocks = 0, last_block_size = 0;
334 for (
size_type i = 0, t = 0; i < m_level_pointer_and_rank.size(); i += 2)
337 sum_blocks += m_level_pointer_and_rank[i];
338 m_level_pointer_and_rank[i] = t;
342 last_block_size = sum_blocks - t;
345 m_overflow =
bit_vector(sum_blocks - last_block_size, 0);
346 m_data.resize(sum_blocks);
348 assert(last_block_size > 0);
358 m_data[j] = val & mask;
365 j = cnt[level_x_2]++;
366 m_data[j] = val & mask;
374 util::init_support(m_overflow_rank, &m_overflow);
376 2 * i < m_level_pointer_and_rank.size() and m_level_pointer_and_rank[2 * i] < m_overflow.size();
379 m_level_pointer_and_rank[2 * i + 1] = m_overflow_rank(m_level_pointer_and_rank[2 * i]);
383template <u
int8_t t_b,
typename t_rank>
389 written_bytes += m_data.serialize(out, child,
"data");
390 written_bytes += m_overflow.serialize(out, child,
"overflow");
391 written_bytes += m_overflow_rank.serialize(out, child,
"overflow_rank");
392 written_bytes += m_level_pointer_and_rank.serialize(out, child,
"level_pointer_and_rank");
393 written_bytes +=
write_member(m_max_level, out, child,
"max_level");
395 return written_bytes;
398template <u
int8_t t_b,
typename t_rank>
399template <
typename archive_t>
409template <u
int8_t t_b,
typename t_rank>
410template <
typename archive_t>
417 m_overflow_rank.set_vector(&m_overflow);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
bool empty() const
Returns if the dac_vector is empty.
const value_type const_reference
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
dac_vector(dac_vector &&v)
dac_vector(dac_vector const &v)
bool operator==(dac_vector const &v) const
dac_vector & operator=(dac_vector &&v)
dac_vector & operator=(dac_vector const &v)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the dac_vector to a stream.
int_vector ::size_type size_type
const const_iterator end() const
Iterator that points to the position after the last element of the dac_vector.
static size_type max_size()
Return the largest size that this container can ever have.
random_access_const_iterator< dac_vector > const_iterator
const_reference reference
size_type size() const
The number of elements in the dac_vector.
void load(std::istream &in)
Load from a stream.
int_vector ::value_type value_type
value_type operator[](size_type i) const
[]-operator
const pointer const_pointer
bool operator!=(dac_vector const &v) const
const const_iterator begin() const
Iterator that points to the first element of the dac_vector.
ptrdiff_t difference_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
const_reference * pointer
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
int_vector_size_type size_type
int_vector_trait< t_width >::value_type value_type
static size_type max_size() noexcept
Maximum size of the int_vector.
Generic iterator for a random access container.
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.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
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)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
rank_support_v5.hpp contains rank_support_v5.5
Contains declarations and definitions of data structure concepts.
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
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.