811a5a4a |
1 | /* |
2 | * Copyright (C) 2011 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 android.support.v2.app; |
18 | |
19 | import android.util.Log; |
20 | |
21 | /** |
22 | * A copy of Honeycomb's SparseArray, only so we can have the removeAt() method. |
23 | */ |
24 | public class HCSparseArray<E> { |
25 | private static final Object DELETED = new Object(); |
26 | private boolean mGarbage = false; |
27 | |
28 | /** |
29 | * Creates a new SparseArray containing no mappings. |
30 | */ |
31 | public HCSparseArray() { |
32 | this(10); |
33 | } |
34 | |
35 | /** |
36 | * Creates a new SparseArray containing no mappings that will not |
37 | * require any additional memory allocation to store the specified |
38 | * number of mappings. |
39 | */ |
40 | public HCSparseArray(int initialCapacity) { |
41 | initialCapacity = idealIntArraySize(initialCapacity); |
42 | |
43 | mKeys = new int[initialCapacity]; |
44 | mValues = new Object[initialCapacity]; |
45 | mSize = 0; |
46 | } |
47 | |
48 | /** |
49 | * Gets the Object mapped from the specified key, or <code>null</code> |
50 | * if no such mapping has been made. |
51 | */ |
52 | public E get(int key) { |
53 | return get(key, null); |
54 | } |
55 | |
56 | /** |
57 | * Gets the Object mapped from the specified key, or the specified Object |
58 | * if no such mapping has been made. |
59 | */ |
60 | public E get(int key, E valueIfKeyNotFound) { |
61 | int i = binarySearch(mKeys, 0, mSize, key); |
62 | |
63 | if (i < 0 || mValues[i] == DELETED) { |
64 | return valueIfKeyNotFound; |
65 | } else { |
66 | return (E) mValues[i]; |
67 | } |
68 | } |
69 | |
70 | /** |
71 | * Removes the mapping from the specified key, if there was any. |
72 | */ |
73 | public void delete(int key) { |
74 | int i = binarySearch(mKeys, 0, mSize, key); |
75 | |
76 | if (i >= 0) { |
77 | if (mValues[i] != DELETED) { |
78 | mValues[i] = DELETED; |
79 | mGarbage = true; |
80 | } |
81 | } |
82 | } |
83 | |
84 | /** |
85 | * Alias for {@link #delete(int)}. |
86 | */ |
87 | public void remove(int key) { |
88 | delete(key); |
89 | } |
90 | |
91 | /** |
92 | * Removes the mapping at the specified index. |
93 | */ |
94 | public void removeAt(int index) { |
95 | if (mValues[index] != DELETED) { |
96 | mValues[index] = DELETED; |
97 | mGarbage = true; |
98 | } |
99 | } |
100 | |
101 | private void gc() { |
102 | // Log.e("SparseArray", "gc start with " + mSize); |
103 | |
104 | int n = mSize; |
105 | int o = 0; |
106 | int[] keys = mKeys; |
107 | Object[] values = mValues; |
108 | |
109 | for (int i = 0; i < n; i++) { |
110 | Object val = values[i]; |
111 | |
112 | if (val != DELETED) { |
113 | if (i != o) { |
114 | keys[o] = keys[i]; |
115 | values[o] = val; |
116 | } |
117 | |
118 | o++; |
119 | } |
120 | } |
121 | |
122 | mGarbage = false; |
123 | mSize = o; |
124 | |
125 | // Log.e("SparseArray", "gc end with " + mSize); |
126 | } |
127 | |
128 | /** |
129 | * Adds a mapping from the specified key to the specified value, |
130 | * replacing the previous mapping from the specified key if there |
131 | * was one. |
132 | */ |
133 | public void put(int key, E value) { |
134 | int i = binarySearch(mKeys, 0, mSize, key); |
135 | |
136 | if (i >= 0) { |
137 | mValues[i] = value; |
138 | } else { |
139 | i = ~i; |
140 | |
141 | if (i < mSize && mValues[i] == DELETED) { |
142 | mKeys[i] = key; |
143 | mValues[i] = value; |
144 | return; |
145 | } |
146 | |
147 | if (mGarbage && mSize >= mKeys.length) { |
148 | gc(); |
149 | |
150 | // Search again because indices may have changed. |
151 | i = ~binarySearch(mKeys, 0, mSize, key); |
152 | } |
153 | |
154 | if (mSize >= mKeys.length) { |
155 | int n = idealIntArraySize(mSize + 1); |
156 | |
157 | int[] nkeys = new int[n]; |
158 | Object[] nvalues = new Object[n]; |
159 | |
160 | // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); |
161 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
162 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
163 | |
164 | mKeys = nkeys; |
165 | mValues = nvalues; |
166 | } |
167 | |
168 | if (mSize - i != 0) { |
169 | // Log.e("SparseArray", "move " + (mSize - i)); |
170 | System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); |
171 | System.arraycopy(mValues, i, mValues, i + 1, mSize - i); |
172 | } |
173 | |
174 | mKeys[i] = key; |
175 | mValues[i] = value; |
176 | mSize++; |
177 | } |
178 | } |
179 | |
180 | /** |
181 | * Returns the number of key-value mappings that this SparseArray |
182 | * currently stores. |
183 | */ |
184 | public int size() { |
185 | if (mGarbage) { |
186 | gc(); |
187 | } |
188 | |
189 | return mSize; |
190 | } |
191 | |
192 | /** |
193 | * Given an index in the range <code>0...size()-1</code>, returns |
194 | * the key from the <code>index</code>th key-value mapping that this |
195 | * SparseArray stores. |
196 | */ |
197 | public int keyAt(int index) { |
198 | if (mGarbage) { |
199 | gc(); |
200 | } |
201 | |
202 | return mKeys[index]; |
203 | } |
204 | |
205 | /** |
206 | * Given an index in the range <code>0...size()-1</code>, returns |
207 | * the value from the <code>index</code>th key-value mapping that this |
208 | * SparseArray stores. |
209 | */ |
210 | public E valueAt(int index) { |
211 | if (mGarbage) { |
212 | gc(); |
213 | } |
214 | |
215 | return (E) mValues[index]; |
216 | } |
217 | |
218 | /** |
219 | * Given an index in the range <code>0...size()-1</code>, sets a new |
220 | * value for the <code>index</code>th key-value mapping that this |
221 | * SparseArray stores. |
222 | */ |
223 | public void setValueAt(int index, E value) { |
224 | if (mGarbage) { |
225 | gc(); |
226 | } |
227 | |
228 | mValues[index] = value; |
229 | } |
230 | |
231 | /** |
232 | * Returns the index for which {@link #keyAt} would return the |
233 | * specified key, or a negative number if the specified |
234 | * key is not mapped. |
235 | */ |
236 | public int indexOfKey(int key) { |
237 | if (mGarbage) { |
238 | gc(); |
239 | } |
240 | |
241 | return binarySearch(mKeys, 0, mSize, key); |
242 | } |
243 | |
244 | /** |
245 | * Returns an index for which {@link #valueAt} would return the |
246 | * specified key, or a negative number if no keys map to the |
247 | * specified value. |
248 | * Beware that this is a linear search, unlike lookups by key, |
249 | * and that multiple keys can map to the same value and this will |
250 | * find only one of them. |
251 | */ |
252 | public int indexOfValue(E value) { |
253 | if (mGarbage) { |
254 | gc(); |
255 | } |
256 | |
257 | for (int i = 0; i < mSize; i++) |
258 | if (mValues[i] == value) |
259 | return i; |
260 | |
261 | return -1; |
262 | } |
263 | |
264 | /** |
265 | * Removes all key-value mappings from this SparseArray. |
266 | */ |
267 | public void clear() { |
268 | int n = mSize; |
269 | Object[] values = mValues; |
270 | |
271 | for (int i = 0; i < n; i++) { |
272 | values[i] = null; |
273 | } |
274 | |
275 | mSize = 0; |
276 | mGarbage = false; |
277 | } |
278 | |
279 | /** |
280 | * Puts a key/value pair into the array, optimizing for the case where |
281 | * the key is greater than all existing keys in the array. |
282 | */ |
283 | public void append(int key, E value) { |
284 | if (mSize != 0 && key <= mKeys[mSize - 1]) { |
285 | put(key, value); |
286 | return; |
287 | } |
288 | |
289 | if (mGarbage && mSize >= mKeys.length) { |
290 | gc(); |
291 | } |
292 | |
293 | int pos = mSize; |
294 | if (pos >= mKeys.length) { |
295 | int n = idealIntArraySize(pos + 1); |
296 | |
297 | int[] nkeys = new int[n]; |
298 | Object[] nvalues = new Object[n]; |
299 | |
300 | // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); |
301 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
302 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
303 | |
304 | mKeys = nkeys; |
305 | mValues = nvalues; |
306 | } |
307 | |
308 | mKeys[pos] = key; |
309 | mValues[pos] = value; |
310 | mSize = pos + 1; |
311 | } |
312 | |
313 | private static int binarySearch(int[] a, int start, int len, int key) { |
314 | int high = start + len, low = start - 1, guess; |
315 | |
316 | while (high - low > 1) { |
317 | guess = (high + low) / 2; |
318 | |
319 | if (a[guess] < key) |
320 | low = guess; |
321 | else |
322 | high = guess; |
323 | } |
324 | |
325 | if (high == start + len) |
326 | return ~(start + len); |
327 | else if (a[high] == key) |
328 | return high; |
329 | else |
330 | return ~high; |
331 | } |
332 | |
333 | private void checkIntegrity() { |
334 | for (int i = 1; i < mSize; i++) { |
335 | if (mKeys[i] <= mKeys[i - 1]) { |
336 | for (int j = 0; j < mSize; j++) { |
337 | Log.e("FAIL", j + ": " + mKeys[j] + " -> " + mValues[j]); |
338 | } |
339 | |
340 | throw new RuntimeException(); |
341 | } |
342 | } |
343 | } |
344 | |
345 | static int idealByteArraySize(int need) { |
346 | for (int i = 4; i < 32; i++) |
347 | if (need <= (1 << i) - 12) |
348 | return (1 << i) - 12; |
349 | |
350 | return need; |
351 | } |
352 | |
353 | static int idealIntArraySize(int need) { |
354 | return idealByteArraySize(need * 4) / 4; |
355 | } |
356 | |
357 | private int[] mKeys; |
358 | private Object[] mValues; |
359 | private int mSize; |
360 | } |