University of Toronto
Department of Computer Science
CSC148H, Summer 2007

Assignment 2 (Due June 16 @ 9am)

Motivation

What you should learn from this assignment includes the use and implementation of two standard data structures: Stacks and Queues. The assignment will also give you practice working with specifications, testing and documentation.

In order for all this to succeed, you must follow the specifications precisely. It is common even for quite experienced programmers to find that they have neglected some point of a specification and that their "obviously correct" program does not work properly. For beginners, reading carefully does not come naturally, and one thing you will learn from this assignment is that you do have to read parts of the handout more than once.

You will also learn that specifications never achieve complete precision; sometimes you'll need to ask us for further details, and sometimes you'll need to make an intelligent extrapolation on your own.

This assignment will also extend your experience with good programming practices, in the form of JUnit testing and Javadoc documentation.

Part 1 [20 %]

The goal of Part 1 is to implement a PureStack (defined in section 8.1.1 of the text) using only instances of PureQueue (defined in section 8.2.1 of the text). You are given an implementation of PureQueue in the starter code for use in this part; this is the class LLPureQueue. You are also given most of the implementation for the PureStack, in the class QStack. Your only job is to implement the pop() function. The peek() function is to be left unimplemented.

In order to get full marks, you may not use any other instance variables other than those defined in the starter code. You may declare local variables in the pop() function as you see fit, but you cannot use anything from java.util.*, and you cannot use any data structures other than PureQueue for implementing this method. Not following these constraints will cost you all correctness marks for this part.

You should use good programming practices, document your code, and use appropriate style. You should also write JUnit tests to test your code. However, you do not have to submit your JUnit tests for Part 1. (Submission of JUnit tests will be done in part 2).

Question: Is implementing a PureStack using a PureQueue a good idea? Why or why not? (Hint: Comment on how long it takes to execute your implementation of the pop() function compared to how long it would take if you had used java.util.LinkedList for the implementation instead.) Submit your answer in a text file called answer.txt. Your answer should be no more than a sentence or two in length.

Part 2 [80 %]

Millenium Robots is a company renowned for making robots. It makes robots that can perform many different tasks, including anything from washing your dishes to doing your laundry. The only problem is that the robots are not "extensible" -- that is, they are not programmable. They come with a fixed set of tasks that they know how to do, but if someone wants program them to do something else, they're out of luck.

Your job is to help Millenium Robots to program the software for a new extensible robot. We realize that developing such a complex piece of machinery can take months, or even years, and so our expectations for what you will have implemented at the end of this assignment are actually quite modest. The aim of this assignment is for you to implement some code that will allow us to run rudimentary simulations of the robot.

The most basic things that your robot understands are Instructions. Instructions are grouped into Functions. In order to get your robot to do anything meaningful, you need to submit Tasks to it. A task basically consists of a "main" function, which specifies where execution is to begin.

Once all the tasks to be run have been submitted to the robot, the robot can be told to start executing tasks for a specified duration of time. How the robot runs the tasks depends on the type of robot being used. It can either be a Non-Preemptive robot, or a Round Robin robot. In the former case, the robot runs each task to completion before starting the next one. In the latter case, the robot runs the task for a specified "quantum" of time, and if the task is not done at the end of this time, it will move the task to the end of the queue of tasks waiting to be executed and move to the next task to be executed.

There are four types of instructions that you have to concern yourself with:

CALL_TYPE. These types of instructions are invoked when a new Function is to be called by the robot. When a new function is called, the current one being executed is pushed onto a "call stack", so that when the new function returns, the robot knows where execution should continue.
RETURN_TYPE. These types of instructions are invoked when the end of a function is reached and control is supposed to return to the calling function. The calling function is determined by popping the "call stack". When a task's main function returns, the Task is considered "done".
GOTO_TYPE. These types of instructions are invoked in order to jump to an instruction anywhere inside the function currently being executed. Normally instructions are executed one after another (in linear sequence), but this instruction allows for other paths of execution.
OTHER_TYPE. All other types of instructions are lumped into this category and do not have any special semantics.

Instructions are defined by three things: their type (one of the four types just described), the the time it takes to execute them, and their operands. (Think of "operands" like arguments to a function.)

