package freegraph;

/****
 * class with static functions to find solutions to equations using
 * either Newton's Method or Bisection techniques.
 */
public class EquationSolver
{
    /****
     * maximum iterations for various loops to prevent falling into infinite
     * loops
     */
    private static int MAX_ITERATIONS = 200;

    /***
     * maximum number to repeats in the repeat newton method
     */
    private static int MAX_NEWTON_REPEATS = 10;

    /****
     * internal method used to round a double (value) to the nearest roundX.
     * @param roundX    "round to the nearest" roundX
     * @param value the value to round
     * @return
     * value rounded to the nearest roundX
     */
    private static double roundTo(double roundX, double value)
    {
        return Math.rint(value / roundX) * roundX;
    }

    /*****
     * attempts to solve the equation expr1=exrp2 using Newton's method and
     * repeatedly moving to different starting points looking for an answer.
     * @param expr1 the left side of the equation.
     * @param expr2 the rigth side of the equation.
     * @param value the x value.
     * @param tolerance the tolerance of the solution (how close to the actual
     * answer must the result be)
     * @param slopeLimit    the difference in x values used in estimating the
     * slope of the line
     * @param solvefor  the character of the equation to solve for
     * @return a solution to the equation expr1=expr2.
     * @throws NoSolutionException if no solution can be found
     */
    public static double repeatNewton(
        ExpressionEvaluator expr1, ExpressionEvaluator expr2,
        double value, double tolerance, double slopeLimit,
        char solveFor) throws NoSolutionException
    {
        double x = value;
        double orgx = x;
        int c = 0;
        do
        {
            try
            {
                return newton(expr1, expr2, x, tolerance, slopeLimit, solveFor);
            }
            catch (NoSolutionException e)
            {
                x = (orgx + Math.pow(2, c / 2)) * ( (c % 2 * 2) - 1);
            }
        }
        while (c++ < MAX_NEWTON_REPEATS);

        if (orgx != 0)
        {
            c = MAX_NEWTON_REPEATS;
            do
            {
                try
                {
                    return newton(expr1, expr2, x, tolerance, slopeLimit,
                                  solveFor);
                }
                catch (NoSolutionException e)
                {
                    x = (orgx + 2 / (double) (c) * ( (c % 2 * 2) - 1));
                }
            }
            while (c-- > 1);
        }
        orgx = 0;
        c = MAX_NEWTON_REPEATS * 10;
        do
        {
            try
            {
                return newton(expr1, expr2, x, tolerance, slopeLimit, solveFor);
            }
            catch (NoSolutionException e)
            {
                x = (orgx + 2 / (double) (c) * ( (c % 2 * 2) - 1));
            }
        }
        while (c-- > 1);
        throw new NoSolutionException("No solution found.");
    }

    /****
     * attempts to zero in on a solution using Newtons equation solving
     * technique.
     * @param expr1 the left side of the equation.
     * @param expr2 the rigth side of the equation.
     * @param value the x value.
     * @param tolerance the tolerance of the solution (how close to the actual
     * answer must the result be)
     * @param slopeLimit    the difference in x values used in estimating the
     * slope of the line
     * @param solvefor  the character of the equation to solve for
     * @return a solution to the equation expr1=expr2.
     * @throws NoSolutionException if no solution can be found
     */
    public static double newton(
        ExpressionEvaluator expr1, ExpressionEvaluator expr2,
        double value, double tolerance, double slopeLimit,
        char solveFor) throws NoSolutionException
    {
        int c = 0;
        do
        {
            try
            {
                value = xintercept(expr1, expr2, value, tolerance,
                                   slopeLimit, solveFor);
            }
            catch (SolutionFound x)
            {
                return roundTo(tolerance, x.value);
            }
        }
        while (c++ < MAX_ITERATIONS);
        throw new NoSolutionException("No solution found.");
    }

    /*****
     * attempts to solve the equation expr1=exrp2 using bisection
     * repeatedly by moving trying various starting points.
     * @param expr1 the left side of the equation.
     * @param expr2 the rigth side of the equation.
     * @param low   the low value to start in the bisection
     * @param high  the high value to start in the bisection
     * @param tolerance the tolerance of the solution (how close to the actual
     * answer must the result be)
     * @param solvefor  the character of the equation to solve for
     * @return a solution to the equation expr1=expr2.
     * @throws NoSolutionException if no solution can be found
     */
    public static double repeatBisection(
        ExpressionEvaluator expr1, ExpressionEvaluator expr2,
        double low, double high, double tolerance, char solveFor) throws
        NoSolutionException
    {
        int iterations = 200;
        double dx = (high - low) / iterations;
        int cnt = 0;
        try
        {
            return bisection(expr1, expr2, low, high, tolerance, solveFor);
        }
        catch (Exception e)
        {}
        do
        {
            try
            {
                return bisection(expr1, expr2, low + cnt * dx,
                                 low + (cnt + 1) * dx,
                                 tolerance, solveFor);
            }
            catch (Exception e)
            {
                high = high - dx;
            }
        }
        while (cnt++ <= iterations);
        throw new NoSolutionException("No solution found.");
    }

