/*
               Commandment #12592
Oh ye who go about saying unto each other:  "Hello sailor":
Dost thou know the magnitude of thy sin before the gods?
Yea, verily, thou shalt be ground between two stones.
Shall the angry gods cast thy body into the whirlpool?
Surely, thy eye shall be put out with a sharp stick!
Even unto the ends of the earth shalt thou wander and
unto the land of the dead shalt thou be sent at last.
Surely thou shalt repent of thy cunning.
                     
4. Vjezba
Ancvfngv cebtenz xbwv pr cbqngxr vm fyvwrqar sbezngvmvenar qngbgrxr
cebvmibywabt fnqemnwn cercvfngv h herqwrab ovaneab fgnoyb fgehxghen fzwršgrab
h qverxgabw arsbezngvenabw qngbgrpv. Xywhp mncvfn bqerqvgv fnzbfgnyab.
Ancvfngv v vfcebongv fywrqrpr shaxpvwr:
n) shaxpvwh mn genmrawr ryrzragn fgnoyn fn mnqnavz xywhprz
o) shaxpvwh mn vmenpha enmvar piben fn mnqnavz xywhprz
p) shaxpvwh mn vmenpha qhovar fgnoyn
Qbqngnx:
Ancvfngv shaxpvwh mn oevfnawr ryrzragn fgnoyn fn mnqnavz xywhprz.
*/

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

//                   (c) kreator '97
//        greetz goes 2 all nice lookin' blondes

//declare structure for one node
struct node_type
{
	char element[20];
	struct node_type *left, *right;
};

//define type for node
typedef struct node_type node;

//exit function to release spc allocated by nodes [postorder]
void exit_func(node *root)
{
	if (root)
	{
		exit_func(root->left);
		exit_func(root->right);
		free(root);
	}
}

//create binary tree
node *create(node *root, char *element)
{
	int direction;
	if (!root)
	{
		root=(node *)malloc(sizeof(node));
		strcpy(root->element, element);
		root->left=root->right=0;
	} else if ((direction=strcmp(element, root->element))<0)
		root->left=create(root->left, element);
			else if (direction>0) root->right=create(root->right, element);
	return root;
}

//display binary tree
void display(node const *root)
{
	if (root)
	{
		display(root->left);
		printf("%s ", root->element);
		display(root->right);
	}
}

//memory dump nodes into a binary file
void outfile(node const *root, FILE *output)
{
	if (root)
	{
		outfile(root->left, output);
		fwrite(root->element, sizeof(root->element), 1, output);
		outfile(root->right, output);
	}
}

//display a binary tree like a tree.. root is at 0 level
void tree(node const *root, int level)
{
	int i;
	if (root)
	{
		tree(root->right, level+1);
		for(i=0; i<level; ++i) printf("    ");
		printf("%s\n", root->element);
		tree(root->left, level+1);
	}
}

//search node, ret addr
void search(node const *root, char *string)
{
	if (root)
	{
		search(root->left, string);
		if (!strcmp(root->element, string))
			printf("%s found at %p address\n", root->element, root->element);
		search(root->right, string);
	}
}

//search for node, based on key
void calc_depth_key(node const *root, int tmp_lvl, char const *string, int *level)
{
	if (root)
	{
		calc_depth_key(root->left, tmp_lvl+1, string, level);
		if (!strcmp(root->element, string)) *level=tmp_lvl;
		calc_depth_key(root->right, tmp_lvl+1, string, level);
	}
}

//calculate max depth in binary tree
void calc_depth(node const *root, int level, int *max_level)
{
	if (root)
	{
		if (level>*max_level) *max_level=level;
		calc_depth(root->right, level+1, max_level);
		calc_depth(root->left, level+1, max_level);
	}
}

//function for seek_and_destroy
void outfile2(node const *root, FILE *output, char const *string)
{
	if (root)
	{
		if (strcmp(root->element, string))
			fprintf(output, "%s\n", root->element);
		outfile2(root->right, output, string);
		outfile2(root->left, output, string);
	}
}

//calling mr dj..... yeeeeah... pamela anderson rulez..­!
//create new binary tree using tmp file
node *seek_and_destroy(node *root, char const *string)
{
	FILE *input;
	char tmp[20];

	input=fopen("input2", "wt");
	outfile2(root, input, string);
	fclose(input);
	input=fopen("input2", "rt");
	exit_func(root);
	root=0;
	while (fscanf(input, "%s", tmp)!=EOF)
		if (!(root=create(root, tmp))) break;
	fclose(input);
	return root;
}

//#define main MAIN ;)
void main(void)
{
	FILE *input, *output;
	node *root=0;
	char string[20];
	int level=EOF, max_level=0;

	//clear screen using asm opcode
	//asm mov ax,0x003;
	//asm int 0x010;

	//some init stuff
	if (!(input=fopen("input", "rt"))) exit(EXIT_FAILURE);
	output=fopen("output", "wb");

	//do loop until EOF (-1) or mem_alloc_err (0)
	while (fscanf(input, "%s", string)!=EOF)
		if (!(root=create(root, string))) break;

	printf("Sorted list: ");
	display(root);
	outfile(root, output);
	fcloseall();

	printf("\nEnter a string to search and delete: ");
	scanf("%s", string);

	search(root, string);
	calc_depth_key(root, 0, string, &level);
	if (level<0) printf("%s not found!\n", string);
		else
		{
			printf("%s found at level %d\n", string, level);
			printf("Starting cleaning tree daemon...\n");
			root=seek_and_destroy(root, string);
		}
	calc_depth(root, 0, &max_level);
	printf("Maximal depth is %d\nTree organisation is:\n\n", max_level);
	tree(root, 0);
	exit_func(root);
}