public class TimeoutPriorityQueueImpl extends java.lang.Object implements TimeoutPriorityQueue
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.| Modifier and Type | Class and Description |
|---|---|
private class |
TimeoutPriorityQueueImpl.TimeoutExtImpl
Our private Timeout implementation.
|
| Modifier and Type | Field and Description |
|---|---|
private java.lang.Object |
lock
The lock object
|
private TimeoutPriorityQueueImpl.TimeoutExtImpl[] |
queue
The timeouts
|
private int |
size
The size of the timeout queue.
|
| Constructor and Description |
|---|
TimeoutPriorityQueueImpl()
Create a new TimeoutPriorityQueueImpl.
|
| Modifier and Type | Method and Description |
|---|---|
private void |
assertExpr(boolean expr)
Debugging helper.
|
void |
cancel()
Cancels the queue
|
(package private) void |
checkTree()
Check invariants of the queue.
|
private TimeoutPriorityQueueImpl.TimeoutExtImpl |
cleanupTimeoutExtImpl(TimeoutPriorityQueueImpl.TimeoutExtImpl timeout)
Recursive cleanup of a TimeoutImpl
|
void |
clear()
Clears the queue
|
boolean |
isCancelled()
Whether the queue is cancelled
|
private boolean |
normalizeUp(int index)
A new node has been added at index
index. |
TimeoutExt |
offer(long time,
TimeoutTarget target)
Add a timeout to the queue
|
TimeoutExt |
peek()
Retrieves but does not remove the top of the queue
or null if there is no such element
|
TimeoutExt |
poll()
Retrieves and removes the top of the queue if it times out
or null if there is no such element
|
TimeoutExt |
poll(long wait)
Retrieves and removes the top of the queue if it times out
or null if there is no such element
|
boolean |
remove(TimeoutExt timeout)
Removes the passed timeout from the queue
|
private TimeoutPriorityQueueImpl.TimeoutExtImpl |
removeNode(int index)
Remove a node from the tree and normalize.
|
int |
size() |
private void |
swap(int a,
int b)
Swap two nodes in the tree.
|
TimeoutExt |
take()
Take a timeout when it times out
|
private java.lang.Object lock
private int size
private TimeoutPriorityQueueImpl.TimeoutExtImpl[] queue
public TimeoutPriorityQueueImpl()
public TimeoutExt offer(long time, TimeoutTarget target)
TimeoutPriorityQueueoffer in interface TimeoutPriorityQueuetime - the time of the timeouttarget - the timeout targetpublic TimeoutExt take()
TimeoutPriorityQueuetake in interface TimeoutPriorityQueuepublic TimeoutExt poll()
TimeoutPriorityQueuepoll in interface TimeoutPriorityQueuepublic TimeoutExt poll(long wait)
TimeoutPriorityQueuepoll in interface TimeoutPriorityQueuewait - how to long to wait in milliseconds
if the queue is emptypublic TimeoutExt peek()
TimeoutPriorityQueuepeek in interface TimeoutPriorityQueuepublic boolean remove(TimeoutExt timeout)
TimeoutPriorityQueueremove in interface TimeoutPriorityQueuepublic void clear()
TimeoutPriorityQueueclear in interface TimeoutPriorityQueuepublic void cancel()
TimeoutPriorityQueuecancel in interface TimeoutPriorityQueuepublic int size()
size in interface TimeoutPriorityQueuepublic boolean isCancelled()
private boolean normalizeUp(int index)
index.
Normalize the tree by moving the new node up the tree.private void swap(int a,
int b)
a - the first indexb - the second indexprivate TimeoutPriorityQueueImpl.TimeoutExtImpl removeNode(int index)
index - the index in the queueprivate TimeoutPriorityQueueImpl.TimeoutExtImpl cleanupTimeoutExtImpl(TimeoutPriorityQueueImpl.TimeoutExtImpl timeout)
void checkTree()
private void assertExpr(boolean expr)