/* Possibile soluzione al compito del 26 luglio 1999 per coloro che dovevano sostenere 
 * l'esame di FONDAMENTI DI INFORMATICA 2                                      */

#include<stdio.h>
#include<stdlib.h> /* molti di voi si dimenticano di includere stdlib
                    * che pero' e' necessaria per le funzioni di 
                    * allocazione dinamica della memoria !! */

/* definizione struttura dati contenente l'albero di ricerca */
struct mytree{
	char *nome;
	long int matricola;
	struct mytree *maggiori;
	struct mytree *minori;
};

/* prototipi delle funzioni */
void *Malloc(size_t); 
void *Realloc(void *, size_t);
FILE *Fopen(const char *, const char *);
char *leggi_parola(FILE *);
void inserisci_in_albero(struct mytree*, char *, long int);
struct mytree *ricerca_in_albero_dove_inserire(struct mytree*, long int);
struct mytree *ricerca_in_albero(struct mytree*, long int);


int main(int argc, char **argv){

char *tmp_string;
char *tmp_matricola;
long int matricola;
FILE *dati_studenti;
struct mytree *albero_dati=NULL;
struct mytree *tmp_nodo;

dati_studenti=Fopen("stud.dat","r");

while(!feof(dati_studenti)){
  /* leggo dal file una riga */
  tmp_string=leggi_parola(dati_studenti);
  if(!tmp_string) break;
  tmp_matricola=leggi_parola(dati_studenti);
  matricola=atol(tmp_matricola);
  /* inserisco nell'albero di ricerca (prima pero' controllo che esista
   * e se non esiste ne alloco la radice */
  if(albero_dati==NULL){
	  albero_dati=Malloc(sizeof(struct mytree));
	  albero_dati->matricola=matricola;
	  albero_dati->nome=tmp_string;
	  albero_dati->maggiori=NULL;
	  albero_dati->minori=NULL;
  }
  else
	  inserisci_in_albero(albero_dati, tmp_string, matricola);
 }

/* itero indefinitamente chiedendo la matricola e stampando i risultati */
while(1){
	printf("Inserisci la matricola da ricercare: ");
	scanf("%ld", &matricola);
        tmp_nodo=ricerca_in_albero(albero_dati, matricola);
	if(tmp_nodo)
		printf("La matricola %ld corrisponde a: %s \n",matricola, tmp_nodo->nome);
	else
		printf("Matricola %ld non trovata\n",matricola);
}
}

/*************************************************************************/
/* Legge una stringa allocandola dinamicamente finche'
 * non incontra un \n oppure un ; */
char *leggi_parola(FILE *mio_file)
{
 char c=' ';
 char *parola=NULL;
 int lenparola=1;

 c=fgetc(mio_file);

 if(feof(mio_file))return NULL;
 
 parola=Malloc(sizeof(char));
 *parola=c;

 while((!feof(mio_file))&&(c!=';')&&(c!='\n'))
  {
   c=fgetc(mio_file);
   parola=Realloc(parola, sizeof(char)*(lenparola+1));
   parola[lenparola]=c;
   lenparola++;
  }

 /* aggiungo il terminatore per le stringhe */
  if(feof(mio_file))
   {
    parola=Realloc(parola, sizeof(char)*(lenparola+1));
    parola[lenparola]='\0';
   }
  else
   parola[lenparola-1]='\0';
  
 return parola;
}

/*************************************************************************/
/* inserisce i dati nell'albero di ricerca */
void inserisci_in_albero(struct mytree* albero, char * dato_nome, long int key){
	struct mytree *punto_di_inserzione;
	struct mytree *nuovo_nodo;
	
	/* prima di tutto alloco e inizializzo il nuovo nodo */
	nuovo_nodo=Malloc(sizeof(struct mytree));
	nuovo_nodo->matricola=key;
	nuovo_nodo->nome=dato_nome;
	nuovo_nodo->maggiori=NULL;
	nuovo_nodo->minori=NULL;

	/* cerco il punto di inserzione */
	punto_di_inserzione=ricerca_in_albero_dove_inserire(albero, key);
	/* lo inserisco come figlio destro o figlio sinistro a
	 * seconda del valore della chiave/matricola */
	if(punto_di_inserzione->matricola>nuovo_nodo->matricola)
		punto_di_inserzione->minori=nuovo_nodo;
	else
		punto_di_inserzione->maggiori=nuovo_nodo;
}

/*************************************************************************/
/* questa funzione ricerca quale e' il punto di inserzione per un nodo a seconda
 * del valore della chiave/matricola, ritorna esattamente il nodo sotto cui
 * aggiungere il nuovo nodo */ 
struct mytree *ricerca_in_albero_dove_inserire(struct mytree *albero, long int key){
	if(albero->matricola>key){
		if(albero->minori) 
			return ricerca_in_albero_dove_inserire(albero->minori,key);
		else
			return albero;
	}
	else{
		if(albero->maggiori) 
			return ricerca_in_albero_dove_inserire(albero->maggiori,key);
		else
			return albero;
	}
/* non dovrebbe MAI arrivare in questo punto sempre che il file
 * dati non contenga matricole duplicate */
fprintf(stderr, "ERRORE: matricola duplicata !!!\n");
exit(1);
}

/*************************************************************************/
/* ritorna il nodo corrispondente alla chiave richiesta oppure NULL se
 * non lo trova */
struct mytree *ricerca_in_albero(struct mytree *albero, long int key){
	if(!albero)return NULL;
	if(albero->matricola==key)return albero;
	if(albero->matricola>key)
		return ricerca_in_albero(albero->minori,key);
	else
		return ricerca_in_albero(albero->maggiori,key);
	return NULL;
}

/*************************************************************************/
/* da qui in poi sono semplici funzioni di utilita' gia' viste a lezione */
void *Malloc(size_t size)
{
 void *genericp;
 if((genericp=malloc(size))==NULL)
  {
   perror("Malloc");
   exit(1);
  }
  return genericp;
}

/*************************************************************************/

void *Realloc(void *ptr, size_t size)
{
 void *genericp;
 if((genericp=realloc(ptr, size))==NULL)
  {
   perror("Realloc");
   exit(1);
  }
  return genericp;
}

/*************************************************************************/

FILE *Fopen(const char *nome, const char *modo)
{
FILE *tmp;

 if((tmp=fopen(nome, modo))==NULL)
  {
   fprintf(stderr, "Non riesco ad aprire il file %s in maniera %s\n",nome, modo);
   perror("Fopen");
   exit(1);
  }
return tmp;
}