!********o*********o*********o*********o*********o*********o*********o**
! This program simulates the scheduling of landings and takeoffs at an
! airport.  It is problem 28 on page 511 of Nyhoff & Leestma.
!
! Problem Statement
!    The airport has one runway, which must be shared by takeoffs and
!    landings.  Requests to land or take off occur at random, but on the
!    average we have eight of each per hour.  A landing occupies the
!    runway for three minutes;  takeoffs for two.  Since only one plane
!    at a time can be making use of the runway, some airplanes will
!    have to wait in a queue until the runway is free.  Landings take
!    priority over takeoffs-- a takeoff cannot occur if any plane is
!    waiting to land.
!
!    This program must simulate the activity at the airport over a 24
!    hour period, showing results for the first and last hour, and
!    produce statistics about the queues (average length, average
!    waiting time).
!
!    In order to determine a reasonable range of simulation results,
!    this program goes a step farther.  It runs the 24-hour simulation
!    10,000 times, and keeps track of the minimum, maximum, and average
!    values of each statistic.
!
! Implementation
!    The airport is simulated on a minute by minute basis.  During each
!    minute, we generate requests, manage waiting queues, track the
!    state of planes using the runway, and give clearance for planes to
!    begin landing or taking off.  This activity is shown in a codified
!    display, one line per minute.  The basic layout of our per-minute
!    loop is
!        1) simulate requests, add them to queues
!        2) if runway is in use, advance to the next runway event
!        3) if we can start a new event, do so
!        4) print what's happening
!
!    Requests for landing and takeoff are simulated using a pseudo
!    random number generator.  To achieve an average rate of 8 landing
!    requests per hour, a random 'landing arrival event' is generated
!    with probability 8/60ths.  The same is done for 'takeoff arrival
!    events.  Since the events are mathematically independent, two
!    separate random numbers are used.
!
!    The two waiting queues are implemented with simple counters.  When
!    a landing request is made the landing counter is increased by 1.
!    When a plane is cleared to land, the counter is decreased by 1.
!    Another counter is used for the takeoff queue.
!
!    Runway usage is represented by a single state variable.  Negative
!    numbers represent a landing taking place, positive numbers
!    represent a takeoff.  For example, three stages of landing are
!    represented as -3, -2, and -1.  Zero represents an unused runway.
!    This representation was chosen because it provided simple test
!    clauses (e.g. "runway clear" is a simple zero test, and advancing
!    to the next runway state is an increment or decrement).
!
!    In order to produce the desired statistics at the end, we keep
!    a count of the number of landings and takeoffs, and the sum of
!    the queue lengths over time.  We use the formulas
!
!                           sum over t of queue_length(t)
!        avg_queue_length = -----------------------------
!                                   total_minutes
!
!    and
!
!                           sum over t of queue_length(t)
!        avg_waiting_time = -----------------------------
!                                   total_planes
!
!    The justification for this latter formula is that each minute that
!    a plane spends waiting contributes a 'one' to the queue length for
!    that minute.  This formula will also give slightly wrong answers
!    if the simulation ends while a plane is left in the queue, but the
!    error is small enough to be ignored.
!---------------------
! Inputs
!   (none).
!
! Control Parameters
!   debug:                  true iff we should include extra output to
!                           aid in debugging the program.
!   landingProbability:     The probability, in any given minute, that a
!                           new plane enters our airspace wanting to
!                           land.
!   takeoffProbability:     The probability, in any given minute, that a
!                           new plane approaches the runway wanting to
!                           take off.
!   totalMinutes:           The total number of minutes that we will
!                           simulate.
!   visibleHour1:           Designates an hour that we will show the
!                           user minute-by-minute simulation results.
!                           A -1 can be used to disable this.
!   visibleHour2:           Designates another display hour (similar to
!                           visibleHour1).
!
! Working Variables
!   runwayState:            The activity going on on the runway.
!                               0 => runway is empty
!                              -3 => runway is reserved for LB
!                              -2 => runway is reserved for LP
!                              -1 => runway is reserved for LC
!                              +2 => runway is reserved for TB
!                              +1 => runway is reserved for TC
!   waitingToLand:          Number of planes waiting to land.
!   waitingToTakeoff:       Number of planes waiting to takeoff.
!   sumOfWaitingToLand:     Sum, over every minute, of the number of
!                           planes waiting to land.
!   sumOfWaitingToTakeoff:  Sum, over every minute, of the number of
!                           planes waiting to take off.
!   numberLanding:          Total number of planes that have wanted to
!                           land.
!   numberTakingOff:        Total number of planes that have wanted to
!                           take off.
!   newLandingArrival:      true iff we had an LA during this minute.
!   newTakeoffArrival:      true iff we had an TA during this minute.
!   sumOfLandingArrival:    Sum, over every plane that has wanted to
!                           land, of the time it arrived.
!   sumOfTakeoffArrival:    Sum, over every plane that has wanted to
!                           take off, of the time it arrived.
!   sumOfLandingBegun:      Sum, over every plane that has been given
!                           clearance to land, of the time it began
!                           to land.
!   sumOfTakeoffBegun:      Sum, over every plane that has been given
!                           clearance to take off, of the time it began
!                           to take off.
!   hour, minute:           Time of day, in 24-hour format.
!   minutesSinceStart:      Number of minutes since we began the
!                           simulation.
!   hidLastMinute:          true iff the most recent minute was hidden
!                           from the user.
!   r:                      A random number, in the range 0 <= r < 1.
!
! Output Variables
!   averageLandingQueue:    The average number of planes in the landing
!                           queue.
!   averageTakeoffQueue:    The average number of planes in the takeoff
!                           queue.
!   averageLandingWait:     The average number of minutes a plane was
!                           in the landing queue.
!   averageTakeoffWait:     The average number of minutes a plane was
!                           in the takeoff queue.
!
! Outputs
!   A series of lines showing the simulation process minute-by-minute,
!   such as shown below, and statistics gathered from the simulation.
!       0803  -- -- -- -- TA TB --     0         0
!       0804  LA -- -- -- -- -- TC     1         0
!       0805  -- LB -- -- -- -- --     0         0
!       0806  -- -- LP -- -- -- --     0         0
!       0807  LA -- -- LC -- -- --     1         0
!       0808  LA LB -- -- TA -- --     1         1
!       0809  -- -- LP -- -- -- --     1         1
!       0810  -- -- -- LC TA -- --     1         2
!         ... (and so on) ...
!
!   This is followed by statistics, such as these.
!       average length of landing queue:  0.1465278
!       average length of takeoff queue:  0.6833333
!
!       average time waiting to land:     1.024272
!       average time waiting to take off: 4.776699
!
!---------------------
! Author:   Bob Harris
! Class:    CMPSC 201F
! Section:  1234
! Date Due: 24 Nov 2003
!********o*********o*********o*********o*********o*********o*********o**

