/* CPQueue.h ver 2008.30.3b
   @Author: Iker@cuteam.org
   @Revisado y Documentado: Iker@cuteam.org
   @Descripción: Cola de prioridades.

   Está prohibida la copia de cualquiera de los archivos, o de partes 
   de los mismos sin la respectiva autorizacion de sus autores.
*/

#ifndef __CPQUEUE_H__
#define __CPQUEUE_H__

#include "common.h"

//	Definicion de la clase
template<class TYPE>
class CPQueue{
protected:
	//	Estructura nodo base
	struct QueueNode
	{
		//	Argumento de nodo
		TYPE Arg;
		//	Nodo siguiente
		QueueNode *Sig;
		//	Proridad
		u_long ulPriority;
	};

	//	Contador de Items
	u_long ulCount;
	//	Primer Nodo de la cola
	QueueNode *Root;
	//	Ultimo nodo de la estructura
	QueueNode *Last;
	/*  CreateNode
		@Param: TYPE Arg, contenido del nodo actual
		@Return: Retorna el nodo recien creado
		@Descripcion: Crea un nodo y retorna su estructura.
	*/
	QueueNode *CreateNode( TYPE, u_long ulPriority);
	/*	DeleteNode
		@Descripcion: Elimina el primer nodo
	*/
	void DeleteNode( void );
	/*	pFindNode
		@Param: u_long ulPriority, Prioridad del nodo que se desea encontrar
		@Return: Retorna el Nodo con prioridad mas alta
		@Descripcion: Busca el nodo con la prioridad especificada, si no existe retorna Nulo.
	*/
	QueueNode *FindPosForNode( u_long );
	/*	ResetAll
		@Descripcion: Devuelve el estado de la estructura y sus elementos a nulo
	*/
	void ResetAll( void );
public:
	/*	AddNode
		@Param: TYPE Arg, Informacion del nodo a anadir
		@Param: u_long ulPriority, Prioridad del nodo a añadir.
		@Return: Informacion del nodo anadido
		@Descripcion: Anade un nodo nuevo a la cola segun su prioridad.
	*/
	TYPE AddNode( TYPE, u_long);
	/*	GetNode
		@Param: u_long *pulPriority, Puntero a u_long en la que se informa la
									 prioridad del nodo recibido.
		@Param: bool bDel, true para borrar el nodo, false para dejarlo
		@Return: La informacion del nodo
		@Descripcion: Devuelve la informacion del primer nodo de la cola. en caso
					  que no existan nodos retorna nulo y -1 en pulPriority.
	*/
	TYPE GetNode( u_long *, bool);
	/*	RemoveAll
		@Descripcion: Elimina todos los nodos de la cola
	*/
	void RemoveAll( void );
	/*	IsEmpty
		@Return: true si la estructura está vacia, false de lo contrario
		@Descripcion: Verifica si la estructura está vacia
	*/
	bool IsEmpty( void );
	/*	GetSize
		@Return: El número de nodos en la estructura
		@Descripcion: retorna el número de nodos en la estructura
	*/
	u_long GetSize( void );
	/*
		Constructor por defecto
	*/
	CPQueue();
	/*
		Destructor por defecto, elimina todos los nodos de la lista y destruye el objeto
	*/
	~CPQueue();
};

template<class TYPE>
CPQueue<TYPE>::CPQueue()
{
	Root = Last = NULL;
	ulCount = 0;
}

template<class TYPE>
CPQueue<TYPE>::~CPQueue()
{
	RemoveAll();
}

template<class TYPE>
void CPQueue<TYPE>::RemoveAll()
{
	while(!IsEmpty())
		DeleteNode();

	ResetAll();
}

template<class TYPE>
void CPQueue<TYPE>::ResetAll( void )
{
	Root = Last = NULL;
	ulCount = 0;
}

template<class TYPE>
typename CPQueue<TYPE>::QueueNode*
CPQueue<TYPE>::CreateNode( TYPE Arg, u_long ulPriority)
{
	QueueNode *Ret = new QueueNode;

	if (!Ret)
		return NULL;

	Ret->Arg = Arg;
	Ret->Sig = NULL;
	Ret->ulPriority = ulPriority;
	++ulCount;
	return Ret;
}

template<class TYPE>
TYPE CPQueue<TYPE>::AddNode( TYPE Arg, u_long ulPriority)
{
	QueueNode *Node = CreateNode( Arg, ulPriority);
	QueueNode *Ant;

	if (!Node)
		return NULL;

	if (!Root)
		return (Last = Root = Node)->Arg;

	if (!ulPriority) {
		Last->Sig = Node;
		return (Last = Node)->Arg;
	}
	
	if (!(Ant = FindPosForNode( ulPriority ))) {
		Node->Sig = Root;
		return (Root = Node)->Arg;
	}

	Node->Sig = Ant->Sig;
	Ant->Sig = Node;

	return Node->Sig ? Node->Arg : (Last = Node)->Arg;
}

template<class TYPE>
void CPQueue<TYPE>::DeleteNode( void )
{
	QueueNode *Aux;

	if (!Root)
		return;
	
	Aux = Root->Sig;

	delete Root;
	Root = NULL;
	
	--ulCount;

	if (!(Root = Aux)) {
		ResetAll();
		return;
	}
}

template<class TYPE>
TYPE CPQueue<TYPE>::GetNode( u_long *pulPriority, bool bDel)
{
	TYPE Arg;

	if (!Root) {
		*pulPriority = (u_long)-1;
		return NULL;
	}

	Arg = Root->Arg;
	*pulPriority = Root->ulPriority;

	if ( bDel )
		DeleteNode();

	return Arg;
}

template<class TYPE>
typename CPQueue<TYPE>::QueueNode*
CPQueue<TYPE>::FindPosForNode( u_long ulPriority )
{
	QueueNode *Ant = Root, *Sig;

	if (!Root || ulPriority < Root->ulPriority)
		return NULL;

	if (!ulPriority)
		return Last;

	Ant = Root;
	Sig = Root->Sig;


	while (Sig && Sig->ulPriority <= ulPriority) {
		Ant = Sig;
		Sig = Ant->Sig;
	}


	return Ant;
}

template<class TYPE>
bool CPQueue<TYPE>::IsEmpty( void )
{
	return !ulCount ? true : false;
}

template<class TYPE>
u_long CPQueue<TYPE>::GetSize( void )
{
	return ulCount;
}


#endif