©2005 Felleisen, Proulx, et. al.

9  Abstracting Traversals; Using Runtime Exceptions; Introducing Collections

In this problem set you will work with several predefined classes that represent cities and lists of cities, as well as files that provide infrastructure for the tests and for dealing with user input.

The focus of your work is on learning to use abstractions in building reusable program components.

Part 1: Iterators, Loops, User input

Start by downloading the file HW9part1.zip and making an Eclipse project HW9part1 that contains these files. Add jpt.jar as a Variable to your project. Run the project, to make sure you have all pieces in place. The main method is in the class Interactions.

The classes you will work with are the following:

9.1  Problem

For the given classes City, AListOfCities (and its subclasses), and the interface IRange design the following classes and methods:

  1. class ListRange that implements the IRange iterator for the list of cities.

  2. In the class Algorithms design the method buildList that consumes an IRange iterator and produces a list of cities. In one of your tests for this method make a copy of a list of cities and compare the results. (You may need to reverse the result.)

  3. Explore the use of the method buildList in the class Interactions by using the InGuiRange, InConsoleRange and InFileRangeBuffered iterators.

  4. Design the method orMapWhile that is a variant of orMap that uses Java while statement instead of recursion. Use as a model the implementation of the filter and filterWhile methods.

  5. Add the methods andMap and andMapWhile to the Algorithms class.

  6. In the Examples class include the following additional tests for the filter, orMap, and andMap methods:

9.2  Problem

Design the class ArrayListRange to provide a traversal of the data represented by Java ArrayList object.

Re-run the tests from the Part 5 of the previous problem using data stored in an ArrayList.

9.3  Problem

Design a new variant of the class ArrayListRange that will allow the user to decide at construction time what part of the given ArrayList should the iterator traverse. So, for example, you may choose to only look at the consecutive elements of the ArrayList starting at index 5 and going up to index 14.

Re-run the tests from the Part 5 of the previous problem using data stored in an ArrayList.

9.4  Problem

The goal here is to start thinking about systematic design of tests.

Read the code for the class SimpleTestHarness. Design a test suite for it.

Write a pragraph or two of documentation that describes what kinds of tests can/cannot be done using this test harness.

Part 2

In this part you will implement several sorting algorithms possibly using the iterators from the first part for the traversal. Use function objects that implement Java Comparator interface to determine the ordering of two objects.

9.5  Problem

Implement the insertion sort in the class Algorithms and test it on both a list of cities and an ArrayList that represents cities.

9.6  Problem

Implement the quick sort in the class Algorithms and test it on both a list of cities and an ArrayList that represents cities.

9.7  Problem

The selections sort works as follows. Select the smallest item in the list and remember its position. Swap the first item with the smallest one you found. The first item is now in the correct position. Repeat these steps for the remaining part of the list, until all items move into their correct places.

Part 3

9.8  Problem

We have the following data definitions:

A Reply consists of

A CrystalBall consists of an ArrayList of Reply

Make a new project named Eliza, import the files from eliza.zip, and your iterator classes for ArrayList

Add the jpt.jar variable to your project as well.

Now design the following methods

Make an example of a CrystalBall object in the Interactions class.

In the Interactions class design a method that forever requests a String s from the user and displays the answer given by the findReply method fo the CrystalBall class. When the user aborts the input response, the method prints Goodbye.

Last modified: Friday, March 11th, 2005
HTML conversion by TeX2page 2004-09-11