From ce760cd6df920efff026c8757a371692ac54fad4 Mon Sep 17 00:00:00 2001
From: Marc Capdevielle <marc.capdevielle@gmail.com>
Date: Wed, 3 Feb 2010 11:15:38 +0100
Subject: Use a circular buffer in VelocityTracker

Optimizes the frequently called addPoint() method while keeping the
same velocity computation.

Thx Cyril Mottier for help and tests.
---
 core/java/android/view/VelocityTracker.java | 88 +++++++++++------------------
 1 file changed, 33 insertions(+), 55 deletions(-)

diff --git a/core/java/android/view/VelocityTracker.java b/core/java/android/view/VelocityTracker.java
index 5d89c46a3db1..fd173eb68158 100644
--- a/core/java/android/view/VelocityTracker.java
+++ b/core/java/android/view/VelocityTracker.java
@@ -59,6 +59,8 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     final float mPastY[] = new float[NUM_PAST];
     final long mPastTime[] = new long[NUM_PAST];
 
+    int mLastTouch;
+
     float mYVelocity;
     float mXVelocity;
 
@@ -105,7 +107,10 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * Reset the velocity tracker back to its initial state.
      */
     public void clear() {
-        mPastTime[0] = 0;
+        final long[] pastTime = mPastTime;
+        for (int i = 0; i < NUM_PAST; i++) {
+            pastTime[i] = 0;
+        }
     }
     
     /**
@@ -128,42 +133,11 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     }
 
     private void addPoint(float x, float y, long time) {
-        int drop = -1;
-        int i;
-        if (localLOGV) Log.v(TAG, "Adding past y=" + y + " time=" + time);
-        final long[] pastTime = mPastTime;
-        for (i=0; i<NUM_PAST; i++) {
-            if (pastTime[i] == 0) {
-                break;
-            } else if (pastTime[i] < time-LONGEST_PAST_TIME) {
-                if (localLOGV) Log.v(TAG, "Dropping past too old at "
-                        + i + " time=" + pastTime[i]);
-                drop = i;
-            }
-        }
-        if (localLOGV) Log.v(TAG, "Add index: " + i);
-        if (i == NUM_PAST && drop < 0) {
-            drop = 0;
-        }
-        if (drop == i) drop--;
-        final float[] pastX = mPastX;
-        final float[] pastY = mPastY;
-        if (drop >= 0) {
-            if (localLOGV) Log.v(TAG, "Dropping up to #" + drop);
-            final int start = drop+1;
-            final int count = NUM_PAST-drop-1;
-            System.arraycopy(pastX, start, pastX, 0, count);
-            System.arraycopy(pastY, start, pastY, 0, count);
-            System.arraycopy(pastTime, start, pastTime, 0, count);
-            i -= (drop+1);
-        }
-        pastX[i] = x;
-        pastY[i] = y;
-        pastTime[i] = time;
-        i++;
-        if (i < NUM_PAST) {
-            pastTime[i] = 0;
-        }
+        final int lastTouch = (mLastTouch + 1) % NUM_PAST;
+        mPastX[lastTouch] = x;
+        mPastY[lastTouch] = y;
+        mPastTime[lastTouch] = time;
+        mLastTouch = lastTouch;
     }
 
     /**
@@ -193,35 +167,39 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
         final float[] pastX = mPastX;
         final float[] pastY = mPastY;
         final long[] pastTime = mPastTime;
+        final int lastTouch = mLastTouch;
+        
+        // find oldest acceptable time
+        int oldestTouch = lastTouch;
+        if (pastTime[lastTouch] > 0) { // cleared ?
+            oldestTouch = (lastTouch + 1) % NUM_PAST;
+            final float acceptableTime = pastTime[lastTouch] - LONGEST_PAST_TIME;
+            while (pastTime[oldestTouch] < acceptableTime) {
+                oldestTouch = (oldestTouch + 1) % NUM_PAST;
+            }
+        }
         
         // Kind-of stupid.
-        final float oldestX = pastX[0];
-        final float oldestY = pastY[0];
-        final long oldestTime = pastTime[0];
+        final float oldestX = pastX[oldestTouch];
+        final float oldestY = pastY[oldestTouch];
+        final long oldestTime = pastTime[oldestTouch];
         float accumX = 0;
         float accumY = 0;
-        int N=0;
-        while (N < NUM_PAST) {
-            if (pastTime[N] == 0) {
-                break;
-            }
-            N++;
-        }
+        float N = (lastTouch - oldestTouch + NUM_PAST) % NUM_PAST + 1;
         // Skip the last received event, since it is probably pretty noisy.
         if (N > 3) N--;
-        
+
         for (int i=1; i < N; i++) {
-            final int dur = (int)(pastTime[i] - oldestTime);
+            final int j = (oldestTouch + i) % NUM_PAST;
+            final int dur = (int)(pastTime[j] - oldestTime);
             if (dur == 0) continue;
-            float dist = pastX[i] - oldestX;
+            float dist = pastX[j] - oldestX;
             float vel = (dist/dur) * units;   // pixels/frame.
-            if (accumX == 0) accumX = vel;
-            else accumX = (accumX + vel) * .5f;
+            accumX = (accumX == 0) ? vel : (accumX + vel) * .5f;
             
-            dist = pastY[i] - oldestY;
+            dist = pastY[j] - oldestY;
             vel = (dist/dur) * units;   // pixels/frame.
-            if (accumY == 0) accumY = vel;
-            else accumY = (accumY + vel) * .5f;
+            accumY = (accumY == 0) ? vel : (accumY + vel) * .5f;
         }
         mXVelocity = accumX < 0.0f ? Math.max(accumX, -maxVelocity) : Math.min(accumX, maxVelocity);
         mYVelocity = accumY < 0.0f ? Math.max(accumY, -maxVelocity) : Math.min(accumY, maxVelocity);
-- 
cgit v1.2.3-59-g8ed1b