/*
 * Ordenação de arquivos - 09/11/2002 (versao 0.1b)
 * fabiano@seng.com.br
 *
 * Utiliza-se do algoritmo de ordenação "Intercalação de Arquivos".
 *
 * Historico:
 *  versão 0.1a (26/10/2002)
 *   - Código inicial.
 *
 *  versão 0.1b (09/11/2002)
 *   - Eliminou-se o problema de ficar fazendo acessos ao arquivo sem necessidade,
 *     usando apenas duas variáveis auxiliares (int *x, fpos_t *pos) para demarcar
 *     a ultima intercalação, ocasionando uma melhor performance na intercalação.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <time.h>

#define VERSION "0.1b"
#define LINES 10000 // Número de linhas do arquivo randômico a ser gerado
#define SEGMENT   2 // Tamanho inicial do segmento
#define TMPFILE "file.tmp"
#define TLINE 256

void usage(const char *);
void gerar(const char *);
 int flength(const char *);
void intercala(const char *, int, int, int n, int *, fpos_t *);
void ordena(const char *, const char *);
 int enfeite(int);

void usage(const char *progname) {
 fprintf(stderr, "usage: %s [-g|-n] [-i <infile>] [-o <outfile>]\n", progname);
 fprintf(stderr, " -g\tgera arquivo randomico (%d linhas)\n", LINES);
 fprintf(stderr, " -n\tordena arquivo\n"
                 " -i str\tnome do arquivo de entrada (default: \"file.in\")\n"
                 " -o str\tnome do arquivo de saida (default: \"file.out\")\n\n");
 exit(EXIT_FAILURE);
}

void gerar(const char *infile) {
 FILE   *in = NULL;
  int  cont = 0,
       tnow = 0,
       told = 0;

 srandom(time(NULL)); // Inicializa a randomizacao
 
 if((in = fopen(infile, "w")) == NULL) {
  fprintf(stderr, "error: impossivel abrir arquivo(%s)\n\n", infile);
  exit(EXIT_FAILURE);
 }

 told = time(0);
 fprintf(stdout, "Gerando arquivo randomico(%s): \n", infile);
 for(cont=1;cont<=LINES;cont++) {
  fprintf(stdout, "\r %d", cont);
  fprintf(in, "%d\n", random());
  fflush(in);
 }
 tnow = time(0);
 fprintf(stdout, " linhas em %d segundos\n\n", (tnow - told));
 
 fclose(in);
}

int flength(const char *filename) {
 char str[TLINE] = "\0";
  int       cont = 0;
 FILE       *buf = NULL;

 if((buf = fopen(filename, "r")) != NULL)
  while(fgets(str, TLINE, buf))
   cont++;
 fclose(buf);

 return(cont);
}

void intercala(const char *infile, int i1, int f1, int n, int *x, fpos_t *pos) {
 FILE         *in = NULL,
             *tmp = NULL;
 int           i2 = f1 + 1,
               f2 = (2 * f1) - i1 + 1,
             cont = 0;
 char str1[TLINE] = "\0",
      str2[TLINE] = "\0";
 fpos_t        p1,
               p2;
               
 if((i2 < n)) {
  if(f2 > n) f2 = n; if(f1 > n) f1 = n;

  if((in = fopen(infile, "r")) == NULL) {
   fprintf(stderr, "error: impossivel abrir arquivo(%s)\n\n", infile);
   exit(EXIT_FAILURE);
  }
  
  fsetpos(in, pos);
  
  for(cont=*(x);cont<i1;cont++) // Procura posicao 1
   fgets(str1, TLINE, in);
  fgetpos(in, &p1);

  for(;cont<i2;cont++) // Procura posicao 2
   fgets(str2, TLINE, in);
  fgetpos(in, &p2);
  
  *(x) = i2;
  fgetpos(in, pos);
  
  if((tmp = fopen(TMPFILE, "a")) == NULL) {
   fprintf(stderr, "error: impossivel abrir arquivo(%s)\n\n", TMPFILE);
   exit(EXIT_FAILURE);
  }
  while((i1 <= f1) && (i2 <= f2)) {
   fsetpos(in, &p1);
   fgets(str1, TLINE, in);
   str1[(strlen(str1)-1)] = '\0'; // Retira o caracter '\n'
   
   fsetpos(in, &p2);
   fgets(str2, TLINE, in);
   str2[(strlen(str2)-1)] = '\0'; // Retira o caracter '\n'
   if(atoi(str1) < atoi(str2)) {
    fprintf(tmp, "%s\n", str1);
    i1++;
    fsetpos(in, &p1);
    fgets(str1, TLINE, in);
    fgetpos(in, &p1);
   } else {
    fprintf(tmp, "%s\n", str2);
    i2++;
    fsetpos(in, &p2);
    fgets(str2, TLINE, in);
    fgetpos(in, &p2);
   }
  }
  if(i1 <= f1) {
   fsetpos(in, &p1);
   while(i1 <= f1) {
    fgets(str1, TLINE, in);
    fprintf(tmp, "%s", str1);
    i1++;
   }
  } else {
   fsetpos(in, &p2);
   while(i2 <= f2) {
    fgets(str2, TLINE, in);
    fprintf(tmp, "%s", str2);
    i2++;
   }
  }
  fclose(in);
  fclose(tmp);
 } else {
  if((in = fopen(infile, "r")) == NULL) {
   fprintf(stderr, "error: impossivel abrir arquivo(%s)\n\n", infile);
   exit(EXIT_FAILURE);
  }
  fsetpos(in, pos);
  if((tmp = fopen(TMPFILE, "a")) == NULL) {
   fprintf(stderr, "error: impossivel abrir arquivo(%s)\n\n", TMPFILE);
   exit(EXIT_FAILURE);
  }
  for(cont=*(x);cont<i1;cont++)
   fgets(str1, TLINE, in);
  while(i1 <= n) {
   fgets(str1, TLINE, in);
   fprintf(tmp, "%s", str1);
   i1++;
  }
  fclose(in);
  fclose(tmp);
 }
}

void ordena(const char *infile, const char *outfile) {
 int          l = (SEGMENT/2),
              i = 0,
              f = 0,
              x = 0,
           told = 0,
           tnow = 0,
           cont = 0,
              n = flength(infile);
 fpos_t     pos;
 FILE      *tmp = NULL;

 fprintf(stdout, "Intercalando(%s)->(%s)\n", infile, outfile);
 do { 
  told = time(0);
  l = l * 2;
  fprintf(stdout, "Intercalacao(%d)  ",(l/2));
  fflush(stdout);
  x = 1;
  i = 1;
  f = (l / 2);
  tmp = fopen(infile, "r");
  fseek(tmp, 0L, SEEK_SET);
  fgetpos(tmp, &pos);
  fclose(tmp);
  remove(TMPFILE);
  while(i <= n) {
   cont = enfeite(cont);
   if(l == SEGMENT)
    intercala(infile, i, f, n, &x, &pos);
   else
    intercala(outfile, i, f, n, &x, &pos);
   i = i + l;
   f = i + ((l / 2) - 1);
   cont++;
  }
  remove(outfile);
  rename(TMPFILE,outfile);
  tnow = time(0);
  fprintf(stdout, "\bem %d segundos.\n", (tnow - told));
 } while(l <= n);
 fprintf(stdout, "\n");
}

int enfeite(int cont) {
 switch(cont) {
  case 1 : fprintf(stdout, "\b|");  cont++; break;
  case 2 : fprintf(stdout, "\b/");  cont++; break;
  case 3 : fprintf(stdout, "\b-");  cont++; break;
  case 4 : fprintf(stdout, "\b\\"); cont++; break;
  case 5 : fprintf(stdout, "\b|");  cont++; break;
  case 6 : fprintf(stdout, "\b/");  cont++; break;
  case 7 : fprintf(stdout, "\b-");  cont++; break;
 default : fprintf(stdout, "\b\\"); cont=1; break;
 }
 fflush(stdout);
 return(cont);
}

int main(int argc, char *argv[]) {
  char     opt = '\0',
    infile[21] = "file.in",
   outfile[21] = "file.out";
   int   opcao = 0;
 
 fprintf(stdout, "Ordenacao de arquivos - 26/10/2002 (v"VERSION")\n"
                 "fabiano@seng.com.br\n\n");
 
 if(argc < 2)
  usage(argv[0]);

 while((opt = getopt(argc, argv, "gni:o:")) != EOF) {
  switch(opt) {
   case 'g' : if(opcao != 0)
               usage(argv[0]);
              opcao = 1;
              break;
   case 'n' : if(opcao != 0)
               usage(argv[0]);
              opcao = 2;
              break;
   case 'i' : if(strlen(optarg) > 20) 
               usage(argv[0]);
              strcpy(infile,optarg); 
              break;
   case 'o' : if(strlen(optarg) > 20)
               usage(argv[0]);
              strcpy(outfile,optarg);
              break;
    default : usage(argv[0]);
              break;
  }
 }
 
 switch(opcao) {
   case 1 : gerar(infile);
            break;
   case 2 : ordena(infile, outfile);
            break;
  default : usage(argv[0]);
            break;
 }

 return(EXIT_SUCCESS);
}