// HashC.h: interface for the CHashC class.
//
//////////////////////////////////////////////////////////////////////


#include <vector>
using namespace std;


template <class T>
class CHashC
{

	enum { DIM_NORMAL = 1011, POS_VAZIA = -2, FIM_SEQ = -1 };

	struct SPos {
		T   info;
		int prox;
	};

	vector<SPos> tabela;

	void copia(const CHashC<T>& obj);

	public:
	CHashC(const int nTam = DIM_NORMAL);
	CHashC(const CHashC<T>& obj) ;
		
	bool inserir(const T& elemento);
	bool pesquisar(const T& elemento);
	//bool eliminar(const T& elemento);

	CHashC<T>& operator=(const CHashC<T>& obj);
};


template <class T>
void CHashC<T>::copia(const CHashC<T>& obj)
{
	tabela = obj.tabela;
}


template <class T>
CHashC<T>::CHashC(const int nTam)
{
	tabela.resize(nTam);

	for (int i = 0; i < nTam; i++) 
		tabela[i].prox = POS_VAZIA;
}


// Mini Teste A - a)
template <class T>
CHashC<T>::CHashC(const CHashC<T>& obj)
{
	copia(obj);
}


// Mini Teste B - a)
template <class T>
CHashC<T>& CHashC<T>::operator=(const CHashC<T>& obj)
{
	copia(obj);
	return *this;
}


// Mini Teste A - b)
template <class T>
bool CHashC<T>::inserir(const T& elemento)
{
	int pos = hashing(elemento) % tabela.size();

	if (tabela[pos].prox == POS_VAZIA )
	{
		tabela[pos].info = elemento;
		tabela[pos].prox = FIM_SEQ;
		return true;
	}

	int index = pos;

	while (tabela[index].prox != FIM_SEQ)
		index = tabela[index].prox;

	for (int j = tabela.size()-1; j >= 0; j--)
	{
		if (tabela[j].prox == POS_VAZIA)
		{
			tabela[j].info = elemento;
			tabela[j].prox = FIM_SEQ;
			tabela[index].prox = j;
			return true;
		}
	}
	return false;
}


// Mini Teste B - b)
template <class T>
bool CHashC<T>::pesquisar(const T& elemento)
{
	int pos = hashing(elemento) % tabela.size();

	do
	{
		if (tabela[pos].prox == POS_VAZIA)
			return false;

		if (tabela[pos].info == elemento)
			return true;
		pos = tabela[pos].prox;
	} while (pos != FIM_SEQ);

	return false;
}