java.util
Class TaskQueue
java.lang.Object
|
+--java.util.TaskQueue
- class TaskQueue
- extends Object
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
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.
-