SE450: Lecture 10 (Iterator and Visitor)

package iterator.listone;
import java.util.NoSuchElementException;

/* public */
interface List {
  public Iterator newIterator();
}

/* public */
class ListF {
  private ListF() {}
  public static final List nil = new Nil(); /* Singleton */
  public static final List cons(int hd, List tl) /* Factory */ {
    return new Cons(hd, tl);
  }
}

/* public */
interface Iterator {
  public boolean hasNext();
  public int next();
}

/*
 *************************************************************************
 * List classes.
 *************************************************************************
 */
class Nil implements List {
  Nil() {}
  public String toString() { return "nil"; }
  public Iterator newIterator() { return new NullIterator(); }
}

class Cons implements List {
  final int hd;
  final List tl;
  Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
  public String toString() { return hd + "::" + tl.toString(); }
  public Iterator newIterator() { return new ListIterator(this); }
}

class NullIterator implements Iterator {
  NullIterator() { }
  public boolean hasNext() { return false; }
  public int next() { throw new NoSuchElementException(); }
}

class ListIterator implements Iterator {
  private List node;
  ListIterator(List node) { this.node = node; }
  public boolean hasNext() {
    return node != ListF.nil;
  }
  public int next() {
    if (! hasNext())
      throw new NoSuchElementException();
    int result = ((Cons)node).hd;
    node = ((Cons)node).tl;
    return result;
  }
}

/*
 *************************************************************************
 * A test case.
 *************************************************************************
 */
public class Main {
  public static void main(String[] args) {
    List test = ListF.cons(1, ListF.cons(2, ListF.cons(3, ListF.nil)));
    System.out.println(test);

    int sum=0;
    for (Iterator i = test.newIterator(); i.hasNext(); )
      sum += i.next();
    System.out.println(sum);

    List rev=ListF.nil;
    for (Iterator i = test.newIterator(); i.hasNext(); )
      rev = ListF.cons(i.next(),rev);
    System.out.println(rev);
  }
}

Note that the attributes must be package private so that the external iterator can access them.

A Linked List: Internal Iterator [2/25]

This is an internal iterator.

The list controls the traversal.

file:iterator/listtwo/Main.java [source] [doc-public] [doc-private]

package iterator.listtwo;

/* public */
interface List {
  public void accept(IntIterator i);
}

/* public */
class ListF {
  private ListF() {}
  public static final List nil = new Nil(); /* Singleton */
  public static final List cons(int hd, List tl) /* Factory */ {
    return new Cons(hd, tl);
  }
}

/* public */
interface IntIterator {
  public void run(int element);
}


/*
 *************************************************************************
 * List classes.
 *************************************************************************
 */
class Nil implements List {
  Nil() {}
  public String toString() { return "nil"; }
  public void accept(IntIterator i) { }
}

class Cons implements List {
  private final int hd;
  private final List tl;
  Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
  public String toString() { return hd + "::" + tl.toString(); }
  public void accept(IntIterator i) {
    i.run(hd);
    tl.accept(i);
  }
}

/*
 *************************************************************************
 * Internal Iterators.
 * Traversal controlled by the list.
 *************************************************************************
 */
class Sum implements IntIterator {
  public int value = 0;
  public void run(int hd) {
    value += hd;
  }
}

class Reverse implements IntIterator {
  public List value = ListF.nil;
  public void run(int hd) {
    value = ListF.cons(hd, value);
  }
}

/*
 *************************************************************************
 * A test case.
 *************************************************************************
 */
public class Main {
  public static void main(String[] args) {
    List test = ListF.cons(1, ListF.cons(2, ListF.cons(3, ListF.nil)));
    System.out.println(test);

    Sum v1 = new Sum();
    test.accept(v1);
    System.out.println(v1.value);

    Reverse v3 = new Reverse();
    test.accept(v3);
    System.out.println(v3.value);
  }
}

A Linked List: Internal Iterator [3/25]

This is an internal iterator.

The iterator controls the traversal.

file:iterator/listthree/Main.java [source] [doc-public] [doc-private]

package iterator.listthree;

/* public */
interface List {
  public void accept(IntIterator i);
}

/* public */
class ListF {
  private ListF() {}
  public static final List nil = new Nil(); /* Singleton */
  public static final List cons(int hd, List tl) /* Factory */ {
    return new Cons(hd, tl);
  }
}

/* public */
interface IntIterator {
  public void run(int element, List rest);
}


/*
 *************************************************************************
 * List classes.
 *************************************************************************
 */
class Nil implements List {
  Nil() {}
  public String toString() { return "nil"; }
  public void accept(IntIterator i) { }
}

class Cons implements List {
  private final int hd;
  private final List tl;
  Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
  public String toString() { return hd + "::" + tl.toString(); }
  public void accept(IntIterator i) {
    i.run(hd, tl);
  }
}

/*
 *************************************************************************
 * Internal Iterators.
 * Traversal controlled by the iterator.
 *************************************************************************
 */
class Sum implements IntIterator {
  public int value = 0;
  public void run(int hd, List tl) {
    value += hd;
    tl.accept(this);
  }
}

class Reverse implements IntIterator {
  public List value = ListF.nil;
  public void run(int hd, List tl) {
    value = ListF.cons(hd, value);
    tl.accept(this);
  }
}

/*
 *************************************************************************
 * A test case.
 *************************************************************************
 */
public class Main {
  public static void main(String[] args) {
    List test = ListF.cons(1, ListF.cons(2, ListF.cons(3, ListF.nil)));
    System.out.println(test);

    Sum v1 = new Sum();
    test.accept(v1);
    System.out.println(v1.value);

    Reverse v3 = new Reverse();
    test.accept(v3);
    System.out.println(v3.value);
  }
}

A Linked List: Visitor [4/25]

This is visitor.

A visitor is a double-dispatched iterator.

Visitors are typically internal iterators in which the iterator controls the traversal. (This is the most flexible form, as we will see when we get to trees.)

file:visitor/list/Main.java [source] [doc-public] [doc-private]

package visitor.list;

/* public */
interface List {
  public <T> T accept(ListVisitor<T> v);
}

/* public */
class ListF {
  private ListF() {}
  public static final List nil = new Nil(); /* Singleton */
  public static final List cons(int hd, List tl) /* Factory */ {
    return new Cons(hd, tl);
  }
}

/* public */
interface ListVisitor<T> {
  public T visitNil();
  public T visitCons(int hd, List tl);
}

/*
 *************************************************************************
 * List classes.
 *************************************************************************
 */
class Nil implements List {
  Nil() {}
  public String toString() { return "nil"; }
  public <T> T accept(ListVisitor<T> v) {
    return v.visitNil();
  }
}

class Cons implements List {
  private final int hd;
  private final List tl;
  Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
  public String toString() { return hd + "::" + tl.toString(); }
  public <T> T accept(ListVisitor<T> v) {
    return v.visitCons(hd, tl);
  }
}

/*
 *************************************************************************
 * Visitor classes.
 * The visitor to a Cons is responsible for visiting the tl.
 *************************************************************************
 */
class Sum implements ListVisitor<Integer> {
  public Integer visitNil() { return 0; }
  public Integer visitCons(int hd, List tl) {
    return hd + tl.accept(this);
  }
}

class Reverse implements ListVisitor<List> {
  private List result = ListF.nil; // use a field to accumulate the value
  public List visitNil() { return result; }
  public List visitCons(int hd, List tl) {
    result = ListF.cons(hd, result);
    return tl.accept(this);
  }
}

/*
 *************************************************************************
 * A test case.
 *************************************************************************
 */
public class Main {
  public static void main(String[] args) {
    List test = ListF.cons(1, ListF.cons(2, ListF.cons(3, ListF.nil)));
    System.out.println(test);

    System.out.println(test.accept(new Sum()));

    System.out.println(test.accept(new Reverse()));
  }
}


/*
 *************************************************************************
 * Here is the corresponding SML code.
 * It is intended to match the Java as closely as possible.
 *************************************************************************
datatype List = Nil | Cons of int * List

fun toString (this : List) : string =
    case this of
        Nil => "nil"
      | Cons(hd, tl) => Int.toString(hd) ^ "::" ^ toString(tl)

fun sum (acceptor : List) : int =
    case acceptor of
        Nil => 0
      | Cons(hd, tl) => hd + sum(tl)

fun reverse (acceptor : List) : List =
    let fun reverseAux (acceptor : List, result : List) =
            case acceptor of
                Nil => result
              | Cons(hd, tl) => reverseAux(tl, Cons(hd,result))
    in
        reverseAux (acceptor, Nil)
    end

fun main () : unit =
    let
        val testList = Cons(1, Cons(2, Cons(3, Nil)))
        val  = print(toString(testList) ^ "\n")
        val  = print(Int.toString(sum(testList)) ^ "\n")
        val  = print(toString(copy(testList)) ^ "\n")
        val  = print(toString(reverse(testList)) ^ "\n")
    in
        ()
    end

 *************************************************************************
 */

