/*
 *	gtree.c
 *
 *	Balanced Binary Trees - a sorted collection of key/value pairs optimized for searching and traversing in order
 *
 *	* Mon Jul 04 21:02:51 JST 2016 Naoyuki Sawa
 *	- 1st リリース。
 *	- GLibのBalanced Binary Trees(https://developer.gnome.org/glib/stable/glib-Balanced-Binary-Trees.html)を参考にしました。
 *	  関数仕様はGLib版と同じですが、実装は、GLib版のソースではなく、下記のサイトのソースを参考にして作成しました。
 *	  □参考資料
 *	  │「OK おじさんのホームページ」(http://www.moon.sannet.ne.jp/okahisa/)さんの、「AVL Tree by Java -- これで分かったAVL木」(http://www.moon.sannet.ne.jp/okahisa/avl-tree/avl-tree.html)の記事
 *	  │⇒/clip/keep/AVL木参考資料.7zに保存しておきました。
 *	  GLibのソースではなく、上記のサイトのソースを参考にした理由は、GLibのソースよりも、上記のサイトのソースの方がコンパクトで判りやすかったからです。
 *	  尚、上記のサイトには、別の実装として「Java による再帰を使わないAVL木の実装」(http://www.moon.sannet.ne.jp/okahisa/avl-tree/iavl-tree.html)も載っているのですが、今回は、普通に再帰を使う版を参考にさせて頂きました。
 *	  再帰を使わない版は、AVL木のノードの型に親ノードへのリンクを追加する必要が有り、個々のノードのサイズが増えて、全体としてヒープメモリ使用量が多くなる問題が有るからです。
 *	  今回は、速度よりも、省メモリを優先する事にしました。(ただし、普通に再帰を使う版の方が、再帰呼び出しの分、スタックフレームのメモリ消費量は多いです。)
 *	- 今回の実装は、ほぼ、上記のサイトのソースと同じですが、一点、意図的に削除した点が有ります。
 *	  それは、補助情報の型の、changeフラグを廃止した点です。
 *	  上記のサイトのソースでは、バランスを回復する処理をどこまで遡って継続するかを判断するために、補助情報の型のchangeフラグを使用しています。
 *	  しかし、それは単に高速化だけのためであり、動作上は、ルートノードまで遡ってバランスを回復する処理を行っても、結果は同じになります。
 *	  その余分な処理を行ったとしても、g_tree_node_balanceL(),又は,g_tree_node_balanceR()の先頭でバイアスを判定した時点で、回転が不要である事は判るので、実際に回転処理は行いません。
 *	  つまり、changeフラグを廃止した場合のオーバーヘッドは、余分なg_tree_node_bias()が、一階層につき一回発生するだけの違いです。
 *	  g_tree_node_bias()は十分高速なので、さほど大きなオーバーヘッドではありません。
 *	  また、階層の数はおおよそ log2(ノード数) ですから、仮に100万ノード有ったとしてもせいぜい二十数階層程度です。
 *	  まとめますと、changeフラグを廃止した事によるオーバーヘッドは、ノードの追加や削除を行う度に、g_tree_node_bias()を(多くても)二十数回実行する程度のオーバーヘッドに過ぎず、十分許容できます。
 *	  むしろ、changeフラグを適切にセット・クリアする処理の方が、直感的に判り辛い点が有りましたので、changeフラグを廃止するのは理に適っていると思います。
 *	  以上の理由により、当実装では、補助情報の型の、changeフラグを廃止しました。
 *	  尚、アプリケーションの観点からは、この点について気にする必要は有りません。
 *	- 実際の所、gtreeは、ght_hash_tableに対して、特にメリットは有りません。
 *	  下記のプログラムで速度を計測した所、gtreeはght_hash_tableに対して約4倍遅いです。
 *	  changeフラグを廃止した事によって極端に遅くなっている訳ではないので、元々、AVL木とハッシュテーブルには、これぐらいの速度差が有るのだと思います。
 *	  │//■速度比較プログラム
 *	  │void test1();  //前方参照
 *	  │void test2();  //前方参照
 *	  │int compar(const void* _x, const void* _y);  //前方参照
 *	  │int app_main(int argc, char* argv[]) {
 *	  │  test1();  // 344[ms]
 *	  │  test2();  //1422[ms]
 *	  │  return 0;
 *	  │}
 *	  │void test1() {  //ght_hash_table版
 *	  │  ght_hash_table_t* ht = ght_create(0);
 *	  │  int t, i, r;
 *	  │  ght_set_rehash(ht, 1);
 *	  │  seed = 0;
 *	  │  t = GetTickCount();
 *	  │  for(i = 0; i < 1000000; i++) {
 *	  │    r = RND16(seed) + 1;
 *	  │    ght_insert(ht, (void*)r, sizeof r, &r);
 *	  │    r = RND16(seed) + 1;
 *	  │    ght_remove(ht, sizeof r, &r);
 *	  │    r = RND16(seed) + 1;
 *	  │    ght_get(ht, sizeof r, &r);
 *	  │  }
 *	  │  t = GetTickCount() - t;
 *	  │  ght_finalize(ht);
 *	  │  printf("ght_hash_table: %d\n", t);
 *	  │}
 *	  │void test2() {  //GTree版
 *	  │  GTree* tree = g_tree_new(compar);
 *	  │  int t, i, r;
 *	  │  seed = 0;
 *	  │  t = GetTickCount();
 *	  │  for(i = 0; i < 1000000; i++) {
 *	  │    r = RND16(seed) + 1;
 *	  │    g_tree_insert(tree, (void*)r, (void*)r);
 *	  │    r = RND16(seed) + 1;
 *	  │    g_tree_remove(tree, (void*)r);
 *	  │    r = RND16(seed) + 1;
 *	  │    g_tree_lookup(tree, (void*)r);
 *	  │  }
 *	  │  t = GetTickCount() - t;
 *	  │  g_tree_unref(tree);
 *	  │  printf("GTree: %d\n", t);
 *	  │}
 *	  │int compar(const void* _x, const void* _y) {
 *	  │  int x = (int)_x;
 *	  │  int y = (int)_y;
 *	  │  if(x < y) { return -1; }
 *	  │  if(x > y) { return  1; }
 *	  │  return 0;
 *	  │}
 *	  消費メモリ量については厳密に検証していませんが、ほとんど差は無いのではないかと思います。
 *	  従って、単に辞書として使用するだけならば、敢えてgtreeを使う意味は無く、ght_hash_tableを使う方が良いです。
 *	  ght_hash_tableよりもgtreeが優れている点としては、下記の点が挙げられます。
 *	  ○負荷が平均的である。ght_hash_tableは普段は高速だがリハッシュが発生した時に瞬間的に大きな負荷が発生する。gtreeは低速だが瞬間的に極端に大きな負荷が発生する事は無い。
 *	  ○自動的にソートされる。ght_hash_tableはソートが必要な場合イテレーションの前に明示的にソートする必要が有る。gtreeは単にイテレーションするだけで常にソートされている。
 *	* Tue Jul 05 22:24:53 JST 2016 Naoyuki Sawa
 *	- g_tree_first_np(),g_tree_next_np()を追加しました。
 *	  これらの関数は、オリジナルのGLib版には無い、独自拡張です。
 *	  関数名サフィックス'np'は、'not portable'の略です。
 *	  Pthreadsが、移植性の無い関数にサフィックス'np'を付与している流儀に倣いました。
 *	  これらの関数を追加した理由は、以下の通りです。
 *	- オリジナルのGLib版でのイテレーション関数は、g_tree_foreach()です。
 *	  g_tree_foreach()は、コールバック型のイテレーション関数です。
 *	  コールバック型のイテレーション関数は、実際のアプリケーションでは使い辛い事が多く、first/next型のイテレーション関数が欲しいと思いました。
 *	  そこで、独自拡張として、first/next型のイテレーション関数g_tree_first_np(),g_tree_next_np()を追加する事にしました。
 *	- g_tree_first_np(),g_tree_next_np()の使い方は、ght_first(),ght_next()等とほぼ同じです。
 *	  ただし、ght_first(),ght_next()は'値'が戻り値であるのに対し、g_tree_first_np(),g_tree_next_np()の戻り値はフラグである事に注意して下さい。
 *	  そうした理由は、ght_hash_tableではNULLは'値'として不可であるのに対し、gtreeではNULLの値も有り得るため、もし'値'を戻り値とするとNULLと終端を区別出来なくなるからです。
 *	* Sun Sep 04 21:41:17 JST 2016 Naoyuki Sawa
 *	- g_tree_next_np()に、64ビット対応のための変更を行いました。
 *	  詳細は、g_tree_next_np()内のコメントを参照して下さい。
 */
