0x00 Background
It is common for a list to have a specific order, assuming you have a bunch of contacts in your list, you might want to sort them in alphabet order, or if you have some kind of notes, you like to sort them in time order. These sorting requirements are common and easy, you can just use a list and a comparator, just use the compare() method, however some are much complicated, like different kind of data, different sort rules, how to deal with the duplicated names. Also, you need to handle all the changes like insert, remove and updates. Sometimes it can be annoying, no worry, we have SortedList.
0x01 What is a SortedList
In order to have a sorted list in recycler view, and update automatically, we used a library from RecyclerView, it is SortedList from android.support.v7.util.
As we can find in SortedList implementation.
/**
* 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}.
* <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 ⌃ the order of items and change notifications via the {@link Callback} parameter.
*/
SortedList holds a recycler view adapter and manages updates like insertion\delete\item updates. And also supports serval useful functions like batch updates.
0x02 SortedList and updates
SortedList is just like its name, it is sorted since created, all operations will just update the list, and it will always be sorted, it can help you handle UI update and data change.
Create a sorted list and callback
SortedList is easy to use. We can create our own instance of SortedList by inheriting the original SortedList and add our methods there.
To have our own compare rules, all we need to do is to implement a SortedCallback from SortedList.Callback<T>, where T is the generic type of your data, and override these methods.
abstract public int compare(T2 o1, T2 o2);
abstract public boolean areContentsTheSame(T2 oldItem, T2 newItem);
abstract public boolean areItemsTheSame(T2 item1, T2 item2);
I will explain these methods later in next section 0x03 Sort rules.
After create your own SortedList instance and create your own SortedCallback, you can easily add your data to your sorted list.
Just like a normal list, you are able to use add() addAll() remove(), you can also write your own useful methods like removeById(). Most methods are used like in a normal recycler list adapter. Just remember to call the methods from SortedList.
In fragment, like all recycler view, you crate your adapter, set your adapter to recycler view, and here comes the differences. You have to create a sorted list and put your own SortedCallback instance to it.
adapter = new MyAdapter(this);
recyclerView.setAdapter(adapter);
mySortedList = new MySortedList(ListItem.class, new SortedCallback(adapter));
adapter.initDataList(mySortedList);
After all these done, you can happily use your mySortedList to update items.
Batch updates
Since we have to sort the whole list and update them on UI, if we have serval data to update, it is expensive to update them one by one, we need to update them once and all. That is why we need batch updates.
By using SortedList, it is very easy to have batch updates, when you have multiple data to update, you can do it either in your list or in UI.
// In your sorted list
beginBatchedUpdates();
// Do the updates like insert or remove or update
endBatchedUpdates();
// In UI
mySortedList.beginBatchedUpdates();
// Do the updates like insert or remove or update
mySortedList.endBatchedUpdates();
SortedList will handle batch updates during your event and update them to UI once for all.
Delayed refresh
For some reason, some callback might call frequently, we also need a buffer to cache the updates and update them once in a time slot, like 1 second.
We create a set to hold the data, and post a handler delay for 1 second if there is any update.
// Create the buffer set
private Set<ListItemData> dataSet = new HashSet<>(10);
// In Callback method that called frequently
@Override
public void onDataChange(ListItemData data) {
dataSet.add(data);
if (!handler.hasMessages(1)) {
handler.sendEmptyMessageDelayed(1, 1000);
}
}
// Handler
private Handler handler = new Handler() {
@Override
public void handleMessage(Message msg) {
super.handleMessage(msg);
if (msg.what == 1) {
beginBatchedUpdates();
for (ListItemData data : dataSet) {
int index = indexOf(data);
if (index >= 0) {
callback.setPayload(TYPE_CHANGE); // For partial updates
updateItemAt(index, data);
}
}
endBatchedUpdates();
dataSet.clear(); // Clear for next update
}
}
};
Note:
Remember to remove the handler when clear the list or UI destroy, or it might cause memory leak.
Partial updates
Sometimes we have serval fields on UI need to update, like photos\names\status, when one field update, we want to only refresh the specific view rather than the whole view holder. That comes the partial updates.
To understand partial updates in recycler view. One thing to know is the payloads in onBindViewHolder(RecyclerView.ViewHolder holder, int position, List<Object> payloads). We can set our own payloads and update using adapter's update method.
In your own SortedCallBack, override the onChange() method and notify the changes.
@Override
public void onChanged(int position, int count) {
mAdapter.notifyItemRangeChanged(position, count, payload);
}
Also in Adapter, we need to implement two onBindViewHolder() methods. One with payloads and one not.
If update with payloads, first retrieve the payload list to detect what need to be updated, then update them separately.
Performance considering
UI updates are expensive, we have to do them in main thread, and sometimes you have to be careful about refreshing UI, loading bitmaps or refreshing too frequently might cost a lot of CPU or memory resourse.
To avoid the performance issues of refreshing list, we combine the batched updates, delayed refresh and partial updates, try to refresh UI less but never miss a point. When data changed, data list is able to get the change event in time and cache them in buffer, then batch update them, when it comes to UI, just refresh the changed part without refreshing other views. This can help a lot for CPU and memory usage.
0x03 Sort rules
Here comes the most important part for sorted list: the sort rules.
For a sorted list, we have to decide, which one should be at the top, which one should be after, that is why we need a rule.
Remember the methods in SortedList.Callback?
abstract public int compare(T2 o1, T2 o2);
abstract public boolean areContentsTheSame(T2 oldItem, T2 newItem);
abstract public boolean areItemsTheSame(T2 item1, T2 item2);
I will explain them one by one.
First, the compare() method. Actually it is from Comparator interface, SortedList.Callback implements it and makes it abstract, so we need to override it. For two items the compare() method decides which one is Bigger than the other one, if o1>o2, then returns 1, if o1<02, then returns -1, if they are the same, then 0 will be returned.
Then, the areContentsTheSame() method, like described in comments(which you can find in codes), this method decides whether it need to refresh the UI or not. Mostly it compares the UI related data, since it might need to refresh.
From comments:
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.
Lastly, the areItemsTheSame() method, it is more like an equals() method, it decides whether two object represent the same Item or not. If you have an unique ID for your data, you should use that ID.
From comments:
@return True if the two items represent the same object or false if they are different.
In order to have a completely sorted list for different kind of data, we need a common field to compare and keep the order.
So we need an interface, to mark the common fields for different kind of data.
public interface DataItem {
int TYPE_A = 1;
int TYPE_B = 2;
int TYPE_C = 3;
protected String sortName;
int getType(); // For adapter to create view holder
String getSortName(); // For sorting
}
For different types of data class, they all need to implement from DataItem.
class DataTypeA implements DataItem {
@Override
public int getType {
return TYPE_A;
}
@Override
public String getSortName() {
return sortName;
}
}
class DataTypeB implements DataItem {
@Override
public int getType {
return TYPE_B;
}
@Override
public String getSortName() {
return sortName;
}
}
class DataTypeC implements DataItem {
@Override
public int getType {
return TYPE_C;
}
@Override
public String getSortName() {
return sortName;
}
}
In order to have different priority of sort, we can define different sortName rules. For example, A must sort before B, B must sort before C.
So we have a specific order of type A B and C, to archive this, we can add a prefix to every different instance of A B and C, let them start with different character.
Assuming that A B and C are all related with field displayName, never mind how to generate a display name, just remember, we need A < B < C.
What can we do?
Ok, it is pretty easy, see codes below.
class DataTypeA {
private void initSortName() {
sortName = '\u0000' + displayName;
}
}
class DataTypeB {
private void initSortName() {
sortName = '\u0001' + displayName;
}
}
class DataTypeC {
private void initSortName() {
sortName = '\u0002' + displayName;
}
}
Now we have orders for A B and C, but we might meet another issue about sorting, what if two A instances have the same displayName, it is OK if just want to sort them in order, but it is an unstable sorting, we need them to keep in the same order. It is also easy, just add a random string after the sortName.
However, if you just do so, you might found that, if two people both named yang, after adding the random string, it might be yang001 and yang900, now they are different, and they will keep in different order, but what if there is another person named as yang2, this will break the rules using random string, luckily we have another fix for this: adding a postfix to the sortName, then the random string. We can use the minimal character \u0000 to keep the order, so now, the yang guys might have sortName like yang'\u0000'001 and yang'\u0000'900, this will work even when there is another guy named like yang2.
See codes below:
class DataTypeA {
private void initSortName() {
sortName = '\u0000' + displayName + '\u0000' + String.valueOf(Math.random());
}
}
These are the complete rules for the sorted list.
0x04 Summary
SortedList is a helper for creating a UI related sorted list when using recycler view, with some methods you can have a powerful yet simple list with orders, even if you have some other kind of requirements like change the sort type, like sometimes I want it sorted by alphabet, sometimes I want it sorted by time, just modify the compare() method and add a different sortName like timeOrder, also some helper methods, this is completely under your ⌃.
Hope you enjoy it.
