
1. Re: TimeoutFactory update
Scott Stark Jan 22, 2006 11:00 AM (in response to Scott Stark)The previous TimeoutFactory priority queue is not gernalized as its coupled to the TimeoutImpl details. There is a org.jboss.util.Heap which could be used instead.

2. Re: TimeoutFactory update
Dimitris Andreadis Jan 27, 2006 10:20 AM (in response to Scott Stark)I looked at many generic Heap / PriorityQueue implementations and they all suffer from the inefficiency that removing an arbitrary object, other than the one on the "top" on the heap requires (a) a sequencial scan of the stored elements, until it is found & removed, (b) the heap restructured.
Ole's implementation avoids (a) because the stored elements keep an index back to Heap, that is updated whenever stored elemenets are swapped inside the Heap.
So generalizing this (factoring out the priority queue), without the performance hit it not possible, I think. 
3. Re: TimeoutFactory update
Scott Stark Jan 27, 2006 9:53 PM (in response to Scott Stark)Here is one acm article that claims an integer priority queue with O(log log n) delete operations:
http://portal.acm.org/citation.cfm?id=780566
We consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are in the range [0,N), we can also support delete in O(log log N) time.Even for the special case of monotone priority queues, where the minimum has to be nondecreasing, the best previous bounds on delete were O((log n)1/(3?)) and O((log N)1/(4?)). These previous bounds used both randomization and amortization. Our new bounds a deterministic, worstcase, with no restriction to monotonicity, and exponentially faster.As a classical application, for a directed graph with n nodes and m edges with nonnegative integer weights, we get single source shortest paths in O(m+n log log n) time, or O(m+n log log C) if C is the maximal edge weight. The later solves an open problem of Ahuja, Mehlhorn, Orlin, and Tarjan from 1990. 
4. Re: TimeoutFactory update
Scott Stark Jan 27, 2006 10:02 PM (in response to Scott Stark)I can't tell from the link if this is an arbitrary delete or just the deleteMin. Given the time bound its probably just the deleteMin, not deletion of an arbitary element.

5. Re: TimeoutFactory update
Dimitris Andreadis Jan 28, 2006 3:57 AM (in response to Scott Stark)I've checkedin in HEAD a restore of the previous implementation, enhanced with the new interface (ability to create new TimeoutFactories using a user provided ThreadPool, with graceful shutdown) if anyone wants to review. Needs testing.

6. Re: TimeoutFactory update
Dimitris Andreadis Jan 30, 2006 3:48 AM (in response to Scott Stark)It looks ok to me so I'm porting this TimeoutFactory to 3.2.x/4.0.x