// Chap 7, pp 334 - 339
// See also files C07P339.CPP and C07P341.CPP
// *******************************************************
// Event-driven simulation of a single waiting line of
// people.
//
// Input:
// A text file of arrival and transaction times.
// Each line contains the arrival time and required
// transaction time for a customer.
//
// Assumption:
// The arrival times in the input file are ordered by
// increasing time.
//
// Output:
// A trace of the events executed and a summary of
// statistics (total number of arrivals and average time
// spent waiting in line).
//
// ADTs:
// Line of people - a queue of arrival events
// Event list - a list of arrival events and
// departure events that are sorted
// by the time of the event.
// Functions:
// GetArrival - reads arrival event from input file
// and inserts it into event list
// ProcessArrival - executes an arrival event
// ProcessDeparture - executes a departure event
// Simulate - performs the simulation
// *******************************************************
char* const ARRIVAL_FILE_NAME = "BANK.DAT";
const int FIELD_WIDTH = 3; // output field width for time
const int MAX_STRING = 12;
typedef char nameType[MAX_STRING];
#include // file operations
#include // enables setw()
#include // enables exit()
#include "EL.h" // ADT event list operations
// for simplicity, queue items and event list items
// are the same structures; both indicate the kind of
// event and contain arrival and transaction times
#ifndef QTYPE
typedef event queueItemType; // desired-type-of-queue-item
#define QTYPE
#endif
// omit declaration of queueItemType from Queue.h
//#include "Queue.h" // ADT queue operations
// statistics of simulation
struct stats
{ int TotalNum; // total no. of customers
int TotalWait; // cumulative waiting time
stats(); // constructor
}; // end struct
stats::stats() : TotalNum(0), TotalWait(0)
{
} // end constructor
void GetArrival(ifstream& ArrivalFile, eventListClass& EL,
boolean& Success)
// --------------------------------------------------------
// Reads data for the next arrival event, and inserts the
// new arrival node into the event list.
// Precondition: ArrivalFile is a text file, which is open
// for input, of arrival and transaction times. EL is the
// current event list.
// Postcondition: The next event is read from ArrivalFile
// and is inserted into EL and Success is TRUE. At end-of-
// file, EL is unchanged. If insertion is impossible,
// Success is FALSE. ArrivalFile is open for input.
// Calls: InsertEvent.
// --------------------------------------------------------
{
int NextTime; // time of next arrival event
int TTime; // event's transaction time
// (i.e. transaction length)
if (ArrivalFile >> NextTime >> TTime) // read next event
{ // create a new arrival event
event NewEvent(A, NextTime, TTime);
// insert the event into the event list
EL.InsertEvent(NewEvent, Success);
} // end if
} // end GetArrival
void ProcessArrival(event ArrivalEvent,
ifstream& ArrivalFile,
eventListClass& EL, queueClass& Line,
stats& Statistics, boolean& Success)
// --------------------------------------------------------
// Executes an arrival event.
// Precondition: ArrivalEvent contains the arrival event,
// ArrivalFile of arrival events is open for input,
// EL is the event list, the queue Line has been created,
// and Statistics.TotalNum is the total number of arrivals.
// Postcondition: If Line is empty, a departure event is
// created for ArrivalEvent and inserted into event list EL.
// ArrivalEvent is deleted from event list and added to
// Line (the queue). A new arrival event is read from
// ArrivalFile and is inserted into EL. Statistics.TotalNum
// (total no. of arrivals) is updated. ArrivalFile is open
// for input. Success is TRUE unless an insertion into the
// event list is impossible.
// Calls: InsertEvent, DeleteEvent, GetArrival,
// QueueIsEmpty, and QueueAdd.
// --------------------------------------------------------
{
// update the total number of arrivals
++Statistics.TotalNum;
int CurrentTime = ArrivalEvent.Time; // arrival time
cout << "Processing an arrival event at time: "
<< setw(FIELD_WIDTH) << CurrentTime << endl;
// if queue is empty, arrival will be at head of line
boolean AtHead = Line.QueueIsEmpty();
// person arrives and enters the waiting line (queue)
Line.QueueAdd(ArrivalEvent, Success);
// update event list
EL.DeleteEvent(Success); // delete event from event list
// if at head of line, the person starts transaction
if (AtHead)
{ // create a departure event
event DepartureEvent(D, CurrentTime +
ArrivalEvent.TransTime, 0);
// insert the event into the event list
EL.InsertEvent(DepartureEvent, Success);
} // end if
if (Success)
// get the next arrival event, if any, from input file
GetArrival(ArrivalFile, EL, Success);
} // end ProcessArrival
void ProcessDeparture(event DepartureEvent,
eventListClass& EL, queueClass& Line,
stats& Statistics, boolean& Success)
// --------------------------------------------------------
// Executes a departure event.
// Precondition: DepartureEvent contains the departure
// event, EL is the event list, the queue Line has been
// created, Statistics.TotalWait is the total waiting time.
// Postcondition: A person is removed from the queue. The
// event list is updated by deleting the current event and
// adding a departure event for the next customer, if any.
// Statistics.TotalWait (total waiting time) is updated.
// Success is TRUE unless an insertion into the event list
// was impossible.
// Calls: InsertEvent, DeleteEvent, QueueIsEmpty,
// QueueRemove, and GetQueueFront.
// --------------------------------------------------------
{
queueItemType PersonInLine; // data for person in queue
int CurrentTime = DepartureEvent.Time; // arrival time
cout << "Processing a departure event at time: "
<< setw(FIELD_WIDTH) << CurrentTime << endl;
// person departs - update the line (queue)
Line.QueueRemove(Success); // remove person from queue
// update the event list:
EL.DeleteEvent(Success); // delete event from event list
// if the line is not empty, the next person starts
// a transaction
if (!Line.QueueIsEmpty())
{ // create a departure event
Line.GetQueueFront(PersonInLine, Success);
event DepartureEvent(D, CurrentTime +
PersonInLine.TransTime,0);
// insert the event into the event list
EL.InsertEvent(DepartureEvent, Success);
if (Success)
// update the statistics
Statistics.TotalWait += (CurrentTime -
PersonInLine.Time);
} // end if
} // end ProcessDeparture
void Simulate(nameType FileName, stats& Statistics)
// --------------------------------------------------------
// Simulates a line of people.
// Precondition: FileName is the name of the text file
// of arrival events. Data members of Statistics are 0.
// Postcondition: Statistics.TotalWait is the total
// cumulative waiting time of all customers.
// Statistics.TotalNum is the total number of customers.
// ArrivalFile is closed.
// Calls: GetArrival, ProcessArrival, ProcessDeparture,
// EventListIsEmpty, and RetrieveEvent.
// --------------------------------------------------------
{
event NewEvent; // current event
eventListClass EL; // event list
queueClass Line; // waiting line
ifstream ArrivalFile(FileName); // file of times
boolean Success;
cout << "Simulation begins:\n";
// get the first arrival event and place on event list
GetArrival(ArrivalFile, EL, Success);
// process events until the event list is empty
while ( Success && !EL.EventListIsEmpty() )
{ // get next event from beginning of event list
EL.RetrieveEvent(NewEvent, Success);
if (NewEvent.WhichEvent == A)
// process arrival event
ProcessArrival(NewEvent, ArrivalFile, EL, Line,
Statistics, Success);
else
// process departure event
ProcessDeparture(NewEvent, EL, Line,
Statistics, Success);
} // end while
if (!Success)
{ cerr << "Error in event list. "
<< "Execution aborted.\n";
exit(1); // abort
} // end if
cout << "Simulation ends.\n";
} // end Simulate
main()
{
stats Statistics; // summary statistics initialized to 0
// perform the simulation
Simulate(ARRIVAL_FILE_NAME, Statistics);
// write out the final statistics
cout << "\nFinal Statistics:\n"
<< " Total number of people processed: "
<< Statistics.TotalNum << "\n"
<< " Average amount of time spent waiting: ";
if (Statistics.TotalNum == 0)
cout << " 0.0\n";
else
cout << float(Statistics.TotalWait)/
float(Statistics.TotalNum) << endl;
return 0;
} // end program
(
geocities.com/siliconvalley/program/2864/ds) (
geocities.com/siliconvalley/program/2864) (
geocities.com/siliconvalley/program) (
geocities.com/siliconvalley)