// Having fun with Visitors.
//
// Written by Doron Rajwan, doron@rajwan.org, http://www.rajwan.org, 2003.
// Thanks to Oren Ben-Kiki for the FractalMutationVisitor idea.

import java.util.Stack;

// The abstract node class. Can accept() a visitor.
// 1. Unlike in the books, it returns it's parameter -- see invocation below.
abstract class Node {
    abstract Visitor accept(Visitor v);      // must return 'v'.
}

// The immutable (read-only) value node.
class ValueNode extends Node {
    ValueNode(double value) {
        m_Value = value;
    }
    Visitor accept(Visitor v) {
        v.visit(this);
        return v;
    }
    final double m_Value;
}

// The immutable (read-only) binary operator node.
class BinaryNode extends Node {
    BinaryNode(char operator, Node left, Node right) {
        m_Operator = operator;
        m_Left = left;
        m_Right = right;
    }
    Visitor accept(Visitor v) {      // RULE: pre arg0 [mid arg_j]* post
        if (v.preVisit(this)) {
            m_Left.accept(v).midVisit(this);
            m_Right.accept(v).postVisit(this);
        }
        return v;
    }
    final char m_Operator;
    final Node m_Left, m_Right;
}

// The visitor interface.
// 1. Simple node are just 'visited'.
// 2. Complex nodes are pre-visited, mid-visited, post-visited.
// 3. Also, has a getResult() call.
//    The last two gives a lot of flexability -- much more than in the books!
interface Visitor {
    void visit(ValueNode node);
    boolean preVisit(BinaryNode node); // return false to skip this sub-tree.
    void midVisit(BinaryNode node);
    void postVisit(BinaryNode node);
    Object getResult();                 // may be called ONLY ONCE.
}

// Trivial print visitor.
class PrintVisitor implements Visitor {
    public void visit(ValueNode node) {
        m_buf.append(node.m_Value);
    }
    public boolean preVisit(BinaryNode node) {
        m_buf.append('(');
        return true;
    }
    public void midVisit(BinaryNode node) {
        m_buf.append(node.m_Operator);
    }
    public void postVisit(BinaryNode node) {
        m_buf.append(')');
    }
    public Object getResult() {
        return m_buf.toString();
    }
    protected StringBuffer m_buf = new StringBuffer();
}

// A little more complex XML print visitor.
// 1. Has depth parameter (-1 is unlimited depth).
// 2. Print value of node for nodes which are too deep.
class XMLVisitor extends PrintVisitor {
    XMLVisitor(int depth) {
        m_depth = depth;
    }
    public void visit(ValueNode node) {
        m_buf.append(m_sp).append("<DOUBLE VAL=\"").append(node.m_Value).append("\"/>\n");
    }
    public boolean preVisit(BinaryNode node) {
        if (m_depth == 0) {     // just print the computed value of this sub-tree.
            m_buf.append(m_sp).append("<DOUBLE VAL=\"")
                 .append(node.accept(m_Eval).getResult())
                 .append("\" COMPUTATION_OF=\"").append(label(node.m_Operator))
                 .append("\" />\n");
            return false;       // skip this sub-tree for XML visitor.
        }
        m_buf.append(m_sp).append("<").append(label(node.m_Operator)).append(">\n");
        m_sp += "    ";
        --m_depth;
        return true;
    }
    public void midVisit(BinaryNode node) {
    }
    public void postVisit(BinaryNode node) {
        ++m_depth;
        m_sp = m_sp.substring(4);
        m_buf.append(m_sp).append("</").append(label(node.m_Operator)).append(">\n");
    }
    private int m_depth;
    private String m_sp = "";
    private Visitor m_Eval = new EvalVisitor();
    private static String label(char op) {
        switch (op) {
        case '+':
            return "PLUS";
        case '-':
            return "MINUS";
        case '*':
            return "MUL";
        case '/':
            return "DIV";
        default:
            throw new UnsupportedOperationException("Invalid Operator: " + op);
        }
    }
}

// Evaluate the expression.
class EvalVisitor implements Visitor {
    public void visit(ValueNode node) {
        m_stack.push(new Double(node.m_Value));
    }
    public boolean preVisit(BinaryNode node) {
        return true;
    }
    public void midVisit(BinaryNode node) {
    }
    public void postVisit(BinaryNode node) {
        double right = ((Double)m_stack.pop()).doubleValue();   // right first,
        double left = ((Double)m_stack.pop()).doubleValue();    // left second!
        double result;
        switch (node.m_Operator) {
        case '+':
            result = left + right;
            break;
        case '-':
            result = left - right;
            break;
        case '*':
            result = left * right;
            break;
        case '/':
            result = left / right;
            break;
        default:
            throw new UnsupportedOperationException("Invalid Operator: " + node.m_Operator);
        }
        m_stack.push(new Double(result));
    }
    public Object getResult() {  // return a Double. May be called only ONCE!
        return m_stack.pop();
    }
    private Stack m_stack = new Stack();
}

// This is the ONLY non-trivial example. This class mutate the tree:
// 1. Values are mutated.
//    Tree structure and operators are NOT mutated.
// 2. The probability parameter is the probability to ENTER the next level.
//    If a leaf is entered -- it is ALWAYS mutated.
//    Thus, the list of the mutated leaves creates a Fractal.
// 3. The new created tree takes minimal amount of memory.
//    Because the nodes are immutable (read-only), it means that only the
//    path from the mutated values to the root will be replaced.
//    Thus, both Trees are valid, and share the most!
class FractalMutationVisitor implements Visitor {
    FractalMutationVisitor(double digProb) {
        m_digProb = digProb;
    }
    public void visit(ValueNode node) {
        m_stack.push(new ValueNode(Math.random()));     // Mutation!
    }
    public boolean preVisit(BinaryNode node) {
        if (Math.random() >= m_digProb) {   // do not dig down.
            m_stack.push(node);
            return false;
        }
        return true; // it's digging time!
    }
    public void midVisit(BinaryNode node) {
    }
    public void postVisit(BinaryNode node) {
        Node right = (Node)m_stack.pop();       // right first,
        Node left = (Node)m_stack.pop();        // left second!
        if (left == node.m_Left && right == node.m_Right) {
            m_stack.push(node); // digging stopped in the middle
        } else {
            m_stack.push(new BinaryNode(node.m_Operator, left, right));
        }
    }
    public Object getResult() {
        return m_stack.pop();       // The created tree.
    }
    private final double m_digProb;
    private Stack m_stack = new Stack();
}

// Test program.
public class FunWithVisitors {
	public static void main(String[] args)  {
        // Simple Expression.
        Node p1 = new BinaryNode('+', new ValueNode(12), new ValueNode(3));
        Node p2 = new BinaryNode('/', new ValueNode(60), p1);
        Node p3 = new BinaryNode('*', new ValueNode(5), new ValueNode(3));
        Node p = new BinaryNode('+', p3, p2);
        // Print it as XML.
        System.out.println(p.accept(new XMLVisitor(-1)).getResult()); // any depth.
        System.out.println(p.accept(new XMLVisitor(2)).getResult());
        System.out.println(p.accept(new XMLVisitor(1)).getResult());
        System.out.println(p.accept(new XMLVisitor(0)).getResult());
        // And as expression.
        System.out.println(p.accept(new PrintVisitor()).getResult() 
                         + "="
                         + p.accept(new EvalVisitor()).getResult());
        // Now Mutate!   Run until only the "60" changes.
        Node mut = (Node)p.accept(new FractalMutationVisitor(0.6)).getResult();
        System.out.println("\nAfter Mutation: (same_instance=" + (mut == p) +")");
        System.out.println(mut.accept(new XMLVisitor(-1)).getResult());
    }
}