©2009 Felleisen, Proulx, et. al.

10  Loops; Sorting

Goals

In the first part of the lab you will learn how to convert recursive loops to imperative (mutating) loops using either the Java while statement or the Java for statement to implement the imperative loops.

In the second part we will look at how we can leverage the direct access to the items within the data set to implement a new kind of sorting algorithm.

For this lab download the files in Lab10-Sp2009.zip. The folder contains the following files:

• The file Balloon.java — our sample data class

• The file ISelect.java — the interface for a generic predicate method

• The files RedBallon and SmallBalloon that implement the ISelect interface for the Balloon data.

• The files IList.java, MTList.java, and ConsList.java that define a generic cons-list that implements the Traversal interface.

• The file ArrListTraversal.java shows how we can define a Traversal wrapper for the ArrayList class.

• The Algorithms.java file shows an implementation of several algorithms that consume data generated by a Traversal iterator and illustrates a number of ways in which loops can be implemented in Java.

• The Examples.java file that defines examples of all data and defines all tests.

Create a new Project Lab10 and import into it all files from the zip file. Import the tester.jar and colors.jar.

10.1  Converting Recursive Loops into Imperative while Loops

The goal of this part of the lab is to make sure you know how to implement a traversal over data within an ArrayList using Java while and for loops. Make sure you understand the role of each part of the loop method definition: BASE VALUE, CONTINUATION-PREDICATE, CURRENT, ADVANCE, UPDATE, and know how to construct both the while loop and the for loop.

• Work with the Lab handout. The first page gives you an overview of all classes and interfaces and the relationship between them. We introduce a dotted line from a method that consumes an instance of some class to that class.

• Read first the code for the contains method and for the countSuch method in the Algorithms class. These have been designed in the classical HtDP style.

• We will look together at the next two examples of orMap in the Algorithms class.

  We first write down the template for the case we already know — the one where the loop uses the Traversal iterator. As we have done in class, we start by converting the recursive method into a form that uses the accumulator to keep track of the knowledge we already have, and passes that information to the next recursive invocation.

  Read carefully the Template Analysis and make sure you understand the meaning of all parts.