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 36 import java.util.Arrays; 37 import java.util.Collection; 38 import java.util.Iterator; 39 import java.util.LinkedList; 40 import java.util.List; 41 import java.util.NoSuchElementException; 42 import java.util.concurrent.ThreadLocalRandom; 43 44 import junit.framework.Test; 45 46 public class LinkedListTest extends JSR166TestCase { 47 public static void main(String[] args) { 48 main(suite(), args); 49 } 50 51 public static Test suite() { 52 class Implementation implements CollectionImplementation { 53 public Class<?> klazz() { return LinkedList.class; } 54 public List emptyCollection() { return new LinkedList(); } 55 public Object makeElement(int i) { return i; } 56 public boolean isConcurrent() { return false; } 57 public boolean permitsNulls() { return true; } 58 } 59 class SubListImplementation extends Implementation { 60 public List emptyCollection() { 61 List list = super.emptyCollection(); 62 ThreadLocalRandom rnd = ThreadLocalRandom.current(); 63 if (rnd.nextBoolean()) 64 list.add(makeElement(rnd.nextInt())); 65 int i = rnd.nextInt(list.size() + 1); 66 return list.subList(i, i); 67 } 68 } 69 return newTestSuite( 70 LinkedListTest.class, 71 CollectionTest.testSuite(new Implementation()), 72 CollectionTest.testSuite(new SubListImplementation())); 73 } 74 75 /** 76 * Returns a new queue of given size containing consecutive 77 * Integers 0 ... n - 1. 78 */ 79 private static LinkedList<Integer> populatedQueue(int n) { 80 LinkedList<Integer> q = new LinkedList<>(); 81 assertTrue(q.isEmpty()); 82 for (int i = 0; i < n; ++i) 83 assertTrue(q.offer(new Integer(i))); 84 assertFalse(q.isEmpty()); 85 assertEquals(n, q.size()); 86 assertEquals((Integer) 0, q.peekFirst()); 87 assertEquals((Integer) (n - 1), q.peekLast()); 88 return q; 89 } 90 91 /** 92 * new queue is empty 93 */ 94 public void testConstructor1() { 95 assertEquals(0, new LinkedList().size()); 96 } 97 98 /** 99 * Initializing from null Collection throws NPE 100 */ 101 public void testConstructor3() { 102 try { 103 new LinkedList((Collection)null); 104 shouldThrow(); 105 } catch (NullPointerException success) {} 106 } 107 108 /** 109 * Queue contains all elements of collection used to initialize 110 */ 111 public void testConstructor6() { 112 Integer[] ints = new Integer[SIZE]; 113 for (int i = 0; i < SIZE; ++i) 114 ints[i] = i; 115 LinkedList q = new LinkedList(Arrays.asList(ints)); 116 for (int i = 0; i < SIZE; ++i) 117 assertEquals(ints[i], q.poll()); 118 } 119 120 /** 121 * isEmpty is true before add, false after 122 */ 123 public void testEmpty() { 124 LinkedList q = new LinkedList(); 125 assertTrue(q.isEmpty()); 126 q.add(new Integer(1)); 127 assertFalse(q.isEmpty()); 128 q.add(new Integer(2)); 129 q.remove(); 130 q.remove(); 131 assertTrue(q.isEmpty()); 132 } 133 134 /** 135 * size changes when elements added and removed 136 */ 137 public void testSize() { 138 LinkedList q = populatedQueue(SIZE); 139 for (int i = 0; i < SIZE; ++i) { 140 assertEquals(SIZE - i, q.size()); 141 q.remove(); 142 } 143 for (int i = 0; i < SIZE; ++i) { 144 assertEquals(i, q.size()); 145 q.add(new Integer(i)); 146 } 147 } 148 149 /** 150 * offer(null) succeeds 151 */ 152 public void testOfferNull() { 153 LinkedList q = new LinkedList(); 154 q.offer(null); 155 assertNull(q.get(0)); 156 assertTrue(q.contains(null)); 157 } 158 159 /** 160 * Offer succeeds 161 */ 162 public void testOffer() { 163 LinkedList q = new LinkedList(); 164 assertTrue(q.offer(new Integer(0))); 165 assertTrue(q.offer(new Integer(1))); 166 } 167 168 /** 169 * add succeeds 170 */ 171 public void testAdd() { 172 LinkedList q = new LinkedList(); 173 for (int i = 0; i < SIZE; ++i) { 174 assertEquals(i, q.size()); 175 assertTrue(q.add(new Integer(i))); 176 } 177 } 178 179 /** 180 * addAll(null) throws NPE 181 */ 182 public void testAddAll1() { 183 LinkedList q = new LinkedList(); 184 try { 185 q.addAll(null); 186 shouldThrow(); 187 } catch (NullPointerException success) {} 188 } 189 190 /** 191 * Queue contains all elements, in traversal order, of successful addAll 192 */ 193 public void testAddAll5() { 194 Integer[] empty = new Integer[0]; 195 Integer[] ints = new Integer[SIZE]; 196 for (int i = 0; i < SIZE; ++i) 197 ints[i] = i; 198 LinkedList q = new LinkedList(); 199 assertFalse(q.addAll(Arrays.asList(empty))); 200 assertTrue(q.addAll(Arrays.asList(ints))); 201 for (int i = 0; i < SIZE; ++i) 202 assertEquals(ints[i], q.poll()); 203 } 204 205 /** 206 * addAll with too large an index throws IOOBE 207 */ 208 public void testAddAll2_IndexOutOfBoundsException() { 209 LinkedList l = new LinkedList(); 210 l.add(new Object()); 211 LinkedList m = new LinkedList(); 212 m.add(new Object()); 213 try { 214 l.addAll(4,m); 215 shouldThrow(); 216 } catch (IndexOutOfBoundsException success) {} 217 } 218 219 /** 220 * addAll with negative index throws IOOBE 221 */ 222 public void testAddAll4_BadIndex() { 223 LinkedList l = new LinkedList(); 224 l.add(new Object()); 225 LinkedList m = new LinkedList(); 226 m.add(new Object()); 227 try { 228 l.addAll(-1,m); 229 shouldThrow(); 230 } catch (IndexOutOfBoundsException success) {} 231 } 232 233 /** 234 * poll succeeds unless empty 235 */ 236 public void testPoll() { 237 LinkedList q = populatedQueue(SIZE); 238 for (int i = 0; i < SIZE; ++i) { 239 assertEquals(i, q.poll()); 240 } 241 assertNull(q.poll()); 242 } 243 244 /** 245 * peek returns next element, or null if empty 246 */ 247 public void testPeek() { 248 LinkedList q = populatedQueue(SIZE); 249 for (int i = 0; i < SIZE; ++i) { 250 assertEquals(i, q.peek()); 251 assertEquals(i, q.poll()); 252 assertTrue(q.peek() == null || 253 !q.peek().equals(i)); 254 } 255 assertNull(q.peek()); 256 } 257 258 /** 259 * element returns next element, or throws NSEE if empty 260 */ 261 public void testElement() { 262 LinkedList q = populatedQueue(SIZE); 263 for (int i = 0; i < SIZE; ++i) { 264 assertEquals(i, q.element()); 265 assertEquals(i, q.poll()); 266 } 267 try { 268 q.element(); 269 shouldThrow(); 270 } catch (NoSuchElementException success) {} 271 } 272 273 /** 274 * remove removes next element, or throws NSEE if empty 275 */ 276 public void testRemove() { 277 LinkedList q = populatedQueue(SIZE); 278 for (int i = 0; i < SIZE; ++i) { 279 assertEquals(i, q.remove()); 280 } 281 try { 282 q.remove(); 283 shouldThrow(); 284 } catch (NoSuchElementException success) {} 285 } 286 287 /** 288 * remove(x) removes x and returns true if present 289 */ 290 public void testRemoveElement() { 291 LinkedList q = populatedQueue(SIZE); 292 for (int i = 1; i < SIZE; i += 2) { 293 assertTrue(q.contains(i)); 294 assertTrue(q.remove((Integer)i)); 295 assertFalse(q.contains(i)); 296 assertTrue(q.contains(i - 1)); 297 } 298 for (int i = 0; i < SIZE; i += 2) { 299 assertTrue(q.contains(i)); 300 assertTrue(q.remove((Integer)i)); 301 assertFalse(q.contains(i)); 302 assertFalse(q.remove((Integer)(i + 1))); 303 assertFalse(q.contains(i + 1)); 304 } 305 assertTrue(q.isEmpty()); 306 } 307 308 /** 309 * contains(x) reports true when elements added but not yet removed 310 */ 311 public void testContains() { 312 LinkedList q = populatedQueue(SIZE); 313 for (int i = 0; i < SIZE; ++i) { 314 assertTrue(q.contains(new Integer(i))); 315 q.poll(); 316 assertFalse(q.contains(new Integer(i))); 317 } 318 } 319 320 /** 321 * clear removes all elements 322 */ 323 public void testClear() { 324 LinkedList q = populatedQueue(SIZE); 325 q.clear(); 326 assertTrue(q.isEmpty()); 327 assertEquals(0, q.size()); 328 assertTrue(q.add(new Integer(1))); 329 assertFalse(q.isEmpty()); 330 q.clear(); 331 assertTrue(q.isEmpty()); 332 } 333 334 /** 335 * containsAll(c) is true when c contains a subset of elements 336 */ 337 public void testContainsAll() { 338 LinkedList q = populatedQueue(SIZE); 339 LinkedList p = new LinkedList(); 340 for (int i = 0; i < SIZE; ++i) { 341 assertTrue(q.containsAll(p)); 342 assertFalse(p.containsAll(q)); 343 assertTrue(p.add(new Integer(i))); 344 } 345 assertTrue(p.containsAll(q)); 346 } 347 348 /** 349 * retainAll(c) retains only those elements of c and reports true if changed 350 */ 351 public void testRetainAll() { 352 LinkedList q = populatedQueue(SIZE); 353 LinkedList p = populatedQueue(SIZE); 354 for (int i = 0; i < SIZE; ++i) { 355 boolean changed = q.retainAll(p); 356 if (i == 0) 357 assertFalse(changed); 358 else 359 assertTrue(changed); 360 361 assertTrue(q.containsAll(p)); 362 assertEquals(SIZE - i, q.size()); 363 p.remove(); 364 } 365 } 366 367 /** 368 * removeAll(c) removes only those elements of c and reports true if changed 369 */ 370 public void testRemoveAll() { 371 for (int i = 1; i < SIZE; ++i) { 372 LinkedList q = populatedQueue(SIZE); 373 LinkedList p = populatedQueue(i); 374 assertTrue(q.removeAll(p)); 375 assertEquals(SIZE - i, q.size()); 376 for (int j = 0; j < i; ++j) { 377 Integer x = (Integer)(p.remove()); 378 assertFalse(q.contains(x)); 379 } 380 } 381 } 382 383 /** 384 * toArray contains all elements in FIFO order 385 */ 386 public void testToArray() { 387 LinkedList q = populatedQueue(SIZE); 388 Object[] o = q.toArray(); 389 for (int i = 0; i < o.length; i++) 390 assertSame(o[i], q.poll()); 391 } 392 393 /** 394 * toArray(a) contains all elements in FIFO order 395 */ 396 public void testToArray2() { 397 LinkedList<Integer> q = populatedQueue(SIZE); 398 Integer[] ints = new Integer[SIZE]; 399 Integer[] array = q.toArray(ints); 400 assertSame(ints, array); 401 for (int i = 0; i < ints.length; i++) 402 assertSame(ints[i], q.poll()); 403 } 404 405 /** 406 * toArray(null) throws NullPointerException 407 */ 408 public void testToArray_NullArg() { 409 LinkedList l = new LinkedList(); 410 l.add(new Object()); 411 try { 412 l.toArray(null); 413 shouldThrow(); 414 } catch (NullPointerException success) {} 415 } 416 417 /** 418 * toArray(incompatible array type) throws ArrayStoreException 419 */ 420 public void testToArray1_BadArg() { 421 LinkedList l = new LinkedList(); 422 l.add(new Integer(5)); 423 try { 424 l.toArray(new String[10]); 425 shouldThrow(); 426 } catch (ArrayStoreException success) {} 427 } 428 429 /** 430 * iterator iterates through all elements 431 */ 432 public void testIterator() { 433 LinkedList q = populatedQueue(SIZE); 434 Iterator it = q.iterator(); 435 int i; 436 for (i = 0; it.hasNext(); i++) 437 assertTrue(q.contains(it.next())); 438 assertEquals(i, SIZE); 439 assertIteratorExhausted(it); 440 } 441 442 /** 443 * iterator of empty collection has no elements 444 */ 445 public void testEmptyIterator() { 446 assertIteratorExhausted(new LinkedList().iterator()); 447 } 448 449 /** 450 * iterator ordering is FIFO 451 */ 452 public void testIteratorOrdering() { 453 final LinkedList q = new LinkedList(); 454 q.add(new Integer(1)); 455 q.add(new Integer(2)); 456 q.add(new Integer(3)); 457 int k = 0; 458 for (Iterator it = q.iterator(); it.hasNext();) { 459 assertEquals(++k, it.next()); 460 } 461 462 assertEquals(3, k); 463 } 464 465 /** 466 * iterator.remove removes current element 467 */ 468 public void testIteratorRemove() { 469 final LinkedList q = new LinkedList(); 470 q.add(new Integer(1)); 471 q.add(new Integer(2)); 472 q.add(new Integer(3)); 473 Iterator it = q.iterator(); 474 assertEquals(1, it.next()); 475 it.remove(); 476 it = q.iterator(); 477 assertEquals(2, it.next()); 478 assertEquals(3, it.next()); 479 assertFalse(it.hasNext()); 480 } 481 482 /** 483 * Descending iterator iterates through all elements 484 */ 485 public void testDescendingIterator() { 486 LinkedList q = populatedQueue(SIZE); 487 int i = 0; 488 Iterator it = q.descendingIterator(); 489 while (it.hasNext()) { 490 assertTrue(q.contains(it.next())); 491 ++i; 492 } 493 assertEquals(i, SIZE); 494 assertFalse(it.hasNext()); 495 try { 496 it.next(); 497 shouldThrow(); 498 } catch (NoSuchElementException success) {} 499 } 500 501 /** 502 * Descending iterator ordering is reverse FIFO 503 */ 504 public void testDescendingIteratorOrdering() { 505 final LinkedList q = new LinkedList(); 506 q.add(new Integer(3)); 507 q.add(new Integer(2)); 508 q.add(new Integer(1)); 509 int k = 0; 510 for (Iterator it = q.descendingIterator(); it.hasNext();) { 511 assertEquals(++k, it.next()); 512 } 513 514 assertEquals(3, k); 515 } 516 517 /** 518 * descendingIterator.remove removes current element 519 */ 520 public void testDescendingIteratorRemove() { 521 final LinkedList q = new LinkedList(); 522 q.add(three); 523 q.add(two); 524 q.add(one); 525 Iterator it = q.descendingIterator(); 526 it.next(); 527 it.remove(); 528 it = q.descendingIterator(); 529 assertSame(it.next(), two); 530 assertSame(it.next(), three); 531 assertFalse(it.hasNext()); 532 } 533 534 /** 535 * toString contains toStrings of elements 536 */ 537 public void testToString() { 538 LinkedList q = populatedQueue(SIZE); 539 String s = q.toString(); 540 for (int i = 0; i < SIZE; ++i) { 541 assertTrue(s.contains(String.valueOf(i))); 542 } 543 } 544 545 /** 546 * peek returns element inserted with addFirst 547 */ 548 public void testAddFirst() { 549 LinkedList q = populatedQueue(3); 550 q.addFirst(four); 551 assertSame(four, q.peek()); 552 } 553 554 /** 555 * peekFirst returns element inserted with push 556 */ 557 public void testPush() { 558 LinkedList q = populatedQueue(3); 559 q.push(four); 560 assertSame(four, q.peekFirst()); 561 } 562 563 /** 564 * pop removes next element, or throws NSEE if empty 565 */ 566 public void testPop() { 567 LinkedList q = populatedQueue(SIZE); 568 for (int i = 0; i < SIZE; ++i) { 569 assertEquals(i, q.pop()); 570 } 571 try { 572 q.pop(); 573 shouldThrow(); 574 } catch (NoSuchElementException success) {} 575 } 576 577 /** 578 * OfferFirst succeeds 579 */ 580 public void testOfferFirst() { 581 LinkedList q = new LinkedList(); 582 assertTrue(q.offerFirst(new Integer(0))); 583 assertTrue(q.offerFirst(new Integer(1))); 584 } 585 586 /** 587 * OfferLast succeeds 588 */ 589 public void testOfferLast() { 590 LinkedList q = new LinkedList(); 591 assertTrue(q.offerLast(new Integer(0))); 592 assertTrue(q.offerLast(new Integer(1))); 593 } 594 595 /** 596 * pollLast succeeds unless empty 597 */ 598 public void testPollLast() { 599 LinkedList q = populatedQueue(SIZE); 600 for (int i = SIZE - 1; i >= 0; --i) { 601 assertEquals(i, q.pollLast()); 602 } 603 assertNull(q.pollLast()); 604 } 605 606 /** 607 * peekFirst returns next element, or null if empty 608 */ 609 public void testPeekFirst() { 610 LinkedList q = populatedQueue(SIZE); 611 for (int i = 0; i < SIZE; ++i) { 612 assertEquals(i, q.peekFirst()); 613 assertEquals(i, q.pollFirst()); 614 assertTrue(q.peekFirst() == null || 615 !q.peekFirst().equals(i)); 616 } 617 assertNull(q.peekFirst()); 618 } 619 620 /** 621 * peekLast returns next element, or null if empty 622 */ 623 public void testPeekLast() { 624 LinkedList q = populatedQueue(SIZE); 625 for (int i = SIZE - 1; i >= 0; --i) { 626 assertEquals(i, q.peekLast()); 627 assertEquals(i, q.pollLast()); 628 assertTrue(q.peekLast() == null || 629 !q.peekLast().equals(i)); 630 } 631 assertNull(q.peekLast()); 632 } 633 634 public void testFirstElement() { 635 LinkedList q = populatedQueue(SIZE); 636 for (int i = 0; i < SIZE; ++i) { 637 assertEquals(i, q.getFirst()); 638 assertEquals(i, q.pollFirst()); 639 } 640 try { 641 q.getFirst(); 642 shouldThrow(); 643 } catch (NoSuchElementException success) {} 644 } 645 646 /** 647 * getLast returns next element, or throws NSEE if empty 648 */ 649 public void testLastElement() { 650 LinkedList q = populatedQueue(SIZE); 651 for (int i = SIZE - 1; i >= 0; --i) { 652 assertEquals(i, q.getLast()); 653 assertEquals(i, q.pollLast()); 654 } 655 try { 656 q.getLast(); 657 shouldThrow(); 658 } catch (NoSuchElementException success) {} 659 assertNull(q.peekLast()); 660 } 661 662 /** 663 * removeFirstOccurrence(x) removes x and returns true if present 664 */ 665 public void testRemoveFirstOccurrence() { 666 LinkedList q = populatedQueue(SIZE); 667 for (int i = 1; i < SIZE; i += 2) { 668 assertTrue(q.removeFirstOccurrence(new Integer(i))); 669 } 670 for (int i = 0; i < SIZE; i += 2) { 671 assertTrue(q.removeFirstOccurrence(new Integer(i))); 672 assertFalse(q.removeFirstOccurrence(new Integer(i + 1))); 673 } 674 assertTrue(q.isEmpty()); 675 } 676 677 /** 678 * removeLastOccurrence(x) removes x and returns true if present 679 */ 680 public void testRemoveLastOccurrence() { 681 LinkedList q = populatedQueue(SIZE); 682 for (int i = 1; i < SIZE; i += 2) { 683 assertTrue(q.removeLastOccurrence(new Integer(i))); 684 } 685 for (int i = 0; i < SIZE; i += 2) { 686 assertTrue(q.removeLastOccurrence(new Integer(i))); 687 assertFalse(q.removeLastOccurrence(new Integer(i + 1))); 688 } 689 assertTrue(q.isEmpty()); 690 } 691 692 }