/*
(c) kreator, system admins inc.
Sun Jun  7 22:19:51 CEST 1998

"But now I see nothing. My whole being exists in a formless void.  My senses
are idle. My spirit, free to work without a plan, follows its own instinct."

13 program iz asp-a.. stvaranje slijedne datoteke i stabla na disku.. i
usporedjivanje brzine pristupa (pretrazivanja)
*/

#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
       
#define INPUT "input.txt"
#define OUTPUT_TREE "output_tree.bin"
#define OUTPUT_ROW "output_row.bin"

/* macro to get funcs as small as it gets.. yeah! */
#define COMMON_TREE_SAVE(node_direction)				\
{									\
	if (!elem_output.node_direction)				\
	{								\
		pos_cur=ftell(output)-(long)sizeof(node_t);		\
		fseek(output,0L,SEEK_END);				\
		pos_end=ftell(output);					\
		fwrite(&elem_input,sizeof(node_t),1,output);		\
		fseek(output,pos_cur,SEEK_SET);				\
		elem_output.node_direction=pos_end;			\
		fwrite(&elem_output,sizeof(node_t),1,output);		\
		break;							\
	} else fseek(output,elem_output.node_direction,SEEK_SET);	\
}

typedef struct
{
	char string[20+1];
	int key;
} data_t;

typedef struct
{
	data_t node;
	long left,right;
} node_t;

void fatal(char *msg)
{
	puts(msg);
	exit(EXIT_FAILURE);
}

void input_disk_tree(FILE *output,node_t elem_input)
{
	node_t elem_output;
	long pos_cur,pos_end;
	
	rewind(output);
	for(;;)
	{
		elem_input.left=elem_input.right=0L;
		if (!fread(&elem_output,sizeof(node_t),1,output)) 
		{
			/* empty tree */
			fwrite(&elem_input,sizeof(node_t),1,output);
			break;
		}
		if (elem_input.node.key>elem_output.node.key)
		{
			/* check || jump right */
			COMMON_TREE_SAVE(right);
		}
		else if (elem_input.node.key<elem_output.node.key)
		{
			/* check || jump left */
			COMMON_TREE_SAVE(left);
		}
		else break;
	}
}

#ifdef DEBUG
void display_tree(FILE *input, long pos)
{
	node_t tmp;
	fseek(input,pos,SEEK_SET);
	if (fread(&tmp,sizeof(node_t),1,input))
	{
		if (tmp.left) display_tree(input,tmp.left);
		printf("%d %s\n",tmp.node.key,tmp.node.string);
		if (tmp.right) display_tree(input,tmp.right);
	}
}
#endif

void input_disk_row(FILE *output,node_t data)
{
	/* notice that there is no same_data checking, as in tree */
	data.left=data.right=0L;
	fwrite(&data,sizeof(node_t),1,output);
}

void search_tree(FILE *input,int key)
{
	node_t tmp;
	
	rewind(input);
	for(;;)
	{
		if (!fread(&tmp,sizeof(node_t),1,input)) break;
		if ((key>tmp.node.key) && tmp.right) 
			fseek(input,tmp.right,SEEK_SET);
		else
		if (key==tmp.node.key) {puts(tmp.node.string); break;}
		else
		if (tmp.left) fseek(input,tmp.left,SEEK_SET);
	}
}

void search_row(FILE *input, int key)
{
	node_t tmp;
	while (fread(&tmp,sizeof(node_t),1,input))
		if (tmp.node.key==key) puts(tmp.node.string);
}

int main(void)
{
	node_t input_data;
	FILE *input,*output_tree,*output_row;
	clock_t time_tree,time_row;
	int key;
	struct tms buf;
	
	if (!(input=fopen(INPUT,"rt"))) fatal("I/O error!");
	if (!(output_tree=fopen(OUTPUT_TREE,"w+b"))) fatal("I/O error!");
	if (!(output_row=fopen(OUTPUT_ROW,"w+b"))) fatal("I/O error!");
	
	while(fscanf(input,"%d %s",&input_data.node.key,
		input_data.node.string)!=EOF)
	{
		input_disk_tree(output_tree,input_data);
		input_disk_row(output_row,input_data);
	}

#ifdef DEBUG	
	display_tree(output_tree,0L);
#endif

	rewind(output_tree);
	rewind(output_row);
	printf("key to search for: ");
	scanf("%d",&key);
	
	search_tree(output_tree,key);
	search_row(output_row,key);
	
	/* how about some zen timer? :) */

	fclose(input);
	fclose(output_tree);
	fclose(output_row);
	exit(EXIT_SUCCESS);
}