The data structure holding bit data operated on by Rank
and Select
.
More...
#include "nn/nlib/SmartBitmap.h"
|
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.
|
|
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
-
N | The size of the bit data (N bits). |
Derived | The 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 52 of file SmartBitmap.h.
◆ GetBitVector()
template<size_t N, class Derived, class BIT>
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 68 of file SmartBitmap.h.
◆ GetBitVectorSize()
template<size_t N, class Derived, class BIT>
Returns the size of the bit data.
- Returns
- The size of the set of domains (the size of the bit data).
Definition at line 67 of file SmartBitmap.h.
◆ Has()
template<size_t N, class Derived, class BIT>
Tests to determine whether a particular value is contained in the set.
- Parameters
-
[in] | idx | An unsigned 32-bit integer. |
- Returns
- Returns
true
if idx is included in the set.
Definition at line 69 of file SmartBitmap.h.
◆ operator[]()
template<size_t N, class Derived, class BIT>
Tests to determine whether a particular value is contained in the set.
- Parameters
-
[in] | idx | An unsigned 32-bit integer. |
- Returns
- Returns
true
if idx is included in the set.
Definition at line 77 of file SmartBitmap.h.
◆ Rank0()
template<size_t N, class Derived, class BIT>
Performs a Rank
operation.
- Parameters
-
[in] | idx | An 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 83 of file SmartBitmap.h.
◆ Rank1()
template<size_t N, class Derived, class BIT>
Performs a Rank
operation.
- Parameters
-
[in] | idx | An 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 78 of file SmartBitmap.h.
◆ Select0()
template<size_t N, class Derived, class BIT>
Returns the position of the nth 0 bit. nth starts from 0.
- Parameters
-
[in] | nth | An 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 92 of file SmartBitmap.h.
◆ Select1()
template<size_t N, class Derived, class BIT>
Returns the position of the nth 1 bit. nth starts from 0.
- Parameters
-
[in] | nth | An 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 87 of file SmartBitmap.h.
◆ Set() [1/2]
template<size_t N, class Derived, class BIT>
Adds a 32-bit unsigned integer to the set.
- Parameters
-
[in] | idx | The 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 97 of file SmartBitmap.h.
◆ Set() [2/2]
template<size_t N, class Derived, class BIT>
Sets bits in the bit data.
- Parameters
-
[in] | idx | Where to turn bits ON or OFF. |
[in] | value | The 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 120 of file SmartBitmap.h.
◆ TurnOn()
template<size_t N, class Derived, class BIT>
Adds a 32-bit unsigned integer to the set.
- Parameters
-
[in] | idx | The 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 108 of file SmartBitmap.h.
◆ Unset()
template<size_t N, class Derived, class BIT>
Removes a 32-bit unsigned integer from the set.
- Parameters
-
[in] | idx | The 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 109 of file SmartBitmap.h.
The documentation for this class was generated from the following files: