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

// Aula de 10 de Janeiro de 2002

#include "lista.h"

// cListaOrdenada<class T> é derivada de cLista<class T>
//      Redefine os métodos :  Inserir e Procurar

template<class T>
class cListaOrdenada : public cLista<T>
{
public :
	cListaOrdenada();
	bool Inserir( T Obj  );				// Inserção ordenada

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


// IMPLEMENTAÇÃO dos métodos da classe Template cListaOrdenada<class T>

template<class T>
cListaOrdenada<T>::cListaOrdenada()
{
}

template<class T>
bool cListaOrdenada<T>::Inserir( T Obj )
{
	cElemLista *pNovo , *p, *pAnt;
	
	pNovo = new cElemLista();

	pNovo->Obj  = Obj;
	
	// Procura a zona de inserção
	Procurar( Obj , p, pAnt );
	
	pNovo->Proximo = p;
	pAnt->Proximo = pNovo;
	
	if ( pAnt == Tail ) Tail = pNovo;    // inserção no fim

	NrElementos ++;
	return true;
}

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

	pAnt = Sentinela;
	p = Sentinela->Proximo ;

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

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