| /* |
| * 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.NonNull; |
| import androidx.annotation.Nullable; |
| |
| import java.lang.reflect.Array; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Comparator; |
| |
| /** |
| * A Sorted list implementation that can keep items in order and also notify for changes in the |
| * list |
| * such that it can be bound to a {@link RecyclerView.Adapter |
| * RecyclerView.Adapter}. |
| * <p> |
| * It keeps items ordered using the {@link Callback#compare(Object, Object)} method and uses |
| * binary search to retrieve items. If the sorting criteria of your items may change, make sure you |
| * call appropriate methods while editing them to avoid data inconsistencies. |
| * <p> |
| * You can control the order of items and change notifications via the {@link Callback} parameter. |
| */ |
| @SuppressWarnings("unchecked") |
| public class SortedList<T> { |
| |
| /** |
| * Used by {@link #indexOf(Object)} when the item cannot be found in the list. |
| */ |
| public static final int INVALID_POSITION = -1; |
| |
| private static final int MIN_CAPACITY = 10; |
| private static final int CAPACITY_GROWTH = MIN_CAPACITY; |
| private static final int INSERTION = 1; |
| private static final int DELETION = 1 << 1; |
| private static final int LOOKUP = 1 << 2; |
| T[] mData; |
| |
| /** |
| * A reference to the previous set of data that is kept during a mutation operation (addAll or |
| * replaceAll). |
| */ |
| private T[] mOldData; |
| |
| /** |
| * The current index into mOldData that has not yet been processed during a mutation operation |
| * (addAll or replaceAll). |
| */ |
| private int mOldDataStart; |
| private int mOldDataSize; |
| |
| /** |
| * The current index into the new data that has not yet been processed during a mutation |
| * operation (addAll or replaceAll). |
| */ |
| private int mNewDataStart; |
| |
| /** |
| * The callback instance that controls the behavior of the SortedList and get notified when |
| * changes happen. |
| */ |
| private Callback mCallback; |
| |
| private BatchedCallback mBatchedCallback; |
| |
| private int mSize; |
| private final Class<T> mTClass; |
| |
| /** |
| * Creates a new SortedList of type T. |
| * |
| * @param klass The class of the contents of the SortedList. |
| * @param callback The callback that controls the behavior of SortedList. |
| */ |
| public SortedList(@NonNull Class<T> klass, @NonNull Callback<T> callback) { |
| this(klass, callback, MIN_CAPACITY); |
| } |
| |
| /** |
| * Creates a new SortedList of type T. |
| * |
| * @param klass The class of the contents of the SortedList. |
| * @param callback The callback that controls the behavior of SortedList. |
| * @param initialCapacity The initial capacity to hold items. |
| */ |
| public SortedList(@NonNull Class<T> klass, @NonNull Callback<T> callback, int initialCapacity) { |
| mTClass = klass; |
| mData = (T[]) Array.newInstance(klass, initialCapacity); |
| mCallback = callback; |
| mSize = 0; |
| } |
| |
| /** |
| * The number of items in the list. |
| * |
| * @return The number of items in the list. |
| */ |
| public int size() { |
| return mSize; |
| } |
| |
| /** |
| * Adds the given item to the list. If this is a new item, SortedList calls |
| * {@link Callback#onInserted(int, int)}. |
| * <p> |
| * If the item already exists in the list and its sorting criteria is not changed, it is |
| * replaced with the existing Item. SortedList uses |
| * {@link Callback#areItemsTheSame(Object, Object)} to check if two items are the same item |
| * and uses {@link Callback#areContentsTheSame(Object, Object)} to decide whether it should |
| * call {@link Callback#onChanged(int, int)} or not. In both cases, it always removes the |
| * reference to the old item and puts the new item into the backing array even if |
| * {@link Callback#areContentsTheSame(Object, Object)} returns false. |
| * <p> |
| * If the sorting criteria of the item is changed, SortedList won't be able to find |
| * its duplicate in the list which will result in having a duplicate of the Item in the list. |
| * If you need to update sorting criteria of an item that already exists in the list, |
| * use {@link #updateItemAt(int, Object)}. You can find the index of the item using |
| * {@link #indexOf(Object)} before you update the object. |
| * |
| * @param item The item to be added into the list. |
| * |
| * @return The index of the newly added item. |
| * @see Callback#compare(Object, Object) |
| * @see Callback#areItemsTheSame(Object, Object) |
| * @see Callback#areContentsTheSame(Object, Object)} |
| */ |
| public int add(T item) { |
| throwIfInMutationOperation(); |
| return add(item, true); |
| } |
| |
| /** |
| * Adds the given items to the list. Equivalent to calling {@link SortedList#add} in a loop, |
| * except the callback events may be in a different order/granularity since addAll can batch |
| * them for better performance. |
| * <p> |
| * If allowed, will reference the input array during, and possibly after, the operation to avoid |
| * extra memory allocation, in which case you should not continue to reference or modify the |
| * array yourself. |
| * <p> |
| * @param items Array of items to be added into the list. |
| * @param mayModifyInput If true, SortedList is allowed to modify and permanently reference the |
| * input array. |
| * @see SortedList#addAll(T[] items) |
| */ |
| public void addAll(@NonNull T[] items, boolean mayModifyInput) { |
| throwIfInMutationOperation(); |
| if (items.length == 0) { |
| return; |
| } |
| |
| if (mayModifyInput) { |
| addAllInternal(items); |
| } else { |
| addAllInternal(copyArray(items)); |
| } |
| } |
| |
| /** |
| * Adds the given items to the list. Does not modify or retain the input. |
| * |
| * @see SortedList#addAll(T[] items, boolean mayModifyInput) |
| * |
| * @param items Array of items to be added into the list. |
| */ |
| public void addAll(@NonNull T... items) { |
| addAll(items, false); |
| } |
| |
| /** |
| * Adds the given items to the list. Does not modify or retain the input. |
| * |
| * @see SortedList#addAll(T[] items, boolean mayModifyInput) |
| * |
| * @param items Collection of items to be added into the list. |
| */ |
| public void addAll(@NonNull Collection<T> items) { |
| T[] copy = (T[]) Array.newInstance(mTClass, items.size()); |
| addAll(items.toArray(copy), true); |
| } |
| |
| /** |
| * Replaces the current items with the new items, dispatching {@link ListUpdateCallback} events |
| * for each change detected as appropriate. |
| * <p> |
| * If allowed, will reference the input array during, and possibly after, the operation to avoid |
| * extra memory allocation, in which case you should not continue to reference or modify the |
| * array yourself. |
| * <p> |
| * Note: this method does not detect moves or dispatch |
| * {@link ListUpdateCallback#onMoved(int, int)} events. It instead treats moves as a remove |
| * followed by an add and therefore dispatches {@link ListUpdateCallback#onRemoved(int, int)} |
| * and {@link ListUpdateCallback#onRemoved(int, int)} events. See {@link DiffUtil} if you want |
| * your implementation to dispatch move events. |
| * <p> |
| * @param items Array of items to replace current items. |
| * @param mayModifyInput If true, SortedList is allowed to modify and permanently reference the |
| * input array. |
| * @see #replaceAll(T[]) |
| */ |
| public void replaceAll(@NonNull T[] items, boolean mayModifyInput) { |
| throwIfInMutationOperation(); |
| |
| if (mayModifyInput) { |
| replaceAllInternal(items); |
| } else { |
| replaceAllInternal(copyArray(items)); |
| } |
| } |
| |
| /** |
| * Replaces the current items with the new items, dispatching {@link ListUpdateCallback} events |
| * for each change detected as appropriate. Does not modify or retain the input. |
| * |
| * @see #replaceAll(T[], boolean) |
| * |
| * @param items Array of items to replace current items. |
| */ |
| public void replaceAll(@NonNull T... items) { |
| replaceAll(items, false); |
| } |
| |
| /** |
| * Replaces the current items with the new items, dispatching {@link ListUpdateCallback} events |
| * for each change detected as appropriate. Does not modify or retain the input. |
| * |
| * @see #replaceAll(T[], boolean) |
| * |
| * @param items Array of items to replace current items. |
| */ |
| public void replaceAll(@NonNull Collection<T> items) { |
| T[] copy = (T[]) Array.newInstance(mTClass, items.size()); |
| replaceAll(items.toArray(copy), true); |
| } |
| |
| private void addAllInternal(T[] newItems) { |
| if (newItems.length < 1) { |
| return; |
| } |
| |
| final int newSize = sortAndDedup(newItems); |
| |
| if (mSize == 0) { |
| mData = newItems; |
| mSize = newSize; |
| mCallback.onInserted(0, newSize); |
| } else { |
| merge(newItems, newSize); |
| } |
| } |
| |
| private void replaceAllInternal(@NonNull T[] newData) { |
| final boolean forceBatchedUpdates = !(mCallback instanceof BatchedCallback); |
| if (forceBatchedUpdates) { |
| beginBatchedUpdates(); |
| } |
| |
| mOldDataStart = 0; |
| mOldDataSize = mSize; |
| mOldData = mData; |
| |
| mNewDataStart = 0; |
| int newSize = sortAndDedup(newData); |
| mData = (T[]) Array.newInstance(mTClass, newSize); |
| |
| while (mNewDataStart < newSize || mOldDataStart < mOldDataSize) { |
| if (mOldDataStart >= mOldDataSize) { |
| int insertIndex = mNewDataStart; |
| int itemCount = newSize - mNewDataStart; |
| System.arraycopy(newData, insertIndex, mData, insertIndex, itemCount); |
| mNewDataStart += itemCount; |
| mSize += itemCount; |
| mCallback.onInserted(insertIndex, itemCount); |
| break; |
| } |
| if (mNewDataStart >= newSize) { |
| int itemCount = mOldDataSize - mOldDataStart; |
| mSize -= itemCount; |
| mCallback.onRemoved(mNewDataStart, itemCount); |
| break; |
| } |
| |
| T oldItem = mOldData[mOldDataStart]; |
| T newItem = newData[mNewDataStart]; |
| |
| int result = mCallback.compare(oldItem, newItem); |
| if (result < 0) { |
| replaceAllRemove(); |
| } else if (result > 0) { |
| replaceAllInsert(newItem); |
| } else { |
| if (!mCallback.areItemsTheSame(oldItem, newItem)) { |
| // The items aren't the same even though they were supposed to occupy the same |
| // place, so both notify to remove and add an item in the current location. |
| replaceAllRemove(); |
| replaceAllInsert(newItem); |
| } else { |
| mData[mNewDataStart] = newItem; |
| mOldDataStart++; |
| mNewDataStart++; |
| if (!mCallback.areContentsTheSame(oldItem, newItem)) { |
| // The item is the same but the contents have changed, so notify that an |
| // onChanged event has occurred. |
| mCallback.onChanged(mNewDataStart - 1, 1, |
| mCallback.getChangePayload(oldItem, newItem)); |
| } |
| } |
| } |
| } |
| |
| mOldData = null; |
| |
| if (forceBatchedUpdates) { |
| endBatchedUpdates(); |
| } |
| } |
| |
| private void replaceAllInsert(T newItem) { |
| mData[mNewDataStart] = newItem; |
| mNewDataStart++; |
| mSize++; |
| mCallback.onInserted(mNewDataStart - 1, 1); |
| } |
| |
| private void replaceAllRemove() { |
| mSize--; |
| mOldDataStart++; |
| mCallback.onRemoved(mNewDataStart, 1); |
| } |
| |
| /** |
| * Sorts and removes duplicate items, leaving only the last item from each group of "same" |
| * items. Move the remaining items to the beginning of the array. |
| * |
| * @return Number of deduplicated items at the beginning of the array. |
| */ |
| private int sortAndDedup(@NonNull T[] items) { |
| if (items.length == 0) { |
| return 0; |
| } |
| |
| // Arrays.sort is stable. |
| Arrays.sort(items, mCallback); |
| |
| // Keep track of the range of equal items at the end of the output. |
| // Start with the range containing just the first item. |
| int rangeStart = 0; |
| int rangeEnd = 1; |
| |
| for (int i = 1; i < items.length; ++i) { |
| T currentItem = items[i]; |
| |
| int compare = mCallback.compare(items[rangeStart], currentItem); |
| |
| if (compare == 0) { |
| // The range of equal items continues, update it. |
| final int sameItemPos = findSameItem(currentItem, items, rangeStart, rangeEnd); |
| if (sameItemPos != INVALID_POSITION) { |
| // Replace the duplicate item. |
| items[sameItemPos] = currentItem; |
| } else { |
| // Expand the range. |
| if (rangeEnd != i) { // Avoid redundant copy. |
| items[rangeEnd] = currentItem; |
| } |
| rangeEnd++; |
| } |
| } else { |
| // The range has ended. Reset it to contain just the current item. |
| if (rangeEnd != i) { // Avoid redundant copy. |
| items[rangeEnd] = currentItem; |
| } |
| rangeStart = rangeEnd++; |
| } |
| } |
| return rangeEnd; |
| } |
| |
| |
| private int findSameItem(T item, T[] items, int from, int to) { |
| for (int pos = from; pos < to; pos++) { |
| if (mCallback.areItemsTheSame(items[pos], item)) { |
| return pos; |
| } |
| } |
| return INVALID_POSITION; |
| } |
| |
| /** |
| * This method assumes that newItems are sorted and deduplicated. |
| */ |
| private void merge(T[] newData, int newDataSize) { |
| final boolean forceBatchedUpdates = !(mCallback instanceof BatchedCallback); |
| if (forceBatchedUpdates) { |
| beginBatchedUpdates(); |
| } |
| |
| mOldData = mData; |
| mOldDataStart = 0; |
| mOldDataSize = mSize; |
| |
| final int mergedCapacity = mSize + newDataSize + CAPACITY_GROWTH; |
| mData = (T[]) Array.newInstance(mTClass, mergedCapacity); |
| mNewDataStart = 0; |
| |
| int newDataStart = 0; |
| while (mOldDataStart < mOldDataSize || newDataStart < newDataSize) { |
| if (mOldDataStart == mOldDataSize) { |
| // No more old items, copy the remaining new items. |
| int itemCount = newDataSize - newDataStart; |
| System.arraycopy(newData, newDataStart, mData, mNewDataStart, itemCount); |
| mNewDataStart += itemCount; |
| mSize += itemCount; |
| mCallback.onInserted(mNewDataStart - itemCount, itemCount); |
| break; |
| } |
| |
| if (newDataStart == newDataSize) { |
| // No more new items, copy the remaining old items. |
| int itemCount = mOldDataSize - mOldDataStart; |
| System.arraycopy(mOldData, mOldDataStart, mData, mNewDataStart, itemCount); |
| mNewDataStart += itemCount; |
| break; |
| } |
| |
| T oldItem = mOldData[mOldDataStart]; |
| T newItem = newData[newDataStart]; |
| int compare = mCallback.compare(oldItem, newItem); |
| if (compare > 0) { |
| // New item is lower, output it. |
| mData[mNewDataStart++] = newItem; |
| mSize++; |
| newDataStart++; |
| mCallback.onInserted(mNewDataStart - 1, 1); |
| } else if (compare == 0 && mCallback.areItemsTheSame(oldItem, newItem)) { |
| // Items are the same. Output the new item, but consume both. |
| mData[mNewDataStart++] = newItem; |
| newDataStart++; |
| mOldDataStart++; |
| if (!mCallback.areContentsTheSame(oldItem, newItem)) { |
| mCallback.onChanged(mNewDataStart - 1, 1, |
| mCallback.getChangePayload(oldItem, newItem)); |
| } |
| } else { |
| // Old item is lower than or equal to (but not the same as the new). Output it. |
| // New item with the same sort order will be inserted later. |
| mData[mNewDataStart++] = oldItem; |
| mOldDataStart++; |
| } |
| } |
| |
| mOldData = null; |
| |
| if (forceBatchedUpdates) { |
| endBatchedUpdates(); |
| } |
| } |
| |
| /** |
| * Throws an exception if called while we are in the middle of a mutation operation (addAll or |
| * replaceAll). |
| */ |
| private void throwIfInMutationOperation() { |
| if (mOldData != null) { |
| throw new IllegalStateException("Data cannot be mutated in the middle of a batch " |
| + "update operation such as addAll or replaceAll."); |
| } |
| } |
| |
| /** |
| * Batches adapter updates that happen after calling this method and before calling |
| * {@link #endBatchedUpdates()}. For example, if you add multiple items in a loop |
| * and they are placed into consecutive indices, SortedList calls |
| * {@link Callback#onInserted(int, int)} only once with the proper item count. If an event |
| * cannot be merged with the previous event, the previous event is dispatched |
| * to the callback instantly. |
| * <p> |
| * After running your data updates, you <b>must</b> call {@link #endBatchedUpdates()} |
| * which will dispatch any deferred data change event to the current callback. |
| * <p> |
| * A sample implementation may look like this: |
| * <pre> |
| * mSortedList.beginBatchedUpdates(); |
| * try { |
| * mSortedList.add(item1) |
| * mSortedList.add(item2) |
| * mSortedList.remove(item3) |
| * ... |
| * } finally { |
| * mSortedList.endBatchedUpdates(); |
| * } |
| * </pre> |
| * <p> |
| * Instead of using this method to batch calls, you can use a Callback that extends |
| * {@link BatchedCallback}. In that case, you must make sure that you are manually calling |
| * {@link BatchedCallback#dispatchLastEvent()} right after you complete your data changes. |
| * Failing to do so may create data inconsistencies with the Callback. |
| * <p> |
| * If the current Callback is an instance of {@link BatchedCallback}, calling this method |
| * has no effect. |
| */ |
| public void beginBatchedUpdates() { |
| throwIfInMutationOperation(); |
| if (mCallback instanceof BatchedCallback) { |
| return; |
| } |
| if (mBatchedCallback == null) { |
| mBatchedCallback = new BatchedCallback(mCallback); |
| } |
| mCallback = mBatchedCallback; |
| } |
| |
| /** |
| * Ends the update transaction and dispatches any remaining event to the callback. |
| */ |
| public void endBatchedUpdates() { |
| throwIfInMutationOperation(); |
| if (mCallback instanceof BatchedCallback) { |
| ((BatchedCallback) mCallback).dispatchLastEvent(); |
| } |
| if (mCallback == mBatchedCallback) { |
| mCallback = mBatchedCallback.mWrappedCallback; |
| } |
| } |
| |
| private int add(T item, boolean notify) { |
| int index = findIndexOf(item, mData, 0, mSize, INSERTION); |
| if (index == INVALID_POSITION) { |
| index = 0; |
| } else if (index < mSize) { |
| T existing = mData[index]; |
| if (mCallback.areItemsTheSame(existing, item)) { |
| if (mCallback.areContentsTheSame(existing, item)) { |
| //no change but still replace the item |
| mData[index] = item; |
| return index; |
| } else { |
| mData[index] = item; |
| mCallback.onChanged(index, 1, mCallback.getChangePayload(existing, item)); |
| return index; |
| } |
| } |
| } |
| addToData(index, item); |
| if (notify) { |
| mCallback.onInserted(index, 1); |
| } |
| return index; |
| } |
| |
| /** |
| * Removes the provided item from the list and calls {@link Callback#onRemoved(int, int)}. |
| * |
| * @param item The item to be removed from the list. |
| * |
| * @return True if item is removed, false if item cannot be found in the list. |
| */ |
| public boolean remove(T item) { |
| throwIfInMutationOperation(); |
| return remove(item, true); |
| } |
| |
| /** |
| * Removes the item at the given index and calls {@link Callback#onRemoved(int, int)}. |
| * |
| * @param index The index of the item to be removed. |
| * |
| * @return The removed item. |
| */ |
| public T removeItemAt(int index) { |
| throwIfInMutationOperation(); |
| T item = get(index); |
| removeItemAtIndex(index, true); |
| return item; |
| } |
| |
| private boolean remove(T item, boolean notify) { |
| int index = findIndexOf(item, mData, 0, mSize, DELETION); |
| if (index == INVALID_POSITION) { |
| return false; |
| } |
| removeItemAtIndex(index, notify); |
| return true; |
| } |
| |
| private void removeItemAtIndex(int index, boolean notify) { |
| System.arraycopy(mData, index + 1, mData, index, mSize - index - 1); |
| mSize--; |
| mData[mSize] = null; |
| if (notify) { |
| mCallback.onRemoved(index, 1); |
| } |
| } |
| |
| /** |
| * Updates the item at the given index and calls {@link Callback#onChanged(int, int)} and/or |
| * {@link Callback#onMoved(int, int)} if necessary. |
| * <p> |
| * You can use this method if you need to change an existing Item such that its position in the |
| * list may change. |
| * <p> |
| * If the new object is a different object (<code>get(index) != item</code>) and |
| * {@link Callback#areContentsTheSame(Object, Object)} returns <code>true</code>, SortedList |
| * avoids calling {@link Callback#onChanged(int, int)} otherwise it calls |
| * {@link Callback#onChanged(int, int)}. |
| * <p> |
| * If the new position of the item is different than the provided <code>index</code>, |
| * SortedList |
| * calls {@link Callback#onMoved(int, int)}. |
| * |
| * @param index The index of the item to replace |
| * @param item The item to replace the item at the given Index. |
| * @see #add(Object) |
| */ |
| public void updateItemAt(int index, T item) { |
| throwIfInMutationOperation(); |
| final T existing = get(index); |
| // assume changed if the same object is given back |
| boolean contentsChanged = existing == item || !mCallback.areContentsTheSame(existing, item); |
| if (existing != item) { |
| // different items, we can use comparison and may avoid lookup |
| final int cmp = mCallback.compare(existing, item); |
| if (cmp == 0) { |
| mData[index] = item; |
| if (contentsChanged) { |
| mCallback.onChanged(index, 1, mCallback.getChangePayload(existing, item)); |
| } |
| return; |
| } |
| } |
| if (contentsChanged) { |
| mCallback.onChanged(index, 1, mCallback.getChangePayload(existing, item)); |
| } |
| // TODO this done in 1 pass to avoid shifting twice. |
| removeItemAtIndex(index, false); |
| int newIndex = add(item, false); |
| if (index != newIndex) { |
| mCallback.onMoved(index, newIndex); |
| } |
| } |
| |
| /** |
| * This method can be used to recalculate the position of the item at the given index, without |
| * triggering an {@link Callback#onChanged(int, int)} callback. |
| * <p> |
| * If you are editing objects in the list such that their position in the list may change but |
| * you don't want to trigger an onChange animation, you can use this method to re-position it. |
| * If the item changes position, SortedList will call {@link Callback#onMoved(int, int)} |
| * without |
| * calling {@link Callback#onChanged(int, int)}. |
| * <p> |
| * A sample usage may look like: |
| * |
| * <pre> |
| * final int position = mSortedList.indexOf(item); |
| * item.incrementPriority(); // assume items are sorted by priority |
| * mSortedList.recalculatePositionOfItemAt(position); |
| * </pre> |
| * In the example above, because the sorting criteria of the item has been changed, |
| * mSortedList.indexOf(item) will not be able to find the item. This is why the code above |
| * first |
| * gets the position before editing the item, edits it and informs the SortedList that item |
| * should be repositioned. |
| * |
| * @param index The current index of the Item whose position should be re-calculated. |
| * @see #updateItemAt(int, Object) |
| * @see #add(Object) |
| */ |
| public void recalculatePositionOfItemAt(int index) { |
| throwIfInMutationOperation(); |
| // TODO can be improved |
| final T item = get(index); |
| removeItemAtIndex(index, false); |
| int newIndex = add(item, false); |
| if (index != newIndex) { |
| mCallback.onMoved(index, newIndex); |
| } |
| } |
| |
| /** |
| * Returns the item at the given index. |
| * |
| * @param index The index of the item to retrieve. |
| * |
| * @return The item at the given index. |
| * @throws java.lang.IndexOutOfBoundsException if provided index is negative or larger than the |
| * size of the list. |
| */ |
| public T get(int index) throws IndexOutOfBoundsException { |
| if (index >= mSize || index < 0) { |
| throw new IndexOutOfBoundsException("Asked to get item at " + index + " but size is " |
| + mSize); |
| } |
| if (mOldData != null) { |
| // The call is made from a callback during addAll execution. The data is split |
| // between mData and mOldData. |
| if (index >= mNewDataStart) { |
| return mOldData[index - mNewDataStart + mOldDataStart]; |
| } |
| } |
| return mData[index]; |
| } |
| |
| /** |
| * Returns the position of the provided item. |
| * |
| * @param item The item to query for position. |
| * |
| * @return The position of the provided item or {@link #INVALID_POSITION} if item is not in the |
| * list. |
| */ |
| public int indexOf(T item) { |
| if (mOldData != null) { |
| int index = findIndexOf(item, mData, 0, mNewDataStart, LOOKUP); |
| if (index != INVALID_POSITION) { |
| return index; |
| } |
| index = findIndexOf(item, mOldData, mOldDataStart, mOldDataSize, LOOKUP); |
| if (index != INVALID_POSITION) { |
| return index - mOldDataStart + mNewDataStart; |
| } |
| return INVALID_POSITION; |
| } |
| return findIndexOf(item, mData, 0, mSize, LOOKUP); |
| } |
| |
| private int findIndexOf(T item, T[] mData, int left, int right, int reason) { |
| while (left < right) { |
| final int middle = (left + right) / 2; |
| T myItem = mData[middle]; |
| final int cmp = mCallback.compare(myItem, item); |
| if (cmp < 0) { |
| left = middle + 1; |
| } else if (cmp == 0) { |
| if (mCallback.areItemsTheSame(myItem, item)) { |
| return middle; |
| } else { |
| int exact = linearEqualitySearch(item, middle, left, right); |
| if (reason == INSERTION) { |
| return exact == INVALID_POSITION ? middle : exact; |
| } else { |
| return exact; |
| } |
| } |
| } else { |
| right = middle; |
| } |
| } |
| return reason == INSERTION ? left : INVALID_POSITION; |
| } |
| |
| private int linearEqualitySearch(T item, int middle, int left, int right) { |
| // go left |
| for (int next = middle - 1; next >= left; next--) { |
| T nextItem = mData[next]; |
| int cmp = mCallback.compare(nextItem, item); |
| if (cmp != 0) { |
| break; |
| } |
| if (mCallback.areItemsTheSame(nextItem, item)) { |
| return next; |
| } |
| } |
| for (int next = middle + 1; next < right; next++) { |
| T nextItem = mData[next]; |
| int cmp = mCallback.compare(nextItem, item); |
| if (cmp != 0) { |
| break; |
| } |
| if (mCallback.areItemsTheSame(nextItem, item)) { |
| return next; |
| } |
| } |
| return INVALID_POSITION; |
| } |
| |
| private void addToData(int index, T item) { |
| if (index > mSize) { |
| throw new IndexOutOfBoundsException( |
| "cannot add item to " + index + " because size is " + mSize); |
| } |
| if (mSize == mData.length) { |
| // we are at the limit enlarge |
| T[] newData = (T[]) Array.newInstance(mTClass, mData.length + CAPACITY_GROWTH); |
| System.arraycopy(mData, 0, newData, 0, index); |
| newData[index] = item; |
| System.arraycopy(mData, index, newData, index + 1, mSize - index); |
| mData = newData; |
| } else { |
| // just shift, we fit |
| System.arraycopy(mData, index, mData, index + 1, mSize - index); |
| mData[index] = item; |
| } |
| mSize++; |
| } |
| |
| private T[] copyArray(T[] items) { |
| T[] copy = (T[]) Array.newInstance(mTClass, items.length); |
| System.arraycopy(items, 0, copy, 0, items.length); |
| return copy; |
| } |
| |
| /** |
| * Removes all items from the SortedList. |
| */ |
| public void clear() { |
| throwIfInMutationOperation(); |
| if (mSize == 0) { |
| return; |
| } |
| final int prevSize = mSize; |
| Arrays.fill(mData, 0, prevSize, null); |
| mSize = 0; |
| mCallback.onRemoved(0, prevSize); |
| } |
| |
| /** |
| * The class that controls the behavior of the {@link SortedList}. |
| * <p> |
| * It defines how items should be sorted and how duplicates should be handled. |
| * <p> |
| * SortedList calls the callback methods on this class to notify changes about the underlying |
| * data. |
| */ |
| public static abstract class Callback<T2> implements Comparator<T2>, ListUpdateCallback { |
| |
| /** |
| * Similar to {@link java.util.Comparator#compare(Object, Object)}, should compare two and |
| * return how they should be ordered. |
| * |
| * @param o1 The first object to compare. |
| * @param o2 The second object to compare. |
| * |
| * @return a negative integer, zero, or a positive integer as the |
| * first argument is less than, equal to, or greater than the |
| * second. |
| */ |
| @Override |
| abstract public int compare(T2 o1, T2 o2); |
| |
| /** |
| * Called by the SortedList when the item at the given position is updated. |
| * |
| * @param position The position of the item which has been updated. |
| * @param count The number of items which has changed. |
| */ |
| abstract public void onChanged(int position, int count); |
| |
| @Override |
| public void onChanged(int position, int count, Object payload) { |
| onChanged(position, count); |
| } |
| |
| /** |
| * Called by the SortedList when it wants to check whether two items have the same data |
| * or not. SortedList uses this information to decide whether it should call |
| * {@link #onChanged(int, int)} or not. |
| * <p> |
| * SortedList uses 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 SortedList with a |
| * {@link RecyclerView.Adapter RecyclerView.Adapter}, you should |
| * return whether the items' visual representations are the same or not. |
| * |
| * @param oldItem The previous representation of the object. |
| * @param newItem The new object that replaces the previous one. |
| * |
| * @return True if the contents of the items are the same or false if they are different. |
| */ |
| abstract public boolean areContentsTheSame(T2 oldItem, T2 newItem); |
| |
| /** |
| * Called by the SortedList to decide whether two objects represent the same Item or not. |
| * <p> |
| * For example, if your items have unique ids, this method should check their equality. |
| * |
| * @param item1 The first item to check. |
| * @param item2 The second item to check. |
| * |
| * @return True if the two items represent the same object or false if they are different. |
| */ |
| abstract public boolean areItemsTheSame(T2 item1, T2 item2); |
| |
| /** |
| * When {@link #areItemsTheSame(T2, T2)} returns {@code true} for two items and |
| * {@link #areContentsTheSame(T2, T2)} returns false for them, {@link Callback} calls this |
| * method to get a payload about the change. |
| * <p> |
| * For example, if you are using {@link Callback} 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 item1 The first item to check. |
| * @param item2 The second item to check. |
| * @return A payload object that represents the changes between the two items. |
| */ |
| @Nullable |
| public Object getChangePayload(T2 item1, T2 item2) { |
| return null; |
| } |
| } |
| |
| /** |
| * A callback implementation that can batch notify events dispatched by the SortedList. |
| * <p> |
| * This class can be useful if you want to do multiple operations on a SortedList but don't |
| * want to dispatch each event one by one, which may result in a performance issue. |
| * <p> |
| * For example, if you are going to add multiple items to a SortedList, BatchedCallback call |
| * convert individual <code>onInserted(index, 1)</code> calls into one |
| * <code>onInserted(index, N)</code> if items are added into consecutive indices. This change |
| * can help RecyclerView resolve changes much more easily. |
| * <p> |
| * If consecutive changes in the SortedList are not suitable for batching, BatchingCallback |
| * dispatches them as soon as such case is detected. After your edits on the SortedList is |
| * complete, you <b>must</b> always call {@link BatchedCallback#dispatchLastEvent()} to flush |
| * all changes to the Callback. |
| */ |
| public static class BatchedCallback<T2> extends Callback<T2> { |
| |
| final Callback<T2> mWrappedCallback; |
| private final BatchingListUpdateCallback mBatchingListUpdateCallback; |
| /** |
| * Creates a new BatchedCallback that wraps the provided Callback. |
| * |
| * @param wrappedCallback The Callback which should received the data change callbacks. |
| * Other method calls (e.g. {@link #compare(Object, Object)} from |
| * the SortedList are directly forwarded to this Callback. |
| */ |
| public BatchedCallback(Callback<T2> wrappedCallback) { |
| mWrappedCallback = wrappedCallback; |
| mBatchingListUpdateCallback = new BatchingListUpdateCallback(mWrappedCallback); |
| } |
| |
| @Override |
| public int compare(T2 o1, T2 o2) { |
| return mWrappedCallback.compare(o1, o2); |
| } |
| |
| @Override |
| public void onInserted(int position, int count) { |
| mBatchingListUpdateCallback.onInserted(position, count); |
| } |
| |
| @Override |
| public void onRemoved(int position, int count) { |
| mBatchingListUpdateCallback.onRemoved(position, count); |
| } |
| |
| @Override |
| public void onMoved(int fromPosition, int toPosition) { |
| mBatchingListUpdateCallback.onMoved(fromPosition, toPosition); |
| } |
| |
| @Override |
| public void onChanged(int position, int count) { |
| mBatchingListUpdateCallback.onChanged(position, count, null); |
| } |
| |
| @Override |
| public void onChanged(int position, int count, Object payload) { |
| mBatchingListUpdateCallback.onChanged(position, count, payload); |
| } |
| |
| @Override |
| public boolean areContentsTheSame(T2 oldItem, T2 newItem) { |
| return mWrappedCallback.areContentsTheSame(oldItem, newItem); |
| } |
| |
| @Override |
| public boolean areItemsTheSame(T2 item1, T2 item2) { |
| return mWrappedCallback.areItemsTheSame(item1, item2); |
| } |
| |
| @Nullable |
| @Override |
| public Object getChangePayload(T2 item1, T2 item2) { |
| return mWrappedCallback.getChangePayload(item1, item2); |
| } |
| |
| /** |
| * This method dispatches any pending event notifications to the wrapped Callback. |
| * You <b>must</b> always call this method after you are done with editing the SortedList. |
| */ |
| public void dispatchLastEvent() { |
| mBatchingListUpdateCallback.dispatchLastEvent(); |
| } |
| } |
| } |