Lab 8

Goals: The goals of this lab is to learn how to implement methods that process a collection of data using the Java loop control statements.

In the second part of this lab we will learn to implement an in-place sorting algorithm for ArrayList data structure defined in the Java Collections Framework library.

The first three sections of the lab are the lecture notes for the Wednesday lecture and describe the code that is given to you in the file Loops.java.

All files you will need for this lab are in Lab8.zip. Before you start reading the lecture notes, create a new project will all files from this folder and open the file Loops.java.

The anatomy of a loop

We have seen a number of loop functions in DrRacket. Let us recall one of them, the map function.

We show not only the contract, purpose, and header for this function, but include its implementation (as we would get by following the design recipe.

The result for the empty case is an empty list, and the function keeps building the result by adding to the list the value we get from applying the given function to each element of the given list.

So, to design a loop method we need to be able to generate each element of the given list, one at a time, we need to define the value produced in the base case, and define how every new element of the list contributes to or (updates) the accumulated result.

The Java for-each loop

In Java we start by defining a more concrete example: a method that produces the list of lengths of the Strings in the given list of Strings, and a method that produces the list of first letters of all Strings in the given list of Strings (and we assume all Strings in the given list have length at least one).

Here is the purpose statement and header for the first method:

Note: We specify the ArrayList as a list of Integer not int. When Java introduced the parametrized types, it added new classes to represent the objects of the primitive type (with a few methods for each), and an automatic conversion between the instance of this wrapper class and it corresponding primitive type value. So there is a class Double, class Boolean, and, of course, a class Integer.

Java does the conversion between the primitive type and the wrapper class instances automatically, and so we can write slist.add(5) instead of slist.add(new Integer(5)).

We start with creating the accumulator that at the beginning will represent the base case value, and return the accumulator value at the end:

To generate all elements of the ArrayList one at a time, in the order of increasing indices we use the Java for-each statement:

This statement works for any ArrayList as follows. After the for inside the parentheses we define the variable that will represent each element of the ArrayList. We specify its type – it must be the same as the type of elements that the ArrayList contains. We follow the varible definition by a colon : and the name of the variable that represents the ArrayList. The body of the for-each loop statement, enclosed in the curly braces {} is invoked once for each element of the specified ArrayList and can contain any statements. The complete method definition would then be

For the second example we produce a list of Strings that are the first first characters of each of the Strings in the original ArrayList:

The file Loops.java shows you how to define tests for these two methods.

The code in the file also show you how we can abstract over these two methods so that the map method aslo consumes a function object:

We first define the interface String2T<T> that defines the method apply that consumes an element of the type String and is parametrized over the type of value it produces.

The two classes that implement our two desired update functions will then be:

We can now pass an instance of the type String2T<T> to our map method and use its apply method to process each element of the ArrayList in the body of our for-each loop:

There is something new in the definition of this method. It starts with <T>. Try removing it in your code. Java will tell you that you have not defined a class T. Indeed, inside of the class Algorithms there is no mention of the type T. If we wrote the same method and substituted Book or String for every occurrence of T, it would be a perfectly well-defined method. How is Java to know that T is not a name of a class, but a type parameter? The <T> before the method definition is there to notify Java that the letter T denotes a type parameter, not a name of a data type.

The code provides complete tests. To define the tests we defined a method init for each ArrayList (the given one and the one we expect the method to produce) that initializes its values. The first line in these init methods invokes the clear() method on its ArrayList. This deletes all elements that may have been already in the ArrayList, making sure we work with clean data every time.

Read the tests and run the code.

The counted for loop

There is another way this loop can be implemented. Befre the for-each loop aas added to the language, the programmers had to generate the data elements by specifying the index of each element and invoking the get method for each of them as follows:

The loop construct used here is known as counted loop. The loop is controlled by three statements inside the parentheses after the word for:

• the initialization statement that is executed before the loop is first run.

  Here we have int index = 0;

• the continuation condition – a boolean expression that is evaluated before the loops body is executed. If it evaluates to true the loop body is run, otherwise, the program conintues with the statement that follows the loop body.

  Here we have index < slist.size(); indicating that we stop when the index reaches the value of the size of the given ArrayList.

• the loop advance statement – that is executed after the completion of each iteration, each execution of the loop body.

  Here we have index = index + 1 which increments the value of the index after the loop body is run.

We see that every time the loop body is performed, the index value keeps increasing until all elements of the ArrayList have been processed.

Run the code, examine the way the tests are designed, make sure all parts make sense.

Designing loop methods - Problem 1

• Design a method mapBookTitle that consumes an ArrayList of Books and produces an ArrayList of Strings that are the titles of the books in the given list. Use the for-each loop control.

• Design the method mapBookAuthor that consumes an ArrayList of Books and produces an ArrayList Strings that are the names of the authors of the books in the given list. Use the for-each loop control.

• Design the method mapBookPrice that consumes an ArrayList of Books and produces an ArrayList Integers that are the prices of the authors of the books in the given list. Use the for-each loop control.

• Define the interface Book2T parametrized over the type T that will represent the function apply that consumes a Book and produces a value of teh type T

• Define three classes that implement this inerface by producing the title, author, price of the given book respectively.

• Now design an abstraction, a method mapBookT that will replace all three of these methods. Add the tests that use the new method, but consume and produce the same data.

• Desing the method mapBookTfor that does the same thing as mapBookT but uses the counted for loop control.

Designing loop methods - Problem 2

• Design the method filterShort that will produce an ArrayList of all short Strings in the given ArrayList of Strings.

  Short strings have three or fewer characters.

• Design the method filterAs that will produce an ArrayList of all Strings in the given ArrayList of Strings that start with the letter a.

• Design an abstraction, a method filterStrings that will produce an ArrayList of all Strings in the given ArrayList of Strings that satisfy the predicate given as an instance of the type ISelect.

  The interface ISelect is already defined for you.

  Make sure you rerun all tests you have designed earlier.

Selection sort

With the ability to access any element of an ArrayList and change its value at will, we can design a sorting algorithm that mutates the given ArrayList into a sorted order.

For this example we will use an ArrayList of Strings and sort it in the lexicographical order.

Selection sort is one of the familiar sorting algorithms. It is well suited for the situations where you are trying to minimize the moving of the data from one location to another.

Suppose you have an ArrayList of data of size s in which the first k elements are sorted, and every item in the unsorted part is greater than the largest item in the sorted part.

You would like to sort the rest of the ArrayList. We know how to swap two items in the ArrayList. So, if we can find the location of the smallest item in the unsorted part and swap it with the first item in the unsorted part, the sorted part will be one item bigger, and the unsorted part will be one item smaller.

If we repeat this until the last item is swapped into its correct position, we will have finished sorting the remainder of the ArrayList.

Here is an example:

Swap elements at locations 4 and 6:

Swap elements at locations 5 and 7:

Swap elements at locations 6 and 6:

What about the case when none of the ArrayList is sorted? Well, then the sorted part has size 0, and the unsorted part starts at the index 0.

Designing loop methods - Problem 3

• In the Algorithms class design the helper method findMinLoc that finds the location of the smallest item in the unsorted part of the given ArrayList of Strings. The order is determined lexicographically using the method string1.compareTo(string2) that produces

  • an int value <0 if string1 comes before string2

  • 0 if the two strings are equal

  • an int value >0 if string1 comes after string1

  Use the counted for loop. Think carefully through the first step of the design recipe, to make sure you know what the method consumes and what does it produce.

• In the Algorithms class design the method selectionSortLex that implements the selection sort algorithm.

• Java Collections Framework library defines an interface

  interface Comparator<T> {

  public int compare(T t1, T t2);

  }

  where the method produces

  • an int value <0 if t1 comes before t2

  • 0 if the two strings are equal

  • an int value >0 if t2 comes after t1

  Design two classes StringLexComp and StringLengthComp that implement this interface by comparing the Strings first lexicographically, then by length.

• Design a new method selectionSort that consumes an ArrayList<String> to be sorted, as well as an instance of Comparator<String> and mutates the given list to sorted order specified by the given Comparator.

  Rerun the tests you had for the first sorting method.