SDSL 3.0.1
Succinct Data Structure Library
sdsl::rrr_vector< t_bs, t_rac, t_k > Class Template Reference

A. More...

#include <rrr_vector.hpp>

Public Types

enum  { block_size = t_bs }
 
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 iterator const_iterator
 
typedef bv_tag index_category
 
typedef rank_support_rrr< 1, t_bs, t_rac, t_k > rank_1_type
 
typedef rank_support_rrr< 0, t_bs, t_rac, t_k > rank_0_type
 
typedef select_support_rrr< 1, t_bs, t_rac, t_k > select_1_type
 
typedef select_support_rrr< 0, t_bs, t_rac, t_k > select_0_type
 
typedef rrr_helper< t_bs > rrr_helper_type
 
typedef rrr_helper_type::number_type number_type
 

Public Member Functions

Default constructor rrr_vector ()
 
 rrr_vector (const rrr_vector &v)
 
 rrr_vector (rrr_vector &&v)
 
rrr_vectoroperator= (const rrr_vector &v)
 
rrr_vectoroperator= (rrr_vector &&v)
 
Constructor rrr_vector (const bit_vector &bv)
 
Accessing the i th element of the original bit_vector value_type operator[] (size_type i) const
 
Get the integer value of the binary string of length len starting at position idx uint64_t get_int (size_type idx, uint8_t len=64) const
 
Returns the size of the original bit vector size_type size () const
 
Answers select queries Serializes the data structure into the given ostream size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 
Loads the data structure from the given istream void load (std::istream &in)
 
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, t_bs, t_rac, t_k >
 
class rank_support_rrr< 1, t_bs, t_rac, t_k >
 
class select_support_rrr< 0, t_bs, t_rac, t_k >
 
class select_support_rrr< 1, t_bs, t_rac, t_k >
 

Detailed Description

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
class sdsl::rrr_vector< t_bs, t_rac, t_k >

A.

Template Parameters
t_bsSize of a basic block.
t_racRandom access integer vector. Use to store the block types. It is possible to use WTs for t_rac.
t_kA rank sample value is stored before every t_k-th basic block.

References:

  • Rasmus Pagh Low redundancy in dictionaries with O(1) worst case lookup time Technical Report 1998. ftp://ftp.cs.au.dk/BRICS/Reports/RS/98/28/BRICS-RS-98-28.pdf, Section 2.
  • Rajeev Raman, V. Raman and S. Srinivasa Rao Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multi-sets. SODA 2002.
  • Francisco Claude, Gonzalo Navarro: Practical Rank/Select Queries over Arbitrary Sequences. SPIRE 2008: 176-187
  • On the fly-decoding and encoding was discovered in; Gonzalo Navarro, Eliana Providel: Fast, Small, Simple Rank/Select on Bitmaps. SEA 2012

In this version the block size can be adjust by the template parameter t_bs!

See also
sdsl::rrr_vector for a specialized version for block_size=15

Definition at line 61 of file rrr_vector.hpp.

Member Typedef Documentation

◆ const_iterator

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef iterator sdsl::rrr_vector< t_bs, t_rac, t_k >::const_iterator

Definition at line 72 of file rrr_vector.hpp.

◆ difference_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef bit_vector::difference_type sdsl::rrr_vector< t_bs, t_rac, t_k >::difference_type

Definition at line 69 of file rrr_vector.hpp.

◆ index_category

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef bv_tag sdsl::rrr_vector< t_bs, t_rac, t_k >::index_category

Definition at line 73 of file rrr_vector.hpp.

◆ iterator

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef random_access_const_iterator<rrr_vector> sdsl::rrr_vector< t_bs, t_rac, t_k >::iterator

Definition at line 71 of file rrr_vector.hpp.

◆ number_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef rrr_helper_type::number_type sdsl::rrr_vector< t_bs, t_rac, t_k >::number_type

Definition at line 86 of file rrr_vector.hpp.

◆ rac_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef t_rac sdsl::rrr_vector< t_bs, t_rac, t_k >::rac_type

Definition at line 70 of file rrr_vector.hpp.

◆ rank_0_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef rank_support_rrr<0, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::rank_0_type

Definition at line 76 of file rrr_vector.hpp.

◆ rank_1_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef rank_support_rrr<1, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::rank_1_type

Definition at line 75 of file rrr_vector.hpp.

◆ rrr_helper_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef rrr_helper<t_bs> sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_helper_type

Definition at line 85 of file rrr_vector.hpp.

◆ select_0_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef select_support_rrr<0, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::select_0_type

Definition at line 78 of file rrr_vector.hpp.

◆ select_1_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef select_support_rrr<1, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::select_1_type

Definition at line 77 of file rrr_vector.hpp.

◆ size_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef bit_vector::size_type sdsl::rrr_vector< t_bs, t_rac, t_k >::size_type