program ohare

implicit none

! control parameters

logical, parameter :: debug              = .false.
real,    parameter :: landingProbability = 8.0/60.0 ! 8 per hour
real,    parameter :: takeoffProbability = 8.0/60.0 ! 8 per hour
integer, parameter :: totalMinutes       = 24*60    ! 24 hours
integer, parameter :: visibleHour1       = 0        ! hour  0 is visible
integer, parameter :: visibleHour2       = 23       ! hour 23 is visible

! variables

integer :: runwayState
integer, parameter :: clear             = 0
integer, parameter :: landingBegun      = -3
integer, parameter :: landingInProgress = -2
integer, parameter :: landingComplete   = -1
integer, parameter :: takeoffBegun      = 2
integer, parameter :: takeoffComplete   = 1

integer :: waitingToLand, waitingToTakeoff
integer :: sumOfWaitingToLand, sumOfWaitingToTakeoff
integer :: numberLanding, numberTakingOff
logical :: newLandingArrival, newTakeoffArrival
integer :: sumOfLandingArrival, sumOfTakeoffArrival
integer :: sumOfLandingBegun, sumOfTakeoffBegun
integer :: hour, minute, minutesSinceStart
logical :: hideThisMinute, hidLastMinute
real    :: r

real    :: averageLandingQueue
real    :: averageTakeoffQueue
real    :: averageLandingWait
real    :: averageTakeoffWait

