SDSL 3.0.3
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 |
The smallest integer type needed to store the block ranks. | |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
![]() | |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
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. | |
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. | |
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. | |
value_type | value_at (size_type position) const noexcept |
Extracts the value at the given position. | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const |
Saves to the stream. | |
void | load (std::istream &in) |
Loads from the stream. | |
template<typename archive_t> | |
void | CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const |
Saves to the archive. | |
template<typename archive_t> | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Loads from the archive. | |
rank_support_int_v (int_vector<> const *text_ptr=nullptr) | |
Constructs and initialises the rank support structure for the given text. | |
rank_support_int_v (rank_support_int_v const &)=default | |
Defaulted copy constructor. | |
rank_support_int_v (rank_support_int_v &&)=default | |
Defaulted move constructor. | |
rank_support_int_v & | operator= (rank_support_int_v const &)=default |
Defaulted copy assignment. | |
rank_support_int_v & | operator= (rank_support_int_v &&)=default |
Defaulted move assignment. | |
~rank_support_int_v ()=default | |
Defaulted destructor. | |
size_type | rank (const size_type position, const value_type v) const |
Counts the occurrences of v in the prefix [0..idx-1]. | |
size_type | operator() (const size_type position, const value_type v) const |
Alias for rank(position, v) | |
size_type | prefix_rank (const size_type position, const value_type v) const |
Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1]. | |
size_type | size () const |
Returns the size of the original text. | |
value_type | value_at (const size_type position) const |
Returns the text value at the given position. | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const |
Saves to the stream. | |
void | load (std::istream &in, int_vector<> const *) |
Loads from the stream. | |
void | CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const |
Saves to the archive. | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Loads from the archive. | |
void | set_vector (int_vector<> const *) |
Does nothing for the rank_support_int structure. | |
![]() | |
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. | |
Public Attributes | |
std::array< uint64_t,(alphabet_size - 1)> | superblocks |
The array storing the super block values. | |
std::array< block_value_type,(blocks_per_superblock - 1) *(alphabet_size - 1)> | blocks |
The array storing the block values. | |
std::array< detail::bit_compressed_word< uint8_t, sigma_bits >, words_per_superblock > | superblock_text |
The array storing the bit compressed text. | |
Static Public Attributes | |
static constexpr size_t | block_offset = effective_alphabet_size |
The offset used to jump to the correct block position. | |
static constexpr size_t | bits_per_block_value = ceil_log2(values_per_superblock) |
How many bits needed to store the block ranks. | |
Friends | |
bool | operator== (superblock_entry const &lhs, superblock_entry const &rhs) noexcept |
Equality operator. | |
bool | operator!= (superblock_entry const &lhs, superblock_entry const &rhs) noexcept |
Inequality operator. | |
bool | operator== (rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept |
Equality operator. | |
bool | operator!= (rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept |
Inequality operator. | |
Additional Inherited Members | |
![]() | |
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. | |
![]() | |
int_vector const * | m_v |
Pointer to the rank supported bit_vector. | |
![]() | |
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 |
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 484 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 |
The smallest integer type needed to store the block ranks.
Definition at line 492 of file rank_support_int_v.hpp.
typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type |
Definition at line 207 of file rank_support_int.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 486 of file rank_support_int_v.hpp.
typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type |
Definition at line 209 of file rank_support_int.hpp.
|
default |
Defaulted destructor.
|
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 526 of file rank_support_int_v.hpp.
|
inline |
Loads from the archive.
Definition at line 418 of file rank_support_int_v.hpp.
|
inline |
Loads from the archive.
Definition at line 628 of file rank_support_int_v.hpp.
|
inline |
Saves to the archive.
Definition at line 410 of file rank_support_int_v.hpp.
|
inline |
Saves to the archive.
Definition at line 619 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 544 of file rank_support_int_v.hpp.
|
inline |
Loads from the stream.
Definition at line 585 of file rank_support_int_v.hpp.
|
inlinevirtual |
Loads from the stream.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 389 of file rank_support_int_v.hpp.
|
inlinevirtual |
Alias for rank(position, v)
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 327 of file rank_support_int_v.hpp.
|
default |
Defaulted move assignment.
|
default |
Defaulted copy assignment.
|
inlinevirtual |
Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].
position | The position of the symbol to get the prefix rank for (corresponds to length of the prefix: [0..position - 1] ). |
v | The alphabet symbol to get the rank for. |
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 338 of file rank_support_int_v.hpp.
|
inlinevirtual |
Counts the occurrences of v in the prefix [0..idx-1].
position | The position of the symbol to get the prefix rank for (corresponds to length of the prefix: [0..position - 1] ). |
v | The alphabet symbol to get the rank for. |
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 313 of file rank_support_int_v.hpp.
|
inlineexplicit |
Constructs and initialises the rank support structure for the given text.
[in] | text_ptr | The pointer to the text to build the rank support for. |
The text will be copied into the superblock structure to utilise better cache locality when computing the prefix rank for a given symbol and prefix length. Accordingly, the pointer to the text of the base class will always be a nullptr.
Definition at line 220 of file rank_support_int_v.hpp.
|
default |
Defaulted move constructor.
|
default |
Defaulted copy constructor.
|
inlinevirtual |
Saves to the stream.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 379 of file rank_support_int_v.hpp.
|
inlinevirtual |
Saves to the stream.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 564 of file rank_support_int_v.hpp.
|
inlinevirtual |
Does nothing for the rank_support_int structure.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 425 of file rank_support_int_v.hpp.
|
inline |
Returns the size of the original text.
Definition at line 364 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 509 of file rank_support_int_v.hpp.
|
inline |
Returns the text value at the given position.
[in] | position | The text position to get the value from. |
Definition at line 372 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 557 of file rank_support_int_v.hpp.
|
friend |
Inequality operator.
Definition at line 403 of file rank_support_int_v.hpp.
|
friend |
Inequality operator.
Definition at line 612 of file rank_support_int_v.hpp.
|
friend |
Equality operator.
Definition at line 397 of file rank_support_int_v.hpp.
|
friend |
Equality operator.
Definition at line 605 of file rank_support_int_v.hpp.
|
staticconstexpr |
How many bits needed to store the block ranks.
Definition at line 490 of file rank_support_int_v.hpp.
|
staticconstexpr |
The offset used to jump to the correct block position.
Definition at line 488 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 499 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 501 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 497 of file rank_support_int_v.hpp.