leanback/widget/StaggeredGrid.java

/*
 * Copyright (C) 2014 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 android.support.v17.leanback.widget;

import android.support.v4.util.CircularArray;
import android.support.v4.util.CircularIntArray;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

/**
 * A dynamic data structure that caches staggered grid position information
 * for each individual child. The algorithm ensures that each row will be kept
 * as balanced as possible when prepending and appending a child.
 *
 * <p>
 * You may keep view {@link StaggeredGrid.Location} inside StaggeredGrid as much
 * as possible since prepending and appending views is not symmetric: layout
 * going from 0 to N will likely produce a different result than layout going
 * from N to 0 for the staggered cases. If a user scrolls from 0 to N then
 * scrolls back to 0 and we don't keep history location information, edges of
 * the very beginning of rows will not be aligned. It is recommended to keep a
 * list of tens of thousands of {@link StaggeredGrid.Location}s which will be
 * big enough to remember a typical user's scroll history.
 *
 * <p>
 * This class is abstract and can be replaced with different implementations.
 */
abstract class StaggeredGrid extends Grid {

    /**
     * Cached representation of Staggered item.
     */
    public static class Location extends Grid.Location {
        /**
         * Offset to previous item location.
         * min_edge(index) - min_edge(index - 1) for non reversed case
         * max_edge(index) - max_edge(index - 1) for reversed case
         */
        public int offset;

        /**
         * size of the item.
         */
        public int size;

        public Location(int row, int offset, int size) {
            super(row);
            this.offset = offset;
            this.size = size;
        }
    }

    protected CircularArray<Location> mLocations = new CircularArray<Location>(64);

    // mFirstIndex <= mFirstVisibleIndex <= mLastVisibleIndex
    //    <= mFirstIndex + mLocations.size() - 1
    protected int mFirstIndex = -1;

    private Object[] mTmpItem = new Object[1];

    protected Object mPendingItem;
    protected int mPendingItemSize;

    /**
     * Returns index of first item (cached or visible) in the staggered grid.
     * Returns negative value if no item.
     */
    public final int getFirstIndex() {
        return mFirstIndex;
    }

    /**
     * Returns index of last item (cached or visible) in the staggered grid.
     * Returns negative value if no item.
     */
    public final int getLastIndex() {
        return mFirstIndex + mLocations.size() - 1;
    }

    /**
     * Returns the size of the saved {@link Location}s.
     */
    public final int getSize() {
        return mLocations.size();
    }

    @Override
    public final Location getLocation(int index) {
        if (mLocations.size() == 0) {
            return null;
        }
        return mLocations.get(index - mFirstIndex);
    }

    @Override
    public final void debugPrint(PrintWriter pw) {
        for (int i = 0, size = mLocations.size(); i < size; i++) {
            Location loc = mLocations.get(i);
            pw.print("<" + (mFirstIndex + i) + "," + loc.row + ">");
            pw.print(" ");
            pw.println();
        }
    }

    @Override
    protected final boolean prependVisibleItems(int toLimit, boolean oneColumnMode) {
        if (mProvider.getCount() == 0) {
            return false;
        }
        if (!oneColumnMode && checkPrependOverLimit(toLimit)) {
            return false;
        }
        try {
            if (prependVisbleItemsWithCache(toLimit, oneColumnMode)) {
                return true;
            }
            return prependVisibleItemsWithoutCache(toLimit, oneColumnMode);
        } finally {
            mTmpItem[0] = null;
            mPendingItem = null;
        }
    }

    /**
     * Prepends items using cached locations,  returning true if toLimit is reached.
     * This method should only be called by prependVisibleItems().
     */
    protected final boolean prependVisbleItemsWithCache(int toLimit, boolean oneColumnMode) {
        if (mLocations.size() == 0) {
            return false;
        }
        final int count = mProvider.getCount();
        final int firstIndex = getFirstIndex();
        int itemIndex;
        int edge;
        int offset;
        if (mFirstVisibleIndex >= 0) {
            // prepend visible items from first visible index
            edge = mProvider.getEdge(mFirstVisibleIndex);
            offset = getLocation(mFirstVisibleIndex).offset;
            itemIndex = mFirstVisibleIndex - 1;
        } else {
            // prepend first visible item
            edge = Integer.MAX_VALUE;
            offset = 0;
            itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0;
            if (itemIndex > getLastIndex() || itemIndex < getFirstIndex() - 1) {
                // if the item is not within or adjacent to cached items, clear cache.
                mLocations.clear();
                return false;
            } else if (itemIndex < getFirstIndex()) {
                // if the item is adjacent to first index, should prepend without cache.
                return false;
            }
        }
        for (; itemIndex >= mFirstIndex; itemIndex--) {
            Location loc = getLocation(itemIndex);
            int rowIndex = loc.row;
            int size = mProvider.createItem(itemIndex, false, mTmpItem);
            if (size != loc.size) {
                mLocations.removeFromStart(itemIndex + 1 - mFirstIndex);
                mFirstIndex = mFirstVisibleIndex;
                // pending item will be added in prependVisibleItemsWithoutCache
                mPendingItem = mTmpItem[0];
                mPendingItemSize = size;
                return false;
            }
            mFirstVisibleIndex = itemIndex;
            if (mLastVisibleIndex < 0) {
                mLastVisibleIndex = itemIndex;
            }
            mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge - offset);
            if (!oneColumnMode && checkPrependOverLimit(toLimit)) {
                return true;
            }
            edge = mProvider.getEdge(itemIndex);
            offset = loc.offset;
            // Check limit after filled a full column
            if (rowIndex == 0) {
                if (oneColumnMode) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Calculate offset of item after last cached item.
     */
    private int calculateOffsetAfterLastItem(int row) {
        // Find a cached item in same row, if not found, just use last item.
        int cachedIndex = getLastIndex();
        boolean foundCachedItemInSameRow = false;
        while (cachedIndex >= mFirstIndex) {
            Location loc = getLocation(cachedIndex);
            if (loc.row == row) {
                foundCachedItemInSameRow = true;
                break;
            }
            cachedIndex--;
        }
        if (!foundCachedItemInSameRow) {
            cachedIndex = getLastIndex();
        }
        // Assuming the cachedIndex is next to item on the same row, so the
        // sum of offset of [cachedIndex + 1, itemIndex] should be size of the
        // cached item plus margin.
        int offset = isReversedFlow() ?  -getLocation(cachedIndex).size - mMargin:
                getLocation(cachedIndex).size + mMargin;
        for (int i = cachedIndex + 1; i <= getLastIndex(); i++) {
            offset -= getLocation(i).offset;
        }
        return offset;
    }


    /**
     * This implements the algorithm of layout staggered grid, the method should only be called by
     * prependVisibleItems().
     */
    protected abstract boolean prependVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode);

    /**
     * Prepends one visible item with new Location info.  Only called from
     * prependVisibleItemsWithoutCache().
     */
    protected final int prependVisibleItemToRow(int itemIndex, int rowIndex, int edge) {
        int offset;
        if (mFirstVisibleIndex >= 0) {
            if (mFirstVisibleIndex != getFirstIndex() || mFirstVisibleIndex != itemIndex + 1) {
                // should never hit this when we prepend a new item with a new Location object.
                throw new IllegalStateException();
            }
        }
        Location oldFirstLoc = mFirstIndex >= 0 ? getLocation(mFirstIndex) : null;
        int oldFirstEdge = mProvider.getEdge(mFirstIndex);
        Location loc = new Location(rowIndex, 0, 0);
        mLocations.addFirst(loc);
        Object item;
        if (mPendingItem != null) {
            loc.size = mPendingItemSize;
            item = mPendingItem;
            mPendingItem = null;
        } else {
            loc.size = mProvider.createItem(itemIndex, false, mTmpItem);
            item = mTmpItem[0];
        }
        mFirstIndex = mFirstVisibleIndex = itemIndex;
        if (mLastVisibleIndex < 0) {
            mLastVisibleIndex = itemIndex;
        }
        int thisEdge = !mReversedFlow ? edge - loc.size : edge + loc.size;
        if (oldFirstLoc != null) {
            oldFirstLoc.offset = oldFirstEdge - thisEdge;
        }
        mProvider.addItem(item, itemIndex, loc.size, rowIndex, thisEdge);
        return loc.size;
    }

    @Override
    protected final boolean appendVisibleItems(int toLimit, boolean oneColumnMode) {
        if (mProvider.getCount() == 0) {
            return false;
        }
        if (!oneColumnMode && checkAppendOverLimit(toLimit)) {
            return false;
        }
        try {
            if (appendVisbleItemsWithCache(toLimit, oneColumnMode)) {
                return true;
            }
            return appendVisibleItemsWithoutCache(toLimit, oneColumnMode);
        } finally {
            mTmpItem[0] = null;
            mPendingItem = null;
        }
    }

    /**
     * Appends items using cached locations,  returning true if at least one item is appended
     * and (oneColumnMode is true or reach limit and aboveIndex).
     * This method should only be called by appendVisibleItems()
     */
    protected final boolean appendVisbleItemsWithCache(int toLimit, boolean oneColumnMode) {
        if (mLocations.size() == 0) {
            return false;
        }
        final int count = mProvider.getCount();
        int itemIndex;
        int edge;
        if (mLastVisibleIndex >= 0) {
            // append visible items from last visible index
            itemIndex = mLastVisibleIndex + 1;
            edge = mProvider.getEdge(mLastVisibleIndex);
        } else {
            // append first visible item
            edge = Integer.MAX_VALUE;
            itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0;
            if (itemIndex > getLastIndex() + 1 || itemIndex < getFirstIndex()) {
                // if the item is not within or adjacent to cached items, clear cache.
                mLocations.clear();
                return false;
            } else if (itemIndex > getLastIndex()) {
                // if the item is adjacent to first index, should prepend without cache.
                return false;
            }
        }
        int lastIndex = getLastIndex();
        for (; itemIndex < count && itemIndex <= lastIndex; itemIndex++) {
            Location loc = getLocation(itemIndex);
            if (edge != Integer.MAX_VALUE) {
                edge = edge + loc.offset;
            }
            int rowIndex = loc.row;
            int size = mProvider.createItem(itemIndex, true, mTmpItem);
            if (size != loc.size) {
                loc.size = size;
                mLocations.removeFromEnd(lastIndex - itemIndex);
                lastIndex = itemIndex;
            }
            mLastVisibleIndex = itemIndex;
            if (mFirstVisibleIndex < 0) {
                mFirstVisibleIndex = itemIndex;
            }
            mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge);
            if (!oneColumnMode && checkAppendOverLimit(toLimit)) {
                return true;
            }
            if (edge == Integer.MAX_VALUE) {
                edge = mProvider.getEdge(itemIndex);
            }
            // Check limit after filled a full column
            if (rowIndex == mNumRows - 1) {
                if (oneColumnMode) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * algorithm of layout staggered grid, this method should only be called by
     * appendVisibleItems().
     */
    protected abstract boolean appendVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode);

    /**
     * Appends one visible item with new Location info.  Only called from
     * appendVisibleItemsWithoutCache().
     */
    protected final int appendVisibleItemToRow(int itemIndex, int rowIndex, int location) {
        int offset;
        if (mLastVisibleIndex >= 0) {
            if (mLastVisibleIndex != getLastIndex() || mLastVisibleIndex != itemIndex - 1) {
                // should never hit this when we append a new item with a new Location object.
                throw new IllegalStateException();
            }
        }
        if (mLastVisibleIndex < 0) {
            // if we append first visible item after existing cached items,  we need update
            // the offset later when prependVisbleItemsWithCache()
            if (mLocations.size() > 0 && itemIndex == getLastIndex() + 1) {
                offset = calculateOffsetAfterLastItem(rowIndex);
            } else {
                offset = 0;
            }
        } else {
            offset = location - mProvider.getEdge(mLastVisibleIndex);
        }
        Location loc = new Location(rowIndex, offset, 0);
        mLocations.addLast(loc);
        Object item;
        if (mPendingItem != null) {
            loc.size = mPendingItemSize;
            item = mPendingItem;
            mPendingItem = null;
        } else {
            loc.size = mProvider.createItem(itemIndex, true, mTmpItem);
            item = mTmpItem[0];
        }
        if (mLocations.size() == 1) {
            mFirstIndex = mFirstVisibleIndex = mLastVisibleIndex = itemIndex;
        } else {
            if (mLastVisibleIndex < 0) {
                mFirstVisibleIndex = mLastVisibleIndex = itemIndex;
            } else {
                mLastVisibleIndex++;
            }
        }
        mProvider.addItem(item, itemIndex, loc.size, rowIndex, location);
        return loc.size;
    }

    @Override
    public final CircularIntArray[] getItemPositionsInRows(int startPos, int endPos) {
        for (int i = 0; i < mNumRows; i++) {
            mTmpItemPositionsInRows[i].clear();
        }
        if (startPos >= 0) {
            for (int i = startPos; i <= endPos; i++) {
                CircularIntArray row = mTmpItemPositionsInRows[getLocation(i).row];
                if (row.size() > 0 && row.getLast() == i - 1) {
                    // update continuous range
                    row.popLast();
                    row.addLast(i);
                } else {
                    // add single position
                    row.addLast(i);
                    row.addLast(i);
                }
            }
        }
        return mTmpItemPositionsInRows;
    }

    @Override
    public void invalidateItemsAfter(int index) {
        super.invalidateItemsAfter(index);
        mLocations.removeFromEnd(getLastIndex() - index + 1);
        if (mLocations.size() == 0) {
            mFirstIndex = -1;
        }
    }

}