Airport Simulation (数据结构与算法 - 队列 / Queue 的应用)

Airport Simulation 是数据结构与算法教材中用于演示 Queue 的一个小程序（大多数教师似乎会跳过这个练习）。主程序会通过输入总的运行时间、队列里可以等待的最多飞机数量，平均每个时间单元到来的飞机和离开的飞机（提供泊松分布的均值生成随机数）。

运行效果

程序的结构不算复杂，利用 Runaway 类来封装两个 landing 和 takeoff 队列，处理飞机的请求和行为；Plane 类来封装飞机的状态和信息，以及在受到指令时输出信息到控制台。只是教材里的讲述有些分散，运行效果也由于输出太多而显得凌乱无比。练习布置许久之后也是一直没有找到一整块时间写完这个练习。这里是前几天完成的一个经过输出优化后的程序，格式比较易于观测。

该程序应在 Linux 或 macOS 下编译。在 Windows 下编译由于不支持彩色输出会出现一些奇怪的转移序列，sleep 函数和 usleep 函数也应当用 windows.h 中提供的方法实现。

main.cpp 和 Random.h 的源代码如下。其中 Random.h 用于提供泊松分布的随机数生成，参考自 CSDN。

你可以在这里直接下载：https://cloud.billc.io/s/FeLekECBFKb6GkF

#include <iostream>
#include <queue>
#include <unistd.h>
#include "Random.h"
using namespace std;
typedef int feedback;
const int success = 1;
const int fail = 0;
const int USPEED_SHORT = 1000;
const int USPEED_LONG = 1000;
enum flightStatus{
	null,
	toLand,
	toTakeoff
};
enum runawayAct{
	idle,
	letTakeoff,
	letLand
};
string percentage(int A, int B){
	char *temp = new char[100];
	sprintf(temp, "%3.2f%%", (double)A / (double)B * 100);
	string output = temp;
	return output;
}
class Plane{
  private:
	int ID;
	int comingTime;
	flightStatus status;
  public:
  	Plane(){
		ID = -1;
		comingTime = -1;
		status = null;
	}
	Plane(int _ID, int _comingTime, flightStatus _status){
		usleep(USPEED_SHORT);
		ID = _ID;
		comingTime = _comingTime;
		status = _status;
		cout << "[PLANE MESSAGE] Plane NO." << ID << " is applying to " << ((status == toLand) ? "land " : "take off ") << endl;
	}
	feedback land(int currentTime){
		usleep(USPEED_LONG);
		cout << "\033[42m[PLANE MESSAGE] Plane NO." << ID << " has landed safely.\033[0m" << endl
			 << "                Waiting time before landing: " << currentTime - comingTime << "." << endl;
	}
	feedback takeoff(int currentTime){
		usleep(USPEED_LONG);
		cout << "\033[42m[PLANE MESSAGE] Plane NO." << ID << " has taken off.\033[0m" << endl
			 << "                Waiting time before taking off: " << currentTime - comingTime << "." << endl;
	}
	feedback reject(int currentTime){
		usleep(USPEED_LONG);
		if(status == toLand){
			cout << "\033[41m[AIRPORT MESSAGE] Plane NO." << ID << "'s landing request is rejected.\033[0m" << endl
				 << "                  It has been directed to other airports." << endl;
		}
		else{
			cout << "\033[41m[AIRPORT MESSAGE] Plane NO." << ID << " 's taking off request is rejected.\033[0m" << endl
				 << "                  This flight is delayed." << endl;
		}
	}
	int getTime(){
		return comingTime;
	}
};

class Runaway{
  private:
	queue<Plane> landingQueue;
	queue<Plane> takeoffQueue;
	int limit;
	runawayAct act;
	int landingRequests;
	int landingAccepted;
	int landingRejected;
	int takeoffRequests;
	int takeoffAccepted;
	int takeoffRejected;
	int idleUnit;
	int landingWaitedTime;
	int takeoffWaitedTime;

  public:
	Runaway(int _limit){
		limit = _limit;
		landingRequests = 0;
		landingAccepted = 0;
		takeoffRequests = 0;
		takeoffAccepted = 0;
		takeoffRejected = 0;
		idleUnit = 0;
		landingWaitedTime = 0;
		takeoffWaitedTime = 0;
	}
	feedback CanLand(const Plane &current){
		landingRequests++;
		feedback result;
		if (landingQueue.size() < limit){
			result = success;
			landingQueue.push(current);
		}
		else{
			result = fail;
			landingRejected++;
		}
		return result;
	}
	feedback CanTakeoff(const Plane &current){
		takeoffRequests++;
		feedback result;
		if (takeoffQueue.size() < limit){
			result = success;
			takeoffQueue.push(current);
		}
		else{
			result = fail;
			takeoffRejected++;
		}
		return result;
	}
	runawayAct Act(int timeNow, Plane &moving){
		runawayAct result;
		if (!landingQueue.empty()){
			landingAccepted++;
			moving = landingQueue.front();
			landingWaitedTime += timeNow - moving.getTime();
			landingQueue.pop();
			return letLand;
		}
		else if(!takeoffQueue.empty()){
			takeoffAccepted++;
			moving = takeoffQueue.front();
			takeoffWaitedTime += timeNow - moving.getTime();
			takeoffQueue.pop();
			return letTakeoff;
		}
		else{
			idleUnit++;
			return idle;
		}
	}
	void SumUp(int simulationTime){
		cout << endl;
		cout << "\033[36m=============== SIMULATION RESULTS ===============\033[0m" << endl
			 << "\033[5;3mCalculating...\033[0m" << endl;
		sleep(2);
		cout
			<< "\033[1ATotal simulation time:                         " << simulationTime << endl
			<< "Total flights simulated:                       " << landingRequests + takeoffRequests << endl
			<< "Total flights required to land:                " << landingRequests << endl
			<< "Landing request accepted:                      " << landingAccepted << endl
			<< "Landing request rejected:                      " << landingRejected << endl
			<< "Total flights required to take off:            " << takeoffRequests << endl
			<< "Taking off request accepted:                   " << takeoffAccepted << endl
			<< "Taking off request rejected:                   " << takeoffRejected << endl
			<< "Flights still left in landing queue:           " << landingQueue.size() << endl
			<< "Flights still left in taking off queue:        " << takeoffQueue.size() << endl
			<< "Average waiting time in landing queue:         " << (float)landingWaitedTime / (float)landingAccepted << endl
			<< "Average waiting time in taking off queue:      " << (float)takeoffWaitedTime / (float)takeoffAccepted << endl
			<< "Average observing time for landing flights:    " << (float)landingRequests / (float)simulationTime << endl
			<< "Average observing time for taking off flights: " << (float)takeoffRequests / (float)simulationTime << endl
			<< "Ratio for successfully landed flights:         " << percentage(landingAccepted, landingRequests) << endl
			<< "Ratio for successfully took off flights:       " << percentage(landingAccepted, landingRequests) << endl
			<< "Ratio of runaway idle time:                    " << percentage(idleUnit, simulationTime) << endl
			<< endl
			<< "\033[3;2mSimulation finished.\033[0m" << endl;
	}
};
void initilize(int &totalTime, int &queueLimit, float &arrivingRate, float &departureRate){
	cout << "\033[2J\033[0;0H";
	cout << "Welcome to the \033[46mAIRPORT SIMULATOR\033[0m." << endl;
	sleep(1);
	cout << "\033[36mPlease enter how many time units you will simulate:\033[0m\n"
		 << flush;
	cin >> totalTime;
	cout << "\033[36mHow many flights can be waiting to land or takeoff?\033[0m" << endl
		 << flush;
	cin >> queueLimit;
	cout << "\033[36mWhat is the expected arriving flights per unit time?\033[0m" << endl
		 << flush;
	cin >> arrivingRate;
	cout << "\033[36mWhat is the expected departing flights per unit time?\033[0m" << endl
		 << flush;
	cin >> departureRate;
}

