/*                                                                        data.c
     reads data files for cities and roads and creates data structures        */

#include "utilities.h"
#include "data.h"

#define dictionary_size 1000

int num_cities=0;
int num_roads=0;

city_record *dictionary[dictionary_size];
road_record ***adjacency_matrix=NULL;
city_record **city_list=NULL;
char rough[256];

city_record *make_city_record(char *cityname, int index, float lon, float lat)
{ city_record *r=(city_record *)malloc(sizeof(city_record));
  r->name=new_string(cityname);
  r->index=index;
  r->lon=lon;
  r->lat=lat;
  r->roads=NULL;
  r->next=NULL;
  return r; }

road_record *make_road_record(char *roadname, float length,
                              city_record *end1, city_record *end2)
{ road_record *r=(road_record *)malloc(sizeof(road_record));
  r->name=new_string(roadname);
  r->length=length;
  r->end1=end1;
  r->end2=end2;
  r->next=NULL;
  return r; }

char *direction(city_record *c1, city_record *c2)
{ float x1=-(c1->lon), y1=c1->lat;
  float x2=-(c2->lon), y2=c2->lat;
  float dx=x2-x1, dy=y2-y1;
  if (dy>=0 && dx>=0)
  { if (dy>2*dx) return "N";
    if (dx>2*dy) return "E";
    return "NE"; }
  if (dy>=0 && dx<=0)
  { dx=-dx;
    if (dy>2*dx) return "N";
    if (dx>2*dy) return "W";
    return "NW"; }
  if (dy<=0 && dx>=0)
  { dy=-dy;
    if (dy>2*dx) return "S";
    if (dx>2*dy) return "E";
    return "SE"; }
  if (dy<=0 && dx<=0)
  { dy=-dy; dx=-dx;
    if (dy>2*dx) return "S";
    if (dx>2*dy) return "W";
    return "SW"; }
  return "??"; }

int rough_strcmp(char *a, char *b)
{ int i;
  unsigned char ai, bi;
  i=0;
  while (1)
  { ai=a[i]; bi=b[i];
    if (ai==0)
    { if (bi==0) return 0; else return -1; }
    if (bi==0)
    { return 1; }
    ai=rough[ai];
    bi=rough[bi];
    if (ai!=bi)
    { if (ai<bi) return -1; else return 1; }
    i+=1; } }

int hash_value(char *str)
{ int i, n, h;
  n=strlen(str);
  h=103761;
  for (i=0; i<n; i+=1)
    h=h*1057+rough[str[i]];
  if (h<0) h=-h;
  return (h%dictionary_size); }

void initialise_dictionary(void)
{ int i;
  for (i=0; i<256; i+=1)
    rough[i]=0;
  for (i='a'; i<='z'; i+=1)
    rough[i]=i;
  for (i='0'; i<='9'; i+=1)
    rough[i]=i;
  for (i='A'; i<='Z'; i+=1)
    rough[i]=i+32;
  for (i=0; i<dictionary_size; i+=1)
    dictionary[i]=NULL; }

void add_to_dictionary(city_record *e)
{ int h=hash_value(e->name);
  e->next=dictionary[h];
  dictionary[h]=e; }

city_record *find_in_dictionary(char *name)
{ int h=hash_value(name);
  city_record *e=dictionary[h];
  while (e!=NULL)
  { if (rough_strcmp(name,e->name)==0)
      return e;
    e=e->next; }
  return NULL; }

city_record *read_city(FILE *f)
{ city_record *c=NULL;
  char line[100];
  char *trimmed;
  while (c==NULL)
  { fgets(line,100,f);
    trimmed=trim(line);
    c=find_in_dictionary(trimmed);
    if (c==NULL)
      printf("** City \"%s\" not known.\nReenter: ",trimmed); }
  return c; }

int read_city_file(char *name)
{ FILE *fi;
  char line[100], cityname[100];
  float lon, lat;
  int oks=0;
  fi=fopen(name,"r");
  if (fi==NULL)
  { fprintf(stderr,"Can't open city file \"%s\"\n",name);
    return 0; }
  initialise_dictionary();
  while (1)
  { char *s;
    int n;
    s=fgets(line,100,fi);
    if (s==NULL) break;
    n=sscanf(line,"%s %f %f",cityname,&lat,&lon);
    if (n!=3) break;
    oks+=1;
    add_to_dictionary(make_city_record(cityname,oks,lon,lat)); }
  fclose(fi);
  num_cities=oks;
  return oks; }