    /*****
     * attempts to solve the equation expr1=exrp2 using bisection
     * looking between low and high
     * @param expr1 the left side of the equation.
     * @param expr2 the rigth side of the equation.
     * @param low   the low value to start in the bisection
     * @param high  the high value to start in the bisection
     * @param tolerance the tolerance of the solution (how close to the actual
     * answer must the result be)
     * @param solvefor  the character of the equation to solve for
     * @return a solution to the equation expr1=expr2.
     * @throws NoSolutionException if no solution can be found
     */
    public static double bisection(
        ExpressionEvaluator expr1, ExpressionEvaluator expr2,
        double low, double high, double tolerance, char solveFor) throws
        NoSolutionException
    {
        double equValueLow;
        double equValueHigh;
        double equValueMid;
        double mid;
        do
        {
            mid = low + (high - low) / 2;
            expr1.getVariables().setValue(solveFor, low);
            expr2.getVariables().setValue(solveFor, low);
            equValueLow = expr1.evaluate() - expr2.evaluate();
            if (Math.abs(equValueLow) < tolerance / 10)
            {
                return roundTo(tolerance, low);
            }
            expr1.getVariables().setValue(solveFor, mid);
            expr2.getVariables().setValue(solveFor, mid);
            equValueMid = expr1.evaluate() - expr2.evaluate();
            if (Math.abs(equValueMid) < tolerance / 10)
            {
                return roundTo(tolerance, mid);
            }
            if (equValueMid * equValueLow < 0)
            {
                high = mid;
                continue;
            }
            expr1.getVariables().setValue(solveFor, high);
            expr2.getVariables().setValue(solveFor, high);
            equValueHigh = expr1.evaluate() - expr2.evaluate();
            if (Math.abs(equValueHigh) < tolerance / 10)
            {
                return roundTo(tolerance, high);
            }
            low = mid;
        }
        while (Math.abs(low - high) > tolerance / 100);
        throw new NoSolutionException("No solution found.");
    }

    /*****
     * returns the X-Intercept of the tangent to the equation
     * expr1=expr2 at value. (This method is used by the Newtonian solving
     * methods)
     * @param expr1 the left side of the equation.
     * @param expr2 the rigth side of the equation.
     * @param tolerance the tolerance of the solution (how close to the actual
     * answer must the result be)
     * @param slopeLimit    the difference in x values used in estimating the
     * slope of the line
     * @param solvefor  the character of the equation to solve for
     * @throws SolutionFound is the xintercept is a solution to the equation
     * expr1=expr2 within tolerance.
     * @return  the xintercept
     */
    public static double xintercept(
        ExpressionEvaluator expr1, ExpressionEvaluator expr2,
        double value, double tolerance, double slopeLimit,
        char solveFor) throws SolutionFound
    {
        expr1.getVariables().setValue(solveFor, value);
        expr2.getVariables().setValue(solveFor, value);
        double y = expr1.evaluate() - expr2.evaluate();
        if (Math.abs(y) <= tolerance)
        {
            throw new SolutionFound(value);
        }
        expr1.getVariables().setValue(solveFor, value + slopeLimit);
        expr2.getVariables().setValue(solveFor, value + slopeLimit);
        double m = ( (expr1.evaluate() - expr2.evaluate()) - y) / slopeLimit;
        return value - y / m;
    }

    /***
     * internally used exception used by xintercept method to indicate that a
     * solution was found when the xintercept was calculated.
     */
    private static class SolutionFound extends Exception
    {
        double value;
        SolutionFound(double value)
        {
            this.value = value;
        }
    }

    public static void main(String args[])
    {

        double x = 0;
        double orgx = x;
        int c = MAX_NEWTON_REPEATS * 2;
        do
        {
//            try
//            {
//                return newton(expr1, expr2, x, tolerance, slopeLimit, solveFor);
//            }
//            catch (NoSolutionException e)
//            {
            System.out.println(x);
            x = (orgx + 2 / (double) (c) * ( (c % 2 * 2) - 1));
//            }
        }
        while (c-- > 1);
    }

}