Thanks for the pointers Neil & Stephen. Any further help greatly appreciated.
I have attached a 15k zip file holding 8 java files. I have not included any Apache licensing comments - I will do this later if I this is what I am supposed to do - greenness showing :-). The classes have been placed, for the time being, separately in the package org.apache.commons.collections.xq (eXotic Queues). The classes fall into 4 groups: TapObject - an interface TapObjectAdapter - a simple implementation of TapObject NOTE1: the tap() method is meant to be over-ridden to do any arbitrarily complex priority upgrade, including setting the next timeout. TapConsumer - an interface TapConsumerAdapter - a simple implementation of TapConsumer XBinaryHeap - a copy/paste of BinaryHeap TapBinaryHeap - a subclass of XBinaryHeap TapQueue - the clever bit :-) NOTE2: I need to extend BinaryHeap. Unfortunately, this is marked as final. I have just copied over the code to XBinaryHeap (eXtendable BinaryHeap). You can do a text search for "Cheung" to see all the modifications. How do I ask for an amendment? NOTE3: I have over-ridden the 4 percolate methods and added 2 more to allow bubbling up at any arbitrary index. NOTE4: TapBinaryHeap really needs to be an inner class of TapQueue. I have pulled it out for the time being so it is more clear. TapTest - has a main() method to demonstrate how it all works. NOTE5: I will write Ant/JUnit files later. Internally, TapQueue has 2 TapBinaryHeaps. A priority max heap and a timeout min heap. Everytime a TapObject is inserted into the TapQueue, the same object is inserted into both the priority and timeout heaps. Those objects with the earliest timeouts will bubble to the top of the timeout heap. When, a timeout occurs the guilty object is popped from the timeout heap. The object has a reference to its' index on the priority heap. The new percolateUpMaxHeap(int index) method is called to bubble the object to the top of the priority heap where it too is popped - keeping both heaps synched. The tap() method of the object is called and, if necessary, re-inserted into the TapQueue where it will bubble up to its' new positions. Everytime a free TapConsumer registers itself with the TapQueue, the queue will, if necessary, re-order itself. The highest priority TapObject will then be popped. The object has a reference to its' index on the timeout heap. The new percolateUpMinHeap(int index) method is called to bubble the object to the top of the timeout heap where it too is popped - keeping both heaps synched. The consumer is given the object and de-registered. Each bubble up/down operation takes place in log(n) time. Re-ordering only happens when necessary. If too much re-ordering take place, then the TapQueue operates in nlog(n) time but if this happens, the system is seriously under-resourced and no amount of re-prioritising will help. I have tested the classes and the logic works OK. I do have some problems when running it multi-threaded mode and haven't worked out what's wrong yet. The problems are commented in TapConsumerAdapter.service() and TapTest.main(). Cheung Lo London, UK -----Original Message----- From: Neil O'Toole [mailto:[EMAIL PROTECTED] Sent: 30 July 2003 23:06 To: Jakarta Commons Developers List Subject: Re: [collections] Proposal for a Timeout Affected Priority Queue --- Cheung Lo <[EMAIL PROTECTED]> wrote: > Proposal for a Timeout Affected Priority Queue > I would like to propose the adoption of the TapQueue into the > collections > packages but need feedback on the following issues: > > 1. Has anyone else had a need for a timeout affected priority queue? > 2. If so, what additional requirements did you have that is not > already > described? > 3. How do I submit a draft of the classes - do I attach a zip file > or paste > into the body of an email? > 4. Who do I send it to? 1. Yup, i hacked together a duct-tape and espresso solution for a situation like this a few years ago. I remember at the time not being very happy with it, and since I don't have access to that proprietary code, I can thankfully forget i had anything to do with it. I would very much like to see a first-class implementation in [collections]. 2. Your description appears to suggest that the implementation only bumps up the priority when the (single) timeout occurs. What might be preferable is to have multiple timeout points (or some other aging scheme). Here's an example. Let's say you had a priority scheme 0->9 (9 highest), and in comes a policy admin job (as from your example). This might get priority 1 (as opposed to a customer call, which might initially have priority 6). Rather than waiting until the absolute timeout occurs (say after 14 days) and then bumping the policy job priority up to 9, it would be useful if after 2 days the policy job gets bumped up to priority 2, then 2 days later to priority 3, etc. Likewise I'd like my customer calls (which initially start at priority 6) to get bumped up to priority 7 after six hours, then to priority 8, which would be the maximum priority for customer calls. With this scheme policy jobs would gradually rise in priority, rather than waiting until the deadline when the policy job would then become absolute top priority (this does sound like my normal working pattern though!). To implement this there must be some way of associating an object (or class of objects) with a particular (configurable) prioritizing scheme. All sorts of things pop into my head ;) I'd really like to see what you've come up with, and since i will probably have some OSS dev time available fairly shortly, I'd be more than happy to lend you a hand with development if needed. 3&4. As stephen said, a zip or a link. If the package is large (>100K?) then you won't be able to mail it to the list anyway, so you would be better off with a link. - Neil --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
xq.zip
Description: Zip compressed data
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