Each Task has associated with it a Task State. The state describes the function currently being executed, the instruction within that function to be executed next, and the length of time the task has been running for. After you've run a task for a specified duration, the state that the task is in needs to be updated.

The marker will verify the correctness of your implementation by submitting a number of tasks to the robot (defined by the marker), and running the robot for a specified duration. The state that each task is in after the robot has finished running will be checked. If they are in the expected state, you will receive full marks for correctness; otherwise, you will lose marks.

Class Specifications

The `EditableQueue` Interface and `LLEditableQueue` Class (YOU MUST WRITE CODE)

The EditableQueue interface extends the PureQueue interface (section 8.2.1 of the text) by adding the following method:

public boolean remove(E element) - removes the specified element from the queue (regardless of where it is in the queue).

You are to implement the interface EditableQueue using a linked list. Note: you are allowed to use java.util.* in this part. Your implementation should be put in the class LLEditableQueue.

The `PureStack` Interface and `LLPureStack` Class (provided in full in the Starter code)

The PureStack interface is the interface as defined in section 8.1.1 of the text. LLPureStack is an implementation of it using a linked list.

The `Instruction, OtherInstruction, CallInstruction, GotoInstruction, and ReturnInstruction` Classes (provided in full in the Starter Code)

The Instruction class defines an instruction that can be executed by the robot. It contains 4 constants used for specifying the different types of instructions: CALL_TYPE, RETURN_TYPE, GOTO_TYPE, and OTHER_TYPE. Its constructor takes three parameters: the type, the execution time, and the operands. The type is one of the 4 constants, the execution time is the time it takes the robot to execute the instruction, and the operands are the "extra" information required for executing that instruction (think of "operands" like arguments to a function). Instruction is an abstract class and you should never have to construct an instance of it; instead, you should use one of the four subclasses:

OtherInstruction, CallInstruction, GotoInstruction,
ReturnInstruction.

The Instruction class defines the following methods:

int getType() - returns the type (one of the predefined constants)
long getExecuteTime() - returns the time it takes to execute the instruction
Object[] getOperands() - returns the operands required by this instruction

The constructor for OtherInstruction has 1 parameter: the execution time of the instruction. It has no operands.

The constructor for ReturnInstruction takes no parameters; its execution time is predefined in the class. It has no operands.

The constructor for CallInstruction takes 1 parameter: the function to be called. CallInstruction's execution time is predefined in the class. The function to be called can be retrieved as the first element from the operands array.

The constructor for GotoInstruction takes 1 parameter: the (integer) index of the next instruction to goto. GotoInstruction's execution time is predefined in the class. The index can be retrieved as the first element from the operands array.

The `Function` class (provided in full in the Starter Code)

The Function class is used for grouping instructions, and has the following methods:

public void addInstruction(Instruction i) - adds an instruction to the sequence of instructions to be executed by this function
public Instruction getInstruction(int index) - retrieves the intstruction at the specified index.

See the class documentation in the starter code for a description of how to make use of this class. Also take a look at the sample test case provided (SampleRoundRobinRobotTester).

The `TaskState` class (provided in full in the Starter Code)

The TaskState class is used to specify the current state of a Task. It contains the following methods:

public Function getCurrentFunction() - get the function that's currently executing
public int getInstructionIndex() - get the index of the instruction to be next executed in the current function
public long getRunningTime() - get the "actual" total time that the task has been running for
public boolean isDone() - return if the task is done or not (i.e., if the main function of the task has encountered a return instruction or not)

Its constructor takes four arguments corresponding to the values that are to be returned by the above four functions.

The Task class (YOU MUST WRITE CODE)

A Task consists of a "main" function, which defines where the task's execution begins. Its constructor takes the "main" function as its sole parameter. A Task has the following methods:

public TaskState getState() - returns the current state of the task
public TaskState run(long duration) - runs the task for at most the specified duration and returns the new state at the end of execution. You need to provide an implementation of this method. See the method documentation in the starter code for how your implementation should behave.

There are three instance variables defined in the starter code to help you with the implementation:

PureStack<Function> callStack
PureStack<Integer> indexStack
TaskState curState

