/*---------------------------------------------------------------------------
 * AVLSORT From,To,COLSTART/k,WIDTH/k,CASE/s,REVERSE/s
 *
 * AMIGA Usage: AvlSort <infile> [TO outfile] [starting at column] \
 *			[CASE-sensitive] [REVERSE order]
 *
 * MSDOS Usage: AVLSORT [infile] [outfile] [/COL n] [/WID n] [/U] [/R]
 *	infile	default is stdin
 *	outfile	default is stdout
 *	/COL n	start column; default is 1 (may use /C:n)
 *	/WID n	column width; default is all (may use /W:n)
 *	/U	unique case (case-sensitive)
 *	/R	reverse order
 *
 * Copyright (C) 1990 by Robert L. Pyron
 *
 * "This software may be used at will, provided that all credits
 * and style be left in place, and that its distribution is not
 * restricted."
 *
 * Robert L. Pyron, 24 June 90
 * BIX: rpyron
 *---------------------------------------------------------------------------
 */

#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avl.h"

#if	defined(LATTICE) && defined(AMIGA)	/* We link with ARP */
 #include <Arp/ArpBase.h>
#else
 #include <malloc.h>
 #define ArpAlloc(n) malloc( (unsigned short) (n) )
#endif

/*---------------------------------------------------------------------------
 * Typedefs and defines
 *---------------------------------------------------------------------------
 */

#define FALSE	0
#define TRUE	1
#define	TEXTMAX	32768

typedef	unsigned char	UCHAR;
typedef	unsigned short	USHORT;
typedef	unsigned long	ULONG;
typedef	UCHAR *		PCHAR;
typedef void *		PVOID;

typedef	struct _MYNODE {
	AVLNODE	avlnode;
	PCHAR	text;
	ULONG	textlen;
	ULONG	lineno;
	} MYNODE;
typedef	MYNODE		*PNODE;
#define	SZOF_MYNODE	sizeof(MYNODE)

typedef	int  (*PFNCOMPARE) __ARGS((const char *, const char *, unsigned int));


/*---------------------------------------------------------------------------
 * Prototypes
 *---------------------------------------------------------------------------
 */

int	cmdparse __ARGS(( int argc, char **argv ));
PVOID	myalloc __ARGS(( ULONG size ));
PNODE	newnode __ARGS(( PCHAR text, ULONG textlen, ULONG lineno ));
void	printtree __ARGS(( PNODE p ));

int	cmprtc  __ARGS(( void *keyP, AVLNODE *nodeP ));
AVLNODE *mknode __ARGS(( AVLTREE *treeP, void *keyP, void *dataP, AVLNODE *enodeP ));
void	rmnode  __ARGS(( AVLTREE *treeP, AVLNODE *nodeP ));

/*---------------------------------------------------------------------------
 * Global data
 *---------------------------------------------------------------------------
 */

#if	defined(LATTICE) && defined(AMIGA)

	/* Template and Extended Help for GADS(), from ARP */

extern	struct ArpBase	*ArpBase;

char	*CLI_Template	= "From,To,COLSTART/k,WIDTH/k,CASE/s,REVERSE/s";
char	*CLI_Help	= "Usage: AvlSort <infile> [TO outfile] "
			  "[starting at column] [CASE-sensitive]";

#else	/* Microsoft, MSDOS or OS2 */

char	*program	= "AVLSORT";
char	*usage		= "Usage: %s [infile] [outfile] [/COL n] [/WID n] [/U] [/R]";

#endif

	/* User may specify the following parameters on command line: */

char	*infile		= NULL;		/* input file name, default stdin */
char	*outfile	= NULL;		/* output file name, default stdout */
long	colstart	= 0;		/* start column, default 1 */
long	colwidth	= TEXTMAX-1;	/* width, default full line */
int	caseflag	= 0;		/* case sensitivity, default off */
int	reverseflag	= 0;		/* reverse sort, default off */

	/* This is our AVL tree. */

AVLTREE	avlTree = {
	NULL,
	(PFNCMPRTC)cmprtc,
	(PFNMKNODE)mknode,
	(PFNRMNODE)rmnode
	};
#define	avlRoot	((PNODE)avlTree.t_rootP)

	/*-----------------------------------------------------------
	 * Pointer to string comparison function. If case sensitivity
	 * is off (default), use strnicmp().  Otherwise use strncmp().
	 *------------------------------------------------------------
	 */

