Provides a compact tree structure that can provide various operations in \(O(1)\)
constant time.
More...
#include "nn/nlib/succinct/Louds.h"
|
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.
|
|
|
| Louds () noexcept |
| Instantiates the object.
|
|
| ~Louds () noexcept |
| Destructor.
|
|
Louds & | assign (Louds &rhs, move_tag) |
| Assigns the object by using swap for a move.
|
|
| Louds (Louds &rhs, move_tag) |
| Instantiates the object by using swap for a move.
|
|
| Louds (Louds &&rhs) |
| Instantiates the object (move constructor). This function is useful when using C++11.
|
|
Louds & | operator= (Louds &&rhs) |
| Move assignment operator. This function is useful when using C++11.
|
|
void | swap (Louds &rhs) noexcept |
| Swaps the contents of an object.
|
|
|
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...
|
|
|
bool | Export (BinaryWriter *w) const noexcept |
| Writes the object to the file. More...
|
|
bool | Import (BinaryReader *r) noexcept |
| Reads the written object. More...
|
|
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.
-
Output a 0 bit for every child.
-
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 17 of file Louds.h.
§ Export()
Writes the object to the file.
- Parameters
-
- 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 38 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] | pos | Position in the bit array. |
- Returns
- Position in the bit array corresponding to the child node. Returns
-1
if it does not exist.
§ Import()
Reads the written object.
- Parameters
-
- Returns
- Returns
true
when import is successful.
Definition at line 39 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] | iter | Root node. |
[in] | num_nodes | Number 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 47 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] | pos | Position in the bit array. |
- Returns
- Returns
false
if not a leaf node. All other values are true
.
Definition at line 33 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 36 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] | pos | Position 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] | pos | Position 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] | pos | Position in the bit array. |
- Returns
- Position of the previous sibling node. Returns
-1
if it does not exist.
§ ToNodeId()
nn::nlib::succinct::Louds::ToNodeId |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
Gets the node ID from the bit array position.
- Parameters
-
[in] | pos | Index 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
-
- 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: