/* after years of fiddling..
  'v1.0  September 89
'Jim Butterfield  */

   /* compile with lc -Lcd -v <filename> */
#include <proto/exec.h>
#include <proto/dos.h>
#include <stdio.h>
#define BUFFERLINE 50
#define INFOSIZE sizeof(struct FileInfoBlock)
#define TRAILLEN 60

/* File Support structures */
struct CityData {
                char *CityName;              /* full name  w/state */
                char *StateName;             /* state/province only */
                struct CityData *CityLink;   /* init letter chain */
                struct CityData *StateLink;  /* init letter chain */
                struct RouteData *RoadList;  /* roads to/from city */
                struct CityData *WorkList;   /* temp job queue */
                struct CityData *NextCity[2];  /* result links */
      /* Mindist[0] doubles as CityDupe flag during file input */
                unsigned short MinDist[2];   /* closest so far */
                unsigned char StateDupe;     /* one name per state */
                unsigned char Colum;         /* goes with RoadList */
                };
struct RouteData {
                 struct CityData *CityNum[2];  /* cities each end */
                 unsigned short Dist[2];       /* distance, time */
                 char *Hiway;                  /* name of Highway */
                 struct RouteData *RLink[2];   /* link for each city */
                 unsigned char Colm[2];        /* goes with RLink */
                 };
