9#ifndef INCLUDED_SDSL_RRR_VECTOR_15
10#define INCLUDED_SDSL_RRR_VECTOR_15
32template <
typename T =
void>
42 static const int n = 15;
43 static const int MAX_SIZE = 32;
44 uint8_t m_space_for_bt[16];
45 uint8_t m_space_for_bt_pair[256];
46 uint64_t m_C[MAX_SIZE];
52 m_nr_to_bin.
resize(1 << n);
53 m_bin_to_nr.
resize(1 << n);
54 for (
int i = 0, cnt = 0, class_cnt = 0; i <= n; ++i)
58 std::vector<bool> b(n, 0);
59 for (
int j = 0; j < i; ++j) b[n - j - 1] = 1;
62 for (
int k = 0; k < n; ++k) x |= ((uint32_t)b[n - k - 1]) << (n - 1 - k);
64 m_bin_to_nr[x] = class_cnt;
67 }
while (next_permutation(b.begin(), b.end()));
69 m_space_for_bt[i] = 0;
71 m_space_for_bt[i] =
bits::hi(class_cnt) + 1;
75 for (
int x = 0; x < 256; ++x)
77 m_space_for_bt_pair[x] = m_space_for_bt[x >> 4] + m_space_for_bt[x & 0x0F];
84 static inline uint8_t
space_for_bt(uint32_t i) {
return iii.m_space_for_bt[i]; }
86 static inline uint32_t
nr_to_bin(uint8_t k, uint32_t nr) {
return iii.m_nr_to_bin[iii.m_C[k] + nr]; }
88 static inline uint32_t
bin_to_nr(uint32_t bin) {
return iii.m_bin_to_nr[bin]; }
95typename binomial15_impl<T>::impl binomial15_impl<T>::iii;
111template <
class t_rac, u
int16_t t_k>
173 *
this = std::move(tmp);
184 m_bt = std::move(v.m_bt);
185 m_btnr = std::move(v.m_btnr);
186 m_btnrp = std::move(v.m_btnrp);
187 m_rank = std::move(v.m_rank);
211 btnr_pos += bi_type::space_for_bt(x);
218 btnr_pos += bi_type::space_for_bt(x);
233 btnr_pos = 0, sum_rank = 0;
238 m_btnrp[i / t_k] = btnr_pos;
239 m_rank[i / t_k] = sum_rank;
241 uint16_t space_for_bt = bi_type::space_for_bt(x = bt_array[i++]);
247 btnr_pos += space_for_bt;
254 m_btnrp[i / t_k] = btnr_pos;
255 m_rank[i / t_k] = sum_rank;
257 uint16_t space_for_bt = bi_type::space_for_bt(x = bt_array[i++]);
261 m_btnr.
set_int(btnr_pos, bi_type::bin_to_nr(bv.
get_int(pos, m_size - pos)), space_for_bt);
263 btnr_pos += space_for_bt;
264 assert(m_rank.
size() - 1 == ((i + t_k - 1) / t_k));
268 assert(m_rank.
size() - 1 == ((i + t_k - 1) / t_k));
271 m_rank[m_rank.
size() - 1] = sum_rank;
272 m_bt =
rac_type(std::move(bt_array));
282 uint8_t *
bt = (uint8_t *)(m_bt.data());
283 uint32_t i_bt = *(
bt + (bt_idx / 2));
284 if (bt_idx % 2 == 1) { i_bt >>= 4; }
289 if (i_bt == 0 or i_bt ==
block_size) {
return i_bt > 0; }
294 if (j % 2 == 1 and j < bt_idx)
296 btnrp += bi_type::space_for_bt((*
bt++) >> 4);
299 while (j + 1 < bt_idx)
301 btnrp += bi_type::space_for_bt_pair(*(
bt++));
304 if (j < bt_idx) { btnrp += bi_type::space_for_bt((*
bt) & 0x0F); }
306 uint32_t
btnr = m_btnr.
get_int(btnrp, bi_type::space_for_bt(i_bt));
309 return (bi_type::nr_to_bin(i_bt,
btnr) >> off) & (uint32_t)1;
325 uint16_t
bt = m_bt[bb_idx];
328 if (bb_idx == eb_idx)
341 for (
size_type j = sample_pos * t_k; j < bb_idx; ++j) { btnrp += bi_type::space_for_bt(m_bt[j]); }
342 uint32_t
btnr = m_btnr.
get_int(btnrp, bi_type::space_for_bt(
bt));
349 uint8_t b_len_sum = 0;
351 res |=
get_int(idx, b_len) << b_len_sum;
356 b_len = std::min(len, b_len);
370 written_bytes +=
write_member(m_size, out, child,
"size");
371 written_bytes += m_bt.serialize(out, child,
"bt");
372 written_bytes += m_btnr.
serialize(out, child,
"btnr");
373 written_bytes += m_btnrp.
serialize(out, child,
"btnrp");
374 written_bytes += m_rank.
serialize(out, child,
"rank_samples");
376 return written_bytes;
389 template <
typename archive_t>
399 template <
typename archive_t>
415 return m_size == v.m_size && m_bt == v.m_bt && m_btnr == v.m_btnr && m_btnrp == v.m_btnrp && m_rank == v.m_rank;
424template <u
int8_t t_b,
class t_rac, u
int16_t t_k>
427 static_assert(t_b == 1u or t_b == 0u,
"rank_support_rrr: bit pattern must be `0` or `1`");
464 size_type btnrp = m_v->m_btnrp[sample_pos];
466 if (sample_pos + 1 < m_v->m_rank.size())
476 uint8_t * bt = (uint8_t *)(m_v->m_bt.data());
478 uint8_t last_bt = *(bt + (bt_idx / 2));
479 if (bt_idx % 2 == 1) { last_bt >>= 4; }
486 if (last_bt == 0 or last_bt == 15)
490 bt_idx = bt_idx << 2;
493 const uint64_t * bt64 = m_v->m_bt.data() + (j >> 6);
494 uint8_t bt64_off = j & 0x3F;
495 const uint64_t * bt64_end = m_v->m_bt.data() + (bt_idx >> 6);
496 uint8_t bt64_end_off = bt_idx & 0x3F;
498 if (bt64 == bt64_end)
500 uint64_t w = ((*bt64) >> bt64_off) &
bits::lo_set[bt64_end_off - bt64_off];
501 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
502 rank += ((0x0101010101010101ull * w) >> 56);
506 uint64_t w = ((*bt64) >> bt64_off);
507 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
508 rank += ((0x0101010101010101ull * w) >> 56);
509 while ((++bt64) != bt64_end)
512 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
513 rank += ((0x0101010101010101ull * w) >> 56);
516 if (bt64_end_off > 0)
518 w = *bt64 << (64 - bt64_end_off);
519 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
520 rank += ((0x0101010101010101ull * w) >> 56);
527 if (j % 2 == 1 and j < bt_idx)
529 const uint8_t r = (*bt++) >> 4;
531 btnrp += bi_type::space_for_bt(r);
534 while (j + 1 < bt_idx)
536 const uint8_t r = *(bt++);
537 rank += (r >> 4) + (r & 0x0F);
538 btnrp += bi_type::space_for_bt_pair(r);
543 const uint8_t r = (*bt);
545 btnrp += bi_type::space_for_bt(r & 0x0F);
554 uint32_t btnr = m_v->m_btnr.get_int(btnrp, bi_type::space_for_bt(last_bt));
587 template <
typename archive_t>
591 template <
typename archive_t>
601template <u
int8_t t_b,
class t_rac, u
int16_t t_k>
604 static_assert(t_b == 1u or t_b == 0u,
"select_support_rrr: bit pattern must be `0` or `1`");
625 if (m_v->m_rank[m_v->m_rank.size() - 1] < i)
return size();
627 size_type begin = 0, end = m_v->m_rank.size() - 1;
631 while (end - begin > 1)
633 idx = (begin + end) >> 1;
634 rank = m_v->m_rank[idx];
643 rank = m_v->m_rank[begin];
645 size_type diff_rank = m_v->m_rank[end] - rank;
651 uint8_t bt = 0, s = 0;
654 bt = m_v->m_bt[idx++];
656 btnrp += (s = bi_type::space_for_bt(bt));
659 uint32_t btnr = m_v->m_btnr.get_int(btnrp - s, s);
666 if ((
size() - m_v->m_rank[m_v->m_rank.size() - 1]) < i)
return size();
668 size_type begin = 0, end = m_v->m_rank.size() - 1;
672 while (end - begin > 1)
674 idx = (begin + end) >> 1;
686 if (m_v->m_rank[end] == m_v->m_rank[begin])
691 uint8_t bt = 0, s = 0;
694 bt = m_v->m_bt[idx++];
696 btnrp += (s = bi_type::space_for_bt(bt));
699 uint32_t btnr = m_v->m_btnr.get_int(btnrp - s, s);
730 template <
typename archive_t>
734 template <
typename archive_t>
static uint32_t bin_to_nr(uint32_t bin)
static uint8_t space_for_bt_pair(uint8_t x)
static uint8_t space_for_bt(uint32_t i)
static uint32_t nr_to_bin(uint8_t k, uint32_t nr)
value_type get_int(size_type idx, const uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx in the int_vector.
int_vector_size_type size_type
ptrdiff_t difference_type
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.
int_vector_trait< t_width >::value_type value_type
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.
void set_int(size_type idx, value_type x, const uint8_t len=64)
Set the bits from position idx to idx+len-1 to the binary representation of integer x.
Generic iterator for a random access container.
rank_support_rrr(const bit_vector_type *v=nullptr)
Standard constructor.
rrr_vector< 15, t_rac, t_k > bit_vector_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into a stream.
const size_type rank(size_type i) const
Answers rank queries.
rank_support_rrr & operator=(const rank_support_rrr &rs)
const size_type operator()(size_type i) const
Short hand for rank(i)
const size_type size() const
Returns the size of the original vector.
void set_vector(const bit_vector_type *v=nullptr)
Set the supported vector.
bool operator!=(const rank_support_rrr &other) const noexcept
bit_vector_type::size_type size_type
bool operator==(const rank_support_rrr &other) const noexcept
void load(std::istream &, const bit_vector_type *v=nullptr)
Load the data structure from a stream and set the supported vector.
bit_vector_type::bi_type bi_type
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Answers rank queries const size_type rank(size_type i) const
Set the supported vector void set_vector(const bit_vector_type *v=nullptr)
A specialization of the rrr_vector class for a block_size of 15.
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
bit_vector::difference_type difference_type
uint64_t get_int(size_type idx, uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
rrr_vector & operator=(rrr_vector &&v)
Move assignment.
select_support_rrr< 0, 15, t_rac, t_k > select_0_type
rrr_vector(const rrr_vector &v)
Copy constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
bit_vector::value_type value_type
rank_support_rrr< 0, 15, t_rac, t_k > rank_0_type
random_access_const_iterator< rrr_vector > iterator
void load(std::istream &in)
Loads the data structure from the given istream.
rrr_vector & operator=(const rrr_vector &v)
Assignment operator.
rank_support_rrr< 1, 15, t_rac, t_k > rank_1_type
rrr_vector(const bit_vector &bv)
Constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
bit_vector::size_type size_type
rrr_vector()
Default constructor.
select_support_rrr< 1, 15, t_rac, t_k > select_1_type
bool operator==(const rrr_vector &v) const
size_type size() const
Returns the size of the original bit vector.
bool operator!=(const rrr_vector &v) const
rrr_vector(rrr_vector &&v)
Move constructor.
random_access_const_iterator< rrr_vector > iterator
Returns the size of the original bit vector size_type size() const
Get the integer value of the binary string of length len starting at position idx uint64_t get_int(size_type idx, uint8_t len=64) const
size_type select(size_type i) const
Answers select queries.
rrr_vector< 15, t_rac, t_k > bit_vector_type
bit_vector_type::size_type size_type
const size_type size() const
select_support_rrr & operator=(const select_support_rrr &rs)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
bool operator==(const select_support_rrr &other) const noexcept
bool operator!=(const select_support_rrr &other) const noexcept
bit_vector_type::bi_type bi_type
const size_type operator()(size_type i) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
void set_vector(const bit_vector_type *v=nullptr)
select_support_rrr(const bit_vector_type *v=nullptr)
void load(std::istream &, const bit_vector_type *v=nullptr)
void set_vector(const bit_vector_type *v=nullptr)
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Answers select queries size_type select(size_type i) const
bit_vector_type::size_type size_type
const size_type size() const
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.
rrr_helper.hpp contains the sdsl::binomial struct, a struct which contains informations about the bin...
rrr_vector.hpp contains the sdsl::rrr_vector class, and classes which support rank and select for rrr...
static constexpr uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
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.
static size_type adjust_rank(size_type r, SDSL_UNUSED size_type n)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.