1175 lines
30 KiB
Plaintext
1175 lines
30 KiB
Plaintext
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <stdbool.h>
|
|
#include <math.h>
|
|
|
|
#define CACHE_SIZE 1024
|
|
#define CACHE_MAX_OCCUPIED 4096
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN INIZIALIZZAZIONE DELLA MAPPA
|
|
|
|
|
|
// BEGIN STRUTTURE
|
|
// Struttura per rappresentare una rotta aerea
|
|
typedef struct {
|
|
int dest_x, dest_y; // Coordinate destinazione
|
|
int cost; // Costo della rotta
|
|
} AirRoute;
|
|
|
|
|
|
// Struttura per rappresentare un esagono
|
|
typedef struct {
|
|
int land_cost; // Costo di uscita via terra (0 = bloccato)
|
|
AirRoute air_routes[5]; // Rotte aeree uscenti
|
|
int air_route_count; // Numero di rotte aeree
|
|
} Hexagon;
|
|
|
|
|
|
// Struttura per la mappa
|
|
typedef struct {
|
|
int rows, cols; // Dimensioni della matrice
|
|
Hexagon** grid; // Matrice
|
|
} HexMap;
|
|
|
|
|
|
// Struttura per la coda in change_cost
|
|
typedef struct {
|
|
int x;
|
|
int y;
|
|
int dist;
|
|
} QueueNode;
|
|
|
|
|
|
// END
|
|
|
|
|
|
void init_map(HexMap* map, int cols, int rows){
|
|
// FUNZIONAMENTO:
|
|
// Gli passo una struttura HexMap e gli inserisco il numero di colonne e righe.
|
|
// La matrice è formata da un "array" di puntatori alle teste delle colonne. Per farlo alloco dinamicamente lo spazio per contenere tutti
|
|
// i puntatori agli inizi delle colonne.
|
|
// Vado poi a scorrere ogni elemento della matrice ed a inizializarli con i valori land_cost=1 e air_route_count=0.
|
|
|
|
map -> rows = rows; // Inserisce le dimensioni negli attributi dell'oggetto'
|
|
map -> cols = cols;
|
|
|
|
// Genero la matrice di esagoni
|
|
map -> grid = (Hexagon**) malloc(cols * sizeof(Hexagon*)); // Alloco lo spazio del primo livello della matrice
|
|
|
|
for (int i=0; i<map -> cols; i++){
|
|
map -> grid[i] = (Hexagon*) malloc(rows * sizeof(Hexagon)); // Alloco lo spazio del secondo livello della matrice
|
|
|
|
for (int j=0; j<map -> rows; j++){
|
|
map -> grid[i][j].land_cost=1; // Inizializzo i valori degli esagoni
|
|
map->grid[i][j].air_route_count = 0;
|
|
}
|
|
}
|
|
fprintf(stdout,"OK\n");
|
|
fflush(stdout);
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void destroy_map(HexMap* map){
|
|
// Va a deallocare la mappa
|
|
|
|
|
|
for (int i = 0; i < map -> cols && map -> grid[i]; i++) {
|
|
free(map->grid[i]);
|
|
}
|
|
free(map->grid);
|
|
map->grid = NULL;
|
|
map->rows = map->cols = 0;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
void print_map(HexMap* map){
|
|
printf("\n");
|
|
for (int i=map->rows-1; i>=0; i--){ // Per ogni riga (se pari la offsetta per ottenere forma esagonale)
|
|
if(i%2==1) printf(" ");
|
|
for (int j=0; j<map -> cols; j++){ // Per ogni colonna
|
|
printf("%d ",map -> grid[j][i].land_cost); // Stampa il costo dell'esagono'
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
bool is_valid(HexMap* map, int x, int y){
|
|
if(x<0 || x>map->cols-1 || y<0 || y>map->rows-1){
|
|
return false;
|
|
} else {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int hexagons_distance(int x_1, int y_1, int x_2, int y_2){
|
|
// Viene usato per calcolare la distanza tra due esagoni (tramite coordinate cubiche)
|
|
|
|
|
|
// Converte (x, y) in coordinate cubiche (cx, cy, cz)
|
|
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))); // Ritorno la distanza tra i due esagoni
|
|
}
|
|
|
|
|
|
|
|
|
|
bool change_cost(HexMap* map, int x, int y, int cost, int radius){
|
|
// Controllo che l'esagono sia valido
|
|
if(!is_valid(map, x, y) || radius<=0 || cost < -10 || cost > 10){
|
|
fputs("KO\n", stdout);
|
|
fflush(stdout);
|
|
return false;
|
|
}
|
|
|
|
|
|
// Per ogni esagono in griglia, controllo se dista meno del raggio e, nel caso, gli calbio il costo
|
|
int dist;
|
|
int cost_old_air_route;
|
|
float coeff;
|
|
for(int i=0; i<map->cols; i++){
|
|
for (int j=0; j<map->rows; j++){
|
|
dist=hexagons_distance(x,y,i,j);
|
|
if (dist<radius){
|
|
if(((float)(radius - dist) / (float)radius)>0){ // Calcolo del coefficiente (fidati)
|
|
coeff=((float)(radius - dist) / (float)radius);
|
|
} else {
|
|
coeff=0;
|
|
}
|
|
|
|
map->grid[i][j].land_cost=map->grid[i][j].land_cost+(int)floor(cost * coeff); // Aggiorna il costo
|
|
|
|
|
|
if (map -> grid[i][j].land_cost>100){ // Faccio il controllo sul costo (può essere compreso tra 0 e 100)
|
|
map -> grid[i][j].land_cost=100;
|
|
}
|
|
if (map -> grid[i][j].land_cost<0){
|
|
map -> grid[i][j].land_cost=0;
|
|
}
|
|
|
|
|
|
// Aggiorno i costi delle rotte aeree
|
|
for (int counter=0; counter<map -> grid[i][j].air_route_count;counter++){
|
|
cost_old_air_route=0;
|
|
for (int n=0; n<counter;n++){
|
|
cost_old_air_route=cost_old_air_route + map->grid[i][j].air_routes[n].cost;
|
|
}
|
|
map->grid[i][j].air_routes[counter].cost=(int)((cost_old_air_route+map->grid[i][j].land_cost)/(counter+1));
|
|
}
|
|
|
|
}
|
|
}
|
|
}
|
|
|
|
fputs("OK\n", stdout);
|
|
fflush(stdout);
|
|
return true;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
bool toggle_air_route(HexMap* map, int x_1, int y_1, int x_2, int y_2){
|
|
// FUNZIONAMENTO:
|
|
// Analizzo l'array delle rotte aeree dell'esagono di partenza (x_1, y_1) e, se la rotta è già presente la elimino (rimuovo dall'array); se invece non è presente
|
|
// la aggiungo (inserisco nell'array)
|
|
|
|
// Controllo che gli esagoni siano validi
|
|
if(!is_valid(map, x_1,y_1) || !is_valid(map, x_2,y_2)){
|
|
fputs("KO\n", stdout);
|
|
fflush(stdout);
|
|
return false;
|
|
}
|
|
|
|
|
|
Hexagon* StartingHexagon = &(map -> grid[x_1][y_1]); // Memorizzo il puntatore all'esagono di partenza
|
|
|
|
|
|
// Controllo di non avere più di 5 rotte aeree (uso il 4 per come è costruito il codice)
|
|
if (StartingHexagon -> air_route_count>4){
|
|
fputs("KO\n", stdout);
|
|
fflush(stdout);
|
|
return false;
|
|
}
|
|
|
|
|
|
for (int i=0; i< StartingHexagon -> air_route_count; i++){ // Per ogni elemento all'interno della lista di rotte aeree dell'esagono di partenza
|
|
if ((StartingHexagon -> air_routes[i].dest_x == x_2)&&(StartingHexagon -> air_routes[i].dest_y == y_2)){ // Se la rotta è già presente
|
|
for (int j=i; j<StartingHexagon -> air_route_count; j++){ // Lo elimino shiftando gli elementi successivi a sx (così da non avere buchi nell'array)
|
|
StartingHexagon -> air_routes[j]=StartingHexagon -> air_routes[j+1];
|
|
}
|
|
StartingHexagon -> air_route_count = StartingHexagon -> air_route_count - 1; // Diminuisco il contatore di rotte aeree
|
|
fputs("OK\n", stdout);
|
|
fflush(stdout);
|
|
return true;
|
|
}
|
|
}
|
|
|
|
|
|
// Se sono arrivato qua, significa che la rotta non era presente nell'array e quindi la aggiungo
|
|
// Calcolo il costo della rotta aerea
|
|
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}; // Aggiungo la tratta all'array
|
|
StartingHexagon -> air_route_count = StartingHexagon -> air_route_count + 1; // Aumento il contatore del numero di tratte
|
|
fputs("OK\n", stdout);
|
|
fflush(stdout);
|
|
return true;
|
|
|
|
|
|
|
|
// DEBUGGING
|
|
/*
|
|
* printf("Tratta aggiunta\n");
|
|
* printf("La lista di tratte aeree partendo da %d %d:\n", x_1, y_1);
|
|
* for (int i=0; i< StartingHexagon -> air_route_count; i++){
|
|
* printf("x:%d y:%d costo:%d\n", StartingHexagon -> air_routes[i].dest_x, StartingHexagon -> air_routes[i].dest_y, StartingHexagon -> air_routes[i].cost);
|
|
}
|
|
printf("\n\n");
|
|
*/
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN MIN-HEAP
|
|
|
|
|
|
// BEGIN STRUTTURE
|
|
typedef struct Node Node;
|
|
|
|
struct Node {
|
|
int x,y;
|
|
int cost;
|
|
int heap_index;
|
|
Node* next;
|
|
};
|
|
|
|
|
|
typedef struct MinHeap {
|
|
int size;
|
|
int capacity;
|
|
Node** queue;
|
|
} MinHeap;
|
|
|
|
|
|
// END
|
|
|
|
|
|
// BEGIN BASIC-FUNCTIONS
|
|
|
|
|
|
MinHeap* heap_create(int capacity) {
|
|
// Crea un heap e gli inizializza gli attributi
|
|
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
|
|
heap->queue = (Node**)malloc(sizeof(Node*) * capacity);
|
|
heap->size = 0;
|
|
heap->capacity = capacity;
|
|
return heap;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void heap_clear(MinHeap* heap) {
|
|
// Dealloca un heap
|
|
if (heap) {
|
|
heap->size=0;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void heap_destroy(MinHeap* heap) {
|
|
// Dealloca un heap
|
|
if (heap) {
|
|
free(heap->queue);
|
|
free(heap);
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void heap_swap(Node** a, Node** b) {
|
|
// Va a swappare due nodi dell'heap (aggiorna anche il loro heap_index)
|
|
// Uso un doppio puntatore perchè non devo solamente scambiare i contenuti dei nodi, ma anche i loro puntatori nella queue
|
|
Node* temp = *a;
|
|
*a = *b;
|
|
*b = temp;
|
|
|
|
int tmp_index = (*a)->heap_index;
|
|
(*a)->heap_index = (*b)->heap_index;
|
|
(*b)->heap_index = tmp_index;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void heapify_up(MinHeap* heap, int index) {
|
|
// Vado sempre ad inserire nelle foglie, questo serve per far "salire" il nodo inserito fino alla posizione corretta
|
|
int parent;
|
|
while (index > 0) {
|
|
parent = (index - 1) / 2;
|
|
if (heap->queue[index]->cost < heap->queue[parent]->cost) {
|
|
heap_swap(&heap->queue[index], &heap->queue[parent]);
|
|
index = parent;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void heapify_down(MinHeap* heap, int index) {
|
|
// Quando vado a rimuovere la root (quando consumo un nodo per Dijkstra), metto in root il nodo foglia più grande: devo farlo scendere fino alla sua corretta posizione
|
|
int left, right, smallest;
|
|
|
|
while (1) {
|
|
left = 2 * index + 1;
|
|
right = 2 * index + 2;
|
|
smallest = index;
|
|
|
|
if (left < heap->size && heap->queue[left]->cost < heap->queue[smallest]->cost) {
|
|
smallest = left;
|
|
}
|
|
|
|
if (right < heap->size && heap->queue[right]->cost < heap->queue[smallest]->cost) {
|
|
smallest = right;
|
|
}
|
|
|
|
if (smallest != index) {
|
|
heap_swap(&heap->queue[index], &heap->queue[smallest]);
|
|
index = smallest;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
// BEGIN DIJKSTRA-FUNCTIONS
|
|
|
|
|
|
void heap_enqueue(MinHeap* heap, Node* node) {
|
|
// NOTA: ogni nodo è già presente in hash table.
|
|
// Passo alla funzione un nodo, se ha heap_index==-1 significa che al momento non è in heap, quindi lo aggiungo come foglia e faccio heapify up
|
|
// Se invece heap_index!=-1, qignifica che il nodo è già presente in heap, quindi devo solamente riordinare l'heap (il costo è già stato aggiornato dalla hash table, qua riordino e basta)
|
|
|
|
if (node->heap_index == -1) {
|
|
// Nodo non presente, lo aggiungo
|
|
if (heap->size >= heap->capacity) {
|
|
fprintf(stderr, "Heap overflow!\n");
|
|
exit(1);
|
|
}
|
|
|
|
node->heap_index = heap->size;
|
|
heap->queue[heap->size] = node;
|
|
heap->size++;
|
|
|
|
heapify_up(heap, node->heap_index);
|
|
} else {
|
|
// Nodo già presente, riordino l'heap
|
|
heapify_up(heap, node->heap_index);
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
Node* heap_dequeue(MinHeap* heap) {
|
|
// Voglio prendere il primo nodo della queue e consumarlo.
|
|
// Passo a questa funzione l'heap e lei prende il primo nodo della coda e gli imposta index=-1 (non posso deallocarlo perchè mi serve che sopravviva in hash table).
|
|
// Una volta riorganizzato l'heap (metto il nodo maggiore in testa e poi lo faccio scendere), restituisco il nodo da consumare
|
|
|
|
if (heap->size == 0) {
|
|
return NULL;
|
|
}
|
|
|
|
Node* min = heap->queue[0];
|
|
min->heap_index = -1; // segna come rimosso
|
|
|
|
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; // restituisci il nodo minimo rimosso
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN HASH-TABLE
|
|
|
|
|
|
// BEGIN STRUTTURE
|
|
|
|
|
|
typedef struct{
|
|
int size;
|
|
Node** buckets;
|
|
} HashTable;
|
|
|
|
|
|
// END
|
|
|
|
|
|
// BEGIN BASIC-FUNCTIONS
|
|
|
|
|
|
HashTable* create_hash_table(int size){
|
|
// Riceve la dimensione della tabella esagonale e crea una hash table di dimensioni adeguate
|
|
|
|
|
|
// Trovo la dimensione minima che deve avere la tabella (fattore di carico massimo 1.5)
|
|
int min_size = (int)ceil(size / 1.5);
|
|
|
|
// Numeri primi buoni per dimensioni di hash table
|
|
static const int primes[] = {
|
|
7, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
|
|
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
|
|
6291469, 12582917, 25165843, 50331653, 100663319, 201326611
|
|
};
|
|
|
|
// Trova il primo numero primo >= min_size che sarà la dimensione della tabella hash
|
|
int hash_length=0;
|
|
for (size_t i = 0; i < 23; i++) {
|
|
if (primes[i] >= min_size) {
|
|
hash_length = primes[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
// Allco la struttura principale della hash table e inizializzo i suoi attributi
|
|
HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
|
|
ht->size = hash_length;
|
|
|
|
// Alloco l'array di bucket (li inizializzo tutti a NULL)
|
|
ht->buckets = (Node**) malloc(hash_length * sizeof(Node*));
|
|
for (int i = 0; i < hash_length; i++) {
|
|
ht->buckets[i] = NULL;
|
|
}
|
|
|
|
return ht;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void clear_hash_table(HashTable* ht) {
|
|
// Ripulisce la tabella dai Node per poterla riutilizzare
|
|
|
|
Node* current;
|
|
Node* next;
|
|
// Scorri tutti i bucket
|
|
for (int i = 0; i < ht->size; i++) {
|
|
current = ht->buckets[i];
|
|
|
|
// Libera tutti i nodi nella catena
|
|
while (current != NULL) {
|
|
next = current->next;
|
|
free(current);
|
|
current = next;
|
|
}
|
|
|
|
// Reimposta il bucket a NULL
|
|
ht->buckets[i] = NULL;
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void destroy_hash_table(HashTable** ht) {
|
|
// Distrugge completamente l'hash table
|
|
|
|
// Ripulisce tutti i nodi nella tabella
|
|
clear_hash_table(*ht);
|
|
|
|
// Pulisce l'array dei bucket, la struttura principale e infine imposta a null il puntatore alla hash table
|
|
free((*ht)->buckets);
|
|
free(*ht);
|
|
*ht = NULL;
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
// BEGIN DIJKSTRA-FUNCTIONS
|
|
|
|
|
|
void print_hash_table (HashTable* ht){
|
|
|
|
Node* current;
|
|
for (int i=0; i<(ht->size); i++){
|
|
current = ht->buckets[i];
|
|
printf("Index[%d]: ", i);
|
|
|
|
while (current != NULL) {
|
|
printf("[x:%d y:%d dist:%d]-> ", current -> x, current -> y, current -> cost);
|
|
current = current->next;
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int calculate_hash(int x, int y, int size){
|
|
// Hash function
|
|
|
|
|
|
const int p1 = 7919; // Primo grande
|
|
const int p2 = 1237; // Altro primo grande
|
|
|
|
return ((x * p1) ^ (y * p2)) % size;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
Node* insert_or_update_element (HashTable* ht, int x, int y, int cost){
|
|
// Cerca un nodo nella hash table, se non lo trova lo aggiunge, mentre se lo trova aggiorna (se necessario) il costo
|
|
// Ritorna il nodo quando viene aggiunto/aggiornato, NULL altrimenti
|
|
|
|
|
|
int index = calculate_hash(x, y, ht -> size); // Calcolo l'hash
|
|
|
|
Node* current = ht -> buckets[index]; //Scorro la lista fino a quando trovo il nodo o la finisco
|
|
while (current != NULL && !(current->x == x && current->y == y)){
|
|
current = current -> next;
|
|
}
|
|
|
|
if (current == NULL){ // Se non c'è il nodo, lo inserisco
|
|
Node* hn = malloc(sizeof(Node)); // Crea il nodo con i parametri che sono stati passati alla funzione (l'attributo next lo definisco nell'inserimento in testa)
|
|
hn->x = x;
|
|
hn->y = y;
|
|
hn->cost = cost;
|
|
hn->heap_index=-1;
|
|
|
|
hn->next = ht->buckets[index]; // Inserisco in testa alla lista
|
|
ht->buckets[index] = hn;
|
|
return hn;
|
|
}
|
|
|
|
|
|
if (current->cost > cost){ // Se c'è già, se posso lo aggiorno
|
|
current->cost = cost;
|
|
return current;
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int search_element (HashTable* ht, int x, int y){
|
|
// Cerca un nodo dalla hash table e ne restituisce il costo
|
|
|
|
|
|
int index = calculate_hash(x, y, ht -> size); // Calcolo l'hash
|
|
|
|
Node* current = ht->buckets[index]; //Scorro la lista fino a quando trovo il nodo o la finisco
|
|
while (current != NULL && !(current->x == x && current->y == y)){
|
|
current = current -> next;
|
|
}
|
|
|
|
if(current==NULL){ // Se il nodo non è presente, restituisce -1
|
|
return -1;
|
|
}
|
|
|
|
return current->cost;
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN CACHE
|
|
|
|
|
|
// BEGIN STRUTTURE
|
|
|
|
typedef struct CACHE_HashNode CACHE_HashNode;
|
|
|
|
struct CACHE_HashNode{
|
|
int xp,yp; // Coordinate di partenza
|
|
int xd,yd; // Coordinate di arrivo
|
|
int travel_cost; // Costo da xp,yp a xd,yd
|
|
int LRU; // Valore per la gestione del caching
|
|
CACHE_HashNode* next; // Puntatore al prossimo elemento
|
|
};
|
|
|
|
|
|
typedef struct{
|
|
int size; // Dimensione della hash table (numero di bucket)
|
|
int occupied; // Quantità di nodi inseriti in cache
|
|
CACHE_HashNode** buckets; // Puntatore alla testa dei bucket
|
|
} CACHE_HashTable;
|
|
|
|
|
|
// END
|
|
|
|
|
|
CACHE_HashTable* create_cache(int size){
|
|
// Riceve la dimensione con cui creare la tabella
|
|
|
|
// Numeri primi buoni per dimensioni di hash table
|
|
static const int primes[] = {
|
|
7, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
|
|
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
|
|
6291469, 12582917, 25165843, 50331653, 100663319, 201326611
|
|
};
|
|
|
|
|
|
// Trova il primo numero primo >= min_size che sarà la dimensione della tabella hash
|
|
int hash_length=0;
|
|
for (size_t i = 0; i < 23; i++) {
|
|
if (primes[i] >= size) {
|
|
hash_length = primes[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
|
|
// Allco la struttura principale della hash table e inizializzo i suoi attributi
|
|
CACHE_HashTable* ht = (CACHE_HashTable*)malloc(sizeof(CACHE_HashTable));
|
|
ht->size = hash_length;
|
|
ht->occupied=0;
|
|
|
|
|
|
// Alloco l'array di bucket (li inizializzo tutti a NULL)
|
|
ht->buckets = (CACHE_HashNode**) malloc(hash_length * sizeof(CACHE_HashNode*));
|
|
for (int i = 0; i < hash_length; i++) {
|
|
ht->buckets[i] = NULL;
|
|
}
|
|
|
|
|
|
return ht;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void clear_cache(CACHE_HashTable* ht) {
|
|
// Ripulisce la tabella dai CACHE_HashNode per poterla riutilizzare
|
|
|
|
|
|
// Scorri tutti i bucket
|
|
for (int i = 0; i < ht->size; i++) {
|
|
CACHE_HashNode* current = ht->buckets[i];
|
|
|
|
// Libera tutti i nodi nella catena
|
|
while (current != NULL) {
|
|
CACHE_HashNode* next = current->next;
|
|
free(current);
|
|
current = next;
|
|
}
|
|
|
|
// Reimposta il bucket a NULL
|
|
ht->buckets[i] = NULL;
|
|
}
|
|
|
|
// Imposta il numero di nodi presenti a 0
|
|
ht->occupied=0;
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void destroy_cache(CACHE_HashTable** ht) {
|
|
// Distrugge completamente l'hash table
|
|
|
|
// Ripulisce tutti i nodi nella tabella
|
|
clear_cache(*ht);
|
|
|
|
// Pulisce l'array dei bucket, la struttura principale e infine imposta a null il puntatore alla hash table
|
|
free((*ht)->buckets);
|
|
free(*ht);
|
|
*ht = NULL;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void print_cache (CACHE_HashTable* ht){
|
|
|
|
for (int i=0; i<(ht->size); i++){
|
|
CACHE_HashNode* current = ht->buckets[i];
|
|
printf("Index[%d]: ", i);
|
|
|
|
while (current != NULL) {
|
|
printf("[xp:%d yp:%d xd:%d yd:%d cost:%d LRU:%d]-> ", current->xp, current->yp, current->xd, current->yd, current->travel_cost, current->LRU);
|
|
current = current->next;
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int calculate_hash_cache(int xp, int yp, int xd, int yd, int size) {
|
|
// Hash function con 4 input
|
|
|
|
const int p1 = 7919; // primo per xp
|
|
const int p2 = 1237; // primo per yp
|
|
const int p3 = 1047; // primo per xd
|
|
const int p4 = 1548; // primo per yd
|
|
|
|
|
|
return ((xp * p1) ^ (yp * p2) ^ (xd * p3) ^ (yd * p4)) % size;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void delete_element_cache(CACHE_HashTable* ht){
|
|
// Cerco il nodo con LRU minore in tutta la cache e lo elimino
|
|
|
|
CACHE_HashNode* prev=NULL;
|
|
|
|
CACHE_HashNode* min=NULL;
|
|
CACHE_HashNode* min_prev=NULL;
|
|
int min_LRU=1000;
|
|
int min_index=0;
|
|
|
|
// Scorri tutti i bucket
|
|
for (int i = 0; i < ht->size; i++) {
|
|
CACHE_HashNode* current = ht->buckets[i];
|
|
prev = NULL;
|
|
|
|
|
|
while (current != NULL) { // Per ogni nodo nella catena
|
|
if (current->LRU < min_LRU){ // Se il nodo ha LRU minore di min_LRU, diventa il nuovo min
|
|
min_LRU=current->LRU;
|
|
min=current;
|
|
min_prev=prev;
|
|
min_index=i;
|
|
}
|
|
prev = current;
|
|
current = current->next;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
if (min_prev==NULL){
|
|
ht->buckets[min_index] = min->next;
|
|
} else {
|
|
min_prev->next=min->next;
|
|
}
|
|
|
|
free(min);
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
bool insert_element_cache (CACHE_HashTable* ht, int xp, int yp, int xd, int yd, int travel_cost){
|
|
// Cerca un nodo dalla hash table, se non lo trova lo aggiunge, mentre se lo trova aggiorna (LRU permettendo)
|
|
// Ritorna true se il nodo è stato aggiunto o aggiornato, false altrimenti
|
|
|
|
|
|
int index = calculate_hash_cache(xp, yp, xd, yd, ht -> size); // Calcolo l'hash
|
|
|
|
|
|
CACHE_HashNode* current = ht->buckets[index]; //Scorro la lista fino a quando trovo il nodo o la finisco
|
|
while (current!=NULL && !(current->xp==xp && current->yp==yp && current->xd==xd && current->yd==yd)){
|
|
current = current->next;
|
|
}
|
|
|
|
if (current==NULL){ // Se non c'è il nodo, lo inserisco
|
|
|
|
|
|
// Se la cache ha troppi elementi, ne elimino uno tramite la politica di LRU
|
|
if (ht->occupied>=CACHE_MAX_OCCUPIED){
|
|
delete_element_cache(ht);
|
|
}
|
|
|
|
|
|
CACHE_HashNode* hn = malloc(sizeof(CACHE_HashNode)); // Crea il nodo con i parametri che sono stati passati alla funzione (l'attributo next lo definisco nell'inserimento in testa)
|
|
hn->xp = xp;
|
|
hn->yp = yp;
|
|
hn->xd = xd;
|
|
hn->yd = yd;
|
|
hn->travel_cost=travel_cost;
|
|
ht->occupied=ht->occupied+1;
|
|
|
|
|
|
hn->next = ht->buckets[index]; // Inserisco in testa alla lista
|
|
ht->buckets[index] = hn;
|
|
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int search_element_cache (CACHE_HashTable* ht, int xp, int yp, int xd, int yd){
|
|
// Cerca un nodo contenente il tragitto da xp,yp a xd,yd dalla hash table e ne restituisce il costo
|
|
|
|
|
|
int index = calculate_hash_cache(xp, yp, xd, yd, ht -> size); // Calcolo l'hash
|
|
|
|
|
|
CACHE_HashNode* current = ht -> buckets[index]; //Scorro la lista fino a quando trovo il nodo o la finisco
|
|
while (current != NULL && !(current->xp==xp && current->yp==yp && current->xd==xd && current->yd==yd)){
|
|
current = current -> next;
|
|
}
|
|
|
|
if(current==NULL){ // Se il nodo non è presente, restituisce -2
|
|
return -2;
|
|
}
|
|
|
|
current->LRU=current->LRU+1; // Se il nodo è stato cercato, gli aumento l'LRU
|
|
return current->travel_cost;
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN PATH-FINDING (Dijkstra)
|
|
|
|
|
|
int travel_cost(HexMap* map, HashTable* ht, MinHeap* heap, int xp, int yp, int xd, int yd){
|
|
// FUNZIONAMENTO:
|
|
// È un algoritmo Dijkstra in cui tengo sempre una coda ORDINATA che ha in testa le coordinate x,y del nodo con minore costo, mentre in coda quello con maggior costo.
|
|
// Il costo è dato dalla distanza dal nodo sorgente.
|
|
//
|
|
// Inizializzo la coda e ci inserisco il nodo sorgente; una volta fatto questo inserisco i 6 nodi vicini nella hashtable e poi, se conviene, nella coda.
|
|
//
|
|
// NOTA: la funzione di inserimento dell'hash table inserisce il costo solamente se è minore di quello già presente e riotrna il nodo solo se viene aggiunto o aggiornato
|
|
// (se il costo è maggiore di quello precedente, ritorna NULL).
|
|
//
|
|
// NOTA: la coda è implementata tramite min-heap.
|
|
// NOTA: la funzione di inserimento in coda inserisce i nodi già ordinandoli in base al loro costo.
|
|
|
|
|
|
|
|
|
|
if (!is_valid(map,xp,yp) || !is_valid(map,xd,yd)){
|
|
return -1;
|
|
}
|
|
|
|
|
|
Node* new_node = insert_or_update_element(ht, xp, yp, 0); // Inserisco il nodo sorgente in hash-table
|
|
heap_enqueue(heap, new_node); // Inserisco il nodo sorgente in heap
|
|
|
|
|
|
|
|
|
|
|
|
// TODO guardare le variabili inizializzate
|
|
Node* current; // Inizializzo current, ossia il primo nodo della coda su cui lavoro (quello con costo minore dato che la coda è ordinata)
|
|
Hexagon hex; // Il corrispettivo di current in griglia (per avere accesso a land_cost, air_routes ecc...)
|
|
|
|
// Creo i due percorsi da ispezionare in base alla riga (pari o dispari)
|
|
const int dir_even[6][2] = {
|
|
{+1, 0}, { 0, -1}, {+1, -1},
|
|
{-1, 0}, {+1, +1}, { 0, +1}
|
|
};
|
|
const int dir_odd[6][2] = {
|
|
{+1, 0}, {-1, -1}, { 0, -1},
|
|
{-1, 0}, { 0, +1}, {-1, +1}
|
|
};
|
|
const int (*dirs)[2];
|
|
|
|
|
|
int new_x; // new_x e new_y vengono usate per immagazzinare i 6 nodi vicini
|
|
int new_y;
|
|
|
|
int air_route_count; // In queste due variabili vado a inserire gli attributi delle rotte aeree del nodo corrente
|
|
AirRoute* air_routes;
|
|
|
|
|
|
while (heap->size>0){
|
|
// Per prima cosa, inserisco in current il primo nodo della coda
|
|
// NOTA: non devo fare altri controlli in hash table perchè, non essendoci duplicati, questo è già con il costo minore
|
|
current=heap_dequeue(heap);
|
|
|
|
hex = map->grid[current->x][current->y];
|
|
if(hex.land_cost!=0){ // Se current è transitabile
|
|
// ISPEZIONI I 6 VICINI
|
|
if (current->y % 2 == 1) { // Scelgo la direzione in base alla parità della riga
|
|
dirs = dir_even;
|
|
} else {
|
|
dirs = dir_odd;
|
|
}
|
|
// Guardo le coordinate dei 6 nodi vicini (per ogni iterazione, il nodo vicino avrà coordinate new_x, new_y)
|
|
for (int i = 0; i < 6; i++) {
|
|
new_x = current->x + dirs[i][0];
|
|
new_y = current->y + dirs[i][1];
|
|
|
|
if(is_valid(map, new_x, new_y)){ // Se il nodo è nella mappa
|
|
new_node = insert_or_update_element(ht, new_x, new_y, current->cost + hex.land_cost); // Provo a inserirlo in hash table
|
|
if (new_node != NULL){ // Se viene inserito o aggiorno il costo
|
|
heap_enqueue(heap, new_node); // Lo aggiungo alla coda
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// ISPEZIONO LE ROTTE AEREE USCENTI DA CURRENT
|
|
air_route_count=hex.air_route_count;
|
|
air_routes=hex.air_routes;
|
|
for (int i=0; i<air_route_count; i++){
|
|
new_x=air_routes[i].dest_x; // La destinazione la memorizzo in new_x e new_y (come nell'inserimento dei 6 nodi vicini)
|
|
new_y=air_routes[i].dest_y;
|
|
if(is_valid(map, new_x, new_y)){ // Se il nodo è nella mappa
|
|
new_node = insert_or_update_element(ht, new_x, new_y, current->cost + air_routes[i].cost);
|
|
if (new_node != NULL){ // Se inserendolo ottengo true
|
|
heap_enqueue(heap, new_node); // Lo aggiungo alla coda
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
int ris = search_element(ht, xd, yd);
|
|
heap_clear(heap); // Dealloco la coda
|
|
clear_hash_table(ht); // Pulisco la hash table
|
|
return ris;
|
|
}
|
|
|
|
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
int main(){
|
|
|
|
char testo[30];
|
|
int inp_uno, inp_due, inp_tre, inp_quattro;
|
|
|
|
HexMap map;
|
|
HashTable* ht = NULL;
|
|
MinHeap* heap = NULL;
|
|
CACHE_HashTable* cache = NULL;
|
|
|
|
int already_initialized=0;
|
|
|
|
int cost;
|
|
|
|
while (true){
|
|
|
|
// LEGGO L'INPUT E SE RAGGIUNGO L'EOF FACCIO UNA BREAK
|
|
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){
|
|
|
|
// MAPPA
|
|
if (already_initialized==1){
|
|
destroy_map(&map);
|
|
}
|
|
init_map(&map, inp_uno, inp_due);
|
|
already_initialized=1;
|
|
|
|
// HASH TABLE
|
|
if (ht!=NULL){
|
|
destroy_hash_table(&ht);
|
|
}
|
|
ht = create_hash_table(inp_uno * inp_due);
|
|
|
|
// HEAP
|
|
if (heap!=NULL){
|
|
heap_destroy(heap);
|
|
}
|
|
heap = heap_create(inp_uno * inp_due);
|
|
|
|
// CACHE
|
|
if (cache!=NULL){
|
|
destroy_cache(&cache);
|
|
}
|
|
cache = create_cache(CACHE_SIZE);
|
|
}
|
|
|
|
|
|
if (strcmp(testo, "print")==0){
|
|
if (already_initialized==0){
|
|
fprintf(stdout, "-1\n");
|
|
fflush(stdout);
|
|
continue;
|
|
}
|
|
print_map(&map);
|
|
}
|
|
|
|
|
|
if (strcmp(testo, "change_cost")==0){
|
|
if (already_initialized==0){
|
|
fprintf(stdout, "-1\n");
|
|
fflush(stdout);
|
|
continue;
|
|
}
|
|
if(change_cost(&map, inp_uno, inp_due, inp_tre, inp_quattro)){ // Se la mappa viene effettivamente cambiata restituisce tre (quindi pulisco hash table e cache)
|
|
clear_cache(cache);
|
|
}
|
|
}
|
|
|
|
|
|
if (strcmp(testo, "toggle_air_route")==0){
|
|
if (already_initialized==0){
|
|
fprintf(stdout, "-1\n");
|
|
fflush(stdout);
|
|
continue;
|
|
}
|
|
if(toggle_air_route(&map, inp_uno, inp_due, inp_tre, inp_quattro)){ // Se il cambio di rotte aeree va a buon fine restituisce true
|
|
clear_cache(cache);
|
|
}
|
|
}
|
|
|
|
|
|
if (strcmp(testo, "travel_cost")==0){
|
|
if (already_initialized==0){
|
|
fprintf(stdout, "-1\n");
|
|
fflush(stdout);
|
|
continue;
|
|
}
|
|
cost=search_element_cache(cache, inp_uno, inp_due, inp_tre, inp_quattro); // Cerco l'elemento in cache
|
|
|
|
|
|
if(cost==-2){ // Se non c'è, uso Dijkstra
|
|
cost = travel_cost(&map, ht, heap, inp_uno, inp_due, inp_tre, inp_quattro);
|
|
insert_element_cache(cache, inp_uno, inp_due, inp_tre, inp_quattro, cost);
|
|
}
|
|
|
|
fprintf(stdout, "%d\n", cost);
|
|
fflush(stdout);
|
|
}
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|