gallery3d/ingest/MtpDeviceIndex.java

/*
 * 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.List;
import java.util.Map;
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 {

    @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();
                        switch (objectInfo.getFormat()) {
                            case MtpConstants.FORMAT_JFIF:
                            case MtpConstants.FORMAT_EXIF_JPEG:
                                addObject(objectInfo);
                                break;
                            case MtpConstants.FORMAT_ASSOCIATION:
                                pendingDirectories.add(objectHandle);
                                break;
                        }
                    }
                }
            }
            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];
        }
    }
}