// Laboratorio 8 - Esercizio 1 - main.c
// Matteo Schiff - s295565

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "Elementi.h"
#define MAX_ELEM 5
#define MAX_DIAG 3

typedef struct params
{
    bool acrobNecessaria;
    bool acrobAvantiNecessaria;
    bool acrobIndietroNecessaria;
} Requirements;

Elemento *leggiFile(char *filename, int *N)
{
    FILE *fin;
    if ((fin = fopen(filename, "r")) == NULL)
    {
        puts("Impossibile aprire il file");
        return NULL;
    }
    fscanf(fin, "%d", N);
    Elemento *lista = malloc(*N * sizeof(Elemento));
    for (int i = 0; i < *N; i++)
    {
        lista[i] = leggiElemento(fin);
    }
    fclose(fin);
    return lista;
}

float calcElementValue(Elemento e, Requirements reqs, bool acrobInSeqNecessaria)
{
    float value = (e.valore / e.diff);

    if (e.tipo == AVANTI && reqs.acrobAvantiNecessaria)
    {
        value += 1;
    }

    if (e.tipo == INDIETRO && reqs.acrobIndietroNecessaria)
    {
        value += 1;
    }

    if (e.tipo > 0 && reqs.acrobNecessaria)
    {
        value += 1;
    }

    if (e.tipo > 0 && acrobInSeqNecessaria)
    {
        value += 1;
    }

    return value;
}

// variabili passate come contesto alla funzione di confronto chiamata da qsort
Requirements context;
bool acrobInSeqNecessariaSort;

int greedyChoice(const void *a, const void *b)
{
    Elemento x = *(Elemento *)a;
    Elemento y = *(Elemento *)b;

    float va = calcElementValue(x, context, acrobInSeqNecessariaSort);
    float vb = calcElementValue(y, context, acrobInSeqNecessariaSort);

    return vb > va;
}

void swap(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

void swapE(Elemento *a, Elemento *b)
{
    Elemento c = *a;
    *a = *b;
    *b = c;
}

void sortAccettabili(Elemento *accettabili, int N, Requirements *reqs, bool acrobInSeqNecessaria)
{
    context = *reqs;
    acrobInSeqNecessariaSort = acrobInSeqNecessaria;
    qsort(accettabili, N, sizeof(Elemento), greedyChoice);
}

int getAccettabili(Elemento *accettabili, Elemento *elementi, int N, int DD, int DP, Elemento *soluzione, int posizioneAssoluta, int posInDiag, int currKp, int diffDiags[MAX_DIAG], int diffTot)
{
    int N_accettabili = 0;

    for (int i = 0; i < N; i++)
    {
        if (diffDiags[currKp] + elementi[i].diff > DD || diffTot + elementi[i].diff > DP)
            continue;

        if (posInDiag == 0 && elementi[i].dirIngresso != FRONTE)
            continue;

        if (posInDiag > 0 && elementi[i].dirIngresso != soluzione[posizioneAssoluta - 1].dirUscita)
            continue;

        if (posInDiag == 0 && elementi[i].reqPreced)
            continue;

        accettabili[N_accettabili++] = elementi[i];
    }

    return N_accettabili;
}

void stampaSoluzione(Elemento *soluzione, int *diagSize)
{
    float totPoints = 0, diagPoints;

    for (int i = 0; i < MAX_DIAG; i++)
    {
        diagPoints = 0;
        for (int j = 0; j < diagSize[i]; j++)
        {
            diagPoints += soluzione[i * MAX_ELEM + j].valore;
        }
        printf("DIAG #%d > %.3f", i + 1, diagPoints);
        if (i == MAX_DIAG - 1 && soluzione[diagSize[i] + i * MAX_ELEM - 1].diff >= 8)
        {
            printf(" * 1.5 (BONUS)");
            diagPoints *= 1.5;
        }
        printf("\n");
        totPoints += diagPoints;
        for (int j = 0; j < diagSize[i]; j++)
        {
            printf("%s ", soluzione[i * MAX_ELEM + j].nome);
        }
        printf("\n");
    }
    printf("TOT = %.3f\n", totPoints);
}

void trovaProgrammaGreedy(Elemento *elementi, int N, int DD, int DP)
{
    int diffDiags[MAX_DIAG] = {0};
    int tmp, minDiffAvanti = DD, minDiffIndietro = DD;
    Requirements reqs[MAX_DIAG];
    bool found;
    bool contieneElemFinale[MAX_DIAG];
    bool acrobInSeqNecessaria = true;

    for (int i = 0; i < N; i++)
    {
        if (elementi[i].diff < minDiffAvanti && elementi[i].tipo == AVANTI)
            minDiffAvanti = elementi[i].diff;
        if (elementi[i].diff < minDiffIndietro && elementi[i].tipo == INDIETRO)
            minDiffIndietro = elementi[i].diff;
    }

    for (int i = 0; i < MAX_DIAG; i++)
    {
        contieneElemFinale[i] = false;
        reqs[i].acrobAvantiNecessaria = reqs[i].acrobIndietroNecessaria = reqs[i].acrobNecessaria = true;
    }

    int *diagSize = (int *)malloc(MAX_DIAG * sizeof(int));
    for (int i = 0; i < MAX_DIAG; i++)
        diagSize[i] = 0;
    Elemento *soluzione = (Elemento *)malloc(MAX_DIAG * MAX_ELEM * sizeof(Elemento));
    Elemento *accettabili = (Elemento *)malloc(N * sizeof(Elemento));

    int diffTot = 0;
    for (int numElem = 0; numElem < MAX_ELEM; numElem++)
    {
        for (int numDiag = 0; numDiag < MAX_DIAG; numDiag++)
        {
            int posizioneAssoluta = numElem + numDiag * MAX_ELEM;
            if (!contieneElemFinale[numDiag])
            {
                int numAcc = getAccettabili(accettabili, elementi, N, DD, DP, soluzione, posizioneAssoluta, numElem, numDiag, diffDiags, diffTot);
                if (numAcc > 0)
                {
                    // Ordinamento descrescente delle scelte possibili
                    sortAccettabili(accettabili, numAcc, &reqs[numDiag], acrobInSeqNecessaria);
                    if (reqs[numDiag].acrobAvantiNecessaria != reqs[numDiag].acrobIndietroNecessaria)
                    {
                        found = false;
                        if (reqs[numDiag].acrobAvantiNecessaria)
                        {
                            for (int i = 0; i < numAcc && !found; i++)
                            {
                                // Scelgo la prima diagonale che soddisfa la condizione
                                if (accettabili[i].tipo == AVANTI)
                                {
                                    found = true;
                                    soluzione[posizioneAssoluta] = accettabili[i];
                                    diagSize[numDiag]++;
                                }
                            }

                            if (!found)
                            {
                                for (int i = 0; i < numAcc && !found; i++)
                                {
                                    // "cambio" la direzione in uscita dell'ultimo elemento in modo che nell'iterazione dopo si possa provare ad inserire un elemento acrobatico
                                    if (accettabili[i].dirIngresso != accettabili[i].dirUscita && diffDiags[numDiag] + accettabili[i].diff + minDiffAvanti <= DD && !accettabili[i].finale)
                                    {
                                        soluzione[posizioneAssoluta] = accettabili[i];
                                        diagSize[numDiag]++;
                                        found = true;
                                        // voglio vincolare l'inserimento della acrobazia nell'iterazione successiva (rispetto alle posizioni degli elementi) a questa diagonale
                                        for (tmp = 0; tmp < MAX_DIAG; tmp++)
                                            reqs[tmp].acrobAvantiNecessaria = false;
                                        reqs[numDiag].acrobAvantiNecessaria = true;
                                    }
                                }
                                if (!found)
                                {
                                    // Effettuo la scelta localmente ottima
                                    soluzione[posizioneAssoluta] = accettabili[0];
                                    diagSize[numDiag]++;
                                }
                            }
                        }

                        if (reqs[numDiag].acrobIndietroNecessaria)
                        {
                            for (int i = 0; i < numAcc && !found; i++)
                            {
                                if (accettabili[i].tipo == INDIETRO)
                                {
                                    found = true;
                                    // Effettuo la scelta localmente ottima
                                    soluzione[posizioneAssoluta] = accettabili[i];
                                    diagSize[numDiag]++;
                                }
                            }

                            if (!found)
                            {
                                found = false;
                                for (int i = 0; i < numAcc && !found; i++)
                                {
                                    if (accettabili[i].dirIngresso != accettabili[i].dirUscita && diffDiags[numDiag] + accettabili[i].diff + minDiffIndietro <= DD && !accettabili[i].finale)
                                    {
                                        soluzione[posizioneAssoluta] = accettabili[i];
                                        diagSize[numDiag]++;
                                        for (tmp = 0; tmp < MAX_DIAG; tmp++)
                                            reqs[tmp].acrobIndietroNecessaria = false;
                                        reqs[numDiag].acrobIndietroNecessaria = true;
                                        found = true;
                                    }
                                }
                                if (!found)
                                {
                                    // Effettuo scelta localmente ottima
                                    soluzione[posizioneAssoluta] = accettabili[0];
                                    diagSize[numDiag]++;
                                }
                            }
                        }
                    }
                    else
                    {
                        // Effettuo scelta localmente ottima
                        soluzione[posizioneAssoluta] = accettabili[0];
                        diagSize[numDiag]++;
                    }

                    // Aggiorno le difficoltà di ogni diagonale
                    diffDiags[numDiag] += soluzione[posizioneAssoluta].diff;
                    diffTot += soluzione[posizioneAssoluta].diff;

                    // Aggiorno i parametri della funzione obiettivo
                    if (soluzione[posizioneAssoluta].tipo == AVANTI)
                    {
                        for (int i = 0; i < MAX_DIAG; i++)
                            reqs[i].acrobAvantiNecessaria = false;
                    }
                    if (soluzione[posizioneAssoluta].tipo == INDIETRO)
                    {
                        for (int i = 0; i < MAX_DIAG; i++)
                            reqs[i].acrobIndietroNecessaria = false;
                    }

                    if (numElem > 0 && soluzione[posizioneAssoluta].tipo > 0 && soluzione[posizioneAssoluta - 1].tipo > 0)
                    {
                        acrobInSeqNecessaria = false;
                    }

                    if (soluzione[posizioneAssoluta].finale)
                    {
                        // Blocco l'inserimento di elementi nella diagonale
                        contieneElemFinale[numDiag] = true;
                    }
                }
            }
        }
    }

    // Cerco la diagonale con l'elemento che permette di ottenere il bonus
    int bonusDiag = -1;
    for (int numDiag = 0; numDiag < MAX_DIAG; numDiag++)
    {
        if (soluzione[diagSize[numDiag] + numDiag * MAX_ELEM - 1].diff >= 8)
            bonusDiag = numDiag;
    }

    // Sposto se ho trovato una diagonale idonea al bonus che non è già in ultima posizione
    if (bonusDiag != -1 && bonusDiag != MAX_DIAG - 1)
    {
        swap(&diagSize[MAX_DIAG - 1], &diagSize[bonusDiag]);
        for (int i = 0; i < MAX_ELEM; i++)
            swapE(&soluzione[i + (MAX_DIAG - 1) * MAX_ELEM], &soluzione[i + bonusDiag * MAX_ELEM]);
    }

    stampaSoluzione(soluzione, diagSize);

    free(accettabili);
    free(soluzione);
    free(diagSize);
    return;
}

int main()
{
    int N = 0, DP, DD;
    ;
    Elemento *l = leggiFile("elementi.txt", &N);
    printf("Inserisci DD e DP: ");
    scanf("%d %d", &DD, &DP);

    trovaProgrammaGreedy(l, N, DD, DP);

    free(l);
    return 0;
}