/*
**	SORT_C	sort lines of text
*/

#include	stdio_h

#define	NOCCARGC

#define	MAXFN		36
#define	EXTMARK	'_'
#define	MAXLINE	192

#define	CRTWIDE	80
#define	CRTHIGH	20
#define	PTRWIDE	80
#define	PTRHIGH	66
#define	PTRSKIP	8
#define	PTRHDR	2

#define	MAXPAT	257
#define	CHAR		'c'
#define	BOL		'%'
#define	EOL		'$'
#define	ANY		'.'
#define	CCL		'['
#define	NCCL		'^'
#define	CCLEND	']'
#define	CLOSURE	'*'
#define	DITTO		'&'
#define	ESCAPE	'\\'
#define	NOT		'^'

#define	DITCODE	-3
#define	COUNT		1
#define	PREVCL	2
#define	START		3
#define	CLOSIZE	4

#define	SHELL			1
#define	QUICK			2
#define	WRTMODE		2
#define	MAXRUNS		99
#define	LOGPTR		20
#define	AVGLIN		28
#define	RESERVE		2000
#define	MERGEORDER	5

char
	*linbuf,
	outnam[MAXFN],
	tmpdrv,
	lastline[MAXLINE+1],
	*maxbuf,
	*maxlin,
	tmpout[] = "ram1_sort00.$$$",
	tmpinp[] = "ram1_sort00.$$$",
	tmpdel[] = "ram1_sort00.$$$",
	delim;

int
	field,
	tmpfd[MERGEORDER],
	*linptr,
	nlines,
	low,
	lim,
	high,
	outfil,
	output,
	t,
	order,
	unique,
	typesort;

main(argc, argv) int argc, *argv; {
	lastline[0] = outnam[0] = 0;
	tmpdrv = 'X';
	doargs(argc, argv);
/*
	if (tmpdrv == 'X') {
		strcpy(tmpout, tmpout+2);
		strcpy(tmpinp, tmpinp+2);
		strcpy(tmpdel, tmpdel+2);
		}
	else tmpout[0] = tmpinp[0] = tmpdel[0] = tmpdrv;
*/
	output = stdout;
	if ((lim = avail(YES)) < 0) lim = 32767;
	maxlin = (lim - RESERVE)/(2 + AVGLIN);
	linptr = malloc(2*maxlin);
	if ((lim = avail(YES)) < 0) lim = 32767;
	maxbuf = lim - RESERVE;
	linbuf = malloc(maxbuf);
	high = 0;
	while (YES) {
		if (++high >= MAXRUNS) {
			fputs("File too large\n", stderr);
			abort(-1);
			}
		t = gtext();
		sort(0, nlines-1);
		if (high == 1) {
			if (t == NULL) {
				outfil = output;
				ptext();
				fclose(outfil);
				exit(0);
				}
			}
		maketmp();
		ptext();
		fclose(outfil);
		if (t == NULL) break;
		}
	free(linbuf);
	free(linptr);
	linptr = malloc(2*(MERGEORDER+1));
	linbuf = malloc(MERGEORDER*(MAXLINE+1));
	lastline[0] = 0;
	low = 1;
	while (low < high) {
		lim = low + MERGEORDER - 1;
		if (high < lim) lim = high;
		t = 0;
		while (t <= (lim - low)) {
			bumptmp(tmpinp);
			if ((tmpfd[t++] = fopen(tmpinp, "r")) == NULL) cant(tmpinp);
/*			auxbuf(tmpfd[t++], 2048);		*/
			}
		if (lim == high) outfil = output;
		else maketmp();
		if (++high >= MAXRUNS) {
			fputs("File too large\n", stderr);
			abort(-1);
			}
		merge(lim - low + 1);
		fclose(outfil);
		t = 0;
		while (t <= (lim - low)) {
			fclose(tmpfd[t++]);
			killtmp();
			}
		low = low + MERGEORDER;
		}
	}

