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 Types

typedef uint32_t NodeId
 Represents a node ID with a 32-bit non-negative integer.
 
typedef uint32_t Pos
 Represents an index in the balanced parentheses with a 32-bit non-negative integer.
 

Public Member Functions

int ToNodeId (Pos pos) const noexcept
 Gets the corresponding node ID from the parenthesis position. More...
 
int ToPos (NodeId nodeid) const noexcept
 Gets the corresponding parenthesis position from the node ID. More...
 
std::pair< bool, NodeIdGetNodeIdByPos (Pos pos) const noexcept
 Gets the corresponding node ID from the parenthesis position. More...
 
std::pair< bool, PosGetPosByNodeId (NodeId nodeid) const noexcept
 Gets the corresponding parenthesis position from the node ID. More...
 
size_t MemSize () const noexcept
 Returns the amount of memory explicitly allocated by the class. More...
 
Constructor, Destructor, and Initialization
constexpr Bp () noexcept
 Instantiates the object with default parameters (default constructor). Requires initialization with Init() after execution.
 
 ~Bp () noexcept
 Destructor.
 
Bpassign (Bp &rhs, move_tag)
 Corresponds to a move assignment operator.
 
 Bp (Bp &rhs, move_tag)
 Corresponds to a move constructor.
 
 Bp (Bp &&rhs)
 Instantiates the object (move constructor).
 
Bpoperator= (Bp &&rhs)
 Move assignment operator.
 
template<class TREEITER >
bool Init (TREEITER &root, uint32_t num_nodes) noexcept
 Generates a parentheses representation of a tree from the tree object. More...
 
void Reset () noexcept
 Resets this object to the state immediately after the default constructor was executed.
 
Member Function to Search Within the Parentheses Representation of a Tree
int FindOpen (Pos pos) const noexcept
 Gets the position of the opening '(' parenthesis corresponding to the closing ')' parenthesis. More...
 
int FindClose (Pos pos) const noexcept
 Gets the position of the closing ')' parenthesis corresponding to the opening '(' parenthesis. More...
 
int Enclose (Pos pos) const noexcept
 Gets the position of the opening parenthesis that directly surround the specified parentheses. More...
 
int FirstChild (Pos pos) const noexcept
 Gets the position of the first opening parenthesis that is within the specified parentheses. More...
 
int LastChild (Pos pos) const noexcept
 Gets the position of the last closing parenthesis that is within the specified parentheses. More...
 
int NextSibling (Pos pos) const noexcept
 Gets the position of the parentheses corresponding to the next sibling node of the specified parentheses. More...
 
int PrevSibling (Pos pos) const noexcept
 Gets the position of the parentheses corresponding to the previous sibling node of the specified parentheses. More...
 
int Parent (Pos pos) const noexcept
 Returns the position of the parentheses equivalent to the parent node. More...
 
A member function that only handles balanced parentheses positions.

Although handling of balanced parentheses positions corresponding to one node is slightly complicated as there are multiple balanced parentheses positions, you can reduce overhead by not converting to node IDs.

std::pair< bool, PosGetPosOfFirstChild (Pos pos) const noexcept
 Gets the balanced parentheses position of the first child in the specified balanced parentheses position. More...
 
std::pair< bool, PosGetPosOfLastChild (Pos pos) const noexcept
 Gets the balanced parentheses position of the last child in the specified balanced parentheses position. More...
 
std::pair< bool, PosGetPosOfNextSibling (Pos pos) const noexcept
 Gets the balanced parentheses position of the next sibling node in the specified balanced parentheses position. More...
 
std::pair< bool, PosGetPosOfPrevSibling (Pos pos) const noexcept
 Gets the balanced parentheses position of the previous sibling node in the specified balanced parentheses position. More...
 
std::pair< bool, PosGetPosOfParent (Pos pos) const noexcept
 Gets the balanced parentheses position of the parent node in the specified balanced parentheses position. More...
 
A member function that only handles node IDs.

Althugh overhead exists, Louds can be handled without being aware of internal bit arrays by using node IDs only.

std::pair< bool, NodeIdGetNodeIdOfFirstChild (NodeId nodeid) const noexcept
 Gets the node ID of the first child of the specified node. More...
 
std::pair< bool, NodeIdGetNodeIdOfLastChild (NodeId nodeid) const noexcept
 Gets the node ID of the last child of the specified node. More...
 
std::pair< bool, NodeIdGetNodeIdOfNextSibling (NodeId nodeid) const noexcept
 Gets the node ID of the next sibling node of the specified node. More...
 
std::pair< bool, NodeIdGetNodeIdOfPrevSibling (NodeId nodeid) const noexcept
 Gets the node ID of the previous sibling node of the specified node. More...
 
std::pair< bool, NodeIdGetNodeIdOfParent (NodeId nodeid) const noexcept
 Gets the node ID of the parent node of the specified 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.
The following sample code shows how the tree below is created and traced. Note that the tree is traced uniquely.
dot_inline_dotgraph_32.png
class MyTree {
public:
const void* NodePtr() {
return &data_[cur_];
}
const void* ParentNodePtr() {
int parent = data_[cur_];
return parent >= 0 ? &data_[parent] : nullptr;
}
bool MoveNext() {
if (cur_ + 1 >= data_.size()) return false;
++cur_;
return true;
}
private:
std::vector<int> data_{ -1, 0, 1, 0, 0, 4, 4, 6, 4, 8, 8 };
size_t cur_ = 0;
} mytree;
Bp bp;
SUCCEED_IF(bp.Init(mytree, 11));
std::function<void(Bp::NodeId)> traverse = [&](Bp::NodeId nodeid) {
auto parent = bp.GetNodeIdOfParent(nodeid);
if (parent.first) {
nlib_printf("%u -> %u\n", parent.second, nodeid);
}
auto cld = bp.GetNodeIdOfFirstChild(nodeid);
if (cld.first) {
do {
traverse(cld.second);
cld = bp.GetNodeIdOfNextSibling(cld.second);
} while (cld.first);
}
};
traverse(0);
/*
Output:
0 -> 1
1 -> 2
0 -> 3
0 -> 4
4 -> 5
4 -> 6
6 -> 7
4 -> 8
8 -> 9
8 -> 10
*/

Definition at line 30 of file Bp.h.

Member Function Documentation

◆ Enclose()

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

◆ GetNodeIdByPos()

nn::nlib::succinct::Bp::GetNodeIdByPos ( Pos  pos) const
inlinenoexcept

Gets the corresponding node ID from the parenthesis position.

Parameters
[in]posIndex representing the position of the parenthesis.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 51 of file Bp.h.

◆ GetNodeIdOfFirstChild()

nn::nlib::succinct::Bp::GetNodeIdOfFirstChild ( NodeId  nodeid) const
inlinenoexcept

Gets the node ID of the first child of the specified node.

Parameters
[in]nodeidNode ID.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 81 of file Bp.h.

◆ GetNodeIdOfLastChild()

nn::nlib::succinct::Bp::GetNodeIdOfLastChild ( NodeId  nodeid) const
inlinenoexcept

Gets the node ID of the last child of the specified node.

Parameters
[in]nodeidNode ID.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 86 of file Bp.h.

◆ GetNodeIdOfNextSibling()

nn::nlib::succinct::Bp::GetNodeIdOfNextSibling ( NodeId  nodeid) const
inlinenoexcept

Gets the node ID of the next sibling node of the specified node.

Parameters
[in]nodeidNode ID.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 91 of file Bp.h.

◆ GetNodeIdOfParent()

nn::nlib::succinct::Bp::GetNodeIdOfParent ( NodeId  nodeid) const
inlinenoexcept

Gets the node ID of the parent node of the specified node.

Parameters
[in]nodeidNode ID.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 101 of file Bp.h.

◆ GetNodeIdOfPrevSibling()

nn::nlib::succinct::Bp::GetNodeIdOfPrevSibling ( NodeId  nodeid) const
inlinenoexcept

Gets the node ID of the previous sibling node of the specified node.

Parameters
[in]nodeidNode ID.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 96 of file Bp.h.

◆ GetPosByNodeId()

nn::nlib::succinct::Bp::GetPosByNodeId ( NodeId  nodeid) const
inlinenoexcept

Gets the corresponding parenthesis position from the node ID.

Parameters
[in]nodeidNode ID.
Returns
A pair of the boolean value and the bit array position. The boolean value is true if the bit array position exists.

Definition at line 55 of file Bp.h.

◆ GetPosOfFirstChild()

nn::nlib::succinct::Bp::GetPosOfFirstChild ( Pos  pos) const
inlinenoexcept

Gets the balanced parentheses position of the first child in the specified balanced parentheses position.

Parameters
[in]posPosition in the balanced parentheses.
Returns
A pair of the boolean value and the balanced parentheses position. The boolean value is true if the balanced parentheses position exists.

Definition at line 60 of file Bp.h.

◆ GetPosOfLastChild()

nn::nlib::succinct::Bp::GetPosOfLastChild ( Pos  pos) const
inlinenoexcept

Gets the balanced parentheses position of the last child in the specified balanced parentheses position.

Parameters
[in]posPosition in the balanced parentheses.
Returns
A pair of the boolean value and the balanced parentheses position. The boolean value is true if the balanced parentheses position exists.

Definition at line 64 of file Bp.h.

◆ GetPosOfNextSibling()

nn::nlib::succinct::Bp::GetPosOfNextSibling ( Pos  pos) const
inlinenoexcept

Gets the balanced parentheses position of the next sibling node in the specified balanced parentheses position.

Parameters
[in]posPosition in the balanced parentheses.
Returns
A pair of the boolean value and the balanced parentheses position. The boolean value is true if the balanced parentheses position exists.

Definition at line 68 of file Bp.h.

◆ GetPosOfParent()

nn::nlib::succinct::Bp::GetPosOfParent ( Pos  pos) const
inlinenoexcept

Gets the balanced parentheses position of the parent node in the specified balanced parentheses position.

Parameters
[in]posPosition in the balanced parentheses.
Returns
A pair of the boolean value and the balanced parentheses position. The boolean value is true if the balanced parentheses position exists.

Definition at line 76 of file Bp.h.

◆ GetPosOfPrevSibling()

nn::nlib::succinct::Bp::GetPosOfPrevSibling ( Pos  pos) const
inlinenoexcept

Gets the balanced parentheses position of the previous sibling node in the specified balanced parentheses position.

Parameters
[in]posPosition in the balanced parentheses.
Returns
A pair of the boolean value and the balanced parentheses position. The boolean value is true if the balanced parentheses position exists.

Definition at line 72 of file Bp.h.

◆ 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 (descending order).
The node ID is assigned depth first (descending order), starting at 0.

Definition at line 123 of file Bp.h.

◆ LastChild()

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

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.

◆ NextSibling()

nn::nlib::succinct::Bp::NextSibling ( Pos  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 ( Pos  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 49 of file Bp.h.

◆ PrevSibling()

nn::nlib::succinct::Bp::PrevSibling ( Pos  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 ( Pos  pos) const
noexcept

Gets the corresponding node ID from the parenthesis 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 ( NodeId  nodeid) const
noexcept

Gets the corresponding parenthesis position from the node ID.

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

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