java.util
Class TaskQueue

java.lang.Object
  extended byjava.util.TaskQueue

class TaskQueue
extends Object

This class represents a timer task queue: a priority queue of TimerTasks, ordered on nextExecutionTime. Each Timer object has one of these, which it shares with its TimerThread. Internally this class uses a heap, which offers log(n) performance for the add, removeMin and rescheduleMin operations, and constant time performance for the the getMin operation.


Field Summary
private  TimerTask[] queue
          Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n] and queue[2*n+1].
private  int size
          The number of tasks in the priority queue.
 
Constructor Summary
(package private) TaskQueue()
           
 
Method Summary
(package private)  void add(TimerTask task)
          Adds a new task to the priority queue.
(package private)  void clear()
          Removes all elements from the priority queue.
private  void fixDown(int k)
          Establishes the heap invariant (described above) in the subtree rooted at k, which is assumed to satisfy the heap invariant except possibly for node k itself (which may have a nextExecutionTime greater than its children's).
private  void fixUp(int k)
          Establishes the heap invariant (described above) assuming the heap satisfies the invariant except possibly for the leaf-node indexed by k (which may have a nextExecutionTime less than its parent's).
(package private)  TimerTask getMin()
          Return the "head task" of the priority queue.
(package private)  boolean isEmpty()
          Returns true if the priority queue contains no elements.
(package private)  void removeMin()
          Remove the head task from the priority queue.
(package private)  void rescheduleMin(long newTime)
          Sets the nextExecutionTime associated with the head task to the specified value, and adjusts priority queue accordingly.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

queue

private TimerTask[] queue
Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is ordered on the nextExecutionTime field: The TimerTask with the lowest nextExecutionTime is in queue[1] (assuming the queue is nonempty). For each node n in the heap, and each descendant of n, d, n.nextExecutionTime <= d.nextExecutionTime.


size

private int size
The number of tasks in the priority queue. (The tasks are stored in queue[1] up to queue[size]).

Constructor Detail

TaskQueue

TaskQueue()
Method Detail

add

void add(TimerTask task)
Adds a new task to the priority queue.


getMin

TimerTask getMin()
Return the "head task" of the priority queue. (The head task is an task with the lowest nextExecutionTime.)


removeMin

void removeMin()
Remove the head task from the priority queue.


rescheduleMin

void rescheduleMin(long newTime)
Sets the nextExecutionTime associated with the head task to the specified value, and adjusts priority queue accordingly.


isEmpty

boolean isEmpty()
Returns true if the priority queue contains no elements.


clear

void clear()
Removes all elements from the priority queue.


fixUp

private void fixUp(int k)
Establishes the heap invariant (described above) assuming the heap satisfies the invariant except possibly for the leaf-node indexed by k (which may have a nextExecutionTime less than its parent's). This method functions by "promoting" queue[k] up the hierarchy (by swapping it with its parent) repeatedly until queue[k]'s nextExecutionTime is greater than or equal to that of its parent.


fixDown

private void fixDown(int k)
Establishes the heap invariant (described above) in the subtree rooted at k, which is assumed to satisfy the heap invariant except possibly for node k itself (which may have a nextExecutionTime greater than its children's). This method functions by "demoting" queue[k] down the hierarchy (by swapping it with its smaller child) repeatedly until queue[k]'s nextExecutionTime is less than or equal to those of its children.