/* Polymorphic linked lists - second version  - uses algebraic structure */
using System;
using numbers;

/*
   The inductive definition of linked lists says that a list can be
one of two things: an empty list and something cons'ed onto an
existing list.  Instead of thinking of lists as structures in memory,
which is the conventional approach (see polylist1.cs), we can also
think about representing the different *cases* of the algebraic
definition explicitly using inheritance.  Each possible instance of
a linked list is a subclass of the generic list interface, which 
specifies the operations that can be performed on any type of list.
With this representation, one does not have to check with an if-else
clause if a list is empty - that will be handled by automatic dispatch.
*/ 

/*
   In this program (and the next one) I chose to take advantage of
   C#'s automatic "boxing" operation - so the superclass 'object' is
   often used as a generic type - including for ints and doubles.  It
   would be better, however, to declare a tighter superclass for 
   all numerical types (object is too general).  This will allow us
   to overload operators such as <= and ++, leading to a higher degree
   of abstraction and polymorphism.
*/

namespace poly2 { ////////////////////////

public delegate object visitor(object x); // generic function pointer

public interface list
{
   // define all operations on lists
   int length();
   bool member(object x);
   void print();
   list CDR { get; }
   void map(visitor f);
   void inc();   // added in class 11/9
}

public class nil : list
{
  public int length() { return 0; }
  public bool member(object x) { return false; }
  public void print() { Console.WriteLine(""); }
  public object CAR { get { return null; } }
  public list CDR { get { return null; } }
  public void map(visitor f) {}
  public void inc() {}
}

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

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

// integer cells
public class icell : cell, list
{
  private int head;
  // tail is inherited
  // length is inherited
  public icell(int h, list t) { head = h; tail = t; }
  public object CAR { get { return head; } }
  public bool member(object x) // we know that "object" must be an int!
  {
     int n = (int)x;  // this is called "unboxing"
     return (n==head) || tail.member(x);
  }
  // why isn't member in the superclass? - need another mechanism!

  public void print() 
  {  Console.Write(head+" "); 
     tail.print(); // note: don't need to check if tail is null
  }

  // applies a generic operation (delegate) to all elements of list
  public void map(visitor f)
  {  head = (int) f(head);
     tail.map(f);
  }
  public void inc() { head++; tail.inc(); }
} // 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 object CAR { get { return head; } }
  public bool member(object x)
  {
     rational n = (rational)x;
     return (head.eq(n)) || tail.member(x);
  }
  // why isn't member in the superclass? - need another mechanism!

  public void print() 
  {  Console.Write(head+" "); 
     tail.print(); // note: don't need to check if tail is null
  }

  public void map(visitor f)
  {  head = (rational) f(head);  // depends on runtime typing
     tail.map(f);
  }
  public void inc() { head.add(new rational(1,1));  tail.inc(); }
} // rcell


//// test:

public class polylist2
{
  private static list NIL = new nil();

  public static object add1 (object x)
  {  if (x is int) return ((int)x)+1;
      else if (x is rational) 
	{ rational r = (rational)x; r++; }
     return x;
  }
  
  public static void Main()
  {
    list l;
    l = new icell(3,new rcell(new rational(1,2),new icell(5,NIL)));
    l.print();
    Console.WriteLine(l.length());
    l.map(new visitor(add1));
    l.print();
  } // Main
}


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



/*
Disadvantages of this setup:

each new function on list ADT requires changing every subclass

member only works on lists with uniform-typed elements

The visitor function needs to call -is- which defeats the purpose
of automatic dispatch - might as well tag it ourselves like in C

What if the visitor needed another argument?

Advantage: easy to add a new subclass

*/