各種操作を \(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 |
| デストラクタです。
|
|
Bp & | assign (Bp &rhs, move_tag) |
| swap を利用したムーブにより代入します。
|
|
| Bp (Bp &rhs, move_tag) |
| swap を利用したムーブによりオブジェクトを構築します。
|
|
| Bp (Bp &&rhs) |
| ムーブコンストラクタです。C++11の利用時に有効です。
|
|
Bp & | operator= (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.h の 20 行目に定義があります。
nn::nlib::succinct::Bp::Enclose |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
指定された括弧を直接包む括弧組の開き括弧の位置を取得します。
- 引数
-
- 戻り値
- 対応する開き括弧の位置。存在しなければ
-1
。
- 説明
- 括弧の位置を指定すると、その括弧を包む一番範囲の狭い括弧(の開き括弧)の位置を返します。 木においては親ノードを取得する操作に対応します。
オブジェクトを(ファイルに)書き出します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 書きだしたデータは
Import()
関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。
nn::nlib::succinct::Bp::FindClose |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
開き括弧に対応する閉じ括弧の位置を取得します。
- 引数
-
- 戻り値
- 対応する閉じ括弧の位置。存在しなければ
-1
。
- 開き括弧の位置を指定すると閉じ括弧の位置を返します。 指定した位置に閉じ括弧がある場合は引数と同じ値を返します。
nn::nlib::succinct::Bp::FindOpen |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
閉じ括弧に対応する開き括弧の位置を取得します。
- 引数
-
- 戻り値
- 対応する開き括弧の位置。存在しなければ
-1
。
- 説明
- 閉じ括弧の位置を指定すると開き括弧の位置を返します。 指定した位置に開き括弧がある場合は引数と同じ値を返します。
nn::nlib::succinct::Bp::FirstChild |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
指定された括弧の中にある最初の開き括弧の位置を取得します。
- 引数
-
- 戻り値
- 子ノードに対応する開き括弧の位置。存在しなければ
-1
。
- 説明
- 木において最初の子にアクセスする操作に対応します。
書き出されたオブジェクトを読み出します。
- 引数
-
- 戻り値
- インポートが成功した場合は
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.h の 59 行目に定義があります。
nn::nlib::succinct::Bp::LastChild |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
指定された括弧の中にある最後の閉じ括弧の位置を取得します。
- 引数
-
- 戻り値
- 子ノードに対応する閉じ括弧の位置。存在しなければ
-1
。
- 説明
- 木において最後の子にアクセスする操作に対応します。
nn::nlib::succinct::Bp::MemSize |
( |
| ) |
const |
|
noexcept |
このクラスが明示的に確保するメモリ量を返します。
- 説明
- 実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。
- 戻り値
- バイト数
nn::nlib::succinct::Bp::NextSibling |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
指定された括弧に対応するノードの次の兄弟ノードに対応する括弧の位置を取得します。
- 引数
-
- 戻り値
- 次の兄弟ノードの開き括弧の位置
- 説明
- 木においては次の兄弟にアクセスする操作に対応します。
nn::nlib::succinct::Bp::Parent |
( |
uint32_t |
pos | ) |
const |
|
inlinenoexcept |
親ノードとなる括弧の位置を返します。
- 引数
-
- 戻り値
- 親ノードに対応する開き括弧の位置。存在しなければ
-1
。
- 説明
- 内部で
Enclose()
を実行します。
Bp.h の 42 行目に定義があります。
nn::nlib::succinct::Bp::PrevSibling |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
指定された括弧に対応するノードの前の兄弟ノードに対応する括弧の位置を取得します。
- 引数
-
- 戻り値
- 前の兄弟ノードの閉じ括弧の位置
- 説明
- 木においては前の兄弟にアクセスする操作に対応します。
nn::nlib::succinct::Bp::ToNodeId |
( |
uint32_t |
pos | ) |
const |
|
noexcept |
ビット列の位置からノードIDを取得します。
- 引数
-
- 戻り値
pos
に対応するノードIDが存在する場合は非負整数。存在しなければ-1
。
nn::nlib::succinct::Bp::ToPos |
( |
uint32_t |
nodeid | ) |
const |
|
noexcept |
ノードIDからビット列の位置を取得します。
- 引数
-
- 戻り値
nodeId
が存在する場合対応する非負整数。存在しなければswap
を
このクラス詳解は次のファイルから抽出されました: