/*
 * Sort utility.
 *
 * Updated 13-Mar-80 for the new RSX library.
 *
 *	sort [-nr] [-o outputfile] [file ...]
 *
 *	Sort sorts all of the named files together and writes the  result
 *	to  the standard output.  The standard input is sorted if no file
 *	names are supplied;  sort may be used as a filter.
 *
 *	The `-o' option causes the sorted output to  be  written  to  the
 *	named  output file instead of to the standard output.  The output
 *	file may be the same as one of the input files.
 *
 *	The default sort key is the entire  line.   Default  ordering  is
 *	lexicographic  in  ASCII  collating sequence with upper and lower
 *	case considered different.
 *
 *	The `-n' option changes the ordering to ascending arithmetic on a
 *	leading numeric string consisting of digits and an optional sign.
 *
 *	The `-r' option reverses the sense of the comparisons.
 *
 * Error messages:
 *
 *	"Cannot create temp. file"  if the required temporary file cannot
 *		be  created  in  the  current directory.
 *	"Cannot open" if a file cannot be accessed for reading.
 *	"Cannot create" if a file cannot be  created  for writing.
 *	"Out of space" if the sort runs out of memory.
 *
 *	The following messages occur on a fatal error.  Get help.
 *		"Panic: Unexpected end of file"
 *		"Panic: empty run"
 *		"Panic: temp. file"
 *
 * Author:
 *	David Conroy
 *	Very slightly modified by Martin Minow
 *
 *
 * Warning:
 *
 *	The sort algorithm is recursive.  You must task-build with
 *	a large enough stack.  The following seems to work:
 *		tkb
 *		sort=sort,c:c/lb
 *		/
 *		stack = 2000
 *		//
 *
 *	The "native" C library currently lacks the ftell() function,
 *	Thus, the routine may be used only with the Decus (PDP-11
 *	compatibility mode) library.
 *
 */

#include <stdio.h>

#define	 NLINE	200
#define	 TEMP	"sort.tmp"

struct	run
{
	struct	run *r_rp;
	long	r_seek;
	int	r_size;
};

struct	heap
{
	struct	run *h_rp;
	char	*h_lp;
};

struct	run *crp  = NULL;
struct	run *frp  = NULL;
struct	run *lrp  = NULL;
char	**line;
FILE	*ofp;
FILE	*tfp	= NULL;
FILE	*ifp	= NULL;
char	*ofn	= NULL;
struct	heap *heap;
int	nline	= 0;
int	nruns	= 0;
char	lbuf[128];
int	nflag;
int	rflag;

extern	char *getline();
extern	char *nalloc();

main(argc, argv)
char *argv[];
{
	register struct run *rp;
	register char *cp;
	register nlbuf;
	struct heap *hp;
	int c, i, nf;

	nf = argc - 1;
	for (i=1; i<argc; ++i) {
		cp = argv[i];
		if (*cp == '-') {
			--nf;
			argv[i] = NULL;
			++cp;
			while (c = *cp++)
				switch (c) {

				case 'n':
				case 'N':
					++nflag;
					break;

				case 'o':
				case 'O':
					if (++i >= argc)
						usage();
					ofn = argv[i];
					--nf;
					argv[i] = NULL;
					break;

				case 'r':
				case 'R':
					++rflag;
					break;

				default:
					usage();
				}
		}
	}
	if (nf == 0)
		ifp = stdin;
	if ((tfp = fopen(TEMP, "w")) == NULL) {
		fprintf(stderr, "Cannot create temp. file.\n");
		exit(1);
	}
	line = nalloc(NLINE * sizeof(char *));
	crp  = nalloc(sizeof(struct run));
	for (;;) {
		if (ifp == NULL) {
			for (i=1; i<argc; ++i)
				if ((cp = argv[i]) != NULL)
					break;
			if (i >= argc)
				break;
			argv[i] = NULL;
			if ((ifp = fopen(cp, "r")) == NULL) {
				fprintf(stderr, "%s: cannot open.\n", cp);
				quit();
			}
		}
		if (fgets(lbuf, sizeof lbuf, ifp) == NULL) {
			if (nf == 0)
				break;
			fclose(ifp);
			ifp = NULL;
			continue;
		}
		nlbuf = strlen(lbuf) + sizeof(char);
		if (nline >= NLINE || (cp = malloc(nlbuf)) == NULL) {
			quick(0, nline-1);
			saverun();
			putline(tfp);
			crp = nalloc(sizeof(struct run));
			cp  = nalloc(nlbuf);
		}
		strcpy(cp, lbuf);
		line[nline++] = cp;
	}
	quick(0, nline-1);
	if (frp == NULL) {
		openoutput();
		putline(ofp);
		quit();
	}
	saverun();
	putline(tfp);
	fclose(tfp);
	mfree(line);
	openoutput();
	if ((tfp = fopen(TEMP, "r")) == NULL)
		panic("Temp. file.\n");
	heap = nalloc(nruns * sizeof(struct heap));
	rp = frp;
	hp = &heap[nruns];
	while (rp != NULL) {
		--hp;
		hp->h_rp = rp;
		if ((hp->h_lp = getline(rp)) == NULL)
			panic("Empty run.\n");
		reheap(hp, &heap[nruns]-hp);
		rp = rp->r_rp;
	}
	while (nruns) {
		cp = heap[0].h_lp;
		fputs(cp, ofp);
		mfree(cp);
		if ((heap[0].h_lp = getline(heap[0].h_rp)) == NULL) {
			--nruns;
			heap[0].h_rp = heap[nruns].h_rp;
			heap[0].h_lp = heap[nruns].h_lp;
		}
		reheap(heap, nruns);
	}
	quit();
}

