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