//
//	ght_hash_table.cs
//
//	Generic Hash Table (GHT)
//
//	CLiP - Common Library for P/ECE
//	Copyright (C) 2017 Naoyuki Sawa
//
//	* Sun Apr 16 22:06:49 JST 2017 Naoyuki Sawa
//	- 1st リリース。
//
using System;
namespace org.piece_me {
	public static partial class libclip {
		//*****************************************************************************
		//	構造体
		//*****************************************************************************
		public class ght_hash_entry_t {
			public readonly LIST_ENTRY			le_iterator;
			public readonly LIST_ENTRY			le_bucket;
			public object					p_entry_data;		//Entry data.
			public object					key_data;		//Key data.
			public ght_hash_entry_t() {			//┐
				le_iterator = new LIST_ENTRY(this);	//├【C#版特有】
				le_bucket   = new LIST_ENTRY(this);	//│
			}						//┘
		}
		//-----------------------------------------------------------------------------
		public struct ght_iterator_t {
			public LIST_ENTRY				le_next;		//The current entry.		//イテレータは次のノードを指しているので、イテレーションの中で当該ノードをght_remove()しても安全です。使用例はght_finalize()の実装を参照してください。
		}
		//-----------------------------------------------------------------------------
		public class ght_hash_table_t {
			public bool					b_rehash;		//Automatic rehashing status.
			public int					i_size;			//The current number of items in the table.
			public readonly LIST_ENTRY			le_iterator  = new LIST_ENTRY();
			public int					i_table_size { get { return le_bucket.Length; } }	//The number of buckets.
			public LIST_ENTRY[/*i_table_size*/]		le_bucket;
			public int					bucket_limit;		//The maximum number of items in each bucket. If limit is set to 0, bounded buckets are disabled.
			public Action<object/*data*/,object/*key*/>	fn_bucket_free;		//The function called when a bucket overflows.
		}
		//*****************************************************************************
		//	ローカル関数
		//*****************************************************************************
		private static int ght_get_hash_value(ght_hash_table_t p_ht, object p_key_data) {
			return (int)((uint)p_key_data.GetHashCode() % (uint)p_ht.i_table_size);
		}
		//-----------------------------------------------------------------------------
		//Search for an element in a bucket.
		private static ght_hash_entry_t ght_search_in_bucket(ght_hash_table_t p_ht, object p_key_data) {
			int l_key = ght_get_hash_value(p_ht, p_key_data);
			LIST_ENTRY list_head = p_ht.le_bucket[l_key];
			LIST_ENTRY list_entry = list_head.Flink;
			while(list_entry != list_head) {
				ght_hash_entry_t p_e = CONTAINING_RECORD<ght_hash_entry_t>(list_entry);
				if(p_e.key_data.Equals(p_key_data)) {
				    //	//このハッシュテーブルが、キャッシュとして動作中ならば…	//┐
				    //	if(p_ht.bucket_limit) {						//│このハッシュテーブルがキャッシュとして動作中か否かに関係無く、参照したエントリをこのバケットの先頭へ移動する事にした。
						//このエントリを、このバケットの先頭へ移動する。	//│キャッシュとして動作中でなくても、頻繁に参照するエントリの検索が早くなるという利点があるからです。
						RemoveEntryList(p_e.le_bucket);				//│尚、ght_remove()から呼び出された場合は無駄処理ですが、動作には影響有りません。
						InsertHeadList(list_head, p_e.le_bucket);		//│
				    //	}								//┘
					return p_e;
				}
				list_entry = list_entry.Flink;
			}
			return null;
		}
		//-----------------------------------------------------------------------------
		private static void ght_check_rehash(ght_hash_table_t p_ht) {
			if(p_ht.b_rehash) {
				//現在の要素数を取得する。ただし、要素数が(0)の場合は(1)として、以下の計算を行う。
				int i_size = p_ht.i_size;
				if(i_size == 0) { i_size = 1; }
				//現在のテーブルサイズが、要素数の半分未満,又は,二倍超過ならば、要素数に合わせる。
				if((p_ht.i_table_size < (i_size / 2)) ||
				   (p_ht.i_table_size > (i_size * 2))) { ght_rehash(p_ht, i_size); }
				//以上の処理によって、テーブルサイズが要素数の半分以上～二倍以下の範囲に追従する。
			}
		}
		//*****************************************************************************
		//	グローバル関数
		//*****************************************************************************
		//Create a new hash table.
		public static ght_hash_table_t ght_create(int i_table_size) {
			ght_hash_table_t p_ht;
			p_ht = new ght_hash_table_t();
			InitializeListHead(p_ht.le_iterator);
			ght_rehash(p_ht, i_table_size);
			return p_ht;
		}
		//-----------------------------------------------------------------------------
		//Get the number of items in the hash table.
		public static int ght_size(ght_hash_table_t p_ht) {
			return p_ht.i_size;
		}
		//-----------------------------------------------------------------------------
		//Get the size of the hash table.
		public static int ght_table_size(ght_hash_table_t p_ht) {
			return p_ht.i_table_size;
		}
		//-----------------------------------------------------------------------------
		//Insert an entry into the hash table.
		public static bool ght_insert(ght_hash_table_t p_ht, object p_entry_data, object p_key_data) {	//【C#版特有のコメント】C言語版の戻り値はint型で成功時0,失敗時-1ですが、C#版の戻り値はboolとしたので判り易さを優先して成功時true,失敗時falseとしました。呼び出し側の判定式はC言語版とC#版で逆になる事に注意して下さい。
			ght_hash_entry_t p_e;
			int l_key;
			if(p_entry_data == null) { throw new ApplicationException(); }
			if(ght_get(p_ht, p_key_data) != null) { return false; }	//Don't insert if the key is already present.
			l_key = ght_get_hash_value(p_ht, p_key_data);
			//このハッシュテーブルが、キャッシュとして動作中ならば…
			if(p_ht.bucket_limit != 0) {
				LIST_ENTRY list_head = p_ht.le_bucket[l_key];
				LIST_ENTRY list_entry = list_head.Flink;
				//このバケットの先頭から(bucket_limit-1)個を超えるバケットを全て削除する。
				int i = p_ht.bucket_limit;
				while(list_entry != list_head) {
					p_e = CONTAINING_RECORD<ght_hash_entry_t>(list_entry);
					list_entry = list_entry.Flink;
					if(--i <= 0) {	//bucket_limit個目も削除対象とするのでプレインクリメントです。
						RemoveEntryList(p_e.le_iterator);
						RemoveEntryList(p_e.le_bucket);
						p_ht.fn_bucket_free?.Invoke(p_e.p_entry_data, p_e.key_data);	//「if(p_ht.fn_bucket_free != null) { p_ht.fn_bucket_free.Invoke(p_e.p_entry_data, p_e.key_data); }」と書いても同じです。
						p_ht.i_size--;	//忘れないで!!
					}
				}
			}
			p_e = new ght_hash_entry_t();
			p_e.p_entry_data = p_entry_data;
			p_e.key_data = p_key_data;
			InsertTailList(p_ht.le_iterator, p_e.le_iterator);	//イテレーション用のリストを直接参照している既存のアプリケーションとの互換性のために、イテレーション用のリストへの追加位置はこれまで通り末尾に追加する事にした。	{{2016/05/06コメント追記:本当は、要素の追加順とイテレーション用のリストの順序は無関係であるべきなのだが、当モジュールの実装に依存してリストの末尾に追加される事を期待した実装になってしまっているモジュールが存在する(clipstr.cのintern_string()。SqliteHelper.cも怪しいか?)。望ましくはないのだが、確かに追加順にイテレートされると便利な場面も多いので、このままにする事した。尚、イテレート前に明示的にソートしている(これも仕様外ではあるのだが)場合は、元々追加順には影響されないイテレート順となっているのでこの件とは無関係です(clipwkst.c等)。}}
			InsertHeadList(p_ht.le_bucket[l_key], p_e.le_bucket);	//キャッシュ対応のために、バケットのリストへの追加位置は先頭に追加するように変更した。既存のアプリケーションはバケットのリストを直接参照していないので、この変更による互換性の問題は生じないはずだ。
			p_ht.i_size++;		//┬この処理順序は必須です。
			ght_check_rehash(p_ht);	//┘
			return true;
		}
		//-----------------------------------------------------------------------------
		//Get an entry from the hash table.
		public static object ght_get(ght_hash_table_t p_ht, object p_key_data) {
			ght_hash_entry_t p_e;
			p_e = ght_search_in_bucket(p_ht, p_key_data);
			return p_e?.p_entry_data;	//「if(p_e == null) { return null; } return p_e.p_entry_data;」と書いても同じです。
		}
		//-----------------------------------------------------------------------------
		//Replace an entry from the hash table.
		public static object ght_replace(ght_hash_table_t p_ht, object p_entry_data, object p_key_data) {
			ght_hash_entry_t p_e;
			object p_old_data;
			p_e = ght_search_in_bucket(p_ht, p_key_data);
			if(p_e == null) { return null; }
			p_old_data = p_e.p_entry_data;
			p_e.p_entry_data = p_entry_data;
			return p_old_data;
		}
		//-----------------------------------------------------------------------------
		//Remove an entry from the hash table.
		public static object ght_remove(ght_hash_table_t p_ht, object p_key_data) {
			ght_hash_entry_t p_e;
			object p_old_data;
			p_e = ght_search_in_bucket(p_ht, p_key_data);
			if(p_e == null) { return null; }
			RemoveEntryList(p_e.le_iterator);
			RemoveEntryList(p_e.le_bucket);
			p_old_data = p_e.p_entry_data;
			p_ht.i_size--;		//┬この処理順序は必須です。
			ght_check_rehash(p_ht);	//┘
			return p_old_data;
		}
		//-----------------------------------------------------------------------------
		//Get the first entry in an iteration.
		public static object ght_first(ght_hash_table_t p_ht, out ght_iterator_t p_iterator, out object pp_key_data) {
			LIST_ENTRY list_head = p_ht.le_iterator;
			LIST_ENTRY list_entry = list_head.Flink;
			p_iterator.le_next = list_entry;
			return ght_next(p_ht, ref p_iterator, out pp_key_data);
		}
		//-----------------------------------------------------------------------------
		//Get the next entry in an iteration.
		public static object ght_next(ght_hash_table_t p_ht, ref ght_iterator_t p_iterator, out object pp_key_data) {
			LIST_ENTRY list_head = p_ht.le_iterator;
			LIST_ENTRY list_entry = p_iterator.le_next;
			if(list_entry != list_head) {
				ght_hash_entry_t p_e = CONTAINING_RECORD<ght_hash_entry_t>(list_entry);
				p_iterator.le_next = list_entry.Flink;								//イテレータは次のノードを指しているので、イテレーションの中で当該ノードをght_remove()しても安全です。
				pp_key_data = p_e.key_data;
				return p_e.p_entry_data;
			}
			pp_key_data = null;	//エラー抑制
			return null;
		}
		//-----------------------------------------------------------------------------
		//Set the rehashing status of the table.
		public static void ght_set_rehash(ght_hash_table_t p_ht, bool b_rehash) {
			p_ht.b_rehash = b_rehash;
		}
		//-----------------------------------------------------------------------------
		//Rehash the hash table.
		public static void ght_rehash(ght_hash_table_t p_ht, int i_table_size) {
			LIST_ENTRY list_head = p_ht.le_iterator;
			LIST_ENTRY list_entry = list_head.Flink;
			int i, l_key;
			//Reallocate the new bucket with the new size.
			if(i_table_size < 1) { i_table_size = 1; }
			p_ht.le_bucket = new LIST_ENTRY[i_table_size];
			for(i = 0; i < i_table_size; i++) {
				p_ht.le_bucket[i] = new LIST_ENTRY();
				InitializeListHead(p_ht.le_bucket[i]);
			}
			//Walk through all elements in the table and insert them into the new bucket.
			while(list_entry != list_head) {
				ght_hash_entry_t p_e = CONTAINING_RECORD<ght_hash_entry_t>(list_entry);
				l_key = ght_get_hash_value(p_ht, p_e.key_data);
				InsertHeadList(p_ht.le_bucket[l_key], p_e.le_bucket);	//キャッシュ対応のために、バケットのリストへの追加位置は先頭に追加するように変更した。既存のアプリケーションはバケットのリストを直接参照していないので、この変更による互換性の問題は生じないはずだ。
				list_entry = list_entry.Flink;
			}
		}
		//-----------------------------------------------------------------------------
		//Enable or disable bounded buckets.
		public static void ght_set_bounded_buckets(ght_hash_table_t p_ht, int bucket_limit, Action<object/*data*/,object/*key*/> fn_bucket_free) {
			if((bucket_limit < 0) ||
			  ((bucket_limit == 0) && (fn_bucket_free != null))) { throw new ApplicationException(); }
			p_ht.bucket_limit = bucket_limit;
			p_ht.fn_bucket_free = fn_bucket_free;
		}
	}
}
