/* Example of priority_queue holding virtual objects whose action()
 * method is polymorphic.
 * C++ requires that such methods be virtual and be executed via a pointer
 * or reference ( :( ). In this case the priority_queue ranks such objects
 * by the numerical value of the pointer which is inappropriate so we supply
 * an object with a compare method to compare two such pointers.
 * E objects are events with a time and an action.
 */
#include <iostream.h>
#include <queue>
#include <string>
using namespace std;

class E {  // parent class for objects with action methods
    friend class E_compare;
  protected: int when;
  public:
    E(int time): when(time) {}
    virtual void action()=0; //pure virtual
};
class E_compare { 
  public:
    bool operator()(const E* x, const E* y) const{ return x->when > y->when; }
};
// overrides default ptr comparison and ensures pq ordered by increasing when value

class F: public E {
     int val;
   public:
     F(int time, int val):E(time),val(val){}
     void action(){ cout << "At " << when<<" F: " << val  << endl;}
};

class G: public E {
     double v;
   public:
     G(int time,double v):E(time),v(v){}
     void action(){ cout << "At " << when<<" G: " << v    << endl;}
};

void main(){
  priority_queue<E*,vector<E*>,E_compare> pq;
  pq.push(new F(2888, 1));
  pq.push(new G(1234, 1.5));
  pq.push(new F(   2, 2));
  pq.push(new G(   2, 2.5));
  pq.push(new G(   1, 3.5)); 
  pq.push(new F(  22, 3));
  while(!pq.empty()){
     (pq.top())->action();
     pq.pop();
  }
}
/* output: events in order increasing time
At 1 G: 3.5
At 2 F: 2
At 2 G: 2.5
At 22 F: 3
At 1234 G: 1.5
At 2888 F: 1
*/