#ifndef __MBStaticList

#define __MBStaticList

#include <stdlib.h>
#include <memory.h>
#include "MBStaticListNode.h"

#define MBSL_FOREACH(list, iterator) for (iterator = list.First() ; iterator != -1 ; iterator = list.Next(iterator))
#define MBSL_ELEMENT(list, iterator, pointer) list.Get(iterator, pointer)



template <class T>
class MBStaticList
{
public:
// Constructores/Destructores
                       MBStaticList         ();
                      ~MBStaticList         ();

// Constructor de copia
                      MBStaticList          (const MBStaticList<T>& slOther);

// Inicializacion / Desinicializacion
int                   Init                  (int iDefaultSize=1);
int                   Shutdown              ();
int                   Reset                 ();

// Operadores
MBStaticList<T>&      operator=             (const MBStaticList<T>& slOther);


// Inserciones
int                   InsertHead            (const T& tData);
int                   InsertTail            (const T& tData);
int                   InsertBefore          (const int iID, const T& tData);
int                   InsertAfter           (const int iID, const T& tData);


// Borrado
int                   DeleteHead            ();
int                   DeleteTail            ();
int                   Delete                (const int iID);

// Peticion de datos
int                   GetHead               (T& tData)  const;
int                   GetTail               (T& tData)  const ;
int                   Get                   (const int iID, T& tData) const;
int                   Get                   (const int iID, T*& tData)const;

// Extraccion (Peticion de datos + borrado)
int                   ExtractHead           (T& tData);
int                   ExtractTail           (T& tData);
int                   Extract               (const int iID, T& tData);

// Operadores para iteracion
int                   First                 ()  const;
int                   Last                  ()  const;
int                   Next                  (const int iID) const;
int                   Previous              (const int iID) const;	

// Actualizacion de datos
int                   SetData               (const int iID, const T& tData);

// Accesores
int                   GetNumberElements     ()  const ;
bool                  GetValidity           (const int iID) const;

// Busqueda         
bool                  Has                   (const T& tData);
int                   Find                  (const T& tData);


protected:

// Insercion / Borrado
int                   InsertNode            (const T& tData);
int                   DiscardNode           (const int iID);

// Linkado de nodos
int                   Link                  (const int iFirstNode, const int iSecondNode);
int                   Link                  (const int iFirstNode, const int iSecondNode, const int iThirdNode);

// Expansion de lista
int                   Expand                (int iElements);

// Validez de datos
int                   SetValidity           (int iID, bool bValidity);	

// Datos
int                   m_iMaxElements;
int                   m_iElements;
int                   m_iFirstElement;
int                   m_iLastElement;
int                   m_iFirstFreeElement;
MBStaticListNode<T>*  m_ptNodes;
};


// Nombre      : MBStaticList<T>::MBStaticList()
// Parametros  : No
// Retorno     : No
// Descripcion : Constructor de la clase
template <class T>
MBStaticList<T>::MBStaticList()
{
	m_iMaxElements			=0;
	m_iElements				  =0;
	
	m_iFirstElement			=-1;
	m_iLastElement			=-1;
	m_iFirstFreeElement	=-1;

	m_ptNodes				    =NULL;

}

// Nombre      : MBStaticList<T>::~MBStaticList()
// Parametros  : No
// Retorno     : No
// Descripcion : Destructor de la clase
template <class T>
MBStaticList<T>::~MBStaticList()
{
	Shutdown();
}


// Nombre      : MBStaticList<T>::Init()
// Parametros  : int iMaxElements, int iQuantumSize
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Inicializa la lista estatica con el tamaņo pasado como parametro y como
//				 tamaņo de cuanto el pasado como parametro
template <class T> 
int MBStaticList<T>::Init(int iDefaultSize)
{
	// Chapamos
	Shutdown();

	// Buscamos memoria para guardar los datos
	m_ptNodes=new MBStaticListNode<T>[iDefaultSize];		
	if (!m_ptNodes)
	{	
		
		return (-1);
	}		
	
	// Inicializamos datos
	m_iMaxElements			=iDefaultSize;
	m_iElements				  =0;
	
	m_iFirstElement			=-1;
	m_iLastElement			=-1;
	m_iFirstFreeElement =0;

	// Reseteamos la lista de nodos
	Reset();


	return (0);
}

