DESim Example with Hash Table, C++ (clang)

DESim Example with Hash Table

Language: Layout:

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

// Define the time data type
#define TimeType int

// Define constants used in our simulation
#define TEST_SIZE 40
#define NUM_NAMES 6
string firstNames[NUM_NAMES] = {"Alice","Ambroise","Bert","Denise","Larry","Emily"};
string lastNames[NUM_NAMES] = {"Ghosh","Jones","Lee","Smith","Zhang","Zuckerman"};
#define SIM_LENGTH 100
#define MAX_DURATION 10
#define NUM_TELLERS 4

// Define event types
typedef enum {ARRIVAL, DEPARTURE} EventType;

// Define an event struct to store events
typedef struct {
	string customerName;
	TimeType arrivalTime; // time the customer walks in the door
	TimeType eventTime; // could be either arrival or departure time, used in priority queue
	TimeType startTime; // actual time the customer gets a teller
	TimeType duration;
	EventType eventType;
} EventStruct;

// Define an stats struct to store statistics
typedef struct {
	int numTransactions;
	TimeType totalDuration;
	TimeType totalWaitTime;
    vector<TimeType> waitTimes; 
} StatsStruct;

// A standard way of printing events
void printEvent(const EventStruct & event)
{
	cout << event.customerName;
	cout << ", Event Time: " << event.eventTime;
	cout << ", Duration: " << event.duration;
	cout << ", Event type: ";
	if (event.eventType==ARRIVAL) cout << "ARRIVAL";
	else cout << "DEPARTURE";
}

// How to compare event times for the priority queue
struct compareEventTime
{
	bool operator()(const EventStruct& lhs, const EventStruct& rhs) const
	{
		return lhs.eventTime > rhs.eventTime;
	}
};

// Our Discrete Event Simulation class
class DESim
{
private:
	// event queue -- priority queue with events queued by event time
	priority_queue<EventStruct,vector<EventStruct>,compareEventTime> eventQueue;
	// wait queue -- priority queue with waiting customers queued by arrival time
	queue<EventStruct> bankQueue;
	// statsDB -- a hash table to store statistics on each customer's bank visits
	unordered_map<string,StatsStruct> statsDB;
	TimeType currentTime = 0;
	TimeType totalDurationAssigned = 0;
	TimeType tellerQuitingTime = SIM_LENGTH;
	bool debugOn = false;
	int tellersAvailable = NUM_TELLERS;
public:
	void addArrivalEvent();
	void addDepartureEvent(EventStruct & event);
	void addBankQueueCustomer(const EventStruct & event);
	void updateCustomerDB(const EventStruct & event);
	void setDebugOn(bool value) {debugOn = value;};
	void printTime() {cout << "[" << currentTime << "] ";};
	void printTellerNumberChange();
	void printStats();
	void runSim();
}; // end DESim

// Add an arrival priority queue event
void DESim::addArrivalEvent()
{
	EventStruct myEvent;
	myEvent.customerName = firstNames[rand()%NUM_NAMES] + string(" ")
	                       + lastNames[rand()%NUM_NAMES];
	myEvent.arrivalTime = rand()%SIM_LENGTH+1;
	myEvent.eventTime = myEvent.arrivalTime; // the event is an arrival, so use this time
	myEvent.startTime = -1;
	myEvent.duration = rand()%MAX_DURATION+1;
	myEvent.eventType = ARRIVAL;
	totalDurationAssigned += myEvent.duration;
	if (debugOn) {printTime(); cout << "Adding event: "; printEvent(myEvent); cout << endl;}
	eventQueue.push(myEvent);
}

// Add a departure priority queue event
void DESim::addDepartureEvent(EventStruct & event)
{
	event.startTime = currentTime;
	event.eventTime = event.startTime + event.duration;
	event.eventType = DEPARTURE;
	if (debugOn) {printTime(); cout << "Adding event: "; printEvent(event); cout << endl;}
	eventQueue.push(event);
	updateCustomerDB(event);
	if (event.eventTime > tellerQuitingTime) tellerQuitingTime = event.eventTime;
}

// Add a bank queue customer to wait for a teller (not a priority queue event)
void DESim::addBankQueueCustomer(const EventStruct & event)
{
	if (debugOn) {printTime(); cout << "Adding bank queue customer: "; printEvent(event); cout << endl;}
	bankQueue.push(event);
}

