/********************************/
/*	AVL - Tree -Program	*/
/*	    avl_tree.c		*/
/*		by		*/
/*	tw03d024 P.Klenkhart    */
/*	Vers. 1.0 / 18.5.05	*/
/********************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_DATA 64
#define YES 1
#define NO 0

typedef struct knod
{
	int value;
	int depthLeft;
	int depthRight;
	struct knod *left;
	struct knod *right;
	}knod_t;

void insert_knod(knod_t **temp_root, knod_t *temp);
int search_depth(knod_t *tree);
int lookup_depth(knod_t *tree);

int avl_true = YES;

int main(int argc, char *argv[])
{
	FILE * fp;
	char buffer[MAX_DATA];
	knod_t *temp;
	knod_t *root = NULL;
	
	if(argc != 2)
	{
		fprintf(stdout, "Usage: %s filename\n", argv[0]);
		return EXIT_FAILURE;
		}

	if( (fp=fopen(argv[1], "r")) == NULL)
	{
		fprintf(stdout, "%s: Error opening File!\n", argv[0]);
		return EXIT_FAILURE;
		}
	
	if( (temp =(struct knod*) calloc(1, sizeof(struct knod))) == NULL);
	{
		fprintf(stdout, "%s: Error with malloc!\n", argv[0]);
		}
	
	while( fgets(buffer, MAX_DATA-1, fp) != NULL )
	{
		if( root == NULL )
		{
			if( ( temp = (struct knod *)realloc(temp, sizeof(struct knod) ) ) == NULL);
			{
				fprintf(stdout, "%s: Error with realloc1!\n",argv[0]);
				return EXIT_FAILURE;
				}

			sscanf(buffer, "%d", &temp->value);
			temp->left = NULL;
			temp->right = NULL;
			root = temp;

		}
		else
		{
			if( (temp = (struct knod *)realloc(temp, sizeof(struct knod))) == NULL);
			{
				fprintf(stdout, "%s: Error with realloc2!\n", argv[0]);
				return EXIT_FAILURE;
				}
			
			sscanf(buffer, "%d", &temp->value);			
			
			insert_knod(&root, temp);
			}
		}

	fprintf(stdout, "All Values filled into Tree!\n");
	avl_true = search_depth(root);
	
	fprintf(stdout, "\nAVL:");
	
	if(avl_true)
	{
		fprintf(stdout, "yes\n");
		}
	else
	{
		fprintf(stdout, "no\n");
		}
	
	free (temp);
	return EXIT_SUCCESS;

}

void insert_knod(knod_t **temp_root, knod_t *temp)
{
	if(!*temp_root)
	{
		*temp_root = temp;
		}

	if( (*temp_root)->value > temp->value) 
	{
		insert_knod(&(*temp_root)->left, temp);
		}
	
	else if( (*temp_root)->value < temp->value)
	{
		insert_knod(&(*temp_root)->right, temp);
		}

}

int search_depth(knod_t *tree)
{
	int bal;

	if(tree->left)
	{
		search_depth(tree->left);
		tree->depthLeft = lookup_depth(tree->left) + 1;
	}
	else
	{
		tree->depthLeft = 0;
		}
	
	if(tree->right)
	{
		search_depth(tree->right);
		tree->depthRight = lookup_depth(tree->right) +1;
	}
	else
	{
		tree->depthRight = 0;
		bal = (int)fabs(tree->depthRight - tree->depthRight);
		
		fprintf(stdout, "\nBAL(%d): %d", tree->value, bal);
		
		if(bal > 1)
		{
			fprintf(stdout, " (AVL Violation!)\n");
			avl_true = NO;
			}
		}
	
	return avl_true;
}

int lookup_depth(knod_t *tree)
{
	if(tree->depthLeft > tree->depthRight)
	{
		return tree->depthLeft;
	}
	else
	{
		return tree->depthRight;
		}

}