/*
   Polymorphic linked lists
*/

interface calculator<A>
{
    public A add(A x, A y);
    public A times(A x, A y);
    public A zero();   // this has to be a function
    public A one();
    public boolean lt(A x, A y);  // less than
    public boolean eq(A x, A y);  // equals to 
}

class intcalc implements calculator<Integer>
{
    public Integer add(Integer x, Integer y) { return x+y; }
    public Integer times(Integer x, Integer y) { return x*y; }
    public Integer zero() { return 0; }
    public Integer one() { return 1; }
    public boolean lt(Integer x, Integer y) {return x<y; }
    public boolean eq(Integer x, Integer y) {return x==y; }
}

///////////// class for fractions and corresponding calculator
class fraction
{
    public int n, d;  // numerator and denominator
    public fraction(int a, int b) 
    { int gd = gcd(a,b); n=a/gd;  d=b/gd; }
    private int gcd(int a, int b)  // gcd for reducing fractions
    { if (a==0) return b; else return gcd(b%a,a); }
    public String toString()
    { return n+"/"+d; }
} // fraction class

// fraction calculator
class fractcalc implements calculator<fraction>
{
    public fraction add(fraction x, fraction y)
    {
        return new fraction(x.n*y.d+x.d*y.n, x.d*y.d);
    }
    public fraction times(fraction x, fraction y)
    {   
        return new fraction(x.n*y.n,x.d*y.d);
    }
    public fraction zero() { return new fraction(0,1); }
    public fraction one() { return new fraction(1,1); }
    public boolean lt(fraction x, fraction y)  // less than
    {
	return (x.n*y.d < x.d*y.n);
    }
    public boolean eq(fraction x, fraction y)  // equals to 
    {
	return (x.n*y.d == x.d*y.n);
    }
} //fractcalc


// a parameterized class for linked lists
class cell<A>
{
    A head;
    cell<A> tail;
    public cell(A h, cell<A> t) {head=h;  tail=t;}

    public String toString()
    {
	String s = "";
	for (cell i=this;i!=null;i=i.tail) s=s+i.head+" ";
	return s;
    }

    // product of all numbers
    /*  bad attempt, since list may not just contain integers
    public int product()
    {
	int ax = 1;
	cell i;
	for(i=this;i!=null;i=i.tail) ax = ax * i.head;
	return ax;
    }
    */

    // using the parametric calculator class
    public A product(calculator<A> calc)
    {
	A ax = calc.one();   // int ax = 1;
	cell<A> i = this;
        while (i!=null)
	    {
		ax = calc.times(ax,i.head); // ax = ax * i.head
		i = i.tail;
	    }
	return ax;
    } //product

    // another polymorphic method: check if list is sorted:

    public boolean sorted(calculator<A> calc)
    {
	cell<A> i = this;
	boolean answer = true; // default
	while (i.tail != null && answer)
	{
	    if (calc.lt(i.tail.head,i.head)) answer = false;
	    i = i.tail;
	}
	return answer;
    }//sorted
    
    // in contrast, the length function is "naturally polymorphic":
    public int length()
    {
	int ax = 0;
	for(cell<A> i=this; i!=null; i=i.tail) ax++;
	return ax;
    }

} // cell<A> class

public class polylist
{
    // polymorphic function to compute length of list.  
    // this function is parametric by itself.
    public static int length(cell<?> L)  // ? is a "wildcard"
    {
	int ax =0;
	for (cell i=L;i!=null;i=i.tail) ax++;
	return ax;
    }

    public static void main(String[] args)
    {
	// linked lists of different types
	cell<Integer> I = new cell<Integer>(2,new cell<Integer>(4,null));
	cell<fraction> F = new cell<fraction>(new fraction(1,2),
		      new cell<fraction>(new fraction(2,3),null));
	cell<Double> D = new cell<Double>(2.3,new cell<Double>(4.5,null));
	cell<String> S = new cell<String>("abc",new cell<String>("def",null));

        // setting the calculator objects for Integer and fraction
        calculator<Integer> Icalc = new intcalc();
	calculator<fraction> Fcalc = new fractcalc();
	
	// calling polymorphic methods:
	System.out.println(I.length());
	System.out.println(F.length());
	System.out.println(S.length());  // can call even though no calc
	System.out.println(length(D));   // calling static function above
        
	System.out.println(I.product(Icalc));
	System.out.println(F.product(Fcalc));
	System.out.println(F.sorted(Fcalc));
    } //main

} //polylist