12290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn/* 22290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Copyright (C) 2013 The Android Open Source Project 32290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 42290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 52290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * you may not use this file except in compliance with the License. 62290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * You may obtain a copy of the License at 72290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 82290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 92290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Unless required by applicable law or agreed to in writing, software 112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * See the License for the specific language governing permissions and 142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * limitations under the License. 152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 172290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpackage android.support.v4.util; 182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 192290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornimport android.util.Log; 202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 212290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornimport java.util.Map; 222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn/** 242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Base implementation of {@link ArrayMap} that doesn't include any standard Java 252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * container API interoperability. These features are generally heavier-weight ways 262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * to interact with the container, so discouraged, but they can be useful to make it 272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * easier to use as a drop-in replacement for HashMap. If you don't need them, this 282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * class can be preferrable since it doesn't bring in any of the implementation of those 292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * APIs, allowing that code to be stripped by ProGuard. 302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 312290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpublic class SimpleArrayMap<K, V> { 322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final boolean DEBUG = false; 332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final String TAG = "ArrayMap"; 342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * The minimum amount by which the capacity of a ArrayMap will increase. 372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * This is tuned to be relatively space-efficient. 382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final int BASE_SIZE = 4; 402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Maximum number of entries to have in array caches. 432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final int CACHE_SIZE = 10; 452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Caches of small array objects to avoid spamming garbage. The cache 482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Object[] variable is a pointer to a linked list of array objects. 492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * The first entry in the array is a pointer to the next array in the 502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * list; the second entry is a pointer to the int[] hash code array for it. 512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static Object[] mBaseCache; 532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static int mBaseCacheSize; 542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static Object[] mTwiceBaseCache; 552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static int mTwiceBaseCacheSize; 562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int[] mHashes; 582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object[] mArray; 592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int mSize; 602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int indexOf(Object key, int hash) { 622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int N = mSize; 632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (N == 0) { 662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ~0; 672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 69dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, hash); 702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index < 0) { 732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return index; 742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // If the key at the returned index matches, that's what we want. 77dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key.equals(mArray[index<<1])) { 782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return index; 792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Search for a matching key after the index. 822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int end; 832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (end = index + 1; end < N && mHashes[end] == hash; end++) { 84dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key.equals(mArray[end << 1])) return end; 852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Search for a matching key before the index. 882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 89dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key.equals(mArray[i << 1])) return i; 90dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 91dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 92dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Key not found -- return negative value indicating where a 93dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // new entry for this key should go. We use the end of the 94dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // hash chain to reduce the number of array entries that will 95dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // need to be copied when inserting. 96dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return ~end; 97dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 98dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 99dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int indexOfNull() { 100dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn final int N = mSize; 101dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 102dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 103dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (N == 0) { 104dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return ~0; 105dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 106dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 107dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, 0); 108dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 109dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 110dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (index < 0) { 111dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return index; 112dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 113dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 114dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // If the key at the returned index matches, that's what we want. 115dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (null == mArray[index<<1]) { 116dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return index; 117dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 118dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 119dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Search for a matching key after the index. 120dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int end; 121dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn for (end = index + 1; end < N && mHashes[end] == 0; end++) { 122dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (null == mArray[end << 1]) return end; 123dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 124dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 125dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Search for a matching key before the index. 126dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 127dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (null == mArray[i << 1]) return i; 1282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Key not found -- return negative value indicating where a 1312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // new entry for this key should go. We use the end of the 1322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // hash chain to reduce the number of array entries that will 1332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // need to be copied when inserting. 1342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ~end; 1352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private void allocArrays(final int size) { 1382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size == (BASE_SIZE*2)) { 1392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 1402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mTwiceBaseCache != null) { 1412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mTwiceBaseCache; 1422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = array; 1432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCache = (Object[])array[0]; 1442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = (int[])array[1]; 1452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = array[1] = null; 1462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCacheSize--; 1472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 1482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 1492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return; 1502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else if (size == BASE_SIZE) { 1532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 1542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mBaseCache != null) { 1552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mBaseCache; 1562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = array; 1572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCache = (Object[])array[0]; 1582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = (int[])array[1]; 1592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = array[1] = null; 1602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCacheSize--; 1612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 1622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 1632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return; 1642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = new int[size]; 1692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = new Object[size<<1]; 1702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 1732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (hashes.length == (BASE_SIZE*2)) { 1742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 1752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mTwiceBaseCacheSize < CACHE_SIZE) { 1762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = mTwiceBaseCache; 1772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[1] = hashes; 1782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 1792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[i] = null; 1802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCache = array; 1822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCacheSize++; 1832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 1842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 1852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else if (hashes.length == BASE_SIZE) { 1882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 1892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mBaseCacheSize < CACHE_SIZE) { 1902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = mBaseCache; 1912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[1] = hashes; 1922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 1932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[i] = null; 1942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCache = array; 1962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCacheSize++; 1972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 1982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 1992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new empty ArrayMap. The default capacity of an array map is 0, and 2062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will grow once items are added to it. 2072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SimpleArrayMap() { 2092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 2112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 2122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new ArrayMap with a given initial capacity. 2162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SimpleArrayMap(int capacity) { 2182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (capacity == 0) { 2192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 2212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 2222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(capacity); 2232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 2252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new ArrayMap with the mappings from the given ArrayMap. 2292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SimpleArrayMap(SimpleArrayMap map) { 2312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn this(); 2322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (map != null) { 2332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn putAll(map); 2342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Make the array map empty. All storage is released. 2392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void clear() { 2412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize != 0) { 2422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn freeArrays(mHashes, mArray, mSize); 2432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 2452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 2462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 2512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * items. 2522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void ensureCapacity(int minimumCapacity) { 2542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mHashes.length < minimumCapacity) { 2552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] ohashes = mHashes; 2562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] oarray = mArray; 2572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(minimumCapacity); 2582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize > 0) { 2592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, mSize); 2602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 2612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn freeArrays(ohashes, oarray, mSize); 2632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Check whether a key exists in the array. 2682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 2692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key to search for. 2702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if the key exists, else false. 2712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean containsKey(Object key) { 27352d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski return indexOfKey(key) >= 0; 27452d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski } 27552d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski 27652d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski /** 27752d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * Returns the index of a key in the set. 27852d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * 27952d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * @param key The key to search for. 28052d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * @return Returns the index of the key if it exists, else a negative integer. 28152d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski */ 28252d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski public int indexOfKey(Object key) { 28352d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 2842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int indexOfValue(Object value) { 2872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int N = mSize*2; 2882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mArray; 2892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value == null) { 2902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=1; i<N; i+=2) { 2912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (array[i] == null) { 2922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return i>>1; 2932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 2962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=1; i<N; i+=2) { 2972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value.equals(array[i])) { 2982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return i>>1; 2992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return -1; 3032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Check whether a value exists in the array. This requires a linear search 3072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * through the entire array. 3082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 3092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param value The value to search for. 3102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if the value exists, else false. 3112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean containsValue(Object value) { 3132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return indexOfValue(value) >= 0; 3142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Retrieve a value from the array. 3182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key of the value to retrieve. 3192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value associated with the given key, 3202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * or null if there is no such key. 3212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V get(Object key) { 32352d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski final int index = indexOfKey(key); 3242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return index >= 0 ? (V)mArray[(index<<1)+1] : null; 3252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return the key at the given index in the array. 3292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 3302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the key stored at the given index. 3312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public K keyAt(int index) { 3332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return (K)mArray[index << 1]; 3342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return the value at the given index in the array. 3382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 3392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value stored at the given index. 3402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V valueAt(int index) { 3422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return (V)mArray[(index << 1) + 1]; 3432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Set the value at a given index in the array. 3472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 3482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param value The new value to store at this index. 3492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the previous value at the given index. 3502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V setValueAt(int index, V value) { 3522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn index = (index << 1) + 1; 3532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn V old = (V)mArray[index]; 3542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[index] = value; 3552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return old; 3562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return true if the array map contains no items. 3602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean isEmpty() { 3622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mSize <= 0; 3632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Add a new value to the array map. 3672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key under which to store the value. <b>Must not be null.</b> If 3682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this key already exists in the array, its value will be replaced. 3692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param value The value to store for the given key. 3702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the old value that was stored for the given key, or null if there 3712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * was no such key. 3722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V put(K key, V value) { 374dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn final int hash; 375dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int index; 376dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key == null) { 377dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn hash = 0; 378dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn index = indexOfNull(); 379dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } else { 380dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn hash = key.hashCode(); 381dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn index = indexOf(key, hash); 382dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 3832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index >= 0) { 3842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn index = (index<<1) + 1; 3852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final V old = (V)mArray[index]; 3862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[index] = value; 3872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return old; 3882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn index = ~index; 3912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize >= mHashes.length) { 3922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 3932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 3942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 3962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] ohashes = mHashes; 3982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] oarray = mArray; 3992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(n); 4002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mHashes.length > 0) { 4022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 4032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 4042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 4052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn freeArrays(ohashes, oarray, mSize); 4082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index < mSize) { 4112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 4122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " to " + (index+1)); 4132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 4142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 4152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes[index] = hash; 4182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[index<<1] = key; 4192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[(index<<1)+1] = value; 4202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize++; 4212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return null; 4222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 4252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 4262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param array The array whose contents are to be retrieved. 4272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 4282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void putAll(SimpleArrayMap<? extends K, ? extends V> array) { 4292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int N = array.mSize; 4302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn ensureCapacity(mSize + N); 4312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize == 0) { 4322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (N > 0) { 4332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(array.mHashes, 0, mHashes, 0, N); 4342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 4352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = N; 4362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 4382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<N; i++) { 4392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn put(array.keyAt(i), array.valueAt(i)); 4402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 4452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Remove an existing key from the array map. 4462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key of the mapping to remove. 4472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value that was stored under the key, or null if there 4482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * was no such key. 4492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 4502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V remove(Object key) { 45152d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski final int index = indexOfKey(key); 4522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index >= 0) { 4532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return removeAt(index); 4542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return null; 4572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 4602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Remove the key/value mapping at the given index. 4612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 4622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value that was stored at this index. 4632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 4642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V removeAt(int index) { 465dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn final Object old = mArray[(index << 1) + 1]; 4662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize <= 1) { 4672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Now empty. 4682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 4692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn freeArrays(mHashes, mArray, mSize); 4702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 4712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 4722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 4732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 4742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 4752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 4762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 4772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // that and BASE_SIZE. 4782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 4792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 4812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] ohashes = mHashes; 4832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] oarray = mArray; 4842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(n); 4852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize--; 4872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index > 0) { 4882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 4892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 4902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index << 1); 4912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index < mSize) { 4932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 4942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " to " + index); 4952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 4962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 4972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn (mSize - index) << 1); 4982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 5002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize--; 5012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index < mSize) { 5022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 5032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " to " + index); 5042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 5052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 5062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn (mSize - index) << 1); 5072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[mSize << 1] = null; 5092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[(mSize << 1) + 1] = null; 5102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 512dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return (V)old; 5132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 5162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return the number of items in this array map. 5172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 5182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public int size() { 5192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mSize; 5202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 5232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 5242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 5255b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * <p>This implementation returns false if the object is not a Map or 5265b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * SimpleArrayMap, or if the maps have different sizes. Otherwise, for each 5275b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * key in this map, values of both maps are compared. If the values for any 5285b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * key are not equal, the method returns false, otherwise it returns true. 5292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 5302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 5312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean equals(Object object) { 5322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (this == object) { 5332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return true; 5342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5355b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (object instanceof SimpleArrayMap) { 5365b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran SimpleArrayMap<?, ?> map = (SimpleArrayMap<?, ?>) object; 5375b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (size() != map.size()) { 5385b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 5395b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 5405b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran 5415b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran try { 5425b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran for (int i=0; i<mSize; i++) { 5435b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran K key = keyAt(i); 5445b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran V mine = valueAt(i); 5455b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran Object theirs = map.get(key); 5465b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (mine == null) { 5475b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (theirs != null || !map.containsKey(key)) { 5485b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 5495b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 5505b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } else if (!mine.equals(theirs)) { 5515b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 5525b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 5535b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 5545b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } catch (NullPointerException ignored) { 5555b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 5565b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } catch (ClassCastException ignored) { 5575b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 5585b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 5595b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return true; 5605b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } else if (object instanceof Map) { 5612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Map<?, ?> map = (Map<?, ?>) object; 5622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size() != map.size()) { 5632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 5642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn try { 5672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 5682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn K key = keyAt(i); 5692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn V mine = valueAt(i); 5702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object theirs = map.get(key); 5712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mine == null) { 5722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (theirs != null || !map.containsKey(key)) { 5732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 5742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else if (!mine.equals(theirs)) { 5762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 5772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } catch (NullPointerException ignored) { 5802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 5812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } catch (ClassCastException ignored) { 5822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 5832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return true; 5852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 5872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 5902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 5912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 5922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 5932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public int hashCode() { 5942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] hashes = mHashes; 5952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mArray; 5962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int result = 0; 5972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 5982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = array[v]; 5992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 6002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return result; 6022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 6042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 6052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 6062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 6072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 6082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this map contains itself as a key or a value, the string "(this Map)" 6092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will appear in its place. 6102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 6112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 6122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public String toString() { 6132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (isEmpty()) { 6142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return "{}"; 6152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 6172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 6182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('{'); 6192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 6202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (i > 0) { 6212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(", "); 6222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object key = keyAt(i); 6242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (key != this) { 6252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(key); 6262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 6272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 6282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('='); 6302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = valueAt(i); 6312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value != this) { 6322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(value); 6332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 6342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 6352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('}'); 6382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return buffer.toString(); 6392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn} 641