event_queue.cpp
#include <math.h> #include <assert.h> #include <iostream> #include <vector> #include <queue> using namespace std; /* TYPES *******************************************************************/ typedef double Time; // measured in minutes /*-------------------------------------------------------------------------*/ class Event /* PURPOSE: An event that is scheduled for execution at some time */ { public: Event(Time t); static enum type { ARRIVAL, DEPARTURE }; Event(const Event &src) { _time = src.time(); _type = src._type; cout << "copy: " << _time << endl; } Event(Time t, type my_type): _time(t), _type(my_type) { cout << "Created: " << time() << endl;} virtual void process() { } virtual void show() const; Time time() const { return _time; } virtual ~Event() { cout << "event " << time() << " deleted\n"; } bool operator <(const Event &ev) const { return _time>ev.time(); } private: Time _time; type _type; }; /*-------------------------------------------------------------------------*/ class Arrival : public Event /* PURPOSE: Customer arrives at bank */ { public: Arrival(Time); virtual void process() { } void show() const; }; const Time INTERARRIVAL = 1.0; // 1 minute const Time AVG_PROCTIME = 5.0; // 5 minutes static int event_compare(const Event* a, const Event* b); priority_queue<Event> event_queue; Time now; /* FUNCTIONS ***************************************************************/ static double expdist(double mean) /* PURPOSE: Compute exponentially distributed random numbers RECEIVES: mean - the mean of the number sequence RETURNS: a random number */ { double r = rand(); r /= RAND_MAX; return -mean*log(r); } /*.........................................................................*/ #if defined(_COMPARE) static int event_compare(const Event* a, const Event* b) /* PURPOSE: compare two events by their time stamp RECEIVES: a, b - pointers to two events RETURNS: -1 if a is scheduled earlier than b, 0 if they are scheduled at the same time, 1 otherwise */ { Time d = a->time() - b->time(); return (d > 0) - (d < 0); } #endif /*.........................................................................*/ int main() { //const Time STARTTIME = 9 * 60; // 9 a.m. //const Time ENDTIME = 17 * 60; // 5 p.m. now = 0.0; for (int i = 0; i<6; i++) { Time t = expdist(INTERARRIVAL); Event *e = new Event(now+t,Event::ARRIVAL); event_queue.push(*e); now += 2; } cout << "\nQueue size: " << event_queue.size() << endl; while (event_queue.size()>0) { Event e = event_queue.top(); e.show(); event_queue.pop(); } return 0; } /*-------------------------------------------------------------------------*/ Event::Event(Time t) /* RECEIVES: t - the execution time of this event */ : _time(t) {} void Event::show() const { cout << (_type==ARRIVAL? "Arrival": "Departure") << ": " << time() << endl; } /*-------------------------------------------------------------------------*/ Arrival::Arrival(Time t) /* RECEIVES: t - the time at which the arrival will occur */ : Event(t) {} void Arrival::show() const { cout << "Arrival: " << time() << endl; }
Created: 6.68361 copy: 6.68361 copy: 6.68361 event 6.68361 deleted Created: 2.57344 copy: 2.57344 copy: 6.68361 copy: 2.57344 event 6.68361 deleted event 2.57344 deleted copy: 2.57344 event 2.57344 deleted Created: 5.64349 copy: 5.64349 copy: 2.57344 copy: 6.68361 copy: 5.64349 event 2.57344 deleted event 6.68361 deleted event 5.64349 deleted copy: 5.64349 event 5.64349 deleted Created: 6.21228 copy: 6.21228 copy: 2.57344 copy: 6.68361 copy: 5.64349 copy: 6.21228 event 2.57344 deleted event 6.68361 deleted event 5.64349 deleted event 6.21228 deleted copy: 6.21228 event 6.21228 deleted Created: 8.53613 copy: 8.53613 copy: 2.57344 copy: 6.21228 copy: 5.64349 copy: 6.68361 copy: 8.53613 event 2.57344 deleted event 6.21228 deleted event 5.64349 deleted event 6.68361 deleted event 8.53613 deleted copy: 8.53613 event 8.53613 deleted Created: 10.7342 copy: 10.7342 copy: 10.7342 event 10.7342 deleted Queue size: 6 copy: 2.57344 Arrival: 2.57344 copy: 10.7342 copy: 10.7342 copy: 10.7342 event 10.7342 deleted event 10.7342 deleted event 10.7342 deleted event 2.57344 deleted event 2.57344 deleted copy: 5.64349 Arrival: 5.64349 copy: 8.53613 copy: 8.53613 copy: 8.53613 event 8.53613 deleted event 8.53613 deleted event 8.53613 deleted event 5.64349 deleted event 5.64349 deleted copy: 6.21228 Arrival: 6.21228 copy: 8.53613 copy: 8.53613 copy: 8.53613 event 8.53613 deleted event 8.53613 deleted event 8.53613 deleted event 6.21228 deleted event 6.21228 deleted copy: 6.68361 Arrival: 6.68361 copy: 10.7342 copy: 10.7342 copy: 10.7342 event 10.7342 deleted event 10.7342 deleted event 10.7342 deleted event 6.68361 deleted event 6.68361 deleted copy: 8.53613 Arrival: 8.53613 copy: 10.7342 copy: 10.7342 copy: 10.7342 event 10.7342 deleted event 10.7342 deleted event 10.7342 deleted event 8.53613 deleted event 8.53613 deleted copy: 10.7342 Arrival: 10.7342 event 10.7342 deleted event 10.7342 deleted
Maintained by John Loomis, updated Wed Feb 21 17:29:26 2007