1666ea1b28a76aeba74744148b15099254d918671Owen Lin/* 2666ea1b28a76aeba74744148b15099254d918671Owen Lin * Copyright (C) 2009 The Android Open Source Project 3666ea1b28a76aeba74744148b15099254d918671Owen Lin * 4666ea1b28a76aeba74744148b15099254d918671Owen Lin * Licensed under the Apache License, Version 2.0 (the "License"); 5666ea1b28a76aeba74744148b15099254d918671Owen Lin * you may not use this file except in compliance with the License. 6666ea1b28a76aeba74744148b15099254d918671Owen Lin * You may obtain a copy of the License at 7666ea1b28a76aeba74744148b15099254d918671Owen Lin * 8666ea1b28a76aeba74744148b15099254d918671Owen Lin * http://www.apache.org/licenses/LICENSE-2.0 9666ea1b28a76aeba74744148b15099254d918671Owen Lin * 10666ea1b28a76aeba74744148b15099254d918671Owen Lin * Unless required by applicable law or agreed to in writing, software 11666ea1b28a76aeba74744148b15099254d918671Owen Lin * distributed under the License is distributed on an "AS IS" BASIS, 12666ea1b28a76aeba74744148b15099254d918671Owen Lin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13666ea1b28a76aeba74744148b15099254d918671Owen Lin * See the License for the specific language governing permissions and 14666ea1b28a76aeba74744148b15099254d918671Owen Lin * limitations under the License. 15666ea1b28a76aeba74744148b15099254d918671Owen Lin */ 16666ea1b28a76aeba74744148b15099254d918671Owen Lin 17666ea1b28a76aeba74744148b15099254d918671Owen Linpackage com.android.camera.gallery; 18666ea1b28a76aeba74744148b15099254d918671Owen Lin 19666ea1b28a76aeba74744148b15099254d918671Owen Linimport android.net.Uri; 20666ea1b28a76aeba74744148b15099254d918671Owen Lin 21666ea1b28a76aeba74744148b15099254d918671Owen Linimport com.android.camera.ImageManager; 22666ea1b28a76aeba74744148b15099254d918671Owen Linimport com.android.camera.Util; 23666ea1b28a76aeba74744148b15099254d918671Owen Lin 24666ea1b28a76aeba74744148b15099254d918671Owen Linimport java.util.Arrays; 25666ea1b28a76aeba74744148b15099254d918671Owen Linimport java.util.Comparator; 26666ea1b28a76aeba74744148b15099254d918671Owen Linimport java.util.HashMap; 27666ea1b28a76aeba74744148b15099254d918671Owen Linimport java.util.PriorityQueue; 28666ea1b28a76aeba74744148b15099254d918671Owen Lin 29666ea1b28a76aeba74744148b15099254d918671Owen Lin/** 30666ea1b28a76aeba74744148b15099254d918671Owen Lin * A union of different <code>IImageList</code>. This class can merge several 31666ea1b28a76aeba74744148b15099254d918671Owen Lin * <code>IImageList</code> into one list and sort them according to the 32666ea1b28a76aeba74744148b15099254d918671Owen Lin * timestamp (The sorting must be same as all the given lists). 33666ea1b28a76aeba74744148b15099254d918671Owen Lin */ 34666ea1b28a76aeba74744148b15099254d918671Owen Linpublic class ImageListUber implements IImageList { 35666ea1b28a76aeba74744148b15099254d918671Owen Lin @SuppressWarnings("unused") 36666ea1b28a76aeba74744148b15099254d918671Owen Lin private static final String TAG = "ImageListUber"; 37666ea1b28a76aeba74744148b15099254d918671Owen Lin 38666ea1b28a76aeba74744148b15099254d918671Owen Lin private final IImageList [] mSubList; 39666ea1b28a76aeba74744148b15099254d918671Owen Lin private final PriorityQueue<MergeSlot> mQueue; 40666ea1b28a76aeba74744148b15099254d918671Owen Lin 41666ea1b28a76aeba74744148b15099254d918671Owen Lin // This is an array of Longs wherein each Long consists of two components: 42666ea1b28a76aeba74744148b15099254d918671Owen Lin // "a number" and "an index of sublist". 43666ea1b28a76aeba74744148b15099254d918671Owen Lin // * The lower 32bit indicates the number of consecutive entries that 44666ea1b28a76aeba74744148b15099254d918671Owen Lin // belong to a given sublist. 45666ea1b28a76aeba74744148b15099254d918671Owen Lin // 46666ea1b28a76aeba74744148b15099254d918671Owen Lin // * The higher 32bit component indicates which sublist we're referring 47666ea1b28a76aeba74744148b15099254d918671Owen Lin // to. 48666ea1b28a76aeba74744148b15099254d918671Owen Lin private long[] mSkipList; 49666ea1b28a76aeba74744148b15099254d918671Owen Lin private int mSkipListSize; 50666ea1b28a76aeba74744148b15099254d918671Owen Lin private int [] mSkipCounts; 51666ea1b28a76aeba74744148b15099254d918671Owen Lin private int mLastListIndex; 52666ea1b28a76aeba74744148b15099254d918671Owen Lin 53666ea1b28a76aeba74744148b15099254d918671Owen Lin public ImageListUber(IImageList [] sublist, int sort) { 54666ea1b28a76aeba74744148b15099254d918671Owen Lin mSubList = sublist.clone(); 55666ea1b28a76aeba74744148b15099254d918671Owen Lin mQueue = new PriorityQueue<MergeSlot>(4, 56666ea1b28a76aeba74744148b15099254d918671Owen Lin sort == ImageManager.SORT_ASCENDING 57666ea1b28a76aeba74744148b15099254d918671Owen Lin ? new AscendingComparator() 58666ea1b28a76aeba74744148b15099254d918671Owen Lin : new DescendingComparator()); 59666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipList = new long[16]; 60666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipListSize = 0; 61666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipCounts = new int[mSubList.length]; 62666ea1b28a76aeba74744148b15099254d918671Owen Lin mLastListIndex = -1; 63666ea1b28a76aeba74744148b15099254d918671Owen Lin mQueue.clear(); 64666ea1b28a76aeba74744148b15099254d918671Owen Lin for (int i = 0, n = mSubList.length; i < n; ++i) { 65666ea1b28a76aeba74744148b15099254d918671Owen Lin IImageList list = mSubList[i]; 66666ea1b28a76aeba74744148b15099254d918671Owen Lin MergeSlot slot = new MergeSlot(list, i); 67666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.next()) mQueue.add(slot); 68666ea1b28a76aeba74744148b15099254d918671Owen Lin } 69666ea1b28a76aeba74744148b15099254d918671Owen Lin } 70666ea1b28a76aeba74744148b15099254d918671Owen Lin 71666ea1b28a76aeba74744148b15099254d918671Owen Lin public HashMap<String, String> getBucketIds() { 72666ea1b28a76aeba74744148b15099254d918671Owen Lin HashMap<String, String> hashMap = new HashMap<String, String>(); 73666ea1b28a76aeba74744148b15099254d918671Owen Lin for (IImageList list : mSubList) { 74666ea1b28a76aeba74744148b15099254d918671Owen Lin hashMap.putAll(list.getBucketIds()); 75666ea1b28a76aeba74744148b15099254d918671Owen Lin } 76666ea1b28a76aeba74744148b15099254d918671Owen Lin return hashMap; 77666ea1b28a76aeba74744148b15099254d918671Owen Lin } 78666ea1b28a76aeba74744148b15099254d918671Owen Lin 79666ea1b28a76aeba74744148b15099254d918671Owen Lin public int getCount() { 80666ea1b28a76aeba74744148b15099254d918671Owen Lin int count = 0; 81666ea1b28a76aeba74744148b15099254d918671Owen Lin for (IImageList subList : mSubList) { 82666ea1b28a76aeba74744148b15099254d918671Owen Lin count += subList.getCount(); 83666ea1b28a76aeba74744148b15099254d918671Owen Lin } 84666ea1b28a76aeba74744148b15099254d918671Owen Lin return count; 85666ea1b28a76aeba74744148b15099254d918671Owen Lin } 86666ea1b28a76aeba74744148b15099254d918671Owen Lin 87666ea1b28a76aeba74744148b15099254d918671Owen Lin public boolean isEmpty() { 88666ea1b28a76aeba74744148b15099254d918671Owen Lin for (IImageList subList : mSubList) { 89666ea1b28a76aeba74744148b15099254d918671Owen Lin if (!subList.isEmpty()) return false; 90666ea1b28a76aeba74744148b15099254d918671Owen Lin } 91666ea1b28a76aeba74744148b15099254d918671Owen Lin return true; 92666ea1b28a76aeba74744148b15099254d918671Owen Lin } 93666ea1b28a76aeba74744148b15099254d918671Owen Lin 94666ea1b28a76aeba74744148b15099254d918671Owen Lin // mSkipCounts is used to tally the counts as we traverse 95666ea1b28a76aeba74744148b15099254d918671Owen Lin // the mSkipList. It's a member variable only so that 96666ea1b28a76aeba74744148b15099254d918671Owen Lin // we don't have to allocate each time through. Otherwise 97666ea1b28a76aeba74744148b15099254d918671Owen Lin // it could just as easily be a local. 98666ea1b28a76aeba74744148b15099254d918671Owen Lin 99666ea1b28a76aeba74744148b15099254d918671Owen Lin public IImage getImageAt(int index) { 100666ea1b28a76aeba74744148b15099254d918671Owen Lin if (index < 0 || index > getCount()) { 101666ea1b28a76aeba74744148b15099254d918671Owen Lin throw new IndexOutOfBoundsException( 102666ea1b28a76aeba74744148b15099254d918671Owen Lin "index " + index + " out of range max is " + getCount()); 103666ea1b28a76aeba74744148b15099254d918671Owen Lin } 104666ea1b28a76aeba74744148b15099254d918671Owen Lin 105666ea1b28a76aeba74744148b15099254d918671Owen Lin int skipCounts[] = mSkipCounts; 106666ea1b28a76aeba74744148b15099254d918671Owen Lin // zero out the mSkipCounts since that's only used for the 107666ea1b28a76aeba74744148b15099254d918671Owen Lin // duration of the function call. 108666ea1b28a76aeba74744148b15099254d918671Owen Lin Arrays.fill(skipCounts, 0); 109666ea1b28a76aeba74744148b15099254d918671Owen Lin 110666ea1b28a76aeba74744148b15099254d918671Owen Lin // a counter of how many images we've skipped in 111666ea1b28a76aeba74744148b15099254d918671Owen Lin // trying to get to index. alternatively we could 112666ea1b28a76aeba74744148b15099254d918671Owen Lin // have decremented index but, alas, I liked this 113666ea1b28a76aeba74744148b15099254d918671Owen Lin // way more. 114666ea1b28a76aeba74744148b15099254d918671Owen Lin int skipCount = 0; 115666ea1b28a76aeba74744148b15099254d918671Owen Lin 116666ea1b28a76aeba74744148b15099254d918671Owen Lin // scan the existing mSkipList to see if we've computed 117666ea1b28a76aeba74744148b15099254d918671Owen Lin // enough to just return the answer 118666ea1b28a76aeba74744148b15099254d918671Owen Lin for (int i = 0, n = mSkipListSize; i < n; ++i) { 119666ea1b28a76aeba74744148b15099254d918671Owen Lin long v = mSkipList[i]; 120666ea1b28a76aeba74744148b15099254d918671Owen Lin 121666ea1b28a76aeba74744148b15099254d918671Owen Lin int offset = (int) (v & 0xFFFFFFFF); 122666ea1b28a76aeba74744148b15099254d918671Owen Lin int which = (int) (v >> 32); 123666ea1b28a76aeba74744148b15099254d918671Owen Lin if (skipCount + offset > index) { 124666ea1b28a76aeba74744148b15099254d918671Owen Lin int subindex = mSkipCounts[which] + (index - skipCount); 125666ea1b28a76aeba74744148b15099254d918671Owen Lin return mSubList[which].getImageAt(subindex); 126666ea1b28a76aeba74744148b15099254d918671Owen Lin } 127666ea1b28a76aeba74744148b15099254d918671Owen Lin skipCount += offset; 128666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipCounts[which] += offset; 129666ea1b28a76aeba74744148b15099254d918671Owen Lin } 130666ea1b28a76aeba74744148b15099254d918671Owen Lin 131666ea1b28a76aeba74744148b15099254d918671Owen Lin for (; true; ++skipCount) { 132666ea1b28a76aeba74744148b15099254d918671Owen Lin MergeSlot slot = nextMergeSlot(); 133666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot == null) return null; 134666ea1b28a76aeba74744148b15099254d918671Owen Lin if (skipCount == index) { 135666ea1b28a76aeba74744148b15099254d918671Owen Lin IImage result = slot.mImage; 136666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.next()) mQueue.add(slot); 137666ea1b28a76aeba74744148b15099254d918671Owen Lin return result; 138666ea1b28a76aeba74744148b15099254d918671Owen Lin } 139666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.next()) mQueue.add(slot); 140666ea1b28a76aeba74744148b15099254d918671Owen Lin } 141666ea1b28a76aeba74744148b15099254d918671Owen Lin } 142666ea1b28a76aeba74744148b15099254d918671Owen Lin 143666ea1b28a76aeba74744148b15099254d918671Owen Lin private MergeSlot nextMergeSlot() { 144666ea1b28a76aeba74744148b15099254d918671Owen Lin MergeSlot slot = mQueue.poll(); 145666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot == null) return null; 146666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.mListIndex == mLastListIndex) { 147666ea1b28a76aeba74744148b15099254d918671Owen Lin int lastIndex = mSkipListSize - 1; 148666ea1b28a76aeba74744148b15099254d918671Owen Lin ++mSkipList[lastIndex]; 149666ea1b28a76aeba74744148b15099254d918671Owen Lin } else { 150666ea1b28a76aeba74744148b15099254d918671Owen Lin mLastListIndex = slot.mListIndex; 151666ea1b28a76aeba74744148b15099254d918671Owen Lin if (mSkipList.length == mSkipListSize) { 152666ea1b28a76aeba74744148b15099254d918671Owen Lin long [] temp = new long[mSkipListSize * 2]; 153666ea1b28a76aeba74744148b15099254d918671Owen Lin System.arraycopy(mSkipList, 0, temp, 0, mSkipListSize); 154666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipList = temp; 155666ea1b28a76aeba74744148b15099254d918671Owen Lin } 156666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipList[mSkipListSize++] = (((long) mLastListIndex) << 32) | 1; 157666ea1b28a76aeba74744148b15099254d918671Owen Lin } 158666ea1b28a76aeba74744148b15099254d918671Owen Lin return slot; 159666ea1b28a76aeba74744148b15099254d918671Owen Lin } 160666ea1b28a76aeba74744148b15099254d918671Owen Lin 161666ea1b28a76aeba74744148b15099254d918671Owen Lin public IImage getImageForUri(Uri uri) { 162666ea1b28a76aeba74744148b15099254d918671Owen Lin for (IImageList sublist : mSubList) { 163666ea1b28a76aeba74744148b15099254d918671Owen Lin IImage image = sublist.getImageForUri(uri); 164666ea1b28a76aeba74744148b15099254d918671Owen Lin if (image != null) return image; 165666ea1b28a76aeba74744148b15099254d918671Owen Lin } 166666ea1b28a76aeba74744148b15099254d918671Owen Lin return null; 167666ea1b28a76aeba74744148b15099254d918671Owen Lin } 168666ea1b28a76aeba74744148b15099254d918671Owen Lin 169666ea1b28a76aeba74744148b15099254d918671Owen Lin /** 170666ea1b28a76aeba74744148b15099254d918671Owen Lin * Modify the skip list when an image is deleted by finding 171666ea1b28a76aeba74744148b15099254d918671Owen Lin * the relevant entry in mSkipList and decrementing the 172666ea1b28a76aeba74744148b15099254d918671Owen Lin * counter. This is simple because deletion can never 173666ea1b28a76aeba74744148b15099254d918671Owen Lin * cause change the order of images. 174666ea1b28a76aeba74744148b15099254d918671Owen Lin */ 175666ea1b28a76aeba74744148b15099254d918671Owen Lin private void modifySkipCountForDeletedImage(int index) { 176666ea1b28a76aeba74744148b15099254d918671Owen Lin int skipCount = 0; 177666ea1b28a76aeba74744148b15099254d918671Owen Lin for (int i = 0, n = mSkipListSize; i < n; i++) { 178666ea1b28a76aeba74744148b15099254d918671Owen Lin long v = mSkipList[i]; 179666ea1b28a76aeba74744148b15099254d918671Owen Lin int offset = (int) (v & 0xFFFFFFFF); 180666ea1b28a76aeba74744148b15099254d918671Owen Lin if (skipCount + offset > index) { 181666ea1b28a76aeba74744148b15099254d918671Owen Lin mSkipList[i] = v - 1; 182666ea1b28a76aeba74744148b15099254d918671Owen Lin break; 183666ea1b28a76aeba74744148b15099254d918671Owen Lin } 184666ea1b28a76aeba74744148b15099254d918671Owen Lin skipCount += offset; 185666ea1b28a76aeba74744148b15099254d918671Owen Lin } 186666ea1b28a76aeba74744148b15099254d918671Owen Lin } 187666ea1b28a76aeba74744148b15099254d918671Owen Lin 188666ea1b28a76aeba74744148b15099254d918671Owen Lin private boolean removeImage(IImage image, int index) { 189666ea1b28a76aeba74744148b15099254d918671Owen Lin IImageList list = image.getContainer(); 190666ea1b28a76aeba74744148b15099254d918671Owen Lin if (list != null && list.removeImage(image)) { 191666ea1b28a76aeba74744148b15099254d918671Owen Lin modifySkipCountForDeletedImage(index); 192666ea1b28a76aeba74744148b15099254d918671Owen Lin return true; 193666ea1b28a76aeba74744148b15099254d918671Owen Lin } 194666ea1b28a76aeba74744148b15099254d918671Owen Lin return false; 195666ea1b28a76aeba74744148b15099254d918671Owen Lin } 196666ea1b28a76aeba74744148b15099254d918671Owen Lin 197666ea1b28a76aeba74744148b15099254d918671Owen Lin public boolean removeImage(IImage image) { 198666ea1b28a76aeba74744148b15099254d918671Owen Lin return removeImage(image, getImageIndex(image)); 199666ea1b28a76aeba74744148b15099254d918671Owen Lin } 200666ea1b28a76aeba74744148b15099254d918671Owen Lin 201666ea1b28a76aeba74744148b15099254d918671Owen Lin public boolean removeImageAt(int index) { 202666ea1b28a76aeba74744148b15099254d918671Owen Lin IImage image = getImageAt(index); 203666ea1b28a76aeba74744148b15099254d918671Owen Lin if (image == null) return false; 204666ea1b28a76aeba74744148b15099254d918671Owen Lin return removeImage(image, index); 205666ea1b28a76aeba74744148b15099254d918671Owen Lin } 206666ea1b28a76aeba74744148b15099254d918671Owen Lin 207666ea1b28a76aeba74744148b15099254d918671Owen Lin public synchronized int getImageIndex(IImage image) { 208666ea1b28a76aeba74744148b15099254d918671Owen Lin IImageList list = image.getContainer(); 209666ea1b28a76aeba74744148b15099254d918671Owen Lin int listIndex = Util.indexOf(mSubList, list); 210666ea1b28a76aeba74744148b15099254d918671Owen Lin if (listIndex == -1) { 211666ea1b28a76aeba74744148b15099254d918671Owen Lin throw new IllegalArgumentException(); 212666ea1b28a76aeba74744148b15099254d918671Owen Lin } 213666ea1b28a76aeba74744148b15099254d918671Owen Lin int listOffset = list.getImageIndex(image); 214666ea1b28a76aeba74744148b15099254d918671Owen Lin 215666ea1b28a76aeba74744148b15099254d918671Owen Lin // Similar algorithm as getImageAt(int index) 216666ea1b28a76aeba74744148b15099254d918671Owen Lin int skipCount = 0; 217666ea1b28a76aeba74744148b15099254d918671Owen Lin for (int i = 0, n = mSkipListSize; i < n; ++i) { 218666ea1b28a76aeba74744148b15099254d918671Owen Lin long value = mSkipList[i]; 219666ea1b28a76aeba74744148b15099254d918671Owen Lin int offset = (int) (value & 0xFFFFFFFF); 220666ea1b28a76aeba74744148b15099254d918671Owen Lin int which = (int) (value >> 32); 221666ea1b28a76aeba74744148b15099254d918671Owen Lin if (which == listIndex) { 222666ea1b28a76aeba74744148b15099254d918671Owen Lin if (listOffset < offset) { 223666ea1b28a76aeba74744148b15099254d918671Owen Lin return skipCount + listOffset; 224666ea1b28a76aeba74744148b15099254d918671Owen Lin } 225666ea1b28a76aeba74744148b15099254d918671Owen Lin listOffset -= offset; 226666ea1b28a76aeba74744148b15099254d918671Owen Lin } 227666ea1b28a76aeba74744148b15099254d918671Owen Lin skipCount += offset; 228666ea1b28a76aeba74744148b15099254d918671Owen Lin } 229666ea1b28a76aeba74744148b15099254d918671Owen Lin 230666ea1b28a76aeba74744148b15099254d918671Owen Lin for (; true; ++skipCount) { 231666ea1b28a76aeba74744148b15099254d918671Owen Lin MergeSlot slot = nextMergeSlot(); 232666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot == null) return -1; 233666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.mImage == image) { 234666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.next()) mQueue.add(slot); 235666ea1b28a76aeba74744148b15099254d918671Owen Lin return skipCount; 236666ea1b28a76aeba74744148b15099254d918671Owen Lin } 237666ea1b28a76aeba74744148b15099254d918671Owen Lin if (slot.next()) mQueue.add(slot); 238666ea1b28a76aeba74744148b15099254d918671Owen Lin } 239666ea1b28a76aeba74744148b15099254d918671Owen Lin } 240666ea1b28a76aeba74744148b15099254d918671Owen Lin 241666ea1b28a76aeba74744148b15099254d918671Owen Lin private static class DescendingComparator implements Comparator<MergeSlot> { 242666ea1b28a76aeba74744148b15099254d918671Owen Lin 243666ea1b28a76aeba74744148b15099254d918671Owen Lin public int compare(MergeSlot m1, MergeSlot m2) { 244666ea1b28a76aeba74744148b15099254d918671Owen Lin if (m1.mDateTaken != m2.mDateTaken) { 245666ea1b28a76aeba74744148b15099254d918671Owen Lin return m1.mDateTaken < m2.mDateTaken ? 1 : -1; 246666ea1b28a76aeba74744148b15099254d918671Owen Lin } 247666ea1b28a76aeba74744148b15099254d918671Owen Lin return m1.mListIndex - m2.mListIndex; 248666ea1b28a76aeba74744148b15099254d918671Owen Lin } 249666ea1b28a76aeba74744148b15099254d918671Owen Lin } 250666ea1b28a76aeba74744148b15099254d918671Owen Lin 251666ea1b28a76aeba74744148b15099254d918671Owen Lin private static class AscendingComparator implements Comparator<MergeSlot> { 252666ea1b28a76aeba74744148b15099254d918671Owen Lin 253666ea1b28a76aeba74744148b15099254d918671Owen Lin public int compare(MergeSlot m1, MergeSlot m2) { 254666ea1b28a76aeba74744148b15099254d918671Owen Lin if (m1.mDateTaken != m2.mDateTaken) { 255666ea1b28a76aeba74744148b15099254d918671Owen Lin return m1.mDateTaken < m2.mDateTaken ? -1 : 1; 256666ea1b28a76aeba74744148b15099254d918671Owen Lin } 257666ea1b28a76aeba74744148b15099254d918671Owen Lin return m1.mListIndex - m2.mListIndex; 258666ea1b28a76aeba74744148b15099254d918671Owen Lin } 259666ea1b28a76aeba74744148b15099254d918671Owen Lin } 260666ea1b28a76aeba74744148b15099254d918671Owen Lin 261666ea1b28a76aeba74744148b15099254d918671Owen Lin /** 262666ea1b28a76aeba74744148b15099254d918671Owen Lin * A merging slot is used to trace the current position of a sublist. For 263666ea1b28a76aeba74744148b15099254d918671Owen Lin * each given sub list, there will be one corresponding merge slot. We 264666ea1b28a76aeba74744148b15099254d918671Owen Lin * use merge-sort-like algorithm to build the merged list. At begining, 265666ea1b28a76aeba74744148b15099254d918671Owen Lin * we put all the slots in a sorted heap (by timestamp). Each time, we 266666ea1b28a76aeba74744148b15099254d918671Owen Lin * pop the slot with earliest timestamp out, get the image, and then move 267666ea1b28a76aeba74744148b15099254d918671Owen Lin * the index forward, and put it back to the heap. 268666ea1b28a76aeba74744148b15099254d918671Owen Lin */ 269666ea1b28a76aeba74744148b15099254d918671Owen Lin private static class MergeSlot { 270666ea1b28a76aeba74744148b15099254d918671Owen Lin private int mOffset = -1; 271666ea1b28a76aeba74744148b15099254d918671Owen Lin private final IImageList mList; 272666ea1b28a76aeba74744148b15099254d918671Owen Lin 273666ea1b28a76aeba74744148b15099254d918671Owen Lin int mListIndex; 274666ea1b28a76aeba74744148b15099254d918671Owen Lin long mDateTaken; 275666ea1b28a76aeba74744148b15099254d918671Owen Lin IImage mImage; 276666ea1b28a76aeba74744148b15099254d918671Owen Lin 277666ea1b28a76aeba74744148b15099254d918671Owen Lin public MergeSlot(IImageList list, int index) { 278666ea1b28a76aeba74744148b15099254d918671Owen Lin mList = list; 279666ea1b28a76aeba74744148b15099254d918671Owen Lin mListIndex = index; 280666ea1b28a76aeba74744148b15099254d918671Owen Lin } 281666ea1b28a76aeba74744148b15099254d918671Owen Lin 282666ea1b28a76aeba74744148b15099254d918671Owen Lin public boolean next() { 283666ea1b28a76aeba74744148b15099254d918671Owen Lin if (mOffset >= mList.getCount() - 1) return false; 284666ea1b28a76aeba74744148b15099254d918671Owen Lin mImage = mList.getImageAt(++mOffset); 285666ea1b28a76aeba74744148b15099254d918671Owen Lin mDateTaken = mImage.getDateTaken(); 286666ea1b28a76aeba74744148b15099254d918671Owen Lin return true; 287666ea1b28a76aeba74744148b15099254d918671Owen Lin } 288666ea1b28a76aeba74744148b15099254d918671Owen Lin } 289666ea1b28a76aeba74744148b15099254d918671Owen Lin 290666ea1b28a76aeba74744148b15099254d918671Owen Lin public void close() { 291666ea1b28a76aeba74744148b15099254d918671Owen Lin for (int i = 0, n = mSubList.length; i < n; ++i) { 292666ea1b28a76aeba74744148b15099254d918671Owen Lin mSubList[i].close(); 293666ea1b28a76aeba74744148b15099254d918671Owen Lin } 294666ea1b28a76aeba74744148b15099254d918671Owen Lin } 295666ea1b28a76aeba74744148b15099254d918671Owen Lin} 296