The anatomy of a loop
The Java for-each loop
The counted for loop
Designing loop methods - Problem 1
Designing loop methods - Problem 2
Selection sort
Designing loop methods - Problem 3
5.3.5

Lab 9

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 Lab9.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.

;; produce a list created by applying the given function

;; to every element of the given list

;;

;; map: (f:X->Y) [Listof X] -> [Listof Y]

(define (map f alox)

   (cond

      [(empty? alox) empty]

      [(cons? alox) (cons (f (first alox))

                          (map f (rest alox)))]))

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:

/**

 * Produce a list of the lengths of all <code>String</code>s

 * from the given list of <code>String<.code>s.

 * *param slist the given list of <code>String<.code>s

 * *return a list of the lengths of all <code>String</code>

 */

ArrayList<Integer> mapLength(ArrayList<String> slist) {

 

}

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:

/**

 * Produce a list of the lengths of all <code>String</code>s

 * from the given list of <code>String<.code>s.

 * *param slist the given list of <code>String<.code>s

 * *return a list of the lengths of all <code>String</code>

 */

ArrayList<Integer> mapLength(ArrayList<String> slist) {

    // initialize the accumulator with the base value

    ArrayList<Integer> result = new ArrayList<Integer>();

 

    // here we need to loop through all elements

    // and update the accumulator

 

    // return the accumulated result

    return result;

}

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

for (String s : slist) {

    result.add(s.length();

}

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

/**

 * Produce a list of the lengths of all <code>String</code>s

 * from the given list of <code>String<.code>s.

 * *param slist the given list of <code>String<.code>s

 * *return a list of the lengths of all <code>String</code>

 */

ArrayList<Integer> mapLength(ArrayList<String> slist) {

    // initialize the accumulator with the base value

    ArrayList<Integer> result = new ArrayList<Integer>();

 

    // add the length of every element to the accumulator

    for (String s : slist) {

        result.add(s.length());

    }

 

    // return the accumulated result

    return result;

}

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:

/**

 * Produce a list of the first letters of all <code>String</code>s

 * from the given list of <code>String<.code>s.

 * *param slist the given list of <code>String<.code>s

 * *return a list of the first letters of all <code>String</code>

 */

ArrayList<String> mapFirst(ArrayList<String> slist) {

    // initialize the accumulator with the base value

    ArrayList<String> result = new ArrayList<String>();

 

    // add the first letter of every element to the accumulator

    for (String s : slist) {

        result.add(s.substring(0, 1));

    }

 

    // return the accumulated result

    return result;

}

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.

// to represent a function that consumes a String

// and produces a value of the type T

interface String2T<T> {

    public T apply(String s);

}

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

//to represent a function that produces the length

//of the given String

class StringLength implements String2T<Integer> {

    public Integer apply(String s) {

        return s.length();

    }

}

 

// to represent a function that produces the first character

// of the given String

class StringFirst implements String2T<String> {

    public String apply(String s) {

        return s.substring(0, 1);

    }

}

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:

/**

 * Produce a list by applying the given function to all

 * <code>String</code>s from the given list of <code>String<.code>s.

 * *param slist the given list of <code>String<.code>s

 * *param update the function object that defines the update method

 * *return a list of the first letters of all <code>String</code>

 */

<T> ArrayList<T> mapT(ArrayList<String> slist, String2T<T> update) {

    // initialize the accumulator with the base value

    ArrayList<T> result = new ArrayList<T>();

 

    // apply the update function to every element of the given list

    // add the result to the accumulator

    for (String s : slist) {

        result.add(update.apply(s));

    }

 

    // return the accumulated result

    return result;

}

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:

/**

 * Produce a list by applying the given function to all

 * <code>String</code>s from the given list of <code>String<.code>s.

 * *param slist the given list of <code>String<.code>s

 * *param update the function object that defines the update method

 * *return a list of the first letters of all <code>String</code>

 */

<T> ArrayList<T> mapFor(ArrayList<String> slist, String2T<T> update) {

    // initialize the accumulator with the base value

    ArrayList<T> result = new ArrayList<T>();

 

    // apply the update function to every element of the given list

    // add the result to the accumulator

    for (int index = 0; index < slist.size(); index = index + 1) {

        result.add(update.apply(slist.get(index)));

    }

 

    // return the accumulated result

    return result;

}

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

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

Designing loop methods - Problem 2

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:

 >--- sorted ------<  >---  unsorted  ------------<

+----+----+----+----++----+----+----+----+----+----+

|  0 |  1 |  2 |  3 ||  4 |  5 |  6 |  7 |  8 |  9 |

+----+----+----+----++----+----+----+----+----+----+

| 13 | 16 | 17 | 20 || 27 | 31 | 22 | 25 | 28 | 29 |

+----+----+----+----++----+----+----+----+----+----+

                                  ^

                              min unsorted

Swap elements at locations 4 and 6:

 >-------- sorted ------<  >---  unsorted  -------<

+----+----+----+----+----++----+----+----+----+----+

|  0 |  1 |  2 |  3 |  4 ||  5 |  6 |  7 |  8 |  9 |

+----+----+----+----+----++----+----+----+----+----+

| 13 | 16 | 17 | 20 | 22 || 31 | 27 | 25 | 28 | 29 |

+----+----+----+----+----++----+----+----+----+----+

                                       ^

                                  min unsorted

Swap elements at locations 5 and 7:

 >--------- sorted ----------<  >---  unsorted ---<

+----+----+----+----+----+----++----+----+----+----+

|  0 |  1 |  2 |  3 |  4 |  5 ||  6 |  7 |  8 |  9 |

+----+----+----+----+----+----++----+----+----+----+

| 13 | 16 | 17 | 20 | 22 | 25 || 27 | 31 | 28 | 29 |

+----+----+----+----+----+----++----+----+----+----+

                                  ^

                              min unsorted

Swap elements at locations 6 and 6:

 >----------- sorted -------------<  >- unsorted -<

+----+----+----+----+----+----+----++----+----+----+

|  0 |  1 |  2 |  3 |  4 |  5 |  6 ||  7 |  8 |  9 |

+----+----+----+----+----+----+----++----+----+----+

| 13 | 16 | 17 | 20 | 22 | 25 | 27 || 31 | 28 | 29 |

+----+----+----+----+----+----+----++----+----+----+

                                            ^

                                       min unsorted

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