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