content: /*
   * Copyright (C) 2015 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 com.android.layoutlib.bridge.util;
  
  import android.annotation.NonNull;
  
  import java.awt.geom.CubicCurve2D;
  import java.awt.geom.PathIterator;
  import java.awt.geom.Point2D;
  import java.awt.geom.QuadCurve2D;
  import java.util.ArrayList;
  
  import com.google.android.collect.Lists;
  
  /**
   * Class that returns iterators for a given path. These iterators are lightweight and can be reused
   * multiple times to iterate over the path.
   */
  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(@NonNull PathIterator iterator) {
          mWindingRule = iterator.getWindingRule();
  
          ArrayList<Integer> typesArray = Lists.newArrayList();
          ArrayList<float[]> pointsArray = Lists.newArrayList();
          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];
                  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, @NonNull float[] coords, @NonNull 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(@NonNull 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 += 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, @NonNull float[] coords, float lastX, float
              lastY, float t, @NonNull 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(@NonNull 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;
          }
      }
  }
  