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 }