StaggeredGrid.java revision 6e96b9d46e7af6bedf6213ecc2ba0ad7b8050778
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 /** 44 * Cached representation of Staggered item. 45 */ 46 public static class Location extends Grid.Location { 47 /** 48 * Offset to previous item location. 49 * min_edge(index) - min_edge(index - 1) for non reversed case 50 * max_edge(index) - max_edge(index - 1) for reversed case 51 */ 52 public int offset; 53 54 /** 55 * size of the item. 56 */ 57 public int size; 58 59 public Location(int row, int offset, int size) { 60 super(row); 61 this.offset = offset; 62 this.size = size; 63 } 64 } 65 66 protected CircularArray<Location> mLocations = new CircularArray<Location>(64); 67 68 // mFirstIndex <= mFirstVisibleIndex <= mLastVisibleIndex 69 // <= mFirstIndex + mLocations.size() - 1 70 protected int mFirstIndex = -1; 71 72 private Object[] mTmpItem = new Object[1]; 73 74 protected Object mPendingItem; 75 protected int mPendingItemSize; 76 77 protected int mStartOffset; 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 if (mFirstVisibleIndex >= 0) { 152 // prepend visible items from first visible index 153 edge = mProvider.getEdge(mFirstVisibleIndex) - getLocation(mFirstVisibleIndex).offset; 154 itemIndex = mFirstVisibleIndex - 1; 155 } else { 156 // prepend first visible item 157 edge = Integer.MAX_VALUE; 158 itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0; 159 } 160 for (; itemIndex >= mFirstIndex; itemIndex--) { 161 Location loc = getLocation(itemIndex); 162 int rowIndex = loc.row; 163 int size = mProvider.createItem(itemIndex, false, mTmpItem); 164 if (size != loc.size) { 165 mLocations.removeFromStart(itemIndex + 1 - mFirstIndex); 166 mFirstIndex = mFirstVisibleIndex; 167 // pending item will be added in prependVisibleItemsWithoutCache 168 mPendingItem = mTmpItem[0]; 169 mPendingItemSize = size; 170 return false; 171 } 172 mFirstVisibleIndex = itemIndex; 173 if (mLastVisibleIndex < 0) { 174 mLastVisibleIndex = itemIndex; 175 } 176 mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge); 177 if (edge == Integer.MAX_VALUE) { 178 edge = mProvider.getEdge(itemIndex); 179 } 180 edge = edge - loc.offset; 181 // Check limit after filled a full column 182 if (rowIndex == 0) { 183 if (oneColumnMode || checkPrependOverLimit(toLimit)) { 184 return true; 185 } 186 } 187 } 188 return false; 189 } 190 191 /** 192 * This implements the algorithm of layout staggered grid, the method should only be called by 193 * prependVisibleItems(). 194 */ 195 protected abstract boolean prependVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode); 196 197 /** 198 * Prepends one visible item with new Location info. Only called from 199 * prependVisibleItemsWithoutCache(). 200 */ 201 protected final int prependVisibleItemToRow(int itemIndex, int rowIndex, int edge) { 202 int offset; 203 if (mFirstVisibleIndex >= 0) { 204 if (mFirstVisibleIndex != getFirstIndex() || mFirstVisibleIndex != itemIndex + 1) { 205 // should never hit this when we prepend a new item with a new Location object. 206 throw new IllegalStateException(); 207 } 208 } 209 Location oldFirstLoc = mFirstIndex >= 0 ? getLocation(mFirstIndex) : null; 210 int oldFirstEdge = mProvider.getEdge(mFirstIndex); 211 Location loc = new Location(rowIndex, 0, 0); 212 Object item; 213 if (mPendingItem != null) { 214 loc.size = mPendingItemSize; 215 item = mPendingItem; 216 mPendingItem = null; 217 } else { 218 loc.size = mProvider.createItem(itemIndex, false, mTmpItem); 219 item = mTmpItem[0]; 220 } 221 mFirstIndex = mFirstVisibleIndex = itemIndex; 222 if (mLastVisibleIndex < 0) { 223 mLastVisibleIndex = itemIndex; 224 } 225 mLocations.addFirst(loc); 226 int thisEdge = !mReversedFlow ? edge - loc.size : edge + loc.size; 227 if (oldFirstLoc != null) { 228 oldFirstLoc.offset = oldFirstEdge - thisEdge; 229 } 230 mProvider.addItem(item, itemIndex, loc.size, rowIndex, thisEdge); 231 return loc.size; 232 } 233 234 @Override 235 protected final boolean appendVisibleItems(int toLimit, boolean oneColumnMode) { 236 if (mProvider.getCount() == 0) { 237 return false; 238 } 239 if (!oneColumnMode && mFirstVisibleIndex >= 0 && checkAppendOverLimit(toLimit)) { 240 return false; 241 } 242 try { 243 if (appendVisbleItemsWithCache(toLimit, oneColumnMode)) { 244 return true; 245 } 246 return appendVisibleItemsWithoutCache(toLimit, oneColumnMode); 247 } finally { 248 mTmpItem[0] = null; 249 mPendingItem = null; 250 } 251 } 252 253 /** 254 * Appends items using cached locations, returning true if at least one item is appended 255 * and (oneColumnMode is true or reach limit and aboveIndex). 256 * This method should only be called by appendVisibleItems() 257 */ 258 protected final boolean appendVisbleItemsWithCache(int toLimit, boolean oneColumnMode) { 259 if (mLocations.size() == 0) { 260 return false; 261 } 262 final int count = mProvider.getCount(); 263 int itemIndex; 264 int edge; 265 if (mLastVisibleIndex >= 0) { 266 // append visible items from last visible index 267 itemIndex = mLastVisibleIndex + 1; 268 edge = mProvider.getEdge(mLastVisibleIndex); 269 } else { 270 // append first visible item 271 edge = Integer.MAX_VALUE; 272 itemIndex = mStartIndex != START_DEFAULT ? mStartIndex : 0; 273 for (int i = itemIndex - 1; i >= mFirstIndex; i--) { 274 if (getLocation(i).row == mNumRows - 1) { 275 itemIndex = i + 1; 276 break; 277 } 278 } 279 } 280 int lastIndex = getLastIndex(); 281 for (; itemIndex < count && itemIndex <= lastIndex; itemIndex++) { 282 Location loc = getLocation(itemIndex); 283 if (edge != Integer.MAX_VALUE) { 284 edge = edge + loc.offset; 285 } 286 int rowIndex = loc.row; 287 int size = mProvider.createItem(itemIndex, true, mTmpItem); 288 if (size != loc.size) { 289 loc.size = size; 290 mLocations.removeFromEnd(lastIndex - itemIndex); 291 lastIndex = itemIndex; 292 } 293 mLastVisibleIndex = itemIndex; 294 if (mFirstVisibleIndex < 0) { 295 mFirstVisibleIndex = itemIndex; 296 } 297 mProvider.addItem(mTmpItem[0], itemIndex, size, rowIndex, edge); 298 if (edge == Integer.MAX_VALUE) { 299 edge = mProvider.getEdge(itemIndex); 300 } 301 // Check limit after filled a full column 302 if (rowIndex == mNumRows - 1) { 303 if (oneColumnMode || checkAppendOverLimit(toLimit)) { 304 return true; 305 } 306 } 307 } 308 return false; 309 } 310 311 /** 312 * algorithm of layout staggered grid, this method should only be called by 313 * appendVisibleItems(). 314 */ 315 protected abstract boolean appendVisibleItemsWithoutCache(int toLimit, boolean oneColumnMode); 316 317 /** 318 * Appends one visible item with new Location info. Only called from 319 * appendVisibleItemsWithoutCache(). 320 */ 321 protected final int appendVisibleItemToRow(int itemIndex, int rowIndex, int location) { 322 int offset; 323 if (mLastVisibleIndex >= 0) { 324 if (mLastVisibleIndex != getLastIndex() || mLastVisibleIndex != itemIndex - 1) { 325 // should never hit this when we append a new item with a new Location object. 326 throw new IllegalStateException(); 327 } 328 } 329 if (location == Integer.MAX_VALUE || location == Integer.MIN_VALUE) { 330 if (mStartIndex == itemIndex) { 331 offset = mStartOffset; 332 mStartOffset = 0; 333 } else { 334 offset = 0; 335 } 336 } else { 337 offset = location - mProvider.getEdge(mLastVisibleIndex); 338 } 339 Location loc = new Location(rowIndex, offset, 0); 340 Object item; 341 if (mPendingItem != null) { 342 loc.size = mPendingItemSize; 343 item = mPendingItem; 344 mPendingItem = null; 345 } else { 346 loc.size = mProvider.createItem(itemIndex, true, mTmpItem); 347 item = mTmpItem[0]; 348 } 349 if (mLocations.size() == 0) { 350 mFirstIndex = mFirstVisibleIndex = mLastVisibleIndex = itemIndex; 351 } else { 352 if (mLastVisibleIndex < 0) { 353 mFirstVisibleIndex = mLastVisibleIndex = itemIndex; 354 } else { 355 mLastVisibleIndex++; 356 } 357 } 358 mLocations.addLast(loc); 359 mProvider.addItem(item, itemIndex, loc.size, rowIndex, location); 360 return loc.size; 361 } 362 363 @Override 364 public final CircularIntArray[] getItemPositionsInRows(int startPos, int endPos) { 365 for (int i = 0; i < mNumRows; i++) { 366 mTmpItemPositionsInRows[i].clear(); 367 } 368 if (startPos >= 0) { 369 for (int i = startPos; i <= endPos; i++) { 370 CircularIntArray row = mTmpItemPositionsInRows[getLocation(i).row]; 371 if (row.size() > 0 && row.getLast() == i - 1) { 372 // update continuous range 373 row.popLast(); 374 row.addLast(i); 375 } else { 376 // add single position 377 row.addLast(i); 378 row.addLast(i); 379 } 380 } 381 } 382 return mTmpItemPositionsInRows; 383 } 384 385 @Override 386 public void invalidateItemsAfter(int index) { 387 super.invalidateItemsAfter(index); 388 mLocations.removeFromEnd(getLastIndex() - index + 1); 389 if (mLocations.size() == 0) { 390 mFirstIndex = -1; 391 } 392 } 393 394 @Override 395 public void setStart(int startIndex) { 396 super.setStart(startIndex); 397 if (startIndex >= 0 && startIndex >= getFirstIndex() && startIndex <= getLastIndex()) { 398 // Remembers the offset at index, so next time append uses this value for relative 399 // offset to item in front of the index. 400 mStartOffset = getLocation(startIndex).offset; 401 } else { 402 mStartOffset = 0; 403 } 404 } 405} 406