/*
    This series of three programs illustrate how to use advanced programming
language features to achieve polymorphism in our programs.  An algorithm is
polymorphic if it can work or be adopted to work on different types of data.
But how do we realize the polymorphic potential inherent in an algorithm?

Let's start with a simple program, encapsulated within a class that's 
NOT polymorphic.  This class contains a pointer to an array of doubles,
which is assigned by the constructor.  It also contains some methods that
calculate various properties of the array.
*/

class nopoly
{
    double[] A; // pointer to an array of doubles

    public nopoly(double[] B) {A=B;} // constructor accepts external pointer.

    // function to determine if all elements of A are positive (>0)
    public boolean allpositive()
    {
	boolean ax = true; // default answer
	for(int i=0;i<A.length && ax;i++) if (A[i]<=0) ax = false;
	return ax;
    }// all positive

    // function to check if all elements of A are whole numbers (2.0, 4.0, etc)
    public boolean allints()
    {
	boolean ax = true;
	for(int i=0;i<A.length && ax;i++) if (A[i] != (int)A[i]) ax=false;
	return ax;
    }

    // function to return the *index* of the largest double in A, -1 if
    // error
    public int largest()
    {
	if (A==null || A.length==0) return -1;
	int maxi = 0; // index of largest number found so far
	for(int i=1;i<A.length;i++) if (A[i]>A[maxi]) maxi=i;
	return maxi;
    }
}//nopoly

/***************
Notice that the functions allpositive and allints basically use the same
algorithm.  They differ only in the boolean condition tested.  We should
be able to see that they are both instances of a much more general algorithm
to check that a certain property holds for all numbers in A.   But how
do we write this?

One way to implement the polymorphism inherent in this algorithm is to use
an interface.  An interface specifies a set of public methods that a class
must implement.  For example:

interface I
{
   void f(int x);  // these are just specifications, not actual code.
   int g();
}

class A implements I // implements means A must provide code for f and g
{
   public void f(int x) {System.out.println(x);} 
   public int g() {return 1;}
   // not very interesting, but it satisfies the requirement "implements I"

   //... other stuff in A
}

class A may contain other things, including other public methods, but it must
implement publicly the methods in the interface.  A class may implement
multiple interfaces (implements I1,I2...).

An interface allows us to ABSTRACT over a set of procedures.  In the
above example we abstract over f and g.  In the next, more useful
example, we abstract over a function that returns a boolean with the
following interface:
**************/

interface predicate  // a predicate is a function that returns true or false
{
    boolean p(double x);
}

class positive implements predicate  // test if a double is positive
{  public boolean p(double x) {return x>0;}  }

class wholenum implements predicate  // test if a double is an integer
{  public boolean p(double x) {return x==(int)x;} }


// the following class improves upon the nopoly class by adding 
// some polymorphism using the abstract predicate interface
class somepoly
{
    double[] A; // an array of doubles
    public somepoly(double[] B) {A=B;} // constructor accepts external pointer.

    // function to determine if all elements of A satisfies a given predicate:
    public boolean forall(predicate pred)
    {
	boolean ax = true;
	for(int i=0;i<A.length;i++) if (!pred.p(A[i])) ax = false;
	return ax;
    }

}

/***
The interface predicate allows us to generalize the boolean condition
inside the allpositive and allints functions of 'nopoly' into a
generic, *polymorphic* forall function.  To use this function, we need
to create objects that implement the predicate interface.  That is,
we can now declare variables of type 'predicate', as in

predicate p1;  

or as the parameter of a function

boolean forall (predicate pred)

But how do we assign (or pass) values to such variables?  There are three
ways.

1. Create classes that implement predicate, and then create instances of
those classes in the standard way.  Above the somepoly class we created
a class 'positive' and class 'wholenum', so now we can write (for example)

 somepoly N = new somepoly(A); // assume A points to an array of doubles.
 predicate pred = new wholenum();  // 'instantiates' predicate pred
 boolean b = N.forall(pred); // check if all numbers are ints
 b = N.forall(new positive());   // check if all numbers are positive

2. We can also "inline" a new class and create an instance of it 
using the following syntax:

 b = N.forall(new predicate() { public boolean p(double x) {return x<0;} });

This would check if all doubles in the array are negative.

3. Since Java 1.8 (jdk1.8), it's been possible to do the same thing
with much simpler syntax.  Whenever we have an interface that contains
a *single* declaration of some function, we can skip the steps of
creating a separate class and an instance by using a *lambda expression*
(or lambda term).  

 predicate pred = (x)->(x<0);  // same as 2. above
 N.forall( (x)->x>=0 && x<1.0 ); // returns true if all values between 0 and 1

You can also use {} in defining the body of a lambda term:

 predicate pred2 = (x) -> { System.out.println("x is "+x); return false; };

An expression (x)->x<0 is a called a "lambda term" and allows us to to
instantiate an interface quickly.  The syntax of a lambda term is
(x,y,...)->body.  x,y.. represents the parameters (arguments) of the
function and body represents what will be executed and
returned. However, the name of the function and the type of the
parameters are both inferred by the compiler.  Since the forall
function expects a predicate, (x)->x<0 is inferred to be boolean
p(double x) { return x<0; }.

Here's another example, this time requiring the use of lambda terms
with two parameters.  Given
***/
interface binop  // generic binary operator on integers:
{ int op(int x, int y); }

class testbinop
{
    // define an array of binop instantiations
    static binop[] B= {((x,y)->x+y), ((x,y)->x-y), ((x,y)->x*y), ((x,y)->x/y)};
    static void test(int x, int y)
    {
        for(int i=0;i<B.length;i++)
	    System.out.println( B[i].op(x,y) );
    }
    // calling test(8,2) will print 10, 6, 16, 4
}
// Here, B is an array of objects, each implements 'op' in a different way.


