/*---------------------------------------------*
 | sort.c - Unix-like utility.                 |
 | Syntax: sort [flags] [file [file [ ... ] ]  |
 | Sorts the given files (or stdin) to stdout; |
 | see Syntax() for a complete description.    |
 | v1.00 MLO 911225                            |
 *---------------------------------------------*/

/**
 | For sorting, the read lines are arranged in memory in a binary tree;
 | the tree itself can be balanced (if BALANCED_TREE is defined),
 | according to the algorithm of Adel'son-Vel'skij and Landis as
 | described from D.E.Knuth - The art of computer programming (Addison
 | Wesley) - Vol. 3, pag. 451-471. This leads to a more efficient
 | searching along the tree for unbalanced input (i.e. for almost
 | already sorted files), but is an exercise without pratical effect
 | normally; so you would leave  BALANCED_TREE undefined.
 |
 | #define'ing SIMPLE generates a short version of sort, with the
 | normal binary tree algorithm, and alphabetical ordering from column
 | 1 as only ordering option (the only active switch is -r). This way,
 | a file containing 1202 lines of ASCII text (47100 bytes total) can
 | be sorted on a vanilla A500 in less than 4 seconds, against the 24
 | seconds needed from c:sort (AmigaDOS 1.3: Kickstart 34.5, Workbench
 | 34.28).
**/

#include <stdio.h>
#include <stdlib.h>
#ifndef SIMPLE
#include <string.h>
#include <ctype.h>
#endif
#include <libraries/dos.h>
#include <proto/exec.h>
#include "mlo.h"
#include "sort.h"

short int abortProg = 0;                  /* "CTRL-C hit" flag */
Boolean reverse = False;                  /* "Sort in reverse order" flag */

FILE *fp = NULL;

#ifndef SIMPLE
static SortType method = ALPHABETICAL;    /* "Sort method" flag */
static SortType divide = COLUMN;          /* "Input line division" flag */
static char terminator[TERM_LEN] = " ";   /* Field separator(s) */
static int start = 0;                     /* Sorting Field | Column number */
char *temp1 = NULL;                       /* Temporary buffers */
static char *temp2;
#endif

Node *root = NULL;                        /* Binary tree root */

#ifdef BALANCED_TREE
Node *critical;                           /* Critical node for rebalancing */
Node *father;                             /* Father node of *critical */
#endif

static void DoTheStuff(FILE *filePointer);
static void Syntax(void);

void main(
  int argc,
  char **argv
){

/**
 | Resolves the input line
**/

  while (--argc) {
    if ( ((*++argv)[0] == '-') ) {
      switch ((*argv)[1]) {
        case 'r':
        case 'R':
          reverse = True;
          break;

#ifdef SIMPLE
          default:
            Syntax();
      }
#else
        case 'f':
        case 'F':
          method = CASE_FOLDED;
          break;
        case 'n':
        case 'N':
          method = NUMERICAL;
          break;
        case 't':
        case 'T':
          if ((*argv)[2]) strcpy(terminator, *argv+2);
             else         Syntax();
          break;
        default:
          if (isdigit((*argv)[1])) start = atoi(*argv+1) - 1;
             else                  Syntax();
          divide = COLUMN;
          break;
      }
    } else if ((*argv)[0] == '+') {
      if (isdigit((*argv)[1])) start = atoi(*argv+1);
         else                  Syntax();
      divide = FIELD;
#endif

    } else if ((*argv)[0] == '?') {
      Syntax();
    } else {
      break;
    }
  }

/**
 | Allocate the temporary buffers
**/

#ifndef SIMPLE
  if ((temp1 = calloc(2, LINE_LENGTH)) == NULL) {
    puts("sort: couldn't obtain heap memory.");
    exit(SYS_ABORT_CODE);
  }
  temp2 = temp1 + LINE_LENGTH;
#endif

/**
 | Reads and sorts the input file(s)
**/

  if (argc) {
    while (argc--) {
      if ((fp = fopen(*argv, "r")) == NULL) {
        printf("sort: couldn't open file \"%s\".\n", *argv);
      } else {
        DoTheStuff(fp);
        fclose(fp);
        fp = NULL;
      }
      ++argv;
    }
  } else {
    DoTheStuff(stdin);
  }

