/* Author J. Zobel, August 2001.
   Permission to use this code is freely granted, provided that this
   statement is retained. */

/* Ternary quick sort */

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>

char	*malloc();
void	exit();


#define THRESHOLD  314


typedef struct trierec
{
    struct trierec *ptrs[128];
    short	counts[128];
} TRIE;

typedef struct listrec
{
    char	*word;
    struct listrec *next;
} LIST;


void ternaryqsort(char **, int);
void burstinsert(char *, TRIE *, LIST *);
int bursttraverse(TRIE *, char **, int, int);
int cmpit();
int scmp(char *, char *);

int
main(int argc, char *argv[])
{
    FILE        *fp, *fopen();
    int		c;
    int		i, k, ccnt, scnt;
    char	**thestrings;
    char	*tmp, *ptr;

    if( argc == 1 ) /* reading from standard input */
    {
	fprintf(stderr, "Usage: burstsort filename\n");
	exit(1);
    }
    else
    {
	if( ( fp = fopen(argv[1], "r") ) == NULL )
	{
	    fprintf(stderr, "%s: file not found.\n", argv[1]);
	    exit(1);
	}
    }

	/* how big is the file, how many strings? */
    for( ccnt=scnt=0 ; ( c = getc(fp) ) != EOF ; ccnt++ )
    {
	if( c=='\n' )
	    scnt++;
    }

/* fprintf(stderr, "found %d strings\n", scnt); */

	/* load the strings */
    thestrings = (char **) malloc(sizeof(char *) * ( scnt+1 ));
    tmp = (char *) malloc(sizeof(char) * ccnt);
    rewind(fp);
    fread(tmp, sizeof(char), ccnt, fp);
    thestrings[0] = tmp;
    for( k=i=0 ; i<ccnt ; i++ )
    {
	if( tmp[i]=='\n' )
	{
	    tmp[i] = '\0';
	    k++;
	    thestrings[k] = tmp+i+1;
	}
    }
    fclose(fp);

    ternaryqsort(thestrings, scnt);

    for( i=0 ; i<scnt ; i++ )
	printf("%s\n", thestrings[i]);

    exit(0);
}


void
ternaryqsort(char **strings, int scnt)
{
    void do_ternaryqsort(char **, int, int, int);

    do_ternaryqsort(strings, 0, scnt-1, 0);

    return;
}


void
do_ternaryqsort(char *strings[], int low, int up, int pos)
{
    char	*tmp;
    char	mid, c;
    int		curr, ltup, gtlow;

    if( low>=up )
	return;

    ltup = low;
    gtlow = up;
    mid = ( strings[up][pos]+strings[low][pos] ) /2;

    for( curr=ltup ; curr<=gtlow ; )
    {
	if( ( c=strings[curr][pos] )<mid )
	{
	    if( curr>ltup )
	    {
		tmp = strings[curr];
		strings[curr] = strings[ltup];
		strings[ltup] = tmp;
	    }
	    ltup++;
	    curr++;
	}
	else if( c>mid )
	{
	    /* if( curr<gtlow ) logically sensible but only true
		once so not efficient */
	    {
		tmp = strings[curr];
		strings[curr] = strings[gtlow];
		strings[gtlow] = tmp;
	    }
	    gtlow--;
	}
	else /* c==mid */
	{
	    curr++;
	}
    }

    do_ternaryqsort(strings, low, ltup-1, pos);
    if( strings[ltup][pos] != '\0' )
    {
	do_ternaryqsort(strings, ltup, gtlow, pos+1);
    }
    do_ternaryqsort(strings, gtlow+1, up, pos);

    return;
}