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

#define CACHE_SIZE 4096





// BEGIN STRUCTURES
typedef struct Node {   // Nodo puntato sia dalla hash table che dall'heap. Usato in Dijkstra
    int x, y;   // Coordinate
    int cost;   // Costo di raggiungimento
    int heap_index; // Indice nell'heap
    struct Node* next;  // Puntatore al prossimo elemento (hash table con chaining)
} Node;

typedef struct {    // Hash table
    int size;   // Quantità di nodi presenti
    int capacity;   // Capacità massima
    Node** buckets; // Puntatore all'array di puntatori ai Node
    Node* pool;    // Puntatore alla pool di memoria contigua
    int pool_index; // Indice del pool di memoria contigua
} HashTable;

typedef struct MinHeap {    // Heap
    int size;   // Quantità di nodi presenti
    int capacity;   // Capacità massima
    Node** queue;   // Puntatore all'array di puntatori ai Node
} MinHeap;

typedef struct {    // Rotta aerea
    int dest_x, dest_y; // Destinazione
    int cost;   // Costo di raggiungimento
} AirRoute;

typedef struct {    // Esagono
    int land_cost;  // Costo uscita esagono
    AirRoute air_routes[5]; // Array di rotte aeree
    int air_route_count;    // Quantità di rotte aeree presenti
} Hexagon;

typedef struct {    // Mappa di esagoni
    int rows, cols; // Numero di righe e colonne
    Hexagon* grid_data; // Puntatore al blocco in RAM contenente tutti gli esagoni
    Hexagon** grid; // Array di puntatori alle colonne
} HexMap;

typedef struct CacheNode {  // Nodo della cache
    int xp, yp;   // Coordinate di partenza
    int xd, yd;       // Coordinate di arrivo
    int cost;          // Costo di percorrenza
    struct CacheNode* next; // Puntatore al prossimo elemento (hash table chained)
    struct CacheNode* lru_prev; // Puntatore all'elemento precedente nella double linked list LRU
    struct CacheNode* lru_next; // Puntatore al prossimo elemento nella double linked list LRU
} CacheNode;

typedef struct {    // Hash table della cache
    int size;               // Quantità di bucket
    int capacity;           // Quantità massima di nodi prima di iniziare ad attuare la policy di LRU
    int element_number;      // Quantità attuale di elementi nella cache
    CacheNode** buckets;    // Puntatore all'array di puntatori ai CacheNode
    CacheNode* pool;   // Puntatore alla pool di memoria contigua
    int pool_index;         // Indice del pool di memoria contigua
    CacheNode* head;    // CacheNode più recentemente usato
    CacheNode* tail;    // CacheNode meno recentemente usato
} CacheHashTable;
// END





// BEGIN MAP FUNCTIONS
inline void init_map(HexMap* map, int cols, int rows){
    // Inizializza la griglia: prende in input il puntatore alla struttura mappa, righe e colonne e crea la griglia formata da un array di puntatori ad array
    map->rows = rows;
    map->cols = cols;

    // Alloca lo spazio di tutti gli esagoni in blocco (per minimizzare cache miss)
    map->grid_data = (Hexagon*) calloc(cols * rows, sizeof(Hexagon));

    // Alloca i puntatori alle singole colonne
    map->grid = (Hexagon**) malloc(cols * sizeof(Hexagon*));

    // Inizializza i puntatori alle singole colonne
    for (int i = 0; i < cols; i++) {
        map->grid[i] = &map->grid_data[i * rows];
    }

    // Inizializza gli attributi di tutti gli esagoni (la calloc mette tutto a zero, quindi l'air_route_count è già a 0)
    for (int i = 0; i < cols * rows; i++) {
        map->grid_data[i].land_cost = 1;
    }

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

void destroy_map(HexMap* map){
    // Distrugge la mappa
    free(map->grid_data);  // Dealloca il mega blocco contenente tutti gli esagoni
    free(map->grid);       // Dealloca i singoli puntatori alle colonne
    map->grid = NULL;
    map->grid_data = NULL;
    map->rows = map->cols = 0;
}

inline void print_map(HexMap* map){
    // Stampa la mappa
    printf("\n");
    for (int i=map->rows-1; i>=0; i--){
        if(i%2==1) printf(" ");
        for (int j=0; j<map->cols; j++){
            printf("%d ",map->grid[j][i].land_cost);
        }
        printf("\n");
    }
}

inline bool is_valid(HexMap* map, int x, int y){
    // Controlla se delle coordinate sono entro i bordi della mappa
    return !(x<0 || x>map->cols-1 || y<0 || y>map->rows-1);
}

inline int hexagons_distance(int x_1, int y_1, int x_2, int y_2){
    // Calcola la distanza tra due esagoni tramite le coordinate cubiche (non ho idea di come funzioni, fidati)
    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 change_cost(HexMap* map, int x, int y, int cost, int radius){
    // Cambia il costo nella mappa: per ogni esagono nella mappa all'interno del quadrato che inscrive il cerchio di raggio radius calcola la distanza dal nodo sorgente, se è inferiore del raggio allora cambia il costo dell'esagono secondo la formula. Successivamente aggiorna i costi delle rotte aeree
    // NOTA: il costo può variare massimo tra 0 e 100
    if(!is_valid(map, x, y) || radius<=0 || cost < -10 || cost > 10){
        fputs("KO\n", stdout);
        return false;
    }

    int dist;
    int cost_old_air_route;
    float coeff;

    // Le x e le y che vado a modificare sono solo quelle dentro al quadrato che inscrive la circonferenza di raggio radius
    int min_x = fmax(0, x - radius);
    int max_x = fmin(map->cols - 1, x + radius);
    int min_y = fmax(0, y - radius);
    int max_y = fmin(map->rows - 1, y + radius);

    for(int i = min_x; i <= max_x; i++){
        for (int j = min_y; j <= max_y; j++){
            dist = hexagons_distance(x, y, i, j);
            if (dist < radius){
                coeff = fmax(0.0f, (float)(radius - dist) / (float)radius); // Aggiorna il costo via terra
                Hexagon* hex = &map->grid[i][j];
                hex->land_cost = hex->land_cost + (int)floor(cost * coeff);

                if (hex->land_cost > 100){  // Impone che il costo via terra sia compreso tra 0 e 100
                    hex->land_cost = 100;
                }
                if (hex->land_cost < 0){
                    hex->land_cost = 0;
                }

                for (int counter = 0; counter < hex->air_route_count; counter++){   // Aggiorna il costo delle rotte aeree
                    cost_old_air_route = 0;
                    for (int n = 0; n < counter; n++){
                        cost_old_air_route = cost_old_air_route + hex->air_routes[n].cost;
                    }
                    hex->air_routes[counter].cost = (int)((cost_old_air_route + hex->land_cost) / (counter + 1));
                }
            }
        }
    }

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

bool toggle_air_route(HexMap* map, int x_1, int y_1, int x_2, int y_2){
    // Inserisce o rimuove una rotta aerea da un esagono
    if(!is_valid(map, x_1,y_1) || !is_valid(map, x_2,y_2)){
        fputs("KO\n", stdout);
        return false;
    }

    Hexagon* StartingHexagon = &(map->grid[x_1][y_1]);

    if (StartingHexagon->air_route_count>4){
        fputs("KO\n", stdout);
        return false;
    }

    for (int i=0; i< StartingHexagon->air_route_count; i++){
        if ((StartingHexagon->air_routes[i].dest_x == x_2)&&(StartingHexagon->air_routes[i].dest_y == y_2)){
            for (int j=i; j<StartingHexagon->air_route_count; j++){
                StartingHexagon->air_routes[j]=StartingHexagon->air_routes[j+1];
            }
            StartingHexagon->air_route_count = StartingHexagon->air_route_count - 1;
            fputs("OK\n", stdout);
            return true;
        }
    }

    int cost;
    if (StartingHexagon->air_route_count==0){
        cost = (int) floor(StartingHexagon->land_cost / ((StartingHexagon->air_route_count)+1));
    } else {
        int sum=0;
        for (int i=0; i< StartingHexagon->air_route_count; i++){
            sum = sum + (int) StartingHexagon->air_routes[i].cost;
        }
        cost = (int) floor((int) (sum+(StartingHexagon->land_cost)) / ((StartingHexagon->air_route_count)+1));
    }

    StartingHexagon->air_routes[StartingHexagon->air_route_count] = (AirRoute) {x_2, y_2, cost};
    StartingHexagon->air_route_count = StartingHexagon->air_route_count + 1;
    fputs("OK\n", stdout);
    return true;
}
// END





// BEGIN HASH TABLE FUNCTIONS
inline int calculate_hash(int x, int y, int size){
    // Calcola l'hash dati in input le coordinate e la dimensione della hash table
    return ((x * 73 + y * 31) % size);
}

inline HashTable* create_hash_table(int size){
    // Genera l'hash table con fattore di carico 1.5 per bilanciare performance temporali e spaziali. Calcola il numero primo migliore da usare come dimensione dell'hash table e poi inizializza tutti i suoi attributi
    // NOTA: con calloc() vado a inizializzare già tutti i bucket a 0, quindi non devo preoccuparmi di farli puntare a NULL
    int min_size = (int)ceil(size / 1.3);

    int hash_length;
    if (min_size <= 53) {
        hash_length = 53;
    } else if (min_size <= 97) {
        hash_length = 97;
    } else if (min_size <= 193) {
        hash_length = 193;
    } else if (min_size <= 389) {
        hash_length = 389;
    } else if (min_size <= 769) {
        hash_length = 769;
    } else if (min_size <= 1543) {
        hash_length = 1543;
    } else if (min_size <= 3079) {
        hash_length = 3079;
    } else if (min_size <= 6151) {
        hash_length = 6151;
    } else if (min_size <= 12289) {
        hash_length = 12289;
    } else if (min_size <= 24593) {
        hash_length = 24593;
    } else if (min_size <= 49157) {
        hash_length = 49157;
    } else if (min_size <= 98317) {
        hash_length = 98317;
    } else if (min_size <= 196613) {
        hash_length = 196613;
    } else if (min_size <= 393241) {
        hash_length = 393241;
    } else if (min_size <= 786433) {
        hash_length = 786433;
    } else {
        hash_length = 1572869;
    }

    HashTable* ht = (HashTable*) malloc(sizeof(HashTable));
    ht->size = hash_length;
    ht->capacity = size;
    ht->buckets = calloc(hash_length, sizeof(Node*));
    ht->pool = malloc(size * sizeof(Node));
    ht->pool_index = 0;

    return ht;
}

inline void clear_hash_table(HashTable* ht){
    // Mette a 0 tutti i bucket e va a resettare il pool di memoria contigua
    // NOTA: non va a fare delle free perchè al prossimo utilizzo della hash table vado a sovrascrivere i nodi (verranno sempre scritti nel pool di memoria)
    memset(ht->buckets, 0, ht->size * sizeof(Node*));
    ht->pool_index = 0;
}

void destroy_hash_table(HashTable** ht){
    // Elimina completamente una hash table (anche il suo pool di memoria contigua)
    if (*ht) {
        free((*ht)->buckets);
        free((*ht)->pool);
        free(*ht);
        *ht = NULL;
    }
}

inline Node* insert_or_update_element(HashTable* ht, int x, int y, int cost){
    // Se il nodo che sto provando ad inserire non esiste, lo inserisco in testa alla chain.
    // Se invece esiste controllo il costo: se è maggiore di quello già presente in hash table ignoro (ritorno NULL), altrimenti aggiorno il costo
    // NOTA: quando inserisco per la prima volta in hash table inizializzo heap_index a -1 per intendere che non è ancora stato inserito in heap
    int index = calculate_hash(x, y, ht->size);

    Node* current = ht->buckets[index];
    while (current!=NULL) {
        if (current->x == x && current->y == y) {
            if (current->cost > cost) {
                current->cost = cost;
                return current;
            }
            return NULL;
        }
        current = current->next;
    }

    if (ht->pool_index >= ht->capacity){
        return NULL;
    }

    Node* new_node = &ht->pool[ht->pool_index++];
    new_node->x = x;
    new_node->y = y;
    new_node->cost = cost;
    new_node->heap_index = -1;
    new_node->next = ht->buckets[index];
    ht->buckets[index] = new_node;

    return new_node;
}
// END





// BEGIN HEAP FUNCTIONS
inline void heap_swap(Node** a, Node** b){
    // Permette di swappare due nodi (viene usato dalle heapify)
    Node* temp = *a;
    *a = *b;
    *b = temp;

    int tmp_index = (*a)->heap_index;
    (*a)->heap_index = (*b)->heap_index;
    (*b)->heap_index = tmp_index;
}

inline void heapify_up(MinHeap* heap, int index){
    // Fa salire un nodo dal basso verso l'alto (lo swappo con il genitore)
    // NOTA: viene usato quando inserisco un nuovo nodo: lo inserisco come foglia e poi lo faccio risalire fino alla sua posizione corretta
    int parent;
    while (index > 0) {
        parent = (index - 1) / 2;
        if (heap->queue[index]->cost >= heap->queue[parent]->cost){
            break;
        }

        heap_swap(&heap->queue[index], &heap->queue[parent]);
        index = parent;
    }
}

inline void heapify_down(MinHeap* heap, int index){
    // Fa scendere un nodo dall'alto verso il basso (lo swappo con un figlio)
    // NOTA: viene usato quando consumo il nodo minimo (root) in Dijkstra: metto il nodo più grande di tutti come root e poi lo faccio scendere fino alla posizione corretta
    int left, right, smallest;
    int size = heap->size;

    while (true) {
        left = (index * 2) + 1;
        right = left + 1;
        smallest = index;

        if (left < size && heap->queue[left]->cost < heap->queue[smallest]->cost) {
            smallest = left;
        }

        if (right < size && heap->queue[right]->cost < heap->queue[smallest]->cost) {
            smallest = right;
        }

        if (smallest == index){
            break;

        }

        heap_swap(&heap->queue[index], &heap->queue[smallest]);
        index = smallest;
    }
}

inline void heap_enqueue(MinHeap* heap, Node* node){
    // Se il nodo non è già presente in heap (index==-1) allora lo aggiungo come foglia e poi lo faccio risalire.
    // Se invece il nodo esiste già, gli aggiorno il costo e poi lo faccio risalire (il nuovo costo è per forza minore, quindi deve salire)
    // NOTA: sono sicuro che il costo nuovo sia inferiore del precedente perchè chiamo l'heap_enqueue solo dopo aver controllato tramite la hash table
    if (node->heap_index == -1) {
        if(heap->size >= heap->capacity){
            return;
        }

        node->heap_index = heap->size;
        heap->queue[heap->size] = node;
        heap->size++;

        heapify_up(heap, node->heap_index);
    } else {
        heapify_up(heap, node->heap_index);
    }
}

inline Node* heap_dequeue(MinHeap* heap){
    // Consumo il primo nodo della heap: gli imposto l'index a -1 per intendere che non è più in heap e poi lo ritorno
    // NOTA: per sistemare l'heap metto come root il nodo più grande (quello all'ultimo indice) in root e poi lo faccio scendere
    if (heap->size == 0){
        return NULL;
    }

    Node* min = heap->queue[0];
    min->heap_index = -1;

    heap->size--;

    if (heap->size > 0) {
        heap->queue[0] = heap->queue[heap->size];
        heap->queue[0]->heap_index = 0;
        heapify_down(heap, 0);
    }

    return min;
}

inline MinHeap* heap_create(int capacity){
    // Crea l'heap'
    MinHeap* heap = malloc(sizeof(MinHeap));
    heap->queue = malloc(sizeof(Node*) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

inline void heap_clear(MinHeap* heap){
    // Imposta semplicemente la dimensione dell'heap a 0, tanto ai successivi usi vado a sovrascrivere i puntatori che sono presenti
    heap->size = 0;
}

void heap_destroy(MinHeap* heap){
    // Vado ad eliminare completamente l'heap
    free(heap->queue);
    free(heap);
}
// END





// BEGIN DIJKSTRA
int travel_cost(HexMap* map, HashTable* ht, MinHeap* heap, int xp, int yp, int xd, int yd) {
    // Inserisco il nodo sorgente in hash table e in heap.
    // Nel while (che va avanti finchè non esaurisco i nodi nell'heap) faccio:
    //  - Prendo il primo elemento dall'heap (quindi il minimo)
    //  - Se è il nodo destinazione, ritorno il costo di raggiungimento (non mi serve esplorare ulteriormente per come è fatto Dijkstra, appena lo trovo ho già trovato il costo minore)
    //  - Controllo i 6 nodi vicini e, se il loro costo di raggiungimento è minore di quello che già hanno in hash table (oppure se vengono inseriti per la prima volta in hash table), vado ad inserirli anche in heap
    //  - Controllo tutte le rotte aeree del nodo e, se il nodo di destinazione ha costo di raggiungimento minore di quello già presente in hash table, lo inserisco in heap
    // Controllo alla fine il costo di raggiungimento del nodo di destinazione (teoricamente non dovrei mai arrivarci qui)
    // Pulisco heap e hash table


    // Controllo la validità delle coordinate (non so perchè ma is_valid non funziona)
    if ((unsigned)xp >= map->cols || (unsigned)yp >= map->rows || (unsigned)xd >= map->cols || (unsigned)yd >= map->rows) {
        return -1;
    }

    // Esco se partenza e destinazione coincidono
    if (xp == xd && yp == yd){
        return 0;
    }

    Node* new_node = insert_or_update_element(ht, xp, yp, 0);
    heap_enqueue(heap, new_node);

    const int cols = map->cols;
    const int rows = map->rows;

    static const int dir_even[6][2] = {
        {+1,  0}, { 0, -1}, {+1, -1},
        {-1,  0}, {+1, +1}, { 0, +1}
    };
    static const int dir_odd[6][2] = {
        {+1,  0}, {-1, -1}, { 0, -1},
        {-1,  0}, { 0, +1}, {-1, +1}
    };

    while (heap->size > 0) {
        Node* current = heap_dequeue(heap);

        // Se current==destinazione
        if (current->x == xd && current->y == yd) {
            int result = current->cost;
            heap_clear(heap);
            clear_hash_table(ht);
            return result;
        }

        Hexagon* hex = &map->grid[current->x][current->y];
        const int land_cost = hex->land_cost;

        if (land_cost == 0){
            continue;
        }

        // Scelgo i vicini in base alla parità
        const int (*dirs)[2] = (current->y & 1) ? dir_even : dir_odd;
        int new_cost = current->cost + land_cost;

        // Controllo i 6 vicini
        for (int i = 0; i < 6; i++) {
            int new_x = current->x + dirs[i][0];
            int new_y = current->y + dirs[i][1];

            if ((unsigned)new_x < cols && (unsigned)new_y < rows) {
                new_node = insert_or_update_element(ht, new_x, new_y, new_cost);
                if (new_node) {
                    heap_enqueue(heap, new_node);
                }
            }
        }

        // Controllo le rotte aeree
        int route_count = hex->air_route_count;
        for (int i = 0; i < route_count; i++) {
            new_node = insert_or_update_element(ht, hex->air_routes[i].dest_x, hex->air_routes[i].dest_y, current->cost + hex->air_routes[i].cost);
            if (new_node) {
                heap_enqueue(heap, new_node);
            }
        }
    }

    // Destination not reached
    heap_clear(heap);
    clear_hash_table(ht);
    return -1;
}
// END





// BEGIN CACHE FUNCTIONS
inline int calculate_cache_hash(int xp, int yp, int xd, int yd, int size){
    // Calcola l'hash dati in input le quattro coordinate e la dimensione della hash table della cache
    return ((xp * 1009 + yp * 1013 + xd * 1019 + yd * 1021) % size);
}

inline CacheHashTable* create_cache(int capacity){
    // Crea la cache con un fattore di carico di circa 1.2 (per massimizzare efficienza temporale e spaziale).
    // Inizializza tutti gli attributi della tabella hash stessa (dimensione, capacità, pool ecc...) e e anche della lista doppiamente concatenata LRU (head e tail)
    int min_size = (int)ceil(capacity / 1.2);

    int hash_length;
    if (min_size <= 53){
        hash_length = 53;
    } else if (min_size <= 97){
        hash_length = 97;
    } else if (min_size <= 193){
        hash_length = 193;
    } else if (min_size <= 389){
        hash_length = 389;
    } else if (min_size <= 769){
        hash_length = 769;
    } else if (min_size <= 1543){
        hash_length = 1543;
    } else if (min_size <= 3079){
        hash_length = 3079;
    } else{
        hash_length = 6151;
    }


    // Hash table
    CacheHashTable* cache = (CacheHashTable*)malloc(sizeof(CacheHashTable));
    cache->size = hash_length;
    cache->capacity = capacity;
    cache->element_number = 0;
    cache->buckets = calloc(hash_length, sizeof(CacheNode*));
    cache->pool = malloc(capacity * sizeof(CacheNode));
    cache->pool_index = 0;

    // Lista LRU
    cache->head = &cache->pool[cache->pool_index++];
    cache->tail = &cache->pool[cache->pool_index++];
    cache->head->lru_next = cache->tail;
    cache->tail->lru_prev = cache->head;
    cache->head->lru_prev = NULL;
    cache->tail->lru_next = NULL;

    return cache;
}

inline void lru_move_to_head(CacheHashTable* cache, CacheNode* node){
    // Prende in ingresso un nodo già presente in lista e lo inserisce in testa (quando faccio una lookup deve andare in testa)

    // Gestisce i puntatori prima di spostare il nodo
    if (node->lru_prev){
        node->lru_prev->lru_next = node->lru_next;
    }
    if (node->lru_next){
        node->lru_next->lru_prev = node->lru_prev;
    }

    // Sposta il nodo in testa
    node->lru_next = cache->head->lru_next;
    node->lru_prev = cache->head;
    cache->head->lru_next->lru_prev = node;
    cache->head->lru_next = node;
}

inline void remove_node(CacheHashTable* cache, CacheNode* node, int xp, int yp, int xd, int yd){
    // Rimuove un nodo sia dalla lista che dalla hash table

    // Rimozione dalla hash table
    int index = calculate_cache_hash(xp, yp, xd, yd, cache->size);
    CacheNode* current = cache->buckets[index];
    CacheNode* prev = NULL;

    while (current != NULL) {
        if (current == node) {
            if (prev == NULL) {
                cache->buckets[index] = current->next;
            } else {
                prev->next = current->next;
            }
            break;
        }
        prev = current;
        current = current->next;
    }

    // Rimozione dalla lista LRU
    if (node->lru_prev) node->lru_prev->lru_next = node->lru_next;
    if (node->lru_next) node->lru_next->lru_prev = node->lru_prev;

    cache->element_number--;
}

inline CacheNode* cache_lookup(CacheHashTable* cache, int xp, int yp, int xd, int yd){
    // Cerca un nodo in cache e, se lo trova, lo muove in testa nella lista LRU
    int index = calculate_cache_hash(xp, yp, xd, yd, cache->size);
    CacheNode* current = cache->buckets[index];

    while (current != NULL) {
        if (current->xp == xp && current->yp == yp && current->xd == xd && current->yd == yd) { // Se viene trovato il nodo
            lru_move_to_head(cache, current);
            return current;
        }
        current = current->next;
    }
    return NULL;    // Se non viene trovato, restituisco NULL
}

inline CacheNode* cache_insert(CacheHashTable* cache, int xp, int yp, int xd, int yd, int cost){
    // Cerca nell'hash table se il nodo esiste già (nella lookup c'è già lo spostamento in testa). Nel caso aggiorna il costo
    CacheNode* existing = cache_lookup(cache, xp, yp, xd, yd);
    if (existing != NULL) {
        existing->cost = cost;
        return existing;
    }

    // Se la cache è piena, rimuovo il nodo in coda
    if (cache->element_number >= cache->capacity) {
        CacheNode* lru_node = cache->tail->lru_prev;
        if (lru_node != cache->head) {
            remove_node(cache, lru_node, lru_node->xp, lru_node->yp, lru_node->xd, lru_node->yd);
        }
    }

    // Arrivo qua solamente se il nodo non è già presente in cache; creo il nodo
    CacheNode* new_node = &cache->pool[cache->pool_index++];
    new_node->xp = xp;
    new_node->yp = yp;
    new_node->xd = xd;
    new_node->yd = yd;
    new_node->cost = cost;

    // Lo aggiungo in hash table
    int index = calculate_cache_hash(xp, yp, xd, yd, cache->size);
    new_node->next = cache->buckets[index];
    cache->buckets[index] = new_node;

    // Lo aggiungo in testa alla coda
    new_node->lru_next = cache->head->lru_next;
    new_node->lru_prev = cache->head;
    cache->head->lru_next->lru_prev = new_node;
    cache->head->lru_next = new_node;

    cache->element_number++;
    return new_node;
}

inline void cache_remove(CacheHashTable* cache, int xp, int yp, int xd, int yd){
    // Trova un nodo in cache e lo rimuove sia dalla hash table che dalla lista LRU
    int index = calculate_cache_hash(xp, yp, xd, yd, cache->size);
    CacheNode* current = cache->buckets[index];

    while (current != NULL) {
        if (current->xp == xp && current->yp == yp && current->xd == xd && current->yd == yd) {
            remove_node(cache, current, xp, yp, xd, yd);    // Rimuove sia dalla hash table che dalla lista LRU
            return;
        }
        current = current->next;
    }
}

void clear_cache(CacheHashTable* cache){
    // Pulisce tutta la cache ma ne mantiene la struttura (per non dover reinizializzare ogni volta la hash table)
    // NOTA: non faccio la free sugli elementi perchè sono tutti nella pool: verranno sovrascritti dopo
    memset(cache->buckets, 0, cache->size * sizeof(CacheNode*));
    cache->pool_index = 0;
    cache->element_number = 0;

    // Resetta head e tail
    cache->head = &cache->pool[cache->pool_index++];
    cache->tail = &cache->pool[cache->pool_index++];
    cache->head->lru_next = cache->tail;
    cache->tail->lru_prev = cache->head;
    cache->head->lru_prev = NULL;
    cache->tail->lru_next = NULL;
}

void destroy_cache(CacheHashTable** cache){
    // Elimino completamente la struttura e ripulisco la pool
    if (*cache) {
        free((*cache)->buckets);
        free((*cache)->pool);
        free(*cache);
        *cache = NULL;
    }
}
// END





// BEGIN MAIN
int main(){


    char testo[17];
    int inp_uno, inp_due, inp_tre, inp_quattro;

    HexMap map;
    HashTable* ht = NULL;
    MinHeap* heap = NULL;
    CacheHashTable* cache = NULL;

    int already_initialized=0;
    CacheNode* cached;
    int cost;

    while (true){
        int tmp_input = scanf("%s %d %d %d %d",testo, &inp_uno, &inp_due, &inp_tre, &inp_quattro);
        if (tmp_input==-1){
            break;
        }

        if (strcmp(testo, "init")==0){
            if (already_initialized==1){
                destroy_map(&map);
            }
            init_map(&map, inp_uno, inp_due);
            already_initialized=1;

            if (ht!=NULL){
                destroy_hash_table(&ht);
            }
            ht = create_hash_table(inp_uno * inp_due);

            if (heap!=NULL){
                heap_destroy(heap);
            }
            heap = heap_create(inp_uno * inp_due);

            if (cache!=NULL){
                destroy_cache(&cache);
            }
            cache = create_cache(CACHE_SIZE);
        }

        if (strcmp(testo, "print")==0){
            if (already_initialized==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            print_map(&map);
        }

        if (strcmp(testo, "change_cost")==0){
            if (already_initialized==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            if(change_cost(&map, inp_uno, inp_due, inp_tre, inp_quattro)){
                clear_cache(cache);
            }
        }

        if (strcmp(testo, "toggle_air_route")==0){
            if (already_initialized==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            if(toggle_air_route(&map, inp_uno, inp_due, inp_tre, inp_quattro)){
                clear_cache(cache);
            }
        }

        if (strcmp(testo, "travel_cost")==0){
            if (already_initialized==0){
                fprintf(stdout, "-1\n");
                continue;
            }
            cached=cache_lookup(cache, inp_uno, inp_due, inp_tre, inp_quattro);

            if(cached!=NULL){
                cost = cached->cost;
            } else {
                cost = travel_cost(&map, ht, heap, inp_uno, inp_due, inp_tre, inp_quattro);
                cache_insert(cache, inp_uno, inp_due, inp_tre, inp_quattro, cost);
            }

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

    // Cleanup
    if (already_initialized==1) {
        destroy_map(&map);
    }
    if (ht!=NULL) {
        destroy_hash_table(&ht);
    }
    if (heap!=NULL) {
        heap_destroy(heap);
    }
    if (cache!=NULL) {
        destroy_cache(&cache);
    }

    return 0;
}
// END