/* * Copyright (C) 2016 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package android.support.v7.util; import android.support.annotation.Nullable; import android.support.annotation.VisibleForTesting; import android.support.v7.widget.RecyclerView; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * DiffUtil is a utility class that can calculate the difference between two lists and output a * list of update operations that converts the first list into the second one. *

* It can be used to calculate updates for a RecyclerView Adapter. *

* DiffUtil uses Eugene W. Myers's difference algorithm to calculate the minimal number of updates * to convert one list into another. Myers's algorithm does not handle items that are moved so * DiffUtil runs a second pass on the result to detect items that were moved. *

* If the lists are large, this operation may take significant time so you are advised to run this * on a background thread, get the {@link DiffResult} then apply it on the RecyclerView on the main * thread. *

* This algorithm is optimized for space and uses O(N) space to find the minimal * number of addition and removal operations between the two lists. It has O(N + D^2) expected time * performance where D is the length of the edit script. *

* If move detection is enabled, it takes an additional O(N^2) time where N is the total number of * added and removed items. If your lists are already sorted by the same constraint (e.g. a created * timestamp for a list of posts), you can disable move detection to improve performance. *

* The actual runtime of the algorithm significantly depends on the number of changes in the list * and the cost of your comparison methods. Below are some average run times for reference: * (The test list is composed of random UUID Strings and the tests are run on Nexus 5X with M) *

*

* Due to implementation constraints, the max size of the list can be 2^26. */ public class DiffUtil { private DiffUtil() { // utility class, no instance. } private static final Comparator SNAKE_COMPARATOR = new Comparator() { @Override public int compare(Snake o1, Snake o2) { int cmpX = o1.x - o2.x; return cmpX == 0 ? o1.y - o2.y : cmpX; } }; // Myers' algorithm uses two lists as axis labels. In DiffUtil's implementation, `x` axis is // used for old list and `y` axis is used for new list. /** * Calculates the list of update operations that can covert one list into the other one. * * @param cb The callback that acts as a gateway to the backing list data * * @return A DiffResult that contains the information about the edit sequence to convert the * old list into the new list. */ public static DiffResult calculateDiff(Callback cb) { return calculateDiff(cb, true); } /** * Calculates the list of update operations that can covert one list into the other one. *

* If your old and new lists are sorted by the same constraint and items never move (swap * positions), you can disable move detection which takes O(N^2) time where * N is the number of added, moved, removed items. * * @param cb The callback that acts as a gateway to the backing list data * @param detectMoves True if DiffUtil should try to detect moved items, false otherwise. * * @return A DiffResult that contains the information about the edit sequence to convert the * old list into the new list. */ public static DiffResult calculateDiff(Callback cb, boolean detectMoves) { final int oldSize = cb.getOldListSize(); final int newSize = cb.getNewListSize(); final List snakes = new ArrayList<>(); // instead of a recursive implementation, we keep our own stack to avoid potential stack // overflow exceptions final List stack = new ArrayList<>(); stack.add(new Range(0, oldSize, 0, newSize)); final int max = oldSize + newSize + Math.abs(oldSize - newSize); // allocate forward and backward k-lines. K lines are diagonal lines in the matrix. (see the // paper for details) // These arrays lines keep the max reachable position for each k-line. final int[] forward = new int[max * 2]; final int[] backward = new int[max * 2]; // We pool the ranges to avoid allocations for each recursive call. final List rangePool = new ArrayList<>(); while (!stack.isEmpty()) { final Range range = stack.remove(stack.size() - 1); final Snake snake = diffPartial(cb, range.oldListStart, range.oldListEnd, range.newListStart, range.newListEnd, forward, backward, max); if (snake != null) { if (snake.size > 0) { snakes.add(snake); } // offset the snake to convert its coordinates from the Range's area to global snake.x += range.oldListStart; snake.y += range.newListStart; // add new ranges for left and right final Range left = rangePool.isEmpty() ? new Range() : rangePool.remove( rangePool.size() - 1); left.oldListStart = range.oldListStart; left.newListStart = range.newListStart; if (snake.reverse) { left.oldListEnd = snake.x; left.newListEnd = snake.y; } else { if (snake.removal) { left.oldListEnd = snake.x - 1; left.newListEnd = snake.y; } else { left.oldListEnd = snake.x; left.newListEnd = snake.y - 1; } } stack.add(left); // re-use range for right //noinspection UnnecessaryLocalVariable final Range right = range; if (snake.reverse) { if (snake.removal) { right.oldListStart = snake.x + snake.size + 1; right.newListStart = snake.y + snake.size; } else { right.oldListStart = snake.x + snake.size; right.newListStart = snake.y + snake.size + 1; } } else { right.oldListStart = snake.x + snake.size; right.newListStart = snake.y + snake.size; } stack.add(right); } else { rangePool.add(range); } } // sort snakes Collections.sort(snakes, SNAKE_COMPARATOR); return new DiffResult(cb, snakes, forward, backward, detectMoves); } private static Snake diffPartial(Callback cb, int startOld, int endOld, int startNew, int endNew, int[] forward, int[] backward, int kOffset) { final int oldSize = endOld - startOld; final int newSize = endNew - startNew; if (endOld - startOld < 1 || endNew - startNew < 1) { return null; } final int delta = oldSize - newSize; final int dLimit = (oldSize + newSize + 1) / 2; Arrays.fill(forward, kOffset - dLimit - 1, kOffset + dLimit + 1, 0); Arrays.fill(backward, kOffset - dLimit - 1 + delta, kOffset + dLimit + 1 + delta, oldSize); final boolean checkInFwd = delta % 2 != 0; for (int d = 0; d <= dLimit; d++) { for (int k = -d; k <= d; k += 2) { // find forward path // we can reach k from k - 1 or k + 1. Check which one is further in the graph int x; final boolean removal; if (k == -d || k != d && forward[kOffset + k - 1] < forward[kOffset + k + 1]) { x = forward[kOffset + k + 1]; removal = false; } else { x = forward[kOffset + k - 1] + 1; removal = true; } // set y based on x int y = x - k; // move diagonal as long as items match while (x < oldSize && y < newSize && cb.areItemsTheSame(startOld + x, startNew + y)) { x++; y++; } forward[kOffset + k] = x; if (checkInFwd && k >= delta - d + 1 && k <= delta + d - 1) { if (forward[kOffset + k] >= backward[kOffset + k]) { Snake outSnake = new Snake(); outSnake.x = backward[kOffset + k]; outSnake.y = outSnake.x - k; outSnake.size = forward[kOffset + k] - backward[kOffset + k]; outSnake.removal = removal; outSnake.reverse = false; return outSnake; } } } for (int k = -d; k <= d; k += 2) { // find reverse path at k + delta, in reverse final int backwardK = k + delta; int x; final boolean removal; if (backwardK == d + delta || backwardK != -d + delta && backward[kOffset + backwardK - 1] < backward[kOffset + backwardK + 1]) { x = backward[kOffset + backwardK - 1]; removal = false; } else { x = backward[kOffset + backwardK + 1] - 1; removal = true; } // set y based on x int y = x - backwardK; // move diagonal as long as items match while (x > 0 && y > 0 && cb.areItemsTheSame(startOld + x - 1, startNew + y - 1)) { x--; y--; } backward[kOffset + backwardK] = x; if (!checkInFwd && k + delta >= -d && k + delta <= d) { if (forward[kOffset + backwardK] >= backward[kOffset + backwardK]) { Snake outSnake = new Snake(); outSnake.x = backward[kOffset + backwardK]; outSnake.y = outSnake.x - backwardK; outSnake.size = forward[kOffset + backwardK] - backward[kOffset + backwardK]; outSnake.removal = removal; outSnake.reverse = true; return outSnake; } } } } throw new IllegalStateException("DiffUtil hit an unexpected case while trying to calculate" + " the optimal path. Please make sure your data is not changing during the" + " diff calculation."); } /** * A Callback class used by DiffUtil while calculating the diff between two lists. */ public abstract static class Callback { /** * Returns the size of the old list. * * @return The size of the old list. */ public abstract int getOldListSize(); /** * Returns the size of the new list. * * @return The size of the new list. */ public abstract int getNewListSize(); /** * Called by the DiffUtil to decide whether two object represent the same Item. *

* For example, if your items have unique ids, this method should check their id equality. * * @param oldItemPosition The position of the item in the old list * @param newItemPosition The position of the item in the new list * @return True if the two items represent the same object or false if they are different. */ public abstract boolean areItemsTheSame(int oldItemPosition, int newItemPosition); /** * Called by the DiffUtil when it wants to check whether two items have the same data. * DiffUtil uses this information to detect if the contents of an item has changed. *

* DiffUtil uses this method to check equality instead of {@link Object#equals(Object)} * so that you can change its behavior depending on your UI. * For example, if you are using DiffUtil with a * {@link android.support.v7.widget.RecyclerView.Adapter RecyclerView.Adapter}, you should * return whether the items' visual representations are the same. *

* This method is called only if {@link #areItemsTheSame(int, int)} returns * {@code true} for these items. * * @param oldItemPosition The position of the item in the old list * @param newItemPosition The position of the item in the new list which replaces the * oldItem * @return True if the contents of the items are the same or false if they are different. */ public abstract boolean areContentsTheSame(int oldItemPosition, int newItemPosition); /** * When {@link #areItemsTheSame(int, int)} returns {@code true} for two items and * {@link #areContentsTheSame(int, int)} returns false for them, DiffUtil * calls this method to get a payload about the change. *

* For example, if you are using DiffUtil with {@link RecyclerView}, you can return the * particular field that changed in the item and your * {@link android.support.v7.widget.RecyclerView.ItemAnimator ItemAnimator} can use that * information to run the correct animation. *

* Default implementation returns {@code null}. * * @param oldItemPosition The position of the item in the old list * @param newItemPosition The position of the item in the new list * * @return A payload object that represents the change between the two items. */ @Nullable public Object getChangePayload(int oldItemPosition, int newItemPosition) { return null; } } /** * Snakes represent a match between two lists. It is optionally prefixed or postfixed with an * add or remove operation. See the Myers' paper for details. */ static class Snake { /** * Position in the old list */ int x; /** * Position in the new list */ int y; /** * Number of matches. Might be 0. */ int size; /** * If true, this is a removal from the original list followed by {@code size} matches. * If false, this is an addition from the new list followed by {@code size} matches. */ boolean removal; /** * If true, the addition or removal is at the end of the snake. * If false, the addition or removal is at the beginning of the snake. */ boolean reverse; } /** * Represents a range in two lists that needs to be solved. *

* This internal class is used when running Myers' algorithm without recursion. */ static class Range { int oldListStart, oldListEnd; int newListStart, newListEnd; public Range() { } public Range(int oldListStart, int oldListEnd, int newListStart, int newListEnd) { this.oldListStart = oldListStart; this.oldListEnd = oldListEnd; this.newListStart = newListStart; this.newListEnd = newListEnd; } } /** * This class holds the information about the result of a * {@link DiffUtil#calculateDiff(Callback, boolean)} call. *

* You can consume the updates in a DiffResult via * {@link #dispatchUpdatesTo(ListUpdateCallback)} or directly stream the results into a * {@link RecyclerView.Adapter} via {@link #dispatchUpdatesTo(RecyclerView.Adapter)}. */ public static class DiffResult { /** * While reading the flags below, keep in mind that when multiple items move in a list, * Myers's may pick any of them as the anchor item and consider that one NOT_CHANGED while * picking others as additions and removals. This is completely fine as we later detect * all moves. *

* Below, when an item is mentioned to stay in the same "location", it means we won't * dispatch a move/add/remove for it, it DOES NOT mean the item is still in the same * position. */ // item stayed the same. private static final int FLAG_NOT_CHANGED = 1; // item stayed in the same location but changed. private static final int FLAG_CHANGED = FLAG_NOT_CHANGED << 1; // Item has moved and also changed. private static final int FLAG_MOVED_CHANGED = FLAG_CHANGED << 1; // Item has moved but did not change. private static final int FLAG_MOVED_NOT_CHANGED = FLAG_MOVED_CHANGED << 1; // Ignore this update. // If this is an addition from the new list, it means the item is actually removed from an // earlier position and its move will be dispatched when we process the matching removal // from the old list. // If this is a removal from the old list, it means the item is actually added back to an // earlier index in the new list and we'll dispatch its move when we are processing that // addition. private static final int FLAG_IGNORE = FLAG_MOVED_NOT_CHANGED << 1; // since we are re-using the int arrays that were created in the Myers' step, we mask // change flags private static final int FLAG_OFFSET = 5; private static final int FLAG_MASK = (1 << FLAG_OFFSET) - 1; // The Myers' snakes. At this point, we only care about their diagonal sections. private final List mSnakes; // The list to keep oldItemStatuses. As we traverse old items, we assign flags to them // which also includes whether they were a real removal or a move (and its new index). private final int[] mOldItemStatuses; // The list to keep newItemStatuses. As we traverse new items, we assign flags to them // which also includes whether they were a real addition or a move(and its old index). private final int[] mNewItemStatuses; // The callback that was given to calcualte diff method. private final Callback mCallback; private final int mOldListSize; private final int mNewListSize; private final boolean mDetectMoves; /** * @param callback The callback that was used to calculate the diff * @param snakes The list of Myers' snakes * @param oldItemStatuses An int[] that can be re-purposed to keep metadata * @param newItemStatuses An int[] that can be re-purposed to keep metadata * @param detectMoves True if this DiffResult will try to detect moved items */ DiffResult(Callback callback, List snakes, int[] oldItemStatuses, int[] newItemStatuses, boolean detectMoves) { mSnakes = snakes; mOldItemStatuses = oldItemStatuses; mNewItemStatuses = newItemStatuses; Arrays.fill(mOldItemStatuses, 0); Arrays.fill(mNewItemStatuses, 0); mCallback = callback; mOldListSize = callback.getOldListSize(); mNewListSize = callback.getNewListSize(); mDetectMoves = detectMoves; addRootSnake(); findMatchingItems(); } /** * We always add a Snake to 0/0 so that we can run loops from end to beginning and be done * when we run out of snakes. */ private void addRootSnake() { Snake firstSnake = mSnakes.isEmpty() ? null : mSnakes.get(0); if (firstSnake == null || firstSnake.x != 0 || firstSnake.y != 0) { Snake root = new Snake(); root.x = 0; root.y = 0; root.removal = false; root.size = 0; root.reverse = false; mSnakes.add(0, root); } } /** * This method traverses each addition / removal and tries to match it to a previous * removal / addition. This is how we detect move operations. *

* This class also flags whether an item has been changed or not. *

* DiffUtil does this pre-processing so that if it is running on a big list, it can be moved * to background thread where most of the expensive stuff will be calculated and kept in * the statuses maps. DiffResult uses this pre-calculated information while dispatching * the updates (which is probably being called on the main thread). */ private void findMatchingItems() { int posOld = mOldListSize; int posNew = mNewListSize; // traverse the matrix from right bottom to 0,0. for (int i = mSnakes.size() - 1; i >= 0; i--) { final Snake snake = mSnakes.get(i); final int endX = snake.x + snake.size; final int endY = snake.y + snake.size; if (mDetectMoves) { while (posOld > endX) { // this is a removal. Check remaining snakes to see if this was added before findAddition(posOld, posNew, i); posOld--; } while (posNew > endY) { // this is an addition. Check remaining snakes to see if this was removed // before findRemoval(posOld, posNew, i); posNew--; } } for (int j = 0; j < snake.size; j++) { // matching items. Check if it is changed or not final int oldItemPos = snake.x + j; final int newItemPos = snake.y + j; final boolean theSame = mCallback .areContentsTheSame(oldItemPos, newItemPos); final int changeFlag = theSame ? FLAG_NOT_CHANGED : FLAG_CHANGED; mOldItemStatuses[oldItemPos] = (newItemPos << FLAG_OFFSET) | changeFlag; mNewItemStatuses[newItemPos] = (oldItemPos << FLAG_OFFSET) | changeFlag; } posOld = snake.x; posNew = snake.y; } } private void findAddition(int x, int y, int snakeIndex) { if (mOldItemStatuses[x - 1] != 0) { return; // already set by a latter item } findMatchingItem(x, y, snakeIndex, false); } private void findRemoval(int x, int y, int snakeIndex) { if (mNewItemStatuses[y - 1] != 0) { return; // already set by a latter item } findMatchingItem(x, y, snakeIndex, true); } /** * Finds a matching item that is before the given coordinates in the matrix * (before : left and above). * * @param x The x position in the matrix (position in the old list) * @param y The y position in the matrix (position in the new list) * @param snakeIndex The current snake index * @param removal True if we are looking for a removal, false otherwise * * @return True if such item is found. */ private boolean findMatchingItem(final int x, final int y, final int snakeIndex, final boolean removal) { final int myItemPos; int curX; int curY; if (removal) { myItemPos = y - 1; curX = x; curY = y - 1; } else { myItemPos = x - 1; curX = x - 1; curY = y; } for (int i = snakeIndex; i >= 0; i--) { final Snake snake = mSnakes.get(i); final int endX = snake.x + snake.size; final int endY = snake.y + snake.size; if (removal) { // check removals for a match for (int pos = curX - 1; pos >= endX; pos--) { if (mCallback.areItemsTheSame(pos, myItemPos)) { // found! final boolean theSame = mCallback.areContentsTheSame(pos, myItemPos); final int changeFlag = theSame ? FLAG_MOVED_NOT_CHANGED : FLAG_MOVED_CHANGED; mNewItemStatuses[myItemPos] = (pos << FLAG_OFFSET) | FLAG_IGNORE; mOldItemStatuses[pos] = (myItemPos << FLAG_OFFSET) | changeFlag; return true; } } } else { // check for additions for a match for (int pos = curY - 1; pos >= endY; pos--) { if (mCallback.areItemsTheSame(myItemPos, pos)) { // found final boolean theSame = mCallback.areContentsTheSame(myItemPos, pos); final int changeFlag = theSame ? FLAG_MOVED_NOT_CHANGED : FLAG_MOVED_CHANGED; mOldItemStatuses[x - 1] = (pos << FLAG_OFFSET) | FLAG_IGNORE; mNewItemStatuses[pos] = ((x - 1) << FLAG_OFFSET) | changeFlag; return true; } } } curX = snake.x; curY = snake.y; } return false; } /** * Dispatches the update events to the given adapter. *

* For example, if you have an {@link android.support.v7.widget.RecyclerView.Adapter Adapter} * that is backed by a {@link List}, you can swap the list with the new one then call this * method to dispatch all updates to the RecyclerView. *

         *     List oldList = mAdapter.getData();
         *     DiffResult result = DiffUtil.calculateDiff(new MyCallback(oldList, newList));
         *     mAdapter.setData(newList);
         *     result.dispatchUpdatesTo(mAdapter);
         * 
*

* Note that the RecyclerView requires you to dispatch adapter updates immediately when you * change the data (you cannot defer {@code notify*} calls). The usage above adheres to this * rule because updates are sent to the adapter right after the backing data is changed, * before RecyclerView tries to read it. *

* On the other hand, if you have another * {@link android.support.v7.widget.RecyclerView.AdapterDataObserver AdapterDataObserver} * that tries to process events synchronously, this may confuse that observer because the * list is instantly moved to its final state while the adapter updates are dispatched later * on, one by one. If you have such an * {@link android.support.v7.widget.RecyclerView.AdapterDataObserver AdapterDataObserver}, * you can use * {@link #dispatchUpdatesTo(ListUpdateCallback)} to handle each modification * manually. * * @param adapter A RecyclerView adapter which was displaying the old list and will start * displaying the new list. */ public void dispatchUpdatesTo(final RecyclerView.Adapter adapter) { dispatchUpdatesTo(new ListUpdateCallback() { @Override public void onInserted(int position, int count) { adapter.notifyItemRangeInserted(position, count); } @Override public void onRemoved(int position, int count) { adapter.notifyItemRangeRemoved(position, count); } @Override public void onMoved(int fromPosition, int toPosition) { adapter.notifyItemMoved(fromPosition, toPosition); } @Override public void onChanged(int position, int count, Object payload) { adapter.notifyItemRangeChanged(position, count, payload); } }); } /** * Dispatches update operations to the given Callback. *

* These updates are atomic such that the first update call effects every update call that * comes after it (the same as RecyclerView). * * @param updateCallback The callback to receive the update operations. * @see #dispatchUpdatesTo(RecyclerView.Adapter) */ public void dispatchUpdatesTo(ListUpdateCallback updateCallback) { final BatchingListUpdateCallback batchingCallback; if (updateCallback instanceof BatchingListUpdateCallback) { batchingCallback = (BatchingListUpdateCallback) updateCallback; } else { batchingCallback = new BatchingListUpdateCallback(updateCallback); // replace updateCallback with a batching callback and override references to // updateCallback so that we don't call it directly by mistake //noinspection UnusedAssignment updateCallback = batchingCallback; } // These are add/remove ops that are converted to moves. We track their positions until // their respective update operations are processed. final List postponedUpdates = new ArrayList<>(); int posOld = mOldListSize; int posNew = mNewListSize; for (int snakeIndex = mSnakes.size() - 1; snakeIndex >= 0; snakeIndex--) { final Snake snake = mSnakes.get(snakeIndex); final int snakeSize = snake.size; final int endX = snake.x + snakeSize; final int endY = snake.y + snakeSize; if (endX < posOld) { dispatchRemovals(postponedUpdates, batchingCallback, endX, posOld - endX, endX); } if (endY < posNew) { dispatchAdditions(postponedUpdates, batchingCallback, endX, posNew - endY, endY); } for (int i = snakeSize - 1; i >= 0; i--) { if ((mOldItemStatuses[snake.x + i] & FLAG_MASK) == FLAG_CHANGED) { batchingCallback.onChanged(snake.x + i, 1, mCallback.getChangePayload(snake.x + i, snake.y + i)); } } posOld = snake.x; posNew = snake.y; } batchingCallback.dispatchLastEvent(); } private static PostponedUpdate removePostponedUpdate(List updates, int pos, boolean removal) { for (int i = updates.size() - 1; i >= 0; i--) { final PostponedUpdate update = updates.get(i); if (update.posInOwnerList == pos && update.removal == removal) { updates.remove(i); for (int j = i; j < updates.size(); j++) { // offset other ops since they swapped positions updates.get(j).currentPos += removal ? 1 : -1; } return update; } } return null; } private void dispatchAdditions(List postponedUpdates, ListUpdateCallback updateCallback, int start, int count, int globalIndex) { if (!mDetectMoves) { updateCallback.onInserted(start, count); return; } for (int i = count - 1; i >= 0; i--) { int status = mNewItemStatuses[globalIndex + i] & FLAG_MASK; switch (status) { case 0: // real addition updateCallback.onInserted(start, 1); for (PostponedUpdate update : postponedUpdates) { update.currentPos += 1; } break; case FLAG_MOVED_CHANGED: case FLAG_MOVED_NOT_CHANGED: final int pos = mNewItemStatuses[globalIndex + i] >> FLAG_OFFSET; final PostponedUpdate update = removePostponedUpdate(postponedUpdates, pos, true); // the item was moved from that position //noinspection ConstantConditions updateCallback.onMoved(update.currentPos, start); if (status == FLAG_MOVED_CHANGED) { // also dispatch a change updateCallback.onChanged(start, 1, mCallback.getChangePayload(pos, globalIndex + i)); } break; case FLAG_IGNORE: // ignoring this postponedUpdates.add(new PostponedUpdate(globalIndex + i, start, false)); break; default: throw new IllegalStateException( "unknown flag for pos " + (globalIndex + i) + " " + Long .toBinaryString(status)); } } } private void dispatchRemovals(List postponedUpdates, ListUpdateCallback updateCallback, int start, int count, int globalIndex) { if (!mDetectMoves) { updateCallback.onRemoved(start, count); return; } for (int i = count - 1; i >= 0; i--) { final int status = mOldItemStatuses[globalIndex + i] & FLAG_MASK; switch (status) { case 0: // real removal updateCallback.onRemoved(start + i, 1); for (PostponedUpdate update : postponedUpdates) { update.currentPos -= 1; } break; case FLAG_MOVED_CHANGED: case FLAG_MOVED_NOT_CHANGED: final int pos = mOldItemStatuses[globalIndex + i] >> FLAG_OFFSET; final PostponedUpdate update = removePostponedUpdate(postponedUpdates, pos, false); // the item was moved to that position. we do -1 because this is a move not // add and removing current item offsets the target move by 1 //noinspection ConstantConditions updateCallback.onMoved(start + i, update.currentPos - 1); if (status == FLAG_MOVED_CHANGED) { // also dispatch a change updateCallback.onChanged(update.currentPos - 1, 1, mCallback.getChangePayload(globalIndex + i, pos)); } break; case FLAG_IGNORE: // ignoring this postponedUpdates.add(new PostponedUpdate(globalIndex + i, start + i, true)); break; default: throw new IllegalStateException( "unknown flag for pos " + (globalIndex + i) + " " + Long .toBinaryString(status)); } } } @VisibleForTesting List getSnakes() { return mSnakes; } } /** * Represents an update that we skipped because it was a move. *

* When an update is skipped, it is tracked as other updates are dispatched until the matching * add/remove operation is found at which point the tracked position is used to dispatch the * update. */ private static class PostponedUpdate { int posInOwnerList; int currentPos; boolean removal; public PostponedUpdate(int posInOwnerList, int currentPos, boolean removal) { this.posInOwnerList = posInOwnerList; this.currentPos = currentPos; this.removal = removal; } } }