/**
 *   \file
 *
 *   \brief definizione di strutture e primitive per lo heap necessario
 *   all'implementazione dell'algoritmo di Dijkstra
 *
 *   \author Alessandro Ambrosano
 *   Si dichiara che il contenuto di questo file è in ogni sua parte
 *   opera originale dell'autore.
 */

#ifndef __HEAP_H_
#define __HEAP_H_
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "macro.h"

typedef struct status {
    struct status* padre;
    unsigned short* conf;
    unsigned int distance;
} status_t;

/** Elemento dello heap */
typedef struct weighted_status {
    /** Etichetta del nodo */
    status_t* status;
    /** Peso del nodo */
    int weight;
} wstatus_t;

/** Struttura contenente lo heap */
typedef struct heap {
    /** Numero di elementi contenuti nello heap */
    int nval;
    /** Numero di elementi massimo nello heap (variabile usata per doubling e halving) */
    int maxval;
    /** Array di puntatori a wnode_t, elementi veri e proprio dello heap */
    wstatus_t** values;
} heap_t;

/** crea uno heap
    \retval p puntatore al nuovo heap (se tutto è andato bene)
    \retval NULL se si è verificato un errore (setta errno)
    (errno == ENOMEM se l'allocazione è fallita)
*/
heap_t* heap_new();

/** aggiunge un nuovo elemento nello heap
    \param h puntatore allo heap in cui aggiungere il nodo pesato
    \param label etichetta del nodo pesato
    \param weight peso del nodo pesato

    \retval 0 se tutto è andato bene
    \retval -1 se si è verificato un errore (setta errno)
    (errno == EINVAL se i parametri non sono validi)
    (errno == ENOMEM se l'allocazione è fallita)
*/
int heap_add (heap_t* h, wstatus_t* status, int weight);

/** modifica un elemento nello heap
    \param h puntatore allo heap in cui modificare il peso del nodo
    \param label nodo di cui modificare l'etichetta
    \param weight nuova etichetta del nodo

    \retval 0 uscita senza errori
    \retval -1 se si è verificato un errore (setta errno)
    (errno == EINVAL se i parametri non sono validi (nodo inesistente o valore dell'etichetta non valido))
*/
/* int heap_reduce(heap_t* h, int label, double weight); */

/** ordina opportunamente i valori all'interno di uno heap
    \param h puntatore allo heap da ordinare
    \param from da dove cominciare a ordinare
*/
void heap_heapify (heap_t* h, int from);

/** stampa uno heap (funzione di debug)
    \param h puntatore allo heap da stampare
*/
void heap_print (heap_t* h);

/** estrae il primo elemento dello heap
    \param h puntatore allo heap da cui estrarre

    \retval p puntatore al n
    \retval NULL se si è verificato un errore (setta errno)
    (errno == EINVAL se i parametri non sono validi (heap vuoto o h == NULL))
*/
wstatus_t* heap_extract(heap_t* q);

#endif