Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select
operation.
More...
#include "nn/nlib/succinct/Sbv.h"
|
bool | Build () noexcept |
| Constructs the Rank dictionary. More...
|
|
bool | Has (uint32_t idx) const noexcept |
| Tests to determine whether a particular value is contained in the set. More...
|
|
size_t | MemSize () const noexcept |
| Returns the amount of memory explicitly allocated by the class. More...
|
|
uint32_t | GetBitVectorSize () const noexcept |
| Returns the size of the bit vector. More...
|
|
const uint32_t * | GetBitVector () const noexcept |
| Returns the pointer to the bit vector. More...
|
|
void | Reset () noexcept |
| Returns the object to the state immediately after the constructor is called.
|
|
|
constexpr | Set () noexcept |
| Instantiates the object.
|
|
| ~Set () noexcept |
| Destructor.
|
|
Set & | assign (Set &rhs, move_tag) |
| Corresponds to a move assignment operator.
|
|
| Set (Set &rhs, move_tag) |
| Corresponds to a move constructor.
|
|
| Set (Set &&rhs) |
| Instantiates the object (move constructor). This function is useful when using C++11.
|
|
Set & | operator= (Set &&rhs) |
| Move assignment operator. This function is useful when using C++11.
|
|
void | swap (Set &rhs) noexcept |
| Swaps the contents of an object. More...
|
|
|
|
uint32_t | Rank1 (uint32_t idx) const noexcept |
| Performs a Rank operation. More...
|
|
uint32_t | Rank0 (uint32_t idx) const noexcept |
| Performs a Rank operation. More...
|
|
int32_t | Select1 (uint32_t nth) const noexcept |
| Returns the position of the nth 1 bit. nth starts from 0. More...
|
|
int32_t | Select0 (uint32_t nth) const noexcept |
| Returns the position of the nth 0 bit. nth starts from 0. More...
|
|
|
bool | Export (BinaryWriter *w) const noexcept |
| Writes the object to the file. More...
|
|
bool | Import (BinaryReader *r) noexcept |
| Reads the written object. More...
|
|
|
Used before running Build .
|
typedef uint32_t | IdxType |
| typedef for the integer index type.
|
|
bool | Init (uint32_t bv_size) noexcept |
| Initializes an object. More...
|
|
bool | TurnOn (uint32_t idx) noexcept |
| Adds a 32-bit unsigned integer to the set. More...
|
|
bool | TurnOff (uint32_t idx) noexcept |
| Removes a 32-bit unsigned integer from the set. More...
|
|
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select
operation.
- Description
- This class holds a set of 32-bit unsigned integers in the form of a bit vector, and supports
Rank
operations by \(O(1)\)
constant time. See Rank0
/Rank1
for a detailed description of Rank
operations.
- Use this class in the following way.
-
Create the objects using the constructor.
-
Initialize the bit vector using
Init
to set the defined space.
-
Add integers to the set using
TurnOn
.
-
Construct a dictionary using
Build
to run Rank
operations at constant time.
-
This allows operations such as
Rank1
, and Select1
to be run.
-
If a change is needed to the content of the set, use
TurnOn
and TurnOff
to make the changes, and then run Build
again.
- Specifically, this is implemented as follows.
for (idx :
Set of integers) {
}
if (!myset.Build()) { ERROR }
- When the data has been written using
Export
, the data may be used by calling the data using Import
after running the constructor. This class holds all of the bit vector within the definition domain, allowing for high speed Rank
operations. However, it consumes a large amount of memory. The use of SparseSet
is recommended when the set is a nowhere dense set.
Definition at line 41 of file Sbv.h.
◆ Build()
nn::nlib::succinct::Set::Build |
( |
| ) |
|
|
noexcept |
Constructs the Rank
dictionary.
- Returns
- Returns
true
when successful.
◆ Export()
Writes the object to the file.
- Parameters
-
- Returns
- Returns
true
when successful.
- Description
- The written data can be read and restored using the
Import
function. The data is always written little endian.
◆ GetBitVector()
nn::nlib::succinct::Set::GetBitVector |
( |
| ) |
const |
|
noexcept |
Returns the pointer to the bit vector.
- Returns
- Returns the pointer to the bit vector.
- Description
- The bit vector is stored in order, starting from the LSB.
◆ GetBitVectorSize()
nn::nlib::succinct::Set::GetBitVectorSize |
( |
| ) |
const |
|
noexcept |
Returns the size of the bit vector.
- Returns
- Returns the size of the domain of the set (the size of the bit vector).
- Description
- Returns the same value passed to the
Init
function.
◆ Has()
nn::nlib::succinct::Set::Has |
( |
uint32_t |
idx | ) |
const |
|
noexcept |
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.
◆ Import()
Reads the written object.
- Parameters
-
- Returns
- Returns
true
when import is successful.
◆ Init()
nn::nlib::succinct::Set::Init |
( |
uint32_t |
bv_size | ) |
|
|
noexcept |
Initializes an object.
- Parameters
-
[in] | bv_size | The size of the bit vector. |
- Returns
- Returns
true
when successful.
- Description
- This allows a value larger than
0
and smaller than bv_size to be added to the set.
◆ MemSize()
nn::nlib::succinct::Set::MemSize |
( |
| ) |
const |
|
noexcept |
Returns the amount of memory explicitly allocated by the class.
- Returns
- Returns the number of bytes.
- Description
- The actual amount of memory allocated by the system may be larger than the value returned by this function because of alignment and space for heap management.
◆ Rank0()
nn::nlib::succinct::Set::Rank0 |
( |
uint32_t |
idx | ) |
const |
|
inlinenoexcept |
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 vector [0 .. idx]. This operation runs in constant time.
Definition at line 54 of file Sbv.h.
◆ Rank1()
nn::nlib::succinct::Set::Rank1 |
( |
uint32_t |
idx | ) |
const |
|
noexcept |
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 vector [0 .. idx]. This operation runs in constant time.
◆ Select0()
nn::nlib::succinct::Set::Select0 |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
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 OFF in the bit vector. This operation uses
Rank1
to perform a binary search.
◆ Select1()
nn::nlib::succinct::Set::Select1 |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
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 ON in the bit vector. This operation uses
Rank1
to perform a binary search. Normally use Sbv
, which supports the Select
operation running in \(O(1)\)
.
◆ swap()
void nn::nlib::succinct::Set::swap |
( |
Set & |
rhs | ) |
|
|
inlinenoexcept |
Swaps the contents of an object.
- Deprecated:
- This function will be deleted in a future release.
Definition at line 340 of file Sbv.h.
◆ TurnOff()
nn::nlib::succinct::Set::TurnOff |
( |
uint32_t |
idx | ) |
|
|
noexcept |
Removes a 32-bit unsigned integer from the set.
- Parameters
-
[in] | idx | Integer to remove from the set. |
- Returns
- Returns
true
when successful.
- Description
- Specifically, this function sets the bits corresponding to idx OFF in the bit vector.
◆ TurnOn()
nn::nlib::succinct::Set::TurnOn |
( |
uint32_t |
idx | ) |
|
|
noexcept |
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 vector.
The documentation for this class was generated from the following files: