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

Goals

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.

Background

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:

• the region is moved to the top of the stack;
• if the mouse was clicked on one or more squares in the region, all those squares are removed from the region;
• otherwise, a square centered at the mouse click is added to the region.

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.)

Problem

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 :

• add , which adds a region to the top of the stack;
• handleClick , which, given the x and y coordinates of a mouse click, processes the click as described above; and
• regions , which returns a bottom-to-top iterator of regions from the stack.

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

• add , which adds a square to the list;
• handleClick , which, given the x and y coordinates of a mouse click, either removes all squares that contain the given point from the list and returns true , or returns false if no squares contain the given point; and
• elements , which returns an iterator of squares from the list.

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:

• r sets the Region switch;
• s sets the Square switch;
• w sets the CS61BWindow switch;
• k (for "stack") sets the RegionStack switch;
• l (for "list") sets the SquareList switch.

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:

• Estimates of the running time of the operations performed on your RegionStack and SquareList objects. Assume for these estimates that the CS61BWindow contains n regions. Then give, and briefly justify, a big-Oh estimate for the time your program requires for each of the following:
• finding the clicked-on region, assuming it's the kth region down from the top of the stack;
• moving that region to the top of the stack;
• determining which squares were clicked on, assuming that there are m< squares in the region;
• creating an m+1-st square for the region;
• removing j clicked-on squares from among the m in the region.

The documentation for the LinkedList class notes that "all of the operations perform as could be expected for a doubly-linked list." You may assume that a LinkedList object stores pointers to both ends of the list.

• An annotated listing of your HW4Tester file, indicating for each test what evidence it provides for the correctness of your program. An example annotation would be something like "deleting from start of list" or "adding a square to an empty list".