An extended example will illustrate the use of priority queues. The example illustrates one of the more common uses for priority queues, which is to support the construction of a simulation model.
A discrete event-driven simulation is a popular simulation technique. Objects in the simulation model objects in the real world, and are programmed to react as much as possible as the real objects would react. A priority queue is used to store a representation of "events" that are waiting to happen. This queue is stored in order, based on the time the event should occur, so the smallest element will always be the next event to be modeled. As an event occurs, it can spawn other events. These subsequent events are placed into the queue as well. Execution continues until all events have been processed.
Finding Smallest Elements
Events can be represented as subclasses of a base class, which we will call event. The base class simply records the time at which the event will take place. A pure virtual function named processEvent will be invoked to execute the event.
class event {
public:
event (unsigned int t) : time(t) { }
const unsigned int time;
virtual void processEvent() = 0;
};
The simulation queue will need to maintain a collection of different types of events. Each different form of event will be represented by a different subclass of class event. Not all events will have the same exact type, although they will all be subclasses of class event. (This is sometimes called a heterogeneous collection.) For this reason the collection must store pointers to events, instead of the events themselves. (In theory one could store references, instead of pointers, however the standard library containers cannot hold references).
Since comparison of pointers cannot be specialized on the basis of the pointer types, we must instead define a new comparison function for pointers to events. In the standard library this is accomplished by defining a new structure, the sole purpose of which is to define the function invocation operator (the () operator) in the appropriate fashion. Since in this particular example we wish to use the priority queue to return the smallest element each time, rather than the largest, the order of the comparison is reversed, as follows:
struct eventComparison {
bool operator () (event * left, event * right) const
{ return left->time > right->time; }
};
We are now ready to define the class simulation, which provides the structure for the simulation activities. The class simulation provides two functions. The first is used to insert a new event into the queue, while the second runs the simulation. A data field is also provided to hold the current simulation "time."
Storing Pointers versus Storing Values
class simulation {
public:
simulation () : eventQueue(), time(0) { }
void scheduleEvent (event * newEvent)
{ eventQueue.push (newEvent); }
void run();
unsigned int time;
protected:
priority_queue<event *, vector<event *>, eventComparison> eventQueue;
};
Notice the declaration of the priority queue used to hold the pending events. In this case we are using a vector as the underlying container. We could just as easily have used a deque.
The heart of the simulation is the member function run(), which defines the event loop. This procedure makes use of three of the five priority queue operations, namely top(), pop(), and empty(). It is implemented as follows:
void simulation::run()
{
while (! eventQueue.empty()) {
event * nextEvent = eventQueue.top();
eventQueue.pop();
time = nextEvent->time;
nextEvent->processEvent();
delete nextEvent; // free memory used by event
}
}
Obtaining the sample program
To illustrate the use of our simulation framework, this example program gives a simple simulation of an ice cream store. Such a simulation might be used, for example, to determine the optimal number of chairs that should be provided, based on assumptions such as the frequency that customers will arrive, the length of time they will stay, and so on.
Our store simulation will be based around a subclass of class simulation, defined as follows:
class storeSimulation : public simulation {
public:
storeSimulation()
: freeChairs(35), profit(0.0), simulation() { }
bool canSeat (unsigned int numberOfPeople);
void order(unsigned int numberOfScoops);
void leave(unsigned int numberOfPeople);
private:
unsigned int freeChairs;
double profit;
} theSimulation;
There are three basic activities associated with the store. These are arrival, ordering and eating, and leaving. This is reflected not only in the three member functions defined in the simulation class, but in three separate subclasses of event.
The member functions associated with the store simply record the activities taking place, producing a log that can later be studied to evaluate the simulation.
bool storeSimulation::canSeat (unsigned int numberOfPeople)
// if sufficient room, then seat customers
{
cout << "Time: " << time;
cout << " group of " << numberOfPeople << " customers arrives";
if (numberOfPeople < freeChairs) {
cout << " is seated" << endl;
freeChairs -= numberOfPeople;
return true;
}
else {
cout << " no room, they leave" << endl;
return false;
}
}
void storeSimulation::order (unsigned int numberOfScoops)
// serve icecream, compute profits
{
cout << "Time: " << time;
cout << " serviced order for " << numberOfScoops << endl;
profit += 0.35 * numberOfScoops;
}
void storeSimulation::leave (unsigned int numberOfPeople)
// people leave, free up chairs
{
cout << "Time: " << time;
cout << " group of size " << numberOfPeople <<
" leaves" << endl;
freeChairs += numberOfPeople;
}
As we noted already, each activity is matched by a subclass of event. Each subclass of event includes an integer data field, which represents the size of a group of customers. The arrival event occurs when a group enters. When executed, the arrival event creates and installs a new instance of order event. The function randomInteger() (see Chapter 2: Random Access Iterators) is used to compute a random integer between 1 and the argument value.
class arriveEvent : public event {
public:
arriveEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void arriveEvent::processEvent()
{ // see if everybody can be seated
if (theSimulation.canSeat(size))
theSimulation.scheduleEvent
(new orderEvent(time + 1 + randomInteger(4), size));
}
An order event similarly spawns a leave event.
class orderEvent : public event {
public:
orderEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void orderEvent::processEvent()
{ // each person orders some number of scoops
for (int i = 0; i < size; i++)
theSimulation.order(1 + rand(3));
theSimulation.scheduleEvent
(new leaveEvent(time + 1 + randomInteger(10), size));
};
Finally, leave events free up chairs, but do not spawn any new events.
class leaveEvent : public event {
public:
leaveEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void leaveEvent::processEvent ()
{ // leave and free up chairs
theSimulation.leave(size);
}
To run the simulation we simply create some number of initial events (say, 30 minutes worth), then invoke the run() member function.
void main() {
// load queue with some number of initial events
unsigned int t = 0;
while (t < 30) {
t += rand(6);
theSimulation.scheduleEvent(
new arriveEvent(t, 1 + randomInteger(4)));
}
// then run simulation and print profits
theSimulation.run();
cout << "Total profits " << theSimulation.profit << endl;
}