SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::rank_support_int< alphabet_size > Class Template Referenceabstract

The base class of classes supporting rank_queries for a sdsl::int_vector in constant time. More...

#include <rank_support_int.hpp>

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

Public Types

typedef int_vector ::size_type size_type
typedef int_vector ::value_type value_type

Public Member Functions

 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.
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, int_vector<> const *v=nullptr)=0
 Loads the rank_support_int.
virtual void set_vector (int_vector<> const *v=nullptr)=0
 Sets the supported int_vector to the given pointer.

Static Protected Member Functions

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

int_vector const * m_v
 Pointer to the rank supported bit_vector.

Static Protected Attributes

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>
class sdsl::rank_support_int< alphabet_size >

The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.

Definition at line 50 of file rank_support_int.hpp.

Member Typedef Documentation

◆ size_type

template<uint8_t alphabet_size>
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>
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() [1/3]

template<uint8_t alphabet_size>
sdsl::rank_support_int< alphabet_size >::rank_support_int ( int_vector<> const * v = nullptr)
inline

Constructor.

Parameters
vThe supported int_vector.

Definition at line 101 of file rank_support_int.hpp.

◆ rank_support_int() [2/3]

template<uint8_t alphabet_size>
sdsl::rank_support_int< alphabet_size >::rank_support_int ( rank_support_int< alphabet_size > const & )
default

Copy constructor.

◆ rank_support_int() [3/3]

template<uint8_t alphabet_size>
sdsl::rank_support_int< alphabet_size >::rank_support_int ( rank_support_int< alphabet_size > && )
default

◆ ~rank_support_int()

template<uint8_t alphabet_size>
virtual sdsl::rank_support_int< alphabet_size >::~rank_support_int ( )
inlinevirtual

Destructor.

Definition at line 113 of file rank_support_int.hpp.

Member Function Documentation

◆ bm_rec()

template<uint8_t alphabet_size>
template<typename uintX_t>
constexpr uintX_t sdsl::rank_support_int< alphabet_size >::bm_rec ( const uintX_t w,
const uint8_t length,
const uint8_t max_length )
inlinestaticconstexprprotected

Constructs a bit mask with the pattern w of a given length.

It is concatenated until the length of the bitmask reaches max_length.

Definition at line 64 of file rank_support_int.hpp.

◆ extract_word()

template<uint8_t alphabet_size>
constexpr uint64_t sdsl::rank_support_int< alphabet_size >::extract_word ( uint64_t const * data,
const size_type word_position )
inlinestaticconstexprprotectednoexcept

Returns the word a the given word position.

Definition at line 228 of file rank_support_int.hpp.

◆ full_word_prefix_rank()

template<uint8_t alphabet_size>
constexpr uint32_t sdsl::rank_support_int< alphabet_size >::full_word_prefix_rank ( const uint64_t word,
const value_type v )
inlinestaticconstexprprotectednoexcept

Counts the occurrences of v in the word starting at data up to position idx.

Definition at line 213 of file rank_support_int.hpp.

◆ full_word_rank()

template<uint8_t alphabet_size>
constexpr uint32_t sdsl::rank_support_int< alphabet_size >::full_word_rank ( const uint64_t word,
const value_type v )
inlinestaticconstexprprotectednoexcept

Counts the occurrences of v in the word starting at data up to position idx.

Cannot be called on v = 0. Call full_word_prefix_rank(data, word_pos, 0) instead.

Definition at line 221 of file rank_support_int.hpp.

◆ generate_mask_array()

template<uint8_t alphabet_size>
std::array< uint64_t, alphabet_size > sdsl::rank_support_int< alphabet_size >::generate_mask_array ( )
inlinestaticprotected

Definition at line 69 of file rank_support_int.hpp.

◆ load()

template<uint8_t alphabet_size>
virtual void sdsl::rank_support_int< alphabet_size >::load ( std::istream & in,
int_vector<> const * v = nullptr )
pure virtual

◆ mask_prefix()

template<uint8_t alphabet_size>
constexpr uint64_t sdsl::rank_support_int< alphabet_size >::mask_prefix ( value_type const v,
uint64_t const w_even,
uint64_t const w_odd )
inlinestaticconstexprprotectednoexcept

Mask the set prefix positions.

Definition at line 159 of file rank_support_int.hpp.

◆ operator()()

template<uint8_t alphabet_size>
virtual size_type sdsl::rank_support_int< alphabet_size >::operator() ( const size_type idx,
const value_type v ) const
pure virtual

◆ operator=() [1/2]

template<uint8_t alphabet_size>
rank_support_int & sdsl::rank_support_int< alphabet_size >::operator= ( rank_support_int< alphabet_size > && )
default

◆ operator=() [2/2]

template<uint8_t alphabet_size>
rank_support_int & sdsl::rank_support_int< alphabet_size >::operator= ( rank_support_int< alphabet_size > const & )
default

◆ prefix_rank()

template<uint8_t alphabet_size>
virtual size_type sdsl::rank_support_int< alphabet_size >::prefix_rank ( const size_type i,
const value_type v ) const
pure virtual

Answers rank queries for the supported int_vector.

