17.4.2 The scheduling algorithm

// Searches all of the vehicle storage of class class-of-next, which is
// connected to container and has room for aircraft
define method find-available-connection
    (storage :: <vehicle-storage>, class-of-next :: <class>,
     aircraft :: <aircraft>)
 => (next-container :: false-or(<vehicle-storage>))
  block (return)
    for (c in storage.connected-to)
      if (instance?(c, class-of-next)
          & available?(aircraft, c, aircraft.direction))
        return(c);
      end if;
    end for;
  end block;
end method find-available-connection; 

// Generate new transitions to be considered for the next move
// The transitions will be placed in the sorted sequence, which will order
// them by earliest arrival time
define method generate-new-transitions
    (container :: <vehicle-storage>, 
     active-transitions :: <sorted-sequence>,
     containers-visited :: <object-table>)
 => ()
  unless(element(containers-visited, container, default: #f))
    // Keep track of which containers we have searched for new possible
    // transitions
    // We avoid looping forever by checking each container just once
    containers-visited[container] := #t; 

    local method consider-transition (direction)
      // See whether any vehicle is ready to transition out of a container
      let (vehicle, next-container, time) 
        = next-out(container, direction);
      unless (vehicle == #f | vehicle.next-transition.pending?)
        // If there is a vehicle ready, and it is not already in the 
        // sorted sequence of pending transitions, then prepare the 
        // transition instance associated with the vehicle 
        let transition = vehicle.next-transition;
        transition.from-container := container;
        transition.to-container := next-container;

        // The vehicle may have been waiting
        // Take this situation into account when computing the earliest
        // arrival into the next container
        transition.earliest-arrival := transition.earliest-arrival + time;
        // Flag the vehicle as pending, to save searching through the
        // active-transitions sorted sequence later
        transition.pending? := #t;
        // Add the transition to the set to be considered 
        add!(active-transitions, transition);
      end unless;
    end method consider-transition; 

    // Consider both inbound and outbound traffic 
    consider-transition(#"outbound");
    consider-transition(#"inbound");
    // Make sure that every container connected to this one is checked
    for (c in container.connected-to)
      generate-new-transitions(c, active-transitions, containers-visited);
    end for;
  end unless;
end method generate-new-transitions; 

// Main loop of the program
// See what possible transitions exist, then execute the earliest
// transitions that can be completed
// Returns the time of the last transition
define method process-aircraft 
    (airport :: <airport>, #key time = $midnight) 
 => (time :: <time-of-day>)
  format-out("Detailed aircraft schedule for ");
  say(airport);
  format-out("\n\n");
  let sky = airport.sky-above;
  let containers-visited = make(<object-table>);
  let active-transitions = make(<sorted-sequence>, 
                               value-function: earliest-arrival); 

  // We do not have to use return as the name of the exit procedure
  block (done)
    while (#t)
      // Each time through, start by considering every container
      fill!(containers-visited, #f);
      // For every container, see if any vehicles are ready to transition
      // If any are, add transition instances to the active-transitions 
      // sorted sequence
      generate-new-transitions(sky, active-transitions, 
                               containers-visited);

      // If there are no more transitions, we have completed our task
      if (empty?(active-transitions)) done(); end;
      // Find the earliest transition that can complete, because there is 
      // still room available in the destination container
      let transition-index
        = find-key(active-transitions,
                   method (transition)
                     available?(transition.transition-aircraft,
                                transition.to-container,
                                transition.transition-aircraft.direction);
                   end); 

      // If none can complete, there is a problem with the simulation
      // This situation should never occur, but is useful for debugging
      // incorrect container configurations
      if (transition-index == #f)
        error("Pending transitions but none can complete.");
      end if; 

      // Otherwise, the earliest transition that can complete has been
      // found: Execute the transition
      let transition = active-transitions[transition-index];
      let vehicle = transition.transition-aircraft;
      let vehicle-direction = vehicle.direction;
      move-out-vehicle(vehicle, transition.from-container, 
                       vehicle-direction);
      move-in-vehicle(vehicle, transition.to-container, vehicle-direction); 

      // This transition is complete; remove it from consideration 
      transition.pending? := #f;
      remove!(active-transitions, transition);
      // Compute the actual time of arrival at the next container, and
       // display the message 
      time := (transition.earliest-arrival 
                := max(time, transition.earliest-arrival));
      say(transition);
      format-out("\n");
    end while;
  end block;
  time;
end method process-aircraft;