!----------
! initialize
!----------

! initialize the pseudo-random number generator

call RANDOM_SEED

! initialize the simulation state

runwayState      = clear ! (runway clear)
waitingToLand    = 0     ! (no one waiting)
waitingToTakeoff = 0

! initialize statistics

numberLanding         = 0
numberTakingOff       = 0

sumOfWaitingToLand    = 0
sumOfWaitingToTakeoff = 0

sumOfLandingArrival   = 0
sumOfTakeoffArrival   = 0

sumOfLandingBegun     = 0
sumOfTakeoffBegun     = 0

! intialize output

write (*,"(1X,A)") "              events        waiting  waiting to"
write (*,"(1X,A)") "time  LA LB LP LC TA TB TC  to land   take off"
write (*,"(1X,A)") "----  --------------------  -------  ----------"

hidLastMinute = .false.

!----------
! simulate each minute
!----------

hour   = 0
minute = 0

do minutesSinceStart=1,totalMinutes

    !----------
    ! see if we have any arrival events
    !----------

    ! assume no one arrives

    newLandingArrival = .false.
    newTakeoffArrival = .false.

    ! see if we have a landing request;  note that if we do, we just
    ! add it to the queue (to the number of planes waiting);  later
    ! we'll check to see if we can allow it to land

    call RANDOM_NUMBER(r)
    if (r < landingProbability) then
        newLandingArrival   = .true.
        waitingToLand       = waitingToLand + 1
        numberLanding       = numberLanding + 1
        sumOfLandingArrival = sumOfLandingArrival + minutesSinceStart
    end if

    ! see if we have a takeoff request;  as for the landing request,
    ! we just add this to the queue

    call RANDOM_NUMBER(r)
    if (r < takeoffProbability) then
        newTakeoffArrival   = .true.
        waitingToTakeoff    = waitingToTakeoff + 1
        numberTakingOff     = numberTakingOff  + 1
        sumOfTakeoffArrival = sumOfTakeoffArrival + minutesSinceStart
    end if

    !----------
    ! figure out the state of the airport for this minute
    !----------

    ! if the runway was reserved for a plane, 'advance' it;  note that
    ! we have to do this *before* checking for an empty runway, because
    ! this might make the runway empty now

    if (runwayState > 0) then
        runwayState = runwayState - 1
    else if (runwayState < 0) then
        runwayState = runwayState + 1
    end if

    ! see if we can schedule someone to land

    if ((runwayState == clear) .and. (waitingToLand > 0)) then
        ! pull a plane off the landing queue and start it landing
        waitingToLand     = waitingToLand - 1
        runwayState       = landingBegun
        sumOfLandingBegun = sumOfLandingBegun + minutesSinceStart
    else if ((runwayState == clear) .and. (waitingToTakeoff > 0)) then
        ! pull a plane off the takeoff queue and start it taking off
        waitingToTakeoff  = waitingToTakeoff - 1
        runwayState       = takeoffBegun
        sumOfTakeoffBegun = sumOfTakeoffBegun + minutesSinceStart
    end if

    !----------
    ! update statistics
    !----------

    sumOfWaitingToLand    = sumOfWaitingToLand    + waitingToLand
    sumOfWaitingToTakeoff = sumOfWaitingToTakeoff + waitingToTakeoff

    !----------
    ! display the current state
    !----------

    ! see if we should display this minute

    if ((hour /= visibleHour1) .and. (hour /= visibleHour2)) then
        hidLastMinute = .true.
    else

        ! we're going to display this minute;  if we didn't display the
        ! previous one, print out a dividing line so the user won't get
        ! confused by the discontinuity

        if (hidLastMinute) then
            write (*,"(1X,A)") "------------------------------------------"
            hidLastMinute = .false.
        end if

        ! show the time, in four-digit military format

        write (*,"(1X,2I2.2)",advance="no") hour, minute

        ! show landing state

        if (newLandingArrival) then
            write (*,"(1X,A2)",advance="no") "LA"
        else
            write (*,"(1X,A2)",advance="no") "--"
        end if

        if (runwayState == landingBegun) then
            write (*,"(3(1X,A2))",advance="no") "LB", "--", "--"
        else if (runwayState == landingInProgress) then
            write (*,"(3(1X,A2))",advance="no") "--", "LP", "--"
        else if (runwayState == landingComplete) then
            write (*,"(3(1X,A2))",advance="no") "--", "--", "LC"
        else
            write (*,"(3(1X,A2))",advance="no") "--", "--", "--"
        end if

        ! show takeoff state

        if (newTakeoffArrival) then
            write (*,"(1X,A2)",advance="no") "TA"
        else
            write (*,"(1X,A2)",advance="no") "--"
        end if

        if (runwayState == takeoffBegun) then
            write (*,"(2(1X,A2))",advance="no") "TB", "--"
        else if (runwayState == takeoffComplete) then
            write (*,"(2(1X,A2))",advance="no") "--", "TC"
        else
            write (*,"(2(1X,A2))",advance="no") "--", "--"
        end if

        ! show the queue lengths

        write (*,"(2X,I5,5X,I5)",advance="no") waitingToLand, &
                                               waitingToTakeoff

        ! write extra stuff, for debugging

        if (debug) then
            write (*,"(2(1X,I3))",advance="no") numberLanding,       &
                                                numberTakingOff
            write (*,"(2(1X,I4))",advance="no") sumOfWaitingToLand,  &
                                                sumOfWaitingToTakeoff
            write (*,"(2(1X,I6))",advance="no") sumOfLandingArrival, &
                                                sumOfTakeoffArrival
            write (*,"(2(1X,I6))",advance="no") sumOfLandingBegun,   &
                                                sumOfTakeoffBegun
        end if

        ! finish off the line of output

        write (*,*)
    end if

    !----------
    ! advance time to next minute
    !----------

    minute = minute+1
    if (minute >= 60) then
        minute = minute-60
        hour = hour+1
    end if

    if (hour >= 24) then
        hour = hour-24
    end if

