SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::rank_support_int_scan< alphabet_size > Class Template Reference

A class supporting rank queries in linear time. More...

#include <rank_support_int_scan.hpp>

Inheritance diagram for sdsl::rank_support_int_scan< alphabet_size >:
sdsl::rank_support_int< alphabet_size >

Public Types

typedef int_vector int_vector_type
 
typedef rank_support_int< alphabet_size >::size_type size_type
 
typedef rank_support_int< alphabet_size >::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_scan (int_vector<> const *v=nullptr)
 
 rank_support_int_scan (rank_support_int_scan const &rs)=default
 
 rank_support_int_scan (rank_support_int_scan &&rs)=default
 
rank_support_int_scanoperator= (rank_support_int_scan const &rs)=default
 
rank_support_int_scanoperator= (rank_support_int_scan &&rs)=default
 
size_type rank (size_type idx, const value_type v) const
 Counts the occurrences of v in the prefix [0..idx-1].
 
size_type operator() (size_type idx, const value_type v) const
 Alias for rank(idx, v)
 
size_type prefix_rank (size_type idx, 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
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
 Serializes rank_support_int.
 
void load (std::istream &, int_vector<> const *v=nullptr)
 Loads the rank_support_int.
 
void set_vector (int_vector<> const *v=nullptr)
 Sets the supported int_vector to the given pointer.
 
- 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.
 

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

A class supporting rank queries in linear time.

Template Parameters
alphabet_sizeSize of the alphabet used in the underlying sdsl::int_vector.
Space complexity
Constant.
Time complexity
Linear in the size of the supported vector.

Definition at line 28 of file rank_support_int_scan.hpp.

Member Typedef Documentation

◆ int_vector_type

template<uint8_t alphabet_size>
typedef int_vector sdsl::rank_support_int_scan< alphabet_size >::int_vector_type

Definition at line 34 of file rank_support_int_scan.hpp.

◆ size_type

template<uint8_t alphabet_size>
typedef rank_support_int<alphabet_size>::size_type sdsl::rank_support_int_scan< alphabet_size >::size_type

Definition at line 35 of file rank_support_int_scan.hpp.

◆ value_type

template<uint8_t alphabet_size>
typedef rank_support_int<alphabet_size>::value_type sdsl::rank_support_int_scan< alphabet_size >::value_type

Definition at line 36 of file rank_support_int_scan.hpp.

Constructor & Destructor Documentation

◆ rank_support_int_scan() [1/3]

template<uint8_t alphabet_size>
sdsl::rank_support_int_scan< alphabet_size >::rank_support_int_scan ( int_vector<> const *  v = nullptr)
inlineexplicit

Definition at line 39 of file rank_support_int_scan.hpp.

◆ rank_support_int_scan() [2/3]

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

◆ rank_support_int_scan() [3/3]

template<uint8_t alphabet_size>
sdsl::rank_support_int_scan< alphabet_size >::rank_support_int_scan ( rank_support_int_scan< alphabet_size > &&  rs)
default

Member Function Documentation

◆ load()

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

Loads the rank_support_int.

Parameters
inIn-Stream to load the rank_support_int data from.
vThe supported int_vector.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 58 of file rank_support_int_scan.hpp.

◆ operator()()

template<uint8_t alphabet_size>
size_type sdsl::rank_support_int_scan< alphabet_size >::operator() ( size_type  idx,
const value_type  v 
) const
inlinevirtual

Alias for rank(idx, v)

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 45 of file rank_support_int_scan.hpp.

◆ operator=() [1/2]

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

◆ operator=() [2/2]

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

◆ prefix_rank()

template<uint8_t alphabet_size>
rank_support_int_scan< alphabet_size >::size_type sdsl::rank_support_int_scan< alphabet_size >::prefix_rank ( size_type  idx,
const value_type  v 
) const
inlinevirtual

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

Parameters
idxArgument for the length of the prefix v[0..idx-1].
vArgument which value (including smaller values) to count.
See also
rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 104 of file rank_support_int_scan.hpp.

◆ rank()

template<uint8_t alphabet_size>
rank_support_int_scan< alphabet_size >::size_type sdsl::rank_support_int_scan< alphabet_size >::rank ( size_type  idx,
const value_type  v 
) const
inlinevirtual

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

Parameters
idxArgument for the length of the prefix v[0..idx-1].
vArgument which value to count.
See also
prefix_rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 76 of file rank_support_int_scan.hpp.

◆ serialize()

template<uint8_t alphabet_size>
size_type sdsl::rank_support_int_scan< alphabet_size >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
const std::string  name = "" 
) const
inlinevirtual

Serializes rank_support_int.

Parameters
outOut-Stream to serialize the data to.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 54 of file rank_support_int_scan.hpp.

◆ set_vector()

template<uint8_t alphabet_size>
void sdsl::rank_support_int_scan< alphabet_size >::set_vector ( int_vector<> const *  v = nullptr)
inlinevirtual

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

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 63 of file rank_support_int_scan.hpp.

◆ size()

template<uint8_t alphabet_size>
size_type sdsl::rank_support_int_scan< alphabet_size >::size ( ) const
inline

Definition at line 50 of file rank_support_int_scan.hpp.


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