SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 (rrr_vector const &v)
 
 rrr_vector (rrr_vector &&v)
 
rrr_vectoroperator= (rrr_vector const &v)
 
rrr_vectoroperator= (rrr_vector &&v)
 
Constructor rrr_vector (bit_vector const &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== (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, 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 68 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 79 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 76 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 80 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 78 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 93 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 77 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 83 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 82 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 92 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 85 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 84 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 74 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 75 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 95 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 116 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 ( rrr_vector< t_bs, t_rac, t_k > const & v)
inline

Definition at line 117 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 126 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 ( bit_vector const & bv)
inline
Parameters
bvUncompressed bitvector.
kStore rank samples and pointers each k-th blocks.

Definition at line 158 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 413 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 403 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 392 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 418 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 308 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 381 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!= ( rrr_vector< t_bs, t_rac, t_k > const & v) const
inline

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

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

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

Definition at line 423 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 276 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 366 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 359 of file rrr_vector.hpp.

Friends And Related Symbol 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 85 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 85 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 85 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 85 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>
rac_type const& sdsl::rrr_vector< t_bs, t_rac, t_k >::bt = m_bt

Definition at line 112 of file rrr_vector.hpp.

◆ btnr

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

Definition at line 113 of file rrr_vector.hpp.


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