1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.tv.dvr.ui;
18 
19 import android.support.annotation.VisibleForTesting;
20 import androidx.leanback.widget.ArrayObjectAdapter;
21 import androidx.leanback.widget.PresenterSelector;
22 import com.android.tv.common.SoftPreconditions;
23 import java.util.ArrayList;
24 import java.util.Collection;
25 import java.util.Collections;
26 import java.util.Comparator;
27 import java.util.HashSet;
28 import java.util.List;
29 import java.util.Set;
30 
31 /**
32  * Keeps a set of items sorted
33  *
34  * <p>{@code T} must have stable IDs.
35  */
36 public abstract class SortedArrayAdapter<T> extends ArrayObjectAdapter {
37     private final Comparator<T> mComparator;
38     private final int mMaxItemCount;
39     private int mExtraItemCount;
40     private final Set<Long> mIds = new HashSet<>();
41 
SortedArrayAdapter(PresenterSelector presenterSelector, Comparator<T> comparator)42     public SortedArrayAdapter(PresenterSelector presenterSelector, Comparator<T> comparator) {
43         this(presenterSelector, comparator, Integer.MAX_VALUE);
44     }
45 
SortedArrayAdapter( PresenterSelector presenterSelector, Comparator<T> comparator, int maxItemCount)46     public SortedArrayAdapter(
47             PresenterSelector presenterSelector, Comparator<T> comparator, int maxItemCount) {
48         super(presenterSelector);
49         mComparator = comparator;
50         mMaxItemCount = maxItemCount;
51         setHasStableIds(true);
52     }
53 
54     /**
55      * Sets the objects in the given collection to the adapter keeping the elements sorted.
56      *
57      * @param items A {@link Collection} of items to be set.
58      */
59     @VisibleForTesting
setInitialItems(List<T> items)60     final void setInitialItems(List<T> items) {
61         List<T> itemsCopy = new ArrayList<>(items);
62         Collections.sort(itemsCopy, mComparator);
63         for (T item : itemsCopy) {
64             add(item, true);
65             if (size() == mMaxItemCount) {
66                 break;
67             }
68         }
69     }
70 
71     /**
72      * Adds an item in sorted order to the adapter.
73      *
74      * @param item The item to add in sorted order to the adapter.
75      */
76     @Override
add(Object item)77     public final void add(Object item) {
78         add((T) item, false);
79     }
80 
isEmpty()81     public boolean isEmpty() {
82         return size() == 0;
83     }
84 
85     /**
86      * Adds an item in sorted order to the adapter.
87      *
88      * @param item The item to add in sorted order to the adapter.
89      * @param insertToEnd If items are inserted in a more or less sorted fashion, sets this
90      *     parameter to {@code true} to search insertion position from the end to save search time.
91      */
add(T item, boolean insertToEnd)92     public final void add(T item, boolean insertToEnd) {
93         long newItemId = getId(item);
94         SoftPreconditions.checkState(!mIds.contains(newItemId));
95         mIds.add(newItemId);
96         int i;
97         if (insertToEnd) {
98             i = findInsertPosition(item);
99         } else {
100             i = findInsertPositionBinary(item);
101         }
102         super.add(i, item);
103         if (mMaxItemCount < Integer.MAX_VALUE && size() > mMaxItemCount + mExtraItemCount) {
104             Object removedItem = get(mMaxItemCount);
105             remove(removedItem);
106         }
107     }
108 
109     /**
110      * Adds an extra item to the end of the adapter. The items will not be subjected to the sorted
111      * order or the maximum number of items. One or more extra items can be added to the adapter.
112      * They will be presented in their insertion order.
113      */
addExtraItem(T item)114     public int addExtraItem(T item) {
115         long newItemId = getId(item);
116         SoftPreconditions.checkState(!mIds.contains(newItemId));
117         mIds.add(newItemId);
118         super.add(item);
119         return ++mExtraItemCount;
120     }
121 
122     @Override
remove(Object item)123     public boolean remove(Object item) {
124         return removeWithId((T) item);
125     }
126 
127     /** Removes an item which has the same ID as {@code item}. */
removeWithId(T item)128     public boolean removeWithId(T item) {
129         int index = indexWithId(item);
130         return index >= 0 && index < size() && removeItems(index, 1) == 1;
131     }
132 
133     @Override
removeItems(int position, int count)134     public int removeItems(int position, int count) {
135         int upperBound = Math.min(position + count, size());
136         for (int i = position; i < upperBound; i++) {
137             mIds.remove(getId((T) get(i)));
138         }
139         if (upperBound > size() - mExtraItemCount) {
140             mExtraItemCount -= upperBound - Math.max(size() - mExtraItemCount, position);
141         }
142         return super.removeItems(position, count);
143     }
144 
145     @Override
replace(int position, Object item)146     public void replace(int position, Object item) {
147         boolean wasExtra = position >= size() - mExtraItemCount;
148         removeItems(position, 1);
149         if (!wasExtra) {
150             add(item);
151         } else {
152             addExtraItem((T) item);
153         }
154     }
155 
156     @Override
clear()157     public void clear() {
158         mIds.clear();
159         super.clear();
160     }
161 
162     /**
163      * Changes an item in the list.
164      *
165      * @param item The item to change.
166      */
change(T item)167     public final void change(T item) {
168         int oldIndex = indexWithId(item);
169         if (oldIndex != -1) {
170             T old = (T) get(oldIndex);
171             if (mComparator.compare(old, item) == 0) {
172                 replace(oldIndex, item);
173                 return;
174             }
175             remove(old);
176         }
177         add(item);
178     }
179 
180     /** Checks whether the item is in the list. */
contains(T item)181     public final boolean contains(T item) {
182         return indexWithId(item) != -1;
183     }
184 
185     @Override
getId(int position)186     public long getId(int position) {
187         return getId((T) get(position));
188     }
189 
190     /**
191      * Returns the id of the the given {@code item}, which will be used in {@link #change} to decide
192      * if the given item is already existed in the adapter.
193      *
194      * <p>The id must be stable.
195      */
getId(T item)196     protected abstract long getId(T item);
197 
indexWithId(T item)198     private int indexWithId(T item) {
199         long id = getId(item);
200         for (int i = 0; i < size() - mExtraItemCount; i++) {
201             T r = (T) get(i);
202             if (getId(r) == id) {
203                 return i;
204             }
205         }
206         return -1;
207     }
208 
209     /** Finds the position that the given item should be inserted to keep the sorted order. */
findInsertPosition(T item)210     public int findInsertPosition(T item) {
211         for (int i = size() - mExtraItemCount - 1; i >= 0; i--) {
212             T r = (T) get(i);
213             if (mComparator.compare(r, item) <= 0) {
214                 return i + 1;
215             }
216         }
217         return 0;
218     }
219 
findInsertPositionBinary(T item)220     private int findInsertPositionBinary(T item) {
221         int lb = 0;
222         int ub = size() - mExtraItemCount - 1;
223         while (lb <= ub) {
224             int mid = (lb + ub) / 2;
225             T r = (T) get(mid);
226             int compareResult = mComparator.compare(item, r);
227             if (compareResult == 0) {
228                 return mid;
229             } else if (compareResult > 0) {
230                 lb = mid + 1;
231             } else {
232                 ub = mid - 1;
233             }
234         }
235         return lb;
236     }
237 }
238