2 * Copyright (C) 2011 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package android.support.v2.app;
19 import android.util.Log;
22 * A copy of Honeycomb's SparseArray, only so we can have the removeAt() method.
24 public class HCSparseArray<E> {
25 private static final Object DELETED = new Object();
26 private boolean mGarbage = false;
29 * Creates a new SparseArray containing no mappings.
31 public HCSparseArray() {
36 * Creates a new SparseArray containing no mappings that will not
37 * require any additional memory allocation to store the specified
40 public HCSparseArray(int initialCapacity) {
41 initialCapacity = idealIntArraySize(initialCapacity);
43 mKeys = new int[initialCapacity];
44 mValues = new Object[initialCapacity];
49 * Gets the Object mapped from the specified key, or <code>null</code>
50 * if no such mapping has been made.
52 public E get(int key) {
53 return get(key, null);
57 * Gets the Object mapped from the specified key, or the specified Object
58 * if no such mapping has been made.
60 public E get(int key, E valueIfKeyNotFound) {
61 int i = binarySearch(mKeys, 0, mSize, key);
63 if (i < 0 || mValues[i] == DELETED) {
64 return valueIfKeyNotFound;
66 return (E) mValues[i];
71 * Removes the mapping from the specified key, if there was any.
73 public void delete(int key) {
74 int i = binarySearch(mKeys, 0, mSize, key);
77 if (mValues[i] != DELETED) {
85 * Alias for {@link #delete(int)}.
87 public void remove(int key) {
92 * Removes the mapping at the specified index.
94 public void removeAt(int index) {
95 if (mValues[index] != DELETED) {
96 mValues[index] = DELETED;
102 // Log.e("SparseArray", "gc start with " + mSize);
107 Object[] values = mValues;
109 for (int i = 0; i < n; i++) {
110 Object val = values[i];
112 if (val != DELETED) {
125 // Log.e("SparseArray", "gc end with " + mSize);
129 * Adds a mapping from the specified key to the specified value,
130 * replacing the previous mapping from the specified key if there
133 public void put(int key, E value) {
134 int i = binarySearch(mKeys, 0, mSize, key);
141 if (i < mSize && mValues[i] == DELETED) {
147 if (mGarbage && mSize >= mKeys.length) {
150 // Search again because indices may have changed.
151 i = ~binarySearch(mKeys, 0, mSize, key);
154 if (mSize >= mKeys.length) {
155 int n = idealIntArraySize(mSize + 1);
157 int[] nkeys = new int[n];
158 Object[] nvalues = new Object[n];
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);
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);
181 * Returns the number of key-value mappings that this SparseArray
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.
197 public int keyAt(int index) {
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.
210 public E valueAt(int index) {
215 return (E) mValues[index];
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.
223 public void setValueAt(int index, E value) {
228 mValues[index] = value;
232 * Returns the index for which {@link #keyAt} would return the
233 * specified key, or a negative number if the specified
236 public int indexOfKey(int key) {
241 return binarySearch(mKeys, 0, mSize, key);
245 * Returns an index for which {@link #valueAt} would return the
246 * specified key, or a negative number if no keys map to the
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.
252 public int indexOfValue(E value) {
257 for (int i = 0; i < mSize; i++)
258 if (mValues[i] == value)
265 * Removes all key-value mappings from this SparseArray.
267 public void clear() {
269 Object[] values = mValues;
271 for (int i = 0; i < n; i++) {
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.
283 public void append(int key, E value) {
284 if (mSize != 0 && key <= mKeys[mSize - 1]) {
289 if (mGarbage && mSize >= mKeys.length) {
294 if (pos >= mKeys.length) {
295 int n = idealIntArraySize(pos + 1);
297 int[] nkeys = new int[n];
298 Object[] nvalues = new Object[n];
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);
309 mValues[pos] = value;
313 private static int binarySearch(int[] a, int start, int len, int key) {
314 int high = start + len, low = start - 1, guess;
316 while (high - low > 1) {
317 guess = (high + low) / 2;
325 if (high == start + len)
326 return ~(start + len);
327 else if (a[high] == key)
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]);
340 throw new RuntimeException();
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;
353 static int idealIntArraySize(int need) {
354 return idealByteArraySize(need * 4) / 4;
358 private Object[] mValues;