SDSL  3.0.0
Succinct Data Structure Library
sdsl::select_support_mcl< t_b, t_pat_len > Class Template Reference

A class supporting constant time select queries. More...

#include <select_support_mcl.hpp>

Inheritance diagram for sdsl::select_support_mcl< t_b, t_pat_len >:
sdsl::select_support

Public Types

enum  { bit_pat = t_b }
 
enum  { bit_pat_len = t_pat_len }
 
typedef bit_vector bit_vector_type
 
- Public Types inherited from sdsl::select_support
typedef int_vector< 1 >::size_type size_type
 

Public Member Functions

 select_support_mcl (const bit_vector *v=nullptr)
 
 select_support_mcl (const select_support_mcl< t_b, t_pat_len > &ss)
 
 select_support_mcl (select_support_mcl< t_b, t_pat_len > &&ss)
 
 ~select_support_mcl ()
 
void init_slow (const bit_vector *v=nullptr)
 
size_type select (size_type i) const
 Select function. More...
 
size_type operator() (size_type i) const
 Alias for select(i). More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serialize the select_support to an out file stream. More...
 
void load (std::istream &in, const bit_vector *v=nullptr)
 Load the select_support from an in file stream. More...
 
void set_vector (const bit_vector *v=nullptr)
 This method sets the supported bit_vector. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal. More...
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Serialise (load) via cereal. More...
 
select_support_mcl< t_b, t_pat_len > & operator= (const select_support_mcl &ss)
 
select_support_mcl< t_b, t_pat_len > & operator= (select_support_mcl &&)
 
bool operator== (const select_support_mcl &other) const noexcept
 
bool operator!= (const select_support_mcl &other) const noexcept
 
- Public Member Functions inherited from sdsl::select_support
 select_support (const int_vector< 1 > *f_v=nullptr)
 Constructor of select_support. More...
 
 select_support (const select_support &f_v)
 Copy constructor. More...
 
virtual ~select_support ()
 Destructor of select_support. More...
 

Additional Inherited Members

- Public Attributes inherited from sdsl::select_support
const bit_vectorvv
 
- Protected Attributes inherited from sdsl::select_support
const int_vector< 1 > * m_v
 Pointer to the select supported sdsl::bit_vector. More...
 

Detailed Description

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
class sdsl::select_support_mcl< t_b, t_pat_len >

A class supporting constant time select queries.

Space usage
The space usage of the data structure depends on the number of $ m $ of ones in the original bitvector $b$. We store the position of every $4096$th set bit (called L1-sampled bits) of $b$. This takes in the worst case $\frac{m}{4096} \log{n} \leq \frac{n}{64}$ bits. Next, (1) if the distance of two adjacent L1-sampled bits $b[i]$ and $b[j]$ is greater or equal than $\log^4 n$, then we store each of the 4096 positions of the set $b$ in [i..j-1] with $\log{n}$ bits. This results in at most $ \frac{4096\cdot \log n}{\log^4 n}=\frac{4096}{\log^3 n}$ bits per bit. For a bitvector of 4GB, i.e. $ \log n = 35 $ we get about 0.01 bits per bit. If the $j-i+1 < \log^4 n$ then (2) we store the relative position of every $64$th set bit (called L2-sampled bits) in b[i..j-1] in at most $4\log\log n$ bits per L2-sampled bits. An pessimistic upper bound for the space would be $ \frac{4\log\log n}{64} \leq \frac{24}{64} = 0.375$ bit per bit (since $\log\log n\leq 6$. It is very pessimistic, since we store the relative position in $\log\log(j-i+1)\leq \log\log n$ bits.
Template Parameters
t_bBit pattern 0,1,10,01 which should be ranked.
t_pat_lenLength of the bit pattern.

The implementation is a practical variant of the following reference:

Reference
David Clark: PhD Thesis: Compact Pat Trees University of Waterloo, 1996 (Section 2.2.2). http://www.nlc-bnc.ca/obj/s4/f2/dsk3/ftp04/nq21335.pdf

Definition at line 55 of file select_support_mcl.hpp.

Member Typedef Documentation

◆ bit_vector_type

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
typedef bit_vector sdsl::select_support_mcl< t_b, t_pat_len >::bit_vector_type

Definition at line 63 of file select_support_mcl.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
anonymous enum
Enumerator
bit_pat 

Definition at line 64 of file select_support_mcl.hpp.

◆ anonymous enum

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
anonymous enum
Enumerator
bit_pat_len 

Definition at line 68 of file select_support_mcl.hpp.

Constructor & Destructor Documentation

◆ select_support_mcl() [1/3]

template<uint8_t t_b, uint8_t t_pat_len>
sdsl::select_support_mcl< t_b, t_pat_len >::select_support_mcl ( const bit_vector v = nullptr)
explicit

Definition at line 112 of file select_support_mcl.hpp.

◆ select_support_mcl() [2/3]

template<uint8_t t_b, uint8_t t_pat_len>
sdsl::select_support_mcl< t_b, t_pat_len >::select_support_mcl ( const select_support_mcl< t_b, t_pat_len > &  ss)

Definition at line 123 of file select_support_mcl.hpp.

◆ select_support_mcl() [3/3]

template<uint8_t t_b, uint8_t t_pat_len>
sdsl::select_support_mcl< t_b, t_pat_len >::select_support_mcl ( select_support_mcl< t_b, t_pat_len > &&  ss)

Definition at line 146 of file select_support_mcl.hpp.

◆ ~select_support_mcl()

template<uint8_t t_b, uint8_t t_pat_len>
sdsl::select_support_mcl< t_b, t_pat_len >::~select_support_mcl

Definition at line 187 of file select_support_mcl.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t t_b, uint8_t t_pat_len>
template<typename archive_t >
void sdsl::select_support_mcl< t_b, t_pat_len >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)

