HP Integrity NonStop H-Series - Manual (Page 124)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Application - Event-Driven Simulation
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