#include <assert.h>
#include <stdlib.h>     /* srand, rand */
#include <string.h>
#include <stdio.h>
#include <vector>

int Created = 0;
int Deleted = 0;

template <typename T>
T create_empty()
{
    return T();
}

template <>
bool create_empty<bool>()
{
	return false;
}

template <typename T>
bool check_empty(T& a)
{
	return a.is_empty();
}

template <>
bool check_empty<bool>(bool& a)
{
	return a == false;
}

template <typename T,typename C,int Base>
class TrieNode
{
	TrieNode* childs[Base];
	T n;

	unsigned int val;

	void init(unsigned int val)
	{
		Created++;

		this->val = val;
		memset(childs, 0 ,sizeof(TrieNode*) * Base);
		n = create_empty<T>();
	}

	TrieNode(int mult)
	{
		init(mult);
	}

	T& create(unsigned int number,int mult)
	{
		if(!number)
		{
			return n;
		}
		else
		{
			unsigned int digit = number % Base;
			number /= Base;

			TrieNode*& child = childs[digit];

			if(!child)
				child = new TrieNode(digit*mult);

			return child->create(number,mult*Base);
		}
	}

	C get_keys(int val)
	{
		C list;

		if(!check_empty(n))
		{
			list.push_back(val);
		}

		for(int i=0;i<Base;i++)
		{
			TrieNode<T,C,Base>*& child = childs[i];

			if(child)
			{
				C list_new = child->get_keys(child->val + val);

				for(int j=0;j<(int)list_new.size();j++)
				{
					list.push_back(list_new[j]);
				}
			}
		}

		return list;
	}

	TrieNode& move(TrieNode& other)
	{
		this->val = other.val;
		memcpy(this->childs,other.childs,sizeof(TrieNode*) * Base);
		this->n = other.n;

		other.val = 1;
		memset(other.childs,0,sizeof(TrieNode*) * Base);
		other.n = create_empty<T>();

		return *this;
	}


	public :

		~TrieNode()
		{
			Deleted++;

			for(int i=0;i<Base;i++)
				delete childs[i];
		}


		TrieNode(){ init(1); }

		TrieNode (const TrieNode& other)
		{
			move( const_cast<TrieNode&>(other) );
		}

		TrieNode& operator= (TrieNode other)
		{
			return move(other);
		}

		T& operator[](unsigned int number)
		{
			return this->create(number,1);
		}

		bool is_empty()
		{
			if(!check_empty<T>(n))
				return false;

			for(int i=0;i<Base;i++)
			{
				TrieNode*& child = childs[i];

				if(child)
				{
					if(!check_empty< TrieNode<T,C,Base> >(*child))
						return false;
				}
			}

			return true;
		}

		C get_keys()
		{
			return this->get_keys(0);
		}
};

template<typename T,typename C>
struct TrieNodeTen
{
    typedef TrieNode<T,C,10> type;
};

template <typename T>
struct TrieNodeTenVec
{
	typedef typename TrieNodeTen< T,std::vector<int> >::type type;
};

template <typename T,typename C>
class TrieNodeTen1 : public TrieNode<T,C,10> {};

template <typename T>
class TrieNodeTenVec1 : public TrieNodeTen1<T,std::vector<int> > {};

int main(int argc, char* argv[])
{
	{
		TrieNodeTenVec1< TrieNodeTenVec1<bool> > trie;

		for(int i=0;i<100;i++)
			trie[rand()][rand()] = true;
	}

	printf("Created %d\n",Created);
	printf("Deleted %d\n",Deleted);

	getchar();

	return 0;
}