A timeout manager stores a priority queue of timeout items, each a (callback method, callback time) pair.

Fantastic news! We've Found the answer you've been seeking!

Question:

A timeout manager stores a priority queue of timeout items, each a (callback method, callback time) pair. Each callback method is called approximately N milliseconds after the timeout is set, where N is the delay specified when adding the timeout item. Ex:

At time t = 0, a 500-millisecond timeout is set for method A
At time t = 100, a 3000-millisecond timeout is set for method B
At time t = 2000, a 1000 millisecond timeout is set for method C
So the timeout manager should call the callbacks as follows:

Call method A at time t = 0 + 500 = 500
Call method C at time t = 2000 + 1000 = 3000
Call method B at time t = 100 + 3000 = 3100
A timeout item with a callback time <= the current time is said to be "expired".

Millisecond-level callback precision is often unfeasible. So a timeout manager typically has an update method that is called by external code every so often, ex: every 100 milliseconds. The manager's update method calls each expired timeout's callback method.

Step 1: Inspect TimeoutItem.java
Inspect the TimeoutItem class declaration in the read only TimeoutItem.java file. Access TimeoutItem.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. The callbackTime private field stores the time the item was added plus the item's delay. Ex: A TimeoutItem created at t=500 with a delay of 1000 has callbackTime = 500 + 1000 = 1500. The callbackMethod private field is the method to call after the timeout expires.

TimeoutItem implements the compareTo() method so that TimeoutItems can be put in a PriorityQueue that gives higher priority to lesser callbackTime values.

Step 2: Inspect MillisecondClock.java and TestClock.java
MillisecondClock is an abstract base class for a clock. The getTime() method returns an integer indicating the clock's current time, in milliseconds. Inspect the class declarations in the read only TestClock.java file.

Times are simulated during grading using the TestClock class. TestClock extends MillisecondClock and allows the clock's time to be set via the setTime() method.

Step 3: Implement TimeoutManager's addTimeout() and update() methods
Complete the TimeoutManager class implementation in TimeoutManager.java. addTimeout() must add a new TimeoutItem to the priority queue that expires delayBeforeCallback milliseconds after the current time. update() must dequeue and call the callback method for each expired timeout item. Use TimeoutManager's clock field to get the current time.

Step 4: Test in develop mode, then submit
File LabProgram.java contains two automated tests that can be run in develop mode. Each adds timeouts and invokes updates at various times, then verifies that the proper callback methods are called during each update. Additional tests can be added, if desired. Ensure that the two tests in develop mode pass before submitting you code.

Given 5 files: LabProgram.java, MillisecondClock.java, TestClock.java, TimeoutItem.java. TimeoutManager.java

The only file that needs to be changed is TimeoutManager.java

