Package org.jboss.util.timeout

Class HashedTimeoutPriorityQueueImpl

  • All Implemented Interfaces:
    TimeoutPriorityQueue
    public class HashedTimeoutPriorityQueueImpl
extends java.lang.Object
implements TimeoutPriorityQueue
    HashedTimeoutPriorityQueueImpl. 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$