PFNCOMPARE	pfnCompare = (PFNCOMPARE) strnicmp;


/*---------------------------------------------------------------------------
 * Notice int return type, we are returning a value to Arp startup code.
 *---------------------------------------------------------------------------
 */

int	main( int argc, char **argv )
{
register int	byte;
	int	lastch;
	long	line_number	= 0;
	PNODE	pnew;
	int	status		= 10;	/* assume the worst */
register PCHAR	textbuf;
	ULONG	textlen;

	if ( (textbuf = ArpAlloc(TEXTMAX)) == NULL)
	{
		fprintf( stderr, "?? Out of memory\n" );
		goto hell;
	}

	/*-------------------------------
	 * Get options from command line.
	 *-------------------------------
	 */

	if (cmdparse(argc,argv))
		goto hell;

	if (--colstart < 0)	colstart = 0;	/* convert to zero-based */
	if (colwidth <= 0)	colwidth = TEXTMAX - 1;
	if (caseflag)		pfnCompare = (PFNCOMPARE) strncmp;

	/*--------------------------------------------
	 * Redirect stdin to named file, if specified.
	 *--------------------------------------------
	 */

	if (infile && *infile)
	{
		/* redirect stdin to specified file */

		FILE	*fp = freopen( infile, "r", stdin );

		if (fp == NULL)
		{
			fprintf( stderr,
				 "?? Cannot open file %s for input\n",
				 infile );
			goto hell;
		}
		else if (fp != stdin)
		{
			fprintf( stderr, "?? freopen() error\n" );
			goto hell;
		}
	}

	/*-----------------------------------------------------
	 * Read file, putting each line in the appropriate bin.
	 *-----------------------------------------------------
	 */

	lastch = (int) ' ';
	while ( lastch != EOF )
	{
		/*----------------------------------------------------------
		 * Read a line.  We assume that file is opened in text mode.
		 *----------------------------------------------------------
		 */

		textlen = 0;
		while ( byte = getchar() )
		{
			if (byte == EOF || byte == '\n' || byte == '\r')
				break;

			textbuf[textlen++] = (UCHAR) byte;
			if (textlen == TEXTMAX)
			{
				fprintf( stderr,
					"?? Fatal error: line exceeds %lu bytes.\n",
					TEXTMAX-1 );
				goto hell;
			}
		}
		if (byte == EOF && textlen == 0)
			break;

		lastch = byte;
		textbuf[textlen] = (UCHAR) '\0';

		/*---------------------------------------------
		 * Allocate space for line, and insert in tree.
		 *---------------------------------------------
		 */

		if ( (pnew = newnode(textbuf,textlen,line_number)) == NULL )
			goto hell;

		switch (avlinsert(&avlTree, pnew, NULL) )
		{
		case -1:	/* error */
			fprintf( stderr, "?? Cannot insert line (%lu): %s\n",
				pnew->lineno, pnew->text );
			break;

		case  0:	/* success */
			break;

		case  1:	/* duplicate key */
			fprintf( stderr, "?? Duplicate key (%lu): %s\n",
				pnew->lineno, pnew->text );
			break;
		}

		line_number++;
	}				

	/*---------------------------------------------
	 * Redirect stdout to named file, if specified.
	 * Close stdin because may be same file.
	 *---------------------------------------------
	 */

	if (outfile && *outfile)
	{
		/* redirect stdout to specified file */

		FILE	*fp = freopen( outfile, "w", stdout );
		if (fp == NULL)
		{
			fprintf( stderr,
				 "?? Cannot open file %s for output\n",
				 outfile );
			goto hell;
		}
		else if (fp != stdout)
		{
			fprintf( stderr, "?? freopen() error\n" );
			goto hell;
		}
	}

	/*------------
	 * Print file.
	 *------------
	 */

	printtree( avlRoot );

	status = 0;	/* ok */

hell:
	return( status );
}

#if	defined(LATTICE) && defined(AMIGA)	/* Amiga; we link with ARP */

/*--------------------------------------------------------------------
 * We link with S. Vigna's ARP startup code, which calls GADS() for us
 * and returns the result as argv[].  We can ignore argc, which is the
 * number of arguments actually supplied on the command line.
 *--------------------------------------------------------------------
 */

