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

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

#include "nn/nlib/succinct/Bp.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 Bp () noexcept
 デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
 
 ~Bp () noexcept
 デストラクタです。
 
Bpassign (Bp &rhs, move_tag)
 ムーブ代入演算子に相当します。
 
 Bp (Bp &rhs, move_tag)
 ムーブコンストラクタに相当します。
 
 Bp (Bp &&rhs)
 ムーブコンストラクタです。
 
Bpoperator= (Bp &&rhs)
 ムーブ代入演算子です。
 
template<class TREEITER >
bool Init (TREEITER &root, uint32_t num_nodes) noexcept
 ツリーオブジェクトから括弧木を生成します。 [詳解]
 
void Reset () noexcept
 このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
 
括弧木の探索を行うためのメンバ関数
int FindOpen (Pos pos) const noexcept
 閉じ括弧に対応する開き括弧の位置を取得します。 [詳解]
 
int FindClose (Pos pos) const noexcept
 開き括弧に対応する閉じ括弧の位置を取得します。 [詳解]
 
int Enclose (Pos pos) const noexcept
 指定された括弧を直接包む括弧組の開き括弧の位置を取得します。 [詳解]
 
int FirstChild (Pos pos) const noexcept
 指定された括弧の中にある最初の開き括弧の位置を取得します。 [詳解]
 
int LastChild (Pos pos) const noexcept
 指定された括弧の中にある最後の閉じ括弧の位置を取得します。 [詳解]
 
int NextSibling (Pos pos) const noexcept
 指定された括弧に対応するノードの次の兄弟ノードに対応する括弧の位置を取得します。 [詳解]
 
int PrevSibling (Pos pos) const noexcept
 指定された括弧に対応するノードの前の兄弟ノードに対応する括弧の位置を取得します。 [詳解]
 
int Parent (Pos pos) const noexcept
 親ノードとなる括弧の位置を返します。 [詳解]
 
括弧列の位置のみを扱うメンバ関数

ノード1つに対応する括弧列上の位置は複数あり扱いがやや煩雑ですが、ノードIDへの変換を行わないことでオーバーヘッドを削減できます。

std::pair< bool, PosGetPosOfFirstChild (Pos pos) const noexcept
 指定された括弧列上の位置の最初の子の括弧列上の位置を取得します。 [詳解]
 
std::pair< bool, PosGetPosOfLastChild (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, NodeIdGetNodeIdOfLastChild (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)\)で行うことができるコンパクトなツリー構造です。

説明
括弧木と呼ばれるデータ構造を、以下の論文で説明されている手法で実装しています。
括弧木というのは、順序木(ノードに順番(ID)がついた木)を表現する方法で、深さ優先探索で木を探索したときに、行きがけに'('、帰りがけに')'を出力することで作成することができます。 この表記法を使うことでビット列で木を表現することが可能になります。
このデータ構造に、木としての各種操作を \(O(1)\)でサポートするメンバ関数を実装したものがこのクラスです。
例として以下のようなツリーを作成して辿るコードを示します。 ツリーの辿り方が独特であることとに注意してください。
dot_inline_dotgraph_32.png
class MyTree {
public:
const void* NodePtr() {
return &data_[cur_];
}
const void* ParentNodePtr() {
int parent = data_[cur_];
return parent >= 0 ? &data_[parent] : nullptr;
}
bool MoveNext() {
if (cur_ + 1 >= data_.size()) return false;
++cur_;
return true;
}
private:
std::vector<int> data_{ -1, 0, 1, 0, 0, 4, 4, 6, 4, 8, 8 };
size_t cur_ = 0;
} mytree;
Bp bp;
SUCCEED_IF(bp.Init(mytree, 11));
std::function<void(Bp::NodeId)> traverse = [&](Bp::NodeId nodeid) {
auto parent = bp.GetNodeIdOfParent(nodeid);
if (parent.first) {
nlib_printf("%u -> %u\n", parent.second, nodeid);
}
auto cld = bp.GetNodeIdOfFirstChild(nodeid);
if (cld.first) {
do {
traverse(cld.second);
cld = bp.GetNodeIdOfNextSibling(cld.second);
} while (cld.first);
}
};
traverse(0);
/*
Output:
0 -> 1
1 -> 2
0 -> 3
0 -> 4
4 -> 5
4 -> 6
6 -> 7
4 -> 8
8 -> 9
8 -> 10
*/

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

関数詳解

◆ Enclose()

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

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

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

◆ Export()

nn::nlib::succinct::Bp::Export ( BinaryWriter w) const
noexcept

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

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

◆ FindClose()

nn::nlib::succinct::Bp::FindClose ( Pos  pos) const
noexcept

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

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

◆ FindOpen()

nn::nlib::succinct::Bp::FindOpen ( Pos  pos) const
noexcept

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

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

◆ FirstChild()

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

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

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

◆ GetNodeIdByPos()

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

括弧の位置から対応するノードIDを取得します。

引数
[in]pos括弧の位置を表すインデックス
戻り値
ブール値とノードIDのペア。ブール値はノードIDが存在する場合にtrue

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

◆ GetNodeIdOfFirstChild()

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

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

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

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

◆ GetNodeIdOfLastChild()

nn::nlib::succinct::Bp::GetNodeIdOfLastChild ( NodeId  nodeid) const
inlinenoexcept

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

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

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

◆ GetNodeIdOfNextSibling()

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

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

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

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

◆ GetNodeIdOfParent()

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

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

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

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

◆ GetNodeIdOfPrevSibling()

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

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

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

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

◆ GetPosByNodeId()

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

ノードIDから対応する括弧の位置を取得します。

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

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

◆ GetPosOfFirstChild()

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

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

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

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

◆ GetPosOfLastChild()

nn::nlib::succinct::Bp::GetPosOfLastChild ( Pos  pos) const
inlinenoexcept

指定された括弧列上の位置の最後の子の括弧列上の位置を取得します。

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

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

◆ GetPosOfNextSibling()

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

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

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

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

◆ GetPosOfParent()

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

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

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

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

◆ GetPosOfPrevSibling()

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

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

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

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

◆ Import()

nn::nlib::succinct::Bp::Import ( BinaryReader r)
noexcept

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

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

◆ Init()

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

◆ LastChild()

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

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

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

◆ MemSize()

nn::nlib::succinct::Bp::MemSize ( ) const
noexcept

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

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

◆ NextSibling()

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

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

引数
[in]pos括弧の位置
戻り値
次の兄弟ノードの開き括弧の位置
説明
木においては次の兄弟にアクセスする操作に対応します。

◆ Parent()

nn::nlib::succinct::Bp::Parent ( Pos  pos) const
inlinenoexcept

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

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

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

◆ PrevSibling()

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

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

引数
[in]pos括弧の位置
戻り値
前の兄弟ノードの閉じ括弧の位置
説明
木においては前の兄弟にアクセスする操作に対応します。

◆ ToNodeId()

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

括弧の位置から対応するノードIDを取得します。

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

◆ ToPos()

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

ノードIDから対応する括弧の位置を取得します。

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

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