A Linked List: External Iterator [5/25]

External iterators must be careful if the collection is mutable.

The important part here is how MutListObj and ListIterator coordinate on changeCount.

The example looks unusual because MutList is coded using the immutable List class.

file:iterator/listfour/Main.java [source] [doc-public] [doc-private]

package iterator.listfour;
import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;

/* public */
interface MutList {
  public Iterator newIterator();
  public void insert(int i); // insert i at head of list
  public void delete(int i); // delete first occurence of i in the list
}

/* public */
interface Iterator {
  public boolean hasNext();
  public int next();
}

/* public */
class MutListF {
  private MutListF() {}
  public static final MutList newI() {
    return new MutListObj();
  }
}

class MutListObj implements MutList, Changeable {
  private List l = ListF.nil;
  private int changeCount = 0;
  public int changeCount() { return changeCount; }
  public Iterator newIterator() { return l.newIterator(this); }
  public String toString() { return l.toString(); }
  public void insert(int i) {
    changeCount++;
    l = l.insert(i);
  }
  public void delete(int i) {
    changeCount++;
    l = l.delete(i);
  }
}

/*
 *************************************************************************
 * Immutable List classes.
 *************************************************************************
 */
interface Changeable {
  public int changeCount();
}

interface List {
  public Iterator newIterator(Changeable parent);
  public List insert(int i);
  public List delete(int i);
}

class ListF {
  private ListF() {}
  public static final List nil = new Nil(); /* Singleton */
  public static final List cons(int hd, List tl) /* Factory */ {
    return new Cons(hd, tl);
  }
}

class Nil implements List {
  Nil() {}
  public String toString() { return "nil"; }
  public Iterator newIterator(Changeable parent) {
    return new NullIterator();
  }
  public List insert(int i) {
    return ListF.cons(i, this);
  }
  public List delete(int i) {
    throw new NoSuchElementException();
  }
}

class Cons implements List {
  final int hd;
  final List tl;
  Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
  public String toString() { return hd + "::" + tl.toString(); }
  public Iterator newIterator(Changeable parent) {
    return new ListIterator(this, parent);
  }
  public List insert(int i) {
    return ListF.cons(i, this);
  }
  public List delete(int i) {
    if (hd == i) {
      return tl;
    } else {
      List new_tl = tl.delete(i);
      return ListF.cons(hd, new_tl);
    }
  }
}

class NullIterator implements Iterator {
  NullIterator() { }
  public boolean hasNext() { return false; }
  public int next() { throw new NoSuchElementException(); }
}

class ListIterator implements Iterator {
  private List node;
  private Changeable parent;
  private int changeCount;
  ListIterator(List node, Changeable parent) {
    this.node = node;
    this.parent = parent;
    this.changeCount = parent.changeCount();
  }
  public boolean hasNext() {
    if (changeCount != parent.changeCount())
      throw new ConcurrentModificationException();
    return node != ListF.nil;
  }
  public int next() {
    if (changeCount != parent.changeCount())
      throw new ConcurrentModificationException();
    if (! hasNext())
      throw new NoSuchElementException();
    int result = ((Cons)node).hd;
    node = ((Cons)node).tl;
    return result;
  }
}

/*
 *************************************************************************
 * A test case.
 *************************************************************************
 */
public class Main {
  public static void main(String[] args) {
    MutList test = MutListF.newI();
    test.insert(3);
    test.insert(2);
    test.insert(1);
    System.out.println(test);

    int sum=0;
    for (Iterator i = test.newIterator(); i.hasNext(); )
      sum += i.next();
    System.out.println(sum);

    List rev=ListF.nil;
    for (Iterator i = test.newIterator(); i.hasNext(); )
      rev = ListF.cons(i.next(),rev);
    System.out.println(rev);

    for (Iterator i = test.newIterator(); i.hasNext(); )
      test.insert(4);
  }
}

A Tree: Functions over Composite [6/25]

Iterators over a composite have limited value, because they treat every type of node the same.

How to write a function over a composite?

There are two things that vary here: which function and which type of node.

interpreter:
- Method in each node for each function (as usual).
- Hard to add new functions; easy to add new node types.
- This is the "normal" OO style for a composite.
typecase:
- One static class per function; define a static helper method for each node type; use instanceOf and casting to determine node type.
- Hard to add new node types; easy to add new functions.
- Class names and attributes must be public.
- Languages such as ML and scala have support for typecase, making it more attractive.
visitor:
- One object class per function; define an object method for each node type; use double dispatch.
- Hard to add new node types; easy to add new functions.
- Class names and attributes may be private.

