August 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 4

Total Marks: 20 Marks

 Click here to access other questions

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 4
You are to implement an Air Traffic Control queueing system. When a flight reaches the airport, it receives a landing_number which identifies its position in the landing queue. The following data type is used to represent the landing queue:

TYPE airline = (BritishAirways, SingaporeAirlines, KLM, Lufthansa);

aeroplane = RECORD

owner : airline;
flight_number : String[10];
airtimeleft : Integer;
landing_number : Integer;

END;

NodeType = ^Node;
Node = RECORD

next : NodeType;
data : aeroplane;

END;

QueueType = RECORD

front : NodeType;
rear : NodeType;

END;

In QueueType, front points to the first aeroplane in the queue and rear points to the last aeroplane in the queue. The Next field of a node points from the older aeroplane in the queue to the newer aeroplane. In addition to this, it is also needed to know how much fuel an aeroplane has left, in case it is about to run out, and this airtime_left is measured in minutes.

 
(a) Write a function, the prototype of which is given below, which takes the landing queue and removes and returns the oldest aeroplane in the landing queue (the one at the front).

FUNCTION LandPlane (VAR queue: QueueType) : aeroplane;

 [4]
A sample definition of a function LandPlane follows:

FUNCTION LandPlane(VAR queue: QueueType): aeroplane
temp: NodeType;
BEGIN
     IF(queue.^front <> NIL) THEN
     BEGIN
            temp= queue.front
            LandPlane:= queue.^front.data;
            queue.^front:= queue.^front.next;
            Dispose(temp);
     END
     ELSE
           LandPlane:= NIL;
END;

 
(b) Write a function the prototype of which is given below, that returns the landing_number of the aeroplane with the least fuel left in the queue (i.e., the least airtime left). If there are no aeroplanes in the queue, the function should return 0.
FUNCTION LeastFuelLeft(queue: QueueType) : Integer;		 [6]
A sample definition of LeastFuelLeft follows:

FUNCTION LeastFuelLeft(queue: QueueType) : Integer
VAR ptr : NodeType;
VAR fuel_left : Integer;
BEGIN
       ptr                     := queue.^front;
       IF(ptr <> NIL) THEN
       BEGIN
              fuel_left :=ptr.^data.landing_number
       WHILE(ptr <> NIL) DO
       BEGIN
              IF(ptr.^data.airtimeleft < fuel_left) THEN
                   LeastFuelLeft := ptr.^data.landing_number;
              ptr:= ptr.^next
        END;
   END
   ELSE
   BEGIN
        LeastFuelLeft : = 0;
END
END; { LeastFuelLeft }
(c) A takeoff queue is represented by the same QueueType, where airtimeleft represents time remaining until takeoff; and landing_number represents the place in the takeoff queue.

Implement the procedure TakeOffPlane, which takes the takeoff queue and an aeroplanes details, and adds it to the takeoff queue. Note that you will need to calculate the landing_number for the aeroplane, by adding one to the landing number of the oldest aeroplane in the queue.

PROCEDURE TakeOffPlane (VAR queue: QueueType, TimeToTakeOff : Integer);

 [6]
A sample definition of TakeOffPlane follows:

PROCEDURE TakeOffPlane(VAR queue : QueueType, NewPlane:                                               aeroplane, TimeToTakeOff: Integer)
VAR NewNode : NodeType;
BEGIN

        New(NewNode);
        NewNode^.data.owner:= NewPlane.owner;
        NewNode^.data.flight_number:= NewPlane.flight_number;
        NewNode^.data.airtimeleft:= TimeTotakeOff;

        IF(queue.^rear <> NIL) THEN
        BEGIN
              NewNode^.data.landing_number:=
                                             queue.^rear.data.landing_number + 1;
              queue.^rear.next:= NewNode;
              queue.^rear:= NewNode;
         END
         ELSE
         BEGIN
              NewNode^.data.landing_number:= 1;
              queue.^rear:= NewNode;
              queue.^front:= NewNode;
          END
END;

 
(d) Write a function called CoordinateQueue, which will take 3 arguments: the landing queue, the takeoff queue and a time in minutes.

The function should land the oldest aeroplane in the queue, and set it up for takeoff in the takeoff queue, with the time parameter specifying the time in minutes until the plane is expected to take off. The function will return TRUE if there has been a place to land and schedule for takeoff, and FALSE otherwise.

 [4]
A sample definition of CoordinateQueues follows:

FUNCTION CoordinateQueues(VAR LandingQueue : QueueType, VAR TakeOffQueue : QueueType, Time: Integer) : BOOLEAN
VAR plane : aeroplane
BEGIN
      plane:= LandPlane(LandingQueue);
      IF(plane <> NIL) THEN
      BEGIN
           TakeOffPlane(TakeOffQueue, plane, Time);
           CoordinateQueues:= TRUE;
      END;
      ELSE
            CoordinateQueues:= FALSE;
END;