#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
#define EXIT_INCONSISTENCY    5

#define LUNGHEZZA 256

enum _boolean { FALSE = 0, TRUE = 1};
typedef enum _boolean boolean;

typedef struct _struct_frammento Frammento;
typedef Frammento* VettoreFrammenti;

struct _struct_frammento
{
  int PagIn;
  int PagFin;
};


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

void CaricaFrammenti (char *InputFile, int *pNumFrammenti, VettoreFrammenti *pF);

void TrovaFrammentiRidondanti (VettoreFrammenti F, int NumFrammenti, boolean *Ridondante, int *pMaxFin);

void StampaFrammenti (int NumFrammenti, VettoreFrammenti F, boolean *Ridondante);


int main (int argc, char *argv[])
{
  char InputFile[LUNGHEZZA+1];
  int NumFrammenti;
  VettoreFrammenti F;
  boolean *Ridondante;
  int MaxFin;


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

  // 2) Caricamento dei frammenti
  CaricaFrammenti(InputFile,&NumFrammenti,&F);

  // 3) Allocazione delle strutture dati ausiliarie
  Ridondante = (boolean *) calloc(NumFrammenti+1,sizeof(boolean));
  if (Ridondante == NULL)
  {
    printf("Not enough memory to allocate the solution!\n");
    exit(EXIT_MEMORY);
  }

  // 4) Elaborazione
  TrovaFrammentiRidondanti(F,NumFrammenti,Ridondante,&MaxFin);

  // 5) Stampa della soluzione
  StampaFrammenti(NumFrammenti,F,Ridondante);

  // 6) Deallocazione delle strutture dati
  free(F);
  free(Ridondante);

  return EXIT_SUCCESS;
}


void LeggeIstruzioni (int argc, char *argv[], char *InputFile)
{
  if (argc != 2)
  {
    printf("Command line format wrong!\n");
    printf("Use: %s [Fragment file]\n",argv[0]);
    exit(EXIT_WRONGCOMMANDLINE);
  }

  strcpy(InputFile,argv[1]);
}


void CaricaFrammenti (char *InputFile, int *pNumFrammenti, VettoreFrammenti *pF)
{
  FILE *fInputFile;
  int f;


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

  if (fscanf(fInputFile,"%d",pNumFrammenti) != 1)
  {
    printf("File %s does not include the number of fragments!\n",InputFile);
    exit(EXIT_WRONGINPUTFORMAT);
  }

  *pF = (VettoreFrammenti) calloc(*pNumFrammenti+1,sizeof(Frammento));
  if (*pF == NULL)
  {
    printf("Not enough memory to allocate the fragment vector!\n");
    exit(EXIT_MEMORY);
  }

  for (f = 1; f <= *pNumFrammenti; f++)
  {
    if (fscanf(fInputFile,"%d %d",&(*pF)[f].PagIn,&(*pF)[f].PagFin) != 2)
    {
      printf("File %s does not include the initial or final page of fragment %d!\n",f);
      exit(EXIT_WRONGINPUTFORMAT);
    }
  }

  fclose(fInputFile);
}


void TrovaFrammentiRidondanti (VettoreFrammenti F, int NumFrammenti, boolean *Ridondante, int *pMaxFin)
{
  int f, fMax;
  Frammento Temp;

  if (NumFrammenti == 1)
  {
    Ridondante[1] = FALSE;
    *pMaxFin = F[1].PagFin;
  }
  else
  {
    // Costruisce l'istanza ridotta, eliminando l'elemento con pagina iniziale massima
    fMax = NumFrammenti;
    for (f = 1; f < NumFrammenti; f++)
      if (F[f].PagIn > F[fMax].PagIn) fMax = f;

    Temp = F[fMax];
    F[fMax] = F[NumFrammenti];
    F[NumFrammenti] = Temp;

    // Risolve l'istanza ridotta
    TrovaFrammentiRidondanti(F,NumFrammenti-1,Ridondante,pMaxFin);

    // Estende la soluzione dell'istanza ridotta a quella dell'istanza completa
    if (*pMaxFin >= F[NumFrammenti].PagFin)
      Ridondante[NumFrammenti] = TRUE;
    else
    {
      Ridondante[NumFrammenti] = FALSE;
      *pMaxFin = F[f].PagFin;
	}
  }
}


void StampaFrammenti (int NumFrammenti, VettoreFrammenti F, boolean *Ridondante)
{
  int f;

  printf("%d frammenti\n",NumFrammenti);
  for (f = 1; f <= NumFrammenti; f++)
    printf("%d %d %s\n",F[f].PagIn,F[f].PagFin,( Ridondante[f] ? "Ridondante" : "Essenziale") );
}