LabProgram.java

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class LabProgram {
public static boolean verifyCallbacks(PrintWriter testFeedback, ArrayList actual,
ArrayList expected) {
// Compare ArryList sizes first
boolean areEqual = true;
if (actual.size() == expected.size()) {
for (int i = 0; areEqual && i < actual.size(); i++) {
if (!actual.get(i).equals(expected.get(i))) {
areEqual = false;
}
}
}
else {
areEqual = false;
}

// Print results
testFeedback.write(areEqual ? "PASS" : "FAIL");
testFeedback.write(": Verification of invoked callbacks");
testFeedback.write(" Expected: " + expected + "");
testFeedback.write(" Actual: " + actual + "");
return areEqual;
}

public static boolean test1(PrintWriter testFeedback) {
TestClock clock = new TestClock();
TimeoutManager timeouts = new TimeoutManager(clock);

ArrayList actualCallbacks = new ArrayList();
ArrayList expectedCallbacks = new ArrayList();

// Test with items:
// Added at clock time = 0:
// - item D with delay 500 (callback time is 500)
// - item A with delay 100 (callback time is 100)
// Added at clock time = 50
// - item B with delay 150 (callback time is 200)
clock.setTime(0);
timeouts.addTimeout(() -> {
actualCallbacks.add("D");
testFeedback.write("Item D's callback");
}, 500);
timeouts.addTimeout(() -> {
actualCallbacks.add("A");
testFeedback.write("Item A's callback");
}, 100);
clock.setTime(50);
timeouts.addTimeout(() -> {
actualCallbacks.add("B");
testFeedback.write("Item B's callback");
}, 150);

// an update with clock time = 100, which should invoke item A's
// callback
clock.setTime(100);
testFeedback.write("Updating with clock time = 100. Item A should show below.");
timeouts.update();

// Verify that only item A's callback was called
expectedCallbacks.add("A");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// another update with a clock time of 150, which shouldn't invoke any
// callbacks
clock.setTime(150);
testFeedback.write("Updating with clock time = 150. No callbacks should show below.");
timeouts.update();

// Verify that still only item A's callback has been called
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// Add more timeouts at clock time = 300:
// - item E with delay 500 (callback time is 800)
// - item C with delay 100 (callback time is 400)
clock.setTime(300);
testFeedback.write("Adding timeouts E and C");
timeouts.addTimeout(() -> {
actualCallbacks.add("E");
testFeedback.write("Item E's callback");
}, 500);
timeouts.addTimeout(() -> {
actualCallbacks.add("C");
testFeedback.write("Item C's callback");
}, 100);

// Verify that adding new timeouts didn't invoke any new callbacks
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// an update with a clock time of 350, which should invoke item B's
// callback
clock.setTime(350);
testFeedback.write("Updating with clock time = 350. Item B should show below.");
timeouts.update();

// Verify callbacks: A and B called, others not
expectedCallbacks.add("B");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// an update with a clock time of 550, which should invoke item C's
// callback and item D's callback, in that order
clock.setTime(550);
testFeedback.write("Updating with clock time = 550. Item C and D should show below, ");
testFeedback.write("in that order.");
timeouts.update();

// Verify callbacks: A, B, C, and D
expectedCallbacks.add("C");
expectedCallbacks.add("D");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// another update with a clock time of 700, which shouldn't invoke any
// callbacks
clock.setTime(700);
testFeedback.write("Updating with clock time = 700. No callbacks should show below.");
timeouts.update();

// Verify callbacks: again just A, B, C, and D
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// a final update with time = 900, which should invoke item E's callback
clock.setTime(900);
testFeedback.write("Updating with clock time = 900. Item E should show below.");
timeouts.update();

// Verify callbacks: A, B, C, D, and E
expectedCallbacks.add("E");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

return true;
}

public static boolean test2(PrintWriter testFeedback) {
TestClock clock = new TestClock();
TimeoutManager timeouts = new TimeoutManager(clock);

ArrayList actualCallbacks = new ArrayList();
ArrayList expectedCallbacks = new ArrayList();

// At t = 0:
// - Add item A with delay 800 (callback time is 800)
clock.setTime(0);
testFeedback.write("At t=0, adding timeout A with delay = 800");
timeouts.addTimeout(() -> {
actualCallbacks.add("A");
}, 800);

// At t = 50:
// - Add item D with delay 600 (callback time is 650)
clock.setTime(50);
testFeedback.write("At t=50, adding timeout D with delay = 600");
timeouts.addTimeout(() -> {
actualCallbacks.add("D");
}, 600);

// At t = 100:
// - Add item C with delay 200 (callback time is 300)
clock.setTime(100);
testFeedback.write("At t=100, adding timeout C with delay = 200");
timeouts.addTimeout(() -> {
actualCallbacks.add("C");
}, 200);

// At t = 150:
// - Add item E with delay 250 (callback time is 400)
clock.setTime(150);
testFeedback.write("At t=150, adding timeout E with delay = 250");
timeouts.addTimeout(() -> {
actualCallbacks.add("E");
}, 250);

// At t = 200:
// - Add item B with delay 50 (callback time is 250)
// - Update, then verify that no callback have yet been called
clock.setTime(200);
testFeedback.write("At t=200, adding timeout B with delay = 50");
testFeedback.write(", then updating");
timeouts.addTimeout(() -> {
actualCallbacks.add("B");
}, 50);
timeouts.update();
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// At t = 400:
// - Update, then verify that callbacks B, C, and E have been called
clock.setTime(400);
testFeedback.write("At t=400, updating");
timeouts.update();
expectedCallbacks.add("B");
expectedCallbacks.add("C");
expectedCallbacks.add("E");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// At t = 450:
// - Add item F with delay 100 (callback time is 550)
clock.setTime(450);
testFeedback.write("At t=450, adding timeout F with delay = 100");
timeouts.addTimeout(() -> {
actualCallbacks.add("F");
}, 100);

// At t = 600:
// - Update, then verify callbacks: B and C from earlier, E and F now
clock.setTime(600);
testFeedback.write("At t=600, updating");
timeouts.update();
expectedCallbacks.add("F");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

// At t = 800:
// - Update, then verify callbacks: B, C, E, F, D, A
clock.setTime(800);
testFeedback.write("At t=800, updating");
timeouts.update();
expectedCallbacks.add("D");
expectedCallbacks.add("A");
if (!verifyCallbacks(testFeedback, actualCallbacks, expectedCallbacks)) {
return false;
}

return true;
}

public static void main(String[] args) {
PrintWriter testFeedback = new PrintWriter(System.out);
boolean test1Result = test1(testFeedback);
testFeedback.println();

boolean test2Result = test2(testFeedback);
testFeedback.println();

testFeedback.flush();

System.out.println("Local test 1: " + (test1Result ? "PASS" : "FAIL"));
System.out.println("Local test 2: " + (test2Result ? "PASS" : "FAIL"));

testFeedback.close();
}
}