Definition at line 67 of file rrr_vector.hpp.

◆ value_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
typedef bit_vector::value_type sdsl::rrr_vector< t_bs, t_rac, t_k >::value_type

Definition at line 68 of file rrr_vector.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
anonymous enum
Enumerator
block_size 

Definition at line 88 of file rrr_vector.hpp.

Constructor & Destructor Documentation

◆ rrr_vector() [1/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Default constructor sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( )
inline

Definition at line 109 of file rrr_vector.hpp.

◆ rrr_vector() [2/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( const rrr_vector< t_bs, t_rac, t_k > &  v)
inline

Definition at line 110 of file rrr_vector.hpp.

◆ rrr_vector() [3/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( rrr_vector< t_bs, t_rac, t_k > &&  v)
inline

Definition at line 119 of file rrr_vector.hpp.

◆ rrr_vector() [4/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Constructor sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( const bit_vector bv)
inline
Parameters
bvUncompressed bitvector.
kStore rank samples and pointers each k-th blocks.

Definition at line 148 of file rrr_vector.hpp.

Member Function Documentation

◆ begin()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
iterator sdsl::rrr_vector< t_bs, t_rac, t_k >::begin ( ) const
inline

Definition at line 390 of file rrr_vector.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
template<typename archive_t >
void sdsl::rrr_vector< t_bs, t_rac, t_k >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 380 of file rrr_vector.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
template<typename archive_t >
void sdsl::rrr_vector< t_bs, t_rac, t_k >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 369 of file rrr_vector.hpp.

◆ end()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
iterator sdsl::rrr_vector< t_bs, t_rac, t_k >::end ( ) const
inline

Definition at line 392 of file rrr_vector.hpp.

◆ get_int()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Get the integer value of the binary string of length len starting at position idx uint64_t sdsl::rrr_vector< t_bs, t_rac, t_k >::get_int ( size_type  idx,
uint8_t  len = 64 
) const
inline
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 291 of file rrr_vector.hpp.

◆ load()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Loads the data structure from the given istream void sdsl::rrr_vector< t_bs, t_rac, t_k >::load ( std::istream &  in)
inline

Definition at line 358 of file rrr_vector.hpp.

◆ operator!=()

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

Definition at line 400 of file rrr_vector.hpp.

◆ operator=() [1/2]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
rrr_vector & sdsl::rrr_vector< t_bs, t_rac, t_k >::operator= ( const rrr_vector< t_bs, t_rac, t_k > &  v)
inline

Definition at line 120 of file rrr_vector.hpp.

◆ operator=() [2/2]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
rrr_vector & sdsl::rrr_vector< t_bs, t_rac, t_k >::operator= ( rrr_vector< t_bs, t_rac, t_k > &&  v)
inline

Definition at line 129 of file rrr_vector.hpp.

◆ operator==()

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

Definition at line 394 of file rrr_vector.hpp.

◆ operator[]()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Accessing the i th element of the original bit_vector value_type sdsl::rrr_vector< t_bs, t_rac, t_k >::operator[] ( size_type  i) const
inline
Parameters
iAn index i with $ 0 \leq i < size()  $.
Returns
The i-th bit of the original bit_vector

Definition at line 263 of file rrr_vector.hpp.

◆ serialize()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Answers select queries Serializes the data structure into the given ostream size_type sdsl::rrr_vector< t_bs, t_rac, t_k >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Definition at line 343 of file rrr_vector.hpp.

◆ size()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
Returns the size of the original bit vector size_type sdsl::rrr_vector< t_bs, t_rac, t_k >::size ( ) const
inline

Definition at line 339 of file rrr_vector.hpp.

Friends And Related Function Documentation

◆ rank_support_rrr< 0, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
friend class rank_support_rrr< 0, t_bs, t_rac, t_k >
friend

Definition at line 78 of file rrr_vector.hpp.

◆ rank_support_rrr< 1, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
friend class rank_support_rrr< 1, t_bs, t_rac, t_k >
friend

Definition at line 78 of file rrr_vector.hpp.

◆ select_support_rrr< 0, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
friend class select_support_rrr< 0, t_bs, t_rac, t_k >
friend

Definition at line 78 of file rrr_vector.hpp.

◆ select_support_rrr< 1, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
friend class select_support_rrr< 1, t_bs, t_rac, t_k >
friend

Definition at line 78 of file rrr_vector.hpp.

Member Data Documentation

◆ bt

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
const rac_type& sdsl::rrr_vector< t_bs, t_rac, t_k >::bt = m_bt

Definition at line 105 of file rrr_vector.hpp.

◆ btnr

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
const bit_vector& sdsl::rrr_vector< t_bs, t_rac, t_k >::btnr = m_btnr

Definition at line 106 of file rrr_vector.hpp.


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