/*
 * Data Structures - Assignment 2
 * Polynomials
 */
package datastructuresassignment2;

/**
 *
 * @author Randal Adamson 10191613 and Luke Spartalis 10194177
 */
public class Polynomial {

    final static private int mantissa = 52;
    final static private double epsilon = Math.pow(2.0, -mantissa);
    private double coefficient = 0.0;
    private int power = 0;
    private Polynomial successor = null;

    public Polynomial(double coefficient, int power) {
        if (Double.isNaN(coefficient)) {
            return;
        }
        if (Math.abs(coefficient) < epsilon) {
            return;
        }
        if (power < 0) {
            return;
        }
        this.coefficient = coefficient;
        this.power = power;
    }

    /* conditions
    this(X) => sum(coefficient(i)*X^i:for(i=degree;i>=0;i--)) && X^0=1
    this.degree()==this.power==highestPower
    this.highestPoweredCoefficient==this.coefficient
    this.successor!=null links to terms whose powers uniquely decrease
    Polynomial(0.0,0)=(coefficient=0.0,power=0,successor=null)==0.0
    if (coefficient==NaN) coefficient=0.0
    if (abs(coefficient)<epsilon)) coefficient=0.0
    if (power<0) power=0
    if (this.degree()==0) abs(coefficient(0))>=0.0
    if (this.degree()>0) abs(coefficient(i))>=epsilon for all i>=0
     */

    // cdd Method
    // validates the parameters before changing the state of polynomial
    // to reflect the addition of the term:
    // coefficient t X x power
    private static void add(Polynomial polynomial, double coefficient, int power) {
        /*students #1*/
        if (polynomial == null) return;
        if (Math.abs(coefficient) < epsilon) coefficient = 0.0;
        if (coefficient == 0.0) return;
        if (power < 0) return;

        // our part:
        if (polynomial.coefficient == 0.0)
        {
            polynomial.coefficient = coefficient;
            polynomial.power = power;
            return;
        }

        if (polynomial.power == power)
        {
            // case 3
            polynomial.coefficient += coefficient;
            if (Math.abs(polynomial.coefficient) < epsilon)
            polynomial.coefficient = 0.0;
            //subcase 3.1 and 3.2
            if (polynomial.coefficient != 0.0 || polynomial.power == 0) return;
            if (polynomial.successor == null)
            {
                polynomial.power = 0;
                return;
            }
            polynomial.coefficient = polynomial.successor.coefficient;
            polynomial.power = polynomial.successor.power;
            polynomial.successor = polynomial.successor.successor;
            return;
        }

        //
        Polynomial previous = null;
        Polynomial traverser = polynomial;

        // search the SLL to find a suitable place in the SLL
        while (traverser != null)
        {
            if (traverser.power <= power) break;
            previous = traverser;
            traverser = traverser.successor;
        }

        //
        if (previous == null)
        {
            Polynomial term = new Polynomial(0.0,0);
            term.coefficient = polynomial.coefficient;
            term.power = polynomial.power;
            term.successor = polynomial.successor;
            polynomial.coefficient = coefficient;
            polynomial.power = power;
            polynomial.successor = term;
            return;
        }
        //
        if (traverser == null || traverser.power < power)
        {
            Polynomial term = new Polynomial(0.0,0);
            term.coefficient = coefficient;
            term.power = power;
            term.successor = traverser;
            previous.successor = term;
            return;
        }
        coefficient += traverser.coefficient;
        if (Math.abs(coefficient) < epsilon) coefficient = 0.0;
        if (coefficient == 0.0)
            previous.successor = traverser.successor;
        else
            traverser.coefficient = coefficient;
    }

    // cardinality Method
    // yields the number of terms in this polynomial
    final public int cardinality() {
        int count = 1;

        Polynomial traverser = this.successor;

        while (traverser != null) {
            count++;
            traverser = traverser.successor;
        }
        return count;
    }

    // clone Method
    // yields a link-by-link copy of this polynomial
    final public Polynomial clone() {
        Polynomial result = new Polynomial(0.0, 0);

        result.coefficient = this.coefficient;

        result.power = this.power;

        Polynomial traverserThis = this;

        Polynomial traverserResult = result;

        while (traverserThis.successor != null) {
            traverserResult.successor = new Polynomial(0.0, 0);
            traverserThis = traverserThis.successor;
            traverserResult = traverserResult.successor;
            traverserResult.coefficient = traverserThis.coefficient;
            traverserResult.power = traverserThis.power;
        }

        return result;
    }

    // coefficient Method
    // yields the coefficient of the term with that power
    // in this polynomial
    final public double coefficient(int power) {
        if (power < 0) {
            return 0.0;
        }

        Polynomial traverser = this;

        do {
            if (traverser.power < power) {
                return 0.0;
            }
            if (traverser.power == power) {
                return traverser.coefficient;
            }
            traverser = traverser.successor;
        } while (traverser != null);

        return 0.0;
    }

    // composite Method
    // validates the parameter and yields the polynomial result
    // for the operation: this(that(x))
            /**
         * validates the parameter and yields the polynomial result
         * for the operation: this(that(x))
         *
         * @param Polynomial that
         *
         * @return Polynomial outcome
         */
        final public Polynomial composite(Polynomial that) {
            /*students #2*/
            if (that == null) {
                return null;
            }

            // setup a clone for this Polynomial
            Polynomial thisClone = this.clone();
            // setup a clone for that Polynomial
            Polynomial thatClone = that.clone();
            // setup a provisional (temporary) Polynomial
            Polynomial provisional = new Polynomial(0.0, 0);
            // store the outcome (result) in this Polynomial
            Polynomial outcome = new Polynomial(0.0, 0);

            // formula is: this(that) = this.coeff(n).times(that(n)) + this.coeff(n-1).times(that(n-1))

            while(thisClone != null)
            {
                // expand this power by the coefficient
                for( int i = 1; i <= thisClone.power; i++)
                {
                    provisional.coefficient = thisClone.coefficient;
                    provisional = provisional.times(thatClone);
                }
                // add to the outcome
                outcome = outcome.plus(provisional);
                // clear the provisional for the next loop
                provisional = new Polynomial(0.0,0);
                // move to the next element
                thisClone = thisClone.successor;
            }


            return outcome;
        }


    // degree Method
    // yields the degree (highest power) of this polynomial
    final public int degree() {
        return this.power;
    }

    // differentiate method
    // yields the polynomial result for the operation:
    // d/dx(this(x))
    final public Polynomial differentiate() {
        /*students #3*/
        // setup traverser Polynomial
        Polynomial traverser = this;
        // setup provisional (temporary) Polynomial
        Polynomial provisional = new Polynomial(0.0,0);
        // setup outcome (result) Polynomial
        Polynomial outcome = new Polynomial(0.0,0);

        if (this.power == 0)
        {
            return new Polynomial(0.0,0);
        }
        else
        {
            // search the Polynomial with traverser
            while (traverser!=null)
            {
                // Power > 1
                if(traverser.power >1)
                {
                    provisional.coefficient = traverser.coefficient * traverser.power;
                    provisional.power = traverser.power - 1;

                }
                // Power = 1
                if(traverser.power ==1)
                {
                    provisional.coefficient = traverser.coefficient;
                    provisional.power = 0;
                }
                // Power = 0
                if(traverser.power ==0)
                {
                    provisional.coefficient =0.0;
                    provisional.power =0;
                }
                // move the traverser to the next element
                traverser = traverser.successor;
                // add the provisional to the ouctome Polynomial
                outcome = outcome.plus(provisional);
            }
        }
        return outcome;
    }

    // dividedBy method
    // validates the parameter and yields the quotient and the
    // remainder (as a 2-array of polynomials) for
    // the operation: this(x) / that(x)
    final public Polynomial[] dividedBy(Polynomial that) {
        if (that == null) {
            return null;
        }
        if (that.coefficient == 0.0) {
            return null;
        }






        // Student Part


        double powerMaxM = that.powerMax();

       int provisionalpower = (int) (this.degree() - powerMaxM);

        // setup a provisional (temporary) Polynomial

//         setup two doubles used to divide the quotient coefficient
        Polynomial quotient = new Polynomial(0.0, provisionalpower);
        Polynomial reminder = this.clone();


        for (int i = this.degree(); i >= powerMaxM; i--) {

            quotient.coefficient = reminder.coefficient / that.coefficient;


            reminder = this.minus(that.times(quotient));



        }


        // end Student Part

        Polynomial[] result = new Polynomial[2];
        result[0] = quotient;
        result[1] = reminder;
        return result;
    }



    // equals Method
    // yields true when this polynomial is a hard-copy
    // of that polynomial; and false otherwise
    final public boolean equals(Polynomial that) {
        if (that == null) {
            return false;
        }

        if (this.coefficient != that.coefficient) {
            return false;
        }

        if (this.power != that.power) {
            return false;
        }

        if (this.successor == null && that.successor == null) {
            return true;
        }

        if (this.successor == null && that.successor != null) {
            return false;
        }

        if (this.successor != null && that.successor == null) {
            return false;
        }

        return this.successor.equals(that.successor);
    }

    // evaluate Method
    // validates the parameter and yields the double result
    // for the operation this(variable).
    final public double evaluate(double variable) {
        /*students #5 */
        if (Double.isNaN(variable)) {
            variable = 0.0;
        }
        if (Math.abs(variable) < epsilon) {
            variable = 0.0;
        }
        double value = 0.0;

        // Student Part

        // Setup a Polynomial for this Clone (pointer)
        Polynomial thisClone = this.clone();
        // search through this clone
        while(thisClone !=null)
        {
            // Power > 0
            if(thisClone.power > 0)
            {
                // append the clone's coeffeicient multiplied by the power
                value += thisClone.coefficient * Math.pow(variable, thisClone.power);
            }
            // Power is not > 0
            else
            {
                // append the clone's coefficient
                value += thisClone.coefficient;
            }
            // move the clone to the successor for the loop
            thisClone = thisClone.successor;
        }

        // End Student Part

        return value;
    }

    // integrate Method
    // yields the polynomial result for the operation
    // [ this(x) x dx
    final public Polynomial integrate() {
        /*students #6*/
        if (this.coefficient == 0.0) {
            return new Polynomial(0.0, 0);
        }
        Polynomial result = this.clone();

        // Student Part

        // Setup outcome (answer) Polynomial
        Polynomial outcome = new Polynomial(0.0, 0);
        // Setup provisional (temporary) Polynomial
        Polynomial provisional = new Polynomial(0.0, 0);

        while(result!=null)
        {
            // add 1 to the power for provisional
            provisional.power = result.power + 1;
            // make provisional coefficient equal
            // the result coefficient divided by
            // the new provisional power
            // provisional.coefficient = result.coefficient / provisional.power;
            provisional.coefficient = result.coefficient / (result.power +1);
            // move the result to the successor element
            result = result.successor;
            // add the provisional to the outcome and loop
            outcome = outcome.plus(provisional);
        }

        // End Student Part

        return result;
    }

    // minus Method
    // yields a hard-copy of the result of this polynomial
    // subtract that polynomial
    final public Polynomial minus(Polynomial that) {
        if (that == null) {
            return null;
        }

        if (this.equals(that)) {
            return new Polynomial(0.0, 0);
        }

        Polynomial result = this.clone();

        if (that.coefficient == 0.0) {
            return result;
        }

        Polynomial traverser = that;

        do {
            add(result, -traverser.coefficient, traverser.power);
            traverser = traverser.successor;
        } while (traverser != null);

        return result;
    }

    // plus Method
    // yields a hard-copy of the result of this polynomial
    // and that polynomial
    final public Polynomial plus(Polynomial that) {
        if (that == null) {
            return null;
        }

        if (this.coefficient == 0.0) {
            return that.clone();
        }

        Polynomial result = this.clone();

        if (that.coefficient == 0.0) {
            return result;
        }

        Polynomial traverser = that;

        do {
            add(result, traverser.coefficient, traverser.power);
            traverser = traverser.successor;
        } while (traverser != null);

        return result;
    }

    // powerMax Method
    // yields the highest power of this polynomial by traversing all
    // the terms
    final public int powerMax() {
        int max = Integer.MIN_VALUE;

        Polynomial traverser = this;

        do {
            if (max < traverser.power) {
                max = traverser.power;
            }

            traverser = traverser.successor;

        } while (traverser != null);

        return max;
    }

    // powerMin Method
    // yields the least power of this polynomial by traversing all
    // the terms
    final public int powerMin() {
        int min = Integer.MAX_VALUE;

        Polynomial traverser = this;

        do {
            if (min > traverser.power) {
                min = traverser.power;
            }
            traverser = traverser.successor;
        } while (traverser != null);

        return min;
    }

    // times Method
    // validates the parameter and yields the polynomial result
    // for the operation this(x) x that(x)
    final public Polynomial times(Polynomial that) {
        /*students #7*/
        if (that == null)
        {
            return null;
        }

        Polynomial result = new Polynomial(0.0, 0);

        // Student Part

        // Setup new polynomial for this clone
        Polynomial thisClone = this.clone();
        // Setup new polynomial for that clone
        Polynomial thatClone = that.clone();
        // Setup new provisional (temporary) polynomial
        Polynomial provisional = new Polynomial(0.0, 0);

        // search through this clone
	while (thisClone != null)
	{
            // search through that clone
            while (thatClone != null)
            {
                // Either clone's coefficient is equal to zero (0)
                if (thisClone.coefficient == 0.0 || thatClone.coefficient == 0.0)
                {
                    // make the provisional coefficient zero
                    provisional.coefficient = 0.0;
                    // make the provisional power zero
                    provisional.power = 0;
                }
                // otherwise:
                else
                {
                    // make the provisional coefficient equal this clone's coefficient
                    // multiplied by that clone's coefficient
                    provisional.coefficient = thisClone.coefficient * thatClone.coefficient;
                    // make the provisional power equal to this clone's power
                    // multiplied by that clone's power
                    provisional.power = thisClone.power + thatClone.power;
                }
                // add the provisional to the result
                result = result.plus(provisional);
                // make that clone it's successor
                thatClone = thatClone.successor;
            }
            // clear that clone for next loop
            thatClone = that.clone();
            // make this clone it's successor
            thisClone = thisClone.successor;
	}

        // End Student Part

        return result;
        }

//    @Override
    // toString Method
    // yields a String representation of all the terms
    // of this polynomial
    final public String toString() {
        String string = "" + this.coefficient + (this.power == 0 ? "" : "*X^" + this.power);

        Polynomial traverser = this.successor;

        while (traverser != null) {
            string += (traverser.coefficient > 0.0 ? "+" : "")
                    + traverser.coefficient
                    + (traverser.power == 0 ? "" : "*X^"
                    + traverser.power);
            traverser = traverser.successor;
        }

        return string;
    }

}