content: /*
   * Copyright (C) 2012 The Android Open Source Project
   *
   * Licensed 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 android.util;
  
  /**
   * Performs spline interpolation given a set of control points.
   * @hide
   */
  public abstract class Spline {
  
      /**
       * Interpolates the value of Y = f(X) for given X.
       * Clamps X to the domain of the spline.
       *
       * @param x The X value.
       * @return The interpolated Y = f(X) value.
       */
      public abstract float interpolate(float x);
  
      /**
       * Creates an appropriate spline based on the properties of the control points.
       *
       * If the control points are monotonic then the resulting spline will preserve that and
       * otherwise optimize for error bounds.
       */
      public static Spline createSpline(float[] x, float[] y) {
          if (!isStrictlyIncreasing(x)) {
              throw new IllegalArgumentException("The control points must all have strictly "
                      + "increasing X values.");
          }
  
          if (isMonotonic(y)) {
              return createMonotoneCubicSpline(x, y);
          } else {
              return createLinearSpline(x, y);
          }
      }
  
      /**
       * Creates a monotone cubic spline from a given set of control points.
       *
       * The spline is guaranteed to pass through each control point exactly.
       * Moreover, assuming the control points are monotonic (Y is non-decreasing or
       * non-increasing) then the interpolated values will also be monotonic.
       *
       * This function uses the Fritsch-Carlson method for computing the spline parameters.
       * http://en.wikipedia.org/wiki/Monotone_cubic_interpolation
       *
       * @param x The X component of the control points, strictly increasing.
       * @param y The Y component of the control points, monotonic.
       * @return
       *
       * @throws IllegalArgumentException if the X or Y arrays are null, have
       * different lengths or have fewer than 2 values.
       * @throws IllegalArgumentException if the control points are not monotonic.
       */
      public static Spline createMonotoneCubicSpline(float[] x, float[] y) {
          return new MonotoneCubicSpline(x, y);
      }
  
      /**
       * Creates a linear spline from a given set of control points.
       *
       * Like a monotone cubic spline, the interpolated curve will be monotonic if the control points
       * are monotonic.
       *
       * @param x The X component of the control points, strictly increasing.
       * @param y The Y component of the control points.
       * @return
       *
       * @throws IllegalArgumentException if the X or Y arrays are null, have
       * different lengths or have fewer than 2 values.
       * @throws IllegalArgumentException if the X components of the control points are not strictly
       * increasing.
       */
      public static Spline createLinearSpline(float[] x, float[] y) {
          return new LinearSpline(x, y);
      }
  
      private static boolean isStrictlyIncreasing(float[] x) {
          if (x == null || x.length < 2) {
              throw new IllegalArgumentException("There must be at least two control points.");
          }
          float prev = x[0];
          for (int i = 1; i < x.length; i++) {
              float curr = x[i];
              if (curr <= prev) {
                  return false;
              }
              prev = curr;
          }
          return true;
      }
  
      private static boolean isMonotonic(float[] x) {
          if (x == null || x.length < 2) {
              throw new IllegalArgumentException("There must be at least two control points.");
          }
          float prev = x[0];
          for (int i = 1; i < x.length; i++) {
              float curr = x[i];
              if (curr < prev) {
                  return false;
              }
              prev = curr;
          }
          return true;
      }
  
      public static class MonotoneCubicSpline extends Spline {
          private float[] mX;
          private float[] mY;
          private float[] mM;
  
          public MonotoneCubicSpline(float[] x, float[] y) {
              if (x == null || y == null || x.length != y.length || x.length < 2) {
                  throw new IllegalArgumentException("There must be at least two control "
                          + "points and the arrays must be of equal length.");
              }
  
              final int n = x.length;
              float[] d = new float[n - 1]; // could optimize this out
              float[] m = new float[n];
  
              // Compute slopes of secant lines between successive points.
              for (int i = 0; i < n - 1; i++) {
                  float h = x[i + 1] - x[i];
                  if (h <= 0f) {
                      throw new IllegalArgumentException("The control points must all "
                              + "have strictly increasing X values.");
                  }
                  d[i] = (y[i + 1] - y[i]) / h;
              }
  
              // Initialize the tangents as the average of the secants.
              m[0] = d[0];
              for (int i = 1; i < n - 1; i++) {
                  m[i] = (d[i - 1] + d[i]) * 0.5f;
              }
              m[n - 1] = d[n - 2];
  
              // Update the tangents to preserve monotonicity.
              for (int i = 0; i < n - 1; i++) {
                  if (d[i] == 0f) { // successive Y values are equal
                      m[i] = 0f;
                      m[i + 1] = 0f;
                  } else {
                      float a = m[i] / d[i];
                      float b = m[i + 1] / d[i];
                      if (a < 0f || b < 0f) {
                          throw new IllegalArgumentException("The control points must have "
                                  + "monotonic Y values.");
                      }
                      float h = (float) Math.hypot(a, b);
                      if (h > 3f) {
                          float t = 3f / h;
                          m[i] *= t;
                          m[i + 1] *= t;
                      }
                  }
              }
  
              mX = x;
              mY = y;
              mM = m;
          }
  
          @Override
          public float interpolate(float x) {
              // Handle the boundary cases.
              final int n = mX.length;
              if (Float.isNaN(x)) {
                  return x;
              }
              if (x <= mX[0]) {
                  return mY[0];
              }
              if (x >= mX[n - 1]) {
                  return mY[n - 1];
              }
  
              // Find the index 'i' of the last point with smaller X.
              // We know this will be within the spline due to the boundary tests.
              int i = 0;
              while (x >= mX[i + 1]) {
                  i += 1;
                  if (x == mX[i]) {
                      return mY[i];
                  }
              }
  
              // Perform cubic Hermite spline interpolation.
              float h = mX[i + 1] - mX[i];
              float t = (x - mX[i]) / h;
              return (mY[i] * (1 + 2 * t) + h * mM[i] * t) * (1 - t) * (1 - t)
                      + (mY[i + 1] * (3 - 2 * t) + h * mM[i + 1] * (t - 1)) * t * t;
          }
  
          // For debugging.
          @Override
          public String toString() {
              StringBuilder str = new StringBuilder();
              final int n = mX.length;
              str.append("MonotoneCubicSpline{[");
              for (int i = 0; i < n; i++) {
                  if (i != 0) {
                      str.append(", ");
                  }
                  str.append("(").append(mX[i]);
                  str.append(", ").append(mY[i]);
                  str.append(": ").append(mM[i]).append(")");
              }
              str.append("]}");
              return str.toString();
          }
      }
  
      public static class LinearSpline extends Spline {
          private final float[] mX;
          private final float[] mY;
          private final float[] mM;
  
          public LinearSpline(float[] x, float[] y) {
              if (x == null || y == null || x.length != y.length || x.length < 2) {
                  throw new IllegalArgumentException("There must be at least two control "
                          + "points and the arrays must be of equal length.");
              }
              final int N = x.length;
              mM = new float[N-1];
              for (int i = 0; i < N-1; i++) {
                  mM[i] = (y[i+1] - y[i]) / (x[i+1] - x[i]);
              }
              mX = x;
              mY = y;
          }
  
          @Override
          public float interpolate(float x) {
              // Handle the boundary cases.
              final int n = mX.length;
              if (Float.isNaN(x)) {
                  return x;
              }
              if (x <= mX[0]) {
                  return mY[0];
              }
              if (x >= mX[n - 1]) {
                  return mY[n - 1];
              }
  
              // Find the index 'i' of the last point with smaller X.
              // We know this will be within the spline due to the boundary tests.
              int i = 0;
              while (x >= mX[i + 1]) {
                  i += 1;
                  if (x == mX[i]) {
                      return mY[i];
                  }
              }
              return mY[i] + mM[i] * (x - mX[i]);
          }
  
          @Override
          public String toString() {
              StringBuilder str = new StringBuilder();
              final int n = mX.length;
              str.append("LinearSpline{[");
              for (int i = 0; i < n; i++) {
                  if (i != 0) {
                      str.append(", ");
                  }
                  str.append("(").append(mX[i]);
                  str.append(", ").append(mY[i]);
                  if (i < n-1) {
                      str.append(": ").append(mM[i]);
                  }
                  str.append(")");
              }
              str.append("]}");
              return str.toString();
          }
      }
  }
  