SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry Struct Reference

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.
 

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.
 

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.
 

Detailed Description

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
struct sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry

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.

Member Typedef Documentation

◆ block_value_type

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
using sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::block_value_type
Initial value:
std::conditional_t<bits_per_block_value <= 8,
uint8_t,
std::conditional_t<bits_per_block_value <= 16, uint16_t, uint32_t>>
static constexpr size_t bits_per_block_value
How many bits needed to store the block ranks.

The smallest integer type needed to store the block ranks.

Definition at line 492 of file rank_support_int_v.hpp.

◆ size_type

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
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.

Member Function Documentation

◆ block_rank()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
template<bool compute_prefix_delta>
constexpr size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::block_rank ( size_t const position,
value_type const v ) const
inlineconstexprnoexcept

Returns the rank value from the block.

Template Parameters
compute_prefix_deltaA flag to indicate if the actual value or the delta with the previous symbol shall be computed.
Parameters
[in]positionThe text position to get the rank for.
[in]vThe 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.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
template<typename archive_t >
void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Loads from the archive.

Definition at line 628 of file rank_support_int_v.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
template<typename archive_t >
void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Saves to the archive.

Definition at line 619 of file rank_support_int_v.hpp.

◆ in_block_rank()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
template<bool compute_prefix_delta>
constexpr size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::in_block_rank ( size_t const position,
value_type const v ) const
inlineconstexprnoexcept

Returns the rank value from the in-block query.

Template Parameters
compute_prefix_deltaA flag to indicate if the actual value or the delta with the previous symbol shall be computed.
Parameters
[in]positionThe text position to get the rank for.
[in]vThe 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.

◆ load()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::load ( std::istream & in)
inline

Loads from the stream.

Definition at line 585 of file rank_support_int_v.hpp.

◆ serialize()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
const std::string name = "" ) const
inline

Saves to the stream.

Definition at line 564 of file rank_support_int_v.hpp.

◆ superblock_rank()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
template<bool compute_prefix_delta>
constexpr size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::superblock_rank ( value_type const v) const
inlineconstexprnoexcept

Returns the rank value from the superblock.

Template Parameters
compute_prefix_deltaA flag to indicate if the actual value or the delta with the previous symbol shall be computed.
Parameters
[in]vThe symbol to get the rank for.

Definition at line 509 of file rank_support_int_v.hpp.

◆ value_at()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
value_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::value_at ( size_type position) const
inlinenoexcept

Extracts the value at the given position.

Parameters
positionThe position of the value to extract.

Definition at line 557 of file rank_support_int_v.hpp.

Friends And Related Symbol Documentation

◆ operator!=

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
bool operator!= ( superblock_entry const & lhs,
superblock_entry const & rhs )
friend

Inequality operator.

Definition at line 612 of file rank_support_int_v.hpp.

◆ operator==

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
bool operator== ( superblock_entry const & lhs,
superblock_entry const & rhs )
friend

Equality operator.

Definition at line 605 of file rank_support_int_v.hpp.

Member Data Documentation

◆ bits_per_block_value

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
constexpr size_t sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::bits_per_block_value = ceil_log2(values_per_superblock)
staticconstexpr

How many bits needed to store the block ranks.

Definition at line 490 of file rank_support_int_v.hpp.

◆ block_offset

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
constexpr size_t sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry::block_offset = effective_alphabet_size
staticconstexpr

The offset used to jump to the correct block position.

Definition at line 488 of file rank_support_int_v.hpp.

◆ blocks

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
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.

◆ superblock_text

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
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.

◆ superblocks

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
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.


The documentation for this struct was generated from the following file: