nlib
nn::nlib::succinct::Bp Class Referencefinal

Provides a compact tree structure that can provide various operations in \(O(1)\) constant time. More...

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

Public Member Functions

template<class TREEITER >
bool Init (TREEITER &root, uint32_t num_nodes) noexcept
 Generates a parentheses representation of a tree from the tree object. More...
 
int ToNodeId (uint32_t pos) const noexcept
 Gets the node ID from the bit array position. More...
 
int ToPos (uint32_t nodeid) const noexcept
 Gets Bit array position from the node ID. 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
 Bp () noexcept
 Instantiates the object.
 
 ~Bp () noexcept
 Destructor.
 
Bpassign (Bp &rhs, move_tag)
 Assigns the object by using swap for a move.
 
 Bp (Bp &rhs, move_tag)
 Instantiates the object by using swap for a move.
 
 Bp (Bp &&rhs)
 Instantiates the object (move constructor). This function is useful when using C++11.
 
Bpoperator= (Bp &&rhs)
 Move assignment operator. This function is useful when using C++11.
 
void swap (Bp &rhs) noexcept
 Swaps the contents of an object.
 
Member Function to Search Within the Parentheses Representation of a Tree
int FindOpen (uint32_t pos) const noexcept
 Gets the position of the opening '(' parenthesis corresponding to the closing ')' parenthesis. More...
 
int FindClose (uint32_t pos) const noexcept
 Gets the position of the closing ')' parenthesis corresponding to the opening '(' parenthesis. More...
 
int Enclose (uint32_t pos) const noexcept
 Gets the position of the opening parenthesis that directly surround the specified parentheses. More...
 
int FirstChild (uint32_t pos) const noexcept
 Gets the position of the first opening parenthesis that is within the specified parentheses. More...
 
int LastChild (uint32_t pos) const noexcept
 Gets the position of the last closing parenthesis that is within the specified parentheses. More...
 
int NextSibling (uint32_t pos) const noexcept
 Gets the position of the parentheses corresponding to the next sibling node of the specified parentheses. More...
 
int PrevSibling (uint32_t pos) const noexcept
 Gets the position of the parentheses corresponding to the previous sibling node of the specified parentheses. More...
 
int Parent (uint32_t pos) const noexcept
 Returns the position of the parentheses equivalent to the parent node. 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

Provides a compact tree structure that can provide various operations in \(O(1)\) constant time.

Description
The "parentheses representation of a tree" data structure is implemented using the methodology described at the following link.
A parentheses representation of a tree is a method to describe an ordered tree (a tree with a node that has an ID). This tree is generated by outputting an opening parenthesis '(' when descending in a depth first search, and a closed parenthesis ')' when ascending. This enables you to represent a bit array as a tree.
This class implements member functions that support various tree operations with \(O(1)\) constant time based on this data structure.

Definition at line 30 of file Bp.h.

Member Function Documentation

◆ Enclose()

nn::nlib::succinct::Bp::Enclose ( uint32_t  pos) const
noexcept

Gets the position of the opening parenthesis that directly surround the specified parentheses.

Parameters
[in]posPosition of the parentheses.
Returns
Returns the position of the corresponding opening parenthesis. Returns -1 if it does not exist.
Description
Returns the position of the opening parenthesis of the pair of parentheses with the smallest area surrounding the parentheses at the specified position. This is equivalent to the operation that gets the parent node in a tree.

◆ Export()

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

◆ FindClose()

nn::nlib::succinct::Bp::FindClose ( uint32_t  pos) const
noexcept

Gets the position of the closing ')' parenthesis corresponding to the opening '(' parenthesis.

Parameters
[in]posPosition of the opening parenthesis.
Returns
Position of the corresponding closing parenthesis. Returns -1 if it does not exist.
The position of the closing parenthesis is returned when the position of the opening parenthesis is specified. The same value as the argument is returned when the specified position has a closing parenthesis.

◆ FindOpen()

nn::nlib::succinct::Bp::FindOpen ( uint32_t  pos) const
noexcept

Gets the position of the opening '(' parenthesis corresponding to the closing ')' parenthesis.

Parameters
[in]posPosition of the closing parenthesis.
Returns
Returns the position of the corresponding opening parenthesis. Returns -1 if it does not exist.
Description
The position of the opening parenthesis is returned when the position of the closing parenthesis is specified. The same value as the argument is returned when the specified position has a open parenthesis.

◆ FirstChild()

nn::nlib::succinct::Bp::FirstChild ( uint32_t  pos) const
noexcept

Gets the position of the first opening parenthesis that is within the specified parentheses.

Parameters
[in]posPosition of the parentheses.
Returns
Position of the opening parenthesis corresponding to a child node. Returns -1 if it does not exist.
Description
This is equivalent to the operation that accesses the first child node in a tree.

◆ Import()

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

Reads the written object.

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

◆ Init()

template<class TREEITER >
nn::nlib::succinct::Bp::Init ( TREEITER &  root,
uint32_t  num_nodes 
)
noexcept

Generates a parentheses representation of a tree from the tree object.

Parameters
[in]rootRoot node.
[in]num_nodesNumber of nodes.
Returns
Returns true when successful.
Description
The TREEITER type that is used as an argument must implement the following member functions.
  • const void* NodePtr(); // Returns a pointer to a node.
  • const void* ParentNodePtr(); // Returns a pointer to the parent node.
  • bool MoveNext(); // Moves to the next node depth first.
The node ID is assigned depth first, starting at 0.

Definition at line 69 of file Bp.h.

◆ LastChild()

nn::nlib::succinct::Bp::LastChild ( uint32_t  pos) const
noexcept

Gets the position of the last closing parenthesis that is within the specified parentheses.

Parameters
[in]posPosition of the parentheses.
Returns
Returns the position of the closing parenthesis corresponding to a child node. Returns -1 if it does not exist.
Description
This is equivalent to the operation that accesses the last child node in a tree.

◆ MemSize()

nn::nlib::succinct::Bp::MemSize ( ) const
noexcept

Returns the amount of memory explicitly allocated by the class.

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.
Returns
Returns the number of bytes.

◆ NextSibling()

nn::nlib::succinct::Bp::NextSibling ( uint32_t  pos) const
noexcept

Gets the position of the parentheses corresponding to the next sibling node of the specified parentheses.

Parameters
[in]posPosition of the parentheses.
Returns
Position of the opening parenthesis of the next sibling node.
Description
This is equivalent to the operation that accesses the next child node in a tree.

◆ Parent()

nn::nlib::succinct::Bp::Parent ( uint32_t  pos) const
inlinenoexcept

Returns the position of the parentheses equivalent to the parent node.

Parameters
[in]posPosition of the parentheses.
Returns
Position of the opening parenthesis corresponding to a parent node. Returns -1 if it does not exist.
Description
Runs Enclose internally.

Definition at line 52 of file Bp.h.

◆ PrevSibling()

nn::nlib::succinct::Bp::PrevSibling ( uint32_t  pos) const
noexcept

Gets the position of the parentheses corresponding to the previous sibling node of the specified parentheses.

Parameters
[in]posPosition of the parentheses.
Returns
Position of the closing parenthesis of the previous sibling node.
Description
This is equivalent to the operation that accesses the previous sibling node in a tree.

◆ ToNodeId()

nn::nlib::succinct::Bp::ToNodeId ( uint32_t  pos) const
noexcept

Gets the node ID from the bit array position.

Parameters
[in]posIndex representing the position of the parenthesis.
Returns
A non-negative integer when a node ID corresponds to pos. Returns -1 if it does not exist.

◆ ToPos()

nn::nlib::succinct::Bp::ToPos ( uint32_t  nodeid) const
noexcept

Gets Bit array position from the node ID.

Parameters
[in]nodeidNode ID.
Returns
Corresponding non-negative integer when nodeId exists. swap if it does not exist

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