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$