/*
 *	gnode.h
 *
 *	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の同日のコメントを参照して下さい。
 */
#ifndef __GNODE_H__
#define __GNODE_H__
#ifdef  __cplusplus
extern "C" {
#endif//__cplusplus
/****************************************************************************
 *	G_PRE_ORDER内でnode自身を削除出来るようにするための独自拡張
 ****************************************************************************/
//{{2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
/*--------------------------------------------------------------------------*/
// * Sat Aug 27 21:24:43 JST 2016 Naoyuki Sawa
// - g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
//   詳細は、以下のとおりです。
// - これまで、g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除する事は出来ませんでした。
//   │void test() { g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, func, NULL); }
//   │int func(GNode* node, void* data) { g_node_destroy(node); return 0; } //この関数が処理を返した後、不正な動作となる。尚、1を返せば不正な動作にはならないが、これ以降のトラバースも全てキャンセルされるてしまうい、意図したトラバースの動作にならない。行いたい事は、このノードの子ノードリストのトラバースだけをキャンセルする事である。
//   なぜならば、削除されたnodeのメモリ上のnode->childrenを参照して、子ノードのリストのトラバースを継続しようとしてしまい、不正な動作になるからです。
//   上記の問題には、既に気付いていたのですが、オリジナル版のgnode.cの実装にも存在する制約(多分?)なので、そのままにしていました。
//   ちなみに、Boehm GCを併用していると、free()したメモリが0クリアされるようで、子ノードリストが空に見えて、偶然、不正な動作が顕在化しないようですが、正しい解決方法ではありません。
// - 上記の問題を、仕様としてそのまま受容しても良かったのですが、実際に使ってみると、g_node_traverse(〜G_PRE_ORDER〜)のコールバックでnode自身を削除出来ないのは、かなり不便でした。
//   例えば、ゲームのオブジェクトをツリー構造で管理する場合、親を子よりも先にトラバースする(G_PRE_ORDER)方が自然だと思うのですが、その際、親が自分自身を削除出来ないのは不便です。
//   G_PRE_ORDERの代りにG_POST_ORDER等を使えば、回避する事は可能ではありますが、親よりも子の処理が先に行われてしまうという不自然さが生じます。
// - そこで、上記の操作を可能とするための、変更を行う事にしました。
//   GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSINGシンボルを定義してライブラリをビルドすると、上記の操作が可能になります。
//   具体的には、g_node_traverse_pre_or_post_order()がコールバック関数を呼び出す前にメモリ開放抑制カウンタを増やして、g_nodes_free()によってメモリが開放されないようにします。
//   もし、コールバック関数の中でg_nodes_free()が呼び出されると、メモリを開放せずにメモリ開放要求フラグをセットして、g_node_traverse_pre_or_post_order()がメモリを開放します。
//   具体的には、gnode.cの、g_node_traverse_pre_or_post_order()とg_nodes_free()の実装を参照して下さい。
// - 上記の変更は、これまでは不正な動作になっていたものが、正常に動作できるようになったものですので、アプリケーションの観点からの非互換は生じません。
//   ただし、オリジナル版のgnode.cと比べて、GNode構造体のサイズが4バイト増えた事が、アプリケーションの観点から認識出来る非互換となります。
//   GNode構造体を、アプリケーションが独自に確保する事は無いはずなので、この非互換が問題になる事は無いと思いますが、一応、注意して下さい。
// - 尚、GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSINGシンボルを定義せずにライブラリをビルドすれば、変更前の動作に戻せます。
//   オリジナル版のgnode.cとの互換性が重要な場合は、GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSINGシンボルの定義をコメントアウトして下さい。
#define GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
/*--------------------------------------------------------------------------*/
//■テストプログラム
//│int func(GNode* node, void* data);
//│void test() {
//│  GNode *root, *node1, *node2, *node11, *node12, *node21, *node22;
//│  root = g_node_new("root");
//│    node1 = g_node_append_data(root, "node1");
//│      node11 = g_node_append_data(node1, "node11");
//│      node12 = g_node_append_data(node1, "node12");
//│    node2 = g_node_append_data(root, "node2");
//│      node21 = g_node_append_data(node2, "node21");
//│      node22 = g_node_append_data(node2, "node22");
//│  g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, func, 0);
//│  g_node_destroy(root);
//│}
//│int func(GNode* node, void* data) {
//│  const char* name = node->data;
//│  int nest = (int)data;
//│  printf("%*s%s\n", nest, "", name);
//│  if(!strcmp(name, "node1")) {
//│    if(nest <= 1) {
//│      g_node_traverse(node->parent, G_PRE_ORDER, G_TRAVERSE_ALL, -1, func, (void*)(nest + 1));
//│      if(nest == 1) {
//│        g_node_destroy(node);
//│        printf("%*s%s自身を削除しました。\n", nest, "", name);
//│      }
//│    }
//│  }
//│  return 0;
//│}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//□結果
//│root			←G_PRE_ORDERの順序で、親が先にトラバースされている事を確認しました。
//│node1
//│ root
//│ node1
//│  root
//│  node1
//│  node11
//│  node12
//│  node2
//│  node21
//│  node22
//│ node1自身を削除しました。	←実際にはここでは、node1のメモリ開放要求フラグをセットするだけで、node1のメモリ開放は行われていません。
//│ node2			←期待通り、ここでnode11とnode12のトラバースが行われていないので、正しく動作している事が確認出来ました。
//│ node21
//│ node22
//│node2			←期待通り、ここでnode11とnode12のトラバースが行われていないので、正しく動作している事が確認出来ました。ここでnode1のメモリ開放は行われています。
//│node21
//│node22
/*--------------------------------------------------------------------------*/
//}}2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
/****************************************************************************
 *	
 ****************************************************************************/
//The GNode struct and its associated functions provide a N-ary tree data structure, where nodes in the tree can contain arbitrary data.
//To create a new tree use g_node_new().
//To insert a node into a tree use g_node_insert(), g_node_insert_before(), g_node_append() and g_node_prepend().
//To create a new node and insert it into a tree use g_node_insert_data(), g_node_insert_data_after(), g_node_insert_data_before(), g_node_append_data() and g_node_prepend_data().
//To reverse the children of a node use g_node_reverse_children().
//To find a node use g_node_get_root(), g_node_find(), g_node_find_child(), g_node_child_index(), g_node_child_position(), g_node_first_child(), g_node_last_child(), g_node_nth_child(), g_node_first_sibling(), g_node_prev_sibling(), g_node_next_sibling() or g_node_last_sibling().
//To get information about a node or tree use G_NODE_IS_LEAF(), G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(), g_node_n_children(), g_node_is_ancestor() or g_node_max_height().
//To traverse a tree, calling a function for each node visited in the traversal, use g_node_traverse() or g_node_children_foreach().
//To remove a node or subtree from a tree use g_node_unlink() or g_node_destroy().
/*--------------------------------------------------------------------------*/
//The GNode struct represents one node in a n-ary tree.
typedef struct _GNode {
	void*			data;			//Contains the actual data of the node.
	struct _GNode*		next;			//Points to the node's next sibling (a sibling is another GNode with the same parent).
	struct _GNode*		prev;			//Points to the node's previous sibling.
	struct _GNode*		parent;			//Points to the parent of the GNode, or is NULL if the GNode is the root of the tree.
	struct _GNode*		children;		//Points to the first child of the GNode. The other children are accessed by using the next pointer of each child.
//{{2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
#ifdef  GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
	unsigned short		_prevent_memory_free;	//メモリ開放抑制カウンタ。(g_node_traverse_pre_or_post_order()から、g_nodes_free()への通知)	0〜USHRT_MAX	同じツリーに対してg_tree_traverse()がネストして呼び出された場合のために、フラグではなくカウンタとする必要が有る。	┬実際には、g_tree_traverse()をネストして使う事はほとんど無いし、有ってもせいぜい10回以下だと思うので、_prevent_memory_freeフィールドは4ビットも有れば充分です。同様に、_request_memory_freeも1ビットで充分です。
	unsigned short		_request_memory_free;	//メモリ開放要求フラグ。(g_nodes_free()から、g_node_traverse_pre_or_post_order()への通知)	0〜1																	┘ビットフィールドよりもバイト,又は,ハーフワードの方が処理効率が良いので今回はそうしましたが、もし今後この構造体にさらにフィールドを追加する場合は_prevent_memory_freeと_request_memory_freeをビットフィールドに変更しても構いません。
#endif//GNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSING
//}}2016/08/27追加:g_node_traverse(〜G_PRE_ORDER〜)から呼び出されたコールバック関数が、コールバック関数に渡されたnode自身を削除出来るようにしました。
} GNode;
/*--------------------------------------------------------------------------*/
//Specifies the type of traveral performed by g_tree_traverse(), g_node_traverse() and g_node_find().
//The different orders are illustrated here:
//┌───────────┐
//│　　　　　Ｆ　　　　　│
//│　　　　／　＼　　　　│
//│　　　／　　　＼　　　│
//│　　Ｂ　　　　　Ｇ　　│
//│　／　＼　　　　　＼　│
//│Ａ　　　Ｄ　　　　　Ｉ│
//│　　　／　＼　　　／　│
//│　　Ｃ　　　Ｅ　Ｈ　　│
//└───────────┘
//   In order: A, B, C, D, E, F, G, H, I	⇒省略しました。二分木ではないのでこの順序にはあまり意味が無いと思うからです。実装しても歪になるので省略して良いと思います。
//  Pre order: F, B, A, D, C, E, G, I, H
// Post order: A, C, E, D, B, H, I, G, F
//Level order: F, B, G, A, D, I, C, E, H
//省略	#define G_IN_ORDER	0	//Vists a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function.
#define G_PRE_ORDER		1	//Visits a node, then its children.
#define G_POST_ORDER		2	//Visits the node's children, then the node itself.
#define G_LEVEL_ORDER		3	//Is not implemented for balanced binary trees. For n-ary trees, it vists the root node first, then its children, then its grandchildren, and so on. Note that this is less efficient than the other orders.
/*--------------------------------------------------------------------------*/
//Specifies which nodes are visited during several of the tree functions, including g_node_traverse() and g_node_find().
#define G_TRAVERSE_LEAVES	(1<<0)						//Only leaf nodes should be visited. This name has been introduced in 2.6, for older version use G_TRAVERSE_LEAFS.
#define G_TRAVERSE_NON_LEAVES	(1<<1)						//Only non-leaf nodes should be visited. This name has been introduced in 2.6, for older version use G_TRAVERSE_NON_LEAFS.
#define G_TRAVERSE_ALL		(G_TRAVERSE_LEAVES|G_TRAVERSE_NON_LEAVES)	//All nodes should be visited.
#define G_TRAVERSE_MASK		G_TRAVERSE_ALL					//A mask of all traverse flags.
#define G_TRAVERSE_LEAFS	G_TRAVERSE_LEAVES				//Identical to G_TRAVERSE_LEAVES.
#define G_TRAVERSE_NON_LEAFS	G_TRAVERSE_NON_LEAVES				//Identical to G_TRAVERSE_NON_LEAVES.
/*--------------------------------------------------------------------------*/
//Returns TRUE if a GNode is the root of a tree.
//Parameters
//		node		A GNode.
//Returns
//		TRUE if the GNode is the root of a tree (i.e. it has no parent or siblings).
#define G_NODE_IS_ROOT(node)	((!((GNode*)(node))->parent)&& \
				 (!((GNode*)(node))->prev  )&& \
				 (!((GNode*)(node))->next  ))
/*--------------------------------------------------------------------------*/
//Returns TRUE if a GNode is a leaf node.
//Parameters
//		node		A GNode.
//Returns
//		TRUE if the GNode is a leaf node (i.e. it has no children).
#define G_NODE_IS_LEAF(node)	(!((GNode*)(node))->children)
/****************************************************************************
 *	
 ****************************************************************************/
GNode* g_node_new(void* data);
GNode* g_node_copy(GNode* node);
GNode* g_node_copy_deep(GNode* node, void* (*copy_func)(const void* src, void* data), void* data);
GNode* g_node_insert(GNode* parent, int position, GNode* node);
GNode* g_node_insert_before(GNode* parent, GNode* sibling, GNode* node);
GNode* g_node_insert_after(GNode* parent, GNode* sibling, GNode* node);
GNode* g_node_append(GNode* parent, GNode* node);
GNode* g_node_prepend(GNode* parent, GNode* node);
GNode* g_node_insert_data(GNode* parent, int position, void* data);
GNode* g_node_insert_data_after(GNode* parent, GNode* sibling, void* data);
GNode* g_node_insert_data_before(GNode* parent, GNode* sibling, void* data);
GNode* g_node_append_data(GNode* parent, void* data);
GNode* g_node_prepend_data(GNode* parent, void* data);
void g_node_reverse_children(GNode* node);
void g_node_traverse(GNode* root, int order, int flags, int depth, int (*func)(GNode* node, void* data), void* data);
void g_node_children_foreach(GNode* node, int flags, void (*func)(GNode* node, void* data), void* data);
GNode* g_node_get_root(GNode* node);
GNode* g_node_find(GNode* root, int order, int flags, void* data);
GNode* g_node_find_child(GNode* node, int flags, void* data);
int g_node_child_index(GNode* node, void* data);
int g_node_child_position(GNode* node, GNode* child);
GNode* g_node_first_child(GNode* node);
GNode* g_node_last_child(GNode* node);
GNode* g_node_nth_child(GNode* node, int n);
GNode* g_node_first_sibling(GNode* node);
GNode* g_node_next_sibling(GNode* node);
GNode* g_node_prev_sibling(GNode* node);
GNode* g_node_last_sibling(GNode* node);
int g_node_depth(GNode* node);
int g_node_n_nodes(GNode* root, int flags);
int g_node_n_children(GNode* node);
int g_node_is_ancestor(GNode* node, GNode* descendant);
int g_node_max_height(GNode* root);
void g_node_unlink(GNode* node);
void g_node_destroy(GNode* root);
#ifdef  __cplusplus
}//extern "C"
#endif//__cplusplus
#endif//__GNODE_H__
