9#ifndef INCLUDED_SDSL_RRR_VECTOR
10#define INCLUDED_SDSL_RRR_VECTOR
26template <u
int8_t t_b = 1, u
int16_t t_bs = 15,
class t_rac =
int_vector<>, u
int16_t t_k = 32>
27class rank_support_rrr;
30template <u
int8_t t_b = 1, u
int16_t t_bs = 15,
class t_rac =
int_vector<>, u
int16_t t_k = 32>
31class select_support_rrr;
60template <u
int16_t t_bs = 63,
class t_rac =
int_vector<>, u
int16_t t_k = 32>
63 static_assert(t_bs >= 3 and t_bs <= 256,
"rrr_vector: block size t_bs must be 3 <= t_bs <= 256.");
64 static_assert(t_k > 1,
"rrr_vector: t_k must be > 0.");
116 , m_invert(v.m_invert)
125 *
this = std::move(tmp);
134 m_bt = std::move(v.m_bt);
135 m_btnr = std::move(v.m_btnr);
136 m_btnrp = std::move(v.m_btnrp);
137 m_rank = std::move(v.m_rank);
138 m_invert = std::move(v.m_invert);
160 while (pos + t_bs <= m_size)
175 m_rank =
int_vector<>((bt_array.
size() + t_k - 1) / t_k + ((m_size % (t_k * t_bs)) > 0),
185 btnr_pos = 0, sum_rank = 0;
187 while (pos + t_bs <= m_size)
191 m_btnrp[i / t_k] = btnr_pos;
192 m_rank[i / t_k] = sum_rank;
194 if (i + t_k <= bt_array.
size())
199 if (bt_array[j] > t_bs / 2) ++gt_half_t_bs;
201 if (gt_half_t_bs > (t_k / 2))
203 m_invert[i / t_k] = 1;
204 for (
size_type j = i; j < i + t_k; ++j) { bt_array[j] = t_bs - bt_array[j]; }
218 sum_rank += (invert ? (t_bs - x) : x);
225 btnr_pos += space_for_bt;
232 m_btnrp[i / t_k] = btnr_pos;
233 m_rank[i / t_k] = sum_rank;
234 m_invert[i / t_k] = 0;
239 assert(i == bt_array.
size());
240 sum_rank += invert ? (t_bs - x) : x;
247 btnr_pos += space_for_bt;
248 assert(m_rank.
size() - 1 == ((i + t_k - 1) / t_k));
252 assert(m_rank.
size() - 1 == ((i + t_k - 1) / t_k));
255 m_rank[m_rank.
size() - 1] = sum_rank;
266 uint16_t
bt = m_bt[bt_idx];
268 if (m_invert[sample_pos])
bt = t_bs -
bt;
270 if (
bt == 0 or
bt == t_bs)
275 uint16_t off = i % t_bs;
296 uint16_t
bt = m_bt[bb_idx];
298 size_type eb_idx = (idx + len - 1) / t_bs;
299 if (bb_idx == eb_idx)
301 if (m_invert[sample_pos])
bt = t_bs -
bt;
306 else if (
bt == t_bs and t_bs <= 64)
313 for (
size_type j = sample_pos * t_k; j < bb_idx; ++j)
324 uint16_t b_len = t_bs - bb_off;
325 uint16_t b_len_sum = 0;
327 res |=
get_int(idx, b_len) << b_len_sum;
332 b_len = std::min((uint16_t)len, b_len);
347 written_bytes +=
write_member(m_size, out, child,
"size");
348 written_bytes += m_bt.serialize(out, child,
"bt");
349 written_bytes += m_btnr.
serialize(out, child,
"btnr");
350 written_bytes += m_btnrp.
serialize(out, child,
"btnrp");
351 written_bytes += m_rank.
serialize(out, child,
"rank_samples");
352 written_bytes += m_invert.
serialize(out, child,
"invert");
354 return written_bytes;
368 template <
typename archive_t>
379 template <
typename archive_t>
396 return m_size == v.m_size && m_bt == v.m_bt && m_btnr == v.m_btnr && m_btnrp == v.m_btnrp &&
397 m_rank == v.m_rank && m_invert == v.m_invert;
403template <u
int8_t t_bit_pattern>
428template <u
int8_t t_b, u
int16_t t_bs,
class t_rac, u
int16_t t_k>
429class rank_support_rrr
431 static_assert(t_b == 1u or t_b == 0u,
"rank_support_rrr: bit pattern must be `0` or `1`");
464 assert(m_v !=
nullptr);
465 assert(i <= m_v->
size());
468 size_type btnrp = m_v->m_btnrp[sample_pos];
470 if (sample_pos + 1 < m_v->m_rank.size())
475 else if (diff_rank == (
size_type)t_bs * t_k)
481 const bool inv = m_v->m_invert[sample_pos];
482 for (
size_type j = sample_pos * t_k; j < bt_idx; ++j)
484 uint16_t r = m_v->m_bt[j];
485 rank += (inv ? t_bs - r : r);
488 uint16_t off = i % t_bs;
494 uint16_t bt = inv ? t_bs - m_v->m_bt[bt_idx] : m_v->m_bt[bt_idx];
528 template <
typename archive_t>
532 template <
typename archive_t>
552template <u
int8_t t_b, u
int16_t t_bs,
class t_rac, u
int16_t t_k>
555 static_assert(t_b == 1u or t_b == 0u,
"select_support_rrr: bit pattern must be `0` or `1`");
576 if (m_v->m_rank[m_v->m_rank.size() - 1] < i)
return size();
578 size_type begin = 0, end = m_v->m_rank.size() - 1;
582 while (end - begin > 1)
584 idx = (begin + end) >> 1;
585 rank = m_v->m_rank[idx];
594 rank = m_v->m_rank[begin];
596 size_type diff_rank = m_v->m_rank[end] - rank;
600 return idx * t_bs + i - rank - 1;
603 const bool inv = m_v->m_invert[begin];
605 uint16_t bt = 0, btnrlen = 0;
608 bt = m_v->m_bt[idx++];
609 bt = inv ? t_bs - bt : bt;
620 if ((
size() - m_v->m_rank[m_v->m_rank.size() - 1]) < i) {
return size(); }
622 size_type begin = 0, end = m_v->m_rank.size() - 1;
626 while (end - begin > 1)
628 idx = (begin + end) >> 1;
629 rank = idx * t_bs * t_k - m_v->m_rank[idx];
638 rank = begin * t_bs * t_k - m_v->m_rank[begin];
640 if (m_v->m_rank[end] == m_v->m_rank[begin])
642 return idx * t_bs + i - rank - 1;
644 const bool inv = m_v->m_invert[begin];
646 uint16_t bt = 0, btnrlen = 0;
649 bt = m_v->m_bt[idx++];
650 bt = inv ? t_bs - bt : bt;
656 return (idx - 1) * t_bs + rrr_helper_type::template decode_select_bitpattern<0, 1>(bt, btnr, i - rank);
686 template <
typename archive_t>
690 template <
typename archive_t>
int_vector_size_type size_type
ptrdiff_t difference_type
void load(std::istream &in)
Load the int_vector for a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
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.
Generic iterator for a random access container.
bool operator==(const rank_support_rrr &other) const noexcept
bool operator!=(const rank_support_rrr &other) const noexcept
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Load the data structure from a stream and set the supported vector void load(std::istream &, const bit_vector_type *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
rrr_helper_type::number_type number_type
rank_support_rrr & operator=(const rank_support_rrr &rs)
Serializes the data structure into a stream size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
Standard constructor rank_support_rrr(const bit_vector_type *v=nullptr)
Answers rank queries const size_type rank(size_type i) const
bit_vector_type::rrr_helper_type rrr_helper_type
Returns the size of the original vector const size_type size() const
Set the supported vector void set_vector(const bit_vector_type *v=nullptr)
bit_vector_type::size_type size_type
rrr_vector(const rrr_vector &v)
Loads the data structure from the given istream void load(std::istream &in)
random_access_const_iterator< rrr_vector > iterator
rank_support_rrr< 1, t_bs, t_rac, t_k > rank_1_type
Default constructor rrr_vector()
rank_support_rrr< 0, t_bs, t_rac, t_k > rank_0_type
select_support_rrr< 0, t_bs, t_rac, t_k > select_0_type
bool operator!=(const rrr_vector &v) const
rrr_vector(rrr_vector &&v)
rrr_vector & operator=(const rrr_vector &v)
bool operator==(const rrr_vector &v) const
rrr_helper_type::number_type number_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
bit_vector::difference_type difference_type
rrr_helper< t_bs > rrr_helper_type
bit_vector::size_type size_type
Returns the size of the original bit vector size_type size() const
rrr_vector & operator=(rrr_vector &&v)
Accessing the i th element of the original bit_vector value_type operator[](size_type i) const
select_support_rrr< 1, t_bs, t_rac, t_k > select_1_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Constructor rrr_vector(const bit_vector &bv)
Answers select queries Serializes the data structure into the given ostream size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bit_vector::value_type value_type
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
bit_vector_type::rrr_helper_type rrr_helper_type
void set_vector(const bit_vector_type *v=nullptr)
select_support_rrr(const bit_vector_type *v=nullptr)
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Answers select queries size_type select(size_type i) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
select_support_rrr & operator=(const select_support_rrr &rs)
rrr_helper_type::number_type number_type
const size_type operator()(size_type i) const
bit_vector_type::size_type size_type
bool operator==(const select_support_rrr &other) const noexcept
const size_type size() const
void load(std::istream &, const bit_vector_type *v=nullptr)
bool operator!=(const select_support_rrr &other) const noexcept
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...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word 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, size_type n)
bit_vector::size_type size_type
bit_vector::size_type size_type
static size_type adjust_rank(size_type r, SDSL_UNUSED size_type n)
Class to encode and decode binomial coefficients on the fly.
static void set_bt(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
static uint16_t space_for_bt(uint16_t i)
Returns the space usage in bits of the binary representation of the number .
static uint64_t decode_int(uint16_t k, number_type nr, uint16_t off, uint16_t len)
Decode the len-bit integer starting at position of the block encoded by the pair (k,...
binomial::number_type number_type
The used number type, e.g.
static number_type bin_to_nr(number_type bin)
static uint16_t decode_select(uint16_t k, number_type &nr, uint16_t sel)
static bool decode_bit(uint16_t k, number_type nr, uint16_t off)
Decode the bit at position of the block encoded by the pair (k, nr).
static uint16_t get_bt(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
static number_type decode_btnr(const bit_vector_type &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
static uint16_t decode_popcount(uint16_t k, number_type nr, uint16_t off)
Decode the first off bits bits of the block encoded by the pair (k, nr) and return the set bits.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.