Transcript List

Day 3: The Command and Visitor
Patterns
Preliminaries
• The Java static type system uses simple rules to
infer types for Java expressions.
• The inferred type for an expression is
conservative; it is guaranteed to be correct, but it
may be weaker than what is required for a
particular computation.
Example: recall the finger exercise from Day 1
involving the DeptDirectory class hierarchy.
Given a variable d of type Cons bound to a
directory containing two entries, the expression
d.getRest().getRest()
Explanation
The variable d has type Cons which supports the
method getRest. What is the type of d.getRest()?
The return type of the method getRest, which is
DeptDirectory. Does DeptDirectory support the
method getRest? No. Hence, the method call
(d.getRest()).getRest()
is not well-typed.
Casting: The Standard Work-Around
• Java allows any expression of object
(reference) type A to be cast to another
object type B--provided that the types A and
B overlap (have a non-empty intersection
ignoring null.
• Given a Java expression e of type A, the
notation
(B)e
means expression e of type B. The value of
e is unchanged.
Finger Exercise
In DrJava, open the file DeptDirectory.java from the
code library at the TeachJava website. Compile it.
In the Interactions pane, evaluate:
e1 = new Entry("Corky","DH3104","x 6042");
e2 = new Entry("Matthias","DH3106","x 5732");
d = new Cons(e1, new Cons(e2, new Empty()));
d
d.getRest()
e = (Cons) d.getRest()
e.getRest()
More Practice with the Composite and
Interpreter Patterns
• In DrJava, open the file IntList.java. We want to
convert IntList.java to a program List.java that
implements heterogeneous lists (lists that can hold
arbitrary objects, not just elements of a particular
type). The element type in the program List.java
must be Object. Otherwise the code is unchanged.
• Rewrite the concat and rev methods for
heterogeneous lists. Test your code on some lists
of Integer.
List
abstract class List {
abstract Object getFirst();
abstract List getRest();
abstract String toStringHelp();
}
class Empty extends List {
static Empty ONLY = new Empty(); // singleton pattern
private Empty() {}
Object getFirst() { throw new IllegalArgumentException(
"first requires a non Empty List");
}
List getRest() { throw new IllegalArgumentException(
"rest requires a non Empty List");
}
public String toString() { return "()"; }
String toStringHelp() { return ""; }
}
class Cons extends List {
Object first;
List rest;
Cons(Object f, List r) {
first = f;
rest = r;
}
Object getFirst() { return first; }
List getRest() { return rest; }
public String toString() { return "(" + first + rest.toStringHelp() + ")"; }
String toStringHelp() { return " " + first + rest.toStringHelp(); }
}
Discussion Question
We want to define a method to sort
heterogeneous lists. The method should
work on lists of Integer, Double, Float
Long, Short, Byte, Char, String, etc.
How can we do this?
Some Possible Answers
• Pass the comparison method as an argument
to the sort method. How can we do this?
We will discuss a pattern for doing this
later.
• Exploit an interface in all of the built-in
types with a sensible total ordering called
Comparable.
Java Interfaces
In Java, an interface is a language construct that
resembles a "lightweight" abstract class (an
abstract class with no concrete methods). An
interface definition has the syntax
interface <name> {
<members>
}
which looks exactly like a class definition except
for the use of the keyword interface instead of
class. But the members of an interface are
restricted to abstract methods and static final
fields.
Examples
• The interface Comparable is built-in to Java (part of the core
library java.lang) has the following definition
interface Comparable {
int compareTo(Object other);
}
The value returned by compareTo is negative, zero, or
positive depending on whether this is less than other, equal
to other, or greater than other.
• The built-in class String also implements the interface
CharSequence which includes methods such as int length().
The built-in class StringBuffer (mutable strings) also
implements this interface.
Writing a Sort Program
• Our task is to add a method
List sort() { … }
the List class. We
to
will decompose this
problem into smaller tasks.
• Our first subtask is to write a method
List insert(Object o) { … }
that inserts o in proper order in this
assuming that this is in (ascending)
sorted
order. Your code will be littered with casts.
• Our remaining task is to write sort() using
insert as a help function.
List Sort
abstract class List {
abstract Object getFirst();
abstract List getRest();
abstract List insert(Object e);
abstract List sort();
abstract String toStringHelp();
abstract List sort();
}
class Empty extends List {
static Empty ONLY = new Empty(); // singleton pattern
private Empty() {}
Object getFirst() { throw new IllegalArgumentException(
"first requires a non Empty List");
}
List getRest() { throw new IllegalArgumentException(
"rest requires a non Empty List");
}
List sort() { return Empty.ONLY; }
List insert(Object e) { return new Cons(e,Empty.ONLY); }
public String toString() { return "()"; }
String toStringHelp() { return ""; }
}
List Sort
class Cons extends List {
Object first;
List rest;
Cons(Object f, List r) {
first = f;
rest = r;
}
Object getFirst() { return first; }
List getRest() { return rest; }
List insert(Object e) {
Comparable ce = (Comparable) e;
Comparable cf = (Comparable) first;
if (ce.compareTo(cf) < 0) return new Cons(e,this);
else return new Cons(first, rest.insert(e));
}
List sort() { return rest.sort().insert(first); }
public String toString() {
// no leading space before first
return "(" + first + rest.toStringHelp() + ")";
}
String toStringHelp() {
// leading space before each elt
return " " + first + rest.toStringHelp();
}
}