frameworks/base/core/java/android/util/SparseArray.java

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