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...
Select &	operator= (const Select &other)
	Copy assignment. More...
Select &	operator= (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_bit

the bits to flag (0 or 1)

Definition at line 20 of file Select.hpp.

Constructor & Destructor Documentation

Select() [1/4]

template<bool m_bit>

tdc::Select< m_bit >::Select ( )

inline

Default constructor.

Definition at line 45 of file Select.hpp.

Select() [2/4]

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.

Select() [3/4]

template<bool m_bit>

tdc::Select< m_bit >::Select ( Select< m_bit > &&  other )

inline

Move constructor.

Definition at line 63 of file Select.hpp.

Select() [4/4]

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

bv	the underlying bit vector

Definition at line 101 of file Select.hpp.

Member Function Documentation

operator()()

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.

operator=() [1/2]

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.

operator=() [2/2]

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.

select()

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

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

• Select.hpp