PROGRAM ttables(input,output);

   { The following declarations specify the manner in which time tables
     are represented. They MUST be INCLUDED in any time table program.}

      {  C O N S T   D E C L A R A T I O N S }

CONST
   minsperday = 1440;    {minutes in one day }
   numberofstations = 7;
   maxstringlength=12;   {the length of the longest station string PETER....}
   maxwait = 240;        {longest time between any  connexions}


      { T Y P E    D E C L A R A T I O N S }

TYPE

   mintime = 0..minsperday;    {internal representation of all times}
   hourtime = packed array[1..5] of char;
                               {external representation HH.MM }

   station = (edin, peter, ely, camb, lkx, lls, roy);
                               {internal representaion of  stations}
   stationstring = packed array[1..maxstringlength] of char;
                               {external representation of stations}

   changeinfoptr = ^changeinfo;
   changeinfo = record          { record any changes involved in a list}
                  place :station;   {at which change occurrs orllx for lls}
                  arrt :mintime;    {arrival time }
                  wait :0..maxwait; {interval before departure}
                  next :changeinfoptr
                end;

  journeyptr= ^journey;
  journey = record        { the basic time table entry }
             dept, arrt :mintime;   {time of (complete) journey}
             change1 :changeinfoptr;  { detail of change(s) or nil}
             marked :boolean;
             next :journeyptr
            end;

  ttableptr = ^ttable;
  ttable = record
             from, dest :station;   { all journeys are between these 2 places}
             first :journeyptr   { the first journey}
                                  { journeys are in ascending order of dept}
           end;


   {      C O N V E R S I O N       P R O C E D U R E S        }
     { needed between internal and external representations }
             { of times and of stations }


VAR
   i:integer;
   temp,ek,ep,pe,ec,kr,rc,lc:ttableptr;
   ttp1,ttp2,ttp3,ttp4,ttp5:ttableptr;
   f,d:station;

PROCEDURE mintohour(mt :mintime; var ht :hourtime); extern;
FUNCTION  hourtomin(ht :hourtime) :mintime; extern;
PROCEDURE stationtostr(st :station; var s :stationstring); extern;
FUNCTION  strtostation(s :stationstring) :station; extern;
                                {This is a crude comparison which looks
                                 only at key distinguishing characters!!}




  { I N P U T      A N D     O U T P U T   P R O C E D U R E S }
      { i.e. they read or print one time table }

PROCEDURE  readtt(var inp :text; var tt :ttableptr); extern;
                                                {Program halted if any
                                                 input errors detected!}
PROCEDURE writett (var out :text; tt :ttableptr); extern;
                                              { Prints one table in standard
                                                form on file "out"}


{     E N D    O F   P R E - D E F I N E D    P R O C E D U R E S }


PROCEDURE error(n:integer);
BEGIN
   writeln('***ERROR***');
   CASE n OF
      1: writeln('Attempt to CONNECT timetables of incompatible types.');
      2: writeln('Attempt to MERGE timetables of incompatible types.')
   END;
END;


FUNCTION copy(p1:changeinfoptr):changeinfoptr;
{  Returns a copy of a changeinfo list supplied as parameter.}
VAR
   p2:changeinfoptr;
BEGIN
   IF p1=nil THEN p2:=nil ELSE
   BEGIN
      new(p2);
      WITH p2^ DO
      BEGIN
         place:=p1^.place; arrt:=p1^.arrt; wait:=p1^.wait;
         next:=copy(p1^.next)
      END
   END;
   copy:=p2
END;


FUNCTION interval(t1,t2:mintime):mintime;
VAR
   t:integer;
BEGIN
   t:=t2-t1;
   IF t<0 THEN interval:=t+minsperday ELSE interval:=t
END;


FUNCTION makesconnection(abjp,bcjp:journeyptr; minwt,maxwt:mintime):boolean;
{  Determines whether two given journeys make a valid connection.}
VAR waittime:integer;
BEGIN
   waittime:=interval(abjp^.arrt,bcjp^.dept);
   makesconnection:=(minwt<=waittime) AND (waittime<=maxwt)
END;


FUNCTION connectjourney(abjp,bcjp:journeyptr; s:station):journeyptr;
{  Returns a pointer to a new composite journey.}
VAR acjp:journeyptr;
    cip,p:changeinfoptr;
BEGIN
   new(acjp);
   p:=copy(abjp^.change1);
   IF p=nil THEN
   BEGIN   {No change information for the a->b journey.}
      new(cip);
      p:=cip
   END ELSE   
   BEGIN   {Find the end of the changeinfo list of the a->b journey.}
      cip:=p;
      WHILE p^.next<>nil DO p:=p^.next;
      new(p^.next);
      p:=p^.next
   END;
   WITH p^ DO
   BEGIN   {Record information on the current change.}
      place:=s; arrt:=abjp^.arrt;
      wait:=interval(abjp^.arrt,bcjp^.dept);
      {Append the changeinfo list for the b->c journey.}
      next:=copy(bcjp^.change1)
   END;
   WITH acjp^ DO
   BEGIN
      dept:=abjp^.dept; arrt:=bcjp^.arrt;
      change1:=cip; marked:=false; next:=nil
   END;
   connectjourney:=acjp
END;


