/*

 * 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/

 */

import static java.util.concurrent.TimeUnit.MILLISECONDS;

import java.util.ArrayList;

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.concurrent.BlockingDeque;

import java.util.concurrent.BlockingQueue;

import java.util.concurrent.CountDownLatch;

import java.util.concurrent.Executors;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.LinkedBlockingDeque;

import junit.framework.Test;

public class LinkedBlockingDequeTest extends JSR166TestCase {

    public static class Unbounded extends BlockingQueueTest {

        protected BlockingQueue emptyCollection() {

            return new LinkedBlockingDeque();

        }

    }

    public static class Bounded extends BlockingQueueTest {

        protected BlockingQueue emptyCollection() {

            return new LinkedBlockingDeque(SIZE);

        }

    }

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        class Implementation implements CollectionImplementation {

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

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

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

            public boolean isConcurrent() { return true; }

            public boolean permitsNulls() { return false; }

        }

        return newTestSuite(LinkedBlockingDequeTest.class,

                            new Unbounded().testSuite(),

                            new Bounded().testSuite(),

                            CollectionTest.testSuite(new Implementation()));

    }

    /**

     * Returns a new deque of given size containing consecutive

     * Integers 0 ... n - 1.

     */

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

        LinkedBlockingDeque<Integer> q =

            new LinkedBlockingDeque<Integer>(n);

        assertTrue(q.isEmpty());

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

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

        assertFalse(q.isEmpty());

        assertEquals(0, q.remainingCapacity());

        assertEquals(n, q.size());

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

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

        return q;

    }

    /**

     * isEmpty is true before add, false after

     */

    public void testEmpty() {

        LinkedBlockingDeque q = new LinkedBlockingDeque();

        assertTrue(q.isEmpty());

        q.add(new Integer(1));

        assertFalse(q.isEmpty());

        q.add(new Integer(2));

        q.removeFirst();

        q.removeFirst();

        assertTrue(q.isEmpty());

    }

    /**

     * size changes when elements added and removed

     */

    public void testSize() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

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

            q.removeFirst();

        }

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

            assertEquals(i, q.size());

            q.add(new Integer(i));

        }

    }

    /**

     * offerFirst(null) throws NullPointerException

     */

    public void testOfferFirstNull() {

        LinkedBlockingDeque q = new LinkedBlockingDeque();

        try {

            q.offerFirst(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * offerLast(null) throws NullPointerException

     */

    public void testOfferLastNull() {

        LinkedBlockingDeque q = new LinkedBlockingDeque();

        try {

            q.offerLast(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * OfferFirst succeeds

     */

    public void testOfferFirst() {

        LinkedBlockingDeque q = new LinkedBlockingDeque();

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

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

    }

    /**

     * OfferLast succeeds

     */

    public void testOfferLast() {

        LinkedBlockingDeque q = new LinkedBlockingDeque();

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

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

    }

    /**

     * pollFirst succeeds unless empty

     */

    public void testPollFirst() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.pollFirst());

        }

        assertNull(q.pollFirst());

    }

    /**

     * pollLast succeeds unless empty

     */

    public void testPollLast() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.pollLast());

        }

        assertNull(q.pollLast());

    }

    /**

     * peekFirst returns next element, or null if empty

     */

    public void testPeekFirst() {

        LinkedBlockingDeque 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());

    }

    /**

     * peek returns next element, or null if empty

     */

    public void testPeek() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.peek());

            assertEquals(i, q.pollFirst());

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

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

        }

        assertNull(q.peek());

    }

    /**

     * peekLast returns next element, or null if empty

     */

    public void testPeekLast() {

        LinkedBlockingDeque 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() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.getFirst());

            assertEquals(i, q.pollFirst());

        }

        try {

            q.getFirst();

            shouldThrow();

        } catch (NoSuchElementException success) {}

        assertNull(q.peekFirst());

    }

    /**

     * getLast() returns last element, or throws NSEE if empty

     */

    public void testLastElement() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.getLast());

            assertEquals(i, q.pollLast());

        }

        try {

            q.getLast();

            shouldThrow();

        } catch (NoSuchElementException success) {}

        assertNull(q.peekLast());

    }

    /**

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

     */

    public void testRemoveFirst() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.removeFirst());

        }

        try {

            q.removeFirst();

            shouldThrow();

        } catch (NoSuchElementException success) {}

        assertNull(q.peekFirst());

    }

    /**

     * removeLast() removes last element, or throws NSEE if empty

     */

    public void testRemoveLast() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.removeLast());

        }

        try {

            q.removeLast();

            shouldThrow();

        } catch (NoSuchElementException success) {}

        assertNull(q.peekLast());

    }

    /**

     * remove removes next element, or throws NSEE if empty

     */

    public void testRemove() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.remove());

        }

        try {

            q.remove();

            shouldThrow();

        } catch (NoSuchElementException success) {}

    }

    /**

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

     */

    public void testRemoveFirstOccurrence() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

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

        }

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

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

            assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));

        }

        assertTrue(q.isEmpty());

    }

    /**

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

     */

    public void testRemoveLastOccurrence() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

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

        }

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

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

            assertFalse(q.removeLastOccurrence(new Integer(i + 1)));

        }

        assertTrue(q.isEmpty());

    }

    /**

     * peekFirst returns element inserted with addFirst

     */

    public void testAddFirst() {

        LinkedBlockingDeque q = populatedDeque(3);

        q.pollLast();

        q.addFirst(four);

        assertSame(four, q.peekFirst());

    }

    /**

     * peekLast returns element inserted with addLast

     */

    public void testAddLast() {

        LinkedBlockingDeque q = populatedDeque(3);

        q.pollLast();

        q.addLast(four);

        assertSame(four, q.peekLast());

    }

    /**

     * A new deque has the indicated capacity, or Integer.MAX_VALUE if

     * none given

     */

    public void testConstructor1() {

        assertEquals(SIZE, new LinkedBlockingDeque(SIZE).remainingCapacity());

        assertEquals(Integer.MAX_VALUE, new LinkedBlockingDeque().remainingCapacity());

    }

    /**

     * Constructor throws IllegalArgumentException if capacity argument nonpositive

     */

    public void testConstructor2() {

        try {

            new LinkedBlockingDeque(0);

            shouldThrow();

        } catch (IllegalArgumentException success) {}

    }

    /**

     * Initializing from null Collection throws NullPointerException

     */

    public void testConstructor3() {

        try {

            new LinkedBlockingDeque(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Initializing from Collection of null elements throws NullPointerException

     */

    public void testConstructor4() {

        Collection<Integer> elements = Arrays.asList(new Integer[SIZE]);

        try {

            new LinkedBlockingDeque(elements);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * Initializing from Collection with some null elements throws

     * NullPointerException

     */

    public void testConstructor5() {

        Integer[] ints = new Integer[SIZE];

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

            ints[i] = i;

        Collection<Integer> elements = Arrays.asList(ints);

        try {

            new LinkedBlockingDeque(elements);

            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] = i;

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

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

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

    }

    /**

     * Deque transitions from empty to full when elements added

     */

    public void testEmptyFull() {

        LinkedBlockingDeque q = new LinkedBlockingDeque(2);

        assertTrue(q.isEmpty());

        assertEquals("should have room for 2", 2, q.remainingCapacity());

        q.add(one);

        assertFalse(q.isEmpty());

        q.add(two);

        assertFalse(q.isEmpty());

        assertEquals(0, q.remainingCapacity());

        assertFalse(q.offer(three));

    }

    /**

     * remainingCapacity decreases on add, increases on remove

     */

    public void testRemainingCapacity() {

        BlockingQueue q = populatedDeque(SIZE);

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

            assertEquals(i, q.remainingCapacity());

            assertEquals(SIZE, q.size() + q.remainingCapacity());

            assertEquals(i, q.remove());

        }

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

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

            assertEquals(SIZE, q.size() + q.remainingCapacity());

            assertTrue(q.add(i));

        }

    }

    /**

     * push(null) throws NPE

     */

    public void testPushNull() {

        LinkedBlockingDeque q = new LinkedBlockingDeque(1);

        try {

            q.push(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * push succeeds if not full; throws IllegalStateException if full

     */

    public void testPush() {

        LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);

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

            Integer x = new Integer(i);

            q.push(x);

            assertEquals(x, q.peek());

        }

        assertEquals(0, q.remainingCapacity());

        try {

            q.push(new Integer(SIZE));

            shouldThrow();

        } catch (IllegalStateException success) {}

    }

    /**

     * peekFirst returns element inserted with push

     */

    public void testPushWithPeek() {

        LinkedBlockingDeque q = populatedDeque(3);

        q.pollLast();

        q.push(four);

        assertSame(four, q.peekFirst());

    }

    /**

     * pop removes next element, or throws NSEE if empty

     */

    public void testPop() {

        LinkedBlockingDeque q = populatedDeque(SIZE);

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

            assertEquals(i, q.pop());

        }

        try {

            q.pop();

            shouldThrow();

        } catch (NoSuchElementException success) {}

    }

    /**

     * Offer succeeds if not full; fails if full

     */

    public void testOffer() {

        LinkedBlockingDeque q = new LinkedBlockingDeque(1);

        assertTrue(q.offer(zero));

        assertFalse(q.offer(one));

    }

    /**

     * add succeeds if not full; throws IllegalStateException if full

     */

    public void testAdd() {

        LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);

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

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