各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。
[詳解]
#include "nn/nlib/succinct/Louds.h"
各種操作を \(O(1)\)で行うことができるコンパクトなツリー構造です。
- 説明
- LOUDSと呼ばれるデータ構造を、以下に説明されている手法で実装しています(ビットは逆になってます)。
- LOUDSというのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、幅優先探索で木を探索してノードを見た際に、以下のようにすることで作成することができます。
-
0ビットを子の数だけ出力
-
その後に1ビットを1つ出力
- この表記法を使うことでビット列で木を表現することが可能になります。 このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。
Louds.h の 17 行目に定義があります。
オブジェクトを(ファイルに)書き出します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 書きだしたデータは
Import()
関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。
Louds.h の 38 行目に定義があります。
nn::nlib::succinct::Louds::FirstChild |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
指定されたノードの最初の子の位置を取得します。
- 引数
-
- 戻り値
- 子ノードに対応するビット列上の位置。存在しなければ
-1
。
書き出されたオブジェクトを読み出します。
- 引数
-
- 戻り値
- インポートが成功した場合は
true
Louds.h の 39 行目に定義があります。
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.h の 47 行目に定義があります。
nn::nlib::succinct::Louds::IsLeaf |
( |
uint32_t |
pos | ) |
const |
|
inlinenoexcept |
ノードが葉ノードかどうかを判定します。
- 引数
-
- 戻り値
- 葉ノードでなければfalse。それ以外なら
true
Louds.h の 33 行目に定義があります。
nn::nlib::succinct::Louds::MemSize |
( |
| ) |
const |
|
inlinenoexcept |
このクラスが明示的に確保するメモリ量を返します。
- 戻り値
- バイト数
- 説明
- 実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。
Louds.h の 36 行目に定義があります。
nn::nlib::succinct::Louds::NextSibling |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
次の兄弟ノードの位置を取得します。
- 引数
-
- 戻り値
- 次の兄弟ノードの位置。存在しなければ
-1
。
nn::nlib::succinct::Louds::Parent |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
親ノードの位置を取得します。
- 引数
-
- 戻り値
- 親ノードの位置。存在しなければ-1
nn::nlib::succinct::Louds::PrevSibling |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
前の兄弟ノードの位置を取得します。
- 引数
-
- 戻り値
- 前の兄弟ノードの位置。存在しなければ
-1
。
nn::nlib::succinct::Louds::ToNodeId |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
ビット列の位置からノードIDを取得します。
- 引数
-
[in] | pos | ビット列内のビットを指すインデックス |
- 戻り値
pos
に対応するノードIDが存在する場合は非負整数。存在しなければ-1
。
nn::nlib::succinct::Louds::ToPos |
( |
uint32_t |
nodeid | ) |
const |
|
noexcept |
ノードIDからビット列での位置を取得します。
- 引数
-
- 戻り値
nodeId
が存在する場合対応するビット列上の位置(非負整数)。存在しなければ-1
。
このクラス詳解は次のファイルから抽出されました: