nlib
nn::nlib::succinct::Louds Class Referencefinal

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

#include "nn/nlib/succinct/Louds.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 bit array with a 32-bit non-negative integer.
 

Public Member Functions

int ToNodeId (Pos pos) const noexcept
 Gets the corresponding node ID from the bit array position. More...
 
int ToPos (NodeId nodeid) const noexcept
 Gets the corresponding bit array position from the node ID. More...
 
std::pair< bool, NodeIdGetNodeIdByPos (Pos pos) const noexcept
 Gets the corresponding node ID from the bit array position. More...
 
std::pair< bool, PosGetPosByNodeId (NodeId nodeid) const noexcept
 Gets the corresponding bit array 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 Louds () noexcept
 Instantiates the object with default parameters (default constructor). Requires initialization with Init() after execution.
 
 ~Louds () noexcept
 Destructor.
 
 Louds (Louds &&rhs) noexcept
 Instantiates the object (move constructor).
 
Loudsoperator= (Louds &&rhs) noexcept
 Move assignment operator.
 
 Louds (Louds &rhs, move_tag) noexcept
 Corresponds to a move constructor.
 
Loudsassign (Louds &rhs, move_tag) noexcept
 Corresponds to a move assignment operator.
 
template<class TREEITER >
bool Init (TREEITER &iter, uint32_t num_nodes) noexcept
 Generates a LOUDS 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 LOUDS
int FirstChild (Pos pos) const noexcept
 Gets the position of the first child of the specified node. More...
 
int NextSibling (Pos pos) const noexcept
 Gets the position of the next sibling node. More...
 
int PrevSibling (Pos pos) const noexcept
 Gets the position of the previous sibling node. More...
 
int Parent (Pos pos) const noexcept
 Gets the position of the parent node. More...
 
bool IsLeaf (Pos pos) const noexcept
 Determines whether the specified node is a leaf (or external) node. More...
 
A member function that only handles bit array positions.

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

std::pair< bool, PosGetPosOfFirstChild (Pos pos) const noexcept
 Gets the bit array position of the first child in the specified bit array position. More...
 
std::pair< bool, PosGetPosOfNextSibling (Pos pos) const noexcept
 Gets the bit array position of the next sibling node in the specified bit array position. More...
 
std::pair< bool, PosGetPosOfPrevSibling (Pos pos) const noexcept
 Gets the bit array position of the previous sibling node in the specified bit array position. More...
 
std::pair< bool, PosGetPosOfParent (Pos pos) const noexcept
 Gets the bit array position of the parent node in the specified bit array 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, 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 LOUDS data structure is implemented in the method described in the following links (with reversed bits).
A LOUDS data structure is used to represent an ordered tree, or a tree made up of nodes with ID values. This data structure is generated by running a breadth first search of the tree and doing the following when nodes are found.
  1. Output a 0 bit for every child.
  2. Output a 1 bit after that.
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_33.png
class MyTree {
public:
int GetNumChildren() {
return static_cast<int>(data_[cur_]);
}
bool BfsMoveNext() {
if (cur_ + 1 >= data_.size()) return false;
++cur_;
return true;
}
private:
std::vector<int> data_{ 3, 1, 0, 3, 0, 0, 1, 2, 0, 0, 0 };
size_t cur_ = 0;
} mytree;
Louds louds;
SUCCEED_IF(louds.Init(mytree, 11));
std::function<void(Louds::NodeId)> traverse = [&](Louds::NodeId nodeid) {
auto parent = louds.GetNodeIdOfParent(nodeid);
if (parent.first) {
nlib_printf("%u -> %u\n", parent.second, nodeid);
}
auto cld = louds.GetNodeIdOfFirstChild(nodeid);
if (cld.first) {
do {
traverse(cld.second);
cld = louds.GetNodeIdOfNextSibling(cld.second);
} while (cld.first);
}
};
traverse(0);
/*
Output:
0 -> 1
1 -> 4
0 -> 2
0 -> 3
3 -> 5
3 -> 6
6 -> 8
3 -> 7
7 -> 9
7 -> 10
*/

Definition at line 31 of file Louds.h.

Member Function Documentation

◆ Export()

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

◆ FirstChild()

nn::nlib::succinct::Louds::FirstChild ( Pos  pos) const
noexcept

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

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

◆ GetNodeIdByPos()

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

Gets the corresponding node ID from the bit array position.

Parameters
[in]posIndex indicating a bit within the bit array.
Returns
A pair of the boolean value and the node ID. The boolean value is true if the node ID exists.

Definition at line 55 of file Louds.h.

◆ GetNodeIdOfFirstChild()

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

◆ GetNodeIdOfNextSibling()

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

◆ GetNodeIdOfParent()

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

◆ GetNodeIdOfPrevSibling()

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

◆ GetPosByNodeId()

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

Gets the corresponding bit array 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 59 of file Louds.h.

◆ GetPosOfFirstChild()

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

Gets the bit array position of the first child in the specified bit array position.

Parameters
[in]posPosition in the bit array.
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 69 of file Louds.h.

◆ GetPosOfNextSibling()

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

Gets the bit array position of the next sibling node in the specified bit array position.

Parameters
[in]posPosition in the bit array.
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 73 of file Louds.h.

◆ GetPosOfParent()

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

Gets the bit array position of the parent node in the specified bit array position.

Parameters
[in]posPosition in the bit array.
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 81 of file Louds.h.

◆ GetPosOfPrevSibling()

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

Gets the bit array position of the previous sibling node in the specified bit array position.

Parameters
[in]posPosition in the bit array.
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 77 of file Louds.h.

◆ Import()

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

Reads the written object.

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

Definition at line 111 of file Louds.h.

◆ Init()

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

Generates a LOUDS from the tree object.

Parameters
[in]iterRoot 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.
  • int GetNumChildren(); // Return the number of child nodes.
  • bool BfsMoveNext(); // Moves to the next node breadth first.
The node ID is assigned breadth first starting from 0.

Definition at line 119 of file Louds.h.

◆ IsLeaf()

nn::nlib::succinct::Louds::IsLeaf ( Pos  pos) const
inlinenoexcept

Determines whether the specified node is a leaf (or external) node.

Parameters
[in]posPosition in the bit array.
Returns
Returns false if not a leaf node. All other values are true.

Definition at line 107 of file Louds.h.

◆ MemSize()

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

◆ NextSibling()

nn::nlib::succinct::Louds::NextSibling ( Pos  pos) const
noexcept

Gets the position of the next sibling node.

Parameters
[in]posPosition in the bit array.
Returns
Position of the next sibling node. Returns -1 if it does not exist.

◆ Parent()

nn::nlib::succinct::Louds::Parent ( Pos  pos) const
noexcept

Gets the position of the parent node.

Parameters
[in]posPosition in the bit array.
Returns
Position of the parent node. Returns -1 if the parent node does not exist.

◆ PrevSibling()

nn::nlib::succinct::Louds::PrevSibling ( Pos  pos) const
noexcept

Gets the position of the previous sibling node.

Parameters
[in]posPosition in the bit array.
Returns
Position of the previous sibling node. Returns -1 if it does not exist.

◆ ToNodeId()

nn::nlib::succinct::Louds::ToNodeId ( Pos  pos) const
noexcept

Gets the corresponding node ID from the bit array position.

Parameters
[in]posIndex indicating a bit within the bit array.
Returns
A non-negative integer when a node ID corresponds to pos. Returns -1 if it does not exist.

◆ ToPos()

nn::nlib::succinct::Louds::ToPos ( NodeId  nodeid) const
noexcept

Gets the corresponding bit array 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: