1 /* 2 * Copyright (C) 2009 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 * SparseArray mapping longs 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 Longs 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 LongSparseArray<E> implements Cloneable { 53 private static final Object DELETED = new Object(); 54 private boolean mGarbage = false; 55 56 private long[] mKeys; 57 private Object[] mValues; 58 private int mSize; 59 60 /** 61 * Creates a new LongSparseArray containing no mappings. 62 */ LongSparseArray()63 public LongSparseArray() { 64 this(10); 65 } 66 67 /** 68 * Creates a new LongSparseArray 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 */ LongSparseArray(int initialCapacity)74 public LongSparseArray(int initialCapacity) { 75 if (initialCapacity == 0) { 76 mKeys = EmptyArray.LONG; 77 mValues = EmptyArray.OBJECT; 78 } else { 79 mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity); 80 mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); 81 } 82 mSize = 0; 83 } 84 85 @Override 86 @SuppressWarnings("unchecked") clone()87 public LongSparseArray<E> clone() { 88 LongSparseArray<E> clone = null; 89 try { 90 clone = (LongSparseArray<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(long key)103 public E get(long 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(long key, E valueIfKeyNotFound)112 public E get(long 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(long key)125 public void delete(long 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(long)}. 138 */ remove(long key)139 public void remove(long 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 gc()153 private void gc() { 154 // Log.e("SparseArray", "gc start with " + mSize); 155 156 int n = mSize; 157 int o = 0; 158 long[] keys = mKeys; 159 Object[] values = mValues; 160 161 for (int i = 0; i < n; i++) { 162 Object val = values[i]; 163 164 if (val != DELETED) { 165 if (i != o) { 166 keys[o] = keys[i]; 167 values[o] = val; 168 values[i] = null; 169 } 170 171 o++; 172 } 173 } 174 175 mGarbage = false; 176 mSize = o; 177 178 // Log.e("SparseArray", "gc end with " + mSize); 179 } 180 181 /** 182 * Adds a mapping from the specified key to the specified value, 183 * replacing the previous mapping from the specified key if there 184 * was one. 185 */ put(long key, E value)186 public void put(long key, E value) { 187 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 188 189 if (i >= 0) { 190 mValues[i] = value; 191 } else { 192 i = ~i; 193 194 if (i < mSize && mValues[i] == DELETED) { 195 mKeys[i] = key; 196 mValues[i] = value; 197 return; 198 } 199 200 if (mGarbage && mSize >= mKeys.length) { 201 gc(); 202 203 // Search again because indices may have changed. 204 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); 205 } 206 207 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); 208 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); 209 mSize++; 210 } 211 } 212 213 /** 214 * Returns the number of key-value mappings that this LongSparseArray 215 * currently stores. 216 */ size()217 public int size() { 218 if (mGarbage) { 219 gc(); 220 } 221 222 return mSize; 223 } 224 225 /** 226 * Given an index in the range <code>0...size()-1</code>, returns 227 * the key from the <code>index</code>th key-value mapping that this 228 * LongSparseArray stores. 229 * 230 * <p>The keys corresponding to indices in ascending order are guaranteed to 231 * be in ascending order, e.g., <code>keyAt(0)</code> will return the 232 * smallest key and <code>keyAt(size()-1)</code> will return the largest 233 * key.</p> 234 */ keyAt(int index)235 public long keyAt(int index) { 236 if (mGarbage) { 237 gc(); 238 } 239 240 return mKeys[index]; 241 } 242 243 /** 244 * Given an index in the range <code>0...size()-1</code>, returns 245 * the value from the <code>index</code>th key-value mapping that this 246 * LongSparseArray stores. 247 * 248 * <p>The values corresponding to indices in ascending order are guaranteed 249 * to be associated with keys in ascending order, e.g., 250 * <code>valueAt(0)</code> will return the value associated with the 251 * smallest key and <code>valueAt(size()-1)</code> will return the value 252 * associated with the largest key.</p> 253 */ 254 @SuppressWarnings("unchecked") valueAt(int index)255 public E valueAt(int index) { 256 if (mGarbage) { 257 gc(); 258 } 259 260 return (E) mValues[index]; 261 } 262 263 /** 264 * Given an index in the range <code>0...size()-1</code>, sets a new 265 * value for the <code>index</code>th key-value mapping that this 266 * LongSparseArray stores. 267 */ setValueAt(int index, E value)268 public void setValueAt(int index, E value) { 269 if (mGarbage) { 270 gc(); 271 } 272 273 mValues[index] = value; 274 } 275 276 /** 277 * Returns the index for which {@link #keyAt} would return the 278 * specified key, or a negative number if the specified 279 * key is not mapped. 280 */ indexOfKey(long key)281 public int indexOfKey(long key) { 282 if (mGarbage) { 283 gc(); 284 } 285 286 return ContainerHelpers.binarySearch(mKeys, mSize, key); 287 } 288 289 /** 290 * Returns an index for which {@link #valueAt} would return the 291 * specified key, or a negative number if no keys map to the 292 * specified value. 293 * Beware that this is a linear search, unlike lookups by key, 294 * and that multiple keys can map to the same value and this will 295 * find only one of them. 296 */ indexOfValue(E value)297 public int indexOfValue(E value) { 298 if (mGarbage) { 299 gc(); 300 } 301 302 for (int i = 0; i < mSize; i++) { 303 if (mValues[i] == value) { 304 return i; 305 } 306 } 307 return -1; 308 } 309 310 /** 311 * Returns an index for which {@link #valueAt} would return the 312 * specified key, or a negative number if no keys map to the 313 * specified value. 314 * <p>Beware that this is a linear search, unlike lookups by key, 315 * and that multiple keys can map to the same value and this will 316 * find only one of them. 317 * <p>Note also that this method uses {@code equals} unlike {@code indexOfValue}. 318 * @hide 319 */ indexOfValueByValue(E value)320 public int indexOfValueByValue(E value) { 321 if (mGarbage) { 322 gc(); 323 } 324 325 for (int i = 0; i < mSize; i++) { 326 if (value == null) { 327 if (mValues[i] == null) { 328 return i; 329 } 330 } else { 331 if (value.equals(mValues[i])) { 332 return i; 333 } 334 } 335 } 336 return -1; 337 } 338 339 /** 340 * Removes all key-value mappings from this LongSparseArray. 341 */ clear()342 public void clear() { 343 int n = mSize; 344 Object[] values = mValues; 345 346 for (int i = 0; i < n; i++) { 347 values[i] = null; 348 } 349 350 mSize = 0; 351 mGarbage = false; 352 } 353 354 /** 355 * Puts a key/value pair into the array, optimizing for the case where 356 * the key is greater than all existing keys in the array. 357 */ append(long key, E value)358 public void append(long key, E value) { 359 if (mSize != 0 && key <= mKeys[mSize - 1]) { 360 put(key, value); 361 return; 362 } 363 364 if (mGarbage && mSize >= mKeys.length) { 365 gc(); 366 } 367 368 mKeys = GrowingArrayUtils.append(mKeys, mSize, key); 369 mValues = GrowingArrayUtils.append(mValues, mSize, value); 370 mSize++; 371 } 372 373 /** 374 * {@inheritDoc} 375 * 376 * <p>This implementation composes a string by iterating over its mappings. If 377 * this map contains itself as a value, the string "(this Map)" 378 * will appear in its place. 379 */ 380 @Override toString()381 public String toString() { 382 if (size() <= 0) { 383 return "{}"; 384 } 385 386 StringBuilder buffer = new StringBuilder(mSize * 28); 387 buffer.append('{'); 388 for (int i=0; i<mSize; i++) { 389 if (i > 0) { 390 buffer.append(", "); 391 } 392 long key = keyAt(i); 393 buffer.append(key); 394 buffer.append('='); 395 Object value = valueAt(i); 396 if (value != this) { 397 buffer.append(value); 398 } else { 399 buffer.append("(this Map)"); 400 } 401 } 402 buffer.append('}'); 403 return buffer.toString(); 404 } 405 } 406