// Nombre      : MBStaticList<T>::Reset()
// Parametros  : No
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Resetea la lista
template <class T>
int MBStaticList<T>::Reset()
{
	int i;

	// Hacemos el linkaje de todos los nodes
	Link(-1, 0);
	for (i=1 ; i<m_iMaxElements-1 ; i++)
	{
		Link(i-1, i);
	}
	Link(m_iMaxElements-2, m_iMaxElements-1, -1);

	for (i=0 ; i<m_iMaxElements ; i++)
	{
		// Invalidamos el dato
		SetValidity(i, false);
	}

	m_iFirstElement			=-1;
	m_iLastElement			=-1;
	m_iFirstFreeElement		=0;
	m_iElements				=0;


	return (0);
}


// Nombre      : MBStaticList<T>::Shutdown()
// Parametros  : No
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Cierra la lista
template <class T>
int MBStaticList<T>::Shutdown()
{	
	if (m_ptNodes)
	{
		delete[] m_ptNodes;
		m_ptNodes=NULL;
	}

	m_iMaxElements			=0;
	m_iElements				=0;
	
	m_iFirstElement			=-1;
	m_iLastElement			=-1;
	m_iFirstFreeElement		=-1;

	return (0);
}

// Nombre      : MBStaticList<T>::InsertHead()
// Parametros  : T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Pone el dato pasado como parametro al principio de la lista
template <class T>
int MBStaticList<T>::InsertHead(const T& tData)
{
	int iNewElementID;

	// Insertamos el elemento en la lista
	iNewElementID=InsertNode(tData);

	// Chequeamos que se haya podido insertar
	if (iNewElementID==-1)
	{
		return (-1);
	}

	// Linkamos el nuevo nodo para que sea el nuevo primero	
	Link(-1, iNewElementID, m_iFirstElement);

	// El nuevo elemento es el primero de la lista
	m_iFirstElement=iNewElementID;

	// Chequeo de caso particular
	if (m_iElements==1)
	{
		m_iLastElement=m_iFirstElement;
	}

	return (iNewElementID);
}

// Nombre      : MBStaticList<T>::InsertTail()
// Parametros  : T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Insera un nodo al final de la lista
template <class T>
int MBStaticList<T>::InsertTail(const T& tData)
{
	int iNewElementID;

  // Insertamos el elemento en la lista
	iNewElementID=InsertNode(tData);

	// Chequeamos que se haya podido insertar
	if (iNewElementID==-1)
	{
		return (-1);
	}


	// Linkamos el nuevo nodo para que sea el nuevo primero	
	Link(m_iLastElement, iNewElementID, -1);

	// El nuevo elemento es el primero de la lista
	m_iLastElement=iNewElementID;

	// Chequeo de caso particular
	if (m_iElements==1)
	{
		m_iFirstElement=m_iLastElement;
	}

	return (iNewElementID);
}


template <class T>
int MBStaticList<T>::InsertBefore(const int iID, const T& tData)
{
  int iNewElementID;

  // inserting before -1 == inserting tail
  if (iID == -1)
  {
    return InsertTail(tData);
  }
  
	// Insertamos el elemento en la lista
	iNewElementID=InsertNode(tData);

	// Chequeamos que se haya podido insertar
	if (iNewElementID==-1)
	{
		return (-1);
	}


	// Linkamos el nuevo nodo para que sea el nuevo primero	
	Link(Previous(iID), iNewElementID, iID);

	// El nuevo elemento es el primero de la lista
  if (m_iFirstElement==iID)
  {
    m_iFirstElement=iNewElementID;
  }
  
	return (iNewElementID);
}
              

// Nombre      : 
// Parametros  : 
// Retorno     : 
// Descripcion : 
template <class T>
int MBStaticList<T>::InsertAfter(const int iID, const T& tData)
{
  int iNewElementID;

  // inserting after -1 == inserting head
  if (iID == -1)
  {
    return InsertHead(tData);
  }
  

	// Insertamos el elemento en la lista
	iNewElementID=InsertNode(tData);

	// Chequeamos que se haya podido insertar
	if (iNewElementID==-1)
	{
		return (-1);
	}


	// Linkamos el nuevo nodo para que sea el nuevo primero	
	Link(iID, iNewElementID, Next(iID));

	// El nuevo elemento es el primero de la lista
  if (m_iLastElement==iID)
  {
    m_iLastElement=iNewElementID;
  }
	
	return (iNewElementID);
}

// Nombre      : MBStaticList<T>::DeleteHead()
// Parametros  : No
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Borra la cabeza de la lista
template <class T>
int MBStaticList<T>::DeleteHead()
{
	Delete(m_iFirstElement);
	return (0);
}

// Nombre      : MBStaticList<T>::DeleteTail()
// Parametros  : No
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Borra el final de la lista
template <class T>
int MBStaticList<T>::DeleteTail()
{
	Delete(m_iLastElement);
	return (0);
}

// Nombre      : MBStaticList<T>::Delete()
// Parametros  : int iID
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Borra el nodo de identificador iID
template <class T>
int	MBStaticList<T>::Delete(const int iID)
{
	DiscardNode(iID);
	
	return (0);
}

// Nombre      : MBStaticList<T>::GetHead()
// Parametros  : T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Devuelve el primer elemento de la lista
template <class T>
int	MBStaticList<T>::GetHead(T& tData) const
{
	return ((Get(m_iFirstElement, tData)));	
}

// Nombre      : MBStaticList<T>::GetTail()
// Parametros  : T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Devuelve el ultimo elemento de la lista
template <class T>
int	MBStaticList<T>::GetTail(T& tData) const
{
	return ((Get(m_iLastElement, tData)));	
}


// Nombre      : MBStaticList<T>::Get()
// Parametros  : int iID, T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Devuelve el elemento con el ID pasado como parametro
template <class T>
int MBStaticList<T>::Get(const int iID, T& tData) const
{
	if (iID!=-1 && GetValidity(iID))
	{
		tData=m_ptNodes[iID].m_tData;
		return (0);
	}
	else
	{
		return (-1);
	}
}

// Nombre      : MBStaticList<T>::Get()
// Parametros  : int iID, T*& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Devuelve el puntero al dato de id pasado como parametro
template <class T>
int MBStaticList<T>::Get(const int iID, T*& tData) const
{
	if (iID!=-1 && GetValidity(iID))
	{
		tData=&m_ptNodes[iID].m_tData;
		return (0);
	}
	else
	{
		return (-1);
	}
}

// Nombre      : MBStaticList<T>::Extract()
// Parametros  : int iID, T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Extrae el elemento de ID iID
template <class T>
int	MBStaticList<T>::Extract(const int iID, T& tData) 
{
	tData=m_ptNodes[iID].m_tData;

	Delete(iID);

	return (0);
}

// Nombre      : MBStaticList<T>::ExtractHead()
// Parametros  : No
// Retorno     : int
// Descripcion : Extrae el primer elemnento de la lista
template <class T>
int	MBStaticList<T>::ExtractHead(T& tData)
{
	if (m_iElements==0)
	{
		return (-1);
	}
	
	tData=m_ptNodes[m_iFirstElement].m_tData;

	DeleteHead();

	return (0);
}

// Nombre      : MBStaticList<T>::ExtractTail()
// Parametros  : T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Extrae el ultimo elemento de la lista
template <class T>
int	MBStaticList<T>::ExtractTail(T& tData)
{
	if (m_iElements==0)
	{
		return (-1);
	}

	tData=m_ptNodes[m_iLastElement].m_tData;

	DeleteTail();

	return (0);
}

// Nombre      : MBStaticList<T>::DiscardNode()
// Parametros  : int iNode
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Pone el nodo en la lista de nodos libres
template <class T>
int MBStaticList<T>::DiscardNode(const int iID)
{
	if (!m_iElements || iID==-1)
	{
		return (-1);
	}

	// Chequeo para usuarios incautos
	if (!GetValidity(iID))
	{
		return (-1);
	}

	// Invalidamos el dato
	SetValidity(iID, false);
	
	// Linkamos anterior con siguient
  int iPrevious = Previous(iID);
  int iNext = Next(iID);
	Link(iPrevious, iNext);

	// Si es el primero o el ultimo. Ajustamos
	if (iID==m_iFirstElement)
	{
		m_iFirstElement=Next(iID);		
	}

	if (iID==m_iLastElement)
	{
		m_iLastElement=Previous(iID);				
	}
	
	// Ajustamos la lista de libres para que el nodo sea el primer nodo libre
	Link(-1, iID, m_iFirstFreeElement);

	// Este elemento sera el nuevo primer elemento libre
	m_iFirstFreeElement=iID;

	// Hay un elemento menos en la lista
	m_iElements--;

	return (0);
}

// Nombre      : MBStaticList<T>::Link()
// Parametros  : int iFirstNode, int iSecondNode
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Linka los nodos pasados como parametro en el orden iFirstNode, iSecondNode
template <class T>
int MBStaticList<T>::Link(const int iFirstNode, const int iSecondNode)
{
	if (iFirstNode!=-1)
	{
		m_ptNodes[iFirstNode].m_iNext=iSecondNode;
	}

	if (iSecondNode!=-1)
	{
		m_ptNodes[iSecondNode].m_iPrevious=iFirstNode;
	}

	return (0);
}