A Tree: Recall Composite [7/25]

file:enumeration/Expr.java [source] [doc-public] [doc-private]

package enumeration;

public interface Expr {
  void printPostorder();
  int evaluate();
}

class Const implements Expr {
  private final int v;
  public Const(int v) {
    this.v = v;
  }

  public int evaluate() {
    return v;
  }
  public void printPostorder() {
    System.out.print(v + " ");
  }
}

class BinOp implements Expr {
  private final Expr l;
  private final Expr r;
  private final Op op;

  public BinOp(Expr l, Op op, Expr r) {
    if ((l == null) || (op == null) || (r == null)) {
      throw new IllegalArgumentException();
    }
    this.op = op;
    this.l = l;
    this.r = r;
  }

  public int evaluate() {
    return op.eval(l.evaluate(), r.evaluate());
  }
  public void printPostorder() {
    l.printPostorder();
    r.printPostorder();
    System.out.print(op + " ");
  }
}

file:enumeration/Op.java [source] [doc-public] [doc-private]

package enumeration;

public abstract class Op {
  private final String name;
  Op(String name) { this.name = name; }
  public String toString() { return name; }

  public abstract int eval(int x, int y);

  public static final Op ADD = new OpAdd();
  public static final Op SUB = new OpSub();
  public static final Op MUL = new OpMul();
  public static final Op DIV = new OpDiv();
}

final class OpAdd extends Op {
  OpAdd() {  super("+"); }
  public int eval(int x, int y) { return x+y; }
}
final class OpSub extends Op {
  OpSub() {  super("-"); }
  public int eval(int x, int y) { return x-y; }
}
final class OpMul extends Op {
  OpMul() {  super("*"); }
  public int eval(int x, int y) { return x*y; }
}
final class OpDiv extends Op {
  OpDiv() {  super("/"); }
  public int eval(int x, int y) { return x/y; }
}

A Tree: Typecase [8/25]

file:visitor/typecase/Main.java [source] [doc-public] [doc-private]

package visitor.typecase;
import enumeration.Op;

public class Main {
  public static void main (String[] args) {
    Expr one = new Const(1);
    Expr onePtwo = new BinOp (new Const(1), Op.ADD, new Const(2));
    Expr threeMfour = new BinOp (new Const(3), Op.MUL, new Const(4));
    Expr m = new BinOp (onePtwo, Op.SUB, threeMfour);
    Expr n = new BinOp (m, Op.DIV, new Const(5));

    System.out.println (PostorderPrint.run(n));
    System.out.println ("Value: " + Eval.run(n));
  }
}

class PostorderPrint {
  private PostorderPrint() {}
  static private StringBuilder b = new StringBuilder();
  static private StringBuilder runConst(int c) {
    b.append(c + " ");
    return b;
  }
  static private StringBuilder runBinOp(Expr l, Op op, Expr r) {
    run(l); run(r); b.append(op + " ");
    return b;
  }
  static public StringBuilder run(Expr e) {
    if (e instanceof BinOp) {
      BinOp x = (BinOp) e;
      return runBinOp(x.l, x.op, x.r);
    } else {
      Const x = (Const) e;
      return runConst(x.c);
    }
  }
}

class Eval {
  private Eval() {}
  static private Integer runConst(int c) {
    return c;
  }
  static private Integer runBinOp(Expr l, Op op, Expr r) {
    return op.eval(run(l), run(r));
  }
  static public Integer run(Expr e) {
    if (e instanceof BinOp) {
      BinOp x = (BinOp) e;
      return runBinOp(x.l, x.op, x.r);
    } else {
      Const x = (Const) e;
      return runConst(x.c);
    }
  }
}

file:visitor/typecase/Expr.java [source] [doc-public] [doc-private]

package visitor.typecase;
import enumeration.Op;

public interface Expr { }

class Const implements Expr {
  public final int c;
  public Const(int c) {
    this.c = c;
  }
}

class BinOp implements Expr {
  public final Expr l;
  public final Expr r;
  public final Op op;

  public BinOp(Expr l, Op op, Expr r) {
    if ((l == null) || (op == null) || (r == null)) {
      throw new IllegalArgumentException();
    }
    this.op = op;
    this.l = l;
    this.r = r;
  }
}

A Tree: Visitor [9/25]

Visitor is a "cleaned up" version of typecase.

file:visitor/expr/ExprVisitor.java [source] [doc-public] [doc-private]

package visitor.expr;
import enumeration.Op;

public interface ExprVisitor<T> {
  T visitConst(int c);
  T visitBinOp(Expr l, Op op, Expr r);
}

file:visitor/expr/Main.java [source] [doc-public] [doc-private]

package visitor.expr;
import enumeration.Op;

public class Main {
  public static void main (String[] args) {
    Expr one = new Const(1);
    Expr onePtwo = new BinOp (new Const(1), Op.ADD, new Const(2));
    Expr threeMfour = new BinOp (new Const(3), Op.MUL, new Const(4));
    Expr m = new BinOp (onePtwo, Op.SUB, threeMfour);
    Expr n = new BinOp (m, Op.DIV, new Const(5));

    System.out.println (n.accept(new PostorderToString()));
    System.out.println ("Value: " + n.accept(new Eval()));
  }
}

class Eval implements ExprVisitor<Integer> {
  public Integer visitConst(int c) {
    return c;
  }
  public Integer visitBinOp(Expr l, Op op, Expr r) {
    return op.eval(l.accept(this), r.accept(this));
  }
}

class PostorderToString implements ExprVisitor<StringBuilder> {
  StringBuilder b = new StringBuilder();
  public StringBuilder visitConst(int c) {
    b.append (c + " ");
    return b;
  }
  public StringBuilder visitBinOp(Expr l, Op op, Expr r) {
    l.accept(this); r.accept(this); b.append (op + " ");
    return b;
  }
}

class PreOrderToString implements ExprVisitor<StringBuilder> {
  StringBuilder b = new StringBuilder();
  public StringBuilder visitConst(int c) {
    b.append (c + " ");
    return b;
  }
  public StringBuilder visitBinOp(Expr l, Op op, Expr r) {
    b.append (op + " "); l.accept(this); r.accept(this);
    return b;
  }
}

class InOrderToString implements ExprVisitor<StringBuilder> {
  StringBuilder b = new StringBuilder();
  public StringBuilder visitConst(int c) {
    b.append (c + " ");
    return b;
  }
  public StringBuilder visitBinOp(Expr l, Op op, Expr r) {
    l.accept(this); b.append (op + " "); r.accept(this);
    return b;
  }
}

file:visitor/expr/Expr.java [source] [doc-public] [doc-private]

package visitor.expr;
import enumeration.Op;

public interface Expr {
  <T> T accept(ExprVisitor<T> v);
}

class Const implements Expr {
  private final int c;
  public Const(int c) {
    this.c = c;
  }
  public <T> T accept(ExprVisitor<T> v) {
    return v.visitConst(c);
  }
}

class BinOp implements Expr {
  private final Expr l;
  private final Expr r;
  private final Op op;

  public BinOp(Expr l, Op op, Expr r) {
    if ((l == null) || (op == null) || (r == null)) {
      throw new IllegalArgumentException();
    }
    this.op = op;
    this.l = l;
    this.r = r;
  }
  public <T> T accept(ExprVisitor<T> v) {
    return v.visitBinOp(l, op, r);
  }
}

A Tree: External Iterator using a Stack [10/25]

file:iterator/exprtwo/Main.java [source] [doc-public] [doc-private]

package iterator.exprtwo;
import java.util.Iterator;
import enumeration.Op;

public class Main {
  public static void main (String[] args) {
    AbsExpr one = new Const(1);
    AbsExpr onePtwo = new BinOp (new Const(1), Op.ADD, new Const(2));
    AbsExpr threeMfour = new BinOp (new Const(3), Op.MUL, new Const(4));
    AbsExpr m = new BinOp (onePtwo, Op.SUB, threeMfour);
    Expr n = new BinOp (m, Op.DIV, new Const(5));

    for (Iterator<Object> i = n.postorderIterator(); i.hasNext(); )
      System.out.print (i.next() + " ");
    System.out.println ("");

    for (Iterator<Object> i = n.preorderIterator(); i.hasNext(); )
      System.out.print (i.next() + " ");
    System.out.println ("");

    for (Iterator<Object> i = n.breadthIterator(); i.hasNext(); )
      System.out.print (i.next() + " ");
    System.out.println ("");

    System.out.println ("Value: " + n.evaluate());
  }
}

file:iterator/exprtwo/Expr.java [source] [doc-public] [doc-private]

package iterator.exprtwo;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Set;
import java.util.HashSet;
import enumeration.Op;

public interface Expr {
  public int evaluate();
  public Iterator<Object> preorderIterator();
  public Iterator<Object> postorderIterator();
  public Iterator<Object> breadthIterator();
}

abstract class AbsExpr implements Expr {
  public abstract int evaluate();
  public Iterator<Object> preorderIterator() {
    PreorderIterator i = new PreorderIterator();
    i.addNode(this);
    return i;
  }
  public Iterator<Object> postorderIterator() {
    PostorderIterator i = new PostorderIterator();
    i.addNode(this);
    return i;
  }
  public Iterator<Object> breadthIterator() {
    BreadthIterator i = new BreadthIterator();
    i.addNode(this);
    return i;
  }
  abstract Object acceptPreOrder(PreorderIterator i);
  abstract Object acceptPostOrder(PostorderIterator i);
  abstract Object acceptBreadth(BreadthIterator i);
}

class Const extends AbsExpr {
  private final int v;
  public Const(int v) {
    this.v = v;
  }
  public int evaluate() {
    return v;
  }
  Object acceptPreOrder(PreorderIterator i) {
    return v;
  }
  Object acceptPostOrder(PostorderIterator i) {
    i.markVisited(this);
    return v;
  }
  Object acceptBreadth(BreadthIterator i) {
    i.markVisited(this);
    return v;
  }
}

class BinOp extends AbsExpr {
  private final AbsExpr l;
  private final AbsExpr r;
  private final Op op;
  public BinOp(AbsExpr l, Op op, AbsExpr r) {
    if ((l == null) || (op == null) || (r == null)) {
      throw new IllegalArgumentException();
    }
    this.op = op;
    this.l = l;
    this.r = r;
  }
  public int evaluate() {
    return op.eval(l.evaluate(), r.evaluate());
  }
  Object acceptPreOrder(PreorderIterator i) {
    i.addNode(r);
    i.addNode(l);
    return op;
  }
  Object acceptPostOrder(PostorderIterator i) {
    i.markVisited(this);
    if (i.visited(r)) {
      return op;
    } else {
      i.addNode(this);
      if (i.visited(l))
        return r.acceptPostOrder(i);
      else
        return l.acceptPostOrder(i);
    }
  }
  Object acceptBreadth(BreadthIterator i) {
    if (i.visited(this)) {
      i.addNode(l);
      i.addNode(r);
      return i.next();
    } else {
      i.markVisited(this);
      i.addNode(this);
      return op;
    }
  }
}

class PreorderIterator implements Iterator<Object> {
  private Stack<AbsExpr> s = new Stack<AbsExpr>();
  public boolean hasNext() {
    return ! s.empty();
  }
  void addNode(AbsExpr e) {
    s.push(e);
  }
  public Object next() {
    if (hasNext())
      return (s.pop()).acceptPreOrder(this);
    throw new NoSuchElementException();
  }
  public void remove() {
    throw new UnsupportedOperationException();
  }
}

class PostorderIterator implements Iterator<Object> {
  private Set<AbsExpr> v = new HashSet<AbsExpr>();
  private Stack<AbsExpr> s = new Stack<AbsExpr>();
  public boolean hasNext() {
    return ! s.empty();
  }
  boolean visited(AbsExpr e) {
    return v.contains(e);
  }
  void markVisited(AbsExpr e) {
    v.add(e);
  }
  void addNode(AbsExpr e) {
    s.push(e);
  }
  public Object next() {
    if (hasNext())
      return (s.pop()).acceptPostOrder(this);
    throw new NoSuchElementException();
  }
  public void remove() {
    throw new UnsupportedOperationException();
  }
}

class BreadthIterator implements Iterator<Object> {
  private Set<AbsExpr> v = new HashSet<AbsExpr>();
  private List<AbsExpr> l = new ArrayList<AbsExpr>();
  public boolean hasNext() {
    return ! l.isEmpty();
  }
  boolean visited(AbsExpr e) {
    return v.contains(e);
  }
  void markVisited(AbsExpr e) {
    v.add(e);
  }
  void addNode(AbsExpr e) {
    l.add(e);
  }
  public Object next() {
    if (hasNext()) {
      AbsExpr e = l.get(0);
      l.remove(0);
      return e.acceptBreadth(this);
    }
    throw new NoSuchElementException();
  }
  public void remove() {
    throw new UnsupportedOperationException();
  }
}

A Tree: External Iterator in CSharp [11/25]

External iterators are much easier to write in C#, which maintains the stack for you. Rather than return, use yield.

file:csharp/tree.cs [source]

// from http://en.csharp-online.net/ECMA-334:_26.4_Implementation_example
// See also http://msdn.microsoft.com/msdnmag/issues/06/00/C20/default.aspx

using System;
using System.Collections;
using System.Collections.Generic;

class Tree<T> : IEnumerable<T>
{
  private T value;
  private Tree<T> left;
  private Tree<T> right;
  public Tree(T value, Tree<T> left, Tree<T> right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
  // Returns the elements postorder
  IEnumerator<T> IEnumerable<T>.GetEnumerator() {
    if (left != null) foreach (T x in left) yield return x;
    if (right != null) foreach (T x in right) yield return x;
    yield return value;
  }
  IEnumerator IEnumerable.GetEnumerator() {
    return  ((IEnumerable<T>)this).GetEnumerator();
  }
}

class Program
{
  private static Tree<T> MakeTree<T>(params T[] items) {
    return MakeTree(items, 0, items.Length - 1);
  }
  private static Tree<T> MakeTree<T>(T[] items, int left, int right) {
    if (left > right) return null;
    int i = (left + right) / 2;
    return new Tree<T>(items[i],
                       MakeTree(items, left, i - 1),
                       MakeTree(items, i + 1, right));
  }


  public static void Main() {
    {
      Tree<int> t = MakeTree(1, 2, 3, 4, 5, 6, 7, 8, 9);
      foreach (int i in t) Console.Write("{0} ", i);
      Console.WriteLine();
    }
    {
      Tree<string> t = MakeTree("Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun");
      foreach (string s in t) Console.Write("{0} ", s);
      Console.WriteLine();
    }
  }
}

Review: OO Mechanisms: Subtyping (Polymorphism) [12/25]

Objects may be seen at more abstract (or more concrete) types.

The set of messages available to the user depend upon the declared type at which the user sees the object.

interface I { public void m(); }
class D implements I { public void m() { System.out.println("D.m");
                       public void f() { System.out.println("D.f"); }
class Main {
  public static void main(String[] args) {
    I x = new D();
    x.f();  // access denied -- won't compile
    x.m();  // prints "D.m"
  }
}

Review: OO Mechanisms: Dynamic Dispatch [13/25]

Objects may be seen at more abstract (or more concrete) types.

The way an object responds to a message depends upon its actual type.

This is called single dispatch.

GoF: In single-dispatch languages, two criteria determine which operation will fulfill a request: the name of the request and the [actual] type of receiver.

interface I { public void m(); }
class C implements I { public void m() { System.out.println("C.m"); }
class D implements I { public void m() { System.out.println("D.m");
                       public void f() { System.out.println("D.f"); }
class Main {
  public static void main(String[] args) {
    I x = new D();
    x.m();  // prints "D.m"
  }
}

Review: OO Mechanisms: Double Dispatch [14/25]

The method body depends upon the actual type of two objects.

GoF: "Double-dispatch" simply means the operation that gets executed depends on the [name] of request and the types of two receivers.

interface I {
  public void accept (V z);
}
class C implements I {
  public void accept (V z) { z.visitC(this); }
}  
class D implements I {
  public void accept (V z) { z.visitD(this); }
}  
interface V {
  public void visitC(C x);
  public void visitD(D x);
}
class U implements V {
  public void visitC(C x) { System.out.println("C accepted U"); }
  public void visitD(D x) { System.out.println("D accepted U"); }
}
class W implements V {
  public void visitC(C x) { System.out.println("C accepted W"); }
  public void visitD(D x) { System.out.println("D accepted W"); }
}
class Main {
  public static void main(String[] args) {
    I x = new D();
    V z = new W();
    x.accept(z);
  }
}

GoF: Accept is a double-dispatch operation. Its meaning depends on two types: the Visitor's and the Element's. Double-dispatching lets visitors request different operations on each class of element.

Cecil and other languages support multiple dispatch syntactically.

This is much easier in Cecil!

Review: OO Mechanisms: Delegation [15/25]

(Partial) responsibility for a message is given to another object.

The receiving object forwards messages to another object, perhaps doing some processing before and after the call.

class C { public void m() { System.out.println("C.m"); }
class D {
  C z = new C();
  public void f() { z.m(); System.out.println("D.f"); }
  public void m() { z.m(); }  // pure delegation
}
class Main {
  public static void main(String[] args) {
    D x = new D();
    x.f(); // prints "C.m D.f"
    x.m(); // prints "C.m"
  }
}

Note that delegation is often referred to as composition. This is different from the strict sense of composition used in the UML.

Review: OO Mechanisms: Classes [16/25]

Classes are a mechanism for describing objects.

Constructors are used to create instances.

Prototype-based languages use prototype objects and cloning. These languages allow either method update (assignment of new methods to objects) or multi-methods (definition of methods outside objects or classes).

Review: OO Mechanisms: Subclassing (Inheritance) [17/25]

(Partial) responsibility for a message is given to a class other than the actual class of the object.

The receiving object's actual class inherits a method, or it explicitly invokes method of an ancestor class, perhaps doing some processing before and after the call.

class C { public void m() { System.out.println("C.m"); }
class D extends C {
  public void f() { this.m(); System.out.println("D.f"); }
  // pure inheritance of m
}
class Main {
  public static void main(String[] args) {
    D x = new D();
    x.f(); // prints "C.m D.f"
    x.m(); // prints "C.m"
  }
}

Review: Pattern Summary: OO Mechanisms [18/25]

Interface: Primitive for describing the type or interface of an object.

Class: Primitive for describing implementation of an object.

Constructor: Primitive construct for building objects.

Delegation: (Partial) responsibility for a message is given to another object.

Subclassing: (Partial) responsibility for a message is given to a class other than the actual class of the object.

Review: Pattern Summary: Basic Concepts [19/25]

Immutable Data Class: Unchanging data (eg, String).

Mutable Data Class: Changing data (eg, an Employee class that contains salary information).

Collection Class: A collection. May be mutable or immutable.

Review: Pattern Summary: Controlling the number of instances [20/25]

Static Class: A set of global variables and functions.

Singleton: A polymorphic version of a static class. A set of global variables and functions, allowing for dynamic dispatch: actual functions not fixed at compile time.

Typesafe Enumeration: An immutable data class whose number of instances is determined at compile-time. The instances are globally accessible.

Flyweight: Ensure that at most once instance of an immutable data class for each value of the attributes. Similar to typesafe enumeration, but the number of possible instances may be large and there are no global references. Must keep references to all instances that have been created. Not on final exam.

Review: Pattern Summary: Creating instances [21/25]

Static Factory: a static class whose purpose is to generate instances of an interface (or interfaces). The interface and factory are public, but the implementing classes are not.

Abstract Factory: A polymorphic version of a static factory. Abstract factories are usually singletons. Not on final exam.

Builder: A mutable object used to build an immutable object. Add pieces to the builder gradually, then convert to its immutable representation (eg, StringBuilder).

Prototype (clone): A method that generates an object based on the actual type of the receiver. The returned object is a copy of the receiver.

Factory Method: A method that generates an object based on the actual type of the receiver. Factory methods are used to tie together related interfaces (eg, Collection and Iterator). Once I have a concrete instance of the primary interface (Collection), I can use it to generate concrete instances of the subsidiary interface (Iterator). Not on final exam.

Review: Pattern Summary: Structuring Behavior [22/25]

Strategy: Encapsulate variation into a separate object. A method accesses the variation (strategy) by delegating to a field or parameter.

Template Method: Encapsulate variation into a separate subclass. The template method accesses the variation (hook) by calling a method implemented in the subclass. Hook methods are often abstract in the superclass.

Command: Encapsulate a function as an object. The command can then be accessed from many places. It may also support undo/redo.

Observer (Publish/Subscribe): Allow many subscribers to observe changes in the publisher. Subscribers attach themselves to the publisher. The publisher calls back to the subscribers to notify them of changes.

Review: Pattern Summary: Structuring Behavior (Replacing Conditionals) [23/25]

Null Object: Replace null reference with an object with trivial behavior. Eliminates if-null-then-else.

Proxy: Keep an interface, but delegate functionality to another object. A proxy objects sole purpose is to control (or enable) access to another object. Eliminates if-then-else.

Decorator: Modify the behavior of an object, maintaining its interface. The decorator delegates some of its function to the object it is decorating. Eliminates if-then-else.

State: Create the illusion that an object changes its actual type (using delegation to a field). Eliminates switch/case.

Chain of Responsibility: Give more than one object a chance to handle a request. Chain the receiving objects and pass the request along the chain until an object handles it. Eliminates switch/case. Not on final exam.

Review: Pattern Summary: Collections [24/25]

Null Object: Replace null reference with an object with trivial behavior.

Composite: Make collections of objects have the same interface as single objects.

Internal Iterator: Pass a function into a collection. The collection runs the function on each element. Not on final exam.

External Iterator: Recieve an object from a collection; use the object to access the elements in the collection. Not on final exam.

Visitor: double dispatch an iterator, typically an internal iterator over a composite.

What now? [25/25]

The following classes emphasize programming with patterns:

SE546: Software Architecture and Design for Desktop Applications
SE552: Concurrent Software Development
SE554: Enterprise Component Architecture
CSC531: Introduction to Bioinformatics

Revised: 2008/09/03 15:27