tlx
BitArray< Size > Class Template Reference

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

#include <radix_heap.hpp>

Public Member Functions

 BitArray () noexcept=default
 
 BitArray (const BitArray &) noexcept=default
 
 BitArray (BitArray &&) noexcept=default
 
BitArrayoperator= (const BitArray &) noexcept=default
 
BitArrayoperator= (BitArray &&) noexcept=default
 
void set_bit (const size_t i)
 Set the i-th bit to true. More...
 
void clear_bit (const size_t i)
 Set the i-th bit to false. More...
 
bool is_set (const size_t i) const
 Returns value of the i-th. More...
 
void clear_all ()
 Sets all bits to false. More...
 
bool empty () const
 True if all bits are false. More...
 
size_t find_lsb () const
 Finds the bit with smallest index that is set. More...
 

Static Public Attributes

static constexpr size_t size
 

Private Types

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

Private Attributes

impl_type impl_
 

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.

Member Typedef Documentation

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

Definition at line 227 of file radix_heap.hpp.

Constructor & Destructor Documentation

BitArray ( )
explicitdefaultnoexcept
BitArray ( const BitArray< Size > &  )
defaultnoexcept
BitArray ( BitArray< Size > &&  )
defaultnoexcept

Member Function Documentation

void clear_all ( )
inline

Sets all bits to false.

Definition at line 254 of file radix_heap.hpp.

void clear_bit ( const size_t  i)
inline

Set the i-th bit to false.

Definition at line 244 of file radix_heap.hpp.

bool empty ( ) const
inline

True if all bits are false.

Definition at line 259 of file radix_heap.hpp.

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.

bool is_set ( const size_t  i) const
inline

Returns value of the i-th.

Definition at line 249 of file radix_heap.hpp.

BitArray& operator= ( const BitArray< Size > &  )
defaultnoexcept
BitArray& operator= ( BitArray< Size > &&  )
defaultnoexcept
void set_bit ( const size_t  i)
inline

Set the i-th bit to true.

Definition at line 239 of file radix_heap.hpp.

Member Data Documentation

impl_type impl_
private

Definition at line 270 of file radix_heap.hpp.

constexpr size_t size
static

Definition at line 230 of file radix_heap.hpp.


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