• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
17 package android.util;
18 
19 import com.android.internal.util.ArrayUtils;
20 import com.android.internal.util.GrowingArrayUtils;
21 
22 import libcore.util.EmptyArray;
23 
24 /**
25  * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
26  * there can be gaps in the indices.  It is intended to be more memory efficient
27  * than using a HashMap to map Integers to Objects, both because it avoids
28  * auto-boxing keys and its data structure doesn't rely on an extra entry object
29  * for each mapping.
30  *
31  * <p>Note that this container keeps its mappings in an array data structure,
32  * using a binary search to find keys.  The implementation is not intended to be appropriate for
33  * data structures
34  * that may contain large numbers of items.  It is generally slower than a traditional
35  * HashMap, since lookups require a binary search and adds and removes require inserting
36  * and deleting entries in the array.  For containers holding up to hundreds of items,
37  * the performance difference is not significant, less than 50%.</p>
38  *
39  * <p>To help with performance, the container includes an optimization when removing
40  * keys: instead of compacting its array immediately, it leaves the removed entry marked
41  * as deleted.  The entry can then be re-used for the same key, or compacted later in
42  * a single garbage collection step of all removed entries.  This garbage collection will
43  * need to be performed at any time the array needs to be grown or the the map size or
44  * entry values are retrieved.</p>
45  *
46  * <p>It is possible to iterate over the items in this container using
47  * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
48  * <code>keyAt(int)</code> with ascending values of the index will return the
49  * keys in ascending order, or the values corresponding to the keys in ascending
50  * order in the case of <code>valueAt(int)</code>.</p>
51  */
52 public class SparseArray<E> implements Cloneable {
53     private static final Object DELETED = new Object();
54     private boolean mGarbage = false;
55 
56     private int[] mKeys;
57     private Object[] mValues;
58     private int mSize;
59 
60     /**
61      * Creates a new SparseArray containing no mappings.
62      */
SparseArray()63     public SparseArray() {
64         this(10);
65     }
66 
67     /**
68      * Creates a new SparseArray containing no mappings that will not
69      * require any additional memory allocation to store the specified
70      * number of mappings.  If you supply an initial capacity of 0, the
71      * sparse array will be initialized with a light-weight representation
72      * not requiring any additional array allocations.
73      */
SparseArray(int initialCapacity)74     public SparseArray(int initialCapacity) {
75         if (initialCapacity == 0) {
76             mKeys = EmptyArray.INT;
77             mValues = EmptyArray.OBJECT;
78         } else {
79             mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
80             mKeys = new int[mValues.length];
81         }
82         mSize = 0;
83     }
84 
85     @Override
86     @SuppressWarnings("unchecked")
clone()87     public SparseArray<E> clone() {
88         SparseArray<E> clone = null;
89         try {
90             clone = (SparseArray<E>) super.clone();
91             clone.mKeys = mKeys.clone();
92             clone.mValues = mValues.clone();
93         } catch (CloneNotSupportedException cnse) {
94             /* ignore */
95         }
96         return clone;
97     }
98 
99     /**
100      * Gets the Object mapped from the specified key, or <code>null</code>
101      * if no such mapping has been made.
102      */
get(int key)103     public E get(int key) {
104         return get(key, null);
105     }
106 
107     /**
108      * Gets the Object mapped from the specified key, or the specified Object
109      * if no such mapping has been made.
110      */
111     @SuppressWarnings("unchecked")
get(int key, E valueIfKeyNotFound)112     public E get(int key, E valueIfKeyNotFound) {
113         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
114 
115         if (i < 0 || mValues[i] == DELETED) {
116             return valueIfKeyNotFound;
117         } else {
118             return (E) mValues[i];
119         }
120     }
121 
122     /**
123      * Removes the mapping from the specified key, if there was any.
124      */
delete(int key)125     public void delete(int key) {
126         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
127 
128         if (i >= 0) {
129             if (mValues[i] != DELETED) {
130                 mValues[i] = DELETED;
131                 mGarbage = true;
132             }
133         }
134     }
135 
136     /**
137      * Alias for {@link #delete(int)}.
138      */
remove(int key)139     public void remove(int key) {
140         delete(key);
141     }
142 
143     /**
144      * Removes the mapping at the specified index.
145      */
removeAt(int index)146     public void removeAt(int index) {
147         if (mValues[index] != DELETED) {
148             mValues[index] = DELETED;
149             mGarbage = true;
150         }
151     }
152 
153     /**
154      * Remove a range of mappings as a batch.
155      *
156      * @param index Index to begin at
157      * @param size Number of mappings to remove
158      */
removeAtRange(int index, int size)159     public void removeAtRange(int index, int size) {
160         final int end = Math.min(mSize, index + size);
161         for (int i = index; i < end; i++) {
162             removeAt(i);
163         }
164     }
165 
gc()166     private void gc() {
167         // Log.e("SparseArray", "gc start with " + mSize);
168 
169         int n = mSize;
170         int o = 0;
171         int[] keys = mKeys;
172         Object[] values = mValues;
173 
174         for (int i = 0; i < n; i++) {
175             Object val = values[i];
176 
177             if (val != DELETED) {
178                 if (i != o) {
179                     keys[o] = keys[i];
180                     values[o] = val;
181                     values[i] = null;
182                 }
183 
184                 o++;
185             }
186         }
187 
188         mGarbage = false;
189         mSize = o;
190 
191         // Log.e("SparseArray", "gc end with " + mSize);
192     }
193 
194     /**
195      * Adds a mapping from the specified key to the specified value,
196      * replacing the previous mapping from the specified key if there
197      * was one.
198      */
put(int key, E value)199     public void put(int key, E value) {
200         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
201 
202         if (i >= 0) {
203             mValues[i] = value;
204         } else {
205             i = ~i;
206 
207             if (i < mSize && mValues[i] == DELETED) {
208                 mKeys[i] = key;
209                 mValues[i] = value;
210                 return;
211             }
212 
213             if (mGarbage && mSize >= mKeys.length) {
214                 gc();
215 
216                 // Search again because indices may have changed.
217                 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
218             }
219 
220             mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
221             mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
222             mSize++;
223         }
224     }
225 
226     /**
227      * Returns the number of key-value mappings that this SparseArray
228      * currently stores.
229      */
size()230     public int size() {
231         if (mGarbage) {
232             gc();
233         }
234 
235         return mSize;
236     }
237 
238     /**
239      * Given an index in the range <code>0...size()-1</code>, returns
240      * the key from the <code>index</code>th key-value mapping that this
241      * SparseArray stores.
242      *
243      * <p>The keys corresponding to indices in ascending order are guaranteed to
244      * be in ascending order, e.g., <code>keyAt(0)</code> will return the
245      * smallest key and <code>keyAt(size()-1)</code> will return the largest
246      * key.</p>
247      */
keyAt(int index)248     public int keyAt(int index) {
249         if (mGarbage) {
250             gc();
251         }
252 
253         return mKeys[index];
254     }
255 
256     /**
257      * Given an index in the range <code>0...size()-1</code>, returns
258      * the value from the <code>index</code>th key-value mapping that this
259      * SparseArray stores.
260      *
261      * <p>The values corresponding to indices in ascending order are guaranteed
262      * to be associated with keys in ascending order, e.g.,
263      * <code>valueAt(0)</code> will return the value associated with the
264      * smallest key and <code>valueAt(size()-1)</code> will return the value
265      * associated with the largest key.</p>
266      */
267     @SuppressWarnings("unchecked")
valueAt(int index)268     public E valueAt(int index) {
269         if (mGarbage) {
270             gc();
271         }
272 
273         return (E) mValues[index];
274     }
275 
276     /**
277      * Given an index in the range <code>0...size()-1</code>, sets a new
278      * value for the <code>index</code>th key-value mapping that this
279      * SparseArray stores.
280      */
setValueAt(int index, E value)281     public void setValueAt(int index, E value) {
282         if (mGarbage) {
283             gc();
284         }
285 
286         mValues[index] = value;
287     }
288 
289     /**
290      * Returns the index for which {@link #keyAt} would return the
291      * specified key, or a negative number if the specified
292      * key is not mapped.
293      */
indexOfKey(int key)294     public int indexOfKey(int key) {
295         if (mGarbage) {
296             gc();
297         }
298 
299         return ContainerHelpers.binarySearch(mKeys, mSize, key);
300     }
301 
302     /**
303      * Returns an index for which {@link #valueAt} would return the
304      * specified key, or a negative number if no keys map to the
305      * specified value.
306      * <p>Beware that this is a linear search, unlike lookups by key,
307      * and that multiple keys can map to the same value and this will
308      * find only one of them.
309      * <p>Note also that unlike most collections' {@code indexOf} methods,
310      * this method compares values using {@code ==} rather than {@code equals}.
311      */
indexOfValue(E value)312     public int indexOfValue(E value) {
313         if (mGarbage) {
314             gc();
315         }
316 
317         for (int i = 0; i < mSize; i++)
318             if (mValues[i] == value)
319                 return i;
320 
321         return -1;
322     }
323 
324     /**
325      * Removes all key-value mappings from this SparseArray.
326      */
clear()327     public void clear() {
328         int n = mSize;
329         Object[] values = mValues;
330 
331         for (int i = 0; i < n; i++) {
332             values[i] = null;
333         }
334 
335         mSize = 0;
336         mGarbage = false;
337     }
338 
339     /**
340      * Puts a key/value pair into the array, optimizing for the case where
341      * the key is greater than all existing keys in the array.
342      */
append(int key, E value)343     public void append(int key, E value) {
344         if (mSize != 0 && key <= mKeys[mSize - 1]) {
345             put(key, value);
346             return;
347         }
348 
349         if (mGarbage && mSize >= mKeys.length) {
350             gc();
351         }
352 
353         mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
354         mValues = GrowingArrayUtils.append(mValues, mSize, value);
355         mSize++;
356     }
357 
358     /**
359      * {@inheritDoc}
360      *
361      * <p>This implementation composes a string by iterating over its mappings. If
362      * this map contains itself as a value, the string "(this Map)"
363      * will appear in its place.
364      */
365     @Override
toString()366     public String toString() {
367         if (size() <= 0) {
368             return "{}";
369         }
370 
371         StringBuilder buffer = new StringBuilder(mSize * 28);
372         buffer.append('{');
373         for (int i=0; i<mSize; i++) {
374             if (i > 0) {
375                 buffer.append(", ");
376             }
377             int key = keyAt(i);
378             buffer.append(key);
379             buffer.append('=');
380             Object value = valueAt(i);
381             if (value != this) {
382                 buffer.append(value);
383             } else {
384                 buffer.append("(this Map)");
385             }
386         }
387         buffer.append('}');
388         return buffer.toString();
389     }
390 }
391