SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::rrr_vector< 15, t_rac, t_k > Class Template Reference

A specialization of the rrr_vector class for a block_size of 15. More...

#include <rrr_vector_15.hpp>

Public Types

enum  { block_size = 15 }
 
typedef bit_vector::size_type size_type
 
typedef bit_vector::value_type value_type
 
typedef bit_vector::difference_type difference_type
 
typedef t_rac rac_type
 
typedef random_access_const_iterator< rrr_vectoriterator
 
typedef bv_tag index_category
 
typedef rank_support_rrr< 1, 15, t_rac, t_k > rank_1_type
 
typedef rank_support_rrr< 0, 15, t_rac, t_k > rank_0_type
 
typedef select_support_rrr< 1, 15, t_rac, t_k > select_1_type
 
typedef select_support_rrr< 0, 15, t_rac, t_k > select_0_type
 
typedef binomial15 bi_type
 

Public Member Functions

 rrr_vector ()
 Default constructor.
 
 rrr_vector (rrr_vector const &v)
 Copy constructor.
 
 rrr_vector (rrr_vector &&v)
 Move constructor.
 
rrr_vectoroperator= (rrr_vector const &v)
 Assignment operator.
 
rrr_vectoroperator= (rrr_vector &&v)
 Move assignment.
 
 rrr_vector (bit_vector const &bv)
 Constructor.
 
value_type operator[] (size_type i) const
 Accessing the i-th element of the original bit_vector.
 
uint64_t get_int (size_type idx, uint8_t len=64) const
 Get the integer value of the binary string of length len starting at position idx.
 
size_type size () const
 Returns the size of the original bit vector.
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream.
 
void load (std::istream &in)
 Loads the data structure from the given istream.
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
iterator begin () const
 
iterator end () const
 
bool operator== (rrr_vector const &v) const
 
bool operator!= (rrr_vector const &v) const
 

Public Attributes

rac_type const & bt = m_bt
 
bit_vector const & btnr = m_btnr
 

Friends

class rank_support_rrr< 0, 15, t_rac, t_k >
 
class rank_support_rrr< 1, 15, t_rac, t_k >
 
class select_support_rrr< 0, 15, t_rac, t_k >
 
class select_support_rrr< 1, 15, t_rac, t_k >
 

Detailed Description

template<class t_rac, uint16_t t_k>
class sdsl::rrr_vector< 15, t_rac, t_k >

A specialization of the rrr_vector class for a block_size of 15.

Template Parameters
t_racRandom access integer vector. Use to store the block types.

Several tricks were used to speed-up the operations:

  • Whenever possible 2 4-bit blocks are decoded at once.
  • When the rank position lies in a block which consists only of zeros or ones (a uniform block), then we only have to sum up the values of the block type array between the last sampled position and the destination block. That can be done by using bit-parallelism on 64-bit words.

Definition at line 135 of file rrr_vector_15.hpp.

Member Typedef Documentation

◆ bi_type

template<class t_rac , uint16_t t_k>
typedef binomial15 sdsl::rrr_vector< 15, t_rac, t_k >::bi_type

Definition at line 159 of file rrr_vector_15.hpp.

◆ difference_type

template<class t_rac , uint16_t t_k>
typedef bit_vector::difference_type sdsl::rrr_vector< 15, t_rac, t_k >::difference_type

Definition at line 140 of file rrr_vector_15.hpp.

◆ index_category

template<class t_rac , uint16_t t_k>
typedef bv_tag sdsl::rrr_vector< 15, t_rac, t_k >::index_category

Definition at line 143 of file rrr_vector_15.hpp.

◆ iterator

template<class t_rac , uint16_t t_k>
typedef random_access_const_iterator<rrr_vector> sdsl::rrr_vector< 15, t_rac, t_k >::iterator

Definition at line 142 of file rrr_vector_15.hpp.

◆ rac_type

template<class t_rac , uint16_t t_k>
typedef t_rac sdsl::rrr_vector< 15, t_rac, t_k >::rac_type

Definition at line 141 of file rrr_vector_15.hpp.

◆ rank_0_type

