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