nlib
nn::nlib::SmartBitmapCrtp< N, Derived, BIT > Class Template Reference

The data structure holding bit data operated on by Rank and Select. More...

#include "nn/nlib/SmartBitmap.h"

Public Member Functions

unsigned int GetBitVectorSize () const noexcept
 Returns the size of the bit data. More...
 
const BIT * GetBitVector () const noexcept
 Returns the pointer to the bit data. More...
 
bool Has (unsigned int idx) const noexcept
 Tests to determine whether a particular value is contained in the set. More...
 
bool operator[] (const unsigned int idx) const noexcept
 Tests to determine whether a particular value is contained in the set. More...
 
unsigned int Rank1 (unsigned int idx) const noexcept
 Performs a Rank operation. More...
 
unsigned int Rank0 (unsigned int idx) const noexcept
 Performs a Rank operation. More...
 
int Select1 (unsigned int nth) const noexcept
 Returns the position of the nth 1 bit. nth starts from 0. More...
 
int Select0 (unsigned int nth) const noexcept
 Returns the position of the nth 0 bit. nth starts from 0. More...
 
bool Set (unsigned int idx) noexcept
 Adds a 32-bit unsigned integer to the set. More...
 
bool TurnOn (unsigned int idx) noexcept
 Adds a 32-bit unsigned integer to the set. More...
 
bool Unset (unsigned int idx) noexcept
 Removes a 32-bit unsigned integer from the set. More...
 
bool Set (unsigned int idx, bool value) noexcept
 Sets bits in the bit data. More...
 
void Reset () noexcept
 Returns the object to the state immediately after the constructor is called.
 

Detailed Description

template<size_t N, class Derived, class BIT>
class nn::nlib::SmartBitmapCrtp< N, Derived, BIT >

The data structure holding bit data operated on by Rank and Select.

Template Parameters
NThe size of the bit data (N bits).
DerivedThe derived class type (for CRTP).
Description
The SmartBitmapCrtp<N, Derived> class implements Rank/Select operations on N bits of bit data with 37.5% of the overhead of the original bit data.
  • The Rank operation counts the number of 1(0) bits until the specified place. It runs in constant time.
  • The Select operation calculates the location where the nth 1(0) bit resides. Operates with \(O(\log N)\).
You can use these operations to perform highly efficient operations while maintaining the compactness of the bit data. This class does not act internally to get new memory from the heap.
What actually happens is that you construct and use the derived classes SmartBitmap and SmartBitmapPtr.

Definition at line 39 of file SmartBitmap.h.

Member Function Documentation

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::GetBitVector ( ) const
inlinenoexcept

Returns the pointer to the bit data.

Returns
The pointer to the bit data.
Description
The bit data is stored in order, starting from the LSB.

Definition at line 52 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::GetBitVectorSize ( ) const
inlinenoexcept

Returns the size of the bit data.

Returns
The size of the set of domains (the size of the bit data).

Definition at line 51 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Has ( unsigned int  idx) const
inlinenoexcept

Tests to determine whether a particular value is contained in the set.

Parameters
[in]idxAn unsigned 32-bit integer.
Returns
Returns true if idx is included in the set.

Definition at line 53 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::operator[] ( const unsigned int  idx) const
inlinenoexcept

Tests to determine whether a particular value is contained in the set.

Parameters
[in]idxAn unsigned 32-bit integer.
Returns
Returns true if idx is included in the set.

Definition at line 61 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Rank0 ( unsigned int  idx) const
inlinenoexcept

Performs a Rank operation.

Parameters
[in]idxAn unsigned 32-bit integer.
Returns
Returns the number of values equal to or less than idx that are not in the set.
Description
Returns the number of elements equal to or less than idx that are not included in the set. In other words, it returns the number of 1s in the bit data [0 .. idx]. This operation runs in constant time.

Definition at line 67 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Rank1 ( unsigned int  idx) const
inlinenoexcept

Performs a Rank operation.

Parameters
[in]idxAn unsigned 32-bit integer.
Returns
Returns the number of values equal to or less than idx in the set.
Description
Returns the number of values equal to or less than idx in the set. In other words, it returns the number of 1s in the bit data [0 .. idx]. This operation runs in constant time.

Definition at line 62 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Select0 ( unsigned int  nth) const
inlinenoexcept

Returns the position of the nth 0 bit. nth starts from 0.

Parameters
[in]nthAn integer equal to or greater than 0.
Returns
Returns the nth element (with 0 as the cardinal number), if that element exists. If not, the function returns -1.
Description
This function returns the position of the nth bit that is set to OFF in the bit data. This operation uses Rank1 to perform a binary search.

Definition at line 76 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Select1 ( unsigned int  nth) const
inlinenoexcept

Returns the position of the nth 1 bit. nth starts from 0.

Parameters
[in]nthAn integer equal to or greater than 0.
Returns
Returns the nth element (with 0 as the cardinal number), if that element exists. If not, the function returns -1.
Description
This function returns the position of the nth bit that is set to 1 in the bit data. This operation uses Rank1 to perform a binary search.
Normally use nn::nlib::succinct::Sbv, which supports the Select operation running in \(O(1)\).

Definition at line 71 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Set ( unsigned int  idx)
inlinenoexcept

Adds a 32-bit unsigned integer to the set.

Parameters
[in]idxThe integer to add to the set.
Returns
Returns true when successful.
Description
Specifically, this function sets the bits corresponding to idx ON in the bit data.

Definition at line 81 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Set ( unsigned int  idx,
bool  value 
)
inlinenoexcept

Sets bits in the bit data.

Parameters
[in]idxWhere to turn bits ON or OFF.
[in]valueThe ON/OFF state of the bit.
Returns
Returns true when successful.
Description
Specifically, this function sets the bits ON or OFF for the part in the set corresponding to idx.

Definition at line 104 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::TurnOn ( unsigned int  idx)
inlinenoexcept

Adds a 32-bit unsigned integer to the set.

Parameters
[in]idxThe integer to add to the set.
Returns
Returns true when successful.
Description
Specifically, this function sets the bits corresponding to idx ON in the bit data. It is the same as Set(idx) .

Definition at line 92 of file SmartBitmap.h.

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Unset ( unsigned int  idx)
inlinenoexcept

Removes a 32-bit unsigned integer from the set.

Parameters
[in]idxThe integer to add to the set.
Returns
Returns true when successful.
Description
Specifically, this function sets the bits OFF for the part in the set corresponding to idx.

Definition at line 93 of file SmartBitmap.h.


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