nlib
nn::nlib::succinct::Louds クラスfinal

各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。 [詳解]

#include "nn/nlib/succinct/Louds.h"

公開型

typedef uint32_t NodeId
 32bit非負整数でノードIDを表します。
 
typedef uint32_t Pos
 32bit非負整数でビット列上のインデックスを表します。
 

公開メンバ関数

int ToNodeId (Pos pos) const noexcept
 ビット列の位置から対応するノードIDを取得します。 [詳解]
 
int ToPos (NodeId nodeid) const noexcept
 ノードIDから対応するビット列での位置を取得します。 [詳解]
 
std::pair< bool, NodeIdGetNodeIdByPos (Pos pos) const noexcept
 ビット列の位置から対応するノードIDを取得します。 [詳解]
 
std::pair< bool, PosGetPosByNodeId (NodeId nodeid) const noexcept
 ノードIDから対応するビット列での位置を取得します。 [詳解]
 
size_t MemSize () const noexcept
 このクラスが明示的に確保するメモリ量を返します。 [詳解]
 
コンストラクタ、デストラクタ、及び初期化
constexpr Louds () noexcept
 デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
 
 ~Louds () noexcept
 デストラクタです。
 
 Louds (Louds &&rhs) noexcept
 ムーブコンストラクタです。
 
Loudsoperator= (Louds &&rhs) noexcept
 ムーブ代入演算子です。
 
 Louds (Louds &rhs, move_tag) noexcept
 ムーブコンストラクタに相当します。
 
Loudsassign (Louds &rhs, move_tag) noexcept
 ムーブ代入演算子に相当します。
 
template<class TREEITER >
bool Init (TREEITER &iter, uint32_t num_nodes) noexcept
 ツリーオブジェクトからLOUDSを生成します。 [詳解]
 
void Reset () noexcept
 このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
 
LOUDSの探索を行うためのメンバ関数
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, PosGetPosOfFirstChild (Pos pos) const noexcept
 指定されたビット列上の位置の最初の子のビット列上の位置を取得します。 [詳解]
 
std::pair< bool, PosGetPosOfNextSibling (Pos pos) const noexcept
 指定されたビット列上の位置の次の兄弟ノードのビット列上の位置を取得します。 [詳解]
 
std::pair< bool, PosGetPosOfPrevSibling (Pos pos) const noexcept
 指定されたビット列上の位置の前の兄弟ノードのビット列上の位置を取得します。 [詳解]
 
std::pair< bool, PosGetPosOfParent (Pos pos) const noexcept
 指定されたビット列上の位置の親ノードのビット列上の位置を取得します。 [詳解]
 
ノードIDのみを扱うメンバ関数

オーバーヘッドは存在しますが、ノードIDのみを利用することで内部のビット列を意識せずにLoudsを扱うことができます。

std::pair< bool, NodeIdGetNodeIdOfFirstChild (NodeId nodeid) const noexcept
 指定されたノードの最初の子のノードIDを取得します。 [詳解]
 
std::pair< bool, NodeIdGetNodeIdOfNextSibling (NodeId nodeid) const noexcept
 指定されたノードの次の兄弟ノードのノードIDを取得します。 [詳解]
 
std::pair< bool, NodeIdGetNodeIdOfPrevSibling (NodeId nodeid) const noexcept
 指定されたノードの前の兄弟ノードのノードIDを取得します。 [詳解]
 
std::pair< bool, NodeIdGetNodeIdOfParent (NodeId nodeid) const noexcept
 指定されたノードの親ノードのノードIDを取得します。 [詳解]
 
インポートとエクスポート
bool Export (BinaryWriter *w) const noexcept
 オブジェクトを(ファイルに)書き出します。 [詳解]
 
bool Import (BinaryReader *r) noexcept
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。

説明
LOUDSと呼ばれるデータ構造を、以下に説明されている手法で実装しています(ビットは逆になってます)。
LOUDSというのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、幅優先探索で木を探索してノードを見た際に、以下のようにすることで作成することができます。
  1. 0ビットを子の数だけ出力
  2. その後に1ビットを1つ出力
