//-----------------------------------------------------------------------------
// Copyright © 2003 - Philip Howard - All rights reserved
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//-----------------------------------------------------------------------------
// package	libh/avl
// homepage	http://libh.slashusr.org/
//-----------------------------------------------------------------------------
// author	Philip Howard
// email	libh at ipal dot org
// homepage	http://phil.ipal.org/
//-----------------------------------------------------------------------------
// This file is best viewed using a fixed spaced font such as Courier
// and in a display at least 120 columns wide.
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// program	showtree
//
// purpose	Show the construction and balancing of a binary tree during
//		each step of words being added to or deleted from a tree.
//
// syntax	showtree [width [height ["sepchars"] ] ] < infile
//-----------------------------------------------------------------------------
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <libh/avl.h>

#define WORDSIZE	256


//-----------------------------------------------------------------------------
// Define a struct that implements a link for a character string key.
// Define a struct that implements a node to carry the key but no data.
// Define a function that compares the keys in two links given to it.
//-----------------------------------------------------------------------------
struct link_str {
    avl_link		link		;
    char *		key		;
};

struct node {
    struct link_str	word		;
    char		data	[16]	;
};

static int cmp_str( avl_link * arg_one, avl_link * arg_two, AVL * arg_tree )
{
    return strcmp(
	( (struct link_str *) arg_one )->key,
	( (struct link_str *) arg_two )->key
    );
}

//-----------------------------------------------------------------------------
// Define a function that returns a pointer to the string key for a given node.
// This is passed to avl_print_tree() so it displays actual keys in the tree.
//-----------------------------------------------------------------------------
const char * get_key ( void * node_p )
{
    return ((struct node *)node_p)->word.key;
}

//-----------------------------------------------------------------------------
// function	readword
//-----------------------------------------------------------------------------
static
int
readword (
    char *	arg_buffer
,
    size_t	arg_length
,
    char *	arg_seps
)
{
    char *	p	;
    char *	q	;
    int		c	;

    //-- Note where the end of the buffer is.
    q = ( p = arg_buffer ) + arg_length - 1;

    //-- Skip all leading separator characters.
    while ( (c = getc( stdin )) != EOF && arg_seps[ c ] ) {
    }

    //-- Get characters until end of word, store until full.
    while ( c != EOF && arg_seps[ c ] == 0 ) {
	if ( p < q ) * p ++ = c;
	c = getc( stdin );
    }
    * p = 0;

    //-- Return 0 if EOF, 1 if a word found.
    return ( c == EOF );
}

//-----------------------------------------------------------------------------
// function	main
//-----------------------------------------------------------------------------
int
main (
    int		argc
,
    char * *	argv
)
{
    AVL			by_word		;
    struct link_str	key_word	;
    struct node *	node_p		;
    char		word		[ WORDSIZE ];
    char		seps		[ 256 ];
    size_t		len		;
    int			width		;
    int			height		;


    //-------------------------------------------------------
    // Get the width and height of the screen from arguments.
    // Otherwise use a default of 79x23.
    //-------------------------------------------------------
    width = 79;
    height = 23;
    if ( argc > 1 && argv[1] ) width = strtol( argv[1], NULL, 0 );
    if ( width < 20 ) width = 20;
    if ( argc > 2 && argv[2] ) height = strtol( argv[2], NULL, 0 );
    if ( height < 8 ) height = 8;

    //------------------------------------------------------------------------
    // Initialize the separator table that is given to readword().  This table
    // tells it what characters separate each word.  Control characters are
    // always placed in the table.  If no explicit characters are given in the
    // third argument then all space and punctuation characters are added by
    // default.  Otherwise just the given characters are added.
    //------------------------------------------------------------------------
    {
	int i;

	//-- Initialize the table with just control characters.
	for ( i = 0; i < 256; ++ i ) seps[ i ] = iscntrl( i );

	if ( argc > 3 && argv[ 3 ] ) {
	    char * p;

	    //-- Add the characters from the given arguments.
	    p = argv[ 3 ];
	    while ( * p ) seps[ 255 & * p ++ ] = 1;

	} else {

	    //-- Add space and punctuation characters.
	    for ( i = 0; i < 256; ++ i ) {
		if ( ispunct( i ) || isspace( i ) ) seps[ i ] = 1;
	    }
	}
    }

    //-----------------------------------------------------------------------
    // Now proceed to actually build, juggle, and display a real binary tree.
    //-----------------------------------------------------------------------

    //-- Initialize the binary tree.
    avl_init( & by_word, struct node, word, cmp_str );

    //-- Initialize the struct used to find stuff in the tree.
    key_word.key = word;

    //-- Read input separated as words.
    while ( 0 == readword( word, WORDSIZE, seps ) ) {

	//-- Alternate the word in and out of the tree.
	node_p = avl_find_exact( & by_word, & key_word );
	if ( node_p ) {

	    //-- Word found: take it back out and free it.
	    avl_delete( & by_word, node_p );
	    free( node_p );

	} else {

	    //-- Word not found: create and insert a new one
	    len = sizeof (struct node) - 16 + strlen( word ) + 1;
	    node_p = malloc( len );
	    if ( ! node_p ) {
		fprintf(stderr,"Out of memory (needed %lu bytes).\n",(unsigned long)len);
		return 1;
	    }
	    strcpy( ( node_p->word.key = node_p->data ), word );
	    avl_insert( & by_word, node_p );
	}

	//-- Flash the tree structure on the screen.
	fputs("\033[0H",stdout);
	avl_print_tree(stdout,&by_word,NULL,"",1,get_key,width,"\033[0K",height);
	fputs("\033[0J",stdout);
	fflush(stdout);

    }

    return 0;
}