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 Member Functions

template<class TREEITER >
bool Init (TREEITER &iter, uint32_t num_nodes) noexcept
 Generates a LOUDS 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 the 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
constexpr Louds () noexcept
 Instantiates the object.
 
 ~Louds () noexcept
 Destructor.
 
 Louds (Louds &&rhs) noexcept
 Instantiates the object (move constructor). This function is useful when using C++11.
 
Loudsoperator= (Louds &&rhs) noexcept
 Move assignment operator. This function is useful when using C++11.
 
 Louds (Louds &rhs, move_tag) noexcept
 Corresponds to a move constructor.
 
Loudsassign (Louds &rhs, move_tag) noexcept
 Corresponds to a move assignment operator.
 
void swap (Louds &rhs) noexcept
 Swaps the contents of an object. More...
 
Member Function to Search LOUDS
int FirstChild (uint32_t pos) const noexcept
 Gets the position of the first child of the specified node. More...
 
int NextSibling (uint32_t pos) const noexcept
 Gets the position of the next sibling node. More...
 
int PrevSibling (uint32_t pos) const noexcept
 Gets the position of the previous sibling node. More...
 
int Parent (uint32_t pos) const noexcept
 Gets the position of the parent node. More...
 
bool IsLeaf (uint32_t pos) const noexcept
 Determines whether the specified node is a leaf (or external) 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.

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 67 of file Louds.h.

◆ FirstChild()

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

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

Parameters
[in]posPosition in the bit array.
Returns
Position in the bit array corresponding to the child node. Returns -1 if it does not exist.

◆ 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 68 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 76 of file Louds.h.

◆ IsLeaf()

nn::nlib::succinct::Louds::IsLeaf ( uint32_t  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 62 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 65 of file Louds.h.

◆ NextSibling()

nn::nlib::succinct::Louds::NextSibling ( uint32_t  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 ( uint32_t  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 ( uint32_t  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.

◆ swap()

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

Swaps the contents of an object.

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

Definition at line 48 of file Louds.h.

◆ ToNodeId()

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

Gets the 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 ( uint32_t  nodeid) const
noexcept

Gets the 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: