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