1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14package android.support.v17.leanback.widget;
15
16/**
17 * A default implementation of {@link StaggeredGrid}.
18 *
19 * This implementation tries to fill items in consecutive row order. The next
20 * item is always in same row or in the next row.
21 */
22final class StaggeredGridDefault extends StaggeredGrid {
23
24    /**
25     * Returns the max edge value of item (visible or cached) in a row.  This
26     * will be the place to append or prepend item not in cache.
27     */
28    int getRowMax(int rowIndex) {
29        if (mFirstVisibleIndex < 0) {
30            return Integer.MIN_VALUE;
31        }
32        if (mReversedFlow) {
33            int edge = mProvider.getEdge(mFirstVisibleIndex);
34            if (getLocation(mFirstVisibleIndex).row == rowIndex) {
35                return edge;
36            }
37            for (int i = mFirstVisibleIndex + 1; i <= getLastIndex(); i++) {
38                Location loc = getLocation(i);
39                edge += loc.offset;
40                if (loc.row == rowIndex) {
41                    return edge;
42                }
43            }
44        } else {
45            int edge = mProvider.getEdge(mLastVisibleIndex);
46            Location loc = getLocation(mLastVisibleIndex);
47            if (loc.row == rowIndex) {
48                return edge + loc.size;
49            }
50            for (int i = mLastVisibleIndex - 1; i >= getFirstIndex(); i--) {
51                edge -= loc.offset;
52                loc = getLocation(i);
53                if (loc.row == rowIndex) {
54                    return edge + loc.size;
55                }
56            }
57        }
58        return Integer.MIN_VALUE;
59    }
60
61    /**
62     * Returns the min edge value of item (visible or cached) in a row.  This
63     * will be the place to prepend or append item not in cache.
64     */
65    int getRowMin(int rowIndex) {
66        if (mFirstVisibleIndex < 0) {
67            return Integer.MAX_VALUE;
68        }
69        if (mReversedFlow) {
70            int edge = mProvider.getEdge(mLastVisibleIndex);
71            Location loc = getLocation(mLastVisibleIndex);
72            if (loc.row == rowIndex) {
73                return edge - loc.size;
74            }
75            for (int i = mLastVisibleIndex - 1; i >= getFirstIndex(); i--) {
76                edge -= loc.offset;
77                loc = getLocation(i);
78                if (loc.row == rowIndex) {
79                    return edge - loc.size;
80                }
81            }
82        } else {
83            int edge = mProvider.getEdge(mFirstVisibleIndex);
84            if (getLocation(mFirstVisibleIndex).row == rowIndex) {
85                return edge;
86            }
87            for (int i = mFirstVisibleIndex + 1; i <= getLastIndex() ; i++) {
88                Location loc = getLocation(i);
89                edge += loc.offset;
90                if (loc.row == rowIndex) {
91                    return edge;
92                }
93            }
94        }
95        return Integer.MAX_VALUE;
96    }
97
98    /**
99     * Note this method has assumption that item is filled either in the same row
100     * next row of last item.  Search until row index wrapped.
101     */
102    @Override
103    public int findRowMax(boolean findLarge, int indexLimit, int[] indices) {
104        int value;
105        int edge = mProvider.getEdge(indexLimit);
106        Location loc = getLocation(indexLimit);
107        int row = loc.row;
108        int index = indexLimit;
109        int visitedRows = 1;
110        int visitRow = row;
111        if (mReversedFlow) {
112            value = edge;
113            for (int i = indexLimit + 1; visitedRows < mNumRows && i <= mLastVisibleIndex; i++) {
114                loc = getLocation(i);
115                edge += loc.offset;
116                if (loc.row != visitRow) {
117                    visitRow = loc.row;
118                    visitedRows++;
119                    if (findLarge ? edge > value : edge < value) {
120                        row = visitRow;
121                        value = edge;
122                        index = i;
123                    }
124                }
125            }
126        } else {
127            value = edge + mProvider.getSize(indexLimit);
128            for (int i = indexLimit - 1; visitedRows < mNumRows && i >= mFirstVisibleIndex; i--) {
129                edge -= loc.offset;
130                loc = getLocation(i);
131                if (loc.row != visitRow) {
132                    visitRow = loc.row;
133                    visitedRows++;
134                    int newValue = edge + mProvider.getSize(i);
135                    if (findLarge ? newValue > value : newValue < value) {
136                        row = visitRow;
137                        value = newValue;
138                        index = i;
139                    }
140                }
141            }
142        }
143        if (indices != null) {
144            indices[0] = row;
145            indices[1] = index;
146        }
147        return value;
148    }
149
150    /**
151     * Note this method has assumption that item is filled either in the same row
152     * next row of last item.  Search until row index wrapped.
153     */
154    @Override
155    public int findRowMin(boolean findLarge, int indexLimit, int[] indices) {
156        int value;
157        int edge = mProvider.getEdge(indexLimit);
158        Location loc = getLocation(indexLimit);
159        int row = loc.row;
160        int index = indexLimit;
161        int visitedRows = 1;
162        int visitRow = row;
163        if (mReversedFlow) {
164            value = edge - mProvider.getSize(indexLimit);
165            for (int i = indexLimit - 1; visitedRows < mNumRows && i >= mFirstVisibleIndex; i--) {
166                edge -= loc.offset;
167                loc = getLocation(i);
168                if (loc.row != visitRow) {
169                    visitRow = loc.row;
170                    visitedRows++;
171                    int newValue = edge - mProvider.getSize(i);
172                    if (findLarge ? newValue > value : newValue < value) {
173                        value = newValue;
174                        row = visitRow;
175                        index = i;
176                    }
177                }
178            }
179        } else {
180            value = edge;
181            for (int i = indexLimit + 1; visitedRows < mNumRows && i <= mLastVisibleIndex; i++) {
182                loc = getLocation(i);
183                edge += loc.offset;
184                if (loc.row != visitRow) {
185                    visitRow = loc.row;
186                    visitedRows++;
187                    if (findLarge ? edge > value : edge < value) {
188                        value = edge;
189                        row = visitRow;
190                        index = i;
191                    }
192                }
193            }
194        }
195        if (indices != null) {
196            indices[0] = row;
197            indices[1] = index;
198        }
199        return value;
200    }
201
202    private int findRowEdgeLimitSearchIndex(boolean append) {
203        boolean wrapped = false;
204        if (append) {
205            for (int index = mLastVisibleIndex; index >= mFirstVisibleIndex; index--) {
206                int row = getLocation(index).row;
207                if (row == 0) {
208                    wrapped = true;
209                } else if (wrapped && row == mNumRows - 1) {
210                    return index;
211                }
212            }
213        } else {
214            for (int index = mFirstVisibleIndex; index <= mLastVisibleIndex; index++) {
215                int row = getLocation(index).row;
216                if (row == mNumRows - 1) {
217                    wrapped = true;
218                } else if (wrapped && row == 0) {
219                    return index;
220                }
221            }
222        }
223        return -1;
224    }
225
226    @Override
227    protected boolean appendVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode) {
228        final int count = mProvider.getCount();
229        int itemIndex;
230        int rowIndex;
231        int edgeLimit;
232        boolean edgeLimitIsValid;
233        if (mLastVisibleIndex >= 0) {
234            if (mLastVisibleIndex < getLastIndex()) {
235                // should fill using cache instead
236                return false;
237            }
238            itemIndex = mLastVisibleIndex + 1;
239            rowIndex = getLocation(mLastVisibleIndex).row;
240            // find start item index of "previous column"
241            int edgeLimitSearchIndex = findRowEdgeLimitSearchIndex(true);
242            if (edgeLimitSearchIndex < 0) {
243                // if "previous colummn" is not found, using edgeLimit of
244                // first row currently in grid
245                edgeLimit = Integer.MIN_VALUE;
246                for (int i = 0; i < mNumRows; i++) {
247                    edgeLimit = mReversedFlow ? getRowMin(i) : getRowMax(i);
248                    if (edgeLimit != Integer.MIN_VALUE) {
249                        break;
250                    }
251                }
252            } else {
253                edgeLimit = mReversedFlow ? findRowMin(false, edgeLimitSearchIndex, null) :
254                        findRowMax(true, edgeLimitSearchIndex, null);
255            }
256            if (mReversedFlow ? getRowMin(rowIndex) <= edgeLimit
257                    : getRowMax(rowIndex) >= edgeLimit) {
258                // if current row exceeds previous column, fill from next row
259                rowIndex = rowIndex + 1;
260                if (rowIndex == mNumRows) {
261                    // start a new column and using edge limit of current column
262                    rowIndex = 0;
263                    edgeLimit = mReversedFlow ? findRowMin(false, null) : findRowMax(true, null);
264                }
265            }
266            edgeLimitIsValid = true;
267        } else {
268            itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0;
269            // if there are cached items,  put on next row of last cached item.
270            rowIndex = (mLocations.size() > 0 ? getLocation(getLastIndex()).row + 1 : itemIndex)
271                    % mNumRows;
272            edgeLimit = 0;
273            edgeLimitIsValid = false;
274        }
275
276        boolean filledOne = false;
277        while (true) {
278            // find end-most row edge (.high is biggest, or .low is smallest in reversed flow)
279            // fill from current row till last row so that each row will grow longer than
280            // the previous highest row.
281            for (; rowIndex < mNumRows; rowIndex++) {
282                // fill one item to a row
283                if (itemIndex == count || (!oneColumnMode && checkAppendOverLimit(toLimit))) {
284                    return filledOne;
285                }
286                int location = mReversedFlow ? getRowMin(rowIndex) : getRowMax(rowIndex);
287                if (location == Integer.MAX_VALUE || location == Integer.MIN_VALUE) {
288                    // nothing on the row
289                    if (rowIndex == 0) {
290                        location = mReversedFlow ? getRowMin(mNumRows - 1) : getRowMax(mNumRows - 1);
291                        if (location != Integer.MAX_VALUE && location != Integer.MIN_VALUE) {
292                            location = location + (mReversedFlow ? -mMargin : mMargin);
293                        }
294                    } else {
295                        location = mReversedFlow ? getRowMax(rowIndex - 1) : getRowMin(rowIndex - 1);
296                    }
297                } else {
298                    location = location + (mReversedFlow ? -mMargin : mMargin);
299                }
300                int size = appendVisibleItemToRow(itemIndex++, rowIndex, location);
301                filledOne = true;
302                // fill more item to the row to make sure this row is longer than
303                // the previous highest row.
304                if (edgeLimitIsValid) {
305                    while (mReversedFlow ? location - size > edgeLimit :
306                            location + size < edgeLimit) {
307                        if (itemIndex == count || (!oneColumnMode && checkAppendOverLimit(toLimit))) {
308                            return filledOne;
309                        }
310                        location = location + (mReversedFlow ? - size - mMargin : size + mMargin);
311                        size = appendVisibleItemToRow(itemIndex++, rowIndex, location);
312                    }
313                } else {
314                    edgeLimitIsValid = true;
315                    edgeLimit = mReversedFlow ? getRowMin(rowIndex) : getRowMax(rowIndex);
316                }
317            }
318            if (oneColumnMode) {
319                return filledOne;
320            }
321            edgeLimit = mReversedFlow ? findRowMin(false, null) : findRowMax(true, null);
322            // start fill from row 0 again
323            rowIndex = 0;
324        }
325    }
326
327    @Override
328    protected boolean prependVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode) {
329        int itemIndex;
330        int rowIndex;
331        int edgeLimit;
332        boolean edgeLimitIsValid;
333        if (mFirstVisibleIndex >= 0) {
334            if (mFirstVisibleIndex > getFirstIndex()) {
335                // should fill using cache instead
336                return false;
337            }
338            itemIndex = mFirstVisibleIndex - 1;
339            rowIndex = getLocation(mFirstVisibleIndex).row;
340            // find start item index of "previous column"
341            int edgeLimitSearchIndex = findRowEdgeLimitSearchIndex(false);
342            if (edgeLimitSearchIndex < 0) {
343                // if "previous colummn" is not found, using edgeLimit of
344                // last row currently in grid and fill from upper row
345                rowIndex = rowIndex - 1;
346                edgeLimit = Integer.MAX_VALUE;
347                for (int i = mNumRows - 1; i >= 0; i--) {
348                    edgeLimit = mReversedFlow ? getRowMax(i) : getRowMin(i);
349                    if (edgeLimit != Integer.MAX_VALUE) {
350                        break;
351                    }
352                }
353            } else {
354                edgeLimit = mReversedFlow ? findRowMax(true, edgeLimitSearchIndex, null) :
355                        findRowMin(false, edgeLimitSearchIndex, null);
356            }
357            if (mReversedFlow ? getRowMax(rowIndex) >= edgeLimit
358                    : getRowMin(rowIndex) <= edgeLimit) {
359                // if current row exceeds previous column, fill from next row
360                rowIndex = rowIndex - 1;
361                if (rowIndex < 0) {
362                    // start a new column and using edge limit of current column
363                    rowIndex = mNumRows - 1;
364                    edgeLimit = mReversedFlow ? findRowMax(true, null) :
365                            findRowMin(false, null);
366                }
367            }
368            edgeLimitIsValid = true;
369        } else {
370            itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0;
371            // if there are cached items,  put on previous row of first cached item.
372            rowIndex = (mLocations.size() >= 0 ? getLocation(getFirstIndex()).row + mNumRows - 1
373                    : itemIndex) % mNumRows;
374            edgeLimit = 0;
375            edgeLimitIsValid = false;
376        }
377        boolean filledOne = false;
378        while (true) {
379            // find start-most row edge (.low is smallest, or .high is largest in reversed flow)
380            // fill from current row till first row so that each row will grow longer than
381            // the previous lowest row.
382            for (; rowIndex >= 0; rowIndex--) {
383                // fill one item to a row
384                if (itemIndex < 0 || (!oneColumnMode && checkPrependOverLimit(toLimit))) {
385                    return filledOne;
386                }
387                int location = mReversedFlow ? getRowMax(rowIndex) : getRowMin(rowIndex);
388                if (location == Integer.MAX_VALUE || location == Integer.MIN_VALUE) {
389                    // nothing on the row
390                    if (rowIndex == mNumRows - 1) {
391                        location = mReversedFlow ? getRowMax(0) : getRowMin(0);
392                        if (location != Integer.MAX_VALUE && location != Integer.MIN_VALUE) {
393                            location = location + (mReversedFlow ? mMargin : -mMargin);
394                        }
395                    } else {
396                        location = mReversedFlow ? getRowMin(rowIndex + 1) : getRowMax(rowIndex + 1);
397                    }
398                } else {
399                    location = location + (mReversedFlow ? mMargin : -mMargin);
400                }
401                int size = prependVisibleItemToRow(itemIndex--, rowIndex, location);
402                filledOne = true;
403
404                // fill more item to the row to make sure this row is longer than
405                // the previous highest row.
406                if (edgeLimitIsValid) {
407                    while (mReversedFlow ? location + size < edgeLimit :
408                            location - size > edgeLimit) {
409                        if (itemIndex < 0 || (!oneColumnMode && checkPrependOverLimit(toLimit))) {
410                            return filledOne;
411                        }
412                        location = location + (mReversedFlow ? size + mMargin : -size - mMargin);
413                        size = prependVisibleItemToRow(itemIndex--, rowIndex, location);
414                    }
415                } else {
416                    edgeLimitIsValid = true;
417                    edgeLimit = mReversedFlow ? getRowMax(rowIndex) : getRowMin(rowIndex);
418                }
419            }
420            if (oneColumnMode) {
421                return filledOne;
422            }
423            edgeLimit = mReversedFlow ? findRowMax(true, null) : findRowMin(false, null);
424            // start fill from last row again
425            rowIndex = mNumRows - 1;
426        }
427    }
428
429
430}
431