PriorityQueue 不是 'polling' 优先级对象，或者我在 compareTo 方法中有逻辑错误
PriorityQueue not 'polling' priority object or I have logical error in compareTo method
要么是我对优先级队列工作原理的理解不正确，要么是我的 compareTo 方法覆盖了 Comparable 接口存在逻辑错误。我正在尝试将最高优先级的跑道分配给正在着陆或起飞的飞机。在以下场景中，有四个航班和四个跑道可用。因此，每个航班都按预定时间降落或起飞。
格式为：
scheduledTime|eventType|flightIdentifier|runwayUsed
00:01|ARRIVAL|A001|null
00:00|DEPARTURE|D001|null
00:01|DEPARTURE|D002|null
00:00|DEPARTURE|D003|null
将航班分配到优先跑道后（'polling'条跑道对象优先队列中的优先跑道），结果为
00:01|ARRIVAL|A001| 1
00:00|DEPARTURE|D001| 4
00:01|DEPARTURE|D002| 2
00:00|DEPARTURE|D003| 3
但是，假设我的 compareTo 方法没有逻辑错误，输出应该是：
00:01|ARRIVAL|A001| 1
00:00|DEPARTURE|D001| 2
00:01|DEPARTURE|D002| 3
00:00|DEPARTURE|D003| 4
这是包含 compareTo 方法的跑道 class：
public class Runway implements Comparable<Runway>{
//instance or class variables
private LocalTime whenAvailable; //when the runway is available
private LocalTime actualTime; //actual time the plane arrived or departed
private List<Flight> flights; //the flights that have been assigned to the runway
private Integer runwayNumber; // the number of the runway. for ex., 1 = Runway 1.
private LocalTime previousSchedTime; //the most recent previous time that the runway was scheduled for arrival or departure. This is just used
// for testing purposes.
/**
* Constructor
*/
protected Runway() {
whenAvailable = null;
flights = new ArrayList<Flight>();
}
/**
* Determine if the runway is available
* @param currentTime The scheduled time of the flight
* @return true if the runway is available or false if it is not
*/
protected boolean isAvailable(LocalTime currentTime) {
if(currentTime == null) {
throw new IllegalArgumentException();
}
return whenAvailable == null || !currentTime.isBefore(whenAvailable); // currentTime >= whenAvailable
}
/**
* Assign flight to the runway, i.e., set the actual time a flight uses the runway and the time ruwnay will be available again
* @param flight The flight being assigned to the runway
* @param scheduledTime The scheduled time of the flight
* @param reserveTime The arrival or departure reserve times of the flight
*/
protected void assignFlight(Flight flight, LocalTime scheduledTime, int reserveTime) {
//if the runway is available
if(isAvailable(scheduledTime)) {
//Set the actual time of the flight and when the runway will be available again
//if the runway is null and available
if(whenAvailable == null) {
actualTime = scheduledTime;
whenAvailable = scheduledTime.plusMinutes(reserveTime);
}
//if runway is available and the scheduled time of flight is equal to when the runway is available
else if(scheduledTime == whenAvailable || scheduledTime.isBefore(whenAvailable)) {
actualTime = whenAvailable;
whenAvailable = actualTime.plusMinutes(reserveTime);
}
else { //if scheduledTime > whenAvailable
actualTime = scheduledTime;
whenAvailable = actualTime.plusMinutes(reserveTime);
}
}
//if the runway is not available aka currentTime < whenAvailable
else {
actualTime = whenAvailable;
whenAvailable = actualTime.plusMinutes(reserveTime);
}
flights.add(flight);
previousSchedTime = scheduledTime; //update previousSchedTime to scheduledTime
}
/**
*
* @return acutialTime the runway was used by flight
*/
protected LocalTime getActualTimeRunway() {
return actualTime;
}
/**
*
* @return the time the runway is available
*/
protected LocalTime getWhenAvailable() {
return whenAvailable;
}
/**
*
* @return List of all the flights that used the runway
*/
protected List<Flight> getFlights(){
List<Flight> tmpList = new LinkedList<Flight>();
for(Flight f : flights) {
tmpList.add(f);
}
return tmpList;
}
/**
*
* @param runwayNumber set the number of the runway
*/
protected void setRunwayNumber(int runwayNumber) {
if(runwayNumber < 1) {
throw new IllegalArgumentException();
} //end of if
this.runwayNumber = runwayNumber;
}
/**
*
* @return the number of the runway
*/
protected Integer getRunwayNumber() {
return runwayNumber;
}
/**
*
* @return the most recent previous time that the runway was scheduled for arrival or departure. This is used
// as a condition in the assignFlight method below
*/
protected LocalTime getPreviousSchedTime() {
return previousSchedTime;
}
/**
* NOTE: this is intended to only be used for testing in other classes when used with reflection
* @param previousSchedTime sets the previousScedTime
*/
private void setPreviousSchedTime(LocalTime previousSchedTime) {
this.previousSchedTime = previousSchedTime;
}
/**
* Override compareTo method of Comparable interface
* Set priority of runway instance when compared other runway instances
*/
@Override
public int compareTo(Runway other) {
if(this.getWhenAvailable() == null && other.getWhenAvailable() == null) {
return 0;
}
else if(this.getWhenAvailable() == null && other.getWhenAvailable() != null) {
return -1;
}
else if(this.getWhenAvailable() !=null && other.getWhenAvailable() == null) {
return 1;
}
else if(this.getWhenAvailable() !=null && other.getWhenAvailable() != null) {
if(this.getWhenAvailable().equals(other.getWhenAvailable())) {
return 0;
}
else if(this.getWhenAvailable().isBefore(other.getWhenAvailable())) {
return -1;
}
else if(this.getWhenAvailable().isAfter(other.getWhenAvailable())) {
return 1;
}
}
return 0;
}
/**
* Intended use is only for JUnit testing when used with reflection
* @param wA set whenAvailable time
*/
private void setWhenAvailable(LocalTime wA) {
this.whenAvailable = wA;
}
} //跑道尽头class ------------------------------ ------
下面是一个class，通过优先级队列实现了compareTo方法：
public class stackExchange {
public static void main(String[] args) {
Flight f1 = new Flight("00:01", "ARRIVAL","A001");
Flight f2 = new Flight("00:00", "DEPARTURE","D001");
Flight f3 = new Flight("00:01", "DEPARTURE","D002");
Flight f4 = new Flight("00:00", "DEPARTURE","D003");
PriorityQueue<Flight> flightsPQ = new PriorityQueue<Flight>();
flightsPQ.add(f1);
flightsPQ.add(f2);
flightsPQ.add(f3);
flightsPQ.add(f4);
Runway r1 = new Runway();
r1.setRunwayNumber(1);
Runway r2 = new Runway();
r2.setRunwayNumber(2);
Runway r3 = new Runway();
r3.setRunwayNumber(3);
Runway r4 = new Runway();
r4.setRunwayNumber(4);
PriorityQueue<Runway> runwaysPQ = new PriorityQueue<Runway>();
runwaysPQ.add(r1);
runwaysPQ.add(r2);
runwaysPQ.add(r3);
runwaysPQ.add(r4);
while(!flightsPQ.isEmpty()) {
Flight tmpFlight = flightsPQ.poll(); //remove priority flight from flightsPQ
Runway tmpRunway = runwaysPQ.poll(); //remove priority runway from runwaysPQ
tmpRunway.assignFlight(tmpFlight, tmpFlight.getScheduledTime(), tmpFlight.getReserveTime()); //assign the priority flight to the runwy
tmpFlight.setActualTime(tmpRunway.getActualTimeRunway()); //set the actual time the flight was used
tmpFlight.setRunwayUsed(tmpRunway); //tell the flight which runway it used
//print out the flight data that used the runway and the number of the runway used
//format: scheduledTime of flight | eventType | identifier | actualTime the flight used the runway | the number of the runway used (used to distinguish runway over
// other runways
System.out.println(tmpFlight.getScheduledTime() + "|" + tmpFlight.getEvent() + "|" + tmpFlight.getIdent() + "|" + tmpFlight.getActualTime()
+ "|" + tmpFlight.getRunwayUsed().getRunwayNumber());
runwaysPQ.add(tmpRunway); //add the runway back into runwaysPQ
}
} //end of main
} //stackExchange 结束 class
一开始whenAvailable是空的，所以所有跑道的优先级是一样的。根据文档：
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.
所以您可能应该首先比较可用时间，如果您想要一致的排序，然后还要比较跑道的数量。
要么是我对优先级队列工作原理的理解不正确，要么是我的 compareTo 方法覆盖了 Comparable 接口存在逻辑错误。我正在尝试将最高优先级的跑道分配给正在着陆或起飞的飞机。在以下场景中，有四个航班和四个跑道可用。因此，每个航班都按预定时间降落或起飞。
格式为：
scheduledTime|eventType|flightIdentifier|runwayUsed
00:01|ARRIVAL|A001|null
00:00|DEPARTURE|D001|null
00:01|DEPARTURE|D002|null
00:00|DEPARTURE|D003|null
将航班分配到优先跑道后（'polling'条跑道对象优先队列中的优先跑道），结果为
00:01|ARRIVAL|A001| 1
00:00|DEPARTURE|D001| 4
00:01|DEPARTURE|D002| 2
00:00|DEPARTURE|D003| 3
但是，假设我的 compareTo 方法没有逻辑错误，输出应该是：
00:01|ARRIVAL|A001| 1
00:00|DEPARTURE|D001| 2
00:01|DEPARTURE|D002| 3
00:00|DEPARTURE|D003| 4
这是包含 compareTo 方法的跑道 class：
public class Runway implements Comparable<Runway>{
//instance or class variables
private LocalTime whenAvailable; //when the runway is available
private LocalTime actualTime; //actual time the plane arrived or departed
private List<Flight> flights; //the flights that have been assigned to the runway
private Integer runwayNumber; // the number of the runway. for ex., 1 = Runway 1.
private LocalTime previousSchedTime; //the most recent previous time that the runway was scheduled for arrival or departure. This is just used
// for testing purposes.
/**
* Constructor
*/
protected Runway() {
whenAvailable = null;
flights = new ArrayList<Flight>();
}
/**
* Determine if the runway is available
* @param currentTime The scheduled time of the flight
* @return true if the runway is available or false if it is not
*/
protected boolean isAvailable(LocalTime currentTime) {
if(currentTime == null) {
throw new IllegalArgumentException();
}
return whenAvailable == null || !currentTime.isBefore(whenAvailable); // currentTime >= whenAvailable
}
/**
* Assign flight to the runway, i.e., set the actual time a flight uses the runway and the time ruwnay will be available again
* @param flight The flight being assigned to the runway
* @param scheduledTime The scheduled time of the flight
* @param reserveTime The arrival or departure reserve times of the flight
*/
protected void assignFlight(Flight flight, LocalTime scheduledTime, int reserveTime) {
//if the runway is available
if(isAvailable(scheduledTime)) {
//Set the actual time of the flight and when the runway will be available again
//if the runway is null and available
if(whenAvailable == null) {
actualTime = scheduledTime;
whenAvailable = scheduledTime.plusMinutes(reserveTime);
}
//if runway is available and the scheduled time of flight is equal to when the runway is available
else if(scheduledTime == whenAvailable || scheduledTime.isBefore(whenAvailable)) {
actualTime = whenAvailable;
whenAvailable = actualTime.plusMinutes(reserveTime);
}
else { //if scheduledTime > whenAvailable
actualTime = scheduledTime;
whenAvailable = actualTime.plusMinutes(reserveTime);
}
}
//if the runway is not available aka currentTime < whenAvailable
else {
actualTime = whenAvailable;
whenAvailable = actualTime.plusMinutes(reserveTime);
}
flights.add(flight);
previousSchedTime = scheduledTime; //update previousSchedTime to scheduledTime
}
/**
*
* @return acutialTime the runway was used by flight
*/
protected LocalTime getActualTimeRunway() {
return actualTime;
}
/**
*
* @return the time the runway is available
*/
protected LocalTime getWhenAvailable() {
return whenAvailable;
}
/**
*
* @return List of all the flights that used the runway
*/
protected List<Flight> getFlights(){
List<Flight> tmpList = new LinkedList<Flight>();
for(Flight f : flights) {
tmpList.add(f);
}
return tmpList;
}
/**
*
* @param runwayNumber set the number of the runway
*/
protected void setRunwayNumber(int runwayNumber) {
if(runwayNumber < 1) {
throw new IllegalArgumentException();
} //end of if
this.runwayNumber = runwayNumber;
}
/**
*
* @return the number of the runway
*/
protected Integer getRunwayNumber() {
return runwayNumber;
}
/**
*
* @return the most recent previous time that the runway was scheduled for arrival or departure. This is used
// as a condition in the assignFlight method below
*/
protected LocalTime getPreviousSchedTime() {
return previousSchedTime;
}
/**
* NOTE: this is intended to only be used for testing in other classes when used with reflection
* @param previousSchedTime sets the previousScedTime
*/
private void setPreviousSchedTime(LocalTime previousSchedTime) {
this.previousSchedTime = previousSchedTime;
}
/**
* Override compareTo method of Comparable interface
* Set priority of runway instance when compared other runway instances
*/
@Override
public int compareTo(Runway other) {
if(this.getWhenAvailable() == null && other.getWhenAvailable() == null) {
return 0;
}
else if(this.getWhenAvailable() == null && other.getWhenAvailable() != null) {
return -1;
}
else if(this.getWhenAvailable() !=null && other.getWhenAvailable() == null) {
return 1;
}
else if(this.getWhenAvailable() !=null && other.getWhenAvailable() != null) {
if(this.getWhenAvailable().equals(other.getWhenAvailable())) {
return 0;
}
else if(this.getWhenAvailable().isBefore(other.getWhenAvailable())) {
return -1;
}
else if(this.getWhenAvailable().isAfter(other.getWhenAvailable())) {
return 1;
}
}
return 0;
}
/**
* Intended use is only for JUnit testing when used with reflection
* @param wA set whenAvailable time
*/
private void setWhenAvailable(LocalTime wA) {
this.whenAvailable = wA;
}
} //跑道尽头class ------------------------------ ------
下面是一个class，通过优先级队列实现了compareTo方法：
public class stackExchange {
public static void main(String[] args) {
Flight f1 = new Flight("00:01", "ARRIVAL","A001");
Flight f2 = new Flight("00:00", "DEPARTURE","D001");
Flight f3 = new Flight("00:01", "DEPARTURE","D002");
Flight f4 = new Flight("00:00", "DEPARTURE","D003");
PriorityQueue<Flight> flightsPQ = new PriorityQueue<Flight>();
flightsPQ.add(f1);
flightsPQ.add(f2);
flightsPQ.add(f3);
flightsPQ.add(f4);
Runway r1 = new Runway();
r1.setRunwayNumber(1);
Runway r2 = new Runway();
r2.setRunwayNumber(2);
Runway r3 = new Runway();
r3.setRunwayNumber(3);
Runway r4 = new Runway();
r4.setRunwayNumber(4);
PriorityQueue<Runway> runwaysPQ = new PriorityQueue<Runway>();
runwaysPQ.add(r1);
runwaysPQ.add(r2);
runwaysPQ.add(r3);
runwaysPQ.add(r4);
while(!flightsPQ.isEmpty()) {
Flight tmpFlight = flightsPQ.poll(); //remove priority flight from flightsPQ
Runway tmpRunway = runwaysPQ.poll(); //remove priority runway from runwaysPQ
tmpRunway.assignFlight(tmpFlight, tmpFlight.getScheduledTime(), tmpFlight.getReserveTime()); //assign the priority flight to the runwy
tmpFlight.setActualTime(tmpRunway.getActualTimeRunway()); //set the actual time the flight was used
tmpFlight.setRunwayUsed(tmpRunway); //tell the flight which runway it used
//print out the flight data that used the runway and the number of the runway used
//format: scheduledTime of flight | eventType | identifier | actualTime the flight used the runway | the number of the runway used (used to distinguish runway over
// other runways
System.out.println(tmpFlight.getScheduledTime() + "|" + tmpFlight.getEvent() + "|" + tmpFlight.getIdent() + "|" + tmpFlight.getActualTime()
+ "|" + tmpFlight.getRunwayUsed().getRunwayNumber());
runwaysPQ.add(tmpRunway); //add the runway back into runwaysPQ
}
} //end of main
} //stackExchange 结束 class
一开始whenAvailable是空的，所以所有跑道的优先级是一样的。根据文档：
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.
所以您可能应该首先比较可用时间，如果您想要一致的排序，然后还要比较跑道的数量。