/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.commons.math4.legacy.analysis.solvers;
  
  import org.apache.commons.math4.legacy.analysis.FunctionUtils;
  import org.apache.commons.math4.legacy.analysis.MonitoredFunction;
  import org.apache.commons.math4.legacy.analysis.QuinticFunction;
  import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
  import org.apache.commons.math4.legacy.analysis.differentiation.DerivativeStructure;
  import org.apache.commons.math4.legacy.analysis.differentiation.UnivariateDifferentiableFunction;
  import org.apache.commons.math4.legacy.analysis.function.Constant;
  import org.apache.commons.math4.legacy.analysis.function.Inverse;
  import org.apache.commons.math4.legacy.analysis.function.Sin;
  import org.apache.commons.math4.legacy.analysis.function.Sqrt;
  import org.apache.commons.math4.legacy.exception.NoBracketingException;
  import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException;
  import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
  import org.apache.commons.math4.core.jdkmath.JdkMath;
  import org.junit.Assert;
  import org.junit.Test;
  
  /**
   * Test case for {@link BrentSolver Brent} solver.
   * Because Brent-Dekker is guaranteed to converge in less than the default
   * maximum iteration count due to bisection fallback, it is quite hard to
   * debug. I include measured iteration counts plus one in order to detect
   * regressions. On average Brent-Dekker should use 4..5 iterations for the
   * default absolute accuracy of 10E-8 for sinus and the quintic function around
   * zero, and 5..10 iterations for the other zeros.
   *
   */
  public final class BrentSolverTest {
      @Test
      public void testSinZero() {
          // The sinus function is behaved well around the root at pi. The second
          // order derivative is zero, which means linar approximating methods will
          // still converge quadratically.
          UnivariateFunction f = new Sin();
          double result;
          UnivariateSolver solver = new BrentSolver();
          // Somewhat benign interval. The function is monotone.
          result = solver.solve(100, f, 3, 4);
          // System.out.println(
          //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
          Assert.assertEquals(result, JdkMath.PI, solver.getAbsoluteAccuracy());
          Assert.assertTrue(solver.getEvaluations() <= 7);
          // Larger and somewhat less benign interval. The function is grows first.
          result = solver.solve(100, f, 1, 4);
          // System.out.println(
          //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
          Assert.assertEquals(result, JdkMath.PI, solver.getAbsoluteAccuracy());
          Assert.assertTrue(solver.getEvaluations() <= 8);
      }
  
      @Test
      public void testQuinticZero() {
          // The quintic function has zeros at 0, +-0.5 and +-1.
          // Around the root of 0 the function is well behaved, with a second derivative
          // of zero a 0.
          // The other roots are less well to find, in particular the root at 1, because
          // the function grows fast for x>1.
          // The function has extrema (first derivative is zero) at 0.27195613 and 0.82221643,
          // intervals containing these values are harder for the solvers.
          UnivariateFunction f = new QuinticFunction();
          double result;
          // Brent-Dekker solver.
          UnivariateSolver solver = new BrentSolver();
          // Symmetric bracket around 0. Test whether solvers can handle hitting
          // the root in the first iteration.
          result = solver.solve(100, f, -0.2, 0.2);
          //System.out.println(
          //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
          Assert.assertEquals(result, 0, solver.getAbsoluteAccuracy());
          Assert.assertTrue(solver.getEvaluations() <= 3);
          // 1 iterations on i586 JDK 1.4.1.
          // Asymmetric bracket around 0, just for fun. Contains extremum.
          result = solver.solve(100, f, -0.1, 0.3);
          //System.out.println(
          //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
          Assert.assertEquals(result, 0, solver.getAbsoluteAccuracy());
          // 5 iterations on i586 JDK 1.4.1.
          Assert.assertTrue(solver.getEvaluations() <= 7);
          // Large bracket around 0. Contains two extrema.
          result = solver.solve(100, f, -0.3, 0.45);
          //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 0, solver.getAbsoluteAccuracy());
         // 6 iterations on i586 JDK 1.4.1.
         Assert.assertTrue(solver.getEvaluations() <= 8);
         // Benign bracket around 0.5, function is monotonous.
         result = solver.solve(100, f, 0.3, 0.7);
         //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
         // 6 iterations on i586 JDK 1.4.1.
         Assert.assertTrue(solver.getEvaluations() <= 9);
         // Less benign bracket around 0.5, contains one extremum.
         result = solver.solve(100, f, 0.2, 0.6);
         // System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 10);
         // Large, less benign bracket around 0.5, contains both extrema.
         result = solver.solve(100, f, 0.05, 0.95);
         //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 11);
         // Relatively benign bracket around 1, function is monotonous. Fast growth for x>1
         // is still a problem.
         result = solver.solve(100, f, 0.85, 1.25);
         //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 11);
         // Less benign bracket around 1 with extremum.
         result = solver.solve(100, f, 0.8, 1.2);
         //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 11);
         // Large bracket around 1. Monotonous.
         result = solver.solve(100, f, 0.85, 1.75);
         //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 13);
         // Large bracket around 1. Interval contains extremum.
         result = solver.solve(100, f, 0.55, 1.45);
         //System.out.println(
         //    "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 10);
         // Very large bracket around 1 for testing fast growth behaviour.
         result = solver.solve(100, f, 0.85, 5);
         //System.out.println(
        //     "Root: " + result + " Evaluations: " + solver.getEvaluations());
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(solver.getEvaluations() <= 15);
 
         try {
             result = solver.solve(5, f, 0.85, 5);
             Assert.fail("Expected TooManyEvaluationsException");
         } catch (TooManyEvaluationsException e) {
             // Expected.
         }
     }
 
     @Test
     public void testRootEndpoints() {
         UnivariateFunction f = new Sin();
         BrentSolver solver = new BrentSolver();
 
         // endpoint is root
         double result = solver.solve(100, f, JdkMath.PI, 4);
         Assert.assertEquals(JdkMath.PI, result, solver.getAbsoluteAccuracy());
 
         result = solver.solve(100, f, 3, JdkMath.PI);
         Assert.assertEquals(JdkMath.PI, result, solver.getAbsoluteAccuracy());
 
         result = solver.solve(100, f, JdkMath.PI, 4, 3.5);
         Assert.assertEquals(JdkMath.PI, result, solver.getAbsoluteAccuracy());
 
         result = solver.solve(100, f, 3, JdkMath.PI, 3.07);
         Assert.assertEquals(JdkMath.PI, result, solver.getAbsoluteAccuracy());
     }
 
     @Test
     public void testBadEndpoints() {
         UnivariateFunction f = new Sin();
         BrentSolver solver = new BrentSolver();
         try {  // bad interval
             solver.solve(100, f, 1, -1);
             Assert.fail("Expecting NumberIsTooLargeException - bad interval");
         } catch (NumberIsTooLargeException ex) {
             // expected
         }
         try {  // no bracket
             solver.solve(100, f, 1, 1.5);
             Assert.fail("Expecting NoBracketingException - non-bracketing");
         } catch (NoBracketingException ex) {
             // expected
         }
         try {  // no bracket
             solver.solve(100, f, 1, 1.5, 1.2);
             Assert.fail("Expecting NoBracketingException - non-bracketing");
         } catch (NoBracketingException ex) {
             // expected
         }
     }
 
     @Test
     public void testInitialGuess() {
         MonitoredFunction f = new MonitoredFunction(new QuinticFunction());
         BrentSolver solver = new BrentSolver();
         double result;
 
         // no guess
         result = solver.solve(100, f, 0.6, 7.0);
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         int referenceCallsCount = f.getCallsCount();
         Assert.assertTrue(referenceCallsCount >= 13);
 
         // invalid guess (it *is* a root, but outside of the range)
         try {
           result = solver.solve(100, f, 0.6, 7.0, 0.0);
           Assert.fail("a NumberIsTooLargeException was expected");
         } catch (NumberIsTooLargeException iae) {
             // expected behaviour
         }
 
         // bad guess
         f.setCallsCount(0);
         result = solver.solve(100, f, 0.6, 7.0, 0.61);
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(f.getCallsCount() > referenceCallsCount);
 
         // good guess
         f.setCallsCount(0);
         result = solver.solve(100, f, 0.6, 7.0, 0.999999);
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertTrue(f.getCallsCount() < referenceCallsCount);
 
         // perfect guess
         f.setCallsCount(0);
         result = solver.solve(100, f, 0.6, 7.0, 1.0);
         Assert.assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
         Assert.assertEquals(1, solver.getEvaluations());
         Assert.assertEquals(1, f.getCallsCount());
     }
 
     @Test
     public void testMath832() {
         final UnivariateFunction f = new UnivariateFunction() {
                 private final UnivariateDifferentiableFunction sqrt = new Sqrt();
                 private final UnivariateDifferentiableFunction inv = new Inverse();
                 private final UnivariateDifferentiableFunction func
                     = FunctionUtils.add(FunctionUtils.multiply(new Constant(1e2), sqrt),
                                         FunctionUtils.multiply(new Constant(1e6), inv),
                                         FunctionUtils.multiply(new Constant(1e4),
                                                                FunctionUtils.compose(inv, sqrt)));
 
                 @Override
                 public double value(double x) {
                     return func.value(new DerivativeStructure(1, 1, 0, x)).getPartialDerivative(1);
                 }
             };
 
         BrentSolver solver = new BrentSolver();
         final double result = solver.solve(100, f, 1, 1e30, 1 + 1e-10);
         Assert.assertEquals(804.93558250, result, solver.getAbsoluteAccuracy());
     }
 }