(This assignment was prepared by Mike Clancy and Kathy Yelick for use in U.C. Berkeley's CS 61B, "Data Structures", in spring 2001.)


This assignment generalizes list processing techniques to lists of lists. It will also give you practice with the LinkedList class in the Java 2 library and familiarize you with techniques used in window managers.


The directory ~cs61b/hw/hw4 contains six files: CS61BWindow.java , Region.java , and Square.java , plus HW4Tester.java , RegionStack.fw.java , and SquareList.fw.java . ("Fw" stands for "framework".) A CS61BWindow object is a window that maintains a list of regions displayed within it. Each region in the window is rectangular. A window may contain any number of regions, and they may overlap; overlapping regions form a sort of stack, stored in a RegionStack object, as shown below.



a stack of regions

the result of clicking on the fourth region
down from the top

Regions respond to mouse clicks; the clicked-on region moves to the top of the stack, as shown in the diagram.

Each Region object may contain colored squares, stored in a SquareList object. One may draw a square in a region by clicking in the region somewhere that's not already occupied by a square. One may remove a square from a region by clicking on the square. Thus each region is associated with a list of squares to be drawn in the region.

CS61BWindow , RegionStack , Region , and Square objects draw themselves using a paint method. The CS61BWindow paint method is called when a region in the window changes or when the window is exposed by moving another window from in front of it. It ask its RegionList for regions, starting with the bottom region and ending with the top, and calls each region's paint method. Regions in turn call the paint methods of their squares. The regions in the window's stack are each drawn with a border, and filled with white ink so they aren't transparent. The squares in the region are drawn (in any order) when the region is drawn, each with a border. All squares in a region are drawn in the same color, a color associated with the region (thus different regions may be associated with different colors)

Clicking any of the mouse buttons in a region should do the following:

In either case, the window is redrawn. Clicking in the window in a position not occupied by a region should have no effect.

Squares are normally 20 pixels wide and 20 pixels high. However, they may be smaller if near the border of a region, since they do not extend beyond the region that contains them. Thus when a square is created, its dimensions are reduced if necessary to make it fit within the region. (This is an organizational flaw; a real window manager would intercept calls that draw outside a region and avoid the overflow.)


You are to provide the two collection classes RegionStack and SquareList , plus an expanded version of the HW4Tester class. RegionStack includes the a zero-argument constructor and the following public methods, all called from CS61BWindow :

SquareList includes a zero-argument constructor and the following public methods, all called from Region :

Miscellaneous requirements

You are to use the class java.util.LinkedList (not available in Java 1.1) as the underlying data structure for RegionStack and SquareList . Identifying the methods for this class will require some research on your part, an intended goal of this assignment.

You may add private data or methods to RegionStack and SquareList , but you are not to change the public interface. You are not to change the CS61BWindow , Region , or Square classes. You should add more comprehensive tests to HW4Tester.java ; calls to the CS61BWindow simulateClick method provide a way to automate the testing.

All calls to methods in the Java Abstract Window Toolkit are supplied in the framework code. Don't add any other AWT calls. (It's possible to represent the regions and squares as AWT components. Don't do this. This is a data structures course, not an AWT course.)

All classes except HW4Tester include a public static boolean variable named DEBUGGING that can be set from outside the class to turn on debugging output. HW4Tester.java contains code to set these debugging switches according to an argument typed on the java command line after the class name:

For example, the command

	java HW4Tester wkr

turns on debugging output for the CS61BWindow, RegionStack, and Region classes. The debugging switches for RegionStack and SquareList , if turned on, should cause output to be produced on System.out about any change to the stack/list.

You should include an overview comment with each class and accompany your methods with comments that describe their arguments, side effects, and pre- and postconditions.

The README file

Include in your submission a file named README. The contents of the README file should include the following: