home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 391.lha / RoadRoute_v1.5 / RoadRoute.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-07-03  |  29.1 KB  |  854 lines
  1. /* after years of fiddling..
  2.   'v1.0  September 89
  3. 'Jim Butterfield  */
  4.  
  5.    /* compile with lc -Lcd -v <filename> */
  6. #include <proto/exec.h>
  7. #include <proto/dos.h>
  8. #include <stdio.h>
  9. #define BUFFERLINE 50
  10. #define INFOSIZE sizeof(struct FileInfoBlock)
  11. #define TRAILLEN 100
  12.  
  13. /* File Support structures */
  14. struct CityData {
  15.                 char *CityName;              /* full name  w/state */
  16.                 char *StateName;             /* state/province only */
  17.                 struct CityData *CityLink;   /* init letter chain */
  18.                 struct CityData *StateLink;  /* init letter chain */
  19.                 struct RouteData *RoadList;  /* roads to/from city */
  20.                 struct CityData *WorkList;   /* temp job queue */
  21.                 struct CityData *NextCity[2];  /* result links */
  22.       /* Mindist[0] doubles as CityDupe flag during file input */
  23.                 unsigned short MinDist[2];   /* closest so far */
  24.                 unsigned char StateDupe;     /* one name per state */
  25.                 unsigned char Colum;         /* goes with RoadList */
  26.                 };
  27. struct RouteData {
  28.                  struct CityData *CityNum[2];  /* cities each end */
  29.                  unsigned short Dist[2];       /* distance, time */
  30.                  char *Hiway;                  /* name of Highway */
  31.                  struct RouteData *RLink[2];   /* link for each city */
  32.                  unsigned char Colm[2];        /* goes with RLink */
  33.                  };
  34. struct RouteData *Route0, *Route9;
  35. struct CityData *City0, *City9;
  36. struct CityData *CharLink[0x20];
  37. struct CityData *ChStLink[0x20];
  38. static char InBuff[BUFFERLINE];
  39. static struct CityData *Trail[TRAILLEN][2];
  40. unsigned short TrailPoint[2];
  41. void TimeShow(unsigned short,char *);
  42. int CityMatch(struct CityData *,char *);
  43. unsigned short ParseCities(char *,long);
  44. unsigned short ParseRoutes(char *,long);
  45. struct CityData * AskCity();
  46. void Navigate(struct CityData *,struct CityData *);
  47. void main()
  48.   {
  49.   long fh, lok;
  50.   unsigned short Column, ColStart, ColEnd;
  51.   unsigned short NextCol, NewCol;
  52.   unsigned short AllocCount, errnum;
  53.   unsigned short TrackTrail;
  54.   struct FileInfoBlock *fibb;
  55.   long CitySize, RouteSize;
  56.   char *CityBlox, *RouteBlox, *DataScan, *Active;
  57.   char *StringStart, *FieldStart;
  58.   char *CityPoint, *RoutePoint;
  59.   struct CityData *From, *Dest, *Via, *SearchCity;
  60.   struct CityData *FLink;
  61.   struct RouteData *NextRoute, *NewRoute;
  62.   unsigned short Cities, Roads;
  63.   unsigned short CityPSize, RoutePSize;
  64.   unsigned char Ct0;             /* general character work value */
  65.   static unsigned short Result[2][2];
  66.   static unsigned short tTime, tMiles;
  67.   static char ActCity[]="Cities";
  68.   static char ActRoad[]="Roads";
  69.   for (Ct0=0; Ct0 < 0x20; Ct0++) CharLink[Ct0]= 0;
  70.   for (Ct0=0; Ct0 < 0x20; Ct0++) ChStLink[Ct0]= 0;
  71.  
  72.   AllocCount=0;
  73.   errnum=2;                   /* no memory */
  74.   if ( (long) (fibb = (struct FileInfoBlock *) AllocMem(INFOSIZE,0L))
  75.                                                                 != 0L)
  76.     {
  77.     AllocCount=1;
  78.     errnum=3;                   /* file problems */
  79.     fprintf(stderr,"RoadRoute V1.5  ..   Jim Butterfield\n");
  80.     fprintf(stderr,"   Release version:  1990 04 09\n");
  81.     Cities=0;
  82.     Active=ActCity;
  83.     if ( (lok = Lock("Cities",ACCESS_READ)) != 0L)
  84.       {
  85.       if ( (fh=Examine(lok,fibb)) !=0L)
  86.         {
  87.         CitySize=fibb->fib_Size;
  88.         if ( (long) (CityBlox = AllocMem(CitySize,0L)) != 0L)
  89.       {
  90.           AllocCount=2;
  91.           if ( (fh = Open("Cities",MODE_OLDFILE)) != 0L)
  92.             {
  93.             errnum=0;
  94.             Read(fh,CityBlox,CitySize);
  95.             Close(fh);
  96.         }                      /* City file opened   */
  97.           }                        /* data alloc OK */
  98.     }                          /* examine OK    */
  99.         UnLock(lok);
  100.       }                            /* lock OK          */
  101.     }                              /* examine alloc OK */
  102.   if (errnum == 0)
  103.     {
  104.     for (DataScan=CityBlox;DataScan < CityBlox+CitySize;DataScan++)
  105.       if (*DataScan == 0x0A) Cities++;
  106.     CityPSize=Cities*sizeof(struct CityData);
  107.     if ( (long) (CityPoint = AllocMem(CityPSize,0L)) != 0L)
  108.       AllocCount=3;
  109.     else
  110.       errnum=2;
  111.     }
  112.   if (errnum ==0 )
  113.     {
  114.     errnum=3;                   /* file problems */
  115.     Active=ActRoad;
  116.     Roads=0;
  117.     if ( (lok = Lock("Roads",ACCESS_READ)) != 0L)
  118.       {
  119.       if ( (fh=Examine(lok,fibb)) !=0L)
  120.         {
  121.         RouteSize=fibb->fib_Size;
  122.         if ( (long) (RouteBlox = AllocMem(RouteSize,0L)) != 0L)
  123.           {
  124.           AllocCount=4;
  125.           if ( (fh = Open("Roads",MODE_OLDFILE)) != 0L)
  126.             {
  127.             errnum=0;
  128.             Read(fh,RouteBlox,RouteSize);
  129.             Close(fh);
  130.             }                      /* file opened   */
  131.           }                        /* data alloc OK */
  132.         }                          /* examine OK    */
  133.       UnLock(lok);
  134.       }                            /* lock OK          */
  135.     }
  136.   if (errnum == 0)
  137.     {
  138.     for (DataScan=RouteBlox;DataScan < RouteBlox+RouteSize;DataScan++)
  139.       if (*DataScan == 0x0A) Roads++;
  140.     RoutePSize=Roads*sizeof(struct RouteData);
  141.     if ( (long) (RoutePoint = AllocMem(RoutePSize,0L)) != 0L)
  142.       AllocCount=5;
  143.     else
  144.       errnum=2;
  145.     }
  146.   if (errnum == 0)
  147.     {
  148.     Active=ActCity;
  149.     fprintf(stderr,">> %d Cities\n",Cities);
  150.     City0 = (struct CityData *) CityPoint;
  151.     errnum=ParseCities(CityBlox,CitySize);
  152.     }
  153.   if (errnum == 0)
  154.     {
  155.     Active=ActRoad;
  156.     fprintf(stderr,">> %d Roads\n",Roads);
  157.     Route0 = (struct RouteData *) RoutePoint;
  158.     errnum=ParseRoutes(RouteBlox,RouteSize);
  159.     }
  160.   switch (errnum)
  161.     {
  162.     case 0:                /* no errors, do main job */
  163.       Ct0='Y';
  164.       while (Ct0 == 'Y')
  165.         {
  166.         TrailPoint[0]=0;
  167.         TrailPoint[1]=0;
  168.         fprintf(stderr,"City from: ");
  169.         if (gets(InBuff) == 0 || *InBuff =='\0')  From=City0;
  170.                       else      From=AskCity();
  171.         fprintf(stderr,"From %s to: ",From->CityName);
  172.         if (gets(InBuff) == 0)
  173.           {
  174.           InBuff[0]='?';
  175.           InBuff[1]='\0';
  176.           }
  177.         Dest=AskCity();
  178.         fprintf(stderr,"%s->%s via (or RETURN):  ",
  179.                                   From->CityName,Dest->CityName);
  180.         Via=0;
  181.         if (gets(InBuff) != 0 && *InBuff != '\0')
  182.           {
  183.           Via = AskCity();
  184.           fprintf(stderr,"\n%s->%s via %s\n",
  185.                   From->CityName,Dest->CityName,Via->CityName);
  186.           Navigate(From,Via);
  187.           Navigate(Via,Dest);
  188.           }
  189.         else
  190.           {
  191.           fprintf(stderr,"\n%s->%s DIRECT\n",From->CityName,Dest->CityName);
  192.           Navigate(From,Dest);
  193.           }
  194.         for (Column=0; Column<2; Column++)
  195.           {
  196.           Result[0][Column]=0;   /* dist */
  197.           Result[1][Column]=0;   /* time */
  198.           SearchCity=From;
  199.           for (TrackTrail=0; TrackTrail <TrailPoint[Column]; TrackTrail++)
  200.             {
  201.             FLink=Trail[TrackTrail][Column];
  202.             NextRoute=SearchCity->RoadList;
  203.             NextCol=SearchCity->Colum;
  204.             while (NextRoute !=0 &&
  205.                    FLink != NextRoute->CityNum[1-NextCol]) 
  206.               {
  207.               NewRoute=NextRoute->RLink[NextCol];
  208.               NewCol=NextRoute->Colm[NextCol];
  209.               NextRoute=NewRoute;
  210.               NextCol=NewCol;
  211.               }
  212.             Result[1][Column]=Result[1][Column]+NextRoute->Dist[1];
  213.             Result[0][Column]=Result[0][Column]+NextRoute->Dist[0];
  214.             SearchCity=FLink;
  215.             }  /* next Link */
  216.           }    /* next Column */
  217.         ColStart=0;
  218.         ColEnd=1;
  219.         if (Result[0][0]==Result[0][1])
  220.           {
  221.           ColStart=1;
  222.           ColEnd=1;
  223.           }
  224.         if (Result[1][0]==Result[1][1])
  225.           {
  226.           ColStart=0;
  227.           ColEnd=0;
  228.           }
  229.         for (Column=ColStart; Column<=ColEnd; Column++)
  230.           {
  231.           fprintf(stderr,"%4d Miles, time: ",Result[0][Column]);
  232.           TimeShow(Result[1][Column],InBuff);
  233.           fprintf(stderr,"%s\n",InBuff);
  234.           } /* next Column */
  235.         if (ColStart != ColEnd)
  236.           {
  237.           Ct0='B';
  238.           fprintf(stderr,"FASTEST, SHORTEST (or BOTH) ");
  239.           if ((StringStart=gets(InBuff)) != 0) Ct0=*StringStart;
  240.           if (Ct0 > 'Z') Ct0 -=32;
  241.           if (Ct0 =='S') ColEnd=0;
  242.           if (Ct0 =='F') ColStart=1;
  243.           }    /* fastest/shortest question */
  244.         else
  245.           {
  246.           fprintf(stderr,"Press any key to continue\n");
  247.       gets(InBuff);
  248.           }
  249.         for (Column=ColStart; Column<=ColEnd; Column++)
  250.           {
  251.           printf ("From: %s\nTo: %s\n",From->CityName,Dest->CityName);
  252.           if (Via != 0) printf ("Via: %s\n",Via->CityName);
  253.           tMiles=0;
  254.           tTime=0;
  255.           SearchCity=From;
  256.           for (TrackTrail=0; TrackTrail <TrailPoint[Column]; TrackTrail++)
  257.             {
  258.             FLink=Trail[TrackTrail][Column];
  259.             NextRoute=SearchCity->RoadList;
  260.             NextCol=SearchCity->Colum;
  261.             while (NextRoute > 0 && 
  262.                    FLink!=NextRoute->CityNum[1-NextCol]) 
  263.               {
  264.               NewRoute=NextRoute->RLink[NextCol];
  265.               NewCol=NextRoute->Colm[NextCol];
  266.               NextRoute=NewRoute;
  267.               NextCol=NewCol;
  268.               }   /* wend, no NextRoute */
  269.             tTime=tTime+NextRoute->Dist[1];
  270.             tMiles=tMiles+NextRoute->Dist[0];
  271.             TimeShow(NextRoute->Dist[1],InBuff);
  272.             /*  Print highway link information */
  273.             printf("%4d %s ",NextRoute->Dist[0],InBuff);
  274.             StringStart=InBuff;
  275.             FieldStart=SearchCity->CityName;
  276.             while (*FieldStart != ',')
  277.               *StringStart++ =*FieldStart++;
  278.             *StringStart++ =' ';
  279.             *StringStart++ ='-';
  280.             *StringStart++ =' ';
  281.             FieldStart=FLink->CityName;
  282.             while (*FieldStart != ',')
  283.               *StringStart++ =*FieldStart++;
  284.             *StringStart++ =0;
  285.             printf("%s via %s\n",InBuff,NextRoute->Hiway);
  286.             SearchCity=FLink;
  287.             }  /* next link */
  288.           printf ("     Total Miles: %d\n",tMiles);
  289.           TimeShow(tTime,InBuff);
  290.           printf ("     Driving Time: %s\n",InBuff);
  291.           }  /* next Column */
  292.         Ct0='N';
  293.         fprintf (stderr,"Another trip? ");
  294.         if ((StringStart=gets(InBuff)) != 0) Ct0=*StringStart;
  295.         if (Ct0 > 'Z') Ct0 -=32;
  296.         }           /* another trip */
  297.       break;
  298.     case 1:         /* trouble in file data */
  299.       fprintf(stderr,"----> Correct data in file %s and try again.\n",Active);
  300.       break;
  301.     case 2:         /* AllocMem refused */
  302.         fprintf(stderr,"----> Not enough memory to run RoadRoute.\n");
  303.     break;
  304.     case 3:         /* real trouble with file */
  305.         fprintf(stderr,"----> Can't proceed due to unreadable file %s.\n",Active);
  306.         break;
  307.     default:
  308.       fprintf(stderr,"System error: %d\n",errnum);
  309.     }  /* error switch area */
  310.   switch (AllocCount)
  311.     {
  312.     case 5:  FreeMem(RoutePoint,RoutePSize);
  313.     case 4:  FreeMem( (char *) RouteBlox,RouteSize);
  314.     case 3:  FreeMem(CityPoint,CityPSize);
  315.     case 2:  FreeMem( (char *) CityBlox,CitySize);
  316.     case 1:  FreeMem( (char *) fibb,INFOSIZE);
  317.     }  /* memory cleanup */
  318.   if (errnum != 0)
  319.     {
  320.     fprintf(stderr,"Press any key to quit\n");
  321.     gets(InBuff);
  322.     }    
  323.   }
  324.  
  325.  
  326. void TimeShow(Time, Buffer)
  327.   unsigned short Time;
  328.   char *Buffer;
  329.   {
  330.   unsigned short MinFlag, radix, digit, SuppressLimit, FillChar, Hours[2];
  331.   Hours[0]=Time/60;
  332.   Hours[1]=Time%60;
  333.   SuppressLimit=1;
  334.   FillChar=':';
  335.   radix=10000;
  336.   while (radix>Hours[0] && radix>SuppressLimit)
  337.     {
  338.     radix/=10;
  339.     *Buffer++ =' ';
  340.     }
  341.   for (MinFlag=0;MinFlag<2;MinFlag++)
  342.     {
  343.     while (radix>0)
  344.       {
  345.       digit=Hours[MinFlag]/radix;
  346.       Hours[MinFlag]%=radix;
  347.       *Buffer++ =digit+'0';
  348.       radix/=10;
  349.       }  /* more digits */
  350.     *Buffer++ =FillChar;
  351.     FillChar=0;
  352.     SuppressLimit=10;
  353.     radix=10;
  354.     }  /* next MinFlag */
  355.   }
  356.  
  357. int CityMatch(TabPoint,CityText)
  358.   struct CityData *TabPoint;
  359.   char *CityText;
  360.   {
  361.   /* Name must match exactly; state is optional */
  362.   int Match, StateMatch;
  363.   char TablChar, TextChar;
  364.   char *TableName;
  365.   TableName=TabPoint->CityName;
  366.   TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
  367.   TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
  368.   Match=1;
  369.   StateMatch=0;
  370.   while (Match == 1 && TextChar != ',')
  371.     {
  372.     if (TablChar != TextChar)
  373.       {
  374.       if (TablChar ==',' && TextChar =='/') StateMatch=1;
  375.       else Match=0;
  376.       }
  377.     TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
  378.     TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
  379.     }
  380.   if (Match==1)
  381.     {
  382.     if (TablChar != 0 && TablChar !=',') Match=0;
  383.     if (TabPoint->MinDist[0]==1 && StateMatch ==0) Match=0;
  384.     }
  385.   return (Match);
  386.   }
  387.  
  388. unsigned short ParseCities(CitiesBlock,CBlockSize)
  389.   char *CitiesBlock;
  390.   long CBlockSize;
  391.   {
  392.   struct CityData *CityStruct, *CityScan;
  393.   char *LineBegin, *EndLine, *NewName, *OldName;
  394.   unsigned short CityError;
  395.   unsigned char CityIndex,NewChar,OldChar;
  396.   unsigned char FoundFlag, StateFlag;
  397.   CityError=0;
  398.   CityStruct = City0;
  399.   LineBegin = CitiesBlock;
  400.   FoundFlag=0;
  401.   for (EndLine=CitiesBlock;EndLine < CitiesBlock+CBlockSize;EndLine++)
  402.   if (*EndLine == ',' || *EndLine == 0x0A)
  403.     {
  404.     if (*EndLine == ',')
  405.       {
  406.       FoundFlag=1;
  407.       CityStruct->CityName=LineBegin;
  408.       /* MinDist[0] used as temporary dupe CityName flag */
  409.       CityStruct->MinDist[0]=0;          /* No City Duplicate Name */
  410.       CityIndex = *LineBegin & 0x1F;        /* strip first char */
  411.       CityScan = CharLink[CityIndex];
  412.       while (CityScan != 0)
  413.         {
  414.         NewName=LineBegin;
  415.         OldName=CityScan->CityName;
  416.         NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  417.         OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  418.         while (NewChar == OldChar && NewChar != ',')
  419.           {
  420.           NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  421.           OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  422.           }
  423.         if (NewChar == OldChar)     /* Dupe City Name */
  424.           {
  425.           CityStruct->MinDist[0]=1;
  426.           CityScan->MinDist[0]=1;
  427.           }
  428.         CityScan = CityScan->CityLink;
  429.         }   /* chain search for input city name */
  430.        CityStruct->CityLink = CharLink[CityIndex];
  431.       CityStruct->RoadList = 0;
  432.       CharLink[CityIndex]=CityStruct;
  433.       LineBegin=EndLine+1;
  434.       }    /* end of comma..City parsing */
  435.     else     /* NewLine */
  436.       {
  437.       *EndLine=0;
  438.       if (FoundFlag ==0)
  439.         {
  440.         fprintf(stderr,"*FILE Cities: NO COMMA:\n%s\n",LineBegin);
  441.         CityError=1;
  442.         }
  443.       FoundFlag=0;
  444.       CityStruct->StateName=LineBegin;
  445.       CityStruct->StateDupe=1;
  446.       CityIndex = *LineBegin & 0x1F;        /* strip first char */
  447.       CityScan = ChStLink[CityIndex];
  448.       StateFlag = 0;
  449.       while (CityScan != 0 && StateFlag == 0)
  450.         {
  451.         NewName=LineBegin;
  452.         OldName=CityScan->StateName;
  453.         NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  454.         OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  455.         while (NewChar == OldChar && NewChar !=0 && OldChar !=0)
  456.           {
  457.           NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  458.           OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  459.           }
  460.         if (NewChar == OldChar)
  461.           {
  462.           CityScan->StateDupe=0;
  463.           StateFlag=1;
  464.           }
  465.         CityScan = CityScan->StateLink;
  466.         }   /* more states in chain */
  467.       CityStruct->StateLink = ChStLink[CityIndex];
  468.       ChStLink[CityIndex]=CityStruct;
  469.       CityStruct++;
  470.       LineBegin=EndLine+1;
  471.       }    /* end of NewLine parsing */
  472.     }
  473.   City9=CityStruct;
  474.   return(CityError);
  475.   }
  476.  
  477. unsigned short ParseRoutes(DataBlock,BlockSize)
  478.   char *DataBlock;
  479.   long BlockSize;
  480.   {
  481.   struct RouteData *RouteStruct;
  482.   struct CityData *CityScan, *FoundCity;
  483.   unsigned short ErrorFlag, CityColm, CityFlag, CityValue, Multiplier;
  484.   unsigned char CtNameKey, Digit;
  485.   char *LineStart,*LineEnd,*FieldStart,*FieldEnd,*NumPtr;
  486.   ErrorFlag=0;
  487.   RouteStruct = Route0;
  488.   LineStart = DataBlock;
  489.   for (LineEnd=DataBlock;LineEnd < DataBlock+BlockSize;LineEnd++)
  490.   if (*LineEnd == 0x0A)
  491.     {
  492.     *LineEnd=0;
  493.     FieldStart=LineStart;
  494.     for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
  495.       {
  496.       for (FieldEnd=FieldStart ;
  497.              *FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
  498.       if (*FieldEnd !=',')
  499.         {
  500.         fprintf(stderr,"*FILE Roads:  MISSING FIELDS:\n%s\n",LineStart);
  501.         ErrorFlag=1;
  502.         }   /* no comma! */
  503.       /* ***** search city name chain */
  504.       CtNameKey = *FieldStart & 0x1F;        /* strip first char */
  505.       CityScan = CharLink[CtNameKey];
  506.       CityValue =0;
  507.       while (CityScan != 0 && CityValue ==0)
  508.         {
  509.         if (CityMatch(CityScan,FieldStart)==1)
  510.           {
  511.           CityValue=1;
  512.           FoundCity=CityScan;
  513.           }
  514.         CityScan = CityScan->CityLink;
  515.         }   /* chain search for input city name */      
  516.       if (CityValue ==0)
  517.         {
  518.         fprintf(stderr,"*FILE Roads:  CITY NOT FOUND:\n%s\n",LineStart);
  519.         ErrorFlag=1;
  520.         }
  521.       RouteStruct->CityNum[CityColm]=FoundCity;
  522.       RouteStruct->RLink[CityColm]=FoundCity->RoadList;
  523.       RouteStruct->Colm[CityColm]=FoundCity->Colum;
  524.       FoundCity->RoadList=RouteStruct;
  525.       FoundCity->Colum=CityColm;
  526.       FieldStart=FieldEnd+1;
  527.       }   /* two-city loop */
  528.     /* Now grab mileage, time, and Hiway */
  529.     for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
  530.       {
  531.       for (FieldEnd=FieldStart ;
  532.                 *FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
  533.       if (*FieldEnd !=',')
  534.         {
  535.         fprintf(stderr,"FILE Roads:  MISSING FIELDS:\n%s????\n",LineStart);
  536.         ErrorFlag=1;
  537.         }   /* no comma! */
  538.       CityValue=0 ; CityFlag=0;
  539.       Multiplier=10;
  540.       for (NumPtr=FieldStart ; CityFlag==0 && NumPtr < FieldEnd ;
  541.                                                           NumPtr++)
  542.         {
  543.         Digit=*NumPtr;
  544.         if (Digit >='0' && Digit<='9')
  545.           {
  546.           CityValue=CityValue * Multiplier + Digit - '0';
  547.           Multiplier=10;
  548.           }
  549.         else if (Digit ==':') Multiplier = 6;
  550.         }  /* Scan for colon */
  551.       RouteStruct->Dist[CityColm]=CityValue;
  552.       FieldStart=FieldEnd+1;
  553.       }    /* Two value paramemters */
  554.     RouteStruct->Hiway=FieldStart;
  555.     RouteStruct++;
  556.     LineStart=LineEnd+1;
  557.     }    /* end of routefile scan */
  558.   Route9 = RouteStruct;
  559.   return(ErrorFlag);
  560.   }   /* if no error, table build */
  561.  
  562. #define MENUSIZE 15
  563. struct CityData * AskCity()
  564.   {
  565.   char *InputString, *InputName, *TableName;
  566.   unsigned char MulKey, CityKey, InChar, CityChar, StateFlag;
  567.   struct CityData *CityStruct, *CityPStruct;
  568.   unsigned short MenuPointer, MenuList;
  569.   static struct CityData *Menu[MENUSIZE];
  570.  
  571.   InputString=InBuff;
  572.   CityKey = *InputString & 0x1F;        /* strip first char */
  573.   CityStruct = CharLink[CityKey];
  574.   MulKey = 0;              /* Single menu */
  575.   CityPStruct = 0;
  576.   MenuPointer = 0;
  577.   while (CityStruct != 0)
  578.     {
  579.     MenuPointer = 0;
  580.     while ( CityStruct !=0 && MenuPointer < MENUSIZE )
  581.       {
  582.       InputName=InputString;
  583.       TableName=CityStruct->CityName;
  584.       InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  585.       CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  586.       while (InChar == CityChar && InChar != 0)
  587.         {
  588.         InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  589.         CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  590.         }
  591.       if (InChar == 0)
  592.         {
  593.         Menu[MenuPointer++]=CityStruct;
  594.         CityPStruct = CityStruct;
  595.         }
  596.       CityStruct = CityStruct->CityLink;
  597.       }   /* chain search for input city name */
  598.     if ( MenuPointer > 1)
  599.       {
  600.       for (MenuList=0;MenuList < MenuPointer;MenuList++)
  601.         fprintf(stderr,"%d: %s\n",MenuList+1,Menu[MenuList]->CityName);
  602.       fprintf(stderr,">>> Pick 1 to %d:",MenuPointer);
  603.       if (CityStruct != 0)
  604.         {
  605.         fprintf(stderr," or RETURN for more:");
  606.         CityStruct = CityPStruct;
  607.     MulKey=1;           /* Multiple menus */
  608.         }
  609.       else if ( MulKey != 0 )
  610.         {
  611.         fprintf(stderr," or RETURN to restart list:");
  612.         CityStruct = CharLink[CityKey]; /* return to first menu */
  613.         }
  614.       StateFlag=0;
  615.       if ((InputString=gets(InBuff)) != 0)
  616.         {
  617.         InChar=*InputString++;
  618.         while (InChar != 0)
  619.           {
  620.           if (InChar >='0' && InChar<='9')
  621.                   StateFlag=StateFlag * 10 + InChar - '0';
  622.           InChar=*InputString++;
  623.           }
  624.         }     /* endif, not RETURN */
  625.       if (StateFlag < 1 || StateFlag > MenuPointer) StateFlag=1;
  626.         else  CityStruct = 0;
  627.       CityPStruct=Menu[StateFlag-1];      
  628.       }  /* endif cities to pick from */
  629.     }   /* while more cities in list */
  630.   switch (MenuPointer)
  631.     {
  632.     case 0:            /* No city match */
  633.       fprintf(stderr,"Province or State: ");
  634.       if ((InputString=gets(InBuff)) == 0) InputString=City0->CityName;
  635.       /* Search for state as input */
  636.       MenuPointer = 0;
  637.       Menu[MenuPointer]=City0;
  638.       CityKey = *InputString & 0x1F;    /* strip state first char */
  639.       CityStruct = ChStLink[CityKey];
  640.       if (CityStruct == 0) CityStruct = City0;
  641.       while (CityStruct != 0)
  642.         {
  643.         if (CityStruct->StateDupe == 1)   /* one flag set per state*/
  644.           {
  645.           InputName=InputString;
  646.           TableName=CityStruct->StateName;
  647.           InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  648.           CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  649.           while (InChar == CityChar && InChar != 0)
  650.             {
  651.             InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  652.             CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  653.             }
  654.           if (InChar == 0)
  655.             if (MenuPointer < MENUSIZE) Menu[MenuPointer++]=CityStruct;
  656.           }
  657.         CityStruct = CityStruct->StateLink;
  658.         }   /* more states in chain */
  659.       if (MenuPointer == 0)    /* search for first letter state */
  660.         {
  661.         CityStruct = ChStLink[CityKey];
  662.         if (CityStruct == 0) CityStruct = City0;
  663.         while (CityStruct != 0)
  664.           {
  665.           if (CityStruct->StateDupe == 1)
  666.             {
  667.             InputName=InputString;
  668.             TableName=CityStruct->StateName;
  669.             InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  670.             CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  671.             if (InChar == CityChar)
  672.               if (MenuPointer < MENUSIZE) Menu[MenuPointer++]=CityStruct;
  673.             }
  674.           CityStruct = CityStruct->StateLink;
  675.           }   /* while more states in alpha chain */
  676.         }  /* endif, single char state search */
  677.       if (MenuPointer > 1)
  678.         {
  679.         for (MenuList=0;MenuList < MenuPointer;MenuList++)
  680.           fprintf(stderr,"%d: %s\n",MenuList+1,Menu[MenuList]->StateName);
  681.         fprintf(stderr,">>> Pick 1 to %d:",MenuPointer);
  682.         StateFlag=0;
  683.         if ((InputString=gets(InBuff)) != 0)
  684.           {
  685.           InChar=*InputString++;
  686.           while (InChar != 0)
  687.             {
  688.             if (InChar >='0' && InChar<='9')
  689.               StateFlag=StateFlag * 10 + InChar - '0';
  690.             InChar=*InputString++;
  691.             }
  692.           if (StateFlag<1 || StateFlag>MenuPointer) StateFlag=1;
  693.           StateFlag -=1;
  694.           }
  695.         CityStruct=Menu[StateFlag];
  696.         }  /* endif, pick state from list */
  697.       if (MenuPointer == 0) CityStruct=City0;
  698.       if (MenuPointer == 1) CityStruct=Menu[0];
  699.       /* Now track cities within a given state */
  700.       InputString=CityStruct->StateName;
  701.       CityKey = *InputString & 0x1F;        /* strip first char */
  702.         /* Track the state alpha list */
  703.       MulKey=0;             /* not multiple menu */
  704.       CityStruct = ChStLink[CityKey];
  705.       CityPStruct = 0;
  706.       MenuPointer = 0;
  707.       while (CityStruct != 0)  /* search cities in a state */
  708.         {
  709.         MenuPointer = 0;
  710.         while ( CityStruct != 0  && MenuPointer < MENUSIZE )
  711.           {
  712.           InputName=InputString;
  713.           TableName=CityStruct->StateName;
  714.           InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  715.           CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  716.           while (InChar == CityChar && InChar != 0)
  717.             {
  718.             InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  719.             CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  720.             }
  721.           if (InChar == CityChar)
  722.         {
  723.             Menu[MenuPointer++]=CityStruct;
  724.             CityPStruct = CityStruct;
  725.             }
  726.           CityStruct = CityStruct->StateLink;
  727.           }   /* while more cities and space in menu */
  728.         if (MenuPointer > 1)
  729.           {
  730.           for (MenuList=0;MenuList < MenuPointer;MenuList++)
  731.             fprintf(stderr,"%d: %s\n",MenuList+1,Menu[MenuList]->CityName);
  732.           fprintf(stderr,">>> Pick 1 to %d:",MenuPointer);
  733.           if (CityStruct != 0)
  734.             {
  735.             fprintf(stderr," or RETURN for more:");
  736.             MulKey=1;      /* multiple menus */
  737.             CityStruct = CityPStruct;
  738.             }
  739.           else if ( MulKey != 0 )
  740.             {
  741.             fprintf(stderr," or RETURN for to restart list:");
  742.             CityStruct = ChStLink[CityKey]; /* back to first menu */
  743.             }
  744.           StateFlag=0;
  745.           if ((InputName=gets(InBuff)) != 0)
  746.             {
  747.             InChar=*InputName++;
  748.             while (InChar != 0)
  749.               {
  750.               if (InChar >='0' && InChar<='9')
  751.                 StateFlag=StateFlag * 10 + InChar - '0';
  752.               InChar=*InputName++;
  753.               }  /* while more numeric string */
  754.             }  /* endif, non-RETURN */
  755.           }              /* endif, pick city within state */
  756.         if (StateFlag < 1 || StateFlag > MenuPointer) StateFlag =1;
  757.           else  CityStruct = 0;
  758.         CityPStruct=Menu[StateFlag-1];
  759.         }     /* while more cities in state list */
  760.       if (MenuPointer == 0) CityPStruct=City0;
  761.       if (MenuPointer == 1) CityPStruct=Menu[0]; 
  762.       break;
  763.     case 1:             /* unique input city match */
  764.       CityPStruct = Menu[0];
  765.     }    /* endswitch, unique or no match */
  766.   return(CityPStruct);
  767.   }
  768.  
  769. void Navigate(struct CityData *Start,struct CityData *Finish)
  770.   {
  771.   unsigned short Column, Travel;
  772.   unsigned short NextCol, NewCol;
  773.   struct CityData *CityScan;
  774.   struct CityData *BLink, *SearchCity;
  775.   struct CityData *ELink, *FLink, *OtherCity;
  776.   struct RouteData *NextRoute, *NewRoute;
  777.   static unsigned short MiniVal;
  778.   static unsigned short ThisDist[2];
  779.         for (CityScan=City0; CityScan<City9; CityScan++)
  780.           {
  781.           CityScan->WorkList = 0;
  782.           for (Column=0; Column<2; Column++)
  783.             {
  784.             CityScan->MinDist[Column]=9999;
  785.             CityScan->NextCity[Column]=0;
  786.             }
  787.           }
  788.         ELink=Finish;
  789.         MiniVal=0;
  790.         for (Column=0; Column<2; Column++)
  791.           {
  792.           Finish->MinDist[Column]=0;
  793.           ThisDist[Column]=9999;
  794.           }
  795.         SearchCity=Finish;       
  796.         while (SearchCity != 0)
  797.           {
  798.           for (Column=0; Column<2; Column++)
  799.             {
  800.             if (SearchCity->MinDist[Column] < Start->MinDist[Column])
  801.               {
  802.     /*   if (Column==0)
  803.      *   printf("Scanning map at range: %d\n",SearchCity->MinDist[0]); */
  804.             MiniVal=SearchCity->MinDist[Column];
  805.             NextRoute=SearchCity->RoadList;
  806.             NextCol=SearchCity->Colum;
  807.             while (NextRoute != 0)
  808.                 {
  809.                 OtherCity=NextRoute->CityNum[1-NextCol];
  810.                 Travel=MiniVal+NextRoute->Dist[Column];
  811.                 if (OtherCity->MinDist[Column] > Travel)
  812.                   /* found a new shortest path */
  813.                   {
  814.                   OtherCity->MinDist[Column]=Travel;
  815.                   OtherCity->NextCity[Column]=SearchCity;
  816.                   if (OtherCity->WorkList == 0 && ELink!=OtherCity)
  817.                     {
  818.                     BLink=SearchCity;
  819.                     FLink=SearchCity->WorkList;
  820.                     while (FLink!=0 && Travel>FLink->MinDist[Column])
  821.                       {
  822.                       BLink=FLink;
  823.                       FLink=BLink->WorkList;
  824.                       }
  825.                     BLink->WorkList=OtherCity;
  826.                     OtherCity->WorkList=FLink;
  827.                     if (FLink==0) ELink=OtherCity;
  828.                     }  /* build new Worklist */
  829.                   }    /* shorter total distance */
  830.                 if (Travel < ThisDist[Column]) ThisDist[Column]=Travel; 
  831.                 NewRoute=NextRoute->RLink[NextCol];
  832.                 NewCol=NextRoute->Colm[NextCol];
  833.                 NextRoute=NewRoute;
  834.                 NextCol=NewCol;
  835.                 }   /* Try another route from SearchCity */
  836.               }     /* City within target range */
  837.             }       /* Next Column */
  838.           BLink=SearchCity->WorkList;
  839.           SearchCity->WorkList=0;
  840.           SearchCity=BLink;
  841.           }  /* if SearchCity not zero, go back */
  842.         for (Column=0; Column<2; Column++)
  843.           {
  844.           SearchCity=Start;
  845.           FLink=SearchCity->NextCity[Column];
  846.           while (FLink != 0)
  847.             {
  848.             if (TrailPoint[Column]<TRAILLEN)
  849.            Trail[TrailPoint[Column]++][Column]=FLink;
  850.             SearchCity=FLink;
  851.             FLink=SearchCity->NextCity[Column];
  852.             }  /* wend for next FLink */
  853.           }    /* next Column */
  854.   }