int	cmdparse( int argc, char **argv )
{
	char	*junk = NULL;
	int	error = 0;

	if (argc <= 0)
	{
		/* Workbench */
		return( -1 );
	}
	else if (argc > 7)
	{
		fprintf( stderr,
			 "?? Too many arguments\n%s\n%s\n",
			 CLI_Help, CLI_Template );
		return( -1 );
	}

	infile = argv[1];
	outfile = argv[2];
	if (argv[3])
	{
		colstart = strtol( argv[3], &junk, 10 );
		if (junk && *junk)
		{
			fprintf( stderr,
				 "?? Invalid digit \"%c\" for COLSTART\n",
				 *junk );
			error = -1;
		}
	}
	if (argv[4])
	{
		colwidth = strtol( argv[4], &junk, 10 );
		if (junk && *junk)
		{
			fprintf( stderr,
				 "?? Invalid digit \"%c\" for WIDTH\n",
				 *junk );
			error = -1;
		}
	}
	caseflag = (argv[5] != NULL);
	reverseflag = (argv[6] != NULL);

	return( error );
}

#else		/* Microsoft MSDOS or OS2; we have to roll our own parser */

/*-------------------------------------------------------------------
 *	Usage: AVLSORT [infile] [outfile] [/COL n] [/WID n] [/U] [/R]
 *	    infile	default is stdin
 *	    outfile	default is stdout
 *	    /COL n	start column; default is 1 (may use /C:n)
 *	    /WID n	column width; default is all (may use /W:n)
 *	    /U		unique case (case-sensitive)
 *	    /R		reverse order
 *-------------------------------------------------------------------
 */

#define	MATCHn(s,t,n)	(strnicmp(s,t,n) == 0)

int	cmdparse( int argc, char **argv )
{
	char	c, *p, *colon, *junk = NULL;
	int	i, helpflag = FALSE;
	int	error = 0;

	/*------------------
	 * Get program name.
	 *------------------
	 */

	if (argc > 0)
	{
		if   (!argv[0] || !*argv[0])	    ;  /* use default */
		else if (p = strrchr(argv[0],'\\')) program = p+1;
		else if (p = strrchr(argv[0],':'))  program = p+1;
		else				    program = argv[0];

		strupr(program);
	}

	/*------------------------------
	 * First pass: look for options.
	 *------------------------------
	 */

	for (i = 1; (i < argc) && !helpflag ; i++)
	{
		junk = NULL;

		if ( !(p = argv[i]) || !(c = *argv[i]) )
			continue;		/* no argument */

		else if ( c == '?')		/* user requested help */
			helpflag = TRUE;

		else if (c != '/' && c != '-')	/* not a switch */
			continue;

		else if (MATCHn(p+1,"COL",3) && (i+1) < argc)
		{
			colstart = strtol( argv[i+1], &junk, 0 );
			*argv[i+1] = 0;		/* ignore on second pass */
		}

		else if ( MATCHn(p+1,"C",1) && (colon = strchr(p+1,':')) )
			colstart = strtol( colon+1, &junk, 0 );

		else if (MATCHn(p+1,"WID",3) && (i+1) < argc)
		{
			colwidth = strtol( argv[i+1], &junk, 0 );
			*argv[i+1] = 0;		/* ignore on second pass */
		}

		else if ( MATCHn(p+1,"W",1) && (colon = strchr(p+1,':')) )
			colwidth = strtol( colon+1, &junk, 0 );

		else if ( MATCHn(p+1,"U",1) )
			caseflag = TRUE;

		else if ( MATCHn(p+1,"R",1) )
			reverseflag = TRUE;

		else
			helpflag = 1;

		if ( junk && *junk )		/* numeric field error */
			helpflag = TRUE;
	}

	/*----------------------------------
	 * Second pass: look for file names.
	 *----------------------------------
	 */

	for (i = 1; (i < argc) && !helpflag ; i++)
	{
		if (!argv[i] || !*argv[i])	/* no argument here */
			continue;

		else if (*argv[i] == '-' || *argv[i] == '/')	/* switch */
			continue;

		else if (!infile)
			infile = strupr(argv[i]);

		else if (!outfile)
			outfile = strupr(argv[i]);

		else
			helpflag = 1;
	}

	/*-----------------------
	 * Help requested? Error?
	 *-----------------------
	 */

	if (helpflag)
	{
		fprintf( stderr, usage, program );
		return( -1 );
	}

	if (outfile && strcmp(outfile,"=") == 0)
		outfile = infile;

	return( 0 );
}

