/* polymorphic linked lists, third version: The Visitor Pattern */

/*
   The visitor pattern is an advanced style of programming that takes
maximum advantage of an oop language's ability for inheritance and
dynamic dispatch.  The basic technique relies on what's called "double
dispatch".  Once again, we define our data structure using subclasses,
such as a nil class for an empty list and a "cell" class for non-empty
lists.  We wish to write various procedures (length, etc ...) for this
structure in a modular manner, and we'd like to avoid using type casts
and "if ( ... is ..." constructs as much as possible.  We'd like the 
*correct procedure* to be executed to be chosen automatically.  The previous
program achieved this to a degree.  However, the definition of each method
was spread out between different classes.  This may be appropriate for
some situations, but may be cumbersome to manage in others.  The visitor
pattern allows us to group all the different clauses of the function
in a single unit called a visitor.  Think of each operation to be 
performed on the linked list as a "visitor" objects that visits each
element of the list and performs some operations on it.  To invoke the
visitation procedure, we call a function "accept":

object accept(visitor v) { return v.visit(this); }

Every (sub)class of the data structure will contain the above generic
procedure, which allows it to be visited by any visitor.  "visitor" is
also the name of a abstract superclass or *interface*.
Each class that implements visitor will be able to visit any objects 
of any subclass.  "Double dispatch" occurs because first the correct
visitor object is chosen, then, based on the type of "this", the correct
visitation method is invoked.  If this sounds confusing, study the following
program first, then read this explanation again.
*/


using System;
using numbers;

namespace poly3 {
////////////////////////

public interface list
{
   list CDR { get; }
   int length();
   object accept(listvisitor v);  /* only one really needed */
}

public interface listvisitor
{
   object visit(nil node);
   object visit(icell node);
   object visit(rcell node);
}

public class nil : list
{
  public list CDR { get { return null; } }  
  public int length() { return 0; }
  public object accept(listvisitor v) { return v.visit(this); }
}

// generic cell class - note, declares tail, but not head!
public abstract class cell 
{
  protected list tail;
  public list CDR { get { return tail; } }
  public int length() { return 1 + tail.length(); }
}

// now we have individual classes for each kind of cell:

// integer cells
public class icell : cell, list
{
  private int head;
  // tail is inherited
  public icell(int h, list t) { head = h; tail = t; }
  public int CAR { get { return head; } set { head=value; } }

  public object accept(listvisitor v) { return v.visit(this); }
} // icell

// rational cells
public class rcell : cell, list
{
  private rational head;
  // tail is inherited
  // length is inherited
  public rcell(rational h, list t) { head = h; tail = t; }
  public rational CAR { get { return head; } }
  public object accept(listvisitor v) { return v.visit(this); }
} // rcell


// *************   visitor classes:

public class printvisitor : listvisitor
{
  public object visit(nil l) { Console.Write("\n"); return l; }
  public object visit(icell n)  
  {  Console.Write("(integer " + n.CAR + ") ");
     return n.CDR.accept(this);  // strange thing, recursion!
  }
  public object visit(rcell n)
  {  Console.Write("(fraction " + n.CAR + ") ");
     return n.CDR.accept(this);  
  }
} // printvisitor


public class adder : listvisitor  // adds a specified num to each cell
{ 
   private int amount;
   public adder(int a) { amount = a; } // constructor
   
   public object visit(nil l) { return l; }
   public object visit(icell n)
      {
           n.CAR = n.CAR + amount;
	   return n.CDR.accept(this);
      }
   public object visit(rcell n)
      {
	   n.CAR.add(new rational(amount,1));
           return n.CDR.accept(this);
      }
} // adder visitor

public class finder : listvisitor
{
   private int x;
   private rational r;
   public finder(int x0) 
      { x = x0; r = new rational(x,1); }
   public finder(int x0, rational r0)
      { x = x0; r = r0; }
   
   public object visit(nil n) { return false; }
   public object visit(icell n)
    {
	return (x==n.CAR) || (bool)n.CDR.accept(this);
    }
   public object visit(rcell n)
    {
	return r.eq(n.CAR) || (bool)n.CDR.accept(this);
    }
// I can also have an inheritance hierarchy for finder visitors,
// with subclasses for integer finders and rational finders
} // finder


////----- test:
public class polylist3
{
  private static list NIL = new nil();
  private static printvisitor printer = new printvisitor();
  
  public static void Main()
  {
    list l;
    l = new icell(3,new rcell(new rational(1,2),new icell(5,NIL)));
    l.accept(printer);
    l.accept(new adder(2));
    l.accept(printer);
    l.accept(new adder(1));
    l.accept(printer);
    bool b = (bool)l.accept(new finder(0,new rational(14,4)));
    Console.WriteLine(b);
    l = new rcell(new rational(10,1),l);
    b = (bool)l.accept(new finder(10));
    Console.WriteLine(b);
  } // Main
}


////////////////////////
}

/*

Advantages of this setup:

  more modular code
  less type casting
  eliminates checking for types
  each visitor can be arbitrarily complex, easy to add new visitors

Disadvantages of this setup:

  Difficult to add a new subclass
  Still need typecasting from object superclass.

  What we're doing here is using object as a "type variable".
  An improvement would be to allow for type variables in the first place!
*/