nlib
nn::nlib::succinct::Map Class Referencefinal

A compact integer to integer read-only associative array. More...

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

Public Types

typedef SetType::IdxType IdxType
 Integer index.
 
typedef std::pair< bool, uint32_t > FindType
 Pair of boolean value and integer. If the value is not found, the boolean value is false.
 

Public Member Functions

size_t MemSize () const noexcept
 Returns the amount of memory explicitly allocated by the class. More...
 
Constructor, Destructor, and Initialization
constexpr Map () noexcept
 Instantiates the object with default parameters (default constructor). Requires initialization with Init() after execution.
 
 ~Map () noexcept
 Destructor.
 
 Map (Map &&rhs)=default
 Instantiates the object (move constructor).
 
Mapoperator= (Map &&rhs)=default
 Move assignment operator.
 
 Map (Map &rhs, move_tag) noexcept
 Corresponds to a move constructor.
 
Mapassign (Map &rhs, move_tag) noexcept
 Corresponds to a move assignment operator.
 
bool Init (IdxType bv_size) noexcept
 Initializes an object. More...
 
void Reset () noexcept
 Resets this object to the state immediately after the default constructor was executed.
 
Construct Map

Sets data using TurnOn(), and then creates data with Build().

bool TurnOn (IdxType idx, uint32_t data) noexcept
 Adds a key and value. More...
 
bool Build () noexcept
 Builds an associative array. More...
 
Getting a Value and Key

May be used after Build.

FindType Find (IdxType idx) noexcept
 Specifies a key and gets the value in the associative array. More...
 
const FindType Find (IdxType idx) const noexcept
 Specifies a key and gets the value in the associative array. More...
 
const SetTypeGetKeys () const noexcept
 Gets the key set. More...
 
const ArrayTypeGetValues () const noexcept
 Gets the set of values. 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

A compact integer to integer read-only associative array.

Description
Stores the key integer using the SparseSet class, and stores the value integers using the CompressedArray class. This class is well-suited for implementing nowhere dense associative arrays.
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 the value corresponding to the key using TurnOn.
  4. Construct a dictionary using Build to run Rank/Select operations at constant time.
  5. The associative array is now ready to use.
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 244 of file Sbv.h.

Member Function Documentation

◆ Build()

nn::nlib::succinct::Map::Build ( )
inlinenoexcept

Builds an associative array.

Returns
Returns true when successful.

Definition at line 282 of file Sbv.h.

◆ Export()

nn::nlib::succinct::Map::Export ( BinaryWriter w) const
inlinenoexcept

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.

Definition at line 306 of file Sbv.h.

◆ Find() [1/2]

nn::nlib::succinct::Map::Find ( IdxType  idx)
inlinenoexcept

Specifies a key and gets the value in the associative array.

Parameters
[in]idxInteger value used as a key.
Returns
Returns a pair of types bool and uint32_t. The bool value is true when a value corresponding to the key is found.

Definition at line 283 of file Sbv.h.

◆ Find() [2/2]

nn::nlib::succinct::Map::Find ( IdxType  idx) const
inlinenoexcept

Specifies a key and gets the value in the associative array.

Parameters
[in]idxInteger value used as a key.
Returns
Returns a pair of types bool and uint32_t. The bool value is true when a value corresponding to the key is found.

Definition at line 289 of file Sbv.h.

◆ GetKeys()

nn::nlib::succinct::Map::GetKeys ( ) const
inlinenoexcept

Gets the key set.

Returns
Returns the set of keys (SparseSet type).

Definition at line 300 of file Sbv.h.

◆ GetValues()

nn::nlib::succinct::Map::GetValues ( ) const
inlinenoexcept

Gets the set of values.

Returns
Returns the set of values (CompressedArray type).

Definition at line 301 of file Sbv.h.

◆ Import()

nn::nlib::succinct::Map::Import ( BinaryReader r)
inlinenoexcept

Reads the written object.

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

Definition at line 311 of file Sbv.h.

◆ Init()

nn::nlib::succinct::Map::Init ( IdxType  bv_size)
inlinenoexcept

Initializes an object.

Parameters
[in]bv_sizeThe upper bound of the key (not including bv_size).
Returns
Returns true when successful.
Description
This allows a key value larger than 0, and smaller than bv_size.

Definition at line 273 of file Sbv.h.

◆ MemSize()

nn::nlib::succinct::Map::MemSize ( ) const
inlinenoexcept

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.

Definition at line 295 of file Sbv.h.

◆ TurnOn()

nn::nlib::succinct::Map::TurnOn ( IdxType  idx,
uint32_t  data 
)
inlinenoexcept

Adds a key and value.

Parameters
[in]idxInteger value used as a key.
[in]dataInteger value used as value.
Returns
Returns true when successful.
Description
To use this function repeatedly, idx value must monotonically increase. It means you need to set the keys in the ascending order of their values.

Definition at line 277 of file Sbv.h.


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