#endif	/* cmdparse() */

/*---------------------------------------------------------------------
 * We request relatively large chunks of memory, and hand out pieces as
 * necessary.  We let Arp keep track, so we need not bother to free the
 * memory when we are done.
 *---------------------------------------------------------------------
 */

#define	ALLOCMAX 0xFF00		/* largest size we can handle */
#define	ALLOCMIN 1024		/* minimum size to allocate */

PVOID	myalloc( ULONG size )
{
	static	PCHAR	pointer	= NULL;
	static	ULONG	offset	= 0;
	PVOID	p	= NULL;

	/*-------------------------------------------------------
	 * Round requested size up to a multiple of 4.
	 * This should be adequate for alignment of most objects.
	 *-------------------------------------------------------
	 */

	size = (size + 3) & 0xFFFFFFFCL;

	/*----------------------------------------------------------
	 * There is a limit to how much we can allocate at one time.
	 *----------------------------------------------------------
	 */

	if (size > ALLOCMAX)
		return( NULL );

	/*------------------------------------------------------
	 * For objects above a certain minimum size, we allocate
	 * a separate block.  This should help when we have a
	 * mixture of large and small objects.
	 *------------------------------------------------------
	 */

	if ( (size >= ALLOCMIN) && (p = ArpAlloc(size)) )
		return( p );

	/*-------------------------------------------------
	 * If there is no room for new object in previously
	 * allocated block, we allocate another block.
	 *-------------------------------------------------
	 */

	if ( !pointer || (size > ALLOCMAX-offset) )	/* prevent overflow */
	{
		pointer = ArpAlloc(ALLOCMAX);
	 	offset = 0;
	}

	/*-----------------------------------------------
	 * If there is a block hanging around, it should
	 * have room for this object.  Carve off a piece.
	 *-----------------------------------------------
	 */

	if (pointer)
	{
		p = (PVOID) (pointer + offset);
		offset += size;
		return( p );
	}
	else
		return( NULL );
}

/*---------------------------------------------------------------------------
 * Initialize a new node to be inserted in the tree.
 *---------------------------------------------------------------------------
 */

PNODE	newnode( PCHAR text, ULONG textlen, ULONG lineno )
{
	PCHAR	ptext;
	PNODE	pnew	 = NULL;
static	AVLNODE	avldummy = { NULL, NULL, 0 };

	if ( (ptext = myalloc(textlen+1)) && (pnew = myalloc(SZOF_MYNODE)) )
	{
		strcpy( ptext, text );
		pnew->avlnode	= avldummy;
		pnew->text	= ptext;
		pnew->textlen	= textlen;
		pnew->lineno	= lineno;
	}
	return( pnew );
}

/*---------------------------------------------------------------------------
 *
 *	int cmprtc( keyP, nodeP )
 *		void	*keyP;
 *		AVLNODE	*nodeP;
 *	
 *	CMPRTC compares a given key against a key associated
 *	with a node.
 *
 *	keyP	the address of a key (interpreted in
 *		whatever way is applicable)
 *	nodeP	the address of an AVLNODE structure
 *		to which the key should be compared.
 *
 *	It shall return
 *		-1 if keyP is less than the key associated with nodeP key;
 *		 0 if they match;
 *		+1 if keyP is greater than the key associated with nodeP.
 *
 *	IMPLEMENTATION NOTE:
 *	For this application, keyP points to a previously-allocated
 *	AVL node.
 *---------------------------------------------------------------------------
 */

