|
int | ToNodeId (Pos pos) const noexcept |
| 括弧の位置から対応するノードIDを取得します。 [詳解]
|
|
int | ToPos (NodeId nodeid) const noexcept |
| ノードIDから対応する括弧の位置を取得します。 [詳解]
|
|
std::pair< bool, NodeId > | GetNodeIdByPos (Pos pos) const noexcept |
| 括弧の位置から対応するノードIDを取得します。 [詳解]
|
|
std::pair< bool, Pos > | GetPosByNodeId (NodeId nodeid) const noexcept |
| ノードIDから対応する括弧の位置を取得します。 [詳解]
|
|
size_t | MemSize () const noexcept |
| このクラスが明示的に確保するメモリ量を返します。 [詳解]
|
|
|
constexpr | Bp () noexcept |
| デフォルトコンストラクタです。実行後Init() による初期化を必要とします。
|
|
| ~Bp () noexcept |
| デストラクタです。
|
|
Bp & | assign (Bp &rhs, move_tag) |
| ムーブ代入演算子に相当します。
|
|
| Bp (Bp &rhs, move_tag) |
| ムーブコンストラクタに相当します。
|
|
| Bp (Bp &&rhs) |
| ムーブコンストラクタです。
|
|
Bp & | operator= (Bp &&rhs) |
| ムーブ代入演算子です。
|
|
template<class TREEITER > |
bool | Init (TREEITER &root, uint32_t num_nodes) noexcept |
| ツリーオブジェクトから括弧木を生成します。 [詳解]
|
|
void | Reset () noexcept |
| このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
|
|
|
int | FindOpen (Pos pos) const noexcept |
| 閉じ括弧に対応する開き括弧の位置を取得します。 [詳解]
|
|
int | FindClose (Pos pos) const noexcept |
| 開き括弧に対応する閉じ括弧の位置を取得します。 [詳解]
|
|
int | Enclose (Pos pos) const noexcept |
| 指定された括弧を直接包む括弧組の開き括弧の位置を取得します。 [詳解]
|
|
int | FirstChild (Pos pos) const noexcept |
| 指定された括弧の中にある最初の開き括弧の位置を取得します。 [詳解]
|
|
int | LastChild (Pos pos) const noexcept |
| 指定された括弧の中にある最後の閉じ括弧の位置を取得します。 [詳解]
|
|
int | NextSibling (Pos pos) const noexcept |
| 指定された括弧に対応するノードの次の兄弟ノードに対応する括弧の位置を取得します。 [詳解]
|
|
int | PrevSibling (Pos pos) const noexcept |
| 指定された括弧に対応するノードの前の兄弟ノードに対応する括弧の位置を取得します。 [詳解]
|
|
int | Parent (Pos pos) const noexcept |
| 親ノードとなる括弧の位置を返します。 [詳解]
|
|
|
ノード1つに対応する括弧列上の位置は複数あり扱いがやや煩雑ですが、ノードIDへの変換を行わないことでオーバーヘッドを削減できます。
|
std::pair< bool, Pos > | GetPosOfFirstChild (Pos pos) const noexcept |
| 指定された括弧列上の位置の最初の子の括弧列上の位置を取得します。 [詳解]
|
|
std::pair< bool, Pos > | GetPosOfLastChild (Pos pos) const noexcept |
| 指定された括弧列上の位置の最後の子の括弧列上の位置を取得します。 [詳解]
|
|
std::pair< bool, Pos > | GetPosOfNextSibling (Pos pos) const noexcept |
| 指定された括弧列上の位置の次の兄弟ノードの括弧列上の位置を取得します。 [詳解]
|
|
std::pair< bool, Pos > | GetPosOfPrevSibling (Pos pos) const noexcept |
| 指定された括弧列上の位置の前の兄弟ノードの括弧列上の位置を取得します。 [詳解]
|
|
std::pair< bool, Pos > | GetPosOfParent (Pos pos) const noexcept |
| 指定された括弧列上の位置の親ノードの括弧列上の位置を取得します。 [詳解]
|
|
|
オーバーヘッドは存在しますが、ノードIDのみを利用することで内部のビット列を意識せずにLoudsを扱うことができます。
|
std::pair< bool, NodeId > | GetNodeIdOfFirstChild (NodeId nodeid) const noexcept |
| 指定されたノードの最初の子のノードIDを取得します。 [詳解]
|
|
std::pair< bool, NodeId > | GetNodeIdOfLastChild (NodeId nodeid) const noexcept |
| 指定されたノードの最後の子のノードIDを取得します。 [詳解]
|
|
std::pair< bool, NodeId > | GetNodeIdOfNextSibling (NodeId nodeid) const noexcept |
| 指定されたノードの次の兄弟ノードのノードIDを取得します。 [詳解]
|
|
std::pair< bool, NodeId > | GetNodeIdOfPrevSibling (NodeId nodeid) const noexcept |
| 指定されたノードの前の兄弟ノードのノードIDを取得します。 [詳解]
|
|
std::pair< bool, NodeId > | GetNodeIdOfParent (NodeId nodeid) const noexcept |
| 指定されたノードの親ノードのノードIDを取得します。 [詳解]
|
|
|
bool | Export (BinaryWriter *w) const noexcept |
| オブジェクトを(ファイルに)書き出します。 [詳解]
|
|
bool | Import (BinaryReader *r) noexcept |
| 書き出されたオブジェクトを読み出します。 [詳解]
|
|
各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。
- 説明
- 括弧木と呼ばれるデータ構造を、以下の論文で説明されている手法で実装しています。
- 括弧木というのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、深さ優先探索で木を探索したときに、行きがけに'('、帰りがけに')'を出力することで作成することができます。 この表記法を使うことでビット列で木を表現することが可能になります。
- このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。
- 例として以下のようなツリーを作成して辿るコードを示します。 ツリーの辿り方が独特であることとに注意してください。
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);
Bp.h の 30 行目に定義があります。