tudocomp
– The TU Dortmund Compression Framework
tdc::Select< m_bit > Class Template Reference

Implements a select data structure for a BitVector. More...

#include <Select.hpp>

Public Member Functions

 Select ()
 Default constructor. More...
 
 Select (const Select &other)
 Copy constructor. More...
 
 Select (Select &&other)
 Move constructor. More...
 
Selectoperator= (const Select &other)
 Copy assignment. More...
 
Selectoperator= (Select &&other)
 Move assignment. More...
 
 Select (BitVector &bv)
 Constructs the select data structure for the given bit vector. More...
 
size_t select (size_t x) const
 Finds the position of the x-th flagged bit in the bit vector. More...
 
size_t operator() (size_t k) const
 

Detailed Description

template<bool m_bit>
class tdc::Select< m_bit >

Implements a select data structure for a BitVector.

The data structure follows a block / superblock principle, where superblocks always contain s flagged bits and blocks contain s' flagged bits (flagged bits meaning 1 for select1 and 0 for select0).

The size of a block is logarithmic in the bit vector's length, the size of a superblock is the squared block size.

Template Parameters
m_bitthe bits to flag (0 or 1)

Definition at line 20 of file Select.hpp.

Constructor & Destructor Documentation

template<bool m_bit>
tdc::Select< m_bit >::Select ( )
inline

Default constructor.

Definition at line 45 of file Select.hpp.

template<bool m_bit>
tdc::Select< m_bit >::Select ( const Select< m_bit > &  other)
inline

Copy constructor.

Definition at line 53 of file Select.hpp.

template<bool m_bit>
tdc::Select< m_bit >::Select ( Select< m_bit > &&  other)
inline

Move constructor.

Definition at line 63 of file Select.hpp.

template<bool m_bit>
tdc::Select< m_bit >::Select ( BitVector bv)
inline

Constructs the select data structure for the given bit vector.

Note that changes to the bit vector after construction of this data structure will cause the select operation to not work correctly anymore. In other words, this data structure is static.

Parameters
bvthe underlying bit vector

Definition at line 101 of file Select.hpp.

Member Function Documentation

template<bool m_bit>
size_t tdc::Select< m_bit >::operator() ( size_t  k) const
inline
See also
select

Definition at line 246 of file Select.hpp.

template<bool m_bit>
Select& tdc::Select< m_bit >::operator= ( const Select< m_bit > &  other)
inline

Copy assignment.

Definition at line 73 of file Select.hpp.

template<bool m_bit>
Select& tdc::Select< m_bit >::operator= ( Select< m_bit > &&  other)
inline

Move assignment.

Definition at line 84 of file Select.hpp.

template<bool m_bit>
size_t tdc::Select< m_bit >::select ( size_t  x) const
inline

Finds the position of the x-th flagged bit in the bit vector.

Parameters
xthe order of the flagged bit to find
Returns
the position of the x-th flagged bit. In case the position is not contained in the bit vector, the bit vector's size is returned.

Definition at line 191 of file Select.hpp.


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