ArrayMapTests.java revision 62d708f4dd8e2a8554df4967837df9896efeff7c
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.ArraySet; 21import android.util.Log; 22 23import java.util.Collection; 24import java.util.HashMap; 25import java.util.HashSet; 26import java.util.Iterator; 27import java.util.Map; 28import java.util.Set; 29 30public 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 88 ControlledHash(int value) { 89 mValue = value; 90 } 91 92 @Override 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 101 public final int hashCode() { 102 return mValue/100; 103 } 104 105 @Override 106 public final String toString() { 107 return Integer.toString(mValue); 108 } 109 } 110 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 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 return true; 150 } 151 152 private static boolean compareSets(HashSet set, ArraySet array) { 153 if (set.size() != array.size()) { 154 Log.e("test", "Bad size: expected " + set.size() + ", got " + array.size()); 155 return false; 156 } 157 158 for (Object entry : set) { 159 if (!array.contains(entry)) { 160 Log.e("test", "Bad value: expected " + entry + " not found in ArraySet"); 161 return false; 162 } 163 } 164 165 for (int i=0; i<array.size(); i++) { 166 Object entry = array.valueAt(i); 167 if (!set.contains(entry)) { 168 Log.e("test", "Bad value: unexpected " + entry + " in ArraySet"); 169 return false; 170 } 171 } 172 173 int index = 0; 174 for (Object entry : array) { 175 Object realEntry = array.valueAt(index); 176 if (!compare(entry, realEntry)) { 177 Log.e("test", "Bad iterator: expected value " + realEntry + ", got " + entry 178 + " at index " + index); 179 return false; 180 } 181 index++; 182 } 183 184 return true; 185 } 186 187 private static boolean validateArrayMap(ArrayMap array) { 188 Set<Map.Entry> entrySet = array.entrySet(); 189 int index=0; 190 Iterator<Map.Entry> entryIt = entrySet.iterator(); 191 while (entryIt.hasNext()) { 192 Map.Entry entry = entryIt.next(); 193 Object value = entry.getKey(); 194 Object realValue = array.keyAt(index); 195 if (!compare(realValue, value)) { 196 Log.e("test", "Bad array map entry set: expected key " + realValue 197 + ", got " + value + " at index " + index); 198 return false; 199 } 200 value = entry.getValue(); 201 realValue = array.valueAt(index); 202 if (!compare(realValue, value)) { 203 Log.e("test", "Bad array map entry set: expected value " + realValue 204 + ", got " + value + " at index " + index); 205 return false; 206 } 207 index++; 208 } 209 210 index = 0; 211 Set keySet = array.keySet(); 212 Iterator keyIt = keySet.iterator(); 213 while (keyIt.hasNext()) { 214 Object value = keyIt.next(); 215 Object realValue = array.keyAt(index); 216 if (!compare(realValue, value)) { 217 Log.e("test", "Bad array map key set: expected key " + realValue 218 + ", got " + value + " at index " + index); 219 return false; 220 } 221 index++; 222 } 223 224 index = 0; 225 Collection valueCol = array.values(); 226 Iterator valueIt = valueCol.iterator(); 227 while (valueIt.hasNext()) { 228 Object value = valueIt.next(); 229 Object realValue = array.valueAt(index); 230 if (!compare(realValue, value)) { 231 Log.e("test", "Bad array map value col: expected value " + realValue 232 + ", got " + value + " at index " + index); 233 return false; 234 } 235 index++; 236 } 237 238 return true; 239 } 240 241 private static void dump(Map map, ArrayMap array) { 242 Log.e("test", "HashMap of " + map.size() + " entries:"); 243 Set<Map.Entry> mapSet = map.entrySet(); 244 for (Map.Entry entry : mapSet) { 245 Log.e("test", " " + entry.getKey() + " -> " + entry.getValue()); 246 } 247 Log.e("test", "ArrayMap of " + array.size() + " entries:"); 248 for (int i=0; i<array.size(); i++) { 249 Log.e("test", " " + array.keyAt(i) + " -> " + array.valueAt(i)); 250 } 251 } 252 253 private static void dump(Set set, ArraySet array) { 254 Log.e("test", "HashSet of " + set.size() + " entries:"); 255 for (Object entry : set) { 256 Log.e("test", " " + entry); 257 } 258 Log.e("test", "ArraySet of " + array.size() + " entries:"); 259 for (int i=0; i<array.size(); i++) { 260 Log.e("test", " " + array.valueAt(i)); 261 } 262 } 263 264 private static void dump(ArrayMap map1, ArrayMap map2) { 265 Log.e("test", "ArrayMap of " + map1.size() + " entries:"); 266 Set<Map.Entry> mapSet = map1.entrySet(); 267 for (int i=0; i<map2.size(); i++) { 268 Log.e("test", " " + map1.keyAt(i) + " -> " + map1.valueAt(i)); 269 } 270 Log.e("test", "ArrayMap of " + map2.size() + " entries:"); 271 for (int i=0; i<map2.size(); i++) { 272 Log.e("test", " " + map2.keyAt(i) + " -> " + map2.valueAt(i)); 273 } 274 } 275 276 public static void run() { 277 HashMap<ControlledHash, Integer> hashMap = new HashMap<ControlledHash, Integer>(); 278 ArrayMap<ControlledHash, Integer> arrayMap = new ArrayMap<ControlledHash, Integer>(); 279 HashSet<ControlledHash> hashSet = new HashSet<ControlledHash>(); 280 ArraySet<ControlledHash> arraySet = new ArraySet<ControlledHash>(); 281 282 for (int i=0; i<OPS.length; i++) { 283 Integer oldHash; 284 Integer oldArray; 285 boolean hashChanged; 286 boolean arrayChanged; 287 ControlledHash key = KEYS[i] < 0 ? null : new ControlledHash(KEYS[i]); 288 switch (OPS[i]) { 289 case OP_ADD: 290 Log.i("test", "Adding key: " + KEYS[i]); 291 oldHash = hashMap.put(key, i); 292 oldArray = arrayMap.put(key, i); 293 hashChanged = hashSet.add(key); 294 arrayChanged = arraySet.add(key); 295 break; 296 case OP_REM: 297 Log.i("test", "Removing key: " + KEYS[i]); 298 oldHash = hashMap.remove(key); 299 oldArray = arrayMap.remove(key); 300 hashChanged = hashSet.remove(key); 301 arrayChanged = arraySet.remove(key); 302 break; 303 default: 304 Log.e("test", "Bad operation " + OPS[i] + " @ " + i); 305 return; 306 } 307 if (!compare(oldHash, oldArray)) { 308 Log.e("test", "Bad result: expected " + oldHash + ", got " + oldArray); 309 dump(hashMap, arrayMap); 310 return; 311 } 312 if (hashChanged != arrayChanged) { 313 Log.e("test", "Bad change: expected " + hashChanged + ", got " + arrayChanged); 314 dump(hashSet, arraySet); 315 return; 316 } 317 if (!validateArrayMap(arrayMap)) { 318 dump(hashMap, arrayMap); 319 return; 320 } 321 if (!compareMaps(hashMap, arrayMap)) { 322 dump(hashMap, arrayMap); 323 return; 324 } 325 if (!compareSets(hashSet, arraySet)) { 326 dump(hashSet, arraySet); 327 return; 328 } 329 } 330 331 arrayMap.put(new ControlledHash(50000), 100); 332 ControlledHash lookup = new ControlledHash(50000); 333 Iterator<ControlledHash> it = arrayMap.keySet().iterator(); 334 while (it.hasNext()) { 335 if (it.next().equals(lookup)) { 336 it.remove(); 337 } 338 } 339 if (arrayMap.containsKey(lookup)) { 340 Log.e("test", "Bad map iterator: didn't remove test key"); 341 dump(hashMap, arrayMap); 342 } 343 344 arraySet.add(new ControlledHash(50000)); 345 it = arraySet.iterator(); 346 while (it.hasNext()) { 347 if (it.next().equals(lookup)) { 348 it.remove(); 349 } 350 } 351 if (arraySet.contains(lookup)) { 352 Log.e("test", "Bad set iterator: didn't remove test key"); 353 dump(hashSet, arraySet); 354 } 355 356 if (!equalsMapTest()) { 357 return; 358 } 359 360 if (!equalsSetTest()) { 361 return; 362 } 363 364 // map copy constructor test 365 ArrayMap newMap = new ArrayMap<Integer, String>(); 366 for (int i = 0; i < 10; ++i) { 367 newMap.put(i, String.valueOf(i)); 368 } 369 ArrayMap mapCopy = new ArrayMap(newMap); 370 if (!compare(mapCopy, newMap)) { 371 Log.e("test", "ArrayMap copy constructor failure: expected " + 372 newMap + ", got " + mapCopy); 373 dump(newMap, mapCopy); 374 return; 375 } 376 377 // set copy constructor test 378 ArraySet newSet = new ArraySet<Integer>(); 379 for (int i = 0; i < 10; ++i) { 380 newSet.add(i); 381 } 382 ArraySet setCopy = new ArraySet(newSet); 383 if (!compare(setCopy, newSet)) { 384 Log.e("test", "ArraySet copy constructor failure: expected " + 385 newSet + ", got " + setCopy); 386 dump(newSet, setCopy); 387 return; 388 } 389 390 Log.e("test", "Test successful; printing final map."); 391 dump(hashMap, arrayMap); 392 393 Log.e("test", "Test successful; printing final set."); 394 dump(hashSet, arraySet); 395 } 396 397 private static boolean equalsMapTest() { 398 ArrayMap<Integer, String> map1 = new ArrayMap<Integer, String>(); 399 ArrayMap<Integer, String> map2 = new ArrayMap<Integer, String>(); 400 HashMap<Integer, String> map3 = new HashMap<Integer, String>(); 401 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 402 Log.e("test", "ArrayMap equals failure for empty maps " + map1 + ", " + 403 map2 + ", " + map3); 404 return false; 405 } 406 407 for (int i = 0; i < 10; ++i) { 408 String value = String.valueOf(i); 409 map1.put(i, value); 410 map2.put(i, value); 411 map3.put(i, value); 412 } 413 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 414 Log.e("test", "ArrayMap equals failure for populated maps " + map1 + ", " + 415 map2 + ", " + map3); 416 return false; 417 } 418 419 map1.remove(0); 420 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 421 Log.e("test", "ArrayMap equals failure for map size " + map1 + ", " + 422 map2 + ", " + map3); 423 return false; 424 } 425 426 map1.put(0, "-1"); 427 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 428 Log.e("test", "ArrayMap equals failure for map contents " + map1 + ", " + 429 map2 + ", " + map3); 430 return false; 431 } 432 433 return true; 434 } 435 436 private static boolean equalsSetTest() { 437 ArraySet<Integer> set1 = new ArraySet<Integer>(); 438 ArraySet<Integer> set2 = new ArraySet<Integer>(); 439 HashSet<Integer> set3 = new HashSet<Integer>(); 440 if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { 441 Log.e("test", "ArraySet equals failure for empty sets " + set1 + ", " + 442 set2 + ", " + set3); 443 return false; 444 } 445 446 for (int i = 0; i < 10; ++i) { 447 set1.add(i); 448 set2.add(i); 449 set3.add(i); 450 } 451 if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { 452 Log.e("test", "ArraySet equals failure for populated sets " + set1 + ", " + 453 set2 + ", " + set3); 454 return false; 455 } 456 457 set1.remove(0); 458 if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { 459 Log.e("test", "ArraSet equals failure for set size " + set1 + ", " + 460 set2 + ", " + set3); 461 return false; 462 } 463 464 set1.add(-1); 465 if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { 466 Log.e("test", "ArraySet equals failure for set contents " + set1 + ", " + 467 set2 + ", " + set3); 468 return false; 469 } 470 471 return true; 472 } 473} 474