SDSL 3.0.1
Succinct Data Structure Library
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. More...
 
 rrr_vector (const rrr_vector &v)
 Copy constructor. More...
 
 rrr_vector (rrr_vector &&v)
 Move constructor. More...
 
rrr_vectoroperator= (const rrr_vector &v)
 Assignment operator. More...
 
rrr_vectoroperator= (rrr_vector &&v)
 Move assignment. More...
 
 rrr_vector (const bit_vector &bv)
 Constructor. More...
 
value_type operator[] (size_type i) const
 Accessing the i-th element of the original bit_vector. More...
 
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. More...
 
size_type size () const
 Returns the size of the original bit vector. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream. More...
 
void load (std::istream &in)
 Loads the data structure from the given istream. More...
 
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== (const rrr_vector &v) const
 
bool operator!= (const rrr_vector &v) const
 

Public Attributes

const rac_typebt = m_bt
 
const bit_vectorbtnr = 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 112 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 136 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 117 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 120 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 119 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 118 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 128 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 127 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 130 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 129 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 115 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 116 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 132 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 153 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 ( const rrr_vector< 15, t_rac, t_k > &  v)
inline

Copy constructor.

Definition at line 156 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 165 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 ( const bit_vector bv)
inline

Constructor.

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

Definition at line 197 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 409 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 400 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 390 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 411 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 320 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 380 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!= ( const rrr_vector< 15, t_rac, t_k > &  v) const
inline

Definition at line 418 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= ( const rrr_vector< 15, t_rac, t_k > &  v)
inline

Assignment operator.

Definition at line 168 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 > &&  v)
inline

Move assignment.

Definition at line 179 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== ( const rrr_vector< 15, t_rac, t_k > &  v) const
inline

Definition at line 413 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 279 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 366 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 363 of file rrr_vector_15.hpp.

Friends And Related Function 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 120 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 120 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 120 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 120 of file rrr_vector_15.hpp.

Member Data Documentation

◆ bt

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

Definition at line 147 of file rrr_vector_15.hpp.

◆ btnr

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

Definition at line 148 of file rrr_vector_15.hpp.


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