FUNCTION connect(abttp,bcttp:ttableptr; minwt,maxwt:mintime):ttableptr;
{  Connect function as specified in Frank's handout.}
VAR
   acttp:ttableptr;
   abjp,bcjp,acjp,temp:journeyptr;
   emptytt:boolean;   {True iff the timetable under construction  
                       currently contains no journeys.}
BEGIN
   IF abttp^.dest<>bcttp^.from THEN error(1);
   emptytt:=true;
   new(acttp);
   WITH acttp^ DO
   BEGIN
      from:=abttp^.from; dest:=bcttp^.dest; first:=nil
   END;
   abjp:=abttp^.first;
   WHILE abjp<>nil DO
   BEGIN   {abjp is used to scan the a->b timetable.}
      bcjp:=bcttp^.first;
      WHILE bcjp<>nil DO
      BEGIN   {For each journey in the a->b timetable scan the
               entire b->c timetable in search of connections.}
         IF makesconnection(abjp,bcjp,minwt,maxwt) THEN
         BEGIN
            temp:=connectjourney(abjp,bcjp,abttp^.dest);
            IF emptytt THEN acttp^.first:=temp ELSE acjp^.next:=temp;
            emptytt:=false;
            acjp:=temp
         END;
         bcjp:=bcjp^.next
      END;
      abjp:=abjp^.next
   END;
   connect:=acttp
END;


FUNCTION merge(ttp1,ttp2:ttableptr):ttableptr;
{  Merge function as specified in Frank's handout.}
VAR
   emptytt:boolean;
   newttp:ttableptr;
   jp1,jp2,newjp,nextjp,temp:journeyptr;
BEGIN
   emptytt:=true;
   IF (ttp1^.from <> ttp2^.from) OR
      (ttp1^.dest <> ttp2^.dest) THEN error(2);
   new(newttp);
   WITH newttp^ DO
   BEGIN
      from:=ttp1^.from; dest:=ttp1^.dest; first:=nil
   END;
   jp1:=ttp1^.first;   {Pointer to scan first timetable.}
   jp2:=ttp2^.first;   {Pointer to scan second timetable.}
   WHILE (jp1 <> nil) OR (jp2 <> nil) DO
   BEGIN
      IF (jp2=nil) THEN nextjp:=jp1
      ELSE IF (jp1=nil) THEN nextjp:=jp2
      ELSE IF (jp1^.dept <= jp2^.dept) THEN nextjp:=jp1
      ELSE nextjp:=jp2;
      new(temp);
      IF emptytt THEN newttp^.first:=temp ELSE newjp^.next:=temp;
      newjp:=temp;
      emptytt:=false;
      WITH newjp^ DO
      BEGIN
         dept:=nextjp^.dept; arrt:=nextjp^.arrt;
         change1:=copy(nextjp^.change1);
         marked:=false; next:=nil
      END;
      IF nextjp=jp1 THEN jp1:=jp1^.next ELSE jp2:=jp2^.next
   END;
   merge:=newttp
END;


FUNCTION overtakes(jp1,jp2:journeyptr):boolean;
{  Determines whether the train specified by the first
   overtakes that specified by the second.}
VAR
   lag,durn1,durn2:mintime;
BEGIN
   lag:=interval(jp2^.dept,jp1^.dept);
   durn1:=interval(jp1^.dept,jp1^.arrt);
   durn2:=interval(jp2^.dept,jp2^.arrt);
   IF lag=0 THEN overtakes:=(durn1<durn2)
            ELSE overtakes:=(durn1+lag) <= durn2
END;


FUNCTION eliminate(oldttp:ttableptr):ttableptr;
VAR
   newttp:ttableptr;
   oldjp,newjp,p,temp:journeyptr;
   emptytt,useless:boolean;
BEGIN
   new(newttp);
   emptytt:=true;
   WITH newttp^ DO
   BEGIN
      from:=oldttp^.from; dest:=oldttp^.dest; first:=nil
   END;
   oldjp:=oldttp^.first;
   WHILE oldjp <> nil DO
   BEGIN
      useless:=false;
      p:=oldttp^.first;
      WHILE (p <> nil) AND NOT useless DO
      BEGIN
         useless:=overtakes(p,oldjp);
         p:=p^.next
      END;
      IF NOT useless THEN
      BEGIN
         new(temp);
         IF emptytt THEN newttp^.first:=temp ELSE newjp^.next:=temp;
         newjp:=temp;
         emptytt:=false;
         WITH newjp^ DO
         BEGIN
            dept:=oldjp^.dept; arrt:=oldjp^.arrt;
            change1:=copy(oldjp^.change1);
            marked:=false; next:=nil
         END
      END;
      oldjp:=oldjp^.next
   END;
   eliminate:=newttp
END;

BEGIN
   FOR i:=1 TO numberofstations DO
   BEGIN
      readtt(input,temp);
      f:=temp^.from;
      d:=temp^.dest;
      IF (f=edin) AND (d=lkx) THEN ek:=temp
      ELSE IF (f=edin) AND (d=peter) THEN ep:=temp
      ELSE IF (f=peter) AND (d=ely) THEN pe:=temp
      ELSE IF (f=ely) AND (d=camb) THEN ec:=temp
      ELSE IF (f=lkx) AND (d=roy) THEN kr:=temp
      ELSE IF (f=roy) AND (d=camb) THEN rc:=temp
      ELSE lc:=temp
   END;
   ttp1:=connect(ep,connect(pe,ec,10,60),10,60);
   ttp2:=connect(ek,connect(kr,rc,10,60),10,60);
   ttp3:=connect(ek,lc,60,240);
   ttp4:=merge(ttp1,merge(ttp2,ttp3));
   writett(output,ttp4);
   ttp5:=eliminate(ttp4);
   writett(output,ttp5)
END.