tlx
Loading...
Searching...
No Matches
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.
 
void clear_bit (const size_t i)
 Set the i-th bit to false.
 
bool is_set (const size_t i) const
 Returns value of the i-th.
 
void clear_all ()
 Sets all bits to false.
 
bool empty () const
 True if all bits are false.
 
size_t find_lsb () const
 Finds the bit with smallest index that is set.
 

Static Public Attributes

static constexpr size_t size
 

Private Types

using impl_type
 

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 227 of file radix_heap.hpp.

Member Typedef Documentation

◆ impl_type

template<size_t Size>
using impl_type
private

Definition at line 229 of file radix_heap.hpp.

Constructor & Destructor Documentation

◆ BitArray() [1/3]

template<size_t Size>
BitArray ( )
explicitdefaultnoexcept

◆ BitArray() [2/3]

template<size_t Size>
BitArray ( const BitArray< Size > & )
defaultnoexcept

◆ BitArray() [3/3]

template<size_t Size>
BitArray ( BitArray< Size > && )
defaultnoexcept

Member Function Documentation

◆ clear_all()

template<size_t Size>
void clear_all ( )
inline

Sets all bits to false.

Definition at line 256 of file radix_heap.hpp.

◆ clear_bit()

template<size_t Size>
void clear_bit ( const size_t i)
inline

Set the i-th bit to false.

Definition at line 246 of file radix_heap.hpp.

◆ empty()

template<size_t Size>
bool empty ( ) const
inline

True if all bits are false.

Definition at line 261 of file radix_heap.hpp.

◆ find_lsb()

template<size_t Size>
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 267 of file radix_heap.hpp.

◆ is_set()

template<size_t Size>
bool is_set ( const size_t i) const
inline

Returns value of the i-th.

Definition at line 251 of file radix_heap.hpp.

◆ operator=() [1/2]

template<size_t Size>
BitArray & operator= ( BitArray< Size > && )
defaultnoexcept

◆ operator=() [2/2]

template<size_t Size>
BitArray & operator= ( const BitArray< Size > & )
defaultnoexcept

◆ set_bit()

template<size_t Size>
void set_bit ( const size_t i)
inline

Set the i-th bit to true.

Definition at line 241 of file radix_heap.hpp.

Member Data Documentation

◆ impl_

template<size_t Size>
impl_type impl_
private

Definition at line 272 of file radix_heap.hpp.

◆ size

template<size_t Size>
constexpr size_t size
staticconstexpr

Definition at line 232 of file radix_heap.hpp.


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