1ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman/* 2ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Copyright (C) 2006 The Android Open Source Project 3ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Copyright (C) 2011 Eric Bowman 4ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * 5ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Licensed under the Apache License, Version 2.0 (the "License"); 6ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * you may not use this file except in compliance with the License. 7ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * You may obtain a copy of the License at 8ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * 9ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * http://www.apache.org/licenses/LICENSE-2.0 10ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * 11ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Unless required by applicable law or agreed to in writing, software 12ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * distributed under the License is distributed on an "AS IS" BASIS, 13ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * See the License for the specific language governing permissions and 15ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * limitations under the License. 16ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 17ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 18ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowmanpackage com.xtremelabs.robolectric.shadows; 19ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 20f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylorimport static com.xtremelabs.robolectric.Robolectric.shadowOf; 21f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor 22f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylorimport java.util.Arrays; 23f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor 24ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowmanimport android.util.SparseArray; 25f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor 26f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylorimport com.xtremelabs.robolectric.Robolectric; 27ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowmanimport com.xtremelabs.robolectric.internal.Implementation; 28ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowmanimport com.xtremelabs.robolectric.internal.Implements; 29f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylorimport com.xtremelabs.robolectric.internal.RealObject; 30ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 31ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman/** 32ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Shadow implementation of SparseArray. Basically copied & pasted the 33ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * real SparseArray implementation, without depending on the ArrayUtils 34ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * class that is not in the SDK. 35ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * 36ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * @author Eric Bowman (ebowman@boboco.ie) 37ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * @since 2011-02-25 11:01 38ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 39ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman@SuppressWarnings({"JavaDoc"}) 40ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman@Implements(SparseArray.class) 41ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowmanpublic class ShadowSparseArray<E> { 42ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 43ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private static final Object DELETED = new Object(); 44ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private boolean mGarbage = false; 45ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 467e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel @RealObject 47f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor private SparseArray<E> realObject; 487e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel 49ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void __constructor__() { 50ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman __constructor__(10); 51ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 52ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 53ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 54ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Creates a new SparseArray containing no mappings that will not 55ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * require any additional memory allocation to store the specified 56ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * number of mappings. 57ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 58ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void __constructor__(int initialCapacity) { 59ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman initialCapacity = idealIntArraySize(initialCapacity); 60ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mKeys = new int[initialCapacity]; 61ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues = new Object[initialCapacity]; 62ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mSize = 0; 63ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 64ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 65ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 66ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 67ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 68ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Gets the Object mapped from the specified key, or <code>null</code> 69ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * if no such mapping has been made. 70ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 71ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 72ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public E get(int key) { 73ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return get(key, null); 74ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 75ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 76ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 77ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Gets the Object mapped from the specified key, or the specified Object 78ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * if no such mapping has been made. 79ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 80ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 81ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public E get(int key, E valueIfKeyNotFound) { 82ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int i = binarySearch(mKeys, 0, mSize, key); 83ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 84ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (i < 0 || mValues[i] == DELETED) { 85ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return valueIfKeyNotFound; 86ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } else { 87ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman //noinspection unchecked 88ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return (E) mValues[i]; 89ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 90ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 91ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 92ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 93ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Removes the mapping from the specified key, if there was any. 94ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 95ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 96ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void delete(int key) { 97ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int i = binarySearch(mKeys, 0, mSize, key); 98ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 99ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (i >= 0) { 100ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mValues[i] != DELETED) { 101ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues[i] = DELETED; 102ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mGarbage = true; 103ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 104ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 105ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 106ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 107ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 108ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Alias for {@link #delete(int)}. 109ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 110ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 111ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void remove(int key) { 112ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman delete(key); 113ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 114ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 115ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private void gc() { 116ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman // Log.e("SparseArray", "gc start with " + mSize); 117ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 118ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int n = mSize; 119ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int o = 0; 120ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int[] keys = mKeys; 121ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman Object[] values = mValues; 122ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 123ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman for (int i = 0; i < n; i++) { 124ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman Object val = values[i]; 125ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 126ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (val != DELETED) { 127ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (i != o) { 128ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman keys[o] = keys[i]; 129ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman values[o] = val; 130ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 131ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 132ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman o++; 133ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 134ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 135ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 136ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mGarbage = false; 137ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mSize = o; 138ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 139ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman // Log.e("SparseArray", "gc end with " + mSize); 140ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 141ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 142ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 143ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Adds a mapping from the specified key to the specified value, 144ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * replacing the previous mapping from the specified key if there 145ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * was one. 146ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 147ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 148ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void put(int key, E value) { 149ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int i = binarySearch(mKeys, 0, mSize, key); 150ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 151ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (i >= 0) { 152ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues[i] = value; 153ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } else { 154ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman i = ~i; 155ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 156ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (i < mSize && mValues[i] == DELETED) { 157ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mKeys[i] = key; 158ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues[i] = value; 159ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return; 160ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 161ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 162ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage && mSize >= mKeys.length) { 163ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 164ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 165ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman // Search again because indices may have changed. 166ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman i = ~binarySearch(mKeys, 0, mSize, key); 167ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 168ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 169ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mSize >= mKeys.length) { 170ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int n = idealIntArraySize(mSize + 1); 171ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 172ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int[] nkeys = new int[n]; 173ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman Object[] nvalues = new Object[n]; 174ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 175ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 176ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 177ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 178ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 179ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mKeys = nkeys; 180ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues = nvalues; 181ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 182ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 183ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mSize - i != 0) { 184ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman // Log.e("SparseArray", "move " + (mSize - i)); 185ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 186ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 187ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 188ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 189ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mKeys[i] = key; 190ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues[i] = value; 191ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mSize++; 192ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 193ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 194ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 195ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 196ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Returns the number of key-value mappings that this SparseArray 197ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * currently stores. 198ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 199ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 200ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public int size() { 201ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage) { 202ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 203ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 204ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 205ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return mSize; 206ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 207ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 208ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 209ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Given an index in the range <code>0...size()-1</code>, returns 210ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * the key from the <code>index</code>th key-value mapping that this 211ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * SparseArray stores. 212ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 213ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 214ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public int keyAt(int index) { 215ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage) { 216ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 217ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 218ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 219ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return mKeys[index]; 220ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 221ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 222ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 223ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Given an index in the range <code>0...size()-1</code>, returns 224ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * the value from the <code>index</code>th key-value mapping that this 225ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * SparseArray stores. 226ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 227ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 228ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public E valueAt(int index) { 229ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage) { 230ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 231ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 232ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 233ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman //noinspection unchecked 234ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return (E) mValues[index]; 235ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 236ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 237ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 238ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Given an index in the range <code>0...size()-1</code>, sets a new 239ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * value for the <code>index</code>th key-value mapping that this 240ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * SparseArray stores. 241ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 242ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 243ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void setValueAt(int index, E value) { 244ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage) { 245ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 246ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 247ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 248ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues[index] = value; 249ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 250ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 251ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 252ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Returns the index for which {@link #keyAt} would return the 253ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * specified key, or a negative number if the specified 254ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * key is not mapped. 255ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 256ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 257ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public int indexOfKey(int key) { 258ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage) { 259ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 260ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 261ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 262ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return binarySearch(mKeys, 0, mSize, key); 263ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 264ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 265ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 266ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Returns an index for which {@link #valueAt} would return the 267ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * specified key, or a negative number if no keys map to the 268ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * specified value. 269ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Beware that this is a linear search, unlike lookups by key, 270ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * and that multiple keys can map to the same value and this will 271ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * find only one of them. 272ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 273ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 274ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public int indexOfValue(E value) { 275ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage) { 276ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 277ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 278ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 279ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman for (int i = 0; i < mSize; i++) 280ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mValues[i] == value) 281ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return i; 282ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 283ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return -1; 284ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 285ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 286ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 287ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Removes all key-value mappings from this SparseArray. 288ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 289ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 290ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void clear() { 291ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int n = mSize; 292ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman Object[] values = mValues; 293ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 294ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman for (int i = 0; i < n; i++) { 295ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman values[i] = null; 296ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 297ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 298ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mSize = 0; 299ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mGarbage = false; 300ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 301ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 302ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman /** 303ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * Puts a key/value pair into the array, optimizing for the case where 304ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman * the key is greater than all existing keys in the array. 305ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman */ 306ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman @Implementation 307ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public void append(int key, E value) { 308ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mSize != 0 && key <= mKeys[mSize - 1]) { 309ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman put(key, value); 310ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return; 311ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 312ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 313ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mGarbage && mSize >= mKeys.length) { 314ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman gc(); 315ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 316ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 317ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int pos = mSize; 318ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (pos >= mKeys.length) { 319ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int n = idealIntArraySize(pos + 1); 320ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 321ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int[] nkeys = new int[n]; 322ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman Object[] nvalues = new Object[n]; 323ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 324ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 325ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 326ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 327ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 328ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mKeys = nkeys; 329ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues = nvalues; 330ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 331ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 332ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mKeys[pos] = key; 333ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mValues[pos] = value; 334ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman mSize = pos + 1; 335ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 336ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 337ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private static int binarySearch(int[] a, int start, int len, int key) { 338ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman int high = start + len, low = start - 1, guess; 339ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 340ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman while (high - low > 1) { 341ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman guess = (high + low) / 2; 342ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 343ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (a[guess] < key) 344ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman low = guess; 345ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman else 346ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman high = guess; 347ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 348ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 349ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (high == start + len) 350ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return ~(start + len); 351ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman else if (a[high] == key) 352ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return high; 353ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman else 354ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return ~high; 355ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 356ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 357ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private void checkIntegrity() { 358ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman for (int i = 1; i < mSize; i++) { 359ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (mKeys[i] <= mKeys[i - 1]) { 360ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman for (int j = 0; j < mSize; j++) { 361ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman System.err.println( 362ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman "FAIL: " + j + ": " + mKeys[j] + " -> " + mValues[j]); 363ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 364ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 365ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman throw new RuntimeException(); 366ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 367ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 368ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 369ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 370ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public static int idealIntArraySize(int need) { 371ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return idealByteArraySize(need * 4) / 4; 372ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 3737e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel 374ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman public static int idealByteArraySize(int need) { 375ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman for (int i = 4; i < 32; i++) 376ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman if (need <= (1 << i) - 12) 377ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return (1 << i) - 12; 378ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 379ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman return need; 380ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman } 381ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman 382f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor @Implementation 383f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor @Override 384f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor public boolean equals(Object o) { 3857e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel if (o == null || o.getClass() != realObject.getClass()) 3867e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel return false; 3877e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel 3887e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel ShadowSparseArray<?> target = (ShadowSparseArray<?>) shadowOf((SparseArray<?>) o); 3897e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel return Arrays.equals(mKeys, target.mKeys) && Arrays.deepEquals(mValues, target.mValues); 390f5937727530ccf761ae1f35cb3888cb25cd3be2fRobert Taylor } 3917e4c2b80178ee77f5c3ec4083c1310833621d7f2Jan Berkel 392ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private int[] mKeys; 393ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private Object[] mValues; 394ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman private int mSize; 395ab6d77189eef0b311133e648b979ecf1a564adbfEric Bowman} 396