CSE 142 Spring 2002

Homework #4

Lists 'n Loops

Due: Electronically, 11:00pm, Sun., May 5;
written report due in lecture, Monday May 6.

Example Solution: http://students.washington.edu/wjr/solution/
(Note that there will be some differences in appearance, required to embed this solution in a web page.)

Purpose

The purpose of this assignment is to gain experience with new control-flow constructs, in particular loops, and basic collection classes, in particular ArrayLists. This assignment is a little different from the previous ones in that it consists of several short problems. The intent is to give you a chance to drill these basic ideas so they become part of your repertoire of programming skills.

Getting Started - The Framework

Download the files DataSourcee.java and HW4.java using one of these methods:

HW4.jar
A tried and untrue method (from HW3).
HW4.zip
Also tried (also HW3) and probably truer version.
Download each file separately. (In Internet Explorer, right-click on each link and select "Save Target As..." When the File Browser dialog comes up asking you where you want to save it, at the very bottom change the "Save As Type" field from "Text" to "All Files". If you don't, IE will append ".txt" to the file's name when it saves it (which isn't much of a problem - you can just edit its name once it has been downloaded).)
- DataSource.java
- HW4.java

The DataSource class creates test data for you to process, and displays a graphical representation of the that data and the results generated by your code. You should not need to modify (or even read) the code in this class.

HW4.java is the skeleton (beginning) of your solution. You will add your code to this file. This class contains a main() method that you can use to test your code.

How it Works

When a HW4 object is created, it creates a DataSource object, and then just sits there. To run an exercise, the HW4 object's runExercise method must be called. (More on that below.)

When an instance of class DataSource is constructed, it creates two GWindows. One is used to display the data the DataSource object will produce to run the exercises (below). The other GWindow is used to display the Rectangles selected by your code for those exercises. When the DataSource object is constructed, the two GWindows appear at exactly the same place on the screen - there is no GWindow interface to set their initial positions, so they appear one on top of the other. Drag the top one so you can see both of them.

Class DataSource contains four key methods that are used in each exercise:

public void startExercise(int testNum)
Causes the DataSource to initialize itself properly for exercise testNum (using the numbers given below). This method should be invoked before beginning each exercise.
public HashSet getHashSet()
Call this to get a HashSet collection containing data for exercises involving HashSets. Returns null if the exercise named in the last startExercise invocation does not use a HashSet.
public ArrayList getDataList()
Returns an ArrayList containing the data for the current exercise. Returns null if the current exercise does not use ArrayList data.
public void registerResult(ArrayList resultList)
Each exercise requires you to generate an ArrayList containing some or all of the items from the original list (except exercise 0, which always returns an empty ArrayList). After executing the code to produce the result ArrayList, call this method of the DataSource object with your result as a parameter. The DataSource will display a graphical representation of resultList in the second GWindow. For example, if the exercise asks you to return a list consisting only of the blue rectangles from the original list, after calling registerResult with the result, you should see a picture that contains only the blue rectangles from the original picture - assuming your code works properly.

Running the Code

Well, as usual, there are at least two ways to run the code.

Jeva and BlueJ
Create a HW4 object. It's constructor will create a DataSource object for you. Now invoke the runExercise method, passing an integer that is the exercise you want to run. (Note that a message will appear saying that the exercise has been run, but that it may well appear behind other windows on the screen, and so not be visible. You cannot continue until you click the OK button, so find it and do so.)
Command line, Jeva, and BlueJ
If you invoke the main() method of class HW4 it will create a HW4 object for you, and then enter a loop asking you to type exercise numbers to be run. To invoke from the command line (i.e., in a Command Prompt window), type "java HW4". To invoke in BlueJ, right-click on the HW4 icon, select main and then accept the default parameter ("{}"). To invoke in Jeva, first type (without the outer quotes) "String args[] = {""};" and then "HW4.main(args);".

Note that exercise 0 (which does virtually nothing) is already implemented, but none of the others are - that's the assignment.

Exercises

Here are the (numbered) exercises you should solve by adding code to the HW4 class:

A trivial exercise, already implemented in the skeleton code as an example showing how to register your result ArrayList with the DataSource object, that simply registers a (new) empty ArrayList as the result (without even looking at the data).

For exercises 1 to 4, use an Iterator object and either a while or a do...while to access each of the Rectangles in the HashSet returned from DataSource.getDataSet(). You may assume that all elements in the HashSet are valid Rectangles (i.e., are not null). (Remember, your job is to create a new ArrayList that has the result rectangles (if any) for each exercise entered into it, and then to call DataSource.registerResult() with that ArrayList.)

Produce an ArrayList that is a copy of the original HashSet, i.e., contains references to all the Rectangles contained in the original HashSet.
Produce an ArrayList containing all of the blue Rectangles in the original HashSet. If there are no blue Rectangles in the original set, the result should be an empty ArrayList (i.e., one containing no elements, not null).
Produce an ArrayList containing the Rectangle with the largest area (width*height) from the original HashSet. If there is more than one Rectangle with largest area, put only the last such one encountered in the result ArrayList.
Return an ArrayList containing the first red Rectangle you encounter in the original HashSet. If there are no red Rectangles in the original HashSet, return an empty ArrayList. Note that because a HashSet does not guarantee any particular order, you probably won't end up selecting the first red rectangle from the data window (and won't even select the same red rectangle if you run this exercise twice on the same data). You should always return a single, red rectangle, however.

The next four exercises use data from the ArrayList obtained from DataSource.getDataList(). You should use a for loop and ArrayList.get() to directly access the elements of the data ArrayList. (Do not use an Iterator object.) You may assume that all elements of the ArrayList refer to actual Rectangles (i.e., are not null).

Produce a result ArrayList that contains references to all of the Rectangles in the data ArrayList
Return an ArrayList containing the first red Rectangle from the original ArrayList. If there are no red Rectangles in the original ArrayList, return an empty ArrayList.
Return an ArrayList containing all of the Rectangles whose indices (positions) in the original ArrayList are odd (1, 3, 5, ...)
Return an ArrayList containing all of the Rectangles whose indices (positions) in the original ArrayList are even (0, 2, 4, ...) (Flipping between these two tests should alternate between two pictures containing half of the rectangles from the full-data picture.)

For the next two exercises, use the data in the ArrayList obtained from DataSource.getDataList(). Some of entries in the data ArrayList will refer to Rectangles and some will be null. You can use whatever sort of loop you like.

Produce an ArrayList containing references to all of the Rectangles from the original list, but none of the nulls. In other words, the result should be the same as the original list, except that any nulls in the original list should not be copied to the result.
Produce an ArrayList containing references to all of the green Rectangles in the original ArrayList. If there are no green Rectangles in the original list, the result should be an empty ArrayList (contain no Rectangles).
Modify the original ArrayList obtained from DataSource.getDataList() to remove all the nulls. You should do this in place, meaning without using any additional collection class objects besides the data ArrayList itself. Note that this is tricky: you'll be changing the elements of the ArrayList while you're going through it.

How to Proceed

This looks like a lot, but (a) each exercise is small, and (b) they are very similar to each other, so once you have one it should be quite quick to finish the others in its group (except that exercise 11 is a bit of an anomaly). Try to finish all exercises in each group before moving on to the next group. Try to finish the groups in the order given above.

Additional Documentation

Sun documentation on HashSet and ArrayList. (Find and click on them in the lower-left navigation frame.)
Javadoc documentation on HW4 and DataSource classes

Turning in the Completed Project

Turn-in form. (now available)

Written Report

In lecture on Monday, May 6, you must turn in a short (no more than one page) written report about your project. Include your name, section, homework number and date at the top. If you didn't get the program finished, describe what still does not work, and your best guess as to what is needed to fix it. Whether or not you finished it, describe the most important things you learned from this project, which could be new ideas that you have never seen before, or misconceptions that you had that the project helped you straighten out. Comments on the positives and negatives of reading versus writing code would also be appropriate.