BitArray< Size > Class Template Reference

Detailed Description

template<size_t Size>
class tlx::radix_heap_detail::BitArray< Size >

A BitArray of fixed size supporting reading, setting, and clearing of individual bits.

The data structure is optimized to find the bit with smallest index that is set (find_lsb).

The BitArray is implemented as a search tree with a fan-out of up to 64. It is thus very flat, and all operations but with the exception of clear_all have a complexity of O(log_64(Size)) which is << 10 for all practical purposes.

Definition at line 225 of file radix_heap.hpp.

Inheritance diagram for BitArray< Size >:

#include <radix_heap.hpp>

Public Member Functions
	BitArray () noexcept=default
	BitArray (const BitArray &) noexcept=default
	BitArray (BitArray &&) noexcept=default
void	clear_all ()
	Sets all bits to false. More...
void	clear_bit (const size_t i)
	Set the i-th bit to false. More...
bool	empty () const
	True if all bits are false. More...
size_t	find_lsb () const
bool	is_set (const size_t i) const
	Returns value of the i-th. More...
BitArray &	operator= (const BitArray &) noexcept=default
BitArray &	operator= (BitArray &&) noexcept=default
void	set_bit (const size_t i)
	Set the i-th bit to true. More...

Static Public Attributes
static constexpr size_t	size = Size

Private Types
using	impl_type = BitArrayRecursive< Size, Size<=64 >

Private Attributes
impl_type	impl_

Member Typedef Documentation

impl_type

using impl_type = BitArrayRecursive<Size, Size <= 64>

private

Definition at line 227 of file radix_heap.hpp.

Constructor & Destructor Documentation

BitArray() [1/3]

BitArray ( )

explicitdefaultnoexcept

BitArray() [2/3]

BitArray ( const BitArray< Size > &  )

defaultnoexcept

BitArray() [3/3]

BitArray ( BitArray< Size > &&  )

defaultnoexcept

Member Function Documentation

clear_all()

void clear_all ( )

inline

Sets all bits to false.

Definition at line 254 of file radix_heap.hpp.

Referenced by RadixHeap< ValueType, KeyExtract, KeyType, Radix >::initialize_().

clear_bit()

void clear_bit ( const size_t  i )

inline

Set the i-th bit to false.

Definition at line 244 of file radix_heap.hpp.

Referenced by RadixHeap< ValueType, KeyExtract, KeyType, Radix >::reorganize_().

empty()

bool empty ( ) const

inline

True if all bits are false.

Definition at line 259 of file radix_heap.hpp.

find_lsb()

size_t find_lsb ( ) const

inline

Finds the bit with smallest index that is set

Warning

If empty() is true, the result is undefined

Definition at line 265 of file radix_heap.hpp.

Referenced by RadixHeap< ValueType, KeyExtract, KeyType, Radix >::reorganize_().

is_set()

bool is_set ( const size_t  i ) const

inline

Returns value of the i-th.

Definition at line 249 of file radix_heap.hpp.

operator=() [1/2]

BitArray& operator= ( const BitArray< Size > &  )

defaultnoexcept

operator=() [2/2]

BitArray& operator= ( BitArray< Size > &&  )

defaultnoexcept

set_bit()

void set_bit ( const size_t  i )

inline

Set the i-th bit to true.

Definition at line 239 of file radix_heap.hpp.

Referenced by RadixHeap< ValueType, KeyExtract, KeyType, Radix >::reorganize_(), and BitArray< num_buckets >::set_bit().

Member Data Documentation

impl_

impl_type impl_

private

Definition at line 270 of file radix_heap.hpp.

size

constexpr size_t size = Size

static

Definition at line 230 of file radix_heap.hpp.

---

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

• extlib/tlx/tlx/container/radix_heap.hpp