#include "bst.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void	insert( BST_EL **t, BST_EL *e )
{
	BST_EL	*ptr;
	BST_EL	*prec;
	int	cmp;

	if( *t == NULL )
	{
		/* L'albero e` vuoto */
		ptr = (BST_EL *)malloc( sizeof( BST_EL ) );
		if( ptr == NULL )
		{
			printf( "Impossibile allocare la memoria\n" );
			exit( 1 );
		}

		ptr->word = (char *)strdup( e->word );
		ptr->freq = e->freq;
		ptr->R = NULL;
		ptr->L = NULL;

		*t = ptr;
	}
	else
	{
		ptr = *t;
		prec = NULL;
		while( ptr != NULL )
		{
			prec = ptr;
			cmp = strcmp( ptr->word, e->word );
			if( cmp == 0 )
				return;	/* Chiave gia` presente */
			if( cmp > 0 )
				ptr = ptr->L;
			else
				ptr = ptr->R;
		}

		ptr = (BST_EL *)malloc( sizeof( BST_EL ) );
		if( ptr == NULL )
		{
			printf( "Impossibile allocare la memoria\n" );
			exit( 1 );
		}

		ptr->word = (char *)strdup( e->word );
		ptr->freq = e->freq;
		ptr->R = NULL;
		ptr->L = NULL;

		if( strcmp( prec->word, e->word ) > 0 )
			prec->L = ptr;
		else
			prec->R = ptr;
	}
}

BST_EL *search( BST_EL *t, char *s )
{
	BST_EL	*ptr;
	int	cmp;

	ptr = t;
	while( ptr != NULL )
	{
		cmp = strcmp( ptr->word, s );
		if( cmp == 0 )
			return( ptr );	/* Ho trovato la chiave */
		if( cmp > 0 )
			ptr = ptr->L;
		else
			ptr = ptr->R;
	}

	return( NULL );	/* Chiave non trovata */
}

void	visit_in_order( BST_EL *t )
{
	if( t == NULL )
		return;
	else
	{
		visit_in_order( t->L );
		printf( "%10s: %5d\n", t->word, t->freq );
		visit_in_order( t->R );
	}
}

void	visit_pre_order( BST_EL *t )
{
	if( t == NULL )
		return;
	else
	{
		printf( "%10s: %5d\n", t->word, t->freq );
		visit_pre_order( t->L );
		visit_pre_order( t->R );
	}
}

void	visit_post_order( BST_EL *t )
{
	if( t == NULL )
		return;
	else
	{
		visit_post_order( t->L );
		visit_post_order( t->R );
		printf( "%10s: %5d\n", t->word, t->freq );
	}
}

void	dispose( BST_EL **t )
{
}