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