SDSL 3.0.1
Succinct Data Structure Library
|
Stores a superblock entry in a cache friendly pattern. More...
#include <rank_support_int_v.hpp>
Public Types | |
using | size_type = typename base_t::size_type |
using | block_value_type = std::conditional_t< bits_per_block_value<=8, uint8_t, std::conditional_t< bits_per_block_value<=16, uint16_t, uint32_t > > |
The smallest integer type needed to store the block ranks. More... | |
Public Member Functions | |
template<bool compute_prefix_delta> | |
constexpr size_type | superblock_rank (value_type const v) const noexcept |
Returns the rank value from the superblock. More... | |
template<bool compute_prefix_delta> | |
constexpr size_type | block_rank (size_t const position, value_type const v) const noexcept |
Returns the rank value from the block. More... | |
template<bool compute_prefix_delta> | |
constexpr size_type | in_block_rank (size_t const position, value_type const v) const noexcept |
Returns the rank value from the in-block query. More... | |
value_type | value_at (size_type position) const noexcept |
Extracts the value at the given position. More... | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const |
Saves to the stream. More... | |
void | load (std::istream &in) |
Loads from the stream. More... | |
template<typename archive_t > | |
void | CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const |
Saves to the archive. More... | |
template<typename archive_t > | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Loads from the archive. More... | |
Public Attributes | |
std::array< uint64_t,(alphabet_size - 1)> | superblocks |
The array storing the super block values. More... | |
std::array< block_value_type,(blocks_per_superblock - 1) *(alphabet_size - 1)> | blocks |
The array storing the block values. More... | |
std::array< detail::bit_compressed_word< uint8_t, sigma_bits >, words_per_superblock > | superblock_text |
The array storing the bit compressed text. More... | |
Static Public Attributes | |
static constexpr size_t | block_offset = effective_alphabet_size |
The offset used to jump to the correct block position. More... | |
static constexpr size_t | bits_per_block_value = ceil_log2(values_per_superblock) |
How many bits needed to store the block ranks. More... | |
Friends | |
bool | operator== (superblock_entry const &lhs, superblock_entry const &rhs) noexcept |
Equality operator. More... | |
bool | operator!= (superblock_entry const &lhs, superblock_entry const &rhs) noexcept |
Inequality operator. More... | |
Stores a superblock entry in a cache friendly pattern.
One superblock entry represents one superblock in the rank support structure. The text is stored efficiently in a sdsl::detail::bit_compressed_word. The superblock array stores a rank count for sigma - 1
many values. The block array stores a rank count for blocks_per_superblock - 1
many blocks times sigma - 1
for every symbol of the alphabet.
Definition at line 454 of file rank_support_int_v.hpp.
using sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::block_value_type = std::conditional_t<bits_per_block_value <= 8, uint8_t, std::conditional_t<bits_per_block_value <= 16, uint16_t, uint32_t> > |
The smallest integer type needed to store the block ranks.
Definition at line 462 of file rank_support_int_v.hpp.
using sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::size_type = typename base_t::size_type |
Definition at line 456 of file rank_support_int_v.hpp.
|
inlineconstexprnoexcept |
Returns the rank value from the block.
compute_prefix_delta | A flag to indicate if the actual value or the delta with the previous symbol shall be computed. |
[in] | position | The text position to get the rank for. |
[in] | v | The symbol to get the rank for. |
The first block stores the counts for the actual second block. Hence, if we are in the first block of the superblock we get the first block value but multiply it with 0.
Definition at line 496 of file rank_support_int_v.hpp.
|
inline |
Loads from the archive.
Definition at line 592 of file rank_support_int_v.hpp.
|
inline |
Saves to the archive.
Definition at line 583 of file rank_support_int_v.hpp.
|
inlineconstexprnoexcept |
Returns the rank value from the in-block query.
compute_prefix_delta | A flag to indicate if the actual value or the delta with the previous symbol shall be computed. |
[in] | position | The text position to get the rank for. |
[in] | v | The symbol to get the rank for. |
If the position is at the beginning of a block the compute rank value is multiplied with 0.
Definition at line 514 of file rank_support_int_v.hpp.
|
inline |
Loads from the stream.
Definition at line 552 of file rank_support_int_v.hpp.
|
inline |
Saves to the stream.
Definition at line 534 of file rank_support_int_v.hpp.
|
inlineconstexprnoexcept |
Returns the rank value from the superblock.
compute_prefix_delta | A flag to indicate if the actual value or the delta with the previous symbol shall be computed. |
[in] | v | The symbol to get the rank for. |
Definition at line 479 of file rank_support_int_v.hpp.
|
inlinenoexcept |
Extracts the value at the given position.
position | The position of the value to extract. |
Definition at line 527 of file rank_support_int_v.hpp.
|
friend |
Inequality operator.
Definition at line 576 of file rank_support_int_v.hpp.
|
friend |
Equality operator.
Definition at line 569 of file rank_support_int_v.hpp.
|
staticconstexpr |
How many bits needed to store the block ranks.
Definition at line 460 of file rank_support_int_v.hpp.
|
staticconstexpr |
The offset used to jump to the correct block position.
Definition at line 458 of file rank_support_int_v.hpp.
std::array<block_value_type, (blocks_per_superblock - 1) * (alphabet_size - 1)> sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::blocks |
The array storing the block values.
Definition at line 469 of file rank_support_int_v.hpp.
std::array<detail::bit_compressed_word<uint8_t, sigma_bits>, words_per_superblock> sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::superblock_text |
The array storing the bit compressed text.
Definition at line 471 of file rank_support_int_v.hpp.
std::array<uint64_t, (alphabet_size - 1)> sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::superblocks |
The array storing the super block values.
Definition at line 467 of file rank_support_int_v.hpp.