template<class t_rac , uint16_t t_k>
typedef rank_support_rrr<0, 15, t_rac, t_k> sdsl::rrr_vector< 15, t_rac, t_k >::rank_0_type

Definition at line 151 of file rrr_vector_15.hpp.

◆ rank_1_type

template<class t_rac , uint16_t t_k>
typedef rank_support_rrr<1, 15, t_rac, t_k> sdsl::rrr_vector< 15, t_rac, t_k >::rank_1_type

Definition at line 150 of file rrr_vector_15.hpp.

◆ select_0_type

template<class t_rac , uint16_t t_k>
typedef select_support_rrr<0, 15, t_rac, t_k> sdsl::rrr_vector< 15, t_rac, t_k >::select_0_type

Definition at line 153 of file rrr_vector_15.hpp.

◆ select_1_type

template<class t_rac , uint16_t t_k>
typedef select_support_rrr<1, 15, t_rac, t_k> sdsl::rrr_vector< 15, t_rac, t_k >::select_1_type

Definition at line 152 of file rrr_vector_15.hpp.

◆ size_type

template<class t_rac , uint16_t t_k>
typedef bit_vector::size_type sdsl::rrr_vector< 15, t_rac, t_k >::size_type

Definition at line 138 of file rrr_vector_15.hpp.

◆ value_type

template<class t_rac , uint16_t t_k>
typedef bit_vector::value_type sdsl::rrr_vector< 15, t_rac, t_k >::value_type

Definition at line 139 of file rrr_vector_15.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_rac , uint16_t t_k>
anonymous enum
Enumerator
block_size 

Definition at line 155 of file rrr_vector_15.hpp.

Constructor & Destructor Documentation

◆ rrr_vector() [1/4]

template<class t_rac , uint16_t t_k>
sdsl::rrr_vector< 15, t_rac, t_k >::rrr_vector ( )
inline

Default constructor.

Parameters
kStore rank samples and pointers each k-th blocks.

Definition at line 176 of file rrr_vector_15.hpp.

◆ rrr_vector() [2/4]

template<class t_rac , uint16_t t_k>
sdsl::rrr_vector< 15, t_rac, t_k >::rrr_vector ( rrr_vector< 15, t_rac, t_k > const &  v)
inline

Copy constructor.

Definition at line 179 of file rrr_vector_15.hpp.

◆ rrr_vector() [3/4]

template<class t_rac , uint16_t t_k>
sdsl::rrr_vector< 15, t_rac, t_k >::rrr_vector ( rrr_vector< 15, t_rac, t_k > &&  v)
inline

Move constructor.

Definition at line 188 of file rrr_vector_15.hpp.

◆ rrr_vector() [4/4]

template<class t_rac , uint16_t t_k>
sdsl::rrr_vector< 15, t_rac, t_k >::rrr_vector ( bit_vector const &  bv)
inline

Constructor.

Parameters
bvUncompressed bitvector.
kStore rank samples and pointers each k-th blocks.

Definition at line 223 of file rrr_vector_15.hpp.

Member Function Documentation

◆ begin()

template<class t_rac , uint16_t t_k>
iterator sdsl::rrr_vector< 15, t_rac, t_k >::begin ( ) const
inline

Definition at line 452 of file rrr_vector_15.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_rac , uint16_t t_k>
template<typename archive_t >
void sdsl::rrr_vector< 15, t_rac, t_k >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 443 of file rrr_vector_15.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_rac , uint16_t t_k>
template<typename archive_t >
void sdsl::rrr_vector< 15, t_rac, t_k >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 433 of file rrr_vector_15.hpp.

◆ end()

template<class t_rac , uint16_t t_k>
iterator sdsl::rrr_vector< 15, t_rac, t_k >::end ( ) const
inline

Definition at line 457 of file rrr_vector_15.hpp.

◆ get_int()

template<class t_rac , uint16_t t_k>
uint64_t sdsl::rrr_vector< 15, t_rac, t_k >::get_int ( size_type  idx,
uint8_t  len = 64 
) const
inline

Get the integer value of the binary string of length len starting at position idx.