end do

!----------
! print the stats
!----------

! compute the stats

averageLandingQueue = sumOfWaitingToLand   /real(totalMinutes)
averageTakeoffQueue = sumOfWaitingToTakeoff/real(totalMinutes)

averageLandingWait  = sumOfWaitingToLand   /real(numberLanding)
averageTakeoffWait  = sumOfWaitingToTakeoff/real(numberLanding)

! print 'em

print *
print *, "average length of landing queue:              ", &
          averageLandingQueue
print *, "average length of takeoff queue:              ", &
          averageTakeoffQueue

print *
print *, "average time waiting to land     (formula 2): ", &
          averageLandingWait
print *, "average time waiting to take off (formula 2): ", &
          averageTakeoffWait

! print some additional stats

if (debug) then

    print *
    print *, "number of landing requests:                  ",  &
              numberLanding
    print *, "number of takeoff requests:                  ",  &
              numberTakingOff

    print *
    print *, "average landing requests per hour:            ", &
              (60*numberLanding)   /real(totalMinutes)
    print *, "average takeoff requests per hour:            ", &
              (60*numberTakingOff) /real(totalMinutes)

    print *
    print *, "average time waiting to land     (formula 1): ", &
              (sumOfLandingBegun-sumOfLandingArrival)/real(numberLanding)
    print *, "average time waiting to take off (formula 1): ", &
              (sumOfTakeoffBegun-sumOfTakeoffArrival)/real(numberTakingOff)

end if

end program ohare