struct RouteData *Route0, *Route9;
struct CityData *City0, *City9;
struct CityData *CharLink[0x20];
struct CityData *ChStLink[0x20];
struct CityData *CityLink[0x20];
struct CityData *CountLink[5];
static char InBuff[BUFFERLINE];
static struct CityData *Trail[TRAILLEN][2];
unsigned short TrailPoint[2];
void TimeShow(unsigned short,char *);
int CityMatch(struct CityData *,char *);
unsigned short ParseCities(char *,long);
unsigned short ParseRoutes(char *,long);
struct CityData * AskCity();
unsigned short Navigate(struct CityData *,struct CityData *);
void main()
  {
  long fh, lok;
  unsigned short NextCol, NewCol;
  unsigned short AllocCount, errnum;
  struct FileInfoBlock *fibb;
  long CitySize, RouteSize;
  char *CityBlox, *RouteBlox, *DataScan, *Active;
  char *CityScan, *CityPoint, *RoutePoint;
  struct CityData *From, *Dest;
  struct RouteData *NextRoute, *NewRoute, *ScanRoute;
  unsigned short Cities, Roads;
  unsigned short CityPSize, RoutePSize;
  unsigned char Ct0;             /* general character work value */
  unsigned short Count, Links;
  static char ActCity[]="Cities";
  static char ActRoad[]="Roads";
  for (Ct0=0; Ct0 < 0x20; Ct0++) CharLink[Ct0]= 0;
  for (Ct0=0; Ct0 < 0x20; Ct0++) ChStLink[Ct0]= 0;
  for (Ct0=0; Ct0 < 5; Ct0++) CountLink[Ct0]= 0;
  AllocCount=0;
  errnum=2;                   /* no memory */
  if ( (long) (fibb = (struct FileInfoBlock *) AllocMem(INFOSIZE,0L))
                                                                != 0L)
    {
    AllocCount=1;
    errnum=3;                   /* file problems */
    fprintf(stderr,"RoadScan V1.0  ..   Jim Butterfield\n");
    fprintf(stderr,"   Release version:  1990 04 06\n");
    Cities=0;
    Active=ActCity;
    if ( (lok = Lock("Cities",ACCESS_READ)) != 0L)
      {
      if ( (fh=Examine(lok,fibb)) !=0L)
        {
        CitySize=fibb->fib_Size;
        if ( (long) (CityBlox = AllocMem(CitySize,0L)) != 0L)
	  {
          AllocCount=2;
          if ( (fh = Open("Cities",MODE_OLDFILE)) != 0L)
            {
            errnum=0;
            Read(fh,CityBlox,CitySize);
            Close(fh);
	    }                      /* City file opened   */
          }                        /* data alloc OK */
	}                          /* examine OK    */
        UnLock(lok);
      }                            /* lock OK          */
    }                              /* examine alloc OK */
  if (errnum == 0)
    {
    for (DataScan=CityBlox;DataScan < CityBlox+CitySize;DataScan++)
      if (*DataScan == 0x0A) Cities++;
    CityPSize=Cities*sizeof(struct CityData);
    if ( (long) (CityPoint = AllocMem(CityPSize,0L)) != 0L)
      AllocCount=3;
    else
      errnum=2;
    }
  if (errnum ==0 )
    {
    errnum=3;                   /* file problems */
    Active=ActRoad;
    Roads=0;
    if ( (lok = Lock("Roads",ACCESS_READ)) != 0L)
      {
      if ( (fh=Examine(lok,fibb)) !=0L)
        {
        RouteSize=fibb->fib_Size;
        if ( (long) (RouteBlox = AllocMem(RouteSize,0L)) != 0L)
          {
          AllocCount=4;
          if ( (fh = Open("Roads",MODE_OLDFILE)) != 0L)
            {
            errnum=0;
            Read(fh,RouteBlox,RouteSize);
            Close(fh);
            }                      /* file opened   */
          }                        /* data alloc OK */
        }                          /* examine OK    */
      UnLock(lok);
      }                            /* lock OK          */
    }
  if (errnum == 0)
    {
    for (DataScan=RouteBlox;DataScan < RouteBlox+RouteSize;DataScan++)
      if (*DataScan == 0x0A) Roads++;
    RoutePSize=Roads*sizeof(struct RouteData);
    if ( (long) (RoutePoint = AllocMem(RoutePSize,0L)) != 0L)
      AllocCount=5;
    else
      errnum=2;
    }
  if (errnum == 0)
    {
    Active=ActCity;
    fprintf(stderr,">> %d Cities\n",Cities);
    City0 = (struct CityData *) CityPoint;
    errnum=ParseCities(CityBlox,CitySize);
    }
  if (errnum == 0)
    {
    Active=ActRoad;
    fprintf(stderr,">> %d Roads\n",Roads);
    Route0 = (struct RouteData *) RoutePoint;
    errnum=ParseRoutes(RouteBlox,RouteSize);
    }
  switch (errnum)
    {
    case 0:                /* no errors, do main job */
      printf("Scanning Cities...\n\n");
      From=City0;
      while (From<City9)
       {
       CityScan=From->CityName;
       while (*(++CityScan) != ',');
       *CityScan=0;
       Count=0;
       NextRoute=From->RoadList;
       NextCol=From->Colum;
       while (NextRoute != 0)
	 {
         Dest=NextRoute->CityNum[1-NextCol];
         for (Links=0; Links<Count; Links++)
           if (CityLink[Links]==Dest && From>Dest )
             printf("DUPE: %s,%s TO %s\n",
	       Dest->CityName,Dest->StateName,From->CityName);
         CityLink[Count]=Dest;
	 Count++;
	 NewRoute=NextRoute->RLink[NextCol];
	 NewCol=NextRoute->Colm[NextCol];
	 NextRoute=NewRoute;
	 NextCol=NewCol;
	 }
       if ( Count<5 )
	 {
	 From->WorkList=CountLink[Count];
	 CountLink[Count]=From;
	 }
       From++;
       }
      From = CountLink[0];
      if ( From !=0 )
       {
       printf("Following Cities have NO Roads !?!...\n");
       printf(">>> connect or eliminate them!\n");
       while (From != 0)
	   {
	   printf(" %s\n",From->CityName);
	   From = From->WorkList;
	   }
       }
      for (Count=1; Count<=3; Count++)
        {
        From = CountLink[Count];
        if ( From!=0 )
         {
         printf("Following Cities have %d Roads...\n",Count);
         printf(">>> you could save space if they were not needed!\n");
         while (From != 0)
           {
           printf(" %s,%s ",From->CityName,From->StateName);
           Ct0='[';
           NextRoute=From->RoadList;
           NextCol=From->Colum;
           while (NextRoute != 0)
             {
             Dest=NextRoute->CityNum[1-NextCol];
	     printf("%c%s",Ct0,Dest->CityName);
             NewRoute=NextRoute->RLink[NextCol];
             NewCol=NextRoute->Colm[NextCol];
             NextRoute=NewRoute;
             NextCol=NewCol;
	     Ct0='-';
	     } /* wend, connecting-city list loop */

	   printf("]\n");
	   From = From->WorkList;
	   }  /* wend, next city for this count-list */
         }  /* endif count-list not empty */
        }   /* next count-list  */
      Ct0=0;
      for (ScanRoute=Route0; ScanRoute<Route9; ScanRoute++)
        {
        TrailPoint[0]=0;
        TrailPoint[1]=0;
        From=ScanRoute->CityNum[0];
        Dest=ScanRoute->CityNum[1];
	if ( Navigate(From,Dest)>1 )
	      {
              if (Ct0==0)
                 printf("... Following DIRECT routes are not shortest!\n");
              Ct0=1;
	      printf("%s,%s->%s \n",
	         From->CityName,From->StateName,Dest->CityName);
              }
        }           /* next Road to analyze */
      break;
    case 1:         /* trouble in file data */
      fprintf(stderr,"----> Correct data in file %s and try again.\n",Active);
      break;
    case 2:         /* AllocMem refused */
        fprintf(stderr,"----> Not enough memory to run RoadRoute.\n");
	break;
    case 3:         /* real trouble with file */
        fprintf(stderr,"----> Can't proceed due to unreadable file %s.\n",Active);
        break;
    default:
      fprintf(stderr,"System error: %d\n",errnum);
    }  /* error switch area */
  switch (AllocCount)
    {
    case 5:  FreeMem(RoutePoint,RoutePSize);
    case 4:  FreeMem( (char *) RouteBlox,RouteSize);
    case 3:  FreeMem(CityPoint,CityPSize);
    case 2:  FreeMem( (char *) CityBlox,CitySize);
    case 1:  FreeMem( (char *) fibb,INFOSIZE);
    }  /* memory cleanup */
  if (errnum != 0)
    {
    fprintf(stderr,"Press any key to quit\n");
    gets(InBuff);
    }	
  }


