nlib
nn::nlib::succinct::SparseSet Class Referencefinal

Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers. More...

#include "nn/nlib/succinct/Sbv.h"

Public Types

typedef uint64_t IdxType
 typedef for the integer index type.
 

Public Member Functions

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.
 
Basic Member Functions
constexpr 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.
 
SparseSetoperator= (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. More...
 
Constructing a Set of Integers

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...
 
Rank and Select Operation

Use after running Build.

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...
 
Importing and Exporting
bool Export (BinaryWriter *w) const noexcept
 Writes the object to the file. More...
 
bool Import (BinaryReader *r) noexcept
 Reads the written object. More...
 

Detailed Description

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 bv_size 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.
  1. Create the objects using the constructor.
  2. Initialize the bit vector using Init to set the defined space.
  3. Add integers to the set using TurnOn.
  4. Construct a dictionary using Build to run Rank/Select operations at constant time.
  5. 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.
Attention
If a method including Has() should reference this object, it should do so after Build() has been performed. This is because an index needs to be created for internal reference.

Definition at line 122 of file Sbv.h.

Member Function Documentation

◆ 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
[in]wWrite out object.
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 162 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]idxAn unsigned 64-bit integer.
[out]rankStores 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 141 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]idxAn unsigned 64-bit integer.
Returns
Returns true if idx is included in the set.

Definition at line 151 of file Sbv.h.

◆ Import()

nn::nlib::succinct::SparseSet::Import ( BinaryReader r)
noexcept

Reads the written object.

Parameters
[in]rRead out object.
Returns
Returns true when import is successful.

◆ Init()

nn::nlib::succinct::SparseSet::Init ( uint64_t  bv_size)
noexcept

Initializes an object.

Parameters
[in]bv_sizeThe 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::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]idxAn 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 155 of file Sbv.h.

◆ Rank1()

nn::nlib::succinct::SparseSet::Rank1 ( uint64_t  idx) const
noexcept

Performs a Rank operation.

Parameters
[in]idxAn 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]nthA 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]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 ON in the bit vector. This operation runs in \(O(1)\) constant time.

◆ swap()

void nn::nlib::succinct::SparseSet::swap ( SparseSet rhs)
noexcept

Swaps the contents of an object.

Deprecated:
This function will be deleted in a future release.

◆ TurnOn()

nn::nlib::succinct::SparseSet::TurnOn ( uint64_t  idx)
noexcept

Adds a 64-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 vector.

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