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