void TimeShow(Time, Buffer)
  unsigned short Time;
  char *Buffer;
  {
  unsigned short MinFlag, radix, digit, SuppressLimit, FillChar, Hours[2];
  Hours[0]=Time/60;
  Hours[1]=Time%60;
  SuppressLimit=1;
  FillChar=':';
  radix=10000;
  while (radix>Hours[0] && radix>SuppressLimit)
    {
    radix/=10;
    *Buffer++ =' ';
    }
  for (MinFlag=0;MinFlag<2;MinFlag++)
    {
    while (radix>0)
      {
      digit=Hours[MinFlag]/radix;
      Hours[MinFlag]%=radix;
      *Buffer++ =digit+'0';
      radix/=10;
      }  /* more digits */
    *Buffer++ =FillChar;
    FillChar=0;
    SuppressLimit=10;
    radix=10;
    }  /* next MinFlag */
  }

int CityMatch(TabPoint,CityText)
  struct CityData *TabPoint;
  char *CityText;
  {
  /* Name must match exactly; state is optional */
  int Match, StateMatch;
  char TablChar, TextChar;
  char *TableName;
  TableName=TabPoint->CityName;
  TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
  TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
  Match=1;
  StateMatch=0;
  while (Match == 1 && TextChar != ',')
    {
    if (TablChar != TextChar)
      {
      if (TablChar ==',' && TextChar =='/') StateMatch=1;
      else Match=0;
      }
    TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
    TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
    }
  if (Match==1)
    {
    if (TablChar != 0 && TablChar !=',') Match=0;
    if (TabPoint->MinDist[0]==1 && StateMatch ==0) Match=0;
    }
  return (Match);
  }

unsigned short ParseCities(CitiesBlock,CBlockSize)
  char *CitiesBlock;
  long CBlockSize;
  {
  struct CityData *CityStruct, *CityScan;
  char *LineBegin, *EndLine, *NewName, *OldName;
  unsigned short CityError;
  unsigned char CityIndex,NewChar,OldChar;
  unsigned char FoundFlag, StateFlag;
  CityError=0;
  CityStruct = City0;
  LineBegin = CitiesBlock;
  FoundFlag=0;
  for (EndLine=CitiesBlock;EndLine < CitiesBlock+CBlockSize;EndLine++)
  if (*EndLine == ',' || *EndLine == 0x0A)
    {
    if (*EndLine == ',')
      {
      FoundFlag=1;
      CityStruct->CityName=LineBegin;
      /* MinDist[0] used as temporary dupe CityName flag */
      CityStruct->MinDist[0]=0;          /* No City Duplicate Name */
      CityIndex = *LineBegin & 0x1F;        /* strip first char */
      CityScan = CharLink[CityIndex];
      while (CityScan != 0)
        {
        NewName=LineBegin;
        OldName=CityScan->CityName;
        NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
        OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
        while (NewChar == OldChar && NewChar != ',')
          {
          NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
          OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
          }
        if (NewChar == OldChar)     /* Dupe City Name */
          {
          CityStruct->MinDist[0]=1;
          CityScan->MinDist[0]=1;
          }
        CityScan = CityScan->CityLink;
        }   /* chain search for input city name */
       CityStruct->CityLink = CharLink[CityIndex];
      CityStruct->RoadList = 0;
      CharLink[CityIndex]=CityStruct;
      LineBegin=EndLine+1;
      }    /* end of comma..City parsing */
    else     /* NewLine */
      {
      *EndLine=0;
      if (FoundFlag ==0)
        {
        fprintf(stderr,"*FILE Cities: NO COMMA:\n%s\n",LineBegin);
        CityError=1;
        }
      FoundFlag=0;
      CityStruct->StateName=LineBegin;
      CityStruct->StateDupe=1;
      CityIndex = *LineBegin & 0x1F;        /* strip first char */
      CityScan = ChStLink[CityIndex];
      StateFlag = 0;
      while (CityScan != 0 && StateFlag == 0)
        {
        NewName=LineBegin;
        OldName=CityScan->StateName;
        NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
        OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
        while (NewChar == OldChar && NewChar !=0 && OldChar !=0)
          {
          NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
          OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
          }
        if (NewChar == OldChar)
          {
          CityScan->StateDupe=0;
          StateFlag=1;
          }
        CityScan = CityScan->StateLink;
        }   /* more states in chain */
      CityStruct->StateLink = ChStLink[CityIndex];
      ChStLink[CityIndex]=CityStruct;
      CityStruct++;
      LineBegin=EndLine+1;
      }    /* end of NewLine parsing */
    }
  City9=CityStruct;
  return(CityError);
  }

unsigned short ParseRoutes(DataBlock,BlockSize)
  char *DataBlock;
  long BlockSize;
  {
  struct RouteData *RouteStruct;
  struct CityData *CityScan, *FoundCity;
  unsigned short ErrorFlag, CityColm, CityFlag, CityValue, Multiplier;
  unsigned char CtNameKey, Digit;
  char *LineStart,*LineEnd,*FieldStart,*FieldEnd,*NumPtr;
  ErrorFlag=0;
  RouteStruct = Route0;
  LineStart = DataBlock;
  for (LineEnd=DataBlock;LineEnd < DataBlock+BlockSize;LineEnd++)
  if (*LineEnd == 0x0A)
    {
    *LineEnd=0;
    FieldStart=LineStart;
    for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
      {
      for (FieldEnd=FieldStart ;
             *FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
      if (*FieldEnd !=',')
        {
        fprintf(stderr,"*FILE Roads:  MISSING FIELDS:\n%s\n",LineStart);
        ErrorFlag=1;
        }   /* no comma! */
      /* ***** search city name chain */
      CtNameKey = *FieldStart & 0x1F;        /* strip first char */
      CityScan = CharLink[CtNameKey];
      CityValue =0;
      while (CityScan != 0 && CityValue ==0)
        {
        if (CityMatch(CityScan,FieldStart)==1)
          {
          CityValue=1;
          FoundCity=CityScan;
          }
        CityScan = CityScan->CityLink;
        }   /* chain search for input city name */	  
      if (CityValue ==0)
        {
        fprintf(stderr,"*FILE Roads:  CITY NOT FOUND:\n%s\n",LineStart);
        ErrorFlag=1;
        }
      RouteStruct->CityNum[CityColm]=FoundCity;
      RouteStruct->RLink[CityColm]=FoundCity->RoadList;
      RouteStruct->Colm[CityColm]=FoundCity->Colum;
      FoundCity->RoadList=RouteStruct;
      FoundCity->Colum=CityColm;
      FieldStart=FieldEnd+1;
      }   /* two-city loop */
    /* Now grab mileage, time, and Hiway */
    for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
      {
      for (FieldEnd=FieldStart ;
                *FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
      if (*FieldEnd !=',')
        {
        fprintf(stderr,"FILE Roads:  MISSING FIELDS:\n%s????\n",LineStart);
        ErrorFlag=1;
        }   /* no comma! */
      CityValue=0 ; CityFlag=0;
      Multiplier=10;
      for (NumPtr=FieldStart ; CityFlag==0 && NumPtr < FieldEnd ;
                                                          NumPtr++)
        {
        Digit=*NumPtr;
        if (Digit >='0' && Digit<='9')
          {
          CityValue=CityValue * Multiplier + Digit - '0';
          Multiplier=10;
          }
        else if (Digit ==':') Multiplier = 6;
        }  /* Scan for colon */
      RouteStruct->Dist[CityColm]=CityValue;
      FieldStart=FieldEnd+1;
      }    /* Two value paramemters */
    RouteStruct->Hiway=FieldStart;
    RouteStruct++;
    LineStart=LineEnd+1;
    }    /* end of routefile scan */
  Route9 = RouteStruct;
  return(ErrorFlag);
  }   /* if no error, table build */

#define MENUSIZE 30

unsigned short Navigate(struct CityData *Start,struct CityData *Finish)
  {
  unsigned short Column, Travel;
  unsigned short NextCol, NewCol;
  struct CityData *CityScan;
  struct CityData *BLink, *SearchCity;
  struct CityData *ELink, *FLink, *OtherCity;
  struct RouteData *NextRoute, *NewRoute;
  static unsigned short MiniVal;
  static unsigned short ThisDist[2], LCount[2];
        for (CityScan=City0; CityScan<City9; CityScan++)
          {
          CityScan->WorkList = 0;
          for (Column=0; Column<2; Column++)
            {
            CityScan->MinDist[Column]=9999;
            CityScan->NextCity[Column]=0;
            }
          }
        ELink=Finish;
        MiniVal=0;
        for (Column=0; Column<2; Column++)
          {
          Finish->MinDist[Column]=0;
          ThisDist[Column]=9999;
          }
        SearchCity=Finish;       
        while (SearchCity != 0)
          {
          for (Column=0; Column<2; Column++)
            {
            if (SearchCity->MinDist[Column] < Start->MinDist[Column])
              {
    /*   if (Column==0)
     *   printf("Scanning map at range: %d\n",SearchCity->MinDist[0]); */
              MiniVal=SearchCity->MinDist[Column];
              NextRoute=SearchCity->RoadList;
              NextCol=SearchCity->Colum;
              while (NextRoute != 0)
                {
                OtherCity=NextRoute->CityNum[1-NextCol];
                Travel=MiniVal+NextRoute->Dist[Column];
                if (OtherCity->MinDist[Column] > Travel)
                  /* found a new shortest path */
                  {
                  OtherCity->MinDist[Column]=Travel;
                  OtherCity->NextCity[Column]=SearchCity;
                  if (OtherCity->WorkList == 0 && ELink!=OtherCity)
                    {
                    BLink=SearchCity;
                    FLink=SearchCity->WorkList;
                    while (FLink!=0 && Travel>FLink->MinDist[Column])
                      {
                      BLink=FLink;
                      FLink=BLink->WorkList;
                      }
                    BLink->WorkList=OtherCity;
                    OtherCity->WorkList=FLink;
                    if (FLink==0) ELink=OtherCity;
                    }  /* build new Worklist */
                  }    /* shorter total distance */
                if (Travel < ThisDist[Column]) ThisDist[Column]=Travel; 
                NewRoute=NextRoute->RLink[NextCol];
                NewCol=NextRoute->Colm[NextCol];
                NextRoute=NewRoute;
                NextCol=NewCol;
                }   /* Try another route from SearchCity */
              }     /* if Search City within target range */
            }       /* Next Column (Mileage/Time) */
          BLink=SearchCity->WorkList;
          SearchCity->WorkList=0;
          SearchCity=BLink;
          }  /* if SearchCity not zero, go back */
        for (Column=0; Column<2; Column++)
          {
          LCount[Column]=0;
          SearchCity=Start;
          FLink=SearchCity->NextCity[Column];
          while (FLink != 0)
            {
            LCount[Column]+=1;
            Trail[TrailPoint[Column]++][Column]=FLink;
            SearchCity=FLink;
            FLink=SearchCity->NextCity[Column];
            }  /* wend for next FLink */
          }    /* next Column */
  MiniVal=LCount[0];
  if (MiniVal<LCount[1]) MiniVal=LCount[1];
  return(MiniVal);
  }