木構造用データベースクラス [詳解]

#include <FK/Tree.h>

公開メンバ関数
	fk_Tree (const std::string name="default")
	コンストラクタ
virtual	~fk_Tree ()
	デストラクタ
fk_TreeData *	getRoot (void)
	根ノード参照関数
void	clear (const std::string name)
	初期化関数
fk_TreeData *	addNewChild (fk_TreeData *parent, const std::string name)
	新規ノード生成関数
bool	deleteBranch (fk_TreeData *node)
	ノードおよびその下の枝の消去関数
bool	clearChildren (fk_TreeData *node)
	子ノードおよびその下の枝の消去関数
fk_TreeData *	cloneOneData (fk_TreeData parent, fk_TreeData node)
	単一ノード複製関数
fk_TreeData *	cloneBranch (fk_TreeData parent, fk_TreeData node)
	枝複製関数
bool	moveBranch (fk_TreeData parent, fk_TreeData node)
	枝移動関数
void	toFront (int n, fk_TreeData *node)
	順位前進関数
void	toBack (int n, fk_TreeData *node)
	順位後退関数
bool	isArive (fk_TreeData *node)
	ノード生存確認関数
fk_TreeData *	findData (const std::string name)
	ノード検索関数
fk_TreeData *	foreachData (fk_TreeData *node)
	逐次ノード参照関数

限定公開メンバ関数
virtual fk_TreeData *	makeNewData (fk_Tree tree, const std::string name, fk_TreeData parent)
	ノード生成時関数

詳解

木構造用データベースクラス

このクラスは、木構造を用いたデータベース機能を提供します。

本クラスは、FK の機能を利用するためのものではなく、ユーザが木構造を利用する際に便利なユーティリティクラスです。本クラスおよび fk_TreeData, fk_TreeBaseObject の各クラスを用いて利用します。これらのクラス中の解説で使用される用語を、以下のように定義します。

根ノード: 木構造の頂点(最上部)にあるノード。
子ノード: あるノードに対し、その下方にあるノードのこと。任意のノードは、複数の子ノードを持つことができます。
親ノード: あるノードに対し、その上方にあるノードのこと。根ノードは親ノードを持ちませんが、その他のノードは必ず親ノードを1つだけ持ちます。
兄弟ノード: あるノードの子ノード全体のこと。
(あるノードの)前のノード: 同じ親ノードを持つノードのうち、順番が1つ前に当たるノードのこと。
(あるノードの)後のノード: 同じ親ノードを持つノードのうち、順番が1つ後に当たるノードのこと。
枝: あるノードと、その下方に位置しているノード全てを総称した集合。
ノード間距離: あるノードを出発点とし、別のノードに親子間を伝って移動する際のステップ数。
ノードの深さ: あるノードの、根ノードからの距離のこと。
ノードの順位: 兄弟ノードの中での、前から何番目に位置するかという順番のこと。

これを図で説明します。

ツリー構造

図中で、ノード A が「根ルート」となります。
A からみれば、B, C, D は全て「子ノード」ということになります。
逆に、A は B の「親ノード」となります。
B, C, D の集合は「兄弟ノード」となります。同様に、F, G も「兄弟ノード」となります。
B, C, D がこの順番に登録されていた場合、 C にとって B は「前のノード」となり、 B にとって C は「後のノード」となります。その場合の B, C, D の順位は 1, 2, 3 となります。
B の「前のノード」は存在しません。同様に、D の「後のノード」も存在しません。
D ノードの「枝」とは、D とその下部にあるノード全てとなりますので、 D, F, G, H, I の集合ということになります。
E ノードと I ノードの「距離」は、親子関係を伝っていくと E → B → A → D → F → I となるため、距離は 5 となります。
E ノードの深さは 2、H ノードの深さは 3 となります。 A ノードについては、根ノードとなるので深さは 0 となります。

各クラスの役割ですが、 fk_Tree クラスは木構造全体のデータベースとなります。 fk_TreeData は各ノードのデータを意味します。 fk_TreeBaseObject は、 fk_TreeData に対してユーザ定義のデータを付加するための基底クラスとなります。基本的には、ノードの生成、移動、消去といった操作は fk_Tree で、ノード自体の設定は fk_TreeData のメンバ関数で行うことになります。

各ノードには任意の名称をつけることができます。異なるノードに同一の名称をつけることは可能です。しかしその場合、 findData() でノードの検索を行う際には不都合が生じる場合があります。検索機能を有効利用したい場合は、名称を一意にしておくとよいでしょう。

参照: fk_TreeData, fk_TreeBaseObject

構築子と解体子

◆ fk_Tree()

FK::fk_Tree::fk_Tree ( const std::string name = "default" )

コンストラクタ

インスタンスの生成時に、同時に根ノードとして fk_TreeData 型のノードが一つ自動的に生成されます。引数によって、その根ノードに対する名称を設定します。

引数

[in] name 根ノードの名称

◆ ~fk_Tree()

virtual FK::fk_Tree::~fk_Tree ( )

virtual

デストラクタ

関数詳解

◆ makeNewData()

virtual fk_TreeData * FK::fk_Tree::makeNewData	(	fk_Tree *	tree,
		const std::string	name,
		fk_TreeData *	parent )

protectedvirtual

ノード生成時関数

この関数は、 addNewChild() などで新たにノードが生成された際に、各ノード (fk_TreeData インスタンス) ごとに呼び出される関数です。 fk_Tree クラスの派生クラスにおいて、本関数を再定義することにより、ノード生成時に自動的に行っておきたい処理を記述することができます。デフォルトでは、以下のようなコードになっています。

fk_TreeData * fk_Tree::makeNewData(fk_Tree *tree,
                                   const std::string name,
                                   fk_TreeData *parent)
{
    return(new fk_TreeData(tree, name, parent));
}

本関数のコードでは、必ず fk_TreeData 型のインスタンスを生成し、それを返す必要があります。

引数

[in]	tree	新ノードが属する fk_Tree インスタンス
[in]	name	新ノードに指定されている名称
[in]	parent	新ノードの親となるノードのインスタンス

戻り値: 新たなノードとなる fk_TreeData 型インスタンスを生成し、それを返すようにして下さい。

◆ getRoot()

fk_TreeData * FK::fk_Tree::getRoot ( void )

根ノード参照関数

根ノードであるノードのインスタンスを返します。

戻り値: 根ノードインスタンス

◆ clear()

void FK::fk_Tree::clear ( const std::string name )

初期化関数

現状の、根ノードを含む全てのノードを消去し、新たな根ノードを作成します。

引数

[in] name 新しい根ノードの名称

参照: deleteBranch()

◆ addNewChild()

fk_TreeData * FK::fk_Tree::addNewChild	(	fk_TreeData *	parent,
		const std::string	name )

新規ノード生成関数

新たなノードを作成します。既に兄弟ノードが存在していた場合、その中での順位は一番後となります。

引数

[in]	parent	新ノードの親となるノードのインスタンス
[in]	name	新ノードの名称

戻り値: 新ノードのインスタンス

◆ deleteBranch()

bool FK::fk_Tree::deleteBranch ( fk_TreeData * node )

ノードおよびその下の枝の消去関数

指定したノードと、そのノードを元とする枝全体を消去します。例えば、下図の左側において「D」のノードを指定した場合、 D および F, G, H, I のノードも消去します。

枝の消去

根ノードについては、本関数によって消去はできません。 clearChildren() との違いは、本関数は指定ノードも消去しますが、 clearChildren() は指定ノードの消去は行わないことです。

引数

[in] node 消去するノードのインスタンス

戻り値: 消去に成功すれば true を、失敗すれば false を返します。

参照: clear(), clearChildren()

◆ clearChildren()

bool FK::fk_Tree::clearChildren ( fk_TreeData * node )

子ノードおよびその下の枝の消去関数

指定したノードの子ノード全てと、その子ノードを元とする枝全体を消去します。例えば、下図の左側において「D」のノードを指定した場合、 F, G, H, I の各ノードを消去します。

子ノードの消去

deleteBranch() との違いは、本関数は指定ノードの消去は行いませんが、 deleteBranch() では指定ノードも消去することです。

引数

[in] node 指定ノードインスタンス

戻り値: 消去に成功すれば true を、失敗すれば false を返します。

参照: clear(), deleteBranch()

◆ cloneOneData()

fk_TreeData * FK::fk_Tree::cloneOneData	(	fk_TreeData *	parent,
		fk_TreeData *	node )

単一ノード複製関数

ノードの複製を行い、任意のノードの子ノードとして登録します。複製する要素は以下のとおりです。

名称
fk_TreeeData::setObject() によって登録されたユーザインスタンス

この関数においては、複製元のノードで子ノードが存在していた場合、子ノードの複製は行いません。例えば、下図の左側で「F」のノードを「B」のノードの下に複製した場合、新たな「F」ノードの下には何もノードがない状態となります。

単一ノードの複製

複製した先に兄弟ノードが存在していた場合、新たなノードの順位は一番後となります。

引数

[in]	parent	複製先の親ノードインスタンス
[in]	node	複製元のノードインスタンス

戻り値: 成功した場合、新たに生成されたノードインスタンスを返します。失敗した場合は nullptr を返します。

参照: cloneBranch(), moveBranch()

◆ cloneBranch()

fk_TreeData * FK::fk_Tree::cloneBranch	(	fk_TreeData *	parent,
		fk_TreeData *	node )

枝複製関数

枝の複製を行い、任意のノードの下に登録します。複製する要素は以下のとおりです。

名称
fk_TreeeData::setObject() によって登録されたユーザインスタンス
各兄弟ノードの前後関係

例えば、下図の左側で「F」のノードを「B」のノードの下に複製した場合、新たな「F」ノードの子ノードとして「H」、「I」のノードも一緒に複製されます。

枝の複製

複製した先に兄弟ノードが存在していた場合、新たなノードの順位は一番後となります。

引数

[in]	parent	複製先の親ノードインスタンス
[in]	node	複製元のノードインスタンス

戻り値: 成功した場合、新たに生成されたノードインスタンスを返します。失敗した場合は nullptr を返します。

参照: cloneOneData(), moveBranch()

◆ moveBranch()

bool FK::fk_Tree::moveBranch	(	fk_TreeData *	parent,
		fk_TreeData *	node )

枝移動関数

枝の移動を行います。移動する要素は以下の通りです。

名称
fk_TreeeData::setObject() によって登録されたユーザインスタンス
各兄弟ノードの前後関係

例えば、下図の左側で「F」のノードを「B」のノードの下に移動した場合、「D」の下にあった「F」はなくなります。

枝の移動

枝が移動できる条件として、移動先となる親ノードに元の枝の中にあるノードを指定することはできません。上図で例えると、「F」の移動先として「H」や「I」は指定できないことになります。移動した先に兄弟ノードが存在していた場合、新たなノードの順位は一番後となります。

引数

[in]	parent	移動先の親ノードインスタンス
[in]	node	移動元のノードインスタンス

戻り値: 成功した場合 true を、失敗した場合 false を返します。

参照: cloneOneData(), cloneBranch()

◆ toFront()

void FK::fk_Tree::toFront	(	int	n,
		fk_TreeData *	node )

順位前進関数

任意のノードに対し、兄弟ノードの中での順位を前に移動します。

引数

[in]	n	前に移動する順位数。ただし、n が以下の条件を満たした場合、一番前に移動します。順位よりも大きな数値を指定した場合。 n が負の場合。(例えば -1 など)
[in]	node	操作対象ノードのインスタンス

参照: toBack()

◆ toBack()

void FK::fk_Tree::toBack	(	int	n,
		fk_TreeData *	node )

順位後退関数

任意のノードに対し、兄弟ノードの中での順位を後に移動します。

引数

[in]	n	後に移動する順位数。ただし、n が以下の条件を満たした場合、一番後に移動します。 (兄弟ノードの個数) - (順位) よりも大きな数値を指定した場合。 n が負の場合。(例えば -1 など)
[in]	node	操作対象ノードのインスタンス

参照: toFront()

◆ isArive()

bool FK::fk_Tree::isArive ( fk_TreeData * node )

ノード生存確認関数

指定したノードが、本インスタンスのデータ中に存在するかどうかを確認します。

引数

[in] node 確認対象ノードインスタンス

戻り値: データ内に存在していれば true を、していなければ false を返します。

◆ findData()

fk_TreeData * FK::fk_Tree::findData ( const std::string name )

ノード検索関数

名称をキーとしてノードを検索します。もし同一名のノードがデータ内に存在している場合は、最も早い段階で生成されていたインスタンスを返します。

引数

[in] name 検索対象ノード名

戻り値: 見つかれば、そのインスタンスを返します。データ内に存在していなかった場合は nullptr を返します。

◆ foreachData()

fk_TreeData * FK::fk_Tree::foreachData ( fk_TreeData * node )

逐次ノード参照関数

データ内の各ノードを、逐次的に参照していきます。引数に代入したノードインスタンスにより、以下のような動作を行います。

引数に nullptr を代入した場合、根ノードを返します。
任意のノードを引数に代入したときは、そのノードの次に生成されたノードを返します。
最後に生成したノードを代入したときは、nullptr を返します。

以下のコードは、データ内の全てのノードを参照するものです。

fk_Tree         tree;
fk_TreeData     *node;

for(node = tree.foreachData(nullptr);
    node != nullptr;
    node = tree.foreachData(node)) {
    // node 変数にノードが入っています。
}

引数

[in] node 逐次探索対象ノードインスタンス

戻り値: 引数の次に生成されたノードインスタンスを返します。引数のノードが最後に生成されたインスタンスであった場合は nullptr を返します。

公開メンバ関数

限定公開メンバ関数

詳解

構築子と解体子

◆ fk_Tree()

◆ ~fk_Tree()

関数詳解

◆ makeNewData()

◆ getRoot()

◆ clear()

◆ addNewChild()

◆ deleteBranch()

◆ clearChildren()

◆ cloneOneData()

◆ cloneBranch()

◆ moveBranch()

◆ toFront()

◆ toBack()

◆ isArive()

◆ findData()

◆ foreachData()