/*
  Expression tree, final C# version: The Parametrized Visitor Pattern

  The program in exptree3.java is fairly good, but notice that the code
  for an operation such as "eval" is scattered across many different
  classes.  This kind of object oriented design makes it easy to add a
  new kind of expression, that is, a new kind of data object to be
  operated on.  But adding a new operation (in addition to eval and
  print) is more difficult to do in a *modular way*.  We wish to
  extend a program without modifying the source code of the existing
  program, only building on top of it.  We learned that the so-called
  "extension methods" feature of C# falls short of allowing us to do this
  because extension methods are resolved statically, not dynamically:
  they will not choose the right type of operation on an *expr* object
  without knowing at compile time what the actual type of the object is
  (intnode, plusnode, etc).

  The "Visitor" design pattern gathers the various cases of an
  operation into one class.  It is the most aggressive use of oop that
  I know of.  Its central mechanism is "double dispatch".

  The classes for the different types of expressions (intnode, timesnode, etc)
  are called "visitees".  Operations such as eval are encapsulated in classes
  called "visitors".  Each visitor class must know how to visit each kind
  of expression (intnode, timesnode, etc). That is, a "eval visitor", when
  visiting a node, will evaluate its integer value.  A "print visitor" will
  print each node that it visits.  Each of these visitors must implement 
  methods for visiting intnodes, plusnodes, timesnodes, etc ...

  Each visitee class will define an accept(visitor v) method that calls
  `v.visit(this)`. Then given a visitor vt and a visitee vs, we call
  vs.accept(vt).  This enables double-dispatch.  The first dispatch, with
  vs.accept(vt), is made on the visitee, which invokes the correct accept
  method.  The second dispatch is made on vt.visit(this), which dispatches
  on the visitor.  Note that there is also a usage of overloading, because
  the different visit methods within a visitor class are all called "visit":
  but this is not the central enabling mechanism.
  
  In this further refinement of the visitor patterns program, we
  use parametrized types to implement visitors, so that they don't 
  always have to return "object".

  Note that the expr interface is not itself parametrized.  Only the
  accept function is parametrized.  That is, the accept function cannot
  make any assumptions about what T is.  We use the notation `? extends T`
  to indicate that T can be covariant, because it is the codomain of the
  visit functions.  This means that the codmain can be a more specific type
  than T (in terms of the inheritance hierarchy).
*/

interface expr    // interface for abstract expression
{
  <T> T accept(exprvisitor<? extends T> v); // polymorphic function
}

interface exprvisitor<T>   // interface for abstract visitor
{
  T visit(intnode e);
  T visit(plusnode e);
  T visit(timesnode e);
  T visit(uminusnode e);
}

class intnode implements expr  // integer expreesion
{
   int val;
   public intnode(int v) {val = v; }
   public <T> T accept(exprvisitor<? extends T> v) { return v.visit(this); }
} // intnode


class plusnode implements expr // + operator expression
{  expr left, right;
   public plusnode(expr l, expr r) { left=l; right=r; }
   public <T> T accept(exprvisitor<? extends T> v) { return v.visit(this); }
} // plusnode

class timesnode implements expr // * operator expression
{  expr left, right;
   public timesnode(expr l, expr r) { left=l; right=r; }
   public <T> T accept(exprvisitor<? extends T> v) { return v.visit(this); }
} // timesnode

class uminusnode implements expr
{  expr left;
   public uminusnode(expr l) {left=l;}
   public <T> T accept(exprvisitor<? extends T> v) { return v.visit(this); }   
}

/////////////////////////////////
//////////// visitor classes: each visitor implements an operation on all
// subclasses (cases) of the abstract data type.

class evalvisitor implements exprvisitor<Integer>
{
   public Integer visit(intnode e) 
   { return e.val; }
   public Integer visit(plusnode e) 
   {
       return e.left.accept(this) + e.right.accept(this);
   }
   public Integer visit(timesnode e)
   {
       return e.left.accept(this) * e.right.accept(this);
   }
   public Integer visit(uminusnode e)
   {
       return e.left.accept(this) * -1;
   }
} // evalvisitor

class printvisitor implements exprvisitor<Object>
{
   public Object visit(intnode e) 
   { System.out.print( e.val ); return null; }

   public Object visit(plusnode e) 
   { print("+",e.left,e.right);  return null; }

   public Object visit(timesnode e)
   { print ("*",e.left,e.right); return null; }

   public Object visit(uminusnode e)
   { System.out.print("(- "); e.left.accept(this); System.out.print(")"); 
     return null;
   }
    
   private void print(String op, expr l, expr r) //utility method
   {
       System.out.print("("+op+" ");
       l.accept(this); System.out.print(" "); 
       r.accept(this); System.out.print(")");
   }
} // printvisitor


///////////////////////////////
public class exptree5
{
  public static void main(String[] args)
  {
    expr A = new plusnode(new timesnode(new intnode(2),new intnode(3)),
	                  new plusnode(new intnode(1),new intnode(4)));
    printvisitor printer = new printvisitor();
    evalvisitor evaluator = new evalvisitor();
    A.accept(printer);
    int v = A.accept(evaluator); // no more need to type cast, and type 
	                         // errors are caught at compile time.
    //int v = A.accept<int>(evaluator); // also works, but inferred!
    System.out.println("\nvalue is "+ v );
  } // main
}