1/* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. 7 * 8 * This code is distributed in the hope that it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 11 * version 2 for more details (a copy is included in the LICENSE file that 12 * accompanied this code). 13 * 14 * You should have received a copy of the GNU General Public License version 15 * 2 along with this work; if not, write to the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 17 * 18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 19 * or visit www.oracle.com if you need additional information or have any 20 * questions. 21 */ 22 23/* 24 * This file is available under and governed by the GNU General Public 25 * License version 2 only, as published by the Free Software Foundation. 26 * However, the following notice accompanied the original version of this 27 * file: 28 * 29 * Written by Doug Lea with assistance from members of JCP JSR-166 30 * Expert Group and released to the public domain, as explained at 31 * http://creativecommons.org/publicdomain/zero/1.0/ 32 * Other contributors include Andrew Wright, Jeffrey Hayes, 33 * Pat Fisher, Mike Judd. 34 */ 35 36import java.util.Arrays; 37import java.util.Collection; 38import java.util.Deque; 39import java.util.Iterator; 40import java.util.NoSuchElementException; 41import java.util.Queue; 42import java.util.Random; 43import java.util.concurrent.ConcurrentLinkedDeque; 44 45import junit.framework.Test; 46import junit.framework.TestSuite; 47 48public class ConcurrentLinkedDequeTest extends JSR166TestCase { 49 50 public static void main(String[] args) { 51 main(suite(), args); 52 } 53 54 public static Test suite() { 55 class Implementation implements CollectionImplementation { 56 public Class<?> klazz() { return ConcurrentLinkedDeque.class; } 57 public Collection emptyCollection() { return new ConcurrentLinkedDeque(); } 58 public Object makeElement(int i) { return i; } 59 public boolean isConcurrent() { return true; } 60 public boolean permitsNulls() { return false; } 61 } 62 return newTestSuite(ConcurrentLinkedDequeTest.class, 63 CollectionTest.testSuite(new Implementation())); 64 } 65 66 /** 67 * Returns a new deque of given size containing consecutive 68 * Integers 0 ... n - 1. 69 */ 70 private ConcurrentLinkedDeque<Integer> populatedDeque(int n) { 71 ConcurrentLinkedDeque<Integer> q = new ConcurrentLinkedDeque<>(); 72 assertTrue(q.isEmpty()); 73 for (int i = 0; i < n; ++i) 74 assertTrue(q.offer(new Integer(i))); 75 assertFalse(q.isEmpty()); 76 assertEquals(n, q.size()); 77 assertEquals((Integer) 0, q.peekFirst()); 78 assertEquals((Integer) (n - 1), q.peekLast()); 79 return q; 80 } 81 82 /** 83 * new deque is empty 84 */ 85 public void testConstructor1() { 86 assertTrue(new ConcurrentLinkedDeque().isEmpty()); 87 assertEquals(0, new ConcurrentLinkedDeque().size()); 88 } 89 90 /** 91 * Initializing from null Collection throws NPE 92 */ 93 public void testConstructor3() { 94 try { 95 new ConcurrentLinkedDeque((Collection)null); 96 shouldThrow(); 97 } catch (NullPointerException success) {} 98 } 99 100 /** 101 * Initializing from Collection of null elements throws NPE 102 */ 103 public void testConstructor4() { 104 try { 105 new ConcurrentLinkedDeque(Arrays.asList(new Integer[SIZE])); 106 shouldThrow(); 107 } catch (NullPointerException success) {} 108 } 109 110 /** 111 * Initializing from Collection with some null elements throws NPE 112 */ 113 public void testConstructor5() { 114 Integer[] ints = new Integer[SIZE]; 115 for (int i = 0; i < SIZE - 1; ++i) 116 ints[i] = new Integer(i); 117 try { 118 new ConcurrentLinkedDeque(Arrays.asList(ints)); 119 shouldThrow(); 120 } catch (NullPointerException success) {} 121 } 122 123 /** 124 * Deque contains all elements of collection used to initialize 125 */ 126 public void testConstructor6() { 127 Integer[] ints = new Integer[SIZE]; 128 for (int i = 0; i < SIZE; ++i) 129 ints[i] = new Integer(i); 130 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(Arrays.asList(ints)); 131 for (int i = 0; i < SIZE; ++i) 132 assertEquals(ints[i], q.poll()); 133 } 134 135 /** 136 * isEmpty is true before add, false after 137 */ 138 public void testEmpty() { 139 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 140 assertTrue(q.isEmpty()); 141 q.add(one); 142 assertFalse(q.isEmpty()); 143 q.add(two); 144 q.remove(); 145 q.remove(); 146 assertTrue(q.isEmpty()); 147 } 148 149 /** 150 * size() changes when elements added and removed 151 */ 152 public void testSize() { 153 ConcurrentLinkedDeque q = populatedDeque(SIZE); 154 for (int i = 0; i < SIZE; ++i) { 155 assertEquals(SIZE - i, q.size()); 156 q.remove(); 157 } 158 for (int i = 0; i < SIZE; ++i) { 159 assertEquals(i, q.size()); 160 q.add(new Integer(i)); 161 } 162 } 163 164 /** 165 * push(null) throws NPE 166 */ 167 public void testPushNull() { 168 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 169 try { 170 q.push(null); 171 shouldThrow(); 172 } catch (NullPointerException success) {} 173 } 174 175 /** 176 * peekFirst() returns element inserted with push 177 */ 178 public void testPush() { 179 ConcurrentLinkedDeque q = populatedDeque(3); 180 q.pollLast(); 181 q.push(four); 182 assertSame(four, q.peekFirst()); 183 } 184 185 /** 186 * pop() removes first element, or throws NSEE if empty 187 */ 188 public void testPop() { 189 ConcurrentLinkedDeque q = populatedDeque(SIZE); 190 for (int i = 0; i < SIZE; ++i) { 191 assertEquals(i, q.pop()); 192 } 193 try { 194 q.pop(); 195 shouldThrow(); 196 } catch (NoSuchElementException success) {} 197 } 198 199 /** 200 * offer(null) throws NPE 201 */ 202 public void testOfferNull() { 203 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 204 try { 205 q.offer(null); 206 shouldThrow(); 207 } catch (NullPointerException success) {} 208 } 209 210 /** 211 * offerFirst(null) throws NPE 212 */ 213 public void testOfferFirstNull() { 214 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 215 try { 216 q.offerFirst(null); 217 shouldThrow(); 218 } catch (NullPointerException success) {} 219 } 220 221 /** 222 * offerLast(null) throws NPE 223 */ 224 public void testOfferLastNull() { 225 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 226 try { 227 q.offerLast(null); 228 shouldThrow(); 229 } catch (NullPointerException success) {} 230 } 231 232 /** 233 * offer(x) succeeds 234 */ 235 public void testOffer() { 236 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 237 assertTrue(q.offer(zero)); 238 assertTrue(q.offer(one)); 239 assertSame(zero, q.peekFirst()); 240 assertSame(one, q.peekLast()); 241 } 242 243 /** 244 * offerFirst(x) succeeds 245 */ 246 public void testOfferFirst() { 247 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 248 assertTrue(q.offerFirst(zero)); 249 assertTrue(q.offerFirst(one)); 250 assertSame(one, q.peekFirst()); 251 assertSame(zero, q.peekLast()); 252 } 253 254 /** 255 * offerLast(x) succeeds 256 */ 257 public void testOfferLast() { 258 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 259 assertTrue(q.offerLast(zero)); 260 assertTrue(q.offerLast(one)); 261 assertSame(zero, q.peekFirst()); 262 assertSame(one, q.peekLast()); 263 } 264 265 /** 266 * add(null) throws NPE 267 */ 268 public void testAddNull() { 269 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 270 try { 271 q.add(null); 272 shouldThrow(); 273 } catch (NullPointerException success) {} 274 } 275 276 /** 277 * addFirst(null) throws NPE 278 */ 279 public void testAddFirstNull() { 280 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 281 try { 282 q.addFirst(null); 283 shouldThrow(); 284 } catch (NullPointerException success) {} 285 } 286 287 /** 288 * addLast(null) throws NPE 289 */ 290 public void testAddLastNull() { 291 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 292 try { 293 q.addLast(null); 294 shouldThrow(); 295 } catch (NullPointerException success) {} 296 } 297 298 /** 299 * add(x) succeeds 300 */ 301 public void testAdd() { 302 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 303 assertTrue(q.add(zero)); 304 assertTrue(q.add(one)); 305 assertSame(zero, q.peekFirst()); 306 assertSame(one, q.peekLast()); 307 } 308 309 /** 310 * addFirst(x) succeeds 311 */ 312 public void testAddFirst() { 313 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 314 q.addFirst(zero); 315 q.addFirst(one); 316 assertSame(one, q.peekFirst()); 317 assertSame(zero, q.peekLast()); 318 } 319 320 /** 321 * addLast(x) succeeds 322 */ 323 public void testAddLast() { 324 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 325 q.addLast(zero); 326 q.addLast(one); 327 assertSame(zero, q.peekFirst()); 328 assertSame(one, q.peekLast()); 329 } 330 331 /** 332 * addAll(null) throws NPE 333 */ 334 public void testAddAll1() { 335 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 336 try { 337 q.addAll(null); 338 shouldThrow(); 339 } catch (NullPointerException success) {} 340 } 341 342 /** 343 * addAll(this) throws IAE 344 */ 345 public void testAddAllSelf() { 346 ConcurrentLinkedDeque q = populatedDeque(SIZE); 347 try { 348 q.addAll(q); 349 shouldThrow(); 350 } catch (IllegalArgumentException success) {} 351 } 352 353 /** 354 * addAll of a collection with null elements throws NPE 355 */ 356 public void testAddAll2() { 357 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 358 try { 359 q.addAll(Arrays.asList(new Integer[SIZE])); 360 shouldThrow(); 361 } catch (NullPointerException success) {} 362 } 363 364 /** 365 * addAll of a collection with any null elements throws NPE after 366 * possibly adding some elements 367 */ 368 public void testAddAll3() { 369 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 370 Integer[] ints = new Integer[SIZE]; 371 for (int i = 0; i < SIZE - 1; ++i) 372 ints[i] = new Integer(i); 373 try { 374 q.addAll(Arrays.asList(ints)); 375 shouldThrow(); 376 } catch (NullPointerException success) {} 377 } 378 379 /** 380 * Deque contains all elements, in traversal order, of successful addAll 381 */ 382 public void testAddAll5() { 383 Integer[] empty = new Integer[0]; 384 Integer[] ints = new Integer[SIZE]; 385 for (int i = 0; i < SIZE; ++i) 386 ints[i] = new Integer(i); 387 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 388 assertFalse(q.addAll(Arrays.asList(empty))); 389 assertTrue(q.addAll(Arrays.asList(ints))); 390 for (int i = 0; i < SIZE; ++i) 391 assertEquals(ints[i], q.poll()); 392 } 393 394 /** 395 * pollFirst() succeeds unless empty 396 */ 397 public void testPollFirst() { 398 ConcurrentLinkedDeque q = populatedDeque(SIZE); 399 for (int i = 0; i < SIZE; ++i) { 400 assertEquals(i, q.pollFirst()); 401 } 402 assertNull(q.pollFirst()); 403 } 404 405 /** 406 * pollLast() succeeds unless empty 407 */ 408 public void testPollLast() { 409 ConcurrentLinkedDeque q = populatedDeque(SIZE); 410 for (int i = SIZE - 1; i >= 0; --i) { 411 assertEquals(i, q.pollLast()); 412 } 413 assertNull(q.pollLast()); 414 } 415 416 /** 417 * poll() succeeds unless empty 418 */ 419 public void testPoll() { 420 ConcurrentLinkedDeque q = populatedDeque(SIZE); 421 for (int i = 0; i < SIZE; ++i) { 422 assertEquals(i, q.poll()); 423 } 424 assertNull(q.poll()); 425 } 426 427 /** 428 * peek() returns next element, or null if empty 429 */ 430 public void testPeek() { 431 ConcurrentLinkedDeque q = populatedDeque(SIZE); 432 for (int i = 0; i < SIZE; ++i) { 433 assertEquals(i, q.peek()); 434 assertEquals(i, q.poll()); 435 assertTrue(q.peek() == null || 436 !q.peek().equals(i)); 437 } 438 assertNull(q.peek()); 439 } 440 441 /** 442 * element() returns first element, or throws NSEE if empty 443 */ 444 public void testElement() { 445 ConcurrentLinkedDeque q = populatedDeque(SIZE); 446 for (int i = 0; i < SIZE; ++i) { 447 assertEquals(i, q.element()); 448 assertEquals(i, q.poll()); 449 } 450 try { 451 q.element(); 452 shouldThrow(); 453 } catch (NoSuchElementException success) {} 454 } 455 456 /** 457 * remove() removes next element, or throws NSEE if empty 458 */ 459 public void testRemove() { 460 ConcurrentLinkedDeque q = populatedDeque(SIZE); 461 for (int i = 0; i < SIZE; ++i) { 462 assertEquals(i, q.remove()); 463 } 464 try { 465 q.remove(); 466 shouldThrow(); 467 } catch (NoSuchElementException success) {} 468 } 469 470 /** 471 * remove(x) removes x and returns true if present 472 */ 473 public void testRemoveElement() { 474 ConcurrentLinkedDeque q = populatedDeque(SIZE); 475 for (int i = 1; i < SIZE; i += 2) { 476 assertTrue(q.contains(i)); 477 assertTrue(q.remove(i)); 478 assertFalse(q.contains(i)); 479 assertTrue(q.contains(i - 1)); 480 } 481 for (int i = 0; i < SIZE; i += 2) { 482 assertTrue(q.contains(i)); 483 assertTrue(q.remove(i)); 484 assertFalse(q.contains(i)); 485 assertFalse(q.remove(i + 1)); 486 assertFalse(q.contains(i + 1)); 487 } 488 assertTrue(q.isEmpty()); 489 } 490 491 /** 492 * peekFirst() returns next element, or null if empty 493 */ 494 public void testPeekFirst() { 495 ConcurrentLinkedDeque q = populatedDeque(SIZE); 496 for (int i = 0; i < SIZE; ++i) { 497 assertEquals(i, q.peekFirst()); 498 assertEquals(i, q.pollFirst()); 499 assertTrue(q.peekFirst() == null || 500 !q.peekFirst().equals(i)); 501 } 502 assertNull(q.peekFirst()); 503 } 504 505 /** 506 * peekLast() returns next element, or null if empty 507 */ 508 public void testPeekLast() { 509 ConcurrentLinkedDeque q = populatedDeque(SIZE); 510 for (int i = SIZE - 1; i >= 0; --i) { 511 assertEquals(i, q.peekLast()); 512 assertEquals(i, q.pollLast()); 513 assertTrue(q.peekLast() == null || 514 !q.peekLast().equals(i)); 515 } 516 assertNull(q.peekLast()); 517 } 518 519 /** 520 * getFirst() returns first element, or throws NSEE if empty 521 */ 522 public void testFirstElement() { 523 ConcurrentLinkedDeque q = populatedDeque(SIZE); 524 for (int i = 0; i < SIZE; ++i) { 525 assertEquals(i, q.getFirst()); 526 assertEquals(i, q.pollFirst()); 527 } 528 try { 529 q.getFirst(); 530 shouldThrow(); 531 } catch (NoSuchElementException success) {} 532 } 533 534 /** 535 * getLast() returns last element, or throws NSEE if empty 536 */ 537 public void testLastElement() { 538 ConcurrentLinkedDeque q = populatedDeque(SIZE); 539 for (int i = SIZE - 1; i >= 0; --i) { 540 assertEquals(i, q.getLast()); 541 assertEquals(i, q.pollLast()); 542 } 543 try { 544 q.getLast(); 545 shouldThrow(); 546 } catch (NoSuchElementException success) {} 547 assertNull(q.peekLast()); 548 } 549 550 /** 551 * removeFirst() removes first element, or throws NSEE if empty 552 */ 553 public void testRemoveFirst() { 554 ConcurrentLinkedDeque q = populatedDeque(SIZE); 555 for (int i = 0; i < SIZE; ++i) { 556 assertEquals(i, q.removeFirst()); 557 } 558 try { 559 q.removeFirst(); 560 shouldThrow(); 561 } catch (NoSuchElementException success) {} 562 assertNull(q.peekFirst()); 563 } 564 565 /** 566 * removeLast() removes last element, or throws NSEE if empty 567 */ 568 public void testRemoveLast() { 569 ConcurrentLinkedDeque q = populatedDeque(SIZE); 570 for (int i = SIZE - 1; i >= 0; --i) { 571 assertEquals(i, q.removeLast()); 572 } 573 try { 574 q.removeLast(); 575 shouldThrow(); 576 } catch (NoSuchElementException success) {} 577 assertNull(q.peekLast()); 578 } 579 580 /** 581 * removeFirstOccurrence(x) removes x and returns true if present 582 */ 583 public void testRemoveFirstOccurrence() { 584 ConcurrentLinkedDeque q = populatedDeque(SIZE); 585 for (int i = 1; i < SIZE; i += 2) { 586 assertTrue(q.removeFirstOccurrence(new Integer(i))); 587 } 588 for (int i = 0; i < SIZE; i += 2) { 589 assertTrue(q.removeFirstOccurrence(new Integer(i))); 590 assertFalse(q.removeFirstOccurrence(new Integer(i + 1))); 591 } 592 assertTrue(q.isEmpty()); 593 } 594 595 /** 596 * removeLastOccurrence(x) removes x and returns true if present 597 */ 598 public void testRemoveLastOccurrence() { 599 ConcurrentLinkedDeque q = populatedDeque(SIZE); 600 for (int i = 1; i < SIZE; i += 2) { 601 assertTrue(q.removeLastOccurrence(new Integer(i))); 602 } 603 for (int i = 0; i < SIZE; i += 2) { 604 assertTrue(q.removeLastOccurrence(new Integer(i))); 605 assertFalse(q.removeLastOccurrence(new Integer(i + 1))); 606 } 607 assertTrue(q.isEmpty()); 608 } 609 610 /** 611 * contains(x) reports true when elements added but not yet removed 612 */ 613 public void testContains() { 614 ConcurrentLinkedDeque q = populatedDeque(SIZE); 615 for (int i = 0; i < SIZE; ++i) { 616 assertTrue(q.contains(new Integer(i))); 617 q.poll(); 618 assertFalse(q.contains(new Integer(i))); 619 } 620 } 621 622 /** 623 * clear() removes all elements 624 */ 625 public void testClear() { 626 ConcurrentLinkedDeque q = populatedDeque(SIZE); 627 q.clear(); 628 assertTrue(q.isEmpty()); 629 assertEquals(0, q.size()); 630 q.add(one); 631 assertFalse(q.isEmpty()); 632 q.clear(); 633 assertTrue(q.isEmpty()); 634 } 635 636 /** 637 * containsAll(c) is true when c contains a subset of elements 638 */ 639 public void testContainsAll() { 640 ConcurrentLinkedDeque q = populatedDeque(SIZE); 641 ConcurrentLinkedDeque p = new ConcurrentLinkedDeque(); 642 for (int i = 0; i < SIZE; ++i) { 643 assertTrue(q.containsAll(p)); 644 assertFalse(p.containsAll(q)); 645 p.add(new Integer(i)); 646 } 647 assertTrue(p.containsAll(q)); 648 } 649 650 /** 651 * retainAll(c) retains only those elements of c and reports true if change 652 */ 653 public void testRetainAll() { 654 ConcurrentLinkedDeque q = populatedDeque(SIZE); 655 ConcurrentLinkedDeque p = populatedDeque(SIZE); 656 for (int i = 0; i < SIZE; ++i) { 657 boolean changed = q.retainAll(p); 658 if (i == 0) 659 assertFalse(changed); 660 else 661 assertTrue(changed); 662 663 assertTrue(q.containsAll(p)); 664 assertEquals(SIZE - i, q.size()); 665 p.remove(); 666 } 667 } 668 669 /** 670 * removeAll(c) removes only those elements of c and reports true if changed 671 */ 672 public void testRemoveAll() { 673 for (int i = 1; i < SIZE; ++i) { 674 ConcurrentLinkedDeque q = populatedDeque(SIZE); 675 ConcurrentLinkedDeque p = populatedDeque(i); 676 assertTrue(q.removeAll(p)); 677 assertEquals(SIZE - i, q.size()); 678 for (int j = 0; j < i; ++j) { 679 Integer x = (Integer)(p.remove()); 680 assertFalse(q.contains(x)); 681 } 682 } 683 } 684 685 /** 686 * toArray() contains all elements in FIFO order 687 */ 688 public void testToArray() { 689 ConcurrentLinkedDeque q = populatedDeque(SIZE); 690 Object[] o = q.toArray(); 691 for (int i = 0; i < o.length; i++) 692 assertSame(o[i], q.poll()); 693 } 694 695 /** 696 * toArray(a) contains all elements in FIFO order 697 */ 698 public void testToArray2() { 699 ConcurrentLinkedDeque<Integer> q = populatedDeque(SIZE); 700 Integer[] ints = new Integer[SIZE]; 701 Integer[] array = q.toArray(ints); 702 assertSame(ints, array); 703 for (int i = 0; i < ints.length; i++) 704 assertSame(ints[i], q.poll()); 705 } 706 707 /** 708 * toArray(null) throws NullPointerException 709 */ 710 public void testToArray_NullArg() { 711 ConcurrentLinkedDeque q = populatedDeque(SIZE); 712 try { 713 q.toArray(null); 714 shouldThrow(); 715 } catch (NullPointerException success) {} 716 } 717 718 /** 719 * toArray(incompatible array type) throws ArrayStoreException 720 */ 721 public void testToArray1_BadArg() { 722 ConcurrentLinkedDeque q = populatedDeque(SIZE); 723 try { 724 q.toArray(new String[10]); 725 shouldThrow(); 726 } catch (ArrayStoreException success) {} 727 } 728 729 /** 730 * Iterator iterates through all elements 731 */ 732 public void testIterator() { 733 ConcurrentLinkedDeque q = populatedDeque(SIZE); 734 Iterator it = q.iterator(); 735 int i; 736 for (i = 0; it.hasNext(); i++) 737 assertTrue(q.contains(it.next())); 738 assertEquals(i, SIZE); 739 assertIteratorExhausted(it); 740 } 741 742 /** 743 * iterator of empty collection has no elements 744 */ 745 public void testEmptyIterator() { 746 Deque c = new ConcurrentLinkedDeque(); 747 assertIteratorExhausted(c.iterator()); 748 assertIteratorExhausted(c.descendingIterator()); 749 } 750 751 /** 752 * Iterator ordering is FIFO 753 */ 754 public void testIteratorOrdering() { 755 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 756 q.add(one); 757 q.add(two); 758 q.add(three); 759 760 int k = 0; 761 for (Iterator it = q.iterator(); it.hasNext();) { 762 assertEquals(++k, it.next()); 763 } 764 765 assertEquals(3, k); 766 } 767 768 /** 769 * Modifications do not cause iterators to fail 770 */ 771 public void testWeaklyConsistentIteration() { 772 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 773 q.add(one); 774 q.add(two); 775 q.add(three); 776 777 for (Iterator it = q.iterator(); it.hasNext();) { 778 q.remove(); 779 it.next(); 780 } 781 782 assertEquals("deque should be empty again", 0, q.size()); 783 } 784 785 /** 786 * iterator.remove() removes current element 787 */ 788 public void testIteratorRemove() { 789 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 790 final Random rng = new Random(); 791 for (int iters = 0; iters < 100; ++iters) { 792 int max = rng.nextInt(5) + 2; 793 int split = rng.nextInt(max - 1) + 1; 794 for (int j = 1; j <= max; ++j) 795 q.add(new Integer(j)); 796 Iterator it = q.iterator(); 797 for (int j = 1; j <= split; ++j) 798 assertEquals(it.next(), new Integer(j)); 799 it.remove(); 800 assertEquals(it.next(), new Integer(split + 1)); 801 for (int j = 1; j <= split; ++j) 802 q.remove(new Integer(j)); 803 it = q.iterator(); 804 for (int j = split + 1; j <= max; ++j) { 805 assertEquals(it.next(), new Integer(j)); 806 it.remove(); 807 } 808 assertFalse(it.hasNext()); 809 assertTrue(q.isEmpty()); 810 } 811 } 812 813 /** 814 * Descending iterator iterates through all elements 815 */ 816 public void testDescendingIterator() { 817 ConcurrentLinkedDeque q = populatedDeque(SIZE); 818 int i = 0; 819 Iterator it = q.descendingIterator(); 820 while (it.hasNext()) { 821 assertTrue(q.contains(it.next())); 822 ++i; 823 } 824 assertEquals(i, SIZE); 825 assertFalse(it.hasNext()); 826 try { 827 it.next(); 828 shouldThrow(); 829 } catch (NoSuchElementException success) {} 830 } 831 832 /** 833 * Descending iterator ordering is reverse FIFO 834 */ 835 public void testDescendingIteratorOrdering() { 836 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 837 for (int iters = 0; iters < 100; ++iters) { 838 q.add(new Integer(3)); 839 q.add(new Integer(2)); 840 q.add(new Integer(1)); 841 int k = 0; 842 for (Iterator it = q.descendingIterator(); it.hasNext();) { 843 assertEquals(++k, it.next()); 844 } 845 846 assertEquals(3, k); 847 q.remove(); 848 q.remove(); 849 q.remove(); 850 } 851 } 852 853 /** 854 * descendingIterator.remove() removes current element 855 */ 856 public void testDescendingIteratorRemove() { 857 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 858 final Random rng = new Random(); 859 for (int iters = 0; iters < 100; ++iters) { 860 int max = rng.nextInt(5) + 2; 861 int split = rng.nextInt(max - 1) + 1; 862 for (int j = max; j >= 1; --j) 863 q.add(new Integer(j)); 864 Iterator it = q.descendingIterator(); 865 for (int j = 1; j <= split; ++j) 866 assertEquals(it.next(), new Integer(j)); 867 it.remove(); 868 assertEquals(it.next(), new Integer(split + 1)); 869 for (int j = 1; j <= split; ++j) 870 q.remove(new Integer(j)); 871 it = q.descendingIterator(); 872 for (int j = split + 1; j <= max; ++j) { 873 assertEquals(it.next(), new Integer(j)); 874 it.remove(); 875 } 876 assertFalse(it.hasNext()); 877 assertTrue(q.isEmpty()); 878 } 879 } 880 881 /** 882 * toString() contains toStrings of elements 883 */ 884 public void testToString() { 885 ConcurrentLinkedDeque q = populatedDeque(SIZE); 886 String s = q.toString(); 887 for (int i = 0; i < SIZE; ++i) { 888 assertTrue(s.contains(String.valueOf(i))); 889 } 890 } 891 892 /** 893 * A deserialized serialized deque has same elements in same order 894 */ 895 public void testSerialization() throws Exception { 896 Queue x = populatedDeque(SIZE); 897 Queue y = serialClone(x); 898 899 assertNotSame(x, y); 900 assertEquals(x.size(), y.size()); 901 assertEquals(x.toString(), y.toString()); 902 assertTrue(Arrays.equals(x.toArray(), y.toArray())); 903 while (!x.isEmpty()) { 904 assertFalse(y.isEmpty()); 905 assertEquals(x.remove(), y.remove()); 906 } 907 assertTrue(y.isEmpty()); 908 } 909 910 /** 911 * contains(null) always return false. 912 * remove(null) always throws NullPointerException. 913 */ 914 public void testNeverContainsNull() { 915 Deque<?>[] qs = { 916 new ConcurrentLinkedDeque<Object>(), 917 populatedDeque(2), 918 }; 919 920 for (Deque<?> q : qs) { 921 assertFalse(q.contains(null)); 922 try { 923 assertFalse(q.remove(null)); 924 shouldThrow(); 925 } catch (NullPointerException success) {} 926 try { 927 assertFalse(q.removeFirstOccurrence(null)); 928 shouldThrow(); 929 } catch (NullPointerException success) {} 930 try { 931 assertFalse(q.removeLastOccurrence(null)); 932 shouldThrow(); 933 } catch (NullPointerException success) {} 934 } 935 } 936} 937