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 17 package com.google.android.test.activity; 18 19 import android.util.ArrayMap; 20 import android.util.ArraySet; 21 import android.util.Log; 22 23 import java.util.Collection; 24 import java.util.HashMap; 25 import java.util.HashSet; 26 import java.util.Iterator; 27 import java.util.Map; 28 import java.util.Set; 29 30 public class ArrayMapTests { 31 static final int OP_ADD = 1; 32 static final int OP_REM = 2; 33 34 static int[] OPS = new int[] { 35 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 36 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 37 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 38 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 39 40 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 41 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 42 43 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 44 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 45 46 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 47 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 48 49 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 50 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 51 OP_ADD, OP_ADD, OP_ADD, 52 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 53 OP_REM, OP_REM, OP_REM, 54 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 55 }; 56 57 static int[] KEYS = new int[] { 58 // General adding and removing. 59 -1, 1900, 600, 200, 1200, 1500, 1800, 100, 1900, 60 2100, 300, 800, 600, 1100, 1300, 2000, 1000, 1400, 61 600, -1, 1900, 600, 300, 2100, 200, 800, 800, 62 1800, 1500, 1300, 1100, 2000, 1400, 1000, 1200, 1900, 63 64 // Shrink when removing item from end. 65 100, 200, 300, 400, 500, 600, 700, 800, 900, 66 900, 800, 700, 600, 500, 400, 300, 200, 100, 67 68 // Shrink when removing item from middle. 69 100, 200, 300, 400, 500, 600, 700, 800, 900, 70 900, 800, 700, 600, 500, 400, 200, 300, 100, 71 72 // Shrink when removing item from front. 73 100, 200, 300, 400, 500, 600, 700, 800, 900, 74 900, 800, 700, 600, 500, 400, 100, 200, 300, 75 76 // Test hash collisions. 77 105, 106, 108, 104, 102, 102, 107, 5, 205, 78 4, 202, 203, 3, 5, 101, 109, 200, 201, 79 0, -1, 100, 80 106, 108, 104, 102, 103, 105, 107, 101, 109, 81 -1, 100, 0, 82 4, 5, 3, 5, 200, 203, 202, 201, 205, 83 }; 84 85 static class ControlledHash { 86 final int mValue; 87 ControlledHash(int value)88 ControlledHash(int value) { 89 mValue = value; 90 } 91 92 @Override equals(Object o)93 public final boolean equals(Object o) { 94 if (o == null) { 95 return false; 96 } 97 return mValue == ((ControlledHash)o).mValue; 98 } 99 100 @Override hashCode()101 public final int hashCode() { 102 return mValue/100; 103 } 104 105 @Override toString()106 public final String toString() { 107 return Integer.toString(mValue); 108 } 109 } 110 compare(Object v1, Object v2)111 private static boolean compare(Object v1, Object v2) { 112 if (v1 == null) { 113 return v2 == null; 114 } 115 if (v2 == null) { 116 return false; 117 } 118 return v1.equals(v2); 119 } 120 compareMaps(HashMap map, ArrayMap array)121 private static boolean compareMaps(HashMap map, ArrayMap array) { 122 if (map.size() != array.size()) { 123 Log.e("test", "Bad size: expected " + map.size() + ", got " + array.size()); 124 return false; 125 } 126 127 Set<Map.Entry> mapSet = map.entrySet(); 128 for (Map.Entry entry : mapSet) { 129 Object expValue = entry.getValue(); 130 Object gotValue = array.get(entry.getKey()); 131 if (!compare(expValue, gotValue)) { 132 Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue 133 + " at key " + entry.getKey()); 134 return false; 135 } 136 } 137 138 for (int i=0; i<array.size(); i++) { 139 Object gotValue = array.valueAt(i); 140 Object key = array.keyAt(i); 141 Object expValue = map.get(key); 142 if (!compare(expValue, gotValue)) { 143 Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue 144 + " at key " + key); 145 return false; 146 } 147 } 148 149 if (map.entrySet().hashCode() != array.entrySet().hashCode()) { 150 Log.e("test", "Entry set hash codes differ: map=0x" 151 + Integer.toHexString(map.entrySet().hashCode()) + " array=0x" 152 + Integer.toHexString(array.entrySet().hashCode())); 153 return false; 154 } 155 156 if (!map.entrySet().equals(array.entrySet())) { 157 Log.e("test", "Failed calling equals on map entry set against array set"); 158 return false; 159 } 160 161 if (!array.entrySet().equals(map.entrySet())) { 162 Log.e("test", "Failed calling equals on array entry set against map set"); 163 return false; 164 } 165 166 if (map.keySet().hashCode() != array.keySet().hashCode()) { 167 Log.e("test", "Key set hash codes differ: map=0x" 168 + Integer.toHexString(map.keySet().hashCode()) + " array=0x" 169 + Integer.toHexString(array.keySet().hashCode())); 170 return false; 171 } 172 173 if (!map.keySet().equals(array.keySet())) { 174 Log.e("test", "Failed calling equals on map key set against array set"); 175 return false; 176 } 177 178 if (!array.keySet().equals(map.keySet())) { 179 Log.e("test", "Failed calling equals on array key set against map set"); 180 return false; 181 } 182 183 if (!map.keySet().containsAll(array.keySet())) { 184 Log.e("test", "Failed map key set contains all of array key set"); 185 return false; 186 } 187 188 if (!array.keySet().containsAll(map.keySet())) { 189 Log.e("test", "Failed array key set contains all of map key set"); 190 return false; 191 } 192 193 if (!array.containsAll(map.keySet())) { 194 Log.e("test", "Failed array contains all of map key set"); 195 return false; 196 } 197 198 if (!map.entrySet().containsAll(array.entrySet())) { 199 Log.e("test", "Failed map entry set contains all of array entry set"); 200 return false; 201 } 202 203 if (!array.entrySet().containsAll(map.entrySet())) { 204 Log.e("test", "Failed array entry set contains all of map entry set"); 205 return false; 206 } 207 208 return true; 209 } 210 compareSets(HashSet set, ArraySet array)211 private static boolean compareSets(HashSet set, ArraySet array) { 212 if (set.size() != array.size()) { 213 Log.e("test", "Bad size: expected " + set.size() + ", got " + array.size()); 214 return false; 215 } 216 217 for (Object entry : set) { 218 if (!array.contains(entry)) { 219 Log.e("test", "Bad value: expected " + entry + " not found in ArraySet"); 220 return false; 221 } 222 } 223 224 for (int i=0; i<array.size(); i++) { 225 Object entry = array.valueAt(i); 226 if (!set.contains(entry)) { 227 Log.e("test", "Bad value: unexpected " + entry + " in ArraySet"); 228 return false; 229 } 230 } 231 232 int index = 0; 233 for (Object entry : array) { 234 Object realEntry = array.valueAt(index); 235 if (!compare(entry, realEntry)) { 236 Log.e("test", "Bad iterator: expected value " + realEntry + ", got " + entry 237 + " at index " + index); 238 return false; 239 } 240 index++; 241 } 242 243 return true; 244 } 245 validateArrayMap(ArrayMap array)246 private static boolean validateArrayMap(ArrayMap array) { 247 Set<Map.Entry> entrySet = array.entrySet(); 248 int index=0; 249 Iterator<Map.Entry> entryIt = entrySet.iterator(); 250 while (entryIt.hasNext()) { 251 Map.Entry entry = entryIt.next(); 252 Object value = entry.getKey(); 253 Object realValue = array.keyAt(index); 254 if (!compare(realValue, value)) { 255 Log.e("test", "Bad array map entry set: expected key " + realValue 256 + ", got " + value + " at index " + index); 257 return false; 258 } 259 value = entry.getValue(); 260 realValue = array.valueAt(index); 261 if (!compare(realValue, value)) { 262 Log.e("test", "Bad array map entry set: expected value " + realValue 263 + ", got " + value + " at index " + index); 264 return false; 265 } 266 index++; 267 } 268 269 index = 0; 270 Set keySet = array.keySet(); 271 Iterator keyIt = keySet.iterator(); 272 while (keyIt.hasNext()) { 273 Object value = keyIt.next(); 274 Object realValue = array.keyAt(index); 275 if (!compare(realValue, value)) { 276 Log.e("test", "Bad array map key set: expected key " + realValue 277 + ", got " + value + " at index " + index); 278 return false; 279 } 280 index++; 281 } 282 283 index = 0; 284 Collection valueCol = array.values(); 285 Iterator valueIt = valueCol.iterator(); 286 while (valueIt.hasNext()) { 287 Object value = valueIt.next(); 288 Object realValue = array.valueAt(index); 289 if (!compare(realValue, value)) { 290 Log.e("test", "Bad array map value col: expected value " + realValue 291 + ", got " + value + " at index " + index); 292 return false; 293 } 294 index++; 295 } 296 297 return true; 298 } 299 dump(Map map, ArrayMap array)300 private static void dump(Map map, ArrayMap array) { 301 Log.e("test", "HashMap of " + map.size() + " entries:"); 302 Set<Map.Entry> mapSet = map.entrySet(); 303 for (Map.Entry entry : mapSet) { 304 Log.e("test", " " + entry.getKey() + " -> " + entry.getValue()); 305 } 306 Log.e("test", "ArrayMap of " + array.size() + " entries:"); 307 for (int i=0; i<array.size(); i++) { 308 Log.e("test", " " + array.keyAt(i) + " -> " + array.valueAt(i)); 309 } 310 } 311 dump(Set set, ArraySet array)312 private static void dump(Set set, ArraySet array) { 313 Log.e("test", "HashSet of " + set.size() + " entries:"); 314 for (Object entry : set) { 315 Log.e("test", " " + entry); 316 } 317 Log.e("test", "ArraySet of " + array.size() + " entries:"); 318 for (int i=0; i<array.size(); i++) { 319 Log.e("test", " " + array.valueAt(i)); 320 } 321 } 322 dump(ArrayMap map1, ArrayMap map2)323 private static void dump(ArrayMap map1, ArrayMap map2) { 324 Log.e("test", "ArrayMap of " + map1.size() + " entries:"); 325 Set<Map.Entry> mapSet = map1.entrySet(); 326 for (int i=0; i<map2.size(); i++) { 327 Log.e("test", " " + map1.keyAt(i) + " -> " + map1.valueAt(i)); 328 } 329 Log.e("test", "ArrayMap of " + map2.size() + " entries:"); 330 for (int i=0; i<map2.size(); i++) { 331 Log.e("test", " " + map2.keyAt(i) + " -> " + map2.valueAt(i)); 332 } 333 } 334 run()335 public static void run() { 336 HashMap<ControlledHash, Integer> hashMap = new HashMap<ControlledHash, Integer>(); 337 ArrayMap<ControlledHash, Integer> arrayMap = new ArrayMap<ControlledHash, Integer>(); 338 HashSet<ControlledHash> hashSet = new HashSet<ControlledHash>(); 339 ArraySet<ControlledHash> arraySet = new ArraySet<ControlledHash>(); 340 341 for (int i=0; i<OPS.length; i++) { 342 Integer oldHash; 343 Integer oldArray; 344 boolean hashChanged; 345 boolean arrayChanged; 346 ControlledHash key = KEYS[i] < 0 ? null : new ControlledHash(KEYS[i]); 347 switch (OPS[i]) { 348 case OP_ADD: 349 Log.i("test", "Adding key: " + KEYS[i]); 350 oldHash = hashMap.put(key, i); 351 oldArray = arrayMap.put(key, i); 352 hashChanged = hashSet.add(key); 353 arrayChanged = arraySet.add(key); 354 break; 355 case OP_REM: 356 Log.i("test", "Removing key: " + KEYS[i]); 357 oldHash = hashMap.remove(key); 358 oldArray = arrayMap.remove(key); 359 hashChanged = hashSet.remove(key); 360 arrayChanged = arraySet.remove(key); 361 break; 362 default: 363 Log.e("test", "Bad operation " + OPS[i] + " @ " + i); 364 return; 365 } 366 if (!compare(oldHash, oldArray)) { 367 Log.e("test", "Bad result: expected " + oldHash + ", got " + oldArray); 368 dump(hashMap, arrayMap); 369 return; 370 } 371 if (hashChanged != arrayChanged) { 372 Log.e("test", "Bad change: expected " + hashChanged + ", got " + arrayChanged); 373 dump(hashSet, arraySet); 374 return; 375 } 376 if (!validateArrayMap(arrayMap)) { 377 dump(hashMap, arrayMap); 378 return; 379 } 380 if (!compareMaps(hashMap, arrayMap)) { 381 dump(hashMap, arrayMap); 382 return; 383 } 384 if (!compareSets(hashSet, arraySet)) { 385 dump(hashSet, arraySet); 386 return; 387 } 388 } 389 390 arrayMap.put(new ControlledHash(50000), 100); 391 ControlledHash lookup = new ControlledHash(50000); 392 Iterator<ControlledHash> it = arrayMap.keySet().iterator(); 393 while (it.hasNext()) { 394 if (it.next().equals(lookup)) { 395 it.remove(); 396 } 397 } 398 if (arrayMap.containsKey(lookup)) { 399 Log.e("test", "Bad map iterator: didn't remove test key"); 400 dump(hashMap, arrayMap); 401 } 402 403 arraySet.add(new ControlledHash(50000)); 404 it = arraySet.iterator(); 405 while (it.hasNext()) { 406 if (it.next().equals(lookup)) { 407 it.remove(); 408 } 409 } 410 if (arraySet.contains(lookup)) { 411 Log.e("test", "Bad set iterator: didn't remove test key"); 412 dump(hashSet, arraySet); 413 } 414 415 if (!equalsMapTest()) { 416 return; 417 } 418 419 if (!equalsSetTest()) { 420 return; 421 } 422 423 // map copy constructor test 424 ArrayMap newMap = new ArrayMap<Integer, String>(); 425 for (int i = 0; i < 10; ++i) { 426 newMap.put(i, String.valueOf(i)); 427 } 428 ArrayMap mapCopy = new ArrayMap(newMap); 429 if (!compare(mapCopy, newMap)) { 430 Log.e("test", "ArrayMap copy constructor failure: expected " + 431 newMap + ", got " + mapCopy); 432 dump(newMap, mapCopy); 433 return; 434 } 435 436 // set copy constructor test 437 ArraySet newSet = new ArraySet<Integer>(); 438 for (int i = 0; i < 10; ++i) { 439 newSet.add(i); 440 } 441 ArraySet setCopy = new ArraySet(newSet); 442 if (!compare(setCopy, newSet)) { 443 Log.e("test", "ArraySet copy constructor failure: expected " + 444 newSet + ", got " + setCopy); 445 dump(newSet, setCopy); 446 return; 447 } 448 449 Log.e("test", "Test successful; printing final map."); 450 dump(hashMap, arrayMap); 451 452 Log.e("test", "Test successful; printing final set."); 453 dump(hashSet, arraySet); 454 } 455 456 private static boolean equalsMapTest() { 457 ArrayMap<Integer, String> map1 = new ArrayMap<Integer, String>(); 458 ArrayMap<Integer, String> map2 = new ArrayMap<Integer, String>(); 459 HashMap<Integer, String> map3 = new HashMap<Integer, String>(); 460 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 461 Log.e("test", "ArrayMap equals failure for empty maps " + map1 + ", " + 462 map2 + ", " + map3); 463 return false; 464 } 465 466 for (int i = 0; i < 10; ++i) { 467 String value = String.valueOf(i); 468 map1.put(i, value); 469 map2.put(i, value); 470 map3.put(i, value); 471 } 472 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 473 Log.e("test", "ArrayMap equals failure for populated maps " + map1 + ", " + 474 map2 + ", " + map3); 475 return false; 476 } 477 478 map1.remove(0); 479 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 480 Log.e("test", "ArrayMap equals failure for map size " + map1 + ", " + 481 map2 + ", " + map3); 482 return false; 483 } 484 485 map1.put(0, "-1"); 486 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 487 Log.e("test", "ArrayMap equals failure for map contents " + map1 + ", " + 488 map2 + ", " + map3); 489 return false; 490 } 491 492 return true; 493 } 494 495 private static boolean equalsSetTest() { 496 ArraySet<Integer> set1 = new ArraySet<Integer>(); 497 ArraySet<Integer> set2 = new ArraySet<Integer>(); 498 HashSet<Integer> set3 = new HashSet<Integer>(); 499 if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { 500 Log.e("test", "ArraySet equals failure for empty sets " + set1 + ", " + 501 set2 + ", " + set3); 502 return false; 503 } 504 505 for (int i = 0; i < 10; ++i) { 506 set1.add(i); 507 set2.add(i); 508 set3.add(i); 509 } 510 if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { 511 Log.e("test", "ArraySet equals failure for populated sets " + set1 + ", " + 512 set2 + ", " + set3); 513 return false; 514 } 515 516 set1.remove(0); 517 if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { 518 Log.e("test", "ArraSet equals failure for set size " + set1 + ", " + 519 set2 + ", " + set3); 520 return false; 521 } 522 523 set1.add(-1); 524 if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { 525 Log.e("test", "ArraySet equals failure for set contents " + set1 + ", " + 526 set2 + ", " + set3); 527 return false; 528 } 529 530 return true; 531 } 532 } 533