// Visitor Pattern Demo
// CSE 401 section 3, 15wi
//
// Nathaniel Mote (nmote@cs)

public class Demo {
  public static void main(String[] args) {
    NodeOrLeaf tree = makeExampleTree();
    traverseInstanceOf(tree);
    System.out.println();
    traverseVisitor(tree);
  }

  // don't do this -- involves casts and instanceof, which are to be avoided.
  public static void traverseInstanceOf(NodeOrLeaf tree) {
    if (tree instanceof Node) {
      Node n = (Node) tree;
      traverseInstanceOf(n.left);
      System.out.println(n.value);
      traverseInstanceOf(n.right);
    } else {
      System.out.println(tree.value);
    }
  }

  // this invokes our visitor defined below
  public static void traverseVisitor(NodeOrLeaf tree) {
    tree.accept(new TraverseVisitor());
  }

  public static NodeOrLeaf makeExampleTree() {
    // construct the following tree:
    //           8
    //         /   \
    //        5     10
    //       / \    / \
    //      4   2  3   9
    NodeOrLeaf left = new Node(5, new Leaf(4), new Leaf(2));
    NodeOrLeaf right = new Node(10, new Leaf(3), new Leaf(9));
    return new Node(8, left, right);
  }
}

// Here's an implementation of TreeVisitor that traverses the tree and outputs
// the values.
class TraverseVisitor implements TreeVisitor {
  public void visit(Node n) {
    // note that we need to call accept, not visit. This takes advantage of
    // dynamic dispatch to "do the right thing"
    n.left.accept(this);
    System.out.println(n.value);
    n.right.accept(this);
  }
  public void visit(Leaf l) {
    System.out.println(l.value);
  }
}

// --------------
// Here we define the Tree classes and the machinery needed to do the visitor
// pattern. The visitor pattern allows us to add behavior to classes without
// having to edit the classes themselves every time we want to do something
// new.
// --------------

interface TreeVisitor {
  public void visit(Node n);
  public void visit(Leaf l);
}

abstract class NodeOrLeaf {
  public final int value;

  public NodeOrLeaf(int value) {
    this.value = value;
  }

  // even though the method bodies are the same, we can't just define them here,
  // because calls to the overloaded visit method must be resolved at
  // compile-time. Since the static type of "this" in this class is NodeOrLeaf,
  // the compiler cannot resolve the call.
  public abstract void accept(TreeVisitor v);
}

class Node extends NodeOrLeaf {
  public final NodeOrLeaf left;
  public final NodeOrLeaf right;

  public Node(int value, NodeOrLeaf left, NodeOrLeaf right) {
    super(value);
    this.left = left;
    this.right = right;
  }

  public void accept(TreeVisitor v) {
    v.visit(this);
  }
}

class Leaf extends NodeOrLeaf {
  public Leaf(int value) {
    super(value);
  }

  public void accept(TreeVisitor v) {
    v.visit(this);
  }
}