priority_queue help

[rrlangly]

I'm trying to create a central event system for my game where I add some events to a priority_queue and pull off the first one as soon as it expires. But I'm having a problem of understanding if I'm adding them to the queue correctly, if they're in order, or how to pull them off. Can anyone lend a hand here?

Initialize the queue.

my_queue = new MyEventQueue();

Here I create 10 events and put them on a queue after assigning the current timestamp, and then the later timestamp to execute this event.

for (int i = 0; i < 10; i++) {
         MyEvent *event = new MyEvent();
         event->set_start_timestamp(); // now time
         event->set_execute_timestamp(); // time to execute from now

         my_queue->push_event(event);
     }

Then in each frame of my game, i want to check the queue to see if the event is ready to be executed.

if (my_queue->count() > 0) {
        MyEvent *evnt = my_queue->top_event();

			// is_expired() is how i was doing it, but didn't work
        if (evnt->is_expired()) { 
            execute_event(evnt->id());

            my_queue->pop_event();
        }
    }

Here are my event classes ...

class MyEvent
{
	...

    public:
		...
        bool is_expired();
        struct timeval start_timestamp();
        double execute_timestamp();
};

struct EventPointerCompare {
    bool operator() (MyEvent* lhs, MyEvent* rhs) const {
        return ( lhs->_execute_time < rhs->_execute_time );
    }
};

// this is my priority_queue wrapper
class MyEventQueue
{
    private:
        priority_queue<MyEvent *, vector<MyEvent *>,
            EventPointerCompare> event_queue;

	public:
		check_queue();
		has_events_of_type_x();
		...

Can anyone help me use priority_queue's correctly?

[stilllearning]

I am a little confused by your queue implementation. Usually your queue functions would be enqueue to add the elements to the queue, and dequeue to get the first element you added off the queue, simulating FIFO behavior.

A stack on the other hand uses push and pop for LIFO

When you do this MyEvent *evnt = my_queue->top_event(); , are you getting the first element you added or the last element you added ? If its the last element its likely that the evnt->is_expired() won't work.

[rrlangly]

I am a little confused by your queue implementation. Usually your queue functions would be enqueue to add the elements to the queue, and dequeue to get the first element you added off the queue, simulating FIFO behavior.

A stack on the other hand uses push and pop for LIFO

When you do this MyEvent *evnt = my_queue->top_event(); , are you getting the first element you added or the last element you added ? If its the last element its likely that the evnt->is_expired() won't work.

I randomly generate timestamps so that these events are to execute from 0 to 10 seconds from the time they are created, so I somehow need to pull them off the queue based on priority of next timestamp that's about to expire.

So this just calls top() but I don't think this will work which is why I started to overload the operator() to get the next timestamp in the queue w/ priority of the least amount of time. MyEvent *evnt = my_queue->top_event();

[stilllearning]

When you insert your elements into the queue, you have to insert them so that the timestamps are sorted in descending order. That way when you dequeue your first element, you should get the correct value.

[rrlangly]

When you insert your elements into the queue, you have to insert them so that the timestamps are sorted in descending order. That way when you dequeue your first element, you should get the correct value.

That's one way, but for a priority_queue, I don't think that's how it should work, otherwise I could use a regular queue if I just placed them on the queue in the order I need. I believe a priority_queue should actually pull off the item in the queue based on it's "priority" or my overriding implementation of the item w/ the next 'least' amount of time. However, I'm having a hardtime understanding the implementation of it.

[stilllearning]

Your priority_queue should be building a max_heap with the highest value at the top. Have you tried printing the contents of your queue after you finish building it, to see if the elements are in order based on your comparison function ?

[rrlangly]

Ok then, I have to find an example somewhere's because I'm not sure how this is to work. Something isn't making sense to me.

[stilllearning]

Here is a decent example Link