/* ------------------------------------------------------------ */
/* IMPLEMENTACION DE FUNCIONES BASICAS SOBRE LISTAS ENCADENADAS */
/* ------------------------------------------------------------ */

#include <stdio.h>
#include <alloc.h>


typedef enum {FALSE=0,TRUE=1} boolean;

/* Tipo de dato que almacena cada elemento de la lista */
typedef int TipoDato;

/* Estructura autoreferenciada */
struct SEle{
       TipoDato valor;
       struct SEle *sig;
       };

typedef struct SEle Elemento;

/* ----------------------------------------------------- */
/* Funciones de Manejo de Múltiples Listas encadenadas   */
/* ----------------------------------------------------- */
/* Cuando podemos modificar la posición inicial de la
   lista señalada por Base, debemos pasar un puntero a Base,
   PBase == & Base  O lo que es lo mismo  *PBase  == Base  */
/* ------------------------------------------------------ */
void     Crear   (Elemento **PBase);
boolean  Vacia   (Elemento  *Base);
TipoDato Primero (Elemento  *Base);
TipoDato Ultimo  (Elemento  *Base);
boolean  PonAlFinal        (Elemento **PBase, TipoDato Dato);
boolean  PonAlPrincipio    (Elemento **PBase, TipoDato Dato);
boolean  BorrarAlFinal     (Elemento **PBase);
boolean  BorrarAlPrincipio (Elemento **PBase);
boolean  InsertarEnOrden   (Elemento **PBase, TipoDato Dato );
boolean  BorrarElemento    (Elemento **PBase, TipoDato Dato );
void     VerLista    (Elemento *Base );
void     VaciarLista (Elemento **PBase );



/*----------------------------------------------------------------*/
/* Inicializa el puntero de la Lista */
void Crear(Elemento **PBase)
{
  *PBase = NULL;
}

/*----------------------------------------------------------------*/
/* Indica si esta o no vacia */
boolean Vacia(Elemento *Base)
{
  return ( Base == NULL)?TRUE:FALSE;
}

/*----------------------------------------------------------------*/
/* evuelve el valor almacenado en
   el primer elemento de la Lista */
TipoDato Primero(Elemento *Base)
{
  return Base->valor;
}

/*----------------------------------------------------------------*/
/* Devuelve el valor almacenado en
   el último elemento de la Lista */
TipoDato Ultimo(Elemento *Base)
{
  Elemento *paux;
  paux = Base;
  while ( paux->sig != NULL )
    {
    paux = paux->sig;
    }
  return paux->valor;
}

/*----------------------------------------------------------------*/
/* Crea un nuevo elemento al principio de la Lista */
boolean PonAlPrincipio (Elemento **PBase,TipoDato Dato)
{
  Elemento *pnuevo;
  boolean resu;

  resu = FALSE;
  pnuevo = malloc( sizeof(Elemento) );
  if ( pnuevo != NULL )
     {
     pnuevo->sig = *PBase;
     pnuevo->valor = Dato;
     *PBase = pnuevo;
     resu = TRUE;
     }
  return resu;
}

/*----------------------------------------------------------------*/
/* Crea un nuevo elemento al final de la lista */

boolean PonAlFinal  (Elemento **PBase, TipoDato Dato)
{
   Elemento *paux,*pnuevo;

   /* Creo el elemento nuevo */
   pnuevo = malloc( sizeof(Elemento));
   if ( pnuevo == NULL )
      {
      /* Si pude crear el elemento termina
       la función */
      return FALSE;
      }

   /* Relleno el nuevo elemento */
   pnuevo->valor = Dato;
   pnuevo->sig   = NULL; /* Va a ser el último */

  /* Si no está vacia recorro la lista
     hasta alcanzar el último elemento */
  if ( *PBase != NULL )
     {
     paux = *PBase;
     while ( paux->sig != NULL )
		 {
		 paux = paux->sig;
       }
     /* El puntero siguiente del último
        elemento señala al nuevo */
     paux->sig   = pnuevo;
     }
 else
     {
     /* La lista está vacia */
     /* Base señala al nuevo elemento */
     *PBase  = pnuevo;
     }
 return TRUE;
}
/*----------------------------------------------------------------*/
/* Elimina el primer elemento
   de la lista */
boolean BorrarAlPrincipio   (Elemento **PBase )
{
  Elemento *paux;

  paux = *PBase;
  if ( !Vacia(*PBase) )
     {
     /* Señala al siguiente y libero memoria */
     *PBase = (*PBase)->sig;
     free(paux);
     return TRUE;
     }
 return FALSE;
}
/*----------------------------------------------------------------*/
/* Borra el último elemento de la lista */
boolean BorrarAlFinal(Elemento **PBase)
{
  Elemento *paux1,*paux2;

  if ( Vacia(*PBase) )
     {
      return FALSE;
     }
  else
     {
     /* Si solo hay uno */
     if ( (*PBase)->sig == NULL )
			{
			free(*PBase);
			*PBase = NULL;
			}
	  else
			{
     	   paux1 = *PBase;      /* Primer elemento */
     		paux2 = (*PBase)->sig; /* Segundo elemento */
     	   while ( paux2->sig != NULL )
       	  {
           paux1 = paux2;
           paux2 = paux2->sig;
           }
         /* Pon el puntero siguiente del
            elemento anterior a NULL */
         paux1->sig = NULL;
         /* Libero el espacio del último elemento */
         free(paux2);
			}
     return TRUE;
     }
}
/*----------------------------------------------------------------*/
/* Coloca un elemento en la lista
   insertando en orden creciente */

