/* 
 * oblikovati memorijsko rezidentno sortirano dvostruko binarno stablo s
 * podacima osobi. kljucevi su jmbg i prezime. 
 * 	(c) kreator, Wed Jan 27 19:40:14 CET 1999
 *
 * The tao that can be tar(1)ed is not the entire Tao. The path that can be
 * specified is not the Full Path. We declare the names of all variables and
 * functions. Yet the Tao has no type specifier. Dynamically binding, you
 * realize the magic. Statically binding, you see only the hierarchy. Yet
 * magic and hierarchy arise from the same source, and this source has a null
 * pointer. Reference the NULL within NULL, it is the gateway to all wizardry.
 */

/* standardni includeovi */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

/* defineovi nekih konstanti */
#define FIRST_NAME_SIZE 10
#define LAST_NAME_SIZE 20
#define INPUT_FILE_NAME "input.txt"
#define BUFLEN_SIZE 512
#define ID_SIZE 13
#define DEBUG

/* definiranje potrebnih struktura */
typedef struct node
{
	/* podaci */
	char first_name[FIRST_NAME_SIZE+1], last_name[LAST_NAME_SIZE+1];
	double id;
	/* ptr-ovi na slijedece strukture */
	struct node *left_name, *right_name, *left_id, *right_id;
} node;

/* do_on_error() */
void fatal(char *mesg)
{
	puts(mesg);
	exit(EXIT_FAILURE);
}

/* obrada 1 reda ulaznih podataka iz datoteke. ulaz je ptr na datoteku te ptr
 * tipa struct node; za datoteku ocekuje da bude formata:
 * prezime:ime:jmbg
 * prezime2:ime2:jmbg2
 * dozvoljeno je i komentiranje linije, sa `#' kao prvi znak.
 * ako linija nije zadovoljavajuceg formata cita slijedecu.
 * vraca 0 ako je kraj file-a ili read error, inace 1 */
char *data_read(FILE *fd, node *data)
{
	char linebuf[BUFLEN_SIZE+1], *retval;

	/* do ovoga ne bi ni trebalo doci */
	if (data==NULL) fatal("noninitialized *data within subroutine.");
	/* nulliranje podataka u data mi je korisno, jer time osiguravam
	 * ASCIIZ, te svi pointeri pokazuju na NULL (moguce je koristiti
	 * `obsolete' bzero() */
	memset(data, 0, sizeof(node));
	/* nazalost, ne smijem koristiti automate.. */
	while ((retval=fgets(linebuf, sizeof(linebuf), fd))!=NULL)
	{
		char *token, *running=linebuf;

		/* komentar */
		if (*linebuf=='#') continue;
		/* nadji lokacije list separatora `:'; mogao bi se koristiti i
		 * strtok da nije bugovit i `obsolete' ;-) 
		 * vazno je primijetiti da strsep vraca ASCIIZ */
		if ((token=strsep(&running, ":"))==NULL) continue;
		memcpy(data->last_name, token, LAST_NAME_SIZE+1);
		if ((token=strsep(&running, ":"))==NULL) continue;
		memcpy(data->first_name, token, FIRST_NAME_SIZE+1);
		if ((running==NULL) || (strlen(running)<(ID_SIZE-1)))
			continue;
		running[ID_SIZE]=0;
		if (!(data->id=strtod(running, NULL))) continue;
		break;
	}
	return retval;
}

/* rekurzivno stvaranje binarnog stabla po prezimenu */
/* glava je root, a data pokazuje na podatke */
node *tree_create_name(node *root, node *data)
{
	int direction;
	if (root==NULL)
		root=(node *)malloc(sizeof(node)),
		/* ovo mogu napraviti zbog memseta() u data_read() */
		memcpy(root, data, sizeof(node));
	else if ((direction=strcmp(data->last_name, root->last_name))<0)
		root->left_name=tree_create_name(root->left_name, data);
	else if (direction>0) 
		root->right_name=tree_create_name(root->right_name, data);
	return root;
}
/* rekurzivno stvaranje binarnog stabla po jmbg-u */
/* glava je root, a data pokazuje na trenutnu node strukturu koju obilazimo */
node *tree_create_id(node *root, node *data)
{
	if (root==NULL)	root=data;
	else 
		if (root->id>data->id) 
			root->left_id=tree_create_id(root->left_id, data);
		else if (root->id<data->id) 
			root->right_id=tree_create_id(root->right_id, data);
	return root;
}

/* funkcija koja ce obici stablo (sortirano) i pozvati kreiranje stabla kad je
 * potrebno .. vidi 2 lijepe rekurzije O:-) */
void circle(node *root, node *tmp)
{
	if (tmp!=NULL) 
		circle(root, tmp->left_name),
		tree_create_id(root, tmp),
		circle(root, tmp->right_name);
}

void display_name(node const *root)
{
	if (root!=NULL)
		display_name(root->left_name),
		printf("%-15s %-10s %.0f\n", root->last_name, 
				root->first_name, root->id),
		display_name(root->right_name);
}

void display_id(node const *root)
{
	if (root!=NULL)
		display_id(root->left_id),
		printf("%-15s %-10s %.0f\n", root->last_name, 
				root->first_name, root->id),
		display_id(root->right_id);
}

void free_all(node *root)
{
	if (root!=NULL)
		free_all(root->left_id),
		free_all(root->right_id),
		free(root);
}

/* funkcija u kojoj ce se sve odvijati */
void pooling(FILE *fd)
{
	node data, *root=NULL;

	/* citanje do kraja datoteke i stvaranje stabla za prezime */
	while(data_read(fd, &data)!=NULL) 
		root=tree_create_name(root, &data);
	/* paranoia_mode=1 ;) */
	if (root==NULL) fatal("null ptr *root encountered.");
	/* pozovi stvaranje stabla za jmbg */
	circle(root, root);
#ifdef DEBUG
	/* prikazi na ekranu dobivene rezultate */
	puts("\ntree sorted by id");
	display_id(root);
	puts("\ntree sorted by name");
	display_name(root);
#endif
	/* dobar shell bi se sam trebao pobrinuti da se free-a alocirana
	 * memorija kad program izadje.. */
	free_all(root);
}

/* glavni program */
int main(void)
{
	FILE *fd;

	if ((fd=fopen(INPUT_FILE_NAME, "r"))==NULL)
		fatal("error opening input file.");
	/* optimiziraj file buffering na linijski, iako bi bilo ljepse
	 * koristiti mmap() */
	setvbuf(fd, NULL, _IOLBF, 0);
	pooling(fd);
	fclose(fd);
	/* vrati 0x0 u eax registru, da se environment osjeca ugodno: DOS
	 * programi ionako pri ulazu u program imaju eax na 0x0, pa tako i ako
	 * je void imaju 0x0 pri izlasku zbog: pusha; <blabla>; popa; */
	return(EXIT_SUCCESS);
}