#include "clip.h"
/*****************************************************************************
 *	GTree
 *****************************************************************************/
/*****************************************************************************
 *	構造体
 *****************************************************************************/
/*typedef*/ struct _GTree {			//ツリーの型
	struct _GTreeNode*	root;		//ルートノード
	int			(*key_compare_func)(const void* a, const void* b, void* user_data);	//アプリケーション定義のキー比較関数
	void*			key_compare_data;							//アプリケーション定義のキー比較関数へ引き渡す任意のデータ
	void			(*key_destroy_func)(void* data);	//アプリケーション定義のキー開放関数
	void			(*value_destroy_func)(void* data);	//アプリケーション定義の値開放関数
	int			nnodes;		//ノード数
	int			ref_count;	//参照カウント
} /*GTree*/;
/*--------------------------------------------------------------------------*/
typedef struct _GTreeNode {			//ノードの型
	int			height;		//この部分木の高さ
	void*			key;		//このノードのキー
	void*			value;		//このノードの値
	struct _GTreeNode*	lst;		//左部分木
	struct _GTreeNode*	rst;		//右部分木
} GTreeNode;
/*--------------------------------------------------------------------------*/
typedef struct _GTreeTrio {			//補助情報の型
	GTree*			tree;		//指定されたツリー				[in]
	void*			key;		//指定されたキー,又は,最大キー			g_tree_insert_subr*()から使用する時は[in]	g_tree_remove_subr*()から使用する時は[in/out]
	void*			value;		//指定された値,又は,最大キーの値		g_tree_insert_subr*()から使用する時は[in]	g_tree_remove_subr*()から使用する時は[out]
	int			mode;		//0=INSERT,1=REPLACE,2=REMOVE,3=STEAL		[in]
	int			found;		//削除するノードが見つかった事を示すフラグ	g_tree_insert_subr*()からは使用しない。		g_tree_remove_subr*()から使用する時は[out]
} GTreeTrio;
/*****************************************************************************
 *	ローカル関数
 *****************************************************************************/
