src/com/android/gallery3d/ingest/MtpDeviceIndex.java

   1 /*
   2  * Copyright (C) 2013 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.android.gallery3d.ingest;
  18
  19 import android.mtp.MtpConstants;
  20 import android.mtp.MtpDevice;
  21 import android.mtp.MtpObjectInfo;
  22
  23 import java.util.ArrayList;
  24 import java.util.Arrays;
  25 import java.util.Collection;
  26 import java.util.Collections;
  27 import java.util.Comparator;
  28 import java.util.HashMap;
  29 import java.util.List;
  30 import java.util.Map;
  31 import java.util.Stack;
  32
  33 /**
  34  * MTP objects in the index are organized into "buckets," or groupings.
  35  * At present, these buckets are based on the date an item was created.
  36  *
  37  * When the index is created, the buckets are sorted in their natural
  38  * order, and the items within the buckets sorted by the date they are taken.
  39  *
  40  * The index enables the access of items and bucket labels as one unified list.
  41  * For example, let's say we have the following data in the index:
  42  *    [Bucket A]: [photo 1], [photo 2]
  43  *    [Bucket B]: [photo 3]
  44  *
  45  * Then the items can be thought of as being organized as a 5 element list:
  46  *   [Bucket A], [photo 1], [photo 2], [Bucket B], [photo 3]
  47  *
  48  * The data can also be accessed in descending order, in which case the list
  49  * would be a bit different from simply reversing the ascending list, since the
  50  * bucket labels need to always be at the beginning:
  51  *   [Bucket B], [photo 3], [Bucket A], [photo 2], [photo 1]
  52  *
  53  * The index enables all the following operations in constant time, both for
  54  * ascending and descending views of the data:
  55  *   - get/getAscending/getDescending: get an item at a specified list position
  56  *   - size: get the total number of items (bucket labels and MTP objects)
  57  *   - getFirstPositionForBucketNumber
  58  *   - getBucketNumberForPosition
  59  *   - isFirstInBucket
  60  *
  61  * See the comments in buildLookupIndex for implementation notes.
  62  */
  63 public class MtpDeviceIndex {
  64
  65     @Override
  66     public int hashCode() {
  67         final int prime = 31;
  68         int result = 1;
  69         result = prime * result + ((mDevice == null) ? 0 : mDevice.getDeviceId());
  70         result = prime * result + mGeneration;
  71         return result;
  72     }
  73
  74     public interface ProgressListener {
  75         public void onObjectIndexed(MtpObjectInfo object, int numVisited);
  76
  77         public void onSorting();
  78
  79         public void onIndexFinish();
  80     }
  81
  82     public enum SortOrder {
  83         Ascending, Descending
  84     }
  85
  86     private MtpDevice mDevice;
  87     private int[] mUnifiedLookupIndex;
  88     private MtpObjectInfo[] mMtpObjects;
  89     private DateBucket[] mBuckets;
  90     private int mGeneration = 0;
  91
  92     public enum Progress {
  93         Uninitialized, Initialized, Pending, Started, Sorting, Finished
  94     }
  95
  96     private Progress mProgress = Progress.Uninitialized;
  97     private ProgressListener mProgressListener;
  98
  99     private static final MtpDeviceIndex sInstance = new MtpDeviceIndex();
 100     private static final MtpObjectTimestampComparator sMtpObjectComparator =
 101             new MtpObjectTimestampComparator();
 102
 103     public static MtpDeviceIndex getInstance() {
 104         return sInstance;
 105     }
 106
 107     private MtpDeviceIndex() {
 108     }
 109
 110     synchronized public MtpDevice getDevice() {
 111         return mDevice;
 112     }
 113
 114     /**
 115      * Sets the MtpDevice that should be indexed and initializes state, but does
 116      * not kick off the actual indexing task, which is instead done by using
 117      * {@link #getIndexRunnable()}
 118      *
 119      * @param device The MtpDevice that should be indexed
 120      */
 121     synchronized public void setDevice(MtpDevice device) {
 122         if (device == mDevice) return;
 123         mDevice = device;
 124         resetState();
 125     }
 126
 127     /**
 128      * Provides a Runnable for the indexing task assuming the state has already
 129      * been correctly initialized (by calling {@link #setDevice(MtpDevice)}) and
 130      * has not already been run.
 131      *
 132      * @return Runnable for the main indexing task
 133      */
 134     synchronized public Runnable getIndexRunnable() {
 135         if (mProgress != Progress.Initialized) return null;
 136         mProgress = Progress.Pending;
 137         return new IndexRunnable(mDevice);
 138     }
 139
 140     synchronized public boolean indexReady() {
 141         return mProgress == Progress.Finished;
 142     }
 143
 144     synchronized public Progress getProgress() {
 145         return mProgress;
 146     }
 147
 148     /**
 149      * @param listener Listener to change to
 150      * @return Progress at the time the listener was added (useful for
 151      *         configuring initial UI state)
 152      */
 153     synchronized public Progress setProgressListener(ProgressListener listener) {
 154         mProgressListener = listener;
 155         return mProgress;
 156     }
 157
 158     /**
 159      * Make the listener null if it matches the argument
 160      *
 161      * @param listener Listener to unset, if currently registered
 162      */
 163     synchronized public void unsetProgressListener(ProgressListener listener) {
 164         if (mProgressListener == listener)
 165             mProgressListener = null;
 166     }
 167
 168     /**
 169      * @return The total number of elements in the index (labels and items)
 170      */
 171     public int size() {
 172         return mProgress == Progress.Finished ? mUnifiedLookupIndex.length : 0;
 173     }
 174
 175     /**
 176      * @param position Index of item to fetch, where 0 is the first item in the
 177      *            specified order
 178      * @param order
 179      * @return the bucket label or MtpObjectInfo at the specified position and
 180      *         order
 181      */
 182     public Object get(int position, SortOrder order) {
 183         if (mProgress != Progress.Finished) return null;
 184         if(order == SortOrder.Ascending) {
 185             DateBucket bucket = mBuckets[mUnifiedLookupIndex[position]];
 186             if (bucket.unifiedStartIndex == position) {
 187                 return bucket.bucket;
 188             } else {
 189                 return mMtpObjects[bucket.itemsStartIndex + position - 1
 190                                    - bucket.unifiedStartIndex];
 191             }
 192         } else {
 193             int zeroIndex = mUnifiedLookupIndex.length - 1 - position;
 194             DateBucket bucket = mBuckets[mUnifiedLookupIndex[zeroIndex]];
 195             if (bucket.unifiedEndIndex == zeroIndex) {
 196                 return bucket.bucket;
 197             } else {
 198                 return mMtpObjects[bucket.itemsStartIndex + zeroIndex
 199                                    - bucket.unifiedStartIndex];
 200             }
 201         }
 202     }
 203
 204     /**
 205      * @param position Index of item to fetch from a view of the data that doesn't
 206      *            include labels and is in the specified order
 207      * @return position-th item in specified order, when not including labels
 208      */
 209     public MtpObjectInfo getWithoutLabels(int position, SortOrder order) {
 210         if (mProgress != Progress.Finished) return null;
 211         if (order == SortOrder.Ascending) {
 212             return mMtpObjects[position];
 213         } else {
 214             return mMtpObjects[mMtpObjects.length - 1 - position];
 215         }
 216     }
 217
 218     /**
 219      * Although this is O(log(number of buckets)), and thus should not be used
 220      * in hotspots, even if the attached device has items for every day for
 221      * a five-year timeframe, it would still only take 11 iterations at most,
 222      * so shouldn't be a huge issue.
 223      * @param position Index of item to map from a view of the data that doesn't
 224      *            include labels and is in the specified order
 225      * @param order
 226      * @return position in a view of the data that does include labels
 227      */
 228     public int getPositionFromPositionWithoutLabels(int position, SortOrder order) {
 229         if (mProgress != Progress.Finished) return -1;
 230         if (order == SortOrder.Descending) {
 231             position = mMtpObjects.length - 1 - position;
 232         }
 233         int bucketNumber = 0;
 234         int iMin = 0;
 235         int iMax = mBuckets.length - 1;
 236         while (iMax >= iMin) {
 237             int iMid = (iMax + iMin) / 2;
 238             if (mBuckets[iMid].itemsStartIndex + mBuckets[iMid].numItems <= position) {
 239                 iMin = iMid + 1;
 240             } else if (mBuckets[iMid].itemsStartIndex > position) {
 241                 iMax = iMid - 1;
 242             } else {
 243                 bucketNumber = iMid;
 244                 break;
 245             }
 246         }
 247         int mappedPos = mBuckets[bucketNumber].unifiedStartIndex
 248                 + position - mBuckets[bucketNumber].itemsStartIndex;
 249         if (order == SortOrder.Descending) {
 250             mappedPos = mUnifiedLookupIndex.length - 1 - mappedPos;
 251         }
 252         return mappedPos;
 253     }
 254
 255     public int getPositionWithoutLabelsFromPosition(int position, SortOrder order) {
 256         if (mProgress != Progress.Finished) return -1;
 257         if(order == SortOrder.Ascending) {
 258             DateBucket bucket = mBuckets[mUnifiedLookupIndex[position]];
 259             if (bucket.unifiedStartIndex == position) position++;
 260             return bucket.itemsStartIndex + position - 1 - bucket.unifiedStartIndex;
 261         } else {
 262             int zeroIndex = mUnifiedLookupIndex.length - 1 - position;
 263             DateBucket bucket = mBuckets[mUnifiedLookupIndex[zeroIndex]];
 264             if (bucket.unifiedEndIndex == zeroIndex) zeroIndex--;
 265             return mMtpObjects.length - 1 - bucket.itemsStartIndex
 266                     - zeroIndex + bucket.unifiedStartIndex;
 267         }
 268     }
 269
 270     /**
 271      * @return The number of MTP items in the index (without labels)
 272      */
 273     public int sizeWithoutLabels() {
 274         return mProgress == Progress.Finished ? mMtpObjects.length : 0;
 275     }
 276
 277     public int getFirstPositionForBucketNumber(int bucketNumber, SortOrder order) {
 278         if (order == SortOrder.Ascending) {
 279             return mBuckets[bucketNumber].unifiedStartIndex;
 280         } else {
 281             return mUnifiedLookupIndex.length - mBuckets[mBuckets.length - 1 - bucketNumber].unifiedEndIndex - 1;
 282         }
 283     }
 284
 285     public int getBucketNumberForPosition(int position, SortOrder order) {
 286         if (order == SortOrder.Ascending) {
 287             return mUnifiedLookupIndex[position];
 288         } else {
 289             return mBuckets.length - 1 - mUnifiedLookupIndex[mUnifiedLookupIndex.length - 1 - position];
 290         }
 291     }
 292
 293     public boolean isFirstInBucket(int position, SortOrder order) {
 294         if (order == SortOrder.Ascending) {
 295             return mBuckets[mUnifiedLookupIndex[position]].unifiedStartIndex == position;
 296         } else {
 297             position = mUnifiedLookupIndex.length - 1 - position;
 298             return mBuckets[mUnifiedLookupIndex[position]].unifiedEndIndex == position;
 299         }
 300     }
 301
 302     private Object[] mCachedReverseBuckets;
 303
 304     public Object[] getBuckets(SortOrder order) {
 305         if (mBuckets == null) return null;
 306         if (order == SortOrder.Ascending) {
 307             return mBuckets;
 308         } else {
 309             if (mCachedReverseBuckets == null) {
 310                 computeReversedBuckets();
 311             }
 312             return mCachedReverseBuckets;
 313         }
 314     }
 315
 316     /*
 317      * See the comments for buildLookupIndex for notes on the specific fields of
 318      * this class.
 319      */
 320     private class DateBucket implements Comparable<DateBucket> {
 321         SimpleDate bucket;
 322         List<MtpObjectInfo> tempElementsList = new ArrayList<MtpObjectInfo>();
 323         int unifiedStartIndex;
 324         int unifiedEndIndex;
 325         int itemsStartIndex;
 326         int numItems;
 327
 328         public DateBucket(SimpleDate bucket) {
 329             this.bucket = bucket;
 330         }
 331
 332         public DateBucket(SimpleDate bucket, MtpObjectInfo firstElement) {
 333             this(bucket);
 334             tempElementsList.add(firstElement);
 335         }
 336
 337         void sortElements(Comparator<MtpObjectInfo> comparator) {
 338             Collections.sort(tempElementsList, comparator);
 339         }
 340
 341         @Override
 342         public String toString() {
 343             return bucket.toString();
 344         }
 345
 346         @Override
 347         public int hashCode() {
 348             return bucket.hashCode();
 349         }
 350
 351         @Override
 352         public boolean equals(Object obj) {
 353             if (this == obj) return true;
 354             if (obj == null) return false;
 355             if (!(obj instanceof DateBucket)) return false;
 356             DateBucket other = (DateBucket) obj;
 357             if (bucket == null) {
 358                 if (other.bucket != null) return false;
 359             } else if (!bucket.equals(other.bucket)) {
 360                 return false;
 361             }
 362             return true;
 363         }
 364
 365         @Override
 366         public int compareTo(DateBucket another) {
 367             return this.bucket.compareTo(another.bucket);
 368         }
 369     }
 370
 371     /**
 372      * Comparator to sort MtpObjectInfo objects by date created.
 373      */
 374     private static class MtpObjectTimestampComparator implements Comparator<MtpObjectInfo> {
 375         @Override
 376         public int compare(MtpObjectInfo o1, MtpObjectInfo o2) {
 377             long diff = o1.getDateCreated() - o2.getDateCreated();
 378             if (diff < 0) {
 379                 return -1;
 380             } else if (diff == 0) {
 381                 return 0;
 382             } else {
 383                 return 1;
 384             }
 385         }
 386     }
 387
 388     private void resetState() {
 389         mGeneration++;
 390         mUnifiedLookupIndex = null;
 391         mMtpObjects = null;
 392         mBuckets = null;
 393         mCachedReverseBuckets = null;
 394         mProgress = (mDevice == null) ? Progress.Uninitialized : Progress.Initialized;
 395     }
 396
 397
 398     private class IndexRunnable implements Runnable {
 399         private int[] mUnifiedLookupIndex;
 400         private MtpObjectInfo[] mMtpObjects;
 401         private DateBucket[] mBuckets;
 402         private Map<SimpleDate, DateBucket> mBucketsTemp;
 403         private MtpDevice mDevice;
 404         private int mNumObjects = 0;
 405
 406         private class IndexingException extends Exception {};
 407
 408         public IndexRunnable(MtpDevice device) {
 409             mDevice = device;
 410         }
 411
 412         /*
 413          * Implementation note: this is the way the index supports a lot of its operations in
 414          * constant time and respecting the need to have bucket names always come before items
 415          * in that bucket when accessing the list sequentially, both in ascending and descending
 416          * orders.
 417          *
 418          * Let's say the data we have in the index is the following:
 419          *  [Bucket A]: [photo 1], [photo 2]
 420          *  [Bucket B]: [photo 3]
 421          *
 422          *  In this case, the lookup index array would be
 423          *  [0, 0, 0, 1, 1]
 424          *
 425          *  Now, whether we access the list in ascending or descending order, we know which bucket
 426          *  to look in (0 corresponds to A and 1 to B), and can return the bucket label as the first
 427          *  item in a bucket as needed. The individual IndexBUckets have a startIndex and endIndex
 428          *  that correspond to indices in this lookup index array, allowing us to calculate the
 429          *  offset of the specific item we want from within a specific bucket.
 430          */
 431         private void buildLookupIndex() {
 432             int numBuckets = mBuckets.length;
 433             mUnifiedLookupIndex = new int[mNumObjects + numBuckets];
 434             int currentUnifiedIndexEntry = 0;
 435             int nextUnifiedEntry;
 436
 437             mMtpObjects = new MtpObjectInfo[mNumObjects];
 438             int currentItemsEntry = 0;
 439             for (int i = 0; i < numBuckets; i++) {
 440                 DateBucket bucket = mBuckets[i];
 441                 nextUnifiedEntry = currentUnifiedIndexEntry + bucket.tempElementsList.size() + 1;
 442                 Arrays.fill(mUnifiedLookupIndex, currentUnifiedIndexEntry, nextUnifiedEntry, i);
 443                 bucket.unifiedStartIndex = currentUnifiedIndexEntry;
 444                 bucket.unifiedEndIndex = nextUnifiedEntry - 1;
 445                 currentUnifiedIndexEntry = nextUnifiedEntry;
 446
 447                 bucket.itemsStartIndex = currentItemsEntry;
 448                 bucket.numItems = bucket.tempElementsList.size();
 449                 for (int j = 0; j < bucket.numItems; j++) {
 450                     mMtpObjects[currentItemsEntry] = bucket.tempElementsList.get(j);
 451                     currentItemsEntry++;
 452                 }
 453                 bucket.tempElementsList = null;
 454             }
 455         }
 456
 457         private void copyResults() {
 458             MtpDeviceIndex.this.mUnifiedLookupIndex = mUnifiedLookupIndex;
 459             MtpDeviceIndex.this.mMtpObjects = mMtpObjects;
 460             MtpDeviceIndex.this.mBuckets = mBuckets;
 461             mUnifiedLookupIndex = null;
 462             mMtpObjects = null;
 463             mBuckets = null;
 464         }
 465
 466         @Override
 467         public void run() {
 468             try {
 469                 indexDevice();
 470             } catch (IndexingException e) {
 471                 synchronized (MtpDeviceIndex.this) {
 472                     resetState();
 473                     if (mProgressListener != null) {
 474                         mProgressListener.onIndexFinish();
 475                     }
 476                 }
 477             }
 478         }
 479
 480         private void indexDevice() throws IndexingException {
 481             synchronized (MtpDeviceIndex.this) {
 482                 mProgress = Progress.Started;
 483             }
 484             mBucketsTemp = new HashMap<SimpleDate, DateBucket>();
 485             for (int storageId : mDevice.getStorageIds()) {
 486                 if (mDevice != getDevice()) throw new IndexingException();
 487                 Stack<Integer> pendingDirectories = new Stack<Integer>();
 488                 pendingDirectories.add(0xFFFFFFFF); // start at the root of the device
 489                 while (!pendingDirectories.isEmpty()) {
 490                     if (mDevice != getDevice()) throw new IndexingException();
 491                     int dirHandle = pendingDirectories.pop();
 492                     for (int objectHandle : mDevice.getObjectHandles(storageId, 0, dirHandle)) {
 493                         MtpObjectInfo objectInfo = mDevice.getObjectInfo(objectHandle);
 494                         if (objectInfo == null) throw new IndexingException();
 495                         switch (objectInfo.getFormat()) {
 496                             case MtpConstants.FORMAT_JFIF:
 497                             case MtpConstants.FORMAT_EXIF_JPEG:
 498                                 addObject(objectInfo);
 499                                 break;
 500                             case MtpConstants.FORMAT_ASSOCIATION:
 501                                 pendingDirectories.add(objectHandle);
 502                                 break;
 503                         }
 504                     }
 505                 }
 506             }
 507             Collection<DateBucket> values = mBucketsTemp.values();
 508             mBucketsTemp = null;
 509             mBuckets = values.toArray(new DateBucket[values.size()]);
 510             values = null;
 511             synchronized (MtpDeviceIndex.this) {
 512                 mProgress = Progress.Sorting;
 513                 if (mProgressListener != null) {
 514                     mProgressListener.onSorting();
 515                 }
 516             }
 517             sortAll();
 518             buildLookupIndex();
 519             synchronized (MtpDeviceIndex.this) {
 520                 if (mDevice != getDevice()) throw new IndexingException();
 521                 copyResults();
 522
 523                 /*
 524                  * In order for getBuckets to operate in constant time for descending
 525                  * order, we must precompute a reversed array of the buckets, mainly
 526                  * because the android.widget.SectionIndexer interface which adapters
 527                  * that call getBuckets implement depends on section numbers to be
 528                  * ascending relative to the scroll position, so we must have this for
 529                  * descending order or the scrollbar goes crazy.
 530                  */
 531                 computeReversedBuckets();
 532
 533                 mProgress = Progress.Finished;
 534                 if (mProgressListener != null) {
 535                     mProgressListener.onIndexFinish();
 536                 }
 537             }
 538         }
 539
 540         private SimpleDate mDateInstance = new SimpleDate();
 541
 542         private void addObject(MtpObjectInfo objectInfo) {
 543             mNumObjects++;
 544             mDateInstance.setTimestamp(objectInfo.getDateCreated());
 545             DateBucket bucket = mBucketsTemp.get(mDateInstance);
 546             if (bucket == null) {
 547                 bucket = new DateBucket(mDateInstance, objectInfo);
 548                 mBucketsTemp.put(mDateInstance, bucket);
 549                 mDateInstance = new SimpleDate(); // only create new date
 550                                                   // objects when they are used
 551                 return;
 552             } else {
 553                 bucket.tempElementsList.add(objectInfo);
 554             }
 555             if (mProgressListener != null) {
 556                 mProgressListener.onObjectIndexed(objectInfo, mNumObjects);
 557             }
 558         }
 559
 560         private void sortAll() {
 561             Arrays.sort(mBuckets);
 562             for (DateBucket bucket : mBuckets) {
 563                 bucket.sortElements(sMtpObjectComparator);
 564             }
 565         }
 566
 567     }
 568
 569     private void computeReversedBuckets() {
 570         mCachedReverseBuckets = new Object[mBuckets.length];
 571         for (int i = 0; i < mCachedReverseBuckets.length; i++) {
 572             mCachedReverseBuckets[i] = mBuckets[mBuckets.length - 1 - i];
 573         }
 574     }
 575 }