8#ifndef INCLUDED_SDSL_RANK_SUPPORT_VFIVE
9#define INCLUDED_SDSL_RANK_SUPPORT_VFIVE
43template <u
int8_t t_b = 1, u
int8_t t_pat_len = 1>
47 static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
48 "rank_support_v5: bit pattern must be `0`,`1`,`10` or `01` or `11`");
49 static_assert(t_pat_len == 1u or t_pat_len == 2u,
"rank_support_v5: bit pattern length must be 1 or 2");
80 size_type basic_block_size = (((v->bit_size() + 63) >> 11) + 1) << 1;
81 m_basic_block.
resize(basic_block_size);
82 if (m_basic_block.
empty())
84 uint64_t
const * data =
m_v->
data();
86 m_basic_block[0] = m_basic_block[1] = 0;
90 uint64_t second_level_cnt = 0;
91 uint64_t cnt_words = 1;
92 for (i = 1; i < ((
m_v->
bit_size() + 63) >> 6); ++i, ++cnt_words)
97 m_basic_block[j - 1] = second_level_cnt;
98 m_basic_block[j] = m_basic_block[j - 2] + sum;
99 second_level_cnt = sum = cnt_words = 0;
101 else if ((cnt_words % 6) == 0)
104 second_level_cnt |= sum << (60 - 12 * (cnt_words / 6));
109 if ((cnt_words % 6) == 0)
111 second_level_cnt |= sum << (60 - 12 * (cnt_words / 6));
116 m_basic_block[j - 1] = second_level_cnt;
117 m_basic_block[j] = m_basic_block[j - 2] + sum;
118 m_basic_block[j + 1] = 0;
122 m_basic_block[j + 1] = second_level_cnt;
133 assert(
m_v !=
nullptr);
134 assert(idx <= m_v->
size());
135 uint64_t
const * p = m_basic_block.
data() + ((idx >> 10) & 0xFFFFFFFFFFFFFFFEULL);
137 size_type result = *p + ((*(p + 1) >> (60 - 12 * ((idx & 0x7FF) / (64 * 6)))) & 0x7FFULL)
140 uint8_t to_do = ((idx >> 6) & 0x1FULL) % 6;
164 written_bytes += m_basic_block.
serialize(out, child,
"cumulative_counts");
166 return written_bytes;
172 m_basic_block.
load(in);
175 template <
typename archive_t>
181 template <
typename archive_t>
189 return m_basic_block == other.m_basic_block;
194 return !(*
this == other);
cereal.hpp offers cereal support
bool empty() const noexcept
Equivalent to size() == 0.
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.
void resize(const size_type size)
Resize the int_vector in terms of elements.
uint64_t const * data() const noexcept
Pointer to the raw data of 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.
size_type bit_size() const noexcept
The number of bits in the int_vector.
A class supporting rank queries in constant time.
bool operator!=(rank_support_v5 const &other) const noexcept
rank_support_trait< t_b, t_pat_len > trait_type
rank_support_v5 & operator=(rank_support_v5 const &)=default
void load(std::istream &in, bit_vector const *v=nullptr)
Loads the rank_support.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes rank_support.
rank_support_v5(bit_vector const *v=nullptr)
size_type rank(size_type idx) const
Answers rank queries for the supported bit_vector.
bool operator==(rank_support_v5 const &other) const noexcept
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
void set_vector(bit_vector const *v=nullptr)
Sets the supported bit_vector to the given pointer.
bit_vector bit_vector_type
rank_support_v5 & operator=(rank_support_v5 &&)=default
rank_support_v5(rank_support_v5 &&)=default
size_type operator()(size_type idx) const
Alias for rank(i)
rank_support_v5(rank_support_v5 const &)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time.
bit_vector const * m_v
Pointer to the rank supported bit_vector.
bit_vector::size_type size_type
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.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
static uint32_t word_rank(uint64_t const *, size_type)
static uint32_t full_word_rank(uint64_t const *, size_type)
static uint64_t init_carry()
static size_type args_in_the_word(uint64_t, uint64_t &)
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.