StaggeredGrid.java revision 85df3117f0fcd0aa10d7bd45194dab97e22112f2
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 16import android.support.v4.util.CircularArray; 17import android.support.v4.util.CircularIntArray; 18 19import java.io.PrintWriter; 20import java.util.ArrayList; 21import java.util.List; 22 23/** 24 * A dynamic data structure that caches staggered grid position information 25 * for each individual child. The algorithm ensures that each row will be kept 26 * as balanced as possible when prepending and appending a child. 27 * 28 * <p> 29 * You may keep view {@link StaggeredGrid.Location} inside StaggeredGrid as much 30 * as possible since prepending and appending views is not symmetric: layout 31 * going from 0 to N will likely produce a different result than layout going 32 * from N to 0 for the staggered cases. If a user scrolls from 0 to N then 33 * scrolls back to 0 and we don't keep history location information, edges of 34 * the very beginning of rows will not be aligned. It is recommended to keep a 35 * list of tens of thousands of {@link StaggeredGrid.Location}s which will be 36 * big enough to remember a typical user's scroll history. 37 * 38 * <p> 39 * This class is abstract and can be replaced with different implementations. 40 */ 41abstract class StaggeredGrid extends Grid { 42 43 private static final int OFFSET_UNDEFINED = Integer.MAX_VALUE; 44 45 /** 46 * Cached representation of Staggered item. 47 */ 48 public static class Location extends Grid.Location { 49 /** 50 * Offset to previous item location. 51 * min_edge(index) - min_edge(index - 1) for non reversed case 52 * max_edge(index) - max_edge(index - 1) for reversed case 53 */ 54 public int offset; 55 56 /** 57 * size of the item. 58 */ 59 public int size; 60 61 public Location(int row, int offset, int size) { 62 super(row); 63 this.offset = offset; 64 this.size = size; 65 } 66 } 67 68 protected CircularArray<Location> mLocations = new CircularArray<Location>(64); 69 70 // mFirstIndex <= mFirstVisibleIndex <= mLastVisibleIndex 71 // <= mFirstIndex + mLocations.size() - 1 72 protected int mFirstIndex = -1; 73 74 private Object[] mTmpItem = new Object[1]; 75 76 protected Object mPendingItem; 77 protected int mPendingItemSize; 78 79 /** 80 * Returns index of first item (cached or visible) in the staggered grid. 81 * Returns negative value if no item. 82 */ 83 public final int getFirstIndex() { 84 return mFirstIndex; 85 } 86 87 /** 88 * Returns index of last item (cached or visible) in the staggered grid. 89 * Returns negative value if no item. 90 */ 91 public final int getLastIndex() { 92 return mFirstIndex + mLocations.size() - 1; 93 } 94 95 /** 96 * Returns the size of the saved {@link Location}s. 97 */ 98 public final int getSize() { 99 return mLocations.size(); 100 } 101 102 @Override 103 public final Location getLocation(int index) { 104 if (mLocations.size() == 0) { 105 return null; 106 } 107 return mLocations.get(index - mFirstIndex); 108 } 109 110 @Override 111 public final void debugPrint(PrintWriter pw) { 112 for (int i = 0, size = mLocations.size(); i < size; i++) { 113 Location loc = mLocations.get(i); 114 pw.print("<" + (mFirstIndex + i) + "," + loc.row + ">"); 115 pw.print(" "); 116 pw.println(); 117 } 118 } 119 120 @Override 121 protected final boolean prependVisibleItems(int toLimit, boolean oneColumnMode) { 122 if (mProvider.getCount() == 0) { 123 return false; 124 } 125 if (!oneColumnMode && checkPrependOverLimit(toLimit)) { 126 return false; 127 } 128 try { 129 if (prependVisbleItemsWithCache(toLimit, oneColumnMode)) { 130 return true; 131 } 132 return prependVisibleItemsWithoutCache(toLimit, oneColumnMode); 133 } finally { 134 mTmpItem[0] = null; 135 mPendingItem = null; 136 } 137 } 138 139 /** 140 * Prepends items using cached locations, returning true if toLimit is reached. 141 * This method should only be called by prependVisibleItems(). 142 */ 143 protected final boolean prependVisbleItemsWithCache(int toLimit, boolean oneColumnMode) { 144 if (mLocations.size() == 0) { 145 return false; 146 } 147 final int count = mProvider.getCount(); 148 final int firstIndex = getFirstIndex(); 149 int itemIndex; 150 int edge; 151 int offset; 152 if (mFirstVisibleIndex >= 0) { 153 // prepend visible items from first visible index 154 edge = mProvider.getEdge(mFirstVisibleIndex); 155 // Note offset of first visible item can be OFFSET_UNDEFINED. 156 offset = getLocation(mFirstVisibleIndex).offset; 157 itemIndex = mFirstVisibleIndex - 1; 158 } else { 159 // prepend first visible item 160 edge = Integer.MAX_VALUE; 161 offset = 0; 162 itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0; 163 } 164 for (; itemIndex >= mFirstIndex; itemIndex--) { 165 Location loc = getLocation(itemIndex); 166 int rowIndex = loc.row; 167 int size = mProvider.createItem(itemIndex, false, mTmpItem); 168 if (size != loc.size) { 169 mLocations.removeFromStart(itemIndex + 1 - mFirstIndex); 170 mFirstIndex = mFirstVisibleIndex; 171 // pending item will be added in prependVisibleItemsWithoutCache 172 mPendingItem = mTmpItem[0]; 173 mPendingItemSize = size; 174 return false; 175 } 176 if (offset == OFFSET_UNDEFINED) { 177 offset = updateFirstVisibleOffset(size); 178 } 179 mFirstVisibleIndex = itemIndex; 180 if (mLastVisibleIndex < 0) { 181 mLastVisibleIndex = itemIndex; 182 } 183 mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge - offset); 184 if (!oneColumnMode && checkPrependOverLimit(toLimit)) { 185 return true; 186 } 187 edge = mProvider.getEdge(itemIndex); 188 offset = loc.offset; 189 // Check limit after filled a full column 190 if (rowIndex == 0) { 191 if (oneColumnMode) { 192 return true; 193 } 194 } 195 } 196 return false; 197 } 198 199 /** 200 * When we append first visible item without cache after cached items, the offset 201 * of the first visible item cannot be determined until we prepend previous item with cache. 202 * This method is called from prependVisbleItemsWithCache() to update the offset 203 * of first visible item. 204 * @param prependedItemSize Size of the prepended item. 205 * @return Updated size of current first visible item. 206 */ 207 protected abstract int updateFirstVisibleOffset(int prependedItemSize); 208 209 /** 210 * This implements the algorithm of layout staggered grid, the method should only be called by 211 * prependVisibleItems(). 212 */ 213 protected abstract boolean prependVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode); 214 215 /** 216 * Prepends one visible item with new Location info. Only called from 217 * prependVisibleItemsWithoutCache(). 218 */ 219 protected final int prependVisibleItemToRow(int itemIndex, int rowIndex, int edge) { 220 int offset; 221 if (mFirstVisibleIndex >= 0) { 222 if (mFirstVisibleIndex != getFirstIndex() || mFirstVisibleIndex != itemIndex + 1) { 223 // should never hit this when we prepend a new item with a new Location object. 224 throw new IllegalStateException(); 225 } 226 } 227 Location oldFirstLoc = mFirstIndex >= 0 ? getLocation(mFirstIndex) : null; 228 int oldFirstEdge = mProvider.getEdge(mFirstIndex); 229 Location loc = new Location(rowIndex, 0, 0); 230 Object item; 231 if (mPendingItem != null) { 232 loc.size = mPendingItemSize; 233 item = mPendingItem; 234 mPendingItem = null; 235 } else { 236 loc.size = mProvider.createItem(itemIndex, false, mTmpItem); 237 item = mTmpItem[0]; 238 } 239 mFirstIndex = mFirstVisibleIndex = itemIndex; 240 if (mLastVisibleIndex < 0) { 241 mLastVisibleIndex = itemIndex; 242 } 243 mLocations.addFirst(loc); 244 int thisEdge = !mReversedFlow ? edge - loc.size : edge + loc.size; 245 if (oldFirstLoc != null) { 246 oldFirstLoc.offset = oldFirstEdge - thisEdge; 247 } 248 mProvider.addItem(item, itemIndex, loc.size, rowIndex, thisEdge); 249 return loc.size; 250 } 251 252 @Override 253 protected final boolean appendVisibleItems(int toLimit, boolean oneColumnMode) { 254 if (mProvider.getCount() == 0) { 255 return false; 256 } 257 if (!oneColumnMode && checkAppendOverLimit(toLimit)) { 258 return false; 259 } 260 try { 261 if (appendVisbleItemsWithCache(toLimit, oneColumnMode)) { 262 return true; 263 } 264 return appendVisibleItemsWithoutCache(toLimit, oneColumnMode); 265 } finally { 266 mTmpItem[0] = null; 267 mPendingItem = null; 268 } 269 } 270 271 /** 272 * Appends items using cached locations, returning true if at least one item is appended 273 * and (oneColumnMode is true or reach limit and aboveIndex). 274 * This method should only be called by appendVisibleItems() 275 */ 276 protected final boolean appendVisbleItemsWithCache(int toLimit, boolean oneColumnMode) { 277 if (mLocations.size() == 0) { 278 return false; 279 } 280 final int count = mProvider.getCount(); 281 int itemIndex; 282 int edge; 283 if (mLastVisibleIndex >= 0) { 284 // append visible items from last visible index 285 itemIndex = mLastVisibleIndex + 1; 286 edge = mProvider.getEdge(mLastVisibleIndex); 287 } else { 288 // append first visible item 289 edge = Integer.MAX_VALUE; 290 itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0; 291 for (int i = itemIndex - 1; i >= mFirstIndex; i--) { 292 if (getLocation(i).row == mNumRows - 1) { 293 itemIndex = i + 1; 294 break; 295 } 296 } 297 } 298 int lastIndex = getLastIndex(); 299 for (; itemIndex < count && itemIndex <= lastIndex; itemIndex++) { 300 Location loc = getLocation(itemIndex); 301 if (edge != Integer.MAX_VALUE) { 302 edge = edge + loc.offset; 303 } 304 int rowIndex = loc.row; 305 int size = mProvider.createItem(itemIndex, true, mTmpItem); 306 if (size != loc.size) { 307 loc.size = size; 308 mLocations.removeFromEnd(lastIndex - itemIndex); 309 lastIndex = itemIndex; 310 } 311 mLastVisibleIndex = itemIndex; 312 if (mFirstVisibleIndex < 0) { 313 mFirstVisibleIndex = itemIndex; 314 } 315 mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge); 316 if (!oneColumnMode && checkAppendOverLimit(toLimit)) { 317 return true; 318 } 319 if (edge == Integer.MAX_VALUE) { 320 edge = mProvider.getEdge(itemIndex); 321 } 322 // Check limit after filled a full column 323 if (rowIndex == mNumRows - 1) { 324 if (oneColumnMode) { 325 return true; 326 } 327 } 328 } 329 return false; 330 } 331 332 /** 333 * algorithm of layout staggered grid, this method should only be called by 334 * appendVisibleItems(). 335 */ 336 protected abstract boolean appendVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode); 337 338 /** 339 * Appends one visible item with new Location info. Only called from 340 * appendVisibleItemsWithoutCache(). 341 */ 342 protected final int appendVisibleItemToRow(int itemIndex, int rowIndex, int location) { 343 int offset; 344 if (mLastVisibleIndex >= 0) { 345 if (mLastVisibleIndex != getLastIndex() || mLastVisibleIndex != itemIndex - 1) { 346 // should never hit this when we append a new item with a new Location object. 347 throw new IllegalStateException(); 348 } 349 } 350 if (mLastVisibleIndex < 0) { 351 // if we append first visible item after existing cached items, we need update 352 // the offset later when prependVisbleItemsWithCache() 353 offset = OFFSET_UNDEFINED; 354 } else { 355 offset = location - mProvider.getEdge(mLastVisibleIndex); 356 } 357 Location loc = new Location(rowIndex, offset, 0); 358 Object item; 359 if (mPendingItem != null) { 360 loc.size = mPendingItemSize; 361 item = mPendingItem; 362 mPendingItem = null; 363 } else { 364 loc.size = mProvider.createItem(itemIndex, true, mTmpItem); 365 item = mTmpItem[0]; 366 } 367 if (mLocations.size() == 0) { 368 mFirstIndex = mFirstVisibleIndex = mLastVisibleIndex = itemIndex; 369 } else { 370 if (mLastVisibleIndex < 0) { 371 mFirstVisibleIndex = mLastVisibleIndex = itemIndex; 372 } else { 373 mLastVisibleIndex++; 374 } 375 } 376 mLocations.addLast(loc); 377 mProvider.addItem(item, itemIndex, loc.size, rowIndex, location); 378 return loc.size; 379 } 380 381 @Override 382 public final CircularIntArray[] getItemPositionsInRows(int startPos, int endPos) { 383 for (int i = 0; i < mNumRows; i++) { 384 mTmpItemPositionsInRows[i].clear(); 385 } 386 if (startPos >= 0) { 387 for (int i = startPos; i <= endPos; i++) { 388 CircularIntArray row = mTmpItemPositionsInRows[getLocation(i).row]; 389 if (row.size() > 0 && row.getLast() == i - 1) { 390 // update continuous range 391 row.popLast(); 392 row.addLast(i); 393 } else { 394 // add single position 395 row.addLast(i); 396 row.addLast(i); 397 } 398 } 399 } 400 return mTmpItemPositionsInRows; 401 } 402 403 @Override 404 public void invalidateItemsAfter(int index) { 405 super.invalidateItemsAfter(index); 406 mLocations.removeFromEnd(getLastIndex() - index + 1); 407 if (mLocations.size() == 0) { 408 mFirstIndex = -1; 409 } 410 } 411 412} 413