nlib
nn::nlib::succinct::Sbv 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 Types

typedef uint32_t IdxType
 typedef for the integer index type.
 

Public Member Functions

bool Build () noexcept
 Constructs the Rank/Select 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
 Sbv () noexcept
 Instantiates the object.
 
 ~Sbv () noexcept
 Destructor.
 
Sbvassign (Sbv &rhs, move_tag)
 Assigns the object by using swap for a move.
 
 Sbv (Sbv &rhs, move_tag)
 Instantiates the object by using swap for a move.
 
 Sbv (Sbv &&rhs)
 Instantiates the object (move constructor). This function is useful when using C++11.
 
Sbvoperator= (Sbv &&rhs)
 Move assignment operator. This function is useful when using C++11.
 
void swap (Sbv &rhs) noexcept
 Swaps the contents of an object.
 
Constructing a Set of Integers

Used before running Build.

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

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 and Select operations by \(O(1)\) constant time. High speed operations on modern compact data structures can be implemented using the Rank/Select operations. Refer to Set::Rank1 and Select1 for a detailed description of Rank/Select 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/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. 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 64 of file Sbv.h.

Member Function Documentation

§ Build()

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

Constructs the Rank/Select dictionary.

Returns
Returns true when successful.

§ Export()

nn::nlib::succinct::Sbv::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::Sbv::GetBitVector ( ) const
inlinenoexcept

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.

Definition at line 88 of file Sbv.h.

§ GetBitVectorSize()

nn::nlib::succinct::Sbv::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 87 of file Sbv.h.

§ Has()

nn::nlib::succinct::Sbv::Has ( uint32_t  idx) const
inlinenoexcept

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.

Definition at line 81 of file Sbv.h.

§ Import()

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

Reads the written object.

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

§ Init()

nn::nlib::succinct::Sbv::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::Sbv::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::Sbv::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 \(O(1)\) constant time.

Definition at line 83 of file Sbv.h.

§ Rank1()

nn::nlib::succinct::Sbv::Rank1 ( 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 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.

Definition at line 82 of file Sbv.h.

§ Select0()

nn::nlib::succinct::Sbv::Select0 ( uint32_t  nth) const
inlinenoexcept

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 0 bit (with 0 as the cardinal number), if that 1 bit 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.

Definition at line 85 of file Sbv.h.

§ Select1()

nn::nlib::succinct::Sbv::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 1 bit (with 0 as the cardinal number), if that 1 bit 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.

§ TurnOff()

nn::nlib::succinct::Sbv::TurnOff ( uint32_t  idx)
inlinenoexcept

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.

Definition at line 79 of file Sbv.h.

§ TurnOn()

nn::nlib::succinct::Sbv::TurnOn ( uint32_t  idx)
inlinenoexcept

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.

Definition at line 78 of file Sbv.h.


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