priority_queue help

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Oct 2008
Posts: 4
Reputation: rrlangly is an unknown quantity at this point 
Solved Threads: 0
rrlangly rrlangly is offline Offline
Newbie Poster

priority_queue help

 
0
  #1
Oct 22nd, 2008
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.
  1. 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.
  1. for (int i = 0; i < 10; i++) {
  2. MyEvent *event = new MyEvent();
  3. event->set_start_timestamp(); // now time
  4. event->set_execute_timestamp(); // time to execute from now
  5.  
  6. my_queue->push_event(event);
  7. }

Then in each frame of my game, i want to check the queue to see if the event is ready to be executed.
  1. if (my_queue->count() > 0) {
  2. MyEvent *evnt = my_queue->top_event();
  3.  
  4. // is_expired() is how i was doing it, but didn't work
  5. if (evnt->is_expired()) {
  6. execute_event(evnt->id());
  7.  
  8. my_queue->pop_event();
  9. }
  10. }

Here are my event classes ...
  1. class MyEvent
  2. {
  3. ...
  4.  
  5. public:
  6. ...
  7. bool is_expired();
  8. struct timeval start_timestamp();
  9. double execute_timestamp();
  10. };
  11.  
  12. struct EventPointerCompare {
  13. bool operator() (MyEvent* lhs, MyEvent* rhs) const {
  14. return ( lhs->_execute_time < rhs->_execute_time );
  15. }
  16. };
  17.  
  18. // this is my priority_queue wrapper
  19. class MyEventQueue
  20. {
  21. private:
  22. priority_queue<MyEvent *, vector<MyEvent *>,
  23. EventPointerCompare> event_queue;
  24.  
  25. public:
  26. check_queue();
  27. has_events_of_type_x();
  28. ...

Can anyone help me use priority_queue's correctly?
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 305
Reputation: stilllearning has a spectacular aura about stilllearning has a spectacular aura about 
Solved Threads: 43
stilllearning stilllearning is offline Offline
Posting Whiz

Re: priority_queue help

 
0
  #2
Oct 22nd, 2008
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.
Last edited by stilllearning; Oct 22nd, 2008 at 2:08 am.
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 4
Reputation: rrlangly is an unknown quantity at this point 
Solved Threads: 0
rrlangly rrlangly is offline Offline
Newbie Poster

Re: priority_queue help

 
0
  #3
Oct 22nd, 2008
Originally Posted by stilllearning View Post
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();
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 305
Reputation: stilllearning has a spectacular aura about stilllearning has a spectacular aura about 
Solved Threads: 43
stilllearning stilllearning is offline Offline
Posting Whiz

Re: priority_queue help

 
0
  #4
Oct 22nd, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 4
Reputation: rrlangly is an unknown quantity at this point 
Solved Threads: 0
rrlangly rrlangly is offline Offline
Newbie Poster

Re: priority_queue help

 
0
  #5
Oct 22nd, 2008
Originally Posted by stilllearning View Post
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.
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 305
Reputation: stilllearning has a spectacular aura about stilllearning has a spectacular aura about 
Solved Threads: 43
stilllearning stilllearning is offline Offline
Posting Whiz

Re: priority_queue help

 
0
  #6
Oct 22nd, 2008
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 ?
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 4
Reputation: rrlangly is an unknown quantity at this point 
Solved Threads: 0
rrlangly rrlangly is offline Offline
Newbie Poster

Re: priority_queue help

 
0
  #7
Oct 22nd, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 305
Reputation: stilllearning has a spectacular aura about stilllearning has a spectacular aura about 
Solved Threads: 43
stilllearning stilllearning is offline Offline
Posting Whiz

Re: priority_queue help

 
0
  #8
Oct 23rd, 2008
Here is a decent example Link
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC