1/* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.support.v7.util; 18 19import android.support.annotation.Nullable; 20import android.support.annotation.VisibleForTesting; 21import android.support.v7.widget.RecyclerView; 22 23import java.util.ArrayList; 24import java.util.Arrays; 25import java.util.Collections; 26import java.util.Comparator; 27import java.util.List; 28 29/** 30 * DiffUtil is a utility class that can calculate the difference between two lists and output a 31 * list of update operations that converts the first list into the second one. 32 * <p> 33 * It can be used to calculate updates for a RecyclerView Adapter. 34 * <p> 35 * DiffUtil uses Eugene W. Myers's difference algorithm to calculate the minimal number of updates 36 * to convert one list into another. Myers's algorithm does not handle items that are moved so 37 * DiffUtil runs a second pass on the result to detect items that were moved. 38 * <p> 39 * If the lists are large, this operation may take significant time so you are advised to run this 40 * on a background thread, get the {@link DiffResult} then apply it on the RecyclerView on the main 41 * thread. 42 * <p> 43 * This algorithm is optimized for space and uses O(N) space to find the minimal 44 * number of addition and removal operations between the two lists. It has O(N + D^2) expected time 45 * performance where D is the length of the edit script. 46 * <p> 47 * If move detection is enabled, it takes an additional O(N^2) time where N is the total number of 48 * added and removed items. If your lists are already sorted by the same constraint (e.g. a created 49 * timestamp for a list of posts), you can disable move detection to improve performance. 50 * <p> 51 * The actual runtime of the algorithm significantly depends on the number of changes in the list 52 * and the cost of your comparison methods. Below are some average run times for reference: 53 * (The test list is composed of random UUID Strings and the tests are run on Nexus 5X with M) 54 * <ul> 55 * <li>100 items and 10 modifications: avg: 0.39 ms, median: 0.35 ms 56 * <li>100 items and 100 modifications: 3.82 ms, median: 3.75 ms 57 * <li>100 items and 100 modifications without moves: 2.09 ms, median: 2.06 ms 58 * <li>1000 items and 50 modifications: avg: 4.67 ms, median: 4.59 ms 59 * <li>1000 items and 50 modifications without moves: avg: 3.59 ms, median: 3.50 ms 60 * <li>1000 items and 200 modifications: 27.07 ms, median: 26.92 ms 61 * <li>1000 items and 200 modifications without moves: 13.54 ms, median: 13.36 ms 62 * </ul> 63 * <p> 64 * Due to implementation constraints, the max size of the list can be 2^26. 65 */ 66public class DiffUtil { 67 68 private DiffUtil() { 69 // utility class, no instance. 70 } 71 72 private static final Comparator<Snake> SNAKE_COMPARATOR = new Comparator<Snake>() { 73 @Override 74 public int compare(Snake o1, Snake o2) { 75 int cmpX = o1.x - o2.x; 76 return cmpX == 0 ? o1.y - o2.y : cmpX; 77 } 78 }; 79 80 // Myers' algorithm uses two lists as axis labels. In DiffUtil's implementation, `x` axis is 81 // used for old list and `y` axis is used for new list. 82 83 /** 84 * Calculates the list of update operations that can covert one list into the other one. 85 * 86 * @param cb The callback that acts as a gateway to the backing list data 87 * 88 * @return A DiffResult that contains the information about the edit sequence to convert the 89 * old list into the new list. 90 */ 91 public static DiffResult calculateDiff(Callback cb) { 92 return calculateDiff(cb, true); 93 } 94 95 /** 96 * Calculates the list of update operations that can covert one list into the other one. 97 * <p> 98 * If your old and new lists are sorted by the same constraint and items never move (swap 99 * positions), you can disable move detection which takes <code>O(N^2)</code> time where 100 * N is the number of added, moved, removed items. 101 * 102 * @param cb The callback that acts as a gateway to the backing list data 103 * @param detectMoves True if DiffUtil should try to detect moved items, false otherwise. 104 * 105 * @return A DiffResult that contains the information about the edit sequence to convert the 106 * old list into the new list. 107 */ 108 public static DiffResult calculateDiff(Callback cb, boolean detectMoves) { 109 final int oldSize = cb.getOldListSize(); 110 final int newSize = cb.getNewListSize(); 111 112 final List<Snake> snakes = new ArrayList<>(); 113 114 // instead of a recursive implementation, we keep our own stack to avoid potential stack 115 // overflow exceptions 116 final List<Range> stack = new ArrayList<>(); 117 118 stack.add(new Range(0, oldSize, 0, newSize)); 119 120 final int max = oldSize + newSize + Math.abs(oldSize - newSize); 121 // allocate forward and backward k-lines. K lines are diagonal lines in the matrix. (see the 122 // paper for details) 123 // These arrays lines keep the max reachable position for each k-line. 124 final int[] forward = new int[max * 2]; 125 final int[] backward = new int[max * 2]; 126 127 // We pool the ranges to avoid allocations for each recursive call. 128 final List<Range> rangePool = new ArrayList<>(); 129 while (!stack.isEmpty()) { 130 final Range range = stack.remove(stack.size() - 1); 131 final Snake snake = diffPartial(cb, range.oldListStart, range.oldListEnd, 132 range.newListStart, range.newListEnd, forward, backward, max); 133 if (snake != null) { 134 if (snake.size > 0) { 135 snakes.add(snake); 136 } 137 // offset the snake to convert its coordinates from the Range's area to global 138 snake.x += range.oldListStart; 139 snake.y += range.newListStart; 140 141 // add new ranges for left and right 142 final Range left = rangePool.isEmpty() ? new Range() : rangePool.remove( 143 rangePool.size() - 1); 144 left.oldListStart = range.oldListStart; 145 left.newListStart = range.newListStart; 146 if (snake.reverse) { 147 left.oldListEnd = snake.x; 148 left.newListEnd = snake.y; 149 } else { 150 if (snake.removal) { 151 left.oldListEnd = snake.x - 1; 152 left.newListEnd = snake.y; 153 } else { 154 left.oldListEnd = snake.x; 155 left.newListEnd = snake.y - 1; 156 } 157 } 158 stack.add(left); 159 160 // re-use range for right 161 //noinspection UnnecessaryLocalVariable 162 final Range right = range; 163 if (snake.reverse) { 164 if (snake.removal) { 165 right.oldListStart = snake.x + snake.size + 1; 166 right.newListStart = snake.y + snake.size; 167 } else { 168 right.oldListStart = snake.x + snake.size; 169 right.newListStart = snake.y + snake.size + 1; 170 } 171 } else { 172 right.oldListStart = snake.x + snake.size; 173 right.newListStart = snake.y + snake.size; 174 } 175 stack.add(right); 176 } else { 177 rangePool.add(range); 178 } 179 180 } 181 // sort snakes 182 Collections.sort(snakes, SNAKE_COMPARATOR); 183 184 return new DiffResult(cb, snakes, forward, backward, detectMoves); 185 186 } 187 188 private static Snake diffPartial(Callback cb, int startOld, int endOld, 189 int startNew, int endNew, int[] forward, int[] backward, int kOffset) { 190 final int oldSize = endOld - startOld; 191 final int newSize = endNew - startNew; 192 193 if (endOld - startOld < 1 || endNew - startNew < 1) { 194 return null; 195 } 196 197 final int delta = oldSize - newSize; 198 final int dLimit = (oldSize + newSize + 1) / 2; 199 Arrays.fill(forward, kOffset - dLimit - 1, kOffset + dLimit + 1, 0); 200 Arrays.fill(backward, kOffset - dLimit - 1 + delta, kOffset + dLimit + 1 + delta, oldSize); 201 final boolean checkInFwd = delta % 2 != 0; 202 for (int d = 0; d <= dLimit; d++) { 203 for (int k = -d; k <= d; k += 2) { 204 // find forward path 205 // we can reach k from k - 1 or k + 1. Check which one is further in the graph 206 int x; 207 final boolean removal; 208 if (k == -d || (k != d && forward[kOffset + k - 1] < forward[kOffset + k + 1])) { 209 x = forward[kOffset + k + 1]; 210 removal = false; 211 } else { 212 x = forward[kOffset + k - 1] + 1; 213 removal = true; 214 } 215 // set y based on x 216 int y = x - k; 217 // move diagonal as long as items match 218 while (x < oldSize && y < newSize 219 && cb.areItemsTheSame(startOld + x, startNew + y)) { 220 x++; 221 y++; 222 } 223 forward[kOffset + k] = x; 224 if (checkInFwd && k >= delta - d + 1 && k <= delta + d - 1) { 225 if (forward[kOffset + k] >= backward[kOffset + k]) { 226 Snake outSnake = new Snake(); 227 outSnake.x = backward[kOffset + k]; 228 outSnake.y = outSnake.x - k; 229 outSnake.size = forward[kOffset + k] - backward[kOffset + k]; 230 outSnake.removal = removal; 231 outSnake.reverse = false; 232 return outSnake; 233 } 234 } 235 } 236 for (int k = -d; k <= d; k += 2) { 237 // find reverse path at k + delta, in reverse 238 final int backwardK = k + delta; 239 int x; 240 final boolean removal; 241 if (backwardK == d + delta || (backwardK != -d + delta 242 && backward[kOffset + backwardK - 1] < backward[kOffset + backwardK + 1])) { 243 x = backward[kOffset + backwardK - 1]; 244 removal = false; 245 } else { 246 x = backward[kOffset + backwardK + 1] - 1; 247 removal = true; 248 } 249 250 // set y based on x 251 int y = x - backwardK; 252 // move diagonal as long as items match 253 while (x > 0 && y > 0 254 && cb.areItemsTheSame(startOld + x - 1, startNew + y - 1)) { 255 x--; 256 y--; 257 } 258 backward[kOffset + backwardK] = x; 259 if (!checkInFwd && k + delta >= -d && k + delta <= d) { 260 if (forward[kOffset + backwardK] >= backward[kOffset + backwardK]) { 261 Snake outSnake = new Snake(); 262 outSnake.x = backward[kOffset + backwardK]; 263 outSnake.y = outSnake.x - backwardK; 264 outSnake.size = 265 forward[kOffset + backwardK] - backward[kOffset + backwardK]; 266 outSnake.removal = removal; 267 outSnake.reverse = true; 268 return outSnake; 269 } 270 } 271 } 272 } 273 throw new IllegalStateException("DiffUtil hit an unexpected case while trying to calculate" 274 + " the optimal path. Please make sure your data is not changing during the" 275 + " diff calculation."); 276 } 277 278 /** 279 * A Callback class used by DiffUtil while calculating the diff between two lists. 280 */ 281 public abstract static class Callback { 282 /** 283 * Returns the size of the old list. 284 * 285 * @return The size of the old list. 286 */ 287 public abstract int getOldListSize(); 288 289 /** 290 * Returns the size of the new list. 291 * 292 * @return The size of the new list. 293 */ 294 public abstract int getNewListSize(); 295 296 /** 297 * Called by the DiffUtil to decide whether two object represent the same Item. 298 * <p> 299 * For example, if your items have unique ids, this method should check their id equality. 300 * 301 * @param oldItemPosition The position of the item in the old list 302 * @param newItemPosition The position of the item in the new list 303 * @return True if the two items represent the same object or false if they are different. 304 */ 305 public abstract boolean areItemsTheSame(int oldItemPosition, int newItemPosition); 306 307 /** 308 * Called by the DiffUtil when it wants to check whether two items have the same data. 309 * DiffUtil uses this information to detect if the contents of an item has changed. 310 * <p> 311 * DiffUtil uses this method to check equality instead of {@link Object#equals(Object)} 312 * so that you can change its behavior depending on your UI. 313 * For example, if you are using DiffUtil with a 314 * {@link android.support.v7.widget.RecyclerView.Adapter RecyclerView.Adapter}, you should 315 * return whether the items' visual representations are the same. 316 * <p> 317 * This method is called only if {@link #areItemsTheSame(int, int)} returns 318 * {@code true} for these items. 319 * 320 * @param oldItemPosition The position of the item in the old list 321 * @param newItemPosition The position of the item in the new list which replaces the 322 * oldItem 323 * @return True if the contents of the items are the same or false if they are different. 324 */ 325 public abstract boolean areContentsTheSame(int oldItemPosition, int newItemPosition); 326 327 /** 328 * When {@link #areItemsTheSame(int, int)} returns {@code true} for two items and 329 * {@link #areContentsTheSame(int, int)} returns false for them, DiffUtil 330 * calls this method to get a payload about the change. 331 * <p> 332 * For example, if you are using DiffUtil with {@link RecyclerView}, you can return the 333 * particular field that changed in the item and your 334 * {@link android.support.v7.widget.RecyclerView.ItemAnimator ItemAnimator} can use that 335 * information to run the correct animation. 336 * <p> 337 * Default implementation returns {@code null}. 338 * 339 * @param oldItemPosition The position of the item in the old list 340 * @param newItemPosition The position of the item in the new list 341 * 342 * @return A payload object that represents the change between the two items. 343 */ 344 @Nullable 345 public Object getChangePayload(int oldItemPosition, int newItemPosition) { 346 return null; 347 } 348 } 349 350 /** 351 * Snakes represent a match between two lists. It is optionally prefixed or postfixed with an 352 * add or remove operation. See the Myers' paper for details. 353 */ 354 static class Snake { 355 /** 356 * Position in the old list 357 */ 358 int x; 359 360 /** 361 * Position in the new list 362 */ 363 int y; 364 365 /** 366 * Number of matches. Might be 0. 367 */ 368 int size; 369 370 /** 371 * If true, this is a removal from the original list followed by {@code size} matches. 372 * If false, this is an addition from the new list followed by {@code size} matches. 373 */ 374 boolean removal; 375 376 /** 377 * If true, the addition or removal is at the end of the snake. 378 * If false, the addition or removal is at the beginning of the snake. 379 */ 380 boolean reverse; 381 } 382 383 /** 384 * Represents a range in two lists that needs to be solved. 385 * <p> 386 * This internal class is used when running Myers' algorithm without recursion. 387 */ 388 static class Range { 389 390 int oldListStart, oldListEnd; 391 392 int newListStart, newListEnd; 393 394 public Range() { 395 } 396 397 public Range(int oldListStart, int oldListEnd, int newListStart, int newListEnd) { 398 this.oldListStart = oldListStart; 399 this.oldListEnd = oldListEnd; 400 this.newListStart = newListStart; 401 this.newListEnd = newListEnd; 402 } 403 } 404 405 /** 406 * This class holds the information about the result of a 407 * {@link DiffUtil#calculateDiff(Callback, boolean)} call. 408 * <p> 409 * You can consume the updates in a DiffResult via 410 * {@link #dispatchUpdatesTo(ListUpdateCallback)} or directly stream the results into a 411 * {@link RecyclerView.Adapter} via {@link #dispatchUpdatesTo(RecyclerView.Adapter)}. 412 */ 413 public static class DiffResult { 414 /** 415 * While reading the flags below, keep in mind that when multiple items move in a list, 416 * Myers's may pick any of them as the anchor item and consider that one NOT_CHANGED while 417 * picking others as additions and removals. This is completely fine as we later detect 418 * all moves. 419 * <p> 420 * Below, when an item is mentioned to stay in the same "location", it means we won't 421 * dispatch a move/add/remove for it, it DOES NOT mean the item is still in the same 422 * position. 423 */ 424 // item stayed the same. 425 private static final int FLAG_NOT_CHANGED = 1; 426 // item stayed in the same location but changed. 427 private static final int FLAG_CHANGED = FLAG_NOT_CHANGED << 1; 428 // Item has moved and also changed. 429 private static final int FLAG_MOVED_CHANGED = FLAG_CHANGED << 1; 430 // Item has moved but did not change. 431 private static final int FLAG_MOVED_NOT_CHANGED = FLAG_MOVED_CHANGED << 1; 432 // Ignore this update. 433 // If this is an addition from the new list, it means the item is actually removed from an 434 // earlier position and its move will be dispatched when we process the matching removal 435 // from the old list. 436 // If this is a removal from the old list, it means the item is actually added back to an 437 // earlier index in the new list and we'll dispatch its move when we are processing that 438 // addition. 439 private static final int FLAG_IGNORE = FLAG_MOVED_NOT_CHANGED << 1; 440 441 // since we are re-using the int arrays that were created in the Myers' step, we mask 442 // change flags 443 private static final int FLAG_OFFSET = 5; 444 445 private static final int FLAG_MASK = (1 << FLAG_OFFSET) - 1; 446 447 // The Myers' snakes. At this point, we only care about their diagonal sections. 448 private final List<Snake> mSnakes; 449 450 // The list to keep oldItemStatuses. As we traverse old items, we assign flags to them 451 // which also includes whether they were a real removal or a move (and its new index). 452 private final int[] mOldItemStatuses; 453 // The list to keep newItemStatuses. As we traverse new items, we assign flags to them 454 // which also includes whether they were a real addition or a move(and its old index). 455 private final int[] mNewItemStatuses; 456 // The callback that was given to calcualte diff method. 457 private final Callback mCallback; 458 459 private final int mOldListSize; 460 461 private final int mNewListSize; 462 463 private final boolean mDetectMoves; 464 465 /** 466 * @param callback The callback that was used to calculate the diff 467 * @param snakes The list of Myers' snakes 468 * @param oldItemStatuses An int[] that can be re-purposed to keep metadata 469 * @param newItemStatuses An int[] that can be re-purposed to keep metadata 470 * @param detectMoves True if this DiffResult will try to detect moved items 471 */ 472 DiffResult(Callback callback, List<Snake> snakes, int[] oldItemStatuses, 473 int[] newItemStatuses, boolean detectMoves) { 474 mSnakes = snakes; 475 mOldItemStatuses = oldItemStatuses; 476 mNewItemStatuses = newItemStatuses; 477 Arrays.fill(mOldItemStatuses, 0); 478 Arrays.fill(mNewItemStatuses, 0); 479 mCallback = callback; 480 mOldListSize = callback.getOldListSize(); 481 mNewListSize = callback.getNewListSize(); 482 mDetectMoves = detectMoves; 483 addRootSnake(); 484 findMatchingItems(); 485 } 486 487 /** 488 * We always add a Snake to 0/0 so that we can run loops from end to beginning and be done 489 * when we run out of snakes. 490 */ 491 private void addRootSnake() { 492 Snake firstSnake = mSnakes.isEmpty() ? null : mSnakes.get(0); 493 if (firstSnake == null || firstSnake.x != 0 || firstSnake.y != 0) { 494 Snake root = new Snake(); 495 root.x = 0; 496 root.y = 0; 497 root.removal = false; 498 root.size = 0; 499 root.reverse = false; 500 mSnakes.add(0, root); 501 } 502 } 503 504 /** 505 * This method traverses each addition / removal and tries to match it to a previous 506 * removal / addition. This is how we detect move operations. 507 * <p> 508 * This class also flags whether an item has been changed or not. 509 * <p> 510 * DiffUtil does this pre-processing so that if it is running on a big list, it can be moved 511 * to background thread where most of the expensive stuff will be calculated and kept in 512 * the statuses maps. DiffResult uses this pre-calculated information while dispatching 513 * the updates (which is probably being called on the main thread). 514 */ 515 private void findMatchingItems() { 516 int posOld = mOldListSize; 517 int posNew = mNewListSize; 518 // traverse the matrix from right bottom to 0,0. 519 for (int i = mSnakes.size() - 1; i >= 0; i--) { 520 final Snake snake = mSnakes.get(i); 521 final int endX = snake.x + snake.size; 522 final int endY = snake.y + snake.size; 523 if (mDetectMoves) { 524 while (posOld > endX) { 525 // this is a removal. Check remaining snakes to see if this was added before 526 findAddition(posOld, posNew, i); 527 posOld--; 528 } 529 while (posNew > endY) { 530 // this is an addition. Check remaining snakes to see if this was removed 531 // before 532 findRemoval(posOld, posNew, i); 533 posNew--; 534 } 535 } 536 for (int j = 0; j < snake.size; j++) { 537 // matching items. Check if it is changed or not 538 final int oldItemPos = snake.x + j; 539 final int newItemPos = snake.y + j; 540 final boolean theSame = mCallback 541 .areContentsTheSame(oldItemPos, newItemPos); 542 final int changeFlag = theSame ? FLAG_NOT_CHANGED : FLAG_CHANGED; 543 mOldItemStatuses[oldItemPos] = (newItemPos << FLAG_OFFSET) | changeFlag; 544 mNewItemStatuses[newItemPos] = (oldItemPos << FLAG_OFFSET) | changeFlag; 545 } 546 posOld = snake.x; 547 posNew = snake.y; 548 } 549 } 550 551 private void findAddition(int x, int y, int snakeIndex) { 552 if (mOldItemStatuses[x - 1] != 0) { 553 return; // already set by a latter item 554 } 555 findMatchingItem(x, y, snakeIndex, false); 556 } 557 558 private void findRemoval(int x, int y, int snakeIndex) { 559 if (mNewItemStatuses[y - 1] != 0) { 560 return; // already set by a latter item 561 } 562 findMatchingItem(x, y, snakeIndex, true); 563 } 564 565 /** 566 * Finds a matching item that is before the given coordinates in the matrix 567 * (before : left and above). 568 * 569 * @param x The x position in the matrix (position in the old list) 570 * @param y The y position in the matrix (position in the new list) 571 * @param snakeIndex The current snake index 572 * @param removal True if we are looking for a removal, false otherwise 573 * 574 * @return True if such item is found. 575 */ 576 private boolean findMatchingItem(final int x, final int y, final int snakeIndex, 577 final boolean removal) { 578 final int myItemPos; 579 int curX; 580 int curY; 581 if (removal) { 582 myItemPos = y - 1; 583 curX = x; 584 curY = y - 1; 585 } else { 586 myItemPos = x - 1; 587 curX = x - 1; 588 curY = y; 589 } 590 for (int i = snakeIndex; i >= 0; i--) { 591 final Snake snake = mSnakes.get(i); 592 final int endX = snake.x + snake.size; 593 final int endY = snake.y + snake.size; 594 if (removal) { 595 // check removals for a match 596 for (int pos = curX - 1; pos >= endX; pos--) { 597 if (mCallback.areItemsTheSame(pos, myItemPos)) { 598 // found! 599 final boolean theSame = mCallback.areContentsTheSame(pos, myItemPos); 600 final int changeFlag = theSame ? FLAG_MOVED_NOT_CHANGED 601 : FLAG_MOVED_CHANGED; 602 mNewItemStatuses[myItemPos] = (pos << FLAG_OFFSET) | FLAG_IGNORE; 603 mOldItemStatuses[pos] = (myItemPos << FLAG_OFFSET) | changeFlag; 604 return true; 605 } 606 } 607 } else { 608 // check for additions for a match 609 for (int pos = curY - 1; pos >= endY; pos--) { 610 if (mCallback.areItemsTheSame(myItemPos, pos)) { 611 // found 612 final boolean theSame = mCallback.areContentsTheSame(myItemPos, pos); 613 final int changeFlag = theSame ? FLAG_MOVED_NOT_CHANGED 614 : FLAG_MOVED_CHANGED; 615 mOldItemStatuses[x - 1] = (pos << FLAG_OFFSET) | FLAG_IGNORE; 616 mNewItemStatuses[pos] = ((x - 1) << FLAG_OFFSET) | changeFlag; 617 return true; 618 } 619 } 620 } 621 curX = snake.x; 622 curY = snake.y; 623 } 624 return false; 625 } 626 627 /** 628 * Dispatches the update events to the given adapter. 629 * <p> 630 * For example, if you have an {@link android.support.v7.widget.RecyclerView.Adapter Adapter} 631 * that is backed by a {@link List}, you can swap the list with the new one then call this 632 * method to dispatch all updates to the RecyclerView. 633 * <pre> 634 * List oldList = mAdapter.getData(); 635 * DiffResult result = DiffUtil.calculateDiff(new MyCallback(oldList, newList)); 636 * mAdapter.setData(newList); 637 * result.dispatchUpdatesTo(mAdapter); 638 * </pre> 639 * <p> 640 * Note that the RecyclerView requires you to dispatch adapter updates immediately when you 641 * change the data (you cannot defer {@code notify*} calls). The usage above adheres to this 642 * rule because updates are sent to the adapter right after the backing data is changed, 643 * before RecyclerView tries to read it. 644 * <p> 645 * On the other hand, if you have another 646 * {@link android.support.v7.widget.RecyclerView.AdapterDataObserver AdapterDataObserver} 647 * that tries to process events synchronously, this may confuse that observer because the 648 * list is instantly moved to its final state while the adapter updates are dispatched later 649 * on, one by one. If you have such an 650 * {@link android.support.v7.widget.RecyclerView.AdapterDataObserver AdapterDataObserver}, 651 * you can use 652 * {@link #dispatchUpdatesTo(ListUpdateCallback)} to handle each modification 653 * manually. 654 * 655 * @param adapter A RecyclerView adapter which was displaying the old list and will start 656 * displaying the new list. 657 */ 658 public void dispatchUpdatesTo(final RecyclerView.Adapter adapter) { 659 dispatchUpdatesTo(new ListUpdateCallback() { 660 @Override 661 public void onInserted(int position, int count) { 662 adapter.notifyItemRangeInserted(position, count); 663 } 664 665 @Override 666 public void onRemoved(int position, int count) { 667 adapter.notifyItemRangeRemoved(position, count); 668 } 669 670 @Override 671 public void onMoved(int fromPosition, int toPosition) { 672 adapter.notifyItemMoved(fromPosition, toPosition); 673 } 674 675 @Override 676 public void onChanged(int position, int count, Object payload) { 677 adapter.notifyItemRangeChanged(position, count, payload); 678 } 679 }); 680 } 681 682 /** 683 * Dispatches update operations to the given Callback. 684 * <p> 685 * These updates are atomic such that the first update call effects every update call that 686 * comes after it (the same as RecyclerView). 687 * 688 * @param updateCallback The callback to receive the update operations. 689 * @see #dispatchUpdatesTo(RecyclerView.Adapter) 690 */ 691 public void dispatchUpdatesTo(ListUpdateCallback updateCallback) { 692 final BatchingListUpdateCallback batchingCallback; 693 if (updateCallback instanceof BatchingListUpdateCallback) { 694 batchingCallback = (BatchingListUpdateCallback) updateCallback; 695 } else { 696 batchingCallback = new BatchingListUpdateCallback(updateCallback); 697 // replace updateCallback with a batching callback and override references to 698 // updateCallback so that we don't call it directly by mistake 699 //noinspection UnusedAssignment 700 updateCallback = batchingCallback; 701 } 702 // These are add/remove ops that are converted to moves. We track their positions until 703 // their respective update operations are processed. 704 final List<PostponedUpdate> postponedUpdates = new ArrayList<>(); 705 int posOld = mOldListSize; 706 int posNew = mNewListSize; 707 for (int snakeIndex = mSnakes.size() - 1; snakeIndex >= 0; snakeIndex--) { 708 final Snake snake = mSnakes.get(snakeIndex); 709 final int snakeSize = snake.size; 710 final int endX = snake.x + snakeSize; 711 final int endY = snake.y + snakeSize; 712 if (endX < posOld) { 713 dispatchRemovals(postponedUpdates, batchingCallback, endX, posOld - endX, endX); 714 } 715 716 if (endY < posNew) { 717 dispatchAdditions(postponedUpdates, batchingCallback, endX, posNew - endY, 718 endY); 719 } 720 for (int i = snakeSize - 1; i >= 0; i--) { 721 if ((mOldItemStatuses[snake.x + i] & FLAG_MASK) == FLAG_CHANGED) { 722 batchingCallback.onChanged(snake.x + i, 1, 723 mCallback.getChangePayload(snake.x + i, snake.y + i)); 724 } 725 } 726 posOld = snake.x; 727 posNew = snake.y; 728 } 729 batchingCallback.dispatchLastEvent(); 730 } 731 732 private static PostponedUpdate removePostponedUpdate(List<PostponedUpdate> updates, 733 int pos, boolean removal) { 734 for (int i = updates.size() - 1; i >= 0; i--) { 735 final PostponedUpdate update = updates.get(i); 736 if (update.posInOwnerList == pos && update.removal == removal) { 737 updates.remove(i); 738 for (int j = i; j < updates.size(); j++) { 739 // offset other ops since they swapped positions 740 updates.get(j).currentPos += removal ? 1 : -1; 741 } 742 return update; 743 } 744 } 745 return null; 746 } 747 748 private void dispatchAdditions(List<PostponedUpdate> postponedUpdates, 749 ListUpdateCallback updateCallback, int start, int count, int globalIndex) { 750 if (!mDetectMoves) { 751 updateCallback.onInserted(start, count); 752 return; 753 } 754 for (int i = count - 1; i >= 0; i--) { 755 int status = mNewItemStatuses[globalIndex + i] & FLAG_MASK; 756 switch (status) { 757 case 0: // real addition 758 updateCallback.onInserted(start, 1); 759 for (PostponedUpdate update : postponedUpdates) { 760 update.currentPos += 1; 761 } 762 break; 763 case FLAG_MOVED_CHANGED: 764 case FLAG_MOVED_NOT_CHANGED: 765 final int pos = mNewItemStatuses[globalIndex + i] >> FLAG_OFFSET; 766 final PostponedUpdate update = removePostponedUpdate(postponedUpdates, pos, 767 true); 768 // the item was moved from that position 769 //noinspection ConstantConditions 770 updateCallback.onMoved(update.currentPos, start); 771 if (status == FLAG_MOVED_CHANGED) { 772 // also dispatch a change 773 updateCallback.onChanged(start, 1, 774 mCallback.getChangePayload(pos, globalIndex + i)); 775 } 776 break; 777 case FLAG_IGNORE: // ignoring this 778 postponedUpdates.add(new PostponedUpdate(globalIndex + i, start, false)); 779 break; 780 default: 781 throw new IllegalStateException( 782 "unknown flag for pos " + (globalIndex + i) + " " + Long 783 .toBinaryString(status)); 784 } 785 } 786 } 787 788 private void dispatchRemovals(List<PostponedUpdate> postponedUpdates, 789 ListUpdateCallback updateCallback, int start, int count, int globalIndex) { 790 if (!mDetectMoves) { 791 updateCallback.onRemoved(start, count); 792 return; 793 } 794 for (int i = count - 1; i >= 0; i--) { 795 final int status = mOldItemStatuses[globalIndex + i] & FLAG_MASK; 796 switch (status) { 797 case 0: // real removal 798 updateCallback.onRemoved(start + i, 1); 799 for (PostponedUpdate update : postponedUpdates) { 800 update.currentPos -= 1; 801 } 802 break; 803 case FLAG_MOVED_CHANGED: 804 case FLAG_MOVED_NOT_CHANGED: 805 final int pos = mOldItemStatuses[globalIndex + i] >> FLAG_OFFSET; 806 final PostponedUpdate update = removePostponedUpdate(postponedUpdates, pos, 807 false); 808 // the item was moved to that position. we do -1 because this is a move not 809 // add and removing current item offsets the target move by 1 810 //noinspection ConstantConditions 811 updateCallback.onMoved(start + i, update.currentPos - 1); 812 if (status == FLAG_MOVED_CHANGED) { 813 // also dispatch a change 814 updateCallback.onChanged(update.currentPos - 1, 1, 815 mCallback.getChangePayload(globalIndex + i, pos)); 816 } 817 break; 818 case FLAG_IGNORE: // ignoring this 819 postponedUpdates.add(new PostponedUpdate(globalIndex + i, start + i, true)); 820 break; 821 default: 822 throw new IllegalStateException( 823 "unknown flag for pos " + (globalIndex + i) + " " + Long 824 .toBinaryString(status)); 825 } 826 } 827 } 828 829 @VisibleForTesting 830 List<Snake> getSnakes() { 831 return mSnakes; 832 } 833 } 834 835 /** 836 * Represents an update that we skipped because it was a move. 837 * <p> 838 * When an update is skipped, it is tracked as other updates are dispatched until the matching 839 * add/remove operation is found at which point the tracked position is used to dispatch the 840 * update. 841 */ 842 private static class PostponedUpdate { 843 844 int posInOwnerList; 845 846 int currentPos; 847 848 boolean removal; 849 850 public PostponedUpdate(int posInOwnerList, int currentPos, boolean removal) { 851 this.posInOwnerList = posInOwnerList; 852 this.currentPos = currentPos; 853 this.removal = removal; 854 } 855 } 856} 857