121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn/* 221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Copyright (C) 2013 The Android Open Source Project 321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * you may not use this file except in compliance with the License. 621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * You may obtain a copy of the License at 721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 1021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Unless required by applicable law or agreed to in writing, software 1121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 1221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * See the License for the specific language governing permissions and 1421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * limitations under the License. 1521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 1621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 1721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornpackage android.util; 1821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 19776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport libcore.util.EmptyArray; 20776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 2121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornimport java.lang.reflect.Array; 2221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornimport java.util.Collection; 2321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornimport java.util.Iterator; 2421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornimport java.util.Map; 2521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornimport java.util.Set; 2621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 2721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn/** 2821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * ArraySet is a generic set data structure that is designed to be more memory efficient than a 2921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * traditional {@link java.util.HashSet}. The design is very similar to 3021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@link ArrayMap}, with all of the caveats described there. This implementation is 3121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * separate from ArrayMap, however, so the Object array contains only one item for each 3221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * entry in the set (instead of a pair for a mapping). 3321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 3421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * <p>Note that this implementation is not intended to be appropriate for data structures 3521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 3621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * HashSet, since lookups require a binary search and adds and removes require inserting 3721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 38b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 3921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 4021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * <p>Because this container is intended to better balance memory use, unlike most other 4121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * standard Java containers it will shrink its array as items are removed from it. Currently 4221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * you have no control over this shrinking -- if you set a capacity and then remove an 4321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * item, it may reduce the capacity to better match the current size. In the future an 44b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 4521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 4621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackbornpublic final class ArraySet<E> implements Collection<E>, Set<E> { 4721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private static final boolean DEBUG = false; 4821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private static final String TAG = "ArraySet"; 4921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 5021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 5121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * The minimum amount by which the capacity of a ArraySet will increase. 5221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * This is tuned to be relatively space-efficient. 5321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 5421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private static final int BASE_SIZE = 4; 5521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 5621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 5721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Maximum number of entries to have in array caches. 5821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 5921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private static final int CACHE_SIZE = 10; 6021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 6121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 6221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Caches of small array objects to avoid spamming garbage. The cache 6321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Object[] variable is a pointer to a linked list of array objects. 6421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * The first entry in the array is a pointer to the next array in the 6521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * list; the second entry is a pointer to the int[] hash code array for it. 6621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 6721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn static Object[] mBaseCache; 6821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn static int mBaseCacheSize; 6921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn static Object[] mTwiceBaseCache; 7021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn static int mTwiceBaseCacheSize; 7121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 7221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int[] mHashes; 7321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object[] mArray; 7421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int mSize; 7521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn MapCollections<E, E> mCollections; 7621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 7721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private int indexOf(Object key, int hash) { 7821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int N = mSize; 7921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 8021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 8121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (N == 0) { 8221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return ~0; 8321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 8421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 853e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, hash); 8621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 8721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 8821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index < 0) { 8921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return index; 9021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 9121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 9221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // If the key at the returned index matches, that's what we want. 9362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[index])) { 9421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return index; 9521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 9621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 9721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Search for a matching key after the index. 9821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int end; 9921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (end = index + 1; end < N && mHashes[end] == hash; end++) { 10062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[end])) return end; 10121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 10221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 10321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Search for a matching key before the index. 10421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 10562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (key.equals(mArray[i])) return i; 10662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 10762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 10862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Key not found -- return negative value indicating where a 10962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // new entry for this key should go. We use the end of the 11062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // hash chain to reduce the number of array entries that will 11162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // need to be copied when inserting. 11262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return ~end; 11362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 11462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 11562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn private int indexOfNull() { 11662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int N = mSize; 11762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 11862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Important fast case: if nothing is in here, nothing to look for. 11962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (N == 0) { 12062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return ~0; 12162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 12262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 12362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index = ContainerHelpers.binarySearch(mHashes, N, 0); 12462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 12562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // If the hash code wasn't found, then we have no entry for this key. 12662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (index < 0) { 12762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return index; 12862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 12962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // If the key at the returned index matches, that's what we want. 13162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[index]) { 13262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return index; 13362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 13462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 13562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Search for a matching key after the index. 13662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int end; 13762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn for (end = index + 1; end < N && mHashes[end] == 0; end++) { 13862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[end]) return end; 13962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 14062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 14162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Search for a matching key before the index. 14262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 14362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (null == mArray[i]) return i; 14421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 14521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 14621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Key not found -- return negative value indicating where a 14721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // new entry for this key should go. We use the end of the 14821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // hash chain to reduce the number of array entries that will 14921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // need to be copied when inserting. 15021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return ~end; 15121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 15221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 15321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private void allocArrays(final int size) { 15421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (size == (BASE_SIZE*2)) { 15521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn synchronized (ArraySet.class) { 15621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mTwiceBaseCache != null) { 15721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] array = mTwiceBaseCache; 15821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mArray = array; 15921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mTwiceBaseCache = (Object[])array[0]; 16021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mHashes = (int[])array[1]; 16121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[0] = array[1] = null; 16221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mTwiceBaseCacheSize--; 16321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 16421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 16521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return; 16621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 16721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 16821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else if (size == BASE_SIZE) { 16921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn synchronized (ArraySet.class) { 17021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mBaseCache != null) { 17121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] array = mBaseCache; 17221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mArray = array; 17321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mBaseCache = (Object[])array[0]; 17421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mHashes = (int[])array[1]; 17521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[0] = array[1] = null; 17621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mBaseCacheSize--; 17721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 17821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " now have " + mBaseCacheSize + " entries"); 17921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return; 18021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 18121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 18221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 18321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 18421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mHashes = new int[size]; 18521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mArray = new Object[size]; 18621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 18721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 18821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 18921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (hashes.length == (BASE_SIZE*2)) { 19021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn synchronized (ArraySet.class) { 19121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mTwiceBaseCacheSize < CACHE_SIZE) { 19221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[0] = mTwiceBaseCache; 19321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[1] = hashes; 19421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=size-1; i>=2; i--) { 19521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[i] = null; 19621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 19721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mTwiceBaseCache = array; 19821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mTwiceBaseCacheSize++; 19921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 20021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " now have " + mTwiceBaseCacheSize + " entries"); 20121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 20221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 20321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else if (hashes.length == BASE_SIZE) { 20421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn synchronized (ArraySet.class) { 20521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mBaseCacheSize < CACHE_SIZE) { 20621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[0] = mBaseCache; 20721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[1] = hashes; 20821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=size-1; i>=2; i--) { 20921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[i] = null; 21021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 21121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mBaseCache = array; 21221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mBaseCacheSize++; 21321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 21421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " now have " + mBaseCacheSize + " entries"); 21521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 21621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 21721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 21821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 21921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 22021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 22121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Create a new empty ArraySet. The default capacity of an array map is 0, and 22221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * will grow once items are added to it. 22321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 22421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public ArraySet() { 225776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 226776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 22721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize = 0; 22821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 22921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 23021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 23121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Create a new ArraySet with a given initial capacity. 23221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 23321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public ArraySet(int capacity) { 23421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (capacity == 0) { 235776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 236776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 23721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else { 23821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn allocArrays(capacity); 23921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 24021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize = 0; 24121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 24221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 24321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 24421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Create a new ArraySet with the mappings from the given ArraySet. 24521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 2469f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey public ArraySet(ArraySet<E> set) { 24721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn this(); 24821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (set != null) { 24921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn addAll(set); 25021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 25121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 25221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 2539f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey /** {@hide} */ 2549f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey public ArraySet(Collection<E> set) { 2559f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey this(); 2569f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey if (set != null) { 2579f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey addAll(set); 2589f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey } 2599f837a99d48c5bb8ad7fbc133943e5bf622ce065Jeff Sharkey } 26021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 26121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 26221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Make the array map empty. All storage is released. 26321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 26421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 26521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public void clear() { 26621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mSize != 0) { 26721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn freeArrays(mHashes, mArray, mSize); 268776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 269776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 27021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize = 0; 27121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 27221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 27321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 27421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 27521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Ensure the array map can hold at least <var>minimumCapacity</var> 27621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * items. 27721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 27821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public void ensureCapacity(int minimumCapacity) { 27921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mHashes.length < minimumCapacity) { 28021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] ohashes = mHashes; 28121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] oarray = mArray; 28221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn allocArrays(minimumCapacity); 28321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mSize > 0) { 28421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, mSize); 28521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(oarray, 0, mArray, 0, mSize); 28621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 28721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn freeArrays(ohashes, oarray, mSize); 28821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 28921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 29021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 29121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 29221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Check whether a value exists in the set. 29321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 29421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @param key The value to search for. 29521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @return Returns true if the value exists, else false. 29621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 29721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 29821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean contains(Object key) { 2994e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return indexOf(key) >= 0; 3004e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski } 3014e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski 3024e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski /** 3034e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * Returns the index of a value in the set. 3044e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * 3054e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * @param key The value to search for. 3064e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski * @return Returns the index of the value if it exists, else a negative integer. 3074e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski */ 3084e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski public int indexOf(Object key) { 3094e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 31021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 31121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 31221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 31321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Return the value at the given index in the array. 31421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 31521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @return Returns the value stored at the given index. 31621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 31721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public E valueAt(int index) { 31821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return (E)mArray[index]; 31921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 32021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 32121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 32221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Return true if the array map contains no items. 32321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 32421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 32521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean isEmpty() { 32621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return mSize <= 0; 32721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 32821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 32921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 33021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Adds the specified object to this set. The set is not modified if it 33121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * already contains the object. 33221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 33321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @param value the object to add. 33421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @return {@code true} if this set is modified, {@code false} otherwise. 33521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @throws ClassCastException 33621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * when the class of the object is inappropriate for this set. 33721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 33821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 33921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean add(E value) { 34062d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final int hash; 34162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn int index; 34262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn if (value == null) { 34362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = 0; 34462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOfNull(); 34562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } else { 34662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn hash = value.hashCode(); 34762d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn index = indexOf(value, hash); 34862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn } 34921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index >= 0) { 35021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 35121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 35221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 35321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn index = ~index; 35421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mSize >= mHashes.length) { 35521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 35621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 35721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 35821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "add: grow from " + mHashes.length + " to " + n); 35921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 36021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] ohashes = mHashes; 36121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] oarray = mArray; 36221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn allocArrays(n); 36321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 36421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mHashes.length > 0) { 36521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "add: copy 0-" + mSize + " to 0"); 36621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 36721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(oarray, 0, mArray, 0, oarray.length); 36821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 36921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 37021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn freeArrays(ohashes, oarray, mSize); 37121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 37221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 37321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index < mSize) { 37421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "add: move " + index + "-" + (mSize-index) 37521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " to " + (index+1)); 37621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 37721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(mArray, index, mArray, index + 1, mSize - index); 37821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 37921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 38021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mHashes[index] = hash; 38121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mArray[index] = value; 38221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize++; 38321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 38421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 38521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 38621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 38721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Perform a {@link #add(Object)} of all values in <var>array</var> 38821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @param array The array whose contents are to be retrieved. 38921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 390497175beffe26336c092ee11a67b90f79dcdaca7Dianne Hackborn public void addAll(ArraySet<? extends E> array) { 39121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int N = array.mSize; 39221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn ensureCapacity(mSize + N); 39321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mSize == 0) { 39421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (N > 0) { 39521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(array.mHashes, 0, mHashes, 0, N); 39621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(array.mArray, 0, mArray, 0, N); 39721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize = N; 39821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 39921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else { 40021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=0; i<N; i++) { 40121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn add(array.valueAt(i)); 40221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 40321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 40421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 40521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 40621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 40721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Removes the specified object from this set. 40821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 40921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @param object the object to remove. 41021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @return {@code true} if this set was modified, {@code false} otherwise. 41121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 41221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 41321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean remove(Object object) { 4144e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski final int index = indexOf(object); 41521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index >= 0) { 41621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn removeAt(index); 41721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 41821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 41921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 42021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 42121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 42221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 42321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Remove the key/value mapping at the given index. 42421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @param index The desired index, must be between 0 and {@link #size()}-1. 42521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * @return Returns the value that was stored at this index. 42621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 42721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public E removeAt(int index) { 42862d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn final Object old = mArray[index]; 42921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mSize <= 1) { 43021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Now empty. 43121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 43221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn freeArrays(mHashes, mArray, mSize); 433776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mHashes = EmptyArray.INT; 434776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mArray = EmptyArray.OBJECT; 43521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize = 0; 43621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else { 43721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 43821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Shrunk enough to reduce size of arrays. We don't allow it to 43921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // shrink smaller than (BASE_SIZE*2) to avoid flapping between 44021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // that and BASE_SIZE. 44121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 44221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 44321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 44421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 44521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] ohashes = mHashes; 44621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final Object[] oarray = mArray; 44721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn allocArrays(n); 44821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 44921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize--; 45021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index > 0) { 45121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 45221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(ohashes, 0, mHashes, 0, index); 45321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(oarray, 0, mArray, 0, index); 45421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 45521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index < mSize) { 45621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 45721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " to " + index); 45821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 45921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(oarray, index + 1, mArray, index, mSize - index); 46021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 46121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } else { 46221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mSize--; 46321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (index < mSize) { 46421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 46521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn + " to " + index); 46621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 46721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(mArray, index + 1, mArray, index, mSize - index); 46821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 46921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mArray[mSize] = null; 47021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 47121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 47262d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return (E)old; 47321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 47421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 47521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 476f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe * Perform a {@link #remove(Object)} of all values in <var>array</var> 477f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe * @param array The array whose contents are to be removed. 478f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe */ 479f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe public boolean removeAll(ArraySet<? extends E> array) { 480f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe // TODO: If array is sufficiently large, a marking approach might be beneficial. In a first 481f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe // pass, use the property that the sets are sorted by hash to make this linear passes 482f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe // (except for hash collisions, which means worst case still n*m), then do one 483f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe // collection pass into a new array. This avoids binary searches and excessive memcpy. 484f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe final int N = array.mSize; 485f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe 486f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe // Note: ArraySet does not make thread-safety guarantees. So instead of OR-ing together all 487f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe // the single results, compare size before and after. 488f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe final int originalSize = mSize; 489f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe for (int i = 0; i < N; i++) { 490f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe remove(array.valueAt(i)); 491f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe } 492f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe return originalSize != mSize; 493f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe } 494f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe 495f9345e93db82adf8eaa2afc731933462d7876b13Andreas Gampe /** 49621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * Return the number of items in this array map. 49721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 49821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 49921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public int size() { 50021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return mSize; 50121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 50221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 50321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 50421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public Object[] toArray() { 50521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Object[] result = new Object[mSize]; 50621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(mArray, 0, result, 0, mSize); 50721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return result; 50821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 50921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 51021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 51121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public <T> T[] toArray(T[] array) { 51221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (array.length < mSize) { 51321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @SuppressWarnings("unchecked") T[] newArray 51421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn = (T[]) Array.newInstance(array.getClass().getComponentType(), mSize); 51521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array = newArray; 51621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 51721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn System.arraycopy(mArray, 0, array, 0, mSize); 51821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (array.length > mSize) { 51921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn array[mSize] = null; 52021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 52121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return array; 52221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 52321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 52421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 52521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 52621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * 52721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * <p>This implementation returns false if the object is not a set, or 52821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * if the sets have different sizes. Otherwise, for each value in this 52921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * set, it checks to make sure the value also exists in the other set. 53021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * If any value doesn't exist, the method returns false; otherwise, it 53121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * returns true. 53221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 53321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 53421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean equals(Object object) { 53521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (this == object) { 53621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 53721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 53821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (object instanceof Set) { 53921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Set<?> set = (Set<?>) object; 54021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (size() != set.size()) { 54121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 54221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 54321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 54421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn try { 54521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=0; i<mSize; i++) { 54621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn E mine = valueAt(i); 54721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (!set.contains(mine)) { 54821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 54921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 55021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 55121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (NullPointerException ignored) { 55221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 55321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } catch (ClassCastException ignored) { 55421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 55521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 55621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 55721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 55821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 55921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 56021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 56121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn /** 56221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn * {@inheritDoc} 56321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn */ 56421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 56521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public int hashCode() { 56621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn final int[] hashes = mHashes; 56721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn int result = 0; 56821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i = 0, s = mSize; i < s; i++) { 56921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn result += hashes[i]; 57021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 57121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return result; 57221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 57321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 574a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn /** 575a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * {@inheritDoc} 576a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * 577a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * <p>This implementation composes a string by iterating over its values. If 578a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * this set contains itself as a value, the string "(this Set)" 579a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn * will appear in its place. 580a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn */ 581a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn @Override 582a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn public String toString() { 583a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (isEmpty()) { 584a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return "{}"; 585a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 586a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 587a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 14); 588a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('{'); 589a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn for (int i=0; i<mSize; i++) { 590a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (i > 0) { 591a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(", "); 592a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 593a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn Object value = valueAt(i); 594a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn if (value != this) { 595a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append(value); 596a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } else { 597a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append("(this Set)"); 598a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 599a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 600a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn buffer.append('}'); 601a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn return buffer.toString(); 602a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn } 603a17c0f5e164729210210ad3f75aea72ed34ca330Dianne Hackborn 60421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // ------------------------------------------------------------------------ 60521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Interop with traditional Java containers. Not as efficient as using 60621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // specialized collection APIs. 60721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // ------------------------------------------------------------------------ 60821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 60921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn private MapCollections<E, E> getCollection() { 61021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (mCollections == null) { 61121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn mCollections = new MapCollections<E, E>() { 61221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 61321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected int colGetSize() { 61421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return mSize; 61521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 61621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 61721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 61821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected Object colGetEntry(int index, int offset) { 61921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return mArray[index]; 62021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 62121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 62221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 62321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected int colIndexOfKey(Object key) { 6244e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return indexOf(key); 62521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 62621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 62721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 62821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected int colIndexOfValue(Object value) { 6294e9c07c0de199169374bded403805c92f1c1c6c1Adam Lesinski return indexOf(value); 63021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 63121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 63221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 63321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected Map<E, E> colGetMap() { 63421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn throw new UnsupportedOperationException("not a map"); 63521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 63621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 63721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 63821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected void colPut(E key, E value) { 63921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn add(key); 64021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 64121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 64221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 64321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected E colSetValue(int index, E value) { 64421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn throw new UnsupportedOperationException("not a map"); 64521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 64621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 64721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 64821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected void colRemoveAt(int index) { 64921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn removeAt(index); 65021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 65121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 65221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 65321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn protected void colClear() { 65421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn clear(); 65521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 65621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn }; 65721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 65821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return mCollections; 65921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 66021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 661f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn /** 662f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * Return an {@link java.util.Iterator} over all values in the set. 663f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * 664f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 665f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * requires generating a number of temporary objects and allocates additional state 666f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * information associated with the container that will remain for the life of the container.</p> 667f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn */ 66821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 66921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public Iterator<E> iterator() { 67021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return getCollection().getKeySet().iterator(); 67121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 67221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 673f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn /** 674f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * Determine if the array set contains all of the values in the given collection. 675f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @param collection The collection whose contents are to be checked against. 676f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @return Returns true if this array set contains a value for every entry 677f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * in <var>collection</var>, else returns false. 678f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn */ 67921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 68021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean containsAll(Collection<?> collection) { 68121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Iterator<?> it = collection.iterator(); 68221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn while (it.hasNext()) { 68321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (!contains(it.next())) { 68421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return false; 68521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return true; 68821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 68921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 690f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn /** 691f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * Perform an {@link #add(Object)} of all values in <var>collection</var> 692f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @param collection The collection whose contents are to be retrieved. 693f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn */ 69421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 69521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean addAll(Collection<? extends E> collection) { 69621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn ensureCapacity(mSize + collection.size()); 69721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn boolean added = false; 69821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (E value : collection) { 69921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn added |= add(value); 70021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 70121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return added; 70221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 70321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 704f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn /** 705f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * Remove all values in the array set that exist in the given collection. 706f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @param collection The collection whose contents are to be used to remove values. 707f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @return Returns true if any values were removed from the array set, else false. 708f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn */ 70921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 71021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean removeAll(Collection<?> collection) { 71121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn boolean removed = false; 71221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (Object value : collection) { 71321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn removed |= remove(value); 71421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 71521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return removed; 71621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 71721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 718f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn /** 719f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * Remove all values in the array set that do <b>not</b> exist in the given collection. 720f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @param collection The collection whose contents are to be used to determine which 721f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * values to keep. 722f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn * @return Returns true if any values were removed from the array set, else false. 723f16747db093f6d6371d617efc8d90698d2d5b389Dianne Hackborn */ 72421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn @Override 72521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn public boolean retainAll(Collection<?> collection) { 72621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn boolean removed = false; 72721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn for (int i=mSize-1; i>=0; i--) { 72821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (!collection.contains(mArray[i])) { 72921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn removeAt(i); 73021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn removed = true; 73121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 73221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 73321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn return removed; 73421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn } 73521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn} 736