In this assignment you will use a priority queue to simulate airplanes arriving
ID: 673637 • Letter: I
Question
In this assignment you will use a priority queue to simulate airplanes arriving at an airport. The goal of the assignment is to wirte your own Priority Queue. You will use your queue to determine how many take-offs and landings a single runway can support, given fixed takeoff and landing times, and priority for landings.
Two files have already been written for you: Plane.java and AirportSimulation.java
Plane is a data class used to store one airplane worth of data. Each plane is either taking off or landing. They keep track of the time that they arrive at the airport, and the time that they successfully take off or land.
The AirportSimulation class uses a static main method to determine the average and longest wait times for take offs and landing. It runs a simulation for a years worth of traffic, assuming that the arrival and departure of planes is evenly distributed throughout the year.
You will notice that the AirportSimulation class uses the PriorityQueue class from the java.util library. Your taks is to write your own implementation of the Queue interface, and substitute your priority queue for the queue currently used in the class. Name your class MyPriorityQueue. Implement the class using an array, or a linked list.
************************************************************************************
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class AirportSimulation {
public static void main(String[] args) {
// These two queues represent all of the take off and landing events in the whole day
PriorityQueue<Plane> allPlaneEvents = new PriorityQueue<Plane>();
// These are the the number of minutes that we expect a plane to take to use the runway
final int TakeOffTime = 5;
final int LandingTime = 3;
// These are the number of take-offs and landings in a day. The events will be
// randomly interspearsed throught the day
final int AverageTakeOffRequestsPerHour = 4;
final int AverageLandingRequestsPerHour = 4;
// We will run our simulation for a years worth of simulated days...
final int HoursInSimulation = 365 * 24;
// Add the take off requests to the queue
int totalTakeOffEventCount = HoursInSimulation * AverageTakeOffRequestsPerHour;
for (int i = 0; i < totalTakeOffEventCount; i++) {
Plane p = new Plane(Plane.Takeoff, getRandomMinuteInHours(HoursInSimulation));
allPlaneEvents.add(p);
}
// Add the landings
int totalLandingEventCount = HoursInSimulation * AverageLandingRequestsPerHour;
for (int i = 0; i < totalLandingEventCount; i++) {
Plane p = new Plane(Plane.Landing, getRandomMinuteInHours(HoursInSimulation));
allPlaneEvents.add(p);
}
// variables for keeping track of longest waits
int longestLandingWait = 0;
int longestTakeoffWait = 0;
// variables for keeping track of average waits
int totalLandingWait = 0;
int totalTakeoffWait = 0;
// Keep track of the next minute in which the runway will be available.
int nextMinuteRunwayWillBeAvailable = 0;
// These two queues represent the Planes that have asked permission to take off or land
Queue<Plane> planesInTheAir = new LinkedList<Plane>();
Queue<Plane> planesOnTheRunway = new LinkedList<Plane>();
// For the simulation, we will tick through every minute in the time period. We will process
// each Plane when its time comes.
for (int minute = 0; minute < (HoursInSimulation * 60); minute++) {
// Check to see if there are new arrivals
while (!allPlaneEvents.isEmpty() && minute >= allPlaneEvents.peek().getArrivalTime()) {
Plane nextPlane = allPlaneEvents.remove();
if (nextPlane.isLanding())
planesInTheAir.add(nextPlane);
else
planesOnTheRunway.add(nextPlane);
}
// if the runWay is available, process the next plane in the air, or on the runway
if (minute >= nextMinuteRunwayWillBeAvailable) {
// In the air...
if (!planesInTheAir.isEmpty()) {
Plane p = planesInTheAir.remove();
int completionTime = minute + LandingTime;
p.setEndTime(completionTime);
nextMinuteRunwayWillBeAvailable = completionTime;
totalLandingWait += p.elapsedTime();
if (p.elapsedTime() > longestLandingWait)
longestLandingWait = p.elapsedTime();
}
// One the runway
else if (!planesOnTheRunway.isEmpty()) {
Plane p = planesOnTheRunway.remove();
int completionTime = minute + TakeOffTime;
p.setEndTime(completionTime);
nextMinuteRunwayWillBeAvailable = completionTime;
totalTakeoffWait += p.elapsedTime();
if (p.elapsedTime() > longestTakeoffWait)
longestTakeoffWait = p.elapsedTime();
}
}
}
System.out.println("longest landing wait: " + longestLandingWait);
System.out.println("average landing wait: " + totalLandingWait / totalLandingEventCount);
System.out.println();
System.out.println("longest takeoff wait: " + longestTakeoffWait);
System.out.println("average takeoff wait: " + totalTakeoffWait / totalTakeOffEventCount);
}
public static int getRandomMinuteInHours(int hours) {
return (int) (Math.random() * (hours * 60));
}
}
*************************************************************************************
import java.util.Comparator;
public class Plane implements Comparable<Plane> {
public static final int Landing = 0;
public static final int Takeoff = 1;
private int priority;
private int arrivalTime;
private int endTime;
public Plane(int priority, int startTime) {
this.priority = priority;
this.arrivalTime = startTime;
}
// Only endTime has a setter
public void setEndTime(int value) {
endTime = value;
}
// Getters
public int getPriority() {
return priority;
}
public int getArrivalTime() {
return arrivalTime;
}
public int getEndTime() {
return endTime;
}
public int elapsedTime() {
return endTime - arrivalTime;
}
public boolean isLanding() {
return priority == Landing;
}
// Compares two planes based on priority first, and start time second.
public int compareTo(Plane p2) {
//System.out.println("about to return " + (startTime - p2.startTime) + " for " + this + " and " + p2);
return arrivalTime - p2.arrivalTime;
}
// For debugging
public String toString() {
String type = isLanding()? "landing" : "takingoff";
return "Plane - " + type + ", arrivalTime: " + arrivalTime;
}
}
Explanation / Answer
Note: Plane class is same;
MyPriorityQueue<Plane> allPlaneEvents = new MyPriorityQueue<Plane>(
2 * totalTakeOffEventCount);
See the above line in AirportSimulation.main() method
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class AirportSimulation {
public static void main(String[] args) {
// These two queues represent all of the take off and landing events in
// the whole day
// These are the the number of minutes that we expect a plane to take to
// use the runway
final int TakeOffTime = 5;
final int LandingTime = 3;
// These are the number of take-offs and landings in a day. The events
// will be
// randomly interspearsed throught the day
final int AverageTakeOffRequestsPerHour = 4;
final int AverageLandingRequestsPerHour = 4;
// We will run our simulation for a years worth of simulated days...
final int HoursInSimulation = 365 * 24;
// Add the take off requests to the queue
int totalTakeOffEventCount = HoursInSimulation
* AverageTakeOffRequestsPerHour;
MyPriorityQueue<Plane> allPlaneEvents = new MyPriorityQueue<Plane>(
2 * totalTakeOffEventCount);
for (int i = 0; i < totalTakeOffEventCount; i++) {
Plane p = new Plane(Plane.Takeoff,
getRandomMinuteInHours(HoursInSimulation));
allPlaneEvents.add(p);
}
// Add the landings
int totalLandingEventCount = HoursInSimulation
* AverageLandingRequestsPerHour;
for (int i = 0; i < totalLandingEventCount; i++) {
Plane p = new Plane(Plane.Landing,
getRandomMinuteInHours(HoursInSimulation));
allPlaneEvents.add(p);
}
// variables for keeping track of longest waits
int longestLandingWait = 0;
int longestTakeoffWait = 0;
// variables for keeping track of average waits
int totalLandingWait = 0;
int totalTakeoffWait = 0;
// Keep track of the next minute in which the runway will be available.
int nextMinuteRunwayWillBeAvailable = 0;
// These two queues represent the Planes that have asked permission to
// take off or land
Queue<Plane> planesInTheAir = new LinkedList<Plane>();
Queue<Plane> planesOnTheRunway = new LinkedList<Plane>();
// For the simulation, we will tick through every minute in the time
// period. We will process
// each Plane when its time comes.
for (int minute = 0; minute < (HoursInSimulation * 60); minute++) {
// Check to see if there are new arrivals
while (!allPlaneEvents.isEmpty()
&& minute >= allPlaneEvents.peek().getArrivalTime()) {
Plane nextPlane = allPlaneEvents.remove();
if (nextPlane.isLanding())
planesInTheAir.add(nextPlane);
else
planesOnTheRunway.add(nextPlane);
}
// if the runWay is available, process the next plane in the air, or
// on the runway
if (minute >= nextMinuteRunwayWillBeAvailable) {
// In the air...
if (!planesInTheAir.isEmpty()) {
Plane p = planesInTheAir.remove();
int completionTime = minute + LandingTime;
p.setEndTime(completionTime);
nextMinuteRunwayWillBeAvailable = completionTime;
totalLandingWait += p.elapsedTime();
if (p.elapsedTime() > longestLandingWait)
longestLandingWait = p.elapsedTime();
}
// One the runway
else if (!planesOnTheRunway.isEmpty()) {
Plane p = planesOnTheRunway.remove();
int completionTime = minute + TakeOffTime;
p.setEndTime(completionTime);
nextMinuteRunwayWillBeAvailable = completionTime;
totalTakeoffWait += p.elapsedTime();
if (p.elapsedTime() > longestTakeoffWait)
longestTakeoffWait = p.elapsedTime();
}
}
}
System.out.println("longest landing wait: " + longestLandingWait);
System.out.println("average landing wait: " + totalLandingWait
/ totalLandingEventCount);
System.out.println();
System.out.println("longest takeoff wait: " + longestTakeoffWait);
System.out.println("average takeoff wait: " + totalTakeoffWait
/ totalTakeOffEventCount);
}
public static int getRandomMinuteInHours(int hours) {
return (int) (Math.random() * (hours * 60));
}
}
// *************************************************************************************
class MyPriorityQueue<E> implements Queue<E> {
private int MAX_SIZE = 10;
private Object[] queue;
private int front;
private int end;
public MyPriorityQueue() {
queue = new Object[MAX_SIZE];
front = 0;
end = 0;
}
public MyPriorityQueue(int size) {
queue = new Object[size];
MAX_SIZE = size;
front = 0;
end = 0;
}
@Override
public boolean addAll(Collection<? extends E> arg0) {
// TODO Auto-generated method stub
if (arg0 != null && arg0.size() > 0) {
for (E obj : arg0)
this.add(obj);
return true;
}
return false;
}
@Override
public void clear() {
// TODO Auto-generated method stub
int len = queue.length;
if (queue != null && len > 0) {
for (int i = 0; i < len; i++)
queue[i] = null;
end = 0;
}
}
@Override
public boolean contains(Object obj) {
// TODO Auto-generated method stub
int len = queue.length;
if (queue != null && len > 0) {
for (Object ele : queue) {
if (ele.equals(obj))
return true;
}
}
return false;
}
@Override
public boolean containsAll(Collection<?> arg0) {
// TODO Auto-generated method stub
if (arg0 != null && arg0.size() > 0) {
for (Object obj : arg0) {
boolean isExist = contains(obj);
if (!isExist)
return false;
}
return true;
}
return false;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return (end <= 0);
}
@Override
public Iterator<E> iterator() {
// TODO Auto-generated method stub
if (queue != null && queue.length > 0) {
ArrayList<E> al = new ArrayList<E>();
for (Object obj : queue) {
al.add((E) obj);
}
return al.iterator();
}
return null;
}
@Override
public boolean remove(Object obj) {
// TODO Auto-generated method stub
int len = queue.length;
if (front != end && queue != null && len > 0) {
for (Object ele : queue) {
if (ele.equals(obj)) {
// remove first element and decrease end
for (int i = front; i < end - 1; i++) {
queue[i] = queue[i + 1];
}
// decrease end to reflect current elements
end--;
return true;
}
}
}
return false;
}
@Override
public boolean removeAll(Collection<?> arg0) {
// TODO Auto-generated method stub
if (arg0 != null && arg0.size() > 0) {
for (Object ele : arg0) {
this.remove(ele);
}
return true;
}
return false;
}
@Override
public boolean retainAll(Collection<?> arg0) {
int len = queue.length;
if (front != end && queue != null && len > 0) {
for (Object ele : queue) {
// If element is not in retain list, remove it
if (!arg0.contains(ele))
this.remove(ele);
}
return true;
}
return false;
}
@Override
public int size() {
// TODO Auto-generated method stub
return end;
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
return queue;
}
@Override
public <T> T[] toArray(T[] arg0) {
// TODO Auto-generated method stub
return (T[]) queue;
}
@Override
public boolean add(E e) {
// TODO Auto-generated method stub
if (end == MAX_SIZE) {
return false;
} else {
int index;
// if inserting first element
if (front == end) {
index = 0;
} else {
index = end;
for (int i = front; i < end; i++) {
Plane pl = (Plane) queue[i];
// This conversion is needed
// if its not less than, insert above
if ((pl).compareTo((Plane) e) >= 0) {
index = i;
break;
}
}
for (int i = end - 1; i >= index; i--) {
queue[i + 1] = queue[i];
queue[i + 1] = queue[i];
}
}
queue[index] = e;
end++;
}
return false;
}
@Override
public E element() {
// TODO Auto-generated method stub
return null;
}
@Override
public boolean offer(E e) {
// TODO Auto-generated method stub
return false;
}
@Override
public E peek() {
// TODO Auto-generated method stub
if (!this.isEmpty())
return (E) queue[front];
return null;
}
@Override
public E poll() {
// TODO Auto-generated method stub
return null;
}
@Override
public E remove() {
// TODO Auto-generated method stub
int len = queue.length;
if (front != end && queue != null && len > 0) {
// remove first element and movie other elements in the queue
E ele = (E) queue[front];
queue[front] = null;
for (int i = front; i < end - 1; i++) {
queue[i] = queue[i + 1];
}
// decrease end to reflect current elements
end--;
return ele;
}
return null;
}
void display() {
System.out.println("Queue Elements : ");
if (front == end)
System.out.println(" Queue is empty");
else {
for (int i = front; i < end; i++) {
System.out.println(((Plane) queue[i]).toString());
}
}
}
}