diff options
| -rw-r--r-- | core/java/android/util/ArrayMap.java | 123 | ||||
| -rw-r--r-- | core/java/android/util/ArraySet.java | 599 | ||||
| -rw-r--r-- | tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java | 206 |
3 files changed, 809 insertions, 119 deletions
diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java index bb0a6e1..4bd9b37 100644 --- a/core/java/android/util/ArrayMap.java +++ b/core/java/android/util/ArrayMap.java @@ -206,6 +206,7 @@ public final class ArrayMap<K, V> implements Map<K, V> { } mSize = 0; } + /** * Create a new ArrayMap with the mappings from the given ArrayMap. */ @@ -216,7 +217,6 @@ public final class ArrayMap<K, V> implements Map<K, V> { } } - /** * Make the array map empty. All storage is released. */ @@ -236,8 +236,8 @@ public final class ArrayMap<K, V> implements Map<K, V> { */ public void ensureCapacity(int minimumCapacity) { if (mHashes.length < minimumCapacity) { - int[] ohashes = mHashes; - Object[] oarray = mArray; + final int[] ohashes = mHashes; + final Object[] oarray = mArray; allocArrays(minimumCapacity); if (mSize > 0) { System.arraycopy(ohashes, 0, mHashes, 0, mSize); @@ -493,6 +493,63 @@ public final class ArrayMap<K, V> implements Map<K, V> { return mSize; } + /** + * {@inheritDoc} + * + * <p>This implementation returns false if the object is not a map, or + * if the maps have different sizes. Otherwise, for each key in this map, + * values of both maps are compared. If the values for any key are not + * equal, the method returns false, otherwise it returns true. + */ + @Override + public boolean equals(Object object) { + if (this == object) { + return true; + } + if (object instanceof Map) { + Map<?, ?> map = (Map<?, ?>) object; + if (size() != map.size()) { + return false; + } + + try { + for (int i=0; i<mSize; i++) { + K key = keyAt(i); + V mine = valueAt(i); + Object theirs = map.get(key); + if (mine == null) { + if (theirs != null || !map.containsKey(key)) { + return false; + } + } else if (!mine.equals(theirs)) { + return false; + } + } + } catch (NullPointerException ignored) { + return false; + } catch (ClassCastException ignored) { + return false; + } + return true; + } + return false; + } + + /** + * {@inheritDoc} + */ + @Override + public int hashCode() { + final int[] hashes = mHashes; + final Object[] array = mArray; + int result = 0; + for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { + Object value = array[v]; + result += hashes[i] ^ (value == null ? 0 : value.hashCode()); + } + return result; + } + // ------------------------------------------------------------------------ // Interop with traditional Java containers. Not as efficient as using // specialized collection APIs. @@ -632,64 +689,4 @@ public final class ArrayMap<K, V> implements Map<K, V> { public Collection<V> values() { return getCollection().getValues(); } - - /** - * {@inheritDoc} - * - * <p>This implementation returns false if the object is not a map, or - * if the maps have different sizes. Otherwise, for each key in this map, - * values of both maps are compared. If the values for any key are not - * equal, the method returns false, otherwise it returns true. - */ - @Override - public boolean equals(Object object) { - if (this == object) { - return true; - } - if (object instanceof Map) { - Map<?, ?> map = (Map<?, ?>) object; - if (size() != map.size()) { - return false; - } - - try { - for (int i=0; i<mSize; i++) { - K key = keyAt(i); - V mine = valueAt(i); - Object theirs = map.get(key); - if (mine == null) { - if (theirs != null || !map.containsKey(key)) { - return false; - } - } else if (!mine.equals(theirs)) { - return false; - } - } - } catch (NullPointerException ignored) { - return false; - } catch (ClassCastException ignored) { - return false; - } - return true; - } - return false; - } - - /** - * {@inheritDoc} - * - * <p>This implementation sums a hashcode using all keys and values. - */ - @Override - public int hashCode() { - int result = 0; - for (int i=0; i<mSize; i++) { - K key = keyAt(i); - V value = valueAt(i); - result += (key == null ? 0 : key.hashCode()) - ^ (value == null ? 0 : value.hashCode()); - } - return result; - } - } diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java new file mode 100644 index 0000000..a84c47c --- /dev/null +++ b/core/java/android/util/ArraySet.java @@ -0,0 +1,599 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package android.util; + +import java.lang.reflect.Array; +import java.util.Collection; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; + +/** + * ArraySet is a generic set data structure that is designed to be more memory efficient than a + * traditional {@link java.util.HashSet}. The design is very similar to + * {@link ArrayMap}, with all of the caveats described there. This implementation is + * separate from ArrayMap, however, so the Object array contains only one item for each + * entry in the set (instead of a pair for a mapping). + * + * <p>Note that this implementation is not intended to be appropriate for data structures + * that may contain large numbers of items. It is generally slower than a traditional + * HashSet, since lookups require a binary search and adds and removes require inserting + * and deleting entries in the array. For containers holding up to hundreds of items, + * the performance difference is not significant, less than 50%. For larger numbers of items + * this data structure should be avoided.</p> + * + * <p><b>Note:</b> unlike {@link java.util.HashSet}, this container does not support + * null values.</p> + * + * <p>Because this container is intended to better balance memory use, unlike most other + * standard Java containers it will shrink its array as items are removed from it. Currently + * you have no control over this shrinking -- if you set a capacity and then remove an + * item, it may reduce the capacity to better match the current size. In the future an + * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p> + * + * @hide + */ +public final class ArraySet<E> implements Collection<E>, Set<E> { + private static final boolean DEBUG = false; + private static final String TAG = "ArraySet"; + + /** + * The minimum amount by which the capacity of a ArraySet will increase. + * This is tuned to be relatively space-efficient. + */ + private static final int BASE_SIZE = 4; + + /** + * Maximum number of entries to have in array caches. + */ + private static final int CACHE_SIZE = 10; + + /** + * Caches of small array objects to avoid spamming garbage. The cache + * Object[] variable is a pointer to a linked list of array objects. + * The first entry in the array is a pointer to the next array in the + * list; the second entry is a pointer to the int[] hash code array for it. + */ + static Object[] mBaseCache; + static int mBaseCacheSize; + static Object[] mTwiceBaseCache; + static int mTwiceBaseCacheSize; + + int[] mHashes; + Object[] mArray; + int mSize; + MapCollections<E, E> mCollections; + + private int indexOf(Object key, int hash) { + final int N = mSize; + + // Important fast case: if nothing is in here, nothing to look for. + if (N == 0) { + return ~0; + } + + int index = SparseArray.binarySearch(mHashes, N, hash); + + // If the hash code wasn't found, then we have no entry for this key. + if (index < 0) { + return index; + } + + // If the key at the returned index matches, that's what we want. + if (mArray[index].equals(key)) { + return index; + } + + // Search for a matching key after the index. + int end; + for (end = index + 1; end < N && mHashes[end] == hash; end++) { + if (mArray[end].equals(key)) return end; + } + + // Search for a matching key before the index. + for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { + if (mArray[i].equals(key)) return i; + } + + // Key not found -- return negative value indicating where a + // new entry for this key should go. We use the end of the + // hash chain to reduce the number of array entries that will + // need to be copied when inserting. + return ~end; + } + + private void allocArrays(final int size) { + if (size == (BASE_SIZE*2)) { + synchronized (ArraySet.class) { + if (mTwiceBaseCache != null) { + final Object[] array = mTwiceBaseCache; + mArray = array; + mTwiceBaseCache = (Object[])array[0]; + mHashes = (int[])array[1]; + array[0] = array[1] = null; + mTwiceBaseCacheSize--; + if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes + + " now have " + mTwiceBaseCacheSize + " entries"); + return; + } + } + } else if (size == BASE_SIZE) { + synchronized (ArraySet.class) { + if (mBaseCache != null) { + final Object[] array = mBaseCache; + mArray = array; + mBaseCache = (Object[])array[0]; + mHashes = (int[])array[1]; + array[0] = array[1] = null; + mBaseCacheSize--; + if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes + + " now have " + mBaseCacheSize + " entries"); + return; + } + } + } + + mHashes = new int[size]; + mArray = new Object[size]; + } + + private static void freeArrays(final int[] hashes, final Object[] array, final int size) { + if (hashes.length == (BASE_SIZE*2)) { + synchronized (ArraySet.class) { + if (mTwiceBaseCacheSize < CACHE_SIZE) { + array[0] = mTwiceBaseCache; + array[1] = hashes; + for (int i=size-1; i>=2; i--) { + array[i] = null; + } + mTwiceBaseCache = array; + mTwiceBaseCacheSize++; + if (DEBUG) Log.d(TAG, "Storing 2x cache " + array + + " now have " + mTwiceBaseCacheSize + " entries"); + } + } + } else if (hashes.length == BASE_SIZE) { + synchronized (ArraySet.class) { + if (mBaseCacheSize < CACHE_SIZE) { + array[0] = mBaseCache; + array[1] = hashes; + for (int i=size-1; i>=2; i--) { + array[i] = null; + } + mBaseCache = array; + mBaseCacheSize++; + if (DEBUG) Log.d(TAG, "Storing 1x cache " + array + + " now have " + mBaseCacheSize + " entries"); + } + } + } + } + + /** + * Create a new empty ArraySet. The default capacity of an array map is 0, and + * will grow once items are added to it. + */ + public ArraySet() { + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + mSize = 0; + } + + /** + * Create a new ArraySet with a given initial capacity. + */ + public ArraySet(int capacity) { + if (capacity == 0) { + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + } else { + allocArrays(capacity); + } + mSize = 0; + } + + /** + * Create a new ArraySet with the mappings from the given ArraySet. + */ + public ArraySet(ArraySet set) { + this(); + if (set != null) { + addAll(set); + } + } + + + /** + * Make the array map empty. All storage is released. + */ + @Override + public void clear() { + if (mSize != 0) { + freeArrays(mHashes, mArray, mSize); + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + mSize = 0; + } + } + + /** + * Ensure the array map can hold at least <var>minimumCapacity</var> + * items. + */ + public void ensureCapacity(int minimumCapacity) { + if (mHashes.length < minimumCapacity) { + final int[] ohashes = mHashes; + final Object[] oarray = mArray; + allocArrays(minimumCapacity); + if (mSize > 0) { + System.arraycopy(ohashes, 0, mHashes, 0, mSize); + System.arraycopy(oarray, 0, mArray, 0, mSize); + } + freeArrays(ohashes, oarray, mSize); + } + } + + /** + * Check whether a value exists in the set. + * + * @param key The value to search for. + * @return Returns true if the value exists, else false. + */ + @Override + public boolean contains(Object key) { + return indexOf(key, key.hashCode()) >= 0; + } + + /** + * Return the value at the given index in the array. + * @param index The desired index, must be between 0 and {@link #size()}-1. + * @return Returns the value stored at the given index. + */ + public E valueAt(int index) { + return (E)mArray[index]; + } + + /** + * Return true if the array map contains no items. + */ + @Override + public boolean isEmpty() { + return mSize <= 0; + } + + /** + * Adds the specified object to this set. The set is not modified if it + * already contains the object. + * + * @param value the object to add. + * @return {@code true} if this set is modified, {@code false} otherwise. + * @throws ClassCastException + * when the class of the object is inappropriate for this set. + */ + @Override + public boolean add(E value) { + final int hash = value.hashCode(); + int index = indexOf(value, hash); + if (index >= 0) { + return false; + } + + index = ~index; + if (mSize >= mHashes.length) { + final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) + : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); + + if (DEBUG) Log.d(TAG, "add: grow from " + mHashes.length + " to " + n); + + final int[] ohashes = mHashes; + final Object[] oarray = mArray; + allocArrays(n); + + if (mHashes.length > 0) { + if (DEBUG) Log.d(TAG, "add: copy 0-" + mSize + " to 0"); + System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); + System.arraycopy(oarray, 0, mArray, 0, oarray.length); + } + + freeArrays(ohashes, oarray, mSize); + } + + if (index < mSize) { + if (DEBUG) Log.d(TAG, "add: move " + index + "-" + (mSize-index) + + " to " + (index+1)); + System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); + System.arraycopy(mArray, index, mArray, index + 1, mSize - index); + } + + mHashes[index] = hash; + mArray[index] = value; + mSize++; + return true; + } + + /** + * Perform a {@link #add(Object)} of all values in <var>array</var> + * @param array The array whose contents are to be retrieved. + */ + public void putAll(ArraySet<? extends E> array) { + final int N = array.mSize; + ensureCapacity(mSize + N); + if (mSize == 0) { + if (N > 0) { + System.arraycopy(array.mHashes, 0, mHashes, 0, N); + System.arraycopy(array.mArray, 0, mArray, 0, N); + mSize = N; + } + } else { + for (int i=0; i<N; i++) { + add(array.valueAt(i)); + } + } + } + + /** + * Removes the specified object from this set. + * + * @param object the object to remove. + * @return {@code true} if this set was modified, {@code false} otherwise. + */ + @Override + public boolean remove(Object object) { + int index = indexOf(object, object.hashCode()); + if (index >= 0) { + removeAt(index); + return true; + } + return false; + } + + /** + * Remove the key/value mapping at the given index. + * @param index The desired index, must be between 0 and {@link #size()}-1. + * @return Returns the value that was stored at this index. + */ + public E removeAt(int index) { + final E old = (E)mArray[index]; + if (mSize <= 1) { + // Now empty. + if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); + freeArrays(mHashes, mArray, mSize); + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + mSize = 0; + } else { + if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { + // Shrunk enough to reduce size of arrays. We don't allow it to + // shrink smaller than (BASE_SIZE*2) to avoid flapping between + // that and BASE_SIZE. + final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); + + if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); + + final int[] ohashes = mHashes; + final Object[] oarray = mArray; + allocArrays(n); + + mSize--; + if (index > 0) { + if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); + System.arraycopy(ohashes, 0, mHashes, 0, index); + System.arraycopy(oarray, 0, mArray, 0, index); + } + if (index < mSize) { + if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize + + " to " + index); + System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); + System.arraycopy(oarray, index + 1, mArray, index, mSize - index); + } + } else { + mSize--; + if (index < mSize) { + if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize + + " to " + index); + System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); + System.arraycopy(mArray, index + 1, mArray, index, mSize - index); + } + mArray[mSize] = null; + } + } + return old; + } + + /** + * Return the number of items in this array map. + */ + @Override + public int size() { + return mSize; + } + + @Override + public Object[] toArray() { + Object[] result = new Object[mSize]; + System.arraycopy(mArray, 0, result, 0, mSize); + return result; + } + + @Override + public <T> T[] toArray(T[] array) { + if (array.length < mSize) { + @SuppressWarnings("unchecked") T[] newArray + = (T[]) Array.newInstance(array.getClass().getComponentType(), mSize); + array = newArray; + } + System.arraycopy(mArray, 0, array, 0, mSize); + if (array.length > mSize) { + array[mSize] = null; + } + return array; + } + + /** + * {@inheritDoc} + * + * <p>This implementation returns false if the object is not a set, or + * if the sets have different sizes. Otherwise, for each value in this + * set, it checks to make sure the value also exists in the other set. + * If any value doesn't exist, the method returns false; otherwise, it + * returns true. + */ + @Override + public boolean equals(Object object) { + if (this == object) { + return true; + } + if (object instanceof Set) { + Set<?> set = (Set<?>) object; + if (size() != set.size()) { + return false; + } + + try { + for (int i=0; i<mSize; i++) { + E mine = valueAt(i); + if (!set.contains(mine)) { + return false; + } + } + } catch (NullPointerException ignored) { + return false; + } catch (ClassCastException ignored) { + return false; + } + return true; + } + return false; + } + + /** + * {@inheritDoc} + */ + @Override + public int hashCode() { + final int[] hashes = mHashes; + int result = 0; + for (int i = 0, s = mSize; i < s; i++) { + result += hashes[i]; + } + return result; + } + + // ------------------------------------------------------------------------ + // Interop with traditional Java containers. Not as efficient as using + // specialized collection APIs. + // ------------------------------------------------------------------------ + + private MapCollections<E, E> getCollection() { + if (mCollections == null) { + mCollections = new MapCollections<E, E>() { + @Override + protected int colGetSize() { + return mSize; + } + + @Override + protected Object colGetEntry(int index, int offset) { + return mArray[index]; + } + + @Override + protected int colIndexOfKey(Object key) { + return indexOf(key, key.hashCode()); + } + + @Override + protected int colIndexOfValue(Object value) { + return indexOf(value, value.hashCode()); + } + + @Override + protected Map<E, E> colGetMap() { + throw new UnsupportedOperationException("not a map"); + } + + @Override + protected void colPut(E key, E value) { + add(key); + } + + @Override + protected E colSetValue(int index, E value) { + throw new UnsupportedOperationException("not a map"); + } + + @Override + protected void colRemoveAt(int index) { + removeAt(index); + } + + @Override + protected void colClear() { + clear(); + } + }; + } + return mCollections; + } + + @Override + public Iterator<E> iterator() { + return getCollection().getKeySet().iterator(); + } + + @Override + public boolean containsAll(Collection<?> collection) { + Iterator<?> it = collection.iterator(); + while (it.hasNext()) { + if (!contains(it.next())) { + return false; + } + } + return true; + } + + @Override + public boolean addAll(Collection<? extends E> collection) { + ensureCapacity(mSize + collection.size()); + boolean added = false; + for (E value : collection) { + added |= add(value); + } + return added; + } + + @Override + public boolean removeAll(Collection<?> collection) { + boolean removed = false; + for (Object value : collection) { + removed |= remove(value); + } + return removed; + } + + @Override + public boolean retainAll(Collection<?> collection) { + boolean removed = false; + for (int i=mSize-1; i>=0; i--) { + if (!collection.contains(mArray[i])) { + removeAt(i); + removed = true; + } + } + return removed; + } +} diff --git a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java index 7d82cd3..9b54927 100644 --- a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java +++ b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java @@ -17,10 +17,12 @@ package com.google.android.test.activity; import android.util.ArrayMap; +import android.util.ArraySet; import android.util.Log; import java.util.Collection; import java.util.HashMap; +import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Set; @@ -137,41 +139,35 @@ public class ArrayMapTests { } } - int index = 0; - for (Object entry : array.entrySet()) { - Object key = ((Map.Entry)entry).getKey(); - Object value = ((Map.Entry)entry).getValue(); - Object realKey = array.keyAt(index); - Object realValue = array.valueAt(index); - if (!compare(key, realKey)) { - Log.e("test", "Bad entry iterator: expected key " + realKey + ", got " + key - + " at index " + index); - return false; - } - if (!compare(value, realValue)) { - Log.e("test", "Bad entry iterator: expected value " + realValue + ", got " + value - + " at index " + index); + return true; + } + + private static boolean compareSets(HashSet set, ArraySet array) { + if (set.size() != array.size()) { + Log.e("test", "Bad size: expected " + set.size() + ", got " + array.size()); + return false; + } + + for (Object entry : set) { + if (!array.contains(entry)) { + Log.e("test", "Bad value: expected " + entry + " not found in ArraySet"); return false; } - index++; } - index = 0; - for (Object key : array.keySet()) { - Object realKey = array.keyAt(index); - if (!compare(key, realKey)) { - Log.e("test", "Bad key iterator: expected key " + realKey + ", got " + key - + " at index " + index); + for (int i=0; i<array.size(); i++) { + Object entry = array.valueAt(i); + if (!set.contains(entry)) { + Log.e("test", "Bad value: unexpected " + entry + " in ArraySet"); return false; } - index++; } - index = 0; - for (Object value : array.values()) { - Object realValue = array.valueAt(index); - if (!compare(value, realValue)) { - Log.e("test", "Bad value iterator: expected value " + realValue + ", got " + value + int index = 0; + for (Object entry : array) { + Object realEntry = array.valueAt(index); + if (!compare(entry, realEntry)) { + Log.e("test", "Bad iterator: expected value " + realEntry + ", got " + entry + " at index " + index); return false; } @@ -190,14 +186,14 @@ public class ArrayMapTests { Object value = entry.getKey(); Object realValue = array.keyAt(index); if (!compare(realValue, value)) { - Log.e("test", "Bad hash array entry set: expected key " + realValue + Log.e("test", "Bad array map entry set: expected key " + realValue + ", got " + value + " at index " + index); return false; } value = entry.getValue(); realValue = array.valueAt(index); if (!compare(realValue, value)) { - Log.e("test", "Bad hash array entry set: expected value " + realValue + Log.e("test", "Bad array map entry set: expected value " + realValue + ", got " + value + " at index " + index); return false; } @@ -211,7 +207,7 @@ public class ArrayMapTests { Object value = keyIt.next(); Object realValue = array.keyAt(index); if (!compare(realValue, value)) { - Log.e("test", "Bad hash array key set: expected key " + realValue + Log.e("test", "Bad array map key set: expected key " + realValue + ", got " + value + " at index " + index); return false; } @@ -225,7 +221,7 @@ public class ArrayMapTests { Object value = valueIt.next(); Object realValue = array.valueAt(index); if (!compare(realValue, value)) { - Log.e("test", "Bad hash array value col: expected value " + realValue + Log.e("test", "Bad array map value col: expected value " + realValue + ", got " + value + " at index " + index); return false; } @@ -235,7 +231,7 @@ public class ArrayMapTests { return true; } - private static void dump(HashMap map, ArrayMap array) { + private static void dump(Map map, ArrayMap array) { Log.e("test", "HashMap of " + map.size() + " entries:"); Set<Map.Entry> mapSet = map.entrySet(); for (Map.Entry entry : mapSet) { @@ -247,6 +243,17 @@ public class ArrayMapTests { } } + private static void dump(Set set, ArraySet array) { + Log.e("test", "HashSet of " + set.size() + " entries:"); + for (Object entry : set) { + Log.e("test", " " + entry); + } + Log.e("test", "ArraySet of " + array.size() + " entries:"); + for (int i=0; i<array.size(); i++) { + Log.e("test", " " + array.valueAt(i)); + } + } + private static void dump(ArrayMap map1, ArrayMap map2) { Log.e("test", "ArrayMap of " + map1.size() + " entries:"); Set<Map.Entry> mapSet = map1.entrySet(); @@ -260,60 +267,93 @@ public class ArrayMapTests { } public static void run() { - HashMap<ControlledHash, Integer> mHashMap = new HashMap<ControlledHash, Integer>(); - ArrayMap<ControlledHash, Integer> mArrayMap = new ArrayMap<ControlledHash, Integer>(); + HashMap<ControlledHash, Integer> hashMap = new HashMap<ControlledHash, Integer>(); + ArrayMap<ControlledHash, Integer> arrayMap = new ArrayMap<ControlledHash, Integer>(); + HashSet<ControlledHash> hashSet = new HashSet<ControlledHash>(); + ArraySet<ControlledHash> arraySet = new ArraySet<ControlledHash>(); for (int i=0; i<OPS.length; i++) { - Integer oldMap; + Integer oldHash; Integer oldArray; + boolean hashChanged; + boolean arrayChanged; switch (OPS[i]) { case OP_ADD: Log.i("test", "Adding key: " + KEYS[i]); - oldMap = mHashMap.put(new ControlledHash(KEYS[i]), i); - oldArray = mArrayMap.put(new ControlledHash(KEYS[i]), i); + oldHash = hashMap.put(new ControlledHash(KEYS[i]), i); + oldArray = arrayMap.put(new ControlledHash(KEYS[i]), i); + hashChanged = hashSet.add(new ControlledHash(KEYS[i])); + arrayChanged = arraySet.add(new ControlledHash(KEYS[i])); break; case OP_REM: Log.i("test", "Removing key: " + KEYS[i]); - oldMap = mHashMap.remove(new ControlledHash(KEYS[i])); - oldArray = mArrayMap.remove(new ControlledHash(KEYS[i])); + oldHash = hashMap.remove(new ControlledHash(KEYS[i])); + oldArray = arrayMap.remove(new ControlledHash(KEYS[i])); + hashChanged = hashSet.remove(new ControlledHash(KEYS[i])); + arrayChanged = arraySet.remove(new ControlledHash(KEYS[i])); break; default: Log.e("test", "Bad operation " + OPS[i] + " @ " + i); return; } - if (!compare(oldMap, oldArray)) { - Log.e("test", "Bad result: expected " + oldMap + ", got " + oldArray); - dump(mHashMap, mArrayMap); + if (!compare(oldHash, oldArray)) { + Log.e("test", "Bad result: expected " + oldHash + ", got " + oldArray); + dump(hashMap, arrayMap); + return; + } + if (hashChanged != arrayChanged) { + Log.e("test", "Bad change: expected " + hashChanged + ", got " + arrayChanged); + dump(hashSet, arraySet); return; } - if (!validateArrayMap(mArrayMap)) { - dump(mHashMap, mArrayMap); + if (!validateArrayMap(arrayMap)) { + dump(hashMap, arrayMap); return; } - if (!compareMaps(mHashMap, mArrayMap)) { - dump(mHashMap, mArrayMap); + if (!compareMaps(hashMap, arrayMap)) { + dump(hashMap, arrayMap); + return; + } + if (!compareSets(hashSet, arraySet)) { + dump(hashSet, arraySet); return; } } - mArrayMap.put(new ControlledHash(50000), 100); + arrayMap.put(new ControlledHash(50000), 100); ControlledHash lookup = new ControlledHash(50000); - Iterator<ControlledHash> it = mArrayMap.keySet().iterator(); + Iterator<ControlledHash> it = arrayMap.keySet().iterator(); + while (it.hasNext()) { + if (it.next().equals(lookup)) { + it.remove(); + } + } + if (arrayMap.containsKey(lookup)) { + Log.e("test", "Bad map iterator: didn't remove test key"); + dump(hashMap, arrayMap); + } + + arraySet.add(new ControlledHash(50000)); + it = arraySet.iterator(); while (it.hasNext()) { if (it.next().equals(lookup)) { it.remove(); } } - if (mArrayMap.containsKey(lookup)) { - Log.e("test", "Bad iterator: didn't remove test key"); - dump(mHashMap, mArrayMap); + if (arraySet.contains(lookup)) { + Log.e("test", "Bad set iterator: didn't remove test key"); + dump(hashSet, arraySet); + } + + if (!equalsMapTest()) { + return; } - if (!equalsTest()) { + if (!equalsSetTest()) { return; } - // copy constructor test + // map copy constructor test ArrayMap newMap = new ArrayMap<Integer, String>(); for (int i = 0; i < 10; ++i) { newMap.put(i, String.valueOf(i)); @@ -322,15 +362,31 @@ public class ArrayMapTests { if (!compare(mapCopy, newMap)) { Log.e("test", "ArrayMap copy constructor failure: expected " + newMap + ", got " + mapCopy); - dump(mHashMap, mArrayMap); + dump(newMap, mapCopy); + return; + } + + // set copy constructor test + ArraySet newSet = new ArraySet<Integer>(); + for (int i = 0; i < 10; ++i) { + newSet.add(i); + } + ArraySet setCopy = new ArraySet(newSet); + if (!compare(setCopy, newSet)) { + Log.e("test", "ArraySet copy constructor failure: expected " + + newSet + ", got " + setCopy); + dump(newSet, setCopy); return; } Log.e("test", "Test successful; printing final map."); - dump(mHashMap, mArrayMap); + dump(hashMap, arrayMap); + + Log.e("test", "Test successful; printing final set."); + dump(hashSet, arraySet); } - private static boolean equalsTest() { + private static boolean equalsMapTest() { ArrayMap<Integer, String> map1 = new ArrayMap<Integer, String>(); ArrayMap<Integer, String> map2 = new ArrayMap<Integer, String>(); HashMap<Integer, String> map3 = new HashMap<Integer, String>(); @@ -368,4 +424,42 @@ public class ArrayMapTests { return true; } + + private static boolean equalsSetTest() { + ArraySet<Integer> set1 = new ArraySet<Integer>(); + ArraySet<Integer> set2 = new ArraySet<Integer>(); + HashSet<Integer> set3 = new HashSet<Integer>(); + if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { + Log.e("test", "ArraySet equals failure for empty sets " + set1 + ", " + + set2 + ", " + set3); + return false; + } + + for (int i = 0; i < 10; ++i) { + set1.add(i); + set2.add(i); + set3.add(i); + } + if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { + Log.e("test", "ArraySet equals failure for populated sets " + set1 + ", " + + set2 + ", " + set3); + return false; + } + + set1.remove(0); + if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { + Log.e("test", "ArraSet equals failure for set size " + set1 + ", " + + set2 + ", " + set3); + return false; + } + + set1.add(-1); + if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { + Log.e("test", "ArraySet equals failure for set contents " + set1 + ", " + + set2 + ", " + set3); + return false; + } + + return true; + } } |