// Nombre      : MBStaticList<T>::Link()
// Parametros  : int iFirstNode, int iSecondNode, int iThirdNode
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Linka los tres nodos pasados como parametro en el orden iFirstNode, iSecondNode, iThirdNode
template <class T>
int MBStaticList<T>::Link(const int iFirstNode, const int iSecondNode, const int iThirdNode)
{
	Link(iFirstNode, iSecondNode);
	Link(iSecondNode, iThirdNode);

	return (0);
}

// Nombre      : MBStaticList<T>::Next()
// Parametros  : int iID
// Retorno     : int
// Descripcion : Devuelve el ID del nodo siguiente al pasado como parametro
template <class T>
int MBStaticList<T>::Next(const int iID) const
{
	return (m_ptNodes[iID].m_iNext);
}

// Nombre      : MBStaticList<T>::First()
// Parametros  : No
// Retorno     : int 
// Descripcion : devuelve indice del primer elemento
template <class T>
int MBStaticList<T>::First() const
{
	return (m_iFirstElement);
}

// Nombre      : MBStaticList<T>::First()
// Parametros  : No
// Retorno     : int 
// Descripcion : devuelve id del ultimo elemento
template <class T>
int	MBStaticList<T>::Last() const
{
	return (m_iLastElement);
}

// Nombre      : MBStaticList<T>::Previous()
// Parametros  : int iID
// Retorno     : int
// Descripcion : Devuelve el ID del nodo previo al pasado como parametro
template <class T>
int MBStaticList<T>::Previous(const int iID) const
{
	return (m_ptNodes[iID].m_iPrevious);
}

// Nombre      : MBStaticList<T>::GetNumberElements()
// Parametros  : No
// Retorno     : i con el numero de elementos
// Descripcion : Devuelve el numero de elementos de la lista
template <class T>
int MBStaticList<T>::GetNumberElements() const
{
	return (m_iElements);
}

// Nombre      : MBStaticList<T>::SetData()
// Parametros  : int iID, T& tData
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Pone el dato en el elemento de ID iID
template <class T>
int MBStaticList<T>::SetData(const int iID, const T& tData)
{
	if (iID==-1)
	{
		return (-1);
	}
	else
	{
		m_ptNodes[iID].m_tData=tData;
	}
	return (0);
}

// Nombre      : MBStaticList<T>::InsertNode()
// Parametros  : T& tData
// Retorno     : 0 o pos: ID del nuevo nodo  ; -1: ERROR
// Descripcion : Crea un nuevo nodo, donde pone el dato
template <class T>
int MBStaticList<T>::InsertNode(const T& tData)
{
	int iNewElementID;

  assert(m_ptNodes);

	// Comprobacion de que no nos pasamos de espacio
	if (m_iElements==m_iMaxElements)
	{
		// No hay espacio libre. Lo buscamos		
		if (Expand(m_iElements)==-1)
		{
			return (-1);
		}				
	}

	// Hacemos que el proximo nodo libre sea el primero
	Link(-1 , Next(m_iFirstFreeElement));

	// Hacemos que el primero libre sea el siguiente al que habia
	iNewElementID=m_iFirstFreeElement;
	m_iFirstFreeElement=Next(m_iFirstFreeElement);
	Link(-1, m_iFirstFreeElement);

	// Ponemos el dato en el primer elemento libre
	SetData(iNewElementID, tData);

	// Validamos el dato
	SetValidity(iNewElementID, true);

	// Incrementamos el numero de elementos de la lista
	m_iElements++;

	return (iNewElementID);
}



// Nombre      : MBStaticList<T>::SetValidity()
// Parametros  : int iID, bool bValidity
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Pone la validez de un nodo
template <class T>
int MBStaticList<T>::SetValidity(const int iID, const bool bValidity)
{
	m_ptNodes[iID].m_bValid=bValidity;
	return (0);
}

// Nombre      : MBStaticList<T>::GetValidity()
// Parametros  : int iID
// Retorno     : bool
// Descripcion : Devuelve la validez del dato de un nodo
template <class T>
bool MBStaticList<T>::GetValidity(const int iID) const
{
	return (m_ptNodes[iID].m_bValid);
}

// Nombre      : MBStaticList<T>::Expand()
// Parametros  : int iElements
// Retorno     : 0: OK ; -1: ERROR
// Descripcion : Expanda la lista hasta ocupar iElements mas
template <class T>
int MBStaticList<T>::Expand(const int iElements)
{
	int i;
	MBStaticListNode<T>* pNewNodes;
	MBStaticListNode<T>* pOldNodes;

	// Buscamos memoria para los nuevos nodos y los antiguos a falta de un realloc
	pNewNodes=new MBStaticListNode<T>[m_iMaxElements+iElements];
	if (!pNewNodes)
	{
		return (-1);
	}

	// Copiamos los nodos
	//memcpy(pNewNodes, m_ptNodes, sizeof(MBStaticListNode<T>)*m_iMaxElements);
	for (i=0 ; i<m_iMaxElements ; i++)
	{
		pNewNodes[i]=m_ptNodes[i];
	}

	// Ponemos nueva lista
	pOldNodes=m_ptNodes;
	m_ptNodes=pNewNodes;

	// Inicializamos los nuevos nodos
	for (i=m_iMaxElements ; i<m_iMaxElements+iElements ; i++)
	{
		// Invalidamos el dato
		SetValidity(i, false);				
	}	

	// Ahora hay que linkar nodos.	
	//for (i=m_iMaxElements+1 ; i<m_iMaxElements+iElements-1 ; i++)
	for (i=m_iMaxElements ; i<m_iMaxElements+iElements-1 ; i++)
	{
		Link(i,i+1);
	}

	// Ajuste de primer y ultimo nodos
	if (m_iFirstFreeElement==-1)
	{
		// No habia elementos libres
		Link(-1, m_iMaxElements);
		Link(m_iMaxElements+iElements-1, -1);
		m_iFirstFreeElement=m_iMaxElements;
	}
	else
	{
		// Introducimos los nuevos en medio de la lista de libres
		Link(m_iMaxElements+iElements-1, Next(m_iFirstFreeElement));		
		Link(m_iFirstFreeElement, m_iMaxElements);
		Link(m_iMaxElements+iElements-1, -1);
	}
		
	// Ajustamos numero maximo de elmentos
	m_iMaxElements+=iElements;

	// Borramos antigua lista. 
	delete [] pOldNodes;
	
	
	return (0);
}

// Nombre      : MBStaticList<T>::MBStaticList()
// Parametros  : MBStaticList<T>& const slOther
// Retorno     : No
// Descripcion : Constructor de copia
template <class T>
MBStaticList<T>::MBStaticList(const MBStaticList<T>& slOther)
{
  int i;
	// Inicializamos del mismo tamaņo
	Init(slOther.m_iMaxElements, slOther.m_iQuantumSize);
	
	// Copiamos datos nivel fisico, para que los ids se conserven
	for (i=0 ; i<slOther.m_iMaxElements ; i++)
	{
    if (slOther.m_ptNodes[i].m_bValid)
    {
		  m_ptNodes[i]=slOther.m_ptNodes[i];
    }
	}

	// Copiamos estado
	m_iElements=slOther.m_iElements;
	m_iFirstElement=slOther.m_iFirstElement;
	m_iLastElement=slOther.m_iLastElement;
	m_iFirstFreeElement=slOther.m_iFirstFreeElement;


}

template <class T>
MBStaticList<T>& MBStaticList<T>::operator=(const MBStaticList<T>& slOther)
{
	int i;

	// Inicializamos del mismo tamaņo
  if (slOther.m_iMaxElements)
  {
    Init(slOther.m_iMaxElements);
	  

	  // Copiamos con operador =
	  for (i=0 ; i<slOther.m_iMaxElements ; i++)
	  {
      //if (slOther.m_ptNodes[i].m_bValid)
      {
		    m_ptNodes[i]=slOther.m_ptNodes[i];
      }
	  }
	  

	  // Copiamos estado
	  m_iElements         =slOther.m_iElements;
	  m_iFirstElement     =slOther.m_iFirstElement;
	  m_iLastElement      =slOther.m_iLastElement;
	  m_iFirstFreeElement =slOther.m_iFirstFreeElement;
  }
  else
  {
    Shutdown();
  }
  

	return (*this);
}

template <class T>
bool MBStaticList<T>::Has(const T& tData)
{   
  return (Find(tData)==-1?0:1);
}

template <class T>
int MBStaticList<T>::Find(const T& tData)
{
  int i;

  for (i=First() ; i!=-1 ; i=Next(i))
  {
    if (m_ptNodes[i].m_tData==tData)
    {
      return (i);
    }
  }

  return (-1);
}

#endif
