Top Description Fields Constructors Methods
java.util

pack-priv Class TaskQueue

Located in compilation unit of java.util.Timer.

extends Object
Class Inheritance
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 getMin operation.

Field Summary

Modifier and TypeField and Description
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

AccessConstructor and Description
pack-priv
TaskQueue()

Method Summary

Modifier and TypeMethod and Description
pack-priv void
add(TimerTask task)

Adds a new task to the priority queue.

pack-priv 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).

pack-priv TimerTask
get(int i)

Return the ith task in the priority queue, where i ranges from 1 (the head task, which is returned by getMin) to the number of tasks on the queue, inclusive.

pack-priv TimerTask
getMin()

Return the "head task" of the priority queue.

pack-priv void
heapify()

Establishes the heap invariant (described above) in the entire tree, assuming nothing about the order of the elements prior to the call.

pack-priv boolean
isEmpty()

Returns true if the priority queue contains no elements.

pack-priv void
quickRemove(int i)

Removes the ith element from queue without regard for maintaining the heap invariant.

pack-priv void
removeMin()

Remove the head task from the priority queue.

pack-priv void
rescheduleMin(long newTime)

Sets the nextExecutionTime associated with the head task to the specified value, and adjusts priority queue accordingly.

pack-priv int
size()

Returns the number of tasks currently on the queue.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

queueback to 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]. 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.

sizeback to summary
private int size

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

Constructor Detail

TaskQueueback to summary
pack-priv TaskQueue()

Method Detail

addback to summary
pack-priv void add(TimerTask task)

Adds a new task to the priority queue.

clearback to summary
pack-priv void clear()

Removes all elements from the priority queue.

fixDownback to summary
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.

fixUpback to summary
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.

getback to summary
pack-priv TimerTask get(int i)

Return the ith task in the priority queue, where i ranges from 1 (the head task, which is returned by getMin) to the number of tasks on the queue, inclusive.

getMinback to summary
pack-priv TimerTask getMin()

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

heapifyback to summary
pack-priv void heapify()

Establishes the heap invariant (described above) in the entire tree, assuming nothing about the order of the elements prior to the call.

isEmptyback to summary
pack-priv boolean isEmpty()

Returns true if the priority queue contains no elements.

quickRemoveback to summary
pack-priv void quickRemove(int i)

Removes the ith element from queue without regard for maintaining the heap invariant. Recall that queue is one-based, so 1 <= i <= size.

removeMinback to summary
pack-priv void removeMin()

Remove the head task from the priority queue.

rescheduleMinback to summary
pack-priv void rescheduleMin(long newTime)

Sets the nextExecutionTime associated with the head task to the specified value, and adjusts priority queue accordingly.

sizeback to summary
pack-priv int size()

Returns the number of tasks currently on the queue.