©2006 Felleisen, Proulx, et. al.

9  Abstracting Traversals and Algorithms.

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 Traversal design the following classes and methods:

  1. Modify the classes AListOfCitiest and its subclasses to implement the Traversal iterator.

  2. In the class Algorithms design the method buildList that consumes an Traversal 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 InGuiTraversal, InConsoleTraversal and InFileBufferedTraversal iterators to provide the sources of data.

  4. Design the methods andMap and filter in the Algorithms class.

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

    • produce a list of all cities in a given state

    • find out whether there are any cities in a given state in some list of cities

    • are all cities in some list in a given state

    • is there a city with the given name in this list

    • produce a list of all cities with the given name from some list of cities

    • do all cities in some list have the given name

  6. Design insertionSort in the Algorithms class that consumes a Traversal and a Comparator.

  7. In the Examples class include the following additional tests for the insertionSort methods:

    • sort the list of cities by latitude

    • sort the list of cities by city and state

    • sort the list of cities by state and city

    Remember, you need to design a Comparator for each case.

9.2  Problem

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

Read the code for the class TraversalTestHarness. 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: Understanding Equality of Lists.

9.3  Problem

The goal here is to understand the difficulties in making copies of lists and comparing them for equality.

The file CopyTests.java defines three different ways of copying lists of cities.

9.4  Writing Problem

Writing assignments are separate from the rest of the assignment for the week. You should work on this assignment alone, and submit your work individually on the due date for the rest of the homework. The answer should be about two paragraphs long - not to exceed half a page or 300 words.

Look at the last problem in this homework. Think of when each type of copying of lists is appropriate. Describe briefly the scenaria where each of the copying would be appropriate and why. Solution

Last modified: Wednesday, March 15th, 2006 8:36:59am