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

typedef struct Node {
   const char* name; /* name of the node */
   unsigned long int hashval; /* hash value of the name */
   struct Neighbor* head; /* linear list of neighbors */
   struct Neighbor* tail; /* points to last member of the linear list */
   struct Node* next; /* within the hash table */
} Node;

typedef struct Neighbor {
   struct Node* node;
   struct Neighbor* next;
} Neighbor;

#define BUCKET_SIZE (1<<5)

typedef struct Graph {
   Node* bucket[BUCKET_SIZE];
} Graph;

Graph* create_graph();

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

Node* create_node(const char* name) {
   name = strdup(name);
   if (!name) return 0;
   Node* node = malloc(sizeof(Node));
   if (node) {
      node->name = name;
      node->hashval = get_hashval(name);
      node->head = node->tail = 0;
      node->next = 0;
   }
   return node;
}

bool add_neighbor(Node* node, Node* other) {
   Neighbor* neighbor;
   neighbor = malloc(sizeof(Neighbor));
   if (!neighbor) return false;
   neighbor->node = other; neighbor->next = 0;
   if (node->head) {
      node->tail->next = neighbor;
   } else {
      node->head = neighbor;
   }
   node->tail = neighbor;
   return true;
}

Node* lookup_neighbor(Node* node, const char* name) {
   unsigned long int hashval = get_hashval(name);
   for (Neighbor* neighbor = node->head; neighbor;
	 neighbor = neighbor->next) {
      if (neighbor->node->hashval == hashval &&
	    strcmp(neighbor->node->name, name) == 0) {
	 return neighbor->node;
      }
   }
   return 0;
}

Graph* create_graph() {
   Graph* graph = malloc(sizeof(Graph));
   if (graph) {
      for (unsigned int i = 0; i < BUCKET_SIZE; ++i) {
	 graph->bucket[i] = 0;
      }
   }
   return graph;
}

void add_node(Graph* graph, Node* node) {
   unsigned int index = node->hashval % BUCKET_SIZE;
   node->next = graph->bucket[index]; graph->bucket[index] = node;
}

Node* find_node(Graph* graph, const char* name) {
   unsigned int index = get_hashval(name) % BUCKET_SIZE;
   for (Node* node = graph->bucket[index]; node; node = node->next) {
      if (strcmp(name, node->name) == 0) {
	 return node;
      }
   }
   return 0;
}

bool biconnect_nodes(Graph* graph, Node* node, const char* name) {
   Node* other = find_node(graph, name);
   if (!other) {
      other = create_node(name);
      if (!other) return false;
      add_node(graph, other);
   }
   return add_neighbor(node, other) && add_neighbor(other, node);
}

Graph* read_graph(const char* filename) {
   FILE* fp = fopen(filename, "r");
   if (!fp) return 0;
   Graph* graph = create_graph();
   char buf[BUFSIZ];
   while (fgets(buf, sizeof buf, fp)) {
      char* name = buf;
      Node* node = 0;
      char* last = 0;
      for (char* cp = buf; ; ++cp) {
	 bool nullbyte = *cp == 0;
	 bool newline = *cp == '\n';
	 if (!nullbyte && *cp != ':' && !newline) continue;
	 *cp = 0;
	 if (node) {
	    if (!biconnect_nodes(graph, node, last)) return 0;
	 } else {
	    node = find_node(graph, name);
	    if (!node) {
	       node = create_node(name);
	       if (!node) return 0;
	       add_node(graph, node);
	    }
	 }
	 if (newline || nullbyte) break;
	 last = cp + 1;
      }
   }
   fclose(fp);
   return graph;
}

void walk(Graph* graph, Node* start) {
   Node* node = start;
   for(;;) {
      int ll = printf("You're located in %s and you are free to move",
	 node->name);
      if (!node->head) {
	 printf(" nowhere. Sorry.\n"); return;
      }
      ll += printf(" to");
      for (Neighbor* neighbor = node->head; neighbor;
	    neighbor = neighbor->next) {
	 char* s;
	 if (neighbor == node->head) {
	    s = "";
	 } else if (!neighbor->next) {
	    s = ", or"; ll += 4;
	 } else {
	    s = ","; ll += 1;
	 }
	 unsigned int namelen = strlen(neighbor->node->name);
	 if (ll + 1 + namelen > 66) {
	    printf("%s\n", s);
	    ll = namelen;
	 } else if (ll == 0) {
	    ll = namelen;
	    printf("%s", s);
	 } else {
	    ll += 1 + namelen;
	    printf("%s ", s);
	 }
	 printf("%s", neighbor->node->name);
      }
      printf(".\n");
      printf("Next? ");
      char line[BUFSIZ];
      if (!fgets(line, sizeof line, stdin)) break;
      if (!line[0] || line[0] == '\n') continue;
      char* cp = strchr(line, '\n');
      if (cp) *cp = 0;
      Node* other = lookup_neighbor(node, line);
      if (!other) {
	 printf("This is not in my neighborhood.\n");
	 continue;
      }
      node = other;
   }
}

int main() {
   Graph* graph = read_graph("bw.txt");
   if (graph) {
      Node* start = find_node(graph, "Ulm");
      if (start) {
	 walk(graph, start);
      } else {
	 printf("Sorry, I was unable to locate Ulm!\n");
      }
   } else {
      printf("Sorry, graph loading failed!\n");
   }
}