SDSL 3.0.1
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 (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.
 

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 (const uint64_t *data, const size_type word_position) noexcept
 Returns the word a the given word position.
 

Protected Attributes

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

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 38 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 42 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 43 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 ( const int_vector<> *  v = nullptr)
inline

Constructor.

Parameters
vThe supported int_vector.

Definition at line 87 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 ( const rank_support_int< alphabet_size > &  )
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 99 of file rank_support_int.hpp.

Member Function Documentation

◆ bm_rec()

template<uint8_t alphabet_size>
template<typename uintX_t >
static 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 52 of file rank_support_int.hpp.

◆ extract_word()

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

Returns the word a the given word position.

Definition at line 214 of file rank_support_int.hpp.

◆ full_word_prefix_rank()

template<uint8_t alphabet_size>
static 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 199 of file rank_support_int.hpp.

◆ full_word_rank()

template<uint8_t alphabet_size>
static 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 207 of file rank_support_int.hpp.

◆ generate_mask_array()

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

Definition at line 57 of file rank_support_int.hpp.

◆ load()

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

◆ mask_prefix()

template<uint8_t alphabet_size>
static 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 144 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= ( const 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 > &&  )
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_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.

◆ 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_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.

◆ 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>
static 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 165 of file rank_support_int.hpp.

◆ set_positions_prefix()

template<uint8_t alphabet_size>
static 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 155 of file rank_support_int.hpp.

◆ set_vector()

template<uint8_t alphabet_size>
virtual void sdsl::rank_support_int< alphabet_size >::set_vector ( const int_vector<> *  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_v< alphabet_size, words_per_block, blocks_per_superblock >, and sdsl::rank_support_int_scan< alphabet_size >.

◆ word_prefix_rank()

template<uint8_t alphabet_size>
template<typename... value_t>
static 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 178 of file rank_support_int.hpp.

◆ word_rank()

template<uint8_t alphabet_size>
static 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 193 of file rank_support_int.hpp.

Member Data Documentation

◆ bits_per_word

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

Definition at line 76 of file rank_support_int.hpp.

◆ carry_select_mask

template<uint8_t alphabet_size>
constexpr 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 78 of file rank_support_int.hpp.

◆ even_mask

template<uint8_t alphabet_size>
constexpr 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 77 of file rank_support_int.hpp.

◆ m_v

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

Pointer to the rank supported bit_vector.

Definition at line 81 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 = generate_mask_array()
staticprotected

Definition at line 79 of file rank_support_int.hpp.

◆ sigma

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

Definition at line 74 of file rank_support_int.hpp.

◆ sigma_bits

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

Definition at line 75 of file rank_support_int.hpp.


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