ArrayMap.java revision 9c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1
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) { 258776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 259776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 260b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mSize = 0; 261b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 262b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 26308735185f8105710e18ad02297461bec9268e514Chet Haase /** 26408735185f8105710e18ad02297461bec9268e514Chet Haase * Create a new ArrayMap with the mappings from the given ArrayMap. 26508735185f8105710e18ad02297461bec9268e514Chet Haase */ 26608735185f8105710e18ad02297461bec9268e514Chet Haase public ArrayMap(ArrayMap map) { 26708735185f8105710e18ad02297461bec9268e514Chet Haase this(); 26808735185f8105710e18ad02297461bec9268e514Chet Haase if (map != null) { 26908735185f8105710e18ad02297461bec9268e514Chet Haase putAll(map); 27008735185f8105710e18ad02297461bec9268e514Chet Haase } 27108735185f8105710e18ad02297461bec9268e514Chet Haase } 27208735185f8105710e18ad02297461bec9268e514Chet Haase 273f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 274f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Make the array map empty. All storage is released. 275f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 276f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 277f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void clear() { 278b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (mSize > 0) { 279390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn freeArrays(mHashes, mArray, mSize); 280776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 281776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 282390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn mSize = 0; 283390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn } 284f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 285f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 286f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 287450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn * @hide 288450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 289450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn */ 290450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn public void erase() { 291450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn if (mSize > 0) { 292450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn final int N = mSize<<1; 293450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn final Object[] array = mArray; 294450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn for (int i=0; i<N; i++) { 295450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn array[i] = null; 296450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 2974a7d824c3b41eafc4ff91d3253ff8a9ebd60a454Dianne Hackborn mSize = 0; 298450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 299450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 300450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn 301450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn /** 302f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 303f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * items. 304f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 305f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void ensureCapacity(int minimumCapacity) { 306f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length < minimumCapacity) { 30721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] ohashes = mHashes; 30821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] oarray = mArray; 309f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(minimumCapacity); 310390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn if (mSize > 0) { 311390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, mSize); 312390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 313f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 314f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 315f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 316f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 317f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 318f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 319f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a key exists in the array. 320f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 321f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key to search for. 322f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the key exists, else false. 323f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 324f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 325f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsKey(Object key) { 32662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return key == null ? (indexOfNull() >= 0) : (indexOf(key, key.hashCode()) >= 0); 327f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 328f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 32962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOfValue(Object value) { 330f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize*2; 331f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mArray; 332f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value == null) { 333f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 334f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (array[i] == null) { 335f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 336f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 337f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 338f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 339f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 340f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value.equals(array[i])) { 341f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 342f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 343f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 344f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 345f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return -1; 346f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 347f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 348f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 349f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a value exists in the array. This requires a linear search 350f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * through the entire array. 351f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 352f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to search for. 353f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the value exists, else false. 354f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 355f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 356f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsValue(Object value) { 357f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value) >= 0; 358f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 359f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 360f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 361f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Retrieve a value from the array. 362f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the value to retrieve. 363f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value associated with the given key, 364f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * or null if there is no such key. 365f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 366f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 367f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V get(Object key) { 36862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int index = key == null ? indexOfNull() : indexOf(key, key.hashCode()); 369f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index >= 0 ? (V)mArray[(index<<1)+1] : null; 370f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 371f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 372f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 373f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the key at the given index in the array. 374f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 375f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the key stored at the given index. 376f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 377f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public K keyAt(int index) { 378f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (K)mArray[index << 1]; 379f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 380f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 381f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 382f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the value at the given index in the array. 383f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 384f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value stored at the given index. 385f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 386f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V valueAt(int index) { 387f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (V)mArray[(index << 1) + 1]; 388f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 389f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 390f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 391f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set the value at a given index in the array. 392f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 393f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The new value to store at this index. 394f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the previous value at the given index. 395f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 396f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V setValueAt(int index, V value) { 397f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index << 1) + 1; 398f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn V old = (V)mArray[index]; 399f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 400f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 401f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 402f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 403f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 404f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return true if the array map contains no items. 405f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 406f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 407f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean isEmpty() { 408f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize <= 0; 409f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 410f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 411f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 412f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Add a new value to the array map. 413a3fb40d5f492825bb86769f541620baca5616e05Dianne Hackborn * @param key The key under which to store the value. If 414f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * this key already exists in the array, its value will be replaced. 415f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to store for the given key. 416f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the old value that was stored for the given key, or null if there 417f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 418f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 419f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 420f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V put(K key, V value) { 42162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash; 42262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index; 42362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key == null) { 42462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = 0; 42562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOfNull(); 42662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } else { 42762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = key.hashCode(); 42862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOf(key, hash); 42962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 430f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 431f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index<<1) + 1; 432f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final V old = (V)mArray[index]; 433f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 434f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 435f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 436f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 437f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = ~index; 438f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize >= mHashes.length) { 439f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 440f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 441f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 442f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 443f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 444f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 445f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 446f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 447f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 448f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > 0) { 449f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 450f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 451f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 452f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 453f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 454f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 455f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 456f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 457f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 458f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 459f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + (index+1)); 460f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 461f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 462f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 463f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 464f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes[index] = hash; 465f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index<<1] = key; 466f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(index<<1)+1] = value; 467f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize++; 468f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 469f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 470f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 471f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 472b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * Special fast path for appending items to the end of the array without validation. 473b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * The array must already be large enough to contain the item. 474b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * @hide 475b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 476b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn public void append(K key, V value) { 477b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn int index = mSize; 47862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash = key == null ? 0 : key.hashCode(); 479b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (index >= mHashes.length) { 480b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn throw new IllegalStateException("Array is full"); 481b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 482b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (index > 0 && mHashes[index-1] > hash) { 483450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn RuntimeException e = new RuntimeException("here"); 484450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn e.fillInStackTrace(); 485450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn Log.w(TAG, "New hash " + hash 486450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn + " is before end of array hash " + mHashes[index-1] 487450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn + " at index " + index + " key " + key, e); 488450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn put(key, value); 489450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn return; 490b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 491b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mSize = index+1; 492b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mHashes[index] = hash; 493b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn index <<= 1; 494b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray[index] = key; 495b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray[index+1] = value; 496b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 497b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 498b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 4999c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * The use of the {@link #append} function can result in invalid array maps, in particular 5009c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * an array map where the same key appears multiple times. This function verifies that 5019c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * the array map is valid, throwing IllegalArgumentException if a problem is found. The 5029c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * main use for this method is validating an array map after unpacking from an IPC, to 5039c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * protect against malicious callers. 5049c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn * @hide 5059c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn */ 5069c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn public void validate() { 5079c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn final int N = mSize; 5089c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (N <= 1) { 5099c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn // There can't be dups. 5109c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn return; 5119c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5129c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn int basehash = mHashes[0]; 5139c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn int basei = 0; 5149c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn for (int i=1; i<N; i++) { 5159c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn int hash = mHashes[i]; 5169c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (hash != basehash) { 5179c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn basehash = hash; 5189c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn basei = i; 5199c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn continue; 5209c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5219c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn // We are in a run of entries with the same hash code. Go backwards through 5229c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn // the array to see if any keys are the same. 5239c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn final Object cur = mArray[i<<1]; 5249c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn for (int j=i-1; j>=basei; j--) { 5259c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn final Object prev = mArray[j<<1]; 5269c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (cur == prev) { 5279c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 5289c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5299c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn if (cur != null && prev != null && cur.equals(prev)) { 5309c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 5319c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5329c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5339c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5349c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn } 5359c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn 5369c3e74f1f77d3b29ad47d2c74b0a0061e67c76f1Dianne Hackborn /** 537f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 538f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param array The array whose contents are to be retrieved. 539f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 540f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(ArrayMap<? extends K, ? extends V> array) { 541f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = array.mSize; 542f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + N); 543f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase if (mSize == 0) { 544f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase if (N > 0) { 545f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase System.arraycopy(array.mHashes, 0, mHashes, 0, N); 546f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 547f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase mSize = N; 548f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } 549f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } else { 550f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase for (int i=0; i<N; i++) { 551f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase put(array.keyAt(i), array.valueAt(i)); 552f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } 553f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 554f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 555f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 556f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 557f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove an existing key from the array map. 558f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the mapping to remove. 559f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored under the key, or null if there 560f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 561f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 562f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 563f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V remove(Object key) { 56462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index = key == null ? indexOfNull() : indexOf(key, key.hashCode()); 565f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 566f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return removeAt(index); 567f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 568f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 569f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 570f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 571f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 572f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 573f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove the key/value mapping at the given index. 574f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 575f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored at this index. 576f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 577f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V removeAt(int index) { 57862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final Object old = mArray[(index << 1) + 1]; 579f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize <= 1) { 580f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Now empty. 581f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 582f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(mHashes, mArray, mSize); 583776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 584776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 585f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 586f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 587f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 588f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 589f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 590f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // that and BASE_SIZE. 591f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 592f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 593f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 594f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 595f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 596f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 597f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 598f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 599f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 600f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index > 0) { 601f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 602f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 603f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index << 1); 604f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 605f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 606f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 607f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 608f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 609f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 610f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 611f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 612f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 613f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 614f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 615f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 616f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 617f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 618f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 619f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 620f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 621f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[mSize << 1] = null; 622f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(mSize << 1) + 1] = null; 623f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 624f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 62562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return (V)old; 626f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 627f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 628f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 629f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the number of items in this array map. 630f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 631f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 632f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public int size() { 633f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 634f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 635f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 63621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 63721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 63821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 63921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * <p>This implementation returns false if the object is not a map, or 64021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * if the maps have different sizes. Otherwise, for each key in this map, 64121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * values of both maps are compared. If the values for any key are not 64221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * equal, the method returns false, otherwise it returns true. 64321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 64421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 64521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean equals(Object object) { 64621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (this == object) { 64721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 64821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 64921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (object instanceof Map) { 65021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Map<?, ?> map = (Map<?, ?>) object; 65121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (size() != map.size()) { 65221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 65321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 65421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 65521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn try { 65621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=0; i<mSize; i++) { 65721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn K key = keyAt(i); 65821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn V mine = valueAt(i); 65921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object theirs = map.get(key); 66021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mine == null) { 66121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (theirs != null || !map.containsKey(key)) { 66221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 66321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 66421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else if (!mine.equals(theirs)) { 66521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 66621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 66721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 66821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (NullPointerException ignored) { 66921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 67021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (ClassCastException ignored) { 67121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 67221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 67321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 67421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 67521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 67621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 67721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 67821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 67921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 68021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 68121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 68221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public int hashCode() { 68321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] hashes = mHashes; 68421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] array = mArray; 68521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int result = 0; 68621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 68721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object value = array[v]; 68821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 68921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 69021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return result; 69121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 69221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 693a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn /** 694a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * {@inheritDoc} 695a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * 696a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 697a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * this map contains itself as a key or a value, the string "(this Map)" 698a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * will appear in its place. 699a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn */ 700a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn @Override 701a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn public String toString() { 702a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (isEmpty()) { 703a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return "{}"; 704a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 705a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 706a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 707a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('{'); 708a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn for (int i=0; i<mSize; i++) { 709a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (i > 0) { 710a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(", "); 711a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 712a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object key = keyAt(i); 713a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (key != this) { 714a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(key); 715a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 716a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Map)"); 717a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 718a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('='); 719a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object value = valueAt(i); 720a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (value != this) { 721a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(value); 722a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 723a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Map)"); 724a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 725a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 726a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('}'); 727a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return buffer.toString(); 728a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 729a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 730f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 731f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Interop with traditional Java containers. Not as efficient as using 732f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // specialized collection APIs. 733f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 734f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 735f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private MapCollections<K, V> getCollection() { 736f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mCollections == null) { 737f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mCollections = new MapCollections<K, V>() { 738f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 739f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colGetSize() { 740f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 741f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 742f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 743f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 744f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Object colGetEntry(int index, int offset) { 745f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mArray[(index<<1) + offset]; 746f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 747f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 748f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 749f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfKey(Object key) { 75062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 751f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 752f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 753f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 754f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfValue(Object value) { 755f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value); 756f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 757f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 758f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 759f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Map<K, V> colGetMap() { 760f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ArrayMap.this; 761f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 762f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 763f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 764f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colPut(K key, V value) { 765f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(key, value); 766f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 767f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 768f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 769f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected V colSetValue(int index, V value) { 770f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return setValueAt(index, value); 771f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 772f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 773f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 774f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colRemoveAt(int index) { 775f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn removeAt(index); 776f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 777f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 778f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 779f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colClear() { 780f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn clear(); 781f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 782f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn }; 783f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 784f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mCollections; 785f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 786f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 787f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 788f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Determine if the array map contains all of the keys in the given collection. 789f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be checked against. 790f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if this array map contains a key for every entry 791f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in <var>collection</var>, else returns false. 792f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 793f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsAll(Collection<?> collection) { 794f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.containsAllHelper(this, collection); 795f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 796f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 797f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 798f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 799f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param map The map whose contents are to be retrieved. 800f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 801f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 802f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(Map<? extends K, ? extends V> map) { 803f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + map.size()); 804f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 805f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(entry.getKey(), entry.getValue()); 806f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 807f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 808f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 809f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 810f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that exist in the given collection. 811f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to remove keys. 812f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 813f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 814f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean removeAll(Collection<?> collection) { 815f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.removeAllHelper(this, collection); 816f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 817f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 818f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 819f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that do <b>not</b> exist in the given collection. 820f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to determine which 821f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * keys to keep. 822f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 823f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 824f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean retainAll(Collection<?> collection) { 825f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.retainAllHelper(this, collection); 826f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 827f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 828f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 829f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all mappings 830f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 831f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 832f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 833f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 834f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 835f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b></p> the semantics of this 836f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set are subtly different than that of a {@link java.util.HashMap}: most important, 837f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 838f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * object that exists for the entire iterator, so you can <b>not</b> hold on to it 839f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 840f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 841f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 842f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<Map.Entry<K, V>> entrySet() { 843f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getEntrySet(); 844f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 845f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 846f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 847f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all keys 848f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 849f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 850f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 851f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 852f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 853f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 854f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<K> keySet() { 855f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getKeySet(); 856f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 857f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 858f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 859f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Collection} for iterating over and interacting with all values 860f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 861f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 862f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 863f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 864f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 865f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 866f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Collection<V> values() { 867f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getValues(); 868f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 869f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 870