//ノードを作成する。
static GTreeNode* g_tree_node_new(void* key, void* value) {
	//ノードのメモリを確保する。
	GTreeNode* t = calloc(1, sizeof(GTreeNode));
	if(!t) { DIE(); }	//メモリ不足
	//フィールドを初期化する。
	t->height = 1;
	t->key    = key;
	t->value  = value;
	//作成したノードを返す。
	return t;
}
/*--------------------------------------------------------------------------*/
//部分木の高さを返す。
static int g_tree_node_height(GTreeNode* t/*NULL可*/) {
	return t ? t->height : 0;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//左右の部分木の高さの差を返す。左が高いと正、右が高いと負。
static int g_tree_node_bias(GTreeNode* t) {
	return g_tree_node_height(t->lst/*NULL可*/) - g_tree_node_height(t->rst/*NULL可*/);
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//左右の部分木の高さから、その木の高さを計算して設定する。
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)   
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)
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)        	                
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)  	                
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);
#ifdef  _DEBUG
	if((bias > 2) || (bias < -1)) { DIE(); }		//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#endif//_DEBUG
	if(bias == 2) {
		bias = g_tree_node_bias(t->lst);
#ifdef  _DEBUG
		if((bias > 1) || (bias < -1)) { DIE(); }	//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#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木の修正
static GTreeNode* g_tree_node_balanceR(GTreeTrio* aux, GTreeNode* t) {
	int bias = g_tree_node_bias(t);
#ifdef  _DEBUG
	if((bias < -2) || (bias > 1)) { DIE(); }		//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#endif//_DEBUG
	if(bias == -2) {
		bias = g_tree_node_bias(t->rst);
#ifdef  _DEBUG
		if((bias < -1) || (bias > 1)) { DIE(); }	//バランスが限界以上に崩れている。ここで停止したら当モジュールのバグです。
#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:右部分木への挿入)
static GTreeNode* g_tree_node_balanceLi(GTreeTrio* aux, GTreeNode* t) { return g_tree_node_balanceL(aux, t); }
static GTreeNode* g_tree_node_balanceRi(GTreeTrio* aux, GTreeNode* t) { return g_tree_node_balanceR(aux, t); }
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//削除時の修正(balanceLd:左部分木での削除,balanceRd:右部分木での削除)
static GTreeNode* g_tree_node_balanceLd(GTreeTrio* aux, GTreeNode* t) { return g_tree_node_balanceR(aux, t); }
static GTreeNode* g_tree_node_balanceRd(GTreeTrio* aux, GTreeNode* t) { return g_tree_node_balanceL(aux, t); }
/*--------------------------------------------------------------------------*/
//部分木tにキーkeyで値valueを挿入する。auxは補助情報。
static GTreeNode* g_tree_insert_subr2(GTreeTrio* aux, GTreeNode* t/*NULL可*/) {
	//部分木tが指定されていたら…
	if(t) {
		//指定されたキーと、このノードのキーを比較する。
		int diff = (*aux->tree->key_compare_func)(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:DIE();
			case 0/*INSERT*/:	//g_tree_insert()から呼び出された場合
				//指定されたキーを開放する。	←←←←要注意!! g_tree_insert()の場合は、既に同じキーのノードが有ったら、既存のキーが維持され、引数keyが指すキーが開放される。
				(*aux->tree->key_destroy_func)(aux->key);
				break;
			case 1/*REPLACE*/:	//g_tree_replace()から呼び出された場合
				//既存のキーを解放する。	←←←←要注意!! g_tree_replace()の場合は、既に同じキーのノードが有ったら、既存のキーが開放され、引数keyが指すキーが格納される。
				(*aux->tree->key_destroy_func)(t->key);
				//指定されたキーを格納する。
				t->key = aux->key;
				break;
			}
			//既存の値を解放する。
			(*aux->tree->value_destroy_func)(t->value);
			//指定された値を格納する。
			t->value = aux->value;
		}
	//部分木tが指定されていなければ…
	} else {
		//新しいノードを作成する。
		t = g_tree_node_new(aux->key, aux->value);
		//ノード数を増やす。
		aux->tree->nnodes++;
#ifdef  _DEBUG
		if(aux->tree->nnodes <= 0) { DIE(); }	//ここで停止したら当モジュールのバグです。
#endif//_DEBUG
	}
	return t;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//tree->rootにキーkeyで値valueを挿入する。
static void g_tree_insert_subr1(GTree* tree, void* key, void* value, int mode/*0=INSERT,1=REPLACE*/) {
	GTreeTrio aux = { tree, key, value, mode };
	tree->root = g_tree_insert_subr2(&aux, tree->root);
}
/*--------------------------------------------------------------------------*/
//部分木tの最大キーのノードを削除する。
//戻り値は削除により修正された部分木。
//部分木tのキーの最大値とその値をauxに返す。
static GTreeNode* g_tree_remove_subr3(GTreeTrio* aux, GTreeNode* t) {
	//このノードに、右部分木が有れば…
	if(t->rst) {
		//右部分木に対して再帰する。
		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--;
#ifdef  _DEBUG
		if(aux->tree->nnodes < 0) { DIE(); }	//ここで停止したら当モジュールのバグです。
#endif//_DEBUG
		//このノードのメモリを開放する。
		free(t);
		//左部分木を昇格させる。
		t = u;
	}
	return t;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//部分木tからキーkeyのノードを削除する。auxは補助情報。
static GTreeNode* g_tree_remove_subr2(GTreeTrio* aux, GTreeNode* t/*NULL可*/) {
	//部分木tが指定されていたら…
	if(t) {
		//指定されたキーと、このノードのキーを比較する。
		int diff = (*aux->tree->key_compare_func)(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) {
				//呼び出し元の関数によって…
				switch(aux->mode) {
				default:DIE();
				case 2/*REMOVE*/:	//g_tree_remove()から呼び出された場合
					//既存のキーを解放する。
					(*aux->tree->key_destroy_func)(t->key);
					//既存の値を解放する。
					(*aux->tree->value_destroy_func)(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:DIE();
				case 2/*REMOVE*/:	//g_tree_remove()から呼び出された場合
					//既存のキーを解放する。
					(*aux->tree->key_destroy_func)(t->key);
					//既存の値を解放する。
					(*aux->tree->value_destroy_func)(t->value);
					break;
				case 3/*STEAL*/:	//g_tree_steal()から呼び出された場合
					/** no job **/
					break;
				}
				//ノード数を減らす。
				aux->tree->nnodes--;
#ifdef  _DEBUG
				if(aux->tree->nnodes < 0) { DIE(); }	//ここで停止したら当モジュールのバグです。
#endif//_DEBUG
				//このノードのメモリを開放する。
				free(t);
				//右部分木を昇格させる。
				t = u;
			}
			//削除するノードが見つかった事を示すフラグをセットする。
			aux->found = 1;
		}
	//部分木tが指定されていなければ…
	} else {
		/** no job **/
	}
	return t;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//tree->rootからキーkeyのノードを削除する。
static int g_tree_remove_subr1(GTree* tree, void* key, int mode/*2=REMOVE,3=STEAL*/) {
	GTreeTrio aux = { tree, key, NULL/*value*/, mode };
	tree->root = g_tree_remove_subr2(&aux, tree->root);
	return aux.found;
}
/*--------------------------------------------------------------------------*/
//ツリーを空にする。
static void g_tree_clear(GTree* tree) {
	GTreeNode* t;
	while((t = tree->root)) {
		g_tree_remove(tree, t->key);
	}
#ifdef  _DEBUG
	if(tree->nnodes) { DIE(); }	//ここで停止したら当モジュールのバグです。
#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.
GTree* g_tree_new(int (*key_compare_func)(const void* a, const void* b)) {
	return g_tree_new_with_data((int (*)(const void*, const void*, void*))key_compare_func, 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.
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.
void g_tree_unref(GTree* tree) {
	//参照カウントを減らして、0になったら…
	if(!--tree->ref_count) {
		//ツリーを空にする。
		g_tree_clear(tree);
		//ツリーのメモリを開放する。
		free(tree);
	}
}
/*--------------------------------------------------------------------------*/
//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.
GTree* g_tree_new_with_data(int (*key_compare_func)(const void* a, const void* b, void* user_data), void* key_compare_data) {
	return g_tree_new_full(key_compare_func, key_compare_data, NULL, NULL);
}
/*--------------------------------------------------------------------------*/
static void g_tree_dummy_destroy_func(void* data) {
	/** no job **/
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//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.
GTree* g_tree_new_full(int (*key_compare_func)(const void* a, const void* b, void* user_data), void* key_compare_data, void (*key_destroy_func/*NULL可*/)(void* data), void (*value_destroy_func/*NULL可*/)(void* data)) {
	//ツリーのメモリを確保する。
	GTree* tree = calloc(1, sizeof(GTree));
	if(!tree) { DIE(); }	//メモリ不足
	//フィールドを初期化する。
	tree->key_compare_func   = key_compare_func;
	tree->key_destroy_func   = key_destroy_func   ? key_destroy_func   : g_tree_dummy_destroy_func;
	tree->value_destroy_func = value_destroy_func ? value_destroy_func : g_tree_dummy_destroy_func;
	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.
void g_tree_insert(GTree* tree, void* key, void* 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.
void g_tree_replace(GTree* tree, void* key, void* 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.
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.
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.
void* g_tree_lookup(GTree* tree, const void* key) {
	void* value;
	return g_tree_lookup_extended(tree, key, NULL, &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.
int g_tree_lookup_extended(GTree* tree, const void* lookup_key, void** orig_key/*NULL可*/, void** value/*NULL可*/) {
	GTreeNode* t = tree->root;
	while(t) {
		//指定されたキーと、このノードのキーを比較する。
		int diff = (*tree->key_compare_func)(lookup_key, t->key, tree->key_compare_data);
		//指定されたキーが、このノードのキーよりも小さければ…
		if(diff < 0) {
			//左部分木へ進む。
			t = t->lst;	//NULL可
		//指定されたキーが、このノードのキーよりも大きければ…
		} else if(diff > 0) {
			//右部分木へ進む。
			t = t->rst;	//NULL可
		//指定されたキーと、このノードのキーが一致したら…
		} else {
			if(orig_key) { *orig_key = t->key;   }
			if(value   ) { *value    = t->value; }
			return 1;
		}
	}
	return 0;
}
/*--------------------------------------------------------------------------*/
static int g_tree_foreach_subr(GTree* tree, GTreeNode* t/*NULL可*/, int (*func)(void* key, void* value, void* data), void* user_data) {
	if(t) {
		//左部分木に対して再帰する。
		if(g_tree_foreach_subr(tree, t->lst/*NULL可*/, func, user_data)) { return 1; }
		//このノードに対して処理を行う。
		if((*func)(t->key, t->value, user_data)) { return 1; }
		//右部分木に対して再帰する。
		if(g_tree_foreach_subr(tree, t->rst/*NULL可*/, func, user_data)) { return 1; }
	}
	return 0;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//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.
void g_tree_foreach(GTree* tree, int (*func)(void* key, void* value, void* data), void* 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を使ってノードを検索する関数です。
//		  どのような目的で、この関数が定義されているのかが、良く判りません。
//		  実際のアプリケーションで、この関数を使う事は、多分無いと思います。
void* g_tree_search(GTree* tree, int (*search_func)(const void* a, const void* b), const void* user_data) {
	GTreeNode* t = tree->root;
	while(t) {
		//ノードのキーと、引数user_dataを、指定された関数に引き渡す。
		// - key_compare_func()とは、引数順序が直観と逆である事に注意せよ。
		//   また、戻り値と進む方向も直観と逆である(ような気がする)事に注意せよ。
		int diff = (*search_func)(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.
int g_tree_remove(GTree* tree, const void* key) {
	return g_tree_remove_subr1(tree, (void*)key, 2/*REMOVE*/);	//キャストはconst警告抑制のため。
}
/*--------------------------------------------------------------------------*/
//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.
int g_tree_steal(GTree* tree, const void* key) {
	return g_tree_remove_subr1(tree, (void*)key, 3/*STEAL*/);	//キャストはconst警告抑制のため。
}
/*--------------------------------------------------------------------------*/
//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.
void g_tree_destroy(GTree* tree) {
	//ツリーを空にする。
	g_tree_clear(tree);
	//参照カウントを減らす。
	g_tree_unref(tree);
}
/*****************************************************************************
 *	独自拡張
 *****************************************************************************/
static void g_tree_push(GTreeIteratorNP* iter, GTreeNode* t) {
	//NULLポインタをプッシュする事は出来ない。
	if(!t) { DIE(); }
	//スタックの深さが範囲内で有る事を確認する。
	if((unsigned)iter->depth >= (unsigned)ARRAY_SIZE(iter->stack)) { DIE(); }
	//ノードを格納する。
	iter->stack[iter->depth] = t;
	//スタックの深さを増やす。
	iter->depth++;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static GTreeNode* g_tree_pop(GTreeIteratorNP* iter) {
	GTreeNode* t;
	//スタックが空ならば、NULLポインタを返す。
	if(!iter->depth) { return NULL; }
	//スタックの深さを減らす。
	iter->depth--;
	//スタックの深さが範囲内で有る事を確認する。
	if((unsigned)iter->depth >= (unsigned)ARRAY_SIZE(iter->stack)) { DIE(); }
	//スタックからノードをポップする。
	t = iter->stack[iter->depth];
	//NULLポインタではないはずである。
	if(!t) { DIE(); }
	//スタックからポップしたノードを返す。
	return t;
}
/*--------------------------------------------------------------------------*/
int g_tree_first_np(GTree* tree, GTreeIteratorNP* iter, void** _key/*NULL可*/, void** _value/*NULL可*/) {
	//スタックを空にしておく。
	iter->depth = 0;
	//最初のノードを取得する。
	return g_tree_next_np(tree, iter, _key, _value);
}
/*--------------------------------------------------------------------------*/
//□2016/07/05メモ
//│この関数のアルゴリズムは、(自画自賛ですが)、かなりいい感じだと思います。
//│普通に作ると、スタックの各要素に、'左を再帰中','そのノードの値を返した','右を再帰中'の状態を覚えておくための変数が必要になるのですが、
//│スタック上の'現在のノード'と'前回のノード'を比較することで状態を判断するようにして、上記の状態を覚えておくための変数を不要にしました。
//│そのために、やや理解しづらいコードになっていますが、処理の流れを追いかけて読めば、理解出来ると思います。(もし自分でも忘れてしまった場合はそうやって思い出そう…)
//│あと、終端に到達したイテレータに対して、再度g_tree_next_np()が呼び出された場合に、0を返し続けるようにするために、ダミーノードをプッシュするのも工夫した点です。
int g_tree_next_np(GTree* tree, GTreeIteratorNP* iter, void** _key/*NULL可*/, void** _value/*NULL可*/) {
	GTreeNode *t, *u;
	//スタックからノードをポップして、前回のノード(t)と見なす。
	t = g_tree_pop(iter);	//NULL可
	//スタックからノードをポップ出来なければ(=スタックが空だったならば)…
	if(!t) {
		//ツリーのルートノードを取得して、現在のノード(u)と見なす。
		u = tree->root;	//NULL可
		//ツリーのルートノード(u)が有れば…
		if(u) {
			//ツリーのルートノード(u)から、最大キーのノードを取得して、現在のノード(u)と見なす。
			for(;;) {
				g_tree_push(iter, u);	//ノードを辿った経路を格納する。
				if(!u->lst) { break; }
				u = u->lst;
			}
		}
	//スタックからノードをポップ出来たら(=スタックが空でなかったならば)…
	} else {
		//前回のノード(t)の右部分木を取得して、現在のノード(u)と見なす。
		u = t->rst;	//NULL可
		//前回のノードの右部分木(u)が有れば…
		if(u) {
			//前回のノード(t)を、再度、スタックにプッシュする。
			g_tree_push(iter, t);
			//前回のノードの右部分木(u)から、最大キーのノードを取得して、現在のノード(u)と見なす。
			for(;;) {
				g_tree_push(iter, u);	//ノードを辿った経路を格納する。
				if(!u->lst) { break; }
				u = u->lst;
			}
		//前回のノードの右部分木(u)が無ければ…
		} else {
			//以下の処理を繰り返す。
			for(;;) {
				//スタックから親ノードをポップして、現在のノード(u)と見なす。
				u = g_tree_pop(iter);
				//スタックから親ノードをポップ出来なければ…
				if(!u) {
					//右部分木が無いダミーノードを、スタックにプッシュする。
					// - 終端に到達したイテレータに対して、再度g_tree_next_np()が呼び出された場合に、0を返し続けるようにするためです。
					static const GTreeNode dummy;		//dummy.rst=NULL
					g_tree_push(iter, (void*)&dummy);	//キャストはconst警告抑制のため。
					//ループを抜けて、0を返す。
					break;
				}
				//前回のノード(t)が、現在ノード(u)の左部分木ならば…
				if(t == u->lst) {
					//現在のノード(u)を、再度、スタックにプッシュする。
					g_tree_push(iter, u);
					//ループを抜けて、現在のノード(u)のキーと値を返す。
					break;
				}
				//前回のノード(t)が、現在ノード(u)の右部分木である事を確認する。
				if(t != u->rst) { DIE(); }
				//現在のノード(u)を、前回のノード(t)と見なして、処理を繰り返す。
				t = u;
			}
		}
	}
	//現在のノードが有れば…
	if(u) {
		//現在のノードのキーと値を格納する。
		if(_key  ) { *_key   = u->key;   }
		if(_value) { *_value = u->value; }
	}
	//現在のノードが有れば0以外の値、現在のノードが無ければ0を返す。
//{{2016/09/04変更:g_tree_next_np()に、64ビット対応のための変更を行いました。
//	return (int)u;
//↓2016/09/04変更:g_tree_next_np()に、64ビット対応のための変更を行いました。
#ifndef _WIN64
	return (int)u;	//32ビットならば、ポインタを(int)にキャストするだけで良い。32ビットでも、下記の64ビットと同じ処理にしても構わないのだが、ポインタを(int)にキャストするだけの方が効率が良いコードが生成される(特にP/ECEの場合)ので、敢えて条件コンパイルで分ける事にした。
#else //_WIN64
	return !!u;	//64ビットならば、明示的にポインタがNULLでないかを、判定する必要が有る。なぜならば、ポインタを(int)にキャストすると、ポインタの上位32ビットが失われてしまい、万一、非NULLポインタの下位32ビットが偶然0だった場合に、間違った結果になってしまうからである。
#endif//_WIN64
//}}2016/09/04変更:g_tree_next_np()に、64ビット対応のための変更を行いました。
}
/*--------------------------------------------------------------------------*/
#if 0
//■テストプログラム
static int compar(const void* _x, const void* _y);	//前方参照
void test() {
	GTree* tree = g_tree_new(compar);
	GTreeIteratorNP iter;
	void *key, *value;
	g_tree_insert(tree, (void*)1, (void*)"One");
	g_tree_insert(tree, (void*)2, (void*)"Two");
	g_tree_insert(tree, (void*)3, (void*)"Three");
	g_tree_insert(tree, (void*)4, (void*)"Four");
	g_tree_insert(tree, (void*)5, (void*)"Five");
	g_tree_insert(tree, (void*)6, (void*)"Six");
	g_tree_insert(tree, (void*)7, (void*)"Seven");
	g_tree_insert(tree, (void*)8, (void*)"Eight");
	g_tree_insert(tree, (void*)9, (void*)"Nine");
	if(g_tree_first_np(tree, &iter, &key, &value)) {
		do {
			printf("%d %s\n", key, value);
			//□結果
			//│1 One
			//│2 Two
			//│3 Three
			//│4 Four
			//│5 Five
			//│6 Six
			//│7 Seven
			//│8 Eight
			//│9 Nine
		} while(g_tree_next_np(tree, &iter, &key, &value));
	}
	if(g_tree_next_np(tree, &iter, NULL, NULL)) { DIE(); }	//┐
	if(g_tree_next_np(tree, &iter, NULL, NULL)) { DIE(); }	//├終端に到達したイテレータに対して、再度g_tree_next_np()が呼び出しても、0が返され続ける。
	if(g_tree_next_np(tree, &iter, NULL, NULL)) { DIE(); }	//┘
	g_tree_unref(tree);
}
static int compar(const void* _x, const void* _y) {
	int x = (int)_x;
	int y = (int)_y;
	if(x < y) { return -1; }
	if(x > y) { return  1; }
	return 0;
}
#endif