doargs(argc, argv) int argc, *argv; {
	char	arg[MAXFN], c;
	int i, error, len;
	field = 0;
	delim = 0;
	order = 1;
	typesort = SHELL;
	unique = error = NO;
	i = 0;
	while (getarg(++i, arg, MAXFN, argc, argv) != EOF) {
		c = arg[1];
		if (arg[0] != '-') error = YES;
		else if	(same(c, 't') &&
					(toupper(arg[2]) > 'A') &&
					(toupper(arg[2]) < 'G') &&
					(arg[3] == 0))
					tmpdrv = arg[2];
		else if (same(c, 'c')) {
			delim = 0;
			if (arg[utoi(arg+2, &field) + 2] != 0) error = YES;
			if (field) --field;
			}
		else if (same(c, 'f')) {
			if (arg[(len = utoi(arg+2, &field)) + 2] > ' ') {
				delim = arg[len+2];
				if (arg[len+3] != 0) error = YES;
				}
			else delim = ' ';
			if (field) --field;
			field = -field;
			}
		else if (arg[2] != 0) error = YES;
		else if (same(c, 'd')) order = -1;
		else if (same(c, 'u')) unique = YES;
		else if (same(c, 'q')) typesort = QUICK;
		else error = YES;
		if (error) {
			fputs("Usage: sort [-c#|-f#?] [-d] [-u] [-tx] [-q]\n", stderr);
			abort(-1);
			}
		}
	}

gtext() {
	int	len;
	char	*lbp;
	lbp = 1;
	nlines = 0;
	while (YES) {
/*		poll(YES);		*/
		if ((len = readline(linbuf+lbp, stdin)) == NULL) break;
		linptr[nlines++] = lbp;
		lbp = lbp + len;
		if (((lbp+1) >= (maxbuf-(MAXLINE+1))) || (nlines >= maxlin))
			break;
		}
	return len;
	}

ptext() {
	int	i;
	char	*lbp;
	i = 0;
	while (i < nlines) {
/*		poll(YES);				*/
		lbp = linbuf + linptr[i++];
		if (duptest(lbp)) continue;
		sout(lbp, outfil);
		}
	}

duptest(line) char *line; {
	int	diff;
	if (!unique) return (NO);
	diff = lexcmp(lastline, line);
	strcpy(lastline, line);
	return (!diff);
	}

bumptmp(tmpname) char tmpname[]; {
	char	*digit;
	digit = strchr(tmpname, '.') - 1;
	if (*digit == '9') {
		*digit = '0';
		--digit;
		}
	++*digit;
	}

maketmp() {
	bumptmp(tmpout);
	if ((outfil = fopen(tmpout, "w")) == NULL) cant(tmpout);
	}

killtmp() {
	bumptmp(tmpdel);
	delete(tmpdel);
	}

sort(lv, uv) int lv, uv; {
	if (typesort == QUICK)	quick(lv, uv);
	else							shell(lv, uv);
	}

shell(lv, uv) int lv, uv; {
	int	gap, i, j, jg;
	gap = (uv - lv + 1) >> 1;
	while (gap > 0) {
/*		poll(YES);			*/
		i = gap + lv;
		while (i <= uv) {
			j = i++ - gap;
			while (j >= lv) {
				jg = j + gap;
				if (compare(linptr[j], linptr[jg]) <= 0) break;
				exchange(j, jg);
				j = j - gap;
				}
			}
		gap = gap >> 1;
		}
	}

quick(lv, uv) int lv, uv; {
	int	i, j, pivlin;
	avail(YES);
/*	poll(YES);			*/
	if (lv >= uv) return;
	i = lv - 1;
	j = uv;
	pivlin = linptr[j];
	while (i < j) {
		++i;
		while (compare(linptr[i], pivlin) < 0) ++i;
		--j;
		while (i < j) {
			if (compare(linptr[j], pivlin) > 0) --j;
			else break;
			}
		if (i < j) exchange(i, j);
		}
	j = uv;
	exchange(i, j);
	if ((i - lv) < (uv - i)) {
		quick(lv, i-1);
		quick(i+1, uv);
		}
	else {
		quick(i+1, uv);
		quick(lv, i-1);
		}
	}

