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