/******************
   The above code (for somepoly) used an abstract interface to allow
us to generalize over a whole class of functions.  But the code is
still not polymorphic enough.  Obviously, the code should work not
just for an array of doubles, but for arrays of any element.  Also,
note that we have not tried to improve the 'largest' function.

The next program uses a different programming language feature
called "generics" to further improve on these topics.

Interfaces and classes can be parameterized by a generic type variable.
*****************/

interface property<T>   // improved interface for predicates
{
    boolean p(T x);
}

class ispositive implements property<Double>
{  public boolean p(Double x) {return x>0;}  }

class isint implements property<Double>
{  public boolean p(Double x) {return x == (int)x.doubleValue();} }

class oddlengthstring implements property<String>
{  public boolean p(String x) {return x.length()%2==1;} }

/**********
Java requires us to instantiate generic variables with object types, so
we have to use Double, Integer, instead of double, int, etc.  Also,
although java is good at automatically converting between double and Double,
sometimes you need to call x.doubleValue() to extract the numerical value
from the object.

To generalize the largest function, a type variable T is not enough,
for not all types define the operations <, <=, >, etc.  We need to be
able to restrict T.  Java contains a built-in generic
interface of the form:

interface Comparable<T>
{
   int compareTo(T x);
}

When implementing different compareto functions, we need to make sure that
a.compareTo(b)<0 if a is "less than" b, ==0 if "equal" to b and >0 if "greater
than" b.  Here, a and b are objects of type Comparable<T>.

Java's built-in classes Double, Integer, String, and many others, all 
implement this interface.  For example, Strings are compared by alphabetical
order.  We can also create our own.  The following fraction class represents
fractions (rational numbers) such as 2/3 using numerator and denominator:
************/
class fraction implements Comparable<fraction> 
{
    int num;  // numerator
    int denom=1; // denominator
    public fraction(int n, int d) { num=n;  if (d!=0) denom=d;}
    public int compareTo(fraction other)
    { return num*other.denom - denom*other.num; }    
    public String toString() { return num+"/"+denom; } // for printing
}// my own Comparable class

class morepoly<TY extends Comparable<TY>>
{
    TY[] A; // an array of elements of type TY
    public morepoly(TY[] B) {A=B;}

    public boolean forall(property<TY> pred)
    {
	boolean ax = true;
	for(int i=0;i<A.length && ax;i++) if (!pred.p(A[i])) ax = false;
	return ax;
    }
    public boolean exists(property<TY> pred)
    {
        return !forall((x)->!pred.p(x));
    }
    // in predicate logic, exists x.P(x) == !forall x.!P(x);

    public int largest()
    {
	if (A==null || A.length==0) return -1;
	int maxi = 0; // index of largest number found so far
	for(int i=1;i<A.length;i++) 
	    if (A[i].compareTo(A[maxi])>0) maxi=i;
	return maxi;
    }
    public TY largestval() {return A[largest()];}// returns value, not index
}//morepoly


public class polymorphism
{
  public static void main(String[] argv)
  {
     String[] S = {"ab","abb","ba","ca","bca"};
     Double[] T = {3.1, 6.5, 1.333, 4.9, 2.0};
     morepoly<String> M = new morepoly<String>(S);
     morepoly<Double> N = new morepoly<Double>(T);
     System.out.println(M.forall(new oddlengthstring())); // false
     System.out.println(M.largestval());                  // ca
     System.out.println(N.forall(new ispositive()));      // true
     System.out.println(N.largestval());                  // 6.5
     System.out.println(M.forall((s)->s!=null));          // true
     System.out.println(N.exists((x)->x<2));              // true

     fraction[] F = {new fraction(1,2),new fraction(2,3),new fraction(1,3)};
     morepoly<fraction> R = new morepoly<fraction>(F);
     System.out.println(R.largestval()); // prints 2/3
     fraction quarter = new fraction(1,4), one = new fraction(1,1);
     boolean b = R.forall( (x)->quarter.compareTo(x)<0 );
     System.out.println("are all fractions in F greater than 1/4? "+b); //true
     b = R.exists( (x)->x.compareTo(one)>0 );
     System.out.println("is there a fraction in F greater than 1? "+b); //false
  }
}//main class


/// another user-defined class that implements Comparable<T>:
class account
{
    double balance; // balance of account in dollars
    // ... boring details skiped ...

    // compare accounts based on balance rounded off to nearest cent:
    public int compareTo(account other)
    {  return (int)(balance*100+0.5) - (int)(other.balance*100 + 0.5); }
    // this will return 0 if balances are same, >0 if greater, etc.
}// user defined Comparable class

// ASIDE:
// Finally, note that the way compareTo is defined satisfies the property
// of transitivity: if x==y and y==z then x==z.  If, on the other hand,we
// had written the return line as:
// return (int) Math.abs(balance*100 - other.balance*100 +0.5);
// then compareTo would not be transitive.  2.4 cents would be considered
// "equal" to 2.8 cents, and 2.8 cents would be considered "equal" to
// 3.2 cents, but 2.4 cents would not be considered equal to 3.2 cents.
// Mistakes like this are never caught by the compiler but can lead to
// serious errors because they can be difficult to detect until it's too late.

// Also, I've defined my own predicate and property interfaces so I can
// explain the principals in detail.  But java also have built-in interfaces
// of this kind that you can use in java.util.function.  For example,
// the java.util.function.Predicate<T> interface is essentially the
// same as our 'property<T>' interface, but the internal function is called
// 'test' instead of 'p'.