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