1 /* 2 * Copyright (C) 2015 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 android.util.cts; 18 19 import android.test.AndroidTestCase; 20 import android.util.ArraySet; 21 import android.util.Log; 22 23 import java.util.ArrayList; 24 import java.util.Collection; 25 import java.util.HashSet; 26 import java.util.Iterator; 27 import java.util.Set; 28 29 // As is the case with ArraySet itself, ArraySetTest borrows heavily from ArrayMapTest. 30 31 public class ArraySetTest extends AndroidTestCase { 32 private static final String TAG = "ArraySetTest"; 33 34 private static final boolean DEBUG = false; 35 36 private static final int OP_ADD = 1; 37 private static final int OP_REM = 2; 38 39 private static int[] OPS = new int[] { 40 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 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 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 44 45 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 46 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 47 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 51 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 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 54 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 55 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 56 OP_ADD, OP_ADD, OP_ADD, 57 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 58 OP_REM, OP_REM, OP_REM, 59 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 60 }; 61 62 private static int[] KEYS = new int[] { 63 // General adding and removing. 64 -1, 1900, 600, 200, 1200, 1500, 1800, 100, 1900, 65 2100, 300, 800, 600, 1100, 1300, 2000, 1000, 1400, 66 600, -1, 1900, 600, 300, 2100, 200, 800, 800, 67 1800, 1500, 1300, 1100, 2000, 1400, 1000, 1200, 1900, 68 69 // Shrink when removing item from end. 70 100, 200, 300, 400, 500, 600, 700, 800, 900, 71 900, 800, 700, 600, 500, 400, 300, 200, 100, 72 73 // Shrink when removing item from middle. 74 100, 200, 300, 400, 500, 600, 700, 800, 900, 75 900, 800, 700, 600, 500, 400, 200, 300, 100, 76 77 // Shrink when removing item from front. 78 100, 200, 300, 400, 500, 600, 700, 800, 900, 79 900, 800, 700, 600, 500, 400, 100, 200, 300, 80 81 // Test hash collisions. 82 105, 106, 108, 104, 102, 102, 107, 5, 205, 83 4, 202, 203, 3, 5, 101, 109, 200, 201, 84 0, -1, 100, 85 106, 108, 104, 102, 103, 105, 107, 101, 109, 86 -1, 100, 0, 87 4, 5, 3, 5, 200, 203, 202, 201, 205, 88 }; 89 90 public static class ControlledHash { 91 final int mValue; 92 ControlledHash(int value)93 ControlledHash(int value) { 94 mValue = value; 95 } 96 97 @Override equals(Object o)98 public final boolean equals(Object o) { 99 if (o == null) { 100 return false; 101 } 102 return mValue == ((ControlledHash)o).mValue; 103 } 104 105 @Override hashCode()106 public final int hashCode() { 107 return mValue/100; 108 } 109 110 @Override toString()111 public final String toString() { 112 return Integer.toString(mValue); 113 } 114 } 115 compare(Object v1, Object v2)116 private static boolean compare(Object v1, Object v2) { 117 if (v1 == null) { 118 return v2 == null; 119 } 120 if (v2 == null) { 121 return false; 122 } 123 return v1.equals(v2); 124 } 125 compareSets(HashSet<E> set, ArraySet<E> array)126 private static <E> void compareSets(HashSet<E> set, ArraySet<E> array) { 127 assertEquals("Bad size", set.size(), array.size()); 128 129 // Check that every entry in HashSet is in ArraySet. 130 for (E entry : set) { 131 assertTrue("ArraySet missing value: " + entry, array.contains(entry)); 132 } 133 134 // Check that every entry in ArraySet is in HashSet using ArraySet.iterator(). 135 for (E entry : array) { 136 assertTrue("ArraySet (via iterator) has unexpected value: " + entry, 137 set.contains(entry)); 138 } 139 140 // Check that every entry in ArraySet is in HashSet using ArraySet.valueAt(). 141 for (int i = 0; i < array.size(); ++i) { 142 E entry = array.valueAt(i); 143 assertTrue("ArraySet (via valueAt) has unexpected value: " + entry, 144 set.contains(entry)); 145 } 146 147 if (set.hashCode() != array.hashCode()) { 148 assertEquals("Set hash codes differ", set.hashCode(), array.hashCode()); 149 } 150 151 assertTrue("HashSet.equals(ArraySet) failed", set.equals(array)); 152 assertTrue("ArraySet.equals(HashSet) failed", array.equals(set)); 153 154 assertTrue("HashSet.containsAll(ArraySet) failed", set.containsAll(array)); 155 assertTrue("ArraySet.containsAll(HashSet) failed", array.containsAll(set)); 156 } 157 compareArraySetAndRawArray(ArraySet<E> arraySet, Object[] rawArray)158 private static <E> void compareArraySetAndRawArray(ArraySet<E> arraySet, Object[] rawArray) { 159 assertEquals("Bad size", arraySet.size(), rawArray.length); 160 for (int i = 0; i < rawArray.length; ++i) { 161 assertEquals("ArraySet<E> and raw array unequal at index " + i, 162 arraySet.valueAt(i), rawArray[i]); 163 } 164 } 165 validateArraySet(ArraySet<E> array)166 private static <E> void validateArraySet(ArraySet<E> array) { 167 int index = 0; 168 Iterator<E> iter = array.iterator(); 169 while (iter.hasNext()) { 170 E value = iter.next(); 171 E realValue = array.valueAt(index); 172 if (!compare(realValue, value)) { 173 fail("Bad array set entry: expected " + realValue 174 + ", got " + value + " at index " + index); 175 } 176 index++; 177 } 178 179 assertEquals("Length of iteration was unequal to size()", array.size(), index); 180 } 181 dump(HashSet<E> set, ArraySet<E> array)182 private static <E> void dump(HashSet<E> set, ArraySet<E> array) { 183 Log.e(TAG, "HashSet of " + set.size() + " entries:"); 184 for (E entry : set) { 185 Log.e(TAG, " " + entry); 186 } 187 Log.e(TAG, "ArraySet of " + array.size() + " entries:"); 188 for (int i = 0; i < array.size(); i++) { 189 Log.e(TAG, " " + array.valueAt(i)); 190 } 191 } 192 dump(ArraySet set1, ArraySet set2)193 private static void dump(ArraySet set1, ArraySet set2) { 194 Log.e(TAG, "ArraySet of " + set1.size() + " entries:"); 195 for (int i = 0; i < set1.size(); i++) { 196 Log.e(TAG, " " + set1.valueAt(i)); 197 } 198 Log.e(TAG, "ArraySet of " + set2.size() + " entries:"); 199 for (int i = 0; i < set2.size(); i++) { 200 Log.e(TAG, " " + set2.valueAt(i)); 201 } 202 } 203 testTest()204 public void testTest() { 205 assertEquals("OPS and KEYS must be equal length", OPS.length, KEYS.length); 206 } 207 testBasicArraySet()208 public void testBasicArraySet() { 209 HashSet<ControlledHash> hashSet = new HashSet<ControlledHash>(); 210 ArraySet<ControlledHash> arraySet = new ArraySet<ControlledHash>(); 211 212 for (int i = 0; i < OPS.length; i++) { 213 ControlledHash key = KEYS[i] < 0 ? null : new ControlledHash(KEYS[i]); 214 String strKey = KEYS[i] < 0 ? null : Integer.toString(KEYS[i]); 215 switch (OPS[i]) { 216 case OP_ADD: 217 if (DEBUG) Log.i(TAG, "Adding key: " + key); 218 boolean hashAdded = hashSet.add(key); 219 boolean arrayAdded = arraySet.add(key); 220 assertEquals("Adding key " + key + " was not symmetric in HashSet and " 221 + "ArraySet", hashAdded, arrayAdded); 222 break; 223 case OP_REM: 224 if (DEBUG) Log.i(TAG, "Removing key: " + key); 225 boolean hashRemoved = hashSet.remove(key); 226 boolean arrayRemoved = arraySet.remove(key); 227 assertEquals("Removing key " + key + " was not symmetric in HashSet and " 228 + "ArraySet", hashRemoved, arrayRemoved); 229 break; 230 default: 231 fail("Bad operation " + OPS[i] + " @ " + i); 232 return; 233 } 234 if (DEBUG) dump(hashSet, arraySet); 235 236 try { 237 validateArraySet(arraySet); 238 } catch (Throwable e) { 239 Log.e(TAG, e.getMessage()); 240 dump(hashSet, arraySet); 241 throw e; 242 } 243 244 try { 245 compareSets(hashSet, arraySet); 246 } catch (Throwable e) { 247 Log.e(TAG, e.getMessage()); 248 dump(hashSet, arraySet); 249 throw e; 250 } 251 } 252 253 // Check to see if HashSet.iterator().remove() works as expected. 254 arraySet.add(new ControlledHash(50000)); 255 ControlledHash lookup = new ControlledHash(50000); 256 Iterator<ControlledHash> it = arraySet.iterator(); 257 while (it.hasNext()) { 258 if (it.next().equals(lookup)) { 259 it.remove(); 260 } 261 } 262 if (arraySet.contains(lookup)) { 263 String msg = "Bad ArraySet iterator: didn't remove test key"; 264 Log.e(TAG, msg); 265 dump(hashSet, arraySet); 266 fail(msg); 267 } 268 269 Log.e(TAG, "Test successful; printing final map."); 270 dump(hashSet, arraySet); 271 } 272 273 public void testCopyArraySet() { 274 // set copy constructor test 275 ArraySet newSet = new ArraySet<Integer>(); 276 for (int i = 0; i < 10; ++i) { 277 newSet.add(i); 278 } 279 280 ArraySet copySet = new ArraySet(newSet); 281 if (!compare(copySet, newSet)) { 282 String msg = "ArraySet copy constructor failure: expected " + 283 newSet + ", got " + copySet; 284 Log.e(TAG, msg); 285 dump(newSet, copySet); 286 fail(msg); 287 return; 288 } 289 } 290 291 public void testEqualsArrayMap() { 292 ArraySet<Integer> set1 = new ArraySet<Integer>(); 293 ArraySet<Integer> set2 = new ArraySet<Integer>(); 294 HashSet<Integer> set3 = new HashSet<Integer>(); 295 if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { 296 fail("ArraySet equals failure for empty sets " + set1 + ", " + 297 set2 + ", " + set3); 298 } 299 300 for (int i = 0; i < 10; ++i) { 301 set1.add(i); 302 set2.add(i); 303 set3.add(i); 304 } 305 if (!compare(set1, set2) || !compare(set1, set3) || !compare(set3, set2)) { 306 fail("ArraySet equals failure for populated sets " + set1 + ", " + 307 set2 + ", " + set3); 308 } 309 310 set1.remove(0); 311 if (compare(set1, set2) || compare(set1, set3) || compare(set3, set1)) { 312 fail("ArraySet equals failure for set size " + set1 + ", " + 313 set2 + ", " + set3); 314 } 315 } 316 317 public void testIsEmpty() { 318 ArraySet<Integer> set = new ArraySet<Integer>(); 319 assertEquals("New ArraySet should have size==0", 0, set.size()); 320 assertTrue("New ArraySet should be isEmptry", set.isEmpty()); 321 322 set.add(3); 323 assertEquals("ArraySet has incorrect size", 1, set.size()); 324 assertFalse("ArraySet should not be isEmptry", set.isEmpty()); 325 326 set.remove(3); 327 assertEquals("ArraySet should have size==0", 0, set.size()); 328 assertTrue("ArraySet should be isEmptry", set.isEmpty()); 329 } 330 331 public void testRemoveAt() { 332 ArraySet<Integer> set = new ArraySet<Integer>(); 333 334 for (int i = 0; i < 10; ++i) { 335 set.add(i * 10); 336 } 337 338 int indexToDelete = 6; 339 assertEquals(10, set.size()); 340 assertEquals(indexToDelete * 10, set.valueAt(indexToDelete).intValue()); 341 assertEquals(indexToDelete * 10, set.removeAt(indexToDelete).intValue()); 342 assertEquals(9, set.size()); 343 344 for (int i = 0; i < 9; ++i) { 345 int expectedValue = ((i >= indexToDelete) ? (i + 1) : i) * 10; 346 assertEquals(expectedValue, set.valueAt(i).intValue()); 347 } 348 349 for (int i = 9; i > 0; --i) { 350 set.removeAt(0); 351 assertEquals(i - 1, set.size()); 352 } 353 354 assertTrue(set.isEmpty()); 355 356 try { 357 set.removeAt(0); 358 fail("Expected ArrayIndexOutOfBoundsException"); 359 } catch (ArrayIndexOutOfBoundsException expected) { 360 // expected 361 } 362 } 363 364 public void testIndexOf() { 365 ArraySet<Integer> set = new ArraySet<Integer>(); 366 367 for (int i = 0; i < 10; ++i) { 368 set.add(i * 10); 369 } 370 371 for (int i = 0; i < 10; ++i) { 372 assertEquals("indexOf(" + (i * 10) + ")", i, set.indexOf(i * 10)); 373 } 374 } 375 376 public void testAddAll() { 377 ArraySet<Integer> arraySet = new ArraySet<Integer>(); 378 ArraySet<Integer> testArraySet = new ArraySet<Integer>(); 379 ArrayList<Integer> testArrayList = new ArrayList<Integer>(); 380 381 for (int i = 0; i < 10; ++i) { 382 testArraySet.add(i * 10); 383 testArrayList.add(i * 10); 384 } 385 386 assertTrue(arraySet.isEmpty()); 387 388 // addAll(ArraySet) has no return value. 389 arraySet.addAll(testArraySet); 390 assertTrue("ArraySet.addAll(ArraySet) failed", arraySet.containsAll(testArraySet)); 391 392 arraySet.clear(); 393 assertTrue(arraySet.isEmpty()); 394 395 // addAll(Collection) returns true if any items were added. 396 assertTrue(arraySet.addAll(testArrayList)); 397 assertTrue("ArraySet.addAll(Container) failed", arraySet.containsAll(testArrayList)); 398 assertTrue("ArraySet.addAll(Container) failed", arraySet.containsAll(testArraySet)); 399 // Adding the same Collection should return false. 400 assertFalse(arraySet.addAll(testArrayList)); 401 assertTrue("ArraySet.addAll(Container) failed", arraySet.containsAll(testArrayList)); 402 } 403 404 public void testRemoveAll() { 405 ArraySet<Integer> arraySet = new ArraySet<Integer>(); 406 ArraySet<Integer> arraySetToRemove = new ArraySet<Integer>(); 407 ArrayList<Integer> arrayListToRemove = new ArrayList<Integer>(); 408 409 for (int i = 0; i < 10; ++i) { 410 arraySet.add(i * 10); 411 } 412 413 for (int i = 6; i < 15; ++i) { 414 arraySetToRemove.add(i * 10); 415 } 416 417 for (int i = 3; i > -3; --i) { 418 arrayListToRemove.add(i * 10); 419 } 420 421 assertEquals(10, arraySet.size()); 422 423 // Remove [6,14] (really [6,9]) via another ArraySet. 424 assertTrue(arraySet.removeAll(arraySetToRemove)); 425 assertEquals(6, arraySet.size()); 426 assertFalse(arraySet.removeAll(arraySetToRemove)); 427 assertEquals(6, arraySet.size()); 428 429 // Remove [-2,3] (really [0,3]) via an ArrayList (ie Collection). 430 assertTrue(arraySet.removeAll(arrayListToRemove)); 431 assertEquals(2, arraySet.size()); 432 assertFalse(arraySet.removeAll(arrayListToRemove)); 433 assertEquals(2, arraySet.size()); 434 435 // Remove the rest of the items. 436 ArraySet<Integer> copy = new ArraySet<Integer>(arraySet); 437 assertTrue(arraySet.removeAll(copy)); 438 assertEquals(0, arraySet.size()); 439 assertFalse(arraySet.removeAll(copy)); 440 assertEquals(0, arraySet.size()); 441 } 442 443 public void testRetainAll() { 444 ArraySet<Integer> arraySet = new ArraySet<Integer>(); 445 ArrayList<Integer> arrayListToRetain = new ArrayList<Integer>(); 446 447 for (int i = 0; i < 10; ++i) { 448 arraySet.add(i * 10); 449 } 450 451 arrayListToRetain.add(30); 452 arrayListToRetain.add(50); 453 arrayListToRetain.add(51); // bogus value 454 455 assertEquals(10, arraySet.size()); 456 457 assertTrue(arraySet.retainAll(arrayListToRetain)); 458 assertEquals(2, arraySet.size()); 459 460 assertTrue(arraySet.contains(30)); 461 assertTrue(arraySet.contains(50)); 462 assertFalse(arraySet.contains(51)); 463 464 // Nothing should change. 465 assertFalse(arraySet.retainAll(arrayListToRetain)); 466 assertEquals(2, arraySet.size()); 467 } 468 469 public void testToArray() { 470 ArraySet<Integer> arraySet = new ArraySet<Integer>(); 471 for (int i = 0; i < 10; ++i) { 472 arraySet.add(i * 10); 473 } 474 475 // Allocate a new array with the right type given a zero-length ephemeral array. 476 Integer[] copiedArray = arraySet.toArray(new Integer[0]); 477 compareArraySetAndRawArray(arraySet, copiedArray); 478 479 // Allocate a new array with the right type given an undersized array. 480 Integer[] undersizedArray = new Integer[5]; 481 copiedArray = arraySet.toArray(undersizedArray); 482 compareArraySetAndRawArray(arraySet, copiedArray); 483 assertNotSame(undersizedArray, copiedArray); 484 485 // Use the passed array that is large enough to hold the ArraySet. 486 Integer[] rightSizedArray = new Integer[10]; 487 copiedArray = arraySet.toArray(rightSizedArray); 488 compareArraySetAndRawArray(arraySet, copiedArray); 489 assertSame(rightSizedArray, copiedArray); 490 491 // Create a new Object[] array. 492 Object[] objectArray = arraySet.toArray(); 493 compareArraySetAndRawArray(arraySet, objectArray); 494 } 495 } 496