apps/AndroidSupportV2/src/android/support/v2/app/HCSparseArray.java

   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
  17 package android.support.v2.app;
  18
  19 import android.util.Log;
  20
  21 /**
  22  * A copy of Honeycomb's SparseArray, only so we can have the removeAt() method.
  23  */
  24 public class HCSparseArray<E> {
  25     private static final Object DELETED = new Object();
  26     private boolean mGarbage = false;
  27
  28     /**
  29      * Creates a new SparseArray containing no mappings.
  30      */
  31     public HCSparseArray() {
  32         this(10);
  33     }
  34
  35     /**
  36      * Creates a new SparseArray containing no mappings that will not
  37      * require any additional memory allocation to store the specified
  38      * number of mappings.
  39      */
  40     public HCSparseArray(int initialCapacity) {
  41         initialCapacity = idealIntArraySize(initialCapacity);
  42
  43         mKeys = new int[initialCapacity];
  44         mValues = new Object[initialCapacity];
  45         mSize = 0;
  46     }
  47
  48     /**
  49      * Gets the Object mapped from the specified key, or <code>null</code>
  50      * if no such mapping has been made.
  51      */
  52     public E get(int key) {
  53         return get(key, null);
  54     }
  55
  56     /**
  57      * Gets the Object mapped from the specified key, or the specified Object
  58      * if no such mapping has been made.
  59      */
  60     public E get(int key, E valueIfKeyNotFound) {
  61         int i = binarySearch(mKeys, 0, mSize, key);
  62
  63         if (i < 0 || mValues[i] == DELETED) {
  64             return valueIfKeyNotFound;
  65         } else {
  66             return (E) mValues[i];
  67         }
  68     }
  69
  70     /**
  71      * Removes the mapping from the specified key, if there was any.
  72      */
  73     public void delete(int key) {
  74         int i = binarySearch(mKeys, 0, mSize, key);
  75
  76         if (i >= 0) {
  77             if (mValues[i] != DELETED) {
  78                 mValues[i] = DELETED;
  79                 mGarbage = true;
  80             }
  81         }
  82     }
  83
  84     /**
  85      * Alias for {@link #delete(int)}.
  86      */
  87     public void remove(int key) {
  88         delete(key);
  89     }
  90
  91     /**
  92      * Removes the mapping at the specified index.
  93      */
  94     public void removeAt(int index) {
  95         if (mValues[index] != DELETED) {
  96             mValues[index] = DELETED;
  97             mGarbage = true;
  98         }
  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 = idealIntArraySize(mSize + 1);
 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 = idealIntArraySize(pos + 1);
 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     private static int binarySearch(int[] a, int start, int len, int key) {
 314         int high = start + len, low = start - 1, guess;
 315
 316         while (high - low > 1) {
 317             guess = (high + low) / 2;
 318
 319             if (a[guess] < key)
 320                 low = guess;
 321             else
 322                 high = guess;
 323         }
 324
 325         if (high == start + len)
 326             return ~(start + len);
 327         else if (a[high] == key)
 328             return high;
 329         else
 330             return ~high;
 331     }
 332
 333     private void checkIntegrity() {
 334         for (int i = 1; i < mSize; i++) {
 335             if (mKeys[i] <= mKeys[i - 1]) {
 336                 for (int j = 0; j < mSize; j++) {
 337                     Log.e("FAIL", j + ": " + mKeys[j] + " -> " + mValues[j]);
 338                 }
 339
 340                 throw new RuntimeException();
 341             }
 342         }
 343     }
 344
 345     static int idealByteArraySize(int need) {
 346         for (int i = 4; i < 32; i++)
 347             if (need <= (1 << i) - 12)
 348                 return (1 << i) - 12;
 349
 350         return need;
 351     }
 352
 353     static int idealIntArraySize(int need) {
 354         return idealByteArraySize(need * 4) / 4;
 355     }
 356
 357     private int[] mKeys;
 358     private Object[] mValues;
 359     private int mSize;
 360 }