/*
  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 provide 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
{
  T accept<T>(exprvisitor<T> v); 
}

interface exprvisitor<out T>   // interface for abstract visitor
{
  T visiti(intnode e);
  T visitp(plusnode e);
  T visitt(timesnode e);
  T visitu(uminusnode e);
} // out T means T can be covariant (? extends T in java)

class intnode : expr  // integer expreesion
{
   internal int val;
   public intnode(int v) {val = v; }
   public T accept<T>(exprvisitor<T> 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 T accept<T>(exprvisitor<T> 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 T accept<T>(exprvisitor<T> v) { return v.visitt(this); }
} // timesnode

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

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

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

class printvisitor : exprvisitor<object>
{
   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<int>
{
  public int visiti(intnode e) { return 1; }
  public int visitp(plusnode e) 
    { return 1 + e.left.accept(this) + e.right.accept(this); }
  public int visitt(timesnode e)
    { return 1 + e.left.accept(this) + e.right.accept(this); }
  public int visitu(uminusnode e)
    { return 1 + 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<T>
    {
      T visit(intnode e);
      T visit(plusnode e);
      T visit(timesnode e);
      T 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.
*/

/// Adding a new type of expression: exponent like 2**n

// Either I extend the visitor interface, or the visitee (expr) interface:

interface extvisitor<out T> : exprvisitor<T>  // extvisitor can visit exptnode
{
   T visite(exptnode x); // no overloading used
}  

class exptnode : expr // ** operator expression
{  internal expr left, right;
   public exptnode(expr l, expr r) { left=l; right=r; }
   public T accept<T>(exprvisitor<T> v) // must have because of expr interface!
     {  if (v is extvisitor<T>)  // oops! what does this mean?
	   return ((extvisitor<T>)v).visite(this);
	else throw new Exception("visitor can't visit exptnode");
        // runtime overhead plus loss of static type safety
     }
} // exptnode

class extevaluator: evalvisitor, extvisitor<int> // this is nice to define
{
   public int visite(exptnode e)
   {
      int a = e.left.accept(this);
      int b = e.right.accept(this);
      return (int)Math.Pow(a,b);
   }
}

/*
The strangeness in this code is the way that the accept method in exptnode was
written.  An original exprvisitor doesn't know how to visit an exptnode, but
because of the expr interface, we have write accept to take exprvisitor as
an argument.  We had to resort to an if..is.. to figure out whether the 
exprvisitor is actually a extvisitor (because there's no dynamic dispatch
on the argument to accept).  What's the big deal?  The type downcast
means that there will be new type errors that are not caught at compile time:

expr B = new exptnode(intnode(2),intnode(6)); // 2**6
B.accept(new printvisitor()); // will compile, but give runtime error.
// The original printvisitor clearly cannot visit an exptnode - the *algorithm*
// is missing.

Thus, this illustrates a subtle but signifcant failure of dynamic dispatch
and the OOP paradigm - we had to resort to an if-else.
*/