MillisecondClock.java

public abstract class MillisecondClock {
abstract int getTime();
}

TestClock.java

public class TestClock extends MillisecondClock {
private int currentTime;

public TestClock() {
currentTime = 0;
}

@Override
public int getTime() {
return currentTime;
}

// Sets this clock's current time, provided the new time is greater than the
// previously set time.
public boolean setTime(int newTime) {
// Only allow time to move forward
if (newTime > currentTime) {
currentTime = newTime;
return true;
}
return false;
}
}

TimeoutItem.java

@FunctionalInterface
interface CallbackMethod {
void invoke();
}

public class TimeoutItem implements Comparable {
private int callbackTime;
private CallbackMethod callbackMethod;

public TimeoutItem(CallbackMethod callbackMethod, int callbackTime) {
this.callbackTime = callbackTime;
this.callbackMethod = callbackMethod;
}

public TimeoutItem(TimeoutItem toCopy) {
this.callbackTime = toCopy.callbackTime;
this.callbackMethod = toCopy.callbackMethod;
}

public void callCallback() {
callbackMethod.invoke();
}

final public int getCallbackTime() {
return callbackTime;
}

@Override
public int compareTo(TimeoutItem tItem) {
// Java's PriorityQueue keeps item with smallest value at the front.
if (this.callbackTime > tItem.callbackTime) {
return 1;
}
else if (this.callbackTime < tItem.callbackTime) {
return -1;
}
else {
return 0;
}
}
}

TimeoutManager.java

import java.util.*;

public class TimeoutManager {
// Priority queue for timeout items. The timeout item with the lowest
// callback time is the first to be dequeued.
protected PriorityQueue pq = new PriorityQueue();

// A clock used to get the current time in the addTimeout() and
// update() method.
protected MillisecondClock clock;

public TimeoutManager(MillisecondClock clock) {
this.clock = clock;
}

// Returns a reference to this timeout manager's internal priority queue.
// Used only for grading purposes.
public PriorityQueue getPriorityQueue() {
return pq;
}

// Adds a timeout item, given a callback method and delay time as
// parameters. The added timeout expires at:
// (clock's current time when this method is called) + (delay time)
public void addTimeout(CallbackMethod callback, int delayBeforeCallback) {
// Your code here

int callBackTime = clock.getTime() + delayBeforeCallback;

TimeoutItem timeoutItem = new TimeoutItem(callback, callBackTime);

pq.offer(timeoutItem);

}

// Dequeues each expired timeout item from the priority queue and calls each
// expired item's callback method.
public void update() {
// Your code here

int time = clock.getTime();

while(!pq.isEmpty() && pq.peek().getCallbackTime() <= time){

TimeoutItem timeoutItem = pq.poll();

timeoutItem.getCallbackTime();

}

}
}