1 /* 2 * Written by Doug Lea with assistance from members of JCP JSR-166 3 * Expert Group and released to the public domain, as explained at 4 * http://creativecommons.org/publicdomain/zero/1.0/ 5 * Other contributors include Andrew Wright, Jeffrey Hayes, 6 * Pat Fisher, Mike Judd. 7 */ 8 9 package jsr166; 10 11 import junit.framework.*; 12 import java.util.ArrayList; 13 import java.util.Arrays; 14 import java.util.Collection; 15 import java.util.Collections; 16 import java.util.Iterator; 17 import java.util.LinkedList; 18 import java.util.List; 19 import java.util.ListIterator; 20 import java.util.NoSuchElementException; 21 import java.util.Vector; 22 import java.util.concurrent.CopyOnWriteArrayList; 23 24 public class CopyOnWriteArrayListTest extends JSR166TestCase { 25 26 static CopyOnWriteArrayList<Integer> populatedArray(int n) { 27 CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<Integer>(); 28 assertTrue(a.isEmpty()); 29 for (int i = 0; i < n; i++) 30 a.add(i); 31 assertFalse(a.isEmpty()); 32 assertEquals(n, a.size()); 33 return a; 34 } 35 36 static CopyOnWriteArrayList<Integer> populatedArray(Integer[] elements) { 37 CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<Integer>(); 38 assertTrue(a.isEmpty()); 39 for (int i = 0; i < elements.length; i++) 40 a.add(elements[i]); 41 assertFalse(a.isEmpty()); 42 assertEquals(elements.length, a.size()); 43 return a; 44 } 45 46 /** 47 * a new list is empty 48 */ 49 public void testConstructor() { 50 CopyOnWriteArrayList a = new CopyOnWriteArrayList(); 51 assertTrue(a.isEmpty()); 52 } 53 54 /** 55 * new list contains all elements of initializing array 56 */ 57 public void testConstructor2() { 58 Integer[] ints = new Integer[SIZE]; 59 for (int i = 0; i < SIZE-1; ++i) 60 ints[i] = new Integer(i); 61 CopyOnWriteArrayList a = new CopyOnWriteArrayList(ints); 62 for (int i = 0; i < SIZE; ++i) 63 assertEquals(ints[i], a.get(i)); 64 } 65 66 /** 67 * new list contains all elements of initializing collection 68 */ 69 public void testConstructor3() { 70 Integer[] ints = new Integer[SIZE]; 71 for (int i = 0; i < SIZE-1; ++i) 72 ints[i] = new Integer(i); 73 CopyOnWriteArrayList a = new CopyOnWriteArrayList(Arrays.asList(ints)); 74 for (int i = 0; i < SIZE; ++i) 75 assertEquals(ints[i], a.get(i)); 76 } 77 78 /** 79 * addAll adds each element from the given collection 80 */ 81 public void testAddAll() { 82 CopyOnWriteArrayList full = populatedArray(3); 83 Vector v = new Vector(); 84 v.add(three); 85 v.add(four); 86 v.add(five); 87 full.addAll(v); 88 assertEquals(6, full.size()); 89 } 90 91 /** 92 * addAllAbsent adds each element from the given collection that did not 93 * already exist in the List 94 */ 95 public void testAddAllAbsent() { 96 CopyOnWriteArrayList full = populatedArray(3); 97 Vector v = new Vector(); 98 v.add(three); 99 v.add(four); 100 v.add(one); // will not add this element 101 full.addAllAbsent(v); 102 assertEquals(5, full.size()); 103 } 104 105 /** 106 * addIfAbsent will not add the element if it already exists in the list 107 */ 108 public void testAddIfAbsent() { 109 CopyOnWriteArrayList full = populatedArray(SIZE); 110 full.addIfAbsent(one); 111 assertEquals(SIZE, full.size()); 112 } 113 114 /** 115 * addIfAbsent adds the element when it does not exist in the list 116 */ 117 public void testAddIfAbsent2() { 118 CopyOnWriteArrayList full = populatedArray(SIZE); 119 full.addIfAbsent(three); 120 assertTrue(full.contains(three)); 121 } 122 123 /** 124 * clear removes all elements from the list 125 */ 126 public void testClear() { 127 CopyOnWriteArrayList full = populatedArray(SIZE); 128 full.clear(); 129 assertEquals(0, full.size()); 130 } 131 132 /** 133 * Cloned list is equal 134 */ 135 public void testClone() { 136 CopyOnWriteArrayList l1 = populatedArray(SIZE); 137 CopyOnWriteArrayList l2 = (CopyOnWriteArrayList)(l1.clone()); 138 assertEquals(l1, l2); 139 l1.clear(); 140 assertFalse(l1.equals(l2)); 141 } 142 143 /** 144 * contains is true for added elements 145 */ 146 public void testContains() { 147 CopyOnWriteArrayList full = populatedArray(3); 148 assertTrue(full.contains(one)); 149 assertFalse(full.contains(five)); 150 } 151 152 /** 153 * adding at an index places it in the indicated index 154 */ 155 public void testAddIndex() { 156 CopyOnWriteArrayList full = populatedArray(3); 157 full.add(0, m1); 158 assertEquals(4, full.size()); 159 assertEquals(m1, full.get(0)); 160 assertEquals(zero, full.get(1)); 161 162 full.add(2, m2); 163 assertEquals(5, full.size()); 164 assertEquals(m2, full.get(2)); 165 assertEquals(two, full.get(4)); 166 } 167 168 /** 169 * lists with same elements are equal and have same hashCode 170 */ 171 public void testEquals() { 172 CopyOnWriteArrayList a = populatedArray(3); 173 CopyOnWriteArrayList b = populatedArray(3); 174 assertTrue(a.equals(b)); 175 assertTrue(b.equals(a)); 176 assertEquals(a.hashCode(), b.hashCode()); 177 a.add(m1); 178 assertFalse(a.equals(b)); 179 assertFalse(b.equals(a)); 180 b.add(m1); 181 assertTrue(a.equals(b)); 182 assertTrue(b.equals(a)); 183 assertEquals(a.hashCode(), b.hashCode()); 184 } 185 186 /** 187 * containsAll returns true for collection with subset of elements 188 */ 189 public void testContainsAll() { 190 CopyOnWriteArrayList full = populatedArray(3); 191 Vector v = new Vector(); 192 v.add(one); 193 v.add(two); 194 assertTrue(full.containsAll(v)); 195 v.add(six); 196 assertFalse(full.containsAll(v)); 197 } 198 199 /** 200 * get returns the value at the given index 201 */ 202 public void testGet() { 203 CopyOnWriteArrayList full = populatedArray(3); 204 assertEquals(0, full.get(0)); 205 } 206 207 /** 208 * indexOf gives the index for the given object 209 */ 210 public void testIndexOf() { 211 CopyOnWriteArrayList full = populatedArray(3); 212 assertEquals(1, full.indexOf(one)); 213 assertEquals(-1, full.indexOf("puppies")); 214 } 215 216 /** 217 * indexOf gives the index based on the given index 218 * at which to start searching 219 */ 220 public void testIndexOf2() { 221 CopyOnWriteArrayList full = populatedArray(3); 222 assertEquals(1, full.indexOf(one, 0)); 223 assertEquals(-1, full.indexOf(one, 2)); 224 } 225 226 /** 227 * isEmpty returns true when empty, else false 228 */ 229 public void testIsEmpty() { 230 CopyOnWriteArrayList empty = new CopyOnWriteArrayList(); 231 CopyOnWriteArrayList full = populatedArray(SIZE); 232 assertTrue(empty.isEmpty()); 233 assertFalse(full.isEmpty()); 234 } 235 236 /** 237 * iterator() returns an iterator containing the elements of the 238 * list in insertion order 239 */ 240 public void testIterator() { 241 Collection empty = new CopyOnWriteArrayList(); 242 assertFalse(empty.iterator().hasNext()); 243 try { 244 empty.iterator().next(); 245 shouldThrow(); 246 } catch (NoSuchElementException success) {} 247 248 Integer[] elements = new Integer[SIZE]; 249 for (int i = 0; i < SIZE; i++) 250 elements[i] = i; 251 Collections.shuffle(Arrays.asList(elements)); 252 Collection<Integer> full = populatedArray(elements); 253 254 Iterator it = full.iterator(); 255 for (int j = 0; j < SIZE; j++) { 256 assertTrue(it.hasNext()); 257 assertEquals(elements[j], it.next()); 258 } 259 assertFalse(it.hasNext()); 260 try { 261 it.next(); 262 shouldThrow(); 263 } catch (NoSuchElementException success) {} 264 } 265 266 /** 267 * iterator.remove throws UnsupportedOperationException 268 */ 269 public void testIteratorRemove() { 270 CopyOnWriteArrayList full = populatedArray(SIZE); 271 Iterator it = full.iterator(); 272 it.next(); 273 try { 274 it.remove(); 275 shouldThrow(); 276 } catch (UnsupportedOperationException success) {} 277 } 278 279 /** 280 * toString contains toString of elements 281 */ 282 public void testToString() { 283 assertEquals("[]", new CopyOnWriteArrayList().toString()); 284 CopyOnWriteArrayList full = populatedArray(3); 285 String s = full.toString(); 286 for (int i = 0; i < 3; ++i) 287 assertTrue(s.contains(String.valueOf(i))); 288 assertEquals(new ArrayList(full).toString(), 289 full.toString()); 290 } 291 292 /** 293 * lastIndexOf returns the index for the given object 294 */ 295 public void testLastIndexOf1() { 296 CopyOnWriteArrayList full = populatedArray(3); 297 full.add(one); 298 full.add(three); 299 assertEquals(3, full.lastIndexOf(one)); 300 assertEquals(-1, full.lastIndexOf(six)); 301 } 302 303 /** 304 * lastIndexOf returns the index from the given starting point 305 */ 306 public void testLastIndexOf2() { 307 CopyOnWriteArrayList full = populatedArray(3); 308 full.add(one); 309 full.add(three); 310 assertEquals(3, full.lastIndexOf(one, 4)); 311 assertEquals(-1, full.lastIndexOf(three, 3)); 312 } 313 314 /** 315 * listIterator traverses all elements 316 */ 317 public void testListIterator1() { 318 CopyOnWriteArrayList full = populatedArray(SIZE); 319 ListIterator i = full.listIterator(); 320 int j; 321 for (j = 0; i.hasNext(); j++) 322 assertEquals(j, i.next()); 323 assertEquals(SIZE, j); 324 } 325 326 /** 327 * listIterator only returns those elements after the given index 328 */ 329 public void testListIterator2() { 330 CopyOnWriteArrayList full = populatedArray(3); 331 ListIterator i = full.listIterator(1); 332 int j; 333 for (j = 0; i.hasNext(); j++) 334 assertEquals(j+1, i.next()); 335 assertEquals(2, j); 336 } 337 338 /** 339 * remove(int) removes and returns the object at the given index 340 */ 341 public void testRemove_int() { 342 int SIZE = 3; 343 for (int i = 0; i < SIZE; i++) { 344 CopyOnWriteArrayList full = populatedArray(SIZE); 345 assertEquals(i, full.remove(i)); 346 assertEquals(SIZE - 1, full.size()); 347 assertFalse(full.contains(new Integer(i))); 348 } 349 } 350 351 /** 352 * remove(Object) removes the object if found and returns true 353 */ 354 public void testRemove_Object() { 355 int SIZE = 3; 356 for (int i = 0; i < SIZE; i++) { 357 CopyOnWriteArrayList full = populatedArray(SIZE); 358 assertFalse(full.remove(new Integer(-42))); 359 assertTrue(full.remove(new Integer(i))); 360 assertEquals(SIZE - 1, full.size()); 361 assertFalse(full.contains(new Integer(i))); 362 } 363 CopyOnWriteArrayList x = new CopyOnWriteArrayList(Arrays.asList(4, 5, 6)); 364 assertTrue(x.remove(new Integer(6))); 365 assertEquals(x, Arrays.asList(4, 5)); 366 assertTrue(x.remove(new Integer(4))); 367 assertEquals(x, Arrays.asList(5)); 368 assertTrue(x.remove(new Integer(5))); 369 assertEquals(x, Arrays.asList()); 370 assertFalse(x.remove(new Integer(5))); 371 } 372 373 /** 374 * removeAll removes all elements from the given collection 375 */ 376 public void testRemoveAll() { 377 CopyOnWriteArrayList full = populatedArray(3); 378 Vector v = new Vector(); 379 v.add(one); 380 v.add(two); 381 full.removeAll(v); 382 assertEquals(1, full.size()); 383 } 384 385 /** 386 * set changes the element at the given index 387 */ 388 public void testSet() { 389 CopyOnWriteArrayList full = populatedArray(3); 390 assertEquals(2, full.set(2, four)); 391 assertEquals(4, full.get(2)); 392 } 393 394 /** 395 * size returns the number of elements 396 */ 397 public void testSize() { 398 CopyOnWriteArrayList empty = new CopyOnWriteArrayList(); 399 CopyOnWriteArrayList full = populatedArray(SIZE); 400 assertEquals(SIZE, full.size()); 401 assertEquals(0, empty.size()); 402 } 403 404 /** 405 * toArray() returns an Object array containing all elements from 406 * the list in insertion order 407 */ 408 public void testToArray() { 409 Object[] a = new CopyOnWriteArrayList().toArray(); 410 assertTrue(Arrays.equals(new Object[0], a)); 411 assertSame(Object[].class, a.getClass()); 412 413 Integer[] elements = new Integer[SIZE]; 414 for (int i = 0; i < SIZE; i++) 415 elements[i] = i; 416 Collections.shuffle(Arrays.asList(elements)); 417 Collection<Integer> full = populatedArray(elements); 418 419 assertTrue(Arrays.equals(elements, full.toArray())); 420 assertSame(Object[].class, full.toArray().getClass()); 421 } 422 423 /** 424 * toArray(Integer array) returns an Integer array containing all 425 * elements from the list in insertion order 426 */ 427 public void testToArray2() { 428 Collection empty = new CopyOnWriteArrayList(); 429 Integer[] a; 430 431 a = new Integer[0]; 432 assertSame(a, empty.toArray(a)); 433 434 a = new Integer[SIZE/2]; 435 Arrays.fill(a, 42); 436 assertSame(a, empty.toArray(a)); 437 assertNull(a[0]); 438 for (int i = 1; i < a.length; i++) 439 assertEquals(42, (int) a[i]); 440 441 Integer[] elements = new Integer[SIZE]; 442 for (int i = 0; i < SIZE; i++) 443 elements[i] = i; 444 Collections.shuffle(Arrays.asList(elements)); 445 Collection<Integer> full = populatedArray(elements); 446 447 Arrays.fill(a, 42); 448 assertTrue(Arrays.equals(elements, full.toArray(a))); 449 for (int i = 0; i < a.length; i++) 450 assertEquals(42, (int) a[i]); 451 assertSame(Integer[].class, full.toArray(a).getClass()); 452 453 a = new Integer[SIZE]; 454 Arrays.fill(a, 42); 455 assertSame(a, full.toArray(a)); 456 assertTrue(Arrays.equals(elements, a)); 457 458 a = new Integer[2*SIZE]; 459 Arrays.fill(a, 42); 460 assertSame(a, full.toArray(a)); 461 assertTrue(Arrays.equals(elements, Arrays.copyOf(a, SIZE))); 462 assertNull(a[SIZE]); 463 for (int i = SIZE + 1; i < a.length; i++) 464 assertEquals(42, (int) a[i]); 465 } 466 467 /** 468 * sublists contains elements at indexes offset from their base 469 */ 470 public void testSubList() { 471 CopyOnWriteArrayList a = populatedArray(10); 472 assertTrue(a.subList(1,1).isEmpty()); 473 for (int j = 0; j < 9; ++j) { 474 for (int i = j ; i < 10; ++i) { 475 List b = a.subList(j,i); 476 for (int k = j; k < i; ++k) { 477 assertEquals(new Integer(k), b.get(k-j)); 478 } 479 } 480 } 481 482 List s = a.subList(2, 5); 483 assertEquals(3, s.size()); 484 s.set(2, m1); 485 assertEquals(a.get(4), m1); 486 s.clear(); 487 assertEquals(7, a.size()); 488 } 489 490 // Exception tests 491 492 /** 493 * toArray throws an ArrayStoreException when the given array 494 * can not store the objects inside the list 495 */ 496 public void testToArray_ArrayStoreException() { 497 try { 498 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 499 c.add("zfasdfsdf"); 500 c.add("asdadasd"); 501 c.toArray(new Long[5]); 502 shouldThrow(); 503 } catch (ArrayStoreException success) {} 504 } 505 506 /** 507 * get throws an IndexOutOfBoundsException on a negative index 508 */ 509 public void testGet1_IndexOutOfBoundsException() { 510 try { 511 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 512 c.get(-1); 513 shouldThrow(); 514 } catch (IndexOutOfBoundsException success) {} 515 } 516 517 /** 518 * get throws an IndexOutOfBoundsException on a too high index 519 */ 520 public void testGet2_IndexOutOfBoundsException() { 521 try { 522 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 523 c.add("asdasd"); 524 c.add("asdad"); 525 c.get(100); 526 shouldThrow(); 527 } catch (IndexOutOfBoundsException success) {} 528 } 529 530 /** 531 * set throws an IndexOutOfBoundsException on a negative index 532 */ 533 public void testSet1_IndexOutOfBoundsException() { 534 try { 535 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 536 c.set(-1,"qwerty"); 537 shouldThrow(); 538 } catch (IndexOutOfBoundsException success) {} 539 } 540 541 /** 542 * set throws an IndexOutOfBoundsException on a too high index 543 */ 544 public void testSet2() { 545 try { 546 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 547 c.add("asdasd"); 548 c.add("asdad"); 549 c.set(100, "qwerty"); 550 shouldThrow(); 551 } catch (IndexOutOfBoundsException success) {} 552 } 553 554 /** 555 * add throws an IndexOutOfBoundsException on a negative index 556 */ 557 public void testAdd1_IndexOutOfBoundsException() { 558 try { 559 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 560 c.add(-1,"qwerty"); 561 shouldThrow(); 562 } catch (IndexOutOfBoundsException success) {} 563 } 564 565 /** 566 * add throws an IndexOutOfBoundsException on a too high index 567 */ 568 public void testAdd2_IndexOutOfBoundsException() { 569 try { 570 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 571 c.add("asdasd"); 572 c.add("asdasdasd"); 573 c.add(100, "qwerty"); 574 shouldThrow(); 575 } catch (IndexOutOfBoundsException success) {} 576 } 577 578 /** 579 * remove throws an IndexOutOfBoundsException on a negative index 580 */ 581 public void testRemove1_IndexOutOfBounds() { 582 try { 583 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 584 c.remove(-1); 585 shouldThrow(); 586 } catch (IndexOutOfBoundsException success) {} 587 } 588 589 /** 590 * remove throws an IndexOutOfBoundsException on a too high index 591 */ 592 public void testRemove2_IndexOutOfBounds() { 593 try { 594 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 595 c.add("asdasd"); 596 c.add("adasdasd"); 597 c.remove(100); 598 shouldThrow(); 599 } catch (IndexOutOfBoundsException success) {} 600 } 601 602 /** 603 * addAll throws an IndexOutOfBoundsException on a negative index 604 */ 605 public void testAddAll1_IndexOutOfBoundsException() { 606 try { 607 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 608 c.addAll(-1,new LinkedList()); 609 shouldThrow(); 610 } catch (IndexOutOfBoundsException success) {} 611 } 612 613 /** 614 * addAll throws an IndexOutOfBoundsException on a too high index 615 */ 616 public void testAddAll2_IndexOutOfBoundsException() { 617 try { 618 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 619 c.add("asdasd"); 620 c.add("asdasdasd"); 621 c.addAll(100, new LinkedList()); 622 shouldThrow(); 623 } catch (IndexOutOfBoundsException success) {} 624 } 625 626 /** 627 * listIterator throws an IndexOutOfBoundsException on a negative index 628 */ 629 public void testListIterator1_IndexOutOfBoundsException() { 630 try { 631 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 632 c.listIterator(-1); 633 shouldThrow(); 634 } catch (IndexOutOfBoundsException success) {} 635 } 636 637 /** 638 * listIterator throws an IndexOutOfBoundsException on a too high index 639 */ 640 public void testListIterator2_IndexOutOfBoundsException() { 641 try { 642 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 643 c.add("adasd"); 644 c.add("asdasdas"); 645 c.listIterator(100); 646 shouldThrow(); 647 } catch (IndexOutOfBoundsException success) {} 648 } 649 650 /** 651 * subList throws an IndexOutOfBoundsException on a negative index 652 */ 653 public void testSubList1_IndexOutOfBoundsException() { 654 try { 655 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 656 c.subList(-1,100); 657 shouldThrow(); 658 } catch (IndexOutOfBoundsException success) {} 659 } 660 661 /** 662 * subList throws an IndexOutOfBoundsException on a too high index 663 */ 664 public void testSubList2_IndexOutOfBoundsException() { 665 try { 666 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 667 c.add("asdasd"); 668 c.subList(1,100); 669 shouldThrow(); 670 } catch (IndexOutOfBoundsException success) {} 671 } 672 673 /** 674 * subList throws IndexOutOfBoundsException when the second index 675 * is lower then the first 676 */ 677 public void testSubList3_IndexOutOfBoundsException() { 678 try { 679 CopyOnWriteArrayList c = new CopyOnWriteArrayList(); 680 c.subList(3,1); 681 shouldThrow(); 682 } catch (IndexOutOfBoundsException success) {} 683 } 684 685 /** 686 * a deserialized serialized list is equal 687 */ 688 public void testSerialization() throws Exception { 689 List x = populatedArray(SIZE); 690 List y = serialClone(x); 691 692 assertNotSame(x, y); 693 assertEquals(x.size(), y.size()); 694 assertEquals(x.toString(), y.toString()); 695 assertTrue(Arrays.equals(x.toArray(), y.toArray())); 696 assertEquals(x, y); 697 assertEquals(y, x); 698 while (!x.isEmpty()) { 699 assertFalse(y.isEmpty()); 700 assertEquals(x.remove(0), y.remove(0)); 701 } 702 assertTrue(y.isEmpty()); 703 } 704 705 } 706