この表記法を使うことでビット列で木を表現することが可能になります。 このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。
例として以下のようなツリーを作成して辿るコードを示します。 ツリーの辿り方が独特であることとに注意してください。
dot_inline_dotgraph_33.png
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;
Louds louds;
SUCCEED_IF(louds.Init(mytree, 11));
std::function<void(Louds::NodeId)> traverse = [&](Louds::NodeId nodeid) {
auto parent = louds.GetNodeIdOfParent(nodeid);
if (parent.first) {
nlib_printf("%u -> %u\n", parent.second, nodeid);
}
auto cld = louds.GetNodeIdOfFirstChild(nodeid);
if (cld.first) {
do {
traverse(cld.second);
cld = louds.GetNodeIdOfNextSibling(cld.second);
} while (cld.first);
}
};
traverse(0);
/*
Output:
0 -> 1
1 -> 4
0 -> 2
0 -> 3
3 -> 5
3 -> 6
6 -> 8
3 -> 7
7 -> 9
7 -> 10
*/

Louds.h31 行目に定義があります。

関数詳解

◆ Export()

nn::nlib::succinct::Louds::Export ( BinaryWriter w) const
inlinenoexcept

オブジェクトを(ファイルに)書き出します。

引数
[in]w書き出し用オブジェクト
戻り値
成功した場合はtrue
説明
書きだしたデータはImport()関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。

Louds.h110 行目に定義があります。

◆ FirstChild()

nn::nlib::succinct::Louds::FirstChild ( Pos  pos) const
noexcept

指定されたノードの最初の子の位置を取得します。

引数
[in]posビット列上の位置
戻り値
ブール値とビット列での位置のペア。ブール値はビット列での位置が存在する場合にtrue

◆ GetNodeIdByPos()

nn::nlib::succinct::Louds::GetNodeIdByPos ( Pos  pos) const
inlinenoexcept

ビット列の位置から対応するノードIDを取得します。

引数
[in]posビット列内のビットを指すインデックス
戻り値
ブール値とノードIDのペア。ブール値はノードIDが存在する場合にtrue

Louds.h55 行目に定義があります。

◆ GetNodeIdOfFirstChild()

nn::nlib::succinct::Louds::GetNodeIdOfFirstChild ( NodeId  nodeid) const
inlinenoexcept

指定されたノードの最初の子のノードIDを取得します。

引数
[in]nodeidノードID
戻り値
ブール値とノードIDのペア。ブール値はノードIDが存在する場合にtrue

Louds.h86 行目に定義があります。

◆ GetNodeIdOfNextSibling()

nn::nlib::succinct::Louds::GetNodeIdOfNextSibling ( NodeId  nodeid) const
inlinenoexcept

指定されたノードの次の兄弟ノードのノードIDを取得します。

引数
[in]nodeidノードID
戻り値
ブール値とノードIDのペア。ブール値はノードIDが存在する場合にtrue

Louds.h91 行目に定義があります。

◆ GetNodeIdOfParent()

nn::nlib::succinct::Louds::GetNodeIdOfParent ( NodeId  nodeid) const
inlinenoexcept

指定されたノードの親ノードのノードIDを取得します。

引数
[in]nodeidノードID
戻り値
ブール値とノードIDのペア。ブール値はノードIDが存在する場合にtrue

Louds.h101 行目に定義があります。

◆ GetNodeIdOfPrevSibling()

nn::nlib::succinct::Louds::GetNodeIdOfPrevSibling ( NodeId  nodeid) const
inlinenoexcept

指定されたノードの前の兄弟ノードのノードIDを取得します。

引数
[in]nodeidノードID
戻り値
ブール値とノードIDのペア。ブール値はノードIDが存在する場合にtrue

Louds.h96 行目に定義があります。

◆ GetPosByNodeId()

nn::nlib::succinct::Louds::GetPosByNodeId ( NodeId  nodeid) const
inlinenoexcept

ノードIDから対応するビット列での位置を取得します。

引数
[in]nodeidノードID
戻り値
ブール値とビット列での位置のペア。ブール値はビット列での位置が存在する場合にtrue

Louds.h59 行目に定義があります。

◆ GetPosOfFirstChild()

nn::nlib::succinct::Louds::GetPosOfFirstChild ( Pos  pos) const
inlinenoexcept

指定されたビット列上の位置の最初の子のビット列上の位置を取得します。

引数
[in]posビット列上の位置
戻り値
ブール値とビット列上の位置のペア。ブール値はビット列上の位置が存在する場合にtrue