void initialise_adjacency_matrix(void)
{ int i, j;
  adjacency_matrix=(road_record ***)malloc((num_cities+1)*sizeof(road_record **));
  for (i=1; i<=num_cities; i+=1)
  { adjacency_matrix[i]=(road_record **)malloc((num_cities+1)*sizeof(road_record *));
    for (j=1; j<=num_cities; j+=1)
      adjacency_matrix[i][j]=NULL; } }

int read_road_file(char *name, int wanted)
{ FILE *fi;
  char line[100], roadname[100], cityname1[100], cityname2[100];
  float len;
  int i, oks=0;
  if (wanted==MAKE_ADJACENCY_MATRIX)
    initialise_adjacency_matrix();
  city_list=(city_record **)malloc((num_cities+1)*sizeof(city_record *));
  for (i=0; i<=num_cities; i+=1)
    city_list[i]=NULL;
  fi=fopen(name,"r");
  if (fi==NULL)
  { fprintf(stderr,"Can't open road file \"%s\"\n",name);
    return 0; }
  while (1)
  { char *s;
    int n, ind1, ind2;
    city_record *city1, *city2;
    road_record *road12, *road21;
    s=fgets(line,100,fi);
    if (s==NULL) break;
    n=sscanf(line,"%s %f %s %s",roadname,&len,cityname1,cityname2);
    if (n!=4) break;
    oks+=1;
    city1=find_in_dictionary(cityname1);
    city2=find_in_dictionary(cityname2);
    if (city1==NULL)
    { fprintf(stderr,"Bad city \"%s\" on line %d of road file\n",cityname1,oks);
      return (oks-1); }
    if (city2==NULL)
    { fprintf(stderr,"Bad city \"%s\" on line %d of road file\n",cityname2,oks);
      return (oks-1); }
    ind1=city1->index;
    ind2=city2->index;
    city_list[ind1]=city1;
    city_list[ind2]=city2;
    road12=make_road_record(roadname,len,city1,city2);
    road21=make_road_record(roadname,len,city2,city1);
    if (wanted==MAKE_ADJACENCY_MATRIX)
    { adjacency_matrix[ind1][ind2]=road12;
      adjacency_matrix[ind2][ind1]=road21; }
    road12->next=city1->roads;
    city1->roads=road12;
    road21->next=city2->roads;
    city2->roads=road21; }
  fclose(fi);
  num_roads=oks;
  return oks; }

  void print_city_data(void)
  { int i;
    for (i=1; i<=num_cities; i+=1)
    { city_record *c1;
      road_record *r;
      c1=city_list[i];
      printf("%3d: ",i);
      if (c1==NULL)
        printf("<NULL>\n");
      else
      { printf("%s  (%.2fN, %.2fW)\n",c1->name,c1->lat,c1->lon);
        r=c1->roads;
        while (r!=NULL)
        { city_record *c2=r->end2;
          printf("        %s, %s %.0f miles to %s\n",
                 r->name,direction(c1,c2),r->length,c2->name);
          r=r->next;  }
        printf("\n"); } } }

  void print_adjacency_matrix(void)
  { int i, j;
    printf("    ");
    for (j=1; j<=num_cities; j+=1)
      printf("%3d ",j);
    printf("\n");
    for (i=1; i<=num_cities; i+=1)
    { printf("%3d ",i);
      for (j=1; j<=num_cities; j+=1)
      { road_record *r;
        r=adjacency_matrix[i][j];
        if (r==NULL)
          printf("  - ");
        else
          printf("%4.0f",r->length); }
      printf("\n"); } }

void read_data(void)
{ int n;
  n=read_city_file("cities.txt");
  printf("[%d city records successfully read]\n",n);
  n=read_road_file("roads.txt",MAKE_ADJACENCY_MATRIX);
  printf("[%d road records successfully read]\n",n); }

void print_data(void)
{ printf("Cities:\n");
  print_city_data();
  dos_pause();
  printf("Connectivity:\n");
  print_adjacency_matrix();
  dos_pause(); }