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 android.support.v17.leanback.widget.ArrayObjectAdapter;
21 import android.support.v17.leanback.widget.PresenterSelector;
22 
23 import java.util.ArrayList;
24 import java.util.Collection;
25 import java.util.Collections;
26 import java.util.Comparator;
27 import java.util.List;
28 
29 /**
30  * Keeps a set of items sorted
31  *
32  * <p>{@code T} must have stable IDs.
33  */
34 public abstract class SortedArrayAdapter<T> extends ArrayObjectAdapter {
35     private final Comparator<T> mComparator;
36     private final int mMaxItemCount;
37     private int mExtraItemCount;
38 
SortedArrayAdapter(PresenterSelector presenterSelector, Comparator<T> comparator)39     SortedArrayAdapter(PresenterSelector presenterSelector, Comparator<T> comparator) {
40         this(presenterSelector, comparator, Integer.MAX_VALUE);
41     }
42 
SortedArrayAdapter(PresenterSelector presenterSelector, Comparator<T> comparator, int maxItemCount)43     SortedArrayAdapter(PresenterSelector presenterSelector, Comparator<T> comparator,
44             int maxItemCount) {
45         super(presenterSelector);
46         mComparator = comparator;
47         mMaxItemCount = maxItemCount;
48     }
49 
50     /**
51      * Sets the objects in the given collection to the adapter keeping the elements sorted.
52      *
53      * @param items A {@link Collection} of items to be set.
54      */
55     @VisibleForTesting
setInitialItems(List<T> items)56     final void setInitialItems(List<T> items) {
57         List<T> itemsCopy = new ArrayList<>(items);
58         Collections.sort(itemsCopy, mComparator);
59         addAll(0, itemsCopy.subList(0, Math.min(mMaxItemCount, itemsCopy.size())));
60     }
61 
62     /**
63      * Adds an item in sorted order to the adapter.
64      *
65      * @param item The item to add in sorted order to the adapter.
66      */
67     @Override
add(Object item)68     public final void add(Object item) {
69         add((T) item, false);
70     }
71 
isEmpty()72     public boolean isEmpty() {
73         return size() == 0;
74     }
75 
76     /**
77      * Adds an item in sorted order to the adapter.
78      *
79      * @param item The item to add in sorted order to the adapter.
80      * @param insertToEnd If items are inserted in a more or less sorted fashion,
81      *                    sets this parameter to {@code true} to search insertion position from
82      *                    the end to save search time.
83      */
add(T item, boolean insertToEnd)84     public final void add(T item, boolean insertToEnd) {
85         int i;
86         if (insertToEnd) {
87             i = findInsertPosition(item);
88         } else {
89             i = findInsertPositionBinary(item);
90         }
91         super.add(i, item);
92         if (size() > mMaxItemCount + mExtraItemCount) {
93             removeItems(mMaxItemCount, size() - mMaxItemCount - mExtraItemCount);
94         }
95     }
96 
97     /**
98      * Adds an extra item to the end of the adapter. The items will not be subjected to the sorted
99      * order or the maximum number of items. One or more extra items can be added to the adapter.
100      * They will be presented in their insertion order.
101      */
addExtraItem(T item)102     public int addExtraItem(T item) {
103         super.add(item);
104         return ++mExtraItemCount;
105     }
106 
107     /**
108      * Removes an item which has the same ID as {@code item}.
109      */
removeWithId(T item)110     public boolean removeWithId(T item) {
111         int index = indexWithTypeAndId(item);
112         return index >= 0 && index < size() && remove(get(index));
113     }
114 
115     /**
116      * Change an item in the list.
117      * @param item The item to change.
118      */
change(T item)119     public final void change(T item) {
120         int oldIndex = indexWithTypeAndId(item);
121         if (oldIndex != -1) {
122             T old = (T) get(oldIndex);
123             if (mComparator.compare(old, item) == 0) {
124                 replace(oldIndex, item);
125                 return;
126             }
127             removeItems(oldIndex, 1);
128         }
129         add(item);
130     }
131 
132     /**
133      * Returns the id of the the given {@code item}, which will be used in {@link #change} to
134      * decide if the given item is already existed in the adapter.
135      *
136      * The id must be stable.
137      */
getId(T item)138     abstract long getId(T item);
139 
indexWithTypeAndId(T item)140     private int indexWithTypeAndId(T item) {
141         long id = getId(item);
142         for (int i = 0; i < size() - mExtraItemCount; i++) {
143             T r = (T) get(i);
144             if (r.getClass() == item.getClass() && getId(r) == id) {
145                 return i;
146             }
147         }
148         return -1;
149     }
150 
151     /**
152      * Finds the position that the given item should be inserted to keep the sorted order.
153      */
findInsertPosition(T item)154     public int findInsertPosition(T item) {
155         for (int i = size() - mExtraItemCount - 1; i >=0; i--) {
156             T r = (T) get(i);
157             if (mComparator.compare(r, item) <= 0) {
158                 return i + 1;
159             }
160         }
161         return 0;
162     }
163 
findInsertPositionBinary(T item)164     private int findInsertPositionBinary(T item) {
165         int lb = 0;
166         int ub = size() - mExtraItemCount - 1;
167         while (lb <= ub) {
168             int mid = (lb + ub) / 2;
169             T r = (T) get(mid);
170             int compareResult = mComparator.compare(item, r);
171             if (compareResult == 0) {
172                 return mid;
173             } else if (compareResult > 0) {
174                 lb = mid + 1;
175             } else {
176                 ub = mid - 1;
177             }
178         }
179         return lb;
180     }
181 }