--- jsr166/src/main/java/util/ArrayDeque.java	2013/05/02 06:02:17	1.55
+++ jsr166/src/main/java/util/ArrayDeque.java	2016/10/18 00:33:05	1.77
@@ -4,9 +4,11 @@
  */
 
 package java.util;
+
 import java.io.Serializable;
 import java.util.function.Consumer;
-import java.util.stream.Stream;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
 
 /**
  * Resizable-array implementation of the {@link Deque} interface.  Array
@@ -52,87 +54,105 @@ import java.util.stream.Stream;
  * Java Collections Framework</a>.
  *
  * @author  Josh Bloch and Doug Lea
+ * @param <E> the type of elements held in this deque
  * @since   1.6
- * @param <E> the type of elements held in this collection
  */
 public class ArrayDeque<E> extends AbstractCollection<E>
                            implements Deque<E>, Cloneable, Serializable
 {
     /**
      * The array in which the elements of the deque are stored.
-     * The capacity of the deque is the length of this array, which is
-     * always a power of two. The array is never allowed to become
-     * full, except transiently within an addX method where it is
-     * resized (see doubleCapacity) immediately upon becoming full,
-     * thus avoiding head and tail wrapping around to equal each
-     * other.  We also guarantee that all array cells not holding
-     * deque elements are always null.
+     * We guarantee that all array cells not holding deque elements
+     * are always null.
      */
-    transient Object[] elements; // non-private to simplify nested class access
+    transient Object[] elements;
 
     /**
      * 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.
+     * arbitrary number 0 <= head < elements.length if the deque is empty.
      */
     transient int head;
 
+    /** Number of elements in this collection. */
+    transient int size;
+
     /**
-     * The index at which the next element would be added to the tail
-     * of the deque (via addLast(E), add(E), or push(E)).
+     * The maximum size of array to allocate.
+     * Some VMs reserve some header words in an array.
+     * Attempts to allocate larger arrays may result in
+     * OutOfMemoryError: Requested array size exceeds VM limit
      */
-    transient int tail;
+    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
     /**
-     * The minimum capacity that we'll use for a newly created deque.
-     * Must be a power of 2.
+     * Increases the capacity of this deque by at least the given amount.
+     *
+     * @param needed the required minimum extra capacity; must be positive
      */
-    private static final int MIN_INITIAL_CAPACITY = 8;
+    private void grow(int needed) {
+        // overflow-conscious code
+        // checkInvariants();
+        int oldCapacity = elements.length;
+        int newCapacity;
+        // Double size if small; else grow by 50%
+        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
+        if (jump < needed
+            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
+            newCapacity = newCapacity(needed, jump);
+        elements = Arrays.copyOf(elements, newCapacity);
+        if (oldCapacity - head < size) {
+            // wrap around; slide first leg forward to end of array
+            int newSpace = newCapacity - oldCapacity;
+            System.arraycopy(elements, head,
+                             elements, head + newSpace,
+                             oldCapacity - head);
+            Arrays.fill(elements, head, head + newSpace, null);
+            head += newSpace;
+        }
+        // checkInvariants();
+    }
 
-    // ******  Array allocation and resizing utilities ******
+    /** Capacity calculation for edge conditions, especially overflow. */
+    private int newCapacity(int needed, int jump) {
+        int oldCapacity = elements.length;
+        int minCapacity;
+        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
+            if (minCapacity < 0)
+                throw new IllegalStateException("Sorry, deque too big");
+            return Integer.MAX_VALUE;
+        }
+        if (needed > jump)
+            return minCapacity;
+        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
+            ? oldCapacity + jump
+            : MAX_ARRAY_SIZE;
+    }
 
     /**
-     * Allocates empty array to hold the given number of elements.
+     * Increases the internal storage of this collection, if necessary,
+     * to ensure that it can hold at least the given number of elements.
      *
-     * @param numElements  the number of elements to hold
+     * @param minCapacity the desired minimum capacity
+     * @since 9
      */
-    private void allocateElements(int numElements) {
-        int initialCapacity = MIN_INITIAL_CAPACITY;
-        // Find the best power of two to hold elements.
-        // Tests "<=" because arrays aren't kept full.
-        if (numElements >= initialCapacity) {
-            initialCapacity = numElements;
-            initialCapacity |= (initialCapacity >>>  1);
-            initialCapacity |= (initialCapacity >>>  2);
-            initialCapacity |= (initialCapacity >>>  4);
-            initialCapacity |= (initialCapacity >>>  8);
-            initialCapacity |= (initialCapacity >>> 16);
-            initialCapacity++;
-
-            if (initialCapacity < 0)   // Too many elements, must back off
-                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
-        }
-        elements = new Object[initialCapacity];
+    public void ensureCapacity(int minCapacity) {
+        if (minCapacity > elements.length)
+            grow(minCapacity - elements.length);
+        // checkInvariants();
     }
 
     /**
-     * Doubles the capacity of this deque.  Call only when full, i.e.,
-     * when head and tail have wrapped around to become equal.
+     * Minimizes the internal storage of this collection.
+     *
+     * @since 9
      */
-    private void doubleCapacity() {
-        assert head == tail;
-        int p = head;
-        int n = elements.length;
-        int r = n - p; // number of elements to the right of p
-        int newCapacity = n << 1;
-        if (newCapacity < 0)
-            throw new IllegalStateException("Sorry, deque too big");
-        Object[] a = new Object[newCapacity];
-        System.arraycopy(elements, p, a, 0, r);
-        System.arraycopy(elements, 0, a, r, p);
-        elements = a;
-        head = 0;
-        tail = n;
+    public void trimToSize() {
+        if (size < elements.length) {
+            elements = toArray();
+            head = 0;
+        }
+        // checkInvariants();
     }
 
     /**
@@ -147,10 +167,10 @@ public class ArrayDeque<E> extends Abstr
      * Constructs an empty array deque with an initial capacity
      * sufficient to hold the specified number of elements.
      *
-     * @param numElements  lower bound on initial capacity of the deque
+     * @param numElements lower bound on initial capacity of the deque
      */
     public ArrayDeque(int numElements) {
-        allocateElements(numElements);
+        elements = new Object[numElements];
     }
 
     /**
@@ -164,8 +184,70 @@ public class ArrayDeque<E> extends Abstr
      * @throws NullPointerException if the specified collection is null
      */
     public ArrayDeque(Collection<? extends E> c) {
-        allocateElements(c.size());
-        addAll(c);
+        Object[] elements = c.toArray();
+        // defend against c.toArray (incorrectly) not returning Object[]
+        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
+        if (elements.getClass() != Object[].class)
+            elements = Arrays.copyOf(elements, size, Object[].class);
+        for (Object obj : elements)
+            Objects.requireNonNull(obj);
+        size = elements.length;
+        this.elements = elements;
+    }
+
+    /**
+     * Returns the array index of the last element.
+     * May return invalid index -1 if there are no elements.
+     */
+    final int tail() {
+        return add(head, size - 1, elements.length);
+    }
+
+    /**
+     * Adds i and j, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
+     */
+    static final int add(int i, int j, int modulus) {
+        if ((i += j) - modulus >= 0) i -= modulus;
+        return i;
+    }
+
+    /**
+     * Increments i, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus.
+     */
+    static final int inc(int i, int modulus) {
+        if (++i == modulus) i = 0;
+        return i;
+    }
+
+    /**
+     * Decrements i, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus.
+     */
+    static final int dec(int i, int modulus) {
+        if (--i < 0) i += modulus;
+        return i;
+    }
+
+    /**
+     * Returns element at array index i.
+     */
+    @SuppressWarnings("unchecked")
+    final E elementAt(int i) {
+        return (E) elements[i];
+    }
+
+    /**
+     * A version of elementAt that checks for null elements.
+     * This check doesn't catch all possible comodifications,
+     * but does catch ones that corrupt traversal.
+     */
+    E checkedElementAt(Object[] elements, int i) {
+        @SuppressWarnings("unchecked") E e = (E) elements[i];
+        if (e == null)
+            throw new ConcurrentModificationException();
+        return e;
     }
 
     // The main insertion and extraction methods are addFirst,
@@ -179,11 +261,14 @@ public class ArrayDeque<E> extends Abstr
      * @throws NullPointerException if the specified element is null
      */
     public void addFirst(E e) {
-        if (e == null)
-            throw new NullPointerException();
-        elements[head = (head - 1) & (elements.length - 1)] = e;
-        if (head == tail)
-            doubleCapacity();
+        // checkInvariants();
+        Objects.requireNonNull(e);
+        Object[] elements;
+        int capacity, s = size;
+        while (s == (capacity = (elements = this.elements).length))
+            grow(1);
+        elements[head = dec(head, capacity)] = e;
+        size = s + 1;
     }
 
     /**
@@ -195,11 +280,44 @@ public class ArrayDeque<E> extends Abstr
      * @throws NullPointerException if the specified element is null
      */
     public void addLast(E e) {
-        if (e == null)
-            throw new NullPointerException();
-        elements[tail] = e;
-        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
-            doubleCapacity();
+        // checkInvariants();
+        Objects.requireNonNull(e);
+        Object[] elements;
+        int capacity, s = size;
+        while (s == (capacity = (elements = this.elements).length))
+            grow(1);
+        elements[add(head, s, capacity)] = e;
+        size = s + 1;
+    }
+
+    /**
+     * Adds all of the elements in the specified collection at the end
+     * of this deque, as if by calling {@link #addLast} on each one,
+     * in the order that they are returned by the collection's
+     * iterator.
+     *
+     * @param c the elements to be inserted into this deque
+     * @return {@code true} if this deque changed as a result of the call
+     * @throws NullPointerException if the specified collection or any
+     *         of its elements are null
+     */
+    @Override
+    public boolean addAll(Collection<? extends E> c) {
+        // checkInvariants();
+        Object[] a, elements;
+        int len, capacity, s = size;
+        if ((len = (a = c.toArray()).length) == 0)
+            return false;
+        while ((capacity = (elements = this.elements).length) - s < len)
+            grow(len - (capacity - s));
+        int i = add(head, s, capacity);
+        for (Object x : a) {
+            Objects.requireNonNull(x);
+            elements[i] = x;
+            i = inc(i, capacity);
+            size++;
+        }
+        return true;
     }
 
     /**
@@ -230,6 +348,7 @@ public class ArrayDeque<E> extends Abstr
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E removeFirst() {
+        // checkInvariants();
         E x = pollFirst();
         if (x == null)
             throw new NoSuchElementException();
@@ -240,6 +359,7 @@ public class ArrayDeque<E> extends Abstr
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E removeLast() {
+        // checkInvariants();
         E x = pollLast();
         if (x == null)
             throw new NoSuchElementException();
@@ -247,59 +367,57 @@ public class ArrayDeque<E> extends Abstr
     }
 
     public E pollFirst() {
-        int h = head;
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[h];
-        // Element is null if deque empty
-        if (result == null)
+        // checkInvariants();
+        final int s, h;
+        if ((s = size) == 0)
             return null;
-        elements[h] = null;     // Must null out slot
-        head = (h + 1) & (elements.length - 1);
-        return result;
+        final Object[] elements = this.elements;
+        @SuppressWarnings("unchecked") E e = (E) elements[h = head];
+        elements[h] = null;
+        head = inc(h, elements.length);
+        size = s - 1;
+        return e;
     }
 
     public E pollLast() {
-        int t = (tail - 1) & (elements.length - 1);
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[t];
-        if (result == null)
+        // checkInvariants();
+        final int s, tail;
+        if ((s = size) == 0)
             return null;
-        elements[t] = null;
-        tail = t;
-        return result;
+        final Object[] elements = this.elements;
+        @SuppressWarnings("unchecked")
+        E e = (E) elements[tail = add(head, s - 1, elements.length)];
+        elements[tail] = null;
+        size = s - 1;
+        return e;
     }
 
     /**
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E getFirst() {
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[head];
-        if (result == null)
-            throw new NoSuchElementException();
-        return result;
+        // checkInvariants();
+        if (size == 0) throw new NoSuchElementException();
+        return elementAt(head);
     }
 
     /**
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E getLast() {
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[(tail - 1) & (elements.length - 1)];
-        if (result == null)
-            throw new NoSuchElementException();
-        return result;
+        // checkInvariants();
+        if (size == 0) throw new NoSuchElementException();
+        return elementAt(tail());
     }
 
-    @SuppressWarnings("unchecked")
     public E peekFirst() {
-        // elements[head] is null if deque empty
-        return (E) elements[head];
+        // checkInvariants();
+        return (size == 0) ? null : elementAt(head);
     }
 
-    @SuppressWarnings("unchecked")
     public E peekLast() {
-        return (E) elements[(tail - 1) & (elements.length - 1)];
+        // checkInvariants();
+        return (size == 0) ? null : elementAt(tail());
     }
 
     /**
@@ -315,17 +433,16 @@ public class ArrayDeque<E> extends Abstr
      * @return {@code true} if the deque contained the specified element
      */
     public boolean removeFirstOccurrence(Object o) {
-        if (o == null)
-            return false;
-        int mask = elements.length - 1;
-        int i = head;
-        Object x;
-        while ( (x = elements[i]) != null) {
-            if (o.equals(x)) {
-                delete(i);
-                return true;
+        // checkInvariants();
+        if (o != null) {
+            final Object[] elements = this.elements;
+            final int capacity = elements.length;
+            for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
+                if (o.equals(elements[i])) {
+                    delete(i);
+                    return true;
+                }
             }
-            i = (i + 1) & mask;
         }
         return false;
     }
@@ -343,17 +460,16 @@ public class ArrayDeque<E> extends Abstr
      * @return {@code true} if the deque contained the specified element
      */
     public boolean removeLastOccurrence(Object o) {
-        if (o == null)
-            return false;
-        int mask = elements.length - 1;
-        int i = (tail - 1) & mask;
-        Object x;
-        while ( (x = elements[i]) != null) {
-            if (o.equals(x)) {
-                delete(i);
-                return true;
+        if (o != null) {
+            final Object[] elements = this.elements;
+            final int capacity = elements.length;
+            for (int k = size, i = add(head, k - 1, capacity);
+                 --k >= 0; i = dec(i, capacity)) {
+                if (o.equals(elements[i])) {
+                    delete(i);
+                    return true;
+                }
             }
-            i = (i - 1) & mask;
         }
         return false;
     }
@@ -472,59 +588,52 @@ public class ArrayDeque<E> extends Abstr
         return removeFirst();
     }
 
-    private void checkInvariants() {
-        assert elements[tail] == null;
-        assert head == tail ? elements[head] == null :
-            (elements[head] != null &&
-             elements[(tail - 1) & (elements.length - 1)] != null);
-        assert elements[(head - 1) & (elements.length - 1)] == null;
-    }
-
     /**
-     * Removes the element at the specified position in the elements array,
-     * adjusting head and tail as necessary.  This can result in motion of
-     * elements backwards or forwards in the array.
+     * Removes the element at the specified position in the elements array.
+     * This can result in forward or backwards motion of array elements.
+     * We optimize for least element motion.
      *
      * <p>This method is called delete rather than remove to emphasize
      * that its semantics differ from those of {@link List#remove(int)}.
      *
      * @return true if elements moved backwards
      */
-    private boolean delete(int i) {
-        checkInvariants();
+    boolean delete(int i) {
+        // checkInvariants();
         final Object[] elements = this.elements;
-        final int mask = elements.length - 1;
+        final int capacity = elements.length;
         final int h = head;
-        final int t = tail;
-        final int front = (i - h) & mask;
-        final int back  = (t - i) & mask;
-
-        // Invariant: head <= i < tail mod circularity
-        if (front >= ((t - h) & mask))
-            throw new ConcurrentModificationException();
-
-        // Optimize for least element motion
+        int front;              // number of elements before to-be-deleted elt
+        if ((front = i - h) < 0) front += capacity;
+        final int back = size - front - 1; // number of elements after
         if (front < back) {
+            // move front elements forwards
             if (h <= i) {
                 System.arraycopy(elements, h, elements, h + 1, front);
             } else { // Wrap around
                 System.arraycopy(elements, 0, elements, 1, i);
-                elements[0] = elements[mask];
-                System.arraycopy(elements, h, elements, h + 1, mask - h);
+                elements[0] = elements[capacity - 1];
+                System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
             }
             elements[h] = null;
-            head = (h + 1) & mask;
+            head = inc(h, capacity);
+            size--;
+            // checkInvariants();
             return false;
         } else {
-            if (i < t) { // Copy the null tail as well
+            // move back elements backwards
+            int tail = tail();
+            if (i <= tail) {
                 System.arraycopy(elements, i + 1, elements, i, back);
-                tail = t - 1;
             } else { // Wrap around
-                System.arraycopy(elements, i + 1, elements, i, mask - i);
-                elements[mask] = elements[0];
-                System.arraycopy(elements, 1, elements, 0, t);
-                tail = (t - 1) & mask;
+                int firstLeg = capacity - (i + 1);
+                System.arraycopy(elements, i + 1, elements, i, firstLeg);
+                elements[capacity - 1] = elements[0];
+                System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
             }
+            elements[tail] = null;
+            size--;
+            // checkInvariants();
             return true;
         }
     }
@@ -537,7 +646,7 @@ public class ArrayDeque<E> extends Abstr
      * @return the number of elements in this deque
      */
     public int size() {
-        return (tail - head) & (elements.length - 1);
+        return size;
     }
 
     /**
@@ -546,7 +655,7 @@ public class ArrayDeque<E> extends Abstr
      * @return {@code true} if this deque contains no elements
      */
     public boolean isEmpty() {
-        return head == tail;
+        return size == 0;
     }
 
     /**
@@ -566,86 +675,242 @@ public class ArrayDeque<E> extends Abstr
     }
 
     private class DeqIterator implements Iterator<E> {
-        /**
-         * Index of element to be returned by subsequent call to next.
-         */
-        private int cursor = head;
+        /** Index of element to be returned by subsequent call to next. */
+        int cursor;
 
-        /**
-         * Tail recorded at construction (also in remove), to stop
-         * iterator and also to check for comodification.
-         */
-        private int fence = tail;
+        /** Number of elements yet to be returned. */
+        int remaining = size;
 
         /**
          * Index of element returned by most recent call to next.
          * Reset to -1 if element is deleted by a call to remove.
          */
-        private int lastRet = -1;
+        int lastRet = -1;
+
+        DeqIterator() { cursor = head; }
+
+        int advance(int i, int modulus) {
+            return inc(i, modulus);
+        }
+
+        void doRemove() {
+            if (delete(lastRet))
+                // if left-shifted, undo advance in next()
+                cursor = dec(cursor, elements.length);
+        }
 
-        public boolean hasNext() {
-            return cursor != fence;
+        public final boolean hasNext() {
+            return remaining > 0;
         }
 
-        public E next() {
-            if (cursor == fence)
+        public final E next() {
+            if (remaining == 0)
                 throw new NoSuchElementException();
-            @SuppressWarnings("unchecked")
-            E result = (E) elements[cursor];
-            // This check doesn't catch all possible comodifications,
-            // but does catch the ones that corrupt traversal
-            if (tail != fence || result == null)
-                throw new ConcurrentModificationException();
+            E e = checkedElementAt(elements, cursor);
             lastRet = cursor;
-            cursor = (cursor + 1) & (elements.length - 1);
-            return result;
+            cursor = advance(cursor, elements.length);
+            remaining--;
+            return e;
         }
 
-        public void remove() {
+        public final void remove() {
             if (lastRet < 0)
                 throw new IllegalStateException();
-            if (delete(lastRet)) { // if left-shifted, undo increment in next()
-                cursor = (cursor - 1) & (elements.length - 1);
-                fence = tail;
-            }
+            doRemove();
             lastRet = -1;
         }
+
+        public final void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            final Object[] elements = ArrayDeque.this.elements;
+            final int capacity = elements.length;
+            int k = remaining;
+            remaining = 0;
+            for (int i = cursor; --k >= 0; i = advance(i, capacity))
+                action.accept(checkedElementAt(elements, i));
+        }
+    }
+
+    private class DescendingIterator extends DeqIterator {
+        DescendingIterator() { cursor = tail(); }
+
+        @Override int advance(int i, int modulus) {
+            return dec(i, modulus);
+        }
+
+        @Override void doRemove() {
+            if (!delete(lastRet))
+                // if right-shifted, undo advance in next
+                cursor = inc(cursor, elements.length);
+        }
     }
 
     /**
-     * This class is nearly a mirror-image of DeqIterator, using tail
-     * instead of head for initial cursor, and head instead of tail
-     * for fence.
+     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
+     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
+     * deque.
+     *
+     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
+     * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
+     * {@link Spliterator#NONNULL}.  Overriding implementations should document
+     * the reporting of additional characteristic values.
+     *
+     * @return a {@code Spliterator} over the elements in this deque
+     * @since 1.8
      */
-    private class DescendingIterator implements Iterator<E> {
-        private int cursor = tail;
-        private int fence = head;
-        private int lastRet = -1;
+    public Spliterator<E> spliterator() {
+        return new ArrayDequeSpliterator();
+    }
 
-        public boolean hasNext() {
-            return cursor != fence;
+    final class ArrayDequeSpliterator implements Spliterator<E> {
+        private int cursor;
+        private int remaining; // -1 until late-binding first use
+
+        /** Constructs late-binding spliterator over all elements. */
+        ArrayDequeSpliterator() {
+            this.remaining = -1;
         }
 
-        public E next() {
-            if (cursor == fence)
-                throw new NoSuchElementException();
-            cursor = (cursor - 1) & (elements.length - 1);
-            @SuppressWarnings("unchecked")
-            E result = (E) elements[cursor];
-            if (head != fence || result == null)
-                throw new ConcurrentModificationException();
-            lastRet = cursor;
-            return result;
+        /** Constructs spliterator over the given slice. */
+        ArrayDequeSpliterator(int cursor, int count) {
+            this.cursor = cursor;
+            this.remaining = count;
         }
 
-        public void remove() {
-            if (lastRet < 0)
-                throw new IllegalStateException();
-            if (!delete(lastRet)) {
-                cursor = (cursor + 1) & (elements.length - 1);
-                fence = head;
+        /** Ensures late-binding initialization; then returns remaining. */
+        private int remaining() {
+            if (remaining < 0) {
+                cursor = head;
+                remaining = size;
             }
-            lastRet = -1;
+            return remaining;
+        }
+
+        public ArrayDequeSpliterator trySplit() {
+            final int mid;
+            if ((mid = remaining() >> 1) > 0) {
+                int oldCursor = cursor;
+                cursor = add(cursor, mid, elements.length);
+                remaining -= mid;
+                return new ArrayDequeSpliterator(oldCursor, mid);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            final Object[] elements = ArrayDeque.this.elements;
+            final int capacity = elements.length;
+            int k = remaining();
+            remaining = 0;
+            for (int i = cursor; --k >= 0; i = inc(i, capacity))
+                action.accept(checkedElementAt(elements, i));
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            if (remaining() == 0)
+                return false;
+            action.accept(checkedElementAt(elements, cursor));
+            cursor = inc(cursor, elements.length);
+            remaining--;
+            return true;
+        }
+
+        public long estimateSize() {
+            return remaining();
+        }
+
+        public int characteristics() {
+            return Spliterator.NONNULL
+                | Spliterator.ORDERED
+                | Spliterator.SIZED
+                | Spliterator.SUBSIZED;
+        }
+    }
+
+    @Override
+    public void forEach(Consumer<? super E> action) {
+        // checkInvariants();
+        Objects.requireNonNull(action);
+        final Object[] elements = this.elements;
+        final int capacity = elements.length;
+        for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
+            action.accept(elementAt(i));
+        // checkInvariants();
+    }
+
+    /**
+     * Replaces each element of this deque with the result of applying the
+     * operator to that element, as specified by {@link List#replaceAll}.
+     *
+     * @param operator the operator to apply to each element
+     * @since 9
+     */
+    public void replaceAll(UnaryOperator<E> operator) {
+        Objects.requireNonNull(operator);
+        final Object[] elements = this.elements;
+        final int capacity = elements.length;
+        for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
+            elements[i] = operator.apply(elementAt(i));
+        // checkInvariants();
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    @Override
+    public boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        return bulkRemove(filter);
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    @Override
+    public boolean removeAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> c.contains(e));
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    @Override
+    public boolean retainAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> !c.contains(e));
+    }
+
+    /** Implementation of bulk remove methods. */
+    private boolean bulkRemove(Predicate<? super E> filter) {
+        // checkInvariants();
+        final Object[] elements = this.elements;
+        final int capacity = elements.length;
+        int i = head, j = i, remaining = size, deleted = 0;
+        try {
+            for (; remaining > 0; remaining--, i = inc(i, capacity)) {
+                @SuppressWarnings("unchecked") E e = (E) elements[i];
+                if (filter.test(e))
+                    deleted++;
+                else {
+                    if (j != i)
+                        elements[j] = e;
+                    j = inc(j, capacity);
+                }
+            }
+            return deleted > 0;
+        } catch (Throwable ex) {
+            for (; remaining > 0;
+                 remaining--, i = inc(i, capacity), j = inc(j, capacity))
+                elements[j] = elements[i];
+            throw ex;
+        } finally {
+            size -= deleted;
+            for (; --deleted >= 0; j = inc(j, capacity))
+                elements[j] = null;
+            // checkInvariants();
         }
     }
 
@@ -658,15 +923,12 @@ public class ArrayDeque<E> extends Abstr
      * @return {@code true} if this deque contains the specified element
      */
     public boolean contains(Object o) {
-        if (o == null)
-            return false;
-        int mask = elements.length - 1;
-        int i = head;
-        Object x;
-        while ( (x = elements[i]) != null) {
-            if (o.equals(x))
-                return true;
-            i = (i + 1) & mask;
+        if (o != null) {
+            final Object[] elements = this.elements;
+            final int capacity = elements.length;
+            for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
+                if (o.equals(elements[i]))
+                    return true;
         }
         return false;
     }
@@ -693,17 +955,18 @@ public class ArrayDeque<E> extends Abstr
      * The deque will be empty after this call returns.
      */
     public void clear() {
-        int h = head;
-        int t = tail;
-        if (h != t) { // clear all cells
-            head = tail = 0;
-            int i = h;
-            int mask = elements.length - 1;
-            do {
-                elements[i] = null;
-                i = (i + 1) & mask;
-            } while (i != t);
+        final Object[] elements = this.elements;
+        final int capacity = elements.length;
+        final int h = this.head;
+        final int s = size;
+        if (capacity - h >= s)
+            Arrays.fill(elements, h, h + s, null);
+        else {
+            Arrays.fill(elements, h, capacity, null);
+            Arrays.fill(elements, 0, s - capacity + h, null);
         }
+        size = head = 0;
+        // checkInvariants();
     }
 
     /**
@@ -721,12 +984,10 @@ public class ArrayDeque<E> extends Abstr
      */
     public Object[] toArray() {
         final int head = this.head;
-        final int tail = this.tail;
-        boolean wrap = (tail < head);
-        int end = wrap ? tail + elements.length : tail;
-        Object[] a = Arrays.copyOfRange(elements, head, end);
-        if (wrap)
-            System.arraycopy(elements, 0, a, elements.length - head, tail);
+        final int firstLeg;
+        Object[] a = Arrays.copyOfRange(elements, head, head + size);
+        if ((firstLeg = elements.length - head) < size)
+            System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
         return a;
     }
 
@@ -752,7 +1013,7 @@ public class ArrayDeque<E> extends Abstr
      * The following code can be used to dump the deque into a newly
      * allocated array of {@code String}:
      *
-     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
+     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
      *
      * Note that {@code toArray(new Object[0])} is identical in function to
      * {@code toArray()}.
@@ -768,22 +1029,20 @@ public class ArrayDeque<E> extends Abstr
      */
     @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
+        final Object[] elements = this.elements;
         final int head = this.head;
-        final int tail = this.tail;
-        boolean wrap = (tail < head);
-        int size = (tail - head) + (wrap ? elements.length : 0);
-        int firstLeg = size - (wrap ? tail : 0);
-        int len = a.length;
-        if (size > len) {
+        final int firstLeg;
+        boolean wrap = (firstLeg = elements.length - head) < size;
+        if (size > a.length) {
             a = (T[]) Arrays.copyOfRange(elements, head, head + size,
                                          a.getClass());
         } else {
-            System.arraycopy(elements, head, a, 0, firstLeg);
-            if (size < len)
+            System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
+            if (size < a.length)
                 a[size] = null;
         }
         if (wrap)
-            System.arraycopy(elements, 0, a, firstLeg, tail);
+            System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
         return a;
     }
 
@@ -810,6 +1069,8 @@ public class ArrayDeque<E> extends Abstr
     /**
      * Saves this deque to a stream (that is, serializes it).
      *
+     * @param s the stream
+     * @throws java.io.IOException if an I/O error occurs
      * @serialData The current size ({@code int}) of the deque,
      * followed by all of its elements (each an object reference) in
      * first-to-last order.
@@ -819,110 +1080,52 @@ public class ArrayDeque<E> extends Abstr
         s.defaultWriteObject();
 
         // Write out size
-        s.writeInt(size());
+        s.writeInt(size);
 
         // Write out elements in order.
-        int mask = elements.length - 1;
-        for (int i = head; i != tail; i = (i + 1) & mask)
+        final Object[] elements = this.elements;
+        final int capacity = elements.length;
+        for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
             s.writeObject(elements[i]);
     }
 
     /**
      * Reconstitutes this deque from a stream (that is, deserializes it).
+     * @param s the stream
+     * @throws ClassNotFoundException if the class of a serialized object
+     *         could not be found
+     * @throws java.io.IOException if an I/O error occurs
      */
     private void readObject(java.io.ObjectInputStream s)
             throws java.io.IOException, ClassNotFoundException {
         s.defaultReadObject();
 
         // Read in size and allocate array
-        int size = s.readInt();
-        allocateElements(size);
-        head = 0;
-        tail = size;
+        elements = new Object[size = s.readInt()];
 
         // Read in all elements in the proper order.
         for (int i = 0; i < size; i++)
             elements[i] = s.readObject();
     }
 
-    public Spliterator<E> spliterator() {
-        return new DeqSpliterator<E>(this, -1, -1);
-    }
-
-    static final class DeqSpliterator<E> implements Spliterator<E> {
-        private final ArrayDeque<E> deq;
-        private int fence;  // -1 until first use
-        private int index;  // current index, modified on traverse/split
-
-        /** Creates new spliterator covering the given array and range */
-        DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
-            this.deq = deq;
-            this.index = origin;
-            this.fence = fence;
-        }
-
-        private int getFence() { // force initialization
-            int t;
-            if ((t = fence) < 0) {
-                t = fence = deq.tail;
-                index = deq.head;
-            }
-            return t;
-        }
-
-        public Spliterator<E> trySplit() {
-            int t = getFence(), h = index, n = deq.elements.length;
-            if (h != t && ((h + 1) & (n - 1)) != t) {
-                if (h > t)
-                    t += n;
-                int m = ((h + t) >>> 1) & (n - 1);
-                return new DeqSpliterator<>(deq, h, index = m);
-            }
-            return null;
-        }
-
-        public void forEachRemaining(Consumer<? super E> consumer) {
-            if (consumer == null)
-                throw new NullPointerException();
-            Object[] a = deq.elements;
-            int m = a.length - 1, f = getFence(), i = index;
-            index = f;
-            while (i != f) {
-                @SuppressWarnings("unchecked") E e = (E)a[i];
-                i = (i + 1) & m;
-                if (e == null)
-                    throw new ConcurrentModificationException();
-                consumer.accept(e);
-            }
-        }
-
-        public boolean tryAdvance(Consumer<? super E> consumer) {
-            if (consumer == null)
-                throw new NullPointerException();
-            Object[] a = deq.elements;
-            int m = a.length - 1, f = getFence(), i = index;
-            if (i != fence) {
-                @SuppressWarnings("unchecked") E e = (E)a[i];
-                index = (i + 1) & m;
-                if (e == null)
-                    throw new ConcurrentModificationException();
-                consumer.accept(e);
-                return true;
-            }
-            return false;
-        }
-
-        public long estimateSize() {
-            int n = getFence() - index;
-            if (n < 0)
-                n += deq.elements.length;
-            return (long) n;
-        }
-
-        @Override
-        public int characteristics() {
-            return Spliterator.ORDERED | Spliterator.SIZED |
-                Spliterator.NONNULL | Spliterator.SUBSIZED;
+    /** debugging */
+    private void checkInvariants() {
+        try {
+            int capacity = elements.length;
+            assert size >= 0 && size <= capacity;
+            assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
+                                 || head < capacity);
+            assert size == 0
+                || (elements[head] != null && elements[tail()] != null);
+            assert size == capacity
+                || (elements[dec(head, capacity)] == null
+                    && elements[inc(tail(), capacity)] == null);
+        } catch (Throwable t) {
+            System.err.printf("head=%d size=%d capacity=%d%n",
+                              head, size, elements.length);
+            System.err.printf("elements=%s%n",
+                              Arrays.toString(elements));
+            throw t;
         }
     }