Parameters
idxStarting index of the binary representation of the integer.
lenLength of the binary representation of the integer. Default value is 64.
Returns
The integer value of the binary string of length len starting at position idx.
Precondition
idx+len-1 in [0..size()-1]
len in [1..64]

Definition at line 355 of file rrr_vector_15.hpp.

◆ load()

template<class t_rac , uint16_t t_k>
void sdsl::rrr_vector< 15, t_rac, t_k >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 423 of file rrr_vector_15.hpp.

◆ operator!=()

template<class t_rac , uint16_t t_k>
bool sdsl::rrr_vector< 15, t_rac, t_k >::operator!= ( rrr_vector< 15, t_rac, t_k > const &  v) const
inline

Definition at line 467 of file rrr_vector_15.hpp.

◆ operator=() [1/2]

template<class t_rac , uint16_t t_k>
rrr_vector & sdsl::rrr_vector< 15, t_rac, t_k >::operator= ( rrr_vector< 15, t_rac, t_k > &&  v)
inline

Move assignment.

Definition at line 205 of file rrr_vector_15.hpp.

◆ operator=() [2/2]

template<class t_rac , uint16_t t_k>
rrr_vector & sdsl::rrr_vector< 15, t_rac, t_k >::operator= ( rrr_vector< 15, t_rac, t_k > const &  v)
inline

Assignment operator.

Definition at line 194 of file rrr_vector_15.hpp.

◆ operator==()

template<class t_rac , uint16_t t_k>
bool sdsl::rrr_vector< 15, t_rac, t_k >::operator== ( rrr_vector< 15, t_rac, t_k > const &  v) const
inline

Definition at line 462 of file rrr_vector_15.hpp.

◆ operator[]()

template<class t_rac , uint16_t t_k>
value_type sdsl::rrr_vector< 15, t_rac, t_k >::operator[] ( size_type  i) const
inline

Accessing the i-th element of the original bit_vector.

Parameters
iAn index i with $ 0 \leq i < size()  $.
Returns
The i-th bit of the original bit_vector

Definition at line 305 of file rrr_vector_15.hpp.

◆ serialize()

template<class t_rac , uint16_t t_k>
size_type sdsl::rrr_vector< 15, t_rac, t_k >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Serializes the data structure into the given ostream.

Definition at line 409 of file rrr_vector_15.hpp.

◆ size()

template<class t_rac , uint16_t t_k>
size_type sdsl::rrr_vector< 15, t_rac, t_k >::size ( ) const
inline

Returns the size of the original bit vector.

Definition at line 403 of file rrr_vector_15.hpp.

Friends And Related Symbol Documentation

◆ rank_support_rrr< 0, 15, t_rac, t_k >

template<class t_rac , uint16_t t_k>
friend class rank_support_rrr< 0, 15, t_rac, t_k >
friend

Definition at line 143 of file rrr_vector_15.hpp.

◆ rank_support_rrr< 1, 15, t_rac, t_k >

template<class t_rac , uint16_t t_k>
friend class rank_support_rrr< 1, 15, t_rac, t_k >
friend

Definition at line 143 of file rrr_vector_15.hpp.

◆ select_support_rrr< 0, 15, t_rac, t_k >

template<class t_rac , uint16_t t_k>
friend class select_support_rrr< 0, 15, t_rac, t_k >
friend

Definition at line 143 of file rrr_vector_15.hpp.

◆ select_support_rrr< 1, 15, t_rac, t_k >

template<class t_rac , uint16_t t_k>
friend class select_support_rrr< 1, 15, t_rac, t_k >
friend

Definition at line 143 of file rrr_vector_15.hpp.

Member Data Documentation

◆ bt

template<class t_rac , uint16_t t_k>
rac_type const& sdsl::rrr_vector< 15, t_rac, t_k >::bt = m_bt

Definition at line 170 of file rrr_vector_15.hpp.

◆ btnr

template<class t_rac , uint16_t t_k>
bit_vector const& sdsl::rrr_vector< 15, t_rac, t_k >::btnr = m_btnr

Definition at line 171 of file rrr_vector_15.hpp.


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