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 21cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shuklaimport java.util.ConcurrentModificationException; 222290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornimport java.util.Map; 232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn/** 252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Base implementation of {@link ArrayMap} that doesn't include any standard Java 262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * container API interoperability. These features are generally heavier-weight ways 272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * to interact with the container, so discouraged, but they can be useful to make it 282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * easier to use as a drop-in replacement for HashMap. If you don't need them, this 292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * class can be preferrable since it doesn't bring in any of the implementation of those 302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * APIs, allowing that code to be stripped by ProGuard. 312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 322290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpublic class SimpleArrayMap<K, V> { 332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final boolean DEBUG = false; 342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final String TAG = "ArrayMap"; 352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 37cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * Attempt to spot concurrent modifications to this data structure. 38cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * 39cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * It's best-effort, but any time we can throw something more diagnostic than an 40cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * ArrayIndexOutOfBoundsException deep in the ArrayMap internals it's going to 41cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * save a lot of development time. 42cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * 43cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * Good times to look for CME include after any allocArrays() call and at the end of 44cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla * functions that change mSize (put/remove/clear). 45cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla */ 46cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true; 47cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla 48cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla /** 492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * The minimum amount by which the capacity of a ArrayMap will increase. 502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * This is tuned to be relatively space-efficient. 512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final int BASE_SIZE = 4; 532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Maximum number of entries to have in array caches. 562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static final int CACHE_SIZE = 10; 582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Caches of small array objects to avoid spamming garbage. The cache 612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Object[] variable is a pointer to a linked list of array objects. 622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * The first entry in the array is a pointer to the next array in the 632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * list; the second entry is a pointer to the int[] hash code array for it. 642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static Object[] mBaseCache; 662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static int mBaseCacheSize; 672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static Object[] mTwiceBaseCache; 682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn static int mTwiceBaseCacheSize; 692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int[] mHashes; 712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object[] mArray; 722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int mSize; 732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 74cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla private static int binarySearchHashes(int[] hashes, int N, int hash) { 75cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla try { 76cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla return ContainerHelpers.binarySearch(hashes, N, hash); 77cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } catch (ArrayIndexOutOfBoundsException e) { 78cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS) { 79cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 80cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } else { 81cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw e; // the cache is poisoned at this point, there's not much we can do 82cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 83cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 84cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 85cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla 862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int indexOf(Object key, int hash) { 872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int N = mSize; 882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (N == 0) { 912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ~0; 922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 94cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla int index = binarySearchHashes(mHashes, N, hash); 952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index < 0) { 982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return index; 992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // If the key at the returned index matches, that's what we want. 102dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key.equals(mArray[index<<1])) { 1032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return index; 1042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Search for a matching key after the index. 1072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int end; 1082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (end = index + 1; end < N && mHashes[end] == hash; end++) { 109dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key.equals(mArray[end << 1])) return end; 1102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Search for a matching key before the index. 1132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 114dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key.equals(mArray[i << 1])) return i; 115dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 116dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 117dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Key not found -- return negative value indicating where a 118dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // new entry for this key should go. We use the end of the 119dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // hash chain to reduce the number of array entries that will 120dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // need to be copied when inserting. 121dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return ~end; 122dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 123dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 124dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int indexOfNull() { 125dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn final int N = mSize; 126dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 127dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 128dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (N == 0) { 129dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return ~0; 130dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 131dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 132cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla int index = binarySearchHashes(mHashes, N, 0); 133dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 134dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 135dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (index < 0) { 136dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return index; 137dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 138dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 139dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // If the key at the returned index matches, that's what we want. 140dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (null == mArray[index<<1]) { 141dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return index; 142dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 143dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 144dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Search for a matching key after the index. 145dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int end; 146dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn for (end = index + 1; end < N && mHashes[end] == 0; end++) { 147dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (null == mArray[end << 1]) return end; 148dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 149dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn 150dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn // Search for a matching key before the index. 151dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 152dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (null == mArray[i << 1]) return i; 1532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Key not found -- return negative value indicating where a 1562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // new entry for this key should go. We use the end of the 1572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // hash chain to reduce the number of array entries that will 1582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // need to be copied when inserting. 1592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ~end; 1602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 162ad1b0e82100ee31e70040d77bfa4d847b2bf0864Aurimas Liutikas @SuppressWarnings("ArrayToString") 1632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private void allocArrays(final int size) { 1642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size == (BASE_SIZE*2)) { 1652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 1662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mTwiceBaseCache != null) { 1672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mTwiceBaseCache; 1682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = array; 1692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCache = (Object[])array[0]; 1702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = (int[])array[1]; 1712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = array[1] = null; 1722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCacheSize--; 1732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 1742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 1752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return; 1762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else if (size == BASE_SIZE) { 1792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 1802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mBaseCache != null) { 1812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mBaseCache; 1822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = array; 1832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCache = (Object[])array[0]; 1842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = (int[])array[1]; 1852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = array[1] = null; 1862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCacheSize--; 1872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 1882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 1892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return; 1902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = new int[size]; 1952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = new Object[size<<1]; 1962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 198ad1b0e82100ee31e70040d77bfa4d847b2bf0864Aurimas Liutikas @SuppressWarnings("ArrayToString") 1992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 2002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (hashes.length == (BASE_SIZE*2)) { 2012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 2022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mTwiceBaseCacheSize < CACHE_SIZE) { 2032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = mTwiceBaseCache; 2042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[1] = hashes; 2052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 2062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[i] = null; 2072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCache = array; 2092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mTwiceBaseCacheSize++; 2102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 2112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 2122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else if (hashes.length == BASE_SIZE) { 2152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn synchronized (ArrayMap.class) { 2162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mBaseCacheSize < CACHE_SIZE) { 2172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[0] = mBaseCache; 2182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[1] = hashes; 2192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=(size<<1)-1; i>=2; i--) { 2202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn array[i] = null; 2212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCache = array; 2232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mBaseCacheSize++; 2242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 2252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " now have " + mBaseCacheSize + " entries"); 2262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new empty ArrayMap. The default capacity of an array map is 0, and 2332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will grow once items are added to it. 2342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SimpleArrayMap() { 2362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 2382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 2392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new ArrayMap with a given initial capacity. 2432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SimpleArrayMap(int capacity) { 2452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (capacity == 0) { 2462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 2482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 2492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(capacity); 2502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 2522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new ArrayMap with the mappings from the given ArrayMap. 2562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 257bd23561c207981ccce302827a0a25b074dfb9e04Alan Viverette public SimpleArrayMap(SimpleArrayMap<K, V> map) { 2582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn this(); 2592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (map != null) { 2602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn putAll(map); 2612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Make the array map empty. All storage is released. 2662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void clear() { 268cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (mSize > 0) { 269cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int[] ohashes = mHashes; 270cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final Object[] oarray = mArray; 271cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int osize = mSize; 2722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 2732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 2742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = 0; 275cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla freeArrays(ohashes, oarray, osize); 276cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 277cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) { 278cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 2792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 2822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 2832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 2842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * items. 2852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void ensureCapacity(int minimumCapacity) { 287cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int osize = mSize; 2882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mHashes.length < minimumCapacity) { 2892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] ohashes = mHashes; 2902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] oarray = mArray; 2912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(minimumCapacity); 2922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize > 0) { 293cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla System.arraycopy(ohashes, 0, mHashes, 0, osize); 294cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla System.arraycopy(oarray, 0, mArray, 0, osize<<1); 2952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 296cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla freeArrays(ohashes, oarray, osize); 297cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 298cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) { 299cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 3002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Check whether a key exists in the array. 3052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 3062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key to search for. 3072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if the key exists, else false. 3082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean containsKey(Object key) { 31052d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski return indexOfKey(key) >= 0; 31152d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski } 31252d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski 31352d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski /** 31452d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * Returns the index of a key in the set. 31552d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * 31652d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * @param key The key to search for. 31752d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski * @return Returns the index of the key if it exists, else a negative integer. 31852d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski */ 31952d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski public int indexOfKey(Object key) { 32052d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 3212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int indexOfValue(Object value) { 3242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int N = mSize*2; 3252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mArray; 3262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value == null) { 3272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=1; i<N; i+=2) { 3282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (array[i] == null) { 3292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return i>>1; 3302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 3332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=1; i<N; i+=2) { 3342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value.equals(array[i])) { 3352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return i>>1; 3362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return -1; 3402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Check whether a value exists in the array. This requires a linear search 3442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * through the entire array. 3452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 3462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param value The value to search for. 3472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if the value exists, else false. 3482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean containsValue(Object value) { 3502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return indexOfValue(value) >= 0; 3512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Retrieve a value from the array. 3552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key of the value to retrieve. 3562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value associated with the given key, 3572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * or null if there is no such key. 3582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V get(Object key) { 36052d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski final int index = indexOfKey(key); 3612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return index >= 0 ? (V)mArray[(index<<1)+1] : null; 3622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return the key at the given index in the array. 3662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 3672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the key stored at the given index. 3682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public K keyAt(int index) { 3702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return (K)mArray[index << 1]; 3712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return the value at the given index in the array. 3752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 3762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value stored at the given index. 3772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V valueAt(int index) { 3792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return (V)mArray[(index << 1) + 1]; 3802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Set the value at a given index in the array. 3842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 3852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param value The new value to store at this index. 3862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the previous value at the given index. 3872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V setValueAt(int index, V value) { 3892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn index = (index << 1) + 1; 3902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn V old = (V)mArray[index]; 3912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[index] = value; 3922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return old; 3932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 3952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return true if the array map contains no items. 3972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean isEmpty() { 3992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mSize <= 0; 4002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 4032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Add a new value to the array map. 4042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key under which to store the value. <b>Must not be null.</b> If 4052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this key already exists in the array, its value will be replaced. 4062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param value The value to store for the given key. 4072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the old value that was stored for the given key, or null if there 4082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * was no such key. 4092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 4102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V put(K key, V value) { 411cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int osize = mSize; 412dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn final int hash; 413dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn int index; 414dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn if (key == null) { 415dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn hash = 0; 416dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn index = indexOfNull(); 417dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } else { 418dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn hash = key.hashCode(); 419dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn index = indexOf(key, hash); 420dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn } 4212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index >= 0) { 4222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn index = (index<<1) + 1; 4232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final V old = (V)mArray[index]; 4242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[index] = value; 4252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return old; 4262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn index = ~index; 429cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (osize >= mHashes.length) { 430cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) 431cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 4322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 4342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] ohashes = mHashes; 4362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] oarray = mArray; 4372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(n); 4382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 439cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 440cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 441cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 442cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla 4432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mHashes.length > 0) { 444cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0"); 4452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 4462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 4472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 449cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla freeArrays(ohashes, oarray, osize); 4502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 452cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (index < osize) { 453cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index) 4542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " to " + (index+1)); 455cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla System.arraycopy(mHashes, index, mHashes, index + 1, osize - index); 4562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 4572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 459cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS) { 460cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (osize != mSize || index >= mHashes.length) { 461cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 462cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 463cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 464cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla 4652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes[index] = hash; 4662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[index<<1] = key; 4672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray[(index<<1)+1] = value; 4682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize++; 4692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return null; 4702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 4732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 4742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param array The array whose contents are to be retrieved. 4752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 4762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void putAll(SimpleArrayMap<? extends K, ? extends V> array) { 4772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int N = array.mSize; 4782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn ensureCapacity(mSize + N); 4792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mSize == 0) { 4802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (N > 0) { 4812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(array.mHashes, 0, mHashes, 0, N); 4822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 4832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mSize = N; 4842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 4862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<N; i++) { 4872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn put(array.keyAt(i), array.valueAt(i)); 4882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 4922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 4932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Remove an existing key from the array map. 4942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param key The key of the mapping to remove. 4952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value that was stored under the key, or null if there 4962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * was no such key. 4972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 4982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V remove(Object key) { 49952d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski final int index = indexOfKey(key); 5002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index >= 0) { 5012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return removeAt(index); 5022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return null; 5052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 5082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Remove the key/value mapping at the given index. 5092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 5102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns the value that was stored at this index. 5112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 5122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public V removeAt(int index) { 513dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn final Object old = mArray[(index << 1) + 1]; 514cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int osize = mSize; 515cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int nsize; 516cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (osize <= 1) { 5172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Now empty. 5182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 519cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla freeArrays(mHashes, mArray, osize); 5202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mHashes = ContainerHelpers.EMPTY_INTS; 5212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mArray = ContainerHelpers.EMPTY_OBJECTS; 522cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla nsize = 0; 5232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 524cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla nsize = osize - 1; 5252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 5262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 5272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 5282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn // that and BASE_SIZE. 529cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2); 5302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 5322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] ohashes = mHashes; 5342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] oarray = mArray; 5352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn allocArrays(n); 5362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 537cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 538cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 539cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 540cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla 5412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (index > 0) { 5422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 5432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 5442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index << 1); 5452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 546cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (index < nsize) { 547cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize 5482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " to " + index); 549cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index); 5502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 551cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla (nsize - index) << 1); 5522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 554cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (index < nsize) { 555cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize 5562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn + " to " + index); 557cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index); 5582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 559cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla (nsize - index) << 1); 5602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 561cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla mArray[nsize << 1] = null; 562cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla mArray[(nsize << 1) + 1] = null; 5632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 565cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 566cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla throw new ConcurrentModificationException(); 567cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla } 568cde1e1ab92ed386095d847fcb6d04b699e60ff8dSuprabh Shukla mSize = nsize; 569dd89bdcaf5609ad2641a980ff48321a647471a3dDianne Hackborn return (V)old; 5702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 5732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return the number of items in this array map. 5742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 5752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public int size() { 5762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mSize; 5772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 5792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 5802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 5812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 5825b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * <p>This implementation returns false if the object is not a Map or 5835b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * SimpleArrayMap, or if the maps have different sizes. Otherwise, for each 5845b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * key in this map, values of both maps are compared. If the values for any 5855b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran * key are not equal, the method returns false, otherwise it returns true. 5862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 5872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 5882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean equals(Object object) { 5892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (this == object) { 5902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return true; 5912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 5925b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (object instanceof SimpleArrayMap) { 5935b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran SimpleArrayMap<?, ?> map = (SimpleArrayMap<?, ?>) object; 5945b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (size() != map.size()) { 5955b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 5965b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 5975b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran 5985b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran try { 5995b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran for (int i=0; i<mSize; i++) { 6005b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran K key = keyAt(i); 6015b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran V mine = valueAt(i); 6025b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran Object theirs = map.get(key); 6035b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (mine == null) { 6045b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran if (theirs != null || !map.containsKey(key)) { 6055b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 6065b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 6075b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } else if (!mine.equals(theirs)) { 6085b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 6095b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 6105b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 6115b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } catch (NullPointerException ignored) { 6125b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 6135b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } catch (ClassCastException ignored) { 6145b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return false; 6155b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } 6165b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran return true; 6175b6d31ca0497e11d9af12810fefbc81a88f75d22Andrew Walbran } else if (object instanceof Map) { 6182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Map<?, ?> map = (Map<?, ?>) object; 6192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size() != map.size()) { 6202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 6212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 6232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn try { 6242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 6252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn K key = keyAt(i); 6262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn V mine = valueAt(i); 6272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object theirs = map.get(key); 6282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mine == null) { 6292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (theirs != null || !map.containsKey(key)) { 6302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 6312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else if (!mine.equals(theirs)) { 6332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 6342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } catch (NullPointerException ignored) { 6372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 6382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } catch (ClassCastException ignored) { 6392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 6402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return true; 6422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return false; 6442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 6462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 6472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 6482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 6492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 6502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public int hashCode() { 6512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final int[] hashes = mHashes; 6522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn final Object[] array = mArray; 6532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int result = 0; 6542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 6552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = array[v]; 6562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 6572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return result; 6592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 6612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 6622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 6632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 6642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 6652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this map contains itself as a key or a value, the string "(this Map)" 6662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will appear in its place. 6672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 6682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 6692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public String toString() { 6702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (isEmpty()) { 6712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return "{}"; 6722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 6742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 6752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('{'); 6762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 6772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (i > 0) { 6782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(", "); 6792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object key = keyAt(i); 6812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (key != this) { 6822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(key); 6832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 6842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 6852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('='); 6872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = valueAt(i); 6882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value != this) { 6892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(value); 6902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 6912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 6922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('}'); 6952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return buffer.toString(); 6962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 6972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn} 698