

/**
  @author d金魚
  @since 2005/11/29
	@brief 簡易辞書機能
	@note

*/


#ifndef DKUTIL_DKTL_DICTIONARY_HPP
#define DKUTIL_DKTL_DICTIONARY_HPP

#include <dkutil/macro.hpp>
#include <vector>

namespace dkutil{

///class dictionary用
template<class T>
struct default_offset_calc_functor{
	size_t operator()(const T &x){
		return x;
	}
};
/**
@note
warning:配列の一つの要素にメモリがsizeof(void *) * __N_ byte 強 かかります。
なので、配列のbyte数が同じような要素が沢山入るような辞書作成には持ってこいです。
逆に1024の配列とその他が1-4くらいの配列で構成される辞書の作成には不向きです。
例えばファイルの拡張子の辞書作成とかが向いています。

以下サンプルソース
@code
int main(){

	dkcCheckMemoryLeak(TRUE);
	typedef dictionary<uint8,256> dic_t;
	dic_t dic;
	uint8 data[]={4,2,6,4,9,2};
	uint8 data2[]={4,2,6,4};

	bool r = dic.insert(data,sizeof(data));
	if(dic.find(data,sizeof(data)))
		std::cout << "find ok" << std::endl;
	dic.insert(data2,sizeof(data2));
	if(dic.find_front(data,sizeof(data)))
		std::cout << "find front ok" << std::endl;
	return 0;
}
@endcode
@todo eraseの実装
*/
template<class T,size_t __N_,class FUNCTOR=default_offset_calc_functor<T>,class A=std::allocator<T> >
class dictionary{
public:
	typedef typename A allocator;
	//BOOST_STATIC_CONSTANT(size_t,node_num = __N_);
	///sizeof -> 4 * __N_ + sizeof(bool) + alpha
	struct node_type{
		T data;
		bool data_stop;
		node_type *next[__N_];
		node_type(){
			data_stop = false;
			for(size_t i=0;i<__N_;i++)
				next[i] = NULL;
		}
	};
	typedef typename std::vector<node_type **> free_node_vector;
	//node_type *root[__N_];

	typedef node_type *root_type[__N_];
protected:
	root_type root;
	void clear_reflective(free_node_vector &v,node_type *pt[__N_]){
		
		for(size_t i=0;i<__N_;i++)
		{
			if(NULL != pt[i])
			{
				v.push_back(&pt[i]);
				
				//if(pt[i]->next[j])
				clear_reflective(v,&(pt[i]->next[0]));
			}
		}

	}
	void node_free(node_type *p){
		delete p;
	}
	node_type *node_alloc(){
		return new node_type;
	}
	bool insert_reflective(node_type **pt,size_t offset,T *pobj,size_t num)
	{
		FUNCTOR calc;
		size_t nt = calc(pobj[offset]);
		if(NULL==pt[nt]){
			pt[nt] = node_alloc();
		}
		offset++;
		if(offset == num){
			pt[nt]->data_stop = true;
			return true;
		}
		return insert_reflective(pt[nt]->next,offset,pobj,num);
	}
	
	bool find_reflective(root_type pt,size_t offset,T *pobj,size_t num)
	{
		FUNCTOR calc;
		size_t nt = calc(pobj[offset]);
		if(NULL==pt[nt]){
			return false;
		}
		offset++;
		if(offset == num){
			if(true==pt[nt]->data_stop)
			{
				return true;
			}
			return false;
		}
		return find_reflective(pt[nt]->next,offset,pobj,num);
	}

public:
	dictionary(){
		for(size_t i=0;i<__N_;i++)
			root[i] = NULL;
	}
	~dictionary(){
		clear();
	}
	bool reset(){
		clear();
		return true;
	}

	void clear()
	{
		//stack
		free_node_vector v;
		clear_reflective(v,&root[0]);
		
		free_node_vector::reverse_iterator it = v.rbegin();
		for(;it != v.rend();it++)
		{
			node_type **tpp = (*it);
			node_free(*tpp);
			tpp = NULL;
		}
		v.clear();
	}
	
	bool insert(T *pobj,size_t num){
		node_type **pt = root;
		size_t offset = 0;
		FUNCTOR calc;
		size_t nt = calc(pobj[offset]);
		if(NULL==pt[nt]){
			pt[nt] = node_alloc();
		}
		pt[nt]->data = pobj[offset];
		offset++;
		if(offset == num){
			pt[nt]->data_stop = true;
			return true;
		}
		return insert_reflective(pt[nt]->next,offset,pobj,num);
	}
	

	
	bool find(T *pobj,size_t num)
	{
		FUNCTOR calc;
		node_type **pt = root;
		size_t offset = 0;
		size_t nt = calc(pobj[offset]);
		if(NULL==pt[nt]){
			return false;
		}
		offset++;
		if(offset == num){
			return true;
		}
		return find_reflective(pt[nt]->next,offset,pobj,num);
	}

	/**
	abcdとabcという定義がこのコンテナ内に存在したら
	abcが見つかり次第trueを返す
	*/
	
