/* ------------------------------------------------------------ */
/* IMPLEMENTACION DE FUNCIONES BASICAS UNA LISTA ENCADENADA     */
/* ------------------------------------------------------------ */

#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;

/* Variable global Puntero de Inicio de la Lista */
Elemento  *Base;

/* ------------------------------------------------- */
/* Funciones de Manejo de UNA lista encadenada       */
/* ------------------------------------------------- */
void     Crear   (void);
boolean  Vacia   (void);
TipoDato Primero (void);
TipoDato Ultimo  (void);
boolean  PonAlFinal        (TipoDato Dato);
boolean  PonAlPrincipio    (TipoDato Dato);
boolean  BorrarAlFinal     (void);
boolean  BorrarAlPrincipio (void);
boolean  InsertarEnOrden   (TipoDato Dato );
boolean  BorrarElemento    (TipoDato Dato );
void     VerLista    (void);
void     VaciarLista (void);






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

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

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

/*----------------------------------------------------------------*/
/* Devuelve el valor almacenado en
   el último elemento de la Lista */
TipoDato Ultimo(void)
{
  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 ( TipoDato Dato)
{
  Elemento *pnuevo;
  boolean resu;

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

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

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

   /* Creo el elemento nuevo */
   pnuevo = (Elemento *) malloc( sizeof(Elemento));
   if ( pnuevo == NULL )
      {
      /* Si no 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 ( Base != NULL )
     {
     paux = Base;
     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 */
     Base  = pnuevo;
     }
 return TRUE;
}
/*----------------------------------------------------------------*/
/* Elimina el primer elemento
   de la lista */
boolean BorrarAlPrincipio   (void)
{
  Elemento *paux;

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

  if ( Vacia() )
     {
      return FALSE;
     }
  else
     {
     /* Si solo hay uno */
     if ( Base->sig == NULL )
			{
			free(Base);
			Base = NULL;
			}
	  else
			{
     	   paux1 = Base;      /* Primer elemento */
     		paux2 = Base->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( TipoDato Dato )
{
  Elemento *paux1, *paux2, *pnuevo;

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

  /* Si está vacia */
  if ( Base == NULL )
     {
     Base = pnuevo;
     pnuevo->sig = NULL;
     }
  else
     {
     /* Si está antes del primero */
     if ( Base->valor > pnuevo->valor )
        {
        pnuevo->sig = Base;
        Base = pnuevo;
        }
     else
        {
        paux1 = Base;      /* Primero */
        paux2 = Base->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 ( TipoDato Dato )
{
   Elemento *paux1,*paux2;

  /* Si no hay elementos */
  if ( Base == NULL )
     {
     return FALSE;
     }
  /* Si es el primero */
  if ( Base->valor == Dato )
     {
     paux1 = Base;
     Base = Base->sig;
     free(paux1);
     }
  else
     {
     /* Busco el elemento */
     paux1 = Base;
     paux2 = Base->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 ( void )
{
  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(void)
{
   Elemento *paux;
   while ( Base != NULL )
    {
    paux = Base;
    Base = Base->sig;
    free(paux);
    }
}
/*----------------------------------------------------------------*/
/*----------------------------------------------------------------*/
/* Prueba de Funciones */
int main()
{

 Crear();
 if ( Vacia () ) puts ("Lista vacia");
 PonAlPrincipio(30);
 PonAlPrincipio(20);
 PonAlPrincipio(10);
 if (! Vacia () ) VerLista () ;
 getchar();

 PonAlFinal(100);
 PonAlFinal(200);
 PonAlFinal(300);
 VerLista();
 getchar();

 printf(" El primero es :%d \n", Primero());
 printf(" El último es  :%d \n", Ultimo() );
 BorrarAlPrincipio();
 BorrarAlFinal();
 VerLista();
 printf(" El primero es :%d \n", Primero());
 printf(" El último es  :%d \n", Ultimo() );
 getchar();

 InsertarEnOrden(5);
 InsertarEnOrden(15);
 InsertarEnOrden(150);
 InsertarEnOrden(1500);
 VerLista();
 getchar();

 if ( !BorrarElemento(88) ) puts("No  puedo borrar el elemento 88 ");
 BorrarElemento(200);
 BorrarElemento(20);
 VerLista();
 getchar();

 VaciarLista();
 VerLista();
 getchar();
}