/**
 *  \file dgraph.c
 *
 *  \author Alessandro Ambrosano
 *
 *  Si dichiara che il contenuto di questo file è in ogni sua parte
 *  opera originale dell'autore.
 */

#include "heap.h"

heap_t* heap_new() {
    heap_t* ret;

    CHECK_ENOMEM((ret = (heap_t*)malloc(sizeof(heap_t))) == NULL, NULL);

    ret->nval = 0;
    ret->maxval = 0;
    ret->values = NULL;

    return ret;
}

int heap_add (heap_t* q, wstatus_t* status, int weight) {
    wstatus_t* temp;
    int i, father;

    CHECK_EINVAL(q == NULL || weight < 0, -1);

    q->nval++;

    /* Controllo se ho bisogno di riallocare, se il numero di elementi è maggiore del massimo raddoppio
     * la dimensione del vettore dei valori */
    if (q->nval > q->maxval) {
        /* Nella heap_extract() dimezzo il valore di q->maxval ogni volta che il numero di elementi
         * nello heap è meno della metà di q->maxval, quando arrivo a 0, ho bisogno di riallocare
         * un solo elemento */
        if (q->maxval == 0) {
            CHECK_ENOMEM((q->values = (wstatus_t**)realloc(q->values, sizeof(wstatus_t*))) == NULL, -1);
            q->maxval++;
        }
        else {
            CHECK_ENOMEM((q->values = (wstatus_t**)realloc(q->values, 2*(q->maxval)*sizeof(wstatus_t*))) == NULL, -1);
            q->maxval *= 2;
        }
    }

    CHECK_ENOMEM((q->values[q->nval-1] = (wstatus_t*)malloc(sizeof(wstatus_t))) == NULL, -1);

    /* Inserisco i dati del nuovo nodo e riordino lo heap */
    q->values[q->nval-1]->status = status->status;
    q->values[q->nval-1]->weight = weight;

    i = q->nval-1;

    father = (i+1)/2-1;
    while (i > 1 && q->values[i]->weight < q->values[father]->weight) {
        temp = q->values[i];
        q->values[i] = q->values[father];
        q->values[father] = temp;
        i = father;
        father = (i+1)/2-1;
    }

    return 0;
}

/* int heap_exists (heap_t* q, int label) {
    int i;

    i = 0;
    while (i < q->nval) {
        if (q->values[i]->label == label) return 1;
        i++;
    }
    return 0;
} */

void heap_heapify (heap_t* h, int from) {
    int left, right, tinyest;
    wstatus_t* temp;

    left = (from+1)*2-1;
    right = (from+1)*2;
    tinyest = from;

    /* Cerco il minore tra il padre e i figli */
    if (left < h->nval && h->values[left]->weight < h->values[from]->weight) tinyest = left;
    if (right < h->nval && h->values[right]->weight < h->values[from]->weight) tinyest = right;

    /* Se il minore non è il padre, scambio il padre con i minori e riapplico
     * la procedura al sottoalbero in cui sono intervenuto */
    if (tinyest != from) {
        temp = h->values[from];
        h->values[from] = h->values[tinyest];
        h->values[tinyest] = temp;
        heap_heapify(h, tinyest);
    }
}

wstatus_t* heap_extract(heap_t* h) {
    wstatus_t* ret;

    CHECK_EINVAL(h == NULL || h->nval == 0, NULL);

    /* Salvo il primo elemento dello heap e lo rimpiazzo con l'ultimo */
    ret = h->values[0];
    h->nval--;
    h->values[0] = h->values[h->nval];

    /* Riordino lo heap */
    heap_heapify(h, 0);

    if (h->nval == 0) {
        free(h->values);
        h->values = NULL;
        h->maxval = 0;
    }
    else if (h->nval == h->maxval/2) {
        h->values = (wstatus_t**)realloc(h->values, (h->maxval/2)*sizeof(wstatus_t*));
        h->maxval = h->maxval/2;
    }

    return ret;
}

#ifdef ASDFIAOETRWQETGQOER
int heap_reduce(heap_t* q, int label, int weight) {
    int i, father;
    wstatus_t* temp;

    i = 0;
    /* Cerco il nodo label, se non lo trovo do errore */
    while (i < q->nval && q->values[i]->label != label) i++;

    if (i == q->nval) return -1;

    q->values[i]->weight = weight;

    /* Una volta aggiornato lo heap, lo riordino */
    /* Mi va bene non considerare il caso infinito, infatti ogni volta che vado a ridurre
     * provengo da un nodo che ha distanza finita, e sommo un valore finito */
    father = (i+1)/2-1;
    while (i > 0 && q->values[i]->weight > q->values[father]->weight) {
        temp = q->values[i];
        q->values[i] = q->values[father];
        q->values[father] = temp;
        i = father;
        father = (i+1)/2-1;
    }

    return 0;
}
#endif

void heap_print (heap_t* q) {
    int i = 0, j = 0;

    wstatus_t* w;
    status_t* s;

    if (q->nval == 0) printf("CODA VUOTA\n");
    for (i = 0; i < q->nval; i++) {
        w = q->values[i];
        s = w->status;

        for (j = 0; j < 9; j++) {
            printf("%d ", s->conf[j]);
        }
        printf("distance: %d\n", w->weight);
/*        printf("node: %d, weight: %f\n", q->values[i]->conf, q->values[i]->distance); */
    }
}