8#ifndef INCLUDED_SDSL_SELECT_SUPPORT_MCL
9#define INCLUDED_SDSL_SELECT_SUPPORT_MCL
63template <u
int8_t t_b = 1, u
int8_t t_pat_len = 1>
67 static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
68 "select_support_mcl: bit pattern must be `0`,`1`,`10`, `01`, or `11`");
69 static_assert(t_pat_len == 1u or t_pat_len == 2u,
"select_support_mcl: bit pattern length must be 1 or 2");
92 void init_fast(
bit_vector const * v =
nullptr);
109 template <
typename archive_t>
112 template <
typename archive_t>
120template <u
int8_t t_b, u
int8_t t_pat_len>
123 if (t_pat_len > 1 or (
vv !=
nullptr and
vv->size() < 100000))
130template <u
int8_t t_b, u
int8_t t_pat_len>
136 m_superblock(ss.m_superblock),
137 m_arg_cnt(ss.m_arg_cnt)
140 if (ss.m_longsuperblock !=
nullptr)
142 m_longsuperblock = new int_vector<0>[sb];
143 for (size_type i = 0; i < sb; ++i)
145 m_longsuperblock[i] = ss.m_longsuperblock[i];
148 m_miniblock =
nullptr;
149 if (ss.m_miniblock !=
nullptr)
151 m_miniblock = new int_vector<0>[sb];
152 for (size_type i = 0; i < sb; ++i)
154 m_miniblock[i] = ss.m_miniblock[i];
159template <u
int8_t t_b, u
int8_t t_pat_len>
162 *
this = std::move(ss);
165template <u
int8_t t_b, u
int8_t t_pat_len>
171 *
this = std::move(tmp);
176template <u
int8_t t_b, u
int8_t t_pat_len>
182 m_logn2 = ss.m_logn2;
183 m_logn4 = ss.m_logn4;
184 m_superblock = std::move(ss.m_superblock);
185 m_arg_cnt = ss.m_arg_cnt;
188 delete[] m_longsuperblock;
189 m_longsuperblock = ss.m_longsuperblock;
190 ss.m_longsuperblock =
nullptr;
192 delete[] m_miniblock;
193 m_miniblock = ss.m_miniblock;
194 ss.m_miniblock =
nullptr;
199template <u
int8_t t_b, u
int8_t t_pat_len>
202 delete[] m_longsuperblock;
203 delete[] m_miniblock;
206template <u
int8_t t_b, u
int8_t t_pat_len>
221 size_type sb = (m_arg_cnt + SUPER_BLOCK_SIZE - 1) / SUPER_BLOCK_SIZE;
222 delete[] m_miniblock;
227 size_type arg_position[SUPER_BLOCK_SIZE], arg_cnt = 0;
233 arg_position[arg_cnt % SUPER_BLOCK_SIZE] = i;
234 assert(arg_position[arg_cnt % SUPER_BLOCK_SIZE] == i);
236 if (arg_cnt % SUPER_BLOCK_SIZE == 0 or arg_cnt == m_arg_cnt)
239 m_superblock[sb_cnt] = arg_position[0];
241 size_type pos_diff = arg_position[(arg_cnt - 1) % SUPER_BLOCK_SIZE] - arg_position[0];
242 if (pos_diff > m_logn4)
244 if (m_longsuperblock ==
nullptr)
246 m_longsuperblock[sb_cnt] =
249 bits::hi(arg_position[(arg_cnt - 1) % SUPER_BLOCK_SIZE]) + 1);
251 for (
size_type j = 0; j <= (arg_cnt - 1) % SUPER_BLOCK_SIZE; ++j)
252 m_longsuperblock[sb_cnt][j] = arg_position[j];
257 for (
size_type j = 0; j <= (arg_cnt - 1) % SUPER_BLOCK_SIZE; j += 64)
259 m_miniblock[sb_cnt][j / 64] = arg_position[j] - arg_position[0];
268template <u
int8_t t_b, u
int8_t t_pat_len>
269void select_support_mcl<t_b, t_pat_len>::init_fast(
bit_vector const * v)
278 const size_type SUPER_BLOCK_SIZE = 64 * 64;
285 size_type sb = (m_arg_cnt + SUPER_BLOCK_SIZE - 1) / SUPER_BLOCK_SIZE;
286 delete[] m_miniblock;
293 uint64_t carry_new = 0;
295 for (
size_type i = 0, cnt_old = 0, cnt_new = 0, last_k64_sum = 1; i < (((v->
bit_size() + 63) >> 6) << 6);
299 cnt_new = std::min(cnt_new,
301 if (cnt_new >= last_k64_sum)
303 arg_position[last_k64 - 1] =
306 last_k64_sum - cnt_old,
311 if (last_k64 == SUPER_BLOCK_SIZE + 1)
313 m_superblock[sb_cnt] = arg_position[0];
314 size_type pos_of_last_arg_in_the_block = arg_position[last_k64 - 65];
316 for (
size_type ii = arg_position[last_k64 - 65] + 1, j = last_k64 - 65;
317 ii < v->
size() and j < SUPER_BLOCK_SIZE;
321 pos_of_last_arg_in_the_block = ii;
324 size_type pos_diff = pos_of_last_arg_in_the_block - arg_position[0];
325 if (pos_diff > m_logn4)
327 if (m_longsuperblock ==
nullptr)
328 m_longsuperblock =
new int_vector<0>[sb + 1];
330 m_longsuperblock[sb_cnt] =
331 int_vector<0>(SUPER_BLOCK_SIZE, 0,
bits::hi(pos_of_last_arg_in_the_block) + 1);
332 for (size_type j = arg_position[0], k = 0;
333 k < SUPER_BLOCK_SIZE and j <= pos_of_last_arg_in_the_block;
337 if (k >= SUPER_BLOCK_SIZE)
339 for (size_type ii = 0; ii < SUPER_BLOCK_SIZE; ++ii)
341 std::cout <<
"(" << ii <<
"," << m_longsuperblock[sb_cnt][ii] <<
") ";
343 std::cout << std::endl;
344 std::cout <<
"k=" << k <<
" SUPER_BLOCK_SIZE=" << SUPER_BLOCK_SIZE << std::endl;
345 std::cout <<
"pos_of_last_arg_in_the_block" << pos_of_last_arg_in_the_block
349 m_longsuperblock[sb_cnt][k++] = j;
355 for (
size_type j = 0; j < SUPER_BLOCK_SIZE; j += 64)
357 m_miniblock[sb_cnt][j / 64] = arg_position[j] - arg_position[0];
369 if (m_longsuperblock ==
nullptr)
372 for (
size_type i = arg_position[0], k = 0; i < v->
size(); ++i)
376 m_longsuperblock[sb_cnt][k++] = i;
383template <u
int8_t t_b, u
int8_t t_pat_len>
386 assert(i > 0 and i <= m_arg_cnt);
391 if (m_longsuperblock !=
nullptr and !m_longsuperblock[sb_idx].
empty())
393 return m_longsuperblock[sb_idx][offset];
397 if ((offset & 0x3F) == 0)
399 assert(sb_idx < m_superblock.size());
400 assert((offset >> 6) < m_miniblock[sb_idx].
size());
401 return m_superblock[sb_idx] + m_miniblock[sb_idx][offset >> 6 ];
405 i = i - (sb_idx << 12) - ((offset >> 6) << 6);
408 size_type pos = m_superblock[sb_idx] + m_miniblock[sb_idx][offset >> 6] + 1;
413 uint64_t
const *
data =
m_v->data() + word_pos;
419 return (word_pos << 6)
425 uint64_t old_carry = carry;
427 while (sum_args + args < i)
430 assert(
data + 1 <
m_v->data() + ((
m_v->bit_size() + 63) >> 6));
435 return (word_pos << 6)
441template <u
int8_t t_b, u
int8_t t_pat_len>
447template <u
int8_t t_b, u
int8_t t_pat_len>
448void select_support_mcl<t_b, t_pat_len>::initData()
453 m_logn = m_logn2 = m_logn4 = 0;
457 m_logn =
bits::hi(((m_v->bit_size() + 63) >> 6) << 6) + 1;
458 m_logn2 = m_logn * m_logn;
459 m_logn4 = m_logn2 * m_logn2;
461 delete[] m_longsuperblock;
462 m_longsuperblock =
nullptr;
463 delete[] m_miniblock;
464 m_miniblock =
nullptr;
467template <u
int8_t t_b, u
int8_t t_pat_len>
473template <u
int8_t t_b, u
int8_t t_pat_len>
480 out.write((
char *)&m_arg_cnt,
sizeof(
size_type) /
sizeof(
char));
481 written_bytes =
sizeof(
size_type) /
sizeof(
char);
487 written_bytes += m_superblock.serialize(out, child,
"superblock");
489 if (m_longsuperblock !=
nullptr)
493 mini_or_long[i] = !m_miniblock[i].
empty();
495 written_bytes += mini_or_long.
serialize(out, child,
"mini_or_long");
499 if (!mini_or_long.
empty() and !mini_or_long[i])
501 written_bytes_long += m_longsuperblock[i].serialize(out);
505 written_bytes_mini += m_miniblock[i].serialize(out);
507 written_bytes += written_bytes_long;
508 written_bytes += written_bytes_mini;
517 return written_bytes;
520template <u
int8_t t_b, u
int8_t t_pat_len>
526 in.read((
char *)&m_arg_cnt,
sizeof(
size_type) /
sizeof(
char));
531 m_superblock.load(in);
533 delete[] m_miniblock;
534 m_miniblock =
nullptr;
535 delete[] m_longsuperblock;
536 m_longsuperblock =
nullptr;
539 mini_or_long.
load(in);
541 if (!mini_or_long.
empty())
545 if (!mini_or_long.
empty() and not mini_or_long[i])
547 m_longsuperblock[i].load(in);
551 m_miniblock[i].load(in);
556template <u
int8_t t_b, u
int8_t t_pat_len>
557template <
typename archive_t>
569 if (m_longsuperblock !=
nullptr)
574 mini_or_long[i] = !m_miniblock[i].
empty();
580 if (!mini_or_long.
empty() and !mini_or_long[i])
592template <u
int8_t t_b, u
int8_t t_pat_len>
593template <
typename archive_t>
596 delete[] m_longsuperblock;
597 m_longsuperblock =
nullptr;
598 delete[] m_miniblock;
599 m_miniblock =
nullptr;
612 delete[] m_miniblock;
613 m_miniblock =
nullptr;
614 delete[] m_longsuperblock;
615 m_longsuperblock =
nullptr;
621 if (!mini_or_long.
empty())
628 if (!mini_or_long.
empty() and !mini_or_long[i])
640template <u
int8_t t_b, u
int8_t t_pat_len>
643 return (m_logn == other.m_logn) && (m_logn2 == other.m_logn2) && (m_logn4 == other.m_logn4)
644 && (m_superblock == other.m_superblock) && (m_arg_cnt == other.m_arg_cnt)
645 && ((m_longsuperblock ==
nullptr && other.m_longsuperblock ==
nullptr)
646 || (*m_longsuperblock == *other.m_longsuperblock))
647 && ((m_miniblock == other.m_miniblock) || (*m_miniblock == *other.m_miniblock));
650template <u
int8_t t_b, u
int8_t t_pat_len>
653 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
A generic vector class for integers of width .
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
bool empty() const noexcept
Equivalent to size() == 0.
int_vector_size_type size_type
size_type bit_size() const noexcept
The number of bits in the int_vector.
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
select_support_mcl< t_b, t_pat_len > & operator=(select_support_mcl &&)
void init_slow(bit_vector const *v=nullptr)
void load(std::istream &in, bit_vector const *v=nullptr)
Load the select_support from an in file stream.
bool operator!=(select_support_mcl const &other) const noexcept
select_support_mcl(bit_vector const *v=nullptr)
select_support_mcl(select_support_mcl< t_b, t_pat_len > &&ss)
bool operator==(select_support_mcl const &other) const noexcept
size_type select(size_type i) const
Select function.
bit_vector bit_vector_type
void set_vector(bit_vector const *v=nullptr)
This method sets the supported bit_vector.
select_support_mcl< t_b, t_pat_len > & operator=(select_support_mcl const &ss)
size_type operator()(size_type i) const
Alias for select(i).
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize the select_support to an out file stream.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
select_support_mcl(select_support_mcl< t_b, t_pat_len > const &ss)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
int_vector< 1 > const * m_v
Pointer to the select supported sdsl::bit_vector.
int_vector< 1 >::size_type size_type
select_support(int_vector< 1 > const *f_v=nullptr)
Constructor of select_support.
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.
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
bool empty(range_type const &r)
Empty range check.
int_vector ::size_type size(range_type const &r)
Size of a range.
excess< T >::impl excess< T >::data
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static uint64_t get_carry(uint64_t)
static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t)
static uint64_t init_carry(uint64_t const *, size_type)
static size_type args_in_the_word(uint64_t, uint64_t &)
static bool found_arg(size_type, bit_vector const &)
static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t)
static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t)
static size_type arg_cnt(bit_vector const &)
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.