Class TimeoutPriorityQueueImpl

  • All Implemented Interfaces:
    TimeoutPriorityQueue

    public class TimeoutPriorityQueueImpl
    extends java.lang.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$
    • Constructor Detail

      • TimeoutPriorityQueueImpl

        public TimeoutPriorityQueueImpl()
        Create a new TimeoutPriorityQueueImpl.
    • Method Detail

      • offer

        public TimeoutExt offer​(long time,
                                TimeoutTarget target)
        Description copied from interface: TimeoutPriorityQueue
        Add a timeout to the queue
        Specified by:
        offer in interface TimeoutPriorityQueue
        Parameters:
        time - the time of the timeout
        target - the timeout target
        Returns:
        timeout when it was added to the queue, false otherwise
      • poll

        public TimeoutExt poll()
        Description copied from interface: TimeoutPriorityQueue
        Retrieves and removes the top of the queue if it times out or null if there is no such element
        Specified by:
        poll in interface TimeoutPriorityQueue
        Returns:
        the top the queue or null if the queue is empty
      • poll

        public TimeoutExt poll​(long wait)
        Description copied from interface: TimeoutPriorityQueue
        Retrieves and removes the top of the queue if it times out or null if there is no such element
        Specified by:
        poll in interface TimeoutPriorityQueue
        Parameters:
        wait - how to long to wait in milliseconds if the queue is empty
        Returns:
        the top of the queue or null if the queue is empty
      • peek

        public TimeoutExt peek()
        Description copied from interface: TimeoutPriorityQueue
        Retrieves but does not remove the top of the queue or null if there is no such element
        Specified by:
        peek in interface TimeoutPriorityQueue
        Returns:
        the top of the queue or null if the queue is empty
      • isCancelled

        public boolean isCancelled()
        Whether the queue is cancelled
        Returns:
        true when cancelled
      • normalizeUp

        private boolean normalizeUp​(int index)
        A new node has been added at index index. Normalize the tree by moving the new node up the tree.
        Returns:
        true if the tree was modified.
      • swap

        private void swap​(int a,
                          int b)
        Swap two nodes in the tree.
        Parameters:
        a - the first index
        b - the second index
      • removeNode

        private TimeoutPriorityQueueImpl.TimeoutExtImpl removeNode​(int index)
        Remove a node from the tree and normalize.
        Parameters:
        index - the index in the queue
        Returns:
        the removed node.
      • checkTree

        void checkTree()
        Check invariants of the queue.
      • assertExpr

        private void assertExpr​(boolean expr)
        Debugging helper.