int	cmprtc( void *keyP, AVLNODE *nodeP )
{
	PNODE	kp	= (PNODE) keyP;
	PNODE	np	= (PNODE) nodeP;
	PCHAR	ktext	= kp->text + colstart;
	PCHAR	ntext	= np->text + colstart;
	int	khastext = (kp->textlen > colstart);
	int	nhastext = (np->textlen > colstart);
	int	cmp;

	/*---------------------------------------------------------------*/
	/* If both lines are long enough, apply the comparison function. */
	/* If only one line is long enough, it should precede the other. */
	/* If neither line is long enough, call them equal (for now).	 */
	/*---------------------------------------------------------------*/

	if (khastext && nhastext)
		cmp = (*pfnCompare)( ktext, ntext, colwidth );
	else
	{
		/*--------------------------------------*/
		/* k n -> cmp				*/
		/* ----------				*/
		/* 0 0     0	equal			*/
		/* 1 0    -1	key has precedence	*/
		/* 0 1     1	node has precedence	*/
		/* 1 1    n/a	handled by if(), above	*/
		/*--------------------------------------*/

		cmp = nhastext - khastext;
	}

	/*-------------------------------------------------------*/
	/* If the lines are equal, then the line that came first */
	/*	in the original file should have precedence.	 */
	/* Otherwise, make sure we return 1 or -1.		 */
	/*-------------------------------------------------------*/

	if (cmp == 0)
	{
		/*------------------------------------------------------*/
		/* k < n  : (0 - 1) = -1	key has precedence	*/
		/* k > n  : (1 - 0) = 1		node has precedence	*/
		/* k == n : (0 - 0) = 0		error, should not match	*/
		/*------------------------------------------------------*/

		return (kp->lineno > np->lineno) - (kp->lineno < np->lineno);
	}
	else
	{
		/*------------------------------------------------------*/
		/* cmp == 0 : n/a		handled by if(), above	*/
		/* cmp < 0  : (0 - 1) = -1	key has precedence	*/
		/* cmp > 0  : (1 - 0) = 1	node has precedence	*/
		/*------------------------------------------------------*/

		return (cmp > 0) - (cmp < 0);
	}
}

/*---------------------------------------------------------------------------
 *	AVLNODE *mknode( treeP, keyP, dataP, enodeP )
 *		AVLTREE	*treeP;
 *		void	*keyP;
 *		void	*dataP;
 *		AVLNODE	*enodeP;
 *	
 *	MKNODE creates a node on behalf of tree insertion.
 *	
 *	treeP	the address of the tree description structure
 *	keyP	the address of any key associated with the node
 *	dataP	the address of any data associated with the node
 *	enodeP	the address of any node that already exists in
 *		the tree for keyP.
 *
 *	If enodeP is not NULL, then this routine is being called
 *	to replace the data in an existing node.  It can signal
 *	its unwillingness to do this by returning NULL as its
 *	return value, otherwise it must return the address of the
 *	existing node.  Otherwise (if enodeP is NULL), this
 *	routine should allocate (or otherwise create) a new node
 *	and fill it in.
 *	
 *	MKNODE shall return the address of the node constructed,
 *	or NULL if no node was made.
 *
 *	IMPLEMENTATION NOTE:
 *	For this application, keyP points to a previously-allocated
 *	AVL node.
 *---------------------------------------------------------------------------
 */

AVLNODE *mknode( AVLTREE *treeP, void *keyP, void *dataP, AVLNODE *enodeP )
{
	if (enodeP)
		return( (AVLNODE *)NULL );
	else
		return( (AVLNODE *)keyP );
}

/*---------------------------------------------------------------------------
 *	void rmnode( treeP, nodeP )
 *		AVLTREE	*treeP;
 *		AVLNODE	*nodeP;
 *	
 *	RMNODE is called to delete a node and its information.
 *	
 *	treeP is the address of the tree description structure;
 *	nodeP is the address of the node to delete.
 *	
 *	It is called when a node is removed from a tree; it may
 *	do what it likes and does not return any information.
 *
 *	IMPLEMENTATION NOTE:
 *	For this application, we cannot do anything.
 *---------------------------------------------------------------------------
 */

void	rmnode( AVLTREE *treeP, AVLNODE *nodeP )
{
}

/*---------------------------------------------------------------------------
 * Print the tree to stdout (which may have been redirected).
 *---------------------------------------------------------------------------
 */

void	printtree( PNODE p )
{
	if (!p)
		return;

	else if (reverseflag)
	{
		printtree( (PNODE)(p->avlnode.n_rightP) );
		puts( p->text );
		printtree( (PNODE)(p->avlnode.n_leftP) );
	}

	else
	{
		printtree( (PNODE)(p->avlnode.n_leftP) );
		puts( p->text );
		printtree( (PNODE)(p->avlnode.n_rightP) );
	}
}