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