#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 (int NumFrammenti, VettoreFrammenti F, boolean *Ridondante);

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


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


  // 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(NumFrammenti,F,Ridondante);

  // 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);
}


int chiavemaggiore (int e1, int e2, VettoreFrammenti F)
{
  if (F[e1].PagIn > F[e2].PagIn) return TRUE;
  if (F[e1].PagIn < F[e2].PagIn) return FALSE;
  if (F[e1].PagFin < F[e2].PagFin) return TRUE;
  if (F[e1].PagFin > F[e2].PagFin) return FALSE;
  return TRUE;
}


void Heapify (int e, int n, VettoreFrammenti F)
{
  int l, r, eMin;
  Frammento temp;

  l = 2*e;
  r = 2*e+1;

  eMin = e;
  if ( (l <= n) && chiavemaggiore(l,eMin,F) ) eMin = l;
  if ( (r <= n) && chiavemaggiore(r,eMin,F) ) eMin = r;

  if (eMin != e)
  {
    temp = F[e];
    F[e] = F[eMin];
    F[eMin] = temp;

    Heapify(eMin,n,F);
  }
}


void BuildHeap (int n, VettoreFrammenti F)
{
  int i;

  for (i = n/2; i > 0; i--)
    Heapify(i,n,F);
}


void TrovaFrammentiRidondanti (int NumFrammenti, VettoreFrammenti F, boolean *Ridondante)
{
  int g;
  int MaxFin;
  Frammento Temp;


  // Ordina i frammenti per pagina iniziale crescente, costruendo un heap,
  // eliminando ogni volta l'elemento massimo F[1] e riaggiornando l'heap
  BuildHeap(NumFrammenti,F);
  for (g = NumFrammenti; g >= 2; g--)
  {
    Temp = F[1];
    F[1] = F[g];
    F[g] = Temp;
    Heapify(1,g-1,F);
  }
  // Instaura (con g-1 = 1) l'invariante di ciclo:
  // "i g-1 intervalli con PagIn minima sono marcati correttamente
  //  e MaxFin e' il valore massimo delle loro PagFin"
  MaxFin = F[1].PagFin;
  Ridondante[1] = FALSE;

  // Estende la proprieta' sino a g-1 = NumFrammenti
  for (g = 2; g <= NumFrammenti; g++)
  {
    // Conserva l'invariante di ciclo, cercando il frammento non ancora
    // esaminato con PagIn minima e marcandolo correttamente
    if ( MaxFin >= F[g].PagFin)
      Ridondante[g] = TRUE;
    else
    {
      Ridondante[g] = FALSE;
      MaxFin = F[g].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") );
}