SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
Public Types | Public Member Functions
sdsl::select_support_mcl< b, pattern_len > Class Template Reference

A class supporting constant time select queries (proposed by Munro/Clark, 1996) enhanced by broadword computing tricks. More...

#include <select_support_mcl.hpp>

Inherits sdsl::select_support.

List of all members.

Public Types

typedef bit_vector bit_vector_type

Public Member Functions

 select_support_mcl (const int_vector< 1 > *v=NULL)
 select_support_mcl (const select_support_mcl< b, pattern_len > &ss)
void init (const int_vector< 1 > *v=NULL)
 Initalization method for select_support.
void init_slow (const int_vector< 1 > *v=NULL)
const size_type select (size_type i) const
 Select function.
const size_type operator() (size_type i) const
 Alias for select(i).
size_type serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
 Serialize the select_support to an out file stream.
void load (std::istream &in, const int_vector< 1 > *v=NULL)
 Load the select_support from an in file stream.
void set_vector (const int_vector< 1 > *v=NULL)
 This method sets the supported bit_vector.
select_support_mcl< b,
pattern_len > & 
operator= (const select_support_mcl &ss)
void swap (select_support_mcl< b, pattern_len > &ss)
 Swap operator.
bool operator== (const select_support_mcl< b, pattern_len > &ss) const
 Equality Operator.
bool operator!= (const select_support_mcl< b, pattern_len > &ss) const
 Unequality Operator.

Detailed Description

template<uint8_t b = 1, uint8_t pattern_len = 1>
class sdsl::select_support_mcl< b, pattern_len >

A class supporting constant time select queries (proposed by Munro/Clark, 1996) enhanced by broadword computing tricks.

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{64}{n}$ bits. Next, (1) if the distance of two adjacent L1-sampled bits $b[i]$ and $b[j]$ is greater or equal than $^4 n$, then we store each of the 4096 positions of the set $b$ in [i..j-1] with ${n}$ bits. This results in at most $ {4096 n}{^4 n}={4096}{^3 n}$ bits per bit. For a bitvector of 1GB, i.e. $ \log n = 35 $ we get about 0.01 bits per bit. If the $j-i+1 < ^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 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 $ n 6$. It is very pessimistic, since we store the relative position in $(j-i+1) n$ bits.

Member Function Documentation

template<uint8_t b, uint8_t pattern_len>
void sdsl::select_support_mcl< b, pattern_len >::init ( const int_vector< 1 > *  v = NULL) [virtual]

Initalization method for select_support.

Init takes no arguments and should be called before the first call to the select method if not

  • load is called to initialize the select_support or
  • the constructor is called with the pointer to the supported bit_vector.
    See also:
    select, load.

Implements sdsl::select_support.

template<uint8_t b, uint8_t pattern_len>
void sdsl::select_support_mcl< b, pattern_len >::load ( std::istream &  in,
const int_vector< 1 > *  v = NULL 
) [virtual]

Load the select_support from an in file stream.

Load an previously serialized select_support from a std::istream. This method could replace the call of init before the first call of the select method.

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

Implements sdsl::select_support.

template<uint8_t b, uint8_t pattern_len>
bool sdsl::select_support_mcl< b, pattern_len >::operator!= ( const select_support_mcl< b, pattern_len > &  ss) const

Unequality Operator.

Two select_support_mcls are not equal if any member variable are not equal. Required for the Equality Comparable Concept of the STL.

See also:
operator==
template<uint8_t b, uint8_t pattern_len>
bool sdsl::select_support_mcl< b, pattern_len >::operator== ( const select_support_mcl< b, pattern_len > &  ss) const

Equality Operator.

Two select_support_mcls are equal if all member variables are equal. Required for the Equality Comparable Concept of the STL.

See also:
operator!=
template<uint8_t b, uint8_t pattern_len>
const select_support_mcl< b, pattern_len >::size_type sdsl::select_support_mcl< b, pattern_len >::select ( size_type  i) const [inline, virtual]

Select function.

See also:
select_support.select

Implements sdsl::select_support.

template<uint8_t b, uint8_t pattern_len>
void sdsl::select_support_mcl< b, pattern_len >::set_vector ( const int_vector< 1 > *  v = NULL) [virtual]

This method sets the supported bit_vector.

Note:
Call the init function before you call select the first time after you changed the supported bit_vector.

Implements sdsl::select_support.

template<uint8_t b, uint8_t pattern_len>
void sdsl::select_support_mcl< b, pattern_len >::swap ( select_support_mcl< b, pattern_len > &  ss)

Swap operator.

This swap operator swaps two select_support_mcls in constant time.


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