Emulate java.util.ArrayDeque
Tests adapted from Apache Harmony.
Bug: #8511
Bug-Link: https://github.com/gwtproject/gwt/issues/8511
Review-Link: https://gwt-review.googlesource.com/#/c/6037/
Change-Id: Ic1b55332c9444b0451d165145dfb90ea2754b6d8
diff --git a/user/super/com/google/gwt/emul/java/util/ArrayDeque.java b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
new file mode 100644
index 0000000..619b7e8
--- /dev/null
+++ b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
@@ -0,0 +1,487 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package java.util;
+
+import static javaemul.internal.InternalPreconditions.checkCriticalElement;
+import static javaemul.internal.InternalPreconditions.checkCriticalNotNull;
+import static javaemul.internal.InternalPreconditions.checkElement;
+import static javaemul.internal.InternalPreconditions.checkState;
+
+import javaemul.internal.ArrayHelper;
+
+/**
+ * A {@link Deque} based on circular buffer that is implemented with an array and head/tail
+ * pointers. Array deques have no capacity restrictions; they grow as necessary to support usage.
+ * Null elements are prohibited. This class is likely to be faster than {@link Stack}
+ * when used as a stack, and faster than {@link LinkedList} when used as a queue.
+ * <a href="https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html">ArrayDeque</a>
+ *
+ * @param <E> the element type.
+ */
+public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable {
+
+ private final class IteratorImpl implements Iterator<E> {
+ /**
+ * Index of element to be returned by subsequent call to next.
+ */
+ private int currentIndex = head;
+
+ /**
+ * Tail recorded at construction (also in remove), to stop
+ * iterator and also to check for comodification.
+ */
+ private int fence = tail;
+
+ /**
+ * Index of element returned by most recent call to next.
+ * Reset to -1 if element is deleted by a call to remove.
+ */
+ private int lastIndex = -1;
+
+ @Override
+ public boolean hasNext() {
+ return currentIndex != fence;
+ }
+
+ @Override
+ public E next() {
+ checkCriticalElement(hasNext());
+
+ E e = array[currentIndex];
+ // OpenJDK ArrayDeque doesn't catch all possible comodifications,
+ // but does catch the ones that corrupt traversal
+ checkConcurrentModification(fence == tail && e != null);
+ lastIndex = currentIndex;
+ currentIndex = (currentIndex + 1) & (array.length - 1);
+ return e;
+ }
+
+ @Override
+ public void remove() {
+ checkState(lastIndex >= 0);
+ checkConcurrentModification(head <= lastIndex && lastIndex < tail);
+
+ if (removeAtIndex(lastIndex) < 0) {
+ // if left-shifted, undo increment in next()
+ currentIndex = (currentIndex - 1) & (array.length - 1);
+ fence = tail;
+ }
+ lastIndex = -1;
+ }
+ }
+
+ private final class DescendingIteratorImpl implements Iterator<E> {
+ private int currentIndex = tail;
+ private int fence = head;
+ private int lastIndex = -1;
+
+ @Override
+ public boolean hasNext() {
+ return currentIndex != fence;
+ }
+
+ @Override
+ public E next() {
+ checkCriticalElement(hasNext());
+
+ currentIndex = (currentIndex - 1) & (array.length - 1);
+ E e = array[currentIndex];
+ checkConcurrentModification(fence == head && e != null);
+ lastIndex = currentIndex;
+ return e;
+ }
+
+ @Override
+ public void remove() {
+ checkState(lastIndex >= 0);
+ checkConcurrentModification(head <= lastIndex && lastIndex < tail);
+
+ if (removeAtIndex(lastIndex) > 0) {
+ // if right-shifted, undo decrement in next()
+ currentIndex = (currentIndex + 1) & (array.length - 1);
+ fence = head;
+ }
+ lastIndex = -1;
+ }
+ }
+
+ /**
+ * The minimum capacity that we'll use for a newly created deque.
+ * Must be a power of 2.
+ */
+ private static final int MIN_INITIAL_CAPACITY = 8;
+
+ private static void checkConcurrentModification(boolean expression) {
+ if (!expression) {
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ /**
+ * Returns best power-of-two array length to hold the given number of elements.
+ *
+ * @param numElements the number of elements to hold
+ */
+ @SuppressWarnings("unchecked")
+ private static int nextArrayLength(int numElements) {
+ return nextPowerOfTwo(Math.max(MIN_INITIAL_CAPACITY, numElements));
+ }
+
+ /**
+ * Returns a number that is greater than {@code num} and is a power of two.
+ * If passed {@code num} is not positive integer or next power of two overflows then
+ * returned value is non-positive.
+ * E.g., if num == 32, returns 64. if num == 31, returns 32.
+ *
+ * @param num positive integer.
+ */
+ private static int nextPowerOfTwo(int num) {
+ return Integer.highestOneBit(num) << 1;
+ }
+
+ /**
+ * This field holds a JavaScript array.
+ */
+ @SuppressWarnings("unchecked")
+ private E[] array = (E[]) new Object[MIN_INITIAL_CAPACITY];
+
+ /**
+ * The index of the element at the head of the deque (which is the
+ * element that would be removed by remove() or pop()); or an
+ * arbitrary number equal to tail if the deque is empty.
+ */
+ private int head;
+
+ /**
+ * The index at which the next element would be added to the tail
+ * of the deque (via addLast(E), add(E), or push(E)).
+ */
+ private int tail;
+
+ public ArrayDeque() {
+ }
+
+ public ArrayDeque(Collection<? extends E> c) {
+ this(c.size());
+ addAll(c);
+ }
+
+ public ArrayDeque(int numElements) {
+ ArrayHelper.setLength(array, nextArrayLength(numElements));
+ }
+
+ @Override
+ public boolean add(E e) {
+ addLast(e);
+ return true;
+ }
+
+ @Override
+ public void addFirst(E e) {
+ checkCriticalNotNull(e);
+
+ head = (head - 1) & (array.length - 1);
+ array[head] = e;
+ ensureCapacity();
+ }
+
+ @Override
+ public void addLast(E e) {
+ checkCriticalNotNull(e);
+
+ array[tail] = e;
+ tail = (tail + 1) & (array.length - 1);
+ ensureCapacity();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void clear() {
+ if (head == tail) {
+ return;
+ }
+
+ array = (E[]) new Object[MIN_INITIAL_CAPACITY];
+ head = 0;
+ tail = 0;
+ }
+
+ public Object clone() {
+ return new ArrayDeque<>(this);
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return contains(iterator(), o);
+ }
+
+ @Override
+ public Iterator<E> descendingIterator() {
+ return new DescendingIteratorImpl();
+ }
+
+ @Override
+ public E element() {
+ return getFirst();
+ }
+
+ @Override
+ public E getFirst() {
+ E e = peekFirstElement();
+ checkElement(e != null);
+ return e;
+ }
+
+ @Override
+ public E getLast() {
+ E e = peekLastElement();
+ checkElement(e != null);
+ return e;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return head == tail;
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new IteratorImpl();
+ }
+
+ @Override
+ public boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ @Override
+ public boolean offerFirst(E e) {
+ addFirst(e);
+ return true;
+ }
+
+ @Override
+ public boolean offerLast(E e) {
+ addLast(e);
+ return true;
+ }
+
+ @Override
+ public E peek() {
+ return peekFirst();
+ }
+
+ @Override
+ public E peekFirst() {
+ return peekFirstElement();
+ }
+
+ @Override
+ public E peekLast() {
+ return peekLastElement();
+ }
+
+ @Override
+ public E poll() {
+ return pollFirst();
+ }
+
+ @Override
+ public E pollFirst() {
+ E e = peekFirstElement();
+ if (e == null) {
+ return null;
+ }
+ array[head] = null;
+ head = (head + 1) & (array.length - 1);
+ return e;
+ }
+
+ @Override
+ public E pollLast() {
+ E e = peekLastElement();
+ if (e == null) {
+ return null;
+ }
+ tail = (tail - 1) & (array.length - 1);
+ array[tail] = null;
+ return e;
+ }
+
+ @Override
+ public E pop() {
+ return removeFirst();
+ }
+
+ @Override
+ public void push(E e) {
+ addFirst(e);
+ }
+
+ @Override
+ public E remove() {
+ return removeFirst();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ return removeFirstOccurrence(o);
+ }
+
+ @Override
+ public E removeFirst() {
+ E e = pollFirst();
+ checkElement(e != null);
+ return e;
+ }
+
+ @Override
+ public boolean removeFirstOccurrence(Object o) {
+ return remove(iterator(), o);
+ }
+
+ @Override
+ public E removeLast() {
+ E e = pollLast();
+ checkElement(e != null);
+ return e;
+ }
+
+ @Override
+ public boolean removeLastOccurrence(Object o) {
+ return remove(descendingIterator(), o);
+ }
+
+ @Override
+ public int size() {
+ return (tail - head) & (array.length - 1);
+ }
+
+ @Override
+ public Spliterator<E> spliterator() {
+ return Spliterators.spliterator(this, Spliterator.NONNULL | Spliterator.ORDERED);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public <T> T[] toArray(T[] out) {
+ int size = size();
+ if (out.length < size) {
+ out = ArrayHelper.createFrom(out, size);
+ }
+ Object[] dest = out;
+ final int mask = size - 1;
+ for (int i = head, dstIdx = 0; dstIdx < size; i = (i + 1) & mask, ++dstIdx) {
+ dest[dstIdx] = array[i];
+ }
+ if (out.length > size) {
+ out[size] = null;
+ }
+ return out;
+ }
+
+ private boolean contains(Iterator<E> it, Object o) {
+ if (o == null) {
+ return false;
+ }
+
+ while (it.hasNext()) {
+ if (o.equals(it.next())) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private boolean remove(Iterator<E> it, Object o) {
+ if (contains(it, o)) {
+ it.remove();
+ return true;
+ }
+ return false;
+ }
+
+ private E peekFirstElement() {
+ return array[head];
+ }
+
+ private E peekLastElement() {
+ return array[(tail - 1) & (array.length - 1)];
+ }
+
+ /**
+ * Increase the capacity of this deque when full, i.e.,
+ * when head and tail have wrapped around to become equal.
+ */
+ private void ensureCapacity() {
+ if (head != tail) {
+ return;
+ }
+
+ int numElements = array.length;
+ int newLength = nextArrayLength(numElements);
+ if (head != 0) {
+ E[] newArray = ArrayHelper.createFrom(array, newLength);
+ array = toArray(newArray);
+ } else {
+ ArrayHelper.setLength(array, newLength);
+ }
+ head = 0;
+ tail = numElements;
+ }
+
+ /**
+ * Removes the element at the specified position in the elements array,
+ * adjusting head and tail as necessary. This results in motion of
+ * elements backwards or forwards in the array.
+ *
+ * @return -1 if elements moved backwards (left-shifted); 1 if forwards (right-shifted).
+ */
+ private int removeAtIndex(int i) {
+ final int mask = array.length - 1;
+ int headDistance = (i - head) & mask;
+ int tailDistance = (tail - i) & mask;
+ if (headDistance >= tailDistance) {
+ shiftLeftAtIndex(i);
+ return -1;
+ } else {
+ shiftRightAtIndex(i);
+ return 1;
+ }
+ }
+
+ private void shiftLeftAtIndex(int i) {
+ final int mask = array.length - 1;
+ tail = (tail - 1) & mask;
+ while (i != tail) {
+ int nextOffset = (i + 1) & mask;
+ array[i] = array[nextOffset];
+ i = nextOffset;
+ }
+ array[tail] = null;
+ }
+
+ private void shiftRightAtIndex(int i) {
+ final int mask = array.length - 1;
+ while (i != head) {
+ int prevOffset = (i - 1) & mask;
+ array[i] = array[prevOffset];
+ i = prevOffset;
+ }
+ array[head] = null;
+ head = (head + 1) & mask;
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/CollectionsSuite.java b/user/test/com/google/gwt/emultest/CollectionsSuite.java
index 6ab5bfa..6d69a38 100644
--- a/user/test/com/google/gwt/emultest/CollectionsSuite.java
+++ b/user/test/com/google/gwt/emultest/CollectionsSuite.java
@@ -15,6 +15,7 @@
*/
package com.google.gwt.emultest;
+import com.google.gwt.emultest.java.util.ArrayDequeTest;
import com.google.gwt.emultest.java.util.ArrayListTest;
import com.google.gwt.emultest.java.util.ArraysTest;
import com.google.gwt.emultest.java.util.BitSetTest;
@@ -48,6 +49,7 @@
GWTTestSuite suite = new GWTTestSuite("Tests for emulation of Java Collections");
// $JUnit-BEGIN$
+ suite.addTestSuite(ArrayDequeTest.class);
suite.addTestSuite(ArrayListTest.class);
suite.addTestSuite(ArraysTest.class);
suite.addTestSuite(BitSetTest.class);
diff --git a/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
new file mode 100644
index 0000000..9915e2a
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
@@ -0,0 +1,856 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import static java.util.Arrays.asList;
+
+import com.google.gwt.core.client.JavaScriptException;
+
+import org.apache.commons.collections.TestCollection;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * Tests ArrayDeque class.
+ */
+public class ArrayDequeTest extends TestCollection {
+
+ public void testAdd() throws Exception {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertTrue(deque.add(o1));
+ checkDequeSizeAndContent(deque, o1);
+ assertTrue(deque.add(o2));
+ checkDequeSizeAndContent(deque, o1, o2);
+ assertTrue(deque.add(o3));
+ checkDequeSizeAndContent(deque, o1, o2, o3);
+
+ try {
+ deque.add(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testAddAll() throws Exception {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertTrue(deque.addAll(asList(o1, o2)));
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ try {
+ deque = new ArrayDeque<>();
+ deque.addAll(asList(o1, null, o2));
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testAddFirst() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ deque.addFirst(o1);
+ checkDequeSizeAndContent(deque, o1);
+ deque.addFirst(o2);
+ checkDequeSizeAndContent(deque, o2, o1);
+ deque.addFirst(o3);
+ checkDequeSizeAndContent(deque, o3, o2, o1);
+
+ try {
+ deque.addFirst(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testAddLast() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ deque.addLast(o1);
+ checkDequeSizeAndContent(deque, o1);
+ deque.addLast(o2);
+ checkDequeSizeAndContent(deque, o1, o2);
+ deque.addLast(o3);
+ checkDequeSizeAndContent(deque, o1, o2, o3);
+
+ try {
+ deque.addLast(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testConstructorFromCollection() {
+ assertEquals(0, new ArrayDeque<>(new ArrayList<>()).size());
+ try {
+ new ArrayDeque<>(null);
+ fail();
+ } catch (NullPointerException expected) {
+ // expected
+ } catch (JavaScriptException expected) {
+ // expected
+ }
+
+ try {
+ new ArrayDeque<>(asList(new Object(), null, new Object()));
+ fail();
+ } catch (NullPointerException expected) { }
+
+ Collection<Object> collection = new ArrayList<>(asList(getFullNonNullElements()));
+ checkDequeSizeAndContent(new ArrayDeque<>(collection), getFullNonNullElements());
+ }
+
+ public void testContains() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertFalse(deque.contains(o3));
+ assertFalse(deque.contains(null));
+ assertTrue(deque.add(o1));
+ assertTrue(deque.add(o2));
+ assertTrue(deque.add(o1));
+ assertTrue(deque.add(o3));
+ assertTrue(deque.contains(o1));
+ assertTrue(deque.contains(o2));
+ assertTrue(deque.contains(o3));
+ assertFalse(deque.contains(null));
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ assertFalse(deque.contains(o1));
+ assertFalse(deque.contains(o2));
+ assertFalse(deque.contains(o3));
+ }
+
+ public void testDescendingIterator() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ Iterator<Object> it = deque.descendingIterator();
+ assertFalse(it.hasNext());
+ try {
+ it.next();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ it = deque.descendingIterator();
+ assertTrue(it.hasNext());
+ assertEquals(o3, it.next());
+ assertTrue(it.hasNext());
+ assertEquals(o2, it.next());
+ assertTrue(it.hasNext());
+ assertEquals(o1, it.next());
+ assertFalse(it.hasNext());
+ try {
+ it.next();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ checkDequeSizeAndContent(deque, o1, o2, o3);
+
+ deque = new ArrayDeque<>();
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ it = deque.descendingIterator();
+ assertTrue(it.hasNext());
+ assertEquals(o3, it.next());
+ it.remove();
+ assertEquals(2, deque.size());
+ assertTrue(it.hasNext());
+ assertEquals(o2, it.next());
+ assertTrue(it.hasNext());
+ assertEquals(o1, it.next());
+ it.remove();
+ checkDequeSizeAndContent(deque, o2);
+ }
+
+ public void testElement() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.element();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.element());
+ checkDequeSizeAndContent(deque, o1);
+
+ deque.add(o2);
+ assertEquals(o1, deque.element());
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ try {
+ deque.element();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testFailFastIterator() {
+ ArrayDeque<Object> deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ Iterator<Object> it = deque.iterator();
+ it.next();
+ deque.removeFirst();
+ try {
+ it.next();
+ } catch (ConcurrentModificationException e) {
+ fail();
+ }
+ deque.removeLast();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.iterator();
+ it.next();
+ deque.clear();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.iterator();
+ it.next();
+ deque.addFirst(new Object());
+ try {
+ it.next();
+ } catch (ConcurrentModificationException e) {
+ fail();
+ }
+ deque.addLast(new Object());
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.iterator();
+ it.next();
+ it.next();
+ deque.removeFirst();
+ try {
+ it.remove();
+ } catch (ConcurrentModificationException e) {
+ fail();
+ }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.iterator();
+ it.next();
+ it.next();
+ deque.removeFirst();
+ deque.removeFirst();
+ try {
+ it.remove();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+ }
+
+ public void testFailFastDescendingIterator() {
+ ArrayDeque<Object> deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ Iterator<Object> it = deque.descendingIterator();
+ it.next();
+ deque.removeLast();
+ try {
+ it.next();
+ } catch (ConcurrentModificationException e) {
+ fail();
+ }
+ deque.removeFirst();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.descendingIterator();
+ it.next();
+ deque.clear();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.descendingIterator();
+ it.next();
+ deque.addLast(new Object());
+ try {
+ it.next();
+ } catch (ConcurrentModificationException e) {
+ fail();
+ }
+ deque.addFirst(new Object());
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.descendingIterator();
+ it.next();
+ it.next();
+ deque.removeLast();
+ try {
+ it.remove();
+ } catch (ConcurrentModificationException e) {
+ fail();
+ }
+
+ deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+ it = deque.descendingIterator();
+ it.next();
+ it.next();
+ deque.removeLast();
+ deque.removeLast();
+ try {
+ it.remove();
+ fail();
+ } catch (ConcurrentModificationException expected) { }
+ }
+
+ public void testGetFirst() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.getFirst();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.getFirst());
+ checkDequeSizeAndContent(deque, o1);
+
+ deque.add(o2);
+ assertEquals(o1, deque.getFirst());
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ try {
+ deque.getFirst();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testGetLast() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.getLast();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.getLast());
+ checkDequeSizeAndContent(deque, o1);
+
+ deque.add(o2);
+ assertEquals(o2, deque.getLast());
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ try {
+ deque.getLast();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testOffer() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertTrue(deque.offer(o1));
+ checkDequeSizeAndContent(deque, o1);
+ assertTrue(deque.offer(o2));
+ checkDequeSizeAndContent(deque, o1, o2);
+ assertTrue(deque.offer(o3));
+ checkDequeSizeAndContent(deque, o1, o2, o3);
+
+ try {
+ deque.offer(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testOfferFirst() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertTrue(deque.offerFirst(o1));
+ checkDequeSizeAndContent(deque, o1);
+ assertTrue(deque.offerFirst(o2));
+ checkDequeSizeAndContent(deque, o2, o1);
+ assertTrue(deque.offerFirst(o3));
+ checkDequeSizeAndContent(deque, o3, o2, o1);
+
+ try {
+ deque.offerFirst(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testOfferLast() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertTrue(deque.offerLast(o1));
+ checkDequeSizeAndContent(deque, o1);
+ assertTrue(deque.offerLast(o2));
+ checkDequeSizeAndContent(deque, o1, o2);
+ assertTrue(deque.offerLast(o3));
+ checkDequeSizeAndContent(deque, o1, o2, o3);
+
+ try {
+ deque.offerLast(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testPeek() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertNull(deque.peek());
+
+ deque.add(o1);
+ assertEquals(o1, deque.peek());
+ checkDequeSizeAndContent(deque, o1);
+
+ deque.add(o2);
+ assertEquals(o1, deque.peek());
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ deque.addFirst(o3);
+ assertEquals(o3, deque.peek());
+ checkDequeSizeAndContent(deque, o3, o1, o2);
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ assertNull(deque.peek());
+ }
+
+ public void testPeekFirst() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertNull(deque.peekFirst());
+
+ deque.add(o1);
+ assertEquals(o1, deque.peekFirst());
+ checkDequeSizeAndContent(deque, o1);
+
+ deque.add(o2);
+ assertEquals(o1, deque.peekFirst());
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ deque.addFirst(o3);
+ assertEquals(o3, deque.peekFirst());
+ checkDequeSizeAndContent(deque, o3, o1, o2);
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ assertNull(deque.peekFirst());
+ }
+
+ public void testPeekLast() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertNull(deque.peekLast());
+
+ deque.add(o1);
+ assertEquals(o1, deque.peekLast());
+ checkDequeSizeAndContent(deque, o1);
+
+ deque.add(o2);
+ assertEquals(o2, deque.peekLast());
+ checkDequeSizeAndContent(deque, o1, o2);
+
+ deque.addFirst(o3);
+ assertEquals(o2, deque.peekLast());
+ checkDequeSizeAndContent(deque, o3, o1, o2);
+
+ deque.clear();
+ assertTrue(deque.isEmpty());
+ assertNull(deque.peekLast());
+ }
+
+ public void testPoll() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertNull(deque.poll());
+
+ deque.add(o1);
+ assertEquals(o1, deque.poll());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o1, deque.poll());
+ checkDequeSizeAndContent(deque, o2);
+ assertEquals(o2, deque.poll());
+ assertTrue(deque.isEmpty());
+ assertNull(deque.poll());
+ }
+
+ public void testPollFirst() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertNull(deque.pollFirst());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ assertEquals(o1, deque.pollFirst());
+ assertTrue(deque.isEmpty());
+ assertNull(deque.pollFirst());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o1, deque.pollFirst());
+ checkDequeSizeAndContent(deque, o2);
+ assertEquals(o2, deque.pollFirst());
+ assertTrue(deque.isEmpty());
+ assertNull(deque.pollFirst());
+ }
+
+ public void testPollLast() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertNull(deque.pollLast());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ assertEquals(o1, deque.pollLast());
+ assertTrue(deque.isEmpty());
+ assertNull(deque.pollFirst());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o2, deque.pollLast());
+ checkDequeSizeAndContent(deque, o1);
+ assertEquals(o1, deque.pollLast());
+ assertTrue(deque.isEmpty());
+ assertNull(deque.pollLast());
+ }
+
+ public void testPop() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.pop();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.pop());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o1, deque.pop());
+ checkDequeSizeAndContent(deque, o2);
+ assertEquals(o2, deque.pop());
+ assertTrue(deque.isEmpty());
+ try {
+ deque.pop();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testPush() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ deque.push(o1);
+ checkDequeSizeAndContent(deque, o1);
+ deque.push(o2);
+ checkDequeSizeAndContent(deque, o2, o1);
+ deque.push(o3);
+ checkDequeSizeAndContent(deque, o3, o2, o1);
+
+ try {
+ deque.push(null);
+ fail();
+ } catch (NullPointerException expected) { }
+ }
+
+ public void testRemove() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.remove();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.remove());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o1, deque.remove());
+ checkDequeSizeAndContent(deque, o2);
+ assertEquals(o2, deque.removeFirst());
+ assertTrue(deque.isEmpty());
+
+ try {
+ deque.remove();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testRemoveElement() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertFalse(deque.remove(o1));
+
+ deque.add(o1);
+ assertTrue(deque.remove(o1));
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertTrue(deque.remove(o1));
+ checkDequeSizeAndContent(deque, o2);
+ assertTrue(deque.remove(o2));
+ assertTrue(deque.isEmpty());
+
+ assertFalse(deque.remove(null));
+ }
+
+ public void testRemoveFirst() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.removeFirst();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.removeFirst());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o1, deque.removeFirst());
+ checkDequeSizeAndContent(deque, o2);
+ assertEquals(o2, deque.removeFirst());
+ assertTrue(deque.isEmpty());
+
+ try {
+ deque.removeFirst();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testRemoveFirstOccurrence() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertFalse(deque.removeFirstOccurrence(o1));
+
+ deque.add(o1);
+ assertTrue(deque.removeFirstOccurrence(o1));
+ assertTrue(deque.isEmpty());
+
+ deque = new ArrayDeque<>();
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ assertTrue(deque.removeFirstOccurrence(o2));
+ checkDequeSizeAndContent(deque, o1, o3);
+
+ deque = new ArrayDeque<>();
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ assertTrue(deque.removeFirstOccurrence(o2));
+ checkDequeSizeAndContent(deque, o1, o3, o1, o2, o3);
+ assertTrue(deque.removeFirstOccurrence(o2));
+ checkDequeSizeAndContent(deque, o1, o3, o1, o3);
+ assertTrue(deque.removeFirstOccurrence(o1));
+ checkDequeSizeAndContent(deque, o3, o1, o3);
+ assertTrue(deque.removeFirstOccurrence(o1));
+ checkDequeSizeAndContent(deque, o3, o3);
+ assertFalse(deque.removeFirstOccurrence(o1));
+
+ assertFalse(deque.removeFirstOccurrence(null));
+ }
+
+ public void testRemoveLast() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ try {
+ deque.removeLast();
+ fail();
+ } catch (NoSuchElementException expected) { }
+
+ deque.add(o1);
+ assertEquals(o1, deque.removeLast());
+ assertTrue(deque.isEmpty());
+
+ deque.add(o1);
+ deque.add(o2);
+ assertEquals(o2, deque.removeLast());
+ checkDequeSizeAndContent(deque, o1);
+ assertEquals(o1, deque.removeLast());
+ assertEquals(0, deque.size());
+
+ try {
+ deque.removeLast();
+ fail();
+ } catch (NoSuchElementException expected) { }
+ }
+
+ public void testRemoveLastOccurrence() {
+ Object o1 = new Object();
+ Object o2 = new Object();
+ Object o3 = new Object();
+
+ ArrayDeque<Object> deque = new ArrayDeque<>();
+ assertFalse(deque.removeLastOccurrence(o1));
+
+ deque.add(o1);
+ assertTrue(deque.removeLastOccurrence(o1));
+ assertTrue(deque.isEmpty());
+
+ deque = new ArrayDeque<>();
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ assertTrue(deque.removeLastOccurrence(o2));
+ checkDequeSizeAndContent(deque, o1, o3);
+
+ deque = new ArrayDeque<>();
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ deque.add(o1);
+ deque.add(o2);
+ deque.add(o3);
+ assertTrue(deque.removeLastOccurrence(o2));
+ checkDequeSizeAndContent(deque, o1, o2, o3, o1, o3);
+ assertTrue(deque.removeLastOccurrence(o2));
+ checkDequeSizeAndContent(deque, o1, o3, o1, o3);
+ assertTrue(deque.removeLastOccurrence(o3));
+ checkDequeSizeAndContent(deque, o1, o3, o1);
+ assertTrue(deque.removeLastOccurrence(o3));
+ checkDequeSizeAndContent(deque, o1, o1);
+ assertFalse(deque.removeLastOccurrence(o3));
+
+ assertFalse(deque.removeLastOccurrence(null));
+ }
+
+ /**
+ * Null elements are prohibited in ArrayDeque.
+ */
+ @Override
+ protected Object[] getFullElements() {
+ return getFullNonNullElements();
+ }
+
+ @Override
+ protected Collection makeConfirmedCollection() {
+ return new ArrayList<>();
+ }
+
+ @Override
+ protected Collection makeConfirmedFullCollection() {
+ return new ArrayList<>(asList(getFullElements()));
+ }
+
+ @Override
+ protected Collection makeCollection() {
+ return new ArrayDeque<>();
+ }
+
+ private void checkDequeSizeAndContent(Deque<?> deque, Object... expected) {
+ assertEquals(expected.length, deque.size());
+ int i = 0;
+ for (Object e : deque) {
+ assertEquals(expected[i++], e);
+ }
+ assertEquals(expected.length, i);
+ }
+}
