1/*
2 * Copyright (C) 2012 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.inputmethod.keyboard.internal;
18
19import android.util.Log;
20
21import com.android.inputmethod.latin.common.Constants;
22import com.android.inputmethod.latin.common.InputPointers;
23import com.android.inputmethod.latin.common.ResizableIntArray;
24
25/**
26 * This class holds event points to recognize a gesture stroke.
27 * TODO: Should be package private class.
28 */
29public final class GestureStrokeRecognitionPoints {
30    private static final String TAG = GestureStrokeRecognitionPoints.class.getSimpleName();
31    private static final boolean DEBUG = false;
32    private static final boolean DEBUG_SPEED = false;
33
34    // The height of extra area above the keyboard to draw gesture trails.
35    // Proportional to the keyboard height.
36    public static final float EXTRA_GESTURE_TRAIL_AREA_ABOVE_KEYBOARD_RATIO = 0.25f;
37
38    private final int mPointerId;
39    private final ResizableIntArray mEventTimes = new ResizableIntArray(
40            Constants.DEFAULT_GESTURE_POINTS_CAPACITY);
41    private final ResizableIntArray mXCoordinates = new ResizableIntArray(
42            Constants.DEFAULT_GESTURE_POINTS_CAPACITY);
43    private final ResizableIntArray mYCoordinates = new ResizableIntArray(
44            Constants.DEFAULT_GESTURE_POINTS_CAPACITY);
45
46    private final GestureStrokeRecognitionParams mRecognitionParams;
47
48    private int mKeyWidth; // pixel
49    private int mMinYCoordinate; // pixel
50    private int mMaxYCoordinate; // pixel
51    // Static threshold for starting gesture detection
52    private int mDetectFastMoveSpeedThreshold; // pixel /sec
53    private int mDetectFastMoveTime;
54    private int mDetectFastMoveX;
55    private int mDetectFastMoveY;
56    // Dynamic threshold for gesture after fast typing
57    private boolean mAfterFastTyping;
58    private int mGestureDynamicDistanceThresholdFrom; // pixel
59    private int mGestureDynamicDistanceThresholdTo; // pixel
60    // Variables for gesture sampling
61    private int mGestureSamplingMinimumDistance; // pixel
62    private long mLastMajorEventTime;
63    private int mLastMajorEventX;
64    private int mLastMajorEventY;
65    // Variables for gesture recognition
66    private int mGestureRecognitionSpeedThreshold; // pixel / sec
67    private int mIncrementalRecognitionSize;
68    private int mLastIncrementalBatchSize;
69
70    private static final int MSEC_PER_SEC = 1000;
71
72    // TODO: Make this package private
73    public GestureStrokeRecognitionPoints(final int pointerId,
74            final GestureStrokeRecognitionParams recognitionParams) {
75        mPointerId = pointerId;
76        mRecognitionParams = recognitionParams;
77    }
78
79    // TODO: Make this package private
80    public void setKeyboardGeometry(final int keyWidth, final int keyboardHeight) {
81        mKeyWidth = keyWidth;
82        mMinYCoordinate = -(int)(keyboardHeight * EXTRA_GESTURE_TRAIL_AREA_ABOVE_KEYBOARD_RATIO);
83        mMaxYCoordinate = keyboardHeight;
84        // TODO: Find an appropriate base metric for these length. Maybe diagonal length of the key?
85        mDetectFastMoveSpeedThreshold = (int)(
86                keyWidth * mRecognitionParams.mDetectFastMoveSpeedThreshold);
87        mGestureDynamicDistanceThresholdFrom = (int)(
88                keyWidth * mRecognitionParams.mDynamicDistanceThresholdFrom);
89        mGestureDynamicDistanceThresholdTo = (int)(
90                keyWidth * mRecognitionParams.mDynamicDistanceThresholdTo);
91        mGestureSamplingMinimumDistance = (int)(
92                keyWidth * mRecognitionParams.mSamplingMinimumDistance);
93        mGestureRecognitionSpeedThreshold = (int)(
94                keyWidth * mRecognitionParams.mRecognitionSpeedThreshold);
95        if (DEBUG) {
96            Log.d(TAG, String.format(
97                    "[%d] setKeyboardGeometry: keyWidth=%3d tT=%3d >> %3d tD=%3d >> %3d",
98                    mPointerId, keyWidth,
99                    mRecognitionParams.mDynamicTimeThresholdFrom,
100                    mRecognitionParams.mDynamicTimeThresholdTo,
101                    mGestureDynamicDistanceThresholdFrom,
102                    mGestureDynamicDistanceThresholdTo));
103        }
104    }
105
106    // TODO: Make this package private
107    public int getLength() {
108        return mEventTimes.getLength();
109    }
110
111    // TODO: Make this package private
112    public void addDownEventPoint(final int x, final int y, final int elapsedTimeSinceFirstDown,
113            final int elapsedTimeSinceLastTyping) {
114        reset();
115        if (elapsedTimeSinceLastTyping < mRecognitionParams.mStaticTimeThresholdAfterFastTyping) {
116            mAfterFastTyping = true;
117        }
118        if (DEBUG) {
119            Log.d(TAG, String.format("[%d] onDownEvent: dT=%3d%s", mPointerId,
120                    elapsedTimeSinceLastTyping, mAfterFastTyping ? " afterFastTyping" : ""));
121        }
122        // Call {@link #addEventPoint(int,int,int,boolean)} to record this down event point as a
123        // major event point.
124        addEventPoint(x, y, elapsedTimeSinceFirstDown, true /* isMajorEvent */);
125    }
126
127    private int getGestureDynamicDistanceThreshold(final int deltaTime) {
128        if (!mAfterFastTyping || deltaTime >= mRecognitionParams.mDynamicThresholdDecayDuration) {
129            return mGestureDynamicDistanceThresholdTo;
130        }
131        final int decayedThreshold =
132                (mGestureDynamicDistanceThresholdFrom - mGestureDynamicDistanceThresholdTo)
133                * deltaTime / mRecognitionParams.mDynamicThresholdDecayDuration;
134        return mGestureDynamicDistanceThresholdFrom - decayedThreshold;
135    }
136
137    private int getGestureDynamicTimeThreshold(final int deltaTime) {
138        if (!mAfterFastTyping || deltaTime >= mRecognitionParams.mDynamicThresholdDecayDuration) {
139            return mRecognitionParams.mDynamicTimeThresholdTo;
140        }
141        final int decayedThreshold =
142                (mRecognitionParams.mDynamicTimeThresholdFrom
143                        - mRecognitionParams.mDynamicTimeThresholdTo)
144                * deltaTime / mRecognitionParams.mDynamicThresholdDecayDuration;
145        return mRecognitionParams.mDynamicTimeThresholdFrom - decayedThreshold;
146    }
147
148    // TODO: Make this package private
149    public final boolean isStartOfAGesture() {
150        if (!hasDetectedFastMove()) {
151            return false;
152        }
153        final int size = getLength();
154        if (size <= 0) {
155            return false;
156        }
157        final int lastIndex = size - 1;
158        final int deltaTime = mEventTimes.get(lastIndex) - mDetectFastMoveTime;
159        if (deltaTime < 0) {
160            return false;
161        }
162        final int deltaDistance = getDistance(
163                mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex),
164                mDetectFastMoveX, mDetectFastMoveY);
165        final int distanceThreshold = getGestureDynamicDistanceThreshold(deltaTime);
166        final int timeThreshold = getGestureDynamicTimeThreshold(deltaTime);
167        final boolean isStartOfAGesture = deltaTime >= timeThreshold
168                && deltaDistance >= distanceThreshold;
169        if (DEBUG) {
170            Log.d(TAG, String.format("[%d] isStartOfAGesture: dT=%3d tT=%3d dD=%3d tD=%3d%s%s",
171                    mPointerId, deltaTime, timeThreshold,
172                    deltaDistance, distanceThreshold,
173                    mAfterFastTyping ? " afterFastTyping" : "",
174                    isStartOfAGesture ? " startOfAGesture" : ""));
175        }
176        return isStartOfAGesture;
177    }
178
179    // TODO: Make this package private
180    public void duplicateLastPointWith(final int time) {
181        final int lastIndex = getLength() - 1;
182        if (lastIndex >= 0) {
183            final int x = mXCoordinates.get(lastIndex);
184            final int y = mYCoordinates.get(lastIndex);
185            if (DEBUG) {
186                Log.d(TAG, String.format("[%d] duplicateLastPointWith: %d,%d|%d", mPointerId,
187                        x, y, time));
188            }
189            // TODO: Have appendMajorPoint()
190            appendPoint(x, y, time);
191            updateIncrementalRecognitionSize(x, y, time);
192        }
193    }
194
195    private void reset() {
196        mIncrementalRecognitionSize = 0;
197        mLastIncrementalBatchSize = 0;
198        mEventTimes.setLength(0);
199        mXCoordinates.setLength(0);
200        mYCoordinates.setLength(0);
201        mLastMajorEventTime = 0;
202        mDetectFastMoveTime = 0;
203        mAfterFastTyping = false;
204    }
205
206    private void appendPoint(final int x, final int y, final int time) {
207        final int lastIndex = getLength() - 1;
208        // The point that is created by {@link duplicateLastPointWith(int)} may have later event
209        // time than the next {@link MotionEvent}. To maintain the monotonicity of the event time,
210        // drop the successive point here.
211        if (lastIndex >= 0 && mEventTimes.get(lastIndex) > time) {
212            Log.w(TAG, String.format("[%d] drop stale event: %d,%d|%d last: %d,%d|%d", mPointerId,
213                    x, y, time, mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex),
214                    mEventTimes.get(lastIndex)));
215            return;
216        }
217        mEventTimes.add(time);
218        mXCoordinates.add(x);
219        mYCoordinates.add(y);
220    }
221
222    private void updateMajorEvent(final int x, final int y, final int time) {
223        mLastMajorEventTime = time;
224        mLastMajorEventX = x;
225        mLastMajorEventY = y;
226    }
227
228    private final boolean hasDetectedFastMove() {
229        return mDetectFastMoveTime > 0;
230    }
231
232    private int detectFastMove(final int x, final int y, final int time) {
233        final int size = getLength();
234        final int lastIndex = size - 1;
235        final int lastX = mXCoordinates.get(lastIndex);
236        final int lastY = mYCoordinates.get(lastIndex);
237        final int dist = getDistance(lastX, lastY, x, y);
238        final int msecs = time - mEventTimes.get(lastIndex);
239        if (msecs > 0) {
240            final int pixels = getDistance(lastX, lastY, x, y);
241            final int pixelsPerSec = pixels * MSEC_PER_SEC;
242            if (DEBUG_SPEED) {
243                final float speed = (float)pixelsPerSec / msecs / mKeyWidth;
244                Log.d(TAG, String.format("[%d] detectFastMove: speed=%5.2f", mPointerId, speed));
245            }
246            // Equivalent to (pixels / msecs < mStartSpeedThreshold / MSEC_PER_SEC)
247            if (!hasDetectedFastMove() && pixelsPerSec > mDetectFastMoveSpeedThreshold * msecs) {
248                if (DEBUG) {
249                    final float speed = (float)pixelsPerSec / msecs / mKeyWidth;
250                    Log.d(TAG, String.format(
251                            "[%d] detectFastMove: speed=%5.2f T=%3d points=%3d fastMove",
252                            mPointerId, speed, time, size));
253                }
254                mDetectFastMoveTime = time;
255                mDetectFastMoveX = x;
256                mDetectFastMoveY = y;
257            }
258        }
259        return dist;
260    }
261
262    /**
263     * Add an event point to this gesture stroke recognition points. Returns true if the event
264     * point is on the valid gesture area.
265     * @param x the x-coordinate of the event point
266     * @param y the y-coordinate of the event point
267     * @param time the elapsed time in millisecond from the first gesture down
268     * @param isMajorEvent false if this is a historical move event
269     * @return true if the event point is on the valid gesture area
270     */
271    // TODO: Make this package private
272    public boolean addEventPoint(final int x, final int y, final int time,
273            final boolean isMajorEvent) {
274        final int size = getLength();
275        if (size <= 0) {
276            // The first event of this stroke (a.k.a. down event).
277            appendPoint(x, y, time);
278            updateMajorEvent(x, y, time);
279        } else {
280            final int distance = detectFastMove(x, y, time);
281            if (distance > mGestureSamplingMinimumDistance) {
282                appendPoint(x, y, time);
283            }
284        }
285        if (isMajorEvent) {
286            updateIncrementalRecognitionSize(x, y, time);
287            updateMajorEvent(x, y, time);
288        }
289        return y >= mMinYCoordinate && y < mMaxYCoordinate;
290    }
291
292    private void updateIncrementalRecognitionSize(final int x, final int y, final int time) {
293        final int msecs = (int)(time - mLastMajorEventTime);
294        if (msecs <= 0) {
295            return;
296        }
297        final int pixels = getDistance(mLastMajorEventX, mLastMajorEventY, x, y);
298        final int pixelsPerSec = pixels * MSEC_PER_SEC;
299        // Equivalent to (pixels / msecs < mGestureRecognitionThreshold / MSEC_PER_SEC)
300        if (pixelsPerSec < mGestureRecognitionSpeedThreshold * msecs) {
301            mIncrementalRecognitionSize = getLength();
302        }
303    }
304
305    // TODO: Make this package private
306    public final boolean hasRecognitionTimePast(
307            final long currentTime, final long lastRecognitionTime) {
308        return currentTime > lastRecognitionTime + mRecognitionParams.mRecognitionMinimumTime;
309    }
310
311    // TODO: Make this package private
312    public final void appendAllBatchPoints(final InputPointers out) {
313        appendBatchPoints(out, getLength());
314    }
315
316    // TODO: Make this package private
317    public final void appendIncrementalBatchPoints(final InputPointers out) {
318        appendBatchPoints(out, mIncrementalRecognitionSize);
319    }
320
321    private void appendBatchPoints(final InputPointers out, final int size) {
322        final int length = size - mLastIncrementalBatchSize;
323        if (length <= 0) {
324            return;
325        }
326        out.append(mPointerId, mEventTimes, mXCoordinates, mYCoordinates,
327                mLastIncrementalBatchSize, length);
328        mLastIncrementalBatchSize = size;
329    }
330
331    private static int getDistance(final int x1, final int y1, final int x2, final int y2) {
332        return (int)Math.hypot(x1 - x2, y1 - y2);
333    }
334}
335