#ifndef TLISTA_H
#define TLISTA_H



#include <iostream>



template<class T>
struct dato_enlazado
{
	T dato; // El dato como tipo abstracto
	float prioridad; // Por si queremos ordenar la lista con prioridad
	dato_enlazado * sig; // Puntero al siguient
	dato_enlazado (void); // Constructor por defecto
	dato_enlazado (const T& a); // Constructor de copia
	dato_enlazado (const T& a, const float); // Constructor de copia
	dato_enlazado& operator =(const dato_enlazado& d); // Operador de asignación
	bool operator ==(const dato_enlazado& d) const; // Operador de igualdad
	bool operator !=(const dato_enlazado& d) const; // Operador de desigualdad
	//friend ostream& operator << (ostream& os, T& d);
};


//------------------------------------------------------------------------------------------------------------------------------
// NO LA BORRO PORQUE ES INTERESANTE
//------------------------------------------------------------------------------------------------------------------------------
/*template<class T>
ostream& operator << (ostream& os, T& d)
{
	os << d.dato;

	return os;
}*/


//------------------------------------------------------------------------------------------------------------------------------
// Constructor por defecto, inicializa el siguiente a nulo
// Parámetros : ninguno
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>::dato_enlazado (void) : sig(NULL), prioridad(0.0f)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor de copia
// Parámetros : T& a --> Referencia constante al dato a copiar
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>::dato_enlazado (const T& a) : dato(a), sig(NULL)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor con dato de prioridad
// Parámetros : T& a --> Referencia constante al dato a copiar
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>::dato_enlazado (const T& a, const float prior) : dato(a), sig(NULL), prioridad(prior)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de asignación
// Parámetros : const dato_enlazado& d --> Referencia constante al dato que se va a copiar
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>& dato_enlazado<T>::operator =(const dato_enlazado& d)
{
	dato = d.dato;
	sig = NULL;
	return *this;
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de igualdad, devuelve true si los datos son iguales y false en caso contrario
// Parámetros : const dato_enlazado& d
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool dato_enlazado<T>::operator ==(const dato_enlazado<T>& d) const
{
	return dato == d.dato;
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de desigualdad, devuelve true si los datos son distintos y false si son iguales
// Parámetros : const dato_enlazado
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool dato_enlazado<T>::operator !=(const dato_enlazado<T>& d) const
{
	return dato != d.dato;
}


//------------------------------------------------------------------------------------------------------------------------------
template<class T> class iterador_lista;
template<class T> class iterador_prioridad;
//------------------------------------------------------------------------------------------------------------------------------

template<class T>
class lista
{
	protected :
		float Prioridad (const unsigned long); // Devuelve la prioridad del elemento seleccionado
	public :
	dato_enlazado<T> *cab;
	//dato_enlazado<T> *cola;
	dato_enlazado<T> *selec; // Puntero al dato actualmente 'encontrado', 
							 // aumenta la eficiencia en la busqueda de datos consecutivos
	dato_enlazado<T> *cola; // Esto es temporal, hay que borrarlo
	
public:
	lista (void); // Constructor vacio
	virtual ~lista (void); // Destructor
	lista (lista<T>&); // Constructor de copia
	bool operator == (lista<T>&) const; // Operador de comparación
	bool operator != (lista<T>&) const; // Idem
	virtual bool Inserta (const T& a); // Inserta un dato en la lista
	virtual bool InsertaPrioridad (const T&, const float, const bool); // Inserta manteniendo orden
	virtual bool Busca (const T& a);
	virtual bool Borra (const T& a);   // Borra a si existe
	virtual bool BorraLista (void);   // Borra todos los elementos de la lista
	virtual bool Cab (void); // Situa el seleccionado al principio de la lista
	virtual bool Sig (void);
	virtual T GetCab (void); // Extrae la cabeza de la lista
	virtual T GetCola (void);
	virtual bool BorraCola (void); //borra la cola
	virtual unsigned long NDatos (void) const; // Devuelve el número de datos en la lista
	virtual unsigned long NPrioridadDatos (void) const; //
	friend class iterador_lista<T>;
	friend class iterador_prioridad<T>;
	// A partir de aqui las funciones son sólo para depurar el código
	friend std::ostream& operator << (std::ostream& os, lista<T>& d);
};


//------------------------------------------------------------------------------------------------------------------------------
// PARA DEPURAR EL CÓDIGO, PERO ES INTERESANTE
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
std::ostream& operator << (std::ostream& os, lista<T>& l)
{
	dato_enlazado<T> * tmp = l.cab;

	while (tmp)
	{
		cout << (*tmp).dato;
		tmp = tmp->sig;
	}

	return os;
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor por defecto
// Parámetros : Ninguno
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
lista<T>::lista (void) : cab(NULL), selec(NULL), cola(NULL)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor de copia
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
lista<T>::lista (lista<T>& l) : cab(NULL), selec(NULL), cola(NULL)
{
	dato_enlazado<T> *tmp = l.cab;
	dato_enlazado<T> *nuevo; // Apuntador a la memoria que se va a reservar

	while (tmp != NULL)
	{
		nuevo = new dato_enlazado<T> (*tmp); // Reservo espacio para el nuevo dato
		if (cola == NULL) cola = nuevo;
		nuevo->sig = cab; // El siguiente del nuevo dato será la cabeza de la lista	
		selec = cab = nuevo; // Ahora hago apuntar la cabeza al nuevo dato

		tmp = tmp->sig;
	}
}


//------------------------------------------------------------------------------------------------------------------------------
// Destructor por defecto
// Parámetros : Ninguno
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
lista<T>::~lista (void)
{
	//BorraLista ();
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de comparación. Dos listas son iguales si contienen los mismos elementos aunque no estén en el mismo orden
// Parámetros --> const lista<T>& l : Lista con la que se compara
// Salida --> 'true' si las dos listas contienen los mismos elementos
//			  'false' en cualquier otro caso
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::operator == (lista<T>& l) const
{
	if (NDatos () != l.NDatos ()) return false; // Si no tienen el mismo número de datos no pueden ser iguales

	//lista<T> tmp = *this;
	lista<T> tmpl = l;
	//iterador_lista<T> iterador (tmp); // Creo un iterador sobre esta lista
	//T* dato;

	//while (dato = iterador ())
		//if (!tmpl.Busca(*dato)) return false; // Si uno de los datos de la primera lista no lo encuentro en la segunda no son iguales

	dato_enlazado<T> *tmpd = cab;

	while (tmpd != NULL)
	{
		if (tmpl.Busca (tmpd->dato) == false) return false;
		tmpd = tmpd->sig;
	}

	return true; // si todos los de la primera están en la segunda y tienen el mismo tamaño es que son iguales
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de desigualdad
// Parámetros --> const lista<T>& l : Lista con la que se compara
// Salida --> 'true' si las listas son distintas
//			  'false' en caso contrario
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::operator != (lista<T>& l) const
{
	if (*this == l) return false;

	return true;
}


//------------------------------------------------------------------------------------------------------------------------------
// Devuelve la prioridad en la posición i-ésima
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
float lista<T>::Prioridad (const unsigned long i)
{
	unsigned long cont = 0L; // Inicializo el contador de posiciones

	selec = cab; //Inicio la búsqueda desde la cabeza
	while (i != cont && selec != NULL) // Mientras no haya encontrado la posición y me queden elementos
	{
		selec = selec->sig; // Paso al siguiente
		cont++; // e incremento en uno el contador
	}

	return selec->prioridad;
}


//------------------------------------------------------------------------------------------------------------------------------
// Inserta un nuevo elemento en la lista. El nuevo elemento se inserta en la cabeza
// Parámetros : a --> el dato que hay que añadir a la lista
// Salida : 'true' si el dato se ha podido insertar en la lista
//			'false' en caso contrario
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Inserta (const T& a)
{
	
	if (cola == NULL)
	{
		selec = cab = cola = new dato_enlazado<T> (a);
		return true;
	}
	else
	{
		if (!(cola->sig = new dato_enlazado<T> (a))) // Reservo espacio para el nuevo dato
			return false;
		else
		{
			cola = cola->sig;
			selec = cola; // Ahora hago apuntar la cabeza al nuevo dato
			return true;
		}
	}
}


//------------------------------------------------------------------------------------------------------------------------------
// Inserta manteniendo orden
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::InsertaPrioridad (const T& a, const float prior, const bool borra)
{
	dato_enlazado<T>* tmp = cola;

	selec = new dato_enlazado<T> (a, prior); // Creo el nodo a insertar

	if (cab == NULL) // No hay ningún dato en la lista
	{
		cab = cola = selec;
		return true;
	}
	// Tengo mas de uno en la lista y el que voy a insertar es el menor
	if (cola->prioridad >= prior)
	{
		if (cola->dato != a)
		{
			selec->sig = cola;
			cola = selec;
		}
		else if (cola->dato == a && borra)
		{
			dato_enlazado<T>* tmp_selec = cola;
			cola = cola->sig;
			delete tmp_selec;
		}
		else delete selec;
		return true;
	}
	else
	{
		while (tmp != cab) // Mientras no llegue a la cabeza
		{
			if (tmp->sig->prioridad >= prior) // inserto antes de tmp->sig
			{
				if (a != tmp->sig->dato) // Si no está ya presente en la lista
				{
					selec->sig = tmp->sig; // lo inserto
					tmp->sig = selec;
				}
				else if (a == tmp->sig->dato && borra) // Si hay que borrarlo
				{
					dato_enlazado<T>* tmp_selec = tmp->sig;
					if (tmp->sig == cab) cab = tmp;
					tmp->sig = tmp->sig->sig;
					delete tmp_selec;
				}
				else // si está presente
				{
					delete selec; // Libero la memoria que había reservado
				}
				return true;
			}
			tmp = tmp->sig;
		}
		if ((tmp == cab) && (a != cab->dato)) // Si llego a la cabeza sin encontrar ninguno en la lista con prioridad mayor
		{				// es porque el que voy a insertar tiene la mayor prioridad
			cab->sig = selec;
			cab = selec;
			return true;
		}
		else
		{
			delete selec;
			selec = cab;
		}
	}
	return false;
}



//------------------------------------------------------------------------------------------------------------------------------
// Busca un elemento en la lista y deja el puntero selec apuntando a él si lo encuentra
// Parámetros : const T& a --> Referencia al dato que se está buscando
// Salida : true si el dato efectivamente es encontrado
//			false si el dato no está en la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Busca (const T& a)
{
	dato_enlazado<T> *tmp; // Puntero de reserva

	if (!cab) return false; // Si no hay ningún dato no hay donde buscar

	if (selec && selec->dato != a)
	{
		tmp = selec; // Me guardo el actualmente seleccionado
		selec = selec->sig; // Iniciaré la búsqueda a partir del dato siguiente
	}
	else
	{
		selec = cab; // Iniciaré la busqueda desde la cabeza si no
		//tmp = NULL;
	}

	while (selec != NULL && selec->dato != a)
		selec = selec->sig; // lo busco a partir de la posición original hacia el final

	if (!selec) // Si antes habia uno seleccionado
	{
		selec = cab; // Iniciaré la búsqueda desde la cabeza
		while (selec != tmp && selec->dato != a) selec = selec->sig;
	}
	
	if (selec && selec->dato == a) return true;
	return false;
}


//------------------------------------------------------------------------------------------------------------------------------
// Borra el elemento indicado de la lista
// Parámetros : const T& a --> Referencia al elemento a borrar
// Salida --> true si el elemento ha sido encontrado y borrado
//			  false si no se ha encontrado el elemento
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Borra (const T& a)
{
	dato_enlazado<T> *tmp = cab; // Me guardo la posición de lo que quiero borrar

	if (!Busca (a)) return false; // Si no lo encuentra devuelve false

	if (selec == cab) // Si lo que quiero borrar es la cabeza
	{
		cab = cab->sig; // Adelanto la cabeza
		delete selec; // Borro el dato
		selec = cab; // Hago apuntar el actual a la nueva cabeza
	}
	else
	{
		while (tmp->sig->dato != a) tmp = tmp->sig; // Encuentro el anterior al que quiero borrar
		if (tmp->sig == cola) cola = tmp;

		tmp->sig = selec->sig; // Saco el que voy a borrar fuera de la lista
		delete selec; // Borro el dato
		if (!(selec = tmp->sig)) selec = cab; // Si al avanzar el seleccionado llego al final, inicio desde la cabeza
	}

	return true;
}




//------------------------------------------------------------------------------------------------------------------------------
// Elimina todos los elementos de lista
// Parámetros : ninguno
// Salida : Si la lista ha sido efectivamente borrada true
//			false en caso contrario
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::BorraLista (void)
{
	while (cab)
	{
		selec = cab;
		if (!Borra (selec->dato)) return false; // Borro siempre la cabeza
	}
	return true;
}


//------------------------------------------------------------------------------------------------------------------------------
// Coloca el seleccionado al inicio de la lista
// Parémetros --> ninguno
// Salida --> 'true' si efectivamente se ha colocado al inicio de la lista
//			  'false' si ha habido algún error y el seleccionado no apunta al inicio de la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Cab (void)
{
	if (cab)
	{
		selec = cab;
		return true;
	}
	return false;
}


//------------------------------------------------------------------------------------------------------------------------------
// Avanza el seleccionado hasta la siguiente posición, el siguiente del último es de nuevo la cabeza
// Parámetros : ninguno
// Salida : 'true' si se inicia desde la cabeza al avanzar
//			'false' en cualquier otro caso
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Sig (void)
{
	if (!(selec = selec->sig))
	{
		selec = cab; // Avanzo el seleccionado hasta el siguiente, y si me paso, lo llevo
		return true; // de nuevo a la cabeza
	}
	return false;
}


//------------------------------------------------------------------------------------------------------------------------------
// Extrae la cabeza de la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T lista<T>::GetCab (void)
{
	if (cab->dato == NULL) return NULL; // Si no hay nada en la lista devuelve NULL
	
		else	return cab->dato;
}


//------------------------------------------------------------------------------------------------------------------------------
// Extrae la cola de la lista  ///ACABAAAR melon
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T lista<T>::GetCola (void)
{
	
	if (cola->dato == NULL) return NULL; // Si no hay nada en la lista devuelve NULL
	
		else	return cola->dato;
	
}
//------------------------------------------------------------------------------------------------------------------------------
// Extrae y borra la cola de la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::BorraCola (void)
{
	/*dato_enlazado<T>* tmp = cab; // Nos situamos incialmente en la cabeza


	if (cab == NULL) return false; // Si no hay nada en la lista devuelve NULL
	if (cab == cola) // Si solo tenemos un elemento
	{
		delete cab;
		cab = cola = selec = NULL;
		return true;
	}
	else
	{
		while (tmp->sig != cola)
			tmp = tmp->sig;
		delete cola;
		cola = tmp;
		cola->sig = NULL;
		selec = cab;
		return true;
	}*/
	return Borra (cola->dato);
}

//------------------------------------------------------------------------------------------------------------------------------
// Devuelve el número de datos actuales en la lista
// Parámetros --> Ninguno
// Salida --> int : el número de datos en la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
unsigned long lista<T>::NDatos (void) const
{
	unsigned long nDatos = 0; // Para contar el número de datos de la lista
	/*lista<T> tmp = *this;
	/iterador_lista<T>  iterador(tmp); // Creo un iterador sobre la lista
	T * dato;

	while (dato = iterador ())
		nDatos++;*/

	dato_enlazado<T> * tmp = cab;

	while (tmp != NULL)
	{
		tmp = tmp->sig;
		nDatos++;
	}

	return nDatos;
}


template<class T>
unsigned long lista<T>::NPrioridadDatos (void) const
{
	unsigned nDatos = 0;

	dato_enlazado<T>* tmp = cola;

	while (tmp != NULL)
	{
		tmp = tmp->sig;
		nDatos++;
	}

	return nDatos;
}


//------------------------------------------------------------------------------------------------------------------------------
// Esta es la clase iterador, recorre la lista desde la cabeza a la cola devolviendo punteros a los datos
//------------------------------------------------------------------------------------------------------------------------------

template<class T>
class iterador_lista
{
	private:
		dato_enlazado<T> *iterador; // Elemento de la lista a devolver
		lista<T> *lista_iterada; // Puntero a la lista sobre la que se está iterando

	public:
		iterador_lista (lista<T>&); // Constructor con una lista
		T * const operator () (void); // Operador de iteracion
		T * const IteradorCircular (void); // Igual que el anterior, pero cuando llega al final, recomienza
};


//------------------------------------------------------------------------------------------------------------------------------
// Constructor con un lista
// Parámetros --> lista<T>& l : Referencia a la lista sobre la que se iterará
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
iterador_lista<T>::iterador_lista (lista<T>& l) : lista_iterada (&l), iterador(l.cab)
{
	 // Hago que el primer elemento de iteración sea la cabeza
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador () que es el que hace las funciones de iterador
// Párámetros --> Ninguno
// Salida --> T * const : un puntero constante al elemento devuelto por el iterador
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T * const iterador_lista<T>::operator () (void)
{
	T * tmp = &iterador->dato;

	if (!iterador) iterador = lista_iterada->cab; // Si llegamos al final de la lista, dejamos el iterador 
	else iterador = iterador->sig;					// al inicio de la lista.

	return tmp;
}


//------------------------------------------------------------------------------------------------------------------------------
// Igual que el anterior, pero cuando llega al final de la lista empieza desde el principio
// Parametros --> Ninguno
// Salida T * const : un puntero constante al elemento devuelto
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T * const iterador_lista<T>::IteradorCircular (void)
{
	if (iterador == NULL) return NULL;
	else
	{
		iterador = iterador->sig;
		if (!iterador) iterador = lista_iterada->cab;

		return &iterador->dato;
	}
}


//------------------------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
class iterador_prioridad
{
	private:
		dato_enlazado<T> *iterador; // Elemento de la lista a devolver
		lista<T> *lista_iterada; // Puntero a la lista sobre la que se está iterando

	public:
		iterador_prioridad (lista<T>&); // Constructor con una lista
		T * const operator () (void); // Operador de iteracion
};


//------------------------------------------------------------------------------------------------------------------------------
// Constructor con un lista
// Parámetros --> lista<T>& l : Referencia a la lista sobre la que se iterará
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
iterador_prioridad<T>::iterador_prioridad (lista<T>& l) : lista_iterada (&l), iterador(l.cola)
{
	 // Hago que el primer elemento de iteración sea la cabeza
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador () que es el que hace las funciones de iterador
// Párámetros --> Ninguno
// Salida --> T * const : un puntero constante al elemento devuelto por el iterador
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T * const iterador_prioridad<T>::operator () (void)
{
	T * tmp = &iterador->dato;

	if (!iterador) iterador = lista_iterada->cola; // Si llegamos al final de la lista, dejamos el iterador 
	else iterador = iterador->sig;					// al inicio de la lista.

	return tmp;
}




#endif