Due to Passover, Triduum, and Easter, a special no-cost extension on this lab is granted.
The code portion of this assignment can be turned in before
2 PM, Monday 5 April 1999
and still be counted on-time.
Late-lab coupons cannot be used to extend the deadline further.

Overview:

Meanwhile, and apparently (but actually not) unrelated, Java programs are translated into .class files which contain instructions (bytecodes) for a Java Virtual Machine (JVM). The Java program is then executed by interpreting the bytecodes, and doing what they say. It turns out that arithmetic in Java is performed on a stack. For example, addition is accomplished by popping the stack's top two elements, adding them together, and then pushing the result back on the stack. The instruction that does this is called iadd.

In this lab, you will design a generic Stack class, which will then be extended into two subclasses.

1. RoomStack represents a stack of rooms. Suppose Hansel and Gretel were wandering through a maze. The stack would represent how they would find their way back to the starting point, with a bread crumb dropped in each room. You will use the stack of rooms as you explore a maze, starting at its upper-left corner and looking for its lower-right corner.
2. IntStack represents a stack of integers and offers methods for simple calculations based on the stack's top elements.

Goals:

• Understand the design of a generic ADT
• Understand subclassing in greater detail
• Understand the rudiments of a stack-based calculator
• Understand the concept of exhaustive search
• Understand how to throw an error when something bad happens

The design will be discussed Monday in class. In Lab, your graded design will be returned. No other handouts or code will be issued. So, think carefully about your design!

Before starting:

• Read over this entire document before you start.
• Study the Stack and other ADT examples in the notes.
• Study the subclass examples in class and in the notes.
• Run the sample solution.
• If you need help, please ask.

Note: for this lab you will need your solution to Lab 7. Copy those files into your Lab8 subdirectory, and then add the files from the zip.

Zip includes:

• Lab8.java
• Startup.java
• Stack.java
• IntStack.java
• RoomStack.java
• Room.java

Remember to type the following lines at the top of any files that use the terminal or canvas classes.

import cs101.terminal.*;
import cs101.canvas.*;

Particulars

The Room Explorer

Because of your work on Lab 7, the new, robot-occupied, loop-free building has been successfully constructed. It is now time to simulate the progress of a robot through the rooms, as it starts in the upper-left room and tries to find the lower-right room.

The robot, being a methodical creature, will eseentially do two things:

• Upon entering a room, the robot simulates Hansel and Gretels' dropping of crumbs, by pushing the room onto a stack. The robot can always use the stack to reverse its steps.
• Upon entering a room, the robot knows which door it used to enter the room. It then (recursively) uses the room's other open doors to explore the rest of the building.

The maze is formed. There is a unique path between any pair of rooms. In particular, it is possible to traverse the maze, moving from the upper-left corner to the lower-right corner.

Above, you see the robot beginning to explore the rooms. As the robot makes progress through a room, the room is brightened (the robot turns the lights on).	When the robot is done with a room, knowing it cannot be on a path to its final destination, the room is darkened.

The robot has found the destination. The dark rooms are abandoned and the bright rooms are on the path from the source to the destination.	The robot uses the room stack to trace its steps back to the beginning, making each room red as it goes.

The easiest way for us to simulate the robot is to use the Room class. Your task for this lab is to insert a method in Room called void explore(Room stop). When this method is called on a given room, the maze is traversed as described above.

---

Integer Stack Calculators

Our stack calculator is able to perform the following operations:

boolean isEmpty()	Returns true if the stack is empty; otherwise, returns false.
push(int)	Pushes the supplied integer onto the stack. Design issue: Because int is a primitive type, and our stack holds reference types, you need to investigate the use of Java's Integer class, which wraps the primitive int so it can be used as a reference type. Look at the Integer API to see how to construct an Integer and how to extract its value as an int.
Integer popInteger()	Pops the stack's top element, returning the answer as an Integer. Design issue: What should happen when the stack is already empty?
int getTop()	Returns the stack's top cell as an int. The stack is not popped. Design issue: What should be done if the stack is empty? There is no value that we can return to show that an error has occurred. We need to throw an error. Your design should call for this behavior. In class, you will learn how to do this.
add()	Pops the stack's top two integers, computes their sum, and pushes the result. Design issue: What happens if the stack underflows during this operation (i.e., there are not at least two elements on the stack)? This same issue arises in most of the operations below.
mpy()	Pops the stack's top two integers, computes their product, and pushes the result. Design issue: By now, it seems that a common thing to do is to pop the stack and receive the value as an int. Should a private method be written for this purpose to avoid duplication of code? Or, can other methods in this API be used?
neg()	Pops the stack's top integer, negates its value, and pushes the result.
sub()	Pops the stack's top two integers, computes their difference, and pushes the result. Design issue: neg and sub are similar. Can one be written in terms of other operations?
dup()	Duplicates the stack's top integer. After this operation, the stack has grown by one value and the top two values are identical. Design issue: Should the duplicated Integer be a new Integer, or can the one currently at top-of-stack be reused?
prt()	Shows the contents of the stack using Terminal.println.

Big design issue: Should IntStack extend Stack or should IntStack contain a Stack? Think about the operations that your generic Stack can do, and see if they are appropriate for the IntStack. If so, extension should be done so you don't have to duplicate function.

By contrast, consider that RoomSet did not extend List in Lab 7, because many functions of List, such as shuffle and exchange, were inappropriate for a set.

Startup.java

This class is provided for you.

1. Ten times, a Maze of maze of 5x7 rooms is generated using your code from Lab 7. Each time, the explore method is called on the upper-left corner room.
2. IntStack.selfTest() is called.

Room.java

This class is the same as for Lab 7, except for

void explore(Room stop)

This method initiates the exploration of the maze. Exploration should stop when the parameter's room is reached. The rooms actively involved in the exploration should become brighter when entered; rooms no longer under consideration should become darker when exited. To accomplish these color changes, consult the Color class.

What to turn in:

Design (due Monday)

1. Complete a design cover sheet.
2. Provide an API for your generic Stack class. Be sure to indicate what is private, protected, and public.
3. Consider the design issues presented above for IntStack. Turn in your decisions for the design issues. The API is really given to you above---no need to turn an API in for IntStack.
4. Provide an API and basic description of the new methods you will insert into Room. That is, describe what will happen when your explore(Room) is called.
   • The interface to the outside world is public void explore(Room).
   • Some (private) helper methods may be needed.

Implementation (due Friday)

1. Complete a code cover sheet.
2. Provide a transcript from your self-tests. Be sure to include the transcript from running selfTest in the IntStack class.
3. Provide a printout of any files you have modified (see approach below).
4. Be prepared to demo in lab.

Suggested implementation approach:

(The files contain some more specific instructions.)

1. Implement and test Stack.
2. Implement and test IntStack.
3. Implement and test RoomStack.
4. Implement and test your modifications to Room.