java.util
Class TaskQueue

java.lang.Object
  java.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.