|
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, NodeId > | GetNodeIdByPos (Pos pos) const noexcept |
| Gets the corresponding node ID from the bit array position. More...
|
|
std::pair< bool, Pos > | GetPosByNodeId (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...
|
|
|
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).
|
|
Louds & | operator= (Louds &&rhs) noexcept |
| Move assignment operator.
|
|
| Louds (Louds &rhs, move_tag) noexcept |
| Corresponds to a move constructor.
|
|
Louds & | assign (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.
|
|
|
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...
|
|
|
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, Pos > | GetPosOfFirstChild (Pos pos) const noexcept |
| Gets the bit array position of the first child in the specified bit array position. More...
|
|
std::pair< bool, Pos > | GetPosOfNextSibling (Pos pos) const noexcept |
| Gets the bit array position of the next sibling node in the specified bit array position. More...
|
|
std::pair< bool, Pos > | GetPosOfPrevSibling (Pos pos) const noexcept |
| Gets the bit array position of the previous sibling node in the specified bit array position. More...
|
|
std::pair< bool, Pos > | GetPosOfParent (Pos pos) const noexcept |
| Gets the bit array position of the parent node in the specified bit array position. More...
|
|
|
Althugh overhead exists, Louds can be handled without being aware of internal bit arrays by using node IDs only.
|
std::pair< bool, NodeId > | GetNodeIdOfFirstChild (NodeId nodeid) const noexcept |
| Gets the node ID of the first child of the specified node. More...
|
|
std::pair< bool, NodeId > | GetNodeIdOfNextSibling (NodeId nodeid) const noexcept |
| Gets the node ID of the next sibling node of the specified node. More...
|
|
std::pair< bool, NodeId > | GetNodeIdOfPrevSibling (NodeId nodeid) const noexcept |
| Gets the node ID of the previous sibling node of the specified node. More...
|
|
std::pair< bool, NodeId > | GetNodeIdOfParent (NodeId nodeid) const noexcept |
| Gets the node ID of the parent node of the specified 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.
- The following sample code shows how the tree below is created and traced. Note that the tree is traced uniquely.
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;
SUCCEED_IF(louds.Init(mytree, 11));
std::function<void(Louds::NodeId)> traverse = [&](
Louds::NodeId nodeid) {
auto parent = louds.GetNodeIdOfParent(nodeid);
if (parent.first) {
}
auto cld = louds.GetNodeIdOfFirstChild(nodeid);
if (cld.first) {
do {
traverse(cld.second);
cld = louds.GetNodeIdOfNextSibling(cld.second);
} while (cld.first);
}
};
traverse(0);
Definition at line 31 of file Louds.h.