Lab 9
Goals: The goals of this lab is to practice using the Java loop control statements and learn how to work with Iterators.
The first section of the lab are the lecture notes and describe the code that is given to you in the file LoopAlgorithms.java. Before you start reading the lecture notes, create a new project import the file LoopAlgorithms.java.
For, For-Each, and While loop control in Java
Java provides several loop control statements. These are language constructs that make it possible to repeat some sequence of stetements some specified number of times, or while some condition is met. Last week we preacticed teh two variants of a for loop control, the counted for loop and the for-each loop.
We illustrate the behavior and use of the loop controls on the following problem:
Determine whether the given ArrayList of Strings contains the given String.
Counted for loop variant
Here is a solution using the counted for loop control:
// find whether the given ArrayList contains the given String |
boolean containsFor(ArrayList<String> slist, String s) { |
for (int index = 0; index < slist.size(); index = index + 1) { |
if (s.equals(slist.get(index))) { |
return true; |
} |
} |
return false; |
} |
The index starts at 0 and keeps increasing until it reaches the size of the given ArrayList. Notice, that we can exit the method and return the result at any time inside of the method. That means we do not have to set up a local variable that starts with the base value and is updated inside of the loop. If we go through the whole loop without finding the given String, we know we should return false.
For-each loop variant
The solution using the for-each loop control is similar:
// find whether the given ArrayList contains the given String |
boolean containsForEach(ArrayList<String> slist, String s) { |
for (String sx : slist) { |
if (s.equals(sx)) { |
return true; |
} |
} |
return false; |
} |
The only difference is in how the individual elments of the ArrayList are generated.
While loop variant
The while loop control often results in a nicer code, but requires that the initialization of the loop controls be done manually before the loos itself, and that within the loop there is some statement that modifies the continuation condition. Otherwise, the loop may never terminate. It is easy to omit this as the compiler has no way of noticing that a loop advance statement is missing.
Here is the solution that uses the while loop control:
// find whether the given ArrayList contains the given String |
boolean containsWhile(ArrayList<String> slist, String s) { |
int index = 0; // initialize the index |
while(index < slist.size()) { |
if (s.equals(slist.get(index))) { |
return true; |
} |
index = index + 1; // advance the index |
} |
return false; |
} |
Understanding Iterators
Please, read the lecture on loops for a detailed explanation of the Iterator and Iterable interface and their uses.
Here is the code that uses these interfaces:
// find whether the given ArrayList contains the given String |
boolean containsIterator(Iterable<String> slist, String s) { |
Iterator<String> iter = slist.iterator(); |
while (iter.hasNext()) { |
if (s.equals(iter.next())) { |
return true; |
} |
} |
return false; |
} |
Notice that we consume any Iterable data set, i.e. an instance of a class that implements the method
Iterator<T> iterator();
Problem 1: Loop Practice
Design the method that will consume an ArrayList<String> and two Strings and replace every occurrence of the first String wiht the second one.
Do this using every loop control you think may work.
Design the method that will produce from the given ArrayList<String> a new ArrayList<String> that contains all elements of the original one, but in the reverse order.
Design the method that will produce from the given ArrayList<String> a new ArrayList<String> that contains all elements of the original one except those that are equal to the given String.
Problem 2: Insertion Sort
The Insertion Sort algorithm inserts each new item from the given collection of data into a list that is already sorted. You are familiar with the version of this algorithm implemented in the functional (immutable) style.
We can implement the same idea mutating in place the given ArrayList, making small changes until the whole ArrayList is sorted. (The selection sort you have just worked on is also an in-place algorithm.)
Assume that the ArrayList has a part at the low end alrady sorted, and the rest still needs to be sorted:
>.. sorted .......< >.. unsorted .....< |
+---+---+---+---+---+----+---+---+---+---+ |
index: | 0 | 1 | 2 | 3 | 4 || 5 | 6 | 7 | 8 | 9 | |
+---+---+---+---+---+----+---+---+---+---+ |
value: | d | h | m | p | w || t | k | b | u | g | |
+---+---+---+---+---+----+---+---+---+---+ |
To do:
Design the method insert that will insert the next element of the given partially sorted ArrayList<T> into the sorted lower half. The method consumes the ArrayList<T>, the index of the first element in the unsorted part, (for the example above it would be $5$, and it traverses over the list down to the beginning, moving the out-of-order items to the right. The method also consumes the Comparator<T> that defines the ordering to be used in the insertion.
After the execution of this method the ArrayList would be:
>.. sorted ...........< >... unsorted..< |
+---+---+---+---+---+---+----+---+---+---+ |
index: | 0 | 1 | 2 | 3 | 4 | 5 || 6 | 7 | 8 | 9 | |
+---+---+---+---+---+---+-=--+---+---+---+ |
value: | d | h | m | p | t | w || k | b | u | g | |
+---+---+---+---+---+---+----+---+---+---+ |
After another invocation of the insert methods it would be:
>.. sorted ...............< >.unsorted.< |
+---+---+---+---+---+---+---+----+---+---+ |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 || 7 | 8 | 9 | |
+---+---+---+---+---+---+-=-+----+---+---+ |
value: | d | h | k | m | p | t | w || b | u | g | |
+---+---+---+---+---+---+---+----+---+---+ |
The main loop of the insertion sort starts with the entire list being unsorted. It invokes the insert method with index $1$, then $2$, and so on, the last time with index list.size() - 1.
To do:
Design the method insertionSort that consumes an unsorted ArrayList<T> and a Comparator<T> and mutates the list into one sorted in the order defined by the given Comparator.
Note: The main loop method described above should be just a helper method for the insertionSort method.
Problem 3: Merge
Design the mehtod merge that consumes two sorted ArrayList<T>s and a Comparator<T> that defines their ordering and produces a new sorted ArrayList<T> that contains all items from both lists.