/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * ------------------------------------------
 *
 * Template Classe de Lista (LIFO)
 *
 * t_listaint.h
 *
 */

#ifndef __T_LISTA_INC__
#define __T_LISTA_INC__


#include "erro.h"
//#include "ta_iteradores.h"

#ifndef __T_ITERADORES_INC__
typedef void* Iterador;
#endif

#ifndef NULL
#define NULL 0
#endif

#include <iostream.h>


template <class T>
class No
{
	T m_nConteudo;
	No<T>* m_pProx;

public:
	No(T iValor, No<T>* pProx = NULL)
	{
		m_nConteudo = iValor; 
		m_pProx = pProx; 
	}

	T conteudo() const	{ return m_nConteudo; }
	No<T>* prox() const { return m_pProx; }
};

template <class T> 
class Lista /* : public IteradorFrente<T> */
{
private:

protected:

	No<T>* m_pInicio;
	int m_nCount;

	static void copia(Lista<T>& l, const No<T>* p);

public:
	Lista();
	Lista(const Lista<T>& o);
	~Lista();

	bool inserir(T iValor);
	T retirar();
	T topo() const			{ return m_pInicio->m_nConteudo; }
	int comprimento() const	{ return m_nCount; }
	bool vazia() const		{ return (m_pInicio == NULL); }
	void removerTodos();

	Lista<T>& operator=(const Lista<T>& o);

	friend bool operator==(const Lista<T>& a, const Lista<T>& b);
	friend Lista<T> operator+(const Lista<T>& a, const Lista<T>& b);
	friend ostream& operator<<(ostream& output, const Lista<T>& obj);

	/* iteradores */
	Iterador inicio() const;
	T proximo(Iterador& i) const;
	bool fim(Iterador i) const;
};

template<class T>
Lista<T>::Lista()
{
	m_pInicio = NULL;
	m_nCount = 0;
}

template<class T>
Lista<T>::Lista(const Lista<T>& o)
{
	m_pInicio = NULL;
	m_nCount = 0;
	copia(*this, o.m_pInicio);
}

template<class T>
Lista<T>& Lista<T>::operator=(const Lista<T>& o)
{
	removerTodos();
	copia(*this, o.m_pInicio);
	return *this;
}

template<class T>
void Lista<T>::copia(Lista<T>& l, const No<T>* p)
{
	// caso terminal
	if (p == NULL)
		return;

	//caso geral
	copia(l, p->prox());
	l.inserir(p->conteudo());
}

template<class T>
Lista<T>::~Lista()
{
	removerTodos();
}

template<class T>
void Lista<T>::removerTodos()
{
	while (!vazia())
		retirar();
}

template<class T>
bool Lista<T>::inserir(T iValor)
{
	No<T>* pNo = new No<T>(iValor, m_pInicio);
	//pNo->m_nConteudo = iValor;
	//pNo->m_pProx = m_pInicio;
	m_pInicio = pNo;

	return true;
}

template<class T>
T Lista<T>::retirar()
{
	if (vazia())
		throw Erro(ERRO_GENERICO);

	T v = m_pInicio->conteudo();
	No<T>* p = m_pInicio;
	m_pInicio = m_pInicio->prox();

	delete p;

	return v;
}

template<class T>
Iterador Lista<T>::inicio() const
{
	return (Iterador)m_pInicio;
}

template<class T>
T Lista<T>::proximo(Iterador& i) const
{
	if (i == NULL)
		throw Erro(POSICAO_INVALIDA);

	T v = ((No<T>*)i)->conteudo();
	i = (Iterador)(((No<T>*)i)->prox());

	return v;
}

template<class T>
bool Lista<T>::fim(Iterador i) const
{
	return (i == NULL);
}

template<class T>
bool operator==(const Lista<T>& a, const Lista<T>& b)
{
	if (a.comprimento() != b.comprimento())
		return false;

	No<T>* p1 = a.m_pInicio;
	No<T>* p2 = b.m_pInicio;
	while(p1 != NULL)
	{
		if (p1->m_nConteudo != p2->m_nConteudo)
			return false;

		p1 = p1->m_pProx;
		p2 = p2->m_pProx;
	}
	return true;
}

template<class T>
Lista<T> operator+(const Lista<T>& a, const Lista<T>& b)
{
	Lista<T> laux(a);

	Lista<T>::copia(laux, b.m_pInicio);

	return laux;
}

template<class T>
ostream& operator<<(ostream& output, const Lista<T>& obj)
{
	output << "[";
	for (No<T>* p = obj.m_pInicio; p != NULL; p = p->prox())
	{
		output << p->conteudo();
		if (p->prox() != NULL)
			output << ", ";
	}
	output << "]";
	return output;
}

#endif