ArrayMapTests.java revision f4130cf35fa128e36f96e55955d4f5db86197e4a
1/* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.android.test.activity; 18 19import android.util.ArrayMap; 20import android.util.Log; 21 22import java.util.Collection; 23import java.util.HashMap; 24import java.util.Iterator; 25import java.util.Map; 26import java.util.Set; 27 28public class ArrayMapTests { 29 static final int OP_ADD = 1; 30 static final int OP_REM = 2; 31 32 static int[] OPS = new int[] { 33 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 34 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 35 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 36 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 37 38 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 39 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 40 41 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 42 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 43 44 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 45 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 46 47 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 48 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 49 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 50 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 51 }; 52 53 static int[] KEYS = new int[] { 54 // General adding and removing. 55 100, 1900, 600, 200, 1200, 1500, 1800, 100, 1900, 56 2100, 300, 800, 600, 1100, 1300, 2000, 1000, 1400, 57 600, 100, 1900, 600, 300, 2100, 200, 800, 800, 58 1800, 1500, 1300, 1100, 2000, 1400, 1000, 1200, 1900, 59 60 // Shrink when removing item from end. 61 100, 200, 300, 400, 500, 600, 700, 800, 900, 62 900, 800, 700, 600, 500, 400, 300, 200, 100, 63 64 // Shrink when removing item from middle. 65 100, 200, 300, 400, 500, 600, 700, 800, 900, 66 900, 800, 700, 600, 500, 400, 200, 300, 100, 67 68 // Shrink when removing item from front. 69 100, 200, 300, 400, 500, 600, 700, 800, 900, 70 900, 800, 700, 600, 500, 400, 100, 200, 300, 71 72 // Test hash collisions. 73 105, 106, 108, 104, 102, 102, 107, 5, 205, 74 4, 202, 203, 3, 5, 101, 109, 200, 201, 75 106, 108, 104, 102, 103, 105, 107, 101, 109, 76 4, 5, 3, 5, 200, 203, 202, 201, 205, 77 }; 78 79 static class ControlledHash { 80 final int mValue; 81 82 ControlledHash(int value) { 83 mValue = value; 84 } 85 86 @Override 87 public final boolean equals(Object o) { 88 return mValue == ((ControlledHash)o).mValue; 89 } 90 91 @Override 92 public final int hashCode() { 93 return mValue/100; 94 } 95 96 @Override 97 public final String toString() { 98 return Integer.toString(mValue); 99 } 100 } 101 102 private static boolean compare(Object v1, Object v2) { 103 if (v1 == null) { 104 return v2 == null; 105 } 106 if (v2 == null) { 107 return false; 108 } 109 return v1.equals(v2); 110 } 111 112 private static boolean compareMaps(HashMap map, ArrayMap array) { 113 if (map.size() != array.size()) { 114 Log.e("test", "Bad size: expected " + map.size() + ", got " + array.size()); 115 return false; 116 } 117 118 Set<Map.Entry> mapSet = map.entrySet(); 119 for (Map.Entry entry : mapSet) { 120 Object expValue = entry.getValue(); 121 Object gotValue = array.get(entry.getKey()); 122 if (!compare(expValue, gotValue)) { 123 Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue 124 + " at key " + entry.getKey()); 125 return false; 126 } 127 } 128 129 for (int i=0; i<array.size(); i++) { 130 Object gotValue = array.valueAt(i); 131 Object key = array.keyAt(i); 132 Object expValue = map.get(key); 133 if (!compare(expValue, gotValue)) { 134 Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue 135 + " at key " + key); 136 return false; 137 } 138 } 139 140 int index = 0; 141 for (Object entry : array.entrySet()) { 142 Object key = ((Map.Entry)entry).getKey(); 143 Object value = ((Map.Entry)entry).getValue(); 144 Object realKey = array.keyAt(index); 145 Object realValue = array.valueAt(index); 146 if (!compare(key, realKey)) { 147 Log.e("test", "Bad entry iterator: expected key " + realKey + ", got " + key 148 + " at index " + index); 149 return false; 150 } 151 if (!compare(value, realValue)) { 152 Log.e("test", "Bad entry iterator: expected value " + realValue + ", got " + value 153 + " at index " + index); 154 return false; 155 } 156 index++; 157 } 158 159 index = 0; 160 for (Object key : array.keySet()) { 161 Object realKey = array.keyAt(index); 162 if (!compare(key, realKey)) { 163 Log.e("test", "Bad key iterator: expected key " + realKey + ", got " + key 164 + " at index " + index); 165 return false; 166 } 167 index++; 168 } 169 170 index = 0; 171 for (Object value : array.values()) { 172 Object realValue = array.valueAt(index); 173 if (!compare(value, realValue)) { 174 Log.e("test", "Bad value iterator: expected value " + realValue + ", got " + value 175 + " at index " + index); 176 return false; 177 } 178 index++; 179 } 180 181 return true; 182 } 183 184 private static boolean validateArrayMap(ArrayMap array) { 185 Set<Map.Entry> entrySet = array.entrySet(); 186 int index=0; 187 Iterator<Map.Entry> entryIt = entrySet.iterator(); 188 while (entryIt.hasNext()) { 189 Map.Entry entry = entryIt.next(); 190 Object value = entry.getKey(); 191 Object realValue = array.keyAt(index); 192 if (!compare(realValue, value)) { 193 Log.e("test", "Bad hash array entry set: expected key " + realValue 194 + ", got " + value + " at index " + index); 195 return false; 196 } 197 value = entry.getValue(); 198 realValue = array.valueAt(index); 199 if (!compare(realValue, value)) { 200 Log.e("test", "Bad hash array entry set: expected value " + realValue 201 + ", got " + value + " at index " + index); 202 return false; 203 } 204 index++; 205 } 206 207 index = 0; 208 Set keySet = array.keySet(); 209 Iterator keyIt = keySet.iterator(); 210 while (keyIt.hasNext()) { 211 Object value = keyIt.next(); 212 Object realValue = array.keyAt(index); 213 if (!compare(realValue, value)) { 214 Log.e("test", "Bad hash array key set: expected key " + realValue 215 + ", got " + value + " at index " + index); 216 return false; 217 } 218 index++; 219 } 220 221 index = 0; 222 Collection valueCol = array.values(); 223 Iterator valueIt = valueCol.iterator(); 224 while (valueIt.hasNext()) { 225 Object value = valueIt.next(); 226 Object realValue = array.valueAt(index); 227 if (!compare(realValue, value)) { 228 Log.e("test", "Bad hash array value col: expected value " + realValue 229 + ", got " + value + " at index " + index); 230 return false; 231 } 232 index++; 233 } 234 235 return true; 236 } 237 238 private static void dump(HashMap map, ArrayMap array) { 239 Log.e("test", "HashMap of " + map.size() + " entries:"); 240 Set<Map.Entry> mapSet = map.entrySet(); 241 for (Map.Entry entry : mapSet) { 242 Log.e("test", " " + entry.getKey() + " -> " + entry.getValue()); 243 } 244 Log.e("test", "ArrayMap of " + array.size() + " entries:"); 245 for (int i=0; i<array.size(); i++) { 246 Log.e("test", " " + array.keyAt(i) + " -> " + array.valueAt(i)); 247 } 248 } 249 250 private static void dump(ArrayMap map1, ArrayMap map2) { 251 Log.e("test", "ArrayMap of " + map1.size() + " entries:"); 252 Set<Map.Entry> mapSet = map1.entrySet(); 253 for (int i=0; i<map2.size(); i++) { 254 Log.e("test", " " + map1.keyAt(i) + " -> " + map1.valueAt(i)); 255 } 256 Log.e("test", "ArrayMap of " + map2.size() + " entries:"); 257 for (int i=0; i<map2.size(); i++) { 258 Log.e("test", " " + map2.keyAt(i) + " -> " + map2.valueAt(i)); 259 } 260 } 261 262 public static void run() { 263 HashMap<ControlledHash, Integer> mHashMap = new HashMap<ControlledHash, Integer>(); 264 ArrayMap<ControlledHash, Integer> mArrayMap = new ArrayMap<ControlledHash, Integer>(); 265 266 for (int i=0; i<OPS.length; i++) { 267 Integer oldMap; 268 Integer oldArray; 269 switch (OPS[i]) { 270 case OP_ADD: 271 Log.i("test", "Adding key: " + KEYS[i]); 272 oldMap = mHashMap.put(new ControlledHash(KEYS[i]), i); 273 oldArray = mArrayMap.put(new ControlledHash(KEYS[i]), i); 274 break; 275 case OP_REM: 276 Log.i("test", "Removing key: " + KEYS[i]); 277 oldMap = mHashMap.remove(new ControlledHash(KEYS[i])); 278 oldArray = mArrayMap.remove(new ControlledHash(KEYS[i])); 279 break; 280 default: 281 Log.e("test", "Bad operation " + OPS[i] + " @ " + i); 282 return; 283 } 284 if (!compare(oldMap, oldArray)) { 285 Log.e("test", "Bad result: expected " + oldMap + ", got " + oldArray); 286 dump(mHashMap, mArrayMap); 287 return; 288 } 289 if (!validateArrayMap(mArrayMap)) { 290 dump(mHashMap, mArrayMap); 291 return; 292 } 293 if (!compareMaps(mHashMap, mArrayMap)) { 294 dump(mHashMap, mArrayMap); 295 return; 296 } 297 } 298 299 mArrayMap.put(new ControlledHash(50000), 100); 300 ControlledHash lookup = new ControlledHash(50000); 301 Iterator<ControlledHash> it = mArrayMap.keySet().iterator(); 302 while (it.hasNext()) { 303 if (it.next().equals(lookup)) { 304 it.remove(); 305 } 306 } 307 if (mArrayMap.containsKey(lookup)) { 308 Log.e("test", "Bad iterator: didn't remove test key"); 309 dump(mHashMap, mArrayMap); 310 } 311 312 if (!equalsTest()) { 313 return; 314 } 315 316 // copy constructor test 317 ArrayMap newMap = new ArrayMap<Integer, String>(); 318 for (int i = 0; i < 10; ++i) { 319 newMap.put(i, String.valueOf(i)); 320 } 321 ArrayMap mapCopy = new ArrayMap(newMap); 322 if (!compare(mapCopy, newMap)) { 323 Log.e("test", "ArrayMap copy constructor failure: expected " + 324 newMap + ", got " + mapCopy); 325 dump(mHashMap, mArrayMap); 326 return; 327 } 328 329 Log.e("test", "Test successful; printing final map."); 330 dump(mHashMap, mArrayMap); 331 } 332 333 private static boolean equalsTest() { 334 ArrayMap<Integer, String> map1 = new ArrayMap<Integer, String>(); 335 ArrayMap<Integer, String> map2 = new ArrayMap<Integer, String>(); 336 HashMap<Integer, String> map3 = new HashMap<Integer, String>(); 337 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 338 Log.e("test", "ArrayMap equals failure for empty maps " + map1 + ", " + 339 map2 + ", " + map3); 340 return false; 341 } 342 343 for (int i = 0; i < 10; ++i) { 344 String value = String.valueOf(i); 345 map1.put(i, value); 346 map2.put(i, value); 347 map3.put(i, value); 348 } 349 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 350 Log.e("test", "ArrayMap equals failure for populated maps " + map1 + ", " + 351 map2 + ", " + map3); 352 return false; 353 } 354 355 map1.remove(0); 356 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 357 Log.e("test", "ArrayMap equals failure for map size " + map1 + ", " + 358 map2 + ", " + map3); 359 return false; 360 } 361 362 map1.put(0, "-1"); 363 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 364 Log.e("test", "ArrayMap equals failure for map contents " + map1 + ", " + 365 map2 + ", " + map3); 366 return false; 367 } 368 369 return true; 370 } 371} 372