8 3/10: Quick Lists and Visits, Revisited
Due: 3/10 at 11:59 PM.
Language: Java
There are now some hints on the blog...
8.1 Lab Completion
Finish the AExp visitors from the 2/24: Java, Arithmetic and Visitors lab.
8.2 Quick Lists
Translate the Quick Lists data type from 1/29: Nesting Worlds and Quick Lists into Java. Your goal is to design one or more Java classes that implement the following interface (translated from idiomatic Racket into idiomatic Java):
interface IList<T> {
// Cons given element on to this list.
IList<T> cons(T t);
// Get the first element of this list (or throw an error
// if the list is empty)
T first();
// Get the rest of this list (or throw an error
// if the list is empty)
IList<T> rest();
// Get the nth element of this list (or throw an error
// if the list is too short)
T get(int n);
// Compute the number of elements in this list
int length();
}
8.3 Quick Visits
This problem builds on the quick lists problem, and gives you more practice with a slight variation of the visitor pattern.
Let’s revise the IList<T> interface to include support for visitors:
interface IList<T> {
...
// Allows a visitor to visit this list's data
<U> visit(IListVisitor<T, U> visitor);
}
and define a list visitor interface:
interface IListVisitor<T, U> {
// Visit an empty list and produce a U
U visitMt();
// Visit a "cons" (i.e., first and rest) and produce a U
U visitCons(T first, IList<T> rest);
}
Notice the difference from the visitors we defined for AExps or for binary trees as we did in class: instead of passing the actual Mt or Cons objects to the visitor, we pass their fields. Why? Because our quick lists aren’t structurally implemented with Mt and Cons classes, but they still logically behave just like our regular Mt/Cons lists.
As an example, here is a list visitor that computes the length of a list:
class LengthVisitor<T> implements IListVisitor<T, Integer> {
Integer visitMt() { return 0; }
Integer visitCons(T first, IList<T> rest) {
return 1 + rest.visit(this);
}
}
This visitor ought to work with both regular Mt/Cons lists and with your quick lists, because it only uses the IList<T> interface.
Implement the visit methods on your quick list implementation so that the LengthVisitor above works.
Implement a IListVisitor<T, T> named ReverseVisitor that produces a new quick list that is the reverse of the given list (note: you may need to implement a “helper” visitor that corresponds to the helper function you’d write for the reverse function).
Implement a IListVisitor<T, U> named MapVisitor that mapes a IFun<T, U> across your list.