xref: /external/robolectric-shadows/shadows/framework/src/main/java/org/robolectric/shadows/CachedPathIteratorFactory.java

package org.robolectric.shadows;

import java.awt.geom.CubicCurve2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.QuadCurve2D;
import java.util.ArrayList;

/**
 * Class that returns iterators for a given path. These iterators are lightweight and can be reused
 * multiple times to iterate over the path.
 *
 * <p>copied from
 * https://github.com/aosp-mirror/platform_frameworks_base/blob/oreo-release/tools/layoutlib/bridge/src/com/android/layoutlib/bridge/util/CachedPathIteratorFactory.java
 */
public class CachedPathIteratorFactory {
  /*
   * A few conventions used in the code:
   * Coordinates or coords arrays store segment coordinates. They use the same format as
   * PathIterator#currentSegment coordinates array.
   * float arrays store always points where the first element is X and the second is Y.
   */

  // This governs how accurate the approximation of the Path is.
  private static final float PRECISION = 0.002f;

  private final int mWindingRule;
  private final int[] mTypes;
  private final float[][] mCoordinates;
  private final float[] mSegmentsLength;
  private final float mTotalLength;

  public CachedPathIteratorFactory(PathIterator iterator) {
    mWindingRule = iterator.getWindingRule();

    ArrayList<Integer> typesArray = new ArrayList<>();
    ArrayList<float[]> pointsArray = new ArrayList<>();
    float[] points = new float[6];
    while (!iterator.isDone()) {
      int type = iterator.currentSegment(points);
      int nPoints = getNumberOfPoints(type) * 2; // 2 coordinates per point

      typesArray.add(type);
      float[] itemPoints = new float[nPoints];
      System.arraycopy(points, 0, itemPoints, 0, nPoints);
      pointsArray.add(itemPoints);
      iterator.next();
    }

    mTypes = new int[typesArray.size()];
    mCoordinates = new float[mTypes.length][];
    for (int i = 0; i < typesArray.size(); i++) {
      mTypes[i] = typesArray.get(i);
      mCoordinates[i] = pointsArray.get(i);
    }

    // Do measurement
    mSegmentsLength = new float[mTypes.length];

    // Curves that we can reuse to estimate segments length
    CubicCurve2D.Float cubicCurve = new CubicCurve2D.Float();
    QuadCurve2D.Float quadCurve = new QuadCurve2D.Float();
    float lastX = 0;
    float lastY = 0;
    float totalLength = 0;
    for (int i = 0; i < mTypes.length; i++) {
      switch (mTypes[i]) {
        case PathIterator.SEG_CUBICTO:
          cubicCurve.setCurve(
              lastX,
              lastY,
              mCoordinates[i][0],
              mCoordinates[i][1],
              mCoordinates[i][2],
              mCoordinates[i][3],
              lastX = mCoordinates[i][4],
              lastY = mCoordinates[i][5]);
          mSegmentsLength[i] = getFlatPathLength(cubicCurve.getPathIterator(null, PRECISION));
          break;
        case PathIterator.SEG_QUADTO:
          quadCurve.setCurve(
              lastX,
              lastY,
              mCoordinates[i][0],
              mCoordinates[i][1],
              lastX = mCoordinates[i][2],
              lastY = mCoordinates[i][3]);
          mSegmentsLength[i] = getFlatPathLength(quadCurve.getPathIterator(null, PRECISION));
          break;
        case PathIterator.SEG_CLOSE:
          mSegmentsLength[i] =
              (float)
                  Point2D.distance(
                      lastX, lastY, lastX = mCoordinates[0][0], lastY = mCoordinates[0][1]);
          mCoordinates[i] = new float[2];
          // We convert a SEG_CLOSE segment to a SEG_LINETO so we do not have to worry
          // about this special case in the rest of the code.
          mTypes[i] = PathIterator.SEG_LINETO;
          mCoordinates[i][0] = mCoordinates[0][0];
          mCoordinates[i][1] = mCoordinates[0][1];
          break;
        case PathIterator.SEG_MOVETO:
          mSegmentsLength[i] = 0;
          lastX = mCoordinates[i][0];
          lastY = mCoordinates[i][1];
          break;
        case PathIterator.SEG_LINETO:
          mSegmentsLength[i] =
              (float) Point2D.distance(lastX, lastY, mCoordinates[i][0], mCoordinates[i][1]);
          lastX = mCoordinates[i][0];
          lastY = mCoordinates[i][1];
          break;
        default:
      }
      totalLength += mSegmentsLength[i];
    }

    mTotalLength = totalLength;
  }

  private static void quadCurveSegment(float[] coords, float t0, float t1) {
    // Calculate X and Y at 0.5 (We'll use this to reconstruct the control point later)
    float mt = t0 + (t1 - t0) / 2;
    float mu = 1 - mt;
    float mx = mu * mu * coords[0] + 2 * mu * mt * coords[2] + mt * mt * coords[4];
    float my = mu * mu * coords[1] + 2 * mu * mt * coords[3] + mt * mt * coords[5];

    float u0 = 1 - t0;
    float u1 = 1 - t1;

    // coords at t0
    coords[0] = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0;
    coords[1] = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0;

    // coords at t1
    coords[4] = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1;
    coords[5] = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1;

    // estimated control point at t'=0.5
    coords[2] = 2 * mx - coords[0] / 2 - coords[4] / 2;
    coords[3] = 2 * my - coords[1] / 2 - coords[5] / 2;
  }

  private static void cubicCurveSegment(float[] coords, float t0, float t1) {
    // http://stackoverflow.com/questions/11703283/cubic-bezier-curve-segment
    float u0 = 1 - t0;
    float u1 = 1 - t1;

    // Calculate the points at t0 and t1 for the quadratic curves formed by (P0, P1, P2) and
    // (P1, P2, P3)
    float qxa = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0;
    float qxb = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1;
    float qxc = coords[2] * u0 * u0 + coords[4] * 2 * t0 * u0 + coords[6] * t0 * t0;
    float qxd = coords[2] * u1 * u1 + coords[4] * 2 * t1 * u1 + coords[6] * t1 * t1;

    float qya = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0;
    float qyb = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1;
    float qyc = coords[3] * u0 * u0 + coords[5] * 2 * t0 * u0 + coords[7] * t0 * t0;
    float qyd = coords[3] * u1 * u1 + coords[5] * 2 * t1 * u1 + coords[7] * t1 * t1;

    // Linear interpolation
    coords[0] = qxa * u0 + qxc * t0;
    coords[1] = qya * u0 + qyc * t0;

    coords[2] = qxa * u1 + qxc * t1;
    coords[3] = qya * u1 + qyc * t1;

    coords[4] = qxb * u0 + qxd * t0;
    coords[5] = qyb * u0 + qyd * t0;

    coords[6] = qxb * u1 + qxd * t1;
    coords[7] = qyb * u1 + qyd * t1;
  }

  /**
   * Returns the end point of a given segment
   *
   * @param type the segment type
   * @param coords the segment coordinates array
   * @param point the return array where the point will be stored
   */
  private static void getShapeEndPoint(int type, float[] coords, float[] point) {
    // start index of the end point for the segment type
    int pointIndex = (getNumberOfPoints(type) - 1) * 2;
    point[0] = coords[pointIndex];
    point[1] = coords[pointIndex + 1];
  }

  /** Returns the number of points stored in a coordinates array for the given segment type. */
  private static int getNumberOfPoints(int segmentType) {
    switch (segmentType) {
      case PathIterator.SEG_QUADTO:
        return 2;
      case PathIterator.SEG_CUBICTO:
        return 3;
      case PathIterator.SEG_CLOSE:
        return 0;
      default:
        return 1;
    }
  }

  /**
   * Returns the estimated length of a flat path. If the passed path is not flat (i.e. contains a
   * segment that is not {@link PathIterator#SEG_CLOSE}, {@link PathIterator#SEG_MOVETO} or {@link
   * PathIterator#SEG_LINETO} this method will fail.
   */
  private static float getFlatPathLength(PathIterator iterator) {
    float segment[] = new float[6];
    float totalLength = 0;
    float[] previousPoint = new float[2];
    boolean isFirstPoint = true;

    while (!iterator.isDone()) {
      int type = iterator.currentSegment(segment);
      assert type == PathIterator.SEG_LINETO
          || type == PathIterator.SEG_CLOSE
          || type == PathIterator.SEG_MOVETO;

      // MoveTo shouldn't affect the length
      if (!isFirstPoint && type != PathIterator.SEG_MOVETO) {
        totalLength +=
            (float) Point2D.distance(previousPoint[0], previousPoint[1], segment[0], segment[1]);
      } else {
        isFirstPoint = false;
      }
      previousPoint[0] = segment[0];
      previousPoint[1] = segment[1];
      iterator.next();
    }

    return totalLength;
  }

  /** Returns the estimated position along a path of the given length. */
  private void getPointAtLength(
      int type, float[] coords, float lastX, float lastY, float t, float[] point) {
    if (type == PathIterator.SEG_LINETO) {
      point[0] = lastX + (coords[0] - lastX) * t;
      point[1] = lastY + (coords[1] - lastY) * t;
      // Return here, since we do not need a shape to estimate
      return;
    }

    float[] curve = new float[8];
    int lastPointIndex = (getNumberOfPoints(type) - 1) * 2;

    System.arraycopy(coords, 0, curve, 2, coords.length);
    curve[0] = lastX;
    curve[1] = lastY;
    if (type == PathIterator.SEG_CUBICTO) {
      cubicCurveSegment(curve, 0f, t);
    } else {
      quadCurveSegment(curve, 0f, t);
    }

    point[0] = curve[2 + lastPointIndex];
    point[1] = curve[2 + lastPointIndex + 1];
  }

  public CachedPathIterator iterator() {
    return new CachedPathIterator();
  }

  /** Class that allows us to iterate over a path multiple times */
  public class CachedPathIterator implements PathIterator {
    private int mNextIndex;

    /**
     * Current segment type.
     *
     * @see PathIterator
     */
    private int mCurrentType;

    /**
     * Stores the coordinates array of the current segment. The number of points stored depends on
     * the segment type.
     *
     * @see PathIterator
     */
    private float[] mCurrentCoords = new float[6];

    private float mCurrentSegmentLength;

    /**
     * Current segment length offset. When asking for the length of the current segment, the length
     * will be reduced by this amount. This is useful when we are only using portions of the
     * segment.
     *
     * @see #jumpToSegment(float)
     */
    private float mOffsetLength;

    /** Point where the current segment started */
    private float[] mLastPoint = new float[2];

    private boolean isIteratorDone;

    private CachedPathIterator() {
      next();
    }

    public float getCurrentSegmentLength() {
      return mCurrentSegmentLength;
    }

    @Override
    public int getWindingRule() {
      return mWindingRule;
    }

    @Override
    public boolean isDone() {
      return isIteratorDone;
    }

    @Override
    public void next() {
      if (mNextIndex >= mTypes.length) {
        isIteratorDone = true;
        return;
      }

      if (mNextIndex >= 1) {
        // We've already called next() once so there is a previous segment in this path.
        // We want to get the coordinates where the path ends.
        getShapeEndPoint(mCurrentType, mCurrentCoords, mLastPoint);
      } else {
        // This is the first segment, no previous point so initialize to 0, 0
        mLastPoint[0] = mLastPoint[1] = 0f;
      }
      mCurrentType = mTypes[mNextIndex];
      mCurrentSegmentLength = mSegmentsLength[mNextIndex] - mOffsetLength;

      if (mOffsetLength > 0f && (mCurrentType == SEG_CUBICTO || mCurrentType == SEG_QUADTO)) {
        // We need to skip part of the start of the current segment (because
        // mOffsetLength > 0)
        float[] points = new float[8];

        if (mNextIndex < 1) {
          points[0] = points[1] = 0f;
        } else {
          getShapeEndPoint(mTypes[mNextIndex - 1], mCoordinates[mNextIndex - 1], points);
        }

        System.arraycopy(mCoordinates[mNextIndex], 0, points, 2, mCoordinates[mNextIndex].length);
        float t0 =
            (mSegmentsLength[mNextIndex] - mCurrentSegmentLength) / mSegmentsLength[mNextIndex];
        if (mCurrentType == SEG_CUBICTO) {
          cubicCurveSegment(points, t0, 1f);
        } else {
          quadCurveSegment(points, t0, 1f);
        }
        System.arraycopy(points, 2, mCurrentCoords, 0, mCoordinates[mNextIndex].length);
      } else {
        System.arraycopy(
            mCoordinates[mNextIndex], 0, mCurrentCoords, 0, mCoordinates[mNextIndex].length);
      }

      mOffsetLength = 0f;
      mNextIndex++;
    }

    @Override
    public int currentSegment(float[] coords) {
      System.arraycopy(mCurrentCoords, 0, coords, 0, getNumberOfPoints(mCurrentType) * 2);
      return mCurrentType;
    }

    @Override
    public int currentSegment(double[] coords) {
      throw new UnsupportedOperationException();
    }

    /** Returns the point where the current segment ends */
    public void getCurrentSegmentEnd(float[] point) {
      point[0] = mLastPoint[0];
      point[1] = mLastPoint[1];
    }

    /** Restarts the iterator and jumps all the segments of this path up to the length value. */
    public void jumpToSegment(float length) {
      isIteratorDone = false;
      if (length <= 0f) {
        mNextIndex = 0;
        return;
      }

      float accLength = 0;
      float lastPoint[] = new float[2];
      for (mNextIndex = 0; mNextIndex < mTypes.length; mNextIndex++) {
        float segmentLength = mSegmentsLength[mNextIndex];
        if (accLength + segmentLength >= length && mTypes[mNextIndex] != SEG_MOVETO) {
          float[] estimatedPoint = new float[2];
          getPointAtLength(
              mTypes[mNextIndex],
              mCoordinates[mNextIndex],
              lastPoint[0],
              lastPoint[1],
              (length - accLength) / segmentLength,
              estimatedPoint);

          // This segment makes us go further than length so we go back one step,
          // set a moveto and offset the length of the next segment by the length
          // of this segment that we've already used.
          mCurrentType = PathIterator.SEG_MOVETO;
          mCurrentCoords[0] = estimatedPoint[0];
          mCurrentCoords[1] = estimatedPoint[1];
          mCurrentSegmentLength = 0;

          // We need to offset next path length to account for the segment we've just
          // skipped.
          mOffsetLength = length - accLength;
          return;
        }
        accLength += segmentLength;
        getShapeEndPoint(mTypes[mNextIndex], mCoordinates[mNextIndex], lastPoint);
      }
    }

    /**
     * Returns the current segment up to certain length. If the current segment is shorter than
     * length, then the whole segment is returned. The segment coordinates are copied into the
     * coords array.
     *
     * @return the segment type
     */
    public int currentSegment(float[] coords, float length) {
      int type = currentSegment(coords);
      // If the length is greater than the current segment length, no need to find
      // the cut point. Same if this is a SEG_MOVETO.
      if (mCurrentSegmentLength <= length || type == SEG_MOVETO) {
        return type;
      }

      float t = length / getCurrentSegmentLength();

      // We find at which offset the end point is located within the coords array and set
      // a new end point to cut the segment short
      switch (type) {
        case SEG_CUBICTO:
        case SEG_QUADTO:
          float[] curve = new float[8];
          curve[0] = mLastPoint[0];
          curve[1] = mLastPoint[1];
          System.arraycopy(coords, 0, curve, 2, coords.length);
          if (type == SEG_CUBICTO) {
            cubicCurveSegment(curve, 0f, t);
          } else {
            quadCurveSegment(curve, 0f, t);
          }
          System.arraycopy(curve, 2, coords, 0, coords.length);
          break;
        default:
          float[] point = new float[2];
          getPointAtLength(type, coords, mLastPoint[0], mLastPoint[1], t, point);
          coords[0] = point[0];
          coords[1] = point[1];
      }

      return type;
    }

    /** Returns the total length of the path */
    public float getTotalLength() {
      return mTotalLength;
    }
  }
}