942 lines
28 KiB
C
942 lines
28 KiB
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
|
|
|
|
|
|
|
|
|
|
|
|
// 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, ¶m1, ¶m2, ¶m3, ¶m4);
|
|
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;
|
|
}
|