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