From f4130cf35fa128e36f96e55955d4f5db86197e4a Mon Sep 17 00:00:00 2001
From: Chet Haase <chet@google.com>
Date: Thu, 6 Jun 2013 16:34:33 -0700
Subject: [PATCH] Additional functionality and performance for ArrayMap

Added equals() and hashCode() to ArrayMap to allow equals() tests
of maps with the same key/value pairs to return true.

Changed putAll() to handle the case of an empty map faster, just copying
the arrays instead of adding elements one by one.

Added to ArrayMapTests to test new equals() and copy constructor
functionality.

Issue #9299310 Optimize ArrayMap copy constructor

Change-Id: I1186a0eddd1fd53a0f380c2f3972fc1942cdf879
---
 core/java/android/util/ArrayMap.java               | 76 ++++++++++++++++++++--
 .../android/test/activity/ArrayMapTests.java       | 68 +++++++++++++++++++
 2 files changed, 140 insertions(+), 4 deletions(-)

diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
index edda77938578..bb0a6e1a456b 100644
--- a/core/java/android/util/ArrayMap.java
+++ b/core/java/android/util/ArrayMap.java
@@ -400,8 +400,16 @@ public final class ArrayMap<K, V> implements Map<K, V> {
     public void putAll(ArrayMap<? extends K, ? extends V> array) {
         final int N = array.mSize;
         ensureCapacity(mSize + N);
-        for (int i=0; i<N; i++) {
-            put(array.keyAt(i), array.valueAt(i));
+        if (mSize == 0) {
+            if (N > 0) {
+                System.arraycopy(array.mHashes, 0, mHashes, 0, N);
+                System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
+                mSize = N;
+            }
+        } else {
+            for (int i=0; i<N; i++) {
+                put(array.keyAt(i), array.valueAt(i));
+            }
         }
     }
 
@@ -605,7 +613,7 @@ public final class ArrayMap<K, V> implements Map<K, V> {
      * Return a {@link java.util.Set} for iterating over and interacting with all keys
      * in the array map.
      *
-     * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it
+     * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it
      * requires generating a number of temporary objects.</p>
      */
     @Override
@@ -617,11 +625,71 @@ public final class ArrayMap<K, V> implements Map<K, V> {
      * Return a {@link java.util.Collection} for iterating over and interacting with all values
      * in the array map.
      *
-     * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it
+     * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it
      * requires generating a number of temporary objects.</p>
      */
     @Override
     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/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
index d9e1a83b0bde..7d82cd35b91a 100644
--- a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
+++ b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
@@ -247,6 +247,18 @@ public class ArrayMapTests {
         }
     }
 
+    private static void dump(ArrayMap map1, ArrayMap map2) {
+        Log.e("test", "ArrayMap of " + map1.size() + " entries:");
+        Set<Map.Entry> mapSet = map1.entrySet();
+        for (int i=0; i<map2.size(); i++) {
+            Log.e("test", "    " + map1.keyAt(i) + " -> " + map1.valueAt(i));
+        }
+        Log.e("test", "ArrayMap of " + map2.size() + " entries:");
+        for (int i=0; i<map2.size(); i++) {
+            Log.e("test", "    " + map2.keyAt(i) + " -> " + map2.valueAt(i));
+        }
+    }
+
     public static void run() {
         HashMap<ControlledHash, Integer> mHashMap = new HashMap<ControlledHash, Integer>();
         ArrayMap<ControlledHash, Integer> mArrayMap = new ArrayMap<ControlledHash, Integer>();
@@ -297,7 +309,63 @@ public class ArrayMapTests {
             dump(mHashMap, mArrayMap);
         }
 
+        if (!equalsTest()) {
+            return;
+        }
+
+        // copy constructor test
+        ArrayMap newMap = new ArrayMap<Integer, String>();
+        for (int i = 0; i < 10; ++i) {
+            newMap.put(i, String.valueOf(i));
+        }
+        ArrayMap mapCopy = new ArrayMap(newMap);
+        if (!compare(mapCopy, newMap)) {
+            Log.e("test", "ArrayMap copy constructor failure: expected " +
+                    newMap + ", got " + mapCopy);
+            dump(mHashMap, mArrayMap);
+            return;
+        }
+
         Log.e("test", "Test successful; printing final map.");
         dump(mHashMap, mArrayMap);
     }
+
+    private static boolean equalsTest() {
+        ArrayMap<Integer, String> map1 = new ArrayMap<Integer, String>();
+        ArrayMap<Integer, String> map2 = new ArrayMap<Integer, String>();
+        HashMap<Integer, String> map3 = new HashMap<Integer, String>();
+        if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) {
+            Log.e("test", "ArrayMap equals failure for empty maps " + map1 + ", " +
+                    map2 + ", " + map3);
+            return false;
+        }
+
+        for (int i = 0; i < 10; ++i) {
+            String value = String.valueOf(i);
+            map1.put(i, value);
+            map2.put(i, value);
+            map3.put(i, value);
+        }
+        if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) {
+            Log.e("test", "ArrayMap equals failure for populated maps " + map1 + ", " +
+                    map2 + ", " + map3);
+            return false;
+        }
+
+        map1.remove(0);
+        if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) {
+            Log.e("test", "ArrayMap equals failure for map size " + map1 + ", " +
+                    map2 + ", " + map3);
+            return false;
+        }
+
+        map1.put(0, "-1");
+        if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) {
+            Log.e("test", "ArrayMap equals failure for map contents " + map1 + ", " +
+                    map2 + ", " + map3);
+            return false;
+        }
+
+        return true;
+    }
 }
-- 
2.11.0