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 > Class Template Reference

A rank structure proposed by Christopher Pockrandt. More...

#include <rank_support_int_v.hpp>

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

Classes

struct  superblock_entry
 Stores a superblock entry in a cache friendly pattern. More...
 

Public Types

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

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

Friends

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 = generate_mask_array()
 

Detailed Description

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

A rank structure proposed by Christopher Pockrandt.

This data structure is similar to rank data structures on bit vectors. It supports constant time rank and prefix_rank queries on int vectors.

Template Parameters
alphabet_sizeSize of the alphabet represented in the int_vector, i.e., largest value + 1.
words_per_blockWords per block (equivalent to the number of popcount operations in the worst-case per rank query).
blocks_per_superblockBlocks per superblock.
Reference
Christopher Pockrandt: EPR-Dictionaries: A practical and fast data structure for constant time searches in unidirectional and bidirectional FM-indices. WEA 2008: 154-168

Definition at line 176 of file rank_support_int_v.hpp.

Member Typedef Documentation

◆ size_type

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type

Definition at line 54 of file rank_support_int.hpp.

◆ value_type

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type

Definition at line 55 of file rank_support_int.hpp.

Constructor & Destructor Documentation

◆ rank_support_int_v() [1/3]

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

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const & )
default

Defaulted copy constructor.

◆ rank_support_int_v() [3/3]

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > && )
default

Defaulted move constructor.

◆ ~rank_support_int_v()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::~rank_support_int_v ( )
default

Defaulted destructor.

Member Function Documentation

◆ 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 >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Loads from the archive.

Definition at line 418 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 >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Saves to the archive.

Definition at line 410 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 >::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()()

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

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
rank_support_int_v & sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator= ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > && )
default

Defaulted move assignment.

◆ operator=() [2/2]

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

Defaulted copy assignment.

◆ prefix_rank()

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

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

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

◆ set_vector()

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

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 >::size ( ) const
inline

Returns the size of the original text.

Definition at line 364 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 >::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.

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!= ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const & lhs,
rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const & rhs )
friend

Inequality operator.

Definition at line 403 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== ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const & lhs,
rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const & rhs )
friend

Equality operator.

Definition at line 397 of file rank_support_int_v.hpp.


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