src/com/android/camera/gallery/ImageListUber.java

/*
 * Copyright (C) 2009 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.camera.gallery;

import android.net.Uri;

import com.android.camera.ImageManager;
import com.android.camera.Util;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * A union of different <code>IImageList</code>. This class can merge several
 * <code>IImageList</code> into one list and sort them according to the
 * timestamp (The sorting must be same as all the given lists).
 */
public class ImageListUber implements IImageList {
    @SuppressWarnings("unused")
    private static final String TAG = "ImageListUber";

    private final IImageList [] mSubList;
    private final PriorityQueue<MergeSlot> mQueue;

    // This is an array of Longs wherein each Long consists of two components:
    // "a number" and "an index of sublist".
    //   * The lower 32bit indicates the number of consecutive entries that
    //     belong to a given sublist.
    //
    //   * The higher 32bit component indicates which sublist we're referring
    //     to.
    private long[] mSkipList;
    private int mSkipListSize;
    private int [] mSkipCounts;
    private int mLastListIndex;

    public ImageListUber(IImageList [] sublist, int sort) {
        mSubList = sublist.clone();
        mQueue = new PriorityQueue<MergeSlot>(4,
                sort == ImageManager.SORT_ASCENDING
                ? new AscendingComparator()
                : new DescendingComparator());
        mSkipList = new long[16];
        mSkipListSize = 0;
        mSkipCounts = new int[mSubList.length];
        mLastListIndex = -1;
        mQueue.clear();
        for (int i = 0, n = mSubList.length; i < n; ++i) {
            IImageList list = mSubList[i];
            MergeSlot slot = new MergeSlot(list, i);
            if (slot.next()) mQueue.add(slot);
        }
    }

    public HashMap<String, String> getBucketIds() {
        HashMap<String, String> hashMap = new HashMap<String, String>();
        for (IImageList list : mSubList) {
            hashMap.putAll(list.getBucketIds());
        }
        return hashMap;
    }

    public int getCount() {
        int count = 0;
        for (IImageList subList : mSubList) {
            count += subList.getCount();
        }
        return count;
    }

    public boolean isEmpty() {
        for (IImageList subList : mSubList) {
            if (!subList.isEmpty()) return false;
        }
        return true;
    }

    // mSkipCounts is used to tally the counts as we traverse
    // the mSkipList.  It's a member variable only so that
    // we don't have to allocate each time through.  Otherwise
    // it could just as easily be a local.

    public IImage getImageAt(int index) {
        if (index < 0 || index > getCount()) {
            throw new IndexOutOfBoundsException(
                    "index " + index + " out of range max is " + getCount());
        }

        int skipCounts[] = mSkipCounts;
        // zero out the mSkipCounts since that's only used for the
        // duration of the function call.
        Arrays.fill(skipCounts, 0);

        // a counter of how many images we've skipped in
        // trying to get to index.  alternatively we could
        // have decremented index but, alas, I liked this
        // way more.
        int skipCount = 0;

        // scan the existing mSkipList to see if we've computed
        // enough to just return the answer
        for (int i = 0, n = mSkipListSize; i < n; ++i) {
            long v = mSkipList[i];

            int offset = (int) (v & 0xFFFFFFFF);
            int which  = (int) (v >> 32);
            if (skipCount + offset > index) {
                int subindex = mSkipCounts[which] + (index - skipCount);
                return mSubList[which].getImageAt(subindex);
            }
            skipCount += offset;
            mSkipCounts[which] += offset;
        }

        for (; true; ++skipCount) {
            MergeSlot slot = nextMergeSlot();
            if (slot == null) return null;
            if (skipCount == index) {
                IImage result = slot.mImage;
                if (slot.next()) mQueue.add(slot);
                return result;
            }
            if (slot.next()) mQueue.add(slot);
        }
    }

    private MergeSlot nextMergeSlot() {
        MergeSlot slot = mQueue.poll();
        if (slot == null) return null;
        if (slot.mListIndex == mLastListIndex) {
            int lastIndex = mSkipListSize - 1;
            ++mSkipList[lastIndex];
        } else {
            mLastListIndex = slot.mListIndex;
            if (mSkipList.length == mSkipListSize) {
                long [] temp = new long[mSkipListSize * 2];
                System.arraycopy(mSkipList, 0, temp, 0, mSkipListSize);
                mSkipList = temp;
            }
            mSkipList[mSkipListSize++] = (((long) mLastListIndex) << 32) | 1;
        }
        return slot;
    }

