TimeoutPriorityQueueImpl (JBoss/Common API)

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

org.jboss.util.timeout
Class TimeoutPriorityQueueImpl

java.lang.Object
  org.jboss.util.timeout.TimeoutPriorityQueueImpl

All Implemented Interfaces:: TimeoutPriorityQueue

public class TimeoutPriorityQueueImpl
extends Object
implements TimeoutPriorityQueue
extends Object
implements TimeoutPriorityQueue

TimeoutPriorityQueueImpl. This is a balanced binary tree. If nonempty, the root is at index 1, and all nodes are at indices 1..size. Nodes with index greater than size are null. Index 0 is never used. Children of the node at index j are at j*2 and j*2+1. The children of a node always fire the timeout no earlier than the node. Or, more formally: Only indices 1..size of this array are used. All other indices contain the null reference. This array represent a balanced binary tree. If size is 0 the tree is empty, otherwise the root of the tree is at index 1. Given an arbitrary node at index n that is not the root node, the parent node of n is at index n/2. Given an arbitrary node at index n; if 2*n <= size the node at n has its left child at index 2*n, otherwise the node at n has no left child. Given an arbitrary node at index n; if 2*n+1 <= size the node at n has its right child at index 2*n+1, otherwise the node at n has no right child. The priority function is called T. Given a node n, T(n) denotes the absolute time (in milliseconds since the epoch) that the timeout for node n should happen. Smaller values of T means higher priority. The tree satisfies the following invariant: For any node n in the tree: If node n has a left child l, T(n) <= T(l). If node n has a right child r, T(n) <= T(r). The invariant may be temporarily broken while executing synchronized on this instance, but is always reestablished before leaving the synchronized code. The node at index 1 is always the first node to timeout, as can be deduced from the invariant. For the following algorithm pseudocode, the operation swap(n,m) denotes the exchange of the nodes at indices n and m in the tree. Insertion of a new node happend as follows:

    IF size = q.length THEN
      "expand q array to be larger";
    ENDIF
    size <- size + 1;
    q[size] <- "new node";
    n <- size;
    WHILE n > 1 AND T(n/2) > T(n) DO
      swap(n/2, n);
      n <- n/2;
    ENDWHILE

Proof that this insertion algorithm respects the invariant is left to the interested reader. The removal algorithm is a bit more complicated. To remove the node at index n:

    swap(n, size);
    size <- size - 1;
    IF n > 1 AND T(n/2) > T(n) THEN
      WHILE n > 1 AND T(n/2) > T(n) DO
        swap(n/2, n);
        n <- n/2;
      ENDWHILE
    ELSE
      WHILE 2*n <= size DO
        IF 2*n+1 <= size THEN
          // Both children present
          IF T(2*n) <= T(2*n+1) THEN
            IF T(n) <= T(2*n) THEN
              EXIT;
            ENDIF
            swap(n, 2*n);
            n <- 2*n;
          ELSE
            IF T(n) <= T(2*n+1) THEN
              EXIT;
            ENDIF
            swap(n, 2*n+1);
            n <- 2*n+1;
          ENDIF
        ELSE
          // Only left child, right child not present.
          IF T(n) <= T(2*n) THEN
            EXIT;
          ENDIF
          swap(n, 2*n);
          n <- 2*n;
        ENDIF
      ENDWHILE
    ENDIF

Proof that this removal algorithm respects the invariant is left to the interested reader. Really, I am not going to prove it here. If you are interested, you can find this data structure and its associated operations in most textbooks on algorithmics.

Version:: $Revision: 1.1.2.4 $
Author:: Ole Husgaard, Dimitris Andreadis, Elias Ross, Adrian Brock
See Also:: checkTree

Constructor Summary
`TimeoutPriorityQueueImpl()` Create a new TimeoutPriorityQueueImpl.

Method Summary
`void`	`cancel()` Cancels the queue
`void`	`clear()` Clears the queue
`boolean`	`isCancelled()` Whether the queue is cancelled
`TimeoutExt`	`offer(long time, TimeoutTarget target)` Add a timeout to the queue
`TimeoutExt`	`peek()` Retrieves but does not remove the top of the queue or null if there is no such element
`TimeoutExt`	`poll()` Retrieves and removes the top of the queue if it times out or null if there is no such element
`TimeoutExt`	`poll(long wait)` Retrieves and removes the top of the queue if it times out or null if there is no such element
`boolean`	`remove(TimeoutExt timeout)` Removes the passed timeout from the queue
`int`	`size()` The size of the queue
`TimeoutExt`	`take()` Take a timeout when it times out

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

TimeoutPriorityQueueImpl

public TimeoutPriorityQueueImpl()

Create a new TimeoutPriorityQueueImpl.

Method Detail