events happening at the same time in event-driven simulator

Question

I have been trying to develop a simple event driven simulator and started here

http://stdcxx.apache.org/doc/stdlibug/11-3.html

When I was playing around with the example with some modifications, I came across a condition where when two events (arrival, departure) happen at the same time (say at time unit 5), then the simulator just pops whatever is in the top of the event queue as can be seen from the below code snippet.

void simulation::run () {

while (! eventQueue.empty ()) {

event * nextEvent = eventQueue.top ();
eventQueue.pop ();
time = nextEvent->time;
nextEvent->processEvent ();
delete nextEvent;
  }
}

If both event happens at the same time, how can I enforce the condition that always pop a certain event(arrival event first) before the departure event.

Any help is much appreciated.

Answer 1

I assume that eventQueue has the type described here (because that's what's referenced from the link in your question). From there, you can read that top() ...

Returns a constant reference to the element in the queue with the highest priority

... and that pop() ...

Removes the item with the highest priority from the queue.

So, taking the code from your questions, the most obvious approach would be to take all events out of the queue that have the same time, and only then process them:

while (! eventQueue.empty ()) {
  event * ev = eventQueue.top (); // WHY do you have pointers here ?!?!?
  time = ev->time;
  some_container<event *> arrivals, departures;
  // Take out all events that happen "now" from the queue
  while (time == ev->time) {
    eventQueue->pop();
    if (ev->type == ARRIVAL) {
      arrivals.push_back(ev);
    } else {
      departures.push_back(ev);
    }
    ev = eventQueue->top();
  }
  // Process arrivals
  for (event * e : arrivals) {
    e->processEvent();
    delete e; // Again: WTF pointers? raw? NOT a good idea!
  }
  // Process departures
  for (event * e : departures) {
    e->processEvent();
    delete e;
  }
}

BUT...

... that's not an idiomatic way to handle this in C++. Containers (at least ordered ones) in C++ normally have a template parameter specifying the way the elements should be ordered. And so does the std::priority_queue:

namespace std {
  template <class T,
            class Container = vector<T>,
            class Compare = less<Container::value_type> >
  class priority_queue;
}

Thus, the better approach here is to establish a total order among all events using a custom compare function object:

// sigh ... pointers ... raw pointers ... just WHY???!?
template<typename Event>
struct less_event_ptr {
  std::less<time_type> time_compare; // time_type hopefully is self-describing ...
  bool operator()(Event * lhs, Event * rhs) const {
    if (time_compare(lhs->time, rhs>-time)) {
      return true;
    }
    if (time_compare(rhs->time, lhs->time)) {
      return false;
    }
    if (lhs->type == ARRIVAL && rhs->type == DEPARTURE) {
      return true;
    }
    return false;
  }
};

Note that for this to be a total order, you need to be sure that there won't be multiple arrivals (or departures) at the same time. If there will (possibly) such circumstances, then you should (if you want a deterministic simulation) find other properties (a name? source?) of the events to bring them in order.

Your eventQueue would then be declared like

std::priority_queue<event *, std::vector<event *>, less_event_ptr<event>> eventQueue;