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