//
//	gnode.cs
//
//	N-ary Trees - trees of data with any number of branches
//
//	* Mon Mar 06 23:24:18 JST 2017 Naoyuki Sawa
//	- 1st リリース。
//	- .NET Frameworkには、ツリー構造のコレクションクラスが無いそうです。
//	  CLiPライブラリを.NET版に移植するに当たって、.NET Frameworkのコレクションクラスで用が足りる場合はなるべくそれらを使う事にしているのですが、
//	  .NET Frameworkにはツリー構造のコレクションクラスは無いそうなので、仕方なくツリー構造のコレクションクラスはC言語版から移植する事にしました。
//	- C言語版に有ったGNODE_SAFE_SELF_DESTRUCTION_DURING_PRE_ORDER_TRAVERSINGの仕組みは、C#版では不要なので削除しました。
//	  ただしその代わりとして、g_nodes_free()にC#版特有の処理が必要になりました。
//	  詳細は、g_nodes_free()内のコメントを参照して下さい。
//
using System;
namespace org.piece_me {
	public static partial class libclip {
		//*****************************************************************************
		//	定数
		//*****************************************************************************
		//Specifies the type of traveral performed by g_tree_traverse(), g_node_traverse() and g_node_find().
		//The different orders are illustrated here:
		//省略	public const int 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.
		public const int G_PRE_ORDER		= 1;	//Visits a node, then its children.
		public const int G_POST_ORDER		= 2;	//Visits the node's children, then the node itself.
		public const int 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().
		public const int 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.
		public const int 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.
		public const int G_TRAVERSE_ALL		= (G_TRAVERSE_LEAVES|G_TRAVERSE_NON_LEAVES);	//All nodes should be visited.
		public const int G_TRAVERSE_MASK	= G_TRAVERSE_ALL;				//A mask of all traverse flags.
		public const int G_TRAVERSE_LEAFS	= G_TRAVERSE_LEAVES;				//Identical to G_TRAVERSE_LEAVES.
		public const int 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).
		public static bool G_NODE_IS_ROOT(GNode node) {
			return (node.parent == null) &&
			       (node.prev   == null) &&
			       (node.next   == null);
		}
		//-----------------------------------------------------------------------------
		//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).
		public static bool G_NODE_IS_LEAF(GNode node) {
			return node.children == null;
		}
		//*****************************************************************************
		//	構造体
		//*****************************************************************************
		//The GNode struct represents one node in a n-ary tree.
		public class GNode {
			public object		data;			//Contains the actual data of the node.
			public GNode		next;			//Points to the node's next sibling (a sibling is another GNode with the same parent).
			public GNode		prev;			//Points to the node's previous sibling.
			public GNode		parent;			//Points to the parent of the GNode, or is null if the GNode is the root of the tree.
			public GNode		children;		//Points to the first child of the GNode. The other children are accessed by using the next pointer of each child.
		}
		//*****************************************************************************
		//	
		//*****************************************************************************
		//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.
		public static GNode g_node_new(object data) {
			//新しいノードのメモリを確保する。
			GNode node = new GNode();
			//新しいノードにデータを格納する。
			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.
		public static 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.
		public static GNode g_node_copy_deep(GNode node, Func<object/*src*/,object/*data*/,object> copy_func, object data) {
			object new_data;
			GNode new_node, child, new_child;
			//指定されたノードのデータを取得する。
			new_data = node.data;
			//コピー関数が指定されていたら、データを複製する。
			if(copy_func != null) { new_data = copy_func.Invoke(new_data, data); }
			//新しいノードを作成する。
			new_node = g_node_new(new_data);
			//指定されたノードの全ての子ノードについて…
			for(child = g_node_first_child(node);
			    child != null;
			    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.
		public static 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.
		public static GNode g_node_insert_before(GNode parent, GNode sibling, GNode node) {
			//指定されたノードに、指定された親ノードを格納する。
			node.parent = parent;
			//追加する位置のノードが指定されていたら…
			if(sibling != null) {
				//追加する位置のノードが、最初の子ノードでなければ…
				if(sibling.prev != null) {		//○<------------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 != null) {
					//指定された親ノードの、最後の子ノードを取得する。
					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.
		public static GNode g_node_insert_after(GNode parent, GNode sibling, GNode node) {
			//指定されたノードに、指定された親ノードを格納する。
			node.parent = parent;
			//追加する位置のノードが指定されていたら…
			if(sibling != null) {
				//追加する位置のノードが、最後の子ノードでなければ…
				if(sibling.next != null) {		//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 != null) {		//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.
		public static 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.
		public static 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.
		public static GNode g_node_insert_data(GNode parent, int position, object 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.
		public static GNode g_node_insert_data_after(GNode parent, GNode sibling, object 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.
		public static GNode g_node_insert_data_before(GNode parent, GNode sibling, object 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.
		public static GNode g_node_append_data(GNode parent, object 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.
		public static GNode g_node_prepend_data(GNode parent, object 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.
		public static void g_node_reverse_children(GNode node) {
			GNode child = node.children;
			while(child != null) {
				node.children = child;
				                child = node.children.next;
				                        node.children.next = node.children.prev;
				                                             node.children.prev = child;
			}
		}
		//-----------------------------------------------------------------------------
		private static bool g_node_traverse_pre_or_post_order(GNode node, int order, int flags, int depth, Func<GNode/*node*/,object/*data*/,bool> func, object data) {
			//指定されたノードの、子ノードが有れば…
			if(node.children != null) {
				//Pre orderならば…
				if(order == G_PRE_ORDER) {
					//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
					if(((flags & G_TRAVERSE_NON_LEAVES) != 0) && func.Invoke(node, data)) { return true; }				//【Pre order】このコールバック関数が、コールバック関数に渡されたノードを削除すると、以下の処理が正常に動作しません。以下の処理の中で、削除されたnodeにアクセスしてしまうからです。ただし、コールバック関数に渡されたノードの'子ノード'は削除しても安全です。以下の処理の中で、node.childrenを再取得しているからです。
				}
				//目標レベルに到達していなければ…
				if(--depth != 0) {
					//指定されたノードの、最初の子ノード,又は,nullを取得する。
					GNode child = node.children;											//【Pre order】上のコールバック関数が、コールバック関数に渡されたノードの'子ノード'を削除する可能性が有るので、ここでnode.childrenを再取得する必要が有ります。
					//子ノードのリストの末尾に到達するまで…
					while(child != null) {
						//現在の子ノードを記憶しておく。
						GNode current = child;
						//コールバック関数を呼び出す前に、次の子ノードを取得しておく。
						child = child.next;
						//現在の子ノードについて、再帰する。
						if(g_node_traverse_pre_or_post_order(current, order, flags, depth, func, data)) { return true; }	//【Pre order】【Post order】この再帰処理の中で呼び出されたコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
					}
				}
				//Post orderならば…
				if(order == G_POST_ORDER) {
					//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
					if(((flags & G_TRAVERSE_NON_LEAVES) != 0) && func.Invoke(node, data)) { return true; }				//【Post order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
				}
			//指定されたノードの、子ノードが無ければ…
			} else {
				//G_TRAVERSE_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
				if(((flags & G_TRAVERSE_LEAVES) != 0) && func.Invoke(node, data)) { return true; }					//【Pre order】【Post order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
			}
			return false;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		private static bool g_node_traverse_level(GNode node, int flags, int level, Func<GNode/*node*/,object/*data*/,bool> func, object data) {
			//目標レベルに到達していなければ…
			if(--level != 0) {
				//指定されたノードの、最初の子ノード,又は,nullを取得する。
				node = node.children;
				//子ノードのリストの末尾に到達するまで…
				while(node != null) {
					//現在の子ノードを記憶しておく。
					GNode current = node;
					//コールバック関数を呼び出す前に、次の子ノードを取得しておく。
					node = node.next;
					//現在の子ノードについて、再帰する。
					if(g_node_traverse_level(current, flags, level, func, data)) { return true; }					//【Level order】この再帰処理の中で呼び出されたコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
				}
			//目標レベルに到達したら…
			} else {
				//指定されたノードの、子ノードが有れば…
				if(node.children != null) {
					//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
					if(((flags & G_TRAVERSE_NON_LEAVES) != 0) && func.Invoke(node, data)) { return true; }				//【Level order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
				//指定されたノードの、子ノードが無ければ…
				} else {
					//G_TRAVERSE_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
					if(((flags & G_TRAVERSE_LEAVES) != 0) && func.Invoke(node, data)) { return true; }				//【Level order】このコールバック関数が、コールバック関数に渡されたノードを削除しても安全です。
				}
			}
			return 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】の場合
		//	  ○コールバック関数が、'コールバック関数に渡されたノード'を削除しても安全です。
		//	  ○コールバック関数が、'コールバック関数に渡されたノードの子ノード'を削除しても安全です。
		//	  ×コールバック関数が、上記以外のツリー構造を変化させた場合の動作は未定義です。
		public static void g_node_traverse(GNode root, int order, int flags, int depth, Func<GNode/*node*/,object/*data*/,bool> func, object data) {
			switch(order) {
			default:throw new ApplicationException();
		//省略	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 != 0) {
						//トラバース関数を呼び出す。
						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((uint)depth > (uint)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]
		//	- ○コールバック関数が、'コールバック関数に渡されたノード'を削除しても安全です。
		//	  ○コールバック関数が、'コールバック関数に渡されたノードの子ノード'を削除しても安全です。
		//	  ×コールバック関数が、上記以外のツリー構造を変化させた場合の動作は未定義です。
		public static void g_node_children_foreach(GNode node, int flags, Action<GNode/*node*/,object/*data*/> func, object data) {
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//子ノードのリストの末尾に到達するまで…
			while(node != null) {
				//現在の子ノードを記憶しておく。
				GNode current = node;
				//コールバック関数を呼び出す前に、次の子ノードを取得しておく。
				// - 先に次の子ノードへ進めておく理由は、コールバック関数が現在の子ノードを削除しても、正常に動作出来るようにするためです。
				//   ただし、コールバック関数が次の子ノードを削除した場合は、正常に動作出来ません。
				//   現在の子ノードを削除したいケースは多いが、次の子ノードを削除したいケースは少ないと想定して、前者のみ対策してあります。
				node = node.next;
				//現在の子ノードがリーフならば…
				if(G_NODE_IS_LEAF(current)) {
					//G_TRAVERSE_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
					if((flags & G_TRAVERSE_LEAVES) != 0) { func.Invoke(current, data); }
				//現在の子ノードがリーフでなければ…
				} else {
					//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、コールバック関数を呼び出す。
					if((flags & G_TRAVERSE_NON_LEAVES) != 0) { func.Invoke(current, data); }
				}
			}
		}
		//-----------------------------------------------------------------------------
		//Gets the root of a tree.
		//Parameters
		//		node		A GNode.
		//Returns
		//		The root of the tree.
		public static GNode g_node_get_root(GNode node) {
			while(node.parent != null) {
				node = node.parent;
			}
			return node;
		}
		//-----------------------------------------------------------------------------
		private static bool g_node_find_func(GNode node, object data) {
			object[/*2*/] d = (object[/*2*/])data;
			if(d[0] == node.data) {
				d[1] = node;
				return true;
			} else {
				return 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.
		public static GNode g_node_find(GNode root, int order, int flags, object data) {
			object[/*2*/] d = new object[/*2*/] { data, null };
			g_node_traverse(root, order, flags, -1/*depth*/, g_node_find_func, d);
			return (GNode)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.
		public static GNode g_node_find_child(GNode node, int flags, object data) {
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//子ノードのリストの末尾に到達するまで…
			while(node != null) {
				//この子ノードのデータが、指定されたデータに一致したら…
				if(node.data == data) {
					//この子ノードがリーフならば…
					if(G_NODE_IS_LEAF(node)) {
						//G_TRAVERSE_LEAVESフラグが指定されていたら、この子ノードを返す。
						if((flags & G_TRAVERSE_LEAVES) != 0) { return node; }
					//この子ノードがリーフでなければ…
					} else {
						//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、この子ノードを返す。
						if((flags & G_TRAVERSE_NON_LEAVES) != 0) { 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.
		public static int g_node_child_index(GNode node, object data) {
			int n = 0;
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//子ノードのリストの末尾に到達するまで…
			while(node != null) {
				//この子ノードのデータが、指定されたデータに一致したら、この子ノードのインデクスを返す。
				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.
		public static int g_node_child_position(GNode node, GNode child) {
			int n = 0;
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//子ノードのリストの末尾に到達するまで…
			while(node != null) {
				//この子ノードが、指定されたノードに一致したら、この子ノードのインデクスを返す。
				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.
		public static GNode g_node_first_child(GNode node) {
			return node?.children;	//「return (node != null) ? 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.
		public static GNode g_node_last_child(GNode node) {
			return (node.children != null) ? 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.
		public static GNode g_node_nth_child(GNode node, int n) {
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//子ノードのリストの末尾に到達するまで…
			while(node != null) {
				//指定されたインデクスに到達したら、抜ける。
				if(n-- == 0) { 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.
		public static GNode g_node_first_sibling(GNode node) {
		//不要	if(node.parent != null) { return node.parent.children; }	//この処理は高速化のためだけであり、行っても行わなくても結果は同じです。
			while(node.prev != null) { 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.
		public static GNode g_node_next_sibling(GNode node) {
			return node?.next;	//「return (node != null) ? 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.
		public static GNode g_node_prev_sibling(GNode node) {
			return node?.prev;	//「(node != null) ? 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.
		public static GNode g_node_last_sibling(GNode node) {
			while(node.next != null) { 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.
		public static int g_node_depth(GNode node) {
			int depth = 0;
			while(node != null) {
				depth++;
				node = node.parent;
			}
			return depth;
		}
		//-----------------------------------------------------------------------------
		private static int g_node_count_func(GNode node, int flags, int n) {
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//指定されたノードの、子ノードが有れば…
			if(node != null) {
				//G_TRAVERSE_NON_LEAVESフラグが指定されていたら、ノードの数を増やす。
				if((flags & G_TRAVERSE_NON_LEAVES) != 0) { n++; }
				//子ノードのリストの末尾に到達するまで…
				do {
					//この子ノードについて、再帰する。
					n = g_node_count_func(node, flags, n);
					//次の子ノードへ進める。
					node = node.next;
				} while(node != null);
			//指定されたノードの、子ノードが無ければ…
			} else {
				//G_TRAVERSE_LEAVESフラグが指定されていたら、ノードの数を増やす。
				if((flags & G_TRAVERSE_LEAVES) != 0) { 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.
		public static 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.
		public static int g_node_n_children(GNode node) {
			int n = 0;
			//指定されたノードの、最初の子ノード,又は,nullを取得する。
			node = node.children;
			//子ノードのリストの末尾に到達するまで…
			while(node != null) {
				//子ノードの数を増やす。
				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.
		public static bool g_node_is_ancestor(GNode node, GNode descendant) {
			while(descendant != null) {
				descendant = descendant.parent;
				if(descendant == node) { return true; }
			}
			return 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.
		public static int g_node_max_height(GNode root) {
			int max_height = 0;	//(root==null)ならば0を返す。
			if(root != null) {
				GNode child = root.children;
				while(child != null) {
					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.
		public static void g_node_unlink(GNode node) {
			//指定されたノードが、最後のノードでなければ…
			if(node.next != null) {				//prev<----->node<--->next
				node.next.prev = node.prev;		//prev<---------------next
			}
			//指定されたノードが、最初のノードでなければ…
			if(node.prev != null) {				//prev<----->node---->next
				node.prev.next = node.next;		//prev--------------->next
			//指定されたノードが、親ノードの最初の子ノードならば…
			} else if(node.parent != null) {		//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
		}
		//-----------------------------------------------------------------------------
		private static void g_nodes_free(GNode node) {
			while(node != null) {
				//現在のノードを記憶しておく。
				GNode current = node;
				//現在のノードのメモリを開放する前に、次の子ノードを取得しておく。
				node = node.next;
				//現在のノードの、子ノードを削除する。
			//不要	if(current.children) {	//この判断はg_nodes_free()の処理に含まれているので不要です。
					g_nodes_free(current.children);
			//不要	}
//{{C#版特有の処理
				//【C#版特有の処理】現在のノードの子ノードのリストを空にしておく。
				// - g_node_traverse(～G_PRE_ORDER～)から呼び出されたコールバック関数がコールバック関数に渡されたnode自身を削除した場合に、
				//   g_node_traverse_pre_or_post_order()が削除されたnodeの子ノードをトラバースしてしまわないようにするために必要な処理です。
				//   C言語版はg_node_traverse_pre_or_post_order()にて'_request_memory_free'を見て判断していたので、current.childrenの値が残っていても構わなかったのですが、
				//   C#版は'_request_memory_free'を廃止したので、代わりに明示的にcurrent.childrenをクリアする事でC言語版と同じ動作となります。
				current.children = null;
//}}C#版特有の処理
			}
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//Removes root and its children from the tree, freeing any memory allocated.
		//Parameters
		//		root		The root of the tree/subtree to destroy.
		public static void g_node_destroy(GNode root) {
		//不要	if(!G_NODE_IS_ROOT(root)) {	//この判断はg_node_unlink()の処理に含まれているので不要です。
				g_node_unlink(root);
		//不要	}
			g_nodes_free(root);
		}
	}
}
//-----------------------------------------------------------------------------
// * Mon Mar 06 23:24:18 JST 2017 Naoyuki Sawa
// - gnode.hで2016/08/27にC言語版に対して行ったのと同じ検証を、C#版でも行ったので記録しておきます。
//■テストプログラム
//│using System.Diagnostics;
//│using static org.piece_me.libclip;
//│class Program {
//│  static void Main() {
//│    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);
//│  }
//│  static bool func(GNode node, object data) {
//│    string name = (string)node.data;
//│    int nest = (int)data;
//│    Debug.IndentLevel = nest;
//│    Debug.WriteLine("{0}", (object)name);
//│    if(name == "node1") {
//│      if(nest <= 1) {
//│        g_node_traverse(node.parent, G_PRE_ORDER, G_TRAVERSE_ALL, -1, func, (object)(nest + 1));
//│        if(nest == 1) {
//│          g_node_destroy(node);
//│          Debug.IndentLevel = nest;
//│          Debug.WriteLine("{0}自身を削除しました。", (object)name);
//│        }
//│      }
//│    }
//│    return false;
//│  }
//│}
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//□結果⇒C言語版と同じ結果になったので、C#版も正しく動作していると思います。
//│root
//│node1
//│    root
//│    node1
//│        root
//│        node1
//│        node11
//│        node12
//│        node2
//│        node21
//│        node22
//│    node1自身を削除しました。
//│    node2
//│    node21
//│    node22
//│node2
//│node21
//│node22
//-----------------------------------------------------------------------------