Louds.h69 行目に定義があります。

◆ GetPosOfNextSibling()

nn::nlib::succinct::Louds::GetPosOfNextSibling ( Pos  pos) const
inlinenoexcept

指定されたビット列上の位置の次の兄弟ノードのビット列上の位置を取得します。

引数
[in]posビット列上の位置
戻り値
ブール値とビット列上の位置のペア。ブール値はビット列上の位置が存在する場合にtrue

Louds.h73 行目に定義があります。

◆ GetPosOfParent()

nn::nlib::succinct::Louds::GetPosOfParent ( Pos  pos) const
inlinenoexcept

指定されたビット列上の位置の親ノードのビット列上の位置を取得します。

引数
[in]posビット列上の位置
戻り値
ブール値とビット列上の位置のペア。ブール値はビット列上の位置が存在する場合にtrue

Louds.h81 行目に定義があります。

◆ GetPosOfPrevSibling()

nn::nlib::succinct::Louds::GetPosOfPrevSibling ( Pos  pos) const
inlinenoexcept

指定されたビット列上の位置の前の兄弟ノードのビット列上の位置を取得します。

引数
[in]posビット列上の位置
戻り値
ブール値とビット列上の位置のペア。ブール値はビット列上の位置が存在する場合にtrue

Louds.h77 行目に定義があります。

◆ Import()

nn::nlib::succinct::Louds::Import ( BinaryReader r)
inlinenoexcept

書き出されたオブジェクトを読み出します。

引数
[in]r読み出し用オブジェクト
戻り値
インポートが成功した場合はtrue

Louds.h111 行目に定義があります。

◆ Init()

template<class TREEITER >
nn::nlib::succinct::Louds::Init ( TREEITER &  iter,
uint32_t  num_nodes 
)
noexcept

ツリーオブジェクトからLOUDSを生成します。

引数
[in]iter根ノード
[in]num_nodesノード数
戻り値
成功した場合はtrue
説明
引数となるTREEITER 型は以下のメンバ関数を実装している必要があります。
  • int GetNumChildren(); // ノードの子の数を返す
  • bool BfsMoveNext(); // 幅優先でたどって次のノードに移動
ノードIDは幅優先順で0からついていきます。

Louds.h119 行目に定義があります。

◆ IsLeaf()

nn::nlib::succinct::Louds::IsLeaf ( Pos  pos) const
inlinenoexcept

ノードが葉ノードかどうかを判定します。

引数
[in]posビット列上の位置
戻り値
葉ノードでなければfalse。それ以外ならtrue

Louds.h107 行目に定義があります。

◆ MemSize()

nn::nlib::succinct::Louds::MemSize ( ) const
inlinenoexcept

このクラスが明示的に確保するメモリ量を返します。

戻り値
バイト数
説明
実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。

Louds.h108 行目に定義があります。

◆ NextSibling()

nn::nlib::succinct::Louds::NextSibling ( Pos  pos) const
noexcept

次の兄弟ノードの位置を取得します。

引数
[in]posビット列上の位置
戻り値
次の兄弟ノードの位置。存在しなければ-1

◆ Parent()

nn::nlib::succinct::Louds::Parent ( Pos  pos) const
noexcept

親ノードの位置を取得します。

引数
[in]posビット列上の位置
戻り値
親ノードの位置。存在しなければ-1

◆ PrevSibling()

nn::nlib::succinct::Louds::PrevSibling ( Pos  pos) const
noexcept

前の兄弟ノードの位置を取得します。

引数
[in]posビット列上の位置
戻り値
前の兄弟ノードの位置。存在しなければ-1

◆ ToNodeId()

nn::nlib::succinct::Louds::ToNodeId ( Pos  pos) const
noexcept

ビット列の位置から対応するノードIDを取得します。

引数
[in]posビット列内のビットを指すインデックス
戻り値
pos に対応するノードIDが存在する場合は非負整数。存在しなければ-1

◆ ToPos()

nn::nlib::succinct::Louds::ToPos ( NodeId  nodeid) const
noexcept

ノードIDから対応するビット列での位置を取得します。

引数
[in]nodeidノードID
戻り値
nodeid が存在する場合対応するビット列上の位置(非負整数)。存在しなければ-1

このクラス詳解は次のファイルから抽出されました: