/*
 *	gnode.c
 *
 *	N-ary Trees - trees of data with any number of branches
 *
 *	* Sat Feb 06 21:09:21 JST 2016 Naoyuki Sawa
 *	- 1st リリース。
 *	- GLibのN-ary Trees(http://developer.gnome.org/glib/stable/glib-N-ary-Trees.html)をほとんどそのまま使わせて頂きました。
 *	  勉強のために、ソースを読みながらコメントを付けたりしましたが、処理はほとんど変えていません。
 *	  ただし少しだけ、不要と思う処理を削除したり省略したので、もし不正な動作が出た場合はそれらの変更点を疑って下さい。
 *	* Sat Aug 27 21:24:43 JST 2016 Naoyuki Sawa
 *	- g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
 *	  詳細は、gnode.hの、GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSINGシンボル定義箇所のコメントを参照して下さい。
 *	- ActObj_ApplyTransToTree()が、上記の変更に依存するようになりました。
 *	  詳細は、clipact.hの同日のコメントを参照して下さい。
 */
#include "clip.h"
/****************************************************************************
 *	
 ****************************************************************************/
//Creates a new GNode containing the given data.
//Used to create the first node in a tree.
//Parameters
//		data		The data of the new node.
//Returns
//		A new GNode.
GNode* g_node_new(void* data) {
	//新しいノードのメモリを確保する。
	GNode* node = calloc(1, sizeof(GNode));
	if(!node) { DIE(); }
	//新しいノードにデータを格納する。
	node->data = data;
	//新しいノードを返す。
	return node;
}
/*--------------------------------------------------------------------------*/
//Recursively copies a GNode.
//But does not deep-copy the data inside the nodes, see g_node_copy_deep() if you need that.
//Parameters
//		node		A GNode.
//Returns
//		A new GNode containing the same data pointers.
GNode* g_node_copy(GNode* node) {
	return g_node_copy_deep(node, NULL/*copy_func*/, NULL/*data*/);
}
/*--------------------------------------------------------------------------*/
//Recursively copies a GNode and its data.
//Parameters
//		node		A GNode.
//		copy_func	The function which is called to copy the data inside each node, or NULL to use the original data.
//		data		Data to pass to copy_func.
//Returns
//		A new GNode containing copies of the data in node.
GNode* g_node_copy_deep(GNode* node, void* (*copy_func)(const void* src, void* data), void* data) {
	void* new_data;
	GNode *new_node, *child, *new_child;
	//指定されたノードのデータを取得する。
	new_data = node->data;
	//コピー関数が指定されていたら、データを複製する。
	if(copy_func) { new_data = (*copy_func)(new_data, data); }
	//新しいノードを作成する。
	new_node = g_node_new(new_data);
	//指定されたノードの全ての子ノードについて…
	for(child = g_node_first_child(node);
	    child;
	    child = g_node_next_sibling(child)) {
		//子ノードとデータを複製して、新しい子ノードを作成する。
		new_child = g_node_copy_deep(child, copy_func, data);
		//新しいノードに、新しい子ノードを追加する。
		g_node_append(new_node, new_child);
	}
	//新しいノードを返す。
	return new_node;
}
/*--------------------------------------------------------------------------*/
//Inserts a GNode beneath the parent at the given position.
//Parameters
//		parent		The GNode to place node under.
//		position	The position to place node at, with respect to its siblings.
//				If position is -1, the node is inserted as the last child of parent.
//		node		The GNode to insert.
//Returns
//		The inserted GNode.
GNode* g_node_insert(GNode* parent, int position, GNode* node) {
	//指定された親ノードの、position番目の子ノードの前に、指定されたノードを追加する。
	return g_node_insert_before(parent, g_node_nth_child(parent, position), node);
	//                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~もし ((unsigned)position>=(unsigned)g_node_n_children(node)) だった場合は、戻り値がNULLとなる。
	//                                                                    g_node_insert_before(parent,NULL,node) となって、nodeはparentの最後の子ノードとして追加される。
}
/*--------------------------------------------------------------------------*/
//Inserts a GNode beneath the parent before the given sibling.
//Parameters
//		parent		The GNode to place node under.
//		sibling		The sibling GNode to place node before.
//				If sibling is NULL, the node is inserted as the last child of parent.
//		node		The GNode to insert.
//Returns
//		The inserted GNode.
GNode* g_node_insert_before(GNode* parent, GNode* sibling, GNode* node) {
	//指定されたノードに、指定された親ノードを格納する。
	node->parent = parent;
	//追加する位置のノードが指定されていたら…
	if(sibling) {
		//追加する位置のノードが、最初の子ノードでなければ…
		if(sibling->prev) {			//○<------------sibling
			node->prev = sibling->prev;	//○<-----node
			node->prev->next = node;	//○<---->node
		//追加する位置のノードが、最初の子ノードならば…
		} else {				//parent========>sibling
			parent->children = node;	//parent=>node
		}
		node->next = sibling;			//○<---->node-->sibling
		sibling->prev = node;			//○<---->node<->sibling
	//追加する位置が指定されていなければ…
	} else {
		//指定された親ノードの、子ノードが有れば…
		if(parent->children) {
			//指定された親ノードの、最後の子ノードを取得する。
			sibling = g_node_last_child(parent);
			//最後の子ノードの次に、指定されたノードを追加する。
			node->prev = sibling;		//sibling<--node
			sibling->next = node;		//sibling<->node
		//指定された親ノードの、子ノードが無ければ…
		} else {
			//指定された親ノードの、最初の子ノードとして、指定されたノードを追加する。
			parent->children = node;	//parent===>node
		}
	}
	//指定されたノードを、そのまま返す。
	return node;
}
/*--------------------------------------------------------------------------*/
//Inserts a GNode beneath the parent after the given sibling.
//Parameters
//		parent		The GNode to place node under.
//		sibling		The sibling GNode to place node after.
//				If sibling is NULL, the node is inserted as the first child of parent.
//		node		The GNode to insert.
//Returns
//		The inserted GNode.
GNode* g_node_insert_after(GNode* parent, GNode* sibling, GNode* node) {
	//指定されたノードに、指定された親ノードを格納する。
	node->parent = parent;
	//追加する位置のノードが指定されていたら…
	if(sibling) {
		//追加する位置のノードが、最後の子ノードでなければ…
		if(sibling->next) {			//sibling--------->○
			sibling->next->prev = node;	//          node<--○
		}
		node->next = sibling->next;		//          node<->○
		node->prev = sibling;			//sibling<--node<->○
		sibling->next = node;			//sibling<->node<->○
	//追加する位置が指定されていなければ…
	} else {
		//指定された親ノードの、子ノードが有れば…
		if(parent->children) {			//parent==========>○
			node->next = parent->children;	//          node-->○
			parent->children->prev = node;	//          node<->○
		}
		parent->children = node;		//parent===>node<->○
	}
	//指定されたノードを、そのまま返す。
	return node;
}
/*--------------------------------------------------------------------------*/
//Inserts a GNode as the last child of the given parent.
//Parameters
//		parent		The GNode to place the new GNode under.
//		node		The GNode to insert.
//Returns
//		The inserted GNode.
GNode* g_node_append(GNode* parent, GNode* node) {
	return g_node_insert_before(parent, NULL/*sibling*/, node);
}
/*--------------------------------------------------------------------------*/
//Inserts a GNode as the first child of the given parent.
//Parameters
//		parent		The GNode to place the new GNode under.
//		node		The GNode to insert.
//Returns
//		The inserted GNode.
GNode* g_node_prepend(GNode* parent, GNode* node) {
	return g_node_insert_before(parent, parent->children, node);
}
/*--------------------------------------------------------------------------*/
//Inserts a new GNode at the given position.
//Parameters
//		parent		The GNode to place the new GNode under.
//		position	The position to place the new GNode at.
//				If position is -1, the new GNode is inserted as the last child of parent.
//		data		The data for the new GNode.
//Returns
//		The new GNode.
GNode* g_node_insert_data(GNode* parent, int position, void* data) {
	return g_node_insert(parent, position, g_node_new(data));
}
/*--------------------------------------------------------------------------*/
//Inserts a new GNode after the given sibling.
//Parameters
//		parent		The GNode to place the new GNode under.
//		sibling		The sibling GNode to place the new GNode after.
//		data		The data for the new GNode.
//Returns
//		The new GNode.
GNode* g_node_insert_data_after(GNode* parent, GNode* sibling, void* data) {
	return g_node_insert_after(parent, sibling, g_node_new(data));
}
/*--------------------------------------------------------------------------*/
//Inserts a new GNode before the given sibling.
//Parameters
//		parent		The GNode to place the new GNode under.
//		sibling		The sibling GNode to place the new GNode before.
//		data		The data for the new GNode.
//Returns
//		The new GNode.
GNode* g_node_insert_data_before(GNode* parent, GNode* sibling, void* data) {
	return g_node_insert_before(parent, sibling, g_node_new(data));
}
/*--------------------------------------------------------------------------*/
//Inserts a new GNode as the last child of the given parent.
//Parameters
//		parent		The GNode to place the new GNode under.
//		data		The data for the new GNode.
//Returns
//		The new GNode.
GNode* g_node_append_data(GNode* parent, void* data) {
	return g_node_insert_before(parent, NULL/*sibling*/, g_node_new(data));
}
/*--------------------------------------------------------------------------*/
//Inserts a new GNode as the first child of the given parent.
//Parameters
//		parent		The GNode to place the new GNode under.
//		data		The data for the new GNode.
//Returns
//		The new GNode.
GNode* g_node_prepend_data(GNode* parent, void* data) {
	return g_node_prepend(parent, g_node_new(data));
}
/*--------------------------------------------------------------------------*/
//Reverses the order of the children of a GNode.
//It doesn't change the order of the grandchildren.
//Parameters
//		node		A GNode.
void g_node_reverse_children(GNode* node) {
	GNode* child = node->children;
	while(child) {
		node->children = child;
		                 child = node->children->next;
		                         node->children->next = node->children->prev;
		                                                node->children->prev = child;
	}
}
/*--------------------------------------------------------------------------*/
static int g_node_traverse_pre_or_post_order(GNode* node, int order, int flags, int depth, int (*func)(GNode* node, void* data), void* data) {
	//指定されたノードの、子ノードが有れば…
	if(node->children) {
		//Pre orderならば…
		if(order == G_PRE_ORDER) {
//{{2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
#ifndef GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
//}}2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
			//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if((flags & G_TRAVERSE_NON_LEAVES) && (*func)(node, data)) { return 1/*TRUE*/; }				//【Pre order】このコールバック関数が、コールバック関数に渡されたノードを削除すると、以下の処理が正常に動作しません。以下の処理の中で、削除されたnodeにアクセスしてしまうからです。ただし、コールバック関数に渡されたノードの'子ノード'は削除しても安全です。以下の処理の中で、node->childrenを再取得しているからです。
//{{2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
#else //GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
			//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if(flags & G_TRAVERSE_NON_LEAVES) {
				int retval;
			    #ifdef  _DEBUG
				int save_prevent_memory_free;
			    #endif//_DEBUG
				if(node->_prevent_memory_free >= USHRT_MAX) { DIE(); }			//g_tree_traverse()のネストが深過ぎる。
				if(node->_request_memory_free) { DIE(); }				//既にメモリ開放要求フラグがセットされている事は無いはず。
				node->_prevent_memory_free++;						//メモリ開放抑制カウンタを増やす。
			    #ifdef  _DEBUG
				save_prevent_memory_free = node->_prevent_memory_free;			//デバッグのために、コールバック関数を呼び出す前の、メモリ開放抑制カウンタの元の値を記憶しておく。
			    #endif//_DEBUG
				retval = (*func)(node, data);						//コールバック関数を呼び出す。
			    #ifdef  _DEBUG
				if(node->_prevent_memory_free != save_prevent_memory_free) { DIE(); }	//コールバック関数の呼び出しによって、メモリ開放抑制カウンタが変化する事は無いはず。(もしg_tree_traverse()がネストしていても、±で元に戻っているはず。)
			    #endif//_DEBUG
				node->_prevent_memory_free--;						//メモリ開放抑制カウンタを減らす。
				if(node->_request_memory_free) {					//メモリ開放要求フラグがセットされていたら…(=nodeのメモリは未開放であるが、_prevent_memory_freeと_request_memory_free以外のフィールドはもう無効です。)
					if(!node->_prevent_memory_free) {				//メモリ開放抑制カウンタが0ならば…(=もしg_tree_traverse()がネストしていた場合は、一番外側のg_tree_traverse()ならば…)
						free(node);						//メモリを解放する。メモリ開放以外の処理(親ノードからの取り外しや子ノードのリスト削除)は、既にg_node_destroy(),及び,g_nodes_free()で行われているので、ここでは単純にメモリを解放するだけで良い。
					}
					return retval;							//このノード(=削除済み)の子ノードリスト(=削除済み)のトラバースをキャンセルして、コールバック関数の戻り値を返す。キャンセルするのはこのノード(=削除済み)の子ノードリスト(=削除済み)のトラバースだけであり、トラバース全体を継続するかどうかはコールバック関数の戻り値による事に注意せよ。
				}
				if(retval) { return 1/*TRUE*/; }					//コールバック関数が0以外を返したら、トラバースを中止する。
			}
#endif//GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
//}}2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
		}
		//目標レベルに到達していなければ…
		if(--depth) {
			//指定されたノードの、最初の子ノード,又は,NULLを取得する。
			GNode* child = node->children;											//【Pre order】上のコールバック関数が、コールバック関数に渡されたノードの'子ノード'を削除する可能性が有るので、ここでnode->childrenを再取得する必要が有ります。
			//子ノードのリストの末尾に到達するまで…
			while(child) {
				//現在の子ノードを記憶しておく。
				GNode* current = child;
				//コールバック関数を呼び出す前に、次の子ノードを取得しておく。
				child = child->next;
				//現在の子ノードについて、再帰する。
				if(g_node_traverse_pre_or_post_order(current, order, flags, depth, func, data)) { return 1/*TRUE*/; }	//【Pre order】【Post order】この再帰処理の中で呼び出されたコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
			}
		}
		//Post orderならば…
		if(order == G_POST_ORDER) {
			//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if((flags & G_TRAVERSE_NON_LEAVES) && (*func)(node, data)) { return 1/*TRUE*/; }				//【Post order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
		}
	//指定されたノードの、子ノードが無ければ…
	} else {
		//G_TRAVERSE_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
		if((flags & G_TRAVERSE_LEAVES) && (*func)(node, data)) { return 1/*TRUE*/; }						//【Pre order】【Post order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
	}
	return 0/*FALSE*/;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int g_node_traverse_level(GNode* node, int flags, int level, int (*func)(GNode* node, void* data), void* data) {
	//目標レベルに到達していなければ…
	if(--level) {
		//指定されたノードの、最初の子ノード,又は,NULLを取得する。
		node = node->children;
		//子ノードのリストの末尾に到達するまで…
		while(node) {
			//現在の子ノードを記憶しておく。
			GNode* current = node;
			//コールバック関数を呼び出す前に、次の子ノードを取得しておく。
			node = node->next;
			//現在の子ノードについて、再帰する。
			if(g_node_traverse_level(current, flags, level, func, data)) { return 1/*TRUE*/; }				//【Level order】この再帰処理の中で呼び出されたコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
		}
	//目標レベルに到達したら…
	} else {
		//指定されたノードの、子ノードが有れば…
		if(node->children) {
			//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if((flags & G_TRAVERSE_NON_LEAVES) && (*func)(node, data)) { return 1/*TRUE*/; }				//【Level order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
		//指定されたノードの、子ノードが無ければ…
		} else {
			//G_TRAVERSE_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if((flags & G_TRAVERSE_LEAVES) && (*func)(node, data)) { return 1/*TRUE*/; }					//【Level order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
		}
	}
	return 0/*FALSE*/;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//Traverses a tree starting at the given root GNode.
//It calls the given function for each node visited.
//The traversal can be halted at any point by returning TRUE from func.
//Parameters
//		root		The root GNode of the tree to traverse.
//		order		The order in which nodes are visited - G_IN_ORDER, G_PRE_ORDER, G_POST_ORDER, or G_LEVEL_ORDER.
//		flags		Which types of children are to be visited, one of G_TRAVERSE_ALL, G_TRAVERSE_LEAVES and G_TRAVERSE_NON_LEAVES.
//		depth		The maximum depth of the traversal.
//				Nodes below this depth will not be visited.
//				If depth is -1 all nodes in the tree are visited.
//				If depth is 1, only the root is visited.
//				If depth is 2, the root and its children are visited.
//				And so on.
//		func		The function to call for each visited GNode.
//		data		User data to pass to the function.
//[note]
//	- 【Pre order】の場合
//	  ×コールバック関数が、'コールバック関数に渡されたノード'を削除してはいけません。		←←★要注意★			//{{2016/08/27コメント追記:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。}}
//	  ○コールバック関数が、'コールバック関数に渡されたノードの子ノード'を削除しても安全です。
//	  ×コールバック関数が、上記以外のツリー構造を変化させた場合の動作は未定義です。
//	- 【Post order】又は【Level order】の場合
//	  ○コールバック関数が、'コールバック関数に渡されたノード'を削除しても安全です。
//	  ○コールバック関数が、'コールバック関数に渡されたノードの子ノード'を削除しても安全です。
//	  ×コールバック関数が、上記以外のツリー構造を変化させた場合の動作は未定義です。
void g_node_traverse(GNode* root, int order, int flags, int depth, int (*func)(GNode* node, void* data), void* data) {
	switch(order) {
	default:DIE();
//省略	case G_IN_ORDER:
//省略		g_node_depth_traverse_in_order(root, flags, depth, func, data);
//省略		break;
	case G_PRE_ORDER:
	case G_POST_ORDER:
		{
			//最大深度が0以外ならば…
			if(depth) {
				//トラバース関数を呼び出す。
				g_node_traverse_pre_or_post_order(root, order, flags, depth, func, data);
			}
		}
		break;
	case G_LEVEL_ORDER:
		{
			//ツリーの最大深度を求めます。
			int level, height = g_node_max_height(root);
			//指定された最大深度(,又は,-1=無限)を、ツリーの最大深度に切り詰めます。
			if((unsigned)depth > (unsigned)height) { depth = height; }
			//最大深度が0以外ならば、最大深度までの各レベルについて…
			for(level = 1; level <= depth; level++) {
				//トラバース関数を呼び出す。
				if(g_node_traverse_level(root, flags, level, func, data)) { break; }
			}
		}
		break;
	}
}
/*--------------------------------------------------------------------------*/
//Calls a function for each of the children of a GNode.
//Note that it doesn't descend beneath the child nodes.
//Parameters
//		node		A GNode.
//		flags		Which types of children are to be visited, one of G_TRAVERSE_ALL, G_TRAVERSE_LEAVES and G_TRAVERSE_NON_LEAVES.
//		func		The function to call for each visited node.
//		data		User data to pass to the function.
//[note]
//	- ○コールバック関数が、'コールバック関数に渡されたノード'を削除しても安全です。
//	  ○コールバック関数が、'コールバック関数に渡されたノードの子ノード'を削除しても安全です。
//	  ×コールバック関数が、上記以外のツリー構造を変化させた場合の動作は未定義です。
void g_node_children_foreach(GNode* node, int flags, void (*func)(GNode* node, void* data), void* data) {
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//子ノードのリストの末尾に到達するまで…
	while(node) {
		//現在の子ノードを記憶しておく。
		GNode* current = node;
		//コールバック関数を呼び出す前に、次の子ノードを取得しておく。
		// - 先に次の子ノードへ進めておく理由は、コールバック関数が現在の子ノードを削除しても、正常に動作出来るようにするためです。
		//   ただし、コールバック関数が次の子ノードを削除した場合は、正常に動作出来ません。
		//   現在の子ノードを削除したいケースは多いが、次の子ノードを削除したいケースは少ないと想定して、前者のみ対策してあります。
		node = node->next;
		//現在の子ノードがリーフならば…
		if(G_NODE_IS_LEAF(current)) {
			//G_TRAVERSE_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if(flags & G_TRAVERSE_LEAVES) { (*func)(current, data); }
		//現在の子ノードがリーフでなければ…
		} else {
			//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
			if(flags & G_TRAVERSE_NON_LEAVES) { (*func)(current, data); }
		}
	}
}
/*--------------------------------------------------------------------------*/
//Gets the root of a tree.
//Parameters
//		node		A GNode.
//Returns
//		The root of the tree.
GNode* g_node_get_root(GNode* node) {
	while(node->parent) {
		node = node->parent;
	}
	return node;
}
/*--------------------------------------------------------------------------*/
static int g_node_find_func(GNode* node, void* data) {
	void** d = data;
	if(d[0] == node->data) {
		d[1] = node;
		return 1/*TRUE*/;
	} else {
		return 0/*FALSE*/;
	}
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//Finds a GNode in a tree.
//Parameters
//		root		The root GNode of the tree to search.
//		order		The order in which nodes are visited - G_IN_ORDER, G_PRE_ORDER, G_POST_ORDER, or G_LEVEL_ORDER.
//		flags		Which types of children are to be searched, one of G_TRAVERSE_ALL, G_TRAVERSE_LEAVES and G_TRAVERSE_NON_LEAVES.
//		data		The data to find.
//Returns
//		The found GNode, or NULL if the data is not found.
GNode* g_node_find(GNode* root, int order, int flags, void* data) {
	void* d[2];
	d[0] = data;
	d[1] = NULL;
	g_node_traverse(root, order, flags, -1/*depth*/, g_node_find_func, d);
	return d[1];
}
/*--------------------------------------------------------------------------*/
//Finds the first child of a GNode with the given data.
//Parameters
//		node		A GNode.
//		flags		Which types of children are to be searched, one of G_TRAVERSE_ALL, G_TRAVERSE_LEAVES and G_TRAVERSE_NON_LEAVES.
//		data		The data to find.
//Returns
//		The found child GNode, or NULL if the data is not found.
GNode* g_node_find_child(GNode* node, int flags, void* data) {
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//子ノードのリストの末尾に到達するまで…
	while(node) {
		//この子ノードのデータが、指定されたデータに一致したら…
		if(node->data == data) {
			//この子ノードがリーフならば…
			if(G_NODE_IS_LEAF(node)) {
				//G_TRAVERSE_LEAVESフラグが指定されていたら、この子ノードを返す。
				if(flags & G_TRAVERSE_LEAVES) { return node; }
			//この子ノードがリーフでなければ…
			} else {
				//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、この子ノードを返す。
				if(flags & G_TRAVERSE_NON_LEAVES) { return node; }
			}
		}
		//次の子ノードへ進める。
		node = node->next;
	}
	//条件に一致する子ノードが見つからなければ、NULLを返す。
	return NULL;
}
/*--------------------------------------------------------------------------*/
//Gets the position of the first child of a GNode which contains the given data.
//Parameters
//		node		A GNode.
//		data		The data to find.
//Returns
//		The index of the child of node which contains data, or -1 if the data is not found.
int g_node_child_index(GNode* node, void* data) {
	int n = 0;
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//子ノードのリストの末尾に到達するまで…
	while(node) {
		//この子ノードのデータが、指定されたデータに一致したら、この子ノードのインデクスを返す。
		if(node->data == data) { return n; }
		//インデクスを進める。
		n++;
		//次の子ノードへ進める。
		node = node->next;
	}
	//指定されたデータに一致する子ノードが見つからなければ、-1を返す。
	return -1;
}
/*--------------------------------------------------------------------------*/
//Gets the position of a GNode with respect to its siblings. child must be a child of node.
//The first child is numbered 0, the second 1, and so on.
//Parameters
//		node		A GNode.
//		child		A child of node.
//Returns
//		The position of child with respect to its siblings.
int g_node_child_position(GNode* node, GNode* child) {
	int n = 0;
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//子ノードのリストの末尾に到達するまで…
	while(node) {
		//この子ノードが、指定されたノードに一致したら、この子ノードのインデクスを返す。
		if(node == child) { return n; }
		//インデクスを進める。
		n++;
		//次の子ノードへ進める。
		node = node->next;
	}
	//指定されたノードに一致する子ノードが見つからなければ、-1を返す。
	return -1;
}
/*--------------------------------------------------------------------------*/
//Gets the first child of a GNode.
//Parameters
//		node		A GNode.
//Returns
//		The first child of node, or NULL if node is NULL or has no children.
GNode* g_node_first_child(GNode* node) {
	return node ? node->children : NULL;
}
/*--------------------------------------------------------------------------*/
//Gets the last child of a GNode.
//Parameters
//		node		A GNode (must not be NULL).
//
//Returns
//		The last child of node, or NULL if node has no children.
GNode* g_node_last_child(GNode* node) {
	return node->children ? g_node_last_sibling(node->children) : NULL;
}
/*--------------------------------------------------------------------------*/
//Gets a child of a GNode, using the given index.
//The first child is at index 0.
//If the index is too big, NULL is returned.
//Parameters
//		node		A GNode.
//		n		The index of the desired child.
//Returns
//		The child of node at index n.
GNode* g_node_nth_child(GNode* node, int n) {
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//子ノードのリストの末尾に到達するまで…
	while(node) {
		//指定されたインデクスに到達したら、抜ける。
		if(!n--) { break; }
		//次の子ノードへ進める。
		node = node->next;
	}
	//指定されたインデクスの子ノード,又は,NULLを返す。
	return node;
}
/*--------------------------------------------------------------------------*/
//Gets the first sibling of a GNode.
//This could possibly be the node itself.
//Parameters
//		node		A GNode.
//Returns
//		The first sibling of node.
GNode* g_node_first_sibling(GNode* node) {
//不要	if(node->parent) { return node->parent->children; }	//この処理は高速化のためだけであり、行っても行わなくても結果は同じです。
	while(node->prev) { node = node->prev; }
	return node;
}
/*--------------------------------------------------------------------------*/
//Gets the next sibling of a GNode.
//Parameters
//		node		A GNode.
//Returns
//		The next sibling of node, or NULL if node is the last node or NULL.
GNode* g_node_next_sibling(GNode* node) {
	return node ? node->next : NULL;
}
/*--------------------------------------------------------------------------*/
//Gets the previous sibling of a GNode.
//Parameters
//		node		A GNode.
//Returns
//		The previous sibling of node, or NULL if node is the first node or NULL.
GNode* g_node_prev_sibling(GNode* node) {
	return node ? node->prev : NULL;
}
/*--------------------------------------------------------------------------*/
//Gets the last sibling of a GNode.
//This could possibly be the node itself.
//Parameters
//		node		A GNode.
//Returns
//		The last sibling of node.
GNode* g_node_last_sibling(GNode* node) {
	while(node->next) { node = node->next; }
	return node;
}
/*--------------------------------------------------------------------------*/
//Gets the depth of a GNode.
//If node is NULL the depth is 0.
//The root node has a depth of 1.
//For the children of the root node the depth is 2.
//And so on.
//Parameters
//		node		A GNode.
//Returns
//		The depth of the GNode.
int g_node_depth(GNode* node) {
	int depth = 0;
	while(node) {
		depth++;
		node = node->parent;
	}
	return depth;
}
/*--------------------------------------------------------------------------*/
static int g_node_count_func(GNode* node, int flags, int n) {
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//指定されたノードの、子ノードが有れば…
	if(node) {
		//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、ノードの数を増やす。
		if(flags & G_TRAVERSE_NON_LEAVES) { n++; }
		//子ノードのリストの末尾に到達するまで…
		do {
			//この子ノードについて、再帰する。
			n = g_node_count_func(node, flags, n);
			//次の子ノードへ進める。
			node = node->next;
		} while(node);
	//指定されたノードの、子ノードが無ければ…
	} else {
		//G_TRAVERSE_LEAVESフラグが指定されていたら、ノードの数を増やす。
		if(flags & G_TRAVERSE_LEAVES) { n++; }
	}
	//ノードの数を増やした結果を返す。
	return n;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//Gets the number of nodes in a tree.
//Parameters
//		root		A GNode.
//		flags		Which types of children are to be counted, one of G_TRAVERSE_ALL, G_TRAVERSE_LEAVES and G_TRAVERSE_NON_LEAVES.
//Returns
//		The number of nodes in the tree.
int g_node_n_nodes(GNode* root, int flags) {
	return g_node_count_func(root, flags, 0);
}
/*--------------------------------------------------------------------------*/
//Gets the number of children of a GNode.
//Parameters
//		node		A GNode.
//Returns
//		The number of children of node.
int g_node_n_children(GNode* node) {
	int n = 0;
	//指定されたノードの、最初の子ノード,又は,NULLを取得する。
	node = node->children;
	//子ノードのリストの末尾に到達するまで…
	while(node) {
		//子ノードの数を増やす。
		n++;
		//次の子ノードへ進める。
		node = node->next;
	}
	//子ノードの数を返す。
	return n;
}
/*--------------------------------------------------------------------------*/
//Returns TRUE if node is an ancestor of descendant.
//This is true if node is the parent of descendant, or if node is the grandparent of descendant etc.
//Parameters
//		node		A GNode.
//		descendant	A GNode.
//Returns
//		TRUE if node is an ancestor of descendant.
int g_node_is_ancestor(GNode* node, GNode* descendant) {
	while(descendant) {
		descendant = descendant->parent;
		if(descendant == node) { return 1/*TRUE*/; }
	}
	return 0/*FALSE*/;
}
/*--------------------------------------------------------------------------*/
//Gets the maximum height of all branches beneath a GNode.
//This is the maximum distance from the GNode to all leaf nodes.
//If root is NULL, 0 is returned.
//If root has no children, 1 is returned.
//If root has children, 2 is returned.
//And so on.
//Parameters
//		root		A GNode.
//Returns
//		The maximum height of the tree beneath root.
int g_node_max_height(GNode* root) {
	int max_height = 0;	//(root==NULL)ならば0を返す。
	if(root) {
		GNode* child = root->children;
		while(child) {
			int tmp_height = g_node_max_height(child);
			if(tmp_height > max_height) { max_height = tmp_height; }
			child = child->next;
		}
		max_height++;	//(root!=NULL)ならば1〜を返す。
	}
	return max_height;
}
/*--------------------------------------------------------------------------*/
//Unlinks a GNode from a tree, resulting in two separate trees.
//Parameters
//		node		The GNode to unlink, which becomes the root of a new tree.
void g_node_unlink(GNode* node) {
	//指定されたノードが、最後のノードでなければ…
	if(node->next) {				//prev<----->node<--->next
		node->next->prev = node->prev;		//prev<---------------next
	}
	//指定されたノードが、最初のノードでなければ…
	if(node->prev) {				//prev<----->node---->next
		node->prev->next = node->next;		//prev--------------->next
	//指定されたノードが、親ノードの最初の子ノードならば…
	} else if(node->parent) {			//parent<===>node---->next
		node->parent->children = node->next;	//parent=============>next
	}
	//指定されたノードの、next,prev,parentを確実にクリアする。
	node->next   = NULL;				//prev<------node-×->next
	node->prev   = NULL;				//prev<---×-node
	node->parent = NULL;				//parent<=×=node
}
/*--------------------------------------------------------------------------*/
static void g_nodes_free(GNode* node) {
	while(node) {
		//現在のノードを記憶しておく。
		GNode* current = node;
		//現在のノードのメモリを開放する前に、次の子ノードを取得しておく。
		node = node->next;
		//現在のノードの、子ノードを削除する。
	//不要	if(current->children) {	//この判断はg_nodes_free()の処理に含まれているので不要です。
			g_nodes_free(current->children);
	//不要	}
//{{2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
#ifndef GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
//}}2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
		//現在のノードのメモリを開放する。
		free(current);
//{{2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
#else //GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
		//現在のノードのメモリを開放する。
		if(current->_request_memory_free) { DIE(); }	//既にメモリ開放要求フラグがセットされている事は無いはず。
		if(current->_prevent_memory_free) {		//メモリ開放抑制カウンタが増やされていたら…(=(g_node_traverse(G_PRE_ORDER)⇒このノードに対するg_node_traverse_pre_or_post_order()⇒PreOrderのタイミングでのコールバック関数呼び出し){1,}⇒このノードに対するg_node_destroy()⇒g_nodes_free()という経路で呼び出されたならば…)
			current->_request_memory_free = 1;	//メモリ開放要求フラグをセットし、まだメモリは開放しない。
		} else {					//メモリ開放抑制カウンタが増やされていなければ…(=上記以外の経路で呼び出された場合…)
			free(current);				//メモリを解放する。
		}
#endif//GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
//}}2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
	}
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//Removes root and its children from the tree, freeing any memory allocated.
//Parameters
//		root		The root of the tree/subtree to destroy.
void g_node_destroy(GNode* root) {
//不要	if(!G_NODE_IS_ROOT(root)) {	//この判断はg_node_unlink()の処理に含まれているので不要です。
		g_node_unlink(root);
//不要	}
	g_nodes_free(root);
}
