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

Member Typedef Documentation

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

private

Definition at line 228 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 255 of file radix_heap.hpp.

void clear_bit ( const size_t  i )

inline

Set the i-th bit to false.

Definition at line 245 of file radix_heap.hpp.

bool empty ( ) const

inline

True if all bits are false.

Definition at line 260 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 266 of file radix_heap.hpp.

bool is_set ( const size_t  i ) const

inline

Returns value of the i-th.

Definition at line 250 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 240 of file radix_heap.hpp.

Member Data Documentation

impl_type impl_

private

Definition at line 271 of file radix_heap.hpp.

constexpr size_t size

static

Definition at line 231 of file radix_heap.hpp.

---

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

• tlx/container/radix_heap.hpp