/*
  Expression tree, "csc123" version: the Visitor Pattern.

  The program in exptree3.cs 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 ...

  One item some people might not like about this program is that elements
  that were "private" or "protected" now need to be visible to both the
  expr and the exprvisitor classes.  oop languages provides varying degrees
  of flexibility to implementing such a scenario, in addition to simply making
  everything "public".  The language Eiffel allows you to specify exactly 
  which classes something is to be visible to.  In C++, there is the "friend"
  declaration.  In Java, there's globally public versus public within a
  package.  In C#, instead of "public" we can use the modifier "internal",
  which means that it's public only to code that's compiled together, but
  not if the code is imported as a .dll by another program.  
*/

using System;

interface expr    // interface for abstract expression
{
  object accept(exprvisitor v); 
}

interface exprvisitor   // interface for abstract visitor
{
  object visiti(intnode e);
  object visitp(plusnode e);
  object visitt(timesnode e);
  object visitu(uminusnode e);
}

class intnode : expr  // integer expreesion
{
   internal int val;
   public intnode(int v) {val = v; }
   public object accept(exprvisitor v) { return v.visiti(this); }
} // intnode


class plusnode : expr // + operator expression
{  internal expr left, right;
   public plusnode(expr l, expr r) { left=l; right=r; }
   public object accept(exprvisitor v) { return v.visitp(this); }
} // plusnode

class timesnode : expr // * operator expression
{  internal expr left, right;
   public timesnode(expr l, expr r) { left=l; right=r; }
   public object accept(exprvisitor v) { return v.visitt(this); }
} // timesnode

class uminusnode : expr
{  internal expr left;
   public uminusnode(expr l) {left=l;}
   public object accept(exprvisitor v) { return v.visitu(this); }   
}

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

class evalvisitor : exprvisitor
{
   public object visiti(intnode e) 
   { return e.val; }
   public object visitp(plusnode e) 
   {
       return (int)e.left.accept(this) + (int)e.right.accept(this);
   }
   public object visitt(timesnode e)
   {
       return (int)e.left.accept(this) * (int)e.right.accept(this);
   }
   public object visitu(uminusnode e)
   {
       return (int)e.left.accept(this) * -1;
   }
} // evalvisitor

class printvisitor : exprvisitor
{
   public object visiti(intnode e) 
   { Console.Write( e.val ); return null; }

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

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

   public object visitu(uminusnode e)
   { Console.Write("(- "); e.left.accept(this); Console.Write(")"); 
     return null;
   }
    
   private void print(String op, expr l, expr r) //utility method
   {
       Console.Write("("+op+" ");
       l.accept(this); Console.Write(" "); 
       r.accept(this); Console.Write(")");
   }
} // printvisitor


///////////////////////////////
public class exptree4b
{
  public static void Main()
  {
    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 = (int)A.accept(evaluator); // cast from object to int needed
    Console.WriteLine("\nvalue is "+ v );

    // testing new visitor below:
    Console.WriteLine("size of tree is "+A.accept(new sizefinder()));
  } // main
}

// now it's easy to add another type of visitor modularly (without editing
// above code:

// new visitor to calculate size of expression tree
class sizefinder : exprvisitor
{
  public object visiti(intnode e) { return 1; }
  public object visitp(plusnode e) 
    { return 1 + (int)e.left.accept(this) + (int)e.right.accept(this); }
  public object visitt(timesnode e)
    { return 1 + (int)e.left.accept(this) + (int)e.right.accept(this); }
  public object visitu(uminusnode e)
    { return 1 + (int)e.left.accept(this); }
}//sizefinder

/*
   To understand how a line like 

      A.accept(printer); 

   works.  The first dispatch is made on the "visitee" object A.
   Depending on the (static) type of A, its accept method of A invokes
   
      v.visiti(this)  or   visitp(this) ... or ... visitu(this)

   where v is an abstract exprvisitor.  Now a second dispatch occurs, 
   this time on the "visitor" object v.  That is, both types of the visitee
   and visitor are made abstract and rely on dynamic dispatch.  In this
   example, the visitee is some specific expression node (plusnode), which
   needs to be processed differently.  The visitor is some specific visitor
   (printvisitor) that also behaves differently.  

   One final word: method overloading is a not used in this example
   because it will not make a difference.  We can also define the visitor
   interface as:

    interface exprvisitor
    {
      object visit(intnode e);
      object visit(plusnode e);
      object visit(timesnode e);
      object visit(uminusnode e);
    }

   and the same mechanisms would still be needed because the correct
   version of visit is selected at compile time, based on the static
   type of it's argument.  Overloading is just a convenience.  The
   central mechanism is that there are different kinds of visitors and
   different kinds of visitees, and the Visitor Pattern ties these
   classes together.

   The visitor pattern's disadvantage is that it's harder to add a new visitee
   class (for a new kind of expression).  It's advantage is that it's easier
   to add a new visitor class.
*/