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

#ifdef __linux__
    #include <stdbool.h>
    #include <termios.h>
    #include <unistd.h>
    #define CLEAR_SCREEN "clear"
    #define FLECHA "\xE2\x94\x80\xE2\x96\xBA"
    #define AACUTE "\xC3\xA1"
    #define IACUTE "\xC3\xAD"
    #define OACUTE "\xC3\xB3"
    #define UACUTE "\xC3\xBA"
    #define NTILDE "\xC3\xB1"
    #define Aacute "\xC3\x81"
    int _getch ();
#else
    #include <conio.h>
    #ifdef __TURBOC__
        #define _getch getch
    #endif
    #define CLEAR_SCREEN "cls"
    #define FLECHA "\304\20"
    #define AACUTE "\240"
    #define IACUTE "\241"
    #define OACUTE "\242"
    #define UACUTE "\243"
    #define NTILDE "\244"
    #define Aacute "\265"
    /* Borre la siguiente sentencia si compila como lenguaje C++.  */
    /* Normalmente a los archivos con extencion .cpp el compilador */
    /* los maneja como lenguaje C++. La extencion debe ser .c      */
    typedef enum {false, true} bool;
#endif

typedef struct TDAPila {
    struct TDAPila *liga;
    int dato;
} *Pila;

#define pila_create()    NULL
#define pila_peek(nodo)  nodo->dato
#define pila_empty(nodo) (nodo==NULL)
Pila pila_push     (Pila nodo, int dato);
Pila pila_remove   (Pila nodo, int dato);
bool pila_contains (Pila nodo, int dato);
void pila_list     (Pila nodo);
bool pila_sort     (Pila nodo);
void pila_print    (Pila nodo);
int  pila_size     (Pila nodo);
Pila pila_pop      (Pila nodo);
Pila pila_reverse  (Pila nodo, Pila inversa);
Pila pila_insert_first (Pila nodo, int dato);
Pila pila_remove_first (Pila nodo);
int  leer_entero (const char *mensaje);

int main (void)
{
    Pila cabecera = pila_create();
    int dato;
    char opcion;
    srand ((unsigned) time (NULL));
    do {
        system (CLEAR_SCREEN);
        printf (
            "OPERACIONES B" Aacute "SICAS DE PILAS\n"
            "a) Insertar un n" UACUTE "mero al final\n"
            "b) Quitar el " UACUTE "ltimo n" UACUTE "mero\n"
            "c) Listar n" UACUTE "meros\n"
            "d) Tama" NTILDE "o de la pila\n"
            "e) Vaciar pila\n"
            "OPERACIONES COMPLEMENTARIAS\n"
            "f) Insertar n" UACUTE "meros aleatorios\n"
            "g) Insertar un n" UACUTE "mero al principio\n"
            "h) Consular si contiene un n" UACUTE "mero\n"
            "i) Quitar un n" UACUTE "mero a buscar\n"
            "j) Quitar el primer n" UACUTE "mero\n"
            "k) Ordenar pila\n"
            "l) Invertir pila\n"
            "m) Salir\n\n"
            "Seleccione una opci" OACUTE "n: ");
        do {
            opcion = (char) tolower (_getch ());
        } while (opcion<'a' || opcion>'m');
        if (opcion!='m')
        {
            printf ("%c\n\n", opcion);
            if (pila_empty(cabecera) && opcion!='a' && opcion!='d' && opcion!='f' && opcion!='g')
                printf ("La pila est" AACUTE " vac" IACUTE "a.\n\n");
            else
            {
                if (opcion!='c' && opcion!='d' && opcion!='h')
                {
                    printf ("Pila original:\n");
                    pila_print (cabecera);
                }
                switch (opcion)
                {
                    case 'a': /* Insertar un numero al final */
                        dato = leer_entero ("el n" UACUTE "mero a insertar");
                        cabecera = pila_push (cabecera, dato);
                        break;
                    case 'b': /* Quitar el ultimo numero */
                        cabecera = pila_pop (cabecera);
                        break;
                    case 'c': /* Listar numeros */
                        pila_list (cabecera);
                        putchar ('\n');
                        break;
                    case 'd': /* Tamano de la pila */
                        printf("Tama" NTILDE "o de la pila: %d.\n\n",
                            pila_size (cabecera));
                        break;
                    case 'e': /* Vaciar pila */
                        while (!pila_empty(cabecera))
                            cabecera = pila_pop (cabecera);
                        break;
                    case 'f': /* Insertar numeros aleatorios */
                        dato = leer_entero ("la cantidad de n" UACUTE
                            "meros aleatorios a insertar");
                        for (; dato>0; dato--)
                            cabecera = pila_push (cabecera, rand()%1000);
                        break;
                    case 'g': /* Insertar un numero al principio */
                        dato = leer_entero ("el n" UACUTE "mero a insertar");
                        cabecera = pila_insert_first (cabecera, dato);
                        break;
                    case 'h': /* Consular si existe un numero */
                        dato = leer_entero ("el n" UACUTE "mero a consultar");
                        printf ("El n" UACUTE "mero %d %s est" AACUTE " en la pila.\n\n",
                            dato, pila_contains (cabecera, dato) ? "s" IACUTE : "no");
                        break;
                    case 'i': /* Quitar un numero a buscar */
                        dato = leer_entero ("el n" UACUTE "mero a remove");
                        cabecera = pila_remove (cabecera, dato);
                        break;
                    case 'j': /* Quitar el primer numero */
                        cabecera = pila_remove_first (cabecera);
                        break;
                    case 'k': /* Ordenar pila */
                        pila_sort (cabecera);
                        break;
                    case 'l': /* Invertir pila */
                        cabecera = pila_reverse (cabecera, pila_create());
                        break;
                }
                if (opcion!='c' && opcion!='d' && opcion!='h')
                {
                    printf ("Pila actualizada:\n");
                    pila_print (cabecera);
                }
            }
            printf ("Presione una tecla para continuar . . . ");
            _getch ();
        }
    } while (opcion != 'm');
    return EXIT_SUCCESS;
}

Pila pila_push (Pila cabecera, int dato)
{
    Pila nodo = (Pila) malloc (sizeof (struct TDAPila));
    nodo->liga = cabecera;
    nodo->dato = dato;
    return nodo;
}

Pila pila_remove (Pila nodo, int dato)
{
    if (!pila_empty(nodo))
    {
        if (pila_peek (nodo)==dato)
            return pila_pop (nodo);
        nodo->liga = pila_remove (nodo->liga, dato);
    }
    return nodo;
}

void pila_list (Pila nodo)
{
    if (!pila_empty(nodo))
    {
        pila_list (nodo->liga);
        printf ("%d\n", pila_peek (nodo));
    }
}

bool pila_sort (Pila nodo)
{
    int dato;
    bool cambio = false;
    if (!pila_empty(nodo) && !pila_empty(nodo->liga))
    {
        if (pila_peek (nodo) < pila_peek (nodo->liga))
        {
            dato = pila_peek (nodo);
            nodo->dato = pila_peek (nodo->liga);
            nodo->liga->dato = dato;
            cambio = true;
        }
        cambio = cambio || pila_sort (nodo->liga);
        if (cambio)
            pila_sort (nodo);
    }
    return cambio;
}

Pila pila_reverse (Pila nodo, Pila inversa)
{
    if (!pila_empty(nodo))
    {
        inversa = pila_reverse (nodo->liga, pila_push (inversa, pila_peek (nodo)));
        free (nodo);
    }
    return inversa;
}

void pila_print (Pila nodo)
{
    if (!pila_empty(nodo))
    {
        printf ("%d " FLECHA " ", pila_peek (nodo));
        pila_print (nodo->liga);
    }
    else
        printf ("NULL\n\n");
}

int pila_size (Pila nodo)
{
    return pila_empty(nodo) ? 0 : 1 + pila_size (nodo->liga);
}

Pila pila_insert_first (Pila nodo, int dato)
{
    if (pila_empty(nodo))
        return pila_push (pila_create(), dato);
    nodo->liga = pila_insert_first (nodo->liga, dato);
    return nodo;
}

Pila pila_remove_first (Pila nodo)
{
    if (!pila_empty(nodo))
    {
        if (pila_empty(nodo->liga))
            return pila_pop (nodo);
        nodo->liga = pila_remove_first (nodo->liga);
    }
    return nodo;
}

bool pila_contains (Pila nodo, int dato)
{
    return !pila_empty(nodo) && (pila_peek (nodo)==dato || pila_contains (nodo->liga, dato));
}

Pila pila_pop (Pila nodo)
{
    Pila liga;
    if(!pila_empty(nodo))
    {
        liga = nodo->liga;
        free (nodo);
        return liga;
    }
    return pila_create();
}

int leer_entero (const char *mensaje)
{
    int entero;
    printf ("Ingrese %s: ", mensaje);
    scanf ("%d", &entero);
    (void) getchar();
    putchar ('\n');
    return entero;
}

#ifdef __linux__

int _getch ()
{
    int ch;
    struct termios oldt, newt;
    tcgetattr (STDIN_FILENO, &oldt);
    newt = oldt;
    newt.c_lflag &= ~(ICANON | ECHO);
    tcsetattr (STDIN_FILENO, TCSANOW, &newt);
    ch = getchar();
    tcsetattr (STDIN_FILENO, TCSANOW, &oldt);
    return ch;
}

#endif