/*
 * Open the output file and stash its file
 * pointer in `ofp'. If no output file is
 * given `ofp' is a dup. of `stdout'.
 */
openoutput()
{
	if (ofn == NULL)
		ofp = stdout;
	else if ((ofp = fopen(ofn, "w")) == NULL) {
		fprintf(stderr, "%s: cannot create.\n", ofn);
		quit();
	}
}

/*
 * Hoare's quicksort.
 */
quick(m, n)
{
	register i, j;
	char *p, *t;

	if (m >= n)
		return;
	i = m - 1;
	j = n;
	p = line[j];
	while (i < j) {
		for (++i; compare(line[i], p) < 0; ++i)
			;
		for (--j; j > i; --j)
			if (compare(line[j], p) <= 0)
				break;
		if (i < j) {
			t = line[i];
			line[i] = line[j];
			line[j] = t;
		}
	}
	t = line[i];
	line[i] = line[n];
	line[n] = t;
	quick(m, i-1);
	quick(i+1, n);
}

/*
 * Rebuild a heap.
 * Used to build the initial heap and
 * to reorder the heap when a new item
 * is read into it.
 */
reheap(h, n)
register struct heap *h;
{
	register i, j;
	struct run *trp;
	char *tlp;

	for (i = 0; (j = 2*i+1) < n; i = j) {
		if (j+1 < n && compare(h[j+1].h_lp, h[j].h_lp) < 0)
			++j;
		if (compare(h[i].h_lp, h[j].h_lp) <= 0)
			break;
		trp = h[i].h_rp;
		h[i].h_rp = h[j].h_rp;
		h[j].h_rp = trp;
		tlp = h[i].h_lp;
		h[i].h_lp = h[j].h_lp;
		h[j].h_lp = tlp;
	}
}

/*
 * Save a run.
 * The run block has been preallocated
 * because there may not be enough space
 * to allocate it now.
 */
saverun()
{
	long ftell();

	crp->r_rp = NULL;
	crp->r_seek = ftell(tfp);
	crp->r_size = nline;
	if (frp == NULL)
		frp = crp;
	else
		lrp->r_rp = crp;
	lrp = crp;
	++nruns;
}

/*
 * Get a line from the specified run
 * on the temp. file.
 * Pack the line into allocated storage
 * and return a pointer to it.
 * Return NULL if there are no lines left
 * in the run; real end of file is an
 * internal botch.
 */
char *
getline(rp)
register struct run *rp;
{
	register char *cp;
	long ftell();

	if (rp->r_size == 0)
		return (NULL);
	flseek(tfp, rp->r_seek, 0);
	if (fgets(lbuf, sizeof lbuf, tfp) == NULL)
		panic("Unexpected end of file\n");
	rp->r_seek = ftell(tfp);
	--rp->r_size;
	cp = nalloc(strlen(lbuf) + sizeof(char));
	strcpy(cp, lbuf);
	return (cp);
}

/*
 * Dump the lines in the array `line' to
 * the temp. file.
 */
putline(fp)
register FILE *fp;
{
	register i;
	for (i=0; i<nline; ++i) {
		fputs(line[i], fp);
		mfree(line[i]);
	}
	nline = 0;
}

/*
 * Compare routine.
 */
compare(a, b)
char *a, *b;
{
	register c;
	long d, atol();

	if (nflag) {
		c = 0;
		if ((d = atol(a)-atol(b)) < 0)
			--c;
		else if (d > 0)
			++c;
	} else
		c = strcmp(a, b);
	if (rflag)
		c = -c;
	return (c);
}

/*
 * Allocate space.
 * If no space, abort with a nasty
 * little message.
 */
char *
nalloc(n)
{
	register char *p;

	if ((p = malloc(n)) == NULL) {
		fprintf(stderr, "Out of space.\n");
		exit(1);
	}
	return (p);
}

/*
 * Quit.
 * Get rid of the temp. file.
 * Exit.
 */
quit()
{
	if (tfp != NULL)
		fmkdl(tfp);
	exit(0);
}

/*
 * Tell the user just what is expected
 * of him.
 */
usage()
{
	fprintf(stderr, "Usage: sort [-nr] [-o outputfile] [file ...]\n");
	exit(1);
}

/*
 * Fatal errors.
 * Print a message and die.
 */
panic(a)
{
	fprintf(stderr, "Panic: %r", &a);
	exit(1);
}