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

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

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

公開メンバ関数

template<class TREEITER >
bool Init (TREEITER &iter, uint32_t num_nodes) noexcept
 ツリーオブジェクトからLOUDSを生成します。 [詳解]
 
int ToNodeId (uint32_t pos) const noexcept
 ビット列の位置からノードIDを取得します。 [詳解]
 
int ToPos (uint32_t nodeid) const noexcept
 ノードIDからビット列での位置を取得します。 [詳解]
 
size_t MemSize () const noexcept
 このクラスが明示的に確保するメモリ量を返します。 [詳解]
 
void Reset () noexcept
 オブジェクトをコンストラクタが呼ばれた直後の状態にします。
 
基本的なメンバ関数
constexpr Louds () noexcept
 コンストラクタです。
 
 ~Louds () noexcept
 デストラクタです。
 
 Louds (Louds &&rhs) noexcept
 ムーブコンストラクタです。C++11の利用時に有効です。
 
Loudsoperator= (Louds &&rhs) noexcept
 ムーブ代入演算子です。C++11の利用時に有効です。
 
 Louds (Louds &rhs, move_tag) noexcept
 ムーブコンストラクタに相当します。
 
Loudsassign (Louds &rhs, move_tag) noexcept
 ムーブ代入演算子に相当します。
 
void swap (Louds &rhs) noexcept
 オブジェクトの内容をスワップします。 [詳解]
 
LOUDSの探索を行うためのメンバ関数
int FirstChild (uint32_t pos) const noexcept
 指定されたノードの最初の子の位置を取得します。 [詳解]
 
int NextSibling (uint32_t pos) const noexcept
 次の兄弟ノードの位置を取得します。 [詳解]
 
int PrevSibling (uint32_t pos) const noexcept
 前の兄弟ノードの位置を取得します。 [詳解]
 
int Parent (uint32_t pos) const noexcept
 親ノードの位置を取得します。 [詳解]
 
bool IsLeaf (uint32_t pos) const noexcept
 ノードが葉ノードかどうかを判定します。 [詳解]
 
インポートとエクスポート
bool Export (BinaryWriter *w) const noexcept
 オブジェクトを(ファイルに)書き出します。 [詳解]
 
bool Import (BinaryReader *r) noexcept
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

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

説明
LOUDSと呼ばれるデータ構造を、以下に説明されている手法で実装しています(ビットは逆になってます)。
LOUDSというのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、幅優先探索で木を探索してノードを見た際に、以下のようにすることで作成することができます。
  1. 0ビットを子の数だけ出力
  2. その後に1ビットを1つ出力
この表記法を使うことでビット列で木を表現することが可能になります。 このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。

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

関数詳解

◆ Export()

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

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

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

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

◆ FirstChild()

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

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

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

◆ Import()

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

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

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

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

◆ 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.h76 行目に定義があります。

◆ IsLeaf()

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

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

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

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

◆ MemSize()

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

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

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

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

◆ NextSibling()

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

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

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

◆ Parent()

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

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

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

◆ PrevSibling()

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

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

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

◆ swap()

void nn::nlib::succinct::Louds::swap ( Louds rhs)
inlinenoexcept

オブジェクトの内容をスワップします。

非推奨:
この関数は将来のリリースにおいて削除されます。

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

◆ ToNodeId()

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

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

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

◆ ToPos()

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

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

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

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