diff options
Diffstat (limited to 'src/com/android/gallery3d/ingest/MtpDeviceIndex.java')
-rw-r--r-- | src/com/android/gallery3d/ingest/MtpDeviceIndex.java | 596 |
1 files changed, 596 insertions, 0 deletions
diff --git a/src/com/android/gallery3d/ingest/MtpDeviceIndex.java b/src/com/android/gallery3d/ingest/MtpDeviceIndex.java new file mode 100644 index 000000000..d30f94a87 --- /dev/null +++ b/src/com/android/gallery3d/ingest/MtpDeviceIndex.java @@ -0,0 +1,596 @@ +/* + * 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.gallery3d.ingest; + +import android.mtp.MtpConstants; +import android.mtp.MtpDevice; +import android.mtp.MtpObjectInfo; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.Stack; + +/** + * MTP objects in the index are organized into "buckets," or groupings. + * At present, these buckets are based on the date an item was created. + * + * When the index is created, the buckets are sorted in their natural + * order, and the items within the buckets sorted by the date they are taken. + * + * The index enables the access of items and bucket labels as one unified list. + * For example, let's say we have the following data in the index: + * [Bucket A]: [photo 1], [photo 2] + * [Bucket B]: [photo 3] + * + * Then the items can be thought of as being organized as a 5 element list: + * [Bucket A], [photo 1], [photo 2], [Bucket B], [photo 3] + * + * The data can also be accessed in descending order, in which case the list + * would be a bit different from simply reversing the ascending list, since the + * bucket labels need to always be at the beginning: + * [Bucket B], [photo 3], [Bucket A], [photo 2], [photo 1] + * + * The index enables all the following operations in constant time, both for + * ascending and descending views of the data: + * - get/getAscending/getDescending: get an item at a specified list position + * - size: get the total number of items (bucket labels and MTP objects) + * - getFirstPositionForBucketNumber + * - getBucketNumberForPosition + * - isFirstInBucket + * + * See the comments in buildLookupIndex for implementation notes. + */ +public class MtpDeviceIndex { + + public static final int FORMAT_MOV = 0x300D; // For some reason this is not in MtpConstants + + public static final Set<Integer> SUPPORTED_IMAGE_FORMATS; + public static final Set<Integer> SUPPORTED_VIDEO_FORMATS; + + static { + SUPPORTED_IMAGE_FORMATS = new HashSet<Integer>(); + SUPPORTED_IMAGE_FORMATS.add(MtpConstants.FORMAT_JFIF); + SUPPORTED_IMAGE_FORMATS.add(MtpConstants.FORMAT_EXIF_JPEG); + SUPPORTED_IMAGE_FORMATS.add(MtpConstants.FORMAT_PNG); + SUPPORTED_IMAGE_FORMATS.add(MtpConstants.FORMAT_GIF); + SUPPORTED_IMAGE_FORMATS.add(MtpConstants.FORMAT_BMP); + + SUPPORTED_VIDEO_FORMATS = new HashSet<Integer>(); + SUPPORTED_VIDEO_FORMATS.add(MtpConstants.FORMAT_3GP_CONTAINER); + SUPPORTED_VIDEO_FORMATS.add(MtpConstants.FORMAT_AVI); + SUPPORTED_VIDEO_FORMATS.add(MtpConstants.FORMAT_MP4_CONTAINER); + SUPPORTED_VIDEO_FORMATS.add(MtpConstants.FORMAT_MPEG); + // TODO: add FORMAT_MOV once Media Scanner supports .mov files + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((mDevice == null) ? 0 : mDevice.getDeviceId()); + result = prime * result + mGeneration; + return result; + } + + public interface ProgressListener { + public void onObjectIndexed(MtpObjectInfo object, int numVisited); + + public void onSorting(); + + public void onIndexFinish(); + } + + public enum SortOrder { + Ascending, Descending + } + + private MtpDevice mDevice; + private int[] mUnifiedLookupIndex; + private MtpObjectInfo[] mMtpObjects; + private DateBucket[] mBuckets; + private int mGeneration = 0; + + public enum Progress { + Uninitialized, Initialized, Pending, Started, Sorting, Finished + } + + private Progress mProgress = Progress.Uninitialized; + private ProgressListener mProgressListener; + + private static final MtpDeviceIndex sInstance = new MtpDeviceIndex(); + private static final MtpObjectTimestampComparator sMtpObjectComparator = + new MtpObjectTimestampComparator(); + + public static MtpDeviceIndex getInstance() { + return sInstance; + } + + private MtpDeviceIndex() { + } + + synchronized public MtpDevice getDevice() { + return mDevice; + } + + /** + * Sets the MtpDevice that should be indexed and initializes state, but does + * not kick off the actual indexing task, which is instead done by using + * {@link #getIndexRunnable()} + * + * @param device The MtpDevice that should be indexed + */ + synchronized public void setDevice(MtpDevice device) { + if (device == mDevice) return; + mDevice = device; + resetState(); + } + + /** + * Provides a Runnable for the indexing task assuming the state has already + * been correctly initialized (by calling {@link #setDevice(MtpDevice)}) and + * has not already been run. + * + * @return Runnable for the main indexing task + */ + synchronized public Runnable getIndexRunnable() { + if (mProgress != Progress.Initialized) return null; + mProgress = Progress.Pending; + return new IndexRunnable(mDevice); + } + + synchronized public boolean indexReady() { + return mProgress == Progress.Finished; + } + + synchronized public Progress getProgress() { + return mProgress; + } + + /** + * @param listener Listener to change to + * @return Progress at the time the listener was added (useful for + * configuring initial UI state) + */ + synchronized public Progress setProgressListener(ProgressListener listener) { + mProgressListener = listener; + return mProgress; + } + + /** + * Make the listener null if it matches the argument + * + * @param listener Listener to unset, if currently registered + */ + synchronized public void unsetProgressListener(ProgressListener listener) { + if (mProgressListener == listener) + mProgressListener = null; + } + + /** + * @return The total number of elements in the index (labels and items) + */ + public int size() { + return mProgress == Progress.Finished ? mUnifiedLookupIndex.length : 0; + } + + /** + * @param position Index of item to fetch, where 0 is the first item in the + * specified order + * @param order + * @return the bucket label or MtpObjectInfo at the specified position and + * order + */ + public Object get(int position, SortOrder order) { + if (mProgress != Progress.Finished) return null; + if(order == SortOrder.Ascending) { + DateBucket bucket = mBuckets[mUnifiedLookupIndex[position]]; + if (bucket.unifiedStartIndex == position) { + return bucket.bucket; + } else { + return mMtpObjects[bucket.itemsStartIndex + position - 1 + - bucket.unifiedStartIndex]; + } + } else { + int zeroIndex = mUnifiedLookupIndex.length - 1 - position; + DateBucket bucket = mBuckets[mUnifiedLookupIndex[zeroIndex]]; + if (bucket.unifiedEndIndex == zeroIndex) { + return bucket.bucket; + } else { + return mMtpObjects[bucket.itemsStartIndex + zeroIndex + - bucket.unifiedStartIndex]; + } + } + } + + /** + * @param position Index of item to fetch from a view of the data that doesn't + * include labels and is in the specified order + * @return position-th item in specified order, when not including labels + */ + public MtpObjectInfo getWithoutLabels(int position, SortOrder order) { + if (mProgress != Progress.Finished) return null; + if (order == SortOrder.Ascending) { + return mMtpObjects[position]; + } else { + return mMtpObjects[mMtpObjects.length - 1 - position]; + } + } + + /** + * Although this is O(log(number of buckets)), and thus should not be used + * in hotspots, even if the attached device has items for every day for + * a five-year timeframe, it would still only take 11 iterations at most, + * so shouldn't be a huge issue. + * @param position Index of item to map from a view of the data that doesn't + * include labels and is in the specified order + * @param order + * @return position in a view of the data that does include labels + */ + public int getPositionFromPositionWithoutLabels(int position, SortOrder order) { + if (mProgress != Progress.Finished) return -1; + if (order == SortOrder.Descending) { + position = mMtpObjects.length - 1 - position; + } + int bucketNumber = 0; + int iMin = 0; + int iMax = mBuckets.length - 1; + while (iMax >= iMin) { + int iMid = (iMax + iMin) / 2; + if (mBuckets[iMid].itemsStartIndex + mBuckets[iMid].numItems <= position) { + iMin = iMid + 1; + } else if (mBuckets[iMid].itemsStartIndex > position) { + iMax = iMid - 1; + } else { + bucketNumber = iMid; + break; + } + } + int mappedPos = mBuckets[bucketNumber].unifiedStartIndex + + position - mBuckets[bucketNumber].itemsStartIndex; + if (order == SortOrder.Descending) { + mappedPos = mUnifiedLookupIndex.length - 1 - mappedPos; + } + return mappedPos; + } + + public int getPositionWithoutLabelsFromPosition(int position, SortOrder order) { + if (mProgress != Progress.Finished) return -1; + if(order == SortOrder.Ascending) { + DateBucket bucket = mBuckets[mUnifiedLookupIndex[position]]; + if (bucket.unifiedStartIndex == position) position++; + return bucket.itemsStartIndex + position - 1 - bucket.unifiedStartIndex; + } else { + int zeroIndex = mUnifiedLookupIndex.length - 1 - position; + DateBucket bucket = mBuckets[mUnifiedLookupIndex[zeroIndex]]; + if (bucket.unifiedEndIndex == zeroIndex) zeroIndex--; + return mMtpObjects.length - 1 - bucket.itemsStartIndex + - zeroIndex + bucket.unifiedStartIndex; + } + } + + /** + * @return The number of MTP items in the index (without labels) + */ + public int sizeWithoutLabels() { + return mProgress == Progress.Finished ? mMtpObjects.length : 0; + } + + public int getFirstPositionForBucketNumber(int bucketNumber, SortOrder order) { + if (order == SortOrder.Ascending) { + return mBuckets[bucketNumber].unifiedStartIndex; + } else { + return mUnifiedLookupIndex.length - mBuckets[mBuckets.length - 1 - bucketNumber].unifiedEndIndex - 1; + } + } + + public int getBucketNumberForPosition(int position, SortOrder order) { + if (order == SortOrder.Ascending) { + return mUnifiedLookupIndex[position]; + } else { + return mBuckets.length - 1 - mUnifiedLookupIndex[mUnifiedLookupIndex.length - 1 - position]; + } + } + + public boolean isFirstInBucket(int position, SortOrder order) { + if (order == SortOrder.Ascending) { + return mBuckets[mUnifiedLookupIndex[position]].unifiedStartIndex == position; + } else { + position = mUnifiedLookupIndex.length - 1 - position; + return mBuckets[mUnifiedLookupIndex[position]].unifiedEndIndex == position; + } + } + + private Object[] mCachedReverseBuckets; + + public Object[] getBuckets(SortOrder order) { + if (mBuckets == null) return null; + if (order == SortOrder.Ascending) { + return mBuckets; + } else { + if (mCachedReverseBuckets == null) { + computeReversedBuckets(); + } + return mCachedReverseBuckets; + } + } + + /* + * See the comments for buildLookupIndex for notes on the specific fields of + * this class. + */ + private class DateBucket implements Comparable<DateBucket> { + SimpleDate bucket; + List<MtpObjectInfo> tempElementsList = new ArrayList<MtpObjectInfo>(); + int unifiedStartIndex; + int unifiedEndIndex; + int itemsStartIndex; + int numItems; + + public DateBucket(SimpleDate bucket) { + this.bucket = bucket; + } + + public DateBucket(SimpleDate bucket, MtpObjectInfo firstElement) { + this(bucket); + tempElementsList.add(firstElement); + } + + void sortElements(Comparator<MtpObjectInfo> comparator) { + Collections.sort(tempElementsList, comparator); + } + + @Override + public String toString() { + return bucket.toString(); + } + + @Override + public int hashCode() { + return bucket.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof DateBucket)) return false; + DateBucket other = (DateBucket) obj; + if (bucket == null) { + if (other.bucket != null) return false; + } else if (!bucket.equals(other.bucket)) { + return false; + } + return true; + } + + @Override + public int compareTo(DateBucket another) { + return this.bucket.compareTo(another.bucket); + } + } + + /** + * Comparator to sort MtpObjectInfo objects by date created. + */ + private static class MtpObjectTimestampComparator implements Comparator<MtpObjectInfo> { + @Override + public int compare(MtpObjectInfo o1, MtpObjectInfo o2) { + long diff = o1.getDateCreated() - o2.getDateCreated(); + if (diff < 0) { + return -1; + } else if (diff == 0) { + return 0; + } else { + return 1; + } + } + } + + private void resetState() { + mGeneration++; + mUnifiedLookupIndex = null; + mMtpObjects = null; + mBuckets = null; + mCachedReverseBuckets = null; + mProgress = (mDevice == null) ? Progress.Uninitialized : Progress.Initialized; + } + + + private class IndexRunnable implements Runnable { + private int[] mUnifiedLookupIndex; + private MtpObjectInfo[] mMtpObjects; + private DateBucket[] mBuckets; + private Map<SimpleDate, DateBucket> mBucketsTemp; + private MtpDevice mDevice; + private int mNumObjects = 0; + + private class IndexingException extends Exception {}; + + public IndexRunnable(MtpDevice device) { + mDevice = device; + } + + /* + * Implementation note: this is the way the index supports a lot of its operations in + * constant time and respecting the need to have bucket names always come before items + * in that bucket when accessing the list sequentially, both in ascending and descending + * orders. + * + * Let's say the data we have in the index is the following: + * [Bucket A]: [photo 1], [photo 2] + * [Bucket B]: [photo 3] + * + * In this case, the lookup index array would be + * [0, 0, 0, 1, 1] + * + * Now, whether we access the list in ascending or descending order, we know which bucket + * to look in (0 corresponds to A and 1 to B), and can return the bucket label as the first + * item in a bucket as needed. The individual IndexBUckets have a startIndex and endIndex + * that correspond to indices in this lookup index array, allowing us to calculate the + * offset of the specific item we want from within a specific bucket. + */ + private void buildLookupIndex() { + int numBuckets = mBuckets.length; + mUnifiedLookupIndex = new int[mNumObjects + numBuckets]; + int currentUnifiedIndexEntry = 0; + int nextUnifiedEntry; + + mMtpObjects = new MtpObjectInfo[mNumObjects]; + int currentItemsEntry = 0; + for (int i = 0; i < numBuckets; i++) { + DateBucket bucket = mBuckets[i]; + nextUnifiedEntry = currentUnifiedIndexEntry + bucket.tempElementsList.size() + 1; + Arrays.fill(mUnifiedLookupIndex, currentUnifiedIndexEntry, nextUnifiedEntry, i); + bucket.unifiedStartIndex = currentUnifiedIndexEntry; + bucket.unifiedEndIndex = nextUnifiedEntry - 1; + currentUnifiedIndexEntry = nextUnifiedEntry; + + bucket.itemsStartIndex = currentItemsEntry; + bucket.numItems = bucket.tempElementsList.size(); + for (int j = 0; j < bucket.numItems; j++) { + mMtpObjects[currentItemsEntry] = bucket.tempElementsList.get(j); + currentItemsEntry++; + } + bucket.tempElementsList = null; + } + } + + private void copyResults() { + MtpDeviceIndex.this.mUnifiedLookupIndex = mUnifiedLookupIndex; + MtpDeviceIndex.this.mMtpObjects = mMtpObjects; + MtpDeviceIndex.this.mBuckets = mBuckets; + mUnifiedLookupIndex = null; + mMtpObjects = null; + mBuckets = null; + } + + @Override + public void run() { + try { + indexDevice(); + } catch (IndexingException e) { + synchronized (MtpDeviceIndex.this) { + resetState(); + if (mProgressListener != null) { + mProgressListener.onIndexFinish(); + } + } + } + } + + private void indexDevice() throws IndexingException { + synchronized (MtpDeviceIndex.this) { + mProgress = Progress.Started; + } + mBucketsTemp = new HashMap<SimpleDate, DateBucket>(); + for (int storageId : mDevice.getStorageIds()) { + if (mDevice != getDevice()) throw new IndexingException(); + Stack<Integer> pendingDirectories = new Stack<Integer>(); + pendingDirectories.add(0xFFFFFFFF); // start at the root of the device + while (!pendingDirectories.isEmpty()) { + if (mDevice != getDevice()) throw new IndexingException(); + int dirHandle = pendingDirectories.pop(); + for (int objectHandle : mDevice.getObjectHandles(storageId, 0, dirHandle)) { + MtpObjectInfo objectInfo = mDevice.getObjectInfo(objectHandle); + if (objectInfo == null) throw new IndexingException(); + int format = objectInfo.getFormat(); + if (format == MtpConstants.FORMAT_ASSOCIATION) { + pendingDirectories.add(objectHandle); + } else if (SUPPORTED_IMAGE_FORMATS.contains(format) + || SUPPORTED_VIDEO_FORMATS.contains(format)) { + addObject(objectInfo); + } + } + } + } + Collection<DateBucket> values = mBucketsTemp.values(); + mBucketsTemp = null; + mBuckets = values.toArray(new DateBucket[values.size()]); + values = null; + synchronized (MtpDeviceIndex.this) { + mProgress = Progress.Sorting; + if (mProgressListener != null) { + mProgressListener.onSorting(); + } + } + sortAll(); + buildLookupIndex(); + synchronized (MtpDeviceIndex.this) { + if (mDevice != getDevice()) throw new IndexingException(); + copyResults(); + + /* + * In order for getBuckets to operate in constant time for descending + * order, we must precompute a reversed array of the buckets, mainly + * because the android.widget.SectionIndexer interface which adapters + * that call getBuckets implement depends on section numbers to be + * ascending relative to the scroll position, so we must have this for + * descending order or the scrollbar goes crazy. + */ + computeReversedBuckets(); + + mProgress = Progress.Finished; + if (mProgressListener != null) { + mProgressListener.onIndexFinish(); + } + } + } + + private SimpleDate mDateInstance = new SimpleDate(); + + private void addObject(MtpObjectInfo objectInfo) { + mNumObjects++; + mDateInstance.setTimestamp(objectInfo.getDateCreated()); + DateBucket bucket = mBucketsTemp.get(mDateInstance); + if (bucket == null) { + bucket = new DateBucket(mDateInstance, objectInfo); + mBucketsTemp.put(mDateInstance, bucket); + mDateInstance = new SimpleDate(); // only create new date + // objects when they are used + return; + } else { + bucket.tempElementsList.add(objectInfo); + } + if (mProgressListener != null) { + mProgressListener.onObjectIndexed(objectInfo, mNumObjects); + } + } + + private void sortAll() { + Arrays.sort(mBuckets); + for (DateBucket bucket : mBuckets) { + bucket.sortElements(sMtpObjectComparator); + } + } + + } + + private void computeReversedBuckets() { + mCachedReverseBuckets = new Object[mBuckets.length]; + for (int i = 0; i < mCachedReverseBuckets.length; i++) { + mCachedReverseBuckets[i] = mBuckets[mBuckets.length - 1 - i]; + } + } +} |