1cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn/* 2cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Copyright (C) 2011 The Android Open Source Project 3cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * 4cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 5cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * you may not use this file except in compliance with the License. 6cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * You may obtain a copy of the License at 7cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * 8cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 9cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * 10cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Unless required by applicable law or agreed to in writing, software 11cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 12cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * See the License for the specific language governing permissions and 14cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * limitations under the License. 15cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 16cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 17346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powellpackage android.support.v4.util; 18cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 19cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn/** 201d99e1c98bd96903626128b18537427c1fe38eeeChet Haase * A copy of the current platform (currently {@link android.os.Build.VERSION_CODES#KITKAT} 212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * version of {@link android.util.SparseArray}; provides a removeAt() method and other things. 22cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 232290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpublic class SparseArrayCompat<E> implements Cloneable { 24cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn private static final Object DELETED = new Object(); 25cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn private boolean mGarbage = false; 26cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private int[] mKeys; 282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private Object[] mValues; 292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private int mSize; 302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 31cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 32cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Creates a new SparseArray containing no mappings. 33cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 34346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell public SparseArrayCompat() { 35cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn this(10); 36cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 37cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 38cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 39cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Creates a new SparseArray containing no mappings that will not 40cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * require any additional memory allocation to store the specified 412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * number of mappings. If you supply an initial capacity of 0, the 422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * sparse array will be initialized with a light-weight representation 432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * not requiring any additional array allocations. 44cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 45346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell public SparseArrayCompat(int initialCapacity) { 462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (initialCapacity == 0) { 472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mKeys = ContainerHelpers.EMPTY_INTS; 482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mValues = ContainerHelpers.EMPTY_OBJECTS; 492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn initialCapacity = ContainerHelpers.idealIntArraySize(initialCapacity); 512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mKeys = new int[initialCapacity]; 522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mValues = new Object[initialCapacity]; 532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 54cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = 0; 55cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 56cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @SuppressWarnings("unchecked") 592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SparseArrayCompat<E> clone() { 602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn SparseArrayCompat<E> clone = null; 612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn try { 622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clone = (SparseArrayCompat<E>) super.clone(); 632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clone.mKeys = mKeys.clone(); 642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clone.mValues = mValues.clone(); 652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } catch (CloneNotSupportedException cnse) { 662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /* ignore */ 672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return clone; 692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 71cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 72cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Gets the Object mapped from the specified key, or <code>null</code> 73cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * if no such mapping has been made. 74cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 75cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public E get(int key) { 76cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return get(key, null); 77cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 78cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 79cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 80cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Gets the Object mapped from the specified key, or the specified Object 81cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * if no such mapping has been made. 82cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @SuppressWarnings("unchecked") 84cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public E get(int key, E valueIfKeyNotFound) { 852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 86cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 87cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i < 0 || mValues[i] == DELETED) { 88cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return valueIfKeyNotFound; 89cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } else { 90cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return (E) mValues[i]; 91cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 92cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 93cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 94cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 95cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Removes the mapping from the specified key, if there was any. 96cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 97cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void delete(int key) { 982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 99cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 100cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i >= 0) { 101cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mValues[i] != DELETED) { 102cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = DELETED; 103cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = true; 104cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 105cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 106cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 107cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 108cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 109cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Alias for {@link #delete(int)}. 110cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 111cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void remove(int key) { 112cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn delete(key); 113cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 114cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 115cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 116cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Removes the mapping at the specified index. 117cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 118cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void removeAt(int index) { 119cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mValues[index] != DELETED) { 120cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[index] = DELETED; 121cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = true; 122cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 123cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 124346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 125346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell /** 126346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * Remove a range of mappings as a batch. 127346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * 128346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * @param index Index to begin at 129346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * @param size Number of mappings to remove 130346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell */ 131346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell public void removeAtRange(int index, int size) { 132346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell final int end = Math.min(mSize, index + size); 133346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell for (int i = index; i < end; i++) { 134346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell removeAt(i); 135346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell } 136346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell } 137346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 138cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn private void gc() { 139cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "gc start with " + mSize); 140cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 141cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int n = mSize; 142cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int o = 0; 143cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int[] keys = mKeys; 144cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] values = mValues; 145cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 146cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn for (int i = 0; i < n; i++) { 147cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object val = values[i]; 148cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 149cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (val != DELETED) { 150cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i != o) { 151cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn keys[o] = keys[i]; 152cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn values[o] = val; 1532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn values[i] = null; 154cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 155cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 156cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn o++; 157cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 158cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 159cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 160cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = false; 161cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = o; 162cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 163cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "gc end with " + mSize); 164cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 165cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 166cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 167cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Adds a mapping from the specified key to the specified value, 168cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * replacing the previous mapping from the specified key if there 169cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * was one. 170cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 171cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void put(int key, E value) { 1722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 173cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 174cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i >= 0) { 175cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = value; 176cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } else { 177cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn i = ~i; 178cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 179cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i < mSize && mValues[i] == DELETED) { 180cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys[i] = key; 181cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = value; 182cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return; 183cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 184cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 185cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 186cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 187cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 188cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Search again because indices may have changed. 1892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn i = ~ ContainerHelpers.binarySearch(mKeys, mSize, key); 190cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 191cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 192cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mSize >= mKeys.length) { 1932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int n = ContainerHelpers.idealIntArraySize(mSize + 1); 194cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 195cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int[] nkeys = new int[n]; 196cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] nvalues = new Object[n]; 197cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 198cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 199cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 200cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 201cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 202cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys = nkeys; 203cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues = nvalues; 204cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 205cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 206cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mSize - i != 0) { 207cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "move " + (mSize - i)); 208cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 209cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 210cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 211cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 212cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys[i] = key; 213cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = value; 214cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize++; 215cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 216cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 217cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 218cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 219cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Returns the number of key-value mappings that this SparseArray 220cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * currently stores. 221cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 222cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int size() { 223cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 224cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 225cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 226cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 227cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return mSize; 228cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 229cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 230cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 231cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 232cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * the key from the <code>index</code>th key-value mapping that this 233346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * SparseArray stores. 234cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 235cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int keyAt(int index) { 236cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 237cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 238cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 239cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 240cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return mKeys[index]; 241cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 242346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 243cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 244cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 245cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * the value from the <code>index</code>th key-value mapping that this 246346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * SparseArray stores. 247cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 2482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @SuppressWarnings("unchecked") 249cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public E valueAt(int index) { 250cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 251cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 252cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 253cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 254cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return (E) mValues[index]; 255cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 256cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 257cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 258cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, sets a new 259cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * value for the <code>index</code>th key-value mapping that this 260346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * SparseArray stores. 261cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 262cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void setValueAt(int index, E value) { 263cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 264cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 265cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 266cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 267cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[index] = value; 268cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 269346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 270cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 271cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Returns the index for which {@link #keyAt} would return the 272cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * specified key, or a negative number if the specified 273cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * key is not mapped. 274cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 275cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int indexOfKey(int key) { 276cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 277cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 278cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 279cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 2802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ContainerHelpers.binarySearch(mKeys, mSize, key); 281cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 282cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 283cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 284cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Returns an index for which {@link #valueAt} would return the 285cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * specified key, or a negative number if no keys map to the 286cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * specified value. 2872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>Beware that this is a linear search, unlike lookups by key, 288cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * and that multiple keys can map to the same value and this will 289cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * find only one of them. 2902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>Note also that unlike most collections' {@code indexOf} methods, 2912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this method compares values using {@code ==} rather than {@code equals}. 292cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 293cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int indexOfValue(E value) { 294cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 295cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 296cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 297cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 298cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn for (int i = 0; i < mSize; i++) 299cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mValues[i] == value) 300cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return i; 301cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 302cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return -1; 303cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 304cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 305cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 306cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Removes all key-value mappings from this SparseArray. 307cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 308cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void clear() { 309cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int n = mSize; 310cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] values = mValues; 311cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 312cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn for (int i = 0; i < n; i++) { 313cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn values[i] = null; 314cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 315cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 316cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = 0; 317cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = false; 318cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 319cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 320cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 321cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Puts a key/value pair into the array, optimizing for the case where 322cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * the key is greater than all existing keys in the array. 323cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 324cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void append(int key, E value) { 325cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mSize != 0 && key <= mKeys[mSize - 1]) { 326cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn put(key, value); 327cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return; 328cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 329cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 330cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 331cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 332cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 333cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 334cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int pos = mSize; 335cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (pos >= mKeys.length) { 3362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int n = ContainerHelpers.idealIntArraySize(pos + 1); 337cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 338cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int[] nkeys = new int[n]; 339cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] nvalues = new Object[n]; 340cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 341cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 342cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 343cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 344cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 345cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys = nkeys; 346cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues = nvalues; 347cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 348cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 349cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys[pos] = key; 350cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[pos] = value; 351cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = pos + 1; 352cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 353346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 3542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 3562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 3572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 3582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this map contains itself as a value, the string "(this Map)" 3592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will appear in its place. 3602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 3622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public String toString() { 3632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size() <= 0) { 3642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return "{}"; 365cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 366cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 3672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 3682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('{'); 3692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 3702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (i > 0) { 3712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(", "); 3722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int key = keyAt(i); 3742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(key); 3752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('='); 3762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = valueAt(i); 3772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value != this) { 3782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(value); 3792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 3802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 3812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('}'); 3842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return buffer.toString(); 385cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 386cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn} 387