compare(p1, p2) int p1, p2; {
	char	*ptr1, *ptr2;
	ptr1 = linbuf + (p1 - 1);
	ptr1 = ptr1 + *ptr1;
	ptr2 = linbuf + (p2 - 1);
	ptr2 = ptr2 + *ptr2;
	while (lexorder(*++ptr1, *++ptr2) == 0)
		if ((*ptr1 == 0) || (delimit(*ptr1))) return 0;
	if (delimit(*ptr1)) return -order;
	if (delimit(*ptr2)) return  order;
	if (lexorder(*ptr1, *ptr2) > 0) return order;
	return -order;
	}

delimit(c) char c; {
	if (c > delim)		return NO;
	if (delim == ' ') return YES;
	if (c < delim)		return NO;
	return YES;
	}

exchange(i, j) int i, j; {
	int	k;
	k = linptr[i];
	linptr[i] = linptr[j];
	linptr[j] = k;
	}

merge(nfiles) int nfiles; {
	int	i, inf, lbp, lp1, nf;
	char	*ptr;
	lbp = 1;
	nf = i = 0;
	while (i < nfiles) {
		if (readline((linbuf + lbp), tmpfd[i++]) != NULL) {
			linptr[++nf] = lbp;
			lbp = lbp + (MAXLINE + 1);
			}
		}
	sort(1, nf);
	while (nf > 0) {
/*		poll(YES);			*/
		lp1 = linptr[1];
		ptr = linbuf + lp1;
		if (duptest(ptr) == NO) sout(ptr, outfil);
		inf = (lp1/(MAXLINE + 1));
		if (readline((linbuf + lp1), tmpfd[inf]) == NULL)
			linptr[1] = linptr[nf--];
		reheap(nf);
		}
	}

reheap(nf) int nf; {
	int	i, j;
	i = 1;
	while ((j = (i << 1)) <= nf) {
		if (j < nf) {
			if (compare(linptr[j], linptr[j+1]) > 0) ++j;
			}
		if (compare(linptr[i], linptr[j]) <= 0) break;
		exchange(i, j);
		i = j;
		}
	}

readline(str, fd) char *str; int fd; {
	int	fld;
	char	*ptr, *offset;
	if (fgets(str, MAXLINE+1, fd) == NULL) return NULL;
	ptr = offset = str - 1;
	fld = field;
	if (delim) {
		*offset = -1;
		while (*(++ptr)) {
			if (fld < 0) {
				if (delim == ' ') {
					if ((*ptr > ' ') && (*(ptr+1) <= ' ')) ++fld;
					}
				else if (*ptr == delim) ++fld;
				}
			else if ((fld == 0) && ((delim != ' ') || (*ptr > ' '))) {
				*offset = (ptr - str);
				fld = 1;
				}
			}
		if (*offset == -1) *offset = (ptr - str);
		}
	else {
		while (*(++ptr));
		if (field < (ptr - str)) *offset = field;
		else							 *offset = (ptr - str);
		}
	return (ptr - str + 2);
	}

/*
**	CANT_C	abort with "name: can't open" message
*/

cant(str) char *str; {
	fputs(str, stderr);
	fputs(": can't open\n", stderr);
	abort(-1);
	}

/*
** SAME_C	returns YES if c same as lower case lc, else NO
**				c may be upper or lower case
*/

same(c, lc) char c, lc; {
	if ((c >= 'A') && (c <= 'Z')) c = c + 32;
	if (c == lc) return YES;
	return NO;
	}

sout(string, fd) char *string; int fd; {
	if (fputs(string, fd) == EOF) xout();
	}

xout() {
	fputs("Output error\n", stderr);
	abort(-1);
	}