boolean InsertarEnOrden(Elemento **PBase, TipoDato Dato )
{
  Elemento *paux1, *paux2, *pnuevo;

  pnuevo = malloc (sizeof (Elemento) );
  if ( pnuevo == NULL )
     {
     return FALSE;
     }
  pnuevo->valor = Dato;

  /* Si está vacia */
  if ( *PBase == NULL )
     {
     *PBase = pnuevo;
     pnuevo->sig = NULL;
     }
  else
     {
     /* Si está antes del primero */
     if ( (*PBase)->valor > pnuevo->valor )
        {
        pnuevo->sig = *PBase;
        *PBase = pnuevo;
        }
     else
        {
        paux1 = *PBase;      /* Primero */
        paux2 = (*PBase)->sig; /* Segundo */
        while ( paux2 != NULL )
        {
         if ( paux2->valor > pnuevo->valor )
            {
            break;
            }
         paux1 = paux2;
         paux2 = paux2->sig;
        }
        // Inserto
        paux1->sig = pnuevo;
        pnuevo->sig = paux2;
        }
     }
   return TRUE;
}
/*----------------------------------------------------------------*/
/* Borra un elemento determinado */
boolean BorrarElemento (Elemento **PBase, TipoDato Dato )
{
   Elemento *paux1,*paux2;

  /* Si no hay elementos */
  if ( *PBase == NULL )
     {
     return FALSE;
     }
  /* Si es el primero */
  if ( (*PBase)->valor == Dato )
     {
     paux1 = *PBase;
     *PBase = (*PBase)->sig;
     free(paux1);
     }
  else
     {
     /* Busco el elemento */
     paux1 = *PBase;
     paux2 = (*PBase)->sig;
     while ( paux2 != NULL )
      {
      if ( paux2->valor == Dato )
         {
         break;
         }
      paux1 = paux2;
      paux2 = paux2->sig;
      }
     if ( paux2 == NULL )
        {
        /* No está */
        return FALSE;
        }
     else
        {
        paux1->sig = paux2->sig;
        free(paux2);
        }
     }
return TRUE;

}
/*----------------------------------------------------------------*/
/* Muestra el contenido de la lista */
void VerLista (Elemento *Base )
{
  Elemento *paux;

  printf("\n LISTA: [");
  paux = Base;
  while ( paux != NULL )
   {
   printf("->%d ",paux->valor);
   paux = paux->sig;
   }
  printf("]\n");
}


/*----------------------------------------------------------------*/
/* Borrar todos los elemento de la lista */
void VaciarLista (Elemento **PBase )
{
   Elemento *paux;
   while ( *PBase != NULL )
    {
    paux = *PBase;
    *PBase = (*PBase)->sig;
    free(paux);
    }
}
/*----------------------------------------------------------------*/
/*----------------------------------------------------------------*/
/* Prueba de Funciones */
void main()
{
 Elemento *Lista1, *Lista2;

 Crear(&Lista1);
 Crear(&Lista2);
 if ( Vacia (Lista1) ) puts ("Lista1 vacia");
 if ( Vacia (Lista2) ) puts ("Lista2 vacia");
 PonAlPrincipio(&Lista1,100);
 PonAlPrincipio(&Lista1,10);
 PonAlPrincipio(&Lista1,1);
 PonAlPrincipio(&Lista2,200);
 PonAlPrincipio(&Lista2,20);
 PonAlPrincipio(&Lista2,2);

 if (! Vacia (Lista1) ) VerLista (Lista1) ;
 if (! Vacia (Lista2) ) VerLista (Lista2) ;
 getchar();

 PonAlFinal(&Lista1,1000);
 PonAlFinal(&Lista2,2000);
 VerLista(Lista1);
 VerLista(Lista2);
 getchar();

 printf(" El primero de la lista 1 es :%d \n", Primero(Lista1));
 printf(" El primero de la lista 2 es :%d \n", Primero(Lista2));
 printf(" El último de la lista 1 es  :%d \n", Ultimo(Lista1) );
 printf(" El último de la lista 2 es  :%d \n", Ultimo(Lista2) );
 BorrarAlPrincipio(&Lista1);
 BorrarAlFinal(&Lista1);
 VerLista(Lista1);
 BorrarAlPrincipio(&Lista2);
 BorrarAlFinal(&Lista2);
 VerLista(Lista2);


 getchar();

 InsertarEnOrden(&Lista1,5);
 InsertarEnOrden(&Lista2,2);
 InsertarEnOrden(&Lista1,110);
 InsertarEnOrden(&Lista2,220);
 VerLista(Lista1);
 VerLista(Lista2);
 getchar();

 if ( !BorrarElemento(&Lista1,88) )
      puts("No  puedo borrar el elemento 88 de lista 1");
 BorrarElemento(&Lista1,100);
 BorrarElemento(&Lista2,200);
 VerLista(Lista1);
 VerLista(Lista2);
 getchar();

 VaciarLista(&Lista1);
 VerLista(Lista1);
 VaciarLista(&Lista2);
 VerLista(Lista2);
 getchar();
}