// Lista.h
// Declaração e definição da classe Template cLista<class T>    

// Aula de 10 de Janeiro de 2002


template<class T> 
class cLista
{
protected:
	class cElemLista     // Classe privada de cLista
	{
	public :
		T Obj;
		cElemLista *Proximo;
	
		cElemLista() { Proximo = 0;};
	};

	int NrElementos;
	cElemLista *Sentinela;	// ponteiro para o elemento de controle , à cabeça da lista
	cElemLista *Tail;	// ponteiro para o último elemento da lista
	
public :
	cLista();
	~cLista();   // destrutor
	
	bool Inserir( T Obj  );				// Inserção no fim
	bool Remover( T Obj  );				// Remove o elemento que contem um objecto igual a Obj	
	T *Obter( int pos );                // Obtem um o ponteiro para o objecto que está na posição 'pos'
	int GetNrElementos();				// Retorna o nr de elementos da lista

protected :
	bool Procurar( T Obj, cElemLista* &pEl , cElemLista* &pAnterior );
};


// IMPLEMENTAÇÃO dos métodos da classe Template cLista

template<class T> 
cLista<T>::cLista()
{
	Sentinela  = new cElemLista();    // Cria o elemento de controle   
	Tail = Sentinela;
	NrElementos = 0;
}

template<class T> 
cLista<T>::~cLista()
{
	cElemLista *p, *pNext;

	for ( p=Sentinela; p ;  )
	{
		pNext = p->Proximo;
		delete p;
		p = pNext;
	}
}

template<class T> 
int cLista<T>::GetNrElementos()
{
	return NrElementos;
}


template<class T> 
bool cLista<T>::Inserir( T Obj )
{
	cElemLista *pNovo;
	
	pNovo = new cElemLista();

	pNovo->Obj = Obj;
	
	Tail->Proximo = pNovo;
	
	Tail = pNovo;
	
	NrElementos ++;
	return true;
}

template<class T> 
bool cLista<T>::Remover(  T Obj  )
{
	cElemLista *p, *pAnt;
	bool Encontrou;

	if ( NrElementos == 0 ) return false;  // Se a lista estiver vazia ...
	
	Encontrou = Procurar( Obj, p,  pAnt );

	if ( !Encontrou ) return false;

	pAnt->Proximo = p->Proximo ;

	if ( p == Tail ) // Se o elemento a remover estiver no fim
		Tail = pAnt;

	delete p;

	NrElementos --;
	return true;
}


template<class T> 
T *cLista<T>::Obter( int pos )    //  0<= pos <= NrElementos 
{
	if ( pos < 0 || pos > NrElementos ) return 0;

	int i;
	cElemLista *p;

	for ( i=1, p=Sentinela->Proximo ; i < pos; i++, p=p->Proximo ) ;

	return &(p->Obj) ;
}


template<class T> 
bool cLista<T>::Procurar( T Obj,  cElemLista* &pEl ,cElemLista* &pAnterior )
{
	cElemLista *p, *pAnt;

	pAnt = Sentinela;
	p = Sentinela->Proximo ;

	while ( p && !( Obj  == p->Obj ) )
	{
		pAnt = p;
		p = p->Proximo ;
	}

	pAnterior = pAnt;
	pEl = p;
	
	return ( p != 0 );
}