SDSL 3.0.1
Succinct Data Structure Library
|
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time. More...
#include <rank_support_int.hpp>
Public Types | |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
Public Member Functions | |
rank_support_int (const int_vector<> *v=nullptr) | |
Constructor. More... | |
rank_support_int (const rank_support_int &)=default | |
Copy constructor. More... | |
rank_support_int (rank_support_int &&)=default | |
rank_support_int & | operator= (const rank_support_int &)=default |
rank_support_int & | operator= (rank_support_int &&)=default |
virtual | ~rank_support_int () |
Destructor. More... | |
virtual size_type | rank (const size_type i, const value_type v) const =0 |
Answers rank queries for the supported int_vector. More... | |
virtual size_type | operator() (const size_type idx, const value_type v) const =0 |
Alias for rank(idx, v) More... | |
virtual size_type | prefix_rank (const size_type i, const value_type v) const =0 |
Answers rank queries for the supported int_vector. More... | |
virtual size_type | serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0 |
Serializes rank_support_int. More... | |
virtual void | load (std::istream &in, const int_vector<> *v=nullptr)=0 |
Loads the rank_support_int. More... | |
virtual void | set_vector (const int_vector<> *v=nullptr)=0 |
Sets the supported int_vector to the given pointer. More... | |
Static Protected Member Functions | |
template<typename uintX_t > | |
static constexpr uintX_t | bm_rec (const uintX_t w, const uint8_t length, const uint8_t max_length) |
Constructs a bit mask with the pattern w of a given length. More... | |
static std::array< uint64_t, alphabet_size > | generate_mask_array () |
static constexpr uint64_t | mask_prefix (value_type const v, uint64_t const w_even, uint64_t const w_odd) noexcept |
Mask the set prefix positions. More... | |
static constexpr uint64_t | set_positions_prefix (const uint64_t w, const value_type v) noexcept |
Count how often value v or smaller occurs in the word w. More... | |
static constexpr uint64_t | set_positions (const uint64_t w, const value_type v) noexcept |
Count how often value v occurs in the word w. More... | |
template<typename... value_t> | |
static constexpr std::array< uint64_t, sizeof...(value_t)> | word_prefix_rank (const uint64_t word, const size_type bit_pos, const value_t... values) noexcept |
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx. More... | |
static constexpr uint32_t | word_rank (const uint64_t word, const size_type bit_pos, const value_type v) noexcept |
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx. More... | |
static constexpr uint32_t | full_word_prefix_rank (const uint64_t word, const value_type v) noexcept |
Counts the occurrences of v in the word starting at data up to position idx. More... | |
static constexpr uint32_t | full_word_rank (const uint64_t word, const value_type v) noexcept |
Counts the occurrences of v in the word starting at data up to position idx. More... | |
static constexpr uint64_t | extract_word (const uint64_t *data, const size_type word_position) noexcept |
Returns the word a the given word position. More... | |
Protected Attributes | |
const int_vector * | m_v |
Pointer to the rank supported bit_vector. More... | |
Static Protected Attributes | |
static constexpr uint8_t | sigma { alphabet_size } |
static constexpr uint8_t | sigma_bits { ceil_log2(alphabet_size) } |
static constexpr uint8_t | bits_per_word { (64 / sigma_bits) * sigma_bits } |
static constexpr uint64_t | even_mask { bm_rec<uint64_t>(bits::lo_set[sigma_bits], sigma_bits * 2, 64) } |
static constexpr uint64_t | carry_select_mask { bm_rec<uint64_t>(1ULL << sigma_bits, sigma_bits * 2, 64) } |
static const std::array< uint64_t, alphabet_size > | masks = generate_mask_array() |
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.
Definition at line 38 of file rank_support_int.hpp.
typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type |
Definition at line 42 of file rank_support_int.hpp.
typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type |
Definition at line 43 of file rank_support_int.hpp.
|
inline |
Constructor.
v | The supported int_vector. |
Definition at line 87 of file rank_support_int.hpp.
|
default |
Copy constructor.
|
default |
|
inlinevirtual |
Destructor.
Definition at line 99 of file rank_support_int.hpp.
|
inlinestaticconstexprprotected |
Constructs a bit mask with the pattern w of a given length.
It is concatenated until the length of the bitmask reaches max_length.
Definition at line 52 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Returns the word a the given word position.
Definition at line 214 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Counts the occurrences of v in the word starting at data up to position idx.
Definition at line 199 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Counts the occurrences of v in the word starting at data up to position idx.
Cannot be called on v = 0. Call full_word_prefix_rank(data, word_pos, 0) instead.
Definition at line 207 of file rank_support_int.hpp.
|
inlinestaticprotected |
Definition at line 57 of file rank_support_int.hpp.
|
pure virtual |
Loads the rank_support_int.
in | In-Stream to load the rank_support_int data from. |
v | The supported int_vector. |
Implemented in sdsl::rank_support_int_scan< alphabet_size >, and sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >.
|
inlinestaticconstexprprotectednoexcept |
Mask the set prefix positions.
Definition at line 144 of file rank_support_int.hpp.
|
pure virtual |
Alias for rank(idx, v)
Implemented in sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.
|
default |
|
default |
|
pure virtual |
Answers rank queries for the supported int_vector.
i | Argument for the length of the prefix v[0..i-1]. |
v | Argument which value (including smaller values) to count. |
Implemented in sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.
|
pure virtual |
Answers rank queries for the supported int_vector.
i | Argument for the length of the prefix v[0..i-1]. |
v | Argument which value to count. |
Implemented in sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.
|
pure virtual |
Serializes rank_support_int.
out | Out-Stream to serialize the data to. |
Implemented in sdsl::rank_support_int_scan< alphabet_size >, and sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >.
|
inlinestaticconstexprprotectednoexcept |
Count how often value v occurs in the word w.
Cannot be called on v = 0. Call set_positions_prefix(w, 0) instead.
Definition at line 165 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Count how often value v or smaller occurs in the word w.
Definition at line 155 of file rank_support_int.hpp.
|
pure virtual |
Sets the supported int_vector to the given pointer.
v | The new int_vector to support. |
Implemented in sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.
|
inlinestaticconstexprprotectednoexcept |
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.
Definition at line 178 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.
Cannot be called on v = 0. Call word_prefix_rank(data, idx, 0) instead.
Definition at line 193 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 76 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 78 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 77 of file rank_support_int.hpp.
|
protected |
Pointer to the rank supported bit_vector.
Definition at line 81 of file rank_support_int.hpp.
|
staticprotected |
Definition at line 79 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 74 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 75 of file rank_support_int.hpp.