StaggeredGrid.java revision 3e534fdedcd360d1dd5bcc51661d93f71e57b31e
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 && mFirstVisibleIndex >= 0 && 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 edge = mProvider.getEdge(itemIndex); 185 offset = loc.offset; 186 // Check limit after filled a full column 187 if (rowIndex == 0) { 188 if (oneColumnMode || checkPrependOverLimit(toLimit)) { 189 return true; 190 } 191 } 192 } 193 return false; 194 } 195 196 /** 197 * When we append first visible item without cache after cached items, the offset 198 * of the first visible item cannot be determined until we prepend previous item with cache. 199 * This method is called from prependVisbleItemsWithCache() to update the offset 200 * of first visible item. 201 * @param prependedItemSize Size of the prepended item. 202 * @return Updated size of current first visible item. 203 */ 204 protected abstract int updateFirstVisibleOffset(int prependedItemSize); 205 206 /** 207 * This implements the algorithm of layout staggered grid, the method should only be called by 208 * prependVisibleItems(). 209 */ 210 protected abstract boolean prependVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode); 211 212 /** 213 * Prepends one visible item with new Location info. Only called from 214 * prependVisibleItemsWithoutCache(). 215 */ 216 protected final int prependVisibleItemToRow(int itemIndex, int rowIndex, int edge) { 217 int offset; 218 if (mFirstVisibleIndex >= 0) { 219 if (mFirstVisibleIndex != getFirstIndex() || mFirstVisibleIndex != itemIndex + 1) { 220 // should never hit this when we prepend a new item with a new Location object. 221 throw new IllegalStateException(); 222 } 223 } 224 Location oldFirstLoc = mFirstIndex >= 0 ? getLocation(mFirstIndex) : null; 225 int oldFirstEdge = mProvider.getEdge(mFirstIndex); 226 Location loc = new Location(rowIndex, 0, 0); 227 Object item; 228 if (mPendingItem != null) { 229 loc.size = mPendingItemSize; 230 item = mPendingItem; 231 mPendingItem = null; 232 } else { 233 loc.size = mProvider.createItem(itemIndex, false, mTmpItem); 234 item = mTmpItem[0]; 235 } 236 mFirstIndex = mFirstVisibleIndex = itemIndex; 237 if (mLastVisibleIndex < 0) { 238 mLastVisibleIndex = itemIndex; 239 } 240 mLocations.addFirst(loc); 241 int thisEdge = !mReversedFlow ? edge - loc.size : edge + loc.size; 242 if (oldFirstLoc != null) { 243 oldFirstLoc.offset = oldFirstEdge - thisEdge; 244 } 245 mProvider.addItem(item, itemIndex, loc.size, rowIndex, thisEdge); 246 return loc.size; 247 } 248 249 @Override 250 protected final boolean appendVisibleItems(int toLimit, boolean oneColumnMode) { 251 if (mProvider.getCount() == 0) { 252 return false; 253 } 254 if (!oneColumnMode && mFirstVisibleIndex >= 0 && checkAppendOverLimit(toLimit)) { 255 return false; 256 } 257 try { 258 if (appendVisbleItemsWithCache(toLimit, oneColumnMode)) { 259 return true; 260 } 261 return appendVisibleItemsWithoutCache(toLimit, oneColumnMode); 262 } finally { 263 mTmpItem[0] = null; 264 mPendingItem = null; 265 } 266 } 267 268 /** 269 * Appends items using cached locations, returning true if at least one item is appended 270 * and (oneColumnMode is true or reach limit and aboveIndex). 271 * This method should only be called by appendVisibleItems() 272 */ 273 protected final boolean appendVisbleItemsWithCache(int toLimit, boolean oneColumnMode) { 274 if (mLocations.size() == 0) { 275 return false; 276 } 277 final int count = mProvider.getCount(); 278 int itemIndex; 279 int edge; 280 if (mLastVisibleIndex >= 0) { 281 // append visible items from last visible index 282 itemIndex = mLastVisibleIndex + 1; 283 edge = mProvider.getEdge(mLastVisibleIndex); 284 } else { 285 // append first visible item 286 edge = Integer.MAX_VALUE; 287 itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0; 288 for (int i = itemIndex - 1; i >= mFirstIndex; i--) { 289 if (getLocation(i).row == mNumRows - 1) { 290 itemIndex = i + 1; 291 break; 292 } 293 } 294 } 295 int lastIndex = getLastIndex(); 296 for (; itemIndex < count && itemIndex <= lastIndex; itemIndex++) { 297 Location loc = getLocation(itemIndex); 298 if (edge != Integer.MAX_VALUE) { 299 edge = edge + loc.offset; 300 } 301 int rowIndex = loc.row; 302 int size = mProvider.createItem(itemIndex, true, mTmpItem); 303 if (size != loc.size) { 304 loc.size = size; 305 mLocations.removeFromEnd(lastIndex - itemIndex); 306 lastIndex = itemIndex; 307 } 308 mLastVisibleIndex = itemIndex; 309 if (mFirstVisibleIndex < 0) { 310 mFirstVisibleIndex = itemIndex; 311 } 312 mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge); 313 if (edge == Integer.MAX_VALUE) { 314 edge = mProvider.getEdge(itemIndex); 315 } 316 // Check limit after filled a full column 317 if (rowIndex == mNumRows - 1) { 318 if (oneColumnMode || checkAppendOverLimit(toLimit)) { 319 return true; 320 } 321 } 322 } 323 return false; 324 } 325 326 /** 327 * algorithm of layout staggered grid, this method should only be called by 328 * appendVisibleItems(). 329 */ 330 protected abstract boolean appendVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode); 331 332 /** 333 * Appends one visible item with new Location info. Only called from 334 * appendVisibleItemsWithoutCache(). 335 */ 336 protected final int appendVisibleItemToRow(int itemIndex, int rowIndex, int location) { 337 int offset; 338 if (mLastVisibleIndex >= 0) { 339 if (mLastVisibleIndex != getLastIndex() || mLastVisibleIndex != itemIndex - 1) { 340 // should never hit this when we append a new item with a new Location object. 341 throw new IllegalStateException(); 342 } 343 } 344 if (mLastVisibleIndex < 0) { 345 // if we append first visible item after existing cached items, we need update 346 // the offset later when prependVisbleItemsWithCache() 347 offset = OFFSET_UNDEFINED; 348 } else { 349 offset = location - mProvider.getEdge(mLastVisibleIndex); 350 } 351 Location loc = new Location(rowIndex, offset, 0); 352 Object item; 353 if (mPendingItem != null) { 354 loc.size = mPendingItemSize; 355 item = mPendingItem; 356 mPendingItem = null; 357 } else { 358 loc.size = mProvider.createItem(itemIndex, true, mTmpItem); 359 item = mTmpItem[0]; 360 } 361 if (mLocations.size() == 0) { 362 mFirstIndex = mFirstVisibleIndex = mLastVisibleIndex = itemIndex; 363 } else { 364 if (mLastVisibleIndex < 0) { 365 mFirstVisibleIndex = mLastVisibleIndex = itemIndex; 366 } else { 367 mLastVisibleIndex++; 368 } 369 } 370 mLocations.addLast(loc); 371 mProvider.addItem(item, itemIndex, loc.size, rowIndex, location); 372 return loc.size; 373 } 374 375 @Override 376 public final CircularIntArray[] getItemPositionsInRows(int startPos, int endPos) { 377 for (int i = 0; i < mNumRows; i++) { 378 mTmpItemPositionsInRows[i].clear(); 379 } 380 if (startPos >= 0) { 381 for (int i = startPos; i <= endPos; i++) { 382 CircularIntArray row = mTmpItemPositionsInRows[getLocation(i).row]; 383 if (row.size() > 0 && row.getLast() == i - 1) { 384 // update continuous range 385 row.popLast(); 386 row.addLast(i); 387 } else { 388 // add single position 389 row.addLast(i); 390 row.addLast(i); 391 } 392 } 393 } 394 return mTmpItemPositionsInRows; 395 } 396 397 @Override 398 public void invalidateItemsAfter(int index) { 399 super.invalidateItemsAfter(index); 400 mLocations.removeFromEnd(getLastIndex() - index + 1); 401 if (mLocations.size() == 0) { 402 mFirstIndex = -1; 403 } 404 } 405 406} 407