812 lines
23 KiB
Plaintext
812 lines
23 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 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* 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; // Matrice vera e propria
|
|
} HexMap;
|
|
|
|
|
|
// CACHE DA SISTEMARE
|
|
typedef struct CACHE_HashNode CACHE_HashNode;
|
|
|
|
struct CACHE_HashNode{
|
|
int xp,yp;
|
|
int xd,yd;
|
|
int travel_cost;
|
|
int LRU;
|
|
CACHE_HashNode* next;
|
|
};
|
|
|
|
typedef struct{
|
|
int size;
|
|
int occupied;
|
|
CACHE_HashNode** buckets;
|
|
} CACHE_HashTable;
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN MAP FUNCTIONS
|
|
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;
|
|
|
|
map->grid = (Hexagon**) malloc(cols * sizeof(Hexagon*));
|
|
|
|
for (int i=0; i<map->cols; i++){
|
|
map->grid[i] = (Hexagon*) malloc(rows * sizeof(Hexagon));
|
|
|
|
for (int j=0; j<map->rows; j++){
|
|
map->grid[i][j].land_cost=1;
|
|
map->grid[i][j].air_route_count = 0;
|
|
}
|
|
}
|
|
fprintf(stdout,"OK\n");
|
|
fflush(stdout);
|
|
}
|
|
|
|
void destroy_map(HexMap* map){
|
|
// Distrugge 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){
|
|
// 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");
|
|
}
|
|
}
|
|
|
|
static 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);
|
|
}
|
|
|
|
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
|
|
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 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);
|
|
fflush(stdout);
|
|
return false;
|
|
}
|
|
|
|
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){
|
|
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);
|
|
|
|
if (map->grid[i][j].land_cost>100){
|
|
map->grid[i][j].land_cost=100;
|
|
}
|
|
if (map->grid[i][j].land_cost<0){
|
|
map->grid[i][j].land_cost=0;
|
|
}
|
|
|
|
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){
|
|
// 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);
|
|
fflush(stdout);
|
|
return false;
|
|
}
|
|
|
|
Hexagon* StartingHexagon = &(map->grid[x_1][y_1]);
|
|
|
|
if (StartingHexagon->air_route_count>4){
|
|
fputs("KO\n", stdout);
|
|
fflush(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);
|
|
fflush(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);
|
|
fflush(stdout);
|
|
return true;
|
|
}
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN HASH-TABLE FUNCTIONS
|
|
static inline int calculate_hash(int x, int y, int size) {
|
|
// Calcola l'hash date in input le coordinate e la dimensione della hash table
|
|
unsigned int hash = 2166136261u;
|
|
hash ^= (unsigned int)x;
|
|
hash *= 16777619u;
|
|
hash ^= (unsigned int)y;
|
|
hash *= 16777619u;
|
|
return hash % size;
|
|
}
|
|
|
|
HashTable* create_hash_table(int size) {
|
|
// Genera l'hash table con fattore di carico 1.2 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.2);
|
|
|
|
static const int primes[] = {
|
|
53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
|
|
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
|
|
6291469, 12582917, 25165843, 50331653, 100663319
|
|
};
|
|
|
|
int hash_length = 53;
|
|
for (int i = 0; i < 22; i++) {
|
|
if (primes[i] >= min_size) {
|
|
hash_length = primes[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
HashTable* ht = (HashTable*) malloc(sizeof(HashTable));
|
|
ht->size = hash_length;
|
|
ht->capacity = size;
|
|
ht->buckets = calloc(hash_length, sizeof(Node*));
|
|
ht->node_pool = malloc(size * sizeof(Node));
|
|
ht->pool_index = 0;
|
|
|
|
return ht;
|
|
}
|
|
|
|
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)->node_pool);
|
|
free(*ht);
|
|
*ht = NULL;
|
|
}
|
|
}
|
|
|
|
static 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->node_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
|
|
static 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;
|
|
}
|
|
|
|
static 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) >> 1;
|
|
if (heap->queue[index]->cost >= heap->queue[parent]->cost){
|
|
break;
|
|
}
|
|
|
|
heap_swap(&heap->queue[index], &heap->queue[parent]);
|
|
index = parent;
|
|
}
|
|
}
|
|
|
|
static 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 << 1) + 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;
|
|
}
|
|
}
|
|
|
|
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);
|
|
}
|
|
}
|
|
|
|
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;
|
|
}
|
|
|
|
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;
|
|
}
|
|
|
|
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
|
|
if (!is_valid(map,xp,yp) || !is_valid(map,xd,yd)) {
|
|
return -1;
|
|
}
|
|
|
|
Node* new_node = insert_or_update_element(ht, xp, yp, 0);
|
|
heap_enqueue(heap, new_node);
|
|
|
|
|
|
Node* current;
|
|
Hexagon* hex;
|
|
|
|
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}
|
|
};
|
|
const int (*dirs)[2];
|
|
|
|
int new_x, new_y;
|
|
|
|
|
|
while (heap->size > 0) {
|
|
current = heap_dequeue(heap);
|
|
|
|
if (current->x == xd && current->y == yd) {
|
|
int result = current->cost;
|
|
heap_clear(heap);
|
|
clear_hash_table(ht);
|
|
return result;
|
|
}
|
|
|
|
hex = &map->grid[current->x][current->y];
|
|
if (hex->land_cost == 0){
|
|
continue;
|
|
}
|
|
|
|
if (current->y % 2 == 1) {
|
|
dirs = dir_even;
|
|
} else {
|
|
dirs = dir_odd;
|
|
}
|
|
|
|
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)) {
|
|
new_node = insert_or_update_element(ht, new_x, new_y, current->cost + hex->land_cost);
|
|
if (new_node != NULL) {
|
|
heap_enqueue(heap, new_node);
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < hex->air_route_count; i++) {
|
|
new_x = hex->air_routes[i].dest_x;
|
|
new_y = hex->air_routes[i].dest_y;
|
|
|
|
if (is_valid(map, new_x, new_y)) {
|
|
new_node = insert_or_update_element(ht, new_x, new_y, current->cost + hex->air_routes[i].cost);
|
|
if (new_node != NULL) {
|
|
heap_enqueue(heap, new_node);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int index = calculate_hash(xd, yd, ht->size);
|
|
current = ht->buckets[index];
|
|
while (current != NULL) {
|
|
if (current->x == xd && current->y == yd) {
|
|
int result = current->cost;
|
|
heap_clear(heap);
|
|
clear_hash_table(ht);
|
|
return result;
|
|
}
|
|
current = current->next;
|
|
}
|
|
heap_clear(heap);
|
|
clear_hash_table(ht);
|
|
return -1;
|
|
}
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN CACHE
|
|
// DA SISTEMARE
|
|
CACHE_HashTable* create_cache(int size){
|
|
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
|
|
};
|
|
|
|
int hash_length=0;
|
|
for (size_t i = 0; i < 23; i++) {
|
|
if (primes[i] >= size) {
|
|
hash_length = primes[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
CACHE_HashTable* ht = (CACHE_HashTable*)malloc(sizeof(CACHE_HashTable));
|
|
ht->size = hash_length;
|
|
ht->occupied=0;
|
|
|
|
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) {
|
|
for (int i = 0; i < ht->size; i++) {
|
|
CACHE_HashNode* current = ht->buckets[i];
|
|
|
|
while (current != NULL) {
|
|
CACHE_HashNode* next = current->next;
|
|
free(current);
|
|
current = next;
|
|
}
|
|
|
|
ht->buckets[i] = NULL;
|
|
}
|
|
|
|
ht->occupied=0;
|
|
}
|
|
|
|
void destroy_cache(CACHE_HashTable** ht) {
|
|
clear_cache(*ht);
|
|
|
|
free((*ht)->buckets);
|
|
free(*ht);
|
|
*ht = NULL;
|
|
}
|
|
|
|
int calculate_hash_cache(int xp, int yp, int xd, int yd, int size) {
|
|
const int p1 = 7919;
|
|
const int p2 = 1237;
|
|
const int p3 = 1047;
|
|
const int p4 = 1548;
|
|
|
|
return ((xp * p1) ^ (yp * p2) ^ (xd * p3) ^ (yd * p4)) % size;
|
|
}
|
|
|
|
void delete_element_cache(CACHE_HashTable* ht){
|
|
CACHE_HashNode* prev=NULL;
|
|
|
|
CACHE_HashNode* min=NULL;
|
|
CACHE_HashNode* min_prev=NULL;
|
|
int min_LRU=1000;
|
|
int min_index=0;
|
|
|
|
for (int i = 0; i < ht->size; i++) {
|
|
CACHE_HashNode* current = ht->buckets[i];
|
|
prev = NULL;
|
|
|
|
while (current != NULL) {
|
|
if (current->LRU < min_LRU){
|
|
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){
|
|
int index = calculate_hash_cache(xp, yp, xd, yd, ht->size);
|
|
|
|
CACHE_HashNode* current = ht->buckets[index];
|
|
while (current!=NULL && !(current->xp==xp && current->yp==yp && current->xd==xd && current->yd==yd)){
|
|
current = current->next;
|
|
}
|
|
|
|
if (current==NULL){
|
|
if (ht->occupied>=CACHE_MAX_OCCUPIED){
|
|
delete_element_cache(ht);
|
|
}
|
|
|
|
CACHE_HashNode* hn = malloc(sizeof(CACHE_HashNode));
|
|
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];
|
|
ht->buckets[index] = hn;
|
|
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
int search_element_cache (CACHE_HashTable* ht, int xp, int yp, int xd, int yd){
|
|
int index = calculate_hash_cache(xp, yp, xd, yd, ht->size);
|
|
|
|
CACHE_HashNode* current = ht->buckets[index];
|
|
while (current != NULL && !(current->xp==xp && current->yp==yp && current->xd==xd && current->yd==yd)){
|
|
current = current->next;
|
|
}
|
|
|
|
if(current==NULL){
|
|
return -2;
|
|
}
|
|
|
|
current->LRU=current->LRU+1;
|
|
return current->travel_cost;
|
|
}
|
|
// END
|
|
|
|
|
|
|
|
|
|
|
|
// BEGIN MAIN
|
|
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){
|
|
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)){
|
|
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)){
|
|
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);
|
|
|
|
if(cost==-2){
|
|
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);
|
|
}
|
|
}
|
|
|
|
// 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
|