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  */
14 package androidx.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  */
22 final 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      */
getRowMax(int rowIndex)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      */
getRowMin(int rowIndex)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
findRowMax(boolean findLarge, int indexLimit, int[] indices)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
findRowMin(boolean findLarge, int indexLimit, int[] indices)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 
findRowEdgeLimitSearchIndex(boolean append)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
appendVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode)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 column" 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 ? -mSpacing : mSpacing);
293                         }
294                     } else {
295                         location = mReversedFlow ? getRowMax(rowIndex - 1) : getRowMin(rowIndex - 1);
296                     }
297                 } else {
298                     location = location + (mReversedFlow ? -mSpacing : mSpacing);
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 - mSpacing : size + mSpacing);
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
prependVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode)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 column" 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 ? mSpacing : -mSpacing);
394                         }
395                     } else {
396                         location = mReversedFlow ? getRowMin(rowIndex + 1) : getRowMax(rowIndex + 1);
397                     }
398                 } else {
399                     location = location + (mReversedFlow ? mSpacing : -mSpacing);
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 + mSpacing : -size - mSpacing);
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