	bool find_front(T *pobj,size_t num)
	{
		FUNCTOR calc;
		node_type **pt = root;
		size_t nt;
		size_t i = 0;
		for(;i<num;i++){
			nt  = calc(pobj[i]);
			if(NULL==pt[nt]){
				return false;
			}
			if(pt[nt]->data_stop) return true;
			//offset++;
			//if(offset == num){	return true;}
			pt = pt[nt]->next;

		}
		return false;
	}

};



/**
@brief unique idを設定する事の出来る辞書
*/
template<class T,size_t __N_,typename ID_T=int,class FUNCTOR=default_offset_calc_functor<T>,class A=std::allocator<T> >
class id_dictionary{
public:
	typedef typename A allocator;
	typedef typename ID_T id_type;
	typedef typename T value_type;
	typedef typename id_dictionary<T,__N_,ID_T,A,FUNCTOR> self_type;
	BOOST_STATIC_CONSTANT(size_t,node_num = __N_);
	///sizeof -> 4 * __N_ + sizeof(bool) + alpha
	struct node_type{
		bool data_stop;
		ID_T unique_id;
		T data;
		node_type *next[__N_];
		node_type(){
			data_stop = false;
			for(size_t i=0;i<__N_;i++)
				next[i] = NULL;
		}
	};
	typedef typename std::vector<node_type **> free_node_vector;
	//node_type *root[__N_];

	typedef node_type *root_type[__N_];
protected:
	typedef typename std::deque<T> queue_def_t;
	root_type root;
	ID_T mInvalidUniqueID;
	void clear_reflective(free_node_vector &v,node_type *pt[__N_]){
		
		for(size_t i=0;i<__N_;i++)
		{
			if(NULL != pt[i])
			{
				v.push_back(&pt[i]);
				
				//if(pt[i]->next[j])
				clear_reflective(v,&(pt[i]->next[0]));
			}
		}

	}
	void node_free(node_type *p){
		delete p;
	}
	node_type *node_alloc(){
		return new node_type;
	}
public:

	static ID_T getDefaultInvalidUniqueID(){
		return std::numeric_limits<ID_T>::max();
	}
	id_dictionary(ID_T invalid_id=getDefaultInvalidUniqueID())
	{
		for(size_t i=0;i<__N_;i++)
			root[i] = NULL;

		reset(invalid_id);
	}
	~id_dictionary(){
		clear();
	}

	bool reset(ID_T invalid_id){
		mInvalidUniqueID = invalid_id;
		clear();
		return true;
	}
	ID_T getInvalidUniqueID()const{
		return mInvalidUniqueID;
	}
	
	void clear()
	{
		//stack
		free_node_vector v;
		clear_reflective(v,&root[0]);
		
		free_node_vector::reverse_iterator it = v.rbegin();
		for(;it != v.rend();it++)
		{
			node_type **tpp = (*it);
			node_free(*tpp);
			tpp = NULL;
		}
		v.clear();
	}
	
	bool insert(T *pobj,size_t num,ID_T unique_id)
	{
		FUNCTOR calc;
		node_type **pt = root;
		size_t nt;
		size_t i = 0;
		for(;i<num;)
		{
			nt  = calc(pobj[i]);
			if(NULL==pt[nt])
			{
				pt[nt] = node_alloc();
			}
			
			pt[nt]->data = pobj[i];
			i++;

			if(i == num)
			{
				pt[nt]->unique_id = unique_id;
				pt[nt]->data_stop = true;
				return true;
			}
			pt = pt[nt]->next;
		}
		return false;
	}
	

	///@return unique_id
	ID_T find(T *pobj,size_t num)
	{
		FUNCTOR calc;
		node_type **pt = root;
		size_t nt;
		size_t i = 0;
		for(;i<num;){
			nt  = calc(pobj[i]);
			if(NULL==pt[nt]){
				return getInvalidUniqueID();
			}
			i++;
			if(i == num){
				if(true==pt[nt]->data_stop)
				{
					return pt[nt]->unique_id;
				}
				return getInvalidUniqueID();
			}
			pt = pt[nt]->next;
		}
		return getInvalidUniqueID();
	}

	/**
	abcdとabcという定義がこのコンテナ内に存在したら
	abcが見つかり次第unique_idを返す
	*/
	
	ID_T find_front(T *pobj,size_t num)
	{
		FUNCTOR calc;
		node_type **pt = root;
		size_t nt;
		size_t i = 0;
		for(;i<num;i++){
			nt  = calc(pobj[i]);
			if(NULL==pt[nt]){
				return getInvalidUniqueID();
			}
			if(pt[nt]->data_stop){
				return pt[nt]->unique_id;
			}

			pt = pt[nt]->next;

		}
		return getInvalidUniqueID();
	}
	/*
	template<class CONTAINER_T>
	struct find_front_logic{
		ID_T operator()(self_type *t,const CONTAINER_T &x)
		{
			FUNCTOR calc;
			node_type **pt = t->getRoot();
			size_t nt;
			CONTAINER_T::const_iterator it = x.begin();
			for(;it != x.end();it++)
			{
				nt  = calc((*it));
				if(NULL==pt[nt]){
					return t->getInvalidUniqueID();
				}
				if(pt[nt]->data_stop){
					return pt[nt]->unique_id;
				}

				pt = pt[nt]->next;

			}
			return t->getInvalidUniqueID();
		}

	};
	template<class CONTAINER_T>
	ID_T find_front(CONTAINER_T t){//std::deque<T>
		find_front_logic<CONTAINER_T> f;
		return f(this,t);
	}*/
	ID_T find_front(queue_def_t &x)
	{
		FUNCTOR calc;
		node_type **pt = root;
		size_t nt;
		queue_def_t::const_iterator it = x.begin();
		for(;it != x.end();it++)
		{
			nt  = calc((*it));
			if(NULL==pt[nt]){
				return getInvalidUniqueID();
			}
			if(pt[nt]->data_stop){
				return pt[nt]->unique_id;
			}

			pt = pt[nt]->next;

		}
		return getInvalidUniqueID();
	}
};




}//end of dkutil namepsace

#endif //end of include once