|
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 | Louds () noexcept |
| デフォルトコンストラクタです。実行後Init() による初期化を必要とします。
|
|
| ~Louds () noexcept |
| デストラクタです。
|
|
| Louds (Louds &&rhs) noexcept |
| ムーブコンストラクタです。
|
|
Louds & | operator= (Louds &&rhs) noexcept |
| ムーブ代入演算子です。
|
|
| Louds (Louds &rhs, move_tag) noexcept |
| ムーブコンストラクタに相当します。
|
|
Louds & | assign (Louds &rhs, move_tag) noexcept |
| ムーブ代入演算子に相当します。
|
|
template<class TREEITER > |
bool | Init (TREEITER &iter, uint32_t num_nodes) noexcept |
| ツリーオブジェクトからLOUDSを生成します。 [詳解]
|
|
void | Reset () noexcept |
| このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
|
|
|
int | FirstChild (Pos pos) const noexcept |
| 指定されたノードの最初の子の位置を取得します。 [詳解]
|
|
int | NextSibling (Pos pos) const noexcept |
| 次の兄弟ノードの位置を取得します。 [詳解]
|
|
int | PrevSibling (Pos pos) const noexcept |
| 前の兄弟ノードの位置を取得します。 [詳解]
|
|
int | Parent (Pos pos) const noexcept |
| 親ノードの位置を取得します。 [詳解]
|
|
bool | IsLeaf (Pos pos) const noexcept |
| ノードが葉ノードかどうかを判定します。 [詳解]
|
|
|
ノード1つに対応するビット列上の位置は複数あり扱いがやや煩雑ですが、ノードIDへの変換を行わないことでオーバーヘッドを削減できます。
|
std::pair< bool, Pos > | GetPosOfFirstChild (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 > | 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)\)で行うことができるコンパクトなツリー構造です。
- 説明
- LOUDSと呼ばれるデータ構造を、以下に説明されている手法で実装しています(ビットは逆になってます)。
- LOUDSというのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、幅優先探索で木を探索してノードを見た際に、以下のようにすることで作成することができます。
-
0ビットを子の数だけ出力
-
その後に1ビットを1つ出力
- この表記法を使うことでビット列で木を表現することが可能になります。 このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。
- 例として以下のようなツリーを作成して辿るコードを示します。 ツリーの辿り方が独特であることとに注意してください。
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);
Louds.h の 31 行目に定義があります。