/*
   ****************************  NOTICE!  **************************
   *   Contrary to the current trend  in  MS-DOS  software  this   *
   *   program,  for  whatever  it is worth,  is NOT copyrighted   *
   *   (with the exception of the runtime library  from  Borland   *
   *   International's  Turbo  C)!  The program,  in whole or in   *
   *   part,  may be used freely in any fashion  or  environment   *
   *   desired.  If  you  find this program to be useful to you,   *
   *   do NOT send any contribution to the author;  in the words   *
   *   of  Rick  Conn,   'Enjoy!'  However,   if  you  make  any   *
   *   improvements,  I would enjoy  receiving  a  copy  of  the   *
   *   modified  source.  I  can  be reached,  usually within 24   *
   *   hours,  by  messages  on  any  of  the  Phoenix  systems,   *
   *   particularly:                                               *
   *                                                               *
   *               The Tool Shop BBS       [PCBOARD]               *
   *                   (602) 279-2673   1200/2400/9600 bps         *
   *                   (Good luck trying!  VERY BUSY!)             *
   *               Technoids Anonymous     [PCBOARD]               *
   *                   (602) 899-4876   300/1200/2400 bps          *
   *                                                               *
   *   All can be reached through PC Pursuit.                      *
   *                                                               *
   *   or:                                                         *
   *                on GEnie, mail address: DON-WILL               *
   *                on CompuServ:           75410,543              *
   *                                                               *
   *   Every  effort has been made to avoid error and moderately   *
   *   extensive testing has been  performed  on  this  program,   *
   *   however, the author does not warrant it to be fit for any   *
   *   purpose  or  to  be  free  from  error  and disclaims any   *
   *   liability for actual or any other damage arising from the   *
   *   use of this program.                                        *
   *****************************************************************
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <alloc.h>
#include <ctype.h>
#include <dir.h>
#include <dos.h>

#include "queue.h"

void            GetArgs (int argc, char *argv[]);
void            InvalArgu (char *Msg);
int             FillSortArray (void);
void            Usage (void);
int             isdevice (int handle);

void            Merge (void);

unsigned long   MaxMem;
int             S_ArraySize;
char          **SortArray;
int             KeyCount = 0;
int             RecLen = 0;
unsigned long   DiskAdr = 0;
unsigned long   NextAdr = 0;
unsigned long   EndAdr;
long            TotalRecs = 0;
long            OutCount = 0;
char            Buffer[512];
FILE           *fin = NULL;
FILE           *fint, *fout;
unsigned long   lnno = 0;
QUE_DEF        *Keys, Runs;
long            BufSize;
char            IntPath[65] = "";

unsigned        DeBug = 0;

struct KeyEntry {
	int             Begin;
	int             Len;
	char            Order;
	char            Case;
	char            Type;
	};

typedef struct RunStruct {
	unsigned long   Begin;
	unsigned long   Count;
	}               RUN_ENT;

char            InputName[65] = "";
char            OutName[65] = "";
char            IntName[65] = "";
long            Temp;

 void
main (int argc, char *argv[]) {
	extern int      comp();

	int             i, Count;
	RUN_ENT        *r;
	struct dfree    DiskTab;
	char           *p;
	char            OutDisk;
	char            IntDisk;
	long            DiskFree;
	struct KeyEntry *t;

	fprintf(stderr, "PDSORT Version 2.1.0:  June 5, 1990\n");
	if (argc < 2) Usage();
	if ((Keys = malloc(sizeof(QUE_DEF))) == NULL) {
		fprintf(stderr, "Insufficient memory for Key queue.\n");
		exit(1);
		}
	InitQueue(Keys);
	InitQueue(&Runs);
	GetArgs(argc, argv);
	if (RecLen <= 0) {
		fprintf(stderr, "You must supply a record length.\n");
		exit(1);
		}
	if (Keys->Count == 0) {
		if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
			fprintf(stderr, "Insufficient memory for Key entry.\n");
			exit(1);
			}
		t->Order = 'a';
		t->Case = 'm';
		t->Type = 'c';
		t->Begin = 0;
		t->Len = RecLen;
		Enque(Keys, t);
		}

	if (fin != stdin) {
		if ((fin = fopen(InputName, "r")) == NULL) {
			fprintf(stderr, "I can't find input file: %s", InputName);
			perror("");
			exit(1);
			}
		}
	if (!isdevice(fileno(fin))) {
		fseek(fin, 0, SEEK_END);
		EndAdr = ftell(fin);
		fseek(fin, 0, SEEK_SET);
		}
	else EndAdr = 0;

	if (fin != stdin) {
		if ((p = strchr(OutName, ':')) != NULL) OutDisk = toupper(OutName[0]);
		else OutDisk = getdisk() + 1;
		getdfree(OutDisk, &DiskTab);
		DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
		if (DiskFree < EndAdr) {
			fprintf(stderr, "Insufficient space on output disk.\n");
			exit(1);
			}
		if (IntPath[0] != '\0') {
			if (IntPath[1] == ':') IntDisk = toupper(IntPath[0]);
			else IntDisk = getdisk() + 1;
			}
		else {
			if ((p = strrchr(OutName, '\\')) != NULL)
				strncpy(IntPath, OutName, (int) (p - OutName + 1));
			else {
				IntPath[0] = OutDisk + '@';
				IntPath[1] = ':';
				IntPath[2] = '\\';
				getcurdir(OutDisk, &IntPath[3]);
				}
			IntDisk = IntPath[0] - '@';
			}
		getdfree(IntDisk, &DiskTab);
		DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
		if (DiskFree < EndAdr) {
			fprintf(stderr, "Insufficient space on intermediate disk.\n");
			exit(1);
			}
		}

	MaxMem = coreleft();
	MaxMem -= 4 * 1024L;

	S_ArraySize = (int) (MaxMem / (RecLen + 2 + sizeof(char far *) + 10));
	if ((SortArray = malloc(S_ArraySize * sizeof(char far *))) == NULL) {
		fprintf(stderr, "Major Error! Insufficient memory for Sort Array.\n");
		exit(1);
		}

	for (i = 0;
		 (i < S_ArraySize && coreleft() >= ((4 * 1024L) + RecLen + 2));
		 i++) {
		if ((SortArray[i] = malloc(RecLen + 2)) == NULL) {
			fprintf(stderr, "Major Error! Insufficient memory for sort item.\n");
			exit(1);
			}
		}
	S_ArraySize = i;
	fprintf(stderr, "Max records per run = %d\n", S_ArraySize);

	BufSize = (coreleft() - 1024) / 2;

	Count = FillSortArray();

	TotalRecs += Count;
	if (NextAdr >= EndAdr) {
		fprintf(stderr, "Total records read = %ld\n", TotalRecs);
		if (fin != stdin) {
			fclose(fin);
			if ((fout = fopen(OutName, "w")) == NULL) {
				fprintf(stderr, "I can't create output file: %s", OutName);
				perror("");
				exit(1);
				}
			}
		errno = 0;

		qsort(SortArray, Count, sizeof(char far *), comp);

		for (i = 0; i < Count; i++) {
			fputs(SortArray[i], fout);
			if (errno) {
				perror("I/O error on output file");
				exit(1);
				}
			OutCount++;
			}
		}
	else {
		while (Count > 0) {
			if (fint == NULL) {
				strcpy(IntName, IntPath);
				strcat(IntName, "\\SORT.$$$");
				if ((fint = fopen(IntName, "w")) == NULL) {
					fprintf(stderr, "I can't create sort intermediate file: %s", IntName);
					perror("");
					exit(1);
					}
				errno = 0;
				}
			DiskAdr = ftell(fint);

			qsort(SortArray, Count, sizeof(char far *), comp);

			if ((r = malloc(sizeof(RUN_ENT))) == NULL) {
				fprintf(stderr, "Insufficient memory for Run Entry!\n");
				exit(1);
				}
			r->Begin = DiskAdr;
			r->Count = Count;
			Enque(&Runs, r);

			for (i = 0; i < Count; i++) {
				fputs(SortArray[i], fint);
				if (errno) {
					perror("I/O error on intermediate file");
					exit(1);
					}
				}
			Count = FillSortArray();
			TotalRecs += Count;
			}
		fprintf(stderr, "Total records read = %ld\n", TotalRecs);
		if (fin != stdin) {
			fclose(fin);
			if ((fout = fopen(OutName, "w")) == NULL) {
				fprintf(stderr, "I can't create output file: %s", OutName);
				perror("");
				exit(1);
				}
			}
		errno = 0;
		qsort(SortArray, Count, sizeof(char far *), comp);
		for (i = 0; i < Count; i++) {
			fputs(SortArray[i], fout);
			if (errno) {
				perror("I/O error on output file");
				exit(1);
				}
			}
		Merge();
		}
	unlink(IntName);
	fprintf(stderr, "Total records written = %ld\n", OutCount);
	}


 void
GetArgs (int argc, char *argv[]) {
	int             i;
	char           *p1, *p2;
	struct KeyEntry *t;

	for (i = 1; i < argc; ++i) {
		if (argv[i][0] != '-') continue;
		if (!strcmp(argv[i], "-")) {
			fin = stdin;
			fout = stdout;
			continue;
			}
		switch (tolower(argv[i][1])) {
			case 't':
				strcpy(IntPath, &argv[i][2]);
				break;
			default:
				fprintf(stderr, "Invalid option: %s\n", argv[i]);
				Usage();
			}
		}

	for (i = 1; i < argc; ++i) {
		if (argv[i][0] == '-') continue;
		if (fin == NULL) {
			if (InputName[0] == '\0') {
				strcpy(InputName, argv[i]);
				continue;
				}
			else if (OutName[0] == '\0') {
				strcpy(OutName, argv[i]);
				continue;
				}
			}
		p1 = argv[i];
		if (!isdigit(p1[0])) InvalArgu(argv[i]);
		if ( (RecLen == 0) && (strspn(p1, "0123456789") == strlen(p1)) ) {
			RecLen = atoi(argv[i]);
			continue;
			}
		p2 = &p1[strspn(p1, "0123456789")];
		if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
			fprintf(stderr, "Insufficient memory for Key entry.\n");
			exit(1);
			}
		t->Order = 'a';
		t->Case = 'm';
		t->Type = 'c';
		t->Begin = atoi(p1) - 1;
		if (*p2 == ':') t->Len = atoi(++p2);
		else if (*p2 == '-') t->Len = atoi(++p2) - t->Begin;
		else InvalArgu(argv[i]);
		p1 = p2;
		p2 = &p1[strspn(p1, "0123456789")];
		if (*p2 == ':') {
			p1 = ++p2;
			while (*p1 != '\0') {
				switch (tolower(*p1++)) {
					case 'd':
						t->Order = 'd';
						break;
					case 'a':
						t->Order = 'a';
						break;
					case 'i':
						t->Case = 'i';
						break;
					case 'm':
						t->Case = 'm';
						break;
					case 'c':
						t->Type = 'c';
						break;
					default:
						InvalArgu(argv[i]);
					}
				}
			}
		else if (*p2 != '\0') InvalArgu(argv[i]);
		Enque(Keys, t);
		}
	}

 void
InvalArgu (char *Msg) {
	fprintf(stderr, "Invalid argument: %s.\n", Msg);
	Usage();
	}


 int
FillSortArray (void) {
	int             i;

	for (i = 0; i < S_ArraySize; i++) {
		if (fgets(Buffer, RecLen + 1, fin) == NULL) return (i);
		if (errno) {
			perror("I/O error on input file");
			exit(1);
			}
		NextAdr = ftell(fin);
		lnno++;
		if ((strlen(Buffer) == RecLen) && (Buffer[strlen(Buffer) - 1] != '\n')) {
			fprintf(stderr, "Record #%d exceeds maximum length %d\n",
					lnno, RecLen);
			exit(1);
			}
		strcpy(SortArray[i], Buffer);
		}
	return (i);
	}


 int
comp (const void *aa, const void *bb) {
	char          **a, **b;
	char            HoldA, HoldB;
	int             End, Result;
	QUE_ENTRY      *t;
	struct KeyEntry *v;

	a = (char **) aa;
	b = (char **) bb;
	if (*a == *b) return (0);
	if (*a == NULL) return (1);
	if (*b == NULL) return (-1);
	for (Result = 0, t = Keys->Head; (t != NULL) && (Result == 0); t = t->Next) {
		v = t->Body;
		End = v->Begin + v->Len;
		HoldA = (*a)[End];
		(*a)[End] = '\0';
		HoldB = (*b)[End];
		(*b)[End] = '\0';
		Result = (v->Order == 'a') ?
			(v->Case == 'i') ? stricmp(&(*a)[v->Begin], &(*b)[v->Begin])
			: strcmp(&(*a)[v->Begin], &(*b)[v->Begin])
			: (v->Case == 'i') ? stricmp(&(*b)[v->Begin], &(*a)[v->Begin])
			: strcmp(&(*b)[v->Begin], &(*a)[v->Begin]);
		(*a)[End] = HoldA;
		(*b)[End] = HoldB;
		}
	return (Result);
	}


 void
Usage (void) {
	fprintf(stderr, "USAGE: pdsort input_file output_file rec_len\n");
	exit(1);
	}