Priority Queues Events
 

I have a priority queue which is filled with times (in seconds) which is associated with tasks. So far I queue the item, set a timer interval to the time of the item at the head of queue and when that time elapses I de-queue the item at the head of the queue and I set the timer interval to the next item in the at head of the queue, perform the task and then put the item back on the queue.

The problem with this is those tasks with long time intervals will never be performed because the ones with the shorter intervals keep popping up to the front of the queue.

The only solution that comes to mind, is when an item is de-queued, subtract the current item’s (the one that was just de-queued) time from all other items in the queue, this way seems rather long because you have to loop through all the items in every de-queue operation (which could occur frequently).

Are there any other simpler solutions.

Let's say you've implemented this as a heap. Rather than storing a delay with your items, store the 'due time'. In other words, add the delay to the current time, derive a value from this, and use this as the key that determines the placement of your new item in the heap. This way, when enqueuing an item, it will only be on the top of the heap if it indeed must be the first event handled.

You can couple this with setting the timer to fire at only the required intervals with a bit of work, too, though it depends on the granularity you need. You also need to handle the situation where multiple events need 'simultaneous' handling, and by this I mean two or more events that need to be handled on the same firing of the timer. Basically, when the timer fires, you dequeue the top item, handle it, then peek at the next. If its timestamp indicates it needs handling too, you do so, and you continue on until the top element doesn't yet need handling.

This should handle recurring events too, though I kind of inferred you meant one-shot events. For recurring events, just enqueue them again after they get handled. With my suggestion about using due times rather than delays, coupled with handling multiple events per timer firing, lower-priority events should still be handled eventually.

Perhaps you should reconsider your definition of priority.

Thanks lectricpharaoh, yeah I have implemented this using a min-heap. The switch from delay time to due time should definitely fix the problems I was having with low priority events, as for the multiples events occurring at the same time, I shall peek as suggested and take the appropriate action.

I am sort of having a problem implementing the above, all the timer classes that i have come across so far seem to wait for the given time pass. So if I try to feed it the current time plus the delay time, it will wait for that actual amount of time, so if the current time was 20:10 and i added the delay time 10 seconds (20:20), it will wait 20 hours and 20 minutes before it generates an event.

Timers often work on a delay, true. However, given the methods of the DateTime structure, it's a simple matter to convert a future time into a delay from the current time. I wasn't saying that your timer should function this way- unless you're going to roll your own, you have to use what's given. The storing of the due time was for the queue items only.

It goes like this: when you enqueue something, your code determines the due time, and stores the item in the queue. You then peek at the front of the queue, determine the difference between DateTime.Now and the future time. This is your delay; you set your timer to fire when it elapses.

The key thing here is to use the same timer. Under the framework, there will be calls to the raw Win32 API in order to register the timer and set the delay, as well as unregistering it and setting a new one if you set a new delay before the original delay elapses. Don't worry about this; trust the framework to do its job in this regard. The idea here is you are overwriting the delay.

Say the time is currently 0:00:00.00 (ie midnight). You want an event to occur after 5 seconds, and enqueue it. The front of the queue now has an item set to occur at 0:00:05.00, and the timer is set to fire after 5000 milliseconds. You now enqueue (assume that no measurable time has elapsed yet) a second event to occur after 2 seconds. Obviously, this should occur before the first, so now the front of the queue has an item whose due time is 0:00:02.00. The timer is also reset to fire after 2000 milliseconds.

When the timer fires after 2000 milliseconds, the current time will be 0:00:02.00 (actually, it might be a bit more, due to granularity- but again, ignore this for now). You now have another 3000 milliseconds to wait until the next event (the one that should occur at 0:00:05.00). You can determine this when you peek at the front of the queue, and compare that item's due time to the current time. If they are equal, or the due time is earlier, you raise the event. If the due time is later, you use the difference to reset the timer. You repeat this process as long as the item at the front of the queue is due now or earlier (earlier could happen if event processing has enough overhead, as the system clock could 'tick' while this is happening).

Thus, your pseudocode might look like this:
Does that help make it more clear?

I have just skimmed this, I will read it thoroughly tomorrow. I sat down with a piece of paper and came with a similar solution to the one you suggested.

En-queue items as normal (using the delay time not the due time), set the timer interval to the one add the head of the queue, when that item is de-queue subtract that items time from the one at the head of the queue, if it's 0 de-queue and stick on the ready queue with the other items that have been de-queued (this is where all items that have been de-queued go, so that they can be processed) repeat this until the value is non-zero and stick the items that were taken of the queue in the same order back onto the queue, I ran couple of tests f this on paper and it work fine.

