/*
+----------------------------------------------------+
| ORDENACION DE UN FICHERO (SIMILAR AL SORT DEL DOS) |
+----------------------------------------------------+

        Este programa lee  las líneas de un fichero  de entrada (que
puede ser la  consola) y escribe las líneas  ordenadas en un fichero
de salida (que puede ser la consola).
*/

#include <stdio.h> /* printf (), gets (), FILE, fopen (), fclose (),
                    NULL, fprintf (), fgets () */
#include <stdlib.h> /* exit () */
#include <alloc.h>  /* malloc (), free () */
#include <conio.h>  /* getch () */
#include <string.h> /* strcmp (), strcpy () */
#include <ctype.h>  /* toupper () */

#define BOOLEAN int
#define TRUE    1
#define FALSE   0
#define ESC 27
#define ENTER '\r' /* no vale '\n' */
#define NUMMAXCARACTERES 255

struct nodo_arbol
 {
   char linea[NUMMAXCARACTERES];
   struct nodo_arbol *pizq, *pder;         
 };

void inicializar_arbol (struct nodo_arbol **parb);
void hacer_nodo_arbol (struct nodo_arbol **pa);
void insertar_en_arbol (struct nodo_arbol **parb, char *lin);
void imprimir_arbol (struct nodo_arbol *parb, FILE *pfichsal);
void liberar_arbol (struct nodo_arbol **parb);

void main (void)
{
  BOOLEAN salir = FALSE;
  char nombre_fichero_entrada[NUMMAXCARACTERES],
       nombre_fichero_salida[NUMMAXCARACTERES],
       linea_fichero[NUMMAXCARACTERES];
  FILE *pfe, *pfs; /* punteros a fichero de entrada y fichero de
                   salida resp. */
  char ch;
  struct nodo_arbol *parbol;

  while (! salir)
    {
      puts ("\n\nORDENACION DE FICHEROS.\n");
      printf ("Introduzca nombre de fichero de entrada (ENTER o CON "
               "para teclado): ");
      gets (nombre_fichero_entrada);
      if (*nombre_fichero_entrada == '\0')
        strcpy (nombre_fichero_entrada, "con");
      printf ("Introduzca nombre de fichero de salida (ENTER o CON "
               "para pantalla): ");
      gets (nombre_fichero_salida);
      if (*nombre_fichero_salida == '\0')
        strcpy (nombre_fichero_salida, "con");

      if ((pfe = fopen (nombre_fichero_entrada, "r")) == NULL)
        printf ("\nERROR: No es posible abrir el fichero de entrada "
                 "%s.\n", nombre_fichero_entrada);
      else if ((pfs = fopen (nombre_fichero_salida, "w")) == NULL) {
        printf ("\nERROR: No es posible abrir el fichero de salida "
                 "%s.\n", nombre_fichero_salida);
        fclose (pfe); }
      else { inicializar_arbol (&parbol);

        while (fgets (linea_fichero, sizeof (linea_fichero), pfe) !=
               NULL)
        insertar_en_arbol (&parbol, linea_fichero);
        imprimir_arbol (parbol, pfs);
        fclose (pfe);
        fclose (pfs);
        liberar_arbol (&parbol);
      }

      printf ("\n\n¿Desea ordenar otro fichero (S o ENTER: Sí; N o "
               "ESC: No)? ");
      do
        {
          ch = getch ();
        } while (ch != ENTER && toupper (ch) != 'S' &&
                 ch != ESC && toupper (ch) != 'N');
      salir = ch == ESC || toupper (ch) == 'N';
    }
}

void inicializar_arbol (struct nodo_arbol **parb)
{
  *parb = NULL;
}

void hacer_nodo_arbol (struct nodo_arbol **pa)
{
  if ((*pa = (struct nodo_arbol *) malloc (sizeof (struct
       nodo_arbol))) == NULL)
    {
      printf ("\nERROR: Memoria insuficiente.");
      exit (1);
    }
}

void insertar_en_arbol (struct nodo_arbol **parb, char *lin)
{
  struct nodo_arbol *p, *pant, *pa;

  hacer_nodo_arbol (&pa);
  strcpy (pa->linea, lin);
  pa->pizq = pa->pder = NULL;

  p = *parb;
  pant = NULL;
  while (p != NULL)
    {
      pant = p;
      if (strcmp (p->linea, lin) > 0)
        p = p->pizq;
      else
        p = p->pder;
    }

  if (pant == NULL)
    *parb = pa;
  else if (strcmp (pant->linea, lin) > 0)
    pant->pizq = pa;
  else
    pant->pder = pa;
}

void imprimir_arbol (struct nodo_arbol *parb, FILE *pfichsal)
{
  if (parb != NULL)
    {
      imprimir_arbol (parb->pizq, pfichsal);
      fprintf (pfichsal, parb->linea);
      imprimir_arbol (parb->pder, pfichsal);
    }
}

void liberar_arbol (struct nodo_arbol **parb)
{
  if (*parb != NULL)
    {
      liberar_arbol (&(*parb)->pizq);
      liberar_arbol (&(*parb)->pder);
      free (*parb);
    }
}