The code for this part of the lecture can be found here.
As our running example we will use the ALT class:
import java.util.ArrayList;
class ALT<T> implements Traversal<T> { ArrayList<T> al; int
first;
public ALT(ArrayList<T> al){
this.al = al;
this.first = 0;
}
// Used inside ALT only!
private ALT(ArrayList<T> al, int first) {
this.al = al;
this.first = first;
}
// Traversal<T> methods
public T getFirst() { return al.get(this.first); }
public boolean isEmpty() { return this.first == al.size(); }
public Traversal<T> getRest() { return new ALT<T>(this.al, first + 1); }
}
We will also use the class Student to help up us write
some tests.
// to represent a student in our class
class Student {
String name;
String lab;
int ssid;
public Student(String name, String lab, int ssid){
this.name = name;
this.lab = lab;
this.ssid = ssid;
}
public String toString(){
return new String(" Name : " + this.name + ", " +
" Lab : " + this.lab + ", " +
" SSID : " + this.ssid );
}
}
And some examples to get the ball rolling. Some parts are elided here but you can see the full class definition here.
import java.util.ArrayList;
class ALTTests {
// Students
Student skotthe = new Student("Theo", "A", 1234);
Student chadwick = new Student("Bryan", "B", 3456);
Student dimvar = new Student("Dimitris", "C", 7890);
Student chrdimo = new Student("Christos", "D", 1122);
Student mthomas = new Student("Mike", "A", 3344);
// ArrayLists
ArrayList<Student> al0;
ArrayList<Student> al1;
ArrayList<Student> al2;
ArrayList<Student> al3;
ArrayList<Student> al4;
ArrayList<Student> al5;
// ALTS
ALT<Student> altMt = new ALT<Student>(al0);
ALT<Student> alt1 = new ALT<Student>(al1);
ALT<Student> alt2 = new ALT<Student>(al2);
ALT<Student> alt3 = new ALT<Student>(al3);
ALT<Student> alt4 = new ALT<Student>(al4);
ALT<Student> alt5 = new ALT<Student>(al5);
public void resetData(){
// elided
}
public static void main(String[] args){
ALTTests altt = new ALTTests();
altt.resetData();
altt.runTests();
}
public void runTests() {
resetData();
//Run
System.out.println(" ==== Testing altMt ====");
System.out.println("altMt = " + altMt.toString());
System.out.println("altMt.isEmpty = " + altMt.isEmpty());
System.out.println(" ==== Testing alt1 ====");
System.out.println("alt1 = " + alt1.toString());
System.out.println("alt1.isEmpty = " + alt1.isEmpty());
System.out.println("alt1.getFirst = " + alt1.getFirst().toString());
System.out.println("alt1.getRest = " + alt1.getRest().toString());
System.out.println(" ==== Testing alt2 ====");
System.out.println("alt2 = " + alt2.toString());
System.out.println("alt2.isEmpty = " + alt2.isEmpty());
System.out.println("alt2.getFirst = " + alt2.getFirst().toString());
System.out.println("alt2.getRest = " + alt2.getRest().toString());
System.out.println(" ==== Testing alt3 ====");
System.out.println("alt3 = " + alt3.toString());
System.out.println("alt3.isEmpty = " + alt3.isEmpty());
System.out.println("alt3.getFirst = " + alt3.getFirst().toString());
System.out.println("alt3.getRest = " + alt3.getRest().toString());
System.out.println(" ==== Testing alt4 ====");
System.out.println("alt4 = " + alt4.toString());
System.out.println("alt4.isEmpty = " + alt4.isEmpty());
System.out.println("alt4.getFirst = " + alt4.getFirst().toString());
System.out.println("alt4.getRest = " + alt4.getRest().toString());
System.out.println(" ==== Testing alt5 ====");
System.out.println("alt5 = " + alt5.toString());
System.out.println("alt5.isEmpty = " + alt5.isEmpty());
System.out.println("alt5.getFirst = " + alt5.getFirst().toString());
System.out.println("alt5.getRest = " + alt5.getRest().toString());
}
}
Lets design a method with
the name bigString that consumes a traversal of
Students and returns all the names of the students
concatenated as one big string. We want to implement this
method using accumulators.
To assist us with our implementation we'll follow our Accumulator
Template. For any method consuming a Traversal
and implemented using accumulators we can
use the following template as a guide.
<T> retType methodName(Traversal <T> tr, retType acc, ... ){
if (tr.isEmpty())
return acc;
else
return methodName(tr.getRest(),updateAcc(tr.getFirst(),acc, ... ));
}
Names in italics denote the parts of the template that vary.
The ellipses (the three dots ...)
denote extra arguments that we might need to pass to our
method. These parts will be different according to the task
your method is trying to accomplish.
Now that we have our template let's use it to develop bigString.
// 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);
}
Our bigString method consumes a Traversal
of Students and returns a string holding
all the names of students concatenated together. The
method body returns the result of our accumulator method
bigStringAcc. This means that bigStringAcc
also returns a String. We pass our traversal object
tr and the base value for our accumulator. Since
bigStringAcc has String as a return type,
our accumulator value will be of type String. This
is based on our template.
Our bigStringAcc method consumes a
Traversal of Students and an accumulator
of type String. The body of our method is identical
to our template except for the last statement. Our update method
updateBigStringAcc consumes the first element of
tr and our accumulator and returns a string. The body
of our update method simply concatenates the students name to the
current value of our accumulator.
One example is never enough. Let's define a new function orMap that will consume
a Traversal, t, and an ISelect, pick,
and produce a boolean. pick consumes an element of
Traversal and returns a boolean. orMap
logically or's the results returned by all the applications of
pick on elements of tr. We want our
implementation of orMap to be done using accumulators.
So in our ALT class we need to add the following method.
public <T> boolean orMap(Traversal<T> tr, ISelect<T> pick){
return orMapAcc(tr, pick, false);
}
orMap takes two inputs; a Traversal,<T> tr
and an ISelect,<T> pick. The body of our method
calls orMapAcc, our accumulator implementation for
orMap. We pass the traversal tr, our
functional object pick, and the base value for our
accumulator false.
How did we decide that our base value for our accumulator is
false? If we look at our template we see that the
type of the accumulator value is the same as the return type or
our method. orMapAcc must have the same return type
as orMap and orMap's return type is
boolean. Therefore, according to our template the type
of our accumulator acc should be boolean.
Now we need to design orMapAcc following our template.
// using pick walk over tr calling pick on each element or-ing the results
private <T> boolean orMapAcc(Traversal<T> tr, ISelect<T> pick, boolean acc){
if(tr.isEmpty())
return acc;
else return orMapAcc(tr.getRest(),pick,updateOrMapAcc(tr.getFirst(), pick, acc));
}
The first usage of <T>, after the modifier
private denotes that this is a generic method over
the type variable T. Our retType is
boolean as specified by orMap. We
also need to pass to our function pick. We require
pick since we need to call its select
method on each element inside tr. This is an extra
argument that we use in the place of the ellipses in our template.
The body of the method is the same except for the last statement. Our
update method is called updateOrMapAcc and
takes three arguments, the first element of our traversal
tr.getFirst(), pick, and the accumulator
acc. The update method is responsible for what needs
to be done to each element and how to combine this answer with
our accumulator.
Now we need to design updateOrMapAcc.
private <T>boolean updateOrMapAcc(T ele, ISelect<T> pick, boolean acc){
return pick.select(ele) || acc ;
}
Our update method passes the element we got from tr
to pick and combines the result with our accumulator
using a logical or. This completes our implementation, using
accumulators, for orMap.
As a last exmaple, let's define a new function filter
that will consume a Traversal, t, and an ISelect, pick,
and produce an ArrayList. pick consumes an element of
Traversal and returns a boolean. filter
excludes from the result all the elements of tr
that don't satisfy pick. We want our
implementation of filter to be done using accumulators.
So in our ALT class we need to add the following method.
public ArrayList filter(Traversal tr, ISelect pick){
return filterAcc(tr, pick,new ArrayList());
}
filter takes two inputs; a Traversal,<T> tr
and an ISelect,<T> pick. The body of our method
calls filterAcc, our accumulator implementation for
filter. We pass the traversal tr, our
functional object pick, and the base value for our
accumulator ArrayList.
How did we decide that our base value for our accumulator is
ArrayList? If we look at our template we see that the
type of the accumulator value is the same as the return type or
our method. filterAcc must have the same return type
as filter and filter's return type is
ArrayList. Therefore, according to our template the type
of our accumulator acc should be ArrayList.
Now we need to design filterAcc following our template.
// using pick walk over tr calling pick and select only the elements that satisfy pick
private ArrayList filterAcc(Traversal tr, ISelect pick, ArrayList acc){
if (tr.isEmpty())
return acc;
else
return filterAcc(tr.getRest(),pick,updateFilter(tr.getFirst(),pick,acc));
}
The first usage of <T>, after the modifier
private denotes that this is a generic method over
the type variable T. Our retType is
ArrayList as specified by filter. We
also need to pass to our function pick. We require
pick since we need to call its select
method on each element inside tr. This is an extra
argument that we use in the place of the ellipses in our template.
The body of the method is the same except for the last statement. Our
update method is called updateFilterc and
takes three arguments, the first element of our traversal
tr.getFirst(), pick, and the accumulator
acc. The update method is responsible for what needs
to be done to each element and how to combine this answer with
our accumulator.
Now we need to design updateFilter.
private ArrayList updateFilter(T ele,ISelect pick,ArrayList acc){
if (pick.select(ele)){
acc.add(ele);
return acc;}
else
return acc;
}
Our update method passes the element we got from tr
to pick and combines the result with our accumulator
using a logical or. This completes our implementation, using
accumulators, for filter.
The Java language provides special syntax to deal with tasks of
this kind. These constructs are called "loops" and come in two
(main) flavours, the while and for loops.
So let's take our previous example bigString and re-implement it using while loops. First, how does a while loop look like.
while(while-test){
while-block
}
Informally, the while loops works as follows:
false
jump to the end of while-block immediately after the
closing curly brace.
true
then execute while-block once and go back to step 1.
So how would we use a while loop to implement
bigString? Here's our code.
public String bigStringWhile(Traversal tr){
String acc= " "; // Base Value
while(!tr.isEmpty()){
acc = updateBigStringAcc(tr.getFirst(), acc);
tr = tr.getRest();
}
return acc;
}
First we create a local variable acc for our
accumulator and initialize its value to the accumulator's base
value. Then while we still have students in our traversal to
process we use updateBigStringAcc method to process
the first student and update our accumulator. Then we assign
to tr the remainder of our traversal, tr =
tr.getRest();. We then loop back to the beginning of our
while statement and repeat. Once we have processed all students in
our traversal our while-test will return false
and we will jump to the last statement in our method and that will
return acc.