This won't work. This brings you full-circle to your original problem.

Picture this. You add an event that should fire after 10 seconds. You then add an event that should fire after 5 seconds, so it goes to the front of the queue. When it fires, you see the event that has a 10-second delay, and set the timer accordingly. The problem, however, is that 5 seconds have elapsed, so when the 10-second delay expires, it will have been 15 seconds. In essence, any 'lower priority' event is deferred by the amount of a higher-priority event's delay (rather, the sum of all such delays). DaWei is correct; you need to re-think your notion of priority.

This isn't to say you can't have this work- you can- but it will require extra work. Remember that since delays should progressively decrement, you will need to handle this. You either must traverse the entire queue, and update the delay field of each item, or use another mechanism. Traversing a queue like this is bad because a) it incurs O(N) performance overhead, and b) 'traversing' in this manner is not an operation associated with a queue ADT. Rather, you should stick to enqueue, dequeue, and support methods/properties such as peek, isEmpty, etc. If you can iterate through it without dequeuing elements, then it's a list, not a queue.

One mechanism you could use is to maintain an adjustment factor (let's call it delta); delta is initially zero. When the timer fires, you handle the event at the front of the queue, and add its delay to delta. You then peek at the next item, subtract delta, and handle it if the result is zero or less, repeating as necessary. Once all such events are handled, you initialize the timer with the difference between delta and the front of queue's delay, and wait for the next timer firing. This approach, to me, is more complicated than my initial suggestion in this thread, as it requires tracking more state information.

My initial suggestion was aimed at getting around the 'delays not adjusting as time goes by' problem. If you store the delay, you need to adjust it in some manner, as described above. If you store the due time, you can calculate the delay as the difference between the due time and the current time. Thus, you don't need to continuously adjust your delays; since they are expressed as a relationship between an automagically updating value (DateTime.Now) and a fixed value, they update automagically themselves. You also get deterministic behavior in that an event will only be pre-empted by an event that is due sooner (and possibly at the same time, depending on your heap implementation). This is a Good Thing (tm) as it lets you make some guarantees about event latency (subject to event-handling overhead, of course). After all, there's no point having a setup to fire an event after, say, 500 milliseconds and then have it take 30 seconds to occur.

Items in the queue: 5(item1) 10(item2)

5 seconds pass:

dequeue item1, now subtract 5(item1's time) from the item at the head of the queue(item2), not zero so set the interval to 5. Now put all items that were dequeued back into the queue (with their original times).

Items in the queue: 5 (item2), 5 item(1)

5 seconds pass: (in total 10 seconds have passed)

Dequeue item2(because it's at the head of the queue), now subtract 5(item2's time) from the item at the head of the queue(item1), 5-5 = 0, now also dequeue item1.Now put all items that were dequeued back into the queue.(with their original times).

items in the queue5(item1) 10 (item2)


..and so on

You need to decide which approach you want to take. I've suggested two, the first storing due times (I prefer this approach, as it is simpler and thus less likely to be buggy) and the second storing delays (as in your original post) coupled with an adjustment of those delays. From your post above, it seems you're back to the second approach. While it can work, it's got issues that can catch you out. Here's an example, starting with an empty queue:

Enqueue event A with delay 10. Queue looks like A(10). Enqueue B with delay 5. Queue is B(5) A(10). Five 'ticks' (tick being a unit of time, whether seconds, milliseconds, etc is irrelevant) pass, the timer fires, and event B is handled. By subtracting B's delay from A, we get 5, and thus we set the timer to fire after 5 ticks. We also add event C with delay 4. What happens? If we put it at the front of the queue, adjust the delay, and reset the timer, it will fire immediately (rather than after four ticks). If we stick it at the end of the queue, and let it fire along with event A, it will fire one tick later than it should.

This issue can be resolved, but doing so needlessly complicates the system. I really think storing due times is a better idea. Here's how the sequence above would look:

Enqueue event A with delay 10. The 'due time' is set to 10 (assume 'current time' is zero; I'm using a simple number for time, as it can be expressed that way). Enqueue event B with delay 5; due time is set to 5. Queue is now B(5) A(10). Five ticks elapse, and event B fires. Current time is now 5, event C is enqueued with delay 4. Adding this delay to the current time gives us 9, so the queue is C(9) A(10). Timer is set to fire after 4 ticks (9 - now equals 9 - 5 equals 4), and after four ticks, event C fires. Current time is now 9, queue is A(10), and the timer is set to fire after 1 tick. To me, this is a lot easier to follow, and the events all fire in the proper order and after the correct delay, within the limits of timer granularity (timer granularity applies to any implementation, not just mine).