/*
 *	gtree.h
 *
 *	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と終端を区別出来なくなるからです。
 */
#ifndef __GTREE_H__
#define __GTREE_H__
#ifdef __cplusplus
extern "C" {
#endif//__cplusplus
/*****************************************************************************
 *	GTree
 *****************************************************************************/
typedef struct _GTree GTree;	//The GTree struct is an opaque data structure representing a balanced binary tree. It should be accessed only by using the following functions.
/*****************************************************************************
 *	グローバル関数
 *****************************************************************************/
GTree* g_tree_new(int (*key_compare_func)(const void* a, const void* b));
GTree* g_tree_ref(GTree* tree);
void g_tree_unref(GTree* tree);
GTree* g_tree_new_with_data(int (*key_compare_func)(const void* a, const void* b, void* user_data), void* key_compare_data);
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));
void g_tree_insert(GTree* tree, void* key, void* value);
void g_tree_replace(GTree* tree, void* key, void* value);
int g_tree_nnodes(GTree* tree);
int g_tree_height(GTree* tree);
void* g_tree_lookup(GTree* tree, const void* key);
int g_tree_lookup_extended(GTree* tree, const void* lookup_key, void** orig_key/*NULL可*/, void** value/*NULL可*/);
void g_tree_foreach(GTree* tree, int (*func)(void* key, void* value, void* data), void* user_data);
void* g_tree_search(GTree* tree, int (*search_func)(const void* a, const void* b), const void* user_data);
int g_tree_remove(GTree* tree, const void* key);
int g_tree_steal(GTree* tree, const void* key);
void g_tree_destroy(GTree* tree);
/*****************************************************************************
 *	独自拡張
 *****************************************************************************/
typedef struct _GTreeIteratorNP {
	int			depth;			//スタックの深さ	stack[0〜(depth-1)]に有効なノードが格納されている。
	struct _GTreeNode*	stack[31/*調整可*/];	//スタック		ノードを辿った経路を格納する。				スタックサイズは現状の31で十分だと思います。一般的にAVL木は完全並行木の1.5倍程度の高さに収まるので、2^(31/1.5)=約100万要素まで対応出来るからです。
} GTreeIteratorNP;
/*--------------------------------------------------------------------------*/
int g_tree_first_np(GTree* tree, GTreeIteratorNP* iter, void** _key/*NULL可*/, void** _value/*NULL可*/);
int g_tree_next_np(GTree* tree, GTreeIteratorNP* iter, void** _key/*NULL可*/, void** _value/*NULL可*/);
#ifdef __cplusplus
}//extern "C"
#endif//__cplusplus
#endif//__GTREE_H__
