SDSL 3.0.1
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 (const int_vector<> *text_ptr=nullptr)
 Constructs and initialises the rank support structure for the given text.
 
 rank_support_int_v (const rank_support_int_v &)=default
 Defaulted copy constructor.
 
 rank_support_int_v (rank_support_int_v &&)=default
 Defaulted move constructor.
 
rank_support_int_voperator= (const rank_support_int_v &)=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, const int_vector<> *)
 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 (const int_vector<> *)
 Does nothing for the rank_support_int structure.
 
- Public Member Functions inherited from sdsl::rank_support_int< alphabet_size >
 rank_support_int (const int_vector<> *v=nullptr)
 Constructor.
 
 rank_support_int (const rank_support_int &)=default
 Copy constructor.
 
 rank_support_int (rank_support_int &&)=default
 
rank_support_intoperator= (const rank_support_int &)=default
 
rank_support_intoperator= (rank_support_int &&)=default
 
virtual ~rank_support_int ()
 Destructor.
 
virtual size_type rank (const size_type i, const value_type v) const =0
 Answers rank queries for the supported int_vector.
 
virtual size_type operator() (const size_type idx, const value_type v) const =0
 Alias for rank(idx, v)
 
virtual size_type prefix_rank (const size_type i, const value_type v) const =0
 Answers rank queries for the supported int_vector.
 
virtual size_type serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0
 Serializes rank_support_int.
 
virtual void load (std::istream &in, const int_vector<> *v=nullptr)=0
 Loads the rank_support_int.
 
virtual void set_vector (const int_vector<> *v=nullptr)=0
 Sets the supported int_vector to the given pointer.
 

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 (const uint64_t *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 >
const int_vectorm_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 156 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 42 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 43 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 ( const int_vector<> *  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 200 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 ( const rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > &  )
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 388 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 380 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,
const int_vector<> *   
)
inlinevirtual

Loads from the stream.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 359 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 304 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= ( const rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > &  )
default

Defaulted copy 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 > &&  )
default

Defaulted move 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 312 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 293 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 349 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 ( const int_vector<> *  )
inlinevirtual

Does nothing for the rank_support_int structure.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 395 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 337 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 342 of file rank_support_int_v.hpp.

Friends And Related Function 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 373 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 367 of file rank_support_int_v.hpp.


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