/* possibile soluzione all'esame del 9 giugno 2001 */
#include<stdio.h>
#include<stdlib.h>


/* richiesto esplicitamente albero binario di ricerca*/
struct nodo{
  float key; /* dato ma anche chiave 
	      * il testo non lo diceva MA si ipotizza
	      * che la somma di due valori sia univoca */
  struct nodo *maggiori, *minori; /* sottoalberi destro e sinistro */
};

/* prototipi funzioni */
void *Malloc(size_t); 
FILE *Fopen(const char *, const char *);
int leggi_riga(FILE *, float *, float *);
struct nodo *crea_nodo(float k);
struct nodo *inserisci_in_albero(struct nodo *,float);
void stampa_albero(struct nodo *);
void libera_albero(struct nodo *);

/* evito l'utilizzo di variabili globali */

int main(int argc, char **argv){
  FILE *myfile; /* handler per file */
  struct nodo *mytree=NULL; /* BST */
  float a,b,sum; /* float letti riga per riga e loro somma */
  int cod; /* codice ritorno */

  /* prima parte APRO, leggo e memorizzo il file */
  myfile=Fopen("float.txt","r");

  while(1){
    cod=leggi_riga(myfile,&a,&b); /* legge due float dal file se non ci
			           * riesce ritorna 0 */
    if(!cod)break;         /* esce dal while se non riesce a leggere */

    sum=a+b; /* calcola valore da inserire in albero */
    mytree=inserisci_in_albero(mytree,sum); /* inserisco */
  }

  /* chiudo il file */
  fclose(myfile);

  /* seconda parte stampo i risultati ORDINATI e
   * libero la struttura dati */
  stampa_albero(mytree);
  libera_albero(mytree);

  return EXIT_SUCCESS; /* codice di uscita senza errori */
}

/* legge una riga, se non ci riesce restituisce 0 */
int leggi_riga(FILE *f, float *a, float *b){
  int c;

  /* il testo non chiariva esattamente il formato del file, ma visto che lo
   * creiamo noi ipotizzo che i due float siano separati da un
   * singolo spazio */
  c=fscanf(f, "%f %f\n",a,b);
  if(c!=2)return 0;
  /* printf("%f %f\n",*a,*b); */
  return 1;
}

/* alloca un nodo per l'albero */
struct nodo *crea_nodo(float k){
  struct nodo *p;

  p=Malloc(sizeof(struct nodo));
  p->key=k;
  p->maggiori=p->minori=NULL;
  return p;
}

/* inserisce un valore nell'albero */
struct nodo *inserisci_in_albero(struct nodo *root, float k){
  if(!root){
    struct nodo *p;
    p=crea_nodo(k);
    return p;
  }

  if(root->key>k)
    root->minori=inserisci_in_albero(root->minori,k);
  else
    root->maggiori=inserisci_in_albero(root->maggiori,k);
  return root;
}

/* stampa ordinata: di fatto e' un attraversamento inorder */
void stampa_albero(struct nodo *p){
  if(!p)return; /* condizione uscita */
  stampa_albero(p->maggiori);
  printf("%f\n",p->key);
  stampa_albero(p->minori);
}

/* distruzione albero: libera la memoria, di fatto
 * attraversamento postorder */
void libera_albero(struct nodo *p){
  if(!p)return; /* condizione uscita */
  libera_albero(p->maggiori);
  libera_albero(p->minori);
  free(p);
}

/* solite procedure utilizzate durante il corso */
/*************************************************************************/

void *Malloc(size_t size)
{
 void *genericp;
 if((genericp=malloc(size))==NULL)
  {
   perror("Malloc");
   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;
}