#
/*
 * Sort utility subroutines.
 *
 * Usage:
 *	sorta(record);
 *	char	*record;
 *
 *		Add this record to the stuff to be sorted.
 *		After adding the last record, execute sorta(NULL)
 *		to terminate processing.
 *
 *	char *sorto(record)
 *
 *		Return the next record, moving it into record.
 *		sorto() returns record if ok, NULL if finished.
 *
 * Note:
 *
 *	Calling sorta() after calling sorto() will reinitialize
 *	everything.
 *
 *	sorta() normally sorts the entire line in ascending Ascii
 *	ordering.  The following global symbols may be redefined
 *	as needed:
 *
 *	    int	*(sort_c)()	Defines the sort function.
 *				Default is strcmp()
 *
 *	    int	sort_r		Reverses the sense of the comparison.
 *
 *	  char *sort_f		The sort work file, normally sort.tmp.
 *
 *
 * Error messages (all fatal):
 *
 *	"Sort: cannot create temp. file "sort.tmp"
 *		if the required temporary file cannot be created 
 *		in the current directory.
 *	"Sort: out of space"
 *		if the sort runs out of memory.
 *
 *	The following messages occur on a disasterous error.  Get help.
 *		"Sort bug: Unexpected end of file"
 *		"Sort bug: empty run"
 *		"Sort bug: temp. file"
 *
 *
 * To use your own comparison function, stuff its address in sort_c.
 * It will be called with pointers to the two argument strings and
 * must return -1, 0, +1 according to whether the first argument
 * is less than, equal to, or greater than, the second.
 *
 * Author:
 *	David Conroy
 *
 *	Revised by Martin Minow.
 *
 *
 * Warning:
 *
 *	The sort algorithm is recursive.  You must task-build with
 *	a large enough stack.  The following seems to work:
 *		tkb
 *		foo=foo,sorts,c:c/lb
 *		/
 *		stack = 2000
 *		//
 *
 *	As the VMS native C library currently lacks ftell() and fmkdl(),
 *	this routine may be used only with the Decus compiler.
 *
 */

#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;
};

static	struct	run *curr_run	= NULL;
static	struct	run *first_run	= NULL;
static	struct	run *last_run	= NULL;
static	char	**line;
static	FILE	*tfp		= NULL;

static	struct	heap	*heap;

static	struct	run	*run_pointer;
static	struct	heap	*heap_pointer;

static	int	nline	=	0;
static	int	nruns	=	0;
static	char	lbuf[128];

/*
 * The following may be changed by the caller to modify the sort
 */

extern	int	(*sort_c)();	/* Sort function			*/
extern	int	sort_r;		/* Reverse order			*/
extern	char	*sort_f;	/* Sort file name			*/

extern	int	strcmp();	/* Default string compare		*/
int	(*sort_c)() = &strcmp;	/* Define default compare routine	*/
int	sort_n	=	0;	/* Non-zero for numeric comparison	*/
int	sort_r	=	0;	/* Non-zero for reverse comparison	*/
char	*sort_f	=	TEMP;	/* Change for a different temp. file	*/

static	int	first	=	1;
/*
 * First values:
 *	+1		Before first call of sorta (sorto illegal)
 *	 0		During calls to sorta
 *	-1		During calls to sorto
 */

sorta(datum)
char	*datum;
/*
 * Add datum to the stuff to be sorted
 */
{
	register char	*cp;
	register int	ndatum;
	char		*malloc();
	char		*nalloc();

	if (first != 0) {
		first = 0;
		if ((tfp = fopen(sort_f, "wun")) == NULL) {
			error("Cannot create temp file \"%s\"\n", sort_f);
		}
		line = nalloc(NLINE * sizeof(char *));
		curr_run  = nalloc(sizeof(struct run));

	}
	if (datum != NULL) {
		ndatum = strlen(datum) + sizeof(char);
		if (nline >= NLINE || (cp = malloc(ndatum)) == NULL) {
			quick(0, nline-1);
			saverun();
			curr_run = nalloc(sizeof(struct run));
			cp  = nalloc(ndatum);
		}
		strcpy(cp, datum);
		line[nline++] = cp;
	}
	/*
	 * sorta(NULL) called, finish off the last run.
	 */
	else {
		quick(0, nline-1);
		if (first_run == NULL) {
			heap_pointer = NULL;
			nruns = 0;
		}
		else {
			saverun();
			mfree(line);
			if (freopen(sort_f, "run", tfp) == NULL)
				error("?sort-Can't reopen temp. file.\n");
			heap = nalloc(nruns * sizeof(struct heap));
			run_pointer = first_run;
			heap_pointer = &heap[nruns];
		}
		first = -1;		/* Flag sorta(NULL) called	*/
	}
}

char *
sorto(buffer)
char	*buffer;	/* Where output goes				*/
/*
 * Write the next record to the output buffer
 */
{
	register struct	run	*rp;
	register struct heap	*hp;
	register char		*cp;
	char			*nalloc();
	char			*getline();

	if (first != -1)
		error("sorto out of sync");
	/*
	 * If only one buffer load, do it here
	 */
	if ((hp = heap_pointer) == NULL) {
		if (nruns >= nline) {
			goto alldone;
		}
		else {
			strcpy(buffer, line[nruns]);
			mfree(line[nruns]);
			nruns++;
			return(buffer);
		}
	}			
	/*
	 * Multiple runs, first build the heap
	 */
	for (rp = run_pointer; rp != NULL; rp = rp->r_rp) {
		--hp;
		hp->h_rp = rp;
		if ((hp->h_lp = getline(rp)) == NULL)
			error("?sort-Empty run.\n");
		reheap(hp, &heap[nruns]-hp);
	}
	run_pointer = NULL;
	if (nruns) {
		cp = heap[0].h_lp;
		strcpy(buffer, cp);
		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);
		return(buffer);
	}
alldone:
	first = 1;			/* All done		*/
	if (tfp != NULL)
		fmkdl(tfp);
	return(NULL);
}


/*
 * Hoare's quicksort.
 */
static
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.
 */
static
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;
	}
}

/*
 * 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.
 */
static char *
getline(rp)
register struct run *rp;
{
	register char	*cp;
	register int	size;
	char		*nalloc();
	long ftell();

	if (rp->r_size == 0)
		return (NULL);
	flseek(tfp, rp->r_seek, 0);
	size = fget(lbuf, sizeof lbuf, tfp);
	if (feof(tfp))
		error("?sort-Unexpected end of file\n");
	rp->r_seek = ftell(tfp);
	--rp->r_size;
	cp = nalloc(size);
	strcpy(cp, lbuf);
	return (cp);
}

/*
 * Save a run.
 * The run block has been preallocated
 * because there may not be enough space
 * to allocate it now.
 *
 * Dump the lines in the array `line' to
 * the temp. file.
 */
static
saverun()
{
	register i;
	long ftell();

	curr_run->r_rp = NULL;
	curr_run->r_seek = ftell(tfp);
	curr_run->r_size = nline;
	if (first_run == NULL)
		first_run = curr_run;
	else
		last_run->r_rp = curr_run;
	last_run = curr_run;
	++nruns;
	for (i=0; i<nline; ++i) {
		fput(line[i], strlen(line[i]) + 1, tfp);
		mfree(line[i]);
	}
	nline = 0;
}

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

	c = (*sort_c)(a, b);
	if (sort_r)
		c = -c;
	return (c);
}

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

	if ((p = malloc(n)) == NULL) {
		error("sort: out of space.\n");
	}
	return (p);
}