ArrayMap.java revision 4a7d824c3b41eafc4ff91d3253ff8a9ebd60a454
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 19f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornimport java.util.Collection; 20f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornimport java.util.Map; 21f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornimport java.util.Set; 22f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 23f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn/** 24f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * ArrayMap is a generic key->value mapping data structure that is 25f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * designed to be more memory efficient than a traditional {@link java.util.HashMap}. 26f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * It keeps its mappings in an array data structure -- an integer array of hash 27f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * codes for each item, and an Object array of the key/value pairs. This allows it to 28f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * avoid having to create an extra object for every entry put in to the map, and it 29f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * also tries to control the growth of the size of these arrays more aggressively 30f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * (since growing them only requires copying the entries in the array, not rebuilding 31f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * a hash map). 32f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 33f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p>Note that this implementation is not intended to be appropriate for data structures 34f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 35f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 36f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 37b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 38f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 39f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p>Because this container is intended to better balance memory use, unlike most other 40f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * standard Java containers it will shrink its array as items are removed from it. Currently 41f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * you have no control over this shrinking -- if you set a capacity and then remove an 42f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * item, it may reduce the capacity to better match the current size. In the future an 43b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 44f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 45f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornpublic final class ArrayMap<K, V> implements Map<K, V> { 46f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final boolean DEBUG = false; 47f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final String TAG = "ArrayMap"; 48f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 49f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 50f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * The minimum amount by which the capacity of a ArrayMap will increase. 51f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * This is tuned to be relatively space-efficient. 52f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 53f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final int BASE_SIZE = 4; 54f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 55f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 56f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Maximum number of entries to have in array caches. 57f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 58f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final int CACHE_SIZE = 10; 59f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 60f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 61b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * @hide Special immutable empty ArrayMap. 62b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 63b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn public static final ArrayMap EMPTY = new ArrayMap(true); 64b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 65b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 66f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Caches of small array objects to avoid spamming garbage. The cache 67f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Object[] variable is a pointer to a linked list of array objects. 68f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * The first entry in the array is a pointer to the next array in the 69f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * list; the second entry is a pointer to the int[] hash code array for it. 70f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 71f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static Object[] mBaseCache; 72f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static int mBaseCacheSize; 73f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static Object[] mTwiceBaseCache; 74f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static int mTwiceBaseCacheSize; 75f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 76b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 77b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * Special hash array value that indicates the container is immutable. 78b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 79b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn static final int[] EMPTY_IMMUTABLE_INTS = new int[0]; 80b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 81f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int[] mHashes; 82f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Object[] mArray; 83f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int mSize; 84f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn MapCollections<K, V> mCollections; 85f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 8662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOf(Object key, int hash) { 87f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize; 88f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 89f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 90f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (N == 0) { 91f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ~0; 92f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 93f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 943e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, hash); 95f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 96f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 97f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < 0) { 98f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index; 99f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 100f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 101f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the key at the returned index matches, that's what we want. 10262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[index<<1])) { 103f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index; 104f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 105f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 106f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Search for a matching key after the index. 107f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int end; 108f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (end = index + 1; end < N && mHashes[end] == hash; end++) { 10962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[end << 1])) return end; 110f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 111f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 112f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Search for a matching key before the index. 113f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 11462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[i << 1])) return i; 11562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 11662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 11762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Key not found -- return negative value indicating where a 11862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // new entry for this key should go. We use the end of the 11962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // hash chain to reduce the number of array entries that will 12062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // need to be copied when inserting. 12162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return ~end; 12262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 12362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 12462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOfNull() { 12562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int N = mSize; 12662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 12762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 12862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (N == 0) { 12962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return ~0; 13062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 13162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, 0); 13362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 13562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (index < 0) { 13662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return index; 13762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 13862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // If the key at the returned index matches, that's what we want. 14062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[index<<1]) { 14162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return index; 14262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 14362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 14462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Search for a matching key after the index. 14562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int end; 14662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn for (end = index + 1; end < N && mHashes[end] == 0; end++) { 14762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[end << 1]) return end; 14862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 14962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 15062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Search for a matching key before the index. 15162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 15262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[i << 1]) return i; 153f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 154f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 155f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Key not found -- return negative value indicating where a 156f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // new entry for this key should go. We use the end of the 157f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // hash chain to reduce the number of array entries that will 158f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // need to be copied when inserting. 159f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ~end; 160f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 161f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 162f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private void allocArrays(final int size) { 163b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (mHashes == EMPTY_IMMUTABLE_INTS) { 164b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn throw new UnsupportedOperationException("ArrayMap is immutable"); 165b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 166f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (size == (BASE_SIZE*2)) { 167f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 168f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mTwiceBaseCache != null) { 169f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mTwiceBaseCache; 170f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = array; 171f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCache = (Object[])array[0]; 172f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = (int[])array[1]; 173f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = array[1] = null; 174f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCacheSize--; 175f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 176f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 177f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return; 178f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 179f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 180f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else if (size == BASE_SIZE) { 181f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 182f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mBaseCache != null) { 183f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mBaseCache; 184f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = array; 185f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCache = (Object[])array[0]; 186f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = (int[])array[1]; 187f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = array[1] = null; 188f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCacheSize--; 189f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 190f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 191f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return; 192f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 193f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 194f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 195f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 196f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = new int[size]; 197f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = new Object[size<<1]; 198f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 199f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 200f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 201f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (hashes.length == (BASE_SIZE*2)) { 202f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 203f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mTwiceBaseCacheSize < CACHE_SIZE) { 204f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = mTwiceBaseCache; 205f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[1] = hashes; 206f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 207f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[i] = null; 208f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 209f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCache = array; 210f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCacheSize++; 211f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 212f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 213f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 214f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 215f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else if (hashes.length == BASE_SIZE) { 216f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 217f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mBaseCacheSize < CACHE_SIZE) { 218f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = mBaseCache; 219f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[1] = hashes; 220f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 221f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[i] = null; 222f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 223f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCache = array; 224f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCacheSize++; 225f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 226f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 227f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 228f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 229f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 230f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 231f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 232f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 233f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Create a new empty ArrayMap. The default capacity of an array map is 0, and 234f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * will grow once items are added to it. 235f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 236f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public ArrayMap() { 2373e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2383e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 239f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 240f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 241f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 242f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 243f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Create a new ArrayMap with a given initial capacity. 244f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 245f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public ArrayMap(int capacity) { 246f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (capacity == 0) { 2473e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2483e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 249f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 250f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(capacity); 251f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 252f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 253f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 25421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 255b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn private ArrayMap(boolean immutable) { 256b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mHashes = EMPTY_IMMUTABLE_INTS; 257b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 258b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mSize = 0; 259b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 260b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 26108735185f8105710e18ad02297461bec9268e514Chet Haase /** 26208735185f8105710e18ad02297461bec9268e514Chet Haase * Create a new ArrayMap with the mappings from the given ArrayMap. 26308735185f8105710e18ad02297461bec9268e514Chet Haase */ 26408735185f8105710e18ad02297461bec9268e514Chet Haase public ArrayMap(ArrayMap map) { 26508735185f8105710e18ad02297461bec9268e514Chet Haase this(); 26608735185f8105710e18ad02297461bec9268e514Chet Haase if (map != null) { 26708735185f8105710e18ad02297461bec9268e514Chet Haase putAll(map); 26808735185f8105710e18ad02297461bec9268e514Chet Haase } 26908735185f8105710e18ad02297461bec9268e514Chet Haase } 27008735185f8105710e18ad02297461bec9268e514Chet Haase 271f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 272f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Make the array map empty. All storage is released. 273f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 274f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 275f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void clear() { 276b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (mSize > 0) { 277390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn freeArrays(mHashes, mArray, mSize); 2783e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2793e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 280390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn mSize = 0; 281390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn } 282f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 283f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 284f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 285450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn * @hide 286450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 287450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn */ 288450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn public void erase() { 289450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn if (mSize > 0) { 290450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn final int N = mSize<<1; 291450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn final Object[] array = mArray; 292450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn for (int i=0; i<N; i++) { 293450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn array[i] = null; 294450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 2954a7d824c3b41eafc4ff91d3253ff8a9ebd60a454Dianne Hackborn mSize = 0; 296450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 297450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn } 298450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn 299450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn /** 300f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 301f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * items. 302f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 303f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void ensureCapacity(int minimumCapacity) { 304f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length < minimumCapacity) { 30521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] ohashes = mHashes; 30621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] oarray = mArray; 307f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(minimumCapacity); 308390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn if (mSize > 0) { 309390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, mSize); 310390517be2d60dd6e6264150c190c372d89bb331aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 311f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 312f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 313f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 314f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 315f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 316f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 317f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a key exists in the array. 318f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 319f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key to search for. 320f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the key exists, else false. 321f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 322f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 323f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsKey(Object key) { 32462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return key == null ? (indexOfNull() >= 0) : (indexOf(key, key.hashCode()) >= 0); 325f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 326f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 32762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int indexOfValue(Object value) { 328f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize*2; 329f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mArray; 330f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value == null) { 331f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 332f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (array[i] == null) { 333f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 334f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 335f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 336f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 337f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 338f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value.equals(array[i])) { 339f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 340f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 341f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 342f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 343f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return -1; 344f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 345f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 346f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 347f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a value exists in the array. This requires a linear search 348f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * through the entire array. 349f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 350f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to search for. 351f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the value exists, else false. 352f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 353f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 354f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsValue(Object value) { 355f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value) >= 0; 356f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 357f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 358f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 359f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Retrieve a value from the array. 360f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the value to retrieve. 361f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value associated with the given key, 362f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * or null if there is no such key. 363f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 364f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 365f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V get(Object key) { 36662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int index = key == null ? indexOfNull() : indexOf(key, key.hashCode()); 367f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index >= 0 ? (V)mArray[(index<<1)+1] : null; 368f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 369f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 370f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 371f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the key at the given index in the array. 372f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 373f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the key stored at the given index. 374f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 375f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public K keyAt(int index) { 376f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (K)mArray[index << 1]; 377f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 378f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 379f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 380f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the value at the given index in the array. 381f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 382f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value stored at the given index. 383f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 384f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V valueAt(int index) { 385f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (V)mArray[(index << 1) + 1]; 386f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 387f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 388f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 389f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set the value at a given index in the array. 390f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 391f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The new value to store at this index. 392f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the previous value at the given index. 393f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 394f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V setValueAt(int index, V value) { 395f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index << 1) + 1; 396f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn V old = (V)mArray[index]; 397f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 398f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 399f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 400f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 401f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 402f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return true if the array map contains no items. 403f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 404f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 405f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean isEmpty() { 406f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize <= 0; 407f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 408f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 409f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 410f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Add a new value to the array map. 411f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key under which to store the value. <b>Must not be null.</b> If 412f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * this key already exists in the array, its value will be replaced. 413f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to store for the given key. 414f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the old value that was stored for the given key, or null if there 415f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 416f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 417f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 418f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V put(K key, V value) { 41962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash; 42062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index; 42162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key == null) { 42262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = 0; 42362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOfNull(); 42462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } else { 42562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = key.hashCode(); 42662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOf(key, hash); 42762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 428f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 429f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index<<1) + 1; 430f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final V old = (V)mArray[index]; 431f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 432f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 433f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 434f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 435f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = ~index; 436f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize >= mHashes.length) { 437f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 438f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 439f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 440f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 441f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 442f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 443f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 444f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 445f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 446f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > 0) { 447f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 448f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 449f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 450f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 451f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 452f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 453f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 454f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 455f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 456f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 457f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + (index+1)); 458f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 459f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 460f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 461f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 462f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes[index] = hash; 463f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index<<1] = key; 464f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(index<<1)+1] = value; 465f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize++; 466f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 467f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 468f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 469f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 470b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * Special fast path for appending items to the end of the array without validation. 471b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * The array must already be large enough to contain the item. 472b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn * @hide 473b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn */ 474b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn public void append(K key, V value) { 475b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn int index = mSize; 47662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash = key == null ? 0 : key.hashCode(); 477b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (index >= mHashes.length) { 478b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn throw new IllegalStateException("Array is full"); 479b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 480b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn if (index > 0 && mHashes[index-1] > hash) { 481450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn RuntimeException e = new RuntimeException("here"); 482450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn e.fillInStackTrace(); 483450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn Log.w(TAG, "New hash " + hash 484450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn + " is before end of array hash " + mHashes[index-1] 485450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn + " at index " + index + " key " + key, e); 486450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn put(key, value); 487450d8c5b7c936b00fd0d40b5d68670df0fe56daaDianne Hackborn return; 488b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 489b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mSize = index+1; 490b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mHashes[index] = hash; 491b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn index <<= 1; 492b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray[index] = key; 493b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn mArray[index+1] = value; 494b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn } 495b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn 496b87655b3e551c6a32f34084c8533800bbd1aff7dDianne Hackborn /** 497f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 498f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param array The array whose contents are to be retrieved. 499f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 500f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(ArrayMap<? extends K, ? extends V> array) { 501f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = array.mSize; 502f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + N); 503f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase if (mSize == 0) { 504f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase if (N > 0) { 505f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase System.arraycopy(array.mHashes, 0, mHashes, 0, N); 506f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 507f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase mSize = N; 508f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } 509f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } else { 510f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase for (int i=0; i<N; i++) { 511f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase put(array.keyAt(i), array.valueAt(i)); 512f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase } 513f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 514f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 515f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 516f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 517f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove an existing key from the array map. 518f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the mapping to remove. 519f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored under the key, or null if there 520f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 521f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 522f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 523f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V remove(Object key) { 52462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index = key == null ? indexOfNull() : indexOf(key, key.hashCode()); 525f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 526f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return removeAt(index); 527f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 528f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 529f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 530f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 531f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 532f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 533f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove the key/value mapping at the given index. 534f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 535f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored at this index. 536f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 537f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V removeAt(int index) { 53862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final Object old = mArray[(index << 1) + 1]; 539f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize <= 1) { 540f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Now empty. 541f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 542f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(mHashes, mArray, mSize); 5433e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 5443e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 545f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 546f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 547f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 548f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 549f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 550f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // that and BASE_SIZE. 551f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 552f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 553f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 554f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 555f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 556f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 557f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 558f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 559f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 560f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index > 0) { 561f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 562f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 563f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index << 1); 564f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 565f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 566f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 567f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 568f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 569f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 570f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 571f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 572f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 573f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 574f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 575f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 576f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 577f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 578f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 579f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 580f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 581f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[mSize << 1] = null; 582f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(mSize << 1) + 1] = null; 583f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 584f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 58562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return (V)old; 586f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 587f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 588f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 589f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the number of items in this array map. 590f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 591f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 592f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public int size() { 593f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 594f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 595f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 59621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 59721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 59821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 59921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * <p>This implementation returns false if the object is not a map, or 60021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * if the maps have different sizes. Otherwise, for each key in this map, 60121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * values of both maps are compared. If the values for any key are not 60221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * equal, the method returns false, otherwise it returns true. 60321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 60421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 60521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean equals(Object object) { 60621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (this == object) { 60721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 60821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 60921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (object instanceof Map) { 61021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Map<?, ?> map = (Map<?, ?>) object; 61121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (size() != map.size()) { 61221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 61321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 61421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 61521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn try { 61621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=0; i<mSize; i++) { 61721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn K key = keyAt(i); 61821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn V mine = valueAt(i); 61921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object theirs = map.get(key); 62021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mine == null) { 62121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (theirs != null || !map.containsKey(key)) { 62221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 62321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 62421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else if (!mine.equals(theirs)) { 62521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 62621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 62721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 62821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (NullPointerException ignored) { 62921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 63021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (ClassCastException ignored) { 63121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 63221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 63321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 63421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 63521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 63621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 63721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 63821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 63921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 64021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 64121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 64221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public int hashCode() { 64321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] hashes = mHashes; 64421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] array = mArray; 64521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int result = 0; 64621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 64721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object value = array[v]; 64821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 64921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 65021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return result; 65121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 65221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 653a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn /** 654a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * {@inheritDoc} 655a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * 656a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 657a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * this map contains itself as a key or a value, the string "(this Map)" 658a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * will appear in its place. 659a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn */ 660a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn @Override 661a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn public String toString() { 662a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (isEmpty()) { 663a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return "{}"; 664a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 665a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 666a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 667a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('{'); 668a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn for (int i=0; i<mSize; i++) { 669a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (i > 0) { 670a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(", "); 671a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 672a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object key = keyAt(i); 673a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (key != this) { 674a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(key); 675a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 676a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Map)"); 677a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 678a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('='); 679a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object value = valueAt(i); 680a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (value != this) { 681a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(value); 682a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 683a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Map)"); 684a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 685a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 686a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('}'); 687a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return buffer.toString(); 688a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 689a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 690f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 691f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Interop with traditional Java containers. Not as efficient as using 692f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // specialized collection APIs. 693f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 694f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 695f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private MapCollections<K, V> getCollection() { 696f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mCollections == null) { 697f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mCollections = new MapCollections<K, V>() { 698f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 699f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colGetSize() { 700f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 701f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 702f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 703f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 704f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Object colGetEntry(int index, int offset) { 705f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mArray[(index<<1) + offset]; 706f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 707f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 708f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 709f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfKey(Object key) { 71062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 711f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 712f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 713f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 714f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfValue(Object value) { 715f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value); 716f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 717f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 718f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 719f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Map<K, V> colGetMap() { 720f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ArrayMap.this; 721f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 722f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 723f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 724f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colPut(K key, V value) { 725f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(key, value); 726f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 727f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 728f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 729f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected V colSetValue(int index, V value) { 730f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return setValueAt(index, value); 731f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 732f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 733f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 734f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colRemoveAt(int index) { 735f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn removeAt(index); 736f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 737f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 738f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 739f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colClear() { 740f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn clear(); 741f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 742f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn }; 743f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 744f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mCollections; 745f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 746f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 747f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 748f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Determine if the array map contains all of the keys in the given collection. 749f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be checked against. 750f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if this array map contains a key for every entry 751f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in <var>collection</var>, else returns false. 752f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 753f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsAll(Collection<?> collection) { 754f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.containsAllHelper(this, collection); 755f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 756f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 757f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 758f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 759f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param map The map whose contents are to be retrieved. 760f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 761f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 762f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(Map<? extends K, ? extends V> map) { 763f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + map.size()); 764f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 765f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(entry.getKey(), entry.getValue()); 766f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 767f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 768f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 769f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 770f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that exist in the given collection. 771f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to remove keys. 772f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 773f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 774f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean removeAll(Collection<?> collection) { 775f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.removeAllHelper(this, collection); 776f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 777f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 778f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 779f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that do <b>not</b> exist in the given collection. 780f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to determine which 781f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * keys to keep. 782f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 783f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 784f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean retainAll(Collection<?> collection) { 785f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.retainAllHelper(this, collection); 786f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 787f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 788f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 789f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all mappings 790f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 791f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 792f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 793f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 794f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 795f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b></p> the semantics of this 796f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set are subtly different than that of a {@link java.util.HashMap}: most important, 797f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 798f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * object that exists for the entire iterator, so you can <b>not</b> hold on to it 799f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 800f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 801f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 802f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<Map.Entry<K, V>> entrySet() { 803f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getEntrySet(); 804f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 805f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 806f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 807f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all keys 808f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 809f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 810f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 811f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 812f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 813f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 814f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<K> keySet() { 815f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getKeySet(); 816f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 817f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 818f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 819f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Collection} for iterating over and interacting with all values 820f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 821f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 822f4130cf35fa128e36f96e55955d4f5db86197e4aChet Haase * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 823f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 824f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 825f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 826f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Collection<V> values() { 827f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getValues(); 828f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 829f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 830