    public IImage getImageForUri(Uri uri) {
        for (IImageList sublist : mSubList) {
            IImage image = sublist.getImageForUri(uri);
            if (image != null) return image;
        }
        return null;
    }

    /**
     * Modify the skip list when an image is deleted by finding
     * the relevant entry in mSkipList and decrementing the
     * counter.  This is simple because deletion can never
     * cause change the order of images.
     */
    private void modifySkipCountForDeletedImage(int index) {
        int skipCount = 0;
        for (int i = 0, n = mSkipListSize; i < n; i++) {
            long v = mSkipList[i];
            int offset = (int) (v & 0xFFFFFFFF);
            if (skipCount + offset > index) {
                mSkipList[i] = v - 1;
                break;
            }
            skipCount += offset;
        }
    }

    private boolean removeImage(IImage image, int index) {
        IImageList list = image.getContainer();
        if (list != null && list.removeImage(image)) {
            modifySkipCountForDeletedImage(index);
            return true;
        }
        return false;
    }

    public boolean removeImage(IImage image) {
        return removeImage(image, getImageIndex(image));
    }

    public boolean removeImageAt(int index) {
        IImage image = getImageAt(index);
        if (image == null) return false;
        return removeImage(image, index);
    }

    public synchronized int getImageIndex(IImage image) {
        IImageList list = image.getContainer();
        int listIndex = Util.indexOf(mSubList, list);
        if (listIndex == -1) {
            throw new IllegalArgumentException();
        }
        int listOffset = list.getImageIndex(image);

        // Similar algorithm as getImageAt(int index)
        int skipCount = 0;
        for (int i = 0, n = mSkipListSize; i < n; ++i) {
            long value = mSkipList[i];
            int offset = (int) (value & 0xFFFFFFFF);
            int which  = (int) (value >> 32);
            if (which == listIndex) {
                if (listOffset < offset) {
                    return skipCount + listOffset;
                }
                listOffset -= offset;
            }
            skipCount += offset;
        }

        for (; true; ++skipCount) {
            MergeSlot slot = nextMergeSlot();
            if (slot == null) return -1;
            if (slot.mImage == image) {
                if (slot.next()) mQueue.add(slot);
                return skipCount;
            }
            if (slot.next()) mQueue.add(slot);
        }
    }

    private static class DescendingComparator implements Comparator<MergeSlot> {

        public int compare(MergeSlot m1, MergeSlot m2) {
            if (m1.mDateTaken != m2.mDateTaken) {
                return m1.mDateTaken < m2.mDateTaken ? 1 : -1;
            }
            return m1.mListIndex - m2.mListIndex;
        }
    }

    private static class AscendingComparator implements Comparator<MergeSlot> {

        public int compare(MergeSlot m1, MergeSlot m2) {
            if (m1.mDateTaken != m2.mDateTaken) {
                return m1.mDateTaken < m2.mDateTaken ? -1 : 1;
            }
            return m1.mListIndex - m2.mListIndex;
        }
    }

    /**
     * A merging slot is used to trace the current position of a sublist. For
     * each given sub list, there will be one corresponding merge slot. We
     * use merge-sort-like algorithm to build the merged list. At begining,
     * we put all the slots in a sorted heap (by timestamp). Each time, we
     * pop the slot with earliest timestamp out, get the image, and then move
     * the index forward, and put it back to the heap.
     */
    private static class MergeSlot {
        private int mOffset = -1;
        private final IImageList mList;

        int mListIndex;
        long mDateTaken;
        IImage mImage;

        public MergeSlot(IImageList list, int index) {
            mList = list;
            mListIndex = index;
        }

        public boolean next() {
            if (mOffset >= mList.getCount() - 1) return false;
            mImage = mList.getImageAt(++mOffset);
            mDateTaken = mImage.getDateTaken();
            return true;
        }
    }

    public void close() {
        for (int i = 0, n = mSubList.length; i < n; ++i) {
            mSubList[i].close();
        }
    }
}