MovHex/FINALE - main.c

#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





// 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 AirRouteNode {
    int start_x, start_y;   // Coordinate di partenza
    AirRoute routes[5];     // Array di rotte aeree
    int route_count;        // Numero di rotte aeree
    struct AirRouteNode* next;  // Puntatore al prossimo nodo nella hash table (chaining)
} AirRouteNode;

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

typedef struct {    // Mappa di esagoni - UPDATED: no more Hexagon structure
    int rows, cols; // Numero di righe e colonne
    int* grid_data; // Puntatore al blocco in RAM contenente tutti i costi degli esagoni
    int** grid; // Array di puntatori alle colonne
    AirRouteTable* air_routes; // Puntatore alla hash table contenente gli air routes
} 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 STRUCTURES





// BEGIN AIR ROUTE TABLE FUNCTIONS
inline int calculate_air_route_hash(int x, int y, int size) {
    // Calcola la hash nella hash table delle rotte aeree
    return ((x * 73 + y * 31) & (size - 1));
}

inline AirRouteTable* create_air_route_table(int capacity) {
    // Allco la tabella di hash e inizializzo gli attributi
    AirRouteTable* table = (AirRouteTable*) malloc(sizeof(AirRouteTable));
    table->size = AIR_ROUTE_HASH_SIZE;
    table->capacity = capacity;
    table->buckets = (AirRouteNode**) calloc(AIR_ROUTE_HASH_SIZE, sizeof(AirRouteNode*));
    table->pool = (AirRouteNode*) malloc(capacity * sizeof(AirRouteNode));
    table->pool_index = 0;
    return table;
}

inline void clear_air_route_table(AirRouteTable* table) {
    // 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(table->buckets, 0, table->size * sizeof(AirRouteNode*));
    table->pool_index = 0;
}

void destroy_air_route_table(AirRouteTable** table) {
    // Elimina completamente una hash table delle rotte aeree (anche il suo pool di memoria contigua)
    if (*table) {
        free((*table)->buckets);
        free((*table)->pool);
        free(*table);
        *table = NULL;
    }
}

inline AirRouteNode* find_air_route_node(AirRouteTable* table, int x, int y) {
    // Trova il nodo contenente le rotte aeree date le coordinate dell'esagono di partenza
    int index = calculate_air_route_hash(x, y, table->size);
    AirRouteNode* current = table->buckets[index];

    while (current != NULL) {
        if (current->start_x == x && current->start_y == y) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

inline void remove_air_route_node_if_empty(AirRouteTable* table, int x, int y) {
    // Quando un nodo di rotte aeree ha 0 rotte aeree nell'array, vado ad eliminare il nodo dalla hash table
    int index = calculate_air_route_hash(x, y, table->size);
    AirRouteNode* current = table->buckets[index];
    AirRouteNode* prev = NULL;

    while (current != NULL) {
        if (current->start_x == x && current->start_y == y) {
            if (current->route_count == 0) {
                if (prev == NULL) {
                    table->buckets[index] = current->next;
                } else {
                    prev->next = current->next;
                }
            }
            return;
        }
        prev = current;
        current = current->next;
    }
}

bool toggle_air_route_in_node(AirRouteTable* table, HexMap* map, int start_x, int start_y, int dest_x, int dest_y) {
    // Inserisce o rimuove una rotta aerea da un esagono
    // NOTA: Ritorna sempre true se va tutto bene (ritorna false invece se ci sono problemi)
    AirRouteNode* route_node = find_air_route_node(table, start_x, start_y);

    // Controlla se la rotta aerea è già presente e, in caso, la rimuove
    if (route_node != NULL) {
        for (int i = 0; i < route_node->route_count; i++){
            if ((route_node->routes[i].dest_x == dest_x) && (route_node->routes[i].dest_y == dest_y)){
                // Rimuove la rotta
                for (int j = i; j < route_node->route_count - 1; j++){
                    route_node->routes[j] = route_node->routes[j+1];
                }
                route_node->route_count--;

                // Chiamo la funzione per controllare che ci siano ancora rotte aeree (in caso contrario viene eliminato il nodo)
                remove_air_route_node_if_empty(table, start_x, start_y);

                return true;
            }
        }

        // Controlla se posso aggiungere rotte aeree
        if (route_node->route_count >= 5){
            return false;
        }
    } else {
        // Creo il nodo delle rotte aeree (se entro qua è perchè il nodo non esiste già)
        if (table->pool_index >= table->capacity) {
            return false;
        }

        int index = calculate_air_route_hash(start_x, start_y, table->size);
        route_node = &table->pool[table->pool_index++];
        route_node->start_x = start_x;
        route_node->start_y = start_y;
        route_node->route_count = 0;
        route_node->next = table->buckets[index];
        table->buckets[index] = route_node;
    }

    // Aggiorno il nodo delle rotte aeree (se sono qua è perchè esiste già il nodo)
    int starting_hex_cost = map->grid[start_x][start_y];
    int cost;
    if (route_node->route_count == 0){
        cost = (int) floor(starting_hex_cost / (route_node->route_count + 1));
    } else {
        int sum = 0;
        for (int i = 0; i < route_node->route_count; i++){
            sum += route_node->routes[i].cost;
        }
        cost = (int) floor((sum + starting_hex_cost) / (route_node->route_count + 1));
    }

    route_node->routes[route_node->route_count] = (AirRoute) {dest_x, dest_y, cost};
    route_node->route_count++;

    return true;
}
// END AIR ROUTE TABLE FUNCTIONS





// 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 i costi degli esagoni in blocco (per minimizzare cache miss)
    map->grid_data = (int*) calloc(cols * rows, sizeof(int));

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

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

    // Inizializza i costi di tutti gli esagoni a 1
    for (int i = 0; i < cols * rows; i++) {
        map->grid_data[i] = 1;
    }

    // Inizializza la hash map delle rotte aeree
    map->air_routes = create_air_route_table(cols * rows / 10); // Verranno aggiunte massimo un decimo di nodi di rotte aeree

    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
    destroy_air_route_table(&map->air_routes); // Dealloca la hash table di rotte aeree
    map->grid = NULL;
    map->grid_data = NULL;
    map->air_routes = 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]);
        }
        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;
    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);
                int* hex_cost = &map->grid[i][j];
                *hex_cost = *hex_cost + (int)floor(cost * coeff);

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

                // Aggiorna le rotte aeree (NON TOCCARE)
                AirRouteNode* route_node = find_air_route_node(map->air_routes, i, j);
                if (route_node != NULL) {
                    for (int counter = 0; counter < route_node->route_count; counter++){
                        int cost_old_air_route = 0;
                        for (int n = 0; n < counter; n++){
                            cost_old_air_route += route_node->routes[n].cost;
                        }
                        route_node->routes[counter].cost = (int)((cost_old_air_route + *hex_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;
    }

    bool success = toggle_air_route_in_node(map->air_routes, map, x_1, y_1, x_2, y_2);

    if (success) {
        fputs("OK\n", stdout);
        return true;
    } else {
        fputs("KO\n", stdout);
        return false;
    }
}
// END MAP FUNCTIONS





// 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 - 1));
}

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 hash_length=65536;

    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 HASH TABLE FUNCTIONS





// BEGIN HEAP FUNCTIONS
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
    Node** queue = heap->queue;
    int parent;
    int current_cost;
    int parent_cost;

    while (index > 0) {
        parent = (index - 1) >> 1;

        current_cost = queue[index]->cost;
        parent_cost = queue[parent]->cost;

        if (current_cost >= parent_cost) {
            break;
        }

        // Swappa i nodi
        Node* temp = queue[index];
        queue[index] = queue[parent];
        queue[parent] = temp;

        // Aggiorna gli indici
        queue[index]->heap_index = index;
        queue[parent]->heap_index = 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;
    const int size = heap->size;
    Node** queue = heap->queue;
    int current_cost;

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

        current_cost = queue[smallest]->cost;

        // Figlio sinistro
        if (left < size) {
            int left_cost = queue[left]->cost;
            if (left_cost < current_cost) {
                smallest = left;
                current_cost = left_cost;
            }
        }

        // Figlio destro
        if (right < size) {
            int right_cost = queue[right]->cost;
            if (right_cost < current_cost) {
                smallest = right;
            }
        }

        if (smallest == index) {
            break;
        }

        // Swap dei nodi
        Node* temp = queue[index];
        queue[index] = queue[smallest];
        queue[smallest] = temp;

        // Aggiorna gli indici
        queue[index]->heap_index = index;
        queue[smallest]->heap_index = 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 HEAP FUNCTIONS





// 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
    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;
        }

        const int land_cost = map->grid[current->x][current->y];

        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
        AirRouteNode* route_node = find_air_route_node(map->air_routes, current->x, current->y);
        if (route_node != NULL) {
            for (int i = 0; i < route_node->route_count; i++) {
                new_node = insert_or_update_element(ht,route_node->routes[i].dest_x, route_node->routes[i].dest_y, current->cost + route_node->routes[i].cost);
                if (new_node) {
                    heap_enqueue(heap, new_node);
                }
            }
        }
    }

    // Destinazione non raggiunta
    heap_clear(heap);
    clear_hash_table(ht);
    return -1;
}
// END DIJKSTRA





// 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 * 19 + yp * 13 + xd * 27 + yd * 121) & (size-1));
}

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 hash_length = CACHE_SIZE;

    // 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 CACHE FUNCTIONS





// 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