/**
     Solução feita em sala para o problema da lista 3
**/
#include <stdio.h>
#define MAX 9999999
#define NATIVS 10
#define TRUE  1
#define FALSE 0

/**
   Descreve cada atividade do projeto
**/
struct Atividade{
       char* nome;     // nome da atividade
       int dur;        // duração (em dias)
       int nPreds;     // número de predecessoras ainda não concluídas
       int inicio;     // dia de inicio
       };
/** representa a relação de precedência entre as atividades **/
int matSuc[NATIVS][NATIVS];


/** 
    As variáveis atividades[] e matSuc[][] representam o projeto exemplo  usado nos testes iniciais.
    A idéia é, no futuro, ler os dados de um arquivo texto.
    
**/

/** atividades que compõem o projeto exemplo **/
struct Atividade atividades[] = {
                                   /* 0 */     {"Fundacoes",     30, 0, 0},
                                   /* 1 */     {"Alicerce",      25, 0, 0},
                                   /* 2 */     {"Paredes",       30, 0, 0},
                                   /* 3 */     {"Madeiramento",  20, 0, 0},
                                   /* 4 */     {"Cobertura",     20, 0, 0},
                                   /* 5 */     {"Eletrica",      15, 0, 0},
                                   /* 6 */     {"Hidraulica",    15, 0, 0},
                                   /* 7 */     {"Revestimentos", 20, 0, 0},
                                   /* 8 */     {"Pintura",       20, 0, 0},
                                   /* 9 */     {"Azulejos",      15, 0, 0}
                                };       
                                
/**
     Inicia as estruturas que representam o projeto
**/
void inicia(){
     int i,j;
     for(i = 0; i < NATIVS; i++) {
             atividades[i].nPreds = 0;
             for(j = 0; j < NATIVS; j++) matSuc[i][j] = FALSE; 
     }
}

/*
    marca a2 como sucessora de a1 (a1 precede a2)
*/
void defPred(int a1, int a2) {
     matSuc[a1][a2] = TRUE;
     atividades[a2].nPreds ++;
}

/*
    define a relação de precedência entre as atividades do projeto exemplo
*/
void defPreds(){
     defPred(0,1); // fundações << alicerce
     defPred(1,2); // alicerce  << paredes
     defPred(2,3); // paredes   << madeiramento 
     defPred(3,4); // madeiramento << cobertura
     defPred(2,6); // paredes << hidraulica
     defPred(2,5); // paredes << elétrica
     defPred(6,7); // hidraulica << revestimentos
     defPred(5,7); // elétrica << revestimentos
     defPred(7,9); // revestimentos << azulejos
     defPred(7,8); // revestimentos << pintura
     defPred(9,8); // pintura << azulejos
}

/*
    procura uma atividade que possa ser iniciada (nPreds == 0)
    Retorna o índice da mesma
*/
int buscaAtividade(){
    int i;
    for(i = 0; i < NATIVS; i++) 
          if(atividades[i].nPreds == 0) return i;
    return -1;
}

/**
     Uma das predecessoras da atividade a foi concluída:
        - atualiza o número de predecessoras e verifica se
          atualiza um possível instante de início para a.
**/
void decPreds(int a,int t){
    atividades[a].nPreds --;
    if(atividades[a].inicio < t)       // se o início de a é menor que t
            atividades[a].inicio = t;  //    então a deve iniciar no instante t
}

 
/*
    marca a execução da atividade descrita por atividades[i] iniciada no instante t
    atualizando suas sucessoras via decPreds()
*/
void executa(int a){
     int j;
     int termino = atividades[a].inicio + atividades[a].dur;
     for(j = 0; j < NATIVS; j++){
           if(matSuc[a][j]) {               // se j é sucessora de a
                  decPreds(j,termino);      //    então atualiza j       
           }
     }
     printf("%2d\t%s \t(%d) \t inicio:%4d \t termino:%4d \n",
            a, atividades[a].nome, atividades[a].dur, atividades[a].inicio, termino);
     atividades[a].nPreds = MAX; // para evitar que seja escolhida novamente
}

/**
    programa principal:
             repetir
                     busca atividade 'a' que pode ser iniciada
                     executa a
             até que não exista mais atividade que pode ser iniciada.
**/
int main(){
    inicia();
    defPreds();
    int a,i = 0;    // i indica o número de atividades executadas
    do{
        a = buscaAtividade();
        if(a >= 0) {
             executa(a);
             i++;
        }
    } while(a >=0);
    if(i < NATIVS) printf("Erro: %d atividades não podem ser executadas.\n",NATIVS-i);
    system("PAUSE");
}