8 #ifndef INCLUDED_SDSL_SELECT_SUPPORT_MCL
9 #define INCLUDED_SDSL_SELECT_SUPPORT_MCL
54 template <u
int8_t t_b = 1, u
int8_t t_pat_len = 1>
58 static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
59 "select_support_mcl: bit pattern must be `0`,`1`,`10`, `01`, or `11`");
60 static_assert(t_pat_len == 1u or t_pat_len == 2u,
"select_support_mcl: bit pattern length must be 1 or 2");
83 void init_fast(
const bit_vector * v =
nullptr);
100 template <
typename archive_t>
103 template <
typename archive_t>
111 template <u
int8_t t_b, u
int8_t t_pat_len>
115 if (t_pat_len > 1 or (
vv !=
nullptr and
vv->
size() < 100000))
122 template <u
int8_t t_b, u
int8_t t_pat_len>
126 , m_logn2(ss.m_logn2)
127 , m_logn4(ss.m_logn4)
128 , m_superblock(ss.m_superblock)
129 , m_arg_cnt(ss.m_arg_cnt)
132 if (ss.m_longsuperblock !=
nullptr)
135 for (
size_type i = 0; i < sb; ++i) { m_longsuperblock[i] = ss.m_longsuperblock[i]; }
137 m_miniblock =
nullptr;
138 if (ss.m_miniblock !=
nullptr)
141 for (
size_type i = 0; i < sb; ++i) { m_miniblock[i] = ss.m_miniblock[i]; }
145 template <u
int8_t t_b, u
int8_t t_pat_len>
149 *
this = std::move(ss);
152 template <u
int8_t t_b, u
int8_t t_pat_len>
158 *
this = std::move(tmp);
163 template <u
int8_t t_b, u
int8_t t_pat_len>
169 m_logn2 = ss.m_logn2;
170 m_logn4 = ss.m_logn4;
171 m_superblock = std::move(ss.m_superblock);
172 m_arg_cnt = ss.m_arg_cnt;
175 delete[] m_longsuperblock;
176 m_longsuperblock = ss.m_longsuperblock;
177 ss.m_longsuperblock =
nullptr;
179 delete[] m_miniblock;
180 m_miniblock = ss.m_miniblock;
181 ss.m_miniblock =
nullptr;
186 template <u
int8_t t_b, u
int8_t t_pat_len>
189 delete[] m_longsuperblock;
190 delete[] m_miniblock;
193 template <u
int8_t t_b, u
int8_t t_pat_len>
198 if (m_v ==
nullptr)
return;
207 size_type sb = (m_arg_cnt + SUPER_BLOCK_SIZE - 1) / SUPER_BLOCK_SIZE;
208 delete[] m_miniblock;
213 size_type arg_position[SUPER_BLOCK_SIZE], arg_cnt = 0;
219 arg_position[arg_cnt % SUPER_BLOCK_SIZE] = i;
220 assert(arg_position[arg_cnt % SUPER_BLOCK_SIZE] == i);
222 if (arg_cnt % SUPER_BLOCK_SIZE == 0 or arg_cnt == m_arg_cnt)
225 m_superblock[sb_cnt] = arg_position[0];
227 size_type pos_diff = arg_position[(arg_cnt - 1) % SUPER_BLOCK_SIZE] - arg_position[0];
228 if (pos_diff > m_logn4)
230 if (m_longsuperblock ==
nullptr) m_longsuperblock =
new int_vector<0>[sb];
233 bits::hi(arg_position[(arg_cnt - 1) % SUPER_BLOCK_SIZE]) +
236 for (
size_type j = 0; j <= (arg_cnt - 1) % SUPER_BLOCK_SIZE; ++j)
237 m_longsuperblock[sb_cnt][j] = arg_position[j];
242 for (
size_type j = 0; j <= (arg_cnt - 1) % SUPER_BLOCK_SIZE; j += 64)
244 m_miniblock[sb_cnt][j / 64] = arg_position[j] - arg_position[0];
253 template <u
int8_t t_b, u
int8_t t_pat_len>
258 if (m_v ==
nullptr)
return;
262 const size_type SUPER_BLOCK_SIZE = 64 * 64;
269 size_type sb = (m_arg_cnt + SUPER_BLOCK_SIZE - 1) / SUPER_BLOCK_SIZE;
270 delete[] m_miniblock;
276 const uint64_t * data = v->
data();
277 uint64_t carry_new = 0;
279 for (
size_type i = 0, cnt_old = 0, cnt_new = 0, last_k64_sum = 1; i < (((v->
bit_size() + 63) >> 6) << 6);
283 cnt_new = std::min(cnt_new,
285 if (cnt_new >= last_k64_sum)
289 last_k64_sum - cnt_old,
294 if (last_k64 == SUPER_BLOCK_SIZE + 1)
296 m_superblock[sb_cnt] = arg_position[0];
297 size_type pos_of_last_arg_in_the_block = arg_position[last_k64 - 65];
299 for (
size_type ii = arg_position[last_k64 - 65] + 1, j = last_k64 - 65;
300 ii < v->
size() and j < SUPER_BLOCK_SIZE;
304 pos_of_last_arg_in_the_block = ii;
307 size_type pos_diff = pos_of_last_arg_in_the_block - arg_position[0];
308 if (pos_diff > m_logn4)
310 if (m_longsuperblock ==
nullptr)
311 m_longsuperblock =
new int_vector<0>[sb + 1];
313 m_longsuperblock[sb_cnt] = int_vector<0>(SUPER_BLOCK_SIZE,
315 bits::hi(pos_of_last_arg_in_the_block) + 1);
316 for (
size_type j = arg_position[0], k = 0;
317 k < SUPER_BLOCK_SIZE and j <= pos_of_last_arg_in_the_block;
321 if (k >= SUPER_BLOCK_SIZE)
323 for (
size_type ii = 0; ii < SUPER_BLOCK_SIZE; ++ii)
325 std::cout <<
"(" << ii <<
"," << m_longsuperblock[sb_cnt][ii] <<
") ";
327 std::cout << std::endl;
328 std::cout <<
"k=" << k <<
" SUPER_BLOCK_SIZE=" << SUPER_BLOCK_SIZE << std::endl;
329 std::cout <<
"pos_of_last_arg_in_the_block" << pos_of_last_arg_in_the_block
333 m_longsuperblock[sb_cnt][k++] = j;
338 m_miniblock[sb_cnt] = int_vector<0>(64, 0,
bits::hi(pos_diff) + 1);
339 for (
size_type j = 0; j < SUPER_BLOCK_SIZE; j += 64)
341 m_miniblock[sb_cnt][j / 64] = arg_position[j] - arg_position[0];
353 if (m_longsuperblock ==
nullptr) m_longsuperblock =
new int_vector<0>[sb + 1];
354 m_longsuperblock[sb_cnt] = int_vector<0>(SUPER_BLOCK_SIZE, 0,
bits::hi(v->
size() - 1) + 1);
355 for (
size_type i = arg_position[0], k = 0; i < v->
size(); ++i)
363 template <u
int8_t t_b, u
int8_t t_pat_len>
366 assert(i > 0 and i <= m_arg_cnt);
371 if (m_longsuperblock !=
nullptr and !m_longsuperblock[sb_idx].
empty()) {
return m_longsuperblock[sb_idx][offset]; }
374 if ((offset & 0x3F) == 0)
376 assert(sb_idx < m_superblock.size());
377 assert((offset >> 6) < m_miniblock[sb_idx].
size());
378 return m_superblock[sb_idx] + m_miniblock[sb_idx][offset >> 6 ];
382 i = i - (sb_idx << 12) - ((offset >> 6) << 6);
385 size_type pos = m_superblock[sb_idx] + m_miniblock[sb_idx][offset >> 6] + 1;
390 const uint64_t * data = m_v->data() + word_pos;
396 return (word_pos << 6) +
402 uint64_t old_carry = carry;
404 while (sum_args + args < i)
407 assert(data + 1 < m_v->data() + ((m_v->bit_size() + 63) >> 6));
412 return (word_pos << 6) +
418 template <u
int8_t t_b, u
int8_t t_pat_len>
424 template <u
int8_t t_b, u
int8_t t_pat_len>
428 if (
nullptr == m_v) { m_logn = m_logn2 = m_logn4 = 0; }
431 m_logn =
bits::hi(((m_v->bit_size() + 63) >> 6) << 6) + 1;
432 m_logn2 = m_logn * m_logn;
433 m_logn4 = m_logn2 * m_logn2;
435 delete[] m_longsuperblock;
436 m_longsuperblock =
nullptr;
437 delete[] m_miniblock;
438 m_miniblock =
nullptr;
441 template <u
int8_t t_b, u
int8_t t_pat_len>
447 template <u
int8_t t_b, u
int8_t t_pat_len>
454 out.write((
char *)&m_arg_cnt,
sizeof(
size_type) /
sizeof(
char));
455 written_bytes =
sizeof(
size_type) /
sizeof(
char);
461 written_bytes += m_superblock.serialize(out, child,
"superblock");
463 if (m_longsuperblock !=
nullptr)
466 for (
size_type i = 0; i < sb; ++i) mini_or_long[i] = !m_miniblock[i].
empty();
468 written_bytes += mini_or_long.
serialize(out, child,
"mini_or_long");
472 if (!mini_or_long.
empty() and !mini_or_long[i])
474 written_bytes_long += m_longsuperblock[i].serialize(out);
478 written_bytes_mini += m_miniblock[i].serialize(out);
480 written_bytes += written_bytes_long;
481 written_bytes += written_bytes_mini;
483 child,
"longsuperblock", util::class_name(m_longsuperblock));
486 child,
"minisuperblock", util::class_name(m_miniblock));
490 return written_bytes;
493 template <u
int8_t t_b, u
int8_t t_pat_len>
499 in.read((
char *)&m_arg_cnt,
sizeof(
size_type) /
sizeof(
char));
504 m_superblock.load(in);
506 delete[] m_miniblock;
507 m_miniblock =
nullptr;
508 delete[] m_longsuperblock;
509 m_longsuperblock =
nullptr;
512 mini_or_long.
load(in);
517 if (!mini_or_long.
empty() and not mini_or_long[i]) { m_longsuperblock[i].
load(in); }
520 m_miniblock[i].load(in);
525 template <u
int8_t t_b, u
int8_t t_pat_len>
526 template <
typename archive_t>
538 if (m_longsuperblock !=
nullptr)
541 for (
size_type i = 0; i < sb; ++i) { mini_or_long[i] = !m_miniblock[i].
empty(); }
546 if (!mini_or_long.
empty() and !mini_or_long[i]) { ar(
CEREAL_NVP(m_longsuperblock[i])); }
555 template <u
int8_t t_b, u
int8_t t_pat_len>
556 template <
typename archive_t>
559 delete[] m_longsuperblock;
560 m_longsuperblock =
nullptr;
561 delete[] m_miniblock;
562 m_miniblock =
nullptr;
575 delete[] m_miniblock;
576 m_miniblock =
nullptr;
577 delete[] m_longsuperblock;
578 m_longsuperblock =
nullptr;
588 if (!mini_or_long.
empty() and !mini_or_long[i]) { ar(
CEREAL_NVP(m_longsuperblock[i])); }
597 template <u
int8_t t_b, u
int8_t t_pat_len>
600 return (m_logn == other.m_logn) && (m_logn2 == other.m_logn2) && (m_logn4 == other.m_logn4) &&
601 (m_superblock == other.m_superblock) && (m_arg_cnt == other.m_arg_cnt) &&
602 ((m_longsuperblock ==
nullptr && other.m_longsuperblock ==
nullptr) ||
603 (*m_longsuperblock == *other.m_longsuperblock)) &&
604 ((m_miniblock == other.m_miniblock) || (*m_miniblock == *other.m_miniblock));
607 template <u
int8_t t_b, u
int8_t t_pat_len>
610 return !(*
this == other);
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.
const uint64_t * data() const noexcept
Pointer to the raw data of 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.
A class supporting constant time select queries.
select_support_mcl< t_b, t_pat_len > & operator=(select_support_mcl &&)
void init_slow(const bit_vector *v=nullptr)
select_support_mcl(select_support_mcl< t_b, t_pat_len > &&ss)
size_type select(size_type i) const
Select function.
bool operator==(const select_support_mcl &other) const noexcept
void load(std::istream &in, const bit_vector *v=nullptr)
Load the select_support from an in file stream.
bit_vector bit_vector_type
bool operator!=(const select_support_mcl &other) const noexcept
select_support_mcl(const bit_vector *v=nullptr)
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.
select_support_mcl(const select_support_mcl< t_b, t_pat_len > &ss)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
select_support_mcl< t_b, t_pat_len > & operator=(const select_support_mcl &ss)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
void set_vector(const bit_vector *v=nullptr)
This method sets the supported bit_vector.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
int_vector< 1 >::size_type size_type
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.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
bool empty(const range_type &r)
Empty range check.
int_vector ::size_type size(const range_type &r)
Size of a range.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static SDSL_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 size_type args_in_the_word(uint64_t, uint64_t &)
static uint64_t init_carry(const uint64_t *, size_type)
static bool found_arg(size_type, const bit_vector &)
static size_type arg_cnt(const bit_vector &)
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)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.