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

bool Build () noexcept
 Builds an associative array. More...
 
size_t MemSize () const noexcept
 Returns the amount of memory explicitly allocated by the class. More...
 
void Reset () noexcept
 Returns the object to the state immediately after the constructor is called.
 
Basic Member Functions
constexpr Map () noexcept
 Instantiates the object.
 
 ~Map () noexcept
 Destructor.
 
 Map (Map &&rhs)=default
 Instantiates the object (move constructor). This function is useful when using C++11.
 
Mapoperator= (Map &&rhs)=default
 Move assignment operator. This function is useful when using C++11.
 
 Map (Map &rhs, move_tag) noexcept
 Corresponds to a move constructor.
 
Mapassign (Map &rhs, move_tag) noexcept
 Corresponds to a move assignment operator.
 
void swap (Map &rhs) noexcept
 Swaps the contents of an object. More...
 
Construct Map

Member function used before Build.

bool Init (IdxType bv_size) noexcept
 Initializes an object. More...
 
bool TurnOn (IdxType idx, uint32_t data) noexcept
 Adds a key and value. 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 247 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 286 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 310 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 287 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 293 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 304 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 305 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 315 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 277 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.
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 299 of file Sbv.h.

◆ swap()

void nn::nlib::succinct::Map::swap ( Map rhs)
inlinenoexcept

Swaps the contents of an object.

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

Definition at line 349 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 281 of file Sbv.h.


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