/*

 * 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.Deque;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Queue;

import java.util.Random;

import java.util.concurrent.CompletableFuture;

import java.util.concurrent.ConcurrentLinkedDeque;

import java.util.concurrent.ThreadLocalRandom;

import java.util.concurrent.atomic.LongAdder;

import junit.framework.Test;

public class ConcurrentLinkedDequeTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        class Implementation implements CollectionImplementation {

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

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

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

            public boolean isConcurrent() { return true; }

            public boolean permitsNulls() { return false; }

        }

        return newTestSuite(ConcurrentLinkedDequeTest.class,

                            CollectionTest.testSuite(new Implementation()));

    }

    /**

     * Returns a new deque of given size containing consecutive

     * Integers 0 ... n - 1.

     */

    private static ConcurrentLinkedDeque<Integer> populatedDeque(int n) {

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

        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 deque is empty

     */

    public void testConstructor1() {

        assertTrue(new ConcurrentLinkedDeque().isEmpty());

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

    }

    /**

     * Initializing from null Collection throws NPE

     */

    public void testConstructor3() {

        try {

            new ConcurrentLinkedDeque((Collection)null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Initializing from Collection of null elements throws NPE

     */

    public void testConstructor4() {

        try {

            new ConcurrentLinkedDeque(Arrays.asList(new Integer[SIZE]));

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Initializing from Collection with some null elements throws NPE

     */

    public void testConstructor5() {

        Integer[] ints = new Integer[SIZE];

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

            ints[i] = new Integer(i);

        try {

            new ConcurrentLinkedDeque(Arrays.asList(ints));

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Deque 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] = new Integer(i);

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(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() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        assertTrue(q.isEmpty());

        q.add(one);

        assertFalse(q.isEmpty());

        q.add(two);

        q.remove();

        q.remove();

        assertTrue(q.isEmpty());

    }

    /**

     * size() changes when elements added and removed

     */

    public void testSize() {

        ConcurrentLinkedDeque q = populatedDeque(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));

        }

    }

    /**

     * push(null) throws NPE

     */

    public void testPushNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.push(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * peekFirst() returns element inserted with push

     */

    public void testPush() {

        ConcurrentLinkedDeque q = populatedDeque(3);

        q.pollLast();

        q.push(four);

        assertSame(four, q.peekFirst());

    }

    /**

     * pop() removes first element, or throws NSEE if empty

     */

    public void testPop() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.pop());

        }

        try {

            q.pop();

            shouldThrow();

        } catch (NoSuchElementException success) {}

    }

    /**

     * offer(null) throws NPE

     */

    public void testOfferNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.offer(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * offerFirst(null) throws NPE

     */

    public void testOfferFirstNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.offerFirst(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * offerLast(null) throws NPE

     */

    public void testOfferLastNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.offerLast(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * offer(x) succeeds

     */

    public void testOffer() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        assertTrue(q.offer(zero));

        assertTrue(q.offer(one));

        assertSame(zero, q.peekFirst());

        assertSame(one, q.peekLast());

    }

    /**

     * offerFirst(x) succeeds

     */

    public void testOfferFirst() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        assertTrue(q.offerFirst(zero));

        assertTrue(q.offerFirst(one));

        assertSame(one, q.peekFirst());

        assertSame(zero, q.peekLast());

    }

    /**

     * offerLast(x) succeeds

     */

    public void testOfferLast() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        assertTrue(q.offerLast(zero));

        assertTrue(q.offerLast(one));

        assertSame(zero, q.peekFirst());

        assertSame(one, q.peekLast());

    }

    /**

     * add(null) throws NPE

     */

    public void testAddNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.add(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * addFirst(null) throws NPE

     */

    public void testAddFirstNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.addFirst(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * addLast(null) throws NPE

     */

    public void testAddLastNull() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.addLast(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * add(x) succeeds

     */

    public void testAdd() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        assertTrue(q.add(zero));

        assertTrue(q.add(one));

        assertSame(zero, q.peekFirst());

        assertSame(one, q.peekLast());

    }

    /**

     * addFirst(x) succeeds

     */

    public void testAddFirst() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        q.addFirst(zero);

        q.addFirst(one);

        assertSame(one, q.peekFirst());

        assertSame(zero, q.peekLast());

    }

    /**

     * addLast(x) succeeds

     */

    public void testAddLast() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        q.addLast(zero);

        q.addLast(one);

        assertSame(zero, q.peekFirst());

        assertSame(one, q.peekLast());

    }

    /**

     * addAll(null) throws NPE

     */

    public void testAddAll1() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.addAll(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * addAll(this) throws IllegalArgumentException

     */

    public void testAddAllSelf() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

        try {

            q.addAll(q);

            shouldThrow();

        } catch (IllegalArgumentException success) {}

    }

    /**

     * addAll of a collection with null elements throws NPE

     */

    public void testAddAll2() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        try {

            q.addAll(Arrays.asList(new Integer[SIZE]));

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * addAll of a collection with any null elements throws NPE after

     * possibly adding some elements

     */

    public void testAddAll3() {

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

        Integer[] ints = new Integer[SIZE];

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

            ints[i] = new Integer(i);

        try {

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

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Deque 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] = new Integer(i);

        ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();

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

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

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

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

    }

    /**

     * pollFirst() succeeds unless empty

     */

    public void testPollFirst() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.pollFirst());

        }

        assertNull(q.pollFirst());

    }

    /**

     * pollLast() succeeds unless empty

     */

    public void testPollLast() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

        for (int i = SIZE - 1; i >= 0; --i) {

            assertEquals(i, q.pollLast());

        }

        assertNull(q.pollLast());

    }

    /**

     * poll() succeeds unless empty

     */

    public void testPoll() {

        ConcurrentLinkedDeque q = populatedDeque(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() {

        ConcurrentLinkedDeque q = populatedDeque(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 first element, or throws NSEE if empty

     */

    public void testElement() {

        ConcurrentLinkedDeque q = populatedDeque(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() {

        ConcurrentLinkedDeque q = populatedDeque(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() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

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

            assertTrue(q.contains(i));

            assertTrue(q.remove(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(i));

            assertFalse(q.contains(i));

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

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

        }

        assertTrue(q.isEmpty());

    }

    /**

     * peekFirst() returns next element, or null if empty

     */

    public void testPeekFirst() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.peekFirst());

            assertEquals(i, q.pollFirst());

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

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

        }

        assertNull(q.peekFirst());

    }

    /**

     * peekLast() returns next element, or null if empty

     */

    public void testPeekLast() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

        for (int i = SIZE - 1; i >= 0; --i) {

            assertEquals(i, q.peekLast());

            assertEquals(i, q.pollLast());

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

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

        }

        assertNull(q.peekLast());

    }

    /**

     * getFirst() returns first element, or throws NSEE if empty

     */

    public void testFirstElement() {

        ConcurrentLinkedDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.getFirst());