#include <stdio.h>
#include <stdlib.h>
//#include <string.h>

#define EXIT_SUCCESS          0
#define EXIT_WRONGCOMMANDLINE 1
#define EXIT_MEMORY           2
#define EXIT_OPENFILE         3
#define EXIT_WRONGINPUTFORMAT 4


typedef short boolean;

#define TRUE  1
#define FALSE 0


#define NAMELENGTH  30
#define RIGA         2 * NAMELENGTH + 24
#define DATAFASULLA -1

typedef struct _persona
{
  char            nome[NAMELENGTH+1];
  int             nascita;
  int             morte;
  int             ascesa;
  int             disc;
  int             disc_sovr;
  struct _persona *sx, *dx, *padre;

} persona;

typedef persona* binalbero;
typedef persona* nodo;

void creabinalbero (binalbero *pT);

boolean binalberovuoto (binalbero T);

nodo binradice (binalbero T);

nodo binpadre (nodo u, binalbero T);

nodo figliosinistro (nodo u, binalbero T);

nodo figliodestro (nodo u, binalbero T);

boolean sinistrovuoto (nodo u, binalbero T);

boolean destrovuoto (nodo u, binalbero T);

binalbero costrbinalbero (binalbero T, binalbero U);

binalbero cancsottobinalbero (nodo u, binalbero T);

void scrivinodo (nodo n, char *nome, int nascita, int morte, int ascesa, int disc, int disc_sovr);

binalbero appendenodo (nodo f, nodo p, binalbero T);

nodo CercaPersona (char *Padre, binalbero T);

void StampaAlbero (nodo n, binalbero T);


void LeggeIstruzioni (int argc, char *argv[], char *ParentFile);

void CaricaDiscendenze (char *ParentFile, binalbero *pT);

void CalcolaSovrani (int *pdata, binalbero T);

void StampaSovrani (binalbero T);

void CalcolaDiscendenti (binalbero T);

void StampaDiscendenti (binalbero T);


int main(int argc, char *argv[])
{
  char ParentFile[RIGA+1];
  binalbero T;
  int data;


  // 1) Interpretazione della linea di comando
  LeggeIstruzioni(argc,argv,ParentFile);

  // 2) Inizializzazione delle strutture dati
  creabinalbero(&T);

  // 3) Caricamento dei dati
  CaricaDiscendenze(ParentFile,&T);

  // 4a) Determina il sottoinsieme dei sovrani e calcola le date di ascesa al trono
  data = binradice(T)->ascesa;
  CalcolaSovrani(&data, T);

  // 5a) Stampa l'elenco dei sovrani con i relativi intervalli di regno
  StampaSovrani(T);
  printf("FINE\n");

  // 4b) Calcola per ogni personaggio il numero dei discendenti e dei discendenti sovrani
  CalcolaDiscendenti(T);

  // 5b) Stampa per ogni personaggio il numero dei discendenti e dei discendenti sovrani
  StampaDiscendenti(T);
  printf("FINE\n");

  // 6) Deallocazione delle strutture dati
  T = cancsottobinalbero(binradice(T),T);

  return EXIT_SUCCESS;
}


void LeggeIstruzioni (int argc, char *argv[], char *ParentFile)
{
  if (argc != 2)
  {
    printf("Command line format wrong!\n");
    exit(EXIT_WRONGCOMMANDLINE);
  }

  strcpy(ParentFile,argv[1]);
}


void CaricaDiscendenze (char *ParentFile, binalbero *pT)
{
  FILE *fParentFile;
  char Riga[RIGA+1];
  char Figlio[NAMELENGTH+1], Padre[NAMELENGTH+1];
  int Nascita, Morte;
  binalbero F;
  nodo p;


  fParentFile = fopen(ParentFile,"r");
  if (fParentFile == NULL)
  {
    printf("File %s does not exist!\n",ParentFile);
    exit(EXIT_OPENFILE);
  }

  fgets(Riga,RIGA,fParentFile);
  if (sscanf(Riga,"%s [%d-%d] capostipite",Padre,&Nascita,&Morte) != 3)
  {
    printf("Il formato della prima riga (%s) e' scorretto!\n",Riga);
    exit(EXIT_WRONGINPUTFORMAT);
  }

  // Crea un nuovo albero binario, contenente solo il nodo appena letto
  *pT = costrbinalbero(NULL,NULL);
  scrivinodo(*pT,Padre,Nascita,Morte,Nascita,0,0);

  fgets(Riga,RIGA,fParentFile);
  while (strcmp(Riga,"FINE\n") != 0)
  {
    if (sscanf(Riga,"%s [%d-%d] da %s",Figlio,&Nascita,&Morte,Padre) != 4)
    {
      printf("Il formato della riga %s e' scorretto!\n",Riga);
      exit(EXIT_WRONGINPUTFORMAT);
    }

    // Crea un nuovo albero binario, contenente solo il nodo appena letto
    F = costrbinalbero(NULL,NULL);
    scrivinodo(binradice(F),Figlio,Nascita,Morte,DATAFASULLA,0,0);

    // Cerca il nodo di nome Padre nell'albero genealogico corrente
    p = CercaPersona(Padre,*pT);
    if (p == NULL)
    {
      printf("%s (padre di %s) non compare nell'albero corrente!\n",Padre,Figlio);
      exit(EXIT_WRONGINPUTFORMAT);
    }

    // Lo appende all'albero nella posizione indicata dal padre
    *pT = appendenodo(binradice(F),p,*pT);

    fgets(Riga,RIGA,fParentFile);
  }

  fclose(fParentFile);
}

void CalcolaSovrani (int *pdata, binalbero T)
// Visita in pre-ordine, scrivendo solo i personaggi ancora vivi
// alla data della morte dell'ultimo sovrano
{
  nodo n;

  if (!binalberovuoto(T))
  {
    n = binradice(T);
    if (n->morte > *pdata)
    {
      n->ascesa = *pdata;
      *pdata = n->morte;
    }

    CalcolaSovrani(pdata,figliosinistro(n,T));

    CalcolaSovrani(pdata,figliodestro(n,T));
  }
}

void StampaSovrani (binalbero T)
// Visita in pre-ordine, scrivendo solo i personaggi ancora vivi
// alla data della morte dell'ultimo sovrano
{
  nodo n;

  if (!binalberovuoto(T))
  {
    n = binradice(T);
    if (n->ascesa != DATAFASULLA) printf("%s [%d-%d]\n",n->nome,n->ascesa,n->morte);

    StampaSovrani(figliosinistro(n,T));

    StampaSovrani(figliodestro(n,T));
  }
}


void CalcolaDiscendenti (binalbero T)
{
  nodo n, S, D;

  if (!binalberovuoto(T))
  {
    n = binradice(T);
    S = figliosinistro(n,T);
    D = figliodestro(n,T);

    if (S != NULL)
    {
      CalcolaDiscendenti(S);
      n->disc = S->disc + 1;
      n->disc_sovr = S->disc_sovr;
      if (S->ascesa != DATAFASULLA) n->disc_sovr++;
    }

    if (D != NULL)
    {
      CalcolaDiscendenti(D);
      n->disc += D->disc + 1;
      n->disc_sovr += D->disc_sovr;
      if (D->ascesa != DATAFASULLA) n->disc_sovr++;
    }
  }
}

void StampaDiscendenti (binalbero T)
{
  nodo n;

  if (!binalberovuoto(T))
  {
    n = binradice(T);

    StampaDiscendenti(figliosinistro(n,T));

    StampaDiscendenti(figliodestro(n,T));

    printf("%s: %d di cui %d sovrani\n",n->nome,n->disc,n->disc_sovr);
  }
}


void creabinalbero (binalbero *pT)
{
  *pT = NULL;
}

boolean binalberovuoto (binalbero T)
{
  return (T == NULL);
}

nodo binradice (binalbero T)
{
  if (binalberovuoto(T))
    return NULL;
  else
    return T;
}

nodo binpadre (nodo u, binalbero T)
{
  if (binalberovuoto(T))
    return NULL;
  else
    return u->padre;
}

nodo figliosinistro (nodo u, binalbero T)
{
  if (binalberovuoto(T))
    return NULL;
  else
    return u->sx;
}

nodo figliodestro (nodo u, binalbero T)
{
  if (binalberovuoto(T))
    return NULL;
  else
    return u->dx;
}

boolean sinistrovuoto (nodo u, binalbero T)
{
  if (binalberovuoto(T))
    return TRUE;
  else
    return (u->sx == NULL);
}

boolean destrovuoto (nodo u, binalbero T)
{
  if (binalberovuoto(T))
    return TRUE;
  else
    return (u->dx == NULL);
}

binalbero costrbinalbero (binalbero T, binalbero U)
{
  nodo u = malloc(sizeof(persona));
  if (u == NULL)
  {
    printf("Memoria insufficiente per allocare un nodo!\n");
    exit(EXIT_MEMORY);
  }
  u->padre = NULL;
  u->sx = T;
  u->dx = U;
  if (!binalberovuoto(T)) T->padre = u;
  if (!binalberovuoto(U)) U->padre = u;
  return u;
}


binalbero cancsottobinalbero (nodo u, binalbero T)
// Visita in post-ordine e via via dealloca i nodi
{
  nodo s, d, p;

  if (!binalberovuoto(T) && (u != NULL))
  {
    s = figliosinistro(u,T);
    d = figliodestro(u,T);

    T = cancsottobinalbero(s,T);
    T = cancsottobinalbero(d,T);

    p = binpadre(u,T);
    if (p != NULL)
    {
      if (figliosinistro(p,T) == u) p->sx = NULL;
      if (figliodestro(p,T) == u) p->dx = NULL;
      u->padre = NULL;
    }
    free(u);
    if (u == binradice(T)) T = NULL;
  }

  return T;
}


void scrivinodo (nodo n, char *nome, int nascita, int morte, int ascesa, int disc, int disc_sovr)
{
  if (n != NULL)
  {
    strcpy(n->nome,nome);
    n->nascita   = nascita;
    n->morte     = morte;
    n->ascesa    = ascesa;
    n->disc      = disc;
    n->disc_sovr = disc_sovr;
  }
}


binalbero appendenodo (nodo f, nodo p, binalbero T)
// Appende il nodo f al nodo p. Se e' il primo figlio, lo appende a sinistra.
// Se gia' c'e' un figlio di sinistra, controlla se e' piu' anziano.
// Se e' piu' giovane, sposta il figlio gia' presente a destra, e aggiunge quello nuovo a sinistra.
{
  if ( (f != NULL) && (p != NULL) &&
       ( sinistrovuoto(p,T) || destrovuoto(p,T) ) )
  {
    f->padre = p;
    if (sinistrovuoto(p,T))
      p->sx = f;
    else if (figliosinistro(p,T)->nascita < f->nascita)
      p->dx = f;
    else
    {
      p->dx = figliosinistro(p,T);
      p->sx = f;
    }
  }
  return T;
}


nodo CercaPersona (char *Padre, binalbero T)
// In pre-ordine, dato che cerchiamo un padre,
// che sta probabilmente in alto nell'albero
{
  nodo r, n;

  if (!binalberovuoto(T))
  {
    r = binradice(T);
    if (strcmp(Padre,r->nome) == 0) return r;

    n = CercaPersona(Padre,figliosinistro(r,T));
    if (n != NULL) return n;

    n = CercaPersona(Padre,figliodestro(r,T));
    return n;
  }

  return NULL;
}


void StampaAlbero (nodo n, binalbero T)
// Stampa l'albero T in in-ordine
{
  if (!binalberovuoto(T) && (n != NULL) )
  {
    StampaAlbero(figliosinistro(n,T),T);

    printf("%s\n",n->nome);

    StampaAlbero(figliodestro(n,T),T);
  }
}