The code for this part of the lecture can be found here.
Let's recap on while loops. Here are the 5 steps for translating an accumulator style method implementation into a method implementation using a while loop.
return acc;
.
tr.isEmpty()
becomes !tr.isEmpty().
tr = tr.getRest().
Mutation!
| Accumulator | While Loop |
|---|---|
// Concat all Student names in tr into one big string
public String bigString(Traversal<Student> tr) {
return bigStringAcc(tr, "");
}
// acc = Big string with all student names seen thus far
private String bigStringAcc(Traversal<Student> tr, String acc){
if (tr.isEmpty())
return acc;
else
return bigStringAcc(tr.getRest(), updateBigStringAcc(tr.getFirst(), acc));
}
private String updateBigStringAcc(Student s, String acc){
return acc.concat(s.name);
}
|
public String bigStringWhile(Traversal<Student> tr){
String acc= " "; // Base Value
while(!tr.isEmpty()){
acc = updateBigStringAcc(tr.getFirst(), acc);
tr = tr.getRest();
}
return acc;
}
|
Java also provides for loops. What are the different parts that make up a for loop.
for(initializer;test;increment-statement){
for-block
}
A for loop has four parts.
true.
So how does for loop work? When program execution reaches a
for loop we
true then
false then jump to the first statement after the
end of for-block.
Time for an example. Let's re-implement bigString using a for loop instead of a while loop.
public String bigStringFor(Traversal<Student> tr){
String acc= " "; // Base Value
for( ; !tr.isEmpty(); tr = tr.getRest()){
acc = updateBigStringAcc(tr.getFirst(), acc);
}
return acc;
}
As in the case of while loops, we first create a
local variable to hold the value of our accumulator. We initialize
our accumulator to its base value. In this case our initializer is
empty. Our for test is the same as the test used for in our while loop
implementation. Our increment-statement advances our traversal. This
statement is the last statement inside the while-block in our while
loop implementation. Our for-block updates our accumulator using the
same method as before.
Let's make another example. Let's design a method that has the same purpose statement as bigString but instead of consuming a Traversal it consumes an ArrayList. We will design this function twice, once using a for loop and once using a while loop.
| For Loop | While Loop |
|---|---|
public String bigStringForAL (ArrayList<Student> al) {
String acc = " "; // Base Value
for (int index = this.first; 0 <= index && index < al.size(); index = index + 1){
acc = updateBigStringAcc(al.get(index), acc);
}
return acc;
}
|
public String bigStringWhileAL (ArrayList<Student> al) {
String acc = " "; // Base Value
int index = this.first;
while( 0 <= index && index < al.size()){
acc = updateBigStringAcc(al.get(index), acc);
index = index + 1;
}
return acc;
}
|
In both implementations above we use index for the current
position we are currently processing in our ArrayList. The
tests for both our for loop and our while
loop implementation check that index is between
the bounds of our ArrayList, i.e., between 0 and
al.size(). Since we start index at 0 and we
increment by one after each iteration, we are guaranteed that we will
walk over the whole ArrayList from start to end.
Selection sort is a sorting algorithm that we will use as a more elaborate example that uses loops. Selection sort begins with an unsorted list of elements. We mark a position on the list splitting the list into two sublists; one sorted sublist and the remaining unsorted list. We start by setting our marker to the first position. This gives us two sublists. The first sublist starts at position 0 and ends at position 0, i.e., it is empty. The second sublist starts at position 0 and ends at the last position of the list. We then find the minimum value in our unsorted sublist and return its index. We swap the first element of our unsorted list with the minimum element we just found and increase our mark position by one. We repeat this process until we exhaust our unsorted sublist.
Let's make an example and walk through the steps. The symbol
^ denotes the mark that splits the list into the sorted
sublist (left) and the unsorted sublist (right).
findMinLoc(0,9) -> 8 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |5|2|7|3|8|9|6|4|1|9|
| +-------------------+
| ^
|
swap(8,0) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|7|3|8|9|6|4|5|9|
| +-------------------+
| ^
findMinLoc(1,9) -> 1 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|7|3|8|9|6|4|5|9|
| +-------------------+
| ^
swap(1,1) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|7|3|8|9|6|4|5|9|
| +-------------------+
| ^
findMinLoc(2,9) -> 3 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|7|3|8|9|6|4|5|9|
| +-------------------+
| ^
swap(2,3) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|7|8|9|6|4|5|9|
| +-------------------+
| ^
findMinLoc(3,9) -> 7 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|7|8|9|6|4|5|9|
| +-------------------+
| ^
swap(3,7) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|8|9|6|7|5|9|
| +-------------------+
| ^
findMinLoc(4,9) -> 8 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|8|9|6|7|5|9|
| +-------------------+
| ^
swap(4,8) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|9|6|7|8|9|
| +-------------------+
| ^
findMinLoc(5,9) -> 6 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|9|6|7|8|9|
| +-------------------+
| ^
swap(5,6) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|9|7|8|9|
| +-------------------+
| ^
findMinLoc(6,9) -> 7 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|9|7|8|9|
| +-------------------+
| ^
swap(6,7) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|7|9|8|9|
| +-------------------+
| ^
findMinLoc(7,9) -> 8 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|7|9|8|9|
| +-------------------+
| ^
swap(7,8) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|7|8|9|9|
| +-------------------+
| ^
findMinLoc(8,9) -> 9 | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|7|8|9|9|
| +-------------------+
| ^
swap(8,9) | index : 0 1 2 3 4 5 6 7 8 9
| +-------------------+
| |1|2|3|4|5|6|7|8|9|9|
| +-------------------+
^