ArrayMap.java revision f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccda
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, 37f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * the performance difference is not significant, less than 50%. For larger numbers of items 38f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * this data structure should be avoided.</p> 39f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 40f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> unlike {@link java.util.HashMap}, this container does not support 41f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * null keys.</p> 42f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 43f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p>Because this container is intended to better balance memory use, unlike most other 44f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * standard Java containers it will shrink its array as items are removed from it. Currently 45f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * you have no control over this shrinking -- if you set a capacity and then remove an 46f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * item, it may reduce the capacity to better match the current size. In the future an 47f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p> 48f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 49f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @hide 50f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 51f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornpublic final class ArrayMap<K, V> implements Map<K, V> { 52f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final boolean DEBUG = false; 53f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final String TAG = "ArrayMap"; 54f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 55f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 56f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * The minimum amount by which the capacity of a ArrayMap will increase. 57f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * This is tuned to be relatively space-efficient. 58f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 59f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final int BASE_SIZE = 4; 60f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 61f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 62f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Maximum number of entries to have in array caches. 63f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 64f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static final int CACHE_SIZE = 10; 65f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 66f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 67f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Caches of small array objects to avoid spamming garbage. The cache 68f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Object[] variable is a pointer to a linked list of array objects. 69f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * The first entry in the array is a pointer to the next array in the 70f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * list; the second entry is a pointer to the int[] hash code array for it. 71f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 72f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static Object[] mBaseCache; 73f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static int mBaseCacheSize; 74f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static Object[] mTwiceBaseCache; 75f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn static int mTwiceBaseCacheSize; 76f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 77f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int[] mHashes; 78f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Object[] mArray; 79f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int mSize; 80f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn MapCollections<K, V> mCollections; 81f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 82f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private int indexOf(Object key, int hash) { 83f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize; 84f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 85f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 86f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (N == 0) { 87f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ~0; 88f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 89f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 90f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int index = SparseArray.binarySearch(mHashes, N, hash); 91f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 92f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 93f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < 0) { 94f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index; 95f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 96f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 97f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the key at the returned index matches, that's what we want. 98f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mArray[index<<1].equals(key)) { 99f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index; 100f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 101f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 102f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Search for a matching key after the index. 103f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int end; 104f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (end = index + 1; end < N && mHashes[end] == hash; end++) { 105f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mArray[end << 1].equals(key)) return end; 106f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 107f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 108f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Search for a matching key before the index. 109f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 110f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mArray[i << 1].equals(key)) return i; 111f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 112f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 113f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Key not found -- return negative value indicating where a 114f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // new entry for this key should go. We use the end of the 115f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // hash chain to reduce the number of array entries that will 116f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // need to be copied when inserting. 117f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ~end; 118f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 119f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 120f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private void allocArrays(final int size) { 121f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (size == (BASE_SIZE*2)) { 122f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 123f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mTwiceBaseCache != null) { 124f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mTwiceBaseCache; 125f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = array; 126f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCache = (Object[])array[0]; 127f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = (int[])array[1]; 128f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = array[1] = null; 129f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCacheSize--; 130f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 131f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 132f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return; 133f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 134f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 135f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else if (size == BASE_SIZE) { 136f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 137f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mBaseCache != null) { 138f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mBaseCache; 139f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = array; 140f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCache = (Object[])array[0]; 141f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = (int[])array[1]; 142f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = array[1] = null; 143f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCacheSize--; 144f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 145f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 146f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return; 147f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 148f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 149f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 150f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 151f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = new int[size]; 152f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = new Object[size<<1]; 153f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 154f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 155f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 156f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (hashes.length == (BASE_SIZE*2)) { 157f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 158f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mTwiceBaseCacheSize < CACHE_SIZE) { 159f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = mTwiceBaseCache; 160f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[1] = hashes; 161f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 162f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[i] = null; 163f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 164f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCache = array; 165f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mTwiceBaseCacheSize++; 166f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 167f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 168f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 169f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 170f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else if (hashes.length == BASE_SIZE) { 171f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn synchronized (ArrayMap.class) { 172f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mBaseCacheSize < CACHE_SIZE) { 173f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[0] = mBaseCache; 174f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[1] = hashes; 175f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 176f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn array[i] = null; 177f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 178f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCache = array; 179f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mBaseCacheSize++; 180f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 181f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 182f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 183f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 184f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 185f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 186f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 187f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 188f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Create a new empty ArrayMap. The default capacity of an array map is 0, and 189f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * will grow once items are added to it. 190f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 191f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public ArrayMap() { 192f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = SparseArray.EMPTY_INTS; 193f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = SparseArray.EMPTY_OBJECTS; 194f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 195f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 196f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 197f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 198f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Create a new ArrayMap with a given initial capacity. 199f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 200f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public ArrayMap(int capacity) { 201f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (capacity == 0) { 202f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = SparseArray.EMPTY_INTS; 203f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = SparseArray.EMPTY_OBJECTS; 204f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 205f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(capacity); 206f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 207f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 208f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 209f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 210f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 211f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Make the array map empty. All storage is released. 212f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 213f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 214f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void clear() { 215f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(mHashes, mArray, mSize); 216f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = SparseArray.EMPTY_INTS; 217f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = SparseArray.EMPTY_OBJECTS; 218f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 219f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 220f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 221f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 222f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 223f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * items. 224f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 225f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void ensureCapacity(int minimumCapacity) { 226f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length < minimumCapacity) { 227f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int[] ohashes = mHashes; 228f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Object[] oarray = mArray; 229f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(minimumCapacity); 230f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > 0) { 231f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, mHashes.length); 232f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, mArray.length); 233f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 234f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 235f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 236f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 237f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 238f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 239f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a key exists in the array. 240f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 241f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key to search for. 242f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the key exists, else false. 243f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 244f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 245f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsKey(Object key) { 246f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOf(key, key.hashCode()) >= 0; 247f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 248f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 249f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private int indexOfValue(Object value) { 250f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = mSize*2; 251f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] array = mArray; 252f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value == null) { 253f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 254f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (array[i] == null) { 255f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 256f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 257f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 258f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 259f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=1; i<N; i+=2) { 260f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (value.equals(array[i])) { 261f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return i>>1; 262f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 263f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 264f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 265f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return -1; 266f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 267f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 268f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 269f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Check whether a value exists in the array. This requires a linear search 270f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * through the entire array. 271f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 272f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to search for. 273f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if the value exists, else false. 274f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 275f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 276f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsValue(Object value) { 277f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value) >= 0; 278f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 279f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 280f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 281f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Retrieve a value from the array. 282f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the value to retrieve. 283f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value associated with the given key, 284f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * or null if there is no such key. 285f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 286f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 287f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V get(Object key) { 288f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int index = indexOf(key, key.hashCode()); 289f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return index >= 0 ? (V)mArray[(index<<1)+1] : null; 290f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 291f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 292f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 293f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the key at the given index in the array. 294f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 295f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the key stored at the given index. 296f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 297f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public K keyAt(int index) { 298f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (K)mArray[index << 1]; 299f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 300f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 301f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 302f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the value at the given index in the array. 303f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 304f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value stored at the given index. 305f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 306f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V valueAt(int index) { 307f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return (V)mArray[(index << 1) + 1]; 308f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 309f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 310f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 311f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set the value at a given index in the array. 312f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 313f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The new value to store at this index. 314f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the previous value at the given index. 315f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 316f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V setValueAt(int index, V value) { 317f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index << 1) + 1; 318f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn V old = (V)mArray[index]; 319f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 320f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 321f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 322f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 323f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 324f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return true if the array map contains no items. 325f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 326f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 327f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean isEmpty() { 328f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize <= 0; 329f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 330f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 331f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 332f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Add a new value to the array map. 333f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key under which to store the value. <b>Must not be null.</b> If 334f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * this key already exists in the array, its value will be replaced. 335f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param value The value to store for the given key. 336f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the old value that was stored for the given key, or null if there 337f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 338f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 339f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 340f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V put(K key, V value) { 341f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int hash = key.hashCode(); 342f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int index = indexOf(key, hash); 343f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 344f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = (index<<1) + 1; 345f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final V old = (V)mArray[index]; 346f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index] = value; 347f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 348f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 349f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 350f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn index = ~index; 351f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize >= mHashes.length) { 352f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 353f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 354f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 355f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 356f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 357f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 358f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 359f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 360f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 361f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > 0) { 362f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 363f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 364f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 365f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 366f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 367f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(ohashes, oarray, mSize); 368f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 369f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 370f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 371f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 372f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + (index+1)); 373f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 374f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 375f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 376f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 377f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes[index] = hash; 378f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[index<<1] = key; 379f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(index<<1)+1] = value; 380f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize++; 381f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 382f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 383f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 384f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 385f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 386f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param array The array whose contents are to be retrieved. 387f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 388f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(ArrayMap<? extends K, ? extends V> array) { 389f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int N = array.mSize; 390f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + N); 391f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (int i=0; i<N; i++) { 392f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(array.keyAt(i), array.valueAt(i)); 393f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 394f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 395f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 396f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 397f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove an existing key from the array map. 398f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param key The key of the mapping to remove. 399f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored under the key, or null if there 400f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * was no such key. 401f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 402f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 403f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V remove(Object key) { 404f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn int index = indexOf(key, key.hashCode()); 405f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index >= 0) { 406f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return removeAt(index); 407f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 408f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 409f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return null; 410f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 411f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 412f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 413f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove the key/value mapping at the given index. 414f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 415f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns the value that was stored at this index. 416f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 417f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public V removeAt(int index) { 418f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final V old = (V)mArray[(index << 1) + 1]; 419f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mSize <= 1) { 420f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Now empty. 421f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 422f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn freeArrays(mHashes, mArray, mSize); 423f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mHashes = SparseArray.EMPTY_INTS; 424f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray = SparseArray.EMPTY_OBJECTS; 425f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize = 0; 426f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 427f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 428f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 429f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 430f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // that and BASE_SIZE. 431f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 432f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 433f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 434f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 435f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final int[] ohashes = mHashes; 436f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn final Object[] oarray = mArray; 437f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn allocArrays(n); 438f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 439f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 440f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index > 0) { 441f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 442f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 443f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index << 1); 444f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 445f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 446f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 447f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 448f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 449f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 450f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 451f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 452f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 453f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mSize--; 454f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (index < mSize) { 455f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 456f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn + " to " + index); 457f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 458f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 459f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn (mSize - index) << 1); 460f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 461f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[mSize << 1] = null; 462f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mArray[(mSize << 1) + 1] = null; 463f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 464f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 465f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return old; 466f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 467f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 468f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 469f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return the number of items in this array map. 470f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 471f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 472f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public int size() { 473f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 474f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 475f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 476f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 477f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Interop with traditional Java containers. Not as efficient as using 478f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // specialized collection APIs. 479f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // ------------------------------------------------------------------------ 480f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 481f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private MapCollections<K, V> getCollection() { 482f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (mCollections == null) { 483f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mCollections = new MapCollections<K, V>() { 484f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 485f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colGetSize() { 486f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mSize; 487f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 488f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 489f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 490f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Object colGetEntry(int index, int offset) { 491f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mArray[(index<<1) + offset]; 492f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 493f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 494f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 495f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfKey(Object key) { 496f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOf(key, key.hashCode()); 497f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 498f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 499f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 500f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected int colIndexOfValue(Object value) { 501f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return indexOfValue(value); 502f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 503f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 504f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 505f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected Map<K, V> colGetMap() { 506f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return ArrayMap.this; 507f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 508f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 509f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 510f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colPut(K key, V value) { 511f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(key, value); 512f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 513f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 514f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 515f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected V colSetValue(int index, V value) { 516f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return setValueAt(index, value); 517f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 518f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 519f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 520f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colRemoveAt(int index) { 521f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn removeAt(index); 522f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 523f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 524f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 525f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn protected void colClear() { 526f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn clear(); 527f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 528f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn }; 529f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 530f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return mCollections; 531f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 532f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 533f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 534f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Determine if the array map contains all of the keys in the given collection. 535f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be checked against. 536f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if this array map contains a key for every entry 537f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in <var>collection</var>, else returns false. 538f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 539f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean containsAll(Collection<?> collection) { 540f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.containsAllHelper(this, collection); 541f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 542f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 543f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 544f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 545f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param map The map whose contents are to be retrieved. 546f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 547f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 548f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public void putAll(Map<? extends K, ? extends V> map) { 549f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ensureCapacity(mSize + map.size()); 550f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 551f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn put(entry.getKey(), entry.getValue()); 552f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 553f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 554f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 555f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 556f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that exist in the given collection. 557f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to remove keys. 558f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 559f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 560f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean removeAll(Collection<?> collection) { 561f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.removeAllHelper(this, collection); 562f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 563f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 564f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 565f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Remove all keys in the array map that do <b>not</b> exist in the given collection. 566f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @param collection The collection whose contents are to be used to determine which 567f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * keys to keep. 568f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 569f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 570f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public boolean retainAll(Collection<?> collection) { 571f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return MapCollections.retainAllHelper(this, collection); 572f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 573f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 574f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 575f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all mappings 576f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 577f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 578f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 579f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 580f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 581f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b></p> the semantics of this 582f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Set are subtly different than that of a {@link java.util.HashMap}: most important, 583f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 584f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * object that exists for the entire iterator, so you can <b>not</b> hold on to it 585f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 586f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 587f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 588f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<Map.Entry<K, V>> entrySet() { 589f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getEntrySet(); 590f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 591f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 592f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 593f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all keys 594f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 595f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 596f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it 597f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 598f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 599f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 600f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Set<K> keySet() { 601f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getKeySet(); 602f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 603f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 604f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /** 605f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * Return a {@link java.util.Collection} for iterating over and interacting with all values 606f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * in the array map. 607f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * 608f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it 609f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * requires generating a number of temporary objects.</p> 610f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn */ 611f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn @Override 612f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public Collection<V> values() { 613f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return getCollection().getValues(); 614f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 615f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 616