Avoid expensive O(n) main-thread operation when adding Photo Sphere.

  Bug: 10747001

Change-Id: I8dcc3c5e7dd12879a927aa82e71bea0c6370ccda

2 files changed, 114 insertions, 21 deletions

diff --git a/src/com/android/camera/data/CameraDataAdapter.java b/src/com/android/camera/data/CameraDataAdapter.java
index 892aa1056..cf0fb2f98 100644
--- a/src/com/android/camera/data/CameraDataAdapter.java
+++ b/src/com/android/camera/data/CameraDataAdapter.java
@@ -31,9 +31,7 @@ import com.android.camera.Storage;
 import com.android.camera.ui.FilmStripView.ImageData;
 
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.Comparator;
-import java.util.List;
 
 /**
  * A {@link LocalDataAdapter} that provides data in the camera folder.
@@ -44,7 +42,7 @@ public class CameraDataAdapter implements LocalDataAdapter {
     private static final int DEFAULT_DECODE_SIZE = 1600;
     private static final String[] CAMERA_PATH = { Storage.DIRECTORY + "%" };
 
-    private List<LocalData> mImages;
+    private LocalDataList mImages;
 
     private Listener mListener;
     private Drawable mPlaceHolder;
@@ -55,7 +53,7 @@ public class CameraDataAdapter implements LocalDataAdapter {
     private LocalData mLocalDataToDelete;
 
     public CameraDataAdapter(Drawable placeHolder) {
-        mImages = new ArrayList<LocalData>();
+        mImages = new LocalDataList();
         mPlaceHolder = placeHolder;
     }
 
@@ -176,16 +174,10 @@ public class CameraDataAdapter implements LocalDataAdapter {
 
     @Override
     public int findDataByContentUri(Uri uri) {
-        for (int i = 0; i < mImages.size(); i++) {
-            Uri u = mImages.get(i).getContentUri();
-            if (u == null) {
-                continue;
-            }
-            if (u.equals(uri)) {
-                return i;
-            }
-        }
-        return -1;
+        // LocalDataList will return in O(1) if the uri is not contained.
+        // Otherwise the performance is O(n), but this is acceptable as we will
+        // most often call this to find an element at the beginning of the list.
+        return mImages.indexOf(uri);
     }
 
     @Override
@@ -209,7 +201,7 @@ public class CameraDataAdapter implements LocalDataAdapter {
 
     @Override
     public void flush() {
-        replaceData(new ArrayList<LocalData>());
+        replaceData(new LocalDataList());
     }
 
     @Override
@@ -260,7 +252,7 @@ public class CameraDataAdapter implements LocalDataAdapter {
     }
 
     /** Update all the data */
-    private void replaceData(List<LocalData> list) {
+    private void replaceData(LocalDataList list) {
         if (list.size() == 0 && mImages.size() == 0) {
             return;
         }
@@ -270,7 +262,7 @@ public class CameraDataAdapter implements LocalDataAdapter {
         }
     }
 
-    private class QueryTask extends AsyncTask<ContentResolver, Void, List<LocalData>> {
+    private class QueryTask extends AsyncTask<ContentResolver, Void, LocalDataList> {
 
         /**
          * Loads all the photo and video data in the camera folder in background
@@ -280,8 +272,8 @@ public class CameraDataAdapter implements LocalDataAdapter {
          * @return An {@link ArrayList} of all loaded data.
          */
         @Override
-        protected List<LocalData> doInBackground(ContentResolver... resolver) {
-            List<LocalData> l = new ArrayList<LocalData>();
+        protected LocalDataList doInBackground(ContentResolver... resolver) {
+            LocalDataList l = new LocalDataList();
             // Photos
             Cursor c = resolver[0].query(
                     LocalMediaData.PhotoData.CONTENT_URI,
@@ -336,14 +328,14 @@ public class CameraDataAdapter implements LocalDataAdapter {
             }
 
             if (l.size() != 0) {
-                Collections.sort(l, new LocalData.NewestFirstComparator());
+                l.sort(new LocalData.NewestFirstComparator());
             }
 
             return l;
         }
 
         @Override
-        protected void onPostExecute(List<LocalData> l) {
+        protected void onPostExecute(LocalDataList l) {
             replaceData(l);
         }
     }
diff --git a/src/com/android/camera/data/LocalDataList.java b/src/com/android/camera/data/LocalDataList.java
new file mode 100644
index 000000000..3ccc4de54
--- /dev/null
+++ b/src/com/android/camera/data/LocalDataList.java
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2013 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.camera.data;
+
+import android.net.Uri;
+
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.LinkedList;
+
+/**
+ * Fast access data structure for an ordered LocalData list.
+ */
+public class LocalDataList {
+    /**
+     * We use this as a way to compare a Uri to LocalData instances inside a
+     * LinkedList. A linked list in indexOf does a other.equals(get(i)).
+     */
+    private static class UriWrapper {
+        private final Uri mUri;
+
+        public UriWrapper(Uri uri) {
+            mUri = uri;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (!(o instanceof LocalData)) {
+                return false;
+            }
+            return mUri.equals(((LocalData) o).getContentUri());
+        }
+    }
+
+    private LinkedList<LocalData> mList = new LinkedList<LocalData>();
+    private HashMap<Uri, LocalData> mUriMap = new HashMap<Uri, LocalData>();
+
+    public LocalData get(int index) {
+        return mList.get(index);
+    }
+
+    public LocalData remove(int index) {
+        LocalData removedItem = mList.remove(index);
+        mUriMap.remove(removedItem);
+        return removedItem;
+    }
+
+    public LocalData get(Uri uri) {
+        return mUriMap.get(uri);
+    }
+
+    public void set(int pos, LocalData data) {
+        mList.set(pos, data);
+        mUriMap.put(data.getContentUri(), data);
+    }
+
+    public void add(LocalData data) {
+        mList.add(data);
+        mUriMap.put(data.getContentUri(), data);
+    }
+
+    public void add(int pos, LocalData data) {
+        mList.add(pos, data);
+        mUriMap.put(data.getContentUri(), data);
+    }
+
+    public int size() {
+        return mList.size();
+    }
+
+    public void sort(Comparator<LocalData> comparator) {
+        Collections.sort(mList, comparator);
+    }
+
+    /**
+     * This implementation routes through to LinkedList.indexOf, so performs in
+     * O(n) but has a fast exit path for when the uri is not contained in the
+     * list, and immediately returns -1;
+     */
+    public int indexOf(Uri uri) {
+        if (!mUriMap.containsKey(uri)) {
+            return -1;
+        }
+        return mList.indexOf(new UriWrapper(uri));
+    }
+}