/**
 | Final printout, and graceful exit
**/

  if (root)   PrintTree(root);

#ifndef SIMPLE
  free(temp1);
#endif

  exit(SYS_NORMAL_CODE);
}

#ifndef SIMPLE
int Compare(
  char *p1,
  char *p2
){
  int result;

/**
 | Compares the two string in "p1" and "p2"; returns 0 if they
 | are identical, otherwise compares them using the sorting
 | criteria specified in the input line, returning a negative
 | number if "p1" comes before "p2" or a positive number otherwise.
 |
 | Are the string absolutely identical?
**/

  if (!strcmp(p1, p2))  return 0;

/**
 | If not, store in p1 and p2 the pointers to the string regions
 | to be compared.
**/

  switch (divide) {
    case COLUMN:
      p1 += start;
      p2 += start;
      break;
    case FIELD:
      if (*terminator == BLANK) {
        GetTokBlk(p1, start, temp1);
        GetTokBlk(p2, start, temp2);
      } else {
        GetTokDel(p1, terminator, start, temp1);
        GetTokDel(p2, terminator, start, temp2);
      }
      p1 = temp1;
      p2 = temp2;
      break;
  }

  switch (method) {
    case ALPHABETICAL:
      result = strcmp(p1, p2);
      break;
    case CASE_FOLDED:
      result = stricmp(p1, p2);
      break;
    case NUMERICAL:
      result  = atoi(p1);
      result -= atoi(p2);
      break;
  }

/**
 | If the compared field matches, but the original records were
 | not identical, insert them in the order they came (p1 AFTER p2).
**/

  if (!result)  return 1;
     else       return result;
}
#endif

void CheckBreak(
  Boolean exitprog
){

/**
 | Checks the CTRL-C flag and, the first time it is set, prints
 | a warning message. If the argument is True, frees allocated
 | memory and exits; no further action, if the argument is False.
**/
  if (!abortProg && (SetSignal(0L, SIGBREAKF_CTRL_C) & SIGBREAKF_CTRL_C))
      abortProg |= BREAK_DETECTED;

  if (abortProg) {
    if (!(abortProg & WARNING_PRINTED)) {
      puts("sort: *** BREAK ***");
      abortProg |= WARNING_PRINTED;
    }
    if (exitprog) {
      FreeTree(root);
#ifndef SIMPLE
      if (temp1 != NULL) free(temp1);
#endif
      if (fp != NULL) fclose(fp);
      exit(SYS_NORMAL_CODE);
    }
  }
}

int CXBRK(void)
{

/**
 | If a CTRL-C is detected from the operating system,
 | we silently defer all handling until "abortProg" is checked.
**/

  abortProg |= BREAK_DETECTED;
  return 0;
}

static void DoTheStuff(
  FILE *filePointer
){
  char buffer[LINE_LENGTH];

  while (fgets(buffer, LINE_LENGTH, filePointer)) {
    CheckBreak(True);

#ifdef BALANCED_TREE
    father   = NULL;
    critical = root;
#endif

    root = InsertTree(buffer, root);

#ifdef BALANCED_TREE
    BalanceTree(buffer);
#endif

  }
}

static void Syntax(void)
{

#ifdef SIMPLE
  puts("\nUsage:   sort [-r] [file [file [ ... ] ] ]");
#else
  puts("\nUsage:   sort [-r][-f|-n][+N|-N][-tx] [file [file [ ... ] ] ]");
#endif

  puts("Purpose: sorts the records read from the input file(s), or from");
  puts("         stdin, to stdout.");
  puts("    -r : reverse order sorting");

#ifndef SIMPLE
  puts("    -n : numeric sorting                  \\ Default: alphabetic");
  puts("    -f : folds uppercase to lowercase     /          sorting");
  puts("    -N : sorts starting at column N       \\ Default: start");
  puts("    +N : sorts respect to field N         /          at column 1");
  puts(" -t... : separator character(s) between fields (default: space)");
#endif

  puts("");
  exit(SYS_NORMAL_CODE);
}