/* IS-A: fatti del mondo */
/* Allocazione dinamica della base dati */
/* - Creazione di un albero.
   - Visita recursiva di un albero.  */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* definizioni */
#define LUNG_NOME 20+1
#define LUNG_COMMAND 3+1
#define NUM_ELEM 200

typedef enum {FALSE, TRUE} boolean;
typedef struct elemento_s
	{
	char nome[LUNG_NOME];
	struct elemento_s *punt_fratello;
	struct elemento_s *punt_figlio;
	} elemento;
elemento *punttesta, *punt_dato;
char comando[LUNG_COMMAND];
char nome1[LUNG_NOME], nome2[LUNG_NOME];
boolean finito;
/* prototipi */
void lettura(char comando[], char nome1[],
		      char nome2[], boolean *finito);
void leggi_con_terminatore(char nome[], char terminatore);
void inserimento(char nome1[], char nome2[]);
void cerca(char nome[], boolean *trovato);
boolean trovato_in_elemento(char nome[], elemento *puntatore);
boolean trovato_in_fratello(char nome[], elemento *puntatore);
boolean trovato_in_figlio(char nome[], elemento *puntatore);
void rispondi(char nome1[], char nome2[]);


main()
{
printf("Introdurre comandi nelle forme:\n");
printf("isa(nome1,nome2)\n");
printf("is?(nome1,nome2)\n");
punttesta = NULL;
finito = FALSE;
while (!finito)
    {
    lettura(comando, nome1, nome2, &finito);
    if (!finito)
	{
	if (strcmp(comando, "isa") == 0)
	   inserimento(nome1, nome2);
	else
	   rispondi(nome1, nome2);
	}
    }
} /* end main */

void lettura(char comando[], char nome1[],
		      char nome2[], boolean *finito)
				      /* definizione */
{
/* definizioni locali */
char carat;
int indice;

printf("Introduci un comando o <CTRL>+Z:\n");
indice = 0;
while ((( carat = getchar() ) != EOF) /* finche' non si arriva all'EOF */
	   && (indice < 3))          /* legge 4 caratteri del comando */
    {
    comando[indice] = carat;
    indice++;
    }
comando[3] = '\0';                         /* forza fine-stringa */

if (carat != EOF)
    {
    leggi_con_terminatore(nome1,',');
    leggi_con_terminatore(nome2,')');
    while (( carat = getchar() ) != '\n')
	;                                        /* legge fino a EOLN */
    }
else
    *finito = TRUE;
} /* end lettura */

void leggi_con_terminatore(char nome[], char terminatore)
{
/* definizioni locali */
int indice;
char carat;

indice = 0;
while ((( carat = getchar() ) != terminatore)
			   && (indice < LUNG_NOME))
			    /* finche' non si arriva al terminatore */
			    /* o e' finito il vettore */
    {
    nome[indice] = carat;
    indice++;
    }
nome[indice] = '\0';                         /* forza fine-stringa */
} /* end leggi_con_terminatore */


void inserimento(char nome1[], char nome2[])
{
/* definizioni locali */
elemento *puntcorr;
boolean trovato;

if (punttesta == NULL)
    {                           /* base dati vuota */
    punttesta = (elemento *) malloc( sizeof(elemento) );
				  /* alloca memoria primo elem. */
    strcpy((*punttesta).nome, nome2);
    (*punttesta).punt_fratello = NULL;    /* il primo non ha fratelli */
    puntcorr = (elemento *) malloc( sizeof(elemento) );
					  /* alloca memoria II elem. */
    strcpy((*puntcorr).nome, nome1);     /* dati II elemento */
    (*puntcorr).punt_fratello = NULL;
    (*puntcorr).punt_figlio = NULL;
    (*punttesta).punt_figlio = puntcorr; /* effettua collegamento */
    }
else
    {                         /* base dati gia' inizializzata */
    cerca(nome2, &trovato);
    if (trovato)
	{           /* in punt_dato c'e' il puntatore all'elemento: */
		    /* scandisce la lista dei figli */
	puntcorr = (elemento *) malloc( sizeof(elemento) );
					  /* alloca memoria l'elem. */
	strcpy((*puntcorr).nome, nome1);     /* inserisce i dati */
	(*puntcorr).punt_fratello = NULL;
	(*puntcorr).punt_figlio = NULL;
	if ((*punt_dato).punt_figlio == NULL)  /* inserice come figlio: */
	    (*punt_dato).punt_figlio = puntcorr; /* non c'erano figli */
	else
	    {                           /* c'era una lista di figli */
	    punt_dato = (*punt_dato).punt_figlio;
					/* punta al primo figlio */
	    while ((*punt_dato).punt_fratello != NULL)
		punt_dato = (*punt_dato).punt_fratello;
					   /* passa la prossimmo figlio */
	    (*punt_dato).punt_fratello = puntcorr;
					       /* effettua collegamento */
				       /* in fondo alla lista dei figli */
	    }
	}
    else
	printf("Errore : non trovato <%s> !\n", nome2);
    }
} /* end inserimento */


void cerca(char nome[], boolean *trovato)
{
/* definizioni locali */
elemento *puntatore;

puntatore = punttesta;                           /* inizializzazione */
*trovato = trovato_in_elemento(nome, puntatore) ||
	    trovato_in_fratello(nome, puntatore) ||
	     trovato_in_figlio(nome, puntatore); /* parte la recursione */
} /* end cerca */


boolean trovato_in_elemento(char nome[], elemento *puntatore)
{
/* definizioni locali */
boolean trovato;

trovato = (strcmp((*puntatore).nome, nome) == 0);
if (trovato)
    punt_dato = puntatore; /* punt_dato punta al record trovato */
return (trovato);
} /* end trovato_in_elemento */

boolean trovato_in_fratello(char nome[], elemento *puntatore)
{
/* definizioni locali */
boolean trovato;

if ((*puntatore).punt_fratello == NULL)
    trovato = FALSE;
else
    {
    puntatore = (*puntatore).punt_fratello;  /* passa al fratello */
    trovato = trovato_in_elemento(nome, puntatore) ||
	       trovato_in_fratello(nome, puntatore) ||
		trovato_in_figlio(nome, puntatore);
				   /* continua ricerca recursiva */
    }
return (trovato);
} /* end trovato_in_fratello */

boolean trovato_in_figlio(char nome[], elemento *puntatore)
{
/* definizioni locali */
boolean trovato;

if ((*puntatore).punt_figlio == NULL)
    trovato = FALSE;
else
    {
    puntatore = (*puntatore).punt_figlio;     /* passa al figlio */
    trovato = trovato_in_elemento(nome, puntatore) ||
	       trovato_in_fratello(nome, puntatore) ||
		trovato_in_figlio(nome, puntatore);
				   /* continua ricerca recursiva */
    }
return (trovato);
} /* end trovato_in_figlio */


void rispondi(char nome1[], char nome2[])
{
/* definizioni locali */
boolean trovato;
elemento *puntatore;

cerca(nome1, &trovato);
if (trovato)
    {
    cerca(nome2, &trovato);
    if (trovato)
	{
	puntatore = punt_dato;   /* si posiziona sull'elemnto nome2 */
	trovato = trovato_in_figlio(nome1, puntatore);
				   /* parte ricerca recursiva */
	if (trovato)
	    printf("VERO\n");
	else
	    printf("FALSO\n");
	}
    else
	printf("Errore: non esiste <%s> !\n", nome2);
    }
else
    printf("Errore: non esiste <%s> !\n", nome1);
} /* end rispondi */