/*
	Sort/Merge from Software Tools

	Last Modified : 6 October 1982

	Converted from Software Tools RATFOR to BDS C by Leor Zolman
	Sep 2, 1982

	Usage: sort <infile> <outfile>

	Main variables have been made external; this is pretty much in
	line with the RATFOR call-by-name convention anyway.

	Requires lots of disk space, up to around three times the length
	of the file file being sorted. This program is intended for files
	bigger than memory; simpler, faster sorts can be implemented for
	really short files (like ALPH.C)
		-leor

	Compile & Link:
		A>cc sort.c -e2800 -o
		A>l2 sort
	(or...)
		A>cc sort.c -e2900 -o
		A>clink sort

*/


#include <bdscio.h>

#define VERBOSE 1		/* give running account of file activity */

#define MAXLINE 200		/* longest line we want to deal with */
#define NBUFS 7			/* Max number of open buffered files */
#define MAXPTR  3000		/* Max number of lines (set for dict) */
#define MERGEORDER (NBUFS-1)	/* Max # of intermediate files to merge */
#define NAMESIZE 20		/* Max Filename size */
#define LOGPTR 13		/* smallest value >= log (base 2) of  MAXPTR */
#define EOS '\0'		/* string termination character */
#define FILE struct _buf

#define stderr 4
#define fputc putc

char name[NAMESIZE], name2[NAMESIZE + 10];
FILE buffers[NBUFS + 1];	/* up to NBUFS general-purp. buffered files */
FILE *infil[MERGEORDER + 1];	/* tmp file ptrs for sort operation */
unsigned linptr[MAXPTR + 1], nlines;
int temp;
unsigned maxtext;		/* max # of chars in main text buffer */
char *linbuf;			/* text area starts after this variable */

main(argc,argv)
char **argv;
{

	FILE *infile, *outfile;		/* main input and output streams */
	FILE *tmpfile;

	int makfil(), min(), gopen(), gremov();
	int gtext();
	unsigned high, lim, low, t;

	linbuf = endext();		/* start of text buffer area */
	maxtext = topofmem() - endext() - 500;

	tmpfile = buffers[0];

	if (argc != 3)
		exit(puts("Usage: sort <infile> <outfile>\n"));

	infile = buffers[1];
	if (fopen(argv[1], infile) == ERROR)
	{
		puts("Can't open "); puts(argv[1]); exit(-1);
	}

#if VERBOSE
	fputs("Beginning initial formation run\n",stderr);
#endif

	high = 0;		/* Initial formation of runs:	*/
	do {
		t = gtext(infile);
		quick(nlines);		
		high++;
		makfil(high,tmpfile);
		ptext(tmpfile);
		fclout(tmpfile);
	} while (t != NULL);

	fclose(infile);		/* free up the input file buffer */

#if VERBOSE
	fputs("Beginning merge operation\n",stderr);
#endif

	for (low = 1; low < high; low += MERGEORDER)	/* merge */
	{
		lim = min(low + MERGEORDER - 1, high);
		gopen(low, lim);		/* open files */
		high++;
		makfil(high, tmpfile);
		merge(lim - low + 1, tmpfile);
		fclout(tmpfile);	/* terminate, flush and close file */
		gremov(low, lim);
	}

			/* Now write the sorted output file: */

	fputs("Merge complete.\n",stderr);

	gname(high, name);	/* create name of result file */
	infile = buffers[0];

	unlink(argv[2]);	/* remove any old copy of result file */
	if (rename(name,argv[2]) == ERROR)
	{
		puts("An error occurred in renaming the output file from ");
		puts(name); puts(" to "); puts(argv[2]);
	}
}


fclout(obuf)
FILE *obuf;
{
	putc(CPMEOF,obuf);
	fflush(obuf);
	fclose(obuf);
}


/*
 * Quick: Quicksort for character lines
 */

quick(nlines)
unsigned nlines;
{
	unsigned i,j, lv[LOGPTR + 1], p, pivlin, uv[LOGPTR + 1];
	int compar();

	lv[1] = 1;
	uv[1] = nlines;
	p = 1;
	while (p > 0)
		if (lv[p] >= uv[p])	/* only 1 element in this subset */
			p--;		/* pop stack			*/
		else
		{
			i = lv[p] - 1;
			j = uv[p];
			pivlin = linptr[j];	/* pivot line		*/
			while (i < j)
			{
			   for (i++; compar(linptr[i],pivlin) < 0; i++)
				;
			   for (j--; j > i; j--)
				if (compar(linptr[j], pivlin) <= 0)
					break;
			   if (i < j)	/* out of order pair		*/
			   {
				temp = linptr[i];
				linptr[i] = linptr[j];
				linptr[j] = temp;
			   }
			}
		j = uv[p];		/* move pivot to position 1 	*/

		temp = linptr[i];
		linptr[i] = linptr[j];
		linptr[j] = temp;

		if ( (i - lv[p]) < (uv[p] - i))
		  {
			lv[p + 1] = lv[p];
			uv[p + 1] = i - 1;
			lv[p] = i + 1;
		  }
		else
		  {
			lv[p + 1] = i + 1;
			uv[p + 1] = uv[p];
			uv[p] = i - 1;
		  }
		p++;
		}			
	return;
}			


/*
 * Compar: Compare two strings; return 0 if equal, -1 if first is
 *	   lexically smaller, or 1 if first is bigger
 */