The variable callStack maintains a stack of functions that have currently been called. The top of the stack is the function that is currently executing, one level from the top is the function that called the currently executing function, and so forth.

The variable indexStack is stack that is "parallel" to the callStack and maintains the index of the instruction that should be executed next. The top of the stack contains the instruction that should be executed next in the function that is at the top of callStack. One level from the top is the index of the instruction that should be next executed when the function one level from the top in callStack starts executing again, and so forth.

The variable curState maintains the current state of the Task.

The implementation of run() should basically follow this pseudocode:

while (there is time remaining and task isn't done) {

    Function curFunction = top of callStack

    int curIndex = top of indexStack



    Instruction curInstruction =
curFunction.getInstruction(curIndex)

    if (curInstruction.getExecuteTime() <= time
remaining) {

       update remaining time based on the time
it takes to execute the instruction

       

       switch(instruction type) {

       case CALL_TYPE:

          update indexStack
appropriately

          push new function onto
callStack

          push new index onto
indexStack (what should the index be???)

       case RETURN_TYPE:

          left to student to figure
out what to do here

       case GOTO_TYPE:

          update indexStack
appropriately

       case OTHER_TYPE:

          update indexStack
appropriately

       }

    }

}



update the task state (note that the time run may be less than the
duration passed into the run() function)

Note that the pseudocode above only gives you a rough idea of how your implementation should work -- there may be corner cases or other gotchas that you need to handle. Furthermore, the pseudocode is intentionally vague so that the solution isn't entirely laid out for you.

The `Robot` Interface and`NonPreemptiveRobot and RoundRobinRobot` Classes (YOU MUST WRITE CODE)

The Robot interface defines the the main functionality provided by the robot. It contains the following methods

void addTask(Task t) - "submits" a task for execution by the robot. (Implementation provided for you)
void removeTask(Task t) - removes a task previously submitted. You must provide an implementation of this method.
void run(long duration) - runs the robot for at most the specified duration, where the duration is specified in milliseconds. You must provide an implementation of this method.
long getRunningTime() - returns the "actual" amount of time the robot has been running for. (Implementation provided for you)

You must implement NonPreemptiveRobot and RoundRobinRobot. There are two instance variables defined in both of these classes in the starter code to help you:

long runningTime
EditableQueue<Task> queue

The variable runningTime stores the total amount of time that the robot has actually been running for. This value may be slightly less than the sum of the "duration" values passed into calls of run(). This may happen when the duration tasks are expected to run are not an integral multiple of the execution time of the instructions. For example, if you have an instruction that takes 7 ms to execute, and ask the robot to run for 5ms, then the instruction cannot be executed and the "actual" time that the robot ran for is 0 ms.

The variable queue is used for maintaining the queue of tasks that the robot has to execute. Tasks are placed at the end of the queue whenever the method addTask() is called. Tasks are removed from this queue whenever the method removeTask() is called.

The RoundRobinRobot class defines one additional instance variable:

long quantum

The value of quantum is passed in as a parameter to the constructor of RoundRobinRobot and defines the how long the front task in the queue should be run before moving to the next task.

You must provide implementations in both NonPreemptiveRobot and RoundRobinRobot for the removeTask() and run() functions.

The implementation of RoundRobinRobot's run() function should basically follow this pseudocode:

while(the time remaining is greater than the quantum and the
queue is not empty) {

    dequeue the next task

    run the task for the specified quantum



    update the remaining time left based on the actual
time that the task was run for (it may run less than the specified
quantum) 



    reenqueue the task if it isn't done

}

update the total runningTime

The run() method in NonPreemptiveRobot is slightly different and left to the student to figure out.

JUnit Tests

You must write and submit JUnit tests for the following classes.

Task
RoundRobinRobot
NonPreemptiveRobot
LLEditableQueue

The names of your JUnit tests for the above classes should be, respectively:

TaskTester
RoundRobinRobotTester
NonPreemptiveRobotTester
LLEditableQueueTester

You should have test cases that adequately tests the public methods in all the above classes.

