Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers.
More...
#include "nn/nlib/succinct/Sbv.h"
|
typedef uint64_t | IdxType |
| typedef for the integer index type.
|
|
|
bool | Build () noexcept |
| Constructs the Rank /Select dictionary. More...
|
|
bool | Has (uint64_t idx, uint32_t *rank) const noexcept |
| Tests to determine whether a particular value is contained in the set. More...
|
|
bool | Has (uint64_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...
|
|
uint64_t | GetBitVectorSize () const noexcept |
| Returns the size of the bit vector. More...
|
|
void | Reset () noexcept |
| Returns the object to the state immediately after the constructor is called.
|
|
|
| SparseSet () noexcept |
| Instantiates the object.
|
|
| ~SparseSet () noexcept |
| Destructor.
|
|
| SparseSet (SparseSet &&rhs) noexcept |
| Instantiates the object (move constructor). This function is useful when using C++11.
|
|
SparseSet & | operator= (SparseSet &&rhs) noexcept |
| Move assignment operator. This function is useful when using C++11.
|
|
void | swap (SparseSet &rhs) noexcept |
| Swaps the contents of an object.
|
|
|
Used before running Build .
|
bool | Init (uint64_t bv_size) noexcept |
| Initializes an object. More...
|
|
bool | TurnOn (uint64_t idx) noexcept |
| Adds a 64-bit unsigned integer to the set. More...
|
|
|
|
uint32_t | Rank1 (uint64_t idx) const noexcept |
| Performs a Rank operation. More...
|
|
uint32_t | Rank0 (uint64_t idx) const noexcept |
| Performs a Rank operation. More...
|
|
int32_t | Select1 (uint32_t nth) const noexcept |
| Returns the value of the nth element. nth starts from 0 . More...
|
|
int64_t | Select1Ex (uint32_t nth) const noexcept |
| Returns the value of the nth element. 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...
|
|
Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers.
- Description
- Implements
sdarray
, as described at the following link.
- In the case of a nowhere dense set, supports a set of integers (bit vector) that supports
Rank
/Select
operations in a memory space smaller than Set
or Sbv
. As a guideline, consider a nowhere dense set to be a set with 10% or less of its domain being ON.
- The
Select
operation using this class can be executed in \(O(1)\)
constant time. The Rank
operation is approximately \(O(\log N)\)
, where N
is the size of the definition domain (the value of bvSize passed to Init
).
- Unexpectedly, the
Has
operation, which determines whether a set contains a specified integer, is slower than both Rank
and Select
because it involves running a Rank
operation followed by a Select
operation.
- 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
/Select
operations at constant time.
-
Rank/Select
operations can now be used.
- When the data has been written using
Export
, the data may be used by calling the data using Import
after running the constructor.
Definition at line 100 of file Sbv.h.
§ Build()
nn::nlib::succinct::SparseSet::Build |
( |
| ) |
|
|
noexcept |
Constructs the Rank
/Select
dictionary.
- Returns
- Returns
true
when successful.
§ Export()
nn::nlib::succinct::SparseSet::Export |
( |
BinaryWriter * |
w | ) |
const |
|
noexcept |
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.
§ GetBitVectorSize()
nn::nlib::succinct::SparseSet::GetBitVectorSize |
( |
| ) |
const |
|
inlinenoexcept |
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.
Definition at line 141 of file Sbv.h.
§ Has() [1/2]
nn::nlib::succinct::SparseSet::Has |
( |
uint64_t |
idx, |
|
|
uint32_t * |
rank |
|
) |
| const |
|
inlinenoexcept |
Tests to determine whether a particular value is contained in the set.
- Parameters
-
[in] | idx | An unsigned 64-bit integer. |
[out] | rank | Stores the rank value if not NULL . |
- Returns
- Returns
true
if idx is included in the set.
- Description
- Runs a
Rank
and Select
operation. Stores the result of the Rank
calculation if the argument rank is not NULL
.
Definition at line 120 of file Sbv.h.
§ Has() [2/2]
nn::nlib::succinct::SparseSet::Has |
( |
uint64_t |
idx | ) |
const |
|
inlinenoexcept |
Tests to determine whether a particular value is contained in the set.
- Parameters
-
[in] | idx | An unsigned 64-bit integer. |
- Returns
- Returns
true
if idx is included in the set.
Definition at line 130 of file Sbv.h.
§ Import()
Reads the written object.
- Parameters
-
- Returns
- Returns
true
when import is successful.
§ Init()
nn::nlib::succinct::SparseSet::Init |
( |
uint64_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 bvSize to be added to the set.
§ MemSize()
nn::nlib::succinct::SparseSet::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::SparseSet::Rank0 |
( |
uint64_t |
idx | ) |
const |
|
inlinenoexcept |
Performs a Rank
operation.
- Parameters
-
[in] | idx | An unsigned 64-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
\(O(1)\)
constant time.
Definition at line 134 of file Sbv.h.
§ Rank1()
nn::nlib::succinct::SparseSet::Rank1 |
( |
uint64_t |
idx | ) |
const |
|
noexcept |
Performs a Rank
operation.
- Parameters
-
[in] | idx | An unsigned 64-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
\(O(1)\)
constant time.
§ Select1()
nn::nlib::succinct::SparseSet::Select1 |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
Returns the value of the nth element. nth starts from 0
.
- Parameters
-
[in] | nth | A 32-bit integer, 0 or larger. |
- 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 runs in
\(O(1)\)
constant time. Use the Select1Ex
function when there is the possibility of returning a 64-bit value.
§ Select1Ex()
nn::nlib::succinct::SparseSet::Select1Ex |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
Returns the value of the nth element. 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 runs in
\(O(1)\)
constant time.
§ TurnOn()
nn::nlib::succinct::SparseSet::TurnOn |
( |
uint64_t |
idx | ) |
|
|
noexcept |
Adds a 64-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: