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

typedef struct {
   double latitude;
   double longitude;
} Coordinates;

double square(double x) {
   return x * x;
}

#define	PI 3.14159265358979323846

/* formula taken from https://de.wikipedia.org/wiki/Orthodrome */
double compute_distance(Coordinates a, Coordinates b) {
   static const double f = 1/298.257223563;
   static const double ar = 6378.137;
   double F = (a.latitude + b.latitude) / 2;
   double G = (a.latitude - b.latitude) / 2;
   double l = (a.longitude - b.longitude) / 2;

   /* convert F, G and l into radians */
   F = PI/180 * F; G = PI/180 * G; l = PI/180 * l;

   double S = square(sin(G)) * square(cos(l)) +
              square(cos(F)) * square(sin(l));
   double C = square(cos(G)) * square(cos(l)) +
              square(sin(F)) * square(sin(l));
   double w = atan(sqrt(S/C));
   double D = 2 * w * ar;
   double T = sqrt(S*C) / w;
   double H1 = (3*T - 1)/(2*C);
   double H2 = (3*T + 1)/(2*S);
   double s = D * (1 + f*H1*square(sin(F))*square(cos(G)) -
                       f*H2*square(cos(F))*square(sin(G)));
   return s;
}

/* compute the hash value for a name */
unsigned long int get_hashval(const char* name) {
   unsigned long int hashval = 0;
   for (const char* cp = name; *cp; ++cp) {
      hashval = (hashval << 3) ^ *cp ^ (hashval >> 28);
   }
   return hashval;
}

typedef struct Town {
   char* name;
   Coordinates coord;
   struct Town* next;
} Town;

#define BUCKET_SIZE (16384)

typedef struct {
   Town* bucket[BUCKET_SIZE];
} Table;

void init_table(Table* table) {
   for (int i = 0; i < BUCKET_SIZE; ++i) {
      table->bucket[i] = 0;
   }
}

bool add_town(Table* table, char* name, Coordinates coord) {
   Town* town = malloc(sizeof(Town));
   if (!town) return false;
   town->name = strdup(name);
   town->coord = coord;
   unsigned long int hashval = get_hashval(name) % BUCKET_SIZE;
   town->next = table->bucket[hashval];
   table->bucket[hashval] = town;
   return true;
}

Town* find_town(Table* table, char* name) {
   unsigned long int hashval = get_hashval(name) % BUCKET_SIZE;
   for (Town* town = table->bucket[hashval]; town; town = town->next) {
      if (strcmp(town->name, name) == 0) {
	 return town;
      }
   }
   return 0;
}

bool load_towns(Table* table, char* filename) {
   FILE* fp = fopen(filename, "r");
   if (!fp) return false;
   char buf[128];
   while (fgets(buf, sizeof buf, fp)) {
      unsigned int index = 0;
      char* field[3];
      field[0] = buf; ++index;
      for (char* cp = buf; *cp; ++cp) {
	 if (*cp == ':') {
	    *cp = 0;
	    if (index == 3) break;
	    field[index++] = cp + 1;
	 }
      }
      Coordinates coord;
      if (sscanf(field[1], "%lg", &coord.longitude) != 1 ||
	    sscanf(field[2], "%lg", &coord.latitude) != 1 ||
	    !add_town(table, field[0], coord)) {
	 fclose(fp);
	 return false;
      }
   }
   fclose(fp);
   return true;
}

int main() {
   Table table;
   init_table(&table);
   if (!load_towns(&table, "gemeinden.txt")) {
      printf("Could not load table of towns.\n");
      exit(1);
   }
   Town* start = find_town(&table, "Ulm");
   Town* destination = find_town(&table, "Kiel");
   if (!start || !destination) {
      printf("Oops, input data appears to be incomplete.\n");
      exit(1);
   }
   printf("*** Long chain of short trips ***\n");
   printf("Your objective is to travel from %s to %s\n",
      start->name, destination->name);
   printf("through a long chain of intermediate towns where\n");
   printf("the maximal distance between two consecutive towns\n");
   printf("of your journey is to be minimized.\n");

   Town* current = start; double max_distance = 0;
   while (current != destination) {
      printf("You are currently located in %s.\n", current->name);
      Town* next;
      do {
	 printf("Next town? ");
	 char buf[128];
	 if (!fgets(buf, sizeof buf, stdin)) {
	    printf("Bye!\n"); exit(1);
	 }
	 for (char* cp = buf; *cp; ++cp) {
	    if (*cp == '\n') {
	       *cp = 0; break;
	    }
	 }
	 next = find_town(&table, buf);
	 if (!next) {
	    printf("There is no such town.\n");
	 }
      } while (!next);
      double distance = compute_distance(current->coord, next->coord);
      printf("Distance from %s to %s: %.1lf km\n",
	 current->name, next->name, distance);
      if (distance > max_distance) {
	 max_distance = distance;
	 printf("This is the new maximal distance!\n");
      }
      current = next;
   }
   printf("Welcome to %s!\n", destination->name);
   printf("Your maximal intermediate distance was %.1lf km\n",
      max_distance);
}