1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.systemui.recents.misc;
18
19import android.graphics.Path;
20import android.view.animation.BaseInterpolator;
21import android.view.animation.Interpolator;
22
23/**
24 * An interpolator that can traverse a Path. The x coordinate along the <code>Path</code>
25 * is the input value and the output is the y coordinate of the line at that point.
26 * This means that the Path must conform to a function <code>y = f(x)</code>.
27 *
28 * <p>The <code>Path</code> must not have gaps in the x direction and must not
29 * loop back on itself such that there can be two points sharing the same x coordinate.
30 * It is alright to have a disjoint line in the vertical direction:</p>
31 * <p><blockquote><pre>
32 *     Path path = new Path();
33 *     path.lineTo(0.25f, 0.25f);
34 *     path.moveTo(0.25f, 0.5f);
35 *     path.lineTo(1f, 1f);
36 * </pre></blockquote></p>
37 */
38public class FreePathInterpolator extends BaseInterpolator {
39
40    // This governs how accurate the approximation of the Path is.
41    private static final float PRECISION = 0.002f;
42
43    private float[] mX;
44    private float[] mY;
45    private float mArcLength;
46
47    /**
48     * Create an interpolator for an arbitrary <code>Path</code>.
49     *
50     * @param path The <code>Path</code> to use to make the line representing the interpolator.
51     */
52    public FreePathInterpolator(Path path) {
53        initPath(path);
54    }
55
56    private void initPath(Path path) {
57        float[] pointComponents = path.approximate(PRECISION);
58
59        int numPoints = pointComponents.length / 3;
60
61        mX = new float[numPoints];
62        mY = new float[numPoints];
63        mArcLength = 0;
64        float prevX = 0;
65        float prevY = 0;
66        float prevFraction = 0;
67        int componentIndex = 0;
68        for (int i = 0; i < numPoints; i++) {
69            float fraction = pointComponents[componentIndex++];
70            float x = pointComponents[componentIndex++];
71            float y = pointComponents[componentIndex++];
72            if (fraction == prevFraction && x != prevX) {
73                throw new IllegalArgumentException(
74                        "The Path cannot have discontinuity in the X axis.");
75            }
76            if (x < prevX) {
77                throw new IllegalArgumentException("The Path cannot loop back on itself.");
78            }
79            mX[i] = x;
80            mY[i] = y;
81            mArcLength += Math.hypot(x - prevX, y - prevY);
82            prevX = x;
83            prevY = y;
84            prevFraction = fraction;
85        }
86    }
87
88    /**
89     * Using the line in the Path in this interpolator that can be described as
90     * <code>y = f(x)</code>, finds the y coordinate of the line given <code>t</code>
91     * as the x coordinate.
92     *
93     * @param t Treated as the x coordinate along the line.
94     * @return The y coordinate of the Path along the line where x = <code>t</code>.
95     * @see Interpolator#getInterpolation(float)
96     */
97    @Override
98    public float getInterpolation(float t) {
99        int startIndex = 0;
100        int endIndex = mX.length - 1;
101
102        // Return early if out of bounds
103        if (t <= 0) {
104            return mY[startIndex];
105        } else if (t >= 1) {
106            return mY[endIndex];
107        }
108
109        // Do a binary search for the correct x to interpolate between.
110        while (endIndex - startIndex > 1) {
111            int midIndex = (startIndex + endIndex) / 2;
112            if (t < mX[midIndex]) {
113                endIndex = midIndex;
114            } else {
115                startIndex = midIndex;
116            }
117        }
118
119        float xRange = mX[endIndex] - mX[startIndex];
120        if (xRange == 0) {
121            return mY[startIndex];
122        }
123
124        float tInRange = t - mX[startIndex];
125        float fraction = tInRange / xRange;
126
127        float startY = mY[startIndex];
128        float endY = mY[endIndex];
129        return startY + (fraction * (endY - startY));
130    }
131
132    /**
133     * Finds the x that provides the given <code>y = f(x)</code>.
134     *
135     * @param y a value from (0,1) that is in this path.
136     */
137    public float getX(float y) {
138        int startIndex = 0;
139        int endIndex = mY.length - 1;
140
141        // Return early if out of bounds
142        if (y <= 0) {
143            return mX[endIndex];
144        } else if (y >= 1) {
145            return mX[startIndex];
146        }
147
148        // Do a binary search for index that bounds the y
149        while (endIndex - startIndex > 1) {
150            int midIndex = (startIndex + endIndex) / 2;
151            if (y < mY[midIndex]) {
152                startIndex = midIndex;
153            } else {
154                endIndex = midIndex;
155            }
156        }
157
158        float yRange = mY[endIndex] - mY[startIndex];
159        if (yRange == 0) {
160            return mX[startIndex];
161        }
162
163        float tInRange = y - mY[startIndex];
164        float fraction = tInRange / yRange;
165
166        float startX = mX[startIndex];
167        float endX = mX[endIndex];
168        return startX + (fraction * (endX - startX));
169    }
170
171    /**
172     * Returns the arclength of the path we are interpolating.
173     */
174    public float getArcLength() {
175        return mArcLength;
176    }
177}