/* avltest.c -- test routine for Zinn AVL routines */

/* This file contains code to illustrate and test the use of the
   AVL routines in avl.c
*/

#include <stdio.h>
#include "avl.h"

/* Structure of node used by the test routine */

typedef
  struct atnode {
    AVLNODE	at_avl;			/* AVL info */
    long	at_data;		/* key && data */
  } ATNODE;

extern	long	atol();
extern	char	*calloc();
extern	double	drand48();

int	tkeycmp();
AVLNODE	*tmknode();
int	trmnode();

int	Comps = 0;
int	Nodes = 0;
AVLTREE	Treehdr;

main()
{
	int		c;
	int		i;
	int		done;
	int		sts;
	long		key;
	char		*strP;
	char		linebuf[100];

Treehdr.t_cmprtc = tkeycmp;
Treehdr.t_mknode = tmknode;
Treehdr.t_rmnode = trmnode;

for ( done = FALSE; !done ; )
    {
    printf("> ");
    fflush( stdout );
    getline( &linebuf[0] );
    if ( linebuf[0] == NUL )
	continue;
    for( strP = &linebuf[1]; ( c = *strP ) != NUL; ++ strP )
	if ( ( c != ' ' ) && ( c != '	' ) )
	    break;

    switch( linebuf[0] )
	{
	case '0':
	case '1':
	case '2':
	case '3':
	case '4':
	case '5':
	case '6':
	case '7':
	case '8':
	case '9':
	    strP = &linebuf[0];
	case 'a':			/* Add */
	    key = atol( strP );
	    sts = avlinsert( &Treehdr, &key, &key );
	    if ( sts == 0 )
		{
		printf( "ok.\n" );
		++Nodes;
		}
	    else if ( sts == -1 )
		{
		printf( "fatal error.\n" );
		done = TRUE;
		}
	    else
		printf( "Already in tree.\n" );
	    break;		

	case 'd':
	    key = atol( strP );
	    if ( ( sts = avldelete( &Treehdr, &key ) ) == 0 )
		{
		printf( "ok.\n" );
		--Nodes;
		}
	    else
		printf( "not found.\n" );
	    break;

	case 'p':
	    prttree( 0, Treehdr.t_rootP );
	case 's':
	    printf("Nodes: %d;  Comparisons: %d\n", Nodes, Comps );
	    break;
	    
	case 'r':
	    for( i = atoi( strP ); i > 0; --i )
		{
		key = ( drand48( ) * (double)10000.0 );
		sts = avlinsert( &Treehdr, &key, &key );
		if ( sts == -1 )
		    {
		    printf( "fatal error.\n" );
		    done = TRUE;
		    break;
		    }
		else if ( sts == 0 )
		   ++Nodes;
		}
	    break;

	case 'q':
	    done = TRUE;
	    break;

	case 'z':
	    for( i = atoi( strP ); i > 0; --i )
		key = (long)( drand48( ) * (double)10000.0 );
	    break;

	default:
	    printf(" ? a(dd), d(elete), p(rint), q(uit), r(andom), s(tats)\n" );
	    break;
	}
    }
}

prttree( depth, treeP )
	int		depth;
	ATNODE		*treeP;
{
	int		i;

if ( treeP != NULL )
    {
    prttree( depth+1, treeP->at_avl.n_leftP );
    for( i = 0; i < depth; ++i )
	printf( "  " );
    printf( "key =%5ld;  val=%5ld;  bal=%2d\n", treeP->at_data,
    					      treeP->at_data,
    					      treeP->at_avl.n_balance );
    prttree( depth+1, treeP->at_avl.n_rightP );
    }
}


getline( bufP )
	char		*bufP;
{
	int		c;

while( (c = getchar()) != '\n' )
    *bufP++ = c;
*bufP = NUL;
}


/* The key comparison routine; it is passed the address of a key value,
   and the address of the node to which it is being compared.  In our
   case the AVLNODE address is the same as the ATNODE address so we'll
   assume we're being passed an ATNODE ptr.  
*/
tkeycmp( val1, nodeP )
register long	*val1;
register ATNODE *nodeP;
{
	int		rval;

if ( *val1 < nodeP->at_data )
    rval = -1;
else if ( *val1 == nodeP->at_data )
    rval = 0;
else
    rval = 1;

++Comps;
return( rval );
}


/* Node maker.  Note it must return the address of the AVLNODE struct. */

AVLNODE *
tmknode( treeP, keyP, dataP, enodeP )
	AVLTREE		*treeP;
	long		*keyP;
	long		*dataP;
	AVLNODE		*enodeP;
{
	ATNODE		*nodeP;

/* Check for over-write of existing node */
if ( enodeP != NULL )
    return( (AVLNODE *)NULL );

/* New node -- build it */
nodeP = (ATNODE *)calloc( 1, sizeof(ATNODE) );
nodeP->at_data = *keyP;

return( &nodeP->at_avl );
}


int
trmnode( treeP, nodeP )
	AVLTREE		*treeP;
	AVLNODE		*nodeP;
{
free( nodeP );
}