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

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(amount);
           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!
*/