int main(){
START:
	float arrivingRate, departureRate;
	int totalTime, queueLimit;
	initilize(totalTime, queueLimit, arrivingRate, departureRate);
	int currentTime;
	int planeID = 0;
	Random randomSeed;
	Runaway airport(queueLimit);
	for (currentTime = 0; currentTime < totalTime; currentTime++){
		cout << "\033[2m----- Current excution time: " << currentTime << " -----\033[0m" << endl;
		int comingPerUnit = randomSeed.poisson(arrivingRate);
		for (int num = 0; num < comingPerUnit; num++, planeID++){
			Plane currentPlane(planeID, currentTime, toLand);
			if(airport.CanLand(currentPlane)==fail){
				currentPlane.reject(currentTime);
			}
		}
		int departingPerUnit = randomSeed.poisson(departureRate);
		for (int num = 0; num < departingPerUnit; num++, planeID++){
			Plane currentPlane(planeID, currentTime, toTakeoff);
			if(airport.CanTakeoff(currentPlane)==fail){
				currentPlane.reject(currentTime);
			}
		}
		Plane movingPlane;
		switch (airport.Act(currentTime, movingPlane)){
		case letLand:
			movingPlane.land(currentTime);
			break;
		case letTakeoff:
			movingPlane.takeoff(currentTime);
			break;
		case idle:
			cout << "\033[46m[AIRPORT MESSAGE]: Runaway is idle.\033[0m" << endl;
			break;
		}
	}
	airport.SumUp(totalTime);
	char ch;
	cout << "\033[36mDo you want to initialize another simulation? \n([R] or [r] to restart, any other key to exit.)\033[0m" << endl;
	while(cin.get()!='\n')
		;
	if (toupper(ch = cin.get()) == 'R')
		goto START;
	return 0;
}

#ifndef RANDOM_H_INCLUDED
#define RANDOM_H_INCLUDED

#include <iostream>
#include <time.h>
#include <limits.h>
#include <math.h>

using namespace std;

class Random
{

  public:
    Random(bool pseudo = true);
    double random_real();
    int random_integer(int low, int high);
    int poisson(double mean);

  private:
    int reseed();                 //  Re-randomize the seed.
    int seed, multiplier, add_on; //  constants for use in arithmetic operations
};
#include "Random.h"

Random::Random(bool pseudo)
/*Post: The values of seed, add_on, and multiplier are
        initialized.  The seed is initialized randomly only if pseudo == false.
*/
{
    if (pseudo)
        seed = 1;
    else
        seed = time(NULL) % INT_MAX;
    multiplier = 2743; // 斜率
    add_on = 5923;     // 位移
}

int Random::reseed()
//Post: The seed is replaced by a pseudorandom successor.
{
    seed = seed * multiplier + add_on;
    return seed;
}

double Random::random_real()
/\*Post: A random real number between 0 and 1 is returned.\*/
{
    double max = INT_MAX + 1.0; //INT_MAX = (2)31 -1
    double temp = reseed();
    if (temp < 0)
        temp = temp + max;
    return temp / max;
}

int Random::random_integer(int low, int high) // 这个函数在泊松分布中没有用到
{
    double max = INT_MAX + 1.0; //INT_MAX = (2)31 -1
    double temp = reseed();
    if (temp < 0)
        temp = temp + max;
    return (int)(temp / (max / (high - low + 1.0) + low)); // 返回整数，且有规定范围
}

int Random::poisson(double mean) // 泊松分布的实现
{
    double x = -1;
    double u;
    double log1, log2;
    log1 = 0;
    log2 = -mean;
    do
    {
        u = random_real();
        log1 += log(u);
        x++;
    } while (log1 >= log2);
    return x;
}
#endif // RANDOM_H_INCLUDED