int compar(lp1, lp2)
unsigned lp1, lp2;
{
	unsigned i, j;

	for (i = lp1, j = lp2; linbuf[i] == linbuf[j]; i++,j++)
	{
		if (linbuf[i] == EOS)
			return 0;
	}

	return (linbuf[i] < linbuf[j]) ? -1 : 1;
}

/*
 * Ptext: output text lines from linbuf onto the buffered output file given
 */

ptext(outfil)
FILE *outfil;
{
	int i;

	for (i = 1; i <= nlines; i++) {
		if (fputs(&linbuf[linptr[i]], outfil) == ERROR) {
			fputs("Error writing output file..disk full?\n",
					stderr);
			exit(-1);
		}
	}
	return 0;
}


/*
 * Gtext: Get text lines from the buffered input file provided, and
 * 	  place them into linbuf
 */

int gtext(infile)
FILE *infile;
{
	unsigned lbp, len;

	nlines = 0;
	lbp = 1;
	do {
		if ( (len = fgets(&linbuf[lbp], infile)) == NULL)
			break;
		len = strlen(&linbuf[lbp]);
		nlines++;
		linptr[nlines] = lbp;
		lbp += len + 1;
	} while ( lbp < (maxtext - MAXLINE) && nlines < MAXPTR);

	return len;		/* return 0 if done with file */
}


/*
 * Makfil: Make a temporary file having suffix 'n' and open it for
 * 	   output via the supplied buffer
 */

FILE *makfil(n,obuf)	/* make temp file having suffix 'n' */
int n;
FILE *obuf;
{
	FILE *fp;
	char name[20];
	gname(n,name);
	if (fcreat(name,obuf) == ERROR) {
		puts("Can't create "); puts(name); exit(-1);
	}
	return 0;
}


/*
 * Gname: Make temporary filename having suffix 'n'
 */

char *gname(n,name)
char *name;
int n;
{
	char tmptext[10];

	strcpy(name,"TEMP");		/* create "TEMPn.$$$"	*/
	strcat(name,itoa(tmptext,n));
	strcat(name,".$$$");
	return name;		/* return a pointer to it	*/
}


/*
 * Itoa: convert integer value n into ASCII representation at strptr,
 * 	 and return a pointer to it
 */

char *itoa(strptr,n)
char *strptr;
int n;
{
	int length;

	if (n < 0)
	{
		*strptr++ = '-';
		strptr++;
		n = -n;
	}

	if (n < 10)
	{
		*strptr++ = (n + '0');
		*strptr = '\0';
		return strptr - 1;
	}
	else
	{
		length = strlen(itoa(strptr, n/10));
		itoa(&strptr[length], n % 10);
		return strptr;
	}
}


/*
 * Gopen: open group of files low...lim
 */

gopen(low, lim)
int lim, low;
{
	int i;

#if VERBOSE
	fprintf(stderr,"Opening temp files %d-%d\n",low,lim);
#endif

	for (i = 1; i <= (lim - low + 1); i++)
	{
		gname(low + i - 1, name);
		if (fopen(name, buffers[i]) == ERROR)
		{
			puts("Can't open: "); puts(name); exit(-1);;
		}
		infil[i] = &buffers[i];
	}
}


/*
 * Remove group of files low...lim
 *		(should use "close" instead of "fabort" for MP/M II)
 */

gremov(low, lim)
int lim, low;
{
	int i;

#if VERBOSE
	fprintf(stderr,"Removing temp files %d-%d\n",low,lim);
#endif
	for (i = 1; i <= (lim - low + 1); i++)
	{
		fabort(infil[i]->_fd);		/* forget about the file */
		gname(low + i - 1, name);
		unlink(name);			/* and physically remove it */
	}
}

/*
 * Fputs: special version that aborts on output error:
 */

fputs(s,iobuf)
char *s;
FILE *iobuf;
{
	char c;
	while (c = *s++)
	{
		if (c == '\n') putc('\r',iobuf);
		if (putc(c,iobuf) == ERROR)
		{
			fputs("Error on file output\n",stderr);
			exit(ERROR);
		}
	}
	return OK;
}


/*
 * Merge: merge infil[1]...infil[nfiles] onto outfil
 */

merge(nfiles, outfil)
FILE *outfil;
{
	char *fgets();
	int i, inf, lbp, lp1, nf;

	lbp = 1;
	nf = 0;
	for (i = 1; i <= nfiles; i++)  /* get one line from each file */
		if (fgets(&linbuf[lbp], infil[i]) != NULL)
		{
			nf++;
			linptr[nf] = lbp;
			lbp += MAXLINE;	/* leave room for largest line */
		}

	quick(nf);		/* make initial heap */

	while (nf > 0) {
		lp1 = linptr[1];
		fputs(&linbuf[lp1], outfil);				
		inf = lp1 / MAXLINE + 1;	/* compute file index */
		if (fgets(&linbuf[lp1],infil[inf]) == NULL)
		{
			linptr[1] = linptr[nf];
			nf--;
		}
		reheap(nf);

	}
	return;
}

		
/*
 * Reheap: propogate linbuf[linptr[1]] to proper place in heap
 */

reheap(nf)
unsigned nf;
{
	unsigned i,j;

	for (i = 1; (i + i) <= nf; i = j)
	{
		j = i + i;
		if (j < nf && compar(linptr[j], linptr[j + 1]) > 0)
			j++;
		if (compar(linptr[i], linptr[j]) <= 0)
			break;

		temp = linptr[i];
		linptr[i] = linptr[j];
		linptr[j] = temp;
	}
	return;
}

