1f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn/* 2f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Copyright (C) 2013 The Android Open Source Project 3f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 4f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 5f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * you may not use this file except in compliance with the License. 6f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * You may obtain a copy of the License at 7f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 8f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 9f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 10f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Unless required by applicable law or agreed to in writing, software 11f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 12f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * See the License for the specific language governing permissions and 14f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * limitations under the License. 15f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 16f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 17f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornpackage android.util; 18f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 19776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport libcore.util.EmptyArray; 20776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 21f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornimport java.util.Collection; 22f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornimport java.util.Map; 23f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornimport java.util.Set; 24f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 25f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn/** 26f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * ArrayMap is a generic key->value mapping data structure that is 27f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * designed to be more memory efficient than a traditional {@link java.util.HashMap}. 28f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * It keeps its mappings in an array data structure -- an integer array of hash 29f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * codes for each item, and an Object array of the key/value pairs. This allows it to 30f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * avoid having to create an extra object for every entry put in to the map, and it 31f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * also tries to control the growth of the size of these arrays more aggressively 32f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * (since growing them only requires copying the entries in the array, not rebuilding 33f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * a hash map). 34f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 35f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p>Note that this implementation is not intended to be appropriate for data structures 36f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 37f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 38f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 39b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 40f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 41f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p>Because this container is intended to better balance memory use, unlike most other 42f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * standard Java containers it will shrink its array as items are removed from it. Currently 43f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * you have no control over this shrinking -- if you set a capacity and then remove an 44f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * item, it may reduce the capacity to better match the current size. In the future an 45b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 46f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 47f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornpublic final class ArrayMap<K, V> implements Map<K, V> { 48f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final boolean DEBUG = false; 49f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final String TAG = "ArrayMap"; 50f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 51f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 52f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * The minimum amount by which the capacity of a ArrayMap will increase. 53f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * This is tuned to be relatively space-efficient. 54f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 55f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final int BASE_SIZE = 4; 56f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 57f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 58f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Maximum number of entries to have in array caches. 59f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 60f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final int CACHE_SIZE = 10; 61f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 62f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 63b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * @hide Special immutable empty ArrayMap. 64b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 65b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn public static final ArrayMap EMPTY = new ArrayMap(true); 66b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 67b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 68f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Caches of small array objects to avoid spamming garbage. The cache 69f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Object[] variable is a pointer to a linked list of array objects. 70f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * The first entry in the array is a pointer to the next array in the 71f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * list; the second entry is a pointer to the int[] hash code array for it. 72f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 73f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static Object[] mBaseCache; 74f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static int mBaseCacheSize; 75f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static Object[] mTwiceBaseCache; 76f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static int mTwiceBaseCacheSize; 77f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 78b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 79b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * Special hash array value that indicates the container is immutable. 80b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 81b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn static final int[] EMPTY_IMMUTABLE_INTS = new int[0]; 82b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 83f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int[] mHashes; 84f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Object[] mArray; 85f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int mSize; 86f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn MapCollections<K, V> mCollections; 87f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 8862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOf(Object key, int hash) { 89f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize; 90f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 91f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 92f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (N == 0) { 93f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ~0; 94f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 95f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 963e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, hash); 97f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 98f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 99f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < 0) { 100f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index; 101f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 102f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 103f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the key at the returned index matches, that's what we want. 10462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[index<<1])) { 105f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index; 106f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 107f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 108f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Search for a matching key after the index. 109f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int end; 110f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (end = index + 1; end < N && mHashes[end] == hash; end++) { 11162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[end << 1])) return end; 112f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 113f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 114f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Search for a matching key before the index. 115f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 11662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[i << 1])) return i; 11762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 11862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 11962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Key not found -- return negative value indicating where a 12062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // new entry for this key should go. We use the end of the 12162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // hash chain to reduce the number of array entries that will 12262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // need to be copied when inserting. 12362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return ~end; 12462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 12562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 12662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOfNull() { 12762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int N = mSize; 12862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 12962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 13062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (N == 0) { 13162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return ~0; 13262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 13362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, 0); 13562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 13762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (index < 0) { 13862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return index; 13962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 14062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 14162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // If the key at the returned index matches, that's what we want. 14262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[index<<1]) { 14362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return index; 14462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 14562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 14662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Search for a matching key after the index. 14762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int end; 14862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn for (end = index + 1; end < N && mHashes[end] == 0; end++) { 14962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[end << 1]) return end; 15062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 15162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 15262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Search for a matching key before the index. 15362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 15462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[i << 1]) return i; 155f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 156f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 157f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Key not found -- return negative value indicating where a 158f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // new entry for this key should go. We use the end of the 159f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // hash chain to reduce the number of array entries that will 160f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // need to be copied when inserting. 161f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ~end; 162f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 163f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 164f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private void allocArrays(final int size) { 165b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (mHashes == EMPTY_IMMUTABLE_INTS) { 166b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn throw new UnsupportedOperationException("ArrayMap is immutable"); 167b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 168f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (size == (BASE_SIZE*2)) { 169f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 170f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mTwiceBaseCache != null) { 171f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mTwiceBaseCache; 172f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = array; 173f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCache = (Object[])array[0]; 174f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = (int[])array[1]; 175f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = array[1] = null; 176f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCacheSize--; 177f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 178f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 179f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return; 180f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 181f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 182f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else if (size == BASE_SIZE) { 183f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 184f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mBaseCache != null) { 185f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mBaseCache; 186f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = array; 187f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCache = (Object[])array[0]; 188f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = (int[])array[1]; 189f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = array[1] = null; 190f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCacheSize--; 191f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 192f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 193f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return; 194f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 195f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 196f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 197f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 198f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = new int[size]; 199f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = new Object[size<<1]; 200f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 201f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 202f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 203f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (hashes.length == (BASE_SIZE*2)) { 204f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 205f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mTwiceBaseCacheSize < CACHE_SIZE) { 206f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = mTwiceBaseCache; 207f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[1] = hashes; 208f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 209f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[i] = null; 210f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 211f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCache = array; 212f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCacheSize++; 213f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 214f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 215f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 216f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 217f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else if (hashes.length == BASE_SIZE) { 218f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 219f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mBaseCacheSize < CACHE_SIZE) { 220f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = mBaseCache; 221f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[1] = hashes; 222f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 223f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[i] = null; 224f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 225f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCache = array; 226f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCacheSize++; 227f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 228f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 229f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 230f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 231f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 232f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 233f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 234f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 235f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Create a new empty ArrayMap. The default capacity of an array map is 0, and 236f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * will grow once items are added to it. 237f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 238f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public ArrayMap() { 239776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 240776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 241f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 242f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 243f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 244f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 245f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Create a new ArrayMap with a given initial capacity. 246f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 247f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public ArrayMap(int capacity) { 248f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (capacity == 0) { 249776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 250776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 251f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 252f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(capacity); 253f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 254f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 255f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 25621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 257b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn private ArrayMap(boolean immutable) { 258b6bdb0f02df1004307d25ae86e09cdbbc6865e75Adam Lesinski // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS 259b6bdb0f02df1004307d25ae86e09cdbbc6865e75Adam Lesinski // instance instead of the usual EmptyArray.INT. The reference 260b6bdb0f02df1004307d25ae86e09cdbbc6865e75Adam Lesinski // is checked later to see if the array is allowed to grow. 261b6bdb0f02df1004307d25ae86e09cdbbc6865e75Adam Lesinski mHashes = immutable ? EMPTY_IMMUTABLE_INTS : EmptyArray.INT; 262776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 263b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mSize = 0; 264b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 265b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 26608735185f8105710e18ad02297461bec9268e514Chet Haase /** 26708735185f8105710e18ad02297461bec9268e514Chet Haase * Create a new ArrayMap with the mappings from the given ArrayMap. 26808735185f8105710e18ad02297461bec9268e514Chet Haase */ 269f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn public ArrayMap(ArrayMap<K, V> map) { 27008735185f8105710e18ad02297461bec9268e514Chet Haase this(); 27108735185f8105710e18ad02297461bec9268e514Chet Haase if (map != null) { 27208735185f8105710e18ad02297461bec9268e514Chet Haase putAll(map); 27308735185f8105710e18ad02297461bec9268e514Chet Haase } 27408735185f8105710e18ad02297461bec9268e514Chet Haase } 27508735185f8105710e18ad02297461bec9268e514Chet Haase 276f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 277f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Make the array map empty. All storage is released. 278f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 279f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 280f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void clear() { 281b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (mSize > 0) { 282390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn freeArrays(mHashes, mArray, mSize); 283776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 284776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 285390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn mSize = 0; 286390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn } 287f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 288f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 289f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 290450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn * @hide 291450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 292450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn */ 293450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn public void erase() { 294450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn if (mSize > 0) { 295450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn final int N = mSize<<1; 296450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn final Object[] array = mArray; 297450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn for (int i=0; i<N; i++) { 298450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn array[i] = null; 299450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 3004a7d824c3b41eafc4ff91d3253ff8a9ebd60a454Dianne Hackborn mSize = 0; 301450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 302450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 303450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn 304450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn /** 305f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 306f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * items. 307f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 308f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void ensureCapacity(int minimumCapacity) { 309f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length < minimumCapacity) { 31021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] ohashes = mHashes; 31121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] oarray = mArray; 312f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(minimumCapacity); 313390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn if (mSize > 0) { 314390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, mSize); 315390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 316f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 317f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 318f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 319f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 320f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 321f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 322f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a key exists in the array. 323f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 324f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key to search for. 325f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the key exists, else false. 326f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 327f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 328f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsKey(Object key) { 3294e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return indexOfKey(key) >= 0; 3304e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski } 3314e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski 3324e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski /** 3334e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * Returns the index of a key in the set. 3344e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * 3354e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * @param key The key to search for. 3364e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * @return Returns the index of the key if it exists, else a negative integer. 3374e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski */ 3384e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski public int indexOfKey(Object key) { 3394e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 340f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 341f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 34262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOfValue(Object value) { 343f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize*2; 344f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mArray; 345f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value == null) { 346f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 347f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (array[i] == null) { 348f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 349f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 350f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 351f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 352f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 353f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value.equals(array[i])) { 354f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 355f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 356f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 357f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 358f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return -1; 359f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 360f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 361f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 362f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a value exists in the array. This requires a linear search 363f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * through the entire array. 364f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 365f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to search for. 366f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the value exists, else false. 367f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 368f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 369f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsValue(Object value) { 370f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value) >= 0; 371f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 372f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 373f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 374f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Retrieve a value from the array. 375f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the value to retrieve. 376f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value associated with the given key, 377f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * or null if there is no such key. 378f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 379f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 380f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V get(Object key) { 3814e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski final int index = indexOfKey(key); 382f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index >= 0 ? (V)mArray[(index<<1)+1] : null; 383f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 384f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 385f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 386f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the key at the given index in the array. 387f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 388f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the key stored at the given index. 389f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 390f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public K keyAt(int index) { 391f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (K)mArray[index << 1]; 392f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 393f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 394f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 395f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the value at the given index in the array. 396f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 397f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value stored at the given index. 398f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 399f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V valueAt(int index) { 400f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (V)mArray[(index << 1) + 1]; 401f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 402f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 403f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 404f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set the value at a given index in the array. 405f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 406f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The new value to store at this index. 407f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the previous value at the given index. 408f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 409f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V setValueAt(int index, V value) { 410f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index << 1) + 1; 411f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn V old = (V)mArray[index]; 412f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 413f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 414f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 415f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 416f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 417f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return true if the array map contains no items. 418f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 419f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 420f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean isEmpty() { 421f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize <= 0; 422f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 423f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 424f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 425f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Add a new value to the array map. 426a3fb40d5f492825bb86769f541620baca5616e05Dianne Hackborn * @param key The key under which to store the value. If 427f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * this key already exists in the array, its value will be replaced. 428f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to store for the given key. 429f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the old value that was stored for the given key, or null if there 430f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 431f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 432f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 433f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V put(K key, V value) { 43462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash; 43562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index; 43662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key == null) { 43762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = 0; 43862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOfNull(); 43962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } else { 44062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = key.hashCode(); 44162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOf(key, hash); 44262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 443f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 444f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index<<1) + 1; 445f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final V old = (V)mArray[index]; 446f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 447f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 448f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 449f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 450f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = ~index; 451f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize >= mHashes.length) { 452f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 453f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 454f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 455f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 456f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 457f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 458f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 459f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 460f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 461f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > 0) { 462f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 463f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 464f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 465f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 466f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 467f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 468f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 469f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 470f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 471f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 472f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + (index+1)); 473f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 474f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 475f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 476f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 477f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes[index] = hash; 478f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index<<1] = key; 479f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(index<<1)+1] = value; 480f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize++; 481f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 482f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 483f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 484f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 485b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * Special fast path for appending items to the end of the array without validation. 486b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * The array must already be large enough to contain the item. 487b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * @hide 488b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 489b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn public void append(K key, V value) { 490b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn int index = mSize; 49162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash = key == null ? 0 : key.hashCode(); 492b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (index >= mHashes.length) { 493b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn throw new IllegalStateException("Array is full"); 494b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 495b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (index > 0 && mHashes[index-1] > hash) { 496450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn RuntimeException e = new RuntimeException("here"); 497450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn e.fillInStackTrace(); 498450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn Log.w(TAG, "New hash " + hash 499450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn + " is before end of array hash " + mHashes[index-1] 500450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn + " at index " + index + " key " + key, e); 501450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn put(key, value); 502450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn return; 503b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 504b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mSize = index+1; 505b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mHashes[index] = hash; 506b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn index <<= 1; 507b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray[index] = key; 508b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray[index+1] = value; 509b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 510b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 511b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 5129c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * The use of the {@link #append} function can result in invalid array maps, in particular 5139c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * an array map where the same key appears multiple times. This function verifies that 5149c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * the array map is valid, throwing IllegalArgumentException if a problem is found. The 5159c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * main use for this method is validating an array map after unpacking from an IPC, to 5169c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * protect against malicious callers. 5179c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * @hide 5189c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn */ 5199c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn public void validate() { 5209c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn final int N = mSize; 5219c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (N <= 1) { 5229c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn // There can't be dups. 5239c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn return; 5249c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5259c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn int basehash = mHashes[0]; 5269c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn int basei = 0; 5279c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn for (int i=1; i<N; i++) { 5289c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn int hash = mHashes[i]; 5299c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (hash != basehash) { 5309c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn basehash = hash; 5319c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn basei = i; 5329c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn continue; 5339c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5349c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn // We are in a run of entries with the same hash code. Go backwards through 5359c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn // the array to see if any keys are the same. 5369c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn final Object cur = mArray[i<<1]; 5379c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn for (int j=i-1; j>=basei; j--) { 5389c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn final Object prev = mArray[j<<1]; 5399c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (cur == prev) { 5409c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 5419c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5429c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (cur != null && prev != null && cur.equals(prev)) { 5439c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 5449c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5459c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5469c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5479c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5489c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn 5499c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn /** 550f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 551f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param array The array whose contents are to be retrieved. 552f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 553f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(ArrayMap<? extends K, ? extends V> array) { 554f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = array.mSize; 555f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + N); 556f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase if (mSize == 0) { 557f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase if (N > 0) { 558f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase System.arraycopy(array.mHashes, 0, mHashes, 0, N); 559f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 560f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase mSize = N; 561f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } 562f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } else { 563f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase for (int i=0; i<N; i++) { 564f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase put(array.keyAt(i), array.valueAt(i)); 565f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } 566f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 567f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 568f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 569f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 570f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove an existing key from the array map. 571f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the mapping to remove. 572f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored under the key, or null if there 573f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 574f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 575f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 576f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V remove(Object key) { 5774e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski final int index = indexOfKey(key); 578f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 579f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return removeAt(index); 580f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 581f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 582f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 583f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 584f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 585f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 586f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove the key/value mapping at the given index. 587f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 588f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored at this index. 589f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 590f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V removeAt(int index) { 59162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final Object old = mArray[(index << 1) + 1]; 592f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize <= 1) { 593f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Now empty. 594f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 595f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(mHashes, mArray, mSize); 596776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 597776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 598f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 599f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 600f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 601f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 602f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 603f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // that and BASE_SIZE. 604f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 605f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 606f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 607f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 608f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 609f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 610f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 611f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 612f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 613f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index > 0) { 614f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 615f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 616f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index << 1); 617f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 618f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 619f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 620f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 621f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 622f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 623f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 624f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 625f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 626f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 627f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 628f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 629f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 630f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 631f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 632f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 633f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 634f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[mSize << 1] = null; 635f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(mSize << 1) + 1] = null; 636f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 637f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 63862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return (V)old; 639f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 640f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 641f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 642f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the number of items in this array map. 643f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 644f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 645f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public int size() { 646f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 647f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 648f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 64921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 65021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 65121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 65221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * <p>This implementation returns false if the object is not a map, or 65321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * if the maps have different sizes. Otherwise, for each key in this map, 65421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * values of both maps are compared. If the values for any key are not 65521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * equal, the method returns false, otherwise it returns true. 65621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 65721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 65821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean equals(Object object) { 65921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (this == object) { 66021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 66121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 66221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (object instanceof Map) { 66321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Map<?, ?> map = (Map<?, ?>) object; 66421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (size() != map.size()) { 66521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 66621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 66721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 66821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn try { 66921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=0; i<mSize; i++) { 67021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn K key = keyAt(i); 67121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn V mine = valueAt(i); 67221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object theirs = map.get(key); 67321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mine == null) { 67421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (theirs != null || !map.containsKey(key)) { 67521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 67621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 67721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else if (!mine.equals(theirs)) { 67821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 67921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (NullPointerException ignored) { 68221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 68321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (ClassCastException ignored) { 68421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 68521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 68721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 68921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 69021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 69121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 69221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 69321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 69421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 69521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public int hashCode() { 69621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] hashes = mHashes; 69721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] array = mArray; 69821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int result = 0; 69921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 70021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object value = array[v]; 70121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 70221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 70321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return result; 70421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 70521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 706a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn /** 707a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * {@inheritDoc} 708a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * 709a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 710a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * this map contains itself as a key or a value, the string "(this Map)" 711a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * will appear in its place. 712a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn */ 713a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn @Override 714a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn public String toString() { 715a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (isEmpty()) { 716a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return "{}"; 717a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 718a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 719a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 720a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('{'); 721a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn for (int i=0; i<mSize; i++) { 722a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (i > 0) { 723a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(", "); 724a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 725a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object key = keyAt(i); 726a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (key != this) { 727a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(key); 728a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 729a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Map)"); 730a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 731a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('='); 732a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object value = valueAt(i); 733a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (value != this) { 734a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(value); 735a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 736a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Map)"); 737a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 738a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 739a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('}'); 740a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return buffer.toString(); 741a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 742a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 743f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 744f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Interop with traditional Java containers. Not as efficient as using 745f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // specialized collection APIs. 746f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 747f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 748f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private MapCollections<K, V> getCollection() { 749f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mCollections == null) { 750f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mCollections = new MapCollections<K, V>() { 751f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 752f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colGetSize() { 753f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 754f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 755f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 756f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 757f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Object colGetEntry(int index, int offset) { 758f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mArray[(index<<1) + offset]; 759f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 760f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 761f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 762f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfKey(Object key) { 7634e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return indexOfKey(key); 764f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 765f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 766f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 767f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfValue(Object value) { 768f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value); 769f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 770f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 771f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 772f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Map<K, V> colGetMap() { 773f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ArrayMap.this; 774f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 775f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 776f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 777f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colPut(K key, V value) { 778f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(key, value); 779f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 780f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 781f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 782f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected V colSetValue(int index, V value) { 783f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return setValueAt(index, value); 784f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 785f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 786f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 787f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colRemoveAt(int index) { 788f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn removeAt(index); 789f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 790f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 791f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 792f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colClear() { 793f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn clear(); 794f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 795f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn }; 796f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 797f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mCollections; 798f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 799f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 800f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 801f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Determine if the array map contains all of the keys in the given collection. 802f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be checked against. 803f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if this array map contains a key for every entry 804f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in <var>collection</var>, else returns false. 805f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 806f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsAll(Collection<?> collection) { 807f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.containsAllHelper(this, collection); 808f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 809f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 810f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 811f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 812f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param map The map whose contents are to be retrieved. 813f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 814f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 815f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(Map<? extends K, ? extends V> map) { 816f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + map.size()); 817f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 818f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(entry.getKey(), entry.getValue()); 819f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 820f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 821f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 822f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 823f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that exist in the given collection. 824f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to remove keys. 825f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 826f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 827f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean removeAll(Collection<?> collection) { 828f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.removeAllHelper(this, collection); 829f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 830f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 831f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 832f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that do <b>not</b> exist in the given collection. 833f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to determine which 834f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * keys to keep. 835f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 836f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 837f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean retainAll(Collection<?> collection) { 838f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.retainAllHelper(this, collection); 839f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 840f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 841f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 842f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all mappings 843f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 844f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 845f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 846f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * requires generating a number of temporary objects and allocates additional state 847f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * information associated with the container that will remain for the life of the container.</p> 848f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 849f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b></p> the semantics of this 850f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set are subtly different than that of a {@link java.util.HashMap}: most important, 851f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 852f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * object that exists for the entire iterator, so you can <b>not</b> hold on to it 853f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 854f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 855f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 856f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<Map.Entry<K, V>> entrySet() { 857f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getEntrySet(); 858f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 859f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 860f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 861f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all keys 862f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 863f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 864f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 865f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * requires generating a number of temporary objects and allocates additional state 866f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * information associated with the container that will remain for the life of the container.</p> 867f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 868f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 869f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<K> keySet() { 870f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getKeySet(); 871f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 872f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 873f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 874f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Collection} for iterating over and interacting with all values 875f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 876f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 877f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 878f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * requires generating a number of temporary objects and allocates additional state 879f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * information associated with the container that will remain for the life of the container.</p> 880f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 881f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 882f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Collection<V> values() { 883f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getValues(); 884f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 885f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 886