44template <u
int8_t t_b = 4,
typename t_rank = rank_support_v5<>>
48 static_assert(t_b > 0,
"dac_vector: t_b has to be larger than 0");
49 static_assert(t_b < 64,
"dac_vector: t_b has to be smaller than 64");
76 , m_overflow(v.m_overflow)
77 , m_overflow_rank(v.m_overflow_rank)
78 , m_level_pointer_and_rank(v.m_level_pointer_and_rank)
79 , m_max_level(v.m_max_level)
81 m_overflow_rank.set_vector(&m_overflow);
90 *
this = std::move(tmp);
99 m_data = std::move(v.m_data);
100 m_overflow = std::move(v.m_overflow);
101 m_overflow_rank = std::move(v.m_overflow_rank);
102 m_overflow_rank.set_vector(&m_overflow);
103 m_level_pointer_and_rank = std::move(v.m_level_pointer_and_rank);
104 m_max_level = std::move(v.m_max_level);
113 template <
class Container>
117 template <u
int8_t
int_w
idth>
126 bool empty()
const {
return 0 == m_level_pointer_and_rank[2]; }
138 uint8_t offset = t_b;
140 const uint64_t * p = m_level_pointer_and_rank.
data();
141 uint64_t ppi = (*p) + i;
142 while (level < m_max_level and m_overflow[ppi])
145 ppi = *p + (m_overflow_rank(ppi) - *(p - 1));
146 result |= (m_data[ppi] << (offset));
161 m_overflow_rank.load(in, &m_overflow);
162 m_level_pointer_and_rank.
load(in);
167 template <
typename archive_t>
170 template <
typename archive_t>
175 return (m_max_level == v.m_max_level) && (m_data == v.m_data) && (m_overflow == v.m_overflow) &&
176 (m_overflow_rank == v.m_overflow_rank) && (m_level_pointer_and_rank == v.m_level_pointer_and_rank);
182template <u
int8_t t_b,
typename t_rank>
183template <
class Container>
193 m_level_pointer_and_rank[0] = n;
195 uint8_t level_x_2 = 0;
196 uint8_t max_level_x_2 = 4;
205 ++m_level_pointer_and_rank[level_x_2];
208 max_level_x_2 = std::max(max_level_x_2, level_x_2);
211 m_level_pointer_and_rank.resize(max_level_x_2);
214 size_type sum_blocks = 0, last_block_size = 0;
215 for (
size_type i = 0, t = 0; i < m_level_pointer_and_rank.size(); i += 2)
218 sum_blocks += m_level_pointer_and_rank[i];
219 m_level_pointer_and_rank[i] = t;
223 last_block_size = sum_blocks - t;
226 m_overflow =
bit_vector(sum_blocks - last_block_size, 0);
227 m_data.resize(sum_blocks);
229 assert(last_block_size > 0);
239 m_data[j] = val & mask;
246 j = cnt[level_x_2]++;
247 m_data[j] = val & mask;
255 util::init_support(m_overflow_rank, &m_overflow);
257 2 * i < m_level_pointer_and_rank.size() and m_level_pointer_and_rank[2 * i] < m_overflow.size();
260 m_level_pointer_and_rank[2 * i + 1] = m_overflow_rank(m_level_pointer_and_rank[2 * i]);
264template <u
int8_t t_b,
typename t_rank>
265template <u
int8_t
int_w
idth>
275 m_level_pointer_and_rank[0] = n;
277 uint8_t level_x_2 = 0;
278 uint8_t max_level_x_2 = 4;
287 ++m_level_pointer_and_rank[level_x_2];
290 max_level_x_2 = std::max(max_level_x_2, level_x_2);
293 m_level_pointer_and_rank.resize(max_level_x_2);
296 size_type sum_blocks = 0, last_block_size = 0;
297 for (
size_type i = 0, t = 0; i < m_level_pointer_and_rank.size(); i += 2)
300 sum_blocks += m_level_pointer_and_rank[i];
301 m_level_pointer_and_rank[i] = t;
305 last_block_size = sum_blocks - t;
308 m_overflow =
bit_vector(sum_blocks - last_block_size, 0);
309 m_data.resize(sum_blocks);
311 assert(last_block_size > 0);
321 m_data[j] = val & mask;
328 j = cnt[level_x_2]++;
329 m_data[j] = val & mask;
337 util::init_support(m_overflow_rank, &m_overflow);
339 2 * i < m_level_pointer_and_rank.size() and m_level_pointer_and_rank[2 * i] < m_overflow.size();
342 m_level_pointer_and_rank[2 * i + 1] = m_overflow_rank(m_level_pointer_and_rank[2 * i]);
346template <u
int8_t t_b,
typename t_rank>
349 std::string name)
const
353 written_bytes += m_data.serialize(out, child,
"data");
354 written_bytes += m_overflow.serialize(out, child,
"overflow");
355 written_bytes += m_overflow_rank.serialize(out, child,
"overflow_rank");
356 written_bytes += m_level_pointer_and_rank.serialize(out, child,
"level_pointer_and_rank");
357 written_bytes +=
write_member(m_max_level, out, child,
"max_level");
359 return written_bytes;
362template <u
int8_t t_b,
typename t_rank>
363template <
typename archive_t>
373template <u
int8_t t_b,
typename t_rank>
374template <
typename archive_t>
381 m_overflow_rank.set_vector(&m_overflow);
A generic immutable space-saving vector class for unsigned integers.
dac_vector & operator=(const dac_vector &v)
bool operator==(const dac_vector &v) const
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 & operator=(dac_vector &&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.
bool operator!=(const dac_vector &v) const
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
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
dac_vector(const dac_vector &v)
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
void load(std::istream &in)
Load the int_vector for a stream.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
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, 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.
iterators.hpp contains an generic iterator for random access containers.
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)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
rank_support_v5.hpp contains rank_support_v5.5
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.