2 * Copyright (C) 2006 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.
19 import com.android.internal.util.ArrayUtils;
22 * SparseArrays map integers to Objects. Unlike a normal array of Objects,
23 * there can be gaps in the indices. It is intended to be more efficient
24 * than using a HashMap to map Integers to Objects.
26 public class SparseArray<E> {
27 private static final Object DELETED = new Object();
28 private boolean mGarbage = false;
31 * Creates a new SparseArray containing no mappings.
33 public SparseArray() {
38 * Creates a new SparseArray containing no mappings that will not
39 * require any additional memory allocation to store the specified
42 public SparseArray(int initialCapacity) {
43 initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
45 mKeys = new int[initialCapacity];
46 mValues = new Object[initialCapacity];
51 * Gets the Object mapped from the specified key, or <code>null</code>
52 * if no such mapping has been made.
54 public E get(int key) {
55 return get(key, null);
59 * Gets the Object mapped from the specified key, or the specified Object
60 * if no such mapping has been made.
62 public E get(int key, E valueIfKeyNotFound) {
63 int i = binarySearch(mKeys, 0, mSize, key);
65 if (i < 0 || mValues[i] == DELETED) {
66 return valueIfKeyNotFound;
68 return (E) mValues[i];
73 * Removes the mapping from the specified key, if there was any.
75 public void delete(int key) {
76 int i = binarySearch(mKeys, 0, mSize, key);
79 if (mValues[i] != DELETED) {
87 * Alias for {@link #delete(int)}.
89 public void remove(int key) {
94 // Log.e("SparseArray", "gc start with " + mSize);
99 Object[] values = mValues;
101 for (int i = 0; i < n; i++) {
102 Object val = values[i];
104 if (val != DELETED) {
117 // Log.e("SparseArray", "gc end with " + mSize);
121 * Adds a mapping from the specified key to the specified value,
122 * replacing the previous mapping from the specified key if there
125 public void put(int key, E value) {
126 int i = binarySearch(mKeys, 0, mSize, key);
133 if (i < mSize && mValues[i] == DELETED) {
139 if (mGarbage && mSize >= mKeys.length) {
142 // Search again because indices may have changed.
143 i = ~binarySearch(mKeys, 0, mSize, key);
146 if (mSize >= mKeys.length) {
147 int n = ArrayUtils.idealIntArraySize(mSize + 1);
149 int[] nkeys = new int[n];
150 Object[] nvalues = new Object[n];
152 // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
153 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
154 System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
160 if (mSize - i != 0) {
161 // Log.e("SparseArray", "move " + (mSize - i));
162 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
163 System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
173 * Returns the number of key-value mappings that this SparseArray
185 * Given an index in the range <code>0...size()-1</code>, returns
186 * the key from the <code>index</code>th key-value mapping that this
187 * SparseArray stores.
189 public int keyAt(int index) {
198 * Given an index in the range <code>0...size()-1</code>, returns
199 * the value from the <code>index</code>th key-value mapping that this
200 * SparseArray stores.
202 public E valueAt(int index) {
207 return (E) mValues[index];
211 * Given an index in the range <code>0...size()-1</code>, sets a new
212 * value for the <code>index</code>th key-value mapping that this
213 * SparseArray stores.
215 public void setValueAt(int index, E value) {
220 mValues[index] = value;
224 * Returns the index for which {@link #keyAt} would return the
225 * specified key, or a negative number if the specified
228 public int indexOfKey(int key) {
233 return binarySearch(mKeys, 0, mSize, key);
237 * Returns an index for which {@link #valueAt} would return the
238 * specified key, or a negative number if no keys map to the
240 * Beware that this is a linear search, unlike lookups by key,
241 * and that multiple keys can map to the same value and this will
242 * find only one of them.
244 public int indexOfValue(E value) {
249 for (int i = 0; i < mSize; i++)
250 if (mValues[i] == value)
257 * Removes all key-value mappings from this SparseArray.
259 public void clear() {
261 Object[] values = mValues;
263 for (int i = 0; i < n; i++) {
272 * Puts a key/value pair into the array, optimizing for the case where
273 * the key is greater than all existing keys in the array.
275 public void append(int key, E value) {
276 if (mSize != 0 && key <= mKeys[mSize - 1]) {
281 if (mGarbage && mSize >= mKeys.length) {
286 if (pos >= mKeys.length) {
287 int n = ArrayUtils.idealIntArraySize(pos + 1);
289 int[] nkeys = new int[n];
290 Object[] nvalues = new Object[n];
292 // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
293 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
294 System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
301 mValues[pos] = value;
305 private static int binarySearch(int[] a, int start, int len, int key) {
306 int high = start + len, low = start - 1, guess;
308 while (high - low > 1) {
309 guess = (high + low) / 2;
317 if (high == start + len)
318 return ~(start + len);
319 else if (a[high] == key)
325 private void checkIntegrity() {
326 for (int i = 1; i < mSize; i++) {
327 if (mKeys[i] <= mKeys[i - 1]) {
328 for (int j = 0; j < mSize; j++) {
329 Log.e("FAIL", j + ": " + mKeys[j] + " -> " + mValues[j]);
332 throw new RuntimeException();
338 private Object[] mValues;