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

// definicia typu boolean
#ifndef BOOL
  #define BOOL int
#endif

#ifndef FALSE
  #define FALSE 0
#endif

#ifndef TRUE
  #define TRUE 1
#endif

// maximalny pocet uloh
#define ULOH_MAX 20

typedef struct _tUloha
{
  char popis[21]; // nazov ulohy
  int p; // cas spracovania ulohy
  int r; // cas vstupu ulohy do systemu
  int d; // pozadovany cas ukoncenia spracovania
  int w; // vaha ulohy
} tUloha, *pUloha;

int uloh; // pocet uloh
pUloha ulohy[ULOH_MAX]; // pole uloh

// sluzi na zinicializovanie pola uloh
void Inicializacia()
{
  int i;
  
  uloh = 0;
  for (i = 0; i < ULOH_MAX; i++) ulohy[i] = NULL;
}

// sluzi na uvolnenie pola uloh
void Koniec()
{
  int i;
  
  for (i = 0; i < uloh; i++)
  {
    free(ulohy[i]); ulohy[i] = NULL;
  }
  uloh = 0;
}

// sluzi na nacitanie textoveho suboru uloh
void Nacitaj(const char *filename)
{
  FILE *t;
  char s[256];
  char *ps;
  int i, l;
  pUloha pu;

  // otvorenie suboru
  if ((t = fopen(filename, "rt")) == NULL)
  {
    fprintf(stderr, "Nepodarilo sa otvorit subor %s.\n", filename);
    exit(1);
  }
  
  // postupne nacitaj riadky zo suboru
  while (fgets(s, 255, t) != NULL)
  {
    s[255] = '\0'; // ak je riadok v subore dlhsi, treba pridat znak koniec retazca
    l++; // pocitadlo riadkov
    
    // ignoruj prazdny riadok v subore
    if (s[0] == '\0' || s[0] == '\r' || s[0] == '\n') continue;
    
    // ignoruj riadky zacinajuce '#'
    if (s[0] == '#') continue;
    
    // alokuj pamat na ulohu
    if ((pu = (pUloha) malloc(sizeof(tUloha))) == NULL)
    {
      fprintf(stderr, "Nepodarilo sa alokovat pamat.\n");
      exit(1);
    }
    
    // rozdel retazec podla ':'
    if ((ps = strtok(s, ":")) == NULL)
    {
      fprintf(stderr, "Chyba v subore %s na riadku %d.\n", filename, l);
      exit(1);
    }
    // najskor je popis ulohy, pre istotu pridaj znak koniec retazca
    strncpy(pu->popis, ps, 20); pu->popis[20] = '\0'; 
    
    // dalsi podretazec (prvy parameter NULL)
    if ((ps = strtok(NULL, ":")) == NULL)
    {
      fprintf(stderr, "Chyba v subore %s na riadku %d.\n", filename, l);
      exit(1);
    }
    // cas spracovania ulohy
    pu->p = atoi(ps);
    
    // dalsi podretazec (prvy parameter NULL)
    if ((ps = strtok(NULL, ":")) == NULL)
    {
      fprintf(stderr, "Chyba v subore %s na riadku %d.\n", filename, l);
      exit(1);
    }
    // cas vstupu ulohy do systemu
    pu->r = atoi(ps);
    
    // dalsi podretazec (prvy parameter NULL)
    if ((ps = strtok(NULL, ":")) == NULL)
    {
      fprintf(stderr, "Chyba v subore %s na riadku %d.\n", filename, l);
      exit(1);
    }
    // pozadovany cas ukoncenia ulohy
    pu->d = atoi(ps);
    
    // posledny podretazec (prvy parameter NULL, konci znakom koniec riadku)
    if ((ps = strtok(NULL, "\r\n")) == NULL)
    {
      fprintf(stderr, "Chyba v subore %s na riadku %d.\n", filename, l);
      exit(1);
    }
    // vaha ulohy
    pu->w = atoi(ps);
    
    // a uloz do pola
    if (uloh == ULOH_MAX)
    {
      fprintf(stderr, "Pole uloh je uz plne - zvyste prosim konstantu ULOH_MAX.\n");
      exit(1);
    }
    ulohy[uloh++] = pu;
  }
  
  // zatvorenie suboru
  fclose(t);
}

// sluzi na vypisanie pola uloh
void Vypis()
{
  int i, t;
  
  t = 0;
  for (i = 0; i < uloh; i++)
  {
    // vypis nazvu, zaciatku a konca vykonavania ulohy
    printf("%s<%d,%d> ", ulohy[i]->popis, t, t + ulohy[i]->p);
    // posun cas na koniec vykonavania ulohy
    t += ulohy[i]->p;
  }
  printf("\n\n");
}

// vypocet priemernej doby pobytu ulohy v systeme
float Fpriem()
{
  int i;
  long suma;
  
  // vypocet suctu dlzok pobytu uloh v systeme 
  //  S = p_1 + (p_1 + p_2) + (p_1 + p_2 + p_3) + ... = n * p_1 + (n - 1) * p_2 + (n - 2) * p_3 + ....
  
  // !!! v jazyku C kazde pole zacina s indexom 0, teda
  //  S = p_0 + (p_0 + p_1) + (p_0 + p_1 + p_2) + ... = n * p_0 + (n - 1) * p_1 + (n - 2) * p_2 + ....
  
  suma = 0;
  for (i = 0; i < uloh; i++)
  {
    suma += (uloh - i) * ulohy[i]->p;
  }
  // operandy je potrebne pretypovat, aby bol vysledok realne cislo
  return (float) suma / (float) uloh;
}

// minimalizacia Fpriem => usporiadat ulohy podla casu spracovania vzostupne
void MinFpriem()
{
  int i;
  pUloha temp;
  BOOL prehodene;
  
  // vypis aktualne usporadanie pola uloh
  printf("Pociatocne riesenie:\n");
  printf("Fpriem = %6.2f\n", Fpriem());
  Vypis();
  
  // idem usporiadat pole uloh - bublinkove triedenie
  do
  {
    prehodene = FALSE;
    for (i = 0; i < uloh - 1; i++)
    {
      if (ulohy[i]->p > ulohy[i+1]->p)
      {
        temp = ulohy[i]; ulohy[i] = ulohy[i+1]; ulohy[i+1] = temp;
        prehodene = TRUE;
      }
    }
    
    printf("Priebezne riesenie:\n");
    printf("Fpriem = %6.2f\n", Fpriem());
    Vypis();
    
  } while (prehodene);

  printf("Vysledne riesenie:\n");
  printf("Fpriem = %6.2f\n", Fpriem());
  Vypis();
}

// hlavny program
int main(int argc, char *argv[])
{
  // inicializacia a nacitanie pola uloh
  Inicializacia();
  Nacitaj("uloha.txt");
  
  // optimalizacia rozvrhu podla priemernej doby pobytu ulohy v systeme (Fpriem)
  MinFpriem();
  
  // uvolnenie alokovanej pamate
  Koniec();
  
  return 0;
}