Serialise (load) via cereal.

Definition at line 557 of file select_support_mcl.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t t_b, uint8_t t_pat_len>
template<typename archive_t >
void sdsl::select_support_mcl< t_b, t_pat_len >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const

Serialise (save) via cereal.

Definition at line 527 of file select_support_mcl.hpp.

◆ init_slow()

template<uint8_t t_b, uint8_t t_pat_len>
void sdsl::select_support_mcl< t_b, t_pat_len >::init_slow ( const bit_vector v = nullptr)

Definition at line 194 of file select_support_mcl.hpp.

◆ load()

template<uint8_t t_b, uint8_t t_pat_len>
void sdsl::select_support_mcl< t_b, t_pat_len >::load ( std::istream &  in,
const bit_vector v = nullptr 
)
virtual

Load the select_support from an in file stream.

Load an previously serialized select_support from a std::istream.

Parameters
inThe std::istream to load the select_support.
vThe bit_vector to be supported.
See also
init, select.

Implements sdsl::select_support.

Definition at line 494 of file select_support_mcl.hpp.

◆ operator!=()

template<uint8_t t_b, uint8_t t_pat_len>
bool sdsl::select_support_mcl< t_b, t_pat_len >::operator!= ( const select_support_mcl< t_b, t_pat_len > &  other) const
noexcept

Definition at line 608 of file select_support_mcl.hpp.

◆ operator()()

template<uint8_t t_b, uint8_t t_pat_len>
auto sdsl::select_support_mcl< t_b, t_pat_len >::operator() ( size_type  i) const
inlinevirtual

Alias for select(i).

Implements sdsl::select_support.

Definition at line 419 of file select_support_mcl.hpp.

◆ operator=() [1/2]

template<uint8_t t_b, uint8_t t_pat_len>
select_support_mcl< t_b, t_pat_len > & sdsl::select_support_mcl< t_b, t_pat_len >::operator= ( const select_support_mcl< t_b, t_pat_len > &  ss)

Definition at line 153 of file select_support_mcl.hpp.

◆ operator=() [2/2]

template<uint8_t t_b, uint8_t t_pat_len>
select_support_mcl< t_b, t_pat_len > & sdsl::select_support_mcl< t_b, t_pat_len >::operator= ( select_support_mcl< t_b, t_pat_len > &&  ss)

Definition at line 164 of file select_support_mcl.hpp.

◆ operator==()

template<uint8_t t_b, uint8_t t_pat_len>
bool sdsl::select_support_mcl< t_b, t_pat_len >::operator== ( const select_support_mcl< t_b, t_pat_len > &  other) const
noexcept

Definition at line 598 of file select_support_mcl.hpp.

◆ select()

template<uint8_t t_b, uint8_t t_pat_len>
auto sdsl::select_support_mcl< t_b, t_pat_len >::select ( size_type  i) const
inlinevirtual

Select function.

Implements sdsl::select_support.

Definition at line 364 of file select_support_mcl.hpp.

◆ serialize()

template<uint8_t t_b, uint8_t t_pat_len>
auto sdsl::select_support_mcl< t_b, t_pat_len >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
virtual

Serialize the select_support to an out file stream.

Implements sdsl::select_support.

Definition at line 448 of file select_support_mcl.hpp.

◆ set_vector()

template<uint8_t t_b, uint8_t t_pat_len>
void sdsl::select_support_mcl< t_b, t_pat_len >::set_vector ( const bit_vector v = nullptr)
virtual

This method sets the supported bit_vector.

Implements sdsl::select_support.

Definition at line 442 of file select_support_mcl.hpp.


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