// Update stats DB with a customer's experience at our bank
void DESim::updateCustomerDB(const EventStruct & event)
{
	// compute the wait time (if any) based on the current time...
	TimeType waitTime = currentTime - event.arrivalTime;
	// before C++11 had to do the following; however, now can use "auto" data type!
	// unordered_map<string,int>::const_iterator hashTablePointer = customerHashTable.find(customerName);
	auto hashTablePointer = statsDB.find(event.customerName);
	if (hashTablePointer == statsDB.end() ) {
		if (debugOn) {printTime(); cout << event.customerName << " not found in customer DB " << endl;}
		StatsStruct stats;
		stats.numTransactions = 1;
		stats.totalDuration = event.duration;
		stats.totalWaitTime = waitTime;
        stats.waitTimes.push_back(waitTime); 
		statsDB[event.customerName] = stats;
	} else {
		if (debugOn) {printTime(); cout << event.customerName << " found in customer DB " << endl;}
		statsDB[event.customerName].numTransactions++;
		statsDB[event.customerName].totalDuration += event.duration;
		statsDB[event.customerName].totalWaitTime += waitTime;
        statsDB[event.customerName].waitTimes.push_back(waitTime); 
	}
}

// Print the customer statistics from the customer DB
void DESim::printStats()
{
	TimeType totalDurationSimulated = 0;
	for (auto local_it = statsDB.begin(); local_it!= statsDB.end(); ++local_it) {
		cout << "Customer Name: " << local_it->first << endl;
		cout << "    Number of transactions: " << local_it->second.numTransactions << endl;
		cout << "    Total duration: " << local_it->second.totalDuration << endl;
		cout << "    Total wait time: " << local_it->second.totalWaitTime << endl;
        
        cout << "    Wait Times: "; 
        
        for(int i = 0; i < local_it->second.waitTimes.size(); i++){
            cout << local_it->second.waitTimes[i] << " "; 
        }
        
        cout << endl << endl; 
        
		totalDurationSimulated += local_it->second.totalDuration;
	}
	cout << "\nTotal duration scheduled: " << totalDurationSimulated << endl;
	cout << "Total duration simulated: " << totalDurationAssigned << endl << endl;
	cout << "Teller quiting time: " << tellerQuitingTime << endl;
	cout << "Teller utilization: " << (float) totalDurationAssigned
	/ ((float)(NUM_TELLERS * tellerQuitingTime)) << endl;
}

// Indicate that the number of available tellers has changed for debugging
void DESim::printTellerNumberChange()
{
	if (debugOn) {cout << "[" << currentTime <<"] Current number of tellers available: " << tellersAvailable << endl;}
}

// Run the simulation
void DESim::runSim()
{
	while (!eventQueue.empty()) {
		EventStruct nextEvent = eventQueue.top(); // get next event in priority queue
		currentTime = nextEvent.eventTime;
		eventQueue.pop();
		switch (nextEvent.eventType) {
		case ARRIVAL:
			if (tellersAvailable) {
				// enter departure event in eventQueue
				addDepartureEvent(nextEvent);
				tellersAvailable--;
				printTellerNumberChange();
			} else {
				// no tellers available, put customer in bank queue
				addBankQueueCustomer(nextEvent);
			}
			break;
		case DEPARTURE:
			if(!bankQueue.empty()) {
				EventStruct nextCustomer = bankQueue.front();
				bankQueue.pop();
				addDepartureEvent(nextCustomer);
			} else {
				tellersAvailable++;
				printTellerNumberChange();
			}
			break;
		default:
			cout << "ERROR: Should never get here! " << endl;
		}
	}
}

