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 >:

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.

size_type	operator() (size_type i) const
	Alias for select(i).

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
	Serialize the select_support to an out file stream.

void	load (std::istream &in, const bit_vector *v=nullptr)
	Load the select_support from an in file stream.

void	set_vector (const bit_vector *v=nullptr)
	This method sets the supported bit_vector.

template<typename archive_t >
void	CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
	Serialise (save) via cereal.

template<typename archive_t >
void	CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
	Serialise (load) via cereal.

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.

	select_support (const select_support &f_v)
	Copy constructor.

virtual	~select_support ()
	Destructor of select_support.

virtual size_type	select (size_type i) const =0
	Select returns the index of the i-th 1-bit in the supported bit_vector.

virtual size_type	operator() (size_type i) const =0
	Alias for select.

virtual size_type	serialize (std::ostream &out, structure_tree_node *v, std::string name) const =0
	Serialize the select_support to an out file stream.

virtual void	load (std::istream &in, const int_vector< 1 > *v=nullptr)=0
	Load the select_support from an in file stream.

virtual void	set_vector (const int_vector< 1 > *v=nullptr)=0
	This method sets the supported bit_vector.

Additional Inherited Members
Public Attributes inherited from sdsl::select_support
const bit_vector *	vv

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

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 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_b	Bit pattern `0`,`1`,`10`,`01` which should be ranked.
t_pat_len	Length 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

in	The std::istream to load the select_support.
v	The 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:

/builddir/build/BUILD/sdsl-lite-3.0.1/include/sdsl/int_vector.hpp
/builddir/build/BUILD/sdsl-lite-3.0.1/include/sdsl/select_support_mcl.hpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ bit_vector_type

Member Enumeration Documentation

◆ anonymous enum

◆ anonymous enum

Constructor & Destructor Documentation

◆ select_support_mcl() [1/3]

◆ select_support_mcl() [2/3]

◆ select_support_mcl() [3/3]

◆ ~select_support_mcl()

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ init_slow()

◆ load()

◆ operator!=()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ select()

◆ serialize()

◆ set_vector()