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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "cityandroad.h"

#define dictionary_size 1000

int num_cities=0;
int num_roads=0;

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

char *new_string(char *s)
{ char *r=(char *)malloc(strlen(s)+1);
  strcpy(r,s);
  return r; }

char *trim(char *s)
{ int n;
  while (*s<=' ' && *s!='\0')
    s+=1;
  n=strlen(s)-1;
  while (n>0 && s[n]>' ')
    n-=1;
  n+=1;
  s[n]='\0';
  return s; }

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


float direction(city_record *c1, city_record *c2)
{ double lat1, lon1, lat2, lon2, cosg, sing, g, sina, ss, tana, a1, a2, sl21, sl22, e1, e2;
  lat1=c1->lat*pi/180.0;
  lon1=c1->lon*pi/180.0;
  lat2=c2->lat*pi/180.0;
  lon2=c2->lon*pi/180.0;
  cosg=sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon2-lon1);
  g=atan(sqrt(1.0/cosg/cosg-1.0));
  if (g<0.0) g=pi+g;
  sing=sqrt(1.0-cosg*cosg);
  if (sing==0.0)
    sina=0.0;
  else
    sina=cos(lat2)*sin(lon2-lon1)/sing;
  ss=sina*sina;
  if (ss==1.0)
  { if (ss<0.0)
      a1=-pi;
    else
      a1=pi;
    a2=a1; }
  else
  { tana=sina/sqrt(1.0-sina*sina);
    a1=atan(tana);
    a2=pi-a1; }
  if (a1<0.0)
    a1=2.0*pi+a1;
  if (a2<0.0)
    a2=2.0*pi+a2;
  sl21=sin(lat1)*cosg+cos(lat1)*sing*cos(a1);
  sl22=sin(lat1)*cosg+cos(lat1)*sing*cos(a2);
  ss=sin(lat2);
  e1=ss-sl21;
  e1=e1*e1;
  e2=ss-sl22;
  e2=e2*e2;
  if (e1>e2)
  { e1=e2;
    a1=a2; }
  if (e1>0.01)
    printf("Big error in direction (%f)\n",e1);
  return (float)(a1*180.0/pi); }

char *direction_name(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 "??"; }

float distance_between(city_record *c1, city_record *c2)
{ double lon1=c1->lon, lat1=c1->lat, lon2=c2->lon, lat2=c2->lat;
  double cosa, tana, a;
  lon1=lon1*pi/180.0;
  lat1=lat1*pi/180.0;
  lon2=lon2*pi/180.0;
  lat2=lat2*pi/180.0;
  cosa=sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2);
  if (cosa==0)
  { a=pi/2.0; }
  else
  { tana=sqrt(1.0/cosa/cosa-1.0);
    a=atan(tana);
    if (a<0.0)
      a=a+2.0*pi; }
  return ((float)(a*radius_of_earth)); }

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

int read_road_file(char *name)
{ FILE *fi;
  char line[100], roadname[100], cityname1[100], cityname2[100];
  float len;
  int i, oks=0;
  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);
    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 (%.0f miles on bearing %.0f)\n",
                 r->name,direction_name(c1,c2),r->length,c2->name,
                 distance_between(c1,c2),direction(c1,c2));
          r=r->next;  }
        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");
  printf("[%d road records successfully read]\n",n); }

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

void main(void)
{ read_data();
  print_data(); }