int main()
{
	cout << "*** Discrete Event Simulation Example for ECE 2574 ***\n\n";
	DESim mySim;
	mySim.setDebugOn(true);
	srand(123321);
	cout << "Adding " << TEST_SIZE << " events...\n";
	for (int i=0; i<TEST_SIZE; i++) {
		mySim.addArrivalEvent();
	}
	cout << "\nRunning the DES...\n";
	mySim.runSim();
	cout << "\nPrinting out the customer statistics and teller utilization...\n";
	mySim.printStats();
	return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.83 sec, absolute running time: 0.2 sec, cpu time: 0.1 sec, memory peak: 3 Mb, absolute service time: 2,05 sec

*** Discrete Event Simulation Example for ECE 2574 *** Adding 40 events... [0] Adding event: Alice Zuckerman, Event Time: 66, Duration: 1, Event type: ARRIVAL [0] Adding event: Ambroise Ghosh, Event Time: 13, Duration: 6, Event type: ARRIVAL [0] Adding event: Alice Lee, Event Time: 62, Duration: 5, Event type: ARRIVAL [0] Adding event: Bert Smith, Event Time: 6, Duration: 9, Event type: ARRIVAL [0] Adding event: Alice Ghosh, Event Time: 55, Duration: 5, Event type: ARRIVAL [0] Adding event: Larry Zhang, Event Time: 6, Duration: 6, Event type: ARRIVAL [0] Adding event: Alice Zhang, Event Time: 1, Duration: 8, Event type: ARRIVAL [0] Adding event: Ambroise Ghosh, Event Time: 14, Duration: 3, Event type: ARRIVAL [0] Adding event: Larry Lee, Event Time: 53, Duration: 10, Event type: ARRIVAL [0] Adding event: Ambroise Ghosh, Event Time: 47, Duration: 8, Event type: ARRIVAL [0] Adding event: Bert Jones, Event Time: 94, Duration: 9, Event type: ARRIVAL [0] Adding event: Bert Zhang, Event Time: 98, Duration: 3, Event type: ARRIVAL [0] Adding event: Bert Jones, Event Time: 80, Duration: 5, Event type: ARRIVAL [0] Adding event: Emily Lee, Event Time: 52, Duration: 8, Event type: ARRIVAL [0] Adding event: Alice Ghosh, Event Time: 17, Duration: 9, Event type: ARRIVAL [0] Adding event: Alice Smith, Event Time: 1, Duration: 1, Event type: ARRIVAL [0] Adding event: Larry Lee, Event Time: 42, Duration: 2, Event type: ARRIVAL [0] Adding event: Bert Ghosh, Event Time: 1, Duration: 1, Event type: ARRIVAL [0] Adding event: Ambroise Jones, Event Time: 1, Duration: 1, Event type: ARRIVAL [0] Adding event: Emily Zuckerman, Event Time: 33, Duration: 6, Event type: ARRIVAL [0] Adding event: Alice Zuckerman, Event Time: 100, Duration: 4, Event type: ARRIVAL [0] Adding event: Ambroise Smith, Event Time: 53, Duration: 7, Event type: ARRIVAL [0] Adding event: Denise Ghosh, Event Time: 15, Duration: 6, Event type: ARRIVAL [0] Adding event: Bert Zhang, Event Time: 39, Duration: 3, Event type: ARRIVAL [0] Adding event: Alice Zuckerman, Event Time: 4, Duration: 3, Event type: ARRIVAL [0] Adding event: Denise Jones, Event Time: 93, Duration: 8, Event type: ARRIVAL [0] Adding event: Bert Ghosh, Event Time: 18, Duration: 2, Event type: ARRIVAL [0] Adding event: Alice Jones, Event Time: 19, Duration: 5, Event type: ARRIVAL [0] Adding event: Ambroise Zuckerman, Event Time: 51, Duration: 9, Event type: ARRIVAL [0] Adding event: Bert Zhang, Event Time: 35, Duration: 2, Event type: ARRIVAL [0] Adding event: Denise Zhang, Event Time: 68, Duration: 4, Event type: ARRIVAL [0] Adding event: Alice Jones, Event Time: 36, Duration: 9, Event type: ARRIVAL [0] Adding event: Alice Lee, Event Time: 31, Duration: 9, Event type: ARRIVAL [0] Adding event: Denise Ghosh, Event Time: 76, Duration: 6, Event type: ARRIVAL [0] Adding event: Ambroise Zhang, Event Time: 89, Duration: 10, Event type: ARRIVAL [0] Adding event: Emily Lee, Event Time: 56, Duration: 5, Event type: ARRIVAL [0] Adding event: Ambroise Jones, Event Time: 64, Duration: 1, Event type: ARRIVAL [0] Adding event: Alice Smith, Event Time: 32, Duration: 4, Event type: ARRIVAL [0] Adding event: Alice Lee, Event Time: 9, Duration: 3, Event type: ARRIVAL [0] Adding event: Denise Smith, Event Time: 14, Duration: 7, Event type: ARRIVAL Running the DES... [1] Adding event: Alice Zhang, Event Time: 9, Duration: 8, Event type: DEPARTURE [1] Alice Zhang not found in customer DB [1] Current number of tellers available: 3 [1] Adding event: Alice Smith, Event Time: 2, Duration: 1, Event type: DEPARTURE [1] Alice Smith not found in customer DB [1] Current number of tellers available: 2 [1] Adding event: Bert Ghosh, Event Time: 2, Duration: 1, Event type: DEPARTURE [1] Bert Ghosh not found in customer DB [1] Current number of tellers available: 1 [1] Adding event: Ambroise Jones, Event Time: 2, Duration: 1, Event type: DEPARTURE [1] Ambroise Jones not found in customer DB [1] Current number of tellers available: 0 [2] Current number of tellers available: 1 [2] Current number of tellers available: 2 [2] Current number of tellers available: 3 [4] Adding event: Alice Zuckerman, Event Time: 7, Duration: 3, Event type: DEPARTURE [4] Alice Zuckerman not found in customer DB [4] Current number of tellers available: 2 [6] Adding event: Bert Smith, Event Time: 15, Duration: 9, Event type: DEPARTURE [6] Bert Smith not found in customer DB [6] Current number of tellers available: 1 [6] Adding event: Larry Zhang, Event Time: 12, Duration: 6, Event type: DEPARTURE [6] Larry Zhang not found in customer DB [6] Current number of tellers available: 0 [7] Current number of tellers available: 1 [9] Adding event: Alice Lee, Event Time: 12, Duration: 3, Event type: DEPARTURE [9] Alice Lee not found in customer DB [9] Current number of tellers available: 0 [9] Current number of tellers available: 1 [12] Current number of tellers available: 2 [12] Current number of tellers available: 3 [13] Adding event: Ambroise Ghosh, Event Time: 19, Duration: 6, Event type: DEPARTURE [13] Ambroise Ghosh not found in customer DB [13] Current number of tellers available: 2 [14] Adding event: Ambroise Ghosh, Event Time: 17, Duration: 3, Event type: DEPARTURE [14] Ambroise Ghosh found in customer DB [14] Current number of tellers available: 1 [14] Adding event: Denise Smith, Event Time: 21, Duration: 7, Event type: DEPARTURE [14] Denise Smith not found in customer DB [14] Current number of tellers available: 0 [15] Current number of tellers available: 1 [15] Adding event: Denise Ghosh, Event Time: 21, Duration: 6, Event type: DEPARTURE [15] Denise Ghosh not found in customer DB [15] Current number of tellers available: 0 [17] Current number of tellers available: 1 [17] Adding event: Alice Ghosh, Event Time: 26, Duration: 9, Event type: DEPARTURE [17] Alice Ghosh not found in customer DB [17] Current number of tellers available: 0 [18] Adding bank queue customer: Bert Ghosh, Event Time: 18, Duration: 2, Event type: ARRIVAL [19] Adding event: Bert Ghosh, Event Time: 21, Duration: 2, Event type: DEPARTURE [19] Bert Ghosh found in customer DB [19] Adding bank queue customer: Alice Jones, Event Time: 19, Duration: 5, Event type: ARRIVAL [21] Adding event: Alice Jones, Event Time: 26, Duration: 5, Event type: DEPARTURE [21] Alice Jones not found in customer DB [21] Current number of tellers available: 1 [21] Current number of tellers available: 2 [26] Current number of tellers available: 3 [26] Current number of tellers available: 4 [31] Adding event: Alice Lee, Event Time: 40, Duration: 9, Event type: DEPARTURE [31] Alice Lee found in customer DB [31] Current number of tellers available: 3 [32] Adding event: Alice Smith, Event Time: 36, Duration: 4, Event type: DEPARTURE [32] Alice Smith found in customer DB [32] Current number of tellers available: 2 [33] Adding event: Emily Zuckerman, Event Time: 39, Duration: 6, Event type: DEPARTURE [33] Emily Zuckerman not found in customer DB [33] Current number of tellers available: 1 [35] Adding event: Bert Zhang, Event Time: 37, Duration: 2, Event type: DEPARTURE [35] Bert Zhang not found in customer DB [35] Current number of tellers available: 0 [36] Adding bank queue customer: Alice Jones, Event Time: 36, Duration: 9, Event type: ARRIVAL [36] Adding event: Alice Jones, Event Time: 45, Duration: 9, Event type: DEPARTURE [36] Alice Jones found in customer DB [37] Current number of tellers available: 1 [39] Adding event: Bert Zhang, Event Time: 42, Duration: 3, Event type: DEPARTURE [39] Bert Zhang found in customer DB [39] Current number of tellers available: 0 [39] Current number of tellers available: 1 [40] Current number of tellers available: 2 [42] Adding event: Larry Lee, Event Time: 44, Duration: 2, Event type: DEPARTURE [42] Larry Lee not found in customer DB [42] Current number of tellers available: 1 [42] Current number of tellers available: 2 [44] Current number of tellers available: 3 [45] Current number of tellers available: 4 [47] Adding event: Ambroise Ghosh, Event Time: 55, Duration: 8, Event type: DEPARTURE [47] Ambroise Ghosh found in customer DB [47] Current number of tellers available: 3 [51] Adding event: Ambroise Zuckerman, Event Time: 60, Duration: 9, Event type: DEPARTURE [51] Ambroise Zuckerman not found in customer DB [51] Current number of tellers available: 2 [52] Adding event: Emily Lee, Event Time: 60, Duration: 8, Event type: DEPARTURE [52] Emily Lee not found in customer DB [52] Current number of tellers available: 1 [53] Adding event: Larry Lee, Event Time: 63, Duration: 10, Event type: DEPARTURE [53] Larry Lee found in customer DB [53] Current number of tellers available: 0 [53] Adding bank queue customer: Ambroise Smith, Event Time: 53, Duration: 7, Event type: ARRIVAL [55] Adding event: Ambroise Smith, Event Time: 62, Duration: 7, Event type: DEPARTURE [55] Ambroise Smith not found in customer DB [55] Adding bank queue customer: Alice Ghosh, Event Time: 55, Duration: 5, Event type: ARRIVAL [56] Adding bank queue customer: Emily Lee, Event Time: 56, Duration: 5, Event type: ARRIVAL [60] Adding event: Alice Ghosh, Event Time: 65, Duration: 5, Event type: DEPARTURE [60] Alice Ghosh found in customer DB [60] Adding event: Emily Lee, Event Time: 65, Duration: 5, Event type: DEPARTURE [60] Emily Lee found in customer DB [62] Current number of tellers available: 1 [62] Adding event: Alice Lee, Event Time: 67, Duration: 5, Event type: DEPARTURE [62] Alice Lee found in customer DB [62] Current number of tellers available: 0 [63] Current number of tellers available: 1 [64] Adding event: Ambroise Jones, Event Time: 65, Duration: 1, Event type: DEPARTURE [64] Ambroise Jones found in customer DB [64] Current number of tellers available: 0 [65] Current number of tellers available: 1 [65] Current number of tellers available: 2 [65] Current number of tellers available: 3 [66] Adding event: Alice Zuckerman, Event Time: 67, Duration: 1, Event type: DEPARTURE [66] Alice Zuckerman found in customer DB [66] Current number of tellers available: 2 [67] Current number of tellers available: 3 [67] Current number of tellers available: 4 [68] Adding event: Denise Zhang, Event Time: 72, Duration: 4, Event type: DEPARTURE [68] Denise Zhang not found in customer DB [68] Current number of tellers available: 3 [72] Current number of tellers available: 4 [76] Adding event: Denise Ghosh, Event Time: 82, Duration: 6, Event type: DEPARTURE [76] Denise Ghosh found in customer DB [76] Current number of tellers available: 3 [80] Adding event: Bert Jones, Event Time: 85, Duration: 5, Event type: DEPARTURE [80] Bert Jones not found in customer DB [80] Current number of tellers available: 2 [82] Current number of tellers available: 3 [85] Current number of tellers available: 4 [89] Adding event: Ambroise Zhang, Event Time: 99, Duration: 10, Event type: DEPARTURE [89] Ambroise Zhang not found in customer DB [89] Current number of tellers available: 3 [93] Adding event: Denise Jones, Event Time: 101, Duration: 8, Event type: DEPARTURE [93] Denise Jones not found in customer DB [93] Current number of tellers available: 2 [94] Adding event: Bert Jones, Event Time: 103, Duration: 9, Event type: DEPARTURE [94] Bert Jones found in customer DB [94] Current number of tellers available: 1 [98] Adding event: Bert Zhang, Event Time: 101, Duration: 3, Event type: DEPARTURE [98] Bert Zhang found in customer DB [98] Current number of tellers available: 0 [99] Current number of tellers available: 1 [100] Adding event: Alice Zuckerman, Event Time: 104, Duration: 4, Event type: DEPARTURE [100] Alice Zuckerman found in customer DB [100] Current number of tellers available: 0 [101] Current number of tellers available: 1 [101] Current number of tellers available: 2 [103] Current number of tellers available: 3 [104] Current number of tellers available: 4 Printing out the customer statistics and teller utilization... Customer Name: Ambroise Zhang Number of transactions: 1 Total duration: 10 Total wait time: 0 Wait Times: 0 Customer Name: Bert Jones Number of transactions: 2 Total duration: 14 Total wait time: 0 Wait Times: 0 0 Customer Name: Denise Zhang Number of transactions: 1 Total duration: 4 Total wait time: 0 Wait Times: 0 Customer Name: Larry Lee Number of transactions: 2 Total duration: 12 Total wait time: 0 Wait Times: 0 0 Customer Name: Bert Zhang Number of transactions: 3 Total duration: 8 Total wait time: 0 Wait Times: 0 0 0 Customer Name: Alice Ghosh Number of transactions: 2 Total duration: 14 Total wait time: 5 Wait Times: 0 5 Customer Name: Alice Lee Number of transactions: 3 Total duration: 17 Total wait time: 0 Wait Times: 0 0 0 Customer Name: Emily Lee Number of transactions: 2 Total duration: 13 Total wait time: 4 Wait Times: 0 4 Customer Name: Alice Jones Number of transactions: 2 Total duration: 14 Total wait time: 2 Wait Times: 2 0 Customer Name: Bert Smith Number of transactions: 1 Total duration: 9 Total wait time: 0 Wait Times: 0 Customer Name: Emily Zuckerman Number of transactions: 1 Total duration: 6 Total wait time: 0 Wait Times: 0 Customer Name: Denise Smith Number of transactions: 1 Total duration: 7 Total wait time: 0 Wait Times: 0 Customer Name: Denise Ghosh Number of transactions: 2 Total duration: 12 Total wait time: 0 Wait Times: 0 0 Customer Name: Alice Zhang Number of transactions: 1 Total duration: 8 Total wait time: 0 Wait Times: 0 Customer Name: Alice Zuckerman Number of transactions: 3 Total duration: 8 Total wait time: 0 Wait Times: 0 0 0 Customer Name: Ambroise Jones Number of transactions: 2 Total duration: 2 Total wait time: 0 Wait Times: 0 0 Customer Name: Ambroise Zuckerman Number of transactions: 1 Total duration: 9 Total wait time: 0 Wait Times: 0 Customer Name: Larry Zhang Number of transactions: 1 Total duration: 6 Total wait time: 0 Wait Times: 0 Customer Name: Bert Ghosh Number of transactions: 2 Total duration: 3 Total wait time: 1 Wait Times: 0 1 Customer Name: Ambroise Ghosh Number of transactions: 3 Total duration: 17 Total wait time: 0 Wait Times: 0 0 0 Customer Name: Denise Jones Number of transactions: 1 Total duration: 8 Total wait time: 0 Wait Times: 0 Customer Name: Ambroise Smith Number of transactions: 1 Total duration: 7 Total wait time: 2 Wait Times: 2 Customer Name: Alice Smith Number of transactions: 2 Total duration: 5 Total wait time: 0 Wait Times: 0 0 Total duration scheduled: 213 Total duration simulated: 213 Teller quiting time: 104 Teller utilization: 0.512019