Parameters
iArgument for the length of the prefix v[0..i-1].
vArgument which value (including smaller values) to count.
Returns
Number of occurrences of elements smaller or equal to v in the prefix [0..i-1] of the supported int_vector.
Note
Method init has to be called before the first call of rank.
See also
init

Implemented in sdsl::rank_support_int_scan< alphabet_size >, and sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >.

◆ rank()

template<uint8_t alphabet_size>
virtual size_type sdsl::rank_support_int< alphabet_size >::rank ( const size_type i,
const value_type v ) const
pure virtual

Answers rank queries for the supported int_vector.

Parameters
iArgument for the length of the prefix v[0..i-1].
vArgument which value to count.
Returns
Number of occurrences of v in the prefix [0..i-1] of the supported int_vector.
Note
Method init has to be called before the first call of rank.
See also
init

Implemented in sdsl::rank_support_int_scan< alphabet_size >, and sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >.

◆ serialize()

template<uint8_t alphabet_size>
virtual size_type sdsl::rank_support_int< alphabet_size >::serialize ( std::ostream & out,
structure_tree_node * v,
const std::string name ) const
pure virtual

◆ set_positions()

template<uint8_t alphabet_size>
constexpr uint64_t sdsl::rank_support_int< alphabet_size >::set_positions ( const uint64_t w,
const value_type v )
inlinestaticconstexprprotectednoexcept

Count how often value v occurs in the word w.

Cannot be called on v = 0. Call set_positions_prefix(w, 0) instead.

Definition at line 180 of file rank_support_int.hpp.

◆ set_positions_prefix()

template<uint8_t alphabet_size>
constexpr uint64_t sdsl::rank_support_int< alphabet_size >::set_positions_prefix ( const uint64_t w,
const value_type v )
inlinestaticconstexprprotectednoexcept

Count how often value v or smaller occurs in the word w.

Definition at line 170 of file rank_support_int.hpp.

◆ set_vector()

template<uint8_t alphabet_size>
virtual void sdsl::rank_support_int< alphabet_size >::set_vector ( int_vector<> const * v = nullptr)
pure virtual

Sets the supported int_vector to the given pointer.

Parameters
vThe new int_vector to support.
Note
Method init has to be called before the next call of rank or prefix_rank.
See also
init, rank, prefix_rank

Implemented in sdsl::rank_support_int_scan< alphabet_size >, and sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >.

◆ word_prefix_rank()

template<uint8_t alphabet_size>
template<typename... value_t>
constexpr std::array< uint64_t, sizeof...(value_t)> sdsl::rank_support_int< alphabet_size >::word_prefix_rank ( const uint64_t word,
const size_type bit_pos,
const value_t... values )
inlinestaticconstexprprotectednoexcept

Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.

Definition at line 194 of file rank_support_int.hpp.

◆ word_rank()

template<uint8_t alphabet_size>
constexpr uint32_t sdsl::rank_support_int< alphabet_size >::word_rank ( const uint64_t word,
const size_type bit_pos,
const value_type v )
inlinestaticconstexprprotectednoexcept

Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.

Cannot be called on v = 0. Call word_prefix_rank(data, idx, 0) instead.

Definition at line 207 of file rank_support_int.hpp.

Member Data Documentation

◆ bits_per_word

template<uint8_t alphabet_size>
uint8_t sdsl::rank_support_int< alphabet_size >::bits_per_word {(64 / sigma_bits) * sigma_bits}
staticconstexprprotected

Definition at line 90 of file rank_support_int.hpp.

◆ carry_select_mask

template<uint8_t alphabet_size>
uint64_t sdsl::rank_support_int< alphabet_size >::carry_select_mask {bm_rec<uint64_t>(1ULL << sigma_bits, sigma_bits * 2, 64)}
staticconstexprprotected

Definition at line 92 of file rank_support_int.hpp.

◆ even_mask

template<uint8_t alphabet_size>
uint64_t sdsl::rank_support_int< alphabet_size >::even_mask {bm_rec<uint64_t>(bits::lo_set[sigma_bits], sigma_bits * 2, 64)}
staticconstexprprotected

Definition at line 91 of file rank_support_int.hpp.

◆ m_v

template<uint8_t alphabet_size>
int_vector const* sdsl::rank_support_int< alphabet_size >::m_v
protected

Pointer to the rank supported bit_vector.

Definition at line 95 of file rank_support_int.hpp.

◆ masks

template<uint8_t alphabet_size>
const std::array<uint64_t, alphabet_size> sdsl::rank_support_int< alphabet_size >::masks
staticprotected

Definition at line 93 of file rank_support_int.hpp.

◆ sigma

template<uint8_t alphabet_size>
uint8_t sdsl::rank_support_int< alphabet_size >::sigma {alphabet_size}
staticconstexprprotected

Definition at line 88 of file rank_support_int.hpp.

◆ sigma_bits

template<uint8_t alphabet_size>
uint8_t sdsl::rank_support_int< alphabet_size >::sigma_bits {ceil_log2(alphabet_size)}
staticconstexprprotected

Definition at line 89 of file rank_support_int.hpp.


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