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