/* * Copyright (C) 2014 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 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 android.support.v7.widget.RecyclerView.Adapter * RecyclerView.Adapter}. *
* 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. *
* You can control the order of items and change notifications via the {@link Callback} parameter.
*/
@SuppressWarnings("unchecked")
public class SortedList
* 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.
*
* 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) {
throwIfMerging();
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.
*
* If allowed, may modify the input array and even take the ownership over it in order
* to avoid extra memory allocation during sorting and deduplication.
*
* After running your data updates, you must call {@link #endBatchedUpdates()}
* which will dispatch any deferred data change event to the current callback.
*
* A sample implementation may look like this:
*
* 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.
*
* If the current Callback is an instance of {@link BatchedCallback}, calling this method
* has no effect.
*/
public void beginBatchedUpdates() {
throwIfMerging();
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() {
throwIfMerging();
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);
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) {
throwIfMerging();
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) {
throwIfMerging();
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.
*
* You can use this method if you need to change an existing Item such that its position in the
* list may change.
*
* If the new object is a different object (
* If the new position of the item is different than the provided
* 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)}.
*
* A sample usage may look like:
*
*
* It defines how items should be sorted and how duplicates should be handled.
*
* SortedList calls the callback methods on this class to notify changes about the underlying
* data.
*/
public static abstract class Callback
* SortedList 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 SortedList with a {@link android.support.v7.widget.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 object represent the same Item or not.
*
* 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);
}
/**
* A callback implementation that can batch notify events dispatched by the SortedList.
*
* 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.
*
* For example, if you are going to add multiple items to a SortedList, BatchedCallback call
* convert individual
* 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 must always call {@link BatchedCallback#dispatchLastEvent()} to flush
* all changes to the Callback.
*/
public static class BatchedCallback
* mSortedList.beginBatchedUpdates();
* try {
* mSortedList.add(item1)
* mSortedList.add(item2)
* mSortedList.remove(item3)
* ...
* } finally {
* mSortedList.endBatchedUpdates();
* }
*
* get(index) != item
) and
* {@link Callback#areContentsTheSame(Object, Object)} returns true
, SortedList
* avoids calling {@link Callback#onChanged(int, int)} otherwise it calls
* {@link Callback#onChanged(int, int)}.
* index
,
* 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) {
throwIfMerging();
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);
}
return;
}
}
if (contentsChanged) {
mCallback.onChanged(index, 1);
}
// 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.
*
* final int position = mSortedList.indexOf(item);
* item.incrementPriority(); // assume items are sorted by priority
* mSortedList.recalculatePositionOfItemAt(position);
*
* 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) {
throwIfMerging();
// 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 >= mMergedSize) {
return mOldData[index - mMergedSize + 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, mMergedSize, LOOKUP);
if (index != INVALID_POSITION) {
return index;
}
index = findIndexOf(item, mOldData, mOldDataStart, mOldDataSize, LOOKUP);
if (index != INVALID_POSITION) {
return index - mOldDataStart + mMergedSize;
}
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++;
}
/**
* Removes all items from the SortedList.
*/
public void clear() {
throwIfMerging();
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}.
* onInserted(index, 1)
calls into one
* onInserted(index, N)
if items are added into consecutive indices. This change
* can help RecyclerView resolve changes much more easily.
*