| <!-- |
| Licensed to the Apache Software Foundation (ASF) under one or more |
| contributor license agreements. See the NOTICE file distributed |
| with this work for additional information regarding copyright |
| ownership. The ASF licenses this file to you under the Apache |
| License, Version 2.0 (the License); you may not use this file |
| except in compliance with the License. You may obtain a copy of |
| the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, software |
| distributed under the License is distributed on an "AS IS" BASIS, |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or |
| implied. See the License for the specific language governing |
| permissions and limitations under the License. |
| |
| Copyright 1999-2007 Rogue Wave Software, Inc. |
| --> |
| |
| <HTML> |
| <HEAD> |
| <TITLE>Example Program: Event-Driven Simulation</TITLE> |
| <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD> |
| <BODY BGCOLOR=#FFFFFF> |
| <A HREF="11-2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="12.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV> |
| <H2>11.3 Example Program: Event-Driven Simulation</H2> |
| <A NAME="idx212"><!></A> |
| <A NAME="idx213"><!></A> |
| <P>An extended example will now illustrate one of the more common uses of a priority_queues, which is to support the construction of a simulation model. A <I>discrete event-driven simulation</I> 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 <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B> is used to store a representation of <I>events</I> 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.</P> |
| <BLOCKQUOTE><HR><B> |
| NOTE -- The complete version of the ice cream store simulation program is in icecream.cpp. |
| </B><HR></BLOCKQUOTE> |
| <P>Events can be represented as subclasses of a base class, which we call <B><I>event</I></B>. The base class simply records the time at which the event will take place. A pure virtual function named <SAMP>processEvent</SAMP> is invoked to execute the event:</P> |
| |
| <UL><PRE> |
| class event { |
| public: |
| // Construct sets time of event. |
| event (unsigned int t) : time (t) |
| { } |
| |
| // Execute event by invoking this method. |
| virtual void processEvent () = 0; |
| |
| const unsigned int time; |
| }; |
| </PRE></UL> |
| <A NAME="idx214"><!></A> |
| <P>The simulation queue needs to maintain a collection of different types of events, sometimes called a <I>heterogeneous</I> collection. Each different form of event is represented by a subclass of class <B><I>event</I></B>, but not all <B><I>event</I></B>s have the same exact type. For this reason the collection must store <I>pointers</I> to <B><I>event</I></B>s, instead of the events themselves. Since the containers maintain pointers to values, not the values themselves, the programmer is responsible for managing the memory for the objects being manipulated.</P> |
| <P>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 C++ Standard Library we do this by defining a new structure whose sole purpose is to define the function invocation <SAMP>operator()()</SAMP> in the appropriate fashion. Since in this particular example we want to use the <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B> to return the smallest element each time, rather than the largest, the order of the comparison is reversed, as follows:</P> |
| |
| <UL><PRE> |
| struct eventComparator { |
| bool operator() (const event * left, const event * right) const { |
| return left->time > right->time; |
| } |
| }; |
| </PRE></UL> |
| <BLOCKQUOTE><HR><B> |
| NOTE -- We use a priority queue as a structure for quickly discovering the smallest element in a sequence. If, instead, your problem requires the discovery of the largest element, there are various possibilities. One is to supply the inverse operator as either a template argument or the optional comparison function argument to the constructor. If you are defining the comparison argument as a function, as in the example problem, another solution is to simply invert the comparison test. |
| </B><HR></BLOCKQUOTE> |
| <P>We are now ready to define the class <B><I>simulation</I></B>, which provides the structure for the simulation activities. The class <B><I>simulation</I></B> provides two functions: the first is used to insert a new event into the queue, while the second runs the simulation. A data member is also provided to hold the current simulation <B><I>time</I></B>:</P> |
| |
| <UL><PRE> |
| class simulation { |
| public: |
| simulation () : time (0), eventQueue () |
| {} |
| void run (); |
| void scheduleEvent (event * newEvent) { |
| eventQueue.push (newEvent); |
| } |
| unsigned int time; |
| protected: |
| std::priority_queue<event*, |
| std::vector<event *, std::allocator<event*> >, |
| eventComparator> eventQueue; |
| }; |
| </PRE></UL> |
| <P>Notice the declaration of the <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B> used to hold the pending <B><I>event</I></B>s. In this case we are using a <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> as the underlying container, but we could just as easily have used a <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>. </P> |
| <P>The heart of the simulation is the member function<SAMP> run()</SAMP>, which defines the event loop. This procedure makes use of three of the five <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B> operations, namely <SAMP>top()</SAMP>, <SAMP>pop()</SAMP>, and <SAMP>empty().</SAMP> It is implemented as follows:</P> |
| |
| <UL><PRE> |
| void simulation::run () { |
| |
| while (! eventQueue.empty ()) { |
| |
| event * nextEvent = eventQueue.top (); |
| eventQueue.pop (); |
| time = nextEvent->time; |
| nextEvent->processEvent (); |
| delete nextEvent; |
| } |
| } |
| </PRE></UL> |
| <A NAME="idx215"><!></A> |
| <A NAME="1131"><H3>11.3.1 Example Program: An Ice Cream Store Simulation</H3></A> |
| <A NAME="idx216"><!></A> |
| <P>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 with which customers arrive, the length of time they stay, and so on.</P> |
| <P>Our store simulation is based around a subclass of class <B><I>simulation</I></B>, defined as follows:</P> |
| |
| <UL><PRE> |
| class storeSimulation : public simulation { |
| public: |
| storeSimulation () : simulation (), freeChairs (35), profit (0.0) |
| { } |
| bool canSeat (unsigned int numberOfPeople); |
| void order (unsigned int numberOfScoops); |
| void leave (unsigned int numberOfPeople); |
| // Data fields. |
| unsigned int freeChairs; |
| double profit; |
| } theSimulation; |
| </PRE></UL> |
| <P>There are three basic activities associated with the store: arrival, ordering and eating, and leaving. This is reflected not only in the three member functions defined in the <B><I>simulation</I></B> class, but in three separate subclasses of <B><I>event</I></B>.</P> |
| <P>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.</P> |
| |
| <UL><PRE> |
| bool storeSimulation::canSeat (unsigned int numberOfPeople) { |
| |
| std::cout << "Time: " << time; |
| std::cout << " group of " << numberOfPeople << " customers arrives"; |
| |
| if (numberOfPeople < freeChairs) { |
| std::cout << " is seated\n"; |
| freeChairs -= numberOfPeople; |
| return true; |
| } |
| else { |
| std::cout << " no room, they leave\n"; |
| return false; |
| } |
| } |
| |
| void storeSimulation::order (unsigned int numberOfScoops) { |
| |
| std::cout << "Time: " << time << " serviced order for " |
| << numberOfScoops << '\n'; |
| profit += 0.35 * numberOfScoops; |
| } |
| |
| void storeSimulation::leave (unsigned int numberOfPeople) { |
| |
| std::cout << "Time: " << time << " group of size " |
| << numberOfPeople << " leaves\n"; |
| freeChairs += numberOfPeople; |
| } |
| </PRE></UL> |
| <A NAME="idx217"><!></A> |
| <P>As we noted already, each activity is matched by a subclass of <B><I>event</I></B>. Each subclass of <B><I>event</I></B> includes an integer data member, 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 the order event. The function <SAMP>randomInteger()</SAMP> is used to compute a random integer between 1 and the argument value (see <A HREF="2-2.html#225">Section 2.2.5</A>).</P> |
| |
| <UL><PRE> |
| class arriveEvent : public event { |
| public: |
| arriveEvent (unsigned int t, unsigned int groupSize) |
| : event (t), size (groupSize) |
| { } |
| virtual void processEvent (); |
| private: |
| unsigned int size; |
| }; |
| |
| void arriveEvent::processEvent () { |
| |
| if (theSimulation.canSeat (size)) |
| theSimulation.scheduleEvent |
| (new orderEvent (time + 1 + irand (4), size)); |
| } |
| </PRE></UL> |
| <P>An order event similarly spawns a leave event:</P> |
| |
| <UL><PRE> |
| class orderEvent : public event { |
| public: |
| orderEvent (unsigned int t, unsigned int groupSize) |
| : event (t), size (groupSize) |
| { } |
| virtual void processEvent (); |
| private: |
| unsigned int size; |
| }; |
| |
| void orderEvent::processEvent () { |
| |
| // Each person orders some number of scoops. |
| for (unsigned int i = 0; i < size; i++) |
| theSimulation.order (1 + irand (4)); |
| |
| // Then we schedule the leave event. |
| theSimulation.scheduleEvent |
| (new leaveEvent (time + 1 + irand (10), size)); |
| } |
| |
| </PRE></UL> |
| <P>Finally, leave events free up chairs, but do not spawn any new events:</P> |
| |
| <UL><PRE> |
| class leaveEvent : public event |
| { |
| public: |
| leaveEvent (unsigned int t, unsigned int groupSize) |
| : event (t), size (groupSize) |
| { } |
| virtual void processEvent (); |
| private: |
| unsigned int size; |
| }; |
| |
| void leaveEvent::processEvent () { |
| |
| theSimulation.leave (size); |
| } |
| </PRE></UL> |
| <P>To run the simulation we simply create some number of initial events (say, 30 minutes worth), then invoke the <SAMP>run()</SAMP> member function:</P> |
| |
| <UL><PRE> |
| int main () { |
| |
| std::cout << "Ice Cream Store simulation from Chapter 9\n"; |
| |
| // Load queue with some number of initial events. |
| for (unsigned t = 0; t < 20; t += irand (6)) { |
| |
| std::cout << "pumping queue with event " << t << '\n'; |
| theSimulation.scheduleEvent (new arriveEvent (t, 1 + irand (4))); |
| } |
| |
| // Run the simulation. |
| theSimulation.run (); |
| |
| std::cout << "Total profits " << theSimulation.profit |
| << "\nEnd of ice cream store simulation\n"; |
| |
| return 0; |
| } |
| </PRE></UL> |
| |
| <BR> |
| <HR> |
| <A HREF="11-2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="12.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A> |
| |
| <!-- Google Analytics tracking code --> |
| <script src="http://www.google-analytics.com/urchin.js" type="text/javascript"> |
| </script> |
| <script type="text/javascript"> |
| _uacct = "UA-1775151-1"; |
| urchinTracker(); |
| </script> |
| <!-- end of Google Analytics tracking code --> |
| |
| </BODY> |
| </HTML> |
