/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/publicdomain/zero/1.0/

 * Other contributors include Andrew Wright, Jeffrey Hayes,

 * Pat Fisher, Mike Judd.

 */

import java.util.Arrays;

import java.util.Collection;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.NoSuchElementException;

import junit.framework.Test;

public class LinkedListTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        class Implementation implements CollectionImplementation {

            public Class<?> klazz() { return LinkedList.class; }

            public Collection emptyCollection() { return new LinkedList(); }

            public Object makeElement(int i) { return i; }

            public boolean isConcurrent() { return false; }

            public boolean permitsNulls() { return true; }

        }

        class SubListImplementation extends Implementation {

            public Collection emptyCollection() {

                return new LinkedList().subList(0, 0);

            }

        }

        return newTestSuite(

                LinkedListTest.class,

                CollectionTest.testSuite(new Implementation()),

                CollectionTest.testSuite(new SubListImplementation()));

    }

    /**

     * Returns a new queue of given size containing consecutive

     * Integers 0 ... n - 1.

     */

    private static LinkedList<Integer> populatedQueue(int n) {

        LinkedList<Integer> q = new LinkedList<>();

        assertTrue(q.isEmpty());

        for (int i = 0; i < n; ++i)

            assertTrue(q.offer(new Integer(i)));

        assertFalse(q.isEmpty());

        assertEquals(n, q.size());

        assertEquals((Integer) 0, q.peekFirst());

        assertEquals((Integer) (n - 1), q.peekLast());

        return q;

    }

    /**

     * new queue is empty

     */

    public void testConstructor1() {

        assertEquals(0, new LinkedList().size());

    }

    /**

     * Initializing from null Collection throws NPE

     */

    public void testConstructor3() {

        try {

            new LinkedList((Collection)null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Queue contains all elements of collection used to initialize

     */

    public void testConstructor6() {

        Integer[] ints = new Integer[SIZE];

        for (int i = 0; i < SIZE; ++i)

            ints[i] = i;

        LinkedList q = new LinkedList(Arrays.asList(ints));

        for (int i = 0; i < SIZE; ++i)

            assertEquals(ints[i], q.poll());

    }

    /**

     * isEmpty is true before add, false after

     */

    public void testEmpty() {

        LinkedList q = new LinkedList();

        assertTrue(q.isEmpty());

        q.add(new Integer(1));

        assertFalse(q.isEmpty());

        q.add(new Integer(2));

        q.remove();

        q.remove();

        assertTrue(q.isEmpty());

    }

    /**

     * size changes when elements added and removed

     */

    public void testSize() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(SIZE - i, q.size());

            q.remove();

        }

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(i, q.size());

            q.add(new Integer(i));

        }

    }

    /**

     * offer(null) succeeds

     */

    public void testOfferNull() {

        LinkedList q = new LinkedList();

        q.offer(null);

        assertNull(q.get(0));

        assertTrue(q.contains(null));

    }

    /**

     * Offer succeeds

     */

    public void testOffer() {

        LinkedList q = new LinkedList();

        assertTrue(q.offer(new Integer(0)));

        assertTrue(q.offer(new Integer(1)));

    }

    /**

     * add succeeds

     */

    public void testAdd() {

        LinkedList q = new LinkedList();

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(i, q.size());

            assertTrue(q.add(new Integer(i)));

        }

    }

    /**

     * addAll(null) throws NPE

     */

    public void testAddAll1() {

        LinkedList q = new LinkedList();

        try {

            q.addAll(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Queue contains all elements, in traversal order, of successful addAll

     */

    public void testAddAll5() {

        Integer[] empty = new Integer[0];

        Integer[] ints = new Integer[SIZE];

        for (int i = 0; i < SIZE; ++i)

            ints[i] = i;

        LinkedList q = new LinkedList();

        assertFalse(q.addAll(Arrays.asList(empty)));

        assertTrue(q.addAll(Arrays.asList(ints)));

        for (int i = 0; i < SIZE; ++i)

            assertEquals(ints[i], q.poll());

    }

    /**

     * addAll with too large an index throws IOOBE

     */

    public void testAddAll2_IndexOutOfBoundsException() {

        LinkedList l = new LinkedList();

        l.add(new Object());

        LinkedList m = new LinkedList();

        m.add(new Object());

        try {

            l.addAll(4,m);

            shouldThrow();

        } catch (IndexOutOfBoundsException success) {}

    }

    /**

     * addAll with negative index throws IOOBE

     */

    public void testAddAll4_BadIndex() {

        LinkedList l = new LinkedList();

        l.add(new Object());

        LinkedList m = new LinkedList();

        m.add(new Object());

        try {

            l.addAll(-1,m);

            shouldThrow();

        } catch (IndexOutOfBoundsException success) {}

    }

    /**

     * poll succeeds unless empty

     */

    public void testPoll() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(i, q.poll());

        }

        assertNull(q.poll());

    }

    /**

     * peek returns next element, or null if empty

     */

    public void testPeek() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(i, q.peek());

            assertEquals(i, q.poll());

            assertTrue(q.peek() == null ||

                       !q.peek().equals(i));

        }

        assertNull(q.peek());

    }

    /**

     * element returns next element, or throws NSEE if empty

     */

    public void testElement() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(i, q.element());

            assertEquals(i, q.poll());

        }

        try {

            q.element();

            shouldThrow();

        } catch (NoSuchElementException success) {}

    }

    /**

     * remove removes next element, or throws NSEE if empty

     */

    public void testRemove() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            assertEquals(i, q.remove());

        }

        try {

            q.remove();

            shouldThrow();

        } catch (NoSuchElementException success) {}

    }

    /**

     * remove(x) removes x and returns true if present

     */

    public void testRemoveElement() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 1; i < SIZE; i += 2) {

            assertTrue(q.contains(i));

            assertTrue(q.remove((Integer)i));

            assertFalse(q.contains(i));

            assertTrue(q.contains(i - 1));

        }

        for (int i = 0; i < SIZE; i += 2) {

            assertTrue(q.contains(i));

            assertTrue(q.remove((Integer)i));

            assertFalse(q.contains(i));

            assertFalse(q.remove((Integer)(i + 1)));

            assertFalse(q.contains(i + 1));

        }

        assertTrue(q.isEmpty());

    }

    /**

     * contains(x) reports true when elements added but not yet removed

     */

    public void testContains() {

        LinkedList q = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            assertTrue(q.contains(new Integer(i)));

            q.poll();

            assertFalse(q.contains(new Integer(i)));

        }

    }

    /**

     * clear removes all elements

     */

    public void testClear() {

        LinkedList q = populatedQueue(SIZE);

        q.clear();

        assertTrue(q.isEmpty());

        assertEquals(0, q.size());

        assertTrue(q.add(new Integer(1)));

        assertFalse(q.isEmpty());

        q.clear();

        assertTrue(q.isEmpty());

    }

    /**

     * containsAll(c) is true when c contains a subset of elements

     */

    public void testContainsAll() {

        LinkedList q = populatedQueue(SIZE);

        LinkedList p = new LinkedList();

        for (int i = 0; i < SIZE; ++i) {

            assertTrue(q.containsAll(p));

            assertFalse(p.containsAll(q));

            assertTrue(p.add(new Integer(i)));

        }

        assertTrue(p.containsAll(q));

    }

    /**

     * retainAll(c) retains only those elements of c and reports true if changed

     */

    public void testRetainAll() {

        LinkedList q = populatedQueue(SIZE);

        LinkedList p = populatedQueue(SIZE);

        for (int i = 0; i < SIZE; ++i) {

            boolean changed = q.retainAll(p);

            if (i == 0)

                assertFalse(changed);

            else

                assertTrue(changed);

            assertTrue(q.containsAll(p));

            assertEquals(SIZE - i, q.size());

            p.remove();

        }

    }

    /**

     * removeAll(c) removes only those elements of c and reports true if changed

     */

    public void testRemoveAll() {

        for (int i = 1; i < SIZE; ++i) {

            LinkedList q = populatedQueue(SIZE);

            LinkedList p = populatedQueue(i);

            assertTrue(q.removeAll(p));

            assertEquals(SIZE - i, q.size());

            for (int j = 0; j < i; ++j) {

                Integer x = (Integer)(p.remove());

                assertFalse(q.contains(x));

            }

        }

    }

    /**

     * toArray contains all elements in FIFO order

     */

    public void testToArray() {

        LinkedList q = populatedQueue(SIZE);

        Object[] o = q.toArray();

        for (int i = 0; i < o.length; i++)

            assertSame(o[i], q.poll());

    }

    /**

     * toArray(a) contains all elements in FIFO order

     */

    public void testToArray2() {

        LinkedList<Integer> q = populatedQueue(SIZE);

        Integer[] ints = new Integer[SIZE];

        Integer[] array = q.toArray(ints);

        assertSame(ints, array);

        for (int i = 0; i < ints.length; i++)

            assertSame(ints[i], q.poll());

    }

    /**

     * toArray(null) throws NullPointerException

     */

    public void testToArray_NullArg() {

        LinkedList l = new LinkedList();

        l.add(new Object());

        try {

            l.toArray(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * toArray(incompatible array type) throws ArrayStoreException

     */

    public void testToArray1_BadArg() {

        LinkedList l = new LinkedList();

        l.add(new Integer(5));

        try {

            l.toArray(new String[10]);

            shouldThrow();

        } catch (ArrayStoreException success) {}

    }

    /**

     * iterator iterates through all elements

     */

    public void testIterator() {

        LinkedList q = populatedQueue(SIZE);

        Iterator it = q.iterator();

        int i;

        for (i = 0; it.hasNext(); i++)

            assertTrue(q.contains(it.next()));

        assertEquals(i, SIZE);

        assertIteratorExhausted(it);

    }

    /**

     * iterator of empty collection has no elements

     */

    public void testEmptyIterator() {

        assertIteratorExhausted(new LinkedList().iterator());

    }

    /**

     * iterator ordering is FIFO

     */

    public void testIteratorOrdering() {

        final LinkedList q = new LinkedList();

        q.add(new Integer(1));

        q.add(new Integer(2));

        q.add(new Integer(3));

        int k = 0;

        for (Iterator it = q.iterator(); it.hasNext();) {

            assertEquals(++k, it.next());

        }

        assertEquals(3, k);

    }

    /**

     * iterator.remove removes current element

     */

    public void testIteratorRemove() {

        final LinkedList q = new LinkedList();

        q.add(new Integer(1));

        q.add(new Integer(2));

        q.add(new Integer(3));

        Iterator it = q.iterator();

        assertEquals(1, it.next());

        it.remove();

        it = q.iterator();

        assertEquals(2, it.next());

        assertEquals(3, it.next());

        assertFalse(it.hasNext());

    }

    /**

     * Descending iterator iterates through all elements

     */

    public void testDescendingIterator() {

        LinkedList q = populatedQueue(SIZE);

        int i = 0;

        Iterator it = q.descendingIterator();

        while (it.hasNext()) {

            assertTrue(q.contains(it.next()));

            ++i;

        }

        assertEquals(i, SIZE);

        assertFalse(it.hasNext());

        try {

            it.next();

            shouldThrow();

        } catch (NoSuchElementException success) {}

    }

    /**

     * Descending iterator ordering is reverse FIFO

     */

    public void testDescendingIteratorOrdering() {

        final LinkedList q = new LinkedList();

        q.add(new Integer(3));

        q.add(new Integer(2));

        q.add(new Integer(1));

        int k = 0;

        for (Iterator it = q.descendingIterator(); it.hasNext();) {

            assertEquals(++k, it.next());

        }

        assertEquals(3, k);

    }

    /**

     * descendingIterator.remove removes current element

     */

    public void testDescendingIteratorRemove() {

        final LinkedList q = new LinkedList();

        q.add(three);

        q.add(two);

        q.add(one);

        Iterator it = q.descendingIterator();

        it.next();

        it.remove();

        it = q.descendingIterator();

        assertSame(it.next(), two);

        assertSame(it.next(), three);

        assertFalse(it.hasNext());

    }

    /**