Writing tests for all the corner cases and "middle of the road" cases would be extremely time consuming. You want to be sure that your implementation is correct, but for marking purposes we will be looking to make sure that you are testing at least one or two boundary cases, and one or two "typical" cases. Make sure that you include comments in your code explaining exactly what it is you're testing.

Hints, Tips, and Important Assumptions

When we say "run the robot for a specified duration", we do NOT mean to imply that you are running a real-time simulation. That is, if we tell your robot to run for 1 hour, we do not expect your program to take 1 hour to complete. If your code takes more than 30 seconds to execute a particular test case, we will consider that a failed test case.
Any Goto instructions used in our tests will always specify instruction indices that exist. That is, we will not try to mess your robot up by specifying negative indices, or indices that are too large.
Any Call Instructions used in our tests will always specify a non-null Functions.
You cannot execute instructions "partially". That is, if there is not enough time remaining to execute the instruction in full, then the instruction will remain unexecuted.
In the case of RoundRobinRobot, none of the instructions that we test your robot with will have an execution time longer than the time quantum defined for the robot. In other words, whenever you run a task for a given quantum, it should always execute at least one instruction.
The RoundRobinRobot will not execute "partial" quantums. That is, when running a task, it will only run it if there is enough time left to run it for a full quantum.
There is a sample JUnit test case provided in the class SampleRoundRobinRobotTester.java. It should give you some more concrete grounding in becoming familiar with how this assignment is designed and how things are expected to work.
Be sure to read the javadoc in the starter code for any functions you implement.
Even though a lot of javadoc is already provided to you in the starter code, you still must comment your code properly so that people know what you're doing. Be sure to use comments within methods and javadoc with any new private helper methods that you create.

Organization of the Starter Code

The parts of the code that you have to implement contain the comment "TODO".

Testing hints

Your test cases should cover boundary cases (e.g., no tasks submitted to a robot), as well as "middle of the road" cases.

Test basic methods before complicated ones.

Test simple objects before objects that include or contain the simple objects.

Don't test too many things in a single test case.

Be careful testing static variables (which you should avoid anyway).

Write your test cases early. It's easier to think of test cases when you can remember the troubles you had writing the code, and the process of writing and running tests can also help you to write the code if you do it early.

Coding hints

Re-read the specifications before deciding you're finished with a class. Check the spelling and capitalization of your class names. Check method signatures especially: parameter types and return types, and the spelling of the method name must match exactly. If these don't match the description in the assignment handout your program will not compile and run correctly and the automarker will give a mark of zero.

Write your Javadoc documentation before writing the method it describes. Change it if you realize you've misunderstood. Don't leave documentation to the end, when you no longer remember your code.

Make sure your class names are spelled exactly right, agreeing with the spelling in this handout -- including capitalization -- and make sure your file names match the class names.

Start with the simple operations and the operations that facilitate testing. You may want to restrict the functionality of a class and once the limited version is working add more methods.

Feel free to use private "helper" methods as needed. Document them in the same way you would document public methods.

Style hints

The expectations in CSC 148H/A48H are much the same as in CSC 108H/A08H: comments explaining complicated code, well-chosen names for variables and methods, clear indentation and spacing, etc. In particular, we expect you to follow the capitalization conventions: variableName, methodName, ClassName, PUBLIC_STATIC_FINAL_NAME.

What to submit

For Part 1:

QStack.java containing your implementation of the pop() method.
answer.txt containing your written answer to the question posed.

For Part 2:

Task.java
RoundRobinRobot.java
NonPreemptiveRobot.java
LLEditableQueue.java
TaskTester.java
RoundRobinRobotTester.java
NonPreemptiveRobotTester.java
LLEditableQueueTester.java

Do NOT submit anything NOT listed above.
Do NOT make ANY changes to those classes from the starter that you don't submit.
Do NOT make changes to those classes from to starter code that you are submitting except where the assignment calls for it.
You are encouraged (and it's part of the marking scheme) to write helpers when needed.

Marks Breakdown

Part 1 [ 20 % ]

Correctness - 75%
Style and documentation - 10%
Answer to question - 15%

Part 2 [ 80 % ]

Correctness 50 %
Style and documentation - 30%
Test cases - 20 %

University of Toronto Department of Computer Science CSC148H, Summer 2007