1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.android.inputmethod.keyboard.internal;
16
17import android.content.res.TypedArray;
18import android.util.Log;
19
20import com.android.inputmethod.latin.InputPointers;
21import com.android.inputmethod.latin.R;
22import com.android.inputmethod.latin.ResizableIntArray;
23import com.android.inputmethod.latin.ResourceUtils;
24
25public class GestureStroke {
26    private static final String TAG = GestureStroke.class.getSimpleName();
27    private static final boolean DEBUG = false;
28    private static final boolean DEBUG_SPEED = false;
29
30    public static final int DEFAULT_CAPACITY = 128;
31
32    private final int mPointerId;
33    private final ResizableIntArray mEventTimes = new ResizableIntArray(DEFAULT_CAPACITY);
34    private final ResizableIntArray mXCoordinates = new ResizableIntArray(DEFAULT_CAPACITY);
35    private final ResizableIntArray mYCoordinates = new ResizableIntArray(DEFAULT_CAPACITY);
36
37    private final GestureStrokeParams mParams;
38
39    private int mKeyWidth; // pixel
40    // Static threshold for starting gesture detection
41    private int mDetectFastMoveSpeedThreshold; // pixel /sec
42    private int mDetectFastMoveTime;
43    private int mDetectFastMoveX;
44    private int mDetectFastMoveY;
45    // Dynamic threshold for gesture after fast typing
46    private boolean mAfterFastTyping;
47    private int mGestureDynamicDistanceThresholdFrom; // pixel
48    private int mGestureDynamicDistanceThresholdTo; // pixel
49    // Variables for gesture sampling
50    private int mGestureSamplingMinimumDistance; // pixel
51    private long mLastMajorEventTime;
52    private int mLastMajorEventX;
53    private int mLastMajorEventY;
54    // Variables for gesture recognition
55    private int mGestureRecognitionSpeedThreshold; // pixel / sec
56    private int mIncrementalRecognitionSize;
57    private int mLastIncrementalBatchSize;
58
59    public static final class GestureStrokeParams {
60        // Static threshold for gesture after fast typing
61        public final int mStaticTimeThresholdAfterFastTyping; // msec
62        // Static threshold for starting gesture detection
63        public final float mDetectFastMoveSpeedThreshold; // keyWidth/sec
64        // Dynamic threshold for gesture after fast typing
65        public final int mDynamicThresholdDecayDuration; // msec
66        // Time based threshold values
67        public final int mDynamicTimeThresholdFrom; // msec
68        public final int mDynamicTimeThresholdTo; // msec
69        // Distance based threshold values
70        public final float mDynamicDistanceThresholdFrom; // keyWidth
71        public final float mDynamicDistanceThresholdTo; // keyWidth
72        // Parameters for gesture sampling
73        public final float mSamplingMinimumDistance; // keyWidth
74        // Parameters for gesture recognition
75        public final int mRecognitionMinimumTime; // msec
76        public final float mRecognitionSpeedThreshold; // keyWidth/sec
77
78        // Default GestureStroke parameters for test.
79        public static final GestureStrokeParams FOR_TEST = new GestureStrokeParams();
80        public static final GestureStrokeParams DEFAULT = FOR_TEST;
81
82        private GestureStrokeParams() {
83            // These parameter values are default and intended for testing.
84            mStaticTimeThresholdAfterFastTyping = 350; // msec
85            mDetectFastMoveSpeedThreshold = 1.5f; // keyWidth / sec
86            mDynamicThresholdDecayDuration = 450; // msec
87            mDynamicTimeThresholdFrom = 300; // msec
88            mDynamicTimeThresholdTo = 20; // msec
89            mDynamicDistanceThresholdFrom = 6.0f; // keyWidth
90            mDynamicDistanceThresholdTo = 0.35f; // keyWidth
91            // The following parameters' change will affect the result of regression test.
92            mSamplingMinimumDistance = 1.0f / 6.0f; // keyWidth
93            mRecognitionMinimumTime = 100; // msec
94            mRecognitionSpeedThreshold = 5.5f; // keyWidth / sec
95        }
96
97        public GestureStrokeParams(final TypedArray mainKeyboardViewAttr) {
98            mStaticTimeThresholdAfterFastTyping = mainKeyboardViewAttr.getInt(
99                    R.styleable.MainKeyboardView_gestureStaticTimeThresholdAfterFastTyping,
100                    DEFAULT.mStaticTimeThresholdAfterFastTyping);
101            mDetectFastMoveSpeedThreshold = ResourceUtils.getFraction(mainKeyboardViewAttr,
102                    R.styleable.MainKeyboardView_gestureDetectFastMoveSpeedThreshold,
103                    DEFAULT.mDetectFastMoveSpeedThreshold);
104            mDynamicThresholdDecayDuration = mainKeyboardViewAttr.getInt(
105                    R.styleable.MainKeyboardView_gestureDynamicThresholdDecayDuration,
106                    DEFAULT.mDynamicThresholdDecayDuration);
107            mDynamicTimeThresholdFrom = mainKeyboardViewAttr.getInt(
108                    R.styleable.MainKeyboardView_gestureDynamicTimeThresholdFrom,
109                    DEFAULT.mDynamicTimeThresholdFrom);
110            mDynamicTimeThresholdTo = mainKeyboardViewAttr.getInt(
111                    R.styleable.MainKeyboardView_gestureDynamicTimeThresholdTo,
112                    DEFAULT.mDynamicTimeThresholdTo);
113            mDynamicDistanceThresholdFrom = ResourceUtils.getFraction(mainKeyboardViewAttr,
114                    R.styleable.MainKeyboardView_gestureDynamicDistanceThresholdFrom,
115                    DEFAULT.mDynamicDistanceThresholdFrom);
116            mDynamicDistanceThresholdTo = ResourceUtils.getFraction(mainKeyboardViewAttr,
117                    R.styleable.MainKeyboardView_gestureDynamicDistanceThresholdTo,
118                    DEFAULT.mDynamicDistanceThresholdTo);
119            mSamplingMinimumDistance = ResourceUtils.getFraction(mainKeyboardViewAttr,
120                    R.styleable.MainKeyboardView_gestureSamplingMinimumDistance,
121                    DEFAULT.mSamplingMinimumDistance);
122            mRecognitionMinimumTime = mainKeyboardViewAttr.getInt(
123                    R.styleable.MainKeyboardView_gestureRecognitionMinimumTime,
124                    DEFAULT.mRecognitionMinimumTime);
125            mRecognitionSpeedThreshold = ResourceUtils.getFraction(mainKeyboardViewAttr,
126                    R.styleable.MainKeyboardView_gestureRecognitionSpeedThreshold,
127                    DEFAULT.mRecognitionSpeedThreshold);
128        }
129    }
130
131    private static final int MSEC_PER_SEC = 1000;
132
133    public GestureStroke(final int pointerId, final GestureStrokeParams params) {
134        mPointerId = pointerId;
135        mParams = params;
136    }
137
138    public void setKeyboardGeometry(final int keyWidth) {
139        mKeyWidth = keyWidth;
140        // TODO: Find an appropriate base metric for these length. Maybe diagonal length of the key?
141        mDetectFastMoveSpeedThreshold = (int)(keyWidth * mParams.mDetectFastMoveSpeedThreshold);
142        mGestureDynamicDistanceThresholdFrom =
143                (int)(keyWidth * mParams.mDynamicDistanceThresholdFrom);
144        mGestureDynamicDistanceThresholdTo = (int)(keyWidth * mParams.mDynamicDistanceThresholdTo);
145        mGestureSamplingMinimumDistance = (int)(keyWidth * mParams.mSamplingMinimumDistance);
146        mGestureRecognitionSpeedThreshold = (int)(keyWidth * mParams.mRecognitionSpeedThreshold);
147        if (DEBUG) {
148            Log.d(TAG, String.format(
149                    "[%d] setKeyboardGeometry: keyWidth=%3d tT=%3d >> %3d tD=%3d >> %3d",
150                    mPointerId, keyWidth,
151                    mParams.mDynamicTimeThresholdFrom,
152                    mParams.mDynamicTimeThresholdTo,
153                    mGestureDynamicDistanceThresholdFrom,
154                    mGestureDynamicDistanceThresholdTo));
155        }
156    }
157
158    public void onDownEvent(final int x, final int y, final long downTime,
159            final long gestureFirstDownTime, final long lastTypingTime) {
160        reset();
161        final long elapsedTimeAfterTyping = downTime - lastTypingTime;
162        if (elapsedTimeAfterTyping < mParams.mStaticTimeThresholdAfterFastTyping) {
163            mAfterFastTyping = true;
164        }
165        if (DEBUG) {
166            Log.d(TAG, String.format("[%d] onDownEvent: dT=%3d%s", mPointerId,
167                    elapsedTimeAfterTyping, mAfterFastTyping ? " afterFastTyping" : ""));
168        }
169        final int elapsedTimeFromFirstDown = (int)(downTime - gestureFirstDownTime);
170        addPoint(x, y, elapsedTimeFromFirstDown, true /* isMajorEvent */);
171    }
172
173    private int getGestureDynamicDistanceThreshold(final int deltaTime) {
174        if (!mAfterFastTyping || deltaTime >= mParams.mDynamicThresholdDecayDuration) {
175            return mGestureDynamicDistanceThresholdTo;
176        }
177        final int decayedThreshold =
178                (mGestureDynamicDistanceThresholdFrom - mGestureDynamicDistanceThresholdTo)
179                * deltaTime / mParams.mDynamicThresholdDecayDuration;
180        return mGestureDynamicDistanceThresholdFrom - decayedThreshold;
181    }
182
183    private int getGestureDynamicTimeThreshold(final int deltaTime) {
184        if (!mAfterFastTyping || deltaTime >= mParams.mDynamicThresholdDecayDuration) {
185            return mParams.mDynamicTimeThresholdTo;
186        }
187        final int decayedThreshold =
188                (mParams.mDynamicTimeThresholdFrom - mParams.mDynamicTimeThresholdTo)
189                * deltaTime / mParams.mDynamicThresholdDecayDuration;
190        return mParams.mDynamicTimeThresholdFrom - decayedThreshold;
191    }
192
193    public final boolean isStartOfAGesture() {
194        if (!hasDetectedFastMove()) {
195            return false;
196        }
197        final int size = mEventTimes.getLength();
198        if (size <= 0) {
199            return false;
200        }
201        final int lastIndex = size - 1;
202        final int deltaTime = mEventTimes.get(lastIndex) - mDetectFastMoveTime;
203        if (deltaTime < 0) {
204            return false;
205        }
206        final int deltaDistance = getDistance(
207                mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex),
208                mDetectFastMoveX, mDetectFastMoveY);
209        final int distanceThreshold = getGestureDynamicDistanceThreshold(deltaTime);
210        final int timeThreshold = getGestureDynamicTimeThreshold(deltaTime);
211        final boolean isStartOfAGesture = deltaTime >= timeThreshold
212                && deltaDistance >= distanceThreshold;
213        if (DEBUG) {
214            Log.d(TAG, String.format("[%d] isStartOfAGesture: dT=%3d tT=%3d dD=%3d tD=%3d%s%s",
215                    mPointerId, deltaTime, timeThreshold,
216                    deltaDistance, distanceThreshold,
217                    mAfterFastTyping ? " afterFastTyping" : "",
218                    isStartOfAGesture ? " startOfAGesture" : ""));
219        }
220        return isStartOfAGesture;
221    }
222
223    protected void reset() {
224        mIncrementalRecognitionSize = 0;
225        mLastIncrementalBatchSize = 0;
226        mEventTimes.setLength(0);
227        mXCoordinates.setLength(0);
228        mYCoordinates.setLength(0);
229        mLastMajorEventTime = 0;
230        mDetectFastMoveTime = 0;
231        mAfterFastTyping = false;
232    }
233
234    private void appendPoint(final int x, final int y, final int time) {
235        mEventTimes.add(time);
236        mXCoordinates.add(x);
237        mYCoordinates.add(y);
238    }
239
240    private void updateMajorEvent(final int x, final int y, final int time) {
241        mLastMajorEventTime = time;
242        mLastMajorEventX = x;
243        mLastMajorEventY = y;
244    }
245
246    private final boolean hasDetectedFastMove() {
247        return mDetectFastMoveTime > 0;
248    }
249
250    private int detectFastMove(final int x, final int y, final int time) {
251        final int size = mEventTimes.getLength();
252        final int lastIndex = size - 1;
253        final int lastX = mXCoordinates.get(lastIndex);
254        final int lastY = mYCoordinates.get(lastIndex);
255        final int dist = getDistance(lastX, lastY, x, y);
256        final int msecs = time - mEventTimes.get(lastIndex);
257        if (msecs > 0) {
258            final int pixels = getDistance(lastX, lastY, x, y);
259            final int pixelsPerSec = pixels * MSEC_PER_SEC;
260            if (DEBUG_SPEED) {
261                final float speed = (float)pixelsPerSec / msecs / mKeyWidth;
262                Log.d(TAG, String.format("[%d] detectFastMove: speed=%5.2f", mPointerId, speed));
263            }
264            // Equivalent to (pixels / msecs < mStartSpeedThreshold / MSEC_PER_SEC)
265            if (!hasDetectedFastMove() && pixelsPerSec > mDetectFastMoveSpeedThreshold * msecs) {
266                if (DEBUG) {
267                    final float speed = (float)pixelsPerSec / msecs / mKeyWidth;
268                    Log.d(TAG, String.format(
269                            "[%d] detectFastMove: speed=%5.2f T=%3d points=%3d fastMove",
270                            mPointerId, speed, time, size));
271                }
272                mDetectFastMoveTime = time;
273                mDetectFastMoveX = x;
274                mDetectFastMoveY = y;
275            }
276        }
277        return dist;
278    }
279
280    public void addPoint(final int x, final int y, final int time, final boolean isMajorEvent) {
281        final int size = mEventTimes.getLength();
282        if (size <= 0) {
283            // Down event
284            appendPoint(x, y, time);
285            updateMajorEvent(x, y, time);
286        } else {
287            final int distance = detectFastMove(x, y, time);
288            if (distance > mGestureSamplingMinimumDistance) {
289                appendPoint(x, y, time);
290            }
291        }
292        if (isMajorEvent) {
293            updateIncrementalRecognitionSize(x, y, time);
294            updateMajorEvent(x, y, time);
295        }
296    }
297
298    private void updateIncrementalRecognitionSize(final int x, final int y, final int time) {
299        final int msecs = (int)(time - mLastMajorEventTime);
300        if (msecs <= 0) {
301            return;
302        }
303        final int pixels = getDistance(mLastMajorEventX, mLastMajorEventY, x, y);
304        final int pixelsPerSec = pixels * MSEC_PER_SEC;
305        // Equivalent to (pixels / msecs < mGestureRecognitionThreshold / MSEC_PER_SEC)
306        if (pixelsPerSec < mGestureRecognitionSpeedThreshold * msecs) {
307            mIncrementalRecognitionSize = mEventTimes.getLength();
308        }
309    }
310
311    public final boolean hasRecognitionTimePast(
312            final long currentTime, final long lastRecognitionTime) {
313        return currentTime > lastRecognitionTime + mParams.mRecognitionMinimumTime;
314    }
315
316    public final void appendAllBatchPoints(final InputPointers out) {
317        appendBatchPoints(out, mEventTimes.getLength());
318    }
319
320    public final void appendIncrementalBatchPoints(final InputPointers out) {
321        appendBatchPoints(out, mIncrementalRecognitionSize);
322    }
323
324    private void appendBatchPoints(final InputPointers out, final int size) {
325        final int length = size - mLastIncrementalBatchSize;
326        if (length <= 0) {
327            return;
328        }
329        out.append(mPointerId, mEventTimes, mXCoordinates, mYCoordinates,
330                mLastIncrementalBatchSize, length);
331        mLastIncrementalBatchSize = size;
332    }
333
334    private static int getDistance(final int x1, final int y1, final int x2, final int y2) {
335        final int dx = x1 - x2;
336        final int dy = y1 - y2;
337        // Note that, in recent versions of Android, FloatMath is actually slower than
338        // java.lang.Math due to the way the JIT optimizes java.lang.Math.
339        return (int)Math.sqrt(dx * dx + dy * dy);
340    }
341}
342