SDSL 3.0.3
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 (int_vector<> const *v=nullptr) | |
Constructor. | |
rank_support_int (rank_support_int const &)=default | |
Copy constructor. | |
rank_support_int (rank_support_int &&)=default | |
rank_support_int & | operator= (rank_support_int const &)=default |
rank_support_int & | operator= (rank_support_int &&)=default |
virtual | ~rank_support_int () |
Destructor. | |
virtual size_type | rank (const size_type i, const value_type v) const =0 |
Answers rank queries for the supported int_vector. | |
virtual size_type | operator() (const size_type idx, const value_type v) const =0 |
Alias for rank(idx, v) | |
virtual size_type | prefix_rank (const size_type i, const value_type v) const =0 |
Answers rank queries for the supported int_vector. | |
virtual size_type | serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0 |
Serializes rank_support_int. | |
virtual void | load (std::istream &in, int_vector<> const *v=nullptr)=0 |
Loads the rank_support_int. | |
virtual void | set_vector (int_vector<> const *v=nullptr)=0 |
Sets the supported int_vector to the given pointer. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
static constexpr uint64_t | extract_word (uint64_t const *data, const size_type word_position) noexcept |
Returns the word a the given word position. | |
Protected Attributes | |
int_vector const * | m_v |
Pointer to the rank supported bit_vector. | |
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 50 of file rank_support_int.hpp.
typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type |
Definition at line 54 of file rank_support_int.hpp.
typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type |
Definition at line 55 of file rank_support_int.hpp.
|
inline |
Constructor.
v | The supported int_vector. |
Definition at line 101 of file rank_support_int.hpp.
|
default |
Copy constructor.
|
default |
|
inlinevirtual |
Destructor.
Definition at line 113 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 64 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Returns the word a the given word position.
Definition at line 228 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 213 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 221 of file rank_support_int.hpp.
|
inlinestaticprotected |
Definition at line 69 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 159 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 180 of file rank_support_int.hpp.
|
inlinestaticconstexprprotectednoexcept |
Count how often value v or smaller occurs in the word w.
Definition at line 170 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 194 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 207 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 90 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 92 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 91 of file rank_support_int.hpp.
|
protected |
Pointer to the rank supported bit_vector.
Definition at line 95 of file rank_support_int.hpp.
|
staticprotected |
Definition at line 93 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 88 of file rank_support_int.hpp.
|
staticconstexprprotected |
Definition at line 89 of file rank_support_int.hpp.