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