|
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, NodeId > | GetNodeIdByPos (Pos pos) const noexcept |
| Gets the corresponding node ID from the parenthesis position. More...
|
|
std::pair< bool, Pos > | GetPosByNodeId (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...
|
|
|
constexpr | Bp () noexcept |
| Instantiates the object with default parameters (default constructor). Requires initialization with Init() after execution.
|
|
| ~Bp () noexcept |
| Destructor.
|
|
Bp & | assign (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).
|
|
Bp & | operator= (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.
|
|
|
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...
|
|
|
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, Pos > | GetPosOfFirstChild (Pos pos) const noexcept |
| Gets the balanced parentheses position of the first child in the specified balanced parentheses position. More...
|
|
std::pair< bool, Pos > | GetPosOfLastChild (Pos pos) const noexcept |
| Gets the balanced parentheses position of the last child in the specified balanced parentheses position. More...
|
|
std::pair< bool, Pos > | GetPosOfNextSibling (Pos pos) const noexcept |
| Gets the balanced parentheses position of the next sibling node in the specified balanced parentheses position. More...
|
|
std::pair< bool, Pos > | GetPosOfPrevSibling (Pos pos) const noexcept |
| Gets the balanced parentheses position of the previous sibling node in the specified balanced parentheses position. More...
|
|
std::pair< bool, Pos > | GetPosOfParent (Pos pos) const noexcept |
| Gets the balanced parentheses position of the parent node in the specified balanced parentheses 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 > | GetNodeIdOfLastChild (NodeId nodeid) const noexcept |
| Gets the node ID of the last 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 "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.
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;
SUCCEED_IF(bp.Init(mytree, 11));
std::function<void(Bp::NodeId)> traverse = [&](
Bp::NodeId nodeid) {
auto parent = bp.GetNodeIdOfParent(nodeid);
if (parent.first) {
}
auto cld = bp.GetNodeIdOfFirstChild(nodeid);
if (cld.first) {
do {
traverse(cld.second);
cld = bp.GetNodeIdOfNextSibling(cld.second);
} while (cld.first);
}
};
traverse(0);
Definition at line 30 of file Bp.h.