| /* |
| * Copyright 2018 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 androidx.recyclerview.widget; |
| |
| import androidx.annotation.IntRange; |
| import androidx.annotation.NonNull; |
| import androidx.annotation.Nullable; |
| |
| import java.util.ArrayDeque; |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.List; |
| |
| /** |
| * DiffUtil is a utility class that calculates the difference between two lists and outputs a |
| * list of update operations that converts the first list into the second one. |
| * <p> |
| * It can be used to calculate updates for a RecyclerView Adapter. See {@link ListAdapter} and |
| * {@link AsyncListDiffer} which can simplify the use of DiffUtil on a background thread. |
| * <p> |
| * 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. |
| * <p> |
| * Note that DiffUtil, {@link ListAdapter}, and {@link AsyncListDiffer} require the list to not |
| * mutate while in use. |
| * This generally means that both the lists themselves and their elements (or at least, the |
| * properties of elements used in diffing) should not be modified directly. Instead, new lists |
| * should be provided any time content changes. It's common for lists passed to DiffUtil to share |
| * elements that have not mutated, so it is not strictly required to reload all data to use |
| * DiffUtil. |
| * <p> |
| * 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. |
| * <p> |
| * 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. |
| * <p> |
| * If move detection is enabled, it takes an additional O(MN) time where M is the total number of |
| * added items and N is the total number of 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. |
| * <p> |
| * 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) |
| * <ul> |
| * <li>100 items and 10 modifications: avg: 0.39 ms, median: 0.35 ms |
| * <li>100 items and 100 modifications: 3.82 ms, median: 3.75 ms |
| * <li>100 items and 100 modifications without moves: 2.09 ms, median: 2.06 ms |
| * <li>1000 items and 50 modifications: avg: 4.67 ms, median: 4.59 ms |
| * <li>1000 items and 50 modifications without moves: avg: 3.59 ms, median: 3.50 ms |
| * <li>1000 items and 200 modifications: 27.07 ms, median: 26.92 ms |
| * <li>1000 items and 200 modifications without moves: 13.54 ms, median: 13.36 ms |
| * </ul> |
| * <p> |
| * Due to implementation constraints, the max size of the list can be 2^26. |
| * |
| * @see ListAdapter |
| * @see AsyncListDiffer |
| */ |
| public class DiffUtil { |
| private DiffUtil() { |
| // utility class, no instance. |
| } |
| |
| private static final Comparator<Diagonal> DIAGONAL_COMPARATOR = new Comparator<Diagonal>() { |
| @Override |
| public int compare(Diagonal o1, Diagonal o2) { |
| return o1.x - o2.x; |
| } |
| }; |
| |
| // 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. |
| */ |
| @NonNull |
| public static DiffResult calculateDiff(@NonNull Callback cb) { |
| return calculateDiff(cb, true); |
| } |
| |
| /** |
| * Calculates the list of update operations that can covert one list into the other one. |
| * <p> |
| * 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 <code>O(N^2)</code> 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. |
| */ |
| @NonNull |
| public static DiffResult calculateDiff(@NonNull Callback cb, boolean detectMoves) { |
| final int oldSize = cb.getOldListSize(); |
| final int newSize = cb.getNewListSize(); |
| |
| final List<Diagonal> diagonals = new ArrayList<>(); |
| |
| // instead of a recursive implementation, we keep our own stack to avoid potential stack |
| // overflow exceptions |
| final List<Range> stack = new ArrayList<>(); |
| |
| stack.add(new Range(0, oldSize, 0, newSize)); |
| |
| final int max = (oldSize + newSize + 1) / 2; |
| // 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 CenteredArray forward = new CenteredArray(max * 2 + 1); |
| final CenteredArray backward = new CenteredArray(max * 2 + 1); |
| |
| // We pool the ranges to avoid allocations for each recursive call. |
| final List<Range> rangePool = new ArrayList<>(); |
| while (!stack.isEmpty()) { |
| final Range range = stack.remove(stack.size() - 1); |
| final Snake snake = midPoint(range, cb, forward, backward); |
| if (snake != null) { |
| // if it has a diagonal, save it |
| if (snake.diagonalSize() > 0) { |
| diagonals.add(snake.toDiagonal()); |
| } |
| // 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; |
| left.oldListEnd = snake.startX; |
| left.newListEnd = snake.startY; |
| stack.add(left); |
| |
| // re-use range for right |
| //noinspection UnnecessaryLocalVariable |
| final Range right = range; |
| right.oldListEnd = range.oldListEnd; |
| right.newListEnd = range.newListEnd; |
| right.oldListStart = snake.endX; |
| right.newListStart = snake.endY; |
| stack.add(right); |
| } else { |
| rangePool.add(range); |
| } |
| |
| } |
| // sort snakes |
| Collections.sort(diagonals, DIAGONAL_COMPARATOR); |
| |
| return new DiffResult(cb, diagonals, |
| forward.backingData(), backward.backingData(), |
| detectMoves); |
| } |
| |
| /** |
| * Finds a middle snake in the given range. |
| */ |
| @Nullable |
| private static Snake midPoint( |
| Range range, |
| Callback cb, |
| CenteredArray forward, |
| CenteredArray backward) { |
| if (range.oldSize() < 1 || range.newSize() < 1) { |
| return null; |
| } |
| int max = (range.oldSize() + range.newSize() + 1) / 2; |
| forward.set(1, range.oldListStart); |
| backward.set(1, range.oldListEnd); |
| for (int d = 0; d < max; d++) { |
| Snake snake = forward(range, cb, forward, backward, d); |
| if (snake != null) { |
| return snake; |
| } |
| snake = backward(range, cb, forward, backward, d); |
| if (snake != null) { |
| return snake; |
| } |
| } |
| return null; |
| } |
| |
| @Nullable |
| private static Snake forward( |
| Range range, |
| Callback cb, |
| CenteredArray forward, |
| CenteredArray backward, |
| int d) { |
| boolean checkForSnake = Math.abs(range.oldSize() - range.newSize()) % 2 == 1; |
| int delta = range.oldSize() - range.newSize(); |
| for (int k = -d; k <= d; k += 2) { |
| // we either come from d-1, k-1 OR d-1. k+1 |
| // as we move in steps of 2, array always holds both current and previous d values |
| // k = x - y and each array value holds the max X, y = x - k |
| final int startX; |
| final int startY; |
| int x, y; |
| if (k == -d || (k != d && forward.get(k + 1) > forward.get(k - 1))) { |
| // picking k + 1, incrementing Y (by simply not incrementing X) |
| x = startX = forward.get(k + 1); |
| } else { |
| // picking k - 1, incrementing X |
| startX = forward.get(k - 1); |
| x = startX + 1; |
| } |
| y = range.newListStart + (x - range.oldListStart) - k; |
| startY = (d == 0 || x != startX) ? y : y - 1; |
| // now find snake size |
| while (x < range.oldListEnd |
| && y < range.newListEnd |
| && cb.areItemsTheSame(x, y)) { |
| x++; |
| y++; |
| } |
| // now we have furthest reaching x, record it |
| forward.set(k, x); |
| if (checkForSnake) { |
| // see if we did pass over a backwards array |
| // mapping function: delta - k |
| int backwardsK = delta - k; |
| // if backwards K is calculated and it passed me, found match |
| if (backwardsK >= -d + 1 |
| && backwardsK <= d - 1 |
| && backward.get(backwardsK) <= x) { |
| // match |
| Snake snake = new Snake(); |
| snake.startX = startX; |
| snake.startY = startY; |
| snake.endX = x; |
| snake.endY = y; |
| snake.reverse = false; |
| return snake; |
| } |
| } |
| } |
| return null; |
| } |
| |
| @Nullable |
| private static Snake backward( |
| Range range, |
| Callback cb, |
| CenteredArray forward, |
| CenteredArray backward, |
| int d) { |
| boolean checkForSnake = (range.oldSize() - range.newSize()) % 2 == 0; |
| int delta = range.oldSize() - range.newSize(); |
| // same as forward but we go backwards from end of the lists to be beginning |
| // this also means we'll try to optimize for minimizing x instead of maximizing it |
| for (int k = -d; k <= d; k += 2) { |
| // we either come from d-1, k-1 OR d-1, k+1 |
| // as we move in steps of 2, array always holds both current and previous d values |
| // k = x - y and each array value holds the MIN X, y = x - k |
| // when x's are equal, we prioritize deletion over insertion |
| final int startX; |
| final int startY; |
| int x, y; |
| |
| if (k == -d || (k != d && backward.get(k + 1) < backward.get(k - 1))) { |
| // picking k + 1, decrementing Y (by simply not decrementing X) |
| x = startX = backward.get(k + 1); |
| } else { |
| // picking k - 1, decrementing X |
| startX = backward.get(k - 1); |
| x = startX - 1; |
| } |
| y = range.newListEnd - ((range.oldListEnd - x) - k); |
| startY = (d == 0 || x != startX) ? y : y + 1; |
| // now find snake size |
| while (x > range.oldListStart |
| && y > range.newListStart |
| && cb.areItemsTheSame(x - 1, y - 1)) { |
| x--; |
| y--; |
| } |
| // now we have furthest point, record it (min X) |
| backward.set(k, x); |
| if (checkForSnake) { |
| // see if we did pass over a backwards array |
| // mapping function: delta - k |
| int forwardsK = delta - k; |
| // if forwards K is calculated and it passed me, found match |
| if (forwardsK >= -d |
| && forwardsK <= d |
| && forward.get(forwardsK) >= x) { |
| // match |
| Snake snake = new Snake(); |
| // assignment are reverse since we are a reverse snake |
| snake.startX = x; |
| snake.startY = y; |
| snake.endX = startX; |
| snake.endY = startY; |
| snake.reverse = true; |
| return snake; |
| } |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * 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. |
| * <p> |
| * 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. |
| * <p> |
| * 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 RecyclerView.Adapter RecyclerView.Adapter}, you should |
| * return whether the items' visual representations are the same. |
| * <p> |
| * 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. |
| * <p> |
| * For example, if you are using DiffUtil with {@link RecyclerView}, you can return the |
| * particular field that changed in the item and your |
| * {@link RecyclerView.ItemAnimator ItemAnimator} can use that |
| * information to run the correct animation. |
| * <p> |
| * 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; |
| } |
| } |
| |
| /** |
| * Callback for calculating the diff between two non-null items in a list. |
| * <p> |
| * {@link Callback} serves two roles - list indexing, and item diffing. ItemCallback handles |
| * just the second of these, which allows separation of code that indexes into an array or List |
| * from the presentation-layer and content specific diffing code. |
| * |
| * @param <T> Type of items to compare. |
| */ |
| public abstract static class ItemCallback<T> { |
| /** |
| * Called to check whether two objects represent the same item. |
| * <p> |
| * For example, if your items have unique ids, this method should check their id equality. |
| * <p> |
| * Note: {@code null} items in the list are assumed to be the same as another {@code null} |
| * item and are assumed to not be the same as a non-{@code null} item. This callback will |
| * not be invoked for either of those cases. |
| * |
| * @param oldItem The item in the old list. |
| * @param newItem The item in the new list. |
| * @return True if the two items represent the same object or false if they are different. |
| * @see Callback#areItemsTheSame(int, int) |
| */ |
| public abstract boolean areItemsTheSame(@NonNull T oldItem, @NonNull T newItem); |
| |
| /** |
| * Called to check whether two items have the same data. |
| * <p> |
| * This information is used to detect if the contents of an item have changed. |
| * <p> |
| * This method to check equality instead of {@link Object#equals(Object)} so that you can |
| * change its behavior depending on your UI. |
| * <p> |
| * For example, if you are using DiffUtil with a |
| * {@link RecyclerView.Adapter RecyclerView.Adapter}, you should |
| * return whether the items' visual representations are the same. |
| * <p> |
| * This method is called only if {@link #areItemsTheSame(T, T)} returns {@code true} for |
| * these items. |
| * <p> |
| * Note: Two {@code null} items are assumed to represent the same contents. This callback |
| * will not be invoked for this case. |
| * |
| * @param oldItem The item in the old list. |
| * @param newItem The item in the new list. |
| * @return True if the contents of the items are the same or false if they are different. |
| * @see Callback#areContentsTheSame(int, int) |
| */ |
| public abstract boolean areContentsTheSame(@NonNull T oldItem, @NonNull T newItem); |
| |
| /** |
| * When {@link #areItemsTheSame(T, T)} returns {@code true} for two items and |
| * {@link #areContentsTheSame(T, T)} returns false for them, this method is called to |
| * get a payload about the change. |
| * <p> |
| * For example, if you are using DiffUtil with {@link RecyclerView}, you can return the |
| * particular field that changed in the item and your |
| * {@link RecyclerView.ItemAnimator ItemAnimator} can use that |
| * information to run the correct animation. |
| * <p> |
| * Default implementation returns {@code null}. |
| * |
| * @see Callback#getChangePayload(int, int) |
| */ |
| @SuppressWarnings({"unused"}) |
| @Nullable |
| public Object getChangePayload(@NonNull T oldItem, @NonNull T newItem) { |
| return null; |
| } |
| } |
| |
| /** |
| * A diagonal is a match in the graph. |
| * Rather than snakes, we only record the diagonals in the path. |
| */ |
| static class Diagonal { |
| public final int x; |
| public final int y; |
| public final int size; |
| |
| Diagonal(int x, int y, int size) { |
| this.x = x; |
| this.y = y; |
| this.size = size; |
| } |
| |
| int endX() { |
| return x + size; |
| } |
| |
| int endY() { |
| return y + size; |
| } |
| } |
| |
| /** |
| * 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. |
| */ |
| @SuppressWarnings("WeakerAccess") |
| static class Snake { |
| /** |
| * Position in the old list |
| */ |
| public int startX; |
| |
| /** |
| * Position in the new list |
| */ |
| public int startY; |
| |
| /** |
| * End position in the old list, exclusive |
| */ |
| public int endX; |
| |
| /** |
| * End position in the new list, exclusive |
| */ |
| public int endY; |
| |
| /** |
| * True if this snake was created in the reverse search, false otherwise. |
| */ |
| public boolean reverse; |
| |
| boolean hasAdditionOrRemoval() { |
| return endY - startY != endX - startX; |
| } |
| |
| boolean isAddition() { |
| return endY - startY > endX - startX; |
| } |
| |
| int diagonalSize() { |
| return Math.min(endX - startX, endY - startY); |
| } |
| |
| /** |
| * Extract the diagonal of the snake to make reasoning easier for the rest of the |
| * algorithm where we try to produce a path and also find moves. |
| */ |
| @NonNull |
| Diagonal toDiagonal() { |
| if (hasAdditionOrRemoval()) { |
| if (reverse) { |
| // snake edge it at the end |
| return new Diagonal(startX, startY, diagonalSize()); |
| } else { |
| // snake edge it at the beginning |
| if (isAddition()) { |
| return new Diagonal(startX, startY + 1, diagonalSize()); |
| } else { |
| return new Diagonal(startX + 1, startY, diagonalSize()); |
| } |
| } |
| } else { |
| // we are a pure diagonal |
| return new Diagonal(startX, startY, endX - startX); |
| } |
| } |
| } |
| |
| /** |
| * Represents a range in two lists that needs to be solved. |
| * <p> |
| * This internal class is used when running Myers' algorithm without recursion. |
| * <p> |
| * Ends are exclusive |
| */ |
| 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; |
| } |
| |
| int oldSize() { |
| return oldListEnd - oldListStart; |
| } |
| |
| int newSize() { |
| return newListEnd - newListStart; |
| } |
| } |
| |
| /** |
| * This class holds the information about the result of a |
| * {@link DiffUtil#calculateDiff(Callback, boolean)} call. |
| * <p> |
| * 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 { |
| /** |
| * Signifies an item not present in the list. |
| */ |
| public static final int NO_POSITION = -1; |
| |
| |
| /** |
| * 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. |
| * <p> |
| * 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; |
| // Item moved |
| private static final int FLAG_MOVED = FLAG_MOVED_CHANGED | FLAG_MOVED_NOT_CHANGED; |
| |
| // 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 = 4; |
| |
| private static final int FLAG_MASK = (1 << FLAG_OFFSET) - 1; |
| |
| // The diagonals extracted from The Myers' snakes. |
| private final List<Diagonal> mDiagonals; |
| |
| // 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 calculate 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 diagonals Matches between the two lists |
| * @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<Diagonal> diagonals, int[] oldItemStatuses, |
| int[] newItemStatuses, boolean detectMoves) { |
| mDiagonals = diagonals; |
| mOldItemStatuses = oldItemStatuses; |
| mNewItemStatuses = newItemStatuses; |
| Arrays.fill(mOldItemStatuses, 0); |
| Arrays.fill(mNewItemStatuses, 0); |
| mCallback = callback; |
| mOldListSize = callback.getOldListSize(); |
| mNewListSize = callback.getNewListSize(); |
| mDetectMoves = detectMoves; |
| addEdgeDiagonals(); |
| findMatchingItems(); |
| } |
| |
| /** |
| * Add edge diagonals so that we can iterate as long as there are diagonals w/o lots of |
| * null checks around |
| */ |
| private void addEdgeDiagonals() { |
| Diagonal first = mDiagonals.isEmpty() ? null : mDiagonals.get(0); |
| // see if we should add 1 to the 0,0 |
| if (first == null || first.x != 0 || first.y != 0) { |
| mDiagonals.add(0, new Diagonal(0, 0, 0)); |
| } |
| // always add one last |
| mDiagonals.add(new Diagonal(mOldListSize, mNewListSize, 0)); |
| } |
| |
| /** |
| * Find position mapping from old list to new list. |
| * If moves are requested, we'll also try to do an n^2 search between additions and |
| * removals to find moves. |
| */ |
| private void findMatchingItems() { |
| for (Diagonal diagonal : mDiagonals) { |
| for (int offset = 0; offset < diagonal.size; offset++) { |
| int posX = diagonal.x + offset; |
| int posY = diagonal.y + offset; |
| final boolean theSame = mCallback.areContentsTheSame(posX, posY); |
| final int changeFlag = theSame ? FLAG_NOT_CHANGED : FLAG_CHANGED; |
| mOldItemStatuses[posX] = (posY << FLAG_OFFSET) | changeFlag; |
| mNewItemStatuses[posY] = (posX << FLAG_OFFSET) | changeFlag; |
| } |
| } |
| // now all matches are marked, lets look for moves |
| if (mDetectMoves) { |
| // traverse each addition / removal from the end of the list, find matching |
| // addition removal from before |
| findMoveMatches(); |
| } |
| } |
| |
| private void findMoveMatches() { |
| // for each removal, find matching addition |
| int posX = 0; |
| for (Diagonal diagonal : mDiagonals) { |
| while (posX < diagonal.x) { |
| if (mOldItemStatuses[posX] == 0) { |
| // there is a removal, find matching addition from the rest |
| findMatchingAddition(posX); |
| } |
| posX++; |
| } |
| // snap back for the next diagonal |
| posX = diagonal.endX(); |
| } |
| } |
| |
| /** |
| * Search the whole list to find the addition for the given removal of position posX |
| * |
| * @param posX position in the old list |
| */ |
| private void findMatchingAddition(int posX) { |
| int posY = 0; |
| final int diagonalsSize = mDiagonals.size(); |
| for (int i = 0; i < diagonalsSize; i++) { |
| final Diagonal diagonal = mDiagonals.get(i); |
| while (posY < diagonal.y) { |
| // found some additions, evaluate |
| if (mNewItemStatuses[posY] == 0) { // not evaluated yet |
| boolean matching = mCallback.areItemsTheSame(posX, posY); |
| if (matching) { |
| // yay found it, set values |
| boolean contentsMatching = mCallback.areContentsTheSame(posX, posY); |
| final int changeFlag = contentsMatching ? FLAG_MOVED_NOT_CHANGED |
| : FLAG_MOVED_CHANGED; |
| // once we process one of these, it will mark the other one as ignored. |
| mOldItemStatuses[posX] = (posY << FLAG_OFFSET) | changeFlag; |
| mNewItemStatuses[posY] = (posX << FLAG_OFFSET) | changeFlag; |
| return; |
| } |
| } |
| posY++; |
| } |
| posY = diagonal.endY(); |
| } |
| } |
| |
| /** |
| * Given a position in the old list, returns the position in the new list, or |
| * {@code NO_POSITION} if it was removed. |
| * |
| * @param oldListPosition Position of item in old list |
| * @return Position of item in new list, or {@code NO_POSITION} if not present. |
| * @see #NO_POSITION |
| * @see #convertNewPositionToOld(int) |
| */ |
| public int convertOldPositionToNew(@IntRange(from = 0) int oldListPosition) { |
| if (oldListPosition < 0 || oldListPosition >= mOldListSize) { |
| throw new IndexOutOfBoundsException("Index out of bounds - passed position = " |
| + oldListPosition + ", old list size = " + mOldListSize); |
| } |
| final int status = mOldItemStatuses[oldListPosition]; |
| if ((status & FLAG_MASK) == 0) { |
| return NO_POSITION; |
| } else { |
| return status >> FLAG_OFFSET; |
| } |
| } |
| |
| /** |
| * Given a position in the new list, returns the position in the old list, or |
| * {@code NO_POSITION} if it was removed. |
| * |
| * @param newListPosition Position of item in new list |
| * @return Position of item in old list, or {@code NO_POSITION} if not present. |
| * @see #NO_POSITION |
| * @see #convertOldPositionToNew(int) |
| */ |
| public int convertNewPositionToOld(@IntRange(from = 0) int newListPosition) { |
| if (newListPosition < 0 || newListPosition >= mNewListSize) { |
| throw new IndexOutOfBoundsException("Index out of bounds - passed position = " |
| + newListPosition + ", new list size = " + mNewListSize); |
| } |
| final int status = mNewItemStatuses[newListPosition]; |
| if ((status & FLAG_MASK) == 0) { |
| return NO_POSITION; |
| } else { |
| return status >> FLAG_OFFSET; |
| } |
| } |
| |
| /** |
| * Dispatches the update events to the given adapter. |
| * <p> |
| * For example, if you have an {@link 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. |
| * <pre> |
| * List oldList = mAdapter.getData(); |
| * DiffResult result = DiffUtil.calculateDiff(new MyCallback(oldList, newList)); |
| * mAdapter.setData(newList); |
| * result.dispatchUpdatesTo(mAdapter); |
| * </pre> |
| * <p> |
| * 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. |
| * <p> |
| * On the other hand, if you have another |
| * {@link 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 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. |
| * @see AdapterListUpdateCallback |
| */ |
| public void dispatchUpdatesTo(@NonNull final RecyclerView.Adapter adapter) { |
| dispatchUpdatesTo(new AdapterListUpdateCallback(adapter)); |
| } |
| |
| /** |
| * Dispatches update operations to the given Callback. |
| * <p> |
| * These updates are atomic such that the first update call affects 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(@NonNull 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; |
| } |
| // track up to date current list size for moves |
| // when a move is found, we record its position from the end of the list (which is |
| // less likely to change since we iterate in reverse). |
| // Later when we find the match of that move, we dispatch the update |
| int currentListSize = mOldListSize; |
| // list of postponed moves |
| final Collection<PostponedUpdate> postponedUpdates = new ArrayDeque<>(); |
| // posX and posY are exclusive |
| int posX = mOldListSize; |
| int posY = mNewListSize; |
| // iterate from end of the list to the beginning. |
| // this just makes offsets easier since changes in the earlier indices has an effect |
| // on the later indices. |
| for (int diagonalIndex = mDiagonals.size() - 1; diagonalIndex >= 0; diagonalIndex--) { |
| final Diagonal diagonal = mDiagonals.get(diagonalIndex); |
| int endX = diagonal.endX(); |
| int endY = diagonal.endY(); |
| // dispatch removals and additions until we reach to that diagonal |
| // first remove then add so that it can go into its place and we don't need |
| // to offset values |
| while (posX > endX) { |
| posX--; |
| // REMOVAL |
| int status = mOldItemStatuses[posX]; |
| if ((status & FLAG_MOVED) != 0) { |
| int newPos = status >> FLAG_OFFSET; |
| // get postponed addition |
| PostponedUpdate postponedUpdate = getPostponedUpdate(postponedUpdates, |
| newPos, false); |
| if (postponedUpdate != null) { |
| // this is an addition that was postponed. Now dispatch it. |
| int updatedNewPos = currentListSize - postponedUpdate.currentPos; |
| batchingCallback.onMoved(posX, updatedNewPos - 1); |
| if ((status & FLAG_MOVED_CHANGED) != 0) { |
| Object changePayload = mCallback.getChangePayload(posX, newPos); |
| batchingCallback.onChanged(updatedNewPos - 1, 1, changePayload); |
| } |
| } else { |
| // first time we are seeing this, we'll see a matching addition |
| postponedUpdates.add(new PostponedUpdate( |
| posX, |
| currentListSize - posX - 1, |
| true |
| )); |
| } |
| } else { |
| // simple removal |
| batchingCallback.onRemoved(posX, 1); |
| currentListSize--; |
| } |
| } |
| while (posY > endY) { |
| posY--; |
| // ADDITION |
| int status = mNewItemStatuses[posY]; |
| if ((status & FLAG_MOVED) != 0) { |
| // this is a move not an addition. |
| // see if this is postponed |
| int oldPos = status >> FLAG_OFFSET; |
| // get postponed removal |
| PostponedUpdate postponedUpdate = getPostponedUpdate(postponedUpdates, |
| oldPos, true); |
| // empty size returns 0 for indexOf |
| if (postponedUpdate == null) { |
| // postpone it until we see the removal |
| postponedUpdates.add(new PostponedUpdate( |
| posY, |
| currentListSize - posX, |
| false |
| )); |
| } else { |
| // oldPosFromEnd = foundListSize - posX |
| // we can find posX if we swap the list sizes |
| // posX = listSize - oldPosFromEnd |
| int updatedOldPos = currentListSize - postponedUpdate.currentPos - 1; |
| batchingCallback.onMoved(updatedOldPos, posX); |
| if ((status & FLAG_MOVED_CHANGED) != 0) { |
| Object changePayload = mCallback.getChangePayload(oldPos, posY); |
| batchingCallback.onChanged(posX, 1, changePayload); |
| } |
| } |
| } else { |
| // simple addition |
| batchingCallback.onInserted(posX, 1); |
| currentListSize++; |
| } |
| } |
| // now dispatch updates for the diagonal |
| posX = diagonal.x; |
| posY = diagonal.y; |
| for (int i = 0; i < diagonal.size; i++) { |
| // dispatch changes |
| if ((mOldItemStatuses[posX] & FLAG_MASK) == FLAG_CHANGED) { |
| Object changePayload = mCallback.getChangePayload(posX, posY); |
| batchingCallback.onChanged(posX, 1, changePayload); |
| } |
| posX++; |
| posY++; |
| } |
| // snap back for the next diagonal |
| posX = diagonal.x; |
| posY = diagonal.y; |
| } |
| batchingCallback.dispatchLastEvent(); |
| } |
| |
| @Nullable |
| private static PostponedUpdate getPostponedUpdate( |
| Collection<PostponedUpdate> postponedUpdates, |
| int posInList, |
| boolean removal) { |
| PostponedUpdate postponedUpdate = null; |
| Iterator<PostponedUpdate> itr = postponedUpdates.iterator(); |
| while (itr.hasNext()) { |
| PostponedUpdate update = itr.next(); |
| if (update.posInOwnerList == posInList && update.removal == removal) { |
| postponedUpdate = update; |
| itr.remove(); |
| break; |
| } |
| } |
| while (itr.hasNext()) { |
| // re-offset all others |
| PostponedUpdate update = itr.next(); |
| if (removal) { |
| update.currentPos--; |
| } else { |
| update.currentPos++; |
| } |
| } |
| return postponedUpdate; |
| } |
| } |
| |
| /** |
| * Represents an update that we skipped because it was a move. |
| * <p> |
| * 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 { |
| /** |
| * position in the list that owns this item |
| */ |
| int posInOwnerList; |
| |
| /** |
| * position wrt to the end of the list |
| */ |
| int currentPos; |
| |
| /** |
| * true if this is a removal, false otherwise |
| */ |
| boolean removal; |
| |
| PostponedUpdate(int posInOwnerList, int currentPos, boolean removal) { |
| this.posInOwnerList = posInOwnerList; |
| this.currentPos = currentPos; |
| this.removal = removal; |
| } |
| } |
| |
| /** |
| * Array wrapper w/ negative index support. |
| * We use this array instead of a regular array so that algorithm is easier to read without |
| * too many offsets when accessing the "k" array in the algorithm. |
| */ |
| static class CenteredArray { |
| private final int[] mData; |
| private final int mMid; |
| |
| CenteredArray(int size) { |
| mData = new int[size]; |
| mMid = mData.length / 2; |
| } |
| |
| int get(int index) { |
| return mData[index + mMid]; |
| } |
| |
| int[] backingData() { |
| return mData; |
| } |
| |
| void set(int index, int value) { |
| mData[index + mMid] = value; |
| } |
| |
| public void fill(int value) { |
| Arrays.fill(mData, value); |
| } |
| } |
| } |
