/* CMyList.h vr 1.0.5b
   @Author: Iker@cuteam.org
   @Revisado y Documentado: Flacman@cuteam.org
   @Descripción: Lista doblemente enlazada, modificada de la estructura común por eficiencia

   Esta clase hace parte de la futura Colección de Estructuras de datos de
   ColombiaUnderground team http://www.colombiaunderground.org .
   Está prohibida la copia de cualquiera de los archivos, o de partes de los archivos sin
   hacer referencia a los autores
*/

#ifndef __CMYLIST_H__
#define __CMYLIST_H__

#include <stdlib.h>
#include <time.h>

#ifndef NULL
#define NULL 0
#endif

///Definicion de la clase
template<class TYPE>
class CMyList{
protected:
	/// Estructura nodo base
	struct ListNode
	{
		//Argumento de nodo
		TYPE Arg;
		//Nodo anterior
		ListNode *Ant;
		//Nodo siguiente
		ListNode *Sig;
	};

	///	Contador de Items
	long nCount;
	/// Nodo actual, el nodo al que se está apuntando actualmente
	ListNode *AcNode;
	/// Nodo raiz. Inicio de la estructura
	ListNode *Root;
	/// Ultimo nodo de la estructura
	ListNode *Last;
	/*  CreateNode
		@Param: TYPE Arg, contenido del nodo actual
		@Param: ListNode* Ant, Nodo anterior al que se va a crear
		@Param: ListNode* Sig, Nodo siguiente al que se va a crear
		@Return: Retorna el nodo recien creado
		@Descripcion: Crea un nodo en la lista entre los nodos pasados como parametro
	*/
	ListNode *CreateNode( TYPE, ListNode *, ListNode *);
	/*	Delete Node
		@Param: ListNode* Del Nodo a eliminar
		@Return: El nodo anterior al creado, si no hay anterior devuelve Root
		@Descripcion: Elimina el nodo pasado como parámetro
	*/
	ListNode *DeleteNode( ListNode* );
	/*	pFindNode
		@Param: bool Del, si es true elimina el nodo encontrado
		@Param: long Pos, posicion del nodo que se desea encotrar
		@Return: El nodo buscado
		@Descripcion: Busca el nodo en la posicion Pos, lo elimina si Del es true
	*/
	ListNode *pFindNode( bool, long);
	/*	ResetAll
		@Descripcion: Devuleve el estado de la estructura y sus elementos a nulo
	*/
	void ResetAll( void );
public:
	/*	AddNode
		@Param: TYPE Arg, Informacion del nodo a anadir
		@Return: Informacion del nodo anadido
		@Descripcion: Anade un nodo nuevo al final de la lista
	*/
	TYPE AddNode( TYPE );
	/*	RemoveNodeByPos
		@Param: long Pos, posicion del nodo a eliminar
		@Return: true si hay un nodo en esa posicion, false de lo contrario
		@Descripcion: Elimina el nodo de la posicion dada
	*/
	bool RemoveNodeByPos( long );
	/*	ResetCurrent
		@Descripcion: Resetea el apuntador al actual nodo a null
	*/
	void ResetCurrent( void );
	/*	SetCurrentByPos
		@Param: long Pos, Posicion del nodo que sera el actual
		@Return: true si hay un nodo en esa posicion, false de lo contrario
		@Descripcion: Setea el apuntador al nodo actual al indicado en la posicion
	*/
	bool SetCurrentByPos( long );
	/*	RemoveAll
		@Descripcion: Elimina todos los nodos de la estructura
	*/
	void RemoveAll( void );
	/*	FindNodeByPos
		@Param: long Pos, Posicion del nodo a encontrar
		@Return: La informacion del nodo en la posicion Pos
		@Descripcion: Encuentra el nodo en la posicion Pos y retorna la informacion del nodo
	*/	
	TYPE FindNodeByPos( long );
	/*	GetNext
		@Return: La informacion del nodo siguiente
		@Descripcion: Devuelve la informacion del nodo siguiente al nodo actual
	*/
	TYPE GetNext( void );
	/*	GetPrev
		@Return: La informacion del nodo anterior
		@Descripcion: Devuelve la informacion del nodo anterior al nodo actual
	*/
	TYPE GetPrev( void );
	/*	GetRoot
		@Return: La informacion del nodo Raiz
		@Descripcion: Devuelve la informacion del nodo Raiz
	*/
	TYPE GetRoot( void );
	/*	GetLast
		@Return: La informacion del nodo Last
		@Descripcion: Devuelve la informacion del nodo Last
	*/
	TYPE GetLast( void );
	/*	GetCurrentNode
		@Return: La informacion del actual nodo
		@Descripcion: Devuelve la informacion del actual nodo
	*/
	TYPE GetCurrentNode( void );
	/*	IsEmpty
		@return: true si la estructura está vacia, false de lo contrario
		@Descripcion: Verifica si la estructura está vacia
	*/
	bool IsEmpty( void );
	/*	GetCount
		@Return: El número de nodos en la estructura
		@Descripcion: retorna el número de nodos en la estructura
	*/
	long GetSize( void );
	/*	Randomize
		@param: long *Val, puntero a long en el que se retorna el index del nodo aleatorio
		@Return: La informacion del nodo
		@Descripcion: Consigue la información de un nodo cualquiera (aleatorio) de la estructura
	*/
	TYPE Randomize( long * );
	/*	InsertAfter
		@param: long Pos, posicion del nodo al que se le va a anadir insertar despuesel nuevo nodo
		@param: TYPE Arg, informacion del nuevo nodo a anadir
		@return: Informacion del nuevo nodo a anadir
		@descripcion: Inserta un nodo antes del nodo en la posicion dada
	*/
	TYPE InsertAfter( long, TYPE );
	/*	InsertBefore
		@param: long Pos, posicion del nodo al que se le va a insertar antes el nuevo nodo
		@param: TYPE Arg, informacion del nuevo nodo a anadir
		@return: Informacion del nuevo nodo a anadir
		@descripcion: Inserta un nodo despues del nodo en la posicion dada
	*/
	TYPE InsertBefore( long, TYPE );
	/*
		Constructor por defecto
	*/
	CMyList();
	/*
		Destructor por defecto, elimina todos los nodos de la lista y destruye el objeto
	*/
	~CMyList();
};

template<class TYPE>
CMyList<TYPE>::CMyList()
{
	Root = Last = AcNode = NULL;
	nCount = 0;
	srand( (unsigned int)time( NULL ) );
}

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

template<class TYPE>
void CMyList<TYPE>::RemoveAll()
{
	if (!IsEmpty())
		while ( RemoveNodeByPos( 0 ) );
	ResetAll();
}

template<class TYPE>
void CMyList<TYPE>::ResetAll( void )
{
	Root = Last = AcNode = NULL;
	nCount = 0;
}

template<class TYPE>
typename CMyList<TYPE>::ListNode*
CMyList<TYPE>::CreateNode( TYPE Arg, ListNode *Sig, ListNode *Ant)
{
	ListNode *Ret = new ListNode;

	Ret->Arg = Arg;
	Ret->Sig = Sig;
	Ret->Ant = Ant;
	nCount++;
	return Ret;
}

template<class TYPE>
TYPE CMyList<TYPE>::AddNode( TYPE Arg )
{
	if (!Root)
		return (Last = Root = CreateNode( Arg, NULL, NULL))->Arg;
	Last->Sig = CreateNode( Arg, NULL, Last);
	Last = Last->Sig;
	return Last->Arg;
}

template<class TYPE>
TYPE CMyList<TYPE>::GetNext( void )
{
	if ( AcNode ) {
		AcNode = AcNode->Sig;
		return AcNode ? AcNode->Arg : NULL;
	}
	if (!Root)
		return NULL;
	return ( AcNode = Root )->Arg;
}

template<class TYPE>
TYPE CMyList<TYPE>::GetPrev( void )
{
	if ( AcNode ) {
		AcNode = AcNode->Ant;
		return AcNode ? AcNode->Arg : NULL;
	}
	if (!Last)
		return NULL;
	return ( AcNode = Last )->Arg;
}

