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