//------------------------------------------------------------------------------
// Lamp : Open source game middleware
// Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//------------------------------------------------------------------------------

/** @file
 * ハッシュマップヘッダ
 * @author Junpee
 */

#ifndef HASH_MAP_H_
#define HASH_MAP_H_

// アレイリスト
#include <Core/Container/ArrayList.h>

namespace Lamp{

//------------------------------------------------------------------------------
/**
 * ハッシュマップ
 *
 * このクラスは継承しないで下さい。
 * HashKeyは以下の4つのメソッドを実装している必要があります。<br>
 * HashKey();<br>
 * HashKey& operator =(const HashKey& copy);<br>
 * bool equals(const HashKey& compare) const;<br>
 * u_int getHashCode() const;<br>
 * ValueTypeは通常はポインタ型を指定して下さい。
 */
template <typename HashKey, typename ValueType>
class HashMap{
public:
	//--------------------------------------------------------------------------
	/**
	 * ハッシュデータ
	 *
	 * 配列取り出し用クラス
	 */
	template <typename HashKey, typename ValueType>
	class HashData{
	public:
		/// デフォルトコンストラクタ
		HashData() : value_(NULL){}

		/// キー値
		HashKey key_;
		/// 値
		ValueType value_;
	};

	//--------------------------------------------------------------------------
	// 構築、破棄
	//--------------------------------------------------------------------------
	/**
	 * コンストラクタ
	 * @param capacity 初期容量
	 * @param loadFactor 負荷係数
	 */
	explicit HashMap(int capacity = 16, float loadFactor = 0.75f) :
		capacity_(capacity), loadFactor_(loadFactor), count_(0){
		Assert(capacity_ > 0);
		maxSize_ = (int)(capacity_ * loadFactor_);
		array_ = new HashItem<HashKey, ValueType>[capacity_];
	}

	/**
	 * デストラクタ
	 */
	~HashMap(){
		Assert(count_ == 0);
		delete[] array_;
	}

	/**
	 * クローン
	 * @param destination クローン先ハッシュマップ
	 */
	void cloneTo(HashMap* destination) const{
		Assert(destination->getCount() == 0);
		destination->loadFactor_ = loadFactor_;
		destination->setCapacity(capacity_);
		for(int i = 0; i < capacity_; i++){
			HashItem<HashKey, ValueType>* item = &array_[i];
			// 第一要素が空だった
			if(item->value_ == NULL){ continue; }
			while(true){
				destination->put(item->key_, item->value_);
				item = item->next_;
				if(item == NULL){ break; }
			}
		}
	}

	//--------------------------------------------------------------------------
	// 情報の取得
	//--------------------------------------------------------------------------
	/**
	 * 要素数の取得
	 * @return 要素数
	 */
	int getCount() const{ return count_; }

	/**
	 * 空かどうか
	 * @return 空ならtrueを返す
	 */
	bool isEmpty() const{ return (count_ == 0); }

	/**
	 * 要素の取得
	 * @param key 取得する要素のキー
	 * @return 要素。該当するキーが無ければNULL。
	 */
	ValueType get(const HashKey& key) const{
		// ハッシュ値の割り出し
		u_int hashCode = key.getHashCode();
		HashItem<HashKey, ValueType>* item;
		item = &array_[hashCode % capacity_];
		if(item->value_ == NULL){ return NULL; }
		while(true){
			if(item->key_.equals(key)){ return item->value_; }
			item = item->next_;
			if(item == NULL){ return NULL; }
		}
	}

	/**
	 * 容量の取得
	 * @return 容量
	 */
	int getCapacity() const{ return capacity_; }

	/**
	 * 負荷係数の取得
	 * @return 負荷係数
	 */
	float getLoadFactor() const{ return loadFactor_; }

	/**
	 * 配列の取得
	 * @param arrayList [out]データを格納するArrayList
	 */
	void toArray(ArrayList< HashData<HashKey, ValueType> >* arrayList) const{
		if(count_ == 0){ return; }
		arrayList->clear(count_);
		for(int i = 0; i < capacity_; i++){
			HashItem<HashKey, ValueType>* item = &array_[i];
			if(item->value_ == NULL){ continue; }
			while(true){
				HashData<HashKey, ValueType> data;
				data.key_ = item->key_;
				data.value_ = item->value_;
				arrayList->add(data);
				item = item->next_;
				if(item == NULL){ break; }
			}
		}
	}

	//--------------------------------------------------------------------------
	// ハッシュマップの変更
	//--------------------------------------------------------------------------
	/**
	 * 要素の追加
	 * @param key ハッシュキー。同じキーは登録不可。
	 * @param value 格納する値。NULLは不可。
	 * @return 成功すればture、すでに同じ要素があればfalseを返し、値は追加されない。
	 */
	bool put(HashKey key, ValueType value){
		Assert(value != NULL);
		if(value == NULL){ return false; }
		// 配列のリサイズ
		if(count_ + 1 > maxSize_){
			int newCapacity = capacity_ * 2;
			while(true){
				maxSize_ = (int)(newCapacity * loadFactor_);
				if(count_ + 1 <= maxSize_){ break; }
				newCapacity *= 2;
			}
			setCapacity(newCapacity);
		}
		// ハッシュ値の割り出し
		u_int hashCode = key.getHashCode();
		// ハッシュ値にあたる要素が空なら代入して終わり。
		HashItem<HashKey, ValueType>* item;
		item = &array_[hashCode % capacity_];
		if(item->value_ == NULL){
			item->key_ = key;
			item->value_ = value;
			count_++;
			return true;
		}
		while(true){
			// 同値チェック
			if(item->key_.equals(key)){ return false; }
			// アロケーションして追加
			if(item->next_ == NULL){
				HashItem<HashKey, ValueType>* newItem;
				newItem = new HashItem<HashKey, ValueType>(key, value);
				item->next_ = newItem;
				count_++;
				return true;
			}
			item = item->next_;
		}
	}

	/**
	 * 要素の削除
	 * @param key ハッシュキー
	 * @return 削除された値。見つからなければNULL
	 */
	ValueType remove(HashKey key){
		// ハッシュ値の割り出し
		u_int hashCode = key.getHashCode();
		HashItem<HashKey, ValueType>* item = &array_[hashCode % capacity_];
		if(item->value_ == NULL){ return NULL; }
		// 第一要素の削除
		ValueType returnValue = NULL;
		if(item->key_.equals(key)){
			returnValue = item->value_;
			if(item->next_ == NULL){
				// 1番目の要素だけを削除
				item->value_ = NULL;
				item->key_ = HashKey();
			}else{
				// 2番目の要素を1番目に代入して削除
				HashItem<HashKey, ValueType>* nextItem = item->next_;
				*item = *nextItem;
				delete nextItem;
			}
			count_--;
			return returnValue;
		}
		// 第二要素以降の削除
		HashItem<HashKey, ValueType>* nextItem;
		while(true){
			nextItem = item->next_;
			if(nextItem == NULL){ return NULL; }
			if(nextItem->key_.equals(key)){
				returnValue = nextItem->value_;
				item->next_ = nextItem->next_;
				delete nextItem;
				count_--;
				return returnValue;
			}
			item = nextItem;
		}
	}

	/**
	 * クリア
	 */
	void clear(){
		for(int i = 0; i < capacity_; i++){
			HashItem<HashKey, ValueType>* item = &array_[i];
			HashItem<HashKey, ValueType>* nextItem = item->next_;
			// 第一要素が空だった
			if(item->value_ == NULL){ continue; }
			item->key_ = HashKey();
			item->value_ = NULL;
			item->next_ = NULL;
			count_--;
			while(true){
				item = nextItem;
				if(item == NULL){ break; }
				nextItem = item->next_;
				item->key_ = HashKey();
				item->value_ = NULL;
				item->next_ = NULL;
				count_--;
				delete item;
			}
		}
	}

	/**
	 * 容量の設定
	 * @param capacity 設定するキャパシティ
	 */
	void setCapacity(int capacity){
		HashMap<HashKey, ValueType*> hashMap(capacity, loadFactor_);
		int listSize = count_, listCounter = 0;
		HashKey* keyList = new HashKey[listSize];
		ValueType* valueList = new ValueType[listSize];
		for(int i = 0; i < capacity_; i++){
			HashItem<HashKey, ValueType>* item = &array_[i];
			if(item->value_ == NULL){ continue; }
			while(true){
				keyList[listCounter] = item->key_;
				valueList[listCounter] = item->value_;
				listCounter++;
				item = item->next_;
				if(item == NULL){ break; }
			}
		}
		clear();
		delete[] array_;
		capacity_ = capacity;
		maxSize_ = (int)(capacity_ * loadFactor_);
		array_ = new HashItem<HashKey, ValueType>[capacity_];
		// キャパシティの拡張が起こる可能性がある
		for(int i = 0;i < listSize;i++){ put(keyList[i], valueList[i]); }
		delete[] keyList;
		delete[] valueList;
	}

	/**
	 * トリム
	 */
	void trim(){
		int newCapacity = 1, maxSize;
		while(true){
			maxSize = (int)(newCapacity * loadFactor_);
			if(count_ <= maxSize){ break; }
			newCapacity *= 2;
		}
		setCapacity(newCapacity);
	}

	//--------------------------------------------------------------------------
#ifdef _DEBUG
	/**
	 * デバッグ用出力
	 * @param detail 詳細出力
	 */
	void debugPrint(bool detail){
		DebugOut("\nCapacity %d, LoadFactor %.2f MaxSize %d Size %d ",
			capacity_, loadFactor_, maxSize_, count_);
		if(detail){ DebugOut("\n"); }
		int allocCount = 0;
		for(int i = 0;i < capacity_;i++){
			HashItem<HashKey, ValueType>* item = &array_[i];
			int count = 0;
			// 全表示
			while(true){
				count++;
				if(count >= 2){ allocCount++; }
				if(detail){
					if(item->value_ != NULL){ DebugOut("*"); }
				}	
				if(item->next_ == NULL){ break; }
				item = item->next_;
			}
			if(detail){ DebugOut("\n"); }
		}
		DebugOut("allocCount %d allocRate %.1f%%\n",
			allocCount, (float)allocCount / count_ * 100.f);
	}
#endif

private:
	//--------------------------------------------------------------------------
	// ハッシュアイテム
	template <typename HashKey, typename ValueType>
	class HashItem{
	friend class HashMap;
	public:
		// デフォルトコンストラクタ
		HashItem() : key_(), value_(NULL), next_(NULL){}

		// 初期値有りコンストラクタ
		HashItem(HashKey key, ValueType value) :
			key_(), value_(value), next_(NULL){
			key_ = key;// コピーコンストラクタの実装義務を無くす。
		}

		// 代入演算子
		HashItem& operator =(const HashItem& copy){
			key_ = copy.key_;
			value_ = copy.value_;
			next_ = copy.next_;
			return *this;
		}

		// キー値
		HashKey key_;
		// 値
		ValueType value_;
		// 次のアイテム
		HashItem* next_;
	};

	//--------------------------------------------------------------------------
	// コピーコンストラクタの隠蔽
	HashMap(const HashMap& copy);

	// 代入コピーの隠蔽
	void operator =(const HashMap& copy);

	//--------------------------------------------------------------------------
	// 容量
	int capacity_;
	// 負荷係数
	float loadFactor_;
	// 最大サイズ
	int maxSize_;
	// サイズ
	int count_;
	// ハッシュ配列
	HashItem<HashKey, ValueType>* array_;
};

//------------------------------------------------------------------------------
} // End of namespace Lamp
#endif // End of HASH_MAP_H_
//------------------------------------------------------------------------------