template<class TYPE>
typename CMyList<TYPE>::ListNode*
CMyList<TYPE>::DeleteNode( ListNode *Del )
{
	//Si el que quiere matar es root
	if (Del == Root){
		ListNode *Aux = Root->Sig;
		//Liberar memoria
		delete Root;
		Root = NULL;
		//Si hay un siguiente, el siguiente es Root, sino, Root es nulo
		Root = Aux;
		if ( Root ) {
			Root->Ant = NULL;
			--nCount;
		}
		else
			ResetAll();
		AcNode = NULL;
		return Root;
	}
	ListNode* AuxSig = Del->Sig;
	ListNode* AuxAnt = Del->Ant;
	delete Del;
	//Si siguiente AuxSig es NULL, qiuere decir que era el final de la lista
	//por lo tanto AuxAnt = al final
	AuxAnt->Sig = AuxSig;
	if ( AuxSig )
		AuxSig->Ant = AuxAnt;
	else
		Last = AuxAnt;
	--nCount;
	AcNode = NULL;
	return AuxAnt;
}

template<class TYPE>
typename CMyList<TYPE>::ListNode*
CMyList<TYPE>::pFindNode( bool Del, long Pos)
{
	register long ac = 0;
	ListNode *Act;

	if (!Root || Pos < 0 || Pos >= GetSize())
		return NULL;

	Act = Root;

	for ( ;ac < Pos; ++ac)
		Act = Act->Sig;
	
	if ( Del )
		return (ListNode *)DeleteNode( Act );

	return Act;
}

template<class TYPE>
TYPE CMyList<TYPE>::FindNodeByPos( long Pos )
{
	ListNode *Ret = pFindNode( false, Pos);
	return Ret ? Ret->Arg : NULL;
}

template<class TYPE>
bool CMyList<TYPE>::RemoveNodeByPos( long Pos )
{
	return pFindNode( true, Pos) ? true : false;
}

template<class TYPE>
TYPE CMyList<TYPE>::InsertBefore( long Pos, TYPE Arg )
{
	ListNode *Node = pFindNode( false, Pos);
	ListNode *Aux, *New;

	if (!Node)
		return NULL;
	
	New = CreateNode( Arg, Node, NULL);

	if (!(New->Ant = Aux = Node->Ant))
		return ( Root = Node->Ant = New )->Arg;

	return ( Node->Ant = Aux->Sig = New )->Arg;
}

template<class TYPE>
TYPE CMyList<TYPE>::InsertAfter( long Pos, TYPE Arg )
{
	ListNode *Node = pFindNode( false, Pos);
	ListNode *Aux, *New;

	if (!Node)
		return NULL;

	New = CreateNode( Arg, NULL, Node);
	if (!(New->Sig = Aux = Node->Sig))
		return ( Last = Node->Sig = New )->Arg;
	
	return ( Aux->Ant = Node->Sig = New )->Arg;
}

template<class TYPE>
TYPE CMyList<TYPE>::GetRoot( void )
{
	if ( Root )
		return Root->Arg;
	return NULL;
}

template<class TYPE>
TYPE CMyList<TYPE>::GetLast( void )
{
	if ( Last )
		return Last->Arg;
	return NULL;
}

template<class TYPE>
TYPE CMyList<TYPE>::GetCurrentNode( void )
{
	if ( AcNode )
		return AcNode->Arg;
	return NULL;
}

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

template<class TYPE>
void CMyList<TYPE>::ResetCurrent( void )
{
	AcNode = NULL;
}

template<class TYPE>
bool CMyList<TYPE>::SetCurrentByPos( long Pos )
{
	ListNode *Tmp = pFindNode( false, Pos);
	if (!Tmp)
		return false;
	AcNode = Tmp;
	return true;
}

template<class TYPE>
long CMyList<TYPE>::GetSize( void )
{
	return nCount;
}

template<class TYPE>
TYPE CMyList<TYPE>::Randomize( long *Val )
{
	ListNode *Ret = pFindNode( false, (*Val = (rand( )%GetSize( ))));
	if (!Ret) {
		*Val = -1;
		return NULL;
	}
	return Ret->Arg;
}

#endif