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>

Inheritance diagram for sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::superblock_entry:
sdsl::rank_support_int< alphabet_size >

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
 
- Public Types inherited from sdsl::rank_support_int< alphabet_size >
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_voperator= (rank_support_int_v const &)=default
 Defaulted copy assignment.
 
rank_support_int_voperator= (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.
 
- Public Member Functions inherited from sdsl::rank_support_int< alphabet_size >
 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_intoperator= (rank_support_int const &)=default
 
rank_support_intoperator= (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

- Static Protected Member Functions inherited from sdsl::rank_support_int< alphabet_size >
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 inherited from sdsl::rank_support_int< alphabet_size >
int_vector const * m_v
 Pointer to the rank supported bit_vector.
 
- Static Protected Attributes inherited from sdsl::rank_support_int< alphabet_size >
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
 

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 [1/3]

◆ size_type [2/3]

typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type

Definition at line 207 of file rank_support_int.hpp.

◆ size_type [3/3]

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.

◆ value_type [1/2]

◆ value_type [2/2]

typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type

Definition at line 209 of file rank_support_int.hpp.

Constructor & Destructor Documentation

◆ ~rank_support_int_v()

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::~rank_support_int_v ( )
default

Defaulted destructor.

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>
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() [1/2]

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Loads from the archive.

Definition at line 418 of file rank_support_int_v.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME() [2/2]

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() [1/2]

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Saves to the archive.

Definition at line 410 of file rank_support_int_v.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME() [2/2]

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>
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() [1/2]

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.

◆ load() [2/2]

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::load ( std::istream & in,
int_vector<> const *  )
inlinevirtual

Loads from the stream.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 389 of file rank_support_int_v.hpp.

◆ operator()()

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator() ( const size_type position,
const value_type v ) const
inlinevirtual

Alias for rank(position, v)

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 327 of file rank_support_int_v.hpp.

◆ operator=() [1/2]

rank_support_int_v & sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator= ( rank_support_int_v && )
default

Defaulted move assignment.

◆ operator=() [2/2]

rank_support_int_v & sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator= ( rank_support_int_v const & )
default

Defaulted copy assignment.

◆ prefix_rank()

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::prefix_rank ( const size_type position,
const value_type v ) const
inlinevirtual

Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].

Parameters
positionThe position of the symbol to get the prefix rank for (corresponds to length of the prefix: [0..position - 1]).
vThe alphabet symbol to get the rank for.
See also
rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 338 of file rank_support_int_v.hpp.

◆ rank()

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank ( const size_type position,
const value_type v ) const
inlinevirtual

Counts the occurrences of v in the prefix [0..idx-1].

Parameters
positionThe position of the symbol to get the prefix rank for (corresponds to length of the prefix: [0..position - 1]).
vThe alphabet symbol to get the rank for.
See also
prefix_rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 313 of file rank_support_int_v.hpp.

◆ rank_support_int_v() [1/3]

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( int_vector<> const * text_ptr = nullptr)
inlineexplicit

Constructs and initialises the rank support structure for the given text.

Parameters
[in]text_ptrThe 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.

◆ rank_support_int_v() [2/3]

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( rank_support_int_v && )
default

Defaulted move constructor.

◆ rank_support_int_v() [3/3]

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( rank_support_int_v const & )
default

Defaulted copy constructor.

◆ serialize() [1/2]

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
const std::string name = "" ) const
inlinevirtual

Saves to the stream.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 379 of file rank_support_int_v.hpp.

◆ serialize() [2/2]

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
inlinevirtual

Saves to the stream.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 564 of file rank_support_int_v.hpp.

◆ set_vector()

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::set_vector ( int_vector<> const * )
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.

◆ size()

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::size ( ) const
inline

Returns the size of the original text.

Definition at line 364 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>
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() [1/2]

value_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::value_at ( const size_type position) const
inline

Returns the text value at the given position.

Parameters
[in]positionThe text position to get the value from.

Definition at line 372 of file rank_support_int_v.hpp.

◆ value_at() [2/2]

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!= [1/2]

bool operator!= ( rank_support_int_v const & lhs,
rank_support_int_v const & rhs )
friend

Inequality operator.

Definition at line 403 of file rank_support_int_v.hpp.

◆ operator!= [2/2]

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== [1/2]

bool operator== ( rank_support_int_v const & lhs,
rank_support_int_v const & rhs )
friend

Equality operator.

Definition at line 397 of file rank_support_int_v.hpp.

◆ operator== [2/2]

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>
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>
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: