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

#define CACHE_SIZE 4096
#define AIR_ROUTE_HASH_SIZE 1024





// Strutture dati per l'implementazione
typedef struct Node {   // elemento per hash e heap
    int x, y;   // coordinate cella
    int costo;   // costo percorso
    int pos_heap; // posizione nell'heap
    struct Node* prossimo;  // puntatore chain hash
} Node;

typedef struct {    // Tabella hash
    int num_elementi;   // elementi inseriti
    int max_size;   // massimo numero elementi
    Node** bucket; // array bucket
    Node* memoria_pool;    // pool allocazione
    int idx_pool; // indice corrente pool
} HashTable;

typedef struct MinHeap {    // coda priorità minima
    int num_elem;   // elementi presenti
    int capienza;   // capienza massima
    Node** coda;   // array puntatori nodi
} MinHeap;

typedef struct {    // collegamento aereo
    int dest_x, dest_y; // destinazione volo
    int prezzo;   // costo volo
} AirRoute;

typedef struct AirRouteNode {
    int parte_x, parte_y;   // partenza
    AirRoute voli[5];     // voli disponibili
    int num_voli;        // numero voli
    struct AirRouteNode* succ;  // prossimo nella hash
} AirRouteNode;

typedef struct {
    int dimensione;               // num bucket
    int massimo;           // max elementi
    AirRouteNode** contenitori; // bucket array
    AirRouteNode* pool_mem;     // pool memoria
    int indice_pool;         // indice pool
} AirRouteTable;

typedef struct {    // Mappa esagonale
    int righe, colonne; // dimensioni griglia
    int* dati_griglia; // blocco dati costi
    int** griglia; // puntatori colonne
    AirRouteTable* rotte_aeree; // tabella rotte
} HexMap;

typedef struct CacheNode {  // nodo cache
    int xp, yp;   // partenza
    int xa, ya;       // arrivo  
    int costo_path;          // costo percorso
    struct CacheNode* next_chain; // prossimo hash chain
    struct CacheNode* precedente; // precedente in lista LRU
    struct CacheNode* seguente; // seguente in lista LRU
} CacheNode;

typedef struct {    // Cache con LRU
    int dim_hash;               // dimensione hash
    int max_elementi;           // massimo prima di LRU
    int conta_elem;      // elementi attuali
    CacheNode** buckets;    // array bucket
    CacheNode* pool_cache;   // pool allocazione
    int idx_pool_cache;         // indice pool
    CacheNode* primo;    // più recente
    CacheNode* ultimo;    // meno recente
} CacheHashTable;





// Funzioni per gestione rotte aeree
inline int hash_rotta(int x, int y, int size) {
    // hash per tabella rotte - funziona abbastanza bene
    return ((x * 73 + y * 31) & (size - 1));
}

inline AirRouteTable* crea_tabella_rotte(int capacity) {
    // alloca e inizializza tabella rotte aeree
    AirRouteTable* tabella = (AirRouteTable*) malloc(sizeof(AirRouteTable));
    tabella->dimensione = AIR_ROUTE_HASH_SIZE;
    tabella->massimo = capacity;
    tabella->contenitori = (AirRouteNode**) calloc(AIR_ROUTE_HASH_SIZE, sizeof(AirRouteNode*));
    tabella->pool_mem = (AirRouteNode*) malloc(capacity * sizeof(AirRouteNode));
    tabella->indice_pool = 0;
    return tabella;
}

inline void pulisci_tabella_rotte(AirRouteTable* tabella) {
    // resetta tutti i bucket e riazzera il pool
    // non faccio free perché tanto sovrascrivo dopo
    memset(tabella->contenitori, 0, tabella->dimensione * sizeof(AirRouteNode*));
    tabella->indice_pool = 0;
}

void distruggi_tabella_rotte(AirRouteTable** tabella) {
    // libera memoria tabella rotte
    if (*tabella) {
        free((*tabella)->contenitori);
        free((*tabella)->pool_mem);
        free(*tabella);
        *tabella = NULL;
    }
}

inline AirRouteNode* trova_nodo_rotte(AirRouteTable* tabella, int x, int y) {
    // cerca nodo con rotte per coordinate date
    int indice = hash_rotta(x, y, tabella->dimensione);
    AirRouteNode* attuale = tabella->contenitori[indice];

    while (attuale != NULL) {
        if (attuale->parte_x == x && attuale->parte_y == y) {
            return attuale;
        }
        attuale = attuale->succ;
    }
    return NULL;
}

inline void rimuovi_nodo_se_vuoto(AirRouteTable* tabella, int x, int y) {
    // se nodo non ha più rotte lo elimino dalla hash
    int indice = hash_rotta(x, y, tabella->dimensione);
    AirRouteNode* corrente = tabella->contenitori[indice];
    AirRouteNode* prec = NULL;

    while (corrente != NULL) {
        if (corrente->parte_x == x && corrente->parte_y == y) {
            if (corrente->num_voli == 0) {
                if (prec == NULL) {
                    tabella->contenitori[indice] = corrente->succ;
                } else {
                    prec->succ = corrente->succ;
                }
            }
            return;
        }
        prec = corrente;
        corrente = corrente->succ;
    }
}

bool modifica_rotta_aerea(AirRouteTable* tabella, HexMap* mappa, int start_x, int start_y, int dest_x, int dest_y) {
    // aggiunge o rimuove rotta aerea - toggle
    AirRouteNode* nodo_rotte = trova_nodo_rotte(tabella, start_x, start_y);

    // controllo se rotta già esiste per rimuoverla
    if (nodo_rotte != NULL) {
        for (int i = 0; i < nodo_rotte->num_voli; i++){
            if ((nodo_rotte->voli[i].dest_x == dest_x) && (nodo_rotte->voli[i].dest_y == dest_y)){
                // rimuovo questa rotta
                for (int j = i; j < nodo_rotte->num_voli - 1; j++){
                    nodo_rotte->voli[j] = nodo_rotte->voli[j+1];
                }
                nodo_rotte->num_voli--;

                // controllo se devo eliminare il nodo
                rimuovi_nodo_se_vuoto(tabella, start_x, start_y);

                return true;
            }
        }

        // controllo se posso aggiungere altre rotte
        if (nodo_rotte->num_voli >= 5){
            return false;
        }
    } else {
        // devo creare nuovo nodo rotte
        if (tabella->indice_pool >= tabella->massimo) {
            return false;
        }

        int indice = hash_rotta(start_x, start_y, tabella->dimensione);
        nodo_rotte = &tabella->pool_mem[tabella->indice_pool++];
        nodo_rotte->parte_x = start_x;
        nodo_rotte->parte_y = start_y;
        nodo_rotte->num_voli = 0;
        nodo_rotte->succ = tabella->contenitori[indice];
        tabella->contenitori[indice] = nodo_rotte;
    }

    // aggiungo la nuova rotta al nodo
    int costo_hex = mappa->griglia[start_x][start_y];
    int prezzo_volo;
    if (nodo_rotte->num_voli == 0){
        prezzo_volo = (int) floor(costo_hex / (nodo_rotte->num_voli + 1));
    } else {
        int somma = 0;
        for (int i = 0; i < nodo_rotte->num_voli; i++){
            somma += nodo_rotte->voli[i].prezzo;
        }
        prezzo_volo = (int) floor((somma + costo_hex) / (nodo_rotte->num_voli + 1));
    }

    nodo_rotte->voli[nodo_rotte->num_voli] = (AirRoute) {dest_x, dest_y, prezzo_volo};
    nodo_rotte->num_voli++;

    return true;
}





// Funzioni mappa
inline void inizializza_mappa(HexMap* mappa, int cols, int rows){
    // setup iniziale della griglia esagonale
    mappa->righe = rows;
    mappa->colonne = cols;

    // alloco tutto insieme per località memoria
    mappa->dati_griglia = (int*) calloc(cols * rows, sizeof(int));

    // array puntatori alle colonne
    mappa->griglia = (int**) malloc(cols * sizeof(int*));

    // imposto puntatori colonne
    for (int i = 0; i < cols; i++) {
        mappa->griglia[i] = &mappa->dati_griglia[i * rows];
    }

    // inizializzo tutti costi a 1
    for (int i = 0; i < cols * rows; i++) {
        mappa->dati_griglia[i] = 1;
    }

    // creo tabella rotte aeree
    mappa->rotte_aeree = crea_tabella_rotte(cols * rows / 10); // circa 10% celle con rotte

    fprintf(stdout,"OK\n");
}

void distruggi_mappa(HexMap* mappa){
    // cleanup completo mappa
    free(mappa->dati_griglia);  // libero blocco principale
    free(mappa->griglia);       // libero puntatori colonne
    distruggi_tabella_rotte(&mappa->rotte_aeree); // libero rotte aeree
    mappa->griglia = NULL;
    mappa->dati_griglia = NULL;
    mappa->rotte_aeree = NULL;
    mappa->righe = mappa->colonne = 0;
}

inline void stampa_mappa(HexMap* mappa){
    // output mappa per debug
    printf("\n");
    for (int i=mappa->righe-1; i>=0; i--){
        if(i%2==1) printf(" ");
        for (int j=0; j<mappa->colonne; j++){
            printf("%d ",mappa->griglia[j][i]);
        }
        printf("\n");
    }
}

inline bool coordinate_valide(HexMap* mappa, int x, int y){
    // check bounds mappa
    return !(x<0 || x>mappa->colonne-1 || y<0 || y>mappa->righe-1);
}

inline int distanza_esagoni(int x_1, int y_1, int x_2, int y_2){
    // calcolo distanza tra esagoni - formula presa da internet, funziona
    int cx1 = x_1 - (y_1 - (y_1 & 1)) / 2;
    int cz1 = y_1;
    int cy1 = -cx1 - cz1;

    int cx2 = x_2 - (y_2 - (y_2 & 1)) / 2;
    int cz2 = y_2;
    int cy2 = -cx2 - cz2;

    return fmax(fabs(cx1 - cx2), fmax(fabs(cy1 - cy2), fabs(cz1 - cz2)));
}

bool cambia_costo(HexMap* mappa, int x, int y, int costo, int raggio){
    // modifica costi in area circolare attorno a punto
    if(!coordinate_valide(mappa, x, y) || raggio<=0 || costo < -10 || costo > 10){
        fputs("KO\n", stdout);
        return false;
    }

    int dist;
    float coefficiente;

    // limito area da controllare al quadrato che contiene il cerchio
    int min_x = fmax(0, x - raggio);
    int max_x = fmin(mappa->colonne - 1, x + raggio);
    int min_y = fmax(0, y - raggio);
    int max_y = fmin(mappa->righe - 1, y + raggio);

    for(int i = min_x; i <= max_x; i++){
        for (int j = min_y; j <= max_y; j++){
            dist = distanza_esagoni(x, y, i, j);
            if (dist < raggio){
                coefficiente = fmax(0.0f, (float)(raggio - dist) / (float)raggio);
                int* costo_hex = &mappa->griglia[i][j];
                *costo_hex = *costo_hex + (int)floor(costo * coefficiente);

                if (*costo_hex > 100){
                    *costo_hex = 100;
                }
                if (*costo_hex < 0){
                    *costo_hex = 0;
                }

                // aggiorno rotte aeree se presenti
                AirRouteNode* nodo_rotte = trova_nodo_rotte(mappa->rotte_aeree, i, j);
                if (nodo_rotte != NULL) {
                    for (int cnt = 0; cnt < nodo_rotte->num_voli; cnt++){
                        int costo_vecchi_voli = 0;
                        for (int n = 0; n < cnt; n++){
                            costo_vecchi_voli += nodo_rotte->voli[n].prezzo;
                        }
                        nodo_rotte->voli[cnt].prezzo = (int)((costo_vecchi_voli + *costo_hex) / (cnt + 1));
                    }
                }
            }
        }
    }

    fputs("OK\n", stdout);
    return true;
}

bool toggle_rotta_aerea(HexMap* mappa, int x_1, int y_1, int x_2, int y_2){
    // attiva/disattiva collegamento aereo
    if(!coordinate_valide(mappa, x_1,y_1) || !coordinate_valide(mappa, x_2,y_2)){
        fputs("KO\n", stdout);
        return false;
    }

    bool esito = modifica_rotta_aerea(mappa->rotte_aeree, mappa, x_1, y_1, x_2, y_2);

    if (esito) {
        fputs("OK\n", stdout);
        return true;
    } else {
        fputs("KO\n", stdout);
        return false;
    }
}





// Funzioni hash table per dijkstra
inline int calcola_hash(int x, int y, int size){
    // funzione hash per coordinate - numeri scelti a caso che funzionano bene
    return ((x * 73 + y * 31) & (size - 1));
}

inline HashTable* crea_hash_table(int size){
    // alloca hash table per dijkstra con pool memoria

    int lung_hash=65536;

    HashTable* ht = (HashTable*) malloc(sizeof(HashTable));
    ht->num_elementi = lung_hash;
    ht->max_size = size;
    ht->bucket = calloc(lung_hash, sizeof(Node*));
    ht->memoria_pool = malloc(size * sizeof(Node));
    ht->idx_pool = 0;

    return ht;
}

inline void pulisci_hash_table(HashTable* ht){
    // reset hash table senza deallocare - riuso pool
    memset(ht->bucket, 0, ht->num_elementi * sizeof(Node*));
    ht->idx_pool = 0;
}

void distruggi_hash_table(HashTable** ht){
    // deallocazione completa hash table
    if (*ht) {
        free((*ht)->bucket);
        free((*ht)->memoria_pool);
        free(*ht);
        *ht = NULL;
    }
}

inline Node* inserisci_o_aggiorna(HashTable* ht, int x, int y, int costo){
    // inserisce nuovo nodo o aggiorna esistente se costo minore
    // ritorna NULL se non serve aggiornare
    int indice = calcola_hash(x, y, ht->num_elementi);

    Node* attuale = ht->bucket[indice];
    while (attuale!=NULL) {
        if (attuale->x == x && attuale->y == y) {
            if (attuale->costo > costo) {
                attuale->costo = costo;
                return attuale;
            }
            return NULL;
        }
        attuale = attuale->prossimo;
    }

    if (ht->idx_pool >= ht->max_size){
        return NULL;
    }

    Node* nuovo_nodo = &ht->memoria_pool[ht->idx_pool++];
    nuovo_nodo->x = x;
    nuovo_nodo->y = y;
    nuovo_nodo->costo = costo;
    nuovo_nodo->pos_heap = -1;
    nuovo_nodo->prossimo = ht->bucket[indice];
    ht->bucket[indice] = nuovo_nodo;

    return nuovo_nodo;
}





// Funzioni heap minimo
inline void risali_heap(MinHeap* heap, int indice) {
    // fa risalire elemento verso radice se ha costo minore del padre
    Node** coda = heap->coda;
    int padre;
    int costo_attuale;
    int costo_padre;

    while (indice > 0) {
        padre = (indice - 1) >> 1;

        costo_attuale = coda[indice]->costo;
        costo_padre = coda[padre]->costo;

        if (costo_attuale >= costo_padre) {
            break;
        }

        // swap nodi
        Node* temp = coda[indice];
        coda[indice] = coda[padre];
        coda[padre] = temp;

        // aggiorno indici
        coda[indice]->pos_heap = indice;
        coda[padre]->pos_heap = padre;

        indice = padre;
    }
}

inline void scendi_heap(MinHeap* heap, int indice) {
    // fa scendere elemento verso foglie se ha costo maggiore dei figli
    int sinistro, destro, minimo;
    const int dim = heap->num_elem;
    Node** coda = heap->coda;
    int costo_attuale;

    while (true) {
        sinistro = (indice << 1) + 1;
        destro = sinistro + 1;
        minimo = indice;

        costo_attuale = coda[minimo]->costo;

        // controllo figlio sinistro
        if (sinistro < dim) {
            int costo_sin = coda[sinistro]->costo;
            if (costo_sin < costo_attuale) {
                minimo = sinistro;
                costo_attuale = costo_sin;
            }
        }

        // controllo figlio destro
        if (destro < dim) {
            int costo_des = coda[destro]->costo;
            if (costo_des < costo_attuale) {
                minimo = destro;
            }
        }

        if (minimo == indice) {
            break;
        }

        // swap elementi
        Node* temp = coda[indice];
        coda[indice] = coda[minimo];
        coda[minimo] = temp;

        // aggiorno posizioni
        coda[indice]->pos_heap = indice;
        coda[minimo]->pos_heap = minimo;

        indice = minimo;
    }
}

inline void inserisci_in_heap(MinHeap* heap, Node* nodo){
    // inserisce nodo in heap o aggiorna posizione se già presente
    if (nodo->pos_heap == -1) {
        if(heap->num_elem >= heap->capienza){
            return;
        }

        nodo->pos_heap = heap->num_elem;
        heap->coda[heap->num_elem] = nodo;
        heap->num_elem++;

        risali_heap(heap, nodo->pos_heap);
    } else {
        risali_heap(heap, nodo->pos_heap);
    }
}

inline Node* estrai_minimo_heap(MinHeap* heap){
    // prende elemento con costo minimo e riordina heap
    if (heap->num_elem == 0){
        return NULL;
    }

    Node* minimo = heap->coda[0];
    minimo->pos_heap = -1;

    heap->num_elem--;

    if (heap->num_elem > 0) {
        heap->coda[0] = heap->coda[heap->num_elem];
        heap->coda[0]->pos_heap = 0;
        scendi_heap(heap, 0);
    }

    return minimo;
}

inline MinHeap* crea_heap(int capacità){
    // alloca heap minimo
    MinHeap* heap = malloc(sizeof(MinHeap));
    heap->coda = malloc(sizeof(Node*) * capacità);
    heap->num_elem = 0;
    heap->capienza = capacità;
    return heap;
}

inline void pulisci_heap(MinHeap* heap){
    // resetta heap senza deallocare
    heap->num_elem = 0;
}

void distruggi_heap(MinHeap* heap){
    // dealloca completamente heap
    free(heap->coda);
    free(heap);
}





// Algoritmo dijkstra
int calcola_costo_viaggio(HexMap* mappa, HashTable* ht, MinHeap* heap, int xp, int yp, int xd, int yd) {
    // dijkstra per trovare percorso minimo tra due punti
    // uso heap per prendere sempre nodo con costo minore
    // uso hash per non rivisitare nodi già processati

    // controllo coordinate
    if ((unsigned)xp >= mappa->colonne || (unsigned)yp >= mappa->righe || (unsigned)xd >= mappa->colonne || (unsigned)yd >= mappa->righe) {
        return -1;
    }

    // se partenza e arrivo sono uguali
    if (xp == xd && yp == yd){
        return 0;
    }

    Node* nuovo_nodo = inserisci_o_aggiorna(ht, xp, yp, 0);
    inserisci_in_heap(heap, nuovo_nodo);

    const int cols = mappa->colonne;
    const int rows = mappa->righe;

    // direzioni esagono per righe pari e dispari - pattern diverso
    static const int dir_pari[6][2] = {
        {+1,  0}, { 0, -1}, {+1, -1},
        {-1,  0}, {+1, +1}, { 0, +1}
    };
    static const int dir_dispari[6][2] = {
        {+1,  0}, {-1, -1}, { 0, -1},
        {-1,  0}, { 0, +1}, {-1, +1}
    };

    while (heap->num_elem > 0) {
        Node* attuale = estrai_minimo_heap(heap);

        // se ho raggiunto destinazione
        if (attuale->x == xd && attuale->y == yd) {
            int risultato = attuale->costo;
            pulisci_heap(heap);
            pulisci_hash_table(ht);
            return risultato;
        }

        const int costo_terreno = mappa->griglia[attuale->x][attuale->y];

        if (costo_terreno == 0){
            continue;
        }

        // scelgo direzioni in base se riga pari o dispari
        const int (*direzioni)[2] = (attuale->y & 1) ? dir_pari : dir_dispari;
        int nuovo_costo = attuale->costo + costo_terreno;

        // controllo tutti i 6 vicini
        for (int i = 0; i < 6; i++) {
            int nuova_x = attuale->x + direzioni[i][0];
            int nuova_y = attuale->y + direzioni[i][1];

            if ((unsigned)nuova_x < cols && (unsigned)nuova_y < rows) {
                nuovo_nodo = inserisci_o_aggiorna(ht, nuova_x, nuova_y, nuovo_costo);
                if (nuovo_nodo) {
                    inserisci_in_heap(heap, nuovo_nodo);
                }
            }
        }

        // controllo se ci sono rotte aeree da questa posizione
        AirRouteNode* nodo_rotte = trova_nodo_rotte(mappa->rotte_aeree, attuale->x, attuale->y);
        if (nodo_rotte != NULL) {
            for (int i = 0; i < nodo_rotte->num_voli; i++) {
                nuovo_nodo = inserisci_o_aggiorna(ht, nodo_rotte->voli[i].dest_x, nodo_rotte->voli[i].dest_y, attuale->costo + nodo_rotte->voli[i].prezzo);
                if (nuovo_nodo) {
                    inserisci_in_heap(heap, nuovo_nodo);
                }
            }
        }
    }

    // destinazione non raggiungibile
    pulisci_heap(heap);
    pulisci_hash_table(ht);
    return -1;
}





// Funzioni cache LRU
inline int hash_cache(int xp, int yp, int xd, int yd, int size){
    // hash per cache - combina tutte e 4 coordinate
    return ((xp * 19 + yp * 13 + xd * 27 + yd * 121) & (size-1));
}

inline CacheHashTable* crea_cache(int capacity){
    // alloca cache con LRU policy

    int lung_hash = CACHE_SIZE;

    // struttura principale
    CacheHashTable* cache = (CacheHashTable*)malloc(sizeof(CacheHashTable));
    cache->dim_hash = lung_hash;
    cache->max_elementi = capacity;
    cache->conta_elem = 0;
    cache->buckets = calloc(lung_hash, sizeof(CacheNode*));
    cache->pool_cache = malloc(capacity * sizeof(CacheNode));
    cache->idx_pool_cache = 0;

    // lista doppia LRU con sentinelle
    cache->primo = &cache->pool_cache[cache->idx_pool_cache++];
    cache->ultimo = &cache->pool_cache[cache->idx_pool_cache++];
    cache->primo->seguente = cache->ultimo;
    cache->ultimo->precedente = cache->primo;
    cache->primo->precedente = NULL;
    cache->ultimo->seguente = NULL;

    return cache;
}

inline void sposta_in_testa(CacheHashTable* cache, CacheNode* nodo){
    // sposta nodo in testa alla lista LRU (più recente)

    // scollego nodo dalla posizione attuale
    if (nodo->precedente){
        nodo->precedente->seguente = nodo->seguente;
    }
    if (nodo->seguente){
        nodo->seguente->precedente = nodo->precedente;
    }

    // inserisco in testa
    nodo->seguente = cache->primo->seguente;
    nodo->precedente = cache->primo;
    cache->primo->seguente->precedente = nodo;
    cache->primo->seguente = nodo;
}

inline void rimuovi_nodo_cache(CacheHashTable* cache, CacheNode* nodo, int xp, int yp, int xd, int yd){
    // elimina nodo da hash e da lista LRU

    // rimozione da hash table
    int indice = hash_cache(xp, yp, xd, yd, cache->dim_hash);
    CacheNode* attuale = cache->buckets[indice];
    CacheNode* prec = NULL;

    while (attuale != NULL) {
        if (attuale == nodo) {
            if (prec == NULL) {
                cache->buckets[indice] = attuale->next_chain;
            } else {
                prec->next_chain = attuale->next_chain;
            }
            break;
        }
        prec = attuale;
        attuale = attuale->next_chain;
    }

    // rimozione da lista LRU
    if (nodo->precedente) nodo->precedente->seguente = nodo->seguente;
    if (nodo->seguente) nodo->seguente->precedente = nodo->precedente;

    cache->conta_elem--;
}

inline CacheNode* cerca_in_cache(CacheHashTable* cache, int xp, int yp, int xd, int yd){
    // cerca percorso in cache e sposta in testa se trovato
    int indice = hash_cache(xp, yp, xd, yd, cache->dim_hash);
    CacheNode* attuale = cache->buckets[indice];

    while (attuale != NULL) {
        if (attuale->xp == xp && attuale->yp == yp && attuale->xa == xd && attuale->ya == yd) { // trovato
            sposta_in_testa(cache, attuale);
            return attuale;
        }
        attuale = attuale->next_chain;
    }
    return NULL;    // non trovato
}

inline CacheNode* inserisci_in_cache(CacheHashTable* cache, int xp, int yp, int xd, int yd, int costo){
    // inserisce percorso in cache o aggiorna se già presente
    CacheNode* esistente = cerca_in_cache(cache, xp, yp, xd, yd);
    if (esistente != NULL) {
        esistente->costo_path = costo;
        return esistente;
    }

    // se cache piena rimuovo elemento meno recente
    if (cache->conta_elem >= cache->max_elementi) {
        CacheNode* nodo_lru = cache->ultimo->precedente;
        if (nodo_lru != cache->primo) {
            rimuovi_nodo_cache(cache, nodo_lru, nodo_lru->xp, nodo_lru->yp, nodo_lru->xa, nodo_lru->ya);
        }
    }

    // creo nuovo nodo
    CacheNode* nuovo_nodo = &cache->pool_cache[cache->idx_pool_cache++];
    nuovo_nodo->xp = xp;
    nuovo_nodo->yp = yp;
    nuovo_nodo->xa = xd;
    nuovo_nodo->ya = yd;
    nuovo_nodo->costo_path = costo;

    // inserisco in hash table
    int indice = hash_cache(xp, yp, xd, yd, cache->dim_hash);
    nuovo_nodo->next_chain = cache->buckets[indice];
    cache->buckets[indice] = nuovo_nodo;

    // inserisco in testa lista LRU
    nuovo_nodo->seguente = cache->primo->seguente;
    nuovo_nodo->precedente = cache->primo;
    cache->primo->seguente->precedente = nuovo_nodo;
    cache->primo->seguente = nuovo_nodo;

    cache->conta_elem++;
    return nuovo_nodo;
}

inline void elimina_da_cache(CacheHashTable* cache, int xp, int yp, int xd, int yd){
    // trova e rimuove elemento specifico dalla cache
    int indice = hash_cache(xp, yp, xd, yd, cache->dim_hash);
    CacheNode* attuale = cache->buckets[indice];

    while (attuale != NULL) {
        if (attuale->xp == xp && attuale->yp == yp && attuale->xa == xd && attuale->ya == yd) {
            rimuovi_nodo_cache(cache, attuale, xp, yp, xd, yd);
            return;
        }
        attuale = attuale->next_chain;
    }
}

void svuota_cache(CacheHashTable* cache){
    // reset completo cache mantenendo struttura
    memset(cache->buckets, 0, cache->dim_hash * sizeof(CacheNode*));
    cache->idx_pool_cache = 0;
    cache->conta_elem = 0;

    // ricrea sentinelle LRU
    cache->primo = &cache->pool_cache[cache->idx_pool_cache++];
    cache->ultimo = &cache->pool_cache[cache->idx_pool_cache++];
    cache->primo->seguente = cache->ultimo;
    cache->ultimo->precedente = cache->primo;
    cache->primo->precedente = NULL;
    cache->ultimo->seguente = NULL;
}

void distruggi_cache(CacheHashTable** cache){
    // deallocazione completa cache
    if (*cache) {
        free((*cache)->buckets);
        free((*cache)->pool_cache);
        free(*cache);
        *cache = NULL;
    }
}





// Funzione principale
int main(){
    char comando[17];
    int param1, param2, param3, param4;

    HexMap mappa;
    HashTable* hash_dijkstra = NULL;
    MinHeap* heap_dijkstra = NULL;
    CacheHashTable* cache_percorsi = NULL;

    int mappa_inizializzata=0;
    CacheNode* risultato_cache;
    int costo_percorso;

    while (true){
        int esito_input = scanf("%s %d %d %d %d",comando, &param1, &param2, &param3, &param4);
        if (esito_input==-1){
            break;
        }

        if (strcmp(comando, "init")==0){
            if (mappa_inizializzata==1){
                distruggi_mappa(&mappa);
            }
            inizializza_mappa(&mappa, param1, param2);
            mappa_inizializzata=1;

            if (hash_dijkstra!=NULL){
                distruggi_hash_table(&hash_dijkstra);
            }
            hash_dijkstra = crea_hash_table(param1 * param2);

            if (heap_dijkstra!=NULL){
                distruggi_heap(heap_dijkstra);
            }
            heap_dijkstra = crea_heap(param1 * param2);

            if (cache_percorsi!=NULL){
                distruggi_cache(&cache_percorsi);
            }
            cache_percorsi = crea_cache(CACHE_SIZE);
        }

        if (strcmp(comando, "print")==0){
            if (mappa_inizializzata==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            stampa_mappa(&mappa);
        }

        if (strcmp(comando, "change_cost")==0){
            if (mappa_inizializzata==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            if(cambia_costo(&mappa, param1, param2, param3, param4)){
                svuota_cache(cache_percorsi);
            }
        }

        if (strcmp(comando, "toggle_air_route")==0){
            if (mappa_inizializzata==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            if(toggle_rotta_aerea(&mappa, param1, param2, param3, param4)){
                svuota_cache(cache_percorsi);
            }
        }

        if (strcmp(comando, "travel_cost")==0){
            if (mappa_inizializzata==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            risultato_cache=cerca_in_cache(cache_percorsi, param1, param2, param3, param4);

            if(risultato_cache!=NULL){
                costo_percorso = risultato_cache->costo_path;
            } else {
                costo_percorso = calcola_costo_viaggio(&mappa, hash_dijkstra, heap_dijkstra, param1, param2, param3, param4);
                inserisci_in_cache(cache_percorsi, param1, param2, param3, param4, costo_percorso);
            }

            fprintf(stdout, "%d\n", costo_percorso);
            fflush(stdout);
        }
    }

    // cleanup finale
    if (mappa_inizializzata==1) {
        distruggi_mappa(&mappa);
    }
    if (hash_dijkstra!=NULL) {
        distruggi_hash_table(&hash_dijkstra);
    }
    if (heap_dijkstra!=NULL) {
        distruggi_heap(heap_dijkstra);
    }
    if (cache_percorsi!=NULL) {
        distruggi_cache(&cache_percorsi);
    }

    return 0;
}