/*
  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 may not be the desired way to implement a program.  We may
  wish to use algebraic subtypes, but still "gather" the various cases of
  an operation into one class.  The visitor pattern allows this approach.
  It is the most aggressive use of oop that I know of.  Its central mechanism
  is referred to as "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.  

  Note: there is a version of this program that uses generics (templates)
  instead of `object` for polymorphism.  Find it at
  https://cs.hofstra.edu/~cscccl/csc123/exptree5.cs
*/

using System;

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

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

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

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

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

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

class printvisitor : exprvisitor
{
   public object visit(intnode e) 
   { Console.Write( 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)
   { 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 exptree4c
{
  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 with exptnode (defined below...)
    expr B = new plusnode(new intnode(1), new exptnode(new intnode(2),A));
    Console.WriteLine("expt is "+ B.accept(new extevaluator()));

    // B.accept(new printvisitor()); // not a compiler error

  } // main
}

/*
   To understand how a line like 

      A.accept(printer); 

   works.  The first dispatch is made on the "visitee" object A.
   The accept method of the visitee invokes 
   
      v.visit(this);

   where v is an abstract exprvisitor.  Thus 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: it may appear that method overloading is a central 
   mechanism here, but in fact it is not.  We can also define the visitor
   interface as:

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

   and the same mechanisms would still be needed.  Overloading is just
   a further 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 : exprvisitor  // extendedvisitor can visit exptnode
{
   object 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 object accept(exprvisitor v) // must have because of expr interface!
     {  if (v is extvisitor)  // oops! what does this mean?
	   return ((extvisitor)v).visite(this);
	else throw new Exception("visitor can't visit exptnode");
     }
} // exptnode

class extevaluator: evalvisitor, extvisitor // this is nice to define
{
   public object visite(exptnode e)
   {
      int a = (int)e.left.accept(this);
      int b = (int)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.
*/