nlib
nn::nlib::succinct::Set Class Referencefinal

Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation. More...

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

Public Member Functions

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.
 
Basic Member Functions
 Set () noexcept
 Instantiates the object.
 
 ~Set () noexcept
 Destructor.
 
Setassign (Set &rhs, move_tag)
 Assigns the object by using swap for a move.
 
 Set (Set &rhs, move_tag)
 Instantiates the object by using swap for a move.
 
 Set (Set &&rhs)
 Instantiates the object (move constructor). This function is useful when using C++11.
 
Setoperator= (Set &&rhs)
 Move assignment operator. This function is useful when using C++11.
 
void swap (Set &rhs) noexcept
 Swaps the contents of an object.
 
Rank and Select Operation

Use after running Build.

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...
 
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...
 

Constructing a Set of Integers

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...
 

Detailed Description

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.
  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 operations at constant time.
  5. This allows operations such as Rank1, and Select1 to be run.
  6. 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.
Set myset;
if (nlib_is_error(myset.Init(size))) { ERROR }
for (idx : Set of integers) {
if (nlib_is_error(myset.TurnOn(idx))) { ERROR }
}
if (!myset.Build()) { ERROR }
// Rank/Select operations done by the following code.
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.

Member Function Documentation

◆ Build()

nn::nlib::succinct::Set::Build ( )
noexcept

Constructs the Rank dictionary.

Returns
Returns true when successful.

◆ Export()

nn::nlib::succinct::Set::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.

◆ 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]idxAn unsigned 32-bit integer.
Returns
Returns true if idx is included in the set.

◆ Import()

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

Reads the written object.

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

◆ Init()

nn::nlib::succinct::Set::Init ( uint32_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 bvSize 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]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 vector [0 .. idx]. This operation runs in constant time.

Definition at line 58 of file Sbv.h.

◆ Rank1()

nn::nlib::succinct::Set::Rank1 ( uint32_t  idx) const
noexcept

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 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]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 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]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 uses Rank1 to perform a binary search. Normally use Sbv, which supports the Select operation running in \(O(1)\).

◆ TurnOff()

nn::nlib::succinct::Set::TurnOff ( uint32_t  idx)
noexcept

Removes a 32-bit unsigned integer from the set.

Parameters
[in]idxInteger 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]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: