//
//	gtree.cs
//
//	Balanced Binary Trees - a sorted collection of key/value pairs optimized for searching and traversing in order
//
//	* Sat Apr 08 21:36:32 JST 2017 Naoyuki Sawa
//	- 1st リリース。
//
using System;
using System.Collections.Generic;
namespace org.piece_me {
	public static partial class libclip {
		//*****************************************************************************
		//	GTree
		//*****************************************************************************
		public class GTree {	//The GTree struct is an opaque data structure representing a balanced binary tree. It should be accessed only by using the following functions.
			public GTreeNode						root;				//ルートノード
			public Func<object/*a*/,object/*b*/,object/*user_data*/,int>	key_compare_func;		//アプリケーション定義のキー比較関数
			public object							key_compare_data;		//アプリケーション定義のキー比較関数へ引き渡す任意のデータ
			public Action<object/*data*/>					key_destroy_func/*null可*/;	//アプリケーション定義のキー開放関数
			public Action<object/*data*/>					value_destroy_func/*null可*/;	//アプリケーション定義の値開放関数
			public int							nnodes;				//ノード数
			public int							ref_count;			//参照カウント
		}
		//-----------------------------------------------------------------------------
		public class GTreeNode {			//ノードの型
			public int		height;		//この部分木の高さ
			public object		key;		//このノードのキー
			public object		value;		//このノードの値
			public GTreeNode	lst;		//左部分木
			public GTreeNode	rst;		//右部分木
		}
		//-----------------------------------------------------------------------------
		private class GTreeTrio {			//補助情報の型
			public GTree		tree;		//指定されたツリー				[in]
			public object		key;		//指定されたキー,又は,最大キー			g_tree_insert_subr*()から使用する時は[in]	g_tree_remove_subr*()から使用する時は[in/out]
			public object		value;		//指定された値,又は,最大キーの値		g_tree_insert_subr*()から使用する時は[in]	g_tree_remove_subr*()から使用する時は[out]
			public int		mode;		//0=INSERT,1=REPLACE,2=REMOVE,3=STEAL		[in]
			public bool		found;		//削除するノードが見つかった事を示すフラグ	g_tree_insert_subr*()からは使用しない。		g_tree_remove_subr*()から使用する時は[out]
		}
		//*****************************************************************************
		//	ローカル関数
		//*****************************************************************************
		//ノードを作成する。
		private static GTreeNode g_tree_node_new(object key, object value) {
			//ノードのメモリを確保する。
			GTreeNode t = new GTreeNode();
			//フィールドを初期化する。
			t.height = 1;
			t.key    = key;
			t.value  = value;
			//作成したノードを返す。
			return t;
		}
		//-----------------------------------------------------------------------------
		//部分木の高さを返す。
		private static int g_tree_node_height(GTreeNode t/*null可*/) {
			return (t != null) ? t.height : 0;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//左右の部分木の高さの差を返す。左が高いと正、右が高いと負。
		private static int g_tree_node_bias(GTreeNode t) {
			return g_tree_node_height(t.lst/*null可*/) - g_tree_node_height(t.rst/*null可*/);
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//左右の部分木の高さから、その木の高さを計算して設定する。
		private static void g_tree_node_setHeight(GTreeNode t) {
			int lh = g_tree_node_height(t.lst/*null可*/);
			int rh = g_tree_node_height(t.rst/*null可*/);
			t.height = 1 + max(lh, rh);
		}
		//-----------------------------------------------------------------------------
		//二分探索木tの左回転。回転した木を返す。
		//	    t       	       u    
		//	  ／ ＼     	     ／ ＼  
		//	(a)    u    	    t    (b)
		//	     ／ ＼  	  ／ ＼     
		//	   (v)   (b)	(a)   (v)   
		private static GTreeNode g_tree_node_rotateL(GTree tree, GTreeNode t) {
			GTreeNode u = t.rst;	//null不可
			GTreeNode v = u.lst;	//null可
			u.lst = t;
			t.rst = v;
			g_tree_node_setHeight(t);
			g_tree_node_setHeight(u);
			return u;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//二分探索木tの右回転。回転した木を返す。
		//	       t    	    u       
		//	     ／ ＼  	  ／ ＼     
		//	    u    (a)	(b)    t    
		//	  ／ ＼     	     ／ ＼  
		//	(b)   (v)   	   (v)   (a)
		private static GTreeNode g_tree_node_rotateR(GTree tree, GTreeNode t) {
			GTreeNode u = t.lst;	//null不可
			GTreeNode v = u.rst;	//null可
			u.rst = t;
			t.lst = v;
			g_tree_node_setHeight(t);
			g_tree_node_setHeight(u);
			return u;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//二分探索木tの二重回転(左回転→右回転)。回転した木を返す。
		//	       t    	            t      	       v        
		//	     ／ ＼  	          ／ ＼    	     ／ ＼      
		//	    u    (a)	         v    (a)  	    u     t     
		//	  ／ ＼     	       ／ ＼       	  ／│   │＼   
		//	(b)    v    	      u    (d)     	(b) (c)  (d) (a)
		//	     ／ ＼  	    ／ ＼          	                
		//	   (c)   (d)	  (b)   (c)        	                
		private static GTreeNode g_tree_node_rotateLR(GTree tree, GTreeNode t) {
			t.lst = g_tree_node_rotateL(tree, t.lst);
			return   g_tree_node_rotateR(tree, t);
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//二分探索木tの二重回転(右回転→左回転)。回転した木を返す。
		//	    t       	      t            	       v        
		//	  ／ ＼     	    ／ ＼          	     ／ ＼      
		//	(a)    u    	  (a)    v         	    t     u     
		//	     ／ ＼  	       ／ ＼       	  ／│   │＼   
		//	    v    (b)	     (d)    u      	(a) (d)  (c) (b)
		//	  ／ ＼     	          ／ ＼    	                
		//	(d)   (c)   	        (c)   (b)  	                
		private static GTreeNode g_tree_node_rotateRL(GTree tree, GTreeNode t) {
			t.rst = g_tree_node_rotateR(tree, t.rst);
			return   g_tree_node_rotateL(tree, t);
		}
		//-----------------------------------------------------------------------------
		//部分木tのバランスを回復して戻り値で返す。auxに補助情報を返す。
		//左部分木への挿入に伴うAVL木の修正,又は,右部分木での削除に伴うAVL木の修正
		static GTreeNode g_tree_node_balanceL(GTreeTrio aux, GTreeNode t) {
			int bias = g_tree_node_bias(t);
#if     DEBUG
			if((bias > 2) || (bias < -1)) { throw new ApplicationException(); }		//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#endif//DEBUG
			if(bias == 2) {
				bias = g_tree_node_bias(t.lst);
#if     DEBUG
				if((bias > 1) || (bias < -1)) { throw new ApplicationException(); }	//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#endif//DEBUG
				if(bias >= 0) {
					t = g_tree_node_rotateR(aux.tree, t);				//回転処理の中で、'g_tree_node_setHeight(t)'も行われます。
				} else {
					t = g_tree_node_rotateLR(aux.tree, t);				//回転処理の中で、'g_tree_node_setHeight(t)'も行われます。
				}
			} else {
				g_tree_node_setHeight(t);						//回転処理を行わない場合は、明示的に'g_tree_node_setHeight(t)'を行います。
			}
			return t;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//部分木tのバランスを回復して戻り値で返す。auxに補助情報を返す。
		//右部分木への挿入に伴うAVL木の修正,又は,左部分木での削除に伴うAVL木の修正
		private static GTreeNode g_tree_node_balanceR(GTreeTrio aux, GTreeNode t) {
			int bias = g_tree_node_bias(t);
#if     DEBUG
			if((bias < -2) || (bias > 1)) { throw new ApplicationException(); }		//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#endif//DEBUG
			if(bias == -2) {
				bias = g_tree_node_bias(t.rst);
#if     DEBUG
				if((bias < -1) || (bias > 1)) { throw new ApplicationException(); }	//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#endif//DEBUG
				if(bias <= 0) {
					t = g_tree_node_rotateL(aux.tree, t);				//回転処理の中で、'g_tree_node_setHeight(t)'も行われます。
				} else {
					t = g_tree_node_rotateRL(aux.tree, t);				//回転処理の中で、'g_tree_node_setHeight(t)'も行われます。
				}
			} else {
				g_tree_node_setHeight(t);						//回転処理を行わない場合は、明示的に'g_tree_node_setHeight(t)'を行います。
			}
			return t;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//挿入時の修正(balanceLi:左部分木への挿入,balanceRi:右部分木への挿入)
		private static GTreeNode g_tree_node_balanceLi(GTreeTrio aux, GTreeNode t) { return g_tree_node_balanceL(aux, t); }
		private static GTreeNode g_tree_node_balanceRi(GTreeTrio aux, GTreeNode t) { return g_tree_node_balanceR(aux, t); }
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//削除時の修正(balanceLd:左部分木での削除,balanceRd:右部分木での削除)
		private static GTreeNode g_tree_node_balanceLd(GTreeTrio aux, GTreeNode t) { return g_tree_node_balanceR(aux, t); }
		private static GTreeNode g_tree_node_balanceRd(GTreeTrio aux, GTreeNode t) { return g_tree_node_balanceL(aux, t); }
		//-----------------------------------------------------------------------------
		//部分木tにキーkeyで値valueを挿入する。auxは補助情報。
		private static GTreeNode g_tree_insert_subr2(GTreeTrio aux, GTreeNode t/*null可*/) {
			//部分木tが指定されていたら…
			if(t != null) {
				//指定されたキーと、このノードのキーを比較する。
				int diff = aux.tree.key_compare_func.Invoke(aux.key, t.key, aux.tree.key_compare_data);
				//指定されたキーが、このノードのキーよりも小さければ…
				if(diff < 0) {
					//左部分木に対して再帰する。
					t.lst = g_tree_insert_subr2(aux, t.lst);
					//挿入時の修正を行う。
					t = g_tree_node_balanceLi(aux, t);
				//指定されたキーが、このノードのキーよりも大きければ…
				} else if(diff > 0) {
					//右部分木に対して再帰する。
					t.rst = g_tree_insert_subr2(aux, t.rst);
					//挿入時の修正を行う。
					t = g_tree_node_balanceRi(aux, t);
				//指定されたキーと、このノードのキーが一致したら…
				} else {
					//呼び出し元の関数によって…
					switch(aux.mode) {
					default:throw new ApplicationException();
					case 0/*INSERT*/:	//g_tree_insert()から呼び出された場合
						//指定されたキーを開放する。	←←←←要注意!! g_tree_insert()の場合は、既に同じキーのノードが有ったら、既存のキーが維持され、引数keyが指すキーが開放される。
						aux.tree.key_destroy_func.Invoke(aux.key);
						break;
					case 1/*REPLACE*/:	//g_tree_replace()から呼び出された場合
						//既存のキーを解放する。	←←←←要注意!! g_tree_replace()の場合は、既に同じキーのノードが有ったら、既存のキーが開放され、引数keyが指すキーが格納される。
						aux.tree.key_destroy_func.Invoke(t.key);
						//指定されたキーを格納する。
						t.key = aux.key;
						break;
					}
					//既存の値を解放する。
					aux.tree.value_destroy_func.Invoke(t.value);
					//指定された値を格納する。
					t.value = aux.value;
				}
			//部分木tが指定されていなければ…
			} else {
				//新しいノードを作成する。
				t = g_tree_node_new(aux.key, aux.value);
				//ノード数を増やす。
				aux.tree.nnodes++;
#if     DEBUG
				if(aux.tree.nnodes <= 0) { throw new ApplicationException(); }	//ここで停止したら当モジュールのバグです。
#endif//DEBUG
			}
			return t;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//tree.rootにキーkeyで値valueを挿入する。
		private static void g_tree_insert_subr1(GTree tree, object key, object value, int mode/*0=INSERT,1=REPLACE*/) {
			GTreeTrio aux = new GTreeTrio() { tree = tree, key = key, value = value, mode = mode };
			tree.root = g_tree_insert_subr2(aux, tree.root);
		}
		//-----------------------------------------------------------------------------
		//部分木tの最大キーのノードを削除する。
		//戻り値は削除により修正された部分木。
		//部分木tのキーの最大値とその値をauxに返す。
		private static GTreeNode g_tree_remove_subr3(GTreeTrio aux, GTreeNode t) {
			//このノードに、右部分木が有れば…
			if(t.rst != null) {
				//右部分木に対して再帰する。
				t.rst = g_tree_remove_subr3(aux, t.rst);
				//削除時の修正を行う。
				t = g_tree_node_balanceRd(aux, t);
			//このノードに、右部分木が無ければ…
			} else {
				//左部分木を取得しておく。
				GTreeNode u = t.lst;	//null可
				//このノードのキーと値を格納する。
				aux.key   = t.key;
				aux.value = t.value;
				//ノード数を減らす。
				aux.tree.nnodes--;
#if     DEBUG
				if(aux.tree.nnodes < 0) { throw new ApplicationException(); }	//ここで停止したら当モジュールのバグです。
#endif//DEBUG
				//このノードのメモリを開放する。
				/** no job **/
				//左部分木を昇格させる。
				t = u;
			}
			return t;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//部分木tからキーkeyのノードを削除する。auxは補助情報。
		private static GTreeNode g_tree_remove_subr2(GTreeTrio aux, GTreeNode t/*null可*/) {
			//部分木tが指定されていたら…
			if(t != null) {
				//指定されたキーと、このノードのキーを比較する。
				int diff = aux.tree.key_compare_func.Invoke(aux.key, t.key, aux.tree.key_compare_data);
				//指定されたキーが、このノードのキーよりも小さければ…
				if(diff < 0) {
					//左部分木に対して再帰する。
					t.lst = g_tree_remove_subr2(aux, t.lst);
					//削除時の修正を行う。
					t = g_tree_node_balanceLd(aux, t);
				//指定されたキーが、このノードのキーよりも大きければ…
				} else if(diff > 0) {
					//右部分木に対して再帰する。
					t.rst = g_tree_remove_subr2(aux, t.rst);
					//削除時の修正を行う。
					t = g_tree_node_balanceRd(aux, t);
				//指定されたキーと、このノードのキーが一致したら…
				} else {
					//このノードに、左部分木が有れば…
					if(t.lst != null) {
						//呼び出し元の関数によって…
						switch(aux.mode) {
						default:throw new ApplicationException();
						case 2/*REMOVE*/:	//g_tree_remove()から呼び出された場合
							//既存のキーを解放する。
							aux.tree.key_destroy_func.Invoke(t.key);
							//既存の値を解放する。
							aux.tree.value_destroy_func.Invoke(t.value);
							break;
						case 3/*STEAL*/:	//g_tree_steal()から呼び出された場合
							/** no job **/
							break;
						}
						//部分木tの最大キーのノードを削除し、キーと値を取得する。
						t.lst = g_tree_remove_subr3(aux, t.lst);
						//左部分木の最大キーで置き換える。
						t.key = aux.key;
						//左部分木の最大キーに対応する値で置き換える。
						t.value = aux.value;
						//削除時の修正を行う。
						t = g_tree_node_balanceLd(aux, t);
					//このノードに、左部分木が無ければ…
					} else {
						//右部分木を取得しておく。
						GTreeNode u = t.rst;	//null可
						//呼び出し元の関数によって…
						switch(aux.mode) {
						default:throw new ApplicationException();
						case 2/*REMOVE*/:	//g_tree_remove()から呼び出された場合
							//既存のキーを解放する。
							aux.tree.key_destroy_func.Invoke(t.key);
							//既存の値を解放する。
							aux.tree.value_destroy_func.Invoke(t.value);
							break;
						case 3/*STEAL*/:	//g_tree_steal()から呼び出された場合
							/** no job **/
							break;
						}
						//ノード数を減らす。
						aux.tree.nnodes--;
#if     DEBUG
						if(aux.tree.nnodes < 0) { throw new ApplicationException(); }	//ここで停止したら当モジュールのバグです。
#endif//DEBUG
						//このノードのメモリを開放する。
						/** no job **/
						//右部分木を昇格させる。
						t = u;
					}
					//削除するノードが見つかった事を示すフラグをセットする。
					aux.found = true;
				}
			//部分木tが指定されていなければ…
			} else {
				/** no job **/
			}
			return t;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//tree.rootからキーkeyのノードを削除する。
		private static bool g_tree_remove_subr1(GTree tree, object key, int mode/*2=REMOVE,3=STEAL*/) {
			GTreeTrio aux = new GTreeTrio() { tree = tree, key = key, value = null, mode = mode };
			tree.root = g_tree_remove_subr2(aux, tree.root);
			return aux.found;
		}
		//-----------------------------------------------------------------------------
		//ツリーを空にする。
		private static void g_tree_clear(GTree tree) {
			GTreeNode t;
			while((t = tree.root) != null) {
				g_tree_remove(tree, t.key);
			}
#if     DEBUG
			if(tree.nnodes != 0) { throw new ApplicationException(); }	//ここで停止したら当モジュールのバグです。
#endif//DEBUG
		}
		//*****************************************************************************
		//	グローバル関数
		//*****************************************************************************
		//Creates a new GTree.
		//Parameters
		//		key_compare_func	The function used to order the nodes in the GTree.
		//					It should return values similar to the standard strcmp() function - 0 if the two arguments are equal, a negative value if the first argument comes before the second, or a positive value if the first argument comes after the second.
		//Returns
		//		A newly allocated GTree.
		public static GTree g_tree_new(Func<object/*a*/,object/*b*/,int> key_compare_func) {
			return g_tree_new_with_data(delegate(object a, object b, object user_data) { return key_compare_func(a, b); }, null);
		}
		//-----------------------------------------------------------------------------
		//Increments the reference count of tree by one.
		//It is safe to call this function from any thread.				⇒当実装ではスレッドセーフではありません。複数のスレッドから参照する事は無いと思ったからです。実際の所g_tree_ref()/g_tree_unref()だけをスレッドセーフにしても他の関数がスレッドセーフでなければあまり意味は無いと思います。
		//Parameters
		//		tree			A GTree.
		//Returns
		//		The passed in GTree.
		public static GTree g_tree_ref(GTree tree) {
			//参照カウントを増やす。
			tree.ref_count++;
			//引数treeをそのまま返す。
			return tree;
		}
		//-----------------------------------------------------------------------------
		//Decrements the reference count of tree by one.
		//If the reference count drops to 0, all keys and values will be destroyed (if destroy functions were specified) and all memory allocated by tree will be released.
		//It is safe to call this function from any thread.				⇒当実装ではスレッドセーフではありません。複数のスレッドから参照する事は無いと思ったからです。実際の所g_tree_ref()/g_tree_unref()だけをスレッドセーフにしても他の関数がスレッドセーフでなければあまり意味は無いと思います。
		//Parameters
		//		tree			A GTree.
		public static void g_tree_unref(GTree tree) {
			//参照カウントを減らして、0になったら…
			if(--tree.ref_count == 0) {
				//ツリーを空にする。
				g_tree_clear(tree);
				//ツリーのメモリを開放する。
				/** no job **/
			}
		}
		//-----------------------------------------------------------------------------
		//Creates a new GTree with a comparison function that accepts user data.
		//See g_tree_new() for more details.
		//Parameters
		//		key_compare_func	qsort()-style comparison function.
		//		key_compare_data	Data to pass to comparison function.
		//Returns
		//		A newly allocated GTree.
		public static GTree g_tree_new_with_data(Func<object/*a*/,object/*b*/,object/*user_data*/,int> key_compare_func, object key_compare_data) {
			return g_tree_new_full(key_compare_func, key_compare_data, null, null);
		}
		//-----------------------------------------------------------------------------
		//Creates a new GTree like g_tree_new() and allows to specify functions to free the memory allocated for the key and value that get called when removing the entry from the GTree.
		//Parameters
		//		key_compare_func	qsort()-style comparison function.
		//		key_compare_data	Data to pass to comparison function.
		//		key_destroy_func	A function to free the memory allocated for the key used when removing the entry from the GTree or null if you don't want to supply such a function.
		//		value_destroy_func	A function to free the memory allocated for the value used when removing the entry from the GTree or null if you don't want to supply such a function.
		//Returns
		//		A newly allocated GTree.
		public static GTree g_tree_new_full(Func<object/*a*/,object/*b*/,object/*user_data*/,int> key_compare_func, object key_compare_data, Action<object/*data*/> key_destroy_func/*null可*/, Action<object/*data*/> value_destroy_func/*null可*/) {
			//ツリーのメモリを確保する。
			GTree tree = new GTree();
			//フィールドを初期化する。
			tree.key_compare_func   = key_compare_func;
			tree.key_destroy_func   = key_destroy_func   ?? delegate(object data) { };
			tree.value_destroy_func = value_destroy_func ?? delegate(object data) { };
			tree.key_compare_data   = key_compare_data;
			tree.ref_count          = 1;
			//作成したツリーを返す。
			return tree;
		}
		//-----------------------------------------------------------------------------
		//Inserts a key/value pair into a GTree.
		//If the given key already exists in the GTree its corresponding value is set to the new value.			←←←←┐
		//If you supplied a value_destroy_func when creating the GTree, the old value is freed using that function.		├要注意!! g_tree_insert()の場合は、既に同じキーのノードが有ったら、既存のキーが維持され、引数keyが指すキーが開放される。
		//If you supplied a key_destroy_func when creating the GTree, the passed key is freed using that function.	←←←←┘
		//The tree is automatically 'balanced' as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible.
		//Parameters
		//		tree			A GTree.
		//		key			The key to insert.
		//		value			The value corresponding to the key.
		public static void g_tree_insert(GTree tree, object key, object value) {
			g_tree_insert_subr1(tree, key, value, 0/*INSERT*/);
		}
		//-----------------------------------------------------------------------------
		//Inserts a new key and value into a GTree similar to g_tree_insert().
		//The difference is that if the key already exists in the GTree, it gets replaced by the new key.		←←←←┐
		//If you supplied a value_destroy_func when creating the GTree, the old value is freed using that function.		├要注意!! g_tree_replace()の場合は、既に同じキーのノードが有ったら、既存のキーが開放され、引数keyが指すキーが格納される。
		//If you supplied a key_destroy_func when creating the GTree, the old key is freed using that function.		←←←←┘
		//The tree is automatically 'balanced' as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible.
		//Parameters
		//		tree			A GTree
		//		key			The key to insert.
		//		value			The value corresponding to the key.
		public static void g_tree_replace(GTree tree, object key, object value) {
			g_tree_insert_subr1(tree, key, value, 1/*REPLACE*/);
		}
		//-----------------------------------------------------------------------------
		//Gets the number of nodes in a GTree.
		//Parameters
		//		tree			A GTree.
		//Returns
		//		The number of nodes in tree.
		public static int g_tree_nnodes(GTree tree) {
			return tree.nnodes;
		}
		//-----------------------------------------------------------------------------
		//Gets the height of a GTree.
		//If the GTree contains no nodes, the height is 0.
		//If the GTree contains only one root node the height is 1.
		//If the root node has children the height is 2, etc.
		//Parameters
		//		tree			A GTree.
		//Returns
		//		The height of tree.
		public static int g_tree_height(GTree tree) {
			return g_tree_node_height(tree.root);
		}
		//-----------------------------------------------------------------------------
		//Gets the value corresponding to the given key.
		//Since a GTree is automatically balanced as key/value pairs are added, key lookup is O(log n) (where n is the number of key/value pairs in the tree).
		//Parameters
		//		tree			A GTree.
		//		key			The key to look up.
		//Returns
		//		The value corresponding to the key, or null if the key was not found.
		public static object g_tree_lookup(GTree tree, object key) {
			object orig_key, value;
			return g_tree_lookup_extended(tree, key, out orig_key, out value) ? value : null;
		}
		//-----------------------------------------------------------------------------
		//Looks up a key in the GTree, returning the original key and the associated value.
		//This is useful if you need to free the memory allocated for the original key, for example before calling g_tree_remove().
		//Parameters
		//		tree			A GTree.
		//		lookup_key		The key to look up.
		//		orig_key		Returns the original key.			[optional][nullable]
		//		value			Returns the value associated with the key.	[optional][nullable]
		//Returns
		//		TRUE if the key was found in the GTree.
		public static bool g_tree_lookup_extended(GTree tree, object lookup_key, out object orig_key, out object value) {
			orig_key = value = null;	//エラー抑制
			GTreeNode t = tree.root;
			while(t != null) {
				//指定されたキーと、このノードのキーを比較する。
				int diff = tree.key_compare_func.Invoke(lookup_key, t.key, tree.key_compare_data);
				//指定されたキーが、このノードのキーよりも小さければ…
				if(diff < 0) {
					//左部分木へ進む。
					t = t.lst;	//null可
				//指定されたキーが、このノードのキーよりも大きければ…
				} else if(diff > 0) {
					//右部分木へ進む。
					t = t.rst;	//null可
				//指定されたキーと、このノードのキーが一致したら…
				} else {
					orig_key = t.key;
					value    = t.value;
					return true;
				}
			}
			return false;
		}
		//-----------------------------------------------------------------------------
		private static bool g_tree_foreach_subr(GTree tree, GTreeNode t/*null可*/, Func<object/*key*/,object/*value*/,object/*data*/,bool> func, object user_data) {
			if(t != null) {
				//左部分木に対して再帰する。
				if(g_tree_foreach_subr(tree, t.lst/*null可*/, func, user_data)) { return true; }
				//このノードに対して処理を行う。
				if(func.Invoke(t.key, t.value, user_data)) { return true; }
				//右部分木に対して再帰する。
				if(g_tree_foreach_subr(tree, t.rst/*null可*/, func, user_data)) { return true; }
			}
			return false;
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//Calls the given function for each of the key/value pairs in the GTree.
		//The function is passed the key and value of each pair, and the given data parameter.
		//The tree is traversed in sorted order.
		//The tree may not be modified while iterating over it (you can't add/remove items).
		//To remove all items matching a predicate, you need to add each item to a list in your GTraverseFunc as you walk over the tree, then walk the list and remove each item.
		//Parameters
		//		tree			A GTree.
		//		func			The function to call for each node visited.
		//					If this function returns TRUE, the traversal is stopped.
		//		user_data		User data to pass to the function.
		public static void g_tree_foreach(GTree tree, Func<object/*key*/,object/*value*/,object/*data*/,bool> func, object user_data) {
			g_tree_foreach_subr(tree, tree.root, func, user_data);
		}
		//-----------------------------------------------------------------------------
		//Searches a GTree using search_func.
		//The search_func is called with a pointer to the key of a key/value pair in the tree, and the passed in user_data.
		//If search_func returns 0 for a key/value pair, then the corresponding value is returned as the result of g_tree_search().
		//If search_func returns -1, searching will proceed among the key/value pairs that have a smaller key; if search_func returns 1, searching will proceed among the key/value pairs that have a larger key.
		//Parameters
		//		tree			A GTree.
		//		search_func		A function used to search the GTree.
		//		user_data		The data passed as the second argument to search_func.
		//Returns
		//		The value corresponding to the found key, or null if the key was not found.
		//[note]
		//		- g_tree_new()で指定したkey_compare_func関数を使わずに、別の検索関数search_funcを使ってノードを検索する関数です。
		//		  どのような目的で、この関数が定義されているのかが、良く判りません。
		//		  実際のアプリケーションで、この関数を使う事は、多分無いと思います。
		public static object g_tree_search(GTree tree, Func<object/*a*/,object/*b*/,int> search_func, object user_data) {
			GTreeNode t = tree.root;
			while(t != null) {
				//ノードのキーと、引数user_dataを、指定された関数に引き渡す。
				// - key_compare_func()とは、引数順序が直観と逆である事に注意せよ。
				//   また、戻り値と進む方向も直観と逆である(ような気がする)事に注意せよ。
				int diff = search_func.Invoke(t.key, user_data);
				//指定された関数の戻り値がマイナスならば…
				if(diff < 0) {
					//左部分木へ進む。
					t = t.lst;
				//指定された関数の戻り値がプラスならば…
				} else if(diff > 0) {
					//右部分木へ進む。
					t = t.rst;
				//指定された関数の戻り値がゼロならば…
				} else {
					return t.value;
				}
			}
			return null;
		}
		//-----------------------------------------------------------------------------
		//Removes a key/value pair from a GTree.
		//If the GTree was created using g_tree_new_full(), the key and value are freed using the supplied destroy functions, otherwise you have to make sure that any dynamically allocated values are freed yourself.
		//If the key does not exist in the GTree, the function does nothing.
		//Parameters
		//		tree			A GTree.
		//		key			The key to remove.
		//Returns
		//		TRUE if the key was found.
		public static bool g_tree_remove(GTree tree, object key) {
			return g_tree_remove_subr1(tree, key, 2/*REMOVE*/);
		}
		//-----------------------------------------------------------------------------
		//Removes a key and its associated value from a GTree without calling the key and value destroy functions.
		//If the key does not exist in the GTree, the function does nothing.
		//Parameters
		//		tree			A GTree.
		//		key			The key to remove.
		//Returns
		//		TRUE if the key was found.
		public static bool g_tree_steal(GTree tree, object key) {
			return g_tree_remove_subr1(tree, key, 3/*STEAL*/);
		}
		//-----------------------------------------------------------------------------
		//Removes all keys and values from the GTree and decreases its reference count by one.
		//If keys and/or values are dynamically allocated, you should either free them first or create the GTree using g_tree_new_full().
		//In the latter case the destroy functions you supplied will be called on all keys and values before destroying the GTree.
		//Parameters
		//		tree			A GTree.
		public static void g_tree_destroy(GTree tree) {
			//ツリーを空にする。
			g_tree_clear(tree);
			//参照カウントを減らす。
			g_tree_unref(tree);
		}
		//*****************************************************************************
		//	独自拡張
		//*****************************************************************************
		//【C#版特有のコメント】C言語版のGTreeIteratorNP構造体は代入でコピー出来ますが、C#版のGTreeIteratorNP構造体は代入でコピー出来ません。stackフィールドが参照だから浅いコピーになってしまうからです。GTreeIteratorNP構造体をコピーするケースは余り無いと思いますが、もしコピーする必要が生じた場合は注意して下さい。
		public struct GTreeIteratorNP {
			public Stack<GTreeNode>		stack;		//スタック	ノードを辿った経路を格納する。
		}
		//-----------------------------------------------------------------------------
		private static void g_tree_push(ref GTreeIteratorNP iter, GTreeNode t) {
			//nullポインタをプッシュする事は出来ない。
			if(t == null) { throw new ApplicationException(); }
			//スタックにノードをプッシュする。
			iter.stack.Push(t);
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		private static GTreeNode g_tree_pop(ref GTreeIteratorNP iter) {
			GTreeNode t;
			//スタックが空ならば、nullポインタを返す。
			if(iter.stack.Count == 0) { return null; }
			//スタックからノードをポップする。
			t = iter.stack.Pop();
			//nullポインタではないはずである。
			if(t == null) { throw new ApplicationException(); }
			//スタックからポップしたノードを返す。
			return t;
		}
		/*--------------------------------------------------------------------------*/
		public static bool g_tree_first_np(GTree tree, out GTreeIteratorNP iter, out object _key, out object _value) {
			//スタックを空にしておく。
			iter.stack = new Stack<GTreeNode>();
			//最初のノードを取得する。
			return g_tree_next_np(tree, ref iter, out _key, out _value);
		}
		//-----------------------------------------------------------------------------
		//□2016/07/05メモ
		//│この関数のアルゴリズムは、(自画自賛ですが)、かなりいい感じだと思います。
		//│普通に作ると、スタックの各要素に、'左を再帰中','そのノードの値を返した','右を再帰中'の状態を覚えておくための変数が必要になるのですが、
		//│スタック上の'現在のノード'と'前回のノード'を比較することで状態を判断するようにして、上記の状態を覚えておくための変数を不要にしました。
		//│そのために、やや理解しづらいコードになっていますが、処理の流れを追いかけて読めば、理解出来ると思います。(もし自分でも忘れてしまった場合はそうやって思い出そう…)
		//│あと、終端に到達したイテレータに対して、再度g_tree_next_np()が呼び出された場合に、0を返し続けるようにするために、ダミーノードをプッシュするのも工夫した点です。
		public static bool g_tree_next_np(GTree tree, ref GTreeIteratorNP iter, out object _key, out object _value) {
			_key = _value = null;	//エラー抑制
			GTreeNode t, u;
			//スタックからノードをポップして、前回のノード(t)と見なす。
			t = g_tree_pop(ref iter);	//null可
			//スタックからノードをポップ出来なければ(=スタックが空だったならば)…
			if(t == null) {
				//ツリーのルートノードを取得して、現在のノード(u)と見なす。
				u = tree.root;	//null可
				//ツリーのルートノード(u)が有れば…
				if(u != null) {
					//ツリーのルートノード(u)から、最大キーのノードを取得して、現在のノード(u)と見なす。
					for(;;) {
						g_tree_push(ref iter, u);	//ノードを辿った経路を格納する。
						if(u.lst == null) { break; }
						u = u.lst;
					}
				}
			//スタックからノードをポップ出来たら(=スタックが空でなかったならば)…
			} else {
				//前回のノード(t)の右部分木を取得して、現在のノード(u)と見なす。
				u = t.rst;	//null可
				//前回のノードの右部分木(u)が有れば…
				if(u != null) {
					//前回のノード(t)を、再度、スタックにプッシュする。
					g_tree_push(ref iter, t);
					//前回のノードの右部分木(u)から、最大キーのノードを取得して、現在のノード(u)と見なす。
					for(;;) {
						g_tree_push(ref iter, u);	//ノードを辿った経路を格納する。
						if(u.lst == null) { break; }
						u = u.lst;
					}
				//前回のノードの右部分木(u)が無ければ…
				} else {
					//以下の処理を繰り返す。
					for(;;) {
						//スタックから親ノードをポップして、現在のノード(u)と見なす。
						u = g_tree_pop(ref iter);
						//スタックから親ノードをポップ出来なければ…
						if(u == null) {
							//右部分木が無いダミーノードを、スタックにプッシュする。
							// - 終端に到達したイテレータに対して、再度g_tree_next_np()が呼び出された場合に、0を返し続けるようにするためです。
							GTreeNode dummy = new GTreeNode();	//dummy.rst=null
							g_tree_push(ref iter, dummy);
							//ループを抜けて、0を返す。
							break;
						}
						//前回のノード(t)が、現在ノード(u)の左部分木ならば…
						if(t == u.lst) {
							//現在のノード(u)を、再度、スタックにプッシュする。
							g_tree_push(ref iter, u);
							//ループを抜けて、現在のノード(u)のキーと値を返す。
							break;
						}
						//前回のノード(t)が、現在ノード(u)の右部分木である事を確認する。
						if(t != u.rst) { throw new ApplicationException(); }
						//現在のノード(u)を、前回のノード(t)と見なして、処理を繰り返す。
						t = u;
					}
				}
			}
			//現在のノードが有れば…
			if(u != null) {
				//現在のノードのキーと値を格納する。
				_key   = u.key;
				_value = u.value;
			}
			//現在のノードが有れば0以外の値、現在のノードが無ければ0を返す。
			return u != null;
		}
	}
}
