

/*!
  @author d‹à‹›
  @since 2005/11/27
	@note
	licence:BSD Licence
*/


#ifndef DKUTIL_DKTL_TRIE_HPP
#define DKUTIL_DKTL_TRIE_HPP


#include <nysl/tree.h>


namespace dkutil{


template<class T,size_t __N_,class A=std::allocator<T> >
class dictionary{
public:
	typedef typename A allocator;
	BOOST_STATIC_CONSTANT(size_t,node_num = __N_);
	class 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_];
	root_type root;
	struct default_offset_calc_functor{
		size_t operator()(const T &x){
			return x;
		}
	};
	dictionary(){
		for(size_t i=0;i<__N_;i++)
			root[i] = NULL;
	}
	~dictionary(){
		clear();
	}
	bool reset(){
		clear();
		
	}
	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(&(pt[i]->next[0]));
			}
		}
	}
	void node_free(node_type *p){
		delete p;
	}
	node_type *node_alloc(){
		return new node_type;
	}
	void clear()
	{
		free_node_vector v;
		clear_reflective(v,&root[0]);
		
		free_node_vector::iterator it = v.begin();
		for(;it != v.end();it++)
		{
			node_type **tpp = (*it);
			node_free(*tpp);
			tpp = NULL;
		}
	}
	template<class FUNCTOR>
	bool insert(T *pobj,size_t num,FUNCTOR calc=default_offset_calc_functor()){
		root_type pt = root;
		size_t offset = 0;
	
		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,calc);
	}
	template<class FUNCTOR>
	bool insert_reflective(root_type pt,size_t offset,T *pobj,size_t num,FUNCTOR calc=default_offset_calc_functor())
	{
		
		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,calc);
	}

	template<class FUNCTOR>
	bool find(T *pobj,size_t num,FUNCTOR calc=default_offset_calc_functor())
	{
		root_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,calc);
	}
	template<class FUNCTOR>
	bool find_reflective(root_type pt,size_t offset,T *pobj,size_t num,FUNCTOR calc=default_offset_calc_functor())
	{
		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,calc);
	}
	
};




}//end of dkutil namepsace

#endif //end of include once