/* (C) 1993 PdT. */

#define Prototype extern
#define Local static

#ifdef AMIGA
#include <workbench/startup.h>
#endif

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "splaytre.h"
#include "splaypro.h"

#define MAXARGS 3
#define MAXNODES 42
#define MAXTREES 8
#define MAXKEY 99
#define INDENT 3

#if 0
Prototype void ninit( void );
Prototype void nfree( Node *freethis );
Prototype void help( void );
Prototype Node *nalloc( void );
#endif

typedef struct node {
  Snode foo;
  int key;  
} Node;

#define NNULL ((Node *) NULL)

const char *blankstr = "                                                 ";

void
st_print(FILE *whence, Node *root, int indent)
{
  if (root != NULL) {
    st_print(whence, (Node *) st_Left(&(root->foo)), indent+INDENT);
    fprintf(whence, "%.*s%*i\n", indent, blankstr, INDENT, root->key);
    st_print(whence, (Node *) st_Right(&(root->foo)), indent+INDENT);
  }
}

int compcnts[256];

int comps;

int
cmp(const void *a, const Snode *b)
{
  int x = (int)a;
  int y = ((Node *)b)->key;
  comps++;
  return x - y;
}

void *
keyof( const Snode *a )
{
  return (void *)(((Node *)a)->key);
}

/************************************************************************/

Node things[MAXNODES];
Node *firstfree = NULL;
int nodesfree = 0;

void
ninit( void )
/* set up initial freelist chain. */
{
  int i;

  st_Left(things+MAXNODES-1) = NULL;
  st_Right(things+MAXNODES-1) = NULL;
  things[MAXNODES-1].key = -1;

  for (i = MAXNODES-2; i >= 0; i--) {
    st_Left(things+i) = things + i + 1;
    st_Right(things+i) = NULL;
    things[i].key = -1;
  }
  firstfree = things;
  nodesfree = MAXNODES;
}

Node *
nalloc( void )
{
  Node *temp = NULL;

  if ( NULL != firstfree ) {
    nodesfree--;
    temp = firstfree;
    firstfree = st_Left(firstfree);
  }
  return temp;
}

void
nfree(Node *freethis)
{
  if (NULL != freethis) {
    nodesfree++;
    st_Left(freethis) = firstfree;
    st_Right(freethis) = NULL;
    freethis->key = -1;
    firstfree = freethis;
  }
}

/************************************************************************/

typedef struct cmd {
  char *template;
  char *help;
} Cmd;

#define NCMDS 21

const Cmd cmds[] = {
  { "",		"h\t\t: This help screen." },
  { "t",	"Z tree\t\t: return all nodes in tree to free pool." },
  { "",		"?\t\t: Display cumulative comparisons per command." },
  { "tt",	"j tree tree\t: join (pre-split) trees as first." },
  { "tt",	"m tree tree\t: merge any two trees as first." },
  { "ktt",	"s key tree tree\t: put items more than key into second tree." },
  { "ktt",	"l key tree tree\t: split with equal keys in first tree." },
  { "ktt",	"r key tree tree\t: split with equal keys in second tree." },
  { "t",	"v tree\t\t: view tree." },
  { "",		"S\t\t: remove smallest item from default tree." },
  { "",		"G\t\t: remove greatest item from default tree." }, 
  { "",		">\t\t: access next node in default tree." },
  { "",		"<\t\t: access previous node in default tree." },
  { "",		"F\t\t: access first node in default tree." },
  { "",		"L\t\t: access last node in default tree." },
  { "t",	": tree\t\t: set default tree." },
  { "",		";\t\t: view default tree."},
  { "k",	"f key\t\t: find key in default tree." },
  { "k",	"i key\t\t: insert key into default tree." },
  { "k",	"d key\t\t: detach key from default tree." },
  { "k",	"a key\t\t: add key to default tree if not already there." },
  { "",		" \t\t: Oops! miscounted." }
};

void
help( void )
{
  int i;

  puts("Commands available:");
  for ( i = 0; i < NCMDS; i++ ) {
    puts(cmds[i].help);
  }
#ifdef AMIGA
  printf("Hold down the control key and hit \\ to end the program.\n");
#elif defined(UNIX)
  printf("Hold down the control key and hit D to end the program.\n");
#endif
}

/************************************************************************/

void
zap( Node **root )
{
  Node *foo;

  while (NNULL != (foo = st_smallest((Snode **) root))) {
    nfree(foo);
  }
}

void
stats( void )
{
  int i;

  printf("%i nodes free:", nodesfree);
  for (i = 32; i < 256; i ++) {
    if (compcnts[i] != 0) {
      printf("\t%c : %i", i, compcnts[i]);
    }
  }
  printf("\n");
}

#define ROOT(x) ((Snode **)(forest+(x)))

int
main(int argc, char *argv[])
{
  Node *forest[MAXTREES];			/* forest. 		*/
  int deftree = 0;				/* default tree. 	*/

  int i;					/* misc. counter. 	*/
  int j;					/* misc. counter. 	*/

  char cmd[20];
  int arg[MAXARGS];

  ninit();					/* init free list. */
  for ( i = MAXTREES-1; i >= 0; i -- ) {	/* init forest.	*/
    forest[i] = NNULL;
  }
  for (i = 255; i >= 0; i-- ) {			/* init comp. counts */
    compcnts[i] = 0;
  }

  printf("Welcome to the splay tree testbed. Type h for a help screen.\n");

 /* fetch command character. */
  while (!feof(stdin) && (1 == scanf("%1s", cmd))) {	/* input loop. */
    int ok;
    char c;
    Node *foo;
    char *upto;

    c = *cmd;
 /* scan command table looking for match */
    for ( i = NCMDS-1; (i >= 0) && (c != *(cmds[i].help)); i-- )
      ;		/* NULL BODY */

    if (i < 0) {
      printf("I don't know how to %c. Type h for help.\n", c );
      continue;
    }

    for ( upto = cmds[i].template, ok = 1, j = 0; upto[j] != '\0'; j++ ) {
      if (1 != scanf("%i", arg+j) ) { ok = 0; break; }
      if ((upto[j] == 'k') && ((arg[j] < 0) || (MAXKEY < arg[j]))) {
        ok = 0;
	printf("Key %i must be within range %i to %i\n", arg[j], 0, MAXKEY);
      } else if ((upto[j] =='t') && ((arg[j] < 0) || (MAXTREES <= arg[j]))) {
        ok = 0;
        printf("Tree %i must be within range %i to %i\n", arg[j], 0, MAXTREES-1);
      }
    }

    if (!ok) continue;

    comps = 0;
    c = *cmd;
    switch (c) {
    case '?' : stats(); break;
    case 'h' : help(); break;
    case ':' : deftree = arg[0]; break;
    case ';' : st_print( stdout, forest[deftree], 0 ); break;
    case 'v' : st_print( stdout, forest[arg[0]], 0 ); break;
    case 'S' : nfree((Node *) st_smallest(ROOT(deftree))); break;
    case 'G' : nfree((Node *) st_greatest(ROOT(deftree))); break;
    case 'F' : st_first( ROOT(deftree) ); break;
    case 'L' : st_last( ROOT(deftree) ); break;
    case '<' : st_prev( ROOT(deftree) ); break;
    case '>' : st_next( ROOT(deftree) ); break;
    case 'f' :
      if (NNULL != (foo = st_lookup( (void *) arg[0], ROOT(deftree), cmp )))
        printf("Key %i found.\n", foo->key );
      else
        printf("Key %i not found.\n", arg[0] );
      break;
    case 'i' :
      if (NNULL == (foo = nalloc())) {
        puts("Sorry, out of nodes..");
      } else {
        foo->key = arg[0];
        st_insert( (void *) arg[0], ROOT(deftree), &(foo->foo), cmp );
      }
      break;
    case 'd' :
      if (NNULL != (foo = st_detach( (void *) arg[0], ROOT(deftree), cmp ))) {
        printf("Detached %i\n", foo->key );
        nfree(foo);
      }
      break;
    case 'a' :
      Snode bar;

      st_Left(&bar) = st_Right(&bar) = NULL;
      if (&bar == st_addiff( (void *) arg[0], ROOT(deftree), &bar, cmp )) {
        if (NULL != (foo = nalloc())) {
          foo->foo = bar;
          foo->key = arg[0];
          forest[deftree] = foo;
          printf("%i added.\n", arg[0]);
        } else {
          puts("Out of nodes...");
          st_join( st_AsRoot(st_Left(&bar)), st_AsRoot(st_Right(&bar)) );
          forest[deftree] = st_Left(&bar);
        }
      }
      break;
    case 'j' :
    case 'm' :
      if (arg[0] != arg[1]) {
        if ('j' == c) {
          st_join( ROOT(arg[0]), ROOT(arg[1]) );
        } else {
          st_merge( ROOT(arg[0]), ROOT(arg[1]), keyof, cmp );
        }
      } else {
        printf("Can't join or merge tree %i to itself!\n", arg[0]);
      }
      break;
    case 'l' :
    case 'r' :
    case 's' :
      if (arg[1] != arg[2]) {
        zap( ROOT(arg[2]) );
        if ('l' == c)
          st_lsplit( (void *) arg[0], ROOT(arg[1]), ROOT(arg[2]), cmp );
        else if ('r' == c)
          st_rsplit( (void *) arg[0], ROOT(arg[1]), ROOT(arg[2]), cmp );
        else
          st_split( (void *) arg[0], ROOT(arg[1]), ROOT(arg[2]), cmp );
      } else {
        printf("Can't split tree %i to itself and itself!\n", arg[1]);
      }
      break;
    case 'Z' : zap( ROOT(arg[0]) ); break;
    };	/* end switch */
    compcnts[*cmd] += comps;
  }	/* input parsing loop. */
  return 0;
}	/* main */

#ifdef AMIGA

int
wbmain( void *arg )
{
  freopen( "CON:0/0/640/200/Splaytst output window", "r+", stdout);
  *stdin = *stdout;
  main( 0, NULL );
  return 0;
}

#endif