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

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

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

公開メンバ関数

template<class TREEITER >
bool Init (TREEITER &root, uint32_t num_nodes) noexcept
 ツリーオブジェクトから括弧木を生成します。 [詳解]
 
int ToNodeId (uint32_t pos) const noexcept
 ビット列の位置からノードIDを取得します。 [詳解]
 
int ToPos (uint32_t nodeid) const noexcept
 ノードIDからビット列の位置を取得します。 [詳解]
 
size_t MemSize () const noexcept
 このクラスが明示的に確保するメモリ量を返します。 [詳解]
 
void Reset () noexcept
 オブジェクトをコンストラクタが呼ばれた直後の状態にします。
 
基本的なメンバ関数
 Bp () noexcept
 コンストラクタです。
 
 ~Bp () noexcept
 デストラクタです。
 
Bpassign (Bp &rhs, move_tag)
 swapを利用したムーブにより代入します。
 
 Bp (Bp &rhs, move_tag)
 swapを利用したムーブによりオブジェクトを構築します。
 
 Bp (Bp &&rhs)
 ムーブコンストラクタです。C++11の利用時に有効です。
 
Bpoperator= (Bp &&rhs)
 ムーブ代入演算子です。C++11の利用時に有効です。
 
void swap (Bp &rhs) noexcept
 オブジェクトの内容をスワップします。
 
括弧木の探索を行うためのメンバ関数
int FindOpen (uint32_t pos) const noexcept
 閉じ括弧に対応する開き括弧の位置を取得します。 [詳解]
 
int FindClose (uint32_t pos) const noexcept
 開き括弧に対応する閉じ括弧の位置を取得します。 [詳解]
 
int Enclose (uint32_t pos) const noexcept
 指定された括弧を直接包む括弧組の開き括弧の位置を取得します。 [詳解]
 
int FirstChild (uint32_t pos) const noexcept
 指定された括弧の中にある最初の開き括弧の位置を取得します。 [詳解]
 
int LastChild (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 Export (BinaryWriter *w) const noexcept
 オブジェクトを(ファイルに)書き出します。 [詳解]
 
bool Import (BinaryReader *r) noexcept
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

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

説明
括弧木と呼ばれるデータ構造を、以下の論文で説明されている手法で実装しています。
括弧木というのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、深さ優先探索で木を探索したときに、行きがけに'('、帰りがけに')'を出力することで作成することができます。 この表記法を使うことでビット列で木を表現することが可能になります。
このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。

Bp.h20 行目に定義があります。

関数詳解

nn::nlib::succinct::Bp::Enclose ( uint32_t  pos) const
noexcept

指定された括弧を直接包む括弧組の開き括弧の位置を取得します。

引数
[in]pos括弧の位置
戻り値
対応する開き括弧の位置。存在しなければ-1
説明
括弧の位置を指定すると、その括弧を包む一番範囲の狭い括弧(の開き括弧)の位置を返します。 木においては親ノードを取得する操作に対応します。
nn::nlib::succinct::Bp::Export ( BinaryWriter w) const
noexcept

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

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

開き括弧に対応する閉じ括弧の位置を取得します。

引数
[in]pos開き括弧の位置
戻り値
対応する閉じ括弧の位置。存在しなければ-1
開き括弧の位置を指定すると閉じ括弧の位置を返します。 指定した位置に閉じ括弧がある場合は引数と同じ値を返します。
nn::nlib::succinct::Bp::FindOpen ( uint32_t  pos) const
noexcept

閉じ括弧に対応する開き括弧の位置を取得します。

引数
[in]pos閉じ括弧の位置
戻り値
対応する開き括弧の位置。存在しなければ-1
説明
閉じ括弧の位置を指定すると開き括弧の位置を返します。 指定した位置に開き括弧がある場合は引数と同じ値を返します。
nn::nlib::succinct::Bp::FirstChild ( uint32_t  pos) const
noexcept

指定された括弧の中にある最初の開き括弧の位置を取得します。

引数
[in]pos括弧の位置
戻り値
子ノードに対応する開き括弧の位置。存在しなければ-1
説明
木において最初の子にアクセスする操作に対応します。
nn::nlib::succinct::Bp::Import ( BinaryReader r)
noexcept

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

引数
[in]r読み出し用オブジェクト
戻り値
インポートが成功した場合はtrue
template<class TREEITER >
nn::nlib::succinct::Bp::Init ( TREEITER &  root,
uint32_t  num_nodes 
)
noexcept

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

引数
[in]root根ノード
[in]num_nodesノード数
戻り値
成功した場合はtrue
説明
引数となるTREEITER 型は以下のメンバ関数を実装している必要があります。
  • const void* NodePtr(); // ノードのポインタを返す
  • const void* ParentNodePtr(); // 親ノードのポインタを返す
  • bool MoveNext(); // 深さ優先で次のノードに移動
ノードIDは深さ優先順で0からついていきます。

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

nn::nlib::succinct::Bp::LastChild ( uint32_t  pos) const
noexcept

指定された括弧の中にある最後の閉じ括弧の位置を取得します。

引数
[in]pos括弧の位置
戻り値
子ノードに対応する閉じ括弧の位置。存在しなければ-1
説明
木において最後の子にアクセスする操作に対応します。
nn::nlib::succinct::Bp::MemSize ( ) const
noexcept

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

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

指定された括弧に対応するノードの次の兄弟ノードに対応する括弧の位置を取得します。

引数
[in]pos括弧の位置
戻り値
次の兄弟ノードの開き括弧の位置
説明
木においては次の兄弟にアクセスする操作に対応します。
nn::nlib::succinct::Bp::Parent ( uint32_t  pos) const
inlinenoexcept

親ノードとなる括弧の位置を返します。

引数
[in]pos括弧の位置
戻り値
親ノードに対応する開き括弧の位置。存在しなければ-1
説明
内部でEnclose()を実行します。

Bp.h42 行目に定義があります。

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

指定された括弧に対応するノードの前の兄弟ノードに対応する括弧の位置を取得します。

引数
[in]pos括弧の位置
戻り値
前の兄弟ノードの閉じ括弧の位置
説明
木においては前の兄弟にアクセスする操作に対応します。
nn::nlib::succinct::Bp::ToNodeId ( uint32_t  pos) const
noexcept

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

引数
[in]pos括弧の位置を表すインデックス
戻り値
pos に対応するノードIDが存在する場合は非負整数。存在しなければ-1
nn::nlib::succinct::Bp::ToPos ( uint32_t  nodeid) const
noexcept

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

引数
[in]nodeidノードID
